[ARM][LowOverheadLoops] Add checks for narrowing

[samparker]

Summary

Modify ValidateLiveOuts to track 'FalseZeros' more precisely, including checks on specific operations that can generate non-zeros from zero values, e.g VMVN. We can then check that any instructions that retain some information in their output register (all narrowing instructions) that they only use and def registers that always have zeros in their falsely predicated bytes, whether or not tail predication happens.
Most of the logic remains the same, just the names of the data structures and helpers have been renamed to reflect the change in logic. The key change, apart from the opcode checkers, is that the FalseZeros set now strictly contains only instructions which will always generate zeros, and not instructions that could also have their false bytes masked away later.

[SjoerdMeijer]

llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp

521

This is becoming a very tricky pass (if it wasn't already that), for a bunch of different reason: the analysis, the transformations, etc. To keep things readable, I am now going to nitpick on comments. I believe there is one school of thought that code should be self-documenting, and comments will always be out of date or misleading, which I think I can mostly agree with. But here in this case, this function, that checks certain opcodes and returning true/false to a function named canGenerateNonZeros doesn't tell me much. So my request is here is if you can define what exactly canGenerateNonZeros mean, and why these opcodes.

538

Same request here: what is retainsPreviousValue, and why these opcodes?

583

Same here

588

Probably this comment describes the function's purpose, so can be moved up.

[samparker]

llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp

521

Fair! Here, any MVE instruction that could generate a non-zero result given nothing but zero'd registers should be listed. This allows us to track zeros in means zeros out.

538

All these instructions operate upon half a lane of the source register, writing to the destination, but they also leave the other half of the destination register untouched. The reference manual uses this sentence: 'The other half of the destination vector element retains its previous value'.

[SjoerdMeijer]

llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp

521

Thanks, makes sense. If you can later add this as comments, that would be much appreciated. I am now going to do a second pass over this patch, let things sink in, and continue the review.

[SjoerdMeijer]

I am now up to date with this, and don't have any questions about the logic, that looks good.
I would like to go over it once more when (some of) the nits have been addressed as I would like to get an overview how things read and look as this introduces quite a few new things and concepts.

llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp

538

Thanks for pointing this out.

Just a nit/suggestion for the function name then:
retainsPreviousValue -> laneRetainsPreviousValue

A few questions about the list below. Is this list meant to be complete? From looking at the ArmARM a bit more for this behaviour, it looks like there are more, the first search result e.g. showed VQMOVN. Are we for example not interested in this one? Also curious if it would be worth describing this property in a different way, or if this switch will do.

583

nit: perhaps something along the lines of: alwaysZero -> laneAlwaysZero

617

nit: bytes -> lanes?

625

nit: KnownFalseZeros -> Predicated?

629

nit: perhaps something with "lane" in it:

• AlwaysFalseLaneZero, or
• FalseLaneZero, or
• FalsePredLaneZero

[samparker]

llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp

538

It is supposed to be complete, so thanks! Which also reminds me that there's no tests for any movn either!

[samparker]

• Added/moved some comments.
• Renamed variables/functions.
• Added/removed tests.

[SjoerdMeijer]

Cheers, looks good to me.

llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp

547

nit: retainsPreviousHalf -> retainsPreviousHalfElement

550

nit, just:

return Flags & ARMII::RetainsPreviousHalfElement;

llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp

 
 using namespace llvm;
 
 #define DEBUG_TYPE "arm-low-overhead-loops"
 #define ARM_LOW_OVERHEAD_LOOPS_NAME "ARM Low Overhead Loops pass"
 
 namespace {
 
+  using InstSet = SmallPtrSetImpl<MachineInstr *>;
+
   class PostOrderLoopTraversal {
     MachineLoop &ML;
     MachineLoopInfo &MLI;
     SmallPtrSet<MachineBasicBlock*, 4> Visited;
     SmallVector<MachineBasicBlock*, 4> Order;
 
   public:
     PostOrderLoopTraversal(MachineLoop &ML, MachineLoopInfo &MLI)

 static bool isVectorPredicated(MachineInstr *MI) {
   int PIdx = llvm::findFirstVPTPredOperandIdx(*MI);
   return PIdx != -1 && MI->getOperand(PIdx + 1).getReg() == ARM::VPR;
 }
 
 static bool isRegInClass(const MachineOperand &MO,
                          const TargetRegisterClass *Class) {
   return MO.isReg() && MO.getReg() && Class->contains(MO.getReg());
 }
 
+// Can this instruction generate a non-zero result when given only zeroed
+// operands? This allows us to know that, given operands with false bytes
+// zeroed by masked loads, that the result will also contain zeros in those
+// bytes.
+static bool canGenerateNonZeros(const MachineInstr &MI) {
+  switch (MI.getOpcode()) {
+  default:
+    break;
+  // FIXME: FP minus 0?
+  //case ARM::MVE_VNEGf16:
+  //case ARM::MVE_VNEGf32:
+  case ARM::MVE_VMVN:
+  case ARM::MVE_VORN:
+  case ARM::MVE_VCLZs8:
+  case ARM::MVE_VCLZs16:
+  case ARM::MVE_VCLZs32:
+    return true;
+  }
+  return false;
+}
+
+// MVE 'narrowing' operate on half a lane, reading from half and writing
+// to half, which are referred to has the top and bottom half. The other
+// half retains its previous value.
+static bool retainsPreviousHalfElement(const MachineInstr &MI) {
+  const MCInstrDesc &MCID = MI.getDesc();
+  uint64_t Flags = MCID.TSFlags;
+  return (Flags & ARMII::RetainsPreviousHalfElement) != 0;
+}
+
+// Look at its register uses to see if it only can only receive zeros
+// into its false lanes which would then produce zeros. Also check that
+// the output register is also defined by an FalseLaneZeros instruction
+// so that if tail-predication happens, the lanes that aren't updated will
+// still be zeros.
+static bool producesFalseLaneZeros(MachineInstr &MI,
+                                   const TargetRegisterClass *QPRs,
+                                   const ReachingDefAnalysis &RDA,
+                                   InstSet &FalseLaneZeros) {
+  if (canGenerateNonZeros(MI))
+    return false;
+  for (auto &MO : MI.operands()) {
+    if (!MO.isReg() || !MO.getReg())
+      continue;
+    if (auto *OpDef = RDA.getMIOperand(&MI, MO))
+      if (FalseLaneZeros.count(OpDef))
+       continue;
+    return false;
+  }
+  LLVM_DEBUG(dbgs() << "ARM Loops: Always False Zeros: " << MI);
+  return true;
+}
+
 bool LowOverheadLoop::ValidateLiveOuts() const {
   // We want to find out if the tail-predicated version of this loop will
   // produce the same values as the loop in its original form. For this to
   // be true, the newly inserted implicit predication must not change the
   // the (observable) results.
   // We're doing this because many instructions in the loop will not be
   // predicated and so the conversion from VPT predication to tail-predication
   // can result in different values being produced; due to the tail-predication
   // preventing many instructions from updating their falsely predicated
   // lanes. This analysis assumes that all the instructions perform lane-wise
   // operations and don't perform any exchanges.
   // A masked load, whether through VPT or tail predication, will write zeros
   // to any of the falsely predicated bytes. So, from the loads, we know that
   // the false lanes are zeroed and here we're trying to track that those false
   // lanes remain zero, or where they change, the differences are masked away
   // by their user(s).
   // All MVE loads and stores have to be predicated, so we know that any load
   // operands, or stored results are equivalent already. Other explicitly
   // predicated instructions will perform the same operation in the original
   // loop and the tail-predicated form too. Because of this, we can insert
-  // loads, stores and other predicated instructions into our KnownFalseZeros
+  // loads, stores and other predicated instructions into our Predicated
   // set and build from there.
   const TargetRegisterClass *QPRs = TRI.getRegClass(ARM::MQPRRegClassID);
-  SetVector<MachineInstr *> UnknownFalseLanes;
-  SmallPtrSet<MachineInstr *, 4> KnownFalseZeros;
+  SetVector<MachineInstr *> Unknown;
+  SmallPtrSet<MachineInstr *, 4> FalseLaneZeros;
+  SmallPtrSet<MachineInstr *, 4> Predicated;
   MachineBasicBlock *MBB = ML.getHeader();
+
   for (auto &MI : *MBB) {
     const MCInstrDesc &MCID = MI.getDesc();
     uint64_t Flags = MCID.TSFlags;
     if ((Flags & ARMII::DomainMask) != ARMII::DomainMVE)
       continue;
 
     if (isVectorPredicated(&MI)) {
-      KnownFalseZeros.insert(&MI);
+      if (MI.mayLoad())
+        FalseLaneZeros.insert(&MI);
+      Predicated.insert(&MI);
       continue;
     }
 
     if (MI.getNumDefs() == 0)
       continue;
 
-    // Only evaluate instructions which produce a single value.
-    assert((MI.getNumDefs() == 1 && MI.defs().begin()->isReg()) &&
-           "Expected no more than one register def");
-
-    Register DefReg = MI.defs().begin()->getReg();
-    for (auto &MO : MI.operands()) {
-      if (!isRegInClass(MO, QPRs) || !MO.isUse() || MO.getReg() != DefReg)
-        continue;
-
-      // If this instruction overwrites one of its operands, and that register
-      // has known lanes, then this instruction also has known predicated false
-      // lanes.
-      if (auto *OpDef = RDA.getMIOperand(&MI, MO)) {
-        if (KnownFalseZeros.count(OpDef)) {
-          KnownFalseZeros.insert(&MI);
-          break;
-        }
-      }
-    }
-    if (!KnownFalseZeros.count(&MI))
-      UnknownFalseLanes.insert(&MI);
+    if (producesFalseLaneZeros(MI, QPRs, RDA, FalseLaneZeros))
+      FalseLaneZeros.insert(&MI);
+    else if (retainsPreviousHalfElement(MI))
+      return false;
+    else
+      Unknown.insert(&MI);
   }
 
-  auto HasKnownUsers = [this](MachineInstr *MI, const MachineOperand &MO,
-                              SmallPtrSetImpl<MachineInstr *> &Knowns) {
+  auto HasPredicatedUsers = [this](MachineInstr *MI, const MachineOperand &MO,
+                              SmallPtrSetImpl<MachineInstr *> &Predicated) {
     SmallPtrSet<MachineInstr *, 2> Uses;
     RDA.getGlobalUses(MI, MO.getReg(), Uses);
     for (auto *Use : Uses) {
-      if (Use != MI && !Knowns.count(Use))
+      if (Use != MI && !Predicated.count(Use))
         return false;
     }
     return true;
   };
 
-  // Now for all the unknown values, see if they're only consumed by known
-  // instructions. Visit in reverse so that we can start at the values being
+  // Visit the unknowns in reverse so that we can start at the values being
   // stored and then we can work towards the leaves, hopefully adding more
-  // instructions to KnownFalseZeros.
-  for (auto *MI : reverse(UnknownFalseLanes)) {
+  // instructions to Predicated.
+  for (auto *MI : reverse(Unknown)) {
     for (auto &MO : MI->operands()) {
       if (!isRegInClass(MO, QPRs) || !MO.isDef())
         continue;
-      if (!HasKnownUsers(MI, MO, KnownFalseZeros)) {
+      if (!HasPredicatedUsers(MI, MO, Predicated)) {
         LLVM_DEBUG(dbgs() << "ARM Loops: Found an unknown def of : "
                           << TRI.getRegAsmName(MO.getReg()) << " at " << *MI);
         return false;
       }
     }
     // Any unknown false lanes have been masked away by the user(s).
-    KnownFalseZeros.insert(MI);
+    Predicated.insert(MI);
   }
 
   // Collect Q-regs that are live in the exit blocks. We don't collect scalars
   // because they won't be affected by lane predication.
   SmallSet<Register, 2> LiveOuts;
   SmallVector<MachineBasicBlock *, 2> ExitBlocks;
   ML.getExitBlocks(ExitBlocks);
   for (auto *MBB : ExitBlocks)