[Target][ARM] Replace re-uses of old VPR values with VPNOTs

[Pierre-vh]

Summary

This patch is adds another optimisation to the MVE VPT Optimisations pass introduced in the previous patch.
This optimisation replaces usages of old VPR (VCCR) values (within predicated instruction blocks) with VPNOTs in order to avoid spill/reloads.
Those VPNOTs can then be removed by the MVE VPT Block Insertion pass, resulting in clean/compact VPT blocks such as TEET, TETE, etc. instead of lots of small blocks with spill/reloads in-between.

[samparker]

I'm surprised not to see more test changes, does this really have no effect on any existing tests?

[Pierre-vh]

In D76847#1945904, @samparker wrote:

I'm surprised not to see more test changes, does this really have no effect on any existing tests?

I don't think so, I ran check-llvm-codegen and it was green (with the changes in this patch and the parent patch).

[samparker]

Ok. Well, how about a couple more tests with differently ordered instructions too then? Like inserting the unpredicated VORR inbetween the predicated ones? And maybe some larger tests that would generate blocks with multiple instructions on a predicate before performing the inversion?

[dmgreen]

In D76847#1945904, @samparker wrote:

I'm surprised not to see more test changes, does this really have no effect on any existing tests?

This kind of code can come up from intrinsics a lot, but not necessarily from the relatively simple codegen tests we have. Someone can write intrinsics knowing that VPNOT's should be folded into a single VPT block, only for llvm to come along and nicely optimize them all away, producing IR that we end up with worse codegen for. This should help us get back to better assembly.

More testing does sound good.

llvm/lib/Target/ARM/MVEVPTOptimisationsPass.cpp

167–168

addUnpredicatedMveVpredNOp

233

Should this not be replacing _all_ uses of the old condition with the value from the VPNOT?

As in, if we see input code like:
a = VCMP ..
use(a)
b = VPNOT a
..
use(b)
..
use(a)

Could it not be generally beneficial to insert a VPNOT between use of b and the second use of a? We could also probably have any amount of code between the predicated uses and it might still be beneficial, considering the costs of spills/reloads vs a single VPNOT.

[Pierre-vh]

llvm/lib/Target/ARM/MVEVPTOptimisationsPass.cpp

233

I believe it's already doing that. I'll add more tests to show it.
I can certainly do the optimisation even outside blocks of predicated instruction, I just need to remove these lines and add a few tests:

// Stop as soon as we leave the block of predicated instructions
   if (getVPTInstrPredicate(*Iter) == ARMVCC::None)
     break;

[Pierre-vh]

• Fixed issues found during review (comments marked as done)
• Improved the pass:
  • It can now move VPNOTs before their first user when needed. This currently only happens when another VCCR value is used between the VPNOT and its first user.
  • Instead of inserting VPNOTs before VPNOTs, it instead replaces the existing VPNOT with a COPY.
• Added more tests, and they now use virtual registers instead.

[Pierre-vh]

• Fixed bugs related to isKill flags in multiple places. I now correctly change the isKill flags when needed, and I added tests for that.
• Rebased the patch - Added the mve-vpt-blocks.ll test.

[Pierre-vh]

• Rebasing the patch because I inserted D77798 between this and D76709
  • D77798 also added a new test in mve-pred-not and this pass improves it as well.

[dmgreen]

Sorry for the delay.

llvm/lib/Target/ARM/MVEVPTOptimisationsPass.cpp

175

if at there -> if there

240

Does this only find the first pair in a basic block? What would happen if there are multiple (potential) vpt blocks in a larger basic block, and several of them can be optimized?

Can this be done with a linear scan through the block that attempts to find and hold VPNOT's and the original value, converting any uses of the original to the VPNOT. Or does that not work very well for some reason? Maybe using something like MRI->use_instructions would also help.

256

Can you explain the advantage of moving the VPNOT?

[Pierre-vh]

llvm/lib/Target/ARM/MVEVPTOptimisationsPass.cpp

240

What would happen if there are multiple (potential) vpt blocks in a larger basic block, and several of them can be optimized?

