<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Jul 15, 2016 at 4:00 PM, Andrew Trick <span dir="ltr"><<a href="mailto:atrick@apple.com" target="_blank">atrick@apple.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><span class=""><br><div><blockquote type="cite"><div>On Jul 15, 2016, at 3:38 PM, Sanjoy Das <<a href="mailto:sanjoy@playingwithpointers.com" target="_blank">sanjoy@playingwithpointers.com</a>> wrote:</div><br><div><span style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;float:none;display:inline!important">> Note that this is also necessary to makes post-dominance correct (but we</span><br style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><span style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;float:none;display:inline!important">> already do it in most cases, but i think there are still bugs open about</span><br style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><span style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;float:none;display:inline!important">> correctness)</span><br style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><br style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><span style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;float:none;display:inline!important">Yeah, right now in LLVM we cannot rely on post-dominance to conclude</span><br style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><span style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;float:none;display:inline!important">"guaranteed to execute" which isn't ideal.  There's at least one place</span><br style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><span style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;float:none;display:inline!important">I know where a more precise post-dominance could be used. :)</span></div></blockquote></div><div><br></div></span>I completely understand the philosophical criticism, but<div><br><div>- LLVM clearly made the decision/tradeoff to allow implicit early exits, and I’m pretty certain that will never change.</div><div><br></div></div></div></blockquote><div>Nobody is looking to change that necessarily, or at least i'm not, only to make the impact not "correctness requires N^2 algorithms or other things that *already* are slowing down the compiler"</div><div> <br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><div><div></div><div>- LLVM made the decision/tradeoff not to maintain a postdom tree throughout most of the pass pipeline</div><div><br></div></div></div></blockquote><div>Well, actually, this one is likely to change. The only issue here is keeping it updated, and i have a solution for that.<br></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 style="word-wrap:break-word"><div><div></div><div>- Fundamentally, you don’t really lose anything.</div></div></div></blockquote><div><br></div><div>This i'm going to disagree with :)</div><div>This is basically an argument that postdom is not needed, and i think we've actually proven precisely the opposite.  We approximate it in so many places, and then go looking for harder and harder ways to optimize those cases using dominance, and make ever  more complicated "if the cfg kinda looks like that, well then, sure go for it" instead of using postdom.  We never get all the cases, and we're well past the point where it would be easier to use postdom in most of these places.</div><div> <br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><div><div> It’s an easy analysis to find the exit points and mark blocks.</div></div></div></blockquote><div><br></div><div>I'm going to simply point out that may throw was fixed using N^2 methods in at least 3 passes, with no intention to change it.  I haven't looked at the rest, but i also suspect there are more bugs hiding here that nobody has noticed yet.</div><div><br></div><div>So you are right that it may be algorithmically easy, it's apparently not so easy that people did it.</div><div>I will also point out that the design decision lead to simple trivial test cases that exercised this design decision being broken for years in the compiler in on-by-default optimization passes.</div><div><br></div><div>Does that make it the wrong design?<br>No, of course not, but it is empirical evidence that maybe things were missing from "making it easy to get it right", etc.</div><div><br></div><div> <br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><div><div> Doing a CFG walk instead of a PostDom walk is typically not such a big deal.</div></div></div></blockquote><div><br></div><div>Using post-dom to approximate classical control dependence, as we do in several places, has led to a mess nobody quite understands in those places.</div><div> </div><div>But, like i said, i have a plan to fix this by making post-dom updates automatic. There are now incremental dominance update algorithms that are very fast in the common case (IE 100x faster than computing from scratch) and even in the very pathological cases, 2x faster than computing from scratch.  This comes out to "fast enough" to maintain postdom without anyone having to think about anything other than saying "i added an edge" or "i deleted an edge".</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><div></div><div>I often overload the term “control dependence” here. When I say a load is control dependent on a branch, I don’t mean that the load’s block is classically control dependent on the branch, I mean that the load is illegal to speculate above the branch. Yes they are two different things, but I don’t have a better term to use for that dependence information.</div><div><br></div><div>-Andy</div></div></blockquote></div><br></div></div>