[LLVMdev] Jump Theading/GVN bug - moving discussion to llvm-dev

[Philip Reames]

On 02/24/2015 10:51 AM, Hal Finkel wrote:
> ----- Original Message -----
>> From: "Philip Reames" <listmail at philipreames.com>
>> To: "Chandler Carruth" <chandlerc at google.com>, "Katya Romanova" <Katya_Romanova at playstation.sony.com>, "Nick Lewycky"
>> <nlewycky at google.com>
>> Cc: llvmdev at cs.uiuc.edu, "Hal Finkel" <hfinkel at anl.gov>, "Rafael Espindola" <rafael_espindola at playstation.sony.com>,
>> "Sanjoy Das" <sanjoy at playingwithpointers.com>, "David Majnemer" <david.majnemer at gmail.com>
>> Sent: Tuesday, February 24, 2015 12:45:51 PM
>> Subject: Re: Jump Theading/GVN bug - moving discussion to llvm-dev
>>
>> 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.
> And this is exactly what I don't understand. Why would a frontend need to produce "complete garbage" in unreachabe code?
Er, my wording was poor here.  I did not mean the self referential 
case.  I simply meant an unreachable block.  I meant to say that a 
frontend shouldn't have to remove all statically unreachable blocks 
before passing it to LLVM.  Not producing self referential instructions 
seems like a perfectly reasonable restriction.  :)
>
>   -Hal
>
>> 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.
>>
>> 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. :)
>>
>> 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".
>>
>> 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.
>>
>> Philip
>>
>>
>> On 02/23/2015 08:32 PM, Chandler Carruth wrote:
>>
>>
>>
>> So, first things first.
>>
>>
>> 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.
>>
>>
>> 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.
>>
>>
>>
>>
>> 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. =/
>>
>>
>>
>>
>> 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.
>>
>>
>>
>>
>> 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.
>>
>>
>>
>>
>> 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.
>>
>>
>>
>>
>> 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.
>>
>>
>>
>>
>> All of these problems seem surmountable, but in aggregate, they make
>> me strongly doubt that the benefit is worth the cost.
>>
>>
>> -Chandler
>>
>>
>>
>>
>>
>>
>>
>>
>> On Mon, Feb 23, 2015 at 1:04 PM, Romanova, Katya <
>> Katya_Romanova at playstation.sony.com > wrote:
>>
>>
>>
>>
>>
>>
>> Hello,
>>
>> 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.
>>
>>
>>
>> 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.
>>
>>
>>
>>>> Can we move the general discussion to llvm-dev? This probably
>>>> warrants a wider audience.
>>
>>
>> Here is the original post and a couple of replies from last week:
>>
>> http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20150216/261330.html
>>
>>
>>
>> Here is a thread of replies from today:
>>
>> http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20150223/261463.html
>>
>>
>>
>> Katya.
>>
>>
>>
>>