LIS: fix handleMove to properly extend main range

[rampitec]

Summary

handleMoveDown or handleMoveUp cannot properly repair a main
range of a LiveInterval since they only get LiveRange. There
is a problem if certain use has moved few segments away and
there is a hole in the main range in between of these two
locations. We may get a SubRange with a very extended Segment
spanning several Segments of the main range and also spanning
that hole. If that happens then we end up with the main range
not covering its SubRange which is an error.

It might be possible to attempt fixing the main range in place
just between of the old and new index by extending all of its
Segments in between, but it is unclear this logic will be
faster than just straight constructMainRangeFromSubranges,
which itself is pretty cheap since it only contains interval
logic. That will also require shrinkToUses() call after which
is probably even more expensive.

In the test second move is from 64B to 92B for the sub1.
Subrange is correctly fixed:

L000000000000000C [16r,32B:0)[32B,92r:1) 0@16r 1@32B-phi

But the main range has a hole in between 80d and 88r after
updateRange():

%1 [16r,32B:0)[32B,80r:4)[80r,80d:3)[88r,96r:1)[96r,160B:2)

Since source position is 64B this segment is not even considered
by the updateRange().

[rampitec]

If there are better ideas I would be happy to hear!

[rampitec]

I also believe that will happen extremely rare, otherwise we would have already hit this problem. So the main overhead is really covers() checks.

[arsenm]

llvm/lib/CodeGen/LiveIntervals.cpp

1014

Needs a comment explaining this

[rampitec]

Added comment.

[vpykhtin]

Can you please add a LiveInterval dump (possibly truncated) for the test before and after each move to this review? It's a bit hard to follow what happens there.

[rampitec]

In D82916#2135752, @vpykhtin wrote:

Can you please add a LiveInterval dump (possibly truncated) for the test before and after each move to this review? It's a bit hard to follow what happens there.

Sure! This is the LIS at each step w/o this patch:

Before 1st move:

%1 [16r,32B:0)[32B,80r:4)[80r,80d:3)[96r,112r:1)[112r,160B:2)  0@16r 1@96r 2@112r 3@80r 4@32B-phi
L000000000000000C [16r,32B:0)[32B,64r:1)  0@16r 1@32B-phi
L00000000000000C0 [16r,16d:0)  0@16r
L0000000000000003 [16r,16d:1)[96r,96d:0)  0@96r 1@16r
L0000000000000030 [16r,32B:2)[32B,48r:3)[80r,80d:1)[112r,160B:0)  0@112r 1@80r 2@16r 3@32B-phi
weight:0.000000e+00
%2 [48r,80r:0)  0@48r weight:0.000000e+00
%3 [64r,64d:0)  0@64r weight:0.000000e+00
RegMasks:
********** MACHINEINSTRS **********
# Machine code for function func: NoPHIs

0B      bb.0:
          successors: %bb.1(0x80000000); %bb.1(100.00%)

16B       %1:sgpr_128 = IMPLICIT_DEF

32B     bb.1:
        ; predecessors: %bb.0, %bb.1
          successors: %bb.1(0x40000000), %bb.2(0x40000000); %bb.1(50.00%), %bb.2(50.00%)

48B       %2:sgpr_32 = COPY %1.sub2:sgpr_128
64B       dead %3:sgpr_32 = COPY %1.sub1:sgpr_128
80B       dead %1.sub2:sgpr_128 = COPY %2:sgpr_32
96B       %1.sub0:sgpr_128 = IMPLICIT_DEF
112B      %1.sub2:sgpr_128 = IMPLICIT_DEF
128B      S_CBRANCH_SCC1 %bb.1, implicit undef $scc
144B      S_BRANCH %bb.2

160B    bb.2:
        ; predecessors: %bb.1

Before 2nd move (still correct):

