[ARM][ReachingDefs] RDA in LoLoops

[samparker]

Summary

Add several new methods to ReachingDefAnalysis:

• getReachingMIDef, instead of returning an integer, return the MachineInstr that produces the def.
• getInstFromId, return a MachineInstr for which the given integer corresponds to.
• hasSameReachingDef, return whether two MachineInstr use the same def of a register.
• isRegUsedAfter, return whether a register is used after a given MachineInstr.

These methods have been used in ARMLowOverhead to replace searching for uses/defs.

[dmgreen]

llvm/lib/CodeGen/ReachingDefAnalysis.cpp

139

Can you explain this? Is it valid to just set this property?

[samparker]

llvm/lib/CodeGen/ReachingDefAnalysis.cpp

139

This pass doesn't change the code so this should be fine. But now I'm thinking that this pass also should require that liveness information is correct on entry.

[arsenm]

llvm/lib/CodeGen/ReachingDefAnalysis.cpp

139

Yes, this should be setting this in getRequiredProperties

llvm/lib/Target/ARM/ARMInstrThumb2.td

5235 ↗

(On Diff #228444)

This is a separate change

[dmgreen]

llvm/lib/CodeGen/ReachingDefAnalysis.cpp

139

I thought this was a property, like IsSSA. I'm not very sure either way, but it might not be valid to set that the property holds without checking that it does.

Do you know which pass is causing the property to be removed? Can we fix that to keep it valid?

[samparker]

• Added liveness tracking as a requirement to RDA, and removed the setting of the property.
• Removed the CPSR stuff from low-overhead loops, as well as the related test changes.
• Rewrote the neon test because the liveness information needed to be encoded.

[dmgreen]

llvm/lib/CodeGen/ReachingDefAnalysis.cpp

208

You can drop the brackets

llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp

131

Nit: This needs a clang format.

191–192

"LR can be defined"

218–219

Something like an int is usually not made const, unless it's a reference. But that's just a style preference.

223

Is this one correct? (start as opposed to back)

225

This is getInstId(LRDef)?

451

Does this change need the Defs = [CPSR] for t2LoopDec change? Are there some tests for these cases that didn't change?

llvm/test/CodeGen/Thumb2/ifcvt-neon-deprecated.mir

46

Is this part of the test still important?

[samparker]

llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp

223

I think I'll make some helpers for these, with more comments, because it's confusing me looking at it again!

225

good point.

451

It didn't need it in the end as this logic allows us to query for a CPSR def inbetween LoopDec (MI) and LoopEnd (back). Again, I'll create a helper which allows us to clearly whether we have a def of something inbetween A and B.

[dmgreen]

llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp

451

And we don't need to check for uses any more?

[samparker]

llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp

451

Argh! Indeed we do. And that means there's a hole in my testing.

[samparker]

Taken hasSameReachingDef from D70240 and added isRegUsedAfter to RDA. This allows a great simplication for finding an insertion point and allows us to check for CPSR use/def within the loop too. I've added a couple of extra tests for the CPSR logic.

[samparker]

Rebased.

[SjoerdMeijer]

llvm/lib/CodeGen/ReachingDefAnalysis.cpp

219

I am a bit confused, this seems to be done in D70240?

[dmgreen]

I think this all looks OK. Unless Sjoerd/others have further comments. I don't feel like an expert on RDA..

In any case, perhaps leave open for a few days for anyone else to make comments.

llvm/include/llvm/CodeGen/ReachingDefAnalysis.h

128

Lost a / out of ///

llvm/lib/CodeGen/ReachingDefAnalysis.cpp

233

Hmm. You don't know if this is the _same_ PhysReg, right? It could be a different def of the same register?

That would still fit in with how RDA works, but is kind of mixing together liveness and reachability.

Yeah OK. I think this expands reaching defs in a sensible direction.

[samparker]

llvm/lib/CodeGen/ReachingDefAnalysis.cpp

219

Yes, I moved it over and will rebase once that patch is in.

233

True, this doesn't say whether a value is used, just whether a register is live at some point afterwards.

llvm/include/llvm/CodeGen/ReachingDefAnalysis.h

void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesAll();
     MachineFunctionPass::getAnalysisUsage(AU);
   }
 
   bool runOnMachineFunction(MachineFunction &MF) override;
 
   MachineFunctionProperties getRequiredProperties() const override {
     return MachineFunctionProperties().set(
-        MachineFunctionProperties::Property::NoVRegs);
+        MachineFunctionProperties::Property::NoVRegs).set(
+          MachineFunctionProperties::Property::TracksLiveness);
   }
 
   /// Provides the instruction id of the closest reaching def instruction of
   /// PhysReg that reaches MI, relative to the begining of MI's basic block.
   int getReachingDef(MachineInstr *MI, int PhysReg);
 
+  /// Provides the instruction of the closest reaching def instruction of
+  /// PhysReg that reaches MI, relative to the begining of MI's basic block.
+  MachineInstr *getReachingMIDef(MachineInstr *MI, int PhysReg);
+
+  /// Provides the MI, from the given block, corresponding to the Id or a
+  /// nullptr if the id does not refer to the block.
+  MachineInstr *getInstFromId(MachineBasicBlock *MBB, int InstId);
+
+  /// Return whether A and B use the same def of PhysReg.
+  bool hasSameReachingDef(MachineInstr *A, MachineInstr *B, int PhysReg);
+
+  /// Return whether the given register is used after MI, whether it's a local
+  /// use or a live out.
+  bool isRegUsedAfter(MachineInstr *MI, int PhysReg);
+
   /// Provides the clearance - the number of instructions since the closest
   /// reaching def instuction of PhysReg that reaches MI.
   int getClearance(MachineInstr *MI, MCPhysReg PhysReg);
 
 private:
   /// Set up LiveRegs by merging predecessor live-out values.
   void enterBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
 
   /// Update live-out values.
   void leaveBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
 
   /// Process he given basic block.
   void processBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
 
   /// Update def-ages for registers defined by MI.
   /// Also break dependencies on partial defs and undef uses.
   void processDefs(MachineInstr *);
 };
 
 } // namespace llvm
 
 #endif // LLVM_CODEGEN_REACHINGDEFSANALYSIS_H

