This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[patch] Make get_loop_exit_edges return vector


Hello,

this patch makes get_loop_exit_edges return a vector of edges, instead
of array of results + their number.  Bootstrapped & regtested on i686.

Given that the changes outside loop optimizer caused by this are
trivial, I assume I can approve this patch myself.  Just for sure,
I will wait for a while before commiting it, to allow people to
react if this is not the case (or to point out mistakes in the patch).

Zdenek

	* tree-ssa-loop-im.c (schedule_sm, determine_lsm_ref,
	hoist_memory_references, loop_suitable_for_sm, determine_lsm_loop):
	Use vector of edges instead of array.
	* tree-ssa-loop-niter.c (find_loop_niter, find_loop_niter_by_eval,
	estimate_numbers_of_iterations_loop): Ditto.
	* predict.c (predict_loops): Ditto.
	* loop-unroll.c (analyze_insns_in_loop): Ditto.
	* tree-ssa-threadupdate.c: Remove declaration of heap allocation for
	edge vectors.
	* basic-block.h: Declare heap allocation for edge vectors.
	* tree-outof-ssa.c: Ditto.
	* cfgloop.c (get_loop_exit_edges): Return vector of edges.
	* cfgloop.h (get_loop_exit_edges): Declaration changed.

Index: tree-ssa-loop-im.c
===================================================================
*** tree-ssa-loop-im.c	(revision 119015)
--- tree-ssa-loop-im.c	(working copy)
*************** get_lsm_tmp_name (tree ref)
*** 1016,1028 ****
  /* Records request for store motion of memory reference REF from LOOP.
     MEM_REFS is the list of occurrences of the reference REF inside LOOP;
     these references are rewritten by a new temporary variable.
!    Exits from the LOOP are stored in EXITS, there are N_EXITS of them.
!    The initialization of the temporary variable is put to the preheader
!    of the loop, and assignments to the reference from the temporary variable
!    are emitted to exits.  */
  
  static void
! schedule_sm (struct loop *loop, edge *exits, unsigned n_exits, tree ref,
  	     struct mem_ref_loc *mem_refs)
  {
    struct mem_ref_loc *aref;
--- 1016,1027 ----
  /* Records request for store motion of memory reference REF from LOOP.
     MEM_REFS is the list of occurrences of the reference REF inside LOOP;
     these references are rewritten by a new temporary variable.
!    Exits from the LOOP are stored in EXITS.  The initialization of the
!    temporary variable is put to the preheader of the loop, and assignments
!    to the reference from the temporary variable are emitted to exits.  */
  
  static void
! schedule_sm (struct loop *loop, VEC (edge, heap) *exits, tree ref,
  	     struct mem_ref_loc *mem_refs)
  {
    struct mem_ref_loc *aref;
*************** schedule_sm (struct loop *loop, edge *ex
*** 1030,1035 ****
--- 1029,1035 ----
    unsigned i;
    tree load, store;
    struct fmt_data fmt_data;
+   edge ex;
  
    if (dump_file && (dump_flags & TDF_DETAILS))
      {
*************** schedule_sm (struct loop *loop, edge *ex
*** 1060,1070 ****
       all dependencies.  */
    bsi_insert_on_edge (loop_latch_edge (loop), load);
  
!   for (i = 0; i < n_exits; i++)
      {
        store = build2 (MODIFY_EXPR, void_type_node,
  		      unshare_expr (ref), tmp_var);
!       bsi_insert_on_edge (exits[i], store);
      }
  }
  
--- 1060,1070 ----
       all dependencies.  */
    bsi_insert_on_edge (loop_latch_edge (loop), load);
  
!   for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
      {
        store = build2 (MODIFY_EXPR, void_type_node,
  		      unshare_expr (ref), tmp_var);
!       bsi_insert_on_edge (ex, store);
      }
  }
  
*************** schedule_sm (struct loop *loop, edge *ex
*** 1072,1083 ****
     is true, prepare the statements that load the value of the memory reference
     to a temporary variable in the loop preheader, store it back on the loop
     exits, and replace all the references inside LOOP by this temporary variable.
!    LOOP has N_EXITS stored in EXITS.  CLOBBERED_VOPS is the bitmap of virtual
     operands that are clobbered by a call or accessed through multiple references
     in loop.  */
  
  static void
! determine_lsm_ref (struct loop *loop, edge *exits, unsigned n_exits,
  		   bitmap clobbered_vops, struct mem_ref *ref)
  {
    struct mem_ref_loc *aref;
--- 1072,1083 ----
     is true, prepare the statements that load the value of the memory reference
     to a temporary variable in the loop preheader, store it back on the loop
     exits, and replace all the references inside LOOP by this temporary variable.
!    EXITS is the list of exits of LOOP.  CLOBBERED_VOPS is the bitmap of virtual
     operands that are clobbered by a call or accessed through multiple references
     in loop.  */
  
  static void
! determine_lsm_ref (struct loop *loop, VEC (edge, heap) *exits,
  		   bitmap clobbered_vops, struct mem_ref *ref)
  {
    struct mem_ref_loc *aref;
*************** determine_lsm_ref (struct loop *loop, ed
*** 1123,1157 ****
  	return;
      }
  
!   schedule_sm (loop, exits, n_exits, ref->mem, ref->locs);
  }
  
  /* Hoists memory references MEM_REFS out of LOOP.  CLOBBERED_VOPS is the list
     of vops clobbered by call in loop or accessed by multiple memory references.
!    EXITS is the list of N_EXITS exit edges of the LOOP.  */
  
  static void
  hoist_memory_references (struct loop *loop, struct mem_ref *mem_refs,
! 			 bitmap clobbered_vops, edge *exits, unsigned n_exits)
  {
    struct mem_ref *ref;
  
    for (ref = mem_refs; ref; ref = ref->next)
!     determine_lsm_ref (loop, exits, n_exits, clobbered_vops, ref);
  }
  
! /* Checks whether LOOP (with N_EXITS exits stored in EXITS array) is suitable
     for a store motion optimization (i.e. whether we can insert statement
     on its exits).  */
  
  static bool
! loop_suitable_for_sm (struct loop *loop ATTRIBUTE_UNUSED, edge *exits,
! 		      unsigned n_exits)
  {
    unsigned i;
  
!   for (i = 0; i < n_exits; i++)
!     if (exits[i]->flags & EDGE_ABNORMAL)
        return false;
  
    return true;
--- 1123,1158 ----
  	return;
      }
  
!   schedule_sm (loop, exits, ref->mem, ref->locs);
  }
  
  /* Hoists memory references MEM_REFS out of LOOP.  CLOBBERED_VOPS is the list
     of vops clobbered by call in loop or accessed by multiple memory references.
!    EXITS is the list of exit edges of the LOOP.  */
  
  static void
  hoist_memory_references (struct loop *loop, struct mem_ref *mem_refs,
! 			 bitmap clobbered_vops, VEC (edge, heap) *exits)
  {
    struct mem_ref *ref;
  
    for (ref = mem_refs; ref; ref = ref->next)
!     determine_lsm_ref (loop, exits, clobbered_vops, ref);
  }
  
! /* Checks whether LOOP (with exits stored in EXITS array) is suitable
     for a store motion optimization (i.e. whether we can insert statement
     on its exits).  */
  
  static bool
! loop_suitable_for_sm (struct loop *loop ATTRIBUTE_UNUSED,
! 		      VEC (edge, heap) *exits)
  {
    unsigned i;
+   edge ex;
  
!   for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
!     if (ex->flags & EDGE_ABNORMAL)
        return false;
  
    return true;
*************** free_mem_refs (struct mem_ref *refs)
*** 1345,1358 ****
  static void
  determine_lsm_loop (struct loop *loop)
  {
!   unsigned n_exits;
!   edge *exits = get_loop_exit_edges (loop, &n_exits);
    bitmap clobbered_vops;
    struct mem_ref *mem_refs;
  
!   if (!loop_suitable_for_sm (loop, exits, n_exits))
      {
!       free (exits);
        return;
      }
  
--- 1346,1358 ----
  static void
  determine_lsm_loop (struct loop *loop)
  {
!   VEC (edge, heap) *exits = get_loop_exit_edges (loop);
    bitmap clobbered_vops;
    struct mem_ref *mem_refs;
  
!   if (!loop_suitable_for_sm (loop, exits))
      {
!       VEC_free (edge, heap, exits);
        return;
      }
  
*************** determine_lsm_loop (struct loop *loop)
*** 1364,1373 ****
    find_more_ref_vops (mem_refs, clobbered_vops);
  
    /* Hoist all suitable memory references.  */
!   hoist_memory_references (loop, mem_refs, clobbered_vops, exits, n_exits);
  
    free_mem_refs (mem_refs);
!   free (exits);
    BITMAP_FREE (clobbered_vops);
  }
  
--- 1364,1373 ----
    find_more_ref_vops (mem_refs, clobbered_vops);
  
    /* Hoist all suitable memory references.  */
!   hoist_memory_references (loop, mem_refs, clobbered_vops, exits);
  
    free_mem_refs (mem_refs);
!   VEC_free (edge, heap, exits);
    BITMAP_FREE (clobbered_vops);
  }
  
Index: tree-ssa-threadupdate.c
===================================================================
*** tree-ssa-threadupdate.c	(revision 119015)
--- tree-ssa-threadupdate.c	(working copy)
*************** struct local_info
*** 149,155 ****
     opportunities as they are discovered.  We keep the registered
     jump threading opportunities in this vector as edge pairs
     (original_edge, target_edge).  */
- DEF_VEC_ALLOC_P(edge,heap);
  static VEC(edge,heap) *threaded_edges;
  
  
--- 149,154 ----
Index: tree-ssa-loop-niter.c
===================================================================
*** tree-ssa-loop-niter.c	(revision 119015)
--- tree-ssa-loop-niter.c	(working copy)
*************** number_of_iterations_exit (struct loop *
*** 1161,1176 ****
  tree
  find_loop_niter (struct loop *loop, edge *exit)
  {
!   unsigned n_exits, i;
!   edge *exits = get_loop_exit_edges (loop, &n_exits);
    edge ex;
    tree niter = NULL_TREE, aniter;
    struct tree_niter_desc desc;
  
    *exit = NULL;
!   for (i = 0; i < n_exits; i++)
      {
-       ex = exits[i];
        if (!just_once_each_iteration_p (loop, ex->src))
  	continue;
  
--- 1161,1175 ----
  tree
  find_loop_niter (struct loop *loop, edge *exit)
  {
!   unsigned i;
!   VEC (edge, heap) *exits = get_loop_exit_edges (loop);
    edge ex;
    tree niter = NULL_TREE, aniter;
    struct tree_niter_desc desc;
  
    *exit = NULL;
!   for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
      {
        if (!just_once_each_iteration_p (loop, ex->src))
  	continue;
  
*************** find_loop_niter (struct loop *loop, edge
*** 1217,1223 ****
  	  continue;
  	}
      }
!   free (exits);
  
    return niter ? niter : chrec_dont_know;
  }
--- 1216,1222 ----
  	  continue;
  	}
      }
!   VEC_free (edge, heap, exits);
  
    return niter ? niter : chrec_dont_know;
  }
*************** loop_niter_by_eval (struct loop *loop, e
*** 1446,1460 ****
  tree
  find_loop_niter_by_eval (struct loop *loop, edge *exit)
  {
!   unsigned n_exits, i;
!   edge *exits = get_loop_exit_edges (loop, &n_exits);
    edge ex;
    tree niter = NULL_TREE, aniter;
  
    *exit = NULL;
!   for (i = 0; i < n_exits; i++)
      {
-       ex = exits[i];
        if (!just_once_each_iteration_p (loop, ex->src))
  	continue;
  
--- 1445,1458 ----
  tree
  find_loop_niter_by_eval (struct loop *loop, edge *exit)
  {
!   unsigned i;
!   VEC (edge, heap) *exits = get_loop_exit_edges (loop);
    edge ex;
    tree niter = NULL_TREE, aniter;
  
    *exit = NULL;
!   for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
      {
        if (!just_once_each_iteration_p (loop, ex->src))
  	continue;
  
*************** find_loop_niter_by_eval (struct loop *lo
*** 1469,1475 ****
        niter = aniter;
        *exit = ex;
      }
!   free (exits);
  
    return niter ? niter : chrec_dont_know;
  }
--- 1467,1473 ----
        niter = aniter;
        *exit = ex;
      }
!   VEC_free (edge, heap, exits);
  
    return niter ? niter : chrec_dont_know;
  }
*************** infer_loop_bounds_from_undefined (struct
*** 1986,2005 ****
  static void
  estimate_numbers_of_iterations_loop (struct loop *loop)
  {
!   edge *exits;
    tree niter, type;
!   unsigned i, n_exits;
    struct tree_niter_desc niter_desc;
  
    /* Give up if we already have tried to compute an estimation.  */
    if (loop->estimate_state != EST_NOT_COMPUTED)
      return;
    loop->estimate_state = EST_NOT_AVAILABLE;
  
!   exits = get_loop_exit_edges (loop, &n_exits);
!   for (i = 0; i < n_exits; i++)
      {
!       if (!number_of_iterations_exit (loop, exits[i], &niter_desc, false))
  	continue;
  
        niter = niter_desc.niter;
--- 1984,2004 ----
  static void
  estimate_numbers_of_iterations_loop (struct loop *loop)
  {
!   VEC (edge, heap) *exits;
    tree niter, type;
!   unsigned i;
    struct tree_niter_desc niter_desc;
+   edge ex;
  
    /* Give up if we already have tried to compute an estimation.  */
    if (loop->estimate_state != EST_NOT_COMPUTED)
      return;
    loop->estimate_state = EST_NOT_AVAILABLE;
  
!   exits = get_loop_exit_edges (loop);
!   for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
      {
!       if (!number_of_iterations_exit (loop, ex, &niter_desc, false))
  	continue;
  
        niter = niter_desc.niter;
*************** estimate_numbers_of_iterations_loop (str
*** 2010,2019 ****
  			niter);
        record_estimate (loop, niter,
  		       niter_desc.additional_info,
! 		       last_stmt (exits[i]->src),
  		       true, true);
      }
!   free (exits);
    
    infer_loop_bounds_from_undefined (loop);
    compute_estimated_nb_iterations (loop);
--- 2009,2018 ----
  			niter);
        record_estimate (loop, niter,
  		       niter_desc.additional_info,
! 		       last_stmt (ex->src),
  		       true, true);
      }
!   VEC_free (edge, heap, exits);
    
    infer_loop_bounds_from_undefined (loop);
    compute_estimated_nb_iterations (loop);
Index: predict.c
===================================================================
*** predict.c	(revision 119015)
--- predict.c	(working copy)
*************** predict_loops (struct loops *loops_info)
*** 640,662 ****
    for (i = 1; i < loops_info->num; i++)
      {
        basic_block bb, *bbs;
!       unsigned j;
!       unsigned n_exits;
        struct loop *loop = loops_info->parray[i];
!       edge *exits;
        struct tree_niter_desc niter_desc;
  
!       exits = get_loop_exit_edges (loop, &n_exits);
  
! 
!       for (j = 0; j < n_exits; j++)
  	{
  	  tree niter = NULL;
  
! 	  if (number_of_iterations_exit (loop, exits[j], &niter_desc, false))
  	    niter = niter_desc.niter;
  	  if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST)
! 	    niter = loop_niter_by_eval (loop, exits[j]);
  
  	  if (TREE_CODE (niter) == INTEGER_CST)
  	    {
--- 640,662 ----
    for (i = 1; i < loops_info->num; i++)
      {
        basic_block bb, *bbs;
!       unsigned j, n_exits;
        struct loop *loop = loops_info->parray[i];
!       VEC (edge, heap) *exits;
        struct tree_niter_desc niter_desc;
+       edge ex;
  
!       exits = get_loop_exit_edges (loop);
!       n_exits = VEC_length (edge, exits);
  
!       for (j = 0; VEC_iterate (edge, exits, j, ex); j++)
  	{
  	  tree niter = NULL;
  
! 	  if (number_of_iterations_exit (loop, ex, &niter_desc, false))
  	    niter = niter_desc.niter;
  	  if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST)
! 	    niter = loop_niter_by_eval (loop, ex);
  
  	  if (TREE_CODE (niter) == INTEGER_CST)
  	    {
*************** predict_loops (struct loops *loops_info)
*** 673,682 ****
  	      else
  		probability = ((REG_BR_PROB_BASE + max / 2) / max);
  
! 	      predict_edge (exits[j], PRED_LOOP_ITERATIONS, probability);
  	    }
  	}
!       free (exits);
  
        bbs = get_loop_body (loop);
  
--- 673,682 ----
  	      else
  		probability = ((REG_BR_PROB_BASE + max / 2) / max);
  
! 	      predict_edge (ex, PRED_LOOP_ITERATIONS, probability);
  	    }
  	}
!       VEC_free (edge, heap, exits);
  
        bbs = get_loop_body (loop);
  
Index: loop-unroll.c
===================================================================
*** loop-unroll.c	(revision 119015)
--- loop-unroll.c	(working copy)
*************** static struct opt_info *
*** 1709,1722 ****
  analyze_insns_in_loop (struct loop *loop)
  {
    basic_block *body, bb;
!   unsigned i, num_edges = 0;
    struct opt_info *opt_info = XCNEW (struct opt_info);
    rtx insn;
    struct iv_to_split *ivts = NULL;
    struct var_to_expand *ves = NULL;
    PTR *slot1;
    PTR *slot2;
!   edge *edges = get_loop_exit_edges (loop, &num_edges);
    bool can_apply = false;
    
    iv_analysis_loop_init (loop);
--- 1709,1723 ----
  analyze_insns_in_loop (struct loop *loop)
  {
    basic_block *body, bb;
!   unsigned i;
    struct opt_info *opt_info = XCNEW (struct opt_info);
    rtx insn;
    struct iv_to_split *ivts = NULL;
    struct var_to_expand *ves = NULL;
    PTR *slot1;
    PTR *slot2;
!   VEC (edge, heap) *edges = get_loop_exit_edges (loop);
!   edge exit;
    bool can_apply = false;
    
    iv_analysis_loop_init (loop);
*************** analyze_insns_in_loop (struct loop *loop
*** 1730,1740 ****
    /* Record the loop exit bb and loop preheader before the unrolling.  */
    opt_info->loop_preheader = loop_preheader_edge (loop)->src;
    
!   if (num_edges == 1
!       && !(edges[0]->flags & EDGE_COMPLEX))
      {
!       opt_info->loop_exit = split_edge (edges[0]);
!       can_apply = true;
      }
    
    if (flag_variable_expansion_in_unroller
--- 1731,1744 ----
    /* Record the loop exit bb and loop preheader before the unrolling.  */
    opt_info->loop_preheader = loop_preheader_edge (loop)->src;
    
!   if (VEC_length (edge, edges) == 1)
      {
!       exit = VEC_index (edge, edges, 0);
!       if (!(exit->flags & EDGE_COMPLEX))
! 	{
! 	  opt_info->loop_exit = split_edge (exit);
! 	  can_apply = true;
! 	}
      }
    
    if (flag_variable_expansion_in_unroller
*************** analyze_insns_in_loop (struct loop *loop
*** 1774,1780 ****
        }
      }
    
!   free (edges);
    free (body);
    return opt_info;
  }
--- 1778,1784 ----
        }
      }
    
!   VEC_free (edge, heap, edges);
    free (body);
    return opt_info;
  }
Index: tree-outof-ssa.c
===================================================================
*** tree-outof-ssa.c	(revision 119015)
--- tree-outof-ssa.c	(working copy)
*************** rewrite_trees (var_map map, tree *values
*** 1976,1984 ****
    delete_elim_graph (g);
  }
  
- 
- DEF_VEC_ALLOC_P(edge,heap);
- 
  /* These are the local work structures used to determine the best place to 
     insert the copies that were placed on edges by the SSA->normal pass..  */
  static VEC(edge,heap) *edge_leader;
--- 1976,1981 ----
Index: cfgloop.c
===================================================================
*** cfgloop.c	(revision 119015)
--- cfgloop.c	(working copy)
*************** get_loop_body_in_bfs_order (const struct
*** 881,910 ****
    return blocks;
  }
  
! /* Gets exit edges of a LOOP, returning their number in N_EDGES.  */
! edge *
! get_loop_exit_edges (const struct loop *loop, unsigned int *num_edges)
  {
!   edge *edges, e;
!   unsigned i, n;
!   basic_block * body;
    edge_iterator ei;
  
    gcc_assert (loop->latch != EXIT_BLOCK_PTR);
  
    body = get_loop_body (loop);
-   n = 0;
-   for (i = 0; i < loop->num_nodes; i++)
-     FOR_EACH_EDGE (e, ei, body[i]->succs)
-       if (!flow_bb_inside_loop_p (loop, e->dest))
- 	n++;
-   edges = XNEWVEC (edge, n);
-   *num_edges = n;
-   n = 0;
    for (i = 0; i < loop->num_nodes; i++)
      FOR_EACH_EDGE (e, ei, body[i]->succs)
        if (!flow_bb_inside_loop_p (loop, e->dest))
! 	edges[n++] = e;
    free (body);
  
    return edges;
--- 881,904 ----
    return blocks;
  }
  
! /* Returns the list of the exit edges of a LOOP.  */
! 
! VEC (edge, heap) *
! get_loop_exit_edges (const struct loop *loop)
  {
!   VEC (edge, heap) *edges = NULL;
!   edge e;
!   unsigned i;
!   basic_block *body;
    edge_iterator ei;
  
    gcc_assert (loop->latch != EXIT_BLOCK_PTR);
  
    body = get_loop_body (loop);
    for (i = 0; i < loop->num_nodes; i++)
      FOR_EACH_EDGE (e, ei, body[i]->succs)
        if (!flow_bb_inside_loop_p (loop, e->dest))
! 	VEC_safe_push (edge, heap, edges, e);
    free (body);
  
    return edges;
Index: cfgloop.h
===================================================================
*** cfgloop.h	(revision 119015)
--- cfgloop.h	(working copy)
*************** extern void mark_loop_exit_edges (struct
*** 222,228 ****
  extern basic_block *get_loop_body (const struct loop *);
  extern basic_block *get_loop_body_in_dom_order (const struct loop *);
  extern basic_block *get_loop_body_in_bfs_order (const struct loop *);
! extern edge *get_loop_exit_edges (const struct loop *, unsigned *);
  extern unsigned num_loop_branches (const struct loop *);
  
  extern edge loop_preheader_edge (const struct loop *);
--- 222,228 ----
  extern basic_block *get_loop_body (const struct loop *);
  extern basic_block *get_loop_body_in_dom_order (const struct loop *);
  extern basic_block *get_loop_body_in_bfs_order (const struct loop *);
! extern VEC (edge, heap) *get_loop_exit_edges (const struct loop *);
  extern unsigned num_loop_branches (const struct loop *);
  
  extern edge loop_preheader_edge (const struct loop *);
Index: basic-block.h
===================================================================
*** basic-block.h	(revision 119015)
--- basic-block.h	(working copy)
*************** struct edge_def GTY(())
*** 146,151 ****
--- 146,152 ----
  typedef struct edge_def *edge;
  DEF_VEC_P(edge);
  DEF_VEC_ALLOC_P(edge,gc);
+ DEF_VEC_ALLOC_P(edge,heap);
  
  #define EDGE_FALLTHRU		1	/* 'Straight line' flow */
  #define EDGE_ABNORMAL		2	/* Strange flow, like computed


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]