[LLVMdev] choice between SSAPRE and bitvector aporach

[Daniel Berlin]

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