[patch] Final value replacement for loops with several exits

[Zdenek Dvorak <rakdver at kam dot mff dot cuni dot cz>]

Hello,

currently, we only perform final value replacement for loops with single
exit.  This patch makes it work also for loops with several exits --
instead of processing the loops, we now go over the edges of cfg, check
whether they are loop exits and whether we can determine the number of
iterations corresponding to this exit, and pass this number of
iterations to compute_overall_effect_of_inner_loop.

Bootstrapped & regtested on i686 and ppc-linux.

Zdenek

	* tree-scalar-evolution.c (compute_overall_effect_of_inner_loop): Add
	loop_niter parameter.
	(follow_ssa_edge_inner_loop_phi, interpret_loop_phi,
	compute_scalar_evolution_in_loop): Pass NULL as loop_niter to
	compute_overall_effect_of_inner_loop.
	(scev_const_prop): Perform final value replacement for loops with
	multiple exits.

	* gcc.dg/tree-ssa/loop-28.c: New test.

Index: tree-scalar-evolution.c
===================================================================
*** tree-scalar-evolution.c	(revision 124497)
--- tree-scalar-evolution.c	(working copy)
*************** loop_phi_node_p (tree phi)
*** 441,450 ****
     The overall effect of the loop, "i_0 + 20" in the previous example, 
     is obtained by passing in the parameters: LOOP = 1, 
     EVOLUTION_FN = {i_0, +, 2}_1.
  */
   
  static tree 
! compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn)
  {
    bool val = false;
  
--- 441,453 ----
     The overall effect of the loop, "i_0 + 20" in the previous example, 
     is obtained by passing in the parameters: LOOP = 1, 
     EVOLUTION_FN = {i_0, +, 2}_1.
+ 
+    If LOOP_NITER is not NULL, it specifies number of iterations of LOOP.
  */
   
  static tree 
! compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn,
! 				      tree loop_niter)
  {
    bool val = false;
  
*************** compute_overall_effect_of_inner_loop (st
*** 458,464 ****
        if (inner_loop == loop
  	  || flow_loop_nested_p (loop, inner_loop))
  	{
! 	  tree nb_iter = number_of_latch_executions (inner_loop);
  
  	  if (nb_iter == chrec_dont_know)
  	    return chrec_dont_know;
--- 461,473 ----
        if (inner_loop == loop
  	  || flow_loop_nested_p (loop, inner_loop))
  	{
! 	  tree nb_iter;
! 	  
! 	  if (loop_niter != NULL_TREE
! 	      && inner_loop == loop)
! 	    nb_iter = loop_niter;
! 	  else 
! 	    nb_iter = number_of_latch_executions (inner_loop);
  
  	  if (nb_iter == chrec_dont_know)
  	    return chrec_dont_know;
*************** compute_overall_effect_of_inner_loop (st
*** 471,477 ****
  	      res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
  	      
  	      /* Continue the computation until ending on a parent of LOOP.  */
! 	      return compute_overall_effect_of_inner_loop (loop, res);
  	    }
  	}
        else
--- 480,486 ----
  	      res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
  	      
  	      /* Continue the computation until ending on a parent of LOOP.  */
! 	      return compute_overall_effect_of_inner_loop (loop, res, loop_niter);
  	    }
  	}
        else
*************** follow_ssa_edge_inner_loop_phi (struct l
*** 1321,1327 ****
      }
  
    /* Otherwise, compute the overall effect of the inner loop.  */
!   ev = compute_overall_effect_of_inner_loop (loop, ev);
    return follow_ssa_edge_in_rhs (outer_loop, loop_phi_node, ev, halting_phi,
  				 evolution_of_loop, limit);
  }
--- 1330,1336 ----
      }
  
    /* Otherwise, compute the overall effect of the inner loop.  */
!   ev = compute_overall_effect_of_inner_loop (loop, ev, NULL_TREE);
    return follow_ssa_edge_in_rhs (outer_loop, loop_phi_node, ev, halting_phi,
  				 evolution_of_loop, limit);
  }
*************** interpret_loop_phi (struct loop *loop, t
*** 1537,1543 ****
        subloop = superloop_at_depth (phi_loop, loop->depth + 1);
  
        /* Interpret the subloop.  */
!       res = compute_overall_effect_of_inner_loop (subloop, evolution_fn);
        return res;
      }
  
