<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Feb 23, 2015 at 8:32 PM, Chandler Carruth <span dir="ltr"><<a href="mailto:chandlerc@google.com" target="_blank">chandlerc@google.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">So, first things first.<div><br></div><div>Handling unreachable code is annoying. I agree. However, its important to characterize how annoying. Most code is not unreachable, and we're (obviously) fine just bailing on such crazy code paths. So in practice the common cost is keeping a local set to detect cycles in the graph where we aren't expecting them. We are essentially always traversing a linked list representing this graph. Because these linked list nodes don't have any particular reason to have high locality, we have a cache-hostile traversal where we have to do primarily local and cache friendly book-keeping at each step to catch duplication. I suspect that this has a very small (but non-zero) impact on compile time.</div><div><br></div></div></blockquote><div><br></div><div>So it's worse than this.</div><div><br></div><div>It also means that doing something like "walk the graph" is no longer sufficient to generate correct code. It's not just about cycles.</div><div><br></div><div><br></div><div>Let's take an example:</div><div><br>PromoteMemoryToRegisters has a rename pass. This rename pass walks blocks from entry, following successors, renaming values to use the nearest definition. After this is done, it's done.</div><div><br></div><div>Except, it isn't.</div><div>Because you see, then it has to go and see whether it missed some alloca's, because they were unreachable.</div><div><br>And then it has to go and see if any of the blocks ended up with phi nodes that have predecessors that are unreachable, , because it has to replace those with undef.</div><div>And so on.</div><div>(It actually turns out this is not enough, and this handling is buggy).</div><div><br></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 dir="ltr"><div></div><div>Handling unreachable code is also error prone. We have had a long history of bugs here. So if it were free to get rid of unreachable code, that would be super awesome.</div><div><br></div><div><br></div><div>The first problem to realize is that for a large chunk of LLVM, we can't actually get rid of handling unreachable code. Passes are quite likely to create unreachable code while running</div></div></blockquote><div><br></div><div>Which passes, exactly?</div><div><br></div><div>I am going to assert, based on experience writing almost all of the opt passes llvm has (except a vectorizer :P), that it is entirely possible, and not even difficult, to avoid creating unreachable code in these passes. I'm also going to point out that *roughly all the other compilers in the world* do not allow it either :)</div><div>Or at least, not have it at the point at which you need to call a utility or another pass.</div><div> </div><div>So i would say your assertion that things are quite likely to create it is wrong. Things may temporarily create it, but there is simply no need, at all, to expose it to *anything else*.</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>, and that will mean that all of the utilities will end up needing to be conservatively correct and handle unreachable code even when they don't need to. =/</div></div></blockquote><div><br></div><div>So i strongly disagree with this.</div><div>This is an assertion based on the way the world is now, where things willy-nilly create unreachable code and expect the rest of the world to deal with it. I don't believe it is even that difficult to get to a world where this isn't treat.</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 dir="ltr"><div></div><div><br></div><div>The second problem is that cleaning up unreachable code isn't free. The code which is most likely to create unreachable code is similarly likely to destroy the analysis information we would use to remove it cheaply. </div></div></blockquote><div><br></div><div>I disbelieve this :)</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>And even then, just walking lists of basic blocks as we go out of the function is going to dirty cache lines that we might not have any other reason to look at. I can genuinely imagine cases where batching this will be beneficial. Will it outstrip the cost of handling it? I don't know. But I think it will mitigate the gains, especially if the gains aren't as significant as we might naively think.</div><div><br></div><div><br></div><div>The third problem I have is that this makes it much harder to constructively produce a correct IR transformation pass. When transforming the IR we must never forget about regions we have made unreachable.</div></div></blockquote><div><br></div><div>Almost all algorithms i can think of already expect to have to clean up unreachable regions and delete dead blocks. It's only LLVM that doesn't do it.</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> A single mistake here will cascade to a verification failure. This is the reverse of the problem we have today where your pass must *accept* unreachable IR. </div></div></blockquote><div><br></div><div>But is also *much* easier to verify, because the number of points in which predecessors are modified, or edges redirected, is actually not that large. At worst, *those* are the only places that can create forward-unreachable code. So you have some bounded test test. On the other hand, accepting "whatever input" is not a bounded problem. People can come up with crazier and crazier input you must accept.</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>But I think the constructive reasoning is much easier. It makes it harder to have a bug through omission of a case.</div><div><br></div><div><br></div><div>The fourth problem I have is related to the third problem. How do we gain confidence in the correctness of any IR transformation? We must construct test cases that we believe will exercise the system. It seems *incredibly* easier to construct test cases with interesting unreachable IR patterns that should all be handled, than to construct test cases where the pass will happen to form unreachable IR patterns in each way and ensure that none escape the pass. </div></div></blockquote><div><br></div><div>I fundamentally do not understand why you believe this. The number of places that create unreachable code is finite, bounded, and testable. You cannot create unreachable code out of magic. </div><div>You are right that it is easier to create test cases ith interesting unreachable IR patterns, but there is an infinite number of them.</div><div> <br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>One is essentially covering input diversity, the other has to cover *output* diversity, and must prove the negative. We fundamentally must gain confidence that the pass *never* produces unreachable IR. This seems much harder than demonstrating that it does handle unreachable IR.</div><div><br></div><div><br></div><div>The fifth problem I have is also related to the third and fourth problems. Precluding unreachable code seems likely to make tools like delta test case reduction dramatically less effective. Now, when cutting edges in the CFG to minimize a test case they must actually build the graph and prune all unreachable code.</div></div></blockquote><div><br>Again, this is just "not hard". All the other compilers in the world do this, and do it cheaply.</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> </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><br></div><div><br></div><div>All of these problems seem surmountable, but in aggregate, they make me strongly doubt that the benefit is worth the cost.</div><span class="HOEnZb"><font color="#888888"><div><br></div><div>-Chandler</div><div><br></div><div><br></div><div><br></div></font></span></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Feb 23, 2015 at 1:04 PM, Romanova, Katya <span dir="ltr"><<a href="mailto:Katya_Romanova@playstation.sony.com" target="_blank">Katya_Romanova@playstation.sony.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div lang="EN-US" link="blue" vlink="purple">
<div>
<p><span style="font-size:12.0pt;font-family:"Cambria","serif"">Hello,<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;font-family:"Cambria","serif"">I encountered a problem triggered by Jump-Threading optimization. This pass is creating an unreachable block with an instruction that is not well formed, which then causes the
subsequent GVN pass to enter an infinite loop.<u></u><u></u></span></p>
<p><span style="font-size:12.0pt;font-family:"Cambria","serif""><u></u> <u></u></span></p>
<p><span style="font-size:12.0pt;font-family:"Cambria","serif"">I have submitted a bug report and proposed fix to llvm-commits. This bug opened a can of worms. I was asked to move the discussion to llvm-dev to reach for a wider audience.<u></u><u></u></span></p>
<p><span style="font-size:12.0pt;font-family:"Cambria","serif""><u></u> <u></u></span></p>
<p><span style="font-size:12.0pt;font-family:"Cambria","serif"">>> Can we move the general discussion to llvm-dev? This probably warrants a wider audience.<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;font-family:"Cambria","serif""><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;font-family:"Cambria","serif"">Here is the original post and a couple of replies from last week:<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;font-family:"Cambria","serif""><a href="http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20150216/261330.html" target="_blank">http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20150216/261330.html</a><u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;font-family:"Cambria","serif""><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;font-family:"Cambria","serif"">Here is a thread of replies from today:<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;font-family:"Cambria","serif""><a href="http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20150223/261463.html" target="_blank">http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20150223/261463.html</a><span><font color="#888888"><u></u><u></u></font></span></span></p><span><font color="#888888">
<p class="MsoNormal"><span style="font-size:12.0pt;font-family:"Cambria","serif""><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-family:"Cambria","serif"">Katya.<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-family:"Cambria","serif""><u></u> <u></u></span></p>
</font></span></div>
</div>
</blockquote></div><br></div>
</div></div><br>_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
<br></blockquote></div><br></div></div>