[patch] Allow transforming loop before unrolling

Zdenek Dvorak rakdver@atrey.karlin.mff.cuni.cz
Fri Jan 5 00:45:00 GMT 2007


Hello,

in predictive commoning, we unroll the loop to avoid need for copying
the variables; however, we do not want the predictive
commoning transformation to be performed in the loop that we split
to execute the last few iterations, so we cannot do it before unrolling.
We could do it after unrolling, but since all the analyses were done
on the non-unrolled loop, finding where to apply them in the unrolled
loop would be complicated.

I think the best solution is to enable to perform some transformation
after the loop to execute the last few iterations is split, but before
the main loop is unrolled.  There are basically two ways how to do that
-- we could split unrolling into two phases (aligning the number of
iterations and preconditioning + the unrolling itself), or we may
add callback to tree_unroll_loop that is called just before unrolling.
I tried both ways, the later turns out to be a bit simpler, hence the
patch I submit implements that one.  I will wait for a few days before
commiting this change, in case someone would prefer the former way
or some other solution.

Bootstrapped & regtested on i686 and x86_64.

Zdenek

	* tree-ssa-loop-manip.c (tree_unroll_loop): Make it a wrapper over ...
	(tree_transform_and_unroll_loop): New.
	* tree-flow.h (transform_callback, tree_transform_and_unroll_loop):
	Declare.

Index: tree-ssa-loop-manip.c
===================================================================
*** tree-ssa-loop-manip.c	(revision 120437)
--- tree-ssa-loop-manip.c	(working copy)
*************** determine_exit_conditions (struct loop *
*** 803,816 ****
         if (st)
           break;
         post;
!      } */
  
  /* Probability in % that the unrolled loop is entered.  Just a guess.  */
  #define PROB_UNROLLED_LOOP_ENTERED 90
  
  void
! tree_unroll_loop (struct loop *loop, unsigned factor,
! 		  edge exit, struct tree_niter_desc *desc)
  {
    tree dont_exit, exit_if, ctr_before, ctr_after;
    tree enter_main_cond, exit_base, exit_step, exit_bound;
--- 803,822 ----
         if (st)
           break;
         post;
!      }
!  
!    Before the loop is unrolled, TRANSFORM is called for it (only for the
!    unrolled loop, but not for its versioned copy).  DATA is passed to
!    TRANSFORM.  */
  
  /* Probability in % that the unrolled loop is entered.  Just a guess.  */
  #define PROB_UNROLLED_LOOP_ENTERED 90
  
  void
