Index: llvm/include/llvm/CodeGen/ReachingDefAnalysis.h =================================================================== --- llvm/include/llvm/CodeGen/ReachingDefAnalysis.h +++ llvm/include/llvm/CodeGen/ReachingDefAnalysis.h @@ -22,6 +22,7 @@ #define LLVM_CODEGEN_REACHINGDEFSANALYSIS_H #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallVector.h" #include "llvm/CodeGen/LoopTraversal.h" #include "llvm/CodeGen/MachineFunctionPass.h" @@ -37,6 +38,7 @@ private: MachineFunction *MF; const TargetRegisterInfo *TRI; + LoopTraversal::TraversalOrder TraversedMBBOrder; unsigned NumRegUnits; /// Instruction that defined each register, relative to the beginning of the /// current basic block. When a LiveRegsDefInfo is used to represent a @@ -93,18 +95,19 @@ MachineFunctionProperties::Property::TracksLiveness); } + /// Re-run the analysis. + void reset(); + + /// Initialize data structures. + void init(); + + /// Traverse the machine function, mapping definitions. + void traverse(); + /// 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) const; - /// 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) const; - - /// 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) const; - /// Return whether A and B use the same def of PhysReg. bool hasSameReachingDef(MachineInstr *A, MachineInstr *B, int PhysReg) const; @@ -117,6 +120,10 @@ MachineInstr *getLocalLiveOutMIDef(MachineBasicBlock *MBB, int PhysReg) const; + /// If a single MachineInstr creates the reaching definition, then return it. + /// Otherwise return null. + MachineInstr *getUniqueReachingMIDef(MachineInstr *MI, int PhysReg) const; + /// Provide whether the register has been defined in the same basic block as, /// and before, MI. bool hasLocalDefBefore(MachineInstr *MI, int PhysReg) const; @@ -137,6 +144,12 @@ void getReachingLocalUses(MachineInstr *MI, int PhysReg, InstSet &Uses) const; + /// Search MBB for a definition of PhysReg and insert it into Incoming. If no + /// definition is found, recursively search the successor blocks for them. + void getLiveOuts(MachineBasicBlock *MBB, int PhysReg, + SetVector &Defs, + SmallPtrSetImpl &VisitedBBs) const; + /// For the given block, collect the instructions that use the live-in /// value of the provided register. Return whether the value is still /// live on exit. @@ -196,6 +209,14 @@ /// the redundant use-def chain. bool isSafeToRemove(MachineInstr *MI, InstSet &Visited, InstSet &ToRemove, InstSet &Ignore) const; + + /// 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) const; + + /// Provides the instruction of the closest reaching def instruction of + /// PhysReg that reaches MI, relative to the begining of MI's basic block. + MachineInstr *getReachingLocalMIDef(MachineInstr *MI, int PhysReg) const; }; } // namespace llvm Index: llvm/lib/CodeGen/ReachingDefAnalysis.cpp =================================================================== --- llvm/lib/CodeGen/ReachingDefAnalysis.cpp +++ llvm/lib/CodeGen/ReachingDefAnalysis.cpp @@ -136,38 +136,44 @@ bool ReachingDefAnalysis::runOnMachineFunction(MachineFunction &mf) { MF = &mf; TRI = MF->getSubtarget().getRegisterInfo(); + LLVM_DEBUG(dbgs() << "********** REACHING DEFINITION ANALYSIS **********\n"); + init(); + traverse(); + return false; +} +void ReachingDefAnalysis::releaseMemory() { + // Clear the internal vectors. + MBBOutRegsInfos.clear(); + MBBReachingDefs.clear(); + InstIds.clear(); LiveRegs.clear(); - NumRegUnits = TRI->getNumRegUnits(); - - MBBReachingDefs.resize(mf.getNumBlockIDs()); +} - LLVM_DEBUG(dbgs() << "********** REACHING DEFINITION ANALYSIS **********\n"); +void ReachingDefAnalysis::reset() { + releaseMemory(); + init(); + traverse(); +} +void ReachingDefAnalysis::init() { + NumRegUnits = TRI->getNumRegUnits(); + MBBReachingDefs.resize(MF->getNumBlockIDs()); // Initialize the MBBOutRegsInfos - MBBOutRegsInfos.resize(mf.getNumBlockIDs()); + MBBOutRegsInfos.resize(MF->getNumBlockIDs()); + LoopTraversal Traversal; + TraversedMBBOrder = Traversal.traverse(*MF); +} +void ReachingDefAnalysis::traverse() { // Traverse the basic blocks. - LoopTraversal Traversal; - LoopTraversal::TraversalOrder TraversedMBBOrder = Traversal.traverse(mf); - for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder) { + for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder) processBasicBlock(TraversedMBB); - } - // Sorting all reaching defs found for a ceartin reg unit in a given BB. for (MBBDefsInfo &MBBDefs : MBBReachingDefs) { for (MBBRegUnitDefs &RegUnitDefs : MBBDefs) llvm::sort(RegUnitDefs); } - - return false; -} - -void ReachingDefAnalysis::releaseMemory() { - // Clear the internal vectors. - MBBOutRegsInfos.clear(); - MBBReachingDefs.clear(); - InstIds.clear(); } int ReachingDefAnalysis::getReachingDef(MachineInstr *MI, int PhysReg) const { @@ -189,7 +195,7 @@ return LatestDef; } -MachineInstr* ReachingDefAnalysis::getReachingMIDef(MachineInstr *MI, +MachineInstr* ReachingDefAnalysis::getReachingLocalMIDef(MachineInstr *MI, int PhysReg) const { return getInstFromId(MI->getParent(), getReachingDef(MI, PhysReg)); } @@ -244,7 +250,7 @@ // If/when we find a new reaching def, we know that there's no more uses // of 'Def'. - if (getReachingMIDef(&*MI, PhysReg) != Def) + if (getReachingLocalMIDef(&*MI, PhysReg) != Def) return; for (auto &MO : MI->operands()) { @@ -305,6 +311,41 @@ } } +void +ReachingDefAnalysis::getLiveOuts(MachineBasicBlock *MBB, int PhysReg, + SetVector &Defs, + SmallPtrSetImpl &VisitedBBs) const { + if (VisitedBBs.count(MBB)) + return; + + VisitedBBs.insert(MBB); + LivePhysRegs LiveRegs(*TRI); + LiveRegs.addLiveOuts(*MBB); + if (!LiveRegs.contains(PhysReg)) + return; + + if (auto *Def = getLocalLiveOutMIDef(MBB, PhysReg)) + Defs.insert(Def); + else + for (auto *Pred : MBB->predecessors()) + getLiveOuts(Pred, PhysReg, Defs, VisitedBBs); +} + +MachineInstr *ReachingDefAnalysis::getUniqueReachingMIDef(MachineInstr *MI, + int PhysReg) const { + if (auto *Def = getReachingLocalMIDef(MI, PhysReg)) + return Def; + + SmallPtrSet VisitedBBs; + SetVector Incoming; + for (auto *Pred : MI->getParent()->predecessors()) + getLiveOuts(Pred, PhysReg, Incoming, VisitedBBs); + + if (Incoming.size() == 1) + return Incoming.front(); + return nullptr; +} + bool ReachingDefAnalysis::isRegUsedAfter(MachineInstr *MI, int PhysReg) const { MachineBasicBlock *MBB = MI->getParent(); LivePhysRegs LiveRegs(*TRI); @@ -331,7 +372,7 @@ return true; if (auto *Def = getLocalLiveOutMIDef(MBB, PhysReg)) - return Def == getReachingMIDef(MI, PhysReg); + return Def == getReachingLocalMIDef(MI, PhysReg); return false; } @@ -476,7 +517,7 @@ InstSet &Ignore) const { // Check for any uses of the register after MI. if (isRegUsedAfter(MI, PhysReg)) { - if (auto *Def = getReachingMIDef(MI, PhysReg)) { + if (auto *Def = getReachingLocalMIDef(MI, PhysReg)) { SmallPtrSet Uses; getReachingLocalUses(Def, PhysReg, Uses); for (auto *Use : Uses) Index: llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp =================================================================== --- llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp +++ llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp @@ -333,7 +333,7 @@ // 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. - if (auto *LRDef = RDA.getReachingMIDef(Start, ARM::LR)) + if (auto *LRDef = RDA.getUniqueReachingMIDef(Start, ARM::LR)) if (IsMoveLR(LRDef) && RDA.hasSameReachingDef(Start, LRDef, CountReg)) return LRDef; @@ -467,7 +467,7 @@ }; MBB = VCTP->getParent(); - if (MachineInstr *Def = RDA.getReachingMIDef(&MBB->back(), NumElements)) { + if (auto *Def = RDA.getUniqueReachingMIDef(&MBB->back(), NumElements)) { SmallPtrSet ElementChain; SmallPtrSet Ignore = { VCTP }; unsigned ExpectedVectorWidth = getTailPredVectorWidth(VCTP->getOpcode()); @@ -849,8 +849,8 @@ if (!LoLoop.IsTailPredicationLegal()) return; - if (auto *Def = RDA->getReachingMIDef(LoLoop.Start, - LoLoop.Start->getOperand(0).getReg())) { + int ElemCountReg = LoLoop.Start->getOperand(0).getReg(); + if (auto *Def = RDA->getUniqueReachingMIDef(LoLoop.Start, ElemCountReg)) { SmallPtrSet Remove; SmallPtrSet Ignore = { LoLoop.Start, LoLoop.Dec, LoLoop.End, LoLoop.InsertPt }; @@ -897,7 +897,7 @@ for (auto &MO : MI->operands()) { if (!MO.isReg() || !MO.isUse() || MO.getReg() == 0) continue; - if (auto *Op = RDA->getReachingMIDef(MI, MO.getReg())) + if (auto *Op = RDA->getUniqueReachingMIDef(MI, MO.getReg())) Chain.push_back(Op); } Ignore.insert(MI); @@ -1085,6 +1085,9 @@ for (auto *MBB : reverse(PostOrder)) recomputeLivenessFlags(*MBB); + + // We've moved, removed and inserted new instructions, so update RDA. + RDA->reset(); } bool ARMLowOverheadLoops::RevertNonLoops() { Index: llvm/test/CodeGen/Thumb2/LowOverheadLoops/matrix.mir =================================================================== --- llvm/test/CodeGen/Thumb2/LowOverheadLoops/matrix.mir +++ llvm/test/CodeGen/Thumb2/LowOverheadLoops/matrix.mir @@ -1,5 +1,5 @@ # NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py -# RUN: llc -mtriple=thumbv8.1m.main -mattr=+mve -run-pass=arm-low-overhead-loops %s -o - | FileCheck %s +# RUN: llc -mtriple=thumbv8.1m.main -mattr=+mve -run-pass=arm-low-overhead-loops %s -o - --verify-machineinstrs | FileCheck %s # A decent sized test to handle a matrix, with scalar and vector low-overhead loops. @@ -270,9 +270,7 @@ ; CHECK: renamable $r0 = t2BICri killed renamable $r0, 3, 14, $noreg, $noreg ; CHECK: renamable $r3 = t2LSLri $r10, 1, 14, $noreg, $noreg ; CHECK: renamable $r1, dead $cpsr = tSUBi3 killed renamable $r0, 4, 14, $noreg - ; CHECK: renamable $r0, dead $cpsr = tMOVi8 1, 14, $noreg ; CHECK: renamable $q0 = MVE_VDUP32 renamable $r7, 0, $noreg, undef renamable $q0 - ; CHECK: renamable $r0 = nuw nsw t2ADDrs killed renamable $r0, renamable $r1, 19, 14, $noreg, $noreg ; CHECK: renamable $r1, dead $cpsr = tLSRri killed renamable $r1, 2, 14, $noreg ; CHECK: renamable $r9 = t2SUBrs $r10, killed renamable $r1, 18, 14, $noreg, $noreg ; CHECK: bb.5.for.cond4.preheader.us: Index: llvm/test/CodeGen/Thumb2/LowOverheadLoops/multiple-do-loops.mir =================================================================== --- llvm/test/CodeGen/Thumb2/LowOverheadLoops/multiple-do-loops.mir +++ llvm/test/CodeGen/Thumb2/LowOverheadLoops/multiple-do-loops.mir @@ -563,7 +563,6 @@ ; CHECK: early-clobber $sp = frame-setup t2STR_PRE killed $r8, $sp, -4, 14, $noreg ; CHECK: frame-setup CFI_INSTRUCTION offset $r8, -24 ; CHECK: renamable $r6, dead $cpsr = tMOVi8 0, 14, $noreg - ; CHECK: dead renamable $r12 = t2MOVi 1, 14, $noreg, $noreg ; CHECK: t2CMPrs killed renamable $r6, renamable $r3, 11, 14, $noreg, implicit-def $cpsr ; CHECK: tBcc %bb.3, 0, killed $cpsr ; CHECK: bb.1.vector.ph: @@ -801,7 +800,6 @@ ; CHECK: successors: %bb.6(0x30000000), %bb.4(0x50000000) ; CHECK: liveins: $r0, $r1, $r2, $r3 ; CHECK: renamable $r6, dead $cpsr = tMOVi8 0, 14, $noreg - ; CHECK: dead renamable $r8 = t2MOVi 1, 14, $noreg, $noreg ; CHECK: t2CMPrs killed renamable $r6, renamable $r3, 11, 14, $noreg, implicit-def $cpsr ; CHECK: tBcc %bb.6, 0, killed $cpsr ; CHECK: bb.4.vector.ph66: