<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Sun, May 21, 2017 at 3:24 PM, David Majnemer <span dir="ltr"><<a href="mailto:david.majnemer@gmail.com" target="_blank">david.majnemer@gmail.com</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="h5">On Sun, May 21, 2017 at 9:02 AM, 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:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">(I'll reply in more depth a bit later this week, i'm slammed ATM)<br><div class="gmail_extra"><br><div class="gmail_quote"><div><div class="m_-8850657074519103396gmail-h5">On Fri, May 19, 2017 at 4:11 PM, Sanjay Patel <span dir="ltr"><<a href="mailto:spatel@rotateright.com" target="_blank">spatel@rotateright.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">[adding llvm-dev for wider audience]<br><div><div class="gmail_extra"><br><div class="gmail_quote"><div><div class="m_-8850657074519103396gmail-m_-9184931547789586787m_-4595663690091258337h5">On Fri, May 19, 2017 at 12:28 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:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div><br></div><div class="gmail_extra"><br><div class="gmail_quote"><div><div class="m_-8850657074519103396gmail-m_-9184931547789586787m_-4595663690091258337m_-4685454737949553540m_6005733253632269409gmail-m_-8430389241588207758gmail-h5">On Fri, May 19, 2017 at 11:00 AM, Davide Italiano <span dir="ltr"><<a href="mailto:davide@freebsd.org" target="_blank">davide@freebsd.org</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"><span>On Fri, May 19, 2017 at 10:00 AM, Sanjay Patel <<a href="mailto:spatel@rotateright.com" target="_blank">spatel@rotateright.com</a>> wrote:<br>
> Is "VRP" (value range propagation) in LLVM-speak "CVP" (correlated value<br>
> propagation)?<br>
><br>
> If so, we have this comment regarding compares:<br>
> // As a policy choice, we choose not to waste compile time on anything<br>
> where<br>
> // the comparison is testing local values.<br>
><br>
> Or this for div/rem:<br>
> // As a policy choice, we choose not<br>
> // to waste compile time on anything where the operands are local defs.<br>
><br>
> "Local" means in the same basic block from what I can tell by the code here.<br>
><br>
> I think this means that this pass explicitly defers handling simple cases<br>
> like:<br>
> <a href="https://reviews.llvm.org/D33342" rel="noreferrer" target="_blank">https://reviews.llvm.org/D3334<wbr>2</a><br>
> ...to another pass, and currently that pass is InstCombine (because the<br>
> patterns really can't be any simpler than the tests in that patch, right?).<br>
><br>
> I think that improving compile-time should not preclude improving<br>
> InstCombine. We should do both.<br>
><br>
<br>
</span>Just thoughts, feel free to ignore them.<br>
I didn't measure the impact in LLVM, but I'm sure you can do VRP<br>
relatively fast (GCC does that both interprocedurally and<br>
intraprocedurally and their pass is much faster in some cases than<br>
LLVM's), i.e. O(N) in practice, so, maybe we could re-evaluate this<br>
policy?<br></blockquote><div><br></div></div></div><div>Yeah, that's kind of silly, we can do much better.</div><span class="m_-8850657074519103396gmail-m_-9184931547789586787m_-4595663690091258337m_-4685454737949553540m_6005733253632269409gmail-m_-8430389241588207758gmail-"><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
I think replacing a pass in LLVM is not trivial (I'm learning it the<br>
hard way with NewGVN). OTOH, I'm still not entirely convinced<br>
`InstCombine` should handle these cases given it's already a<br>
compile-time sink?<br></blockquote><div><br></div></span></div></div></div></blockquote><div><br></div></div></div><div>Correct me where I'm going wrong.<br><br></div><div>1. We got a bug report with a perf regression that was root caused to this IR:<br><br> define i1 @xor_of_icmps(i64 %a) {<span><br> %b = icmp sgt i64 %a, 0<br></span><span> %c = icmp eq i64 %a, 1<br></span> %r = xor i1 %b, %c<br> ret i1 %r<br> }<br></div></div></div></div></div></blockquote></div></div><div>Yup</div><span class="m_-8850657074519103396gmail-"><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><div class="gmail_extra"><div class="gmail_quote"><div><br></div><div>Because this was a regression, we know that the optimal/canonical IR for this program is:<br><br> define i1 @xor_of_icmps_canonical(i64 %a) {<br> %r = icmp sgt i64 %a, 1<br> ret i1 %r<br> } <br><br></div></div></div></div></div></blockquote></span><div>Yes.</div><span class="m_-8850657074519103396gmail-"><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><div class="gmail_extra"><div class="gmail_quote"><div></div><div>2. I saw this as a bug in InstCombine because I think InstCombine's job is to canonicalize simple IR sequences.<br></div></div></div></div></div></blockquote><div><br></div></span><div>Where is the dividing line between what InstCombine does and what something else does?</div></div></div></div></blockquote><div><br></div></div></div><div>In practice? CFG transformations and inter-procedural reasoning are forbidden. </div></div></div></div></blockquote><div><br></div><div>That's just about everything though :)</div><div> </div><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"><div>The driving philosophy of InstCombine, as I know it, is "do reasonable stuff which exposes further canonicalization <wbr>opportunities." </div></div></div></div></blockquote><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"><div> </div></div></div></div></blockquote><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"><div>This mandate is widely defined but is not unreasonable in and of itself. It is unreasonable to expect InstCombine to perform _all_ canonicalization opportunities. InstCombine is a soupy combination of many passes because it is a engineering trade-off between perfect separation of concerns (performing no overlapping work with any other pass which has a specific responsibility) and having one giant pass which can do everything and anything.</div></div></div></div></blockquote><div><br></div><div>FWIW: I think it's long past turned into the latter.</div><div>If you chart the code growth, it's also actually growing at a much faster rather than all of our other optimizations combined :)</div><div><br></div><div> </div><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 class=""><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_extra"><div class="gmail_quote"><span class="m_-8850657074519103396gmail-"><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><div class="gmail_extra"><div class="gmail_quote"><div><br></div><div>3. I assumed that matching an (xor icmp, icmp) pattern can be done efficiently in InstCombine. In fact, I knew that we already did that match, so there is zero incremental cost to find this pattern in InstCombine.<br></div><div><br></div></div></div></div></div></blockquote><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><div class="gmail_extra"><div class="gmail_quote"><div>4. I knew that we already handle related and-of-cmps and or-of-cmps patterns in InstSimplify/InstCombine.<br></div></div></div></div></div></blockquote><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><div class="gmail_extra"><div class="gmail_quote"><div><br></div><div>5. Based on that, I have proposed a patch that mostly uses existing logic in those passes to solve this bug in the most general way I am aware of. It makes 2 calls to InstSimplify to find a potential fold before morphing/creating new instructions that may get folded by other existing logic.<br><br><br>Questions:<br></div><div>1. Was/is InstCombine intended to handle this transform?<br></div></div></div></div></div></blockquote><div><br></div></span><div>InstCombine has no real philosophy right now. It can handle *anything*.</div><div>The more it handles, the more people want to shove stuff in it. You can see this already. It does random store sinking, phi conversion, etc.</div><div><br></div><div>Because if some other pass handles it, then they don't get as many simplifications, because nobody has built out those places.</div><div>Without some real philosophy line drawing, instcombine expands to cover everything, gets slow and can never be replaced without introducing performance regressions.</div><div><br></div><div>It becomes the only thing that does certain things, and then people want to run it more as a result. But you can't run it more because it's slow (which also incentivizes people to make it do more, so that it catches whatever case when it does run)</div><span class="m_-8850657074519103396gmail-"><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><div class="gmail_extra"><div class="gmail_quote"><div><br>2. If there is a measurable compile-time cost for this patch, then there must be a structural
problem with InstSimplify, InstCombine, and/or the pass pipeline?<br></div><div><br></div></div></div></div></div></blockquote><div><br></div></span><div>Places like InstCombine get slower by very small percentages at a time. Really.</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><div class="gmail_extra"><div class="gmail_quote"><span class="m_-8850657074519103396gmail-"><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_extra"><div class="gmail_quote"><span class="m_-8850657074519103396gmail-m_-9184931547789586787m_-4595663690091258337m_-4685454737949553540m_6005733253632269409gmail-m_-8430389241588207758gmail-"></span><div>People seem intent on adding lots and lots of stuff to instcombine because it's easy.</div><div>This makes it harder to ever replace, while simultaneously making it slower.</div><div>It's not hard to see where that path ends up.</div><div>InstCombine does a lot of random crap that isn't even combining or graph rewrite, too, because well second and third order effects are hard.<br></div></div></div></div></blockquote><div><br></div></span></span><div>Can you provide some examples?]</div></div></div></div></div></blockquote><div><br></div><div>It does:<br><br></div><div>Demanded bits analysis</div><div>Phi translation and attempts to fold</div><div>Instruction sinking</div><div>Reassociation</div><div>Factorization</div><div>Dead code elimination</div></div></div></div></blockquote><div><br></div></span><div>It also does DSE, some memory forwarding optimizations and a restrict subset of SROA. It can also do some really weird stuff like rewriting and/or coalescing allocas. It can even do speculation :)</div><span class=""><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_extra"><div class="gmail_quote"><span class="m_-8850657074519103396gmail-"><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_extra"><div class="gmail_quote"><div> I honestly don't know where I should draw the line. If I've crossed the line, I'd like to fix it. </div></div></div></div></blockquote><div><br></div></span><div>I'm sorry if you feel like this is people saying it's you. It's really not. It's really "hey, uh, are we ever going to stop trying to shove stuff in this thing?"</div><div>I think if you look, every so often people take notice of these kinds of things and it's usually started in a random review thread. :)</div><div>As for where to draw the line, i think that's a good discussion for us all to have.</div><div>I think we *should* say what the line is, draw it, and stick to it, and probably split it up into multiple things (canonicalization, etc).</div><div><br></div><div>Truthfully, right now, Instcombine crossed whatever line you want to draw a long time ago.</div><div>It's 30k lines of code.</div><div><br></div><div>For reference:</div><div>The entirety of transforms/Scalar, combined, is only 60k lines of code.<br></div><div><br></div><div>Of course, line counting is not a great measure of a lot, i'm just pointing out it contains roughly half the code of the rest of our scalar optimization infrastructure, and 30% of the total code of it overall. It's twice as big as our entire vectorization infrastructure. It's big. It does a lot.</div><div>I'd argue that even if most of these transforms belong there, there are probably cleaner, more performance, more maintainable, and easier to reason about ways at this point to produce the same result.</div></div></div></div></blockquote><div><br></div></span><div>If there is a way to do what we do today which is more Pareto optimal, I doubt you will hear any complaints. You will hear loud complains if we made InstCombine as enjoyable to debug as SelectionDAGISel :)</div></div></div></div></blockquote><div><br></div><div>Sure.</div><div><br></div><div>Personally, i would split it into a real canonicalization face, and then a combination/optimization phase (if you still need one)</div><div><br></div><div>The canonicalizer is a set of graph rewrite rules that apply in a fixed order and are fairly easy to debug.</div><div>The combination/optimizer, ... haven't thought about.</div><div>For some significant parts of instcombine and some of the underlying instsimplify transforms it uses, newgvn subsumed it.</div><div><br></div><div>(For example, all of it's thread/backtranslate over phi transformations are subsumed, and we can do ones instcombine can't. This transform is also probably exponential time worst case as implemented in instcombine, while the newgvn impl is polynomial time. It's just not common to have long chains that meet instcombine's condition)<br><br></div><div> However, in general, will you lose some optimization by splitting it? Over the course of a single pass, vs what it does now, yes.</div><div><br></div><div>(which kind of proves the point. if it didn't do everything, you wouldn't have this issue.</div><div>You should be able to make it significantly faster and run it more though :)</div><div> </div></div></div></div>