<div dir="ltr">Sure, so feel free to check out and run the code (use -newgvn to run the pass), and send patches.<div><br></div><div>Compared to the paper, the following major differences exist:<br><br></div><div>1. We just keep the worklist in RPO order using a bitvector</div><div>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</div><div>3. We don't implement phi inference.</div><div>4. All value inferencing is based on the predicate system we have</div><div>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.</div><div><br></div><div>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</div><div>(i suspect we would want post-dominance frontiers rather than their post-dominator-tree based touching, but we can fix that later)</div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Mar 11, 2015 at 4:03 AM, Rakshit Singla <span dir="ltr"><<a href="mailto:cs12b1029@iith.ac.in" target="_blank">cs12b1029@iith.ac.in</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>Hi Daniel,<br><br>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.<br><br></div>Regards<br></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Mar 10, 2015 at 9:50 PM, Daniel Berlin <span dir="ltr"><<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">The GVN algorithm used in LLVM currently (I'm rewriting it) is the basic hash based RPO algorithm.<div>The new one i'm writing is based on <a href="http://dl.acm.org/citation.cfm?id=512536" target="_blank">http://dl.acm.org/citation.cfm?id=512536</a> (see <a href="https://github.com/dberlin/llvm-gvn-rewrite" target="_blank">https://github.com/dberlin/llvm-gvn-rewrite</a>)</div><div><br></div><div>LLVM has different algorithms for both scalar PRE and load PRE.</div><div><br>They are basically variants of standard PRE algorithms transformed into SSA, but with some deliberate limitations made as implementation speed/code size trade offs.</div><div><br></div><div>At some point, i plan on implement reimplementing GVNPRE that will handle both scalars and loads (as GCC's does)</div><div><br></div><div>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.</div><div><br></div></div><div><div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Mar 10, 2015 at 4:25 AM, Rahul Jain <span dir="ltr"><<a href="mailto:1989.rahuljain@gmail.com" target="_blank">1989.rahuljain@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><p dir="ltr">This landed in my spam folder so resending it to the list! </p>
<div class="gmail_quote">On Mar 9, 2015 9:56 PM, "Rakshit Singla" <<a href="mailto:cs12b1029@iith.ac.in" target="_blank">cs12b1029@iith.ac.in</a>> wrote:<br type="attribution"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_quote"><div dir="ltr"><div><div><div><div><div><div>Hello everyone<br><br></div>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.<br><br></div>For starters, I have a couple of questions. <br><br>What is the GVN algorithm used in LLVM? Is it the one by Alpern, Wegman, Zadeck or Briggs, Cooper or some other? <br><br>How much of PRE is done in LLVM? Are any of the well known algorithms for PRE used in LLVM?<br><br></div>Thanks and regards,<br></div>Rakshit Singla<br></div>Third Year Undergrad<br></div>Indian Institute of Technology Hyderabad<br></div>
</div><br></div>
<br>_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
<br></blockquote></div>
<br>_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
<br></blockquote></div><br></div>
</div></div></blockquote></div><br></div>
</div></div></blockquote></div><br></div>