thr3ads.net - llvm dev - [LLVMdev] Multiple connected components in live interval [Apr 2015]

If this information is useful, please help other people find it:
Share via:

Quentin Colombet

2015-Apr-17 16:52 UTC

[LLVMdev] Multiple connected components in live interval

Hi Jonas,

When is the MachineVerifier complaining?
I mean after which pass?

Thanks,
-Quentin
> On Apr 17, 2015, at 7:17 AM, Jonas Paulsson <jonas.paulsson at
ericsson.com> wrote:
> 
> Hi,
> 
> thanks for answering, but the COPY is there already from after isel. It is
a copy of a subreg, after a a call returning 64 bits.
> 
>         call <ga:@safe_div_func_uint64_t_u_u>
>         %vreg45<def> = COPY %r0
>         %vreg46<def> = COPY %r1
>         %vreg3<def> = COPY %vreg46         
<<<<<<<<<<<<<<<<<<
>         ST %vreg46, %vreg0
>         ST %vreg46, %vreg1
>         brr_uncond <BB#4>
> 
> Does this ring any bell? Could there be any place that misses something
about the resulting LiveInterval due to a phys reg copy?
> 
> thanks
> 
> /Jonas
> 
> PS Quentin, as I said I could not reproduce this error on any in-tree
target.
Ah right.
> 
> 
> On 2015-04-17 01:25, Quentin Colombet wrote:
>> Hi Jonas,
>> 
>> Could you file a PR with your test case please?
>> 
>> Thanks,
>> -Quentin
>>> On Apr 16, 2015, at 3:50 PM, Andrew Trick <atrick at apple.com
<mailto:atrick at apple.com>> wrote:
>>> 
>>>> 
>>>> On Apr 16, 2015, at 6:58 AM, Jonas Paulsson <jonas.paulsson
at ericsson.com <mailto:jonas.paulsson at ericsson.com>> wrote:
>>>> 
>>>> Hi,
>>>> 
>>>> I have come across a csmith generated test case that made the
MachineVerifier spit out:
>>>> 
>>>> *** Bad machine code: Multiple connected components in live
interval ***
>>>> 
>>>> Having looked at what this might mean, it seems that
ConnectedVNInfoEqClasses::Classify() was called on the LI in question by the
verifier, and that it returned two equivalence classes, instead of just one,
which is demanded by the verifier. Does this mean that there should never be
>>>> any ValNos in a LiveInterval that are not connected? In other
words should such an LI never exist, but rather two different LIs?
>>> 
>>> That’s right. It looks like a copy was inserted,
>>> 
>>>> %vreg3<def> = COPY %vreg46
>>> 
>>> 
>>> breaking the live interval, and a new LI was not created. Maybe the
splitter did it? You would need to look at debug-only=regalloc.
>>> 
>>> Andy
>>> 
>>>> 
>>>> I have tried to run this on in-tree targets, but unfortunately
they did not reproduce the condition.
>>>> I will therefore try to explain:
>>>> 
>>>> The options to llc are -optimize-regalloc -O0. The function is
meaningless - with -O3 it just returns zero.
>>>> It contains two nested loops, with a call inside the inner
loop, which is a CFG-diamond.
>>>> 
>>>> The PHI-nodes look like this in the inner loop:
>>>> 
>>>> BB#5:  // Inner loop header
>>>>  Predecessors according to CFG: BB#1 BB#4
>>>>    vreg7<def> = PHI %vreg29, <BB#1>, %vreg4,
<BB#4>
>>>>    ...
>>>>  Successors according to CFG: BB#2 BB#6
>>>> 
>>>> BB#2:
>>>>  Predecessors according to CFG: BB#5
>>>>  ...
>>>>  Successors according to CFG: BB#3 BB#4
>>>> 
>>>> BB#3:
>>>>  Predecessors according to CFG: BB#2
>>>>    call()
>>>>     %vreg46<def> = COPY %return_reg
>>>>     %vreg3<def> = COPY %vreg46;
>>>>     use of %vreg 46
>>>> 
>>>>  Successors according to CFG: BB#4
>>>> 
>>>> BB#4:
>>>>  Predecessors according to CFG: BB#2 BB#3
>>>>    %vreg4<def> = PHI %vreg7, <BB#2>, %vreg3,
<BB#3>
>>>>  Successors according to CFG: BB#5
>>>> 
>>>> The observation I made here is that %vreg7 and %vreg4 are sort
of nested PHI nodes, while there are no other users of the registers than the
PHI nodes themselves. There is however a use of %vreg46, which later gets
coalesced with %vreg64, which will include as well the two PHI nodes.
>>>> 
>>>> This is the code with the two equivalence classes, when
verifier aborts:
>>>> 
>>>> 2272B   BB#1: derived from LLVM BB %bb3
>>>>           Predecessors according to CFG: BB#8
>>>> 2304B           %vreg64<def> = mov 0
>>>> 2448B           jmp <BB#5>
>>>>           Successors according to CFG: BB#5
>>>> 
>>>> 2592B   BB#3: derived from LLVM BB %bb6
>>>>           Predecessors according to CFG: BB#2
>>>> 2704B           callr <ga:@safe_div_func_uint64_t_u_u>
>>>> 2736B           %vreg64<def> = COPY %return_reg
>>>> 2768B           use of %vreg64
>>>> 2784B           use of %vreg64
>>>> 2816B           jmp <BB#4>
>>>>           Successors according to CFG: BB#4
>>>> 
>>>> *** Bad machine code: Multiple connected components in live
interval ***
>>>> - function:    func_61
>>>> - interval:    %vreg64 [2304r,2336r:0)[2736r,2784r:3) 0 at
2304r 1 at x 2 at x 3 at 2736r
>>>> 0: valnos 0
>>>> 1: valnos 1 2 3
>>>> LLVM ERROR: Found 1 machine code errors.
>>>> 
>>>> Two small live ranges of %vreg64 (originated from %vreg7 and
%vreg4), which look ok to me, but the verifier does not like it.
>>>> 
>>>> Can anyone give me any background or any hint on what might be
the problem here?
>>>> 
>>>> thanks,
>>>> 
>>>> Jonas Paulsson
>>>> 
>>>> 
>>>> _______________________________________________
>>>> LLVM Developers mailing list
>>>> LLVMdev at cs.uiuc.edu <mailto:LLVMdev at cs.uiuc.edu>   
http://llvm.cs.uiuc.edu <http://llvm.cs.uiuc.edu/>
>>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
<http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev>
>>> 
>>> 
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> LLVMdev at cs.uiuc.edu <mailto:LLVMdev at cs.uiuc.edu>       
http://llvm.cs.uiuc.edu <http://llvm.cs.uiuc.edu/>
>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
<http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev>
> 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150417/4d574e7b/attachment.html>

