<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Sun, Feb 5, 2017 at 12:25 PM, Nuno Lopes <span dir="ltr"><<a href="mailto:nunoplopes@sapo.pt" target="_blank">nunoplopes@sapo.pt</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">Hi Daniel,<br>
<br>
Many thanks for working on this!<br>
SSI/e-SSA is the only way I'm aware of for doing efficient sparse analyses, so I'm definitely in favor of adding support for it in LLVM!<br>
<br>
I read the discussion so far and did a cursory review of the patches, and I have just a few questions:<br>
- Is your plan to keep e-SSA form all the time (do it once and maintain it throughout the pipeline), or do it in the passes that need it and then get of it at end of the pass? </blockquote><div><br></div><div>At the moment, get rid of it.</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"> My concern (similar to Sanjoy's) is the increased overhead for matching patterns and so on. </blockquote><div><br></div><div>So far i have measured exactly none, FWIW.</div><div><br></div><div>I'm also not worried because given how much we try to match tons of useless variants, i'm positive i could make it net zero compile time no matter what happened by removing wasted matching time :)</div><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"> For example, how would instcombine work? </blockquote><div>Assuming you wished to use it there, the intrinsic already has the returned attribute said, which states, specifically, that it always returns its first argument.</div><div><br></div><div>If instcombine doesn't take advantage, it already has a problem with intrinsics marked with the returned attribute :)</div><div>(though yeah, they currently only exist in backends)</div><div><br></div><div><br></div><div>As for how you would make it work, there is no magic, of course</div><div>We either change the matchers to see through it or we don't.</div><div>Both are valid options, with their own tradeoffs. Nobody has yet approached me about adding it to instcombine, so i haven't tried to formulate an opinion which way i'd go :)</div><div><br></div><div><br></div><div>Note that other intrinsics, such as noalias, have the same issue.</div><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"> Would we change the m_*() matchers to know how to see through the intrinsic?<br>
<br>
- What you've implemented never creates phi nodes, right? (as opposed to ABCD paper)<br></blockquote><div><br></div><div>Correct.</div><div>It originally did, but it's not possible to sanely create phi nodes for assumes in all cases.</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">
At least it seems that the current algorithm seems to bail out if the successor has multiple predecessors. </blockquote><div><br></div><div>This is because it's not possible to place info in such cases without phi nodes, and even then it's not clear that it makes sense.</div><div><br></div><div>Also note that such cases are all critical edges (otherwise i can't see how they have info to propagate :P), and if you break the critical edges, it works just fine.</div><div><br></div><div>The need to split critical edges is pretty much true for maximal results for any optimization.</div><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">This might be an ok abstraction for GVN, but for things like CVP it's probably not. CVP merges information incoming from multiple edges (as any other fancier abstractions we may want to have in the future will).<br></blockquote><div><br></div><div><br></div><div>It's important to note: we sort phi node uses into the predecessor block they belong to, so that restriction does *not* apply to the typical phi node use case.</div><div><br></div><div><br></div><div>IE given:<br><div>define i32 @test12(i32 %x) {</div><div> </div><div> %cmp = icmp eq i32 %x, 0</div><div> br i1 %cmp, label %cond_true, label %cond_false</div><div><br></div><div> cond_true:</div><div> br label %ret</div><div><br></div><div> cond_false:</div><div> br label %ret</div><div><br></div><div> ret:</div><div> %res = phi i32 [ %x, %cond_true ], [ %x, %cond_false ]</div><div> ret i32 %res</div><div> }</div></div><div><br></div><div><br></div><div>You will get:<br><div> ; CHECK-LABEL: @test12(</div><div> ; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[X:%.*]], 0</div><div> ; CHECK-NEXT: br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[COND_FALSE:%.*]]</div><div> ; CHECK: cond_true:</div><div> ; CHECK-NEXT: [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]])</div><div> ; CHECK-NEXT: br label [[RET:%.*]]</div><div> ; CHECK: cond_false:</div><div> ; CHECK-NEXT: [[X_1:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]])</div><div> ; CHECK-NEXT: br label [[RET]]</div><div> ; CHECK: ret:</div><div> ; CHECK-NEXT: [[RES:%.*]] = phi i32 [ [[X_0]], [[COND_TRUE]] ], [ [[X_1]], [[COND_FALSE]] ]</div><div> ; CHECK-NEXT: ret i32 [[RES]]</div></div><div><br></div><div>(as you can see, we test this)</div><div><br></div><div>So the cases i think you are thinking about, are not problems except in one degenerate case, which is where critical edges lead directly to the use.</div><div><br></div><div>In such cases, note that the merges it performs can be proved to miss information or be non-optimal in the case of critical edges, even as it tries now.</div><div><br></div><div>All that said ...</div><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">
Any plans to support this? (i.e., is the current algorithm "easily" upgradable to support this scenario?)<br></blockquote><div><br></div><div>It is easy to do, but it is ... messy, IMHO.</div><div><br></div><div>Note that such a thing is generally a mess.</div><div><br></div><div>Here is the degenerate case:<br><br></div><div><br></div><div>As an example:<br><div> define i32 @f1(i32 %x) {</div><div> bb0:<br></div><div> %cmp = icmp eq i32 %x, 0</div><div> br i1 %cmp, label %bb2, label %bb1</div><div> bb1:</div><div> br label %bb2</div><div> bb2:</div><div> %cond = phi i32 [ %x, %bb0 ], [ %x, %bb1 ]</div><div> %foo = add i32 %cond, %x</div><div> ret i32 %foo</div><div> </div><div> }</div></div><div><br></div><div>the critical edge from bb0 to bb2 causes us to have no place to place predicateinfo in the current algorithm for the true branch (we will placefalse info).</div><div><br></div><div>You could also always place it before each branch its for (because that block should dominate all uses in the conditional edges already) .<br></div><div><br>The actual placement is irrelevant, BTW. In the renaming algorithm, by the time it goes to place them, it already knows what it *should* dominate.<br></div><div><br></div><div>The only thing it gets "wrong" is the phi uses, because they are placed in the predecessor blocks right now as we sort.</div><div><br></div><div>But because we see them there, we can detect this case and change placement.</div><div>Because they are guaranteed to be at the beginning of the successor block, you are guaranteed that, if you want to insert, the only thing that can be between them and the def you want to insert there is other phi uses in the same boat.</div><div>So you can lookahead in the stream, find that def, insert it, use it, and pretend everything's great (without even pushing it onto the stack!)</div><div><br></div><div>This is tricky in a one-pass algorithm, as it's really changing a simple renaming automaton into something that has two modes "critical phi use" and "regular" mode. In critical phi use mode, it finds the def, inserts it, and keeps processing until it hits a non-phi use. Then it shifts back into regular mode.</div><div>But there's also only exactly one case all of the above work affects:<br></div><div><br></div><div>The case where the phi node with the use is a direct successor of the branch, such that the edge to that use is critical.</div><div><br></div><div>In any case, this is also precisely the problem that splitting critical edges resolves, and if you use break-crit-edgse on the above, you get right answers all the time :)</div><div><br></div><div>Note also that the thing that we replace, propagateEquality in GVN, also restricts itself to single predecessors, and simply attempts to propagate directly into critical phi node uses to avoid the issue (which we can't do since NewGVN is an analysis followed by an eliminator).</div><div><br></div><div>So yes, we can fix this case if we need to.</div><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">
<br>
- For a function/intrinsic marked as "returned(1) readnone", the obvious optimization to do would be to RAUW the return with the argument (and kill the function call altogether -- assuming readnone allows that; but I lost track of that discussion). Does instcombine do that? </blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> I understand that piggybacking on this existing feature is a good thing, but I'm just wondering if, say, InstCombine won't simply revert e-SSA?<br></blockquote><div><br></div><div>NewGVN is the only pass that uses it ATM, and it destroys the form.</div><div>The current expectation is that anything that uses it will destroy it.</div><div>This is the deliberate outcome of this discussion right now :)</div><div><br></div><div>If it becomes slow enough that we want to keep it up to date, IMHO, we can burn that bridge when we come to it. <br></div><div><br></div><div>At the point at which we are trying to keep predicateinfo up to date in a large number of places, i'd argue we should just move to e-ssa/ssi as the default and be done with it. Since that's what you'll have effectively done anyway.</div><div><br></div><div>I think it would be reasonable to see where it gets used, and if enough places, make a decision what to do.</div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><br>
- In processBranch/processAssume you also consider branches on ANDs/ORs of comparisons, and then each comparison is processed individually. However, this seems incorrect for one of the branches:<br>
if (a && b) {<br>
...<br>
} else {<br>
// holds: !a OR !b<br>
use(a)<br>
use(b)<br>
}<br>
<br>
Right now it seems that the information that is attached to the else branch is !a AND !b, which would be incorrect. </blockquote><div><br></div><div>I could be pedantic and say the only information attached is a comparison, the branch, and whether the edge is the true edge or the false edge :)</div><div>Which is correct.</div><div><br></div><div>It also chains the info to give you the entire string of comparisons that were applied.</div><div><br></div><div>However, in practice you are right, and clients are not likely to get this right with what i've given them.</div><div><br></div><div>Since in practice, the only useful derived info is in the true branch of and, and the false branch of or, i'm going to make it not attach info to the other branch.</div><div><br></div><div>Unless you can see a case it makes sense to?</div><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"> I haven't seen the client of this analysis, so this is just speculation, but the interface doesn't seem to have any indication for this case. Or maybe I'm misreading the code :)<br></blockquote><div><br></div><div>No, you are correct. It just happens that the only client is smart enough to do something sane (i think :P)</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">
<br>
- Now slightly unrelated: do you know of other representations capable of handling relational analyses? For example, with e-SSA:<br>
if (x+y > 0) {<br>
// predicate info attached to 'x+y' only </blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
use(x)<br>}</blockquote><div><br></div><div>We could do that with this pass, actually.</div><div><br></div><div>It's a question of where you terminate the operand-finding.</div><div><br></div><div>You could actually just make it DFS the comparison operation and collect operands until you hit all the leaves, and insert for those.This would be a simple modification to collectCmpOperands.</div><div>(it will still be smart enough to only insert if there are actual uses affected by info).</div><div><br></div><div>We don't do that ATM, but there isn't anything i can see that would stop you.</div><div><br></div><div>The goals i set were to replace propagateEquality in GVN with NewGVN, so we pretty much only produce info that we can directly propagate.</div><div><br></div><div>It all depends on how many names you want to generate.</div><div><br></div><div>I believe the study i saw, which tried splitting at different places, came to the conclusion that the best "bang for buck" was e-ssa.</div><div><br>IE the percent more you get from more was not worth the cost.</div><div><br></div><div>But when i spoke with them about it, their biggest time-waste was actually "we insert a lot of useless phis for operations that never get used, because computing liveness is hard". But as i've shown here, you don't even need to explicitly compute it to solve that problem. So who knows, maybe it does pay to split everywhere once that cost is eliminated.</div><div><br></div><div>I'd put this one in the "evaluation necessary".</div><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"> <br></blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
So at use(x) no information will be available, even if we know that FWIW 'x+y > 0' holds there. I don't think LLVM has any analysis that can track these kind of symbolic relations, but I was just curious if there's anything out there that can handle such analyses?<br></blockquote><div><br></div><div><br></div><div>The folks i know who do this, in fact start with e-ssa and go from there, with the caveats i listed :)</div><div><br></div><div><br></div></div></div></div>