<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Feb 24, 2015 at 10:45 AM, Philip Reames <span dir="ltr"><<a href="mailto:listmail@philipreames.com" target="_blank">listmail@philipreames.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000">
Whatever we end up deciding, I think we do need to preserve the
ability of a language frontend to generate complete garbage in the
form of unreachable code. If we decide to move in the direction of
disallowing the production of unreachable code, we need to write a
canonicalization pass that runs first thing in the pipeline. A
frontend should be able to produce unreachable code. This enables
important simplifications in the frontend.</div></blockquote><div><br></div><div>Sure.</div><div>Note that we essentially already do this in the very first actual optimization pass that gets run both in IPO mode and not IPO mode.</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 bgcolor="#FFFFFF" text="#000000"> <br></div></blockquote><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div bgcolor="#FFFFFF" text="#000000">
I happen to agree with Chandler, but I don't have a strong opinion
either way. His testing point in particular is one that resonates
with me. I'll, in practice, take testability over verification any
day. :) <br></div></blockquote><div><br></div><div>So, in the current world of "unreachable code can contain anything", it's not simply testable, contrary to chandler's assertion (while the reverse, "do not produce unreachable code" is actually pretty easily testable)</div><div>If we change that, yes, it becomes a much more tractable problem.</div><div><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 bgcolor="#FFFFFF" text="#000000">
<br>
Sanjoy's suggestion of having an "unreachable code analysis" might
be a way to split the difference. Every pass could depend on it.
If it doesn't report "no unreachable code", the pass calls a cleanup
transform utility. Any pass that wanted to spend time to "preserve"
the analysis (by making sure there was no unreachable code), could
do so. Everything would "just work". <br>
<br>
Do we have a set of unreachable, but otherwise valid, code
examples? It doesn't seem to hard to write extra run lines for each
pass. The corpus of valid but problematic examples should be common
to all passes. <br><span class="HOEnZb"><font color="#888888">
<br>
Philip</font></span><div><div class="h5"><br>
<br>
<div>On 02/23/2015 08:32 PM, Chandler
Carruth wrote:<br>
</div>
<blockquote type="cite">
<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>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, 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><br>
</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. 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. 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. 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. 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><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>
<div><br>
</div>
<div>-Chandler</div>
<div><br>
</div>
<div><br>
</div>
<div><br>
</div>
</div>
<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 link="blue" vlink="purple" lang="EN-US">
<div>
<p><span style="font-size:12.0pt;font-family:"Cambria","serif"">Hello,</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.</span></p>
<p><span style="font-size:12.0pt;font-family:"Cambria","serif""> </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.</span></p>
<p><span style="font-size:12.0pt;font-family:"Cambria","serif""> </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.</span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;font-family:"Cambria","serif""> </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:</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></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;font-family:"Cambria","serif""> </span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;font-family:"Cambria","serif"">Here
is a thread of replies from today:</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></span></span></p>
<span><font color="#888888">
<p class="MsoNormal"><span style="font-size:12.0pt;font-family:"Cambria","serif""> </span></p>
<p class="MsoNormal"><span style="font-family:"Cambria","serif"">Katya.</span></p>
<p class="MsoNormal"><span style="font-family:"Cambria","serif""> </span></p>
</font></span></div>
</div>
</blockquote>
</div>
<br>
</div>
</blockquote>
<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>