[RegAllocGreedy] avoid using physreg candidates that cannot be correctly spilled

[dfukalov]

Summary

For the AMDGPU target if a MBB contains exec mask restore preamble, SplitEditor may get state when it cannot insert a spill instruction.

E.g. for a MIR

bb.100:
    %1 = S_OR_SAVEEXEC_B64 %2, implicit-def $exec, implicit-def $scc, implicit $exec

and if the regalloc will try to allocate a virtreg to the physreg already assigned to virtreg %1, it should insert spill instruction before the S_OR_SAVEEXEC_B64 instruction.
But it is not possible since can generate incorrect code in terms of exec mask.

The change makes regalloc to ignore such physreg candidates.

[rampitec]

test/CodeGen/AMDGPU/spill-before-exec.mir

7

This test will not work in a non-debug build. It needs at least

; REQUIRES: asserts

[qcolombet]

Hi,

Could you elaborate on that part?

But it is not possible since can generate incorrect code in terms of exec mask.

I don't understand the constraints and thus what you are trying to achieve.

Cheers,
-Quentin

[rampitec]

Thanks! Looks good, but please wait for others to review.

[dfukalov]

In D52052#1235054, @qcolombet wrote:

Hi,

Could you elaborate on that part?

But it is not possible since can generate incorrect code in terms of exec mask.

I don't understand the constraints and thus what you are trying to achieve.

Cheers,
-Quentin

SplitEditor during splitting region can try to insert COPY spill instruction before S_OR_SAVEEXEC_B64 since it interferes with physreg candidate that is already assigned to destination of this exec mask restoration instruction. Unfortunately, such a COPY operation may be lowered to a memory operation that will not be correct because exec mask is not restored before the preamble.

There was related fix https://reviews.llvm.org/D27997 for MachineBasicBlock::SkipPHIsLabelsAndDebug to skip exec masks restore preamble.

test/CodeGen/AMDGPU/spill-before-exec.mir

7

thanks!

[qcolombet]

Hi,

Could you elaborate on the exact constraints?

My understanding is that you don't want split code to occur right before this instruction, but I would like to understand exactly what it is not allowed.

Indeed, it would be easy to trick your fix by building an artificial basic block just before that instruction, so it would be good to go back to the constraints and see how we can properly encode them.

Cheers,
-Quentin

[dfukalov]

In D52052#1236976, @qcolombet wrote:

My understanding is that you don't want split code to occur right before this instruction, but I would like to understand exactly what it is not allowed.

The amdgpu target has special exec mask register that specifies what lanes should execute current vector instruction. So a basic block created from "if/else" construction with vector condition may contain this exec mask register restore code in preamble.
E.g. instruction S_OR_SAVEEXEC_B64 at the start of a BB set (restores) exec mask register value to correctly execute "else" block. So a spilling code SplitKit tries to insert before such an instruction may be transformed into memory operation. And it can be incorrectly executed with a wrong exec mask.

Indeed, it would be easy to trick your fix by building an artificial basic block just before that instruction, so it would be good to go back to the constraints and see how we can properly encode them.

Such new BB should take into account that "effective CFG" of vector operations depends on exec mask register value.

[rampitec]

LGTM

lib/CodeGen/RegAllocGreedy.cpp

private:
   bool LRE_CanEraseVirtReg(unsigned) override;
   void LRE_WillShrinkVirtReg(unsigned) override;
   void LRE_DidCloneVirtReg(unsigned, unsigned) override;
   void enqueue(PQueue &CurQueue, LiveInterval *LI);
   LiveInterval *dequeue(PQueue &CurQueue);
 
   BlockFrequency calcSpillCost();
   bool addSplitConstraints(InterferenceCache::Cursor, BlockFrequency&);