--- 1546,1553 ----
        subloop = superloop_at_depth (phi_loop, loop->depth + 1);
  
        /* Interpret the subloop.  */
!       res = compute_overall_effect_of_inner_loop (subloop, evolution_fn,
! 						  NULL_TREE);
        return res;
      }
  
*************** compute_scalar_evolution_in_loop (struct
*** 1681,1687 ****
      return ev;
  
    def_loop = superloop_at_depth (def_loop, wrto_loop->depth + 1);
!   res = compute_overall_effect_of_inner_loop (def_loop, ev);
  
    return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
  }
--- 1691,1697 ----
      return ev;
  
    def_loop = superloop_at_depth (def_loop, wrto_loop->depth + 1);
!   res = compute_overall_effect_of_inner_loop (def_loop, ev, NULL_TREE);
  
    return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
  }
*************** scev_const_prop (void)
*** 2880,2886 ****
    struct loop *loop, *ex_loop;
    bitmap ssa_names_to_remove = NULL;
    unsigned i;
!   loop_iterator li;
  
    if (!current_loops)
      return 0;
--- 2890,2900 ----
    struct loop *loop, *ex_loop;
    bitmap ssa_names_to_remove = NULL;
    unsigned i;
!   edge_iterator ei;
!   edge exit;
!   tree def, rslt, ass;
!   block_stmt_iterator bsi;
!   struct tree_niter_desc niter;
  
    if (!current_loops)
      return 0;
*************** scev_const_prop (void)
*** 2938,3009 ****
      }
  
    /* Now the regular final value replacement.  */
!   FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
      {
!       edge exit;
!       tree def, rslt, ass, niter;
!       block_stmt_iterator bsi;
! 
!       /* If we do not know exact number of iterations of the loop, we cannot
! 	 replace the final value.  */
!       exit = single_exit (loop);
!       if (!exit)
! 	continue;
! 
!       niter = number_of_latch_executions (loop);
!       /* We used to check here whether the computation of NITER is expensive,
! 	 and avoided final value elimination if that is the case.  The problem
! 	 is that it is hard to evaluate whether the expression is too
! 	 expensive, as we do not know what optimization opportunities the
! 	 the elimination of the final value may reveal.  Therefore, we now
! 	 eliminate the final values of induction variables unconditionally.  */
!       if (niter == chrec_dont_know)
  	continue;
  
!       /* Ensure that it is possible to insert new statements somewhere.  */
!       if (!single_pred_p (exit->dest))
! 	split_loop_exit_edge (exit);
!       tree_block_label (exit->dest);
!       bsi = bsi_after_labels (exit->dest);
! 
!       ex_loop = superloop_at_depth (loop, exit->dest->loop_father->depth + 1);
! 
!       for (phi = phi_nodes (exit->dest); phi; phi = next_phi)
! 	{
! 	  next_phi = PHI_CHAIN (phi);
! 	  rslt = PHI_RESULT (phi);
! 	  def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
! 	  if (!is_gimple_reg (def))
  	    continue;
  
! 	  if (!POINTER_TYPE_P (TREE_TYPE (def))
! 	      && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
  	    continue;
  
! 	  def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, NULL);
! 	  def = compute_overall_effect_of_inner_loop (ex_loop, def);
! 	  if (!tree_does_not_contain_chrecs (def)
! 	      || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
! 	      /* Moving the computation from the loop may prolong life range
! 		 of some ssa names, which may cause problems if they appear
! 		 on abnormal edges.  */
! 	      || contains_abnormal_ssa_name_p (def))
  	    continue;
  
! 	  /* Eliminate the PHI node and replace it by a computation outside
! 	     the loop.  */
! 	  def = unshare_expr (def);
! 	  remove_phi_node (phi, NULL_TREE, false);
  
! 	  ass = build_gimple_modify_stmt (rslt, NULL_TREE);
! 	  SSA_NAME_DEF_STMT (rslt) = ass;
! 	  {
! 	    block_stmt_iterator dest = bsi;
! 	    bsi_insert_before (&dest, ass, BSI_NEW_STMT);
! 	    def = force_gimple_operand_bsi (&dest, def, false, NULL_TREE);
! 	  }
! 	  GIMPLE_STMT_OPERAND (ass, 1) = def;
! 	  update_stmt (ass);
  	}
      }
    return 0;
--- 2952,3039 ----
      }
  
    /* Now the regular final value replacement.  */