%1 [16r,32B:0)[32B,80r:4)[80r,80d:3)[88r,96r:1)[96r,160B:2)  0@16r 1@88r 2@96r 3@80r 4@32B-phi
L000000000000000C [16r,32B:0)[32B,64r:1)  0@16r 1@32B-phi
L00000000000000C0 [16r,16d:0)  0@16r
L0000000000000003 [16r,16d:1)[96r,96d:0)  0@96r 1@16r
L0000000000000030 [16r,32B:2)[32B,48r:3)[80r,80d:1)[88r,160B:0)  0@88r 1@80r 2@16r 3@32B-phi
weight:0.000000e+00
%2 [48r,80r:0)  0@48r weight:0.000000e+00
%3 [64r,64d:0)  0@64r weight:0.000000e+00
RegMasks:
********** MACHINEINSTRS **********
# Machine code for function func: NoPHIs

0B      bb.0:
          successors: %bb.1(0x80000000); %bb.1(100.00%)

16B       %1:sgpr_128 = IMPLICIT_DEF

32B     bb.1:
        ; predecessors: %bb.0, %bb.1
          successors: %bb.1(0x40000000), %bb.2(0x40000000); %bb.1(50.00%), %bb.2(50.00%)

48B       %2:sgpr_32 = COPY %1.sub2:sgpr_128
64B       dead %3:sgpr_32 = COPY %1.sub1:sgpr_128
80B       dead %1.sub2:sgpr_128 = COPY %2:sgpr_32
88B       %1.sub2:sgpr_128 = IMPLICIT_DEF
96B       %1.sub0:sgpr_128 = IMPLICIT_DEF
128B      S_CBRANCH_SCC1 %bb.1, implicit undef $scc
144B      S_BRANCH %bb.2

160B    bb.2:
        ; predecessors: %bb.1

After 2nd move from 64B to 92B, LIS is broken:

%1 [16r,32B:0)[32B,80r:4)[80r,80d:3)[88r,96r:1)[96r,160B:2)  0@16r 1@88r 2@96r 3@80r 4@32B-phi
L000000000000000C [16r,32B:0)[32B,92r:1)  0@16r 1@32B-phi
L00000000000000C0 [16r,16d:0)  0@16r
L0000000000000003 [16r,16d:1)[96r,96d:0)  0@96r 1@16r
L0000000000000030 [16r,32B:2)[32B,48r:3)[80r,80d:1)[88r,160B:0)  0@88r 1@80r 2@16r 3@32B-phi
weight:0.000000e+00
%2 [48r,80r:0)  0@48r weight:0.000000e+00
%3 [92r,92d:0)  0@92r weight:0.000000e+00
RegMasks:
********** MACHINEINSTRS **********
# Machine code for function func: NoPHIs

0B      bb.0:
          successors: %bb.1(0x80000000); %bb.1(100.00%)

16B       %1:sgpr_128 = IMPLICIT_DEF

32B     bb.1:
        ; predecessors: %bb.0, %bb.1
          successors: %bb.1(0x40000000), %bb.2(0x40000000); %bb.1(50.00%), %bb.2(50.00%)

48B       %2:sgpr_32 = COPY %1.sub2:sgpr_128
80B       dead %1.sub2:sgpr_128 = COPY %2:sgpr_32
88B       %1.sub2:sgpr_128 = IMPLICIT_DEF
92B       dead %3:sgpr_32 = COPY %1.sub1:sgpr_128
96B       %1.sub0:sgpr_128 = IMPLICIT_DEF
128B      S_CBRANCH_SCC1 %bb.1, implicit undef $scc
144B      S_BRANCH %bb.2

160B    bb.2:
        ; predecessors: %bb.1

*** Bad machine code: A Subrange is not covered by the main range ***
- function:    func
- interval:    %1 [16r,32B:0)[32B,80r:4)[80r,80d:3)[88r,96r:1)[96r,160B:2)  0@16r 1@88r 2@96r 3@80r 4@32B-phi L000000000000000C [16r,32B:0)[32B,92r:1)  0@16r 1@32B-phi L00000000000000C0 [16r,16d:0)  0@16r L0000000000000003 [16r,16d:1)[96r,96d:0)  0@96r 1@16r L0000000000000030 [16r,32B:2)[32B,48r:3)[80r,80d:1)[88r,160B:0)  0@88r 1@80r 2@16r 3@32B-phi weight:0.000000e+00
LLVM ERROR: Found 1 machine code errors.

The difference after the patch which occurs after the 2nd move:

