This is the mail archive of the gcc@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]

Re: [tree-ssa] CFG cleanup (was: Re: clean)


In message <1060175235.16753.61.camel@steven.lr-s.tudelft.nl>, Steven Bosscher 
writes:
 >I'm trying to implement some of the transformations we need to fully
 >implement their algorithm (I sent a patch to Jeff yesterday because I
 >know he's been looking at this kind of thing).
Yup.  It's on my list of things to look at -- mostly to see how much of
the infrastructure I need to do jump threading out of a dominator tree.

A goodly number of the cases I'm seeing where we miss things that the
path following code in cse1 catches are ultimately related to jump
threading.

Let's consider:

  if (whatever)
     fu = 1;
  else
     fu = 0;

  if (fu)
    blah ()
  else
    oof ()


Even though "fu" is not a compile-time constant, we have enough information
to eliminate the second conditional via jump threading. 

There's a number of sub-problems we have to solve to do this kind of
optimization -- including the ability to create new PHI nodes or
expand existing PHI nodes.  Which is why I'm interested in your work.

 >(Note of frustration: It still _does_ pass all testing of C/C++ with no
 >new regressions, but it doesn't bootstrap!?)
Not unusual.  Bootstraps are usually a more thorough test than the testsuite.

 >if (...)
 >  goto block1;
 >else
 >  goto block1;
 >
 >as
 >
 >if (...)
 >     / \
 >    /   \
 >block1  block1
 >
 >and in this case it's easy to see that the branch is useless and can be
 >removed.
 >
 >But we have to represent the same code as:
 >
 >if (...)
 >     / \
 >    /   \
 >   /    block3
 >  /	goto block1
 >block2
 >goto block1
Right.

To get this (and do it in a general way) you want to implement tail
merging/cross jumping.

Note that tail merging/cross jumping is a general issue and will remain
even when we get to a point where we don't have these nested control
structures.


 >Next, we fail to merge empty blocks (ie. blocks with only non-executable
 >stmts, such as labels or empty stmts).  Until this is fixed, this
 >prevents us from forwarding jumps like this:
The more general problem is that we don't merge blocks A & B where B
is the only successor of A and A is the only predecessor of B.

If you solve that problem, then at least some of the empty blocks should
disappear.

The difficulty in that problem is (of course) our nested control structure
and linking of statements together.  We can't simply splice a chain of
statements out and move them to a new location.

Jeff


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