Create a PHI value when merging with a known undef live-in

[kparzysz]

Summary

The following snippet illustrates the problem.

During register allocation, the value defined at 868 for vreg154:isub_hi (lane mask 0x0001) is extended to the use at 1564 via a single segment. That segment spans over the entry to BB#6, which is reachable from two places: the end of BB#5 (dominated by 868), and the end of BB#6. The value of vreg154:isub_hi is undefined when coming from the end of BB#6, which causes the verifier to complain.

To fix this, create a PHI when a defined value is merged with an undef value at the entry to a block. Currently, undef values are simply ignored when determining the need for PHIs, which leads to a problem when there is a unique defined value.

704B    BB#5: derived from LLVM BB %b17
            Predecessors according to CFG: BB#2 BB#4
868B            %vreg154<def> = COPY %vreg148; DoubleRegs:%vreg154,%vreg148
            Successors according to CFG: BB#6(?%)

1172B   BB#6: derived from LLVM BB %b30
            Predecessors according to CFG: BB#5 BB#6
1212B           %vreg66<def> = C2_cmpgt %vreg152, %vreg154:isub_lo; PredRegs:%vreg66 IntRegs:%vreg152 DoubleRegs:%vreg154
1564B           %vreg153<def> = COPY %vreg154; DoubleRegs:%vreg153,%vreg154
1572B           %vreg154<def> = COPY %vreg153; DoubleRegs:%vreg154,%vreg153
1856B           %vreg154:isub_lo<def,read-undef> = A2_addi %vreg154:isub_lo, 1; DoubleRegs:%vreg154
1984B           J2_jump <BB#6>, %PC<imp-def,dead>
            Successors according to CFG: BB#6(?%)

# End machine code for function fred.

*** Bad machine code: Register not marked live out of predecessor ***
- function:    fred
- basic block: BB#6 b30 (0x50bb8b8) [1172B;1992B)
- liverange:   [868r,1564r:1)[1572r,1572d:0)  0@1572r 1@868r
- v. register: %vreg154
- lanemask:    00000001
- ValNo:       1 (def 868r)
 live into BB#6@1172B, not live before 1992B
LLVM ERROR: Found 1 machine code errors.

[MatzeB]

From what I remember the notion of a nullptr in Map for a block we had already Seen was introduced with the changes supporting undefs when recalculating liveness. I assumed that had the same role as the special VNI you introduce here. Can you elaborate the difference (and/or eliminate the cases looking for nullptr)?

Could you create a .mir test that just does llc -run-pass=liveintervals?

lib/CodeGen/LiveRangeCalc.cpp

289 ↗