Jonas Paulsson

2015-Apr-20 11:03 UTC

head link

[LLVMdev] Multiple connected components in live interval

Hi Quentin,

After Simple Register Coalescing.

thanks,

Jonas

On 2015-04-17 18:52, Quentin Colombet wrote:> Hi Jonas,
>
> When is the MachineVerifier complaining?
> I mean after which pass?
>
> Thanks,
> -Quentin
>
>> On Apr 17, 2015, at 7:17 AM, Jonas Paulsson 
>> <jonas.paulsson at ericsson.com <mailto:jonas.paulsson at
ericsson.com>> wrote:
>>
>> Hi,
>>
>> thanks for answering, but the COPY is there already from after isel. 
>> It is a copy of a subreg, after a a call returning 64 bits.
>>
>>     call <ga:@safe_div_func_uint64_t_u_u>
>>         %vreg45<def> = COPY %r0
>>         %vreg46<def> = COPY %r1
>>         %vreg3<def> = COPY %vreg46
<<<<<<<<<<<<<<<<<<
>>         ST %vreg46, %vreg0
>>         ST %vreg46, %vreg1
>>         brr_uncond <BB#4>
>>
>> Does this ring any bell? Could there be any place that misses 
>> something about the resulting LiveInterval due to a phys reg copy?
>>
>> thanks
>>
>> /Jonas
>>
>> PS Quentin, as I said I could not reproduce this error on any in-tree 
>> target.
>
> Ah right.
>
>>
>>
>> On 2015-04-17 01:25, Quentin Colombet wrote:
>>> Hi Jonas,
>>>
>>> Could you file a PR with your test case please?
>>>
>>> Thanks,
>>> -Quentin
>>>> On Apr 16, 2015, at 3:50 PM, Andrew Trick <atrick at
apple.com
>>>> <mailto:atrick at apple.com>> wrote:
>>>>
>>>>>
>>>>> On Apr 16, 2015, at 6:58 AM, Jonas Paulsson 
>>>>> <jonas.paulsson at ericsson.com
<mailto:jonas.paulsson at ericsson.com>>
>>>>> wrote:
>>>>>
>>>>> Hi,
>>>>>
>>>>> I have come across a csmith generated test case that made
the
>>>>> MachineVerifier spit out:
>>>>>
>>>>> *** Bad machine code: Multiple connected components in live
>>>>> interval ***
>>>>>
>>>>> Having looked at what this might mean, it seems that 
>>>>> ConnectedVNInfoEqClasses::Classify() was called on the LI
in
>>>>> question by the verifier, and that it returned two
equivalence
>>>>> classes, instead of just one, which is demanded by the
verifier.
>>>>> Does this mean that there should never be
>>>>> any ValNos in a LiveInterval that are not connected? In
other
>>>>> words should such an LI never exist, but rather two
different LIs?
>>>>
>>>> That’s right. It looks like a copy was inserted,
>>>>
>>>>> %vreg3<def> = COPY %vreg46
>>>>
>>>>
>>>> breaking the live interval, and a new LI was not created. Maybe
the
>>>> splitter did it? You would need to look at debug-only=regalloc.
>>>>
>>>> Andy
>>>>
>>>>>
>>>>> I have tried to run this on in-tree targets, but
unfortunately
>>>>> they did not reproduce the condition.
>>>>> I will therefore try to explain:
>>>>>
>>>>> The options to llc are -optimize-regalloc -O0. The function
is
>>>>> meaningless - with -O3 it just returns zero.
>>>>> It contains two nested loops, with a call inside the inner
loop,
>>>>> which is a CFG-diamond.
>>>>>
>>>>> The PHI-nodes look like this in the inner loop:
>>>>>
>>>>> BB#5:  // Inner loop header
>>>>>  Predecessors according to CFG: BB#1 BB#4
>>>>>    vreg7<def> = PHI %vreg29, <BB#1>, %vreg4,
<BB#4>
>>>>>    ...
>>>>>  Successors according to CFG: BB#2 BB#6
>>>>>
>>>>> BB#2:
>>>>>  Predecessors according to CFG: BB#5
>>>>>  ...
>>>>>  Successors according to CFG: BB#3 BB#4
>>>>>
>>>>> BB#3:
>>>>>  Predecessors according to CFG: BB#2
>>>>>    call()
>>>>>     %vreg46<def> = COPY %return_reg
>>>>>     %vreg3<def> = COPY %vreg46;
>>>>>     use of %vreg 46
>>>>>
>>>>>  Successors according to CFG: BB#4
>>>>>
>>>>> BB#4:
>>>>>  Predecessors according to CFG: BB#2 BB#3
>>>>>    %vreg4<def> = PHI %vreg7, <BB#2>, %vreg3,
<BB#3>
>>>>>  Successors according to CFG: BB#5
>>>>>
>>>>> The observation I made here is that %vreg7 and %vreg4 are
sort of
>>>>> nested PHI nodes, while there are no other users of the
registers
>>>>> than the PHI nodes themselves. There is however a use of
%vreg46,
>>>>> which later gets coalesced with %vreg64, which will include
as
>>>>> well the two PHI nodes.
>>>>>
>>>>> This is the code with the two equivalence classes, when
verifier
>>>>> aborts:
>>>>>
>>>>> 2272B   BB#1: derived from LLVM BB %bb3
>>>>>           Predecessors according to CFG: BB#8
>>>>> 2304B           %vreg64<def> = mov 0
>>>>> 2448B           jmp <BB#5>
>>>>>           Successors according to CFG: BB#5
>>>>>
>>>>> 2592B   BB#3: derived from LLVM BB %bb6
>>>>>           Predecessors according to CFG: BB#2
>>>>> 2704B           callr
<ga:@safe_div_func_uint64_t_u_u>
>>>>> 2736B           %vreg64<def> = COPY %return_reg
>>>>> 2768B           use of %vreg64
>>>>> 2784B           use of %vreg64
>>>>> 2816B           jmp <BB#4>
>>>>>           Successors according to CFG: BB#4
>>>>>
>>>>> *** Bad machine code: Multiple connected components in live
>>>>> interval ***
>>>>> - function:    func_61
>>>>> - interval:    %vreg64 [2304r,2336r:0)[2736r,2784r:3) 0 at
2304r 1 at x
>>>>> 2 at x 3 at 2736r
>>>>> 0: valnos 0
>>>>> 1: valnos 1 2 3
>>>>> LLVM ERROR: Found 1 machine code errors.
>>>>>
>>>>> Two small live ranges of %vreg64 (originated from %vreg7
and
>>>>> %vreg4), which look ok to me, but the verifier does not
like it.
>>>>>
>>>>> Can anyone give me any background or any hint on what might
be the
>>>>> problem here?
>>>>>
>>>>> thanks,
>>>>>
>>>>> Jonas Paulsson
>>>>>
>>>>>
>>>>> _______________________________________________
>>>>> LLVM Developers mailing list
>>>>> LLVMdev at cs.uiuc.edu <mailto:LLVMdev at
cs.uiuc.edu>
>>>>> http://llvm.cs.uiuc.edu <http://llvm.cs.uiuc.edu/>
>>>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>>>
>>>>
>>>> _______________________________________________
>>>> LLVM Developers mailing list
>>>> LLVMdev at cs.uiuc.edu 
>>>> <mailto:LLVMdev at cs.uiuc.edu>http://llvm.cs.uiuc.edu 
>>>> <http://llvm.cs.uiuc.edu/>
>>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150420/2066721b/attachment.html>

