[ARM] Find VPT implicitly predicated by VCTP

[samparker]

Summary

On failing to find a VCTP in the list of instructions that explicitly predicate the entry of a VPT block, inspect whether the block is controlled via VPT which is implicitly predicated due to it's predicated operand(s).

[samtebbs]

llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp

266

Should this also check for the instruction being a VPT?

[samparker]

llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp

266

We only start VPTBlocks on VPST and VPT, so I will add an assert.

[samparker]

Rebased and added an assert.

[samtebbs]

Nice change! LGTM

llvm/lib/CodeGen/ReachingDefAnalysis.cpp

 
 MachineInstr *ReachingDefAnalysis::getUniqueReachingMIDef(MachineInstr *MI,
                                                           int PhysReg) const {
   // If there's a local def before MI, return it.
   MachineInstr *LocalDef = getReachingLocalMIDef(MI, PhysReg);
   if (LocalDef && InstIds.lookup(LocalDef) < InstIds.lookup(MI))
     return LocalDef;
 
-  SmallPtrSet<MachineBasicBlock*, 4> VisitedBBs;
   SmallPtrSet<MachineInstr*, 2> Incoming;
   MachineBasicBlock *Parent = MI->getParent();
   for (auto *Pred : Parent->predecessors())
     getLiveOuts(Pred, PhysReg, Incoming);
 
   // Check that we have a single incoming value and that it does not
   // come from the same block as MI - since it would mean that the def
   // is executed after MI.

llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp

public:
 
     // Is the VPST, controlling the block entry, predicated upon a VCTP.
     static bool isEntryPredicatedOnVCTP(VPTState &Block,
                                         bool Exclusive = false) {
       SmallVectorImpl<MachineInstr *> &Insts = Block.getInsts();
       return isPredicatedOnVCTP(Insts.front(), Exclusive);
     }
 
-    static bool isValid() {
+    // If this block begins with a VPT, we can check whether it's using
+    // at least one predicated input(s), as well as possible loop invariant
+    // which would result in it being implicitly predicated.
+    static bool hasImplicitlyValidVPT(VPTState &Block,
+                                      ReachingDefAnalysis &RDA) {
+      SmallVectorImpl<MachineInstr *> &Insts = Block.getInsts();
+      MachineInstr *VPT = Insts.front();
+      assert(isVPTOpcode(VPT->getOpcode()) &&
+             "Expected VPT block to begin with VPT/VPST");
+
+      if (VPT->getOpcode() == ARM::MVE_VPST)
+        return false;
+
+      auto IsOperandPredicated = [&](MachineInstr *MI, unsigned Idx) {
+        MachineInstr *Op = RDA.getMIOperand(MI, MI->getOperand(Idx));
+        return Op && PredicatedInsts.count(Op) && isPredicatedOnVCTP(Op);
+      };
+
+      auto IsOperandInvariant = [&](MachineInstr *MI, unsigned Idx) {
+        MachineOperand &MO = MI->getOperand(Idx);
+        if (!MO.isReg() || !MO.getReg())
+          return true;
+
+        SmallPtrSet<MachineInstr *, 2> Defs;
+        RDA.getGlobalReachingDefs(MI, MO.getReg(), Defs);
+        if (Defs.empty())
+          return true;
+
+        for (auto *Def : Defs)
+          if (Def->getParent() == VPT->getParent())
+            return false;
+        return true;
+      };
+
+      // Check that at least one of the operands is directly predicated on a
+      // vctp and allow an invariant value too.
+      return (IsOperandPredicated(VPT, 1) || IsOperandPredicated(VPT, 2)) &&
+             (IsOperandPredicated(VPT, 1) || IsOperandInvariant(VPT, 1)) &&
+             (IsOperandPredicated(VPT, 2) || IsOperandInvariant(VPT, 2));
+    }
+
+    static bool isValid(ReachingDefAnalysis &RDA) {
       // All predication within the loop should be based on vctp. If the block
       // isn't predicated on entry, check whether the vctp is within the block
       // and that all other instructions are then predicated on it.
       for (auto &Block : Blocks) {
-        if (isEntryPredicatedOnVCTP(Block))
+        if (isEntryPredicatedOnVCTP(Block, false) ||
+            hasImplicitlyValidVPT(Block, RDA))
           continue;
 
         SmallVectorImpl<MachineInstr *> &Insts = Block.getInsts();
         for (auto *MI : Insts) {
           // Check that any internal VCTPs are 'Then' predicated.
           if (isVCTP(MI) && getVPTInstrPredicate(*MI) != ARMVCC::Then)
             return false;
           // Skip other instructions that build up the predicate.

 bool LowOverheadLoop::ValidateTailPredicate(MachineInstr *StartInsertPt) {
   assert(!VCTPs.empty() && "VCTP instruction expected but is not set");
 
   if (DisableTailPredication) {
     LLVM_DEBUG(dbgs() << "ARM Loops: tail-predication is disabled\n");
     return false;
   }
 
-  if (!VPTState::isValid())
+  if (!VPTState::isValid(RDA))
     return false;
 
   if (!ValidateLiveOuts()) {
     LLVM_DEBUG(dbgs() << "ARM Loops: Invalid live outs.\n");
     return false;
   }
 
   // For tail predication, we need to provide the number of elements, instead

llvm/test/CodeGen/Thumb2/LowOverheadLoops/remat-vctp.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -mtriple=thumbv8.1m.main -mattr=+mve.fp %s -o - | FileCheck %s
 
 define void @remat_vctp(i32* %arg, i32* %arg1, i32* %arg2, i32* %arg3, i32* %arg4, i16 zeroext %arg5) {
 ; CHECK-LABEL: remat_vctp:
 ; CHECK:       @ %bb.0: @ %bb
 ; CHECK-NEXT:    push {r4, r5, r7, lr}
 ; CHECK-NEXT:    vpush {d8, d9, d10, d11, d12, d13, d14, d15}
 ; CHECK-NEXT:    ldrd r5, r12, [sp, #80]
-; CHECK-NEXT:    cmp.w r12, #4
-; CHECK-NEXT:    mov r4, r12
 ; CHECK-NEXT:    vmvn.i32 q0, #0x80000000
-; CHECK-NEXT:    it ge
-; CHECK-NEXT:    movge r4, #4
 ; CHECK-NEXT:    vmov.i32 q1, #0x3f
-; CHECK-NEXT:    sub.w r4, r12, r4
 ; CHECK-NEXT:    vmov.i32 q2, #0x1
-; CHECK-NEXT:    add.w lr, r4, #3
-; CHECK-NEXT:    movs r4, #1
-; CHECK-NEXT:    add.w lr, r4, lr, lsr #2
-; CHECK-NEXT:    dls lr, lr
+; CHECK-NEXT:    dlstp.32 lr, r12
 ; CHECK-NEXT:  .LBB0_1: @ %bb6
 ; CHECK-NEXT:    @ =>This Inner Loop Header: Depth=1
-; CHECK-NEXT:    vctp.32 r12
-; CHECK-NEXT:    vpst
-; CHECK-NEXT:    vldrwt.u32 q4, [r1], #16
+; CHECK-NEXT:    vldrw.u32 q4, [r1], #16
 ; CHECK-NEXT:    vabs.s32 q5, q4
 ; CHECK-NEXT:    vcls.s32 q3, q5
 ; CHECK-NEXT:    vshl.u32 q5, q5, q3
 ; CHECK-NEXT:    vadd.i32 q3, q3, q2
 ; CHECK-NEXT:    vshr.u32 q6, q5, #24
 ; CHECK-NEXT:    vand q6, q6, q1
 ; CHECK-NEXT:    vldrw.u32 q7, [r5, q6, uxtw #2]
 ; CHECK-NEXT:    vqrdmulh.s32 q6, q7, q5
 ; CHECK-NEXT:    vqsub.s32 q6, q0, q6
 ; CHECK-NEXT:    vqrdmulh.s32 q6, q7, q6
 ; CHECK-NEXT:    vqshl.s32 q6, q6, #1
 ; CHECK-NEXT:    vqrdmulh.s32 q5, q6, q5
 ; CHECK-NEXT:    vqsub.s32 q5, q0, q5
 ; CHECK-NEXT:    vqrdmulh.s32 q5, q6, q5
 ; CHECK-NEXT:    vqshl.s32 q5, q5, #1
 ; CHECK-NEXT:    vpt.s32 lt, q4, zr
 ; CHECK-NEXT:    vnegt.s32 q5, q5
-; CHECK-NEXT:    vctp.32 r12
-; CHECK-NEXT:    sub.w r12, r12, #4
-; CHECK-NEXT:    vpst
-; CHECK-NEXT:    vldrwt.u32 q4, [r0], #16
+; CHECK-NEXT:    vldrw.u32 q4, [r0], #16
 ; CHECK-NEXT:    vqrdmulh.s32 q4, q4, q5
-; CHECK-NEXT:    vpstt
-; CHECK-NEXT:    vstrwt.32 q4, [r2], #16
-; CHECK-NEXT:    vstrwt.32 q3, [r3], #16
-; CHECK-NEXT:    le lr, .LBB0_1
+; CHECK-NEXT:    vstrw.32 q4, [r2], #16
+; CHECK-NEXT:    vstrw.32 q3, [r3], #16
+; CHECK-NEXT:    letp lr, .LBB0_1
 ; CHECK-NEXT:  @ %bb.2: @ %bb44
 ; CHECK-NEXT:    vpop {d8, d9, d10, d11, d12, d13, d14, d15}
 ; CHECK-NEXT:    pop {r4, r5, r7, pc}
 bb:
   %i = zext i16 %arg5 to i32
   br label %bb6
 
 bb6:                                              ; preds = %bb6, %bb

llvm/test/CodeGen/Thumb2/LowOverheadLoops/vpt-blocks.mir

body:             |
   ; CHECK:   frame-setup CFI_INSTRUCTION offset $lr, -4
   ; CHECK:   frame-setup CFI_INSTRUCTION offset $r7, -8
   ; CHECK:   tCMPi8 renamable $r1, 1, 14 /* CC::al */, $noreg, implicit-def $cpsr
   ; CHECK:   t2IT 11, 8, implicit-def $itstate
   ; CHECK:   frame-destroy tPOP_RET 11 /* CC::lt */, killed $cpsr, def $r7, def $pc, implicit killed $itstate
   ; CHECK: bb.1.vector.ph:
   ; CHECK:   successors: %bb.2(0x80000000)
   ; CHECK:   liveins: $r0, $r1, $r2
-  ; CHECK:   renamable $r3, dead $cpsr = tADDi3 renamable $r1, 3, 14 /* CC::al */, $noreg
   ; CHECK:   renamable $q0 = MVE_VMOVimmi32 0, 0, $noreg, undef renamable $q0
-  ; CHECK:   renamable $r3 = t2BICri killed renamable $r3, 3, 14 /* CC::al */, $noreg, $noreg
-  ; CHECK:   renamable $r12 = t2SUBri killed renamable $r3, 4, 14 /* CC::al */, $noreg, $noreg
-  ; CHECK:   renamable $r3, dead $cpsr = tMOVi8 1, 14 /* CC::al */, $noreg
-  ; CHECK:   renamable $lr = nuw nsw t2ADDrs killed renamable $r3, killed renamable $r12, 19, 14 /* CC::al */, $noreg, $noreg
   ; CHECK:   renamable $r3, dead $cpsr = nsw tRSB renamable $r2, 14 /* CC::al */, $noreg
-  ; CHECK:   $lr = t2DLS killed renamable $lr
+  ; CHECK:   $lr = MVE_DLSTP_32 killed renamable $r1
   ; CHECK: bb.2.vector.body:
   ; CHECK:   successors: %bb.2(0x7c000000), %bb.3(0x04000000)
-  ; CHECK:   liveins: $lr, $q0, $r0, $r1, $r2, $r3
-  ; CHECK:   renamable $vpr = MVE_VCTP32 renamable $r1, 0, $noreg
-  ; CHECK:   MVE_VPST 8, implicit $vpr
-  ; CHECK:   renamable $q1 = MVE_VLDRWU32 renamable $r0, 0, 1, killed renamable $vpr
-  ; CHECK:   MVE_VPTv4s32r 14, renamable $q1, renamable $r2, 10, implicit-def $vpr
+  ; CHECK:   liveins: $lr, $q0, $r0, $r2, $r3
+  ; CHECK:   renamable $q1 = MVE_VLDRWU32 renamable $r0, 0, 0, killed $noreg
+  ; CHECK:   MVE_VPTv4s32r 12, renamable $q1, renamable $r2, 10, implicit-def $vpr
   ; CHECK:   renamable $vpr = MVE_VCMPs32r killed renamable $q1, renamable $r3, 13, 1, killed renamable $vpr
-  ; CHECK:   renamable $vpr = MVE_VCTP32 renamable $r1, 2, killed renamable $vpr
   ; CHECK:   renamable $r0 = MVE_VSTRWU32_post renamable $q0, killed renamable $r0, 16, 2, killed renamable $vpr
-  ; CHECK:   renamable $r1, dead $cpsr = tSUBi8 killed renamable $r1, 4, 14 /* CC::al */, $noreg
-  ; CHECK:   $lr = t2LEUpdate killed renamable $lr, %bb.2
+  ; CHECK:   $lr = MVE_LETP killed renamable $lr, %bb.2
   ; CHECK: bb.3.for.cond.cleanup:
   ; CHECK:   frame-destroy tPOP_RET 14 /* CC::al */, $noreg, def $r7, def $pc
   ;
   ; Test including a else-predicated VCTP.
   ;
   bb.0.entry:
     successors: %bb.1(0x80000000)
     liveins: $r0, $r1, $r2, $r7, $lr