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] Do not recurse walking the CFG in phiprop


As suggested by Paolo this fixes/generalizes get_all_dominated_blocks
and uses it to avoid recursion in the CFG walk in phiprop.

Bootstrapped and tested on x86_64-unknown-linux-gnu, applied to trunk.

Richard.

2009-04-20  Richard Guenther  <rguenther@suse.de>

	* basic-block.h (get_all_dominated_blocks): Declare.
	* dominance.c (get_all_dominated_blocks): New function.
	* tree-cfg.c (get_all_dominated_blocks): Remove.
	(remove_edge_and_dominated_blocks): Adjust.
	* tree-ssa-phiprop.c (tree_ssa_phiprop_1): Fold in ...
	(tree_ssa_phiprop): ... here.  Use get_all_dominated_blocks
	instead of recursing.

Index: gcc/basic-block.h
===================================================================
*** gcc/basic-block.h	(revision 146390)
--- gcc/basic-block.h	(working copy)
*************** extern VEC (basic_block, heap) *get_domi
*** 938,943 ****
--- 938,945 ----
  extern VEC (basic_block, heap) *get_dominated_by_region (enum cdi_direction,
  							 basic_block *,
  							 unsigned);
+ extern VEC (basic_block, heap) *get_all_dominated_blocks (enum cdi_direction,
+ 							  basic_block);
  extern void add_to_dominance_info (enum cdi_direction, basic_block);
  extern void delete_from_dominance_info (enum cdi_direction, basic_block);
  basic_block recompute_dominator (enum cdi_direction, basic_block);
Index: gcc/dominance.c
===================================================================
*** gcc/dominance.c	(revision 146390)
--- gcc/dominance.c	(working copy)
*************** get_dominated_by_region (enum cdi_direct
*** 782,787 ****
--- 782,814 ----
    return doms;
  }
  
+ /* Returns the list of basic blocks including BB dominated by BB, in the
+    direction DIR.  The vector will be sorted in preorder.  */
+ 
+ VEC (basic_block, heap) *
+ get_all_dominated_blocks (enum cdi_direction dir, basic_block bb)
+ {
+   VEC(basic_block, heap) *bbs = NULL;
+   unsigned i;
+ 
+   i = 0;
+   VEC_safe_push (basic_block, heap, bbs, bb);
+ 
+   do
+     {
+       basic_block son;
+ 
+       bb = VEC_index (basic_block, bbs, i++);
+       for (son = first_dom_son (dir, bb);
+ 	   son;
+ 	   son = next_dom_son (dir, son))
+ 	VEC_safe_push (basic_block, heap, bbs, son);
+     }
+   while (i < VEC_length (basic_block, bbs));
+ 
+   return bbs;
+ }
+ 
  /* Redirect all edges pointing to BB to TO.  */
  void
  redirect_immediate_dominators (enum cdi_direction dir, basic_block bb,
Index: gcc/tree-cfg.c
===================================================================
*** gcc/tree-cfg.c	(revision 146390)
--- gcc/tree-cfg.c	(working copy)
*************** gimple_purge_dead_abnormal_call_edges (b
*** 6681,6700 ****
    return changed;
  }
  
- /* Stores all basic blocks dominated by BB to DOM_BBS.  */
- 
- static void
- get_all_dominated_blocks (basic_block bb, VEC (basic_block, heap) **dom_bbs)
- {
-   basic_block son;
- 
-   VEC_safe_push (basic_block, heap, *dom_bbs, bb);
-   for (son = first_dom_son (CDI_DOMINATORS, bb);
-        son;
-        son = next_dom_son (CDI_DOMINATORS, son))
-     get_all_dominated_blocks (son, dom_bbs);
- }
- 
  /* Removes edge E and all the blocks dominated by it, and updates dominance
     information.  The IL in E->src needs to be updated separately.
     If dominance info is not available, only the edge E is removed.*/
--- 6681,6686 ----
*************** remove_edge_and_dominated_blocks (edge e
*** 6754,6760 ****
  		    get_immediate_dominator (CDI_DOMINATORS, e->dest)->index);
    else
      {
!       get_all_dominated_blocks (e->dest, &bbs_to_remove);
        for (i = 0; VEC_iterate (basic_block, bbs_to_remove, i, bb); i++)
  	{
  	  FOR_EACH_EDGE (f, ei, bb->succs)
--- 6740,6746 ----
  		    get_immediate_dominator (CDI_DOMINATORS, e->dest)->index);
    else
      {
!       bbs_to_remove = get_all_dominated_blocks (CDI_DOMINATORS, e->dest);
        for (i = 0; VEC_iterate (basic_block, bbs_to_remove, i, bb); i++)
  	{
  	  FOR_EACH_EDGE (f, ei, bb->succs)
Index: gcc/tree-ssa-phiprop.c
===================================================================
*** gcc/tree-ssa-phiprop.c	(revision 146390)
--- gcc/tree-ssa-phiprop.c	(working copy)
*************** next:;
*** 325,365 ****
    return phi_inserted;
  }
  
- /* Helper walking the dominator tree starting from BB and processing
-    phi nodes with global data PHIVN and N.  */
- 
- static bool
- tree_ssa_phiprop_1 (basic_block bb, struct phiprop_d *phivn, size_t n)
- {
-   bool did_something = false; 
-   basic_block son;
-   gimple_stmt_iterator gsi;
- 
-   for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
-     did_something |= propagate_with_phi (bb, gsi_stmt (gsi), phivn, n);
- 
-   for (son = first_dom_son (CDI_DOMINATORS, bb);
-        son;
-        son = next_dom_son (CDI_DOMINATORS, son))
-     did_something |= tree_ssa_phiprop_1 (son, phivn, n);
- 
-   return did_something;
- }
- 
  /* Main entry for phiprop pass.  */
  
  static unsigned int
  tree_ssa_phiprop (void)
  {
    struct phiprop_d *phivn;
  
    calculate_dominance_info (CDI_DOMINATORS);
  
    phivn = XCNEWVEC (struct phiprop_d, num_ssa_names);
  
!   if (tree_ssa_phiprop_1 (ENTRY_BLOCK_PTR, phivn, num_ssa_names))
      gsi_commit_edge_inserts ();
  
    free (phivn);
  
    return 0;
--- 325,358 ----
    return phi_inserted;
  }
  
  /* Main entry for phiprop pass.  */
  
  static unsigned int
  tree_ssa_phiprop (void)
  {
+   VEC(basic_block, heap) *bbs;
    struct phiprop_d *phivn;
+   bool did_something = false; 
+   basic_block bb;
+   gimple_stmt_iterator gsi;
+   unsigned i;
  
    calculate_dominance_info (CDI_DOMINATORS);
  
    phivn = XCNEWVEC (struct phiprop_d, num_ssa_names);
  
!   /* Walk the dominator tree in preorder.  */
!   bbs = get_all_dominated_blocks (CDI_DOMINATORS,
! 				  single_succ (ENTRY_BLOCK_PTR));
!   for (i = 0; VEC_iterate (basic_block, bbs, i, bb); ++i)
!     for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
!       did_something |= propagate_with_phi (bb, gsi_stmt (gsi),
! 					   phivn, num_ssa_names);
! 
!   if (did_something)
      gsi_commit_edge_inserts ();
  
+   VEC_free (basic_block, heap, bbs);
    free (phivn);
  
    return 0;


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