%1 [16r,32B:0)[32B,80r:4)[80r,88r:3)[88r,96r:2)[96r,160B:1)  0@16r 1@96r 2@88r 3@80r 4@32B-phi

[vpykhtin]

I understood your patch. Generally I think patching LIS with cleared undef flags ins't right at first place because the semantic of register lifetime is ruined. After the first move there should be an undef flag set at the %1.sub2 = IMPLICIT_DEF instruction which would break lives of all subregs live at this point. Can we drop updating LIS during scheduling and recreate it from scratch? Or may be fully recreate only the intervals for the registers involved in moves when the undef flag is patched after scheduling?

[vpykhtin]

Given than the condition here is rare, I'm ok with the patch, reworking undef handling in scheduler is a massive work.

[rampitec]

In D82916#2136518, @vpykhtin wrote:

Given than the condition here is rare, I'm ok with the patch, reworking undef handling in scheduler is a massive work.

Right. Scheduler deliberately drops undef flags before the scheduling. To recreate them in the middle of the scheduling would be against the concept. I assume there is nothing after the scheduler which needs them. Moreover it looks like complete recompute of an LI in the middle of the scheduling is expensive and recompute of just some will simply result in an incosistent LIS.

llvm/lib/CodeGen/LiveIntervals.cpp

for (MachineOperand &MO : MI->operands()) {
                                         : MRI.getMaxLaneMaskForVReg(Reg);
           for (LiveInterval::SubRange &S : LI.subranges()) {
             if ((S.LaneMask & LaneMask).none())
               continue;
             updateRange(S, Reg, S.LaneMask);
           }
         }
         updateRange(LI, Reg, LaneBitmask::getNone());
+        // If main range has a hole and we are moving a subrange use across
+        // the hole updateRange() cannot properly handle it since it only
+        // gets the LiveRange and not the whole LiveInterval. As a result
+        // we may end up with a main range not covering all subranges.
+        // This is extremely rare case, so let's check and reconstruct the
+        // main range.
+        for (LiveInterval::SubRange &S : LI.subranges()) {
+          if (LI.covers(S))
+            continue;
+          LI.clear();
+          LIS.constructMainRangeFromSubranges(LI);
+          break;
+        }
+
         continue;
       }
 
       // For physregs, only update the regunits that actually have a
       // precomputed live range.
       for (MCRegUnitIterator Units(Reg, &TRI); Units.isValid(); ++Units)
         if (LiveRange *LR = getRegUnitLI(*Units))
           updateRange(*LR, *Units, LaneBitmask::getNone());

llvm/unittests/MI/LiveIntervalTest.cpp

 )MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
      MachineInstr &UndefSubregDef = getMI(MF, 2, 1);
      // The scheduler clears undef from subregister defs before moving
      UndefSubregDef.getOperand(0).setIsUndef(false);
      testHandleMove(MF, LIS, 4, 1, 1);
   });
 }
 
+TEST(LiveIntervalTest, TestMoveSubRegUseAcrossMainRangeHole) {
+  liveIntervalTest(R"MIR(
+    %1:sgpr_128 = IMPLICIT_DEF
+  bb.1:
+    %2:sgpr_32 = COPY %1.sub2
+    %3:sgpr_32 = COPY %1.sub1
+    %1.sub2 = COPY %2
+    undef %1.sub0 = IMPLICIT_DEF
+    %1.sub2 = IMPLICIT_DEF
+    S_CBRANCH_SCC1 %bb.1, implicit undef $scc
+    S_BRANCH %bb.2
+  bb.2:
+)MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
+    MachineInstr &MI = getMI(MF, 3, /*BlockNum=*/1);
+    MI.getOperand(0).setIsUndef(false);
+    testHandleMove(MF, LIS, 4, 3, 1);
+    testHandleMove(MF, LIS, 1, 4, 1);
+  });
+}
+
 TEST(LiveIntervalTest, BundleUse) {
   liveIntervalTest(R"MIR(
     %0 = IMPLICIT_DEF
     S_NOP 0
     S_NOP 0, implicit %0
     S_NOP 0
 )MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
     testHandleMoveIntoNewBundle(MF, LIS, 1, 2);