On Thu, 2006-01-26 at 11:20 +0100, Bernd Schmidt wrote: > Joern RENNECKE wrote: > > For easier reviewing, I have attached the diff to the cfgcleanup version > > previous to the patch backout. > > Thanks. Let me see if I understood the problem - please correct me if I > describe anything incorrectly. > > The previous cross jumping code didn't care about register liveness, > since it just checked for identical instruction streams. The new, more > clever code, requires that regsets are identical at the end of the > blocks we're trying to match. In addition, cross-jumping can modify > blocks, requiring us to update life information (by calling a global > update_life_info in struct_equiv_init), which is the really expensive > part that caused the slowdown (how often did we end up updating life info?).
We already update life info way too much, even without struct-equiv (Before struct equiv, this was done because flow's dce relied on register liveness, and we called it from everywhere under the sun, usually deep within other functions nobody realized were doing it). I can tell you that *without* struct equiv, we update liveness at least 19 or 20 times per compile, on average. Some are much much higher, because each cleanup_cfg iteration causes a life update. This is a true time sink in the compiler. > > The new patch prevents multiple updates by introducing > STRUCT_EQUIV_SUSPEND_UPDATE. However, I don't see how this is safe > given that cross jumping will modify basic blocks and change the set of > registers live at their ends. > > Is there a way to keep life info accurate when doing the cross jump (so > we don't set any dirty flags)? Hard, but probably possible. It's also probably expensive. > Or, possibly, change the algorithm so > that it visits blocks in a different order - dirtying more blocks before > doing a global life update? If Joern has found a way to avoid updating liveness until he is done with the struct-equiv stuff (even if this means avoiding checking certain blocks because the liveness may be out of date), IMHO that is the best solution. No algorithm that has to iterate, *and update global liveness on each iteration*, will ever really be fast enough that you want it on all the time. IMHO. We already do it with cleanup_cfg (where we do it because we run flow's dce in the middle of cfg cleanups on each iteration), and it is one of the slowest parts of the backend we've got right now. > > I'm not sure what the best way to keep the svn history sane is. When/if > > the patch is approved, should I first do an > > svn merge -r108792:108791, check that in, and then apply the patch with > > the actual new stuff? > > Maybe > > svn diff -r108792:108791 |patch -p0 > patch <fixes.diff > svn commit > change the first command to svn merge -r108792:108791 and you've got it right (the difference being that merge in reverse will properly delete/readd files, and patch -p0 will not) > > Bernd
