[LLVMdev] GVN PRE algorithms in LLVM

[Daniel Berlin]

Sure, so feel free to check out and run the code (use -newgvn to run the
pass), and send patches.

Compared to the paper, the following major differences exist:

1. We just keep the worklist in RPO order using a bitvector
2. We don't implement the predicate system they do.  We use a variant of
the one GVN used to, because it does not require a post-dominator tree
3. We don't implement phi inference.
4. All value inferencing is based on the predicate system we have
5. The algorithm marks things as touched uselessly in some cases given our
predicate system. Our propagateChangeInEdge is muchbetter in this respect,
we only mark downstream phi nodes.

If you want something larger to do, it'd be interesting to implement their
predicate system and value inference and see if it is really worth the cost
(i suspect we would want post-dominance frontiers rather than their
post-dominator-tree based touching, but we can fix that later)


On Wed, Mar 11, 2015 at 4:03 AM, Rakshit Singla <cs12b1029 at iith.ac.in>
wrote:

> Hi Daniel,
>
> I also had the same algorithm (the one by Karthik Gargi) in mind when I
> asked about GVN. I had thoughts of implementing it in LLVM and since it is
> already being written, I'd like to contribute to the project and help in
> any way possible.
>
> Regards
>
> On Tue, Mar 10, 2015 at 9:50 PM, Daniel Berlin <dberlin at dberlin.org>
> wrote:
>
>> The GVN algorithm used in LLVM currently (I'm rewriting it) is the basic
>> hash based RPO algorithm.
>> The new one i'm writing is based on
>> http://dl.acm.org/citation.cfm?id=512536 (see
>> https://github.com/dberlin/llvm-gvn-rewrite)
>>
>> LLVM has different algorithms for both scalar PRE and load PRE.
>>
>> They are basically variants of standard PRE algorithms transformed into
>> SSA, but with some deliberate limitations made as implementation speed/code
>> size trade offs.
>>
>> At some point, i plan on implement reimplementing GVNPRE that will handle
>> both scalars and loads (as GCC's does)
>>
>> If you have interest in working on stuff, i'm happy to chat/help point
>> out whatever I can. Depends on what you want to do.
>>
>>
>> On Tue, Mar 10, 2015 at 4:25 AM, Rahul Jain <1989.rahuljain at gmail.com>
>> wrote:
>>
>>> This landed in my spam folder so resending it to the list!
>>> On Mar 9, 2015 9:56 PM, "Rakshit Singla" <cs12b1029 at iith.ac.in> wrote:
>>>
>>>> Hello everyone
>>>>
>>>> I am Rakshit Singla, a third year undergrad at IIT Hyderabad, India. I
>>>> finished a basic compilers course last semester and am currently doing a
>>>> compiler optimizations course.  I have been exploring LLVM for the past few
>>>> months (wrote a front-end for the Classroom Object Oriented Language and
>>>> have been studying pieces of code.) I would like to work with LLVM and
>>>> contribute to the community.
>>>>
>>>> For starters, I have a couple of questions.
>>>>
>>>> What is the GVN algorithm used in LLVM? Is it the one by Alpern,
>>>> Wegman, Zadeck or Briggs, Cooper or some other?
>>>>
>>>> How much of PRE is done in LLVM? Are any of the well known algorithms
>>>> for PRE used in LLVM?
>>>>
>>>> Thanks and regards,
>>>> Rakshit Singla
>>>> Third Year Undergrad
>>>> Indian Institute of Technology Hyderabad
>>>>
>>>>
>>>> _______________________________________________
>>>> LLVM Developers mailing list
>>>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>>>
>>>>
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>>
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150311/bb25ef27/attachment.html>