[RISCV] Teach VSETVLI insertion to look through PHIs to prove we don't need to insert a vsetvli.

[craig.topper]

Summary

If an instruction's AVL operand is a PHI node in the same block,
we may be able to peek through the PHI to find vsetvli instructions
that produce the AVL in other basic blocks. If we can prove those
vsetvli instructions have the same VTYPE and were the last vsetvli
in their respective blocks, then we don't need to insert a vsetvli
for this pseudo instruction.

[rogfer01]

LGTM. Thanks @craig.topper

llvm/lib/Target/RISCV/RISCVInsertVSETVLI.cpp

36

Just curious here: do you foresee this might get expensive or this is a debugging utility?

[craig.topper]

llvm/lib/Target/RISCV/RISCVInsertVSETVLI.cpp

36

Paranoia. Combining phis and data flow made me a little nervous. Our earlier internal version of this in the EPIRemoveRedundantVSETVLGlobal pass was missing the check that the phi was in the same basic block. A miscompile from it was found months later.

I wonder if we should also have a disable on the global cross BB code. I think EPIRemoveRedundantVSETVLGlobal has a disable right?

llvm/lib/Target/RISCV/RISCVInsertVSETVLI.cpp

 #include "llvm/CodeGen/LiveIntervals.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include <queue>
 using namespace llvm;
 
 #define DEBUG_TYPE "riscv-insert-vsetvli"
 #define RISCV_INSERT_VSETVLI_NAME "RISCV Insert VSETVLI pass"
 
+static cl::opt<bool> DisableInsertVSETVLPHIOpt(
+    "riscv-disable-insert-vsetvl-phi-opt", cl::init(false), cl::Hidden,
+    cl::desc("Disable looking through phis when inserting vsetvlis."));
+
 namespace {
 
 class VSETVLIInfo {
   union {
     Register AVLReg;
     unsigned AVLImm;
   };
 
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);
+  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);
 };
 
void RISCVInsertVSETVLI::computeIncomingVLVTYPE(const MachineBasicBlock &MBB) {
 
   // Add the successors to the work list so we can propagate the changed exit
   // status.
   for (MachineBasicBlock *S : MBB.successors())
     if (!BlockInfo[S->getNumber()].InQueue)
       WorkList.push(S);
 }
 
