[LLVMdev] GVN PRE algorithms in LLVM

[Rakshit Singla]

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

[Rahul Jain]

This landed in my spam folder so resending it to the list!

_______________________________________________
LLVM Developers mailing list
LLV...@cs.uiuc.edu         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

[Daniel Berlin]

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.

[Rakshit Singla]

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

[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)