[AMDGPU] Avoid redundant mode register writes

[timcorringham]

Summary

The SIModeRegister pass attempts to generate the minimal number of
writes to the mode register. However it was failing to correctly
deal with some loops, resulting in some redundant setreg instructions
being inserted.

This change amends the pass to avoid generating these redundant
instructions.

[foad]

Overall I think this is probably OK but (a) I'd like to see it with some of the irrelevant stuff removed and (b) there is ample scope for making this pass look much more like a "normal" dataflow solver, where Status should be a lattice with a proper "bottom" value, the phase 2 worklist should be seeded with just the entry block so we don't have to worry about visiting unreachable blocks, and hopefully processBlockPhase2 will get much simpler again.

llvm/lib/Target/AMDGPU/SIModeRegister.cpp

86

Looks like this is just reformatting. Please commit separately. Maybe even clang-format the whole file first?

115

Just reformatting?

136

Why is this needed? Was there a problem with the existing code using NumSetRegInserted?

355

If a block is its only predecessor then either it's the entry block (this wouldn't be allowed in IR but I guess it is in MIR?), or it's an unreachable single block loop, and it doesn't matter what we do in unreachable code. So the only useful thing this line and line 338 achieve is to set DefaultStatus at the start of the entry block. It seems like this could be simplified.

403–405

Just reformatting?

[timcorringham]

llvm/lib/Target/AMDGPU/SIModeRegister.cpp

86

clang-format did this - I will commit a clang-format version first and then update this review to eliminate formatting changes.

115

It now initialises ExitSet.

136

NumSetReginserted is a STATISTIC, and as such only works when LLVM is built with asserts or debug mode enabled - which is something I hadn't realised when I wrote the original code

355

This handles a case that should never happen but which would cause a loop if it did.

403–405

clang-format again.

[timcorringham]

Removed changes introduced only by clang-format format.

[arsenm]

llvm/lib/Target/AMDGPU/SIModeRegister.cpp

136

Probably should rename this, since this really should try to use S_ROUND_MODE/S_DENORM_MODE

202–206

This should use the encode function from utils for this, but that's a separate cleanup I guess (plus try to use the new gfx10 instruction)

llvm/test/CodeGen/AMDGPU/mode-register.mir

464–465

CHECK-NOT can be fragile. The case is so small I would generate the checks

[foad]

LGTM modulo Matt's comments and please consider cleaning it all up as mentioned earlier.

llvm/lib/Target/AMDGPU/SIModeRegister.cpp

136

Changed is the usual name for this kind of flag.

[timcorringham]

llvm/lib/Target/AMDGPU/SIModeRegister.cpp

202–206

Planned for a future change.

llvm/lib/Target/AMDGPU/SIModeRegister.cpp