Quentin Colombet

2015-Apr-20 17:18 UTC

head link

[LLVMdev] Multiple connected components in live interval

Hi Jonas,

> On Apr 20, 2015, at 4:03 AM, Jonas Paulsson <jonas.paulsson at
ericsson.com> wrote:
> 
> Hi Quentin,
> 
> After Simple Register Coalescing.
Is the code you have pasted with the PHIs feed to the register coalescer?
I am trying to understand the setting to help debugging the problem.
Also, what does -debug-only=regalloc tell you?

Thanks,
-Quentin
> 
> thanks,
> 
> Jonas
> 
> On 2015-04-17 18:52, Quentin Colombet wrote:
>> Hi Jonas,
>> 
>> When is the MachineVerifier complaining?
>> I mean after which pass?
>> 
>> Thanks,
>> -Quentin
>> 
>>> On Apr 17, 2015, at 7:17 AM, Jonas Paulsson <jonas.paulsson at
ericsson.com <mailto:jonas.paulsson at ericsson.com>> wrote:
>>> 
>>> Hi,
>>> 
>>> thanks for answering, but the COPY is there already from after
isel. It is a copy of a subreg, after a a call returning 64 bits.
>>> 
>>>         call <ga:@safe_div_func_uint64_t_u_u>
>>>         %vreg45<def> = COPY %r0
>>>         %vreg46<def> = COPY %r1
>>>         %vreg3<def> = COPY %vreg46         
<<<<<<<<<<<<<<<<<<
>>>         ST %vreg46, %vreg0
>>>         ST %vreg46, %vreg1
>>>         brr_uncond <BB#4>
>>> 
>>> Does this ring any bell? Could there be any place that misses
something about the resulting LiveInterval due to a phys reg copy?
>>> 
>>> thanks
>>> 
>>> /Jonas
>>> 
>>> PS Quentin, as I said I could not reproduce this error on any
in-tree target.
>> 
>> Ah right.
>> 
>>> 
>>> 
>>> On 2015-04-17 01:25, Quentin Colombet wrote:
>>>> Hi Jonas,
>>>> 
>>>> Could you file a PR with your test case please?
>>>> 
>>>> Thanks,
>>>> -Quentin
>>>>> On Apr 16, 2015, at 3:50 PM, Andrew Trick <atrick at
apple.com <mailto:atrick at apple.com>> wrote:
>>>>> 
>>>>>> 
>>>>>> On Apr 16, 2015, at 6:58 AM, Jonas Paulsson
<jonas.paulsson at ericsson.com <mailto:jonas.paulsson at
ericsson.com>> wrote:
>>>>>> 
>>>>>> Hi,
>>>>>> 
>>>>>> I have come across a csmith generated test case that
made the MachineVerifier spit out:
>>>>>> 
>>>>>> *** Bad machine code: Multiple connected components in
live interval ***
>>>>>> 
>>>>>> Having looked at what this might mean, it seems that
ConnectedVNInfoEqClasses::Classify() was called on the LI in question by the    
verifier, and that it returned two equivalence classes, instead of just one,
which is demanded by the verifier. Does this mean that there should never be
>>>>>> any ValNos in a LiveInterval that are not connected? In
other words should such an LI never exist, but rather two different LIs?
>>>>> 
>>>>> That’s right. It looks like a copy was inserted,
>>>>> 
>>>>>> %vreg3<def> = COPY %vreg46
>>>>> 
>>>>> 
>>>>> breaking the live interval, and a new LI was not created.
Maybe the splitter did it? You would need to look at debug-only=regalloc.
>>>>> 
>>>>> Andy
>>>>> 
>>>>>> 
>>>>>> I have tried to run this on in-tree targets, but
unfortunately they did not reproduce the condition.
>>>>>> I will therefore try to explain:
>>>>>> 
>>>>>> The options to llc are -optimize-regalloc -O0. The
function is meaningless - with -O3 it just returns zero.
>>>>>> It contains two nested loops, with a call inside the
inner loop, which is a CFG-diamond.
>>>>>> 
>>>>>> The PHI-nodes look like this in the inner loop:
>>>>>> 
>>>>>> BB#5:  // Inner loop header
>>>>>>  Predecessors according to CFG: BB#1 BB#4
>>>>>>    vreg7<def> = PHI %vreg29, <BB#1>,
%vreg4, <BB#4>
>>>>>>    ...
>>>>>>  Successors according to CFG: BB#2 BB#6
>>>>>> 
>>>>>> BB#2:
>>>>>>  Predecessors according to CFG: BB#5
>>>>>>  ...
>>>>>>  Successors according to CFG: BB#3 BB#4
>>>>>> 
>>>>>> BB#3:
>>>>>>  Predecessors according to CFG: BB#2
>>>>>>    call()
>>>>>>     %vreg46<def> = COPY %return_reg
>>>>>>     %vreg3<def> = COPY %vreg46;
>>>>>>     use of %vreg 46
>>>>>> 
>>>>>>  Successors according to CFG: BB#4
>>>>>> 
>>>>>> BB#4:
>>>>>>  Predecessors according to CFG: BB#2 BB#3
>>>>>>    %vreg4<def> = PHI %vreg7, <BB#2>,
%vreg3, <BB#3>
>>>>>>  Successors according to CFG: BB#5
>>>>>> 
>>>>>> The observation I made here is that %vreg7 and %vreg4
are sort of nested PHI nodes, while there are no other users of the registers
than the PHI nodes themselves. There is however a use of %vreg46, which later
gets coalesced with %vreg64, which will include as well the two PHI nodes.
>>>>>> 
>>>>>> This is the code with the two equivalence classes, when
verifier aborts:
>>>>>> 
>>>>>> 2272B   BB#1: derived from LLVM BB %bb3
>>>>>>           Predecessors according to CFG: BB#8
>>>>>> 2304B           %vreg64<def> = mov 0
>>>>>> 2448B           jmp <BB#5>
>>>>>>           Successors according to CFG: BB#5
>>>>>> 
>>>>>> 2592B   BB#3: derived from LLVM BB %bb6
>>>>>>           Predecessors according to CFG: BB#2
>>>>>> 2704B           callr
<ga:@safe_div_func_uint64_t_u_u>
>>>>>> 2736B           %vreg64<def> = COPY %return_reg
>>>>>> 2768B           use of %vreg64
>>>>>> 2784B           use of %vreg64
>>>>>> 2816B           jmp <BB#4>
>>>>>>           Successors according to CFG: BB#4
>>>>>> 
>>>>>> *** Bad machine code: Multiple connected components in
live interval ***
>>>>>> - function:    func_61
>>>>>> - interval:    %vreg64 [2304r,2336r:0)[2736r,2784r:3) 0
at 2304r 1 at x 2 at x 3 at 2736r
>>>>>> 0: valnos 0
>>>>>> 1: valnos 1 2 3
>>>>>> LLVM ERROR: Found 1 machine code errors.
>>>>>> 
>>>>>> Two small live ranges of %vreg64 (originated from
%vreg7 and %vreg4), which look ok to me, but the verifier does not like it.
>>>>>> 
>>>>>> Can anyone give me any background or any hint on what
might be the problem here?
>>>>>> 
>>>>>> thanks,
>>>>>> 
>>>>>> Jonas Paulsson
>>>>>> 
>>>>>> 
>>>>>> _______________________________________________
>>>>>> LLVM Developers mailing list
>>>>>> LLVMdev at cs.uiuc.edu <mailto:LLVMdev at
cs.uiuc.edu>         http://llvm.cs.uiuc.edu <http://llvm.cs.uiuc.edu/>
>>>>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
<http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev>
>>>>> 
>>>>> 
>>>>> _______________________________________________
>>>>> LLVM Developers mailing list
>>>>> LLVMdev at cs.uiuc.edu <mailto:LLVMdev at
cs.uiuc.edu>         http://llvm.cs.uiuc.edu <http://llvm.cs.uiuc.edu/>
>>>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
<http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev>
>>> 
>> 
> 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150420/b4d8c248/attachment.html>

Seemingly Similar Threads

Search for more maybe matching threads

llvm dev - Apr 2015 - [LLVMdev] Multiple connected components in live interval

[LLVMdev] Multiple connected components in live interval

[LLVMdev] Multiple connected components in live interval

[LLVMdev] Multiple connected components in live interval

Seemingly Similar Threads