Re: [PATCH] PR 62173, re-shuffle insns for RTL loop invariant hoisting

[Kenneth Zadeck <zadeck at naturalbridge dot com>]

On 02/11/2015 06:20 AM, Jiong Wang wrote:
> 2014-12-19 15:21 GMT+00:00 Kenneth Zadeck <zadeck@naturalbridge.com>:
> > however, since i am a nice person ....
> >
> > loop-invariant solves the DF_UD_CHAIN which builds a data structure that
> > connects each use with all of the defs that reach it.   I believe that this
> > is the opposite of what you want here.
> >
> > if you really need this, you need to also turn on the DF_DU_CHAIN which
> > builds the opposite structure.    Both structures can be space hogs, but
> > they are both turned on in other places in the compiler so it is unlikely to
> > be an issue.
> Exactly, Thanks, Kenneth.
>
> This approach works from my experiment and look much better than
> previous REG_NOTE approach.
> while it do have one problem. We need the UD/DU chain built before we
> do insn re-shuffling.
> While after re-shuffling, UD chain needs update, otherwise, the later
> "check_dependecies" in find_invariant_insn may fail.
>
> although we have re-shuffle instruction 1 into 2, the later check
> still using old UD info, thus
> decide instruction 2 is not iv.
>
> 1: regA <- vfp + regB
> 2: regA <- vfp + const
>
> my current fix is to insert those re-shuffled insn into a table named
> "vfp_const_iv", then skip those
> dependencies check  for them as they don't have any dependencies.
You now are beginning to understand why Mark Wegman and I invented SSA 
form almost 30 years ago!!!!  There is no good way to keep the 
information up to data as you are changing the program.    To a large 
extent you are on your own.   If what you are suggesting works, then 
this is likely much faster than rebuilding the chains.

> > > > > > LOG_LINKs have nothing to do with single use; they point from the
> > > > > > _first_
> > > > > > use to its corresponding def.
> > > > > >
> > > > > > You might want to look at what fwprop does instead.
> > > > > Pass rtl fwprop uses df information in single-definition way, it
> > > > > doesn't really take into consideration if register is a single use.
> > > > > This often corrupts other optimizations like post-increment and
> > > > > load/store pair.  For example:
> > > > >
> > > > >     add r2, r1, r0
> > > > >     ldr rx, [r2]
> > > > >     add r2, r2, #4
> > > > > is transformed into below form:
> > > > >     add r2, r1, r0
> > > > >     ldr rx, [r1, r0]
> > > > >     add r2, r2, #4
> > > > >
> > > > > As a result, post-increment opportunity is corrupted, also definition
> > > > > of r2 can't be deleted because it's not single use.
> > > > >
> > > > > Thanks,
> > > > > bin
> > > > thanks for all these suggestion.
> > > >
> > > > Have look at the LOG_LINK build function, a simple reverse scan, while
> > > > needs to allocate big map array for all pseudo regs. Haven't looked at
> > > > similar code in fwprop,
> > > >
> > > > actually, when found the first matched insn pattern, I just want to
> > > > scan several insns next, then abort quickly if nothing meet
> > > > requirement. there is no need to build full single-use information.
> > > >
> > > > still can anyone confirm that it is safe to re-use REG_DEAD info there
> > > > without calling df_note_add_problem and df_analysis first? or I am
> > > > using those info passed down from the previous pass which calculated
> > > > these info and maybe broken?
> > > It's not safe to use REG_DEAD info without re-computing it.
> > not sure that reg_dead is the right answer even if you did re-compute it.
> > I believe you can have two parallel uses (on both sides of an if-then-else)
> > for a single def (above the if then else) and have two REG_DEAD notes.
> >
> > > Richard.