+// If we weren't able to prove a vsetvli was directly unneeded, it might still
+// be/ unneeded if the AVL is a phi node where all incoming values are VL
+// outputs from the last VSETVLI in their respective basic blocks.
+bool RISCVInsertVSETVLI::needVSETVLIPHI(const VSETVLIInfo &Require,
+                                        const MachineBasicBlock &MBB) {
+  if (DisableInsertVSETVLPHIOpt)
+    return true;
+
+  if (!Require.hasAVLReg())
+    return true;
+
+  Register AVLReg = Require.getAVLReg();
+  if (!AVLReg.isVirtual())
+    return true;
+
+  // We need the AVL to be produce by a PHI node in this basic block.
+  MachineInstr *PHI = MRI->getVRegDef(AVLReg);
+  if (!PHI || PHI->getOpcode() != RISCV::PHI || PHI->getParent() != &MBB)
+    return true;
+
+  for (unsigned PHIOp = 1, NumOps = PHI->getNumOperands(); PHIOp != NumOps;
+       PHIOp += 2) {
+    Register InReg = PHI->getOperand(PHIOp).getReg();
+    MachineBasicBlock *PBB = PHI->getOperand(PHIOp + 1).getMBB();
+    const BlockData &PBBInfo = BlockInfo[PBB->getNumber()];
+    // If the exit from the predecessor has the VTYPE we are looking for
+    // we might be able to avoid a VSETVLI.
+    if (PBBInfo.Exit.isUnknown() || !PBBInfo.Exit.hasSameVTYPE(Require))
+      return true;
+
+    // We need the PHI input to the be the output of a VSET(I)VLI.
+    MachineInstr *DefMI = MRI->getVRegDef(InReg);
+    if (!DefMI || (DefMI->getOpcode() != RISCV::PseudoVSETVLI &&
+                   DefMI->getOpcode() != RISCV::PseudoVSETIVLI))
+      return true;
+
+    // We found a VSET(I)VLI make sure it matches the output of the
+    // predecessor block.
+    VSETVLIInfo DefInfo = getInfoForVSETVLI(*DefMI);
+    if (!DefInfo.hasSameAVL(PBBInfo.Exit) ||
+        !DefInfo.hasSameVTYPE(PBBInfo.Exit))
+      return true;
+  }
+
+  // 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;
 
   for (MachineInstr &MI : MBB) {
     // If this is an explicit VSETVLI or VSETIVLI, update our state.
     if (MI.getOpcode() == RISCV::PseudoVSETVLI ||
         MI.getOpcode() == RISCV::PseudoVSETIVLI) {
       // Conservatively, mark the VL and VTYPE as live.
if (RISCVII::hasSEWOp(TSFlags)) {
       MI.addOperand(MachineOperand::CreateReg(RISCV::VTYPE, /*isDef*/ false,
                                               /*isImp*/ true));
 
       if (!CurInfo.isValid()) {
         // We haven't found any vector instructions or VL/VTYPE changes yet,
         // use the predecessor information.
         assert(BlockInfo[MBB.getNumber()].Pred.isValid() &&
                "Expected a valid predecessor state.");
-        if (needVSETVLI(NewInfo, BlockInfo[MBB.getNumber()].Pred)) {
+        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 (needVSETVLI(NewInfo, CurInfo)) {
           insertVSETVLI(MBB, MI, NewInfo, CurInfo);

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

if.else:                                          ; preds = %entry
   br label %if.end
 
 if.end:                                           ; preds = %if.else, %if.then
   %c.0 = phi <vscale x 1 x double> [ %1, %if.then ], [ %2, %if.else ]
   %3 = tail call <vscale x 1 x double> @llvm.riscv.vfmul.nxv1f64.nxv1f64(<vscale x 1 x double> %c.0, <vscale x 1 x double> %a, i64 %0)
   ret <vscale x 1 x double> %3
 }
 
-; FIXME: The last vsetvli is redundant, but we need to look through a phi to
-; prove it.
 define <vscale x 1 x double> @test3(i64 %avl, i8 zeroext %cond, <vscale x 1 x double> %a, <vscale x 1 x double> %b) nounwind {
 ; CHECK-LABEL: test3:
 ; CHECK:       # %bb.0: # %entry
 ; CHECK-NEXT:    beqz a1, .LBB2_2
 ; CHECK-NEXT:  # %bb.1: # %if.then
 ; CHECK-NEXT:    vsetvli a0, a0, e64,m1,ta,mu
 ; CHECK-NEXT:    vfadd.vv v25, v8, v9
-; CHECK-NEXT:    j .LBB2_3
+; CHECK-NEXT:    vfmul.vv v8, v25, v8
+; CHECK-NEXT:    ret
 ; CHECK-NEXT:  .LBB2_2: # %if.else
 ; CHECK-NEXT:    vsetvli a0, a0, e64,m1,ta,mu
 ; CHECK-NEXT:    vfsub.vv v25, v8, v9
-; CHECK-NEXT:  .LBB2_3: # %if.end
-; CHECK-NEXT:    vsetvli zero, a0, e64,m1,ta,mu
 ; CHECK-NEXT:    vfmul.vv v8, v25, v8
 ; CHECK-NEXT:    ret
 entry:
   %tobool = icmp eq i8 %cond, 0
   br i1 %tobool, label %if.else, label %if.then
 
 if.then:                                          ; preds = %entry
   %0 = tail call i64 @llvm.riscv.vsetvli(i64 %avl, i64 3, i64 0)
if.else:                                          ; preds = %entry
   br label %if.end
 
 if.end:                                           ; preds = %if.else, %if.then
   %c.0 = phi <vscale x 1 x double> [ %1, %if.then ], [ %2, %if.else ]
   %3 = tail call <vscale x 1 x double> @llvm.riscv.vfmul.nxv1f64.nxv1f64(<vscale x 1 x double> %c.0, <vscale x 1 x double> %a, i64 %0)
   ret <vscale x 1 x double> %3
 }
 
-; FIXME: The vsetvli in for.body can be removed, it's redundant by its
-; predecessors, but we need to look through a PHI to prove it.
 define void @saxpy_vec(i64 %n, float %a, float* nocapture readonly %x, float* nocapture %y) {
 ; CHECK-LABEL: saxpy_vec:
 ; CHECK:       # %bb.0: # %entry
 ; CHECK-NEXT:    vsetvli a4, a0, e32,m8,ta,mu
 ; CHECK-NEXT:    beqz a4, .LBB8_3
 ; CHECK-NEXT:  # %bb.1: # %for.body.preheader
 ; CHECK-NEXT:    fmv.w.x ft0, a1
 ; CHECK-NEXT:  .LBB8_2: # %for.body
 ; CHECK-NEXT:    # =>This Inner Loop Header: Depth=1
-; CHECK-NEXT:    vsetvli zero, a4, e32,m8,ta,mu
 ; CHECK-NEXT:    vle32.v v8, (a2)
 ; CHECK-NEXT:    vle32.v v16, (a3)
 ; CHECK-NEXT:    slli a1, a4, 2
 ; CHECK-NEXT:    add a2, a2, a1
-; CHECK-NEXT:    vsetvli zero, zero, e32,m8,tu,mu
+; CHECK-NEXT:    vsetvli zero, a4, e32,m8,tu,mu
 ; CHECK-NEXT:    vfmacc.vf v16, ft0, v8
 ; CHECK-NEXT:    vsetvli zero, zero, e32,m8,ta,mu
 ; CHECK-NEXT:    vse32.v v16, (a3)
 ; CHECK-NEXT:    sub a0, a0, a4
 ; CHECK-NEXT:    vsetvli a4, a0, e32,m8,ta,mu
 ; CHECK-NEXT:    add a3, a3, a1
 ; CHECK-NEXT:    bnez a4, .LBB8_2
 ; CHECK-NEXT:  .LBB8_3: # %for.end