<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Feb 2, 2017 at 5:01 PM, Daniel Berlin via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.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">Now with even the right llvm-dev :)<div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Feb 2, 2017 at 4:59 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"><br><div class="gmail_extra"><br><div class="gmail_quote"><div><div class="m_7603874095837050174h5">On Thu, Feb 2, 2017 at 3:52 PM, Chandler Carruth <span dir="ltr"><<a href="mailto:chandlerc@gmail.com" target="_blank">chandlerc@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div class="gmail_quote"><div><div class="h5"><div><div class="m_7603874095837050174m_3740344798178940488gmail-h5"><div dir="ltr">On Wed, Feb 1, 2017 at 8:33 PM Daniel Berlin <<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr" class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg">Hey folks,<div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"><br class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"></div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg">After a long amount of discussion both offline and on, I put a pass/intrinsic to add extended SSA up at <a href="http://reviews.llvm.org/D29316" class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg" target="_blank">http://reviews.llvm.org/D29316</a><wbr>.</div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"><br class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg">Sean asked me to share it more broadly on llvm-dev, so here you go :)</div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"><br class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"></div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg">For those not familiar with extended-SSA, it's described in the paper "ABCD: Eliminating Array Bounds Checks on Demand".</div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"><br class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"></div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg">There is a very large amount of explanation in the summary of the review that i don't want to paste here , but the short version is:<br class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"><br class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"></div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg">1. We make copies of variables where they are used in comparisons that lead to assumes or branches and it's possible to determine something about their value from the branch.</div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"><br class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"></div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg">IE</div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg">define i32 @test1(i32 %x) {</div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"> %cmp = icmp eq i32 %x, 50</div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"> br i1 %cmp, label %true, label %false</div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg">true:</div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"> ret i32 %x<br class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"></div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg">false:</div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"> ret i32 1</div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg">}</div></div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"><br class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"></div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg">becomes</div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"><br class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"></div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg">define i32 @test1(i32 %x) {</div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"> %cmp = icmp eq i32 %x, 50</div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"> br i1 %cmp, label %true, label %false</div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"><br class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"></div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg">true: ; preds = %0</div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg">; Has predicate info</div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg">; branch predicate info { TrueEdge: 1 Comparison: %cmp = icmp eq i32 %x, 50 }</div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"> %x.0 = call i32 @llvm.predicateinfo.i32(i32 %x)</div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"> ret i32 %x.0</div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"><br class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"></div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg">false: ; preds = %0</div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"> ret i32 1</div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg">}</div></div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"><br class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"></div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg">All uses that are dominated by the predicate info are renamed to use it.</div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"><br class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"></div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg">2. We do so very quickly (it takes about 600ms to do 2 million blocks with comparisons, by comparison, most passes simply crash or take forever on the same file. As an example, GVN takes 500 seconds), and only insert when and where the operands are used.</div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"><br class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"></div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg">3. The intrinsics are marked so they do not affect optimization (and currently, passes that use them all destroy them). They also can detect when they've been moved to make sure they are still valid if need me.</div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"><br class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"></div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg">4. They could be updated pretty easily if we wanted</div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"><br class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"></div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg">With one real downside:</div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"><br class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"></div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg">5. We modify the IR in an analysis to do so :(</div></div></blockquote><div><br></div></div></div></div></div><div>One question that occurred to me reading this, that probably is just my ignorance, but maybe you can help =]</div><div><br></div><div>Any particular reason to not model this as essentially a shadow of the IR?</div></div></div></blockquote><div><br></div></div></div><div>Done already :) Checkout the newgvn-predicateinfo-uses branch on github :P.</div><div><br></div><div>The short version there's no point is because it's complex, and you can't update it *anyway* at that point :P</div><span><div><br></div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div class="gmail_quote"><div> I'm imagining creating a map from operand -> predinfo, where predinfo essentially models these inserted intrinsics, and rather than RAUW-ing dominated uses, you insert a mapping for dominated uses.</div></div></div></blockquote><div><br></div></span><div>Ah, if you could easily map from operand to predinfo, this might even work okayish (you now have O(number of uses in the entire program) lookups you've added to newgvn, to check if they have predicateinfo, but okay).</div><div><br></div><div>But to start:</div><div>You can't do this easily<br></div><div>The operands you need to attach to are Use's.</div><div> </div><div>Because</div><div><br></div><div>if (a == 0)<br> ret a</div><div>else</div><div> ret a</div><div><br></div><div>each a has different info.</div><div><br></div><div>The predicateinfo insertion accomplishes this by physical renaming, so the values have different name, and every use of a given predicateinfo has the same value.</div><div><br></div><div>But in a virtual form, it looks like this:</div><div><br></div><div>IE this looks like:<br><div>if (a == 0)<br></div><div>1 = PredicateDef(branch, blah blah blah)</div><div>PredicateUse(1), but really attached to *this use* of a, not to ret</div><div>ret a</div><div>else</div><div>2 = PredicateDef(branch, blah blah blah)</div><div>PredicateUse(2), but really attached to *this use* of a, not to ret</div><div>ret a</div></div><div><br></div><div><br></div><div>(even if you really wanted to, you have to attach to uses because ách operand of an instruction could be a use of different predicateinfo) </div><div><br></div><div>You can in fact, attach to uses.</div><div>You can even do something like the above (IE have predicate use which stores a regular use), so you know what's up, and have a real def/use form. </div><div><br></div><div>it goes downhill from there, though, precisely because the info is attached to Use's :(</div><div><br></div><div>First, we have two types of things that would use this pass.<br><br></div><div>Lazy things, and propagating things.</div><div><br></div><div>Lazy things, that return a value for a thing, all at once, in a single call (LVI if it had no caches) , might be convertible to use this.</div><div><br></div><div>You have the problem that getting a use from an instruction operand is not currently trivial (we'd have to have a getOperandUse that mirrors getOperand or something), but not too bad.</div><div><br></div><div>But all of ours really cache stuff, so they are really lazy propagating things.</div><div><br></div><div><br></div><div>and Propagating things (CVP, SCCP, GVN, etc) , which are the rest of them, are hard.</div><div><br></div><div>They want to store tables of info by Value.</div><div><br></div><div>But we need to store per-use info.</div><div><br></div><div>If you modify them to store per-use info for all uses, you take a 5-15x memory and time hit, to store info about each use, where most have the same info.</div><div><br></div><div>Any elimination you do also has to look up per-use info, not per-value info like we do now, which means the elimination becomes (Defs/Uses) times slower too :(</div><div><br></div><div>This pretty much puts it out of the range of sanity.</div><div>But let's say you are smarter than the average bear. You want to build a hybrid scheme, where you only store special use info for the things that are special.</div><div>You realize you can make your virtual form, above, Value *'s. Then you have the name you need because the PredicateDef is a name you can use like a normal Instruction def.</div><div><br></div><div>But you still have to convert back and forth between Use's and Value's everywhere, and plumb Use& through anything that does lookups, so you can get a Use& and turn it into the right thing above.</div><div>Then, replacement of the original operands, to make it not have to do lookups on every use in the program, requires storing the original uses in the PredicateUse class, so you know which uses in the original IR correspond to which uses in the Predicate virtual IR.</div><div><br></div><div>This is a *lot* of plumbing. and because Use's have an operator Value*, the liklihood you create a lot of bugs is high, because if you use a use where you meant use.getUser(), it still works :(</div><div><br></div><div>You are creative though, and get this all working.</div><div><br></div><div>That gets you value numbering (it's a lot harder in a lot of other cases), without even needing an O(uses in the program) hash table.</div><div><br></div><div>Now you have to try eliminate stuff.</div><div><br></div><div>In everything but NewGVN, you have to rewrite the eliminators. They all replace as they go, which means either double the replace cost (since you have to replace the original uses, and for predicates, the original uses and the uses in the predicate uses), or even more fun as you try to update utilities to understand about looking up uses :(</div><div><br></div><div><br></div><div>In NewGVN, we eliminate in O(uses that have the same value) time, by sorting congruence class instruction defs and uses by global and local dominator numbers, and using a stack.</div><div>So we now need to order the predicate defs, uses, and regular defs and uses all in the right order (and replace the right defs with predicate defs so the lookup happens right) in dominator order to know which replaces which.<br></div><div>But you can't use dominates() to do this, because it doesn't understand these,etc.</div><div><br></div><div>So you have to create a local instruction numbering, and figure out, where in them each thing goes.</div><div>Which you can do, at some non-trivial cost over regular instruction numbering</div><div><br></div><div>This is just the simple parts, mind you.</div><div>After all this, you have something that takes pretty much double the memory, a lot harder to understand, *and* it still gets invalidated easily :)</div><div><br></div><div>But it's immutable! </div><div><br></div><div>There's kind of no upside, and lots of downsides, both in building it, and trying to use it:)<br></div><span><div><br></div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div class="gmail_quote"><div><br></div><div>This would cause it to be a pure analysis again. It would make it relatively fragile of course -- it would be easily invalidated. But given how fast it is to compute, for several of the use cases it seems like it would be sufficient (NewGVN seems like it could tolerate computing this each time, etc.</div><div><br></div><div>Anyways, I'm sure you've looked at something like this, and I'm curious what goes wrong with it.</div><span class="m_7603874095837050174m_3740344798178940488gmail-"><div><br></div></span></div></div></blockquote><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div class="gmail_quote"><span class=""><span class="m_7603874095837050174m_3740344798178940488gmail-"><div></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr" class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"><br class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg"></div><div class="m_7603874095837050174m_3740344798178940488gmail-m_8789023869231092101gmail_msg">The main user at the moment is NewGVN, which uses it to do the equivalent of GVN's propagateEquality. I'd be happy to make it a utility called from NewGVN instead of an analysis. A number of folks online and off asked me to make it usable for others, so i did that :) Some folks want to use it to cleanup existing passes (EarlyCSE, etc), some want to use it in new passes.</div></div></blockquote><div><br></div></span></span><div>So, this definitely sounds useful, but I think that while it mutates the IR itself, I think it should just be a utility routine that passes call at their start to put the IR into the form they need. It'll be a bit tricky if you want analysis passes to observe this form -- you may not be able to use the caching infrastructure of the new PM at all for such analyses and may need to express them as stand alone utilities as well.</div></div></div></blockquote><div><br></div></span><div>Yeah, i'm just going to make it a utility </div></div></div></div></blockquote></div></div></blockquote><div><br></div><div>I don't have much content to add to the discussion, but since I originally asked you to bring the discussion to llvm-dev: making it a utility SGTM.</div><div><br></div><div>-- Sean Silva</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><span><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div class="gmail_quote"><div> <br></div></div></div></blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div class="gmail_quote"><div></div><div>If it is reasonable to do so, I'd also suggest a cleanup utility that ensures the mutated IR doesn't escape the end of the pass either to avoid having to teach the rest of the optimizer about it. But if there are reasons this doesn't work well, maybe we can use actual PHI nodes for this to simplify what we have to teach the rest of the optimizer about?</div></div></div></blockquote><div><br></div></span><div>We can use single argument phi nodes for branches, but it gets tricky with assume, because you need to place the phi at the beginning of the assume block, and you can't do this if the operands are defined in the same block, so you'd have to place n ones with the same info in every successor block, and hope the assume didn't do anything useful in the rest of the assume block or something :(</div><div><br></div><div>I'll also write a verifier.</div><span><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div class="gmail_quote"><span class="m_7603874095837050174m_3740344798178940488gmail-HOEnZb"><font color="#888888"><div><br></div><div>-Chandler</div></font></span><div><br></div><div>PS: In case folks are wondering, the reason *why* I think this needs not be an analysis is because in the new PM we rely heavily on caching of analysis results. This caching behavior means that when things are run isn't very clear and we'd like to avoid ordering dependencies between two analyses running over the same IR to make things more debuggable later on. I can dive into more details here as useful of course.</div></div></div>
</blockquote></span></div><br></div></div>
</blockquote></div><br></div>
<br>______________________________<wbr>_________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
<br></blockquote></div><br></div></div>