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:

Jonas Paulsson

2015-Apr-16 13:58 UTC

[LLVMdev] Multiple connected components in live interval

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?

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

Andrew Trick

2015-Apr-16 22:50 UTC

head link

[LLVMdev] Multiple connected components in live interval

> On Apr 16, 2015, at 6:58 AM, Jonas Paulsson <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         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

Quentin Colombet

2015-Apr-16 23:25 UTC

head link

[LLVMdev] Multiple connected components in live interval

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>
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         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
<http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev>-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150416/6e506c0c/attachment.html>

Apparently Analagous Threads

Search for more possibly parallel 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

Apparently Analagous Threads