(On Diff #104009)

Doesn't the Map[&B].first == nullptr case only exist to deal with undefs? Does it still happen with your changes?

(If you still need it, at least refactor it so we only do 1 lookup in Map).

[kparzysz]

The case where a block is in Seen, but the value is null refers to the situation where the register is live-through this block, but at the moment we don't know what value it has. The "UndefVNI" case denotes a situation where we know that this block undefines the register.

lib/CodeGen/LiveRangeCalc.cpp

289 ↗

(On Diff #104009)

Yes, it still happens. Actually there are 3 testcases in test/CodeGen/Hexagon where this occurs with these changes.

[kparzysz]

Replaced the .ll testcase with a shorter .mir. Avoided two Map lookups when checking block live-out value.

[MatzeB]

Thanks, LGTM.

lib/CodeGen/LiveRangeCalc.cpp

500–501 ↗

(On Diff #104149)

This can be && instead of a nested if.

test/CodeGen/Hexagon/regalloc-liveout-undef.mir

3–6 ↗

(On Diff #104149)

Sounds like we need some AU.addUsedIfAvailable<>() calls in the getUsageInfo of the MachineVerifier. Doesn't need to be in this patch though.

[kparzysz]

lib/CodeGen/LiveRangeCalc.cpp

500–501 ↗

(On Diff #104149)

But then the condition wouldn't fit in a single line.

[MatzeB]

lib/CodeGen/LiveRangeCalc.cpp

500–501 ↗

(On Diff #104149)

But it's two lines either way, isn't it? Not that I care too deeply about it, but my motivation for a single if, is that when I see two ifs, I usually start looking for "else code" or "common code after the inner if" that aren't present here.

llvm/trunk/lib/CodeGen/LiveRangeCalc.cpp

 #include "llvm/ADT/SetVector.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "regalloc"
 
+// Reserve an address that indicates a value that is known to be "undef".
+static VNInfo UndefVNI(0xbad, SlotIndex());
+
 void LiveRangeCalc::resetLiveOutMap() {
   unsigned NumBlocks = MF->getNumBlockIDs();
   Seen.clear();
   Seen.resize(NumBlocks);
   EntryInfos.clear();
   Map.resize(NumBlocks);
 }
 
bool LiveRangeCalc::isDefOnEntry(LiveRange &LR, ArrayRef<SlotIndex> Undefs,
   // that are potentially defined-on-exit to the work list.
   for (MachineBasicBlock *P : MBB.predecessors())
     WorkList.insert(P->getNumber());
 
   for (unsigned i = 0; i != WorkList.size(); ++i) {
     // Determine if the exit from the block is reached by some def.
     unsigned N = WorkList[i];
     MachineBasicBlock &B = *MF->getBlockNumbered(N);
-    if (Seen[N] && Map[&B].first != nullptr)
+    if (Seen[N]) {
+      const LiveOutPair &LOB = Map[&B];
+      if (LOB.first != nullptr && LOB.first != &UndefVNI)
         return MarkDefined(B);
+    }
     SlotIndex Begin, End;
     std::tie(Begin, End) = Indexes->getMBBRange(&B);
     // Treat End as not belonging to B.
     // If LR has a segment S that starts at the next block, i.e. [End, ...),
     // std::upper_bound will return the segment following S. Instead,
     // S should be treated as the first segment that does not overlap B.
     LiveRange::iterator UB = std::upper_bound(LR.begin(), LR.end(),
                                               End.getPrevSlot());
for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
        SlotIndex Start, End;
        std::tie(Start, End) = Indexes->getMBBRange(Pred);
 
        // First time we see Pred.  Try to determine the live-out value, but set
        // it as null if Pred is live-through with an unknown value.
        auto EP = LR.extendInBlock(Undefs, Start, End);
        VNInfo *VNI = EP.first;
        FoundUndef |= EP.second;
-       setLiveOutValue(Pred, VNI);
+       setLiveOutValue(Pred, EP.second ? &UndefVNI : VNI);
        if (VNI) {
          if (TheVNI && TheVNI != VNI)
            UniqueVNI = false;
          TheVNI = VNI;
        }
        if (VNI || EP.second)
          continue;
 
#endif
 
   // Both updateSSA() and LiveRangeUpdater benefit from ordered blocks, but
   // neither require it. Skip the sorting overhead for small updates.
   if (WorkList.size() > 4)
     array_pod_sort(WorkList.begin(), WorkList.end());
 
   // If a unique reaching def was found, blit in the live ranges immediately.
   if (UniqueVNI) {
-    assert(TheVNI != nullptr);
+    assert(TheVNI != nullptr && TheVNI != &UndefVNI);
     LiveRangeUpdater Updater(&LR);
     for (unsigned BN : WorkList) {
       SlotIndex Start, End;
       std::tie(Start, End) = Indexes->getMBBRange(BN);
       // Trim the live range in UseMBB.
       if (BN == UseMBBNum && Use.isValid())
         End = Use;
       else
for (LiveInBlock &I : LiveIn) {
 
       // IDom dominates all of our predecessors, but it may not be their
       // immediate dominator. Check if any of them have live-out values that are
       // properly dominated by IDom. If so, we need a phi-def here.
       if (!needPHI) {
         IDomValue = Map[IDom->getBlock()];
 
         // Cache the DomTree node that defined the value.
-        if (IDomValue.first && !IDomValue.second)
+        if (IDomValue.first && IDomValue.first != &UndefVNI)
+          if (!IDomValue.second)
             Map[IDom->getBlock()].second = IDomValue.second =
               DomTree->getNode(Indexes->getMBBFromIndex(IDomValue.first->def));
 
         for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
                PE = MBB->pred_end(); PI != PE; ++PI) {
           LiveOutPair &Value = Map[*PI];
           if (!Value.first || Value.first == IDomValue.first)
             continue;
+          if (Value.first == &UndefVNI) {
+            needPHI = true;
+            break;
+          }
 
           // Cache the DomTree node that defined the value.
           if (!Value.second)
             Value.second =
               DomTree->getNode(Indexes->getMBBFromIndex(Value.first->def));
 
           // This predecessor is carrying something other than IDomValue.
           // It could be because IDomValue hasn't propagated yet, or it could be
for (LiveInBlock &I : LiveIn) {
         if (I.Kill.isValid()) {
           if (VNI)
             LR.addSegment(LiveInterval::Segment(Start, I.Kill, VNI));
         } else {
           if (VNI)
             LR.addSegment(LiveInterval::Segment(Start, End, VNI));
           LOP = LiveOutPair(VNI, Node);
         }
-      } else if (IDomValue.first) {
+      } else if (IDomValue.first && IDomValue.first != &UndefVNI) {
         // No phi-def here. Remember incoming value.
         I.Value = IDomValue.first;
 
         // If the IDomValue is killed in the block, don't propagate through.
         if (I.Kill.isValid())
           continue;
 
         // Propagate IDomValue if it isn't killed:

llvm/trunk/test/CodeGen/Hexagon/regalloc-liveout-undef.mir

+# RUN: llc -march=hexagon -run-pass liveintervals -run-pass machineverifier -run-pass simple-register-coalescing %s -o - | FileCheck %s
+#
+# If there is no consumer of the live intervals, the live intervals pass
+# will be freed immediately after it runs, before the verifier. Add a
+# user (register coalescer in this case), so that the verification will
+# cover live intervals as well.
+#
+# Make sure that this compiles successfully.
+# CHECK: undef %1.isub_lo = A2_addi %1.isub_lo, 1
+
+---
+name: fred
+tracksRegLiveness: true
+
+registers:
+  - { id: 0, class: intregs }
+  - { id: 1, class: doubleregs }
+  - { id: 2, class: predregs }
+  - { id: 3, class: doubleregs }
+body: |
+  bb.0:
+    liveins: %d0
+    successors: %bb.1
+        %0 = IMPLICIT_DEF
+        %1 = COPY %d0
+
+  bb.1:
+    successors: %bb.1
+        %2 = C2_cmpgt %0, %1.isub_lo
+        %3 = COPY %1
+        %1 = COPY %3
+        undef %1.isub_lo = A2_addi %1.isub_lo, 1
+        J2_jump %bb.1, implicit-def %pc
+...
+