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] Fix PR43571


This fixes the dominator walker to walk dominator children in an
order that tries to ensure all predecessors have already been
visited.  Otherwise for a CFG like

      A
   /     \
  B       C
   \     /
      D

we visit the dominator children of A which are B, C and D in
random order while we should make sure to visit B and C before
visiting D.  That is important if the worker can for example
merge PHI args in D or can record information from B and C
that needs not be invalidated when leaving the blocks (like
SSA constants or copies in DOM).

Thus, the patch ensures that DOM can do its work properly
without iterating.

Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.

Richard.

2010-04-16  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/43571
	* domwalk.c (walk_dominator_tree): Walk the dominator
	sons in more optimal order.

Index: gcc/domwalk.c
===================================================================
*** gcc/domwalk.c.orig	2010-04-16 15:59:40.000000000 +0200
--- gcc/domwalk.c	2010-04-16 16:05:35.000000000 +0200
*************** walk_dominator_tree (struct dom_walk_dat
*** 144,149 ****
--- 144,152 ----
    basic_block dest;
    basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks * 2);
    int sp = 0;
+   sbitmap visited = sbitmap_alloc (last_basic_block + 1);
+   sbitmap_zero (visited);
+   SET_BIT (visited, ENTRY_BLOCK_PTR->index);
  
    while (true)
      {
*************** walk_dominator_tree (struct dom_walk_dat
*** 184,189 ****
--- 187,194 ----
  	  if (walk_data->before_dom_children)
  	    (*walk_data->before_dom_children) (walk_data, bb);
  
+ 	  SET_BIT (visited, bb->index);
+ 
  	  /* Mark the current BB to be popped out of the recursion stack
  	     once children are processed.  */
  	  worklist[sp++] = bb;
*************** walk_dominator_tree (struct dom_walk_dat
*** 213,223 ****
  	    }
  	}
        if (sp)
! 	bb = worklist[--sp];
        else
  	break;
      }
    free (worklist);
  }
  
  void
--- 218,261 ----
  	    }
  	}
        if (sp)
! 	{
! 	  int spp;
! 	  spp = sp - 1;
! 	  if (walk_data->dom_direction == CDI_DOMINATORS)
! 	    /* Find the dominator son that has all its predecessors
! 	       visited and continue with that.  */
! 	    while (1)
! 	      {
! 		edge_iterator ei;
! 		edge e;
! 		bool found = true;
! 		bb = worklist[spp];
! 		FOR_EACH_EDGE (e, ei, bb->preds)
! 		  {
! 		    if (!dominated_by_p (CDI_DOMINATORS, e->src, e->dest)
! 			&& !TEST_BIT (visited, e->src->index))
! 		      {
! 			found = false;
! 			break;
! 		      }
! 		  }
! 		if (found)
! 		  break;
! 		/* If we didn't find a dom child with all visited
! 		   predecessors just use the candidate we were checking.
! 		   This happens for candidates in irreducible loops.  */
! 		if (!worklist[spp - 1])
! 		  break;
! 		--spp;
! 	      }
! 	  bb = worklist[spp];
! 	  worklist[spp] = worklist[--sp];
! 	}
        else
  	break;
      }
    free (worklist);
+   sbitmap_free (visited);
  }
  
  void


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