[llvm-dev] Invalid llvm-ir and unreachable code
Jeroen Dobbelaere via llvm-dev
I have found a case where an optimization pass is barfing on invalid code in an unreachable
basic block. A self referencing GEP '%x = getelementptr %x, 0, 1' is found inside a cycle of
two unreachable basic blocks)
The invalid code and the unreachable basic blocks were introduced by the function inliner.
I am wondering what is valid for these cases ?
(I did not find anything in LangRef, but I might as well have missed it)
- clearly 'dead code' (aka unreachable basic blocks) is valid in an IR ?
- I assume that the self reference in dead code is not valid ?
- should inlining do an extra effort of cleaning up such dead code blocks ?
Thanks,
Jeroen Dobbelaere
_______________________________________________
LLVM Developers mailing list
llvm...@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Roman Lebedev via llvm-dev
<llvm...@lists.llvm.org> wrote:
>
> Hi all,
>
> I have found a case where an optimization pass is barfing on invalid code in an unreachable
> basic block. A self referencing GEP '%x = getelementptr %x, 0, 1' is found inside a cycle of
> two unreachable basic blocks)
>
> The invalid code and the unreachable basic blocks were introduced by the function inliner.
>
> I am wondering what is valid for these cases ?
> (I did not find anything in LangRef, but I might as well have missed it)
>
> - clearly 'dead code' (aka unreachable basic blocks) is valid in an IR ?
> - I assume that the self reference in dead code is not valid ?
Unreachable code is permitted to take various weird shapes and forms.
So no, that is valid.
> - should inlining do an extra effort of cleaning up such dead code blocks ?
>
Which pass?
Generally, it (or the users of that code) should either use DominatoTree
to avoid handling unreachable blocks, or it should be hardened to deal
with such situations gracefully.
> Thanks,
>
> Jeroen Dobbelaere
Roman
Jeroen Dobbelaere via llvm-dev
> >
> > I have found a case where an optimization pass is barfing on invalid code in
> an unreachable
> > basic block. A self referencing GEP '%x = getelementptr %x, 0, 1' is found
> inside a cycle of
> > two unreachable basic blocks)
> >
> > The invalid code and the unreachable basic blocks were introduced by the
> function inliner.
> >
> > I am wondering what is valid for these cases ?
> > (I did not find anything in LangRef, but I might as well have missed it)
> >
> > - clearly 'dead code' (aka unreachable basic blocks) is valid in an IR ?
> Yep.
>
> > - I assume that the self reference in dead code is not valid ?
> Unreachable code is permitted to take various weird shapes and forms.
> So no, that is valid.
>
> > - should inlining do an extra effort of cleaning up such dead code blocks ?
> >
>
> Which pass?
I am not sure yet if it is a generic SROA problem or not, but if it is, I should be able
to create a bugreport.
> Generally, it (or the users of that code) should either use DominatoTree
> to avoid handling unreachable blocks, or it should be hardened to deal
> with such situations gracefully.
Thanks,
Jeroen Dobbelaere
Mehdi AMINI via llvm-dev
Hi all,
I have found a case where an optimization pass is barfing on invalid code in an unreachable
basic block. A self referencing GEP '%x = getelementptr %x, 0, 1' is found inside a cycle of
two unreachable basic blocks)
The invalid code and the unreachable basic blocks were introduced by the function inliner.
I am wondering what is valid for these cases ?
(I did not find anything in LangRef, but I might as well have missed it)
- clearly 'dead code' (aka unreachable basic blocks) is valid in an IR ?
- I assume that the self reference in dead code is not valid ?
Jeroen Dobbelaere via llvm-dev
Thanks for all the feedback !
The issue I encountered is likely not happening on the main llvm, but I believe the issue is interesting enough to
document:
- the problematic code construct consists of a cycle of 'dead' basic blocks that conditionally jumps into live blocks.
That jump introduce a connection of a dead self-referring 'getelementptr' to live code through a PHI node.
- during SROA, the scoped noalias analysis (full restrict version) does an unbounded (MaxLookup == 0) 'getUnderlyingObject' call on a pointer.
- 'getUnderlyingObject' also follows the path to the dead blocks and ends up in the self-referring 'getelementpr'.
Does this mean that 'getUnderlyingObject' should also be prepared to be handling 'invalid instructions' in 'dead code' ?
Greetings,
Jeroen Dobbelaere
Roman Lebedev via llvm-dev
<llvm...@lists.llvm.org> wrote:
>
> Thanks for all the feedback !
>
>
>
> The issue I encountered is likely not happening on the main llvm, but I believe the issue is interesting enough to
>
> document:
>
>
>
> - the problematic code construct consists of a cycle of 'dead' basic blocks that conditionally jumps into live blocks.
>
> That jump introduce a connection of a dead self-referring 'getelementptr' to live code through a PHI node.
>
> - during SROA, the scoped noalias analysis (full restrict version) does an unbounded (MaxLookup == 0) 'getUnderlyingObject' call on a pointer.
>
> - 'getUnderlyingObject' also follows the path to the dead blocks and ends up in the self-referring 'getelementpr'.
>
>
>
> Does this mean that 'getUnderlyingObject' should also be prepared to be handling 'invalid instructions' in 'dead code' ?
to assert that no cycles are encountered instead of endlessly looping.
But i *think* the problem is in your SROA changes.
Can you link me to the particular patch in question?
> Greetings,
>
>
>
> Jeroen Dobbelaere
Roman
Jeroen Dobbelaere via llvm-dev
[..]
> > - the problematic code construct consists of a cycle of 'dead' basic blocks
> that conditionally jumps into live blocks.
> >
> > That jump introduce a connection of a dead self-referring 'getelementptr'
> to live code through a PHI node.
> >
> > - during SROA, the scoped noalias analysis (full restrict version) does an
> unbounded (MaxLookup == 0) 'getUnderlyingObject' call on a pointer.
> >
> > - 'getUnderlyingObject' also follows the path to the dead blocks and ends up
> in the self-referring 'getelementpr'.
> >
> >
> >
> > Does this mean that 'getUnderlyingObject' should also be prepared to be
> handling 'invalid instructions' in 'dead code' ?
> I've just adjusted that function in 36f1c3db66f7268ea3183bcf0bbf05b3e1c570b4
> to assert that no cycles are encountered instead of endlessly looping.
>
> But i *think* the problem is in your SROA changes.
> Can you link me to the particular patch in question?
(llvm/lib/Analysis/ScopedNoAliasAA.cpp, line 269)
I checked again the endless loop: It happens _right after SROA_, in the MemorySSA pass.
Apparently, your extra check also triggers cases without my patches ? A self-reference is
likely a mild version of an 'invalid instruction' but what other constructs can we encounter
in dead blocks ?
I am wondering if we should allow (analysis) passes to follow code into dead blocks at all ?
Greetings,
Jeroen
Florian Hahn via llvm-dev
> On Mar 15, 2021, at 09:53, Jeroen Dobbelaere via llvm-dev <llvm...@lists.llvm.org> wrote:
>
> Hi Roman,
>
> [..]
>>>
>>> - the problematic code construct consists of a cycle of 'dead' basic blocks
>> that conditionally jumps into live blocks.
>>>
>>> That jump introduce a connection of a dead self-referring 'getelementptr'
>> to live code through a PHI node.
>>>
>>> - during SROA, the scoped noalias analysis (full restrict version) does an
>> unbounded (MaxLookup == 0) 'getUnderlyingObject' call on a pointer.
>>>
>>> - 'getUnderlyingObject' also follows the path to the dead blocks and ends up
>> in the self-referring 'getelementpr'.
>>>
>>>
>>>
>>> Does this mean that 'getUnderlyingObject' should also be prepared to be
>> handling 'invalid instructions' in 'dead code' ?
>> I've just adjusted that function in 36f1c3db66f7268ea3183bcf0bbf05b3e1c570b4
>> to assert that no cycles are encountered instead of endlessly looping.
>>
>> But i *think* the problem is in your SROA changes.
>> Can you link me to the particular patch in question?
>
> This is the patch that triggers the unbounded lookup: https://reviews.llvm.org/D68507
> (llvm/lib/Analysis/ScopedNoAliasAA.cpp, line 269)
>
> I checked again the endless loop: It happens _right after SROA_, in the MemorySSA pass.
>
Can you isolate the failure to just a run of MemorySSA? If so, it sounds like it would be a problem in your linked patch. I guess it would be good to know exactly where an infinite loop is triggered (and why).
Nikita Popov via llvm-dev
Roman Lebedev via llvm-dev
<Jeroen.D...@synopsys.com> wrote:
>
> Hi Roman,
>
> [..]
> > >
> > > - the problematic code construct consists of a cycle of 'dead' basic blocks
> > that conditionally jumps into live blocks.
> > >
> > > That jump introduce a connection of a dead self-referring 'getelementptr'
> > to live code through a PHI node.
> > >
> > > - during SROA, the scoped noalias analysis (full restrict version) does an
> > unbounded (MaxLookup == 0) 'getUnderlyingObject' call on a pointer.
> > >
> > > - 'getUnderlyingObject' also follows the path to the dead blocks and ends up
> > in the self-referring 'getelementpr'.
> > >
> > >
> > >
> > > Does this mean that 'getUnderlyingObject' should also be prepared to be
> > handling 'invalid instructions' in 'dead code' ?
> > I've just adjusted that function in 36f1c3db66f7268ea3183bcf0bbf05b3e1c570b4
> > to assert that no cycles are encountered instead of endlessly looping.
> >
> > But i *think* the problem is in your SROA changes.
> > Can you link me to the particular patch in question?
>
> This is the patch that triggers the unbounded lookup: https://reviews.llvm.org/D68507
> (llvm/lib/Analysis/ScopedNoAliasAA.cpp, line 269)
>
> I checked again the endless loop: It happens _right after SROA_, in the MemorySSA pass.
> Apparently, your extra check also triggers cases without my patches ? A self-reference is
> likely a mild version of an 'invalid instruction' but what other constructs can we encounter
> in dead blocks ?
Yeah, i fooled myself there.
> I am wondering if we should allow (analysis) passes to follow code into dead blocks at all ?
I wouldn't think so. It's a waste of time i would say.
Jeroen Dobbelaere via llvm-dev
>>>>
>>>> - the problematic code construct consists of a cycle of 'dead' basic blocks
>>> that conditionally jumps into live blocks.
>>>>
>>>> That jump introduce a connection of a dead self-referring 'getelementptr'
>>> to live code through a PHI node.
>>>>
>>>> - during SROA, the scoped noalias analysis (full restrict version) does an
>>> unbounded (MaxLookup == 0) 'getUnderlyingObject' call on a pointer.
>>>>
>>>> - 'getUnderlyingObject' also follows the path to the dead blocks and ends up
>>> in the self-referring 'getelementpr'.
>>>>
>>>>
>>>>
>>>> Does this mean that 'getUnderlyingObject' should also be prepared to be
>>> handling 'invalid instructions' in 'dead code' ?
>>> I've just adjusted that function in 36f1c3db66f7268ea3183bcf0bbf05b3e1c570b4
>>> to assert that no cycles are encountered instead of endlessly looping.
>>>
>>> But i *think* the problem is in your SROA changes.
>>> Can you link me to the particular patch in question?
>>
>> This is the patch that triggers the unbounded lookup: https://reviews.llvm.org/D68507
>> (llvm/lib/Analysis/ScopedNoAliasAA.cpp, line 269)
>>
>> I checked again the endless loop: It happens _right after SROA_, in the MemorySSA pass.
>>
>>Can you isolate the failure to just a run of MemorySSA? If so, it sounds like it would be a
> problem in your linked patch. I guess it would be good to know exactly where an infinite
> loop is triggered (and why).
>
>The infinite loop happens because getUnderlyingObject() is called with MaxLookup=0. getUnderlyingObject() relies on a finite depth limit to prevent >infinite loops. The problem is specific to the full restrict patch for this reason -- normally we don't perform unlimited getUnderlyingObject() >calls.
>
>The correct fix here is imho to remove the ability to call getUnderlyingObject() with MaxLookup=0, which sounds like a bad idea for pathological cases anyway.
At worst case, it should modify the result of a scoped noalias query to return 'MayAlias' over 'NoAlias'.
Greetings,
Jeroen
Jeroen Dobbelaere via llvm-dev
> blocks at all ?
> I wouldn't think so. It's a waste of time i would say.
>