!   FOR_EACH_BB (bb)
      {
!       loop = bb->loop_father;
!       if (!loop->outer)
  	continue;
  
!       FOR_EACH_EDGE (exit, ei, bb->succs)
! 	{
! 	  if (!loop_exit_edge_p (loop, exit))
  	    continue;
  
! 	  /* Find the outermost loop that is exited by this edge.  */
! 	  ex_loop = superloop_at_depth (loop,
! 					exit->dest->loop_father->depth + 1);
! 
! 	  /* If we do not know exact number of iterations of the loop, we
! 	     cannot replace the final value.  */
! 	  if (!number_of_iterations_exit (ex_loop, exit, &niter, false)
! 	      || !integer_zerop (niter.may_be_zero))
  	    continue;
  
! 	  /* We used to check here whether the computation of NITER is
! 	     expensive, and avoided final value elimination if that is the
! 	     case.  The problem is that it is hard to evaluate whether the
! 	     expression is too expensive, as we do not know what optimization
! 	     opportunities the the elimination of the final value may reveal.
! 	     Therefore, we now eliminate the final values of induction
! 	     variables unconditionally.  */
! 
! 	  if (!phi_nodes (exit->dest))
  	    continue;
  
! 	  /* Ensure that it is possible to insert new statements somewhere.  */
! 	  if (!single_pred_p (exit->dest))
! 	    split_loop_exit_edge (exit);
  
! 	  for (phi = phi_nodes (exit->dest); phi; phi = next_phi)
! 	    {
! 	      next_phi = PHI_CHAIN (phi);
! 	      rslt = PHI_RESULT (phi);
! 	      def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
! 	      if (!is_gimple_reg (def))
! 		continue;
! 
! 	      if (!POINTER_TYPE_P (TREE_TYPE (def))
! 		  && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
! 		continue;
! 
! 	      def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, NULL);
! 	      def = compute_overall_effect_of_inner_loop (ex_loop, def,
! 							  niter.niter);
! 	      if (!tree_does_not_contain_chrecs (def)
! 		  || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
! 		  /* Moving the computation from the loop may prolong life range
! 		     of some ssa names, which may cause problems if they appear
! 		     on abnormal edges.  */
! 		  || contains_abnormal_ssa_name_p (def))
! 		continue;
! 
! 	      if (dump_file && (dump_flags & TDF_DETAILS))
! 		{
! 		  fprintf (dump_file, "Replaced final value ");
! 		  print_generic_expr (dump_file, rslt, TDF_SLIM);
! 		  fprintf (dump_file, " in loop %d by ", ex_loop->num);
! 		  print_generic_expr (dump_file, def, TDF_SLIM);
! 		  fprintf (dump_file, "\n");
! 		}
! 
! 	      /* Eliminate the PHI node and replace it by a computation outside
! 		 the loop.  */
! 	      def = unshare_expr (def);
! 	      remove_phi_node (phi, NULL_TREE, false);
! 
! 	      ass = build_gimple_modify_stmt (rslt, NULL_TREE);
! 	      SSA_NAME_DEF_STMT (rslt) = ass;
! 
! 	      bsi = bsi_after_labels (exit->dest);
! 	      bsi_insert_before (&bsi, ass, BSI_NEW_STMT);
! 	      def = force_gimple_operand_bsi (&bsi, def, false, NULL_TREE);
! 	      GIMPLE_STMT_OPERAND (ass, 1) = def;
! 	      update_stmt (ass);
! 	    }
  	}
      }
    return 0;
Index: testsuite/gcc.dg/tree-ssa/loop-28.c
===================================================================
*** testsuite/gcc.dg/tree-ssa/loop-28.c	(revision 0)
--- testsuite/gcc.dg/tree-ssa/loop-28.c	(revision 0)
***************
*** 0 ****
--- 1,18 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O1 -fdump-tree-sccp-details" } */
+ 
+ char * strncat(char *dest, const char *src, unsigned count)
+ {
+   if (count)
+     {
+       while ((*dest++ = *src++))
+ 	if (--count == 0) 
+ 	  {
+ 	      *dest = '\0';
+ 	      break;
+ 	  }
+     }
+ }
+ 
+ /* { dg-final { scan-tree-dump-times "Replaced final value " 1 "sccp" } } */
+ /* { dg-final { cleanup-tree-dump "sccp" } } */