! tree_transform_and_unroll_loop (struct loop *loop, unsigned factor,
! 				edge exit, struct tree_niter_desc *desc,
! 				transform_callback transform,
! 				void *data)
  {
    tree dont_exit, exit_if, ctr_before, ctr_after;
    tree enter_main_cond, exit_base, exit_step, exit_bound;
*************** tree_unroll_loop (struct loop *loop, uns
*** 859,882 ****
    gcc_assert (new_loop != NULL);
    update_ssa (TODO_update_ssa);
  
!   /* Unroll the loop and remove the old exits.  */
!   dont_exit = ((exit->flags & EDGE_TRUE_VALUE)
! 	       ? boolean_false_node
! 	       : boolean_true_node);
!   exit_if = last_stmt (exit->src);
!   COND_EXPR_COND (exit_if) = dont_exit;
!   update_stmt (exit_if);
!       
!   wont_exit = sbitmap_alloc (factor);
!   sbitmap_ones (wont_exit);
!   ok = tree_duplicate_loop_to_header_edge
! 	  (loop, loop_latch_edge (loop), factor - 1,
! 	   wont_exit, exit, NULL, DLTHE_FLAG_UPDATE_FREQ);
!   free (wont_exit);
!   gcc_assert (ok);
!   update_ssa (TODO_update_ssa);
! 
!   /* Determine the probability of the exit edge.  */
    new_est_niter = est_niter / factor;
  
    /* Without profile feedback, loops for that we do not know a better estimate
--- 865,871 ----
    gcc_assert (new_loop != NULL);
    update_ssa (TODO_update_ssa);
  
!   /* Determine the probability of the exit edge of the unrolled loop.  */
    new_est_niter = est_niter / factor;
  
    /* Without profile feedback, loops for that we do not know a better estimate
*************** tree_unroll_loop (struct loop *loop, uns
*** 892,922 ****
  	new_est_niter = 5;
      }
  
-   /* Ensure that the frequencies in the loop match the new estimated
-      number of iterations.  */
-   freq_h = loop->header->frequency;
-   freq_e = EDGE_FREQUENCY (loop_preheader_edge (loop));
-   if (freq_h != 0)
-     scale_loop_frequencies (loop, freq_e * new_est_niter, freq_h);
- 
    /* Prepare the cfg and update the phi nodes.  */
    rest = loop_preheader_edge (new_loop)->src;
    precond_edge = single_pred_edge (rest);
    split_edge (loop_latch_edge (loop));
    exit_bb = single_pred (loop->latch);
  
    new_exit = make_edge (exit_bb, rest, EDGE_FALSE_VALUE | irr);
!   new_exit->count = loop_preheader_edge (loop)->count;
!   new_exit->probability = REG_BR_PROB_BASE / new_est_niter;
! 
!   rest->count += new_exit->count;
!   rest->frequency += EDGE_FREQUENCY (new_exit);
! 
    new_nonexit = single_pred_edge (loop->latch);
    new_nonexit->flags = EDGE_TRUE_VALUE;
-   new_nonexit->probability = REG_BR_PROB_BASE - new_exit->probability;
-   scale_bbs_frequencies_int (&loop->latch, 1, new_nonexit->probability,
- 			     REG_BR_PROB_BASE);
  
    old_entry = loop_preheader_edge (loop);
    new_entry = loop_preheader_edge (new_loop);
--- 881,904 ----
  	new_est_niter = 5;
      }
  
    /* Prepare the cfg and update the phi nodes.  */
    rest = loop_preheader_edge (new_loop)->src;
    precond_edge = single_pred_edge (rest);
    split_edge (loop_latch_edge (loop));
    exit_bb = single_pred (loop->latch);
  
+   /* For the moment, make it appear that the new exit edge cannot
+      be taken.  */
+   bsi = bsi_last (exit_bb);
+   exit_if = build_if_stmt (boolean_true_node,
+ 			   tree_block_label (loop->latch),
+ 			   tree_block_label (rest));
+   bsi_insert_after (&bsi, exit_if, BSI_NEW_STMT);
    new_exit = make_edge (exit_bb, rest, EDGE_FALSE_VALUE | irr);
!   new_exit->count = 0;
!   new_exit->probability = 0;
    new_nonexit = single_pred_edge (loop->latch);
    new_nonexit->flags = EDGE_TRUE_VALUE;
  
    old_entry = loop_preheader_edge (loop);
    new_entry = loop_preheader_edge (new_loop);
*************** tree_unroll_loop (struct loop *loop, uns
*** 954,969 ****
        SET_USE (op, new_init);
      }
  
    /* Finally create the new counter for number of iterations and add the new
       exit instruction.  */
    bsi = bsi_last (exit_bb);
    create_iv (exit_base, exit_step, NULL_TREE, loop,
! 	     &bsi, true, &ctr_before, &ctr_after);
!   exit_if = build_if_stmt (build2 (exit_cmp, boolean_type_node, ctr_after,
! 				   exit_bound),
! 			   tree_block_label (loop->latch),
! 			   tree_block_label (rest));
!   bsi_insert_after (&bsi, exit_if, BSI_NEW_STMT);
  
  #ifdef ENABLE_CHECKING
    verify_flow_info ();
--- 936,992 ----
        SET_USE (op, new_init);
      }
  