-  void addThroughConstraints(InterferenceCache::Cursor, ArrayRef<unsigned>);
-  void growRegion(GlobalSplitCandidate &Cand);
+  bool addThroughConstraints(InterferenceCache::Cursor, ArrayRef<unsigned>);
+  bool growRegion(GlobalSplitCandidate &Cand);
   bool splitCanCauseEvictionChain(unsigned Evictee, GlobalSplitCandidate &Cand,
                                   unsigned BBNumber,
                                   const AllocationOrder &Order);
   bool splitCanCauseLocalSpill(unsigned VirtRegToSplit,
                                GlobalSplitCandidate &Cand, unsigned BBNumber,
                                const AllocationOrder &Order);
   BlockFrequency calcGlobalSplitCost(GlobalSplitCandidate &,
                                      const AllocationOrder &Order,
if (BI.LiveIn) {
         BC.Entry = SpillPlacement::MustSpill;
         ++Ins;
       } else if (Intf.first() < BI.FirstInstr) {
         BC.Entry = SpillPlacement::PrefSpill;
         ++Ins;
       } else if (Intf.first() < BI.LastInstr) {
         ++Ins;
       }
+
+      // Abort if the spill cannot be inserted at the MBB' start
+      if (((BC.Entry == SpillPlacement::MustSpill) ||
+           (BC.Entry == SpillPlacement::PrefSpill)) &&
+          SlotIndex::isEarlierInstr(BI.FirstInstr,
+                                    SA->getFirstSplitPoint(BC.Number)))
+        return false;
     }
 
     // Interference for the live-out value.
     if (BI.LiveOut) {
       if (Intf.last() >= SA->getLastSplitPoint(BC.Number)) {
         BC.Exit = SpillPlacement::MustSpill;
         ++Ins;
       } else if (Intf.last() > BI.LastInstr) {
bool RAGreedy::addSplitConstraints(InterferenceCache::Cursor Intf,
   // Add constraints for use-blocks. Note that these are the only constraints
   // that may add a positive bias, it is downhill from here.
   SpillPlacer->addConstraints(SplitConstraints);
   return SpillPlacer->scanActiveBundles();
 }
 
 /// addThroughConstraints - Add constraints and links to SpillPlacer from the
 /// live-through blocks in Blocks.
-void RAGreedy::addThroughConstraints(InterferenceCache::Cursor Intf,
+bool RAGreedy::addThroughConstraints(InterferenceCache::Cursor Intf,
                                      ArrayRef<unsigned> Blocks) {
   const unsigned GroupSize = 8;
   SpillPlacement::BlockConstraint BCS[GroupSize];
   unsigned TBS[GroupSize];
   unsigned B = 0, T = 0;
 
   for (unsigned i = 0; i != Blocks.size(); ++i) {
     unsigned Number = Blocks[i];
     Intf.moveToBlock(Number);
 
     if (!Intf.hasInterference()) {
       assert(T < GroupSize && "Array overflow");
       TBS[T] = Number;
       if (++T == GroupSize) {
         SpillPlacer->addLinks(makeArrayRef(TBS, T));
         T = 0;
       }
       continue;
     }
 
     assert(B < GroupSize && "Array overflow");
     BCS[B].Number = Number;
 
+    // Abort if the spill cannot be inserted at the MBB' start
+    MachineBasicBlock *MBB = MF->getBlockNumbered(Number);
+    if (!MBB->empty() &&
+        SlotIndex::isEarlierInstr(LIS->getInstructionIndex(MBB->instr_front()),
+                                  SA->getFirstSplitPoint(Number)))
+      return false;
     // Interference for the live-in value.
     if (Intf.first() <= Indexes->getMBBStartIdx(Number))
       BCS[B].Entry = SpillPlacement::MustSpill;
     else
       BCS[B].Entry = SpillPlacement::PrefSpill;
 
     // Interference for the live-out value.
     if (Intf.last() >= SA->getLastSplitPoint(Number))
       BCS[B].Exit = SpillPlacement::MustSpill;
     else
       BCS[B].Exit = SpillPlacement::PrefSpill;
 
     if (++B == GroupSize) {
       SpillPlacer->addConstraints(makeArrayRef(BCS, B));
       B = 0;
     }
   }
 
   SpillPlacer->addConstraints(makeArrayRef(BCS, B));
   SpillPlacer->addLinks(makeArrayRef(TBS, T));
+  return true;
 }
 
-void RAGreedy::growRegion(GlobalSplitCandidate &Cand) {
+bool RAGreedy::growRegion(GlobalSplitCandidate &Cand) {
   // Keep track of through blocks that have not been added to SpillPlacer.
   BitVector Todo = SA->getThroughBlocks();
   SmallVectorImpl<unsigned> &ActiveBlocks = Cand.ActiveBlocks;
   unsigned AddedTo = 0;
 #ifndef NDEBUG
   unsigned Visited = 0;
 #endif
 
#endif
     }
     // Any new blocks to add?
     if (ActiveBlocks.size() == AddedTo)
       break;
 
     // Compute through constraints from the interference, or assume that all
     // through blocks prefer spilling when forming compact regions.
     auto NewBlocks = makeArrayRef(ActiveBlocks).slice(AddedTo);
-    if (Cand.PhysReg)
-      addThroughConstraints(Cand.Intf, NewBlocks);
-    else
+    if (Cand.PhysReg) {
+      if (!addThroughConstraints(Cand.Intf, NewBlocks))
+        return false;
+    } else
       // Provide a strong negative bias on through blocks to prevent unwanted
       // liveness on loop backedges.
       SpillPlacer->addPrefSpill(NewBlocks, /* Strong= */ true);
     AddedTo = ActiveBlocks.size();
 
     // Perhaps iterating can enable more bundles?
     SpillPlacer->iterate();
   }
   LLVM_DEBUG(dbgs() << ", v=" << Visited);
+  return true;
 }
 
 /// calcCompactRegion - Compute the set of edge bundles that should be live
 /// when splitting the current live range into compact regions.  Compact
 /// regions can be computed without looking at interference.  They are the
 /// regions formed by removing all the live-through blocks from the live range.
 ///
 /// Returns false if the current live range is already compact, or if the
bool RAGreedy::calcCompactRegion(GlobalSplitCandidate &Cand) {
 
   // The static split cost will be zero since Cand.Intf reports no interference.
   BlockFrequency Cost;
   if (!addSplitConstraints(Cand.Intf, Cost)) {
     LLVM_DEBUG(dbgs() << ", none.\n");
     return false;
   }
 
-  growRegion(Cand);
+  if (!growRegion(Cand)) {
+    LLVM_DEBUG(dbgs() << ", cannot spill all interferences.\n");
+    return false;
+  }
+
   SpillPlacer->finish();
 
   if (!Cand.LiveBundles.any()) {
     LLVM_DEBUG(dbgs() << ", none.\n");
     return false;
   }
 
   LLVM_DEBUG({
if (Cost >= BestCost) {
         if (BestCand == NoCand)
           dbgs() << " worse than no bundles\n";
         else
           dbgs() << " worse than "
                  << printReg(GlobalCand[BestCand].PhysReg, TRI) << '\n';
       });
       continue;
     }
-    growRegion(Cand);
+    if (!growRegion(Cand)) {
+      LLVM_DEBUG(dbgs() << ", cannot spill all interferences.\n");
+      continue;
+    }
 
     SpillPlacer->finish();
 
     // No live bundles, defer to splitSingleBlocks().
     if (!Cand.LiveBundles.any()) {
       LLVM_DEBUG(dbgs() << " no bundles.\n");
       continue;
     }

lib/CodeGen/SplitKit.h

 #include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/IntervalMap.h"
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/CodeGen/LiveInterval.h"
+#include "llvm/CodeGen/LiveIntervals.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/SlotIndexes.h"
 #include "llvm/MC/LaneBitmask.h"
 #include "llvm/Support/Compiler.h"
 #include <utility>
 
 namespace llvm {
if (LastInsertPoint[Num].first.isValid() &&
         !LastInsertPoint[Num].second.isValid())
       return LastInsertPoint[Num].first;
     return computeLastInsertPoint(CurLI, MBB);
   }
 
   /// Returns the last insert point as an iterator for \pCurLI in \pMBB.
   MachineBasicBlock::iterator getLastInsertPointIter(const LiveInterval &CurLI,
                                                      MachineBasicBlock &MBB);
+
+  /// Return the base index of the first insert point in \pMBB.
+  SlotIndex getFirstInsertPoint(MachineBasicBlock &MBB) {
+    SlotIndex Res = LIS.getMBBStartIdx(&MBB);
+    if (!MBB.empty()) {
+      MachineBasicBlock::iterator MII = MBB.SkipPHIsLabelsAndDebug(MBB.begin());
+      if (MII != MBB.end())
+        Res = LIS.getInstructionIndex(*MII);
+    }
+    return Res;
+  }
+
 };
 
 /// SplitAnalysis - Analyze a LiveInterval, looking for live range splitting
 /// opportunities.
 class LLVM_LIBRARY_VISIBILITY SplitAnalysis {
 public:
   const MachineFunction &MF;
   const VirtRegMap &VRM;
public:
 
   SlotIndex getLastSplitPoint(unsigned Num) {
     return IPA.getLastInsertPoint(*CurLI, *MF.getBlockNumbered(Num));
   }
 
   MachineBasicBlock::iterator getLastSplitPointIter(MachineBasicBlock *BB) {
     return IPA.getLastInsertPointIter(*CurLI, *BB);
   }
+
+  SlotIndex getFirstSplitPoint(unsigned Num) {
+    return IPA.getFirstInsertPoint(*MF.getBlockNumbered(Num));
+  }
 };
 
 /// SplitEditor - Edit machine code and LiveIntervals for live range
 /// splitting.
 ///
 /// - Create a SplitEditor from a SplitAnalysis.
 /// - Start a new live interval with openIntv.
 /// - Mark the places where the new interval is entered using enterIntv*

test/CodeGen/AMDGPU/spill-before-exec.mir

+# REQUIRES: asserts
+# RUN: llc -mtriple=amdgcn--- -verify-machineinstrs -debug-only=regalloc -run-pass=greedy -o /dev/null %s 2>&1 | FileCheck %s
+
+---
+# Check that physreg candidate is not used since cannot be spilled in a block,
+# e.g. before exec mask preamble
+# CHECK: , cannot spill all interferences.
+
+name:            foo
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: sreg_64 }
+  - { id: 1100, class: sreg_128 }
+  - { id: 1101, class: sreg_128 }
+  - { id: 1102, class: sreg_128 }
+  - { id: 1103, class: sreg_128 }
+  - { id: 1104, class: sreg_128 }
+  - { id: 1105, class: sreg_128 }
+  - { id: 1106, class: sreg_128 }
+  - { id: 1107, class: sreg_128 }
+  - { id: 1108, class: sreg_128 }
+  - { id: 1109, class: sreg_128 }
+  - { id: 1110, class: sreg_128 }
+  - { id: 1111, class: sreg_128 }
+  - { id: 1112, class: sreg_128 }
+  - { id: 1113, class: sreg_128 }
+  - { id: 1114, class: sreg_128 }
+  - { id: 1115, class: sreg_128 }
+  - { id: 1116, class: sreg_128 }
+  - { id: 1117, class: sreg_128 }
+  - { id: 1118, class: sreg_128 }
+  - { id: 1119, class: sreg_128 }
+  - { id: 1120, class: sreg_128 }
+  - { id: 1121, class: sreg_128 }
+body:             |
+  bb.0:
+    successors: %bb.1
+    liveins: $sgpr96_sgpr97, $sgpr98_sgpr99, $sgpr100_sgpr101, $sgpr102_sgpr103
+    %0:sreg_64 = COPY $sgpr102_sgpr103
+    %1100 = COPY $sgpr100_sgpr101_sgpr102_sgpr103
+    %1101 = COPY %1100
+    %1102 = COPY %1100
+    %1103 = COPY %1100
+    %1104 = COPY %1100
+    %1105 = COPY %1100
+    %1106 = COPY %1100
+    %1107 = COPY %1100
+    %1108 = COPY %1100
+    %1109 = COPY %1100
+    %1110 = COPY %1100
+    %1111 = COPY %1100
+    %1112 = COPY %1100
+    %1113 = COPY %1100
+    %1114 = COPY %1100
+    %1115 = COPY %1100
+    %1116 = COPY %1100
+    %1117 = COPY %1100
+    %1118 = COPY %1100
+    %1119 = COPY %1100
+    %1120 = COPY %1100
+    %1121 = COPY %1100
+    S_BRANCH %bb.1
+
+  bb.1:
+    liveins: $sgpr96_sgpr97, $sgpr98_sgpr99, $sgpr102_sgpr103
+    %0 = S_OR_SAVEEXEC_B64 $sgpr96_sgpr97, implicit-def $exec, implicit-def $scc, implicit $exec
+    $exec = S_XOR_B64_term $exec, %0, implicit-def $scc
+    SI_MASK_BRANCH %bb.100, implicit $exec
+    S_BRANCH %bb.2
+
+  bb.2:
+    liveins: $sgpr98_sgpr99, $sgpr102_sgpr103
+    %0:sreg_64 = S_OR_SAVEEXEC_B64 $sgpr98_sgpr99, implicit-def $exec, implicit-def $scc, implicit $exec
+    $exec = S_XOR_B64_term $exec, %0, implicit-def $scc
+    SI_MASK_BRANCH %bb.100, implicit $exec
+    S_BRANCH %bb.200
+
+  bb.100:
+    liveins: $sgpr102_sgpr103
+    %0:sreg_64 = S_OR_SAVEEXEC_B64 $sgpr102_sgpr103, implicit-def $exec, implicit-def $scc, implicit $exec
+    $exec = S_XOR_B64_term $exec, %0, implicit-def $scc
+    S_BRANCH %bb.200
+
+  bb.200:
+    S_CMP_EQ_U64 %1100.sub0_sub1, %1101.sub2_sub3, implicit-def $scc
+    S_CMP_EQ_U64 %1102.sub0_sub1, %1103.sub2_sub3, implicit-def $scc
+    S_CMP_EQ_U64 %1104.sub0_sub1, %1105.sub2_sub3, implicit-def $scc
+    S_CMP_EQ_U64 %1106.sub0_sub1, %1107.sub2_sub3, implicit-def $scc
+    S_CMP_EQ_U64 %1108.sub0_sub1, %1109.sub2_sub3, implicit-def $scc
+    S_CMP_EQ_U64 %1110.sub0_sub1, %1111.sub2_sub3, implicit-def $scc
+    S_CMP_EQ_U64 %1112.sub0_sub1, %1113.sub2_sub3, implicit-def $scc
+    S_CMP_EQ_U64 %1114.sub0_sub1, %1115.sub2_sub3, implicit-def $scc
+    S_CMP_EQ_U64 %1116.sub0_sub1, %1117.sub2_sub3, implicit-def $scc
+    S_CMP_EQ_U64 %1118.sub0_sub1, %1119.sub2_sub3, implicit-def $scc
+    S_CMP_EQ_U64 %1120.sub0_sub1, %1121.sub2_sub3, implicit-def $scc
+
+    $vgpr0 = V_MOV_B32_e32 0, implicit $exec
+    S_SETPC_B64_return %0, implicit $vgpr0
+
+...
+