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

On 24 February 2015 at 02:05, Chandler Carruth <chandlerc at google.com>
wrote:
> Will try to reply to the larger thread again soon, but a quick reply on a
> bit of a tangent...
>
> On Mon, Feb 23, 2015 at 8:45 PM, Hal Finkel <hfinkel at anl.gov>
wrote:
>>
>>  2. Should unreachable code be allowed to contain nonsense (like
>> instructions that depend on themselves)? To this, I believe the answer
is
>> no. We currently permit this, and I think that a lot of the bugs
regarding
>> unreachable code some from this. I've yet to hear a good argument
why, for
>> example, JumpThreading must produce self-referential instructions in
>> trivially-dead regions.
>
>
> I could easily see tightening the rules on what passes the verifier within
> unreachable code to try to make it substantially cheaper, easier, and less
> error prone to handle unreachable code. It seems likely that there are good
> pragmatic compromises here that would actually cost nothing. Obvious
example
> is, as you highlight, self-referential non-phi instructions could easily
> just be rejected, and asserted during construction by the IR builder.
I am worried that the compromise might be worse than the two extremes
in this case.

I don't think that rejecting

  %a = getelementptr inbounds i8* %a, i64 1

but accepting

  %a = getelementptr inbounds i8* %b, i64 1
  %b = getelementptr inbounds i8* %a, i64 1

would get us much. It would probably just make unreachable handling
bugs harder to find and test.

I don't have a strong opinion so far, but it is interesting to note
that this particular bug does showcase arguments on both sides:

* The unreachable testcase that crashes gvn is simpler than the one
that causes unreachable code to be produced.
* Having the verifier reject unreachable code at the end of a pass
would probably have made it easier to identify and reduce the issue,
as the verifier would always detect the unreachable code but the code
has to be in a particular shape to crash gvn.

On the testcase reduction side of things, the only think I would
insist on is that bb1 still counts as reachable in

bb0:
br i1 false, label %bb1, label %bb2

Cheers,
Rafael

On Tue, Feb 24, 2015 at 12:55 PM, Rafael Espíndola <
rafael.espindola at gmail.com> wrote:
> On 24 February 2015 at 02:05, Chandler Carruth <chandlerc at
google.com>
> wrote:
> > Will try to reply to the larger thread again soon, but a quick reply
on a
> > bit of a tangent...
> >
> > On Mon, Feb 23, 2015 at 8:45 PM, Hal Finkel <hfinkel at anl.gov>
wrote:
> >>
> >>  2. Should unreachable code be allowed to contain nonsense (like
> >> instructions that depend on themselves)? To this, I believe the
answer
> is
> >> no. We currently permit this, and I think that a lot of the bugs
> regarding
> >> unreachable code some from this. I've yet to hear a good
argument why,
> for
> >> example, JumpThreading must produce self-referential instructions
in
> >> trivially-dead regions.
> >
> >
> > I could easily see tightening the rules on what passes the verifier
> within
> > unreachable code to try to make it substantially cheaper, easier, and
> less
> > error prone to handle unreachable code. It seems likely that there are
> good
> > pragmatic compromises here that would actually cost nothing. Obvious
> example
> > is, as you highlight, self-referential non-phi instructions could
easily
> > just be rejected, and asserted during construction by the IR builder.
>
> I am worried that the compromise might be worse than the two extremes
> in this case.
>
Maybe.
My view is the ideal is either no-unreachable code, or unreachable blocks
only contain terminators.

>
> I don't think that rejecting
>
>   %a = getelementptr inbounds i8* %a, i64 1
>
> but accepting
>
>   %a = getelementptr inbounds i8* %b, i64 1
>   %b = getelementptr inbounds i8* %a, i64 1
>
>
Does the verifier accept the latter right now?

would get us much. It would probably just make unreachable
handling
> bugs harder to find and test.
>
> I don't have a strong opinion so far, but it is interesting to note
> that this particular bug does showcase arguments on both sides:
>
> * The unreachable testcase that crashes gvn is simpler than the one
> that causes unreachable code to be produced.
>
But this is because the passes cleanup unreachable code after themselves,
whether they need to or not :)

FWIW, at least in every pass i've looked at, outside of jump threading,
making them take unreachable code and "delete all instructions except the
terminator, and make terminator trivial" would be completely and utterly
trivial. In fact, almost *all* of them *already do this* (which is why this
bug was hard to produce a testcase for, because you have to come up with a
transformation that only one of the passes that *doesn't* clean up after
itself will do something to).

This is separate than "what does the input to the compiler look like".
I'm
fine with unreachable code coming in (because such a thing is easy to
cleanup/fix, and we in fact, already do this as the first real pass), i'm
more concerned with the contract between passes.

* Having the verifier reject unreachable code at the end of a
pass
> would probably have made it easier to identify and reduce the issue,
> as the verifier would always detect the unreachable code but the code
> has to be in a particular shape to crash gvn.
>
> On the testcase reduction side of things, the only think I would
> insist on is that bb1 still counts as reachable in
>
> bb0:
> br i1 false, label %bb1, label %bb2
>
Sure.
This is in fact, what i think the ideal for "leave unreachable blocks"
around looks like - we don't mess with the cfg, but we do get rid of all
other instructions/uses.
As i've said, this is what almost all passes *already do*.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150224/24bc882b/attachment.html>