+   /* Transform the loop.  */
+   if (transform)
+     (*transform) (loop, data);
+ 
+   /* Unroll the loop and remove the old exits.  */
+   dont_exit = ((exit->flags & EDGE_TRUE_VALUE)
+ 	       ? boolean_false_node
+ 	       : boolean_true_node);
+   exit_if = last_stmt (exit->src);
+   COND_EXPR_COND (exit_if) = dont_exit;
+   update_stmt (exit_if);
+       
+   wont_exit = sbitmap_alloc (factor);
+   sbitmap_ones (wont_exit);
+   ok = tree_duplicate_loop_to_header_edge
+ 	  (loop, loop_latch_edge (loop), factor - 1,
+ 	   wont_exit, exit, NULL, DLTHE_FLAG_UPDATE_FREQ);
+   free (wont_exit);
+   gcc_assert (ok);
+   update_ssa (TODO_update_ssa);
+ 
+   /* Ensure that the frequencies in the loop match the new estimated
+      number of iterations, and change the probability of the new
+      exit edge.  */
+   freq_h = loop->header->frequency;
+   freq_e = EDGE_FREQUENCY (loop_preheader_edge (loop));
+   if (freq_h != 0)
+     scale_loop_frequencies (loop, freq_e * (new_est_niter + 1), freq_h);
+ 
+   exit_bb = single_pred (loop->latch);
+   new_exit = find_edge (exit_bb, rest);
+   new_exit->count = loop_preheader_edge (loop)->count;
+   new_exit->probability = REG_BR_PROB_BASE / (new_est_niter + 1);
+ 
+   rest->count += new_exit->count;
+   rest->frequency += EDGE_FREQUENCY (new_exit);
+ 
+   new_nonexit = single_pred_edge (loop->latch);
+   new_nonexit->probability = REG_BR_PROB_BASE - new_exit->probability;
+   scale_bbs_frequencies_int (&loop->latch, 1, new_nonexit->probability,
+ 			     REG_BR_PROB_BASE);
+ 
    /* Finally create the new counter for number of iterations and add the new
       exit instruction.  */
    bsi = bsi_last (exit_bb);
+   exit_if = bsi_stmt (bsi);
    create_iv (exit_base, exit_step, NULL_TREE, loop,
! 	     &bsi, false, &ctr_before, &ctr_after);
!   COND_EXPR_COND (exit_if) = build2 (exit_cmp, boolean_type_node, ctr_after,
! 				     exit_bound);
!   update_stmt (exit_if);
  
  #ifdef ENABLE_CHECKING
    verify_flow_info ();
*************** tree_unroll_loop (struct loop *loop, uns
*** 972,974 ****
--- 995,1009 ----
    verify_loop_closed_ssa ();
  #endif
  }
+ 
+ /* Wrapper over tree_transform_and_unroll_loop for case we do not
+    want to transform the loop before unrolling.  The meaning
+    of the arguments is the same as for tree_transform_and_unroll_loop.  */
+ 
+ void
+ tree_unroll_loop (struct loop *loop, unsigned factor,
+ 		  edge exit, struct tree_niter_desc *desc)
+ {
+   tree_transform_and_unroll_loop (loop, factor, exit, desc,
+ 				  NULL, NULL);
+ }
Index: tree-flow.h
===================================================================
*** tree-flow.h	(revision 120437)
--- tree-flow.h	(working copy)
*************** bool can_unroll_loop_p (struct loop *loo
*** 908,913 ****
--- 908,917 ----
  			struct tree_niter_desc *niter);
  void tree_unroll_loop (struct loop *, unsigned,
  		       edge, struct tree_niter_desc *);
+ typedef void (*transform_callback)(struct loop *, void *);
+ void tree_transform_and_unroll_loop (struct loop *, unsigned,
+ 				     edge, struct tree_niter_desc *,
+ 				     transform_callback, void *);
  bool contains_abnormal_ssa_name_p (tree);
  
  /* In tree-ssa-threadedge.c */



More information about the Gcc-patches mailing list