Matt Arsenault via llvm-dev
2020-Nov-19 23:32 UTC
[llvm-dev] Problems with undef subranges in identity copies
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
Jay Foad via llvm-dev
2020-Nov-20 09:19 UTC
[llvm-dev] Problems with undef subranges in identity copies
> 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.There is a precedent for trying to solve that problem: it's what SplitEditor::buildCopy does. Perhaps that logic could be factored out and reused. Jay. On Thu, 19 Nov 2020 at 23:32, Matt Arsenault via llvm-dev < llvm-dev at lists.llvm.org> wrote:> 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 > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20201120/18f606c8/attachment.html>