[llvm-dev] Problems with undef subranges in identity copies

[Matt Arsenault via llvm-dev]

Hi,

I'm stuck trying to fix a variety of problems that occur with undef
subregisters when the register coalescer eliminates identity
copies. The fundamental problem is complexity from the fact that undef
values are a special case since they don't have an associated
VNInfo/Segment unless the value is used across blocks.

For example, in this case, %0 has 2 subregisters sub0 and sub1:
  bb.0:
    undef %0.sub1:vreg_64 = COPY killed $vgpr0

  bb.1:
    %0:vreg_64 = COPY %0
    S_CBRANCH_EXECNZ %bb.1, implicit $exec

  bb.2:
    undef %0.sub1:vreg_64 = nofpexcept V_CEIL_F32_e32 killed %0.sub1, implicit $mode, implicit $exec
    S_BRANCH %bb.1

sub0 has no defined values anywhere in this function. The value only
exists due to this identity copy in %bb.1, which is removed.

When the copy is erased and the interval is updated
(https://github.com/llvm/llvm-project/blob/523cc097fdafa1bb60373dcc70df7dfd31551f56/llvm/lib/CodeGen/RegisterCoalescer.cpp#L1871),
the new live interval looks like this:

%0 [16r,32B:2)[32B,96r:0)[96r,128B:1)  0 at 32B-phi 1 at 96r 2 at 16r
  L0000000000000003 [32B,80B:0)  0 at 32B-phi // sub0

This remaining [32B,80B:0) across %bb.1 is a fake phi-only segment. If
I freshly recompute LiveIntervals, the subrange is empty as it should
be. The verifier doesn't care about this, however it does end up
confusing RenameIndependentSubregs. After RenameIndependentSubregs,
this becomes

%0 [24r,24d:0)[104r,104d:1) 0 at 24r 1 at 104r L0000000000000003
[24r,24d:1)[104r,104d:2) which fails the verifier with "Multiple
connected components in live interval".

I'm able to hack this segment out in simple situations when the
identity copy is removed, but so far have been unable to get it to
work correctly in more complex situtations where there are other valid
segments present. This requires a more complex analysis of the
incoming value than should really be necessary when eliminating a
trivial copy. In a similar situation where undef copies are
eliminated, an IMPLICIT_DEF is inserted in place to give a
corresponding instruction / value number for the cross-block undef
value. However in this situation, there's no specific subregister
index associated to define. It's an arbitrary set of lane masks, and
there's no way to go backwards from a set of lanemasks to a set of
subregister indexes to implicitly def.

I've also hit a second family of this same fundamental problem with a
slight variant of the testcase:

  bb.0:
    liveins: $vgpr0

    undef %0.sub1:vreg_64 = COPY killed $vgpr0

  bb.1:
    %1:vreg_64 = COPY killed %0
    %0:vreg_64 = COPY %1  // Indirect identity copy
    S_CBRANCH_EXECNZ %bb.1, implicit $exec

  bb.2:
    undef %2.sub1:vreg_64 = COPY %0.sub1
    %0:vreg_64 = COPY killed %2
    S_BRANCH %bb.1

...

Here, pruneSubRegValues  (https://github.com/llvm/llvm-project/blob/3ded927cf80ac519f9f9c4664fef08787f7c537d/llvm/lib/CodeGen/RegisterCoalescer.cpp#L3114) ends up leaving behind a similarly dead segment.

1. Is omitting undef lanes from the live segments a good idea in the
first place? This isn't the first time this special case has been an
issue.

2. Should effectively empty segments be a verifier error? I'm not sure
what the exact rule would be.

3. Should RenameIndependentSubregs tolerate these weird segments
instead?

4. Do we need some way to represent an arbitrary lanemask def to have
something to insert in place of the copy?

-Matt