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]

[lno] Loops with multiple exits in ivcanon


Hello,

this patch makes the canonical iv creation pass handle loops
with more than one exit.

Zdenek

Index: ChangeLog.lno
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/ChangeLog.lno,v
retrieving revision 1.1.2.86
diff -c -3 -p -r1.1.2.86 ChangeLog.lno
*** ChangeLog.lno	13 Mar 2004 00:58:38 -0000	1.1.2.86
--- ChangeLog.lno	13 Mar 2004 09:34:44 -0000
***************
*** 1,3 ****
--- 1,15 ----
+ 2004-03-13  Zdenek Dvorak  <rakdver@atrey.karlin.mff.cuni.cz>
+ 
+ 	* tree-scalar-evolution.c (gate_scev_iv_canon): Do not check rtl
+ 	level flags here.
+ 	* tree-ssa-loop-ivcanon.c (get_base_for): Verfify that the argument
+ 	of the phi node is a constant.
+ 	(loop_niter_by_eval, create_canonical_iv, try_unroll_loop_completely,
+ 	canonicalize_loop_induction_variables): Handle loops with more than
+ 	one exit.
+ 	(find_loop_niter_by_eval): New.
+ 	(canonicalize_induction_variables): Check rtl level flags here.
+ 
  2004-03-12  Andrew Pinski  <pinskia@physics.uc.edu>
  
  	* tree-ssa-return.c (tree_ssa_return):
Index: tree-scalar-evolution.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-scalar-evolution.c,v
retrieving revision 1.1.2.19
diff -c -3 -p -r1.1.2.19 tree-scalar-evolution.c
*** tree-scalar-evolution.c	12 Mar 2004 01:28:30 -0000	1.1.2.19
--- tree-scalar-evolution.c	13 Mar 2004 09:34:44 -0000
*************** static bool
*** 2849,2862 ****
  gate_scev_iv_canon (void)
  {
    return (current_loops
! 	  /* Only run this pass if
! 	     1) We will be able to eliminate the superfluous ivs
! 		we create.   */
! 	  && flag_tree_loop
! 	  /* 2) Someone at rtl level will be able to use the information
! 		provided.  */
! 	  && (flag_unroll_loops
! 	      || flag_branch_on_count_reg));
  }
  
  static bool
--- 2849,2857 ----
  gate_scev_iv_canon (void)
  {
    return (current_loops
! 	  /* Only run this pass if we will be able to eliminate the
! 	     superfluous ivs we create.   */
! 	  && flag_tree_loop);
  }
  
  static bool
Index: tree-ssa-loop-ivcanon.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-loop-ivcanon.c,v
retrieving revision 1.1.2.1
diff -c -3 -p -r1.1.2.1 tree-ssa-loop-ivcanon.c
*** tree-ssa-loop-ivcanon.c	12 Mar 2004 01:28:30 -0000	1.1.2.1
--- tree-ssa-loop-ivcanon.c	13 Mar 2004 09:34:44 -0000
*************** get_base_for (struct loop *loop, tree x)
*** 122,127 ****
--- 122,130 ----
    init = phi_element_for_edge (phi, loop_preheader_edge (loop))->def;
    next = phi_element_for_edge (phi, loop_latch_edge (loop))->def;
  
+   if (TREE_CODE (next) != SSA_NAME)
+     return NULL_TREE;
+ 
    if (!is_gimple_min_invariant (init))
      return NULL_TREE;
  
*************** get_val_for (tree x, tree base)
*** 160,180 ****
    return val;
  }
  
! /* Tries to count the number of iterations of LOOP by brute force.  */
  
  static tree
! loop_niter_by_eval (struct loop *loop)
  {
-   edge exit;
    tree cond, cnd, acnd;
    tree op[2], val[2], next[2], aval[2], phi[2];
    unsigned i, j;
    enum tree_code cmp;
  
-   if (loop_num_exits (loop) != 1)
-     return chrec_top;
-   exit = loop_exit_edge (loop, 0);
- 
    cond = last_stmt (exit->src);
    if (!cond || TREE_CODE (cond) != COND_EXPR)
      return chrec_top;
--- 163,179 ----
    return val;
  }
  
! /* Tries to count the number of iterations of LOOP till it exits by EXIT
!    by brute force.  */
  
  static tree
! loop_niter_by_eval (struct loop *loop, edge exit)
  {
    tree cond, cnd, acnd;
    tree op[2], val[2], next[2], aval[2], phi[2];
    unsigned i, j;
    enum tree_code cmp;
  
    cond = last_stmt (exit->src);
    if (!cond || TREE_CODE (cond) != COND_EXPR)
      return chrec_top;
*************** loop_niter_by_eval (struct loop *loop)
*** 246,257 ****
    return chrec_top;
  }
  
! /* Adds a canonical induction variable to LOOP iterating NITER times.  */
  
  static void
! create_canonical_iv (struct loop *loop, tree niter)
  {
!   edge exit, in;
    tree cond, type, var;
    block_stmt_iterator incr_at;
    enum tree_code cmp;
--- 245,293 ----
    return chrec_top;
  }
  
! /* Finds the exit of the LOOP by that the loop exits after a constant
!    number of iterations and stores it to *EXIT.  The iteration count
!    is returned.  */
! 
! static 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;
! 
!       aniter = loop_niter_by_eval (loop, ex);
!       if (TREE_CODE (aniter) != INTEGER_CST)
! 	continue;
! 
!       if (niter
! 	  && !integer_nonzerop (fold (build (LT_EXPR, boolean_type_node,
! 					     aniter, niter))))
! 	continue;
! 
!       niter = aniter;
!       *exit = ex;
!     }
!   free (exits);
! 
!   return niter ? niter : chrec_top;
! }
! 
! /* Adds a canonical induction variable to LOOP iterating NITER times.  EXIT
!    is the exit edge whose condition is replaced.  */
  
  static void
! create_canonical_iv (struct loop *loop, edge exit, tree niter)
  {
!   edge in;
    tree cond, type, var;
    block_stmt_iterator incr_at;
    enum tree_code cmp;
*************** create_canonical_iv (struct loop *loop, 
*** 263,269 ****
        fprintf (tree_dump_file, " iterations.\n");
      }
  
-   exit = loop_exit_edge (loop, 0);
    cond = last_stmt (exit->src);
    in = exit->src->succ;
    if (in == exit)
--- 299,304 ----
*************** estimate_loop_size (struct loop *loop)
*** 300,314 ****
  }
  
  /* Tries to unroll LOOP completely, i.e. NITER times.  LOOPS is the
!    loop tree. */
  
  static bool
! try_unroll_loop_completely (struct loops *loops, struct loop *loop, tree niter)
  {
    tree max_unroll = build_int_2 (PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES),
  				 0);
    unsigned n_unroll, ninsns;
-   edge exit = loop_exit_edge (loop, 0);
    tree cond, dont_exit, do_exit;
  
    if (loop->inner)
--- 335,352 ----
  }
  
  /* Tries to unroll LOOP completely, i.e. NITER times.  LOOPS is the
!    loop tree.  COMPLETELY_UNROLL is true if we should unroll the loop
!    even if it may cause code growth.  EXIT is the exit of the loop
!    that should be eliminated.  */
  
  static bool
! try_unroll_loop_completely (struct loops *loops, struct loop *loop,
! 			    edge exit, tree niter,
! 			    bool completely_unroll)
  {
    tree max_unroll = build_int_2 (PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES),
  				 0);
    unsigned n_unroll, ninsns;
    tree cond, dont_exit, do_exit;
  
    if (loop->inner)
*************** try_unroll_loop_completely (struct loops
*** 318,323 ****
--- 356,365 ----
  				      niter, max_unroll))))
      return false;
    n_unroll = tree_low_cst (niter, 1);
+ 
+   if (n_unroll && !completely_unroll)
+     return false;
+ 
    ninsns = estimate_loop_size (loop);
  
    if (n_unroll * ninsns
*************** try_unroll_loop_completely (struct loops
*** 360,386 ****
  }
  
  /* Adds a canonical induction variable to LOOP if suitable.  LOOPS is the loops
!    tree.  */
  
  static void
! canonicalize_loop_induction_variables (struct loops *loops, struct loop *loop)
  {
    tree niter 
  #if 0 /* Causes bootstrap to fail  */
  	  = number_of_iterations_in_loop (loop);
  
!   if (TREE_CODE (niter) != INTEGER_CST)
      niter  
  #endif
! 	  = loop_niter_by_eval (loop);
  
    if (TREE_CODE (niter) != INTEGER_CST)
      return;
  
!   if (try_unroll_loop_completely (loops, loop, niter))
      return;
  
!   create_canonical_iv (loop, niter);
  }
  
  /* The main entry point of the pass.  Adds canonical induction variables
--- 402,435 ----
  }
  
  /* Adds a canonical induction variable to LOOP if suitable.  LOOPS is the loops
!    tree.  CREATE_IV is true if we may create a new iv.  COMPLETELY_UNROLL is
!    true if we should do complete unrolling even if it may cause the code
!    growth.  */
  
  static void
! canonicalize_loop_induction_variables (struct loops *loops, struct loop *loop,
! 				       bool create_iv, bool completely_unroll)
  {
+   edge exit = NULL;
    tree niter 
  #if 0 /* Causes bootstrap to fail  */
  	  = number_of_iterations_in_loop (loop);
  
!   if (TREE_CODE (niter) == INTEGER_CST)
!     exit = loop_exit_edge (loop, 0);
!   else
      niter  
  #endif
! 	  = find_loop_niter_by_eval (loop, &exit);
  
    if (TREE_CODE (niter) != INTEGER_CST)
      return;
  
!   if (try_unroll_loop_completely (loops, loop, exit, niter, completely_unroll))
      return;
  
!   if (create_iv)
!     create_canonical_iv (loop, exit, niter);
  }
  
  /* The main entry point of the pass.  Adds canonical induction variables
*************** canonicalize_induction_variables (struct
*** 391,402 ****
  {
    unsigned i;
    struct loop *loop;
  
    for (i = 1; i < loops->num; i++)
      {
        loop = loops->parray[i];
  
        if (loop)
! 	canonicalize_loop_induction_variables (loops, loop);
      }
  }
--- 440,454 ----
  {
    unsigned i;
    struct loop *loop;
+   bool create_ivs = flag_unroll_loops || flag_branch_on_count_reg;
+   bool completely_unroll_loops = flag_unroll_loops;
  
    for (i = 1; i < loops->num; i++)
      {
        loop = loops->parray[i];
  
        if (loop)
! 	canonicalize_loop_induction_variables (loops, loop, create_ivs,
! 					       completely_unroll_loops);
      }
  }


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