<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Feb 2, 2017 at 9:08 AM, Johannes Doerfert <span dir="ltr"><<a href="mailto:doerfert@cs.uni-saarland.de" target="_blank">doerfert@cs.uni-saarland.de</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi Daniel,<br>
<br>
I didn't read the discussion in the review but would like to ask one<br>
question anyway. In case it was already discussed elsewhere please just<br>
point me there.<br></blockquote><div><br></div><div>FWIW: It's discussed in detail in the review (i detailed the approaches other passes take to this problem, and one of our goals is precisely to not do it as slowly as they do it :P). That said, happy to answer :)</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
Why do you want to put this information in the IR instead of recomputing<br>
or preserving it like we do with other analysis results that live only<br>
in memory?<br></blockquote><div>The short version is it's very slow, and you can't actually do this in a way that is sane in an analysis.  It's been tried 3 times :)</div><div><br></div><div>We also already have issues in number of analysis that try to do this, with a significant number of open bugs due to the performance of trying do it this way.</div><div><br></div><div>IE this approach works really really well for some analysis, but is really really bad for others.  This is going to be one of the latter ones :)</div><div>One of the reasons is fairly simple:<br></div><div><br></div><div>MemorySSA, which does this, and works well, works well because there is no IR for memory. So there are no defs/uses it's replacing.</div><div><br></div><div>However, this analysis is based  regular ssa, so overlaying a completely different set of defs and uses does not mesh well with existing infrastructure.</div><div><br></div><div>(analysis that is not trying to give def/use style info tend to work well)</div><div><br></div><div>But that's precisely what we need to do in order to know what affects a given predicate.  Thus, what you would build would essentially be a duplicate copy, in memory, of the existing IR, with the names changed (you can throw away some info, obviously). Alone, this gets very slow because you'd have to walk through and duplicate sometimes thousands of uses/users into your in-memory structure, which you have to do at a minimum to be able to tell the user what uses are affected by a given piece of predicate info.</div><div><br></div><div>Even when you do this, it  in turn is hard to use in passes, because they all expect one name (really, Value *) to map to one value.  This is in fact, the whole underlying problem one is trying to solve.   Here, even if you made those fake def/uses Value *'s, it is still very tricky to not make a mess of things.</div><div>Our passes that try (GVN, EarlyCSE) do a combination of various scoped hash tables and eager IR replacement as they go to avoid this issue, but since NewGVN is meant itself to be split as an analysis/eliminator, we can't do IR replacement as we go, and the former is very mess to make work in an analysis *and* still catch all the cases.</div><div>I can point you at a branch on github where we implemented the exact approach GVN takes now, without modifying the IR, just tracking what the effects are. To say it is a complex mess is an understatement. it's also 3x as slow as the predicateinfo approach in the base case. Not to mention predicateinfo required just a small amount of code to do stuff with the compare info (and that really should be a utility), whereas the other approach was a couple thousand lines.</div><div><br></div><div>Additionally, unlike MemorySSA, this could pretty much never be kept up to date, because it needs to be updated for any modification to the IR. This is true regardless of *invalidation* (IE most changes don't change the correctness, but they still have to be applied)</div><div><br></div><div>Given that, it doesn't, IMHO, make sense to try to do that.</div><div>Also, i tried it anyway, and it's ... significantly slower, memory intensive, and not updatable :)</div><div><br></div><div>That doesn't make it impossible, mind you.  It's definitely doable,  but it's fairly complex vs doing this, and i have trouble seeing the benefits.</div><div><br></div><div>Note that i'm not the only person to go through this exercise:</div><div><br></div><div>GCC builds a nearly identical form when doing VRP (see the part where it builds ASSERT_EXPR, which is identical except they directly attach comparisons, where we don't because it constrains our ability to place predicateinfo for assume, which gcc doesn't have).</div><div>It then drops the form.</div><div><br></div><div>A number of other compilers do similar (Jikes, for example, did this).</div><div><br></div><div>Some now even go farther. For example, last i looked, Graal builds pruned SSI.</div><div> </div><div>This is all a short way of saying "yeah, i feel like we tried all the other approaches first" :P<br><br></div><div><br></div><div><br></div><div><br></div></div></div></div>