llvm/lib/CodeGen/ReachingDefAnalysis.cpp

 //===---- ReachingDefAnalysis.cpp - Reaching Def Analysis ---*- C++ -*-----===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/CodeGen/LivePhysRegs.h"
 #include "llvm/CodeGen/ReachingDefAnalysis.h"
 #include "llvm/CodeGen/TargetRegisterInfo.h"
 #include "llvm/CodeGen/TargetSubtargetInfo.h"
 #include "llvm/Support/Debug.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "reaching-deps-analysis"
void ReachingDefAnalysis::processBasicBlock(
   }
   leaveBasicBlock(TraversedMBB);
 }
 
 bool ReachingDefAnalysis::runOnMachineFunction(MachineFunction &mf) {
   if (skipFunction(mf.getFunction()))
     return false;
   MF = &mf;
   TRI = MF->getSubtarget().getRegisterInfo();
 
   LiveRegs.clear();
   NumRegUnits = TRI->getNumRegUnits();
 
   MBBReachingDefs.resize(mf.getNumBlockIDs());
 
   LLVM_DEBUG(dbgs() << "********** REACHING DEFINITION ANALYSIS **********\n");
 
for (int Def : MBBReachingDefs[MBBNumber][*Unit]) {
         break;
       DefRes = Def;
     }
     LatestDef = std::max(LatestDef, DefRes);
   }
   return LatestDef;
 }
 
+MachineInstr* ReachingDefAnalysis::getReachingMIDef(MachineInstr *MI, int PhysReg) {
+  return getInstFromId(MI->getParent(), getReachingDef(MI, PhysReg));
+}
+
+MachineInstr *ReachingDefAnalysis::getInstFromId(MachineBasicBlock *MBB,
+                                                 int InstId) {
+  assert(MBB->getNumber() < MBBReachingDefs.size() &&
+         "Unexpected basic block number.");
+  assert(InstId < static_cast<int>(MBB->size()) &&
+         "Unexpected instruction id.");
+
+  if (InstId < 0)
+    return nullptr;
+
+  for (auto &MI : *MBB) {
+    if (InstIds.count(&MI) && InstIds[&MI] == InstId)
+      return &MI;
+  }
+  return nullptr;
+}
+
 int ReachingDefAnalysis::getClearance(MachineInstr *MI, MCPhysReg PhysReg) {
   assert(InstIds.count(MI) && "Unexpected machine instuction.");
   return InstIds[MI] - getReachingDef(MI, PhysReg);
 }
+
+bool ReachingDefAnalysis::hasSameReachingDef(MachineInstr *A, MachineInstr *B,
+                                             int PhysReg) {
+  MachineBasicBlock *ParentA = A->getParent();
+  MachineBasicBlock *ParentB = B->getParent();
+  if (ParentA != ParentB)
+    return false;
+
+  return getReachingDef(A, PhysReg) == getReachingDef(B, PhysReg);
+}
+
+bool ReachingDefAnalysis::isRegUsedAfter(MachineInstr *MI, int PhysReg) {
+  MachineBasicBlock *MBB = MI->getParent();
+  LivePhysRegs LiveRegs(*TRI);
+  LiveRegs.addLiveOuts(*MBB);
+
+  // Yes if the register is live out of the basic block.
+  if (LiveRegs.contains(PhysReg))
+    return true;
+
+  // Walk backwards through the block to see if the register is live at some
+  // point.
+  for (auto Last = MBB->rbegin(), End = MBB->rend(); Last != End; ++Last) {
+    LiveRegs.stepBackward(*Last);
+    if (LiveRegs.contains(PhysReg))
+      return InstIds[&*Last] > InstIds[MI];
+  }
+  return false;
+}
+

llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp

 #include "ARM.h"
 #include "ARMBaseInstrInfo.h"
 #include "ARMBaseRegisterInfo.h"
 #include "ARMBasicBlockInfo.h"
 #include "ARMSubtarget.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/CodeGen/ReachingDefAnalysis.h"
 #include "llvm/MC/MCInstrDesc.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "arm-low-overhead-loops"
 #define ARM_LOW_OVERHEAD_LOOPS_NAME "ARM Low Overhead Loops pass"
 
 namespace {
bool IsTailPredicationLegal() const {
       // block for tail predication.
       return !Revert && FoundAllComponents() && FoundOneVCTP &&
              !CannotTailPredicate && ML->getNumBlocks() == 1;
     }
 
     // Is it safe to define LR with DLS/WLS?
     // LR can be defined if it is the operand to start, because it's the same
     // value, or if it's going to be equivalent to the operand to Start.
-    MachineInstr *IsSafeToDefineLR();
+    MachineInstr *IsSafeToDefineLR(ReachingDefAnalysis *RDA);
 
-    // Check the branch targets are within range and we satisfy our restructi
-    void CheckLegality(ARMBasicBlockUtils *BBUtils);
+    // Check the branch targets are within range and we satisfy our
+    // restrictions.
+    void CheckLegality(ARMBasicBlockUtils *BBUtils, ReachingDefAnalysis *RDA);
 
     bool FoundAllComponents() const {
       return Start && Dec && End;
     }
 
     void dump() const {
       if (Start) dbgs() << "ARM Loops: Found Loop Start: " << *Start;
       if (Dec) dbgs() << "ARM Loops: Found Loop Dec: " << *Dec;
       if (End) dbgs() << "ARM Loops: Found Loop End: " << *End;
       if (VCTP) dbgs() << "ARM Loops: Found VCTP: " << *VCTP;
       if (!FoundAllComponents())
         dbgs() << "ARM Loops: Not a low-overhead loop.\n";
       else if (!(Start && Dec && End))
         dbgs() << "ARM Loops: Failed to find all loop components.\n";
     }
   };
 
   class ARMLowOverheadLoops : public MachineFunctionPass {
     MachineFunction           *MF = nullptr;
+    ReachingDefAnalysis       *RDA = nullptr;
     const ARMBaseInstrInfo    *TII = nullptr;
     MachineRegisterInfo       *MRI = nullptr;
     std::unique_ptr<ARMBasicBlockUtils> BBUtils = nullptr;
 
   public:
     static char ID;
 
     ARMLowOverheadLoops() : MachineFunctionPass(ID) { }
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.setPreservesCFG();
       AU.addRequired<MachineLoopInfo>();
+      AU.addRequired<ReachingDefAnalysis>();
       MachineFunctionPass::getAnalysisUsage(AU);
     }
 
     bool runOnMachineFunction(MachineFunction &MF) override;
 
     MachineFunctionProperties getRequiredProperties() const override {
       return MachineFunctionProperties().set(
-          MachineFunctionProperties::Property::NoVRegs);
+          MachineFunctionProperties::Property::NoVRegs).set(
+          MachineFunctionProperties::Property::TracksLiveness);
     }
 
     StringRef getPassName() const override {
       return ARM_LOW_OVERHEAD_LOOPS_NAME;
     }
 
   private:
     bool ProcessLoop(MachineLoop *ML);

 
 INITIALIZE_PASS(ARMLowOverheadLoops, DEBUG_TYPE, ARM_LOW_OVERHEAD_LOOPS_NAME,
                 false, false)
 
 static bool IsLoopStart(MachineInstr &MI) {
   return MI.getOpcode() == ARM::t2DoLoopStart ||
          MI.getOpcode() == ARM::t2WhileLoopStart;
 }
 
