[LLVMdev] choice between SSAPRE and bitvector aporach
dberlin at dberlin.org
Fri Apr 4 14:50:36 PDT 2008
GVNPRE (which LLVM uses, see lib/Scalar/GVNPRE.cpp) is value based,
not lexical identity based like SSAPRE. As such it has different
In addition, it operates on SSA form as much as SSAPRE does
SSAPRE builds an expression PRE form, known as EPRE, sparsely, for
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
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?
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
More information about the llvm-dev