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

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.

>
>  -bw
>
>
> _______________________________________________
>  LLVM Developers mailing list
>  LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>  http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

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?

--Vikram

On Fri, Apr 4, 2008 at 2: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?
>
Yes, I think that that was the major problem with it.

-bw

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