-template<typename T>
-static MachineInstr* SearchForDef(MachineInstr *Begin, T End, unsigned Reg) {
-  for(auto &MI : make_range(T(Begin), End)) {
-    for (auto &MO : MI.operands()) {
-      if (!MO.isReg() || !MO.isDef() || MO.getReg() != Reg)
-        continue;
-      return &MI;
-    }
-  }
-  return nullptr;
-}
-
-static MachineInstr* SearchForUse(MachineInstr *Begin,
-                                  MachineBasicBlock::iterator End,
-                                  unsigned Reg) {
-  for(auto &MI : make_range(MachineBasicBlock::iterator(Begin), End)) {
-    for (auto &MO : MI.operands()) {
-      if (!MO.isReg() || !MO.isUse() || MO.getReg() != Reg)
-        continue;
-      return &MI;
-    }
-  }
-  return nullptr;
-}
-
 static bool IsVCTP(MachineInstr *MI) {
   switch (MI->getOpcode()) {
   default:
     break;
   case ARM::MVE_VCTP8:
   case ARM::MVE_VCTP16:
   case ARM::MVE_VCTP32:
   case ARM::MVE_VCTP64:
     return true;
   }
   return false;
 }
 
-MachineInstr *LowOverheadLoop::IsSafeToDefineLR() {
+MachineInstr *LowOverheadLoop::IsSafeToDefineLR(ReachingDefAnalysis *RDA) {
+  // We can define LR because LR already contains the same value.
+  if (Start->getOperand(0).getReg() == ARM::LR)
+    return Start;
 
-  auto IsMoveLR = [](MachineInstr *MI, unsigned Reg) {
+  unsigned CountReg = Start->getOperand(0).getReg();
+  auto IsMoveLR = [&CountReg](MachineInstr *MI) {
     return MI->getOpcode() == ARM::tMOVr &&
            MI->getOperand(0).getReg() == ARM::LR &&
-           MI->getOperand(1).getReg() == Reg &&
+           MI->getOperand(1).getReg() == CountReg &&
            MI->getOperand(2).getImm() == ARMCC::AL;
    };
 
   MachineBasicBlock *MBB = Start->getParent();
-  unsigned CountReg = Start->getOperand(0).getReg();
-  // Walk forward and backward in the block to find the closest instructions
-  // that define LR. Then also filter them out if they're not a mov lr.
-  MachineInstr *PredLRDef = SearchForDef(Start, MBB->rend(), ARM::LR);
-  if (PredLRDef && !IsMoveLR(PredLRDef, CountReg))
-    PredLRDef = nullptr;
-
-  MachineInstr *SuccLRDef = SearchForDef(Start, MBB->end(), ARM::LR);
-  if (SuccLRDef && !IsMoveLR(SuccLRDef, CountReg))
-    SuccLRDef = nullptr;
-
-  // We've either found one, two or none mov lr instructions... Now figure out
-  // if they are performing the equilvant mov that the Start instruction will.
-  // Do this by scanning forward and backward to see if there's a def of the
-  // register holding the count value. If we find a suitable def, return it as
-  // the insert point. Later, if InsertPt != Start, then we can remove the
-  // redundant instruction.
-  if (SuccLRDef) {
-    MachineBasicBlock::iterator End(SuccLRDef);
-    if (!SearchForDef(Start, End, CountReg)) {
-      return SuccLRDef;
-    } else
-      SuccLRDef = nullptr;
-  }
-  if (PredLRDef) {
-    MachineBasicBlock::reverse_iterator End(PredLRDef);
-    if (!SearchForDef(Start, End, CountReg)) {
-      return PredLRDef;
-    } else
-      PredLRDef = nullptr;
-  }
 
-  // We can define LR because LR already contains the same value.
-  if (Start->getOperand(0).getReg() == ARM::LR)
-    return Start;
+  // Find an insertion point:
+  // - Is there a (mov lr, Count) before Start? If so, and nothing else writes
+  //   to Count before Start, we can insert at that mov.
+  // - Is there a (mov lr, Count) after Start? If so, and nothing else writes
+  //   to Count after Start, we can insert at that mov.
+  if (auto *LRDef = RDA->getReachingMIDef(&MBB->back(), ARM::LR)) {
+    if (IsMoveLR(LRDef) && RDA->hasSameReachingDef(Start, LRDef, CountReg))
+      return LRDef;
+  }
 
   // We've found no suitable LR def and Start doesn't use LR directly. Can we
-  // just define LR anyway? 
-  const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
-  LivePhysRegs LiveRegs(*TRI);
-  LiveRegs.addLiveOuts(*MBB);
-
-  // Not if we've haven't found a suitable mov and LR is live out.
-  if (LiveRegs.contains(ARM::LR))
-    return nullptr;
-
-  // If LR is not live out, we can insert the instruction if nothing else
-  // uses LR after it.
-  if (!SearchForUse(Start, MBB->end(), ARM::LR))
+  // just define LR anyway?
+  if (!RDA->isRegUsedAfter(Start, ARM::LR))
     return Start;
 
-  LLVM_DEBUG(dbgs() << "ARM Loops: Failed to find suitable insertion point for"
-             << " LR\n");
   return nullptr;
 }
 
-void LowOverheadLoop::CheckLegality(ARMBasicBlockUtils *BBUtils) {
+void LowOverheadLoop::CheckLegality(ARMBasicBlockUtils *BBUtils,
+                                    ReachingDefAnalysis *RDA) {
   if (Revert)
     return;
 
   if (!End->getOperand(1).isMBB())
     report_fatal_error("Expected LoopEnd to target basic block");
 
   // TODO Maybe there's cases where the target doesn't have to be the header,
   // but for now be safe and revert.
if (Start->getOpcode() == ARM::t2WhileLoopStart &&
       (BBUtils->getOffsetOf(Start) >
        BBUtils->getOffsetOf(Start->getOperand(1).getMBB()) ||
        !BBUtils->isBBInRange(Start, Start->getOperand(1).getMBB(), 4094))) {
     LLVM_DEBUG(dbgs() << "ARM Loops: WLS offset is out-of-range!\n");
     Revert = true;
     return;
   }
 
-  InsertPt = Revert ? nullptr : IsSafeToDefineLR();
+  InsertPt = Revert ? nullptr : IsSafeToDefineLR(RDA);
   if (!InsertPt) {
     LLVM_DEBUG(dbgs() << "ARM Loops: Unable to find safe insertion point.\n");
     Revert = true;
   } else
     LLVM_DEBUG(dbgs() << "ARM Loops: Start insertion point: " << *InsertPt);
 
   LLVM_DEBUG(if (IsTailPredicationLegal()) {
                dbgs() << "ARM Loops: Will use tail predication to convert:\n";
                for (auto *MI : VPTUsers)
                  dbgs() << " - " << *MI;
              });
 }
 
 bool ARMLowOverheadLoops::runOnMachineFunction(MachineFunction &mf) {
   const ARMSubtarget &ST = static_cast<const ARMSubtarget&>(mf.getSubtarget());
   if (!ST.hasLOB())
     return false;
 
   MF = &mf;
   LLVM_DEBUG(dbgs() << "ARM Loops on " << MF->getName() << " ------------- \n");
 
   auto &MLI = getAnalysis<MachineLoopInfo>();
+  RDA = &getAnalysis<ReachingDefAnalysis>();
   MF->getProperties().set(MachineFunctionProperties::Property::TracksLiveness);
   MRI = &MF->getRegInfo();
   TII = static_cast<const ARMBaseInstrInfo*>(ST.getInstrInfo());
   BBUtils = std::unique_ptr<ARMBasicBlockUtils>(new ARMBasicBlockUtils(*MF));
   BBUtils->computeAllBlockSizes();
   BBUtils->adjustBBOffsetsAfter(&MF->front());
 
   bool Changed = false;
for (auto &MI : *MBB) {
       }
     }
   }
 
   LLVM_DEBUG(LoLoop.dump());
   if (!LoLoop.FoundAllComponents())
     return false;
 
-  LoLoop.CheckLegality(BBUtils.get());
+  LoLoop.CheckLegality(BBUtils.get(), RDA);
   Expand(LoLoop);
   return true;
 }
 
 // WhileLoopStart holds the exit block, so produce a cmp lr, 0 and then a
 // beq that branches to the exit branch.
 // TODO: We could also try to generate a cbz if the value in LR is also in
 // another low register.
void ARMLowOverheadLoops::RevertWhile(MachineInstr *MI) const {
   MIB = BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(BrOpc));
   MIB.add(MI->getOperand(1));   // branch target
   MIB.addImm(ARMCC::EQ);        // condition code
   MIB.addReg(ARM::CPSR);
   MI->eraseFromParent();
 }
 
 bool ARMLowOverheadLoops::RevertLoopDec(MachineInstr *MI,
-                                        bool AllowFlags) const {
+                                        bool SetFlags) const {
   LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to sub: " << *MI);
   MachineBasicBlock *MBB = MI->getParent();
 
-  // If nothing uses or defines CPSR between LoopDec and LoopEnd, use a t2SUBS.
-  bool SetFlags = false;
-  if (AllowFlags) {
-    if (auto *Def = SearchForDef(MI, MBB->end(), ARM::CPSR)) {
-      if (!SearchForUse(MI, MBB->end(), ARM::CPSR) &&
-          Def->getOpcode() == ARM::t2LoopEnd)
-        SetFlags = true;
-    }
-  }
+  // If nothing defines CPSR between LoopDec and LoopEnd, use a t2SUBS.
+  if (SetFlags &&
+      (RDA->isRegUsedAfter(MI, ARM::CPSR) ||
+       !RDA->hasSameReachingDef(MI, &MBB->back(), ARM::CPSR)))
+      SetFlags = false;
 
   MachineInstrBuilder MIB = BuildMI(*MBB, MI, MI->getDebugLoc(),
                                     TII->get(ARM::t2SUBri));
   MIB.addDef(ARM::LR);
   MIB.add(MI->getOperand(1));
   MIB.add(MI->getOperand(2));
   MIB.addImm(ARMCC::AL);
   MIB.addReg(0);

llvm/test/CodeGen/ARM/O3-pipeline.ll

 ; CHECK-NEXT:      Branch Probability Basic Block Placement
 ; CHECK-NEXT:      Thumb2 instruction size reduce pass
 ; CHECK-NEXT:      Unpack machine instruction bundles
 ; CHECK-NEXT:      optimise barriers pass
 ; CHECK-NEXT:      MachineDominator Tree Construction
 ; CHECK-NEXT:      ARM constant island placement and branch shortening pass
 ; CHECK-NEXT:      MachineDominator Tree Construction
 ; CHECK-NEXT:      Machine Natural Loop Construction
+; CHECK-NEXT:      ReachingDefAnalysis
 ; CHECK-NEXT:      ARM Low Overhead Loops pass
 ; CHECK-NEXT:      Contiguously Lay Out Funclets
 ; CHECK-NEXT:      StackMap Liveness Analysis
 ; CHECK-NEXT:      Live DEBUG_VALUE analysis
 ; CHECK-NEXT:      Insert fentry calls
 ; CHECK-NEXT:      Insert XRay ops
 ; CHECK-NEXT:      Implement the 'patchable-function' attribute
 ; CHECK-NEXT:      Lazy Machine Block Frequency Analysis
 ; CHECK-NEXT:      Machine Optimization Remark Emitter
 ; CHECK-NEXT:      ARM Assembly Printer
 ; CHECK-NEXT:      Free MachineFunction

llvm/test/CodeGen/Thumb2/LowOverheadLoops/unsafe-cpsr-loop-def.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -mtriple=thumbv8.1m.main -run-pass=arm-low-overhead-loops -verify-machineinstrs %s -o - | FileCheck %s
+# Check that subs isn't used during the revert because there's a def after LoopDec.
+
+--- |
+  define i32 @do_copy(i32 %n, i32* nocapture %p, i32* nocapture readonly %q) {
+  entry:
+    %scevgep = getelementptr i32, i32* %q, i32 -1
+    %scevgep3 = getelementptr i32, i32* %p, i32 -1
+    call void @llvm.set.loop.iterations.i32(i32 %n)
+    %limit = lshr i32 %n, 1
+    br label %while.body
+
+  while.body:                                       ; preds = %while.body, %entry
+    %lsr.iv4 = phi i32* [ %scevgep5, %while.body ], [ %scevgep3, %entry ]
+    %lsr.iv = phi i32* [ %scevgep1, %while.body ], [ %scevgep, %entry ]
+    %tmp = phi i32 [ %n, %entry ], [ %tmp2, %while.body ]
+    %scevgep7 = getelementptr i32, i32* %lsr.iv, i32 1
+    %scevgep4 = getelementptr i32, i32* %lsr.iv4, i32 1
+    %tmp1 = load i32, i32* %scevgep7, align 4
+    %tmp2 = call i32 @llvm.loop.decrement.reg.i32.i32.i32(i32 %tmp, i32 1)
+    %half = lshr i32 %tmp1, 1
+    %cmp = icmp ult i32 %tmp, %limit
+    %res = select i1 %cmp, i32 %tmp1, i32 %half
+    store i32 %res, i32* %scevgep4, align 4
+    %scevgep1 = getelementptr i32, i32* %lsr.iv, i32 1
+    %scevgep5 = getelementptr i32, i32* %lsr.iv4, i32 1
+    %tmp3 = icmp ne i32 %tmp2, 0
+    br i1 %tmp3, label %while.body, label %while.end
+
+  while.end:                                        ; preds = %while.body
+    ret i32 0
+  }
+
+  ; Function Attrs: noduplicate nounwind
+  declare void @llvm.set.loop.iterations.i32(i32) #0
+
+  ; Function Attrs: noduplicate nounwind
+  declare i32 @llvm.loop.decrement.reg.i32.i32.i32(i32, i32) #0
+
+  ; Function Attrs: nounwind
+  declare void @llvm.stackprotector(i8*, i8**) #1
+
+  attributes #0 = { noduplicate nounwind }
+  attributes #1 = { nounwind }
+
+...
+---
+name:            do_copy
+alignment:       2
+exposesReturnsTwice: false
+legalized:       false
+regBankSelected: false
+selected:        false
+failedISel:      false
+tracksRegLiveness: true
+hasWinCFI:       false
+registers:       []
+liveins:
+  - { reg: '$r0', virtual-reg: '' }
+  - { reg: '$r1', virtual-reg: '' }
+  - { reg: '$r2', virtual-reg: '' }
+frameInfo:
+  isFrameAddressTaken: false
+  isReturnAddressTaken: false
+  hasStackMap:     false
+  hasPatchPoint:   false
+  stackSize:       8
+  offsetAdjustment: 0
+  maxAlignment:    4
+  adjustsStack:    false
+  hasCalls:        false
+  stackProtector:  ''
+  maxCallFrameSize: 0
+  cvBytesOfCalleeSavedRegisters: 0
+  hasOpaqueSPAdjustment: false
+  hasVAStart:      false
+  hasMustTailInVarArgFunc: false
+  localFrameSize:  0
+  savePoint:       ''
+  restorePoint:    ''
+fixedStack:      []
+stack:
+  - { id: 0, name: '', type: spill-slot, offset: -4, size: 4, alignment: 4,
+      stack-id: default, callee-saved-register: '$lr', callee-saved-restored: false,
+      debug-info-variable: '', debug-info-expression: '', debug-info-location: '' }
+  - { id: 1, name: '', type: spill-slot, offset: -8, size: 4, alignment: 4,
+      stack-id: default, callee-saved-register: '$r7', callee-saved-restored: true,
+      debug-info-variable: '', debug-info-expression: '', debug-info-location: '' }
+callSites:       []
+constants:       []
+machineFunctionInfo: {}
+body:             |
+  ; CHECK-LABEL: name: do_copy
+  ; CHECK: bb.0.entry:
+  ; CHECK:   successors: %bb.1(0x80000000)
+  ; CHECK:   liveins: $r0, $r1, $r2, $r7, $lr
+  ; CHECK:   frame-setup tPUSH 14, $noreg, killed $r7, killed $lr, implicit-def $sp, implicit $sp
+  ; CHECK:   frame-setup CFI_INSTRUCTION def_cfa_offset 8
+  ; CHECK:   frame-setup CFI_INSTRUCTION offset $lr, -4
+  ; CHECK:   frame-setup CFI_INSTRUCTION offset $r7, -8
+  ; CHECK:   $lr = tMOVr killed $r0, 14, $noreg
+  ; CHECK:   renamable $r0, dead $cpsr = tSUBi3 killed renamable $r1, 4, 14, $noreg
+  ; CHECK:   renamable $r1, dead $cpsr = tSUBi3 killed renamable $r2, 4, 14, $noreg
+  ; CHECK:   renamable $r2 = t2LSRri renamable $lr, 1, 14, $noreg, $noreg
+  ; CHECK: bb.1.while.body:
+  ; CHECK:   successors: %bb.1(0x7c000000), %bb.2(0x04000000)
+  ; CHECK:   liveins: $lr, $r0, $r1, $r2
+  ; CHECK:   renamable $r3, renamable $r1 = t2LDR_PRE killed renamable $r1, 4, 14, $noreg :: (load 4 from %ir.scevgep7)
+  ; CHECK:   tCMPhir renamable $lr, renamable $r2, 14, $noreg, implicit-def $cpsr
+  ; CHECK:   $lr = t2SUBri killed renamable $lr, 1, 14, $noreg, $noreg
+  ; CHECK:   t2IT 2, 8, implicit-def $itstate
+  ; CHECK:   renamable $r3 = tLSRri $noreg, killed renamable $r3, 1, 2, killed $cpsr, implicit renamable $r3, implicit killed $itstate
+  ; CHECK:   early-clobber renamable $r0 = t2STR_PRE killed renamable $r3, killed renamable $r0, 4, 14, $noreg :: (store 4 into %ir.scevgep4)
+  ; CHECK:   t2CMPri renamable $lr, 0, 14, $noreg, implicit-def $cpsr
+  ; CHECK:   tBcc %bb.1, 4, killed $cpsr
+  ; CHECK:   tB %bb.2, 14, $noreg
+  ; CHECK: bb.2.while.end:
+  ; CHECK:   $r0, dead $cpsr = tMOVi8 0, 14, $noreg
+  ; CHECK:   tPOP_RET 14, $noreg, def $r7, def $pc, implicit killed $r0
+  bb.0.entry:
+    successors: %bb.1(0x80000000)
+    liveins: $r0, $r1, $r2, $r7, $lr
+
+    frame-setup tPUSH 14, $noreg, killed $r7, killed $lr, implicit-def $sp, implicit $sp
+    frame-setup CFI_INSTRUCTION def_cfa_offset 8
+    frame-setup CFI_INSTRUCTION offset $lr, -4
+    frame-setup CFI_INSTRUCTION offset $r7, -8
+    $lr = tMOVr killed $r0, 14, $noreg
+    renamable $r0, dead $cpsr = tSUBi3 killed renamable $r1, 4, 14, $noreg
+    renamable $r1, dead $cpsr = tSUBi3 killed renamable $r2, 4, 14, $noreg
+    renamable $r2 = t2LSRri renamable $lr, 1, 14, $noreg, $noreg
+    t2DoLoopStart renamable $lr
+
+  bb.1.while.body:
+    successors: %bb.1(0x7c000000), %bb.2(0x04000000)
+    liveins: $lr, $r0, $r1, $r2
+
+    renamable $r3, renamable $r1 = t2LDR_PRE killed renamable $r1, 4, 14, $noreg :: (load 4 from %ir.scevgep7)
+    tCMPhir renamable $lr, renamable $r2, 14, $noreg, implicit-def $cpsr
+    renamable $lr = t2LoopDec killed renamable $lr, 1
+    t2IT 2, 8, implicit-def $itstate
+    renamable $r3 = tLSRri $noreg, killed renamable $r3, 1, 2, killed $cpsr, implicit renamable $r3, implicit killed $itstate
+    early-clobber renamable $r0 = t2STR_PRE killed renamable $r3, killed renamable $r0, 4, 14, $noreg :: (store 4 into %ir.scevgep4)
+    t2CMPri renamable $lr, 0, 14, $noreg, implicit-def $cpsr
+    tBcc %bb.1, 4, killed $cpsr
+    tB %bb.2, 14, $noreg
+
+  bb.2.while.end:
+    $r0, dead $cpsr = tMOVi8 0, 14, $noreg
+    tPOP_RET 14, $noreg, def $r7, def $pc, implicit killed $r0
+
+...

llvm/test/CodeGen/Thumb2/LowOverheadLoops/unsafe-cpsr-loop-use.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -mtriple=thumbv8.1m.main -run-pass=arm-low-overhead-loops -verify-machineinstrs %s -o - | FileCheck %s
+# Check that subs isn't used during the revert because there's a cpsr use after it.
+
+--- |
+  define i32 @do_copy(i32 %n, i32* nocapture %p, i32* nocapture readonly %q) {
+  entry:
+    %scevgep = getelementptr i32, i32* %q, i32 -1
+    %scevgep3 = getelementptr i32, i32* %p, i32 -1
+    call void @llvm.set.loop.iterations.i32(i32 %n)
+    %limit = lshr i32 %n, 1
+    br label %while.body
+
+  while.body:                                       ; preds = %while.body, %entry
+    %lsr.iv4 = phi i32* [ %scevgep5, %while.body ], [ %scevgep3, %entry ]
+    %lsr.iv = phi i32* [ %scevgep1, %while.body ], [ %scevgep, %entry ]
+    %tmp = phi i32 [ %n, %entry ], [ %tmp2, %while.body ]
+    %scevgep7 = getelementptr i32, i32* %lsr.iv, i32 1
+    %scevgep4 = getelementptr i32, i32* %lsr.iv4, i32 1
+    %tmp1 = load i32, i32* %scevgep7, align 4
+    %tmp2 = call i32 @llvm.loop.decrement.reg.i32.i32.i32(i32 %tmp, i32 1)
+    %half = lshr i32 %tmp1, 1
+    %cmp = icmp ult i32 %tmp, %limit
+    %res = select i1 %cmp, i32 %tmp1, i32 %half
+    store i32 %res, i32* %scevgep4, align 4
+    %scevgep1 = getelementptr i32, i32* %lsr.iv, i32 1
+    %scevgep5 = getelementptr i32, i32* %lsr.iv4, i32 1
+    %tmp3 = icmp ne i32 %tmp2, 0
+    br i1 %tmp3, label %while.body, label %while.end
+
+  while.end:                                        ; preds = %while.body
+    ret i32 0
+  }
+
+  ; Function Attrs: noduplicate nounwind
+  declare void @llvm.set.loop.iterations.i32(i32) #0
+
+  ; Function Attrs: noduplicate nounwind
+  declare i32 @llvm.loop.decrement.reg.i32.i32.i32(i32, i32) #0
+
+  ; Function Attrs: nounwind
+  declare void @llvm.stackprotector(i8*, i8**) #1
+
+  attributes #0 = { noduplicate nounwind }
+  attributes #1 = { nounwind }
+
+...
+---
+name:            do_copy
+alignment:       2
+exposesReturnsTwice: false
+legalized:       false
+regBankSelected: false
+selected:        false
+failedISel:      false
+tracksRegLiveness: true
+hasWinCFI:       false
+registers:       []
+liveins:
+  - { reg: '$r0', virtual-reg: '' }
+  - { reg: '$r1', virtual-reg: '' }
+  - { reg: '$r2', virtual-reg: '' }
+frameInfo:
+  isFrameAddressTaken: false
+  isReturnAddressTaken: false
+  hasStackMap:     false
+  hasPatchPoint:   false
+  stackSize:       8
+  offsetAdjustment: 0
+  maxAlignment:    4
+  adjustsStack:    false
+  hasCalls:        false
+  stackProtector:  ''
+  maxCallFrameSize: 0
+  cvBytesOfCalleeSavedRegisters: 0
+  hasOpaqueSPAdjustment: false
+  hasVAStart:      false
+  hasMustTailInVarArgFunc: false
+  localFrameSize:  0
+  savePoint:       ''
+  restorePoint:    ''
+fixedStack:      []
+stack:
+  - { id: 0, name: '', type: spill-slot, offset: -4, size: 4, alignment: 4,
+      stack-id: default, callee-saved-register: '$lr', callee-saved-restored: false,
+      debug-info-variable: '', debug-info-expression: '', debug-info-location: '' }
+  - { id: 1, name: '', type: spill-slot, offset: -8, size: 4, alignment: 4,
+      stack-id: default, callee-saved-register: '$r7', callee-saved-restored: true,
+      debug-info-variable: '', debug-info-expression: '', debug-info-location: '' }
+callSites:       []
+constants:       []
+machineFunctionInfo: {}
+body:             |
+  ; CHECK-LABEL: name: do_copy
+  ; CHECK: bb.0.entry:
+  ; CHECK:   successors: %bb.1(0x80000000)
+  ; CHECK:   liveins: $r0, $r1, $r2, $r7, $lr
+  ; CHECK:   frame-setup tPUSH 14, $noreg, killed $r7, killed $lr, implicit-def $sp, implicit $sp
+  ; CHECK:   frame-setup CFI_INSTRUCTION def_cfa_offset 8
+  ; CHECK:   frame-setup CFI_INSTRUCTION offset $lr, -4
+  ; CHECK:   frame-setup CFI_INSTRUCTION offset $r7, -8
+  ; CHECK:   renamable $r0, dead $cpsr = tSUBi3 killed renamable $r1, 4, 14, $noreg
+  ; CHECK:   renamable $r1, dead $cpsr = tSUBi3 killed renamable $r2, 4, 14, $noreg
+  ; CHECK:   renamable $r2 = t2LSRri renamable $r0, 1, 14, $noreg, $noreg
+  ; CHECK:   $lr = tMOVr killed $r0, 14, $noreg
+  ; CHECK: bb.1.while.body:
+  ; CHECK:   successors: %bb.1(0x7c000000), %bb.2(0x04000000)
+  ; CHECK:   liveins: $lr, $r0, $r1, $r2
+  ; CHECK:   renamable $r3, renamable $r1 = t2LDR_PRE killed renamable $r1, 4, 14, $noreg :: (load 4 from %ir.scevgep7)
+  ; CHECK:   tCMPhir renamable $lr, renamable $r2, 14, $noreg, implicit-def $cpsr
+  ; CHECK:   $lr = t2SUBri killed renamable $lr, 1, 14, $noreg, $noreg
+  ; CHECK:   t2IT 2, 8, implicit-def $itstate
+  ; CHECK:   renamable $r3 = tLSRri $noreg, killed renamable $r3, 1, 2, killed $cpsr, implicit renamable $r3, implicit killed $itstate
+  ; CHECK:   early-clobber renamable $r0 = t2STR_PRE killed renamable $r3, killed renamable $r0, 4, 14, $noreg :: (store 4 into %ir.scevgep4)
+  ; CHECK:   t2CMPri $lr, 0, 14, $noreg, implicit-def $cpsr
+  ; CHECK:   tBcc %bb.1, 1, $cpsr
+  ; CHECK:   tB %bb.2, 14, $noreg
+  ; CHECK: bb.2.while.end:
+  ; CHECK:   $r0, dead $cpsr = tMOVi8 0, 14, $noreg
+  ; CHECK:   tPOP_RET 14, $noreg, def $r7, def $pc, implicit killed $r0
+  bb.0.entry:
+    successors: %bb.1(0x80000000)
+    liveins: $r0, $r1, $r2, $r7, $lr
+
+    frame-setup tPUSH 14, $noreg, killed $r7, killed $lr, implicit-def $sp, implicit $sp
+    frame-setup CFI_INSTRUCTION def_cfa_offset 8
+    frame-setup CFI_INSTRUCTION offset $lr, -4
+    frame-setup CFI_INSTRUCTION offset $r7, -8
+    renamable $r0, dead $cpsr = tSUBi3 killed renamable $r1, 4, 14, $noreg
+    renamable $r1, dead $cpsr = tSUBi3 killed renamable $r2, 4, 14, $noreg
+    t2DoLoopStart renamable $r0
+    renamable $r2 = t2LSRri renamable $r0, 1, 14, $noreg, $noreg
+    $lr = tMOVr killed $r0, 14, $noreg
+
+  bb.1.while.body:
+    successors: %bb.1(0x7c000000), %bb.2(0x04000000)
+    liveins: $lr, $r0, $r1, $r2
+
+    renamable $r3, renamable $r1 = t2LDR_PRE killed renamable $r1, 4, 14, $noreg :: (load 4 from %ir.scevgep7)
+    tCMPhir renamable $lr, renamable $r2, 14, $noreg, implicit-def $cpsr
+    renamable $lr = t2LoopDec killed renamable $lr, 1
+    t2IT 2, 8, implicit-def $itstate
+    renamable $r3 = tLSRri $noreg, killed renamable $r3, 1, 2, killed $cpsr, implicit renamable $r3, implicit killed $itstate
+    early-clobber renamable $r0 = t2STR_PRE killed renamable $r3, killed renamable $r0, 4, 14, $noreg :: (store 4 into %ir.scevgep4)
+    t2LoopEnd killed renamable $lr, %bb.1, implicit-def dead $cpsr
+    tB %bb.2, 14, $noreg
+
+  bb.2.while.end:
+    $r0, dead $cpsr = tMOVi8 0, 14, $noreg
+    tPOP_RET 14, $noreg, def $r7, def $pc, implicit killed $r0
+
+...

llvm/test/CodeGen/Thumb2/ifcvt-neon-deprecated.mir

-# RUN: llc -mtriple=thumbv7 -start-before=if-converter -o - %s | FileCheck %s
+# RUN: llc -mtriple=thumbv7 -start-before=if-converter %s -o - | FileCheck %s
+
+--- |
+  ; ModuleID = 'vdup-test.ll'
+  source_filename = "vdup-test.ll"
+  target datalayout = "e-m:e-p:32:32-Fi8-i64:64-v128:64:128-a:0:32-n32-S64"
+  target triple = "thumbv7"
+  
+  define arm_aapcs_vfpcc <2 x i32> @NeonVdupMul(i32 %scalar, i32 %N, <2 x i32> %vector) {
+  entry:
+    %cmp = icmp ne i32 %N, 0
+    %broadcast = insertelement <2 x i32> undef, i32 %scalar, i32 0
+    %dup = shufflevector <2 x i32> %broadcast, <2 x i32> undef, <2 x i32> zeroinitializer
+    %mul = mul <2 x i32> %dup, %vector
+    br i1 %cmp, label %select.end, label %select.false
+  
+  select.false:                                     ; preds = %entry
+    br label %select.end
+  
+  select.end:                                       ; preds = %entry, %select.false
+    %res = phi <2 x i32> [ %mul, %entry ], [ %vector, %select.false ]
+    ret <2 x i32> %res
+  }
+
+...
 ---
 name:            NeonVdupMul
+alignment:       2
+exposesReturnsTwice: false
+legalized:       false
+regBankSelected: false
+selected:        false
+failedISel:      false
+tracksRegLiveness: true
+hasWinCFI:       false
+registers:       []
+liveins:
+  - { reg: '$r0', virtual-reg: '' }
+  - { reg: '$r1', virtual-reg: '' }
+  - { reg: '$d0', virtual-reg: '' }
+frameInfo:
+  isFrameAddressTaken: false
+  isReturnAddressTaken: false
+  hasStackMap:     false
+  hasPatchPoint:   false
+  stackSize:       0
+  offsetAdjustment: 0
+  maxAlignment:    1
+  adjustsStack:    false
+  hasCalls:        false
+  stackProtector:  ''
+  maxCallFrameSize: 0
+  cvBytesOfCalleeSavedRegisters: 0
+  hasOpaqueSPAdjustment: false
+  hasVAStart:      false
+  hasMustTailInVarArgFunc: false
+  localFrameSize:  0
+  savePoint:       ''
+  restorePoint:    ''
+fixedStack:      []
+stack:           []
+callSites:       []
+constants:       []
+machineFunctionInfo: {}
 body:             |
-  bb.0:
-    successors: %bb.2, %bb.1
+  bb.0.entry:
+    successors: %bb.1(0x50000000), %bb.2(0x30000000)
     liveins: $d0, $r0, $r1
   
-    t2CMPri killed $r1, 0, 14, $noreg, implicit-def $cpsr
+    t2CMPri killed renamable $r1, 0, 14, $noreg, implicit-def $cpsr
     t2Bcc %bb.2, 0, killed $cpsr
   
   bb.1:
+    successors: %bb.2(0x80000000)
     liveins: $d0, $r0
   
-    $d16 = VDUP32d killed $r0, 14, $noreg
+    renamable $d16 = VDUP32d killed renamable $r0, 14, $noreg
     ; Verify that the neon instructions haven't been conditionalized:
     ; CHECK-LABEL: NeonVdupMul
     ; CHECK: vdup.32
     ; CHECK: vmul.i32
-    $d0 = VMULv2i32 killed $d16, killed $d0, 14, $noreg
+    renamable $d0 = VMULv2i32 killed renamable $d16, killed renamable $d0, 14, $noreg
   
-  bb.2:
+  bb.2.select.end:
     liveins: $d0
   
     tBX_RET 14, $noreg, implicit $d0
 
 ...
----
-name:            NeonVmovVfpLdr
-body:             |
-  bb.0.entry:
-    successors: %bb.1, %bb.2
-    liveins: $r0, $r1
-
-    t2CMPri killed $r1, 0, 14, $noreg, implicit-def $cpsr
-    t2Bcc %bb.2, 1, killed $cpsr
-
-  bb.1:
-    $d0 = VMOVv2i32 0, 14, $noreg
-    tBX_RET 14, $noreg, implicit $d0
-
-  bb.2:
-    liveins: $r0
-
-    $d0 = VLDRD killed $r0, 0, 14, $noreg
-    ; Verify that the neon instruction VMOVv2i32 hasn't been conditionalized,
-    ; but the VLDR instruction that is available both in the VFP and Advanced
-    ; SIMD extensions has.
-    ; CHECK-LABEL: NeonVmovVfpLdr
-    ; CHECK-DAG: vmov.i32 d0, #0x0
-    ; CHECK-DAG: vldr{{ne|eq}} d0, [r0]
-    tBX_RET 14, $noreg, implicit $d0
-
-...