struct Status {
   }
 
   bool operator!=(const Status &S) const { return !(*this == S); }
 
   bool isCompatible(Status &S) {
     return ((Mask & S.Mask) == S.Mask) && ((Mode & S.Mask) == S.Mode);
   }
 
   bool isCombinable(Status &S) { return !(Mask & S.Mask) || isCompatible(S); }
 };
 
 class BlockData {
 public:
   // The Status that represents the mode register settings required by the
   // FirstInsertionPoint (if any) in this block. Calculated in Phase 1.
   Status Require;
 
   // The Status that represents the net changes to the Mode register made by
   // this block, Calculated in Phase 1.
   Status Change;
 
   // The Status that represents the mode register settings on exit from this
   // block. Calculated in Phase 2.
   Status Exit;
 
   // The Status that represents the intersection of exit Mode register settings
   // from all predecessor blocks. Calculated in Phase 2, and used by Phase 3.
   Status Pred;
 
   // In Phase 1 we record the first instruction that has a mode requirement,
   // which is used in Phase 3 if we need to insert a mode change.
   MachineInstr *FirstInsertionPoint;
 
-  BlockData() : FirstInsertionPoint(nullptr){};
+  // A flag to indicate whether an Exit value has been set (we can't tell by
+  // examining the Exit value itself as all values may be valid results).
+  bool ExitSet;
+
+  BlockData() : FirstInsertionPoint(nullptr), ExitSet(false){};
 };
 
 namespace {
 
 class SIModeRegister : public MachineFunctionPass {
 public:
   static char ID;
 
   std::vector<std::unique_ptr<BlockData>> BlockInfo;
   std::queue<MachineBasicBlock *> Phase2List;
 
   // The default mode register setting currently only caters for the floating
   // point double precision rounding mode.
   // We currently assume the default rounding mode is Round to Nearest
   // NOTE: this should come from a per function rounding mode setting once such
   // a setting exists.
   unsigned DefaultMode = FP_ROUND_ROUND_TO_NEAREST;
   Status DefaultStatus =
       Status(FP_ROUND_MODE_DP(0x3), FP_ROUND_MODE_DP(DefaultMode));
 
+  bool Changed = false;
+
 public:
   SIModeRegister() : MachineFunctionPass(ID) {}
 
   bool runOnMachineFunction(MachineFunction &MF) override;
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesCFG();
     MachineFunctionPass::getAnalysisUsage(AU);

 // value of the intervening bits. In that case we need to use more than one
 // setreg instruction.
 void SIModeRegister::insertSetreg(MachineBasicBlock &MBB, MachineInstr *MI,
                                   const SIInstrInfo *TII, Status InstrMode) {
   while (InstrMode.Mask) {
     unsigned Offset = countTrailingZeros<unsigned>(InstrMode.Mask);
     unsigned Width = countTrailingOnes<unsigned>(InstrMode.Mask >> Offset);
     unsigned Value = (InstrMode.Mode >> Offset) & ((1 << Width) - 1);
     BuildMI(MBB, MI, 0, TII->get(AMDGPU::S_SETREG_IMM32_B32))
         .addImm(Value)
         .addImm(((Width - 1) << AMDGPU::Hwreg::WIDTH_M1_SHIFT_) |
                 (Offset << AMDGPU::Hwreg::OFFSET_SHIFT_) |
                 (AMDGPU::Hwreg::ID_MODE << AMDGPU::Hwreg::ID_SHIFT_));
     ++NumSetregInserted;
+    Changed = true;
     InstrMode.Mask &= ~(((1 << Width) - 1) << Offset);
   }
 }
 
 // In Phase 1 we iterate through the instructions of the block and for each
 // instruction we get its mode usage. If the instruction uses the Mode register
 // we:
 // - update the Change status, which tracks the changes to the Mode register

 }
 
 // In Phase 2 we revisit each block and calculate the common Mode register
 // value provided by all predecessor blocks. If the Exit value for the block
 // is changed, then we add the successor blocks to the worklist so that the
 // exit value is propagated.
 void SIModeRegister::processBlockPhase2(MachineBasicBlock &MBB,
                                         const SIInstrInfo *TII) {
-  //  BlockData *BI = BlockInfo[MBB.getNumber()];
+  bool RevisitRequired = false;
+  bool ExitSet = false;
   unsigned ThisBlock = MBB.getNumber();
   if (MBB.pred_empty()) {
     // There are no predecessors, so use the default starting status.
     BlockInfo[ThisBlock]->Pred = DefaultStatus;
+    ExitSet = true;
   } else {
     // Build a status that is common to all the predecessors by intersecting
     // all the predecessor exit status values.
+    // Mask bits (which represent the Mode bits with a known value) can only be
+    // added by explicit SETREG instructions or the initial default value -
+    // the intersection process may remove Mask bits.
+    // If we find a predecessor that has not yet had an exit value determined
+    // (this can happen for example if a block is its own predecessor) we defer
+    // use of that value as the Mask will be all zero, and we will revisit this
+    // block again later (unless the only predecessor without an exit value is
+    // this block).
     MachineBasicBlock::pred_iterator P = MBB.pred_begin(), E = MBB.pred_end();
     MachineBasicBlock &PB = *(*P);
-    BlockInfo[ThisBlock]->Pred = BlockInfo[PB.getNumber()]->Exit;
+    unsigned PredBlock = PB.getNumber();
+    if ((ThisBlock == PredBlock) && (std::next(P) == E)) {
+      BlockInfo[ThisBlock]->Pred = DefaultStatus;
+      ExitSet = true;
+    } else if (BlockInfo[PredBlock]->ExitSet) {
+      BlockInfo[ThisBlock]->Pred = BlockInfo[PredBlock]->Exit;
+      ExitSet = true;
+    } else if (PredBlock != ThisBlock)
+      RevisitRequired = true;
 
     for (P = std::next(P); P != E; P = std::next(P)) {
       MachineBasicBlock *Pred = *P;
-      BlockInfo[ThisBlock]->Pred = BlockInfo[ThisBlock]->Pred.intersect(
-          BlockInfo[Pred->getNumber()]->Exit);
+      unsigned PredBlock = Pred->getNumber();
+      if (BlockInfo[PredBlock]->ExitSet) {
+        if (BlockInfo[ThisBlock]->ExitSet) {
+          BlockInfo[ThisBlock]->Pred =
+              BlockInfo[ThisBlock]->Pred.intersect(BlockInfo[PredBlock]->Exit);
+        } else {
+          BlockInfo[ThisBlock]->Pred = BlockInfo[PredBlock]->Exit;
+        }
+        ExitSet = true;
+      } else if (PredBlock != ThisBlock)
+        RevisitRequired = true;
     }
   }
   Status TmpStatus =
       BlockInfo[ThisBlock]->Pred.merge(BlockInfo[ThisBlock]->Change);
   if (BlockInfo[ThisBlock]->Exit != TmpStatus) {
     BlockInfo[ThisBlock]->Exit = TmpStatus;
     // Add the successors to the work list so we can propagate the changed exit
     // status.
     for (MachineBasicBlock::succ_iterator S = MBB.succ_begin(),
                                           E = MBB.succ_end();
          S != E; S = std::next(S)) {
       MachineBasicBlock &B = *(*S);
       Phase2List.push(&B);
     }
   }
+  BlockInfo[ThisBlock]->ExitSet = ExitSet;
+  if (RevisitRequired)
+    Phase2List.push(&MBB);
 }
 
 // In Phase 3 we revisit each block and if it has an insertion point defined we
 // check whether the predecessor mode meets the block's entry requirements. If
 // not we insert an appropriate setreg instruction to modify the Mode register.
 void SIModeRegister::processBlockPhase3(MachineBasicBlock &MBB,
                                         const SIInstrInfo *TII) {
-  //  BlockData *BI = BlockInfo[MBB.getNumber()];
   unsigned ThisBlock = MBB.getNumber();
   if (!BlockInfo[ThisBlock]->Pred.isCompatible(BlockInfo[ThisBlock]->Require)) {
     Status Delta =
         BlockInfo[ThisBlock]->Pred.delta(BlockInfo[ThisBlock]->Require);
     if (BlockInfo[ThisBlock]->FirstInsertionPoint)
       insertSetreg(MBB, BlockInfo[ThisBlock]->FirstInsertionPoint, TII, Delta);
     else
       insertSetreg(MBB, &MBB.instr_front(), TII, Delta);
   }
 }
 
 bool SIModeRegister::runOnMachineFunction(MachineFunction &MF) {
   BlockInfo.resize(MF.getNumBlockIDs());
bool SIModeRegister::runOnMachineFunction(MachineFunction &MF) {
 
   // Phase 3 - add an initial setreg to each block where the required entry mode
   // is not satisfied by the exit mode of all its predecessors.
   for (MachineBasicBlock &BB : MF)
     processBlockPhase3(BB, TII);
 
   BlockInfo.clear();
 
-  return NumSetregInserted > 0;
+  return Changed;
 }

llvm/test/CodeGen/AMDGPU/mode-register.mir

body: |
   bb.3:
     successors: %bb.4
     $vgpr3_vgpr4 = V_FRACT_F64_e32 killed $vgpr3_vgpr4, implicit $mode, implicit $exec
     S_BRANCH %bb.4
 
   bb.4:
     S_ENDPGM 0
 ...
+---
+# checks for bug where if a block is its own predecessor it could cause mode tracking
+# to produce the wrong mode, resulting in an unnecessary setreg
+# CHECK-LABEL: name: single_block_loop
+# CHECK-LABEL: bb.0:
+# CHECK-NOT: S_SETREG
+
+name: single_block_loop
+
+body: |
+  bb.0:
+    successors: %bb.1
+    S_BRANCH %bb.1
+
+  bb.1:
+    successors: %bb.1, %bb.2
+    S_CBRANCH_VCCZ %bb.1, implicit $vcc
+    S_BRANCH %bb.2
+
+  bb.2:
+    successors: %bb.3
+    liveins: $vgpr1_vgpr2
+    $vgpr1_vgpr2 = V_FRACT_F64_e32 killed $vgpr1_vgpr2, implicit $mode, implicit $exec
+    S_BRANCH %bb.3
+
+  bb.3:
+    S_ENDPGM 0
+...
+---
+# checks for a bug where if the first block is its own predecessor the initial mode was
+# not correctly propagated, resulting in an unnecessary setreg
+# CHECK-LABEL: name: first_block_loop
+# CHECK-LABEL: bb.0:
+# CHECK-NOT: S_SETREG
+
+name: first_block_loop
+
+body: |
+  bb.0:
+    successors: %bb.0, %bb.1
+    S_CBRANCH_VCCZ %bb.0, implicit $vcc
+    S_BRANCH %bb.1
+
+  bb.1:
+    successors: %bb.2
+    liveins: $vgpr1_vgpr2
+    $vgpr1_vgpr2 = V_FRACT_F64_e32 killed $vgpr1_vgpr2, implicit $mode, implicit $exec
+    S_BRANCH %bb.2
+
+  bb.2:
+    S_ENDPGM 0
+...