----- Original Message -----
> From: "Rafael Espíndola" <rafael.espindola at gmail.com>
> To: "Chandler Carruth" <chandlerc at google.com>
> Cc: "Hal Finkel" <hfinkel at anl.gov>, "Katya
Romanova" <Katya_Romanova at playstation.sony.com>, "LLVM
Developers Mailing
> List" <llvmdev at cs.uiuc.edu>, "Rafael Espindola"
<rafael_espindola at playstation.sony.com>
> Sent: Tuesday, February 24, 2015 2:55:16 PM
> Subject: Re: [LLVMdev] Jump Theading/GVN bug - moving discussion to
llvm-dev
> 
> On 24 February 2015 at 02:05, Chandler Carruth <chandlerc at
google.com>
> wrote:
> > Will try to reply to the larger thread again soon, but a quick
> > reply on a
> > bit of a tangent...
> >
> > On Mon, Feb 23, 2015 at 8:45 PM, Hal Finkel <hfinkel at anl.gov>
> > wrote:
> >>
> >>  2. Should unreachable code be allowed to contain nonsense (like
> >> instructions that depend on themselves)? To this, I believe the
> >> answer is
> >> no. We currently permit this, and I think that a lot of the bugs
> >> regarding
> >> unreachable code some from this. I've yet to hear a good
argument
> >> why, for
> >> example, JumpThreading must produce self-referential instructions
> >> in
> >> trivially-dead regions.
> >
> >
> > I could easily see tightening the rules on what passes the verifier
> > within
> > unreachable code to try to make it substantially cheaper, easier,
> > and less
> > error prone to handle unreachable code. It seems likely that there
> > are good
> > pragmatic compromises here that would actually cost nothing.
> > Obvious example
> > is, as you highlight, self-referential non-phi instructions could
> > easily
> > just be rejected, and asserted during construction by the IR
> > builder.
> 
> I am worried that the compromise might be worse than the two extremes
> in this case.
> 
> I don't think that rejecting
> 
>   %a = getelementptr inbounds i8* %a, i64 1
> 
> but accepting
> 
>   %a = getelementptr inbounds i8* %b, i64 1
>   %b = getelementptr inbounds i8* %a, i64 1
> 
> would get us much.
I completely agree with this. I'd like to see the same kind of
'instruction does not dominate all uses' errors as we get for reachable
code for unreachable blocks in such cases.

 -Hal
> It would probably just make unreachable handling
> bugs harder to find and test.
> 
> I don't have a strong opinion so far, but it is interesting to note
> that this particular bug does showcase arguments on both sides:
> 
> * The unreachable testcase that crashes gvn is simpler than the one
> that causes unreachable code to be produced.
> * Having the verifier reject unreachable code at the end of a pass
> would probably have made it easier to identify and reduce the issue,
> as the verifier would always detect the unreachable code but the code
> has to be in a particular shape to crash gvn.
> 
> On the testcase reduction side of things, the only think I would
> insist on is that bb1 still counts as reachable in
> 
> bb0:
> br i1 false, label %bb1, label %bb2
> 
> Cheers,
> Rafael
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

> Maybe.
> My view is the ideal is either no-unreachable code, or unreachable blocks
> only contain terminators.
I am definitely happy with both. What worries me is introducing a
special dominance rule for unreachable blocks.
>> I don't think that rejecting
>>
>>   %a = getelementptr inbounds i8* %a, i64 1
>>
>> but accepting
>>
>>   %a = getelementptr inbounds i8* %b, i64 1
>>   %b = getelementptr inbounds i8* %a, i64 1
>>
>
> Does the verifier accept the latter right now?
Yes. %a dominates %b and %b dominates %a, so it is valid.
>> * Having the verifier reject unreachable code at the end of a pass
>> would probably have made it easier to identify and reduce the issue,
>> as the verifier would always detect the unreachable code but the code
>> has to be in a particular shape to crash gvn.
>>
>> On the testcase reduction side of things, the only think I would
>> insist on is that bb1 still counts as reachable in
>>
>> bb0:
>> br i1 false, label %bb1, label %bb2
>
>
> Sure.
> This is in fact, what i think the ideal for "leave unreachable
blocks"
> around looks like - we don't mess with the cfg, but we do get rid of
all
> other instructions/uses.
> As i've said, this is what almost all passes *already do*.
OK, short of some new argument the other side I agree with you. Given
that "bb1" is still reachable in the "br i1 false" case, I
don't see a
lot of value in allowing unreachable blocks with just terminators in
it. I would suggest just making the verifier reject trivially forward
unreachable blocks.

At least initially, I would keep utility functions accepting
unreachable and keep a verifier mode that accepts it to so that we can
test them.

Cheers,
Rafael