Unfortunately it'd only optimize the first one as it'd only pick up the first pair of VCMP/VPNOT and not the second.
I can try to rewrite the function so it handles those cases, I'll do that tomorrow.

Can this be done with a linear scan through the block that attempts to find and hold VPNOT's and the original value, converting any uses of the original to the VPNOT. Or does that not work very well for some reason?

I don't think it'd work well, but I can certainly try it and see if it works. I'll also look at use_instructions, but I'm not sure it'll help.

256

Sometimes, you can have code like this (taken from the bottom test):

%2:vccr = MVE_VCMPs32 %0:mqpr, %1:mqpr, 10, 0, $noreg
%3:vccr = MVE_VPNOT %2:vccr, 0, $noreg
%4:mqpr = MVE_VORR %0:mqpr, %1:mqpr, 1, %2:vccr, undef %4:mqpr
%5:mqpr = MVE_VORR %1:mqpr, %0:mqpr, 1, %2:vccr, undef %5:mqpr
%6:mqpr = MVE_VORR %4:mqpr, %5:mqpr, 1, %3:vccr, undef %6:mqpr

%3 is not used directly: the original VCCR value, %2 is used before it, so their lifetimes overlap.

If I didn't move the VPNOT further down in such situations, the pass would insert a double VPNOT, like this:

%2:vccr = MVE_VCMPs32 %0:mqpr, %1:mqpr, 10, 0, $noreg
%3:vccr = MVE_VPNOT %2:vccr, 0, $noreg
%foo:vccr = MVE_VPNOT %3:vccr
%4:mqpr = MVE_VORR %0:mqpr, %1:mqpr, 1, %foo:vccr, undef %4:mqpr
%5:mqpr = MVE_VORR %1:mqpr, %0:mqpr, 1, %foo:vccr, undef %5:mqpr
%bar:vccr = MVE_VPNOT %foo:vccr
%6:mqpr = MVE_VORR %4:mqpr, %5:mqpr, 1, %bar:vccr, undef %6:mqpr

But, since I now move the VPNOT further down, we get this instead, which is of course much better.

// VPNOT moved down, no more overlapping VCCR lifetimes, no double VPNOTs.
%2:vccr = MVE_VCMPs32 %0:mqpr, %1:mqpr, 10, 0, $noreg
%4:mqpr = MVE_VORR %0:mqpr, %1:mqpr, 1, %2:vccr, undef %4:mqpr
%5:mqpr = MVE_VORR %1:mqpr, %0:mqpr, 1, %2:vccr, undef %5:mqpr
%3:vccr = MVE_VPNOT %2:vccr, 0, $noreg
%6:mqpr = MVE_VORR %4:mqpr, %5:mqpr, 1, %3:vccr, undef %6:mqpr

That transformation is of course only done if a use of the orginal VCCR value is found before the first use of the VPNOT's result.

[Pierre-vh]

• Added support for optimising multiple VPT blocks in the same Basic Block, and added a test to show it
• Now VCCRValue is only set for VCMPs. (It doesn't really make a difference, but makes it clear that only VCMPs are supported by this optimisation)

[dmgreen]

llvm/lib/Target/ARM/MVEVPTOptimisationsPass.cpp

250

We not do this for predicated VCMP's?

257

findRegisterUseOperandIdx != -1

269

What makes us not do this for other opcodes? (I guess vcmp is the vast majority of cases?)

286

The second loop -> This second loop, just to be a little clearer.

302

Do we need to add the copy? We could just use LastVPNOTResult directly? Or would that be more complex?

305

Set Modified = true here too I think.

[Pierre-vh]

• Minor refactoring of the patch
• The pass is no longer limited to VCMPs for VCCRValue, it can now use any instruction that writes to VPR (e.g. VMSR)
• The pass no longer replaces VPNOT with copies - it just removes the VPNOT and replaces all of its uses.
• Other minor fixes

llvm/lib/Target/ARM/MVEVPTOptimisationsPass.cpp

250

Currently, no, to keep things simple.
I think that allowing predicated vcmps would require a bit more analysis to ensure that we don't make things worse by accident, and I'm not even sure it'd be worth it (are there any cases where it could be beneficial?)

%0:vccr = vpt ...
%1:vccr = vcmp /* predicated on %0 */
%2:vccr = vcmp /* unpredicated, opposite of %1 */

If we replace the second vcmp with vpnot %1:vccr, what happens if the first vcmp isn't executed?

269

It's just that vcmp is the vast majority of cases. There's no issue with enabling it for other instructions that write to VPR.
I've removed this restriction and added a test with vmsr.

[dmgreen]

LGTM. Thanks.

llvm/lib/Target/ARM/MVEVPTOptimisationsPass.cpp

250

It's not about "not executing", a predicated vcmp acts as a "and %0, <newcond>".

Overlapping ranges of different predicates certainly does sound more complex though. Lets leave that for other patches if we find cases where it's needed.

llvm/lib/Target/ARM/MVEVPTOptimisationsPass.cpp

 //===-- MVEVPTOptimisationsPass.cpp ---------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 /// \file This pass does a few optimisations related to MVE VPT blocks before
 /// register allocation is performed. The goal is to maximize the sizes of the
 /// blocks that will be created by the MVE VPT Block Insertion pass (which runs
-/// after register allocation). Currently, this pass replaces VCMPs with VPNOTs
-/// when possible, so the Block Insertion pass can delete them later to create
-/// larger VPT blocks.
+/// after register allocation). The first optimisation done by this pass is the
+/// replacement of VCMPs with VPNOTs when possible, so the Block Insertion pass
+/// can delete them later to create larger VPT blocks. The second optimisation
+/// replaces re-uses of old VPR values with VPNOTs when inside a block of
+/// predicated instructions. This is done to avoid spill/reloads of VPR in the
+/// middle of a block, which prevents the Block Insertion pass from creating
+/// large blocks.
+//
 //===----------------------------------------------------------------------===//
 
 #include "ARM.h"
 #include "ARMSubtarget.h"
 #include "MCTargetDesc/ARMBaseInfo.h"
 #include "Thumb2InstrInfo.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"

 
 // Creates a VPNOT before Instr.
 MachineInstrBuilder
 MVEVPTOptimisations::BuildVPNOTBefore(MachineBasicBlock &MBB,
                                       MachineInstr &Instr) {
   return BuildMI(MBB, &Instr, Instr.getDebugLoc(), TII->get(ARM::MVE_VPNOT));
 }
 
+// Transforms
+//    <Instr that uses %A (at OpIdx)>
+// Into
+//    %K = VPNOT %Target
+//    <Instr that uses %K (at OpIdx)>
+// And returns %K.
+// This optimization is done in the hopes of preventing spills/reloads of VPR.
+MachineInstr &MVEVPTOptimisations::ReplaceUsageOfRegisterByVPNOT(
+    MachineBasicBlock &MBB, MachineInstr &Instr, unsigned OpIdx,
+    Register Target) {
+  MachineOperand &InstrOperand = Instr.getOperand(OpIdx);
+
+  Register NewResult = MRI->createVirtualRegister(MRI->getRegClass(Target));
+  MachineInstrBuilder MIBuilder = BuildVPNOTBefore(MBB, Instr);
+  MIBuilder.add(MachineOperand::CreateReg(NewResult, /*isDef*/ true));
+  MIBuilder.add(MachineOperand::CreateReg(Target, /*isDef*/ false));
+  MIBuilder.addImm(0);
+  MIBuilder.addReg({});
+  InstrOperand.setReg(NewResult);
+
+  LLVM_DEBUG(dbgs() << "  Inserting VPNOT (for spill prevention): ";
+             MIBuilder.getInstr()->dump());
+
+  return *MIBuilder.getInstr();
+}
+
+// Replaces VCMPs by VPNOTs when possible, and tries to reduce spills by
+// replacing uses of old VPR values with VPNOTs inside predicated instruction
+// blocks.
 bool MVEVPTOptimisations::InsertVPNOTs(MachineBasicBlock &MBB) {
   SmallVector<MachineInstr *, 4> DeadInstructions;
 
   // The last VCMP that we have seen and that couldn't be replaced.
   // This is reset when an instruction that writes to VCCR/VPR is found, or when
   // a VCMP is replaced with a VPNOT.
   // We'll only replace VCMPs with VPNOTs when this is not null, and when the
   // current VCMP is the opposite of PrevVCMP.
for (MachineInstr &Instr : MBB.instrs()) {
     MachineInstrBuilder MIBuilder = BuildVPNOTBefore(MBB, Instr);
     MIBuilder.add(Instr.getOperand(0));
     MIBuilder.addReg(PrevVCMPResultReg);
     MIBuilder.add(Instr.getOperand(4));
     MIBuilder.add(Instr.getOperand(5));
     LLVM_DEBUG(dbgs() << "  Inserting VPNOT (to replace VCMP): ";
                MIBuilder.getInstr()->dump());
 
+    // While inside the block of predicated instructions, replace usages of old
+    // VCCR/VPR values by VPNOTs. That way, we avoid overlapping lifetimes
+    // of different VPR values (which always result in spill/reloads).
+    // Those VPNOTs can then be removed by the MVE VPT Block Insertion pass,
+    // and we should end up with clean blocks like "TETE", "TEET", etc.
+
+    Register ValueReg = PrevVCMPResultReg;
+    Register InverseValueReg = Instr.getOperand(0).getReg();
+    Register VPNOTOperand = InverseValueReg;
+
+    // On each iteration, try to replace an usage of "ValueReg" with a VPNOT
+    // on "VPNOTOperand".
+    for (MachineBasicBlock::instr_iterator Iter = ++Instr.getIterator();
+         Iter != MBB.end(); ++Iter) {
+      // Stop as soon as we leave the block of predicated instructions
+      if (getVPTInstrPredicate(*Iter) == ARMVCC::None)
+        break;
+
+      // Keep going until we find an instruction that uses ValueReg.
+      int Idx = Iter->findRegisterUseOperandIdx(ValueReg.id());
+      if (Idx == -1)
+        continue;
+
+      // Replace the usage of said register by a VPNOT on VPNOTOperand
+      MachineInstr &VPNOT =
+          ReplaceUsageOfRegisterByVPNOT(MBB, *Iter, Idx, VPNOTOperand);
+
+      // Continue: The result of the VPNOT we just inserted becomes the new
+      // VPNOTOperand, and ValueReg/InverseValueReg are swapped.
+      VPNOTOperand = VPNOT.getOperand(0).getReg();
+      std::swap(ValueReg, InverseValueReg);
+    }
+
     // Finally, mark the old VCMP for removal and reset PrevVCMP.
     DeadInstructions.push_back(&Instr);
     PrevVCMP = nullptr;
   }
 
   for (MachineInstr *DeadInstruction : DeadInstructions)
     DeadInstruction->removeFromParent();
 
   return !DeadInstructions.empty();
 }
 
 bool MVEVPTOptimisations::runOnMachineFunction(MachineFunction &Fn) {
   const ARMSubtarget &STI =
       static_cast<const ARMSubtarget &>(Fn.getSubtarget());
 
   if (!STI.isThumb2() || !STI.hasMVEIntegerOps())
     return false;
 
   TII = static_cast<const Thumb2InstrInfo *>(STI.getInstrInfo());
   MRI = &Fn.getRegInfo();
 
   LLVM_DEBUG(dbgs() << "********** ARM MVE VPT Optimisations **********\n"
                     << "********** Function: " << Fn.getName() << '\n');
 
   bool Modified = false;
   for (MachineBasicBlock &MBB : Fn)
     Modified |= InsertVPNOTs(MBB);
 
   LLVM_DEBUG(dbgs() << "**************************************\n");
   return Modified;
 }
 
 /// createMVEVPTOptimisationsPass
 FunctionPass *llvm::createMVEVPTOptimisationsPass() {
   return new MVEVPTOptimisations();
 }
 No newline at end of file

llvm/test/CodeGen/Thumb2/mve-vpt-optimisations.mir

entry:
     ret <4 x float> %inactive1
   }
 
   define arm_aapcs_vfpcc <4 x float> @vpr_or_vccr_write_between_vcmps(<4 x float> %inactive1) #0 {
   entry:
     ret <4 x float> %inactive1
   }
 
+  define arm_aapcs_vfpcc <4 x float> @spill_prevention(<4 x float> %inactive1) #0 {
+  entry:
+    ret <4 x float> %inactive1
+  }
+
   attributes #0 = { "target-features"="+armv8.1-m.main,+hwdiv,+mve.fp,+ras,+thumb-mode" }
 ...
 ---
 name:            vcmp_with_opposite_cond
 alignment:       4
 liveins:
   - { reg: '$q0', virtual-reg: '' }
   - { reg: '$q1', virtual-reg: '' }
bb.0:
     renamable $vpr = MVE_VPNOT killed renamable $vpr, 0, $noreg
     renamable $vpr = MVE_VCMPs32 renamable $q1, renamable $q0, 13, 0, $noreg
   bb.1:
     renamable $vpr = MVE_VCMPs32 renamable $q0, renamable $q1, 12, 0, $noreg
     %0:vccr = MVE_VPNOT killed renamable $vpr, 0, $noreg
     renamable $vpr = MVE_VCMPs32 renamable $q1, renamable $q0, 10, 0, $noreg
     tBX_RET 14, $noreg, implicit $q0
 ...
+---
+name:            spill_prevention
+alignment:       4
+liveins:
+  - { reg: '$q0', virtual-reg: '' }
+  - { reg: '$q1', virtual-reg: '' }
+body:             |
+  bb.0:
+    liveins: $q0, $q1
+    ; CHECK-LABEL: name: spill_prevention
+    ; CHECK: [[MVE_VCMPs32_:%[0-9]+]]:vccr = MVE_VCMPs32 renamable $q0, renamable $q1, 10, 0, $noreg
+    ; CHECK: [[MVE_VPNOT:%[0-9]+]]:vccr = MVE_VPNOT [[MVE_VCMPs32_]], 0, $noreg
+    ; CHECK: [[MVE_VORR:%[0-9]+]]:mqpr = MVE_VORR renamable $q1, renamable $q1, 1, [[MVE_VPNOT]], undef [[MVE_VORR]]
+    ; CHECK: [[MVE_VPNOT1:%[0-9]+]]:vccr = MVE_VPNOT [[MVE_VPNOT]], 0, $noreg
+    ; CHECK: [[MVE_VORR1:%[0-9]+]]:mqpr = MVE_VORR [[MVE_VORR]], [[MVE_VORR]], 1, [[MVE_VPNOT1]], undef [[MVE_VORR1]]
+    ; CHECK: [[MVE_VPNOT2:%[0-9]+]]:vccr = MVE_VPNOT [[MVE_VPNOT1]], 0, $noreg
+    ; CHECK: [[MVE_VORR2:%[0-9]+]]:mqpr = MVE_VORR [[MVE_VORR1]], [[MVE_VORR1]], 1, [[MVE_VPNOT2]], undef [[MVE_VORR2]]
+    ; CHECK: tBX_RET 14 /* CC::al */, $noreg, implicit $q0
+    %0:vccr = MVE_VCMPs32 renamable $q0, renamable $q1, 10, 0, $noreg
+    %1:vccr = MVE_VCMPs32 renamable $q1, renamable $q0, 12, 0, $noreg
+    %2:mqpr = MVE_VORR renamable $q1, renamable $q1, 1, %1, undef %2
+    %3:mqpr = MVE_VORR %2, %2, 1, %0:vccr, undef %3:mqpr
+    %4:mqpr = MVE_VORR %3, %3, 1, %1:vccr, undef %4:mqpr
+    tBX_RET 14, $noreg, implicit $q0
+...