[RISCV] Fix VSETVLI insertion by syncing phases 2 and 3

[frasercrmck]

Summary

This patch attempts to make the VSETVLI insertion pass more stable. A
lot of bugs are ultimately introduced due to phases being out of sync.

This is most notable when we skip VSETVLI insertion in phase 3 by re-using a
previous config, but still rely on phase 2 information which was
calculated without full knowledge of what we're going to skip.

The idea used in this patch is something @rogfer01 suggested in D124089.
By ensuring that VSETVLI "skips" are calculated in one re-usable place
(a new overload of needVSETVLI) we can use it during phases 1 and 2 to
produce more accurate information. In addition, during phase 2, we now
re-compute block-local VTYPE changes once predecessors have been
computed.

[frasercrmck]

adjust comments

[reames]

Have you tried adding asserts to the end of emitVSETVLIs to ensure the final block state is as expected? I strongly suspect this change is insufficient to fix all the cases.

I've been working on the same problem, but with a different approach. I've been trying to separate the PHI case and the mutation case into a separate phase 4 which works over the fully materialized form. I've got all the transforms (messily) implemented, but even with those out of line, I'm still getting failures of the expected block end state assert. I don't yet know why.

One really nasty case I came across - that I don't think your change handles - is that mutation of the prior vsetvli can change whether the current state is compatible with a following instruction. The compatibility logic includes a bit which looks back at the defining vsetvli for a vreg operand, and since we mutated it, the result can change between phase 1 and phase 3. At the moment, I'm thinking we can't have both that compatibility rule and the mutation in use in the same pass.

Now despite all that, I think your changes here really help in terms of code structure.

llvm/lib/Target/RISCV/RISCVInsertVSETVLI.cpp

1050

This bit on it's own is super important. It's slower, but it avoids the whole need for the merge and Change state entirely.

I think this is a good idea, and probably stands on it's own.

[reames]

Here (https://reviews.llvm.org/D125035) is the assertion I mentioned above as a flag we can use for testing.

[frasercrmck]

In D125021#3494767, @reames wrote:

Have you tried adding asserts to the end of emitVSETVLIs to ensure the final block state is as expected? I strongly suspect this change is insufficient to fix all the cases.

It's certainly not enough to fix all cases, as I'm seeing new regressions when testing this internally. Looks like we might be missing coverage on loops. I'll get to work on reducing those failures and committing them. Your asserts might help with that.

I've been working on the same problem, but with a different approach. I've been trying to separate the PHI case and the mutation case into a separate phase 4 which works over the fully materialized form. I've got all the transforms (messily) implemented, but even with those out of line, I'm still getting failures of the expected block end state assert. I don't yet know why.

One really nasty case I came across - that I don't think your change handles - is that mutation of the prior vsetvli can change whether the current state is compatible with a following instruction. The compatibility logic includes a bit which looks back at the defining vsetvli for a vreg operand, and since we mutated it, the result can change between phase 1 and phase 3. At the moment, I'm thinking we can't have both that compatibility rule and the mutation in use in the same pass.

Yeah I only really clocked this mutation thing yesterday. I thought that by including the "mutation" in needVSETVLI (now in phases 1 and 2) we might be able to get away with it being synced up?

Now despite all that, I think your changes here really help in terms of code structure.

Thanks. I do think having the one method to decide the compatibility and using it consistently across phases is logical and less error-prone. Unfortunately it seems we're not able to make what should be an NFC change without breaking things.

[frasercrmck]

rebase on new test which now fails

[frasercrmck]

llvm/test/CodeGen/RISCV/rvv/vsetvli-insert-crossbb.mir

824

This is a bug, but I'm not yet sure if it's dormant and exposed by this patch or actually caused by it.

[frasercrmck]

remove need for TmpStatus (and BBInfo.Change, really)

[frasercrmck]

pre-emptively include D125133

[frasercrmck]

This is all largely irrelevant now. I'll open a new revision for the API refactor.

llvm/lib/Target/RISCV/RISCVInsertVSETVLI.cpp

public:
   }
 
   // Determine whether the vector instructions requirements represented by
   // InstrInfo are compatible with the previous vsetvli instruction represented
   // by this.
   bool isCompatible(const VSETVLIInfo &InstrInfo, bool Strict) const {
     assert(isValid() && InstrInfo.isValid() &&
            "Can't compare invalid VSETVLIInfos");
-    assert(!InstrInfo.SEWLMULRatioOnly &&
-           "Expected a valid VTYPE for instruction!");
     // Nothing is compatible with Unknown.
     if (isUnknown() || InstrInfo.isUnknown())
       return false;
 
     // If only our VLMAX ratio is valid, then this isn't compatible.
-    if (SEWLMULRatioOnly)
+    if (SEWLMULRatioOnly || InstrInfo.SEWLMULRatioOnly)
       return false;
 
     // If the instruction doesn't need an AVLReg and the SEW matches, consider
     // it compatible.
     if (!Strict && InstrInfo.hasAVLReg() &&
         InstrInfo.AVLReg == RISCV::NoRegister) {
       if (SEW == InstrInfo.SEW)
         return true;
struct BlockData {
   VSETVLIInfo Pred;
 
   // Keeps track of whether the block is already in the queue.
   bool InQueue = false;
 
   BlockData() = default;
 };
 
+// The different kinds of VSETVLI insertion we support.
+enum VSETVLIInsertionKind {
+  // No VSETVLI required (e.g., compatible with previous)
+  None,
+  // A new VSETVLI is required
+  Required,
+  // A previous VSETVLI may safely be mutated.
+  MutatePrevious,
+};
+
 class RISCVInsertVSETVLI : public MachineFunctionPass {
   const TargetInstrInfo *TII;
   MachineRegisterInfo *MRI;
 
   std::vector<BlockData> BlockInfo;
   std::queue<const MachineBasicBlock *> WorkList;
 
 public:
   static char ID;
 
   RISCVInsertVSETVLI() : MachineFunctionPass(ID) {
     initializeRISCVInsertVSETVLIPass(*PassRegistry::getPassRegistry());
   }
   bool runOnMachineFunction(MachineFunction &MF) override;
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesCFG();
     MachineFunctionPass::getAnalysisUsage(AU);
   }
 
   StringRef getPassName() const override { return RISCV_INSERT_VSETVLI_NAME; }
 
 private:
   bool needVSETVLI(const VSETVLIInfo &Require, const VSETVLIInfo &CurInfo);
+  VSETVLIInsertionKind needVSETVLI(const MachineInstr &MI,
+                                   const VSETVLIInfo &Require,
+                                   const VSETVLIInfo &CurInfo,
+                                   const MachineInstr *PrevVSETVLIMI = nullptr);
   bool needVSETVLIPHI(const VSETVLIInfo &Require, const MachineBasicBlock &MBB);
   void insertVSETVLI(MachineBasicBlock &MBB, MachineInstr &MI,
                      const VSETVLIInfo &Info, const VSETVLIInfo &PrevInfo);
 
   bool computeVLVTYPEChanges(const MachineBasicBlock &MBB);
   void computeIncomingVLVTYPE(const MachineBasicBlock &MBB);
   void emitVSETVLIs(MachineBasicBlock &MBB);
 };
bool canSkipVSETVLIForLoadStore(const MachineInstr &MI,
   case RISCV::PseudoVSSE64_V_M8_MASK:
     EEW = 64;
     break;
   }
 
   return CurInfo.isCompatibleWithLoadStoreEEW(EEW, Require);
 }
 
+VSETVLIInsertionKind RISCVInsertVSETVLI::needVSETVLI(
+    const MachineInstr &MI, const VSETVLIInfo &Require,
+    const VSETVLIInfo &CurInfo, const MachineInstr *PrevVSETVLIMI) {
+  if (!needVSETVLI(Require, CurInfo))
+    return VSETVLIInsertionKind::None;
+
+  // If this is a unit-stride or strided load/store, we may be able to use
+  // the EMUL=(EEW/SEW)*LMUL relationship to avoid changing vtype.
+  if (canSkipVSETVLIForLoadStore(MI, Require, CurInfo))
+    return VSETVLIInsertionKind::None;
+
+  // If the previous VL/VTYPE is set by VSETVLI and do not use, Merge it
+  // with current VL/VTYPE.
+  if (PrevVSETVLIMI) {
+    bool HasSameAVL =
+        CurInfo.hasSameAVL(Require) ||
+        (Require.hasAVLReg() && Require.getAVLReg().isVirtual() &&
+         Require.getAVLReg() == PrevVSETVLIMI->getOperand(0).getReg());
+    // If these two VSETVLI have the same AVL and the same VLMAX,
+    // we could merge these two VSETVLI.
+    if (HasSameAVL && CurInfo.getSEWLMULRatio() == Require.getSEWLMULRatio())
+      return VSETVLIInsertionKind::MutatePrevious;
+
+    if (isScalarMoveInstr(MI) &&
+        ((CurInfo.hasNonZeroAVL() && Require.hasNonZeroAVL()) ||
+         (CurInfo.hasZeroAVL() && Require.hasZeroAVL())) &&
+        Require.hasSameVLMAX(CurInfo))
+      return VSETVLIInsertionKind::MutatePrevious;
+  }
+
+  return VSETVLIInsertionKind::Required;
+}
+
 bool RISCVInsertVSETVLI::computeVLVTYPEChanges(const MachineBasicBlock &MBB) {
   bool HadVectorOp = false;
 
+  // Only set if current VSETVLIInfo is from an explicit VSET(I)VLI.
+  const MachineInstr *PrevVSETVLIMI = nullptr;
+
   BlockData &BBInfo = BlockInfo[MBB.getNumber()];
   for (const MachineInstr &MI : MBB) {
     // If this is an explicit VSETVLI or VSETIVLI, update our state.
     if (isVectorConfigInstr(MI)) {
       HadVectorOp = true;
+      PrevVSETVLIMI = &MI;
       BBInfo.Change = getInfoForVSETVLI(MI);
       continue;
     }
 
     uint64_t TSFlags = MI.getDesc().TSFlags;
     if (RISCVII::hasSEWOp(TSFlags)) {
       HadVectorOp = true;
 
       VSETVLIInfo NewInfo = computeInfoForInstr(MI, TSFlags, MRI);
 
       if (!BBInfo.Change.isValid()) {
         BBInfo.Change = NewInfo;
       } else {
         // If this instruction isn't compatible with the previous VL/VTYPE
         // we need to insert a VSETVLI.
-        // If this is a unit-stride or strided load/store, we may be able to use
-        // the EMUL=(EEW/SEW)*LMUL relationship to avoid changing vtype.
         // NOTE: We only do this if the vtype we're comparing against was
         // created in this block. We need the first and third phase to treat
         // the store the same way.
-        if (!canSkipVSETVLIForLoadStore(MI, NewInfo, BBInfo.Change) &&
-            needVSETVLI(NewInfo, BBInfo.Change))
+        if (needVSETVLI(MI, NewInfo, BBInfo.Change, PrevVSETVLIMI) !=
+            VSETVLIInsertionKind::None) {
           BBInfo.Change = NewInfo;
         }
       }
+      PrevVSETVLIMI = nullptr;
+    }
 
     // If this is something that updates VL/VTYPE that we don't know about, set
     // the state to unknown.
     if (MI.isCall() || MI.isInlineAsm() || MI.modifiesRegister(RISCV::VL) ||
         MI.modifiesRegister(RISCV::VTYPE)) {
       BBInfo.Change = VSETVLIInfo::getUnknown();
     }
   }
void RISCVInsertVSETVLI::computeIncomingVLVTYPE(const MachineBasicBlock &MBB) {
   }
 
   // If we don't have any valid predecessor value, wait until we do.
   if (!InInfo.isValid())
     return;
 
   BBInfo.Pred = InInfo;
 
+  // Now that we've computed the info for predecessors, recompute the VTYPE
+  // changes on this block. The predecessors may have changed the incoming
+  // vtype and we must be in sync with phase 3.
+  BBInfo.Change = InInfo;
+  computeVLVTYPEChanges(MBB);
+
   VSETVLIInfo TmpStatus = BBInfo.Pred.merge(BBInfo.Change);
 
   // If the new exit value matches the old exit value, we don't need to revisit
   // any blocks.
   if (BBInfo.Exit == TmpStatus)
     return;
 
   BBInfo.Exit = TmpStatus;
bool RISCVInsertVSETVLI::needVSETVLIPHI(const VSETVLIInfo &Require,
 
   // If all the incoming values to the PHI checked out, we don't need
   // to insert a VSETVLI.
   return false;
 }
 
 void RISCVInsertVSETVLI::emitVSETVLIs(MachineBasicBlock &MBB) {
   VSETVLIInfo CurInfo;
-  // Only be set if current VSETVLIInfo is from an explicit VSET(I)VLI.
+  // Only set if current VSETVLIInfo is from an explicit VSET(I)VLI.
   MachineInstr *PrevVSETVLIMI = nullptr;
 
   for (MachineInstr &MI : MBB) {
     // If this is an explicit VSETVLI or VSETIVLI, update our state.
     if (isVectorConfigInstr(MI)) {
       // Conservatively, mark the VL and VTYPE as live.
       assert(MI.getOperand(3).getReg() == RISCV::VL &&
              MI.getOperand(4).getReg() == RISCV::VTYPE &&
if (RISCVII::hasSEWOp(TSFlags)) {
         if (needVSETVLI(NewInfo, BlockInfo[MBB.getNumber()].Pred) &&
             needVSETVLIPHI(NewInfo, MBB)) {
           insertVSETVLI(MBB, MI, NewInfo, BlockInfo[MBB.getNumber()].Pred);
           CurInfo = NewInfo;
         }
       } else {
         // If this instruction isn't compatible with the previous VL/VTYPE
         // we need to insert a VSETVLI.
-        // If this is a unit-stride or strided load/store, we may be able to use
-        // the EMUL=(EEW/SEW)*LMUL relationship to avoid changing vtype.
         // NOTE: We can't use predecessor information for the store. We must
         // treat it the same as the first phase so that we produce the correct
-        // vl/vtype for succesor blocks.
-        if (!canSkipVSETVLIForLoadStore(MI, NewInfo, CurInfo) &&
-            needVSETVLI(NewInfo, CurInfo)) {
-          // If the previous VL/VTYPE is set by VSETVLI and do not use, Merge it
-          // with current VL/VTYPE.
-          bool NeedInsertVSETVLI = true;
-          if (PrevVSETVLIMI) {
-            bool HasSameAVL =
-                CurInfo.hasSameAVL(NewInfo) ||
-                (NewInfo.hasAVLReg() && NewInfo.getAVLReg().isVirtual() &&
-                 NewInfo.getAVLReg() == PrevVSETVLIMI->getOperand(0).getReg());
-            // If these two VSETVLI have the same AVL and the same VLMAX,
-            // we could merge these two VSETVLI.
-            if (HasSameAVL &&
-                CurInfo.getSEWLMULRatio() == NewInfo.getSEWLMULRatio()) {
-              PrevVSETVLIMI->getOperand(2).setImm(NewInfo.encodeVTYPE());
-              NeedInsertVSETVLI = false;
-            }
-            if (isScalarMoveInstr(MI) &&
-                ((CurInfo.hasNonZeroAVL() && NewInfo.hasNonZeroAVL()) ||
-                 (CurInfo.hasZeroAVL() && NewInfo.hasZeroAVL())) &&
-                NewInfo.hasSameVLMAX(CurInfo)) {
-              PrevVSETVLIMI->getOperand(2).setImm(NewInfo.encodeVTYPE());
-              NeedInsertVSETVLI = false;
-            }
-          }
-          if (NeedInsertVSETVLI)
+        // vl/vtype for successor blocks.
+        auto Kind = needVSETVLI(MI, NewInfo, CurInfo, PrevVSETVLIMI);
+        if (Kind != VSETVLIInsertionKind::None) {
+          if (Kind == VSETVLIInsertionKind::Required)
             insertVSETVLI(MBB, MI, NewInfo, CurInfo);
+          else if (Kind == VSETVLIInsertionKind::MutatePrevious)
+            PrevVSETVLIMI->getOperand(2).setImm(NewInfo.encodeVTYPE());
           CurInfo = NewInfo;
         }
       }
       PrevVSETVLIMI = nullptr;
     }
 
     // If this is something updates VL/VTYPE that we don't know about, set
     // the state to unknown.

llvm/test/CodeGen/RISCV/rvv/vsetvli-insert-crossbb.mir

bb.2.middle.block:
     %20:vr = PseudoVMV_S_X_M1 %21, %19, 1, 5
     %24:vr = IMPLICIT_DEF
     %23:vr = PseudoVREDSUM_VS_M1 %24, %16, killed %20, 4, 5
     PseudoVSE32_V_M1 killed %23, %8, 1, 5 :: (store (s32) into %ir.res)
     PseudoRET
 
 ...
 ---
-# FIXME: This test shows incorrect VSETVLI insertion. The VLUXEI64 needs
-# configuration for SEW=8 but it instead inherits a SEW=64 from the entry
-# block.
 name:            vsetvli_vluxei64_regression
 tracksRegLiveness: true
 body:             |
   ; CHECK-LABEL: name: vsetvli_vluxei64_regression
   ; CHECK: bb.0:
   ; CHECK-NEXT:   successors: %bb.1(0x80000000)
   ; CHECK-NEXT:   liveins: $x10, $x11, $x12, $v0, $v1, $v2, $v3
   ; CHECK-NEXT: {{  $}}
body:             |
   ; CHECK-NEXT:   %t2:gpr = COPY $x0
   ; CHECK-NEXT:   BEQ %a, %t2, %bb.3
   ; CHECK-NEXT:   PseudoBR %bb.2
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT: bb.2:
   ; CHECK-NEXT:   successors: %bb.3(0x80000000)
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT:   $v0 = COPY %mask
+  ; CHECK-NEXT:   dead $x0 = PseudoVSETVLIX0 killed $x0, 69 /* e8, mf8, ta, mu */, implicit-def $vl, implicit-def $vtype, implicit $vl
   ; CHECK-NEXT:   early-clobber %t0:vrnov0 = PseudoVLUXEI64_V_M1_MF8_MASK %t5, killed %inaddr, %idxs, $v0, -1, 3 /* e8 */, 1, implicit $vl, implicit $vtype
   ; CHECK-NEXT:   %ldval:vr = COPY %t0
   ; CHECK-NEXT:   PseudoBR %bb.3
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT: bb.3:
   ; CHECK-NEXT:   %stval:vr = PHI %t4, %bb.1, %ldval, %bb.2
   ; CHECK-NEXT:   $v0 = COPY %mask
+  ; CHECK-NEXT:   dead $x0 = PseudoVSETVLIX0 killed $x0, 69 /* e8, mf8, ta, mu */, implicit-def $vl, implicit-def $vtype, implicit $vl
   ; CHECK-NEXT:   PseudoVSOXEI64_V_M1_MF8_MASK killed %stval, killed %b, %idxs, $v0, -1, 3 /* e8 */, implicit $vl, implicit $vtype
   ; CHECK-NEXT:   PseudoRET
   bb.0:
     successors: %bb.1
     liveins: $x10, $x11, $x12, $v0, $v1, $v2, $v3
 
     %a:gpr = COPY $x10
     %b:gpr = COPY $x11
bb.2:
     PseudoBR %bb.3
 
   bb.3:
     %stval:vr = PHI %t4, %bb.1, %ldval, %bb.2
     $v0 = COPY %mask
     PseudoVSOXEI64_V_M1_MF8_MASK killed %stval, killed %b, %idxs, $v0, -1, 3
     PseudoRET
 
 ...