Re: Jump Bypass Optimization

[law at redhat dot com]

 In message <20020518203447.GD32425@atrey.karlin.mff.cuni.cz>, Jan Hubicka 
writes:
 > > optimization on an ssa form, but, well, that work has stalled.  In
 > > the short term we might consider doing CSE on blocks in the dominator
 > > tree to at least remove its insane compile time complexity on complex
 > > flow graphs.
 > 
 > How this should work?
Conceptually it's simple.

First you want to do scoped hash table lookups.  ie, an expression may be
in the hash table multiple times -- you always want to get the most recently
added entry.

Second, each entry in the table needs to be marked with the block which
created the entry.  When you've finished walking the children of block X
in the dominator tree, then you remove entries in the hash table corresponding
to block X.  Or you can think of it as unwinding the hash table.

Third, you walk the blocks in the dominator tree and perform CSE on them 
(ie, you process blocks in the same order as you would if you were translating
from normal to SSA form).  This is a depth first walk of the dominator tree.

The only tricky part is we don't have the nice SSA properties -- so as we're
doing CSE on a block, we must allow for an expression from a previous block
to be temporarily killed, but we need to be able to "restore" it do active
status when we "unwind" the hash table.

This kind of scheme for doing CSE is discussed in Morgan, Appel and likely 
others.

The advantages are:

  * Each block is processed one time.

  * You do not rebuild the hash table for each path through the blocks --
    instead you  keep enough information to effectively "unwind" the hash table
    to previous states.

  * By working on basic blocks as computed by the CFG, it's going to fit into
    our compilation model much better than the current cse code which builds
    basic blocks on its own.

  * It effectively gives you extended basic block CSE without the cost of
    our current implementation.


Vlad had some code to attack parts of this problem from years ago.  I don't 
know
how useful it would be now.

I have code which does some of these things, but it's intimately tied to the
SSA code (in the SSA model, you do all this stuff "for free" as you're 
translating from normal form into SSA form).  I don't know if my code would
be useful either.



Probably the first step would be to convert CSE from working on lists of
insns, jump following, etc, to work on lists of insns within blocks and
blocks within extended basic blocks.  Once you've got that model into 
cse.c, you can extend the hash tables to record the information you need,
then you change the order in which you process blocks, then you put in the
code to "unwind" the hash table.

jeff