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@2304r 1@x 2@x 3@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

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

Hi Jonas,

Could you file a PR with your test case please?

Thanks,
-Quentin

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.

Hi Jonas,

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

Thanks,
-Quentin

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.

Hi Quentin,

After Simple Register Coalescing.

thanks,

Jonas

Hi Jonas,

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

Hi,

looking closesly at what the coalescer was doing, I found that:

  1. It merges several smaller intervals into %vreg64. That LI then looks okay, it is live in the pre-header block and throughout all blocks in the loop, so it has just one connected component.
  2. A user of %vreg64 is rematted, and as a result %vreg64 is shrunk. Two dead phi intervals are reported in debug output. As a result here, it is clear that the live ranges are shrunk around the uses, and there are just two small ranges left. They do not reach the block limits. One is in the pre-header block, and one is in a block inside the loop. This seems to be wrong according to the way the verifier complained, i.e. two connected components. It is also clear that there is no dependence between the two ranges – they could have been two live intervals instead, since both ranges are defined and used locally. The computeDeadValues() and shrinkToUses() return true (due to the dead phis), meaning the LI can be separated, but the coalescer does not even check the return value…?

Could it then be that the RegisterCoalescer should split live ranges when LIS->shrinkToUses() return true? Why does it not do that, when the verifier demands this?

thanks,

Jonas

PS The code with PHIs is just prior to de-SSA, to help you to get a view of the loop and the connected PHI nodes.

I think it should. That's an oversight.

Yep, this is likely the problem.

Jonas, do you think you can investigate a fix, or do you want me to look at it?

Cheers,
-Quentin

I looked at SplitKit, but I am not sure how to best do it, so it would be great if you could take a look.

/Jonas

I looked at SplitKit, but I am not sure how to best do it, so it would be great if you could take a look.

Sure.
I will try to do that by the end of the week.

Cheers,
Q.

Hi Jonas,

I won’t have time to look at it this week after all.
I’ll try to do that next week.
If you do not hear back from me by end of next, do not hesitate to ping me!

Cheers,
-Quentin

Hi Jonas,

Could you check if the attached patch fix your problem?

Thanks,
-Quentin

multiple_components.patch (2.69 KB)

Jonas checked that this patch fixes his issue.

Committed revision 236658.

Q.