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

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?
Xuehai

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.

-bw

GVNPRE (which LLVM uses, see lib/Scalar/GVNPRE.cpp) is value based,
not lexical identity based like SSAPRE.  As such it has different
requirements.
In addition, it operates on SSA form as much as SSAPRE does

SSAPRE builds an expression PRE form, known as EPRE, sparsely, for
each variable.
This includes EPHI placement and ESSA renaming.

GVNPRE does not need to build an expression SSA form to do it's work
(It lets value numbering take care of determining the necessary
qualities)

Both take advantage of SSA, neither is really directly working on SSA form.

There is no conversion between bit vector and SSA in either one.
In the case of SSAPRE, there is a conversion from EPRE back into regular SSA.
In the case of GVNPRE, there is no conversion.

It is possible to make a sparse version of GVNPRE (IE compute it
per-variable like SSAPRE does).  I have one completed.
It is neither faster nor more memory efficient than the bitvector approach.

I strongly suggest that you reread the GVNPRE and SSAPRE papers.
The question you are asking implies you believe somehow SSAPRE is a
"true ssa" analysis and GVNPRE is not.
The reality is they both require work on top of SSA.

i"m not sure why you would think it is more suitable.

On Thu, Apr 3, 2008 at 1:11 AM, Xuehai Qian <xqian2 at cs.uiuc.edu>
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?
>  Xuehai
>  _______________________________________________
>  LLVM Developers mailing list
>  LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>  http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

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
>