llvm dev - Apr 2008 - [LLVMdev] choice between SSAPRE and bitvector aporach

On Fri, Apr 4, 2008 at 5:58 PM, Vikram S. Adve <vadve at cs.uiuc.edu>
wrote:
> On Apr 4, 2008, at 4:51 PM, Daniel Berlin wrote:
>
>  > On Fri, Apr 4, 2008 at 2:38 AM, Bill Wendling <isanbard at
gmail.com>
>  > wrote:
>  >> On Apr 2, 2008, at 10:11 PM, Xuehai Qian wrote:
>  >>> Hi LLVMers,
>  >>>   I am a PHD student in CS dept in UIUC, I am doing a project
for
>  >>> Vikram's course, it is about PRE. I would like to know
why you
>  >>> didn't
>  >>> choose SSAPRE in LLVM, since it seems to be more suitable for
LLVM
>  >>> (it
>  >>> can operate directly on SSA form and avoid the conversion
between
>  >>> SSA
>  >>> and bit-vector). Can anyone tell me the reason?
>  >>
>  >> Hi Xuehai,
>  >>>
>  >>
>  >> If I remember correctly, there were several details that the
paper
>  >> assumed that made adapting it to work in LLVM very difficult.
>  >
>  > It would at least require side-data structures to store the
>  > occurrences and expression phis.
>
>
>  Dan,
>
>  Doesn't the paper also assume the invariant that phi operands are
>  effectively dead after the Phi, which is true right after SSA is
>  constructed, but potentially not after transformations?
I do not recall this being *required*. It certainly will miss
optimizations if you have a pruned form (there are still testcases in
gcc bugzilla i believe), but i do not believe it will generate
incorrect code.
I could be misremembering.
The main annoying invariant i recall is that it requires SSA live
ranges of original program variables do not overlap in order for ESSA
renaming to come out correct.    Even simple optimizations on renaming
forms will generate destroy this invariant.
It certainly can be made true as a pre-pass through further renaming.
It is also trivially true of all non-renaming FUD chain variants of SSA

--Dan

On Apr 4, 2008, at 8:28 PM, Daniel Berlin wrote:
> On Fri, Apr 4, 2008 at 5:58 PM, Vikram S. Adve <vadve at cs.uiuc.edu>
> wrote:
>>
>>
>> Dan,
>>
>> Doesn't the paper also assume the invariant that phi operands are
>> effectively dead after the Phi, which is true right after SSA is
>> constructed, but potentially not after transformations?
> I do not recall this being *required*. It certainly will miss
> optimizations if you have a pruned form (there are still testcases in
> gcc bugzilla i believe), but i do not believe it will generate
> incorrect code.
> I could be misremembering.
> The main annoying invariant i recall is that it requires SSA live
> ranges of original program variables do not overlap in order for ESSA
> renaming to come out correct.    Even simple optimizations on renaming
> forms will generate destroy this invariant.
Actually, what I was describing was equivalent to this.
>
> It certainly can be made true as a pre-pass through further renaming.
Yes, but that would just undo the benefits of some of the  
optimizations that can make such live ranges overlap, e.g., GVN.  So  
it seems undesirable to do this.

> It is also trivially true of all non-renaming FUD chain variants of  
> SSA
I'm not sure what you mean by 'FUD' here.  In any case, I think the
problem is non-trivial.

--Vikram
http://www.cs.uiuc.edu/~vadve
http://llvm.org/

On Fri, Apr 11, 2008 at 12:02 AM, Vikram S. Adve <vadve at cs.uiuc.edu>
wrote:
>
>  On Apr 4, 2008, at 8:28 PM, Daniel Berlin wrote:
>
>  > On Fri, Apr 4, 2008 at 5:58 PM, Vikram S. Adve <vadve at
cs.uiuc.edu>
>  > wrote:
>  >>
>  >>
>
> >> Dan,
>  >>
>  >> Doesn't the paper also assume the invariant that phi operands
are
>  >> effectively dead after the Phi, which is true right after SSA is
>  >> constructed, but potentially not after transformations?
>  > I do not recall this being *required*. It certainly will miss
>  > optimizations if you have a pruned form (there are still testcases in
>  > gcc bugzilla i believe), but i do not believe it will generate
>  > incorrect code.
>  > I could be misremembering.
>  > The main annoying invariant i recall is that it requires SSA live
>  > ranges of original program variables do not overlap in order for ESSA
>  > renaming to come out correct.    Even simple optimizations on
renaming
>  > forms will generate destroy this invariant.
>
>  Actually, what I was describing was equivalent to this.
>  > It certainly can be made true as a pre-pass through further renaming.
>
>  Yes, but that would just undo the benefits of some of the
>  optimizations that can make such live ranges overlap, e.g., GVN.  So
>  it seems undesirable to do this.
yes
>
>
>
>  > It is also trivially true of all non-renaming FUD chain variants of
>  > SSA
>
>  I'm not sure what you mean by 'FUD' here.  In any case, I
think the
>  problem is non-trivial.
Factored Use-Def.

See, e.g., http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=323280

Because of how they work (phi nodes but no renaming of variables) they
do not allow overlapping live ranges.
Most also avoid the need to do out-of-ssa, they can just drop their
chains and phi nodes.