[LLVMdev] DominanceFrontier/PostDominanceFrontier for PRE

[Daniel Berlin]

On Sun, Nov 3, 2013 at 9:19 AM, Christopher Wood
<christopherwood07 at gmail.com> wrote:
> On Sun, Nov 3, 2013 at 1:02 AM, Daniel Berlin <dberlin at dberlin.org> wrote:
>>
>> As for a "better" way to implement PRE, it depends on what algorithm
>> you want to use. If you just want to write a PRE pass, that's easy
>> enough without dominance frontiers.
>
>
> I simply want to write a PRE pass to get a better understanding of the
> transformation. Any tips on where to get started (beyond the papers you
> provided) for someone -new- to the game?

Okay, well, SSAPRE is actually a fairly hard paper to implement
correctly if this is your first go-around.

If you want something that gives you an intro to PRE (though the
formulation is not "standard" compared to most papers), take a look at
http://researcher.watson.ibm.com/researcher/files/us-akundu/thesis-mtech.ps

It's implementable, and it'll work, and doesn't require a large amount
of detail discovery by the user.

Also, if you look at LLVM's svn history, there are old PRE
implementations that have been deleted:
http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/Transforms/Scalar/PRE.cpp?view=log&pathrev=25348
(e-path PRE, like the paper above)

http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/Transforms/Scalar/GVNPRE.cpp?revision=80766&view=markup&pathrev=83192
(GVNPRE)

Making a worthwhile PRE that is not slow tends to be quite an engineering task.


>
>>
>>
>> If you want to implement the original SSAPRE, i suggest looking at
>> http://jcse.kiise.org/posting/2-3/jcse_2-3_31.pdf
>>
>
> Thanks - I will read through this paper.

>
> Chris