llvm.org GIT mirror llvm / master
Split MachineLICM into EarlyMachineLICM and MachineLICM; NFC This avoids playing games with pseudo pass IDs and avoids using an unreliable MRI::isSSA() check to determine whether register allocation has happened. Note that this renames: - MachineLICMID -> EarlyMachineLICM - PostRAMachineLICMID -> MachineLICMID to be consistent with the EarlyTailDuplicate/TailDuplicate naming. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@322927 91177308-0d34-0410-b5e6-96231b3b80d8 Matthias Braun 24 minutes ago
8 changed file(s) with 88 addition(s) and 78 deletion(s). Raw diff Collapse all Expand all
272272 /// memory operations.
273273 extern char &ImplicitNullChecksID;
274274
275 /// MachineLICM - This pass performs LICM on machine instructions.
275 /// This pass performs loop invariant code motion on machine instructions.
276276 extern char &MachineLICMID;
277
278 /// This pass performs loop invariant code motion on machine instructions.
279 /// This variant works before register allocation. \see MachineLICMID.
280 extern char &EarlyMachineLICMID;
277281
278282 /// MachineSinking - This pass performs sinking on machine instructions.
279283 extern char &MachineSinkingID;
8383 /// This is an ImmutablePass solely for the purpose of exposing CodeGen options
8484 /// to the internals of other CodeGen passes.
8585 class TargetPassConfig : public ImmutablePass {
86 public:
87 /// Pseudo Pass IDs. These are defined within TargetPassConfig because they
88 /// are unregistered pass IDs. They are only useful for use with
89 /// TargetPassConfig APIs to identify multiple occurrences of the same pass.
90 ///
91
92 /// PostRAMachineLICM - A clone of the LICM pass that runs during late machine
93 /// optimization after regalloc.
94 static char PostRAMachineLICMID;
95
9686 private:
9787 PassManagerBase *PM = nullptr;
9888 AnalysisID StartBefore = nullptr;
9898 void initializeConstantPropagationPass(PassRegistry&);
9999 void initializeCorrelatedValuePropagationPass(PassRegistry&);
100100 void initializeCostModelAnalysisPass(PassRegistry&);
101 void initializeEarlyMachineLICMPass(PassRegistry&);
101102 void initializeEarlyTailDuplicatePass(PassRegistry&);
102103 void initializeEntryExitInstrumenterPass(PassRegistry&);
103104 void initializePostInlineEntryExitInstrumenterPass(PassRegistry&);
2727 initializeDetectDeadLanesPass(Registry);
2828 initializeDwarfEHPreparePass(Registry);
2929 initializeEarlyIfConverterPass(Registry);
30 initializeEarlyMachineLICMPass(Registry);
3031 initializeEarlyTailDuplicatePass(Registry);
3132 initializeExpandISelPseudosPass(Registry);
3233 initializeExpandMemCmpPassPass(Registry);
8484
8585 namespace {
8686
87 class MachineLICM : public MachineFunctionPass {
87 class MachineLICMBase : public MachineFunctionPass {
8888 const TargetInstrInfo *TII;
8989 const TargetLoweringBase *TLI;
9090 const TargetRegisterInfo *TRI;
9191 const MachineFrameInfo *MFI;
9292 MachineRegisterInfo *MRI;
9393 TargetSchedModel SchedModel;
94 bool PreRegAlloc = true;
94 bool PreRegAlloc;
9595
9696 // Various analyses that we use...
9797 AliasAnalysis *AA; // Alias analysis info.
137137 unsigned SpeculationState;
138138
139139 public:
140 static char ID; // Pass identification, replacement for typeid
141
142 MachineLICM() : MachineFunctionPass(ID) {
143 initializeMachineLICMPass(*PassRegistry::getPassRegistry());
144 }
145
146 explicit MachineLICM(bool PreRA)
147 : MachineFunctionPass(ID), PreRegAlloc(PreRA) {
148 initializeMachineLICMPass(*PassRegistry::getPassRegistry());
149 }
140 MachineLICMBase(char &PassID, bool PreRegAlloc)
141 : MachineFunctionPass(PassID), PreRegAlloc(PreRegAlloc) {}
150142
151143 bool runOnMachineFunction(MachineFunction &MF) override;
152144
251243 MachineBasicBlock *getCurPreheader();
252244 };
253245
246 class MachineLICM : public MachineLICMBase {
247 public:
248 static char ID;
249 MachineLICM() : MachineLICMBase(ID, false) {
250 initializeMachineLICMPass(*PassRegistry::getPassRegistry());
251 }
252 };
253
254 class EarlyMachineLICM : public MachineLICMBase {
255 public:
256 static char ID;
257 EarlyMachineLICM() : MachineLICMBase(ID, true) {
258 initializeEarlyMachineLICMPass(*PassRegistry::getPassRegistry());
259 }
260 };
261
254262 } // end anonymous namespace
255263
256 char MachineLICM::ID = 0;
264 char MachineLICM::ID;
265 char EarlyMachineLICM::ID;
257266
258267 char &llvm::MachineLICMID = MachineLICM::ID;
268 char &llvm::EarlyMachineLICMID = EarlyMachineLICM::ID;
259269
260270 INITIALIZE_PASS_BEGIN(MachineLICM, DEBUG_TYPE,
261271 "Machine Loop Invariant Code Motion", false, false)
264274 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
265275 INITIALIZE_PASS_END(MachineLICM, DEBUG_TYPE,
266276 "Machine Loop Invariant Code Motion", false, false)
277
278 INITIALIZE_PASS_BEGIN(EarlyMachineLICM, "early-machinelicm",
279 "Early Machine Loop Invariant Code Motion", false, false)
280 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
281 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
282 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
283 INITIALIZE_PASS_END(EarlyMachineLICM, "early-machinelicm",
284 "Early Machine Loop Invariant Code Motion", false, false)
267285
268286 /// Test if the given loop is the outer-most loop that has a unique predecessor.
269287 static bool LoopIsOuterMostWithPredecessor(MachineLoop *CurLoop) {
278296 return true;
279297 }
280298
281 bool MachineLICM::runOnMachineFunction(MachineFunction &MF) {
299 bool MachineLICMBase::runOnMachineFunction(MachineFunction &MF) {
282300 if (skipFunction(MF.getFunction()))
283301 return false;
284302
367385
368386 /// Examine the instruction for potentai LICM candidate. Also
369387 /// gather register def and frame object update information.
370 void MachineLICM::ProcessMI(MachineInstr *MI,
371 BitVector &PhysRegDefs,
372 BitVector &PhysRegClobbers,
373 SmallSet &StoredFIs,
374 SmallVectorImpl &Candidates) {
388 void MachineLICMBase::ProcessMI(MachineInstr *MI,
389 BitVector &PhysRegDefs,
390 BitVector &PhysRegClobbers,
391 SmallSet &StoredFIs,
392 SmallVectorImpl &Candidates) {
375393 bool RuledOut = false;
376394 bool HasNonInvariantUse = false;
377395 unsigned Def = 0;
454472
455473 /// Walk the specified region of the CFG and hoist loop invariants out to the
456474 /// preheader.
457 void MachineLICM::HoistRegionPostRA() {
475 void MachineLICMBase::HoistRegionPostRA() {
458476 MachineBasicBlock *Preheader = getCurPreheader();
459477 if (!Preheader)
460478 return;
540558
541559 /// Add register 'Reg' to the livein sets of BBs in the current loop, and make
542560 /// sure it is not killed by any instructions in the loop.
543 void MachineLICM::AddToLiveIns(unsigned Reg) {
561 void MachineLICMBase::AddToLiveIns(unsigned Reg) {
544562 const std::vector &Blocks = CurLoop->getBlocks();
545563 for (MachineBasicBlock *BB : Blocks) {
546564 if (!BB->isLiveIn(Reg))
557575
558576 /// When an instruction is found to only use loop invariant operands that is
559577 /// safe to hoist, this instruction is called to do the dirty work.
560 void MachineLICM::HoistPostRA(MachineInstr *MI, unsigned Def) {
578 void MachineLICMBase::HoistPostRA(MachineInstr *MI, unsigned Def) {
561579 MachineBasicBlock *Preheader = getCurPreheader();
562580
563581 // Now move the instructions to the predecessor, inserting it before any
580598
581599 /// Check if this mbb is guaranteed to execute. If not then a load from this mbb
582600 /// may not be safe to hoist.
583 bool MachineLICM::IsGuaranteedToExecute(MachineBasicBlock *BB) {
601 bool MachineLICMBase::IsGuaranteedToExecute(MachineBasicBlock *BB) {
584602 if (SpeculationState != SpeculateUnknown)
585603 return SpeculationState == SpeculateFalse;
586604
599617 return true;
600618 }
601619
602 void MachineLICM::EnterScope(MachineBasicBlock *MBB) {
620 void MachineLICMBase::EnterScope(MachineBasicBlock *MBB) {
603621 DEBUG(dbgs() << "Entering " << printMBBReference(*MBB) << '\n');
604622
605623 // Remember livein register pressure.
606624 BackTrace.push_back(RegPressure);
607625 }
608626
609 void MachineLICM::ExitScope(MachineBasicBlock *MBB) {
627 void MachineLICMBase::ExitScope(MachineBasicBlock *MBB) {
610628 DEBUG(dbgs() << "Exiting " << printMBBReference(*MBB) << '\n');
611629 BackTrace.pop_back();
612630 }
614632 /// Destroy scope for the MBB that corresponds to the given dominator tree node
615633 /// if its a leaf or all of its children are done. Walk up the dominator tree to
616634 /// destroy ancestors which are now done.
617 void MachineLICM::ExitScopeIfDone(MachineDomTreeNode *Node,
618 DenseMap &OpenChildren,
619 DenseMap &ParentMap) {
635 void MachineLICMBase::ExitScopeIfDone(MachineDomTreeNode *Node,
636 DenseMap &OpenChildren,
637 DenseMap &ParentMap) {
620638 if (OpenChildren[Node])
621639 return;
622640
637655 /// specified header block, and that are in the current loop) in depth first
638656 /// order w.r.t the DominatorTree. This allows us to visit definitions before
639657 /// uses, allowing us to hoist a loop body in one pass without iteration.
640 void MachineLICM::HoistOutOfLoop(MachineDomTreeNode *HeaderN) {
658 void MachineLICMBase::HoistOutOfLoop(MachineDomTreeNode *HeaderN) {
641659 MachineBasicBlock *Preheader = getCurPreheader();
642660 if (!Preheader)
643661 return;
718736 /// Sink instructions into loops if profitable. This especially tries to prevent
719737 /// register spills caused by register pressure if there is little to no
720738 /// overhead moving instructions into loops.
721 void MachineLICM::SinkIntoLoop() {
739 void MachineLICMBase::SinkIntoLoop() {
722740 MachineBasicBlock *Preheader = getCurPreheader();
723741 if (!Preheader)
724742 return;
772790 /// Find all virtual register references that are liveout of the preheader to
773791 /// initialize the starting "register pressure". Note this does not count live
774792 /// through (livein but not used) registers.
775 void MachineLICM::InitRegPressure(MachineBasicBlock *BB) {
793 void MachineLICMBase::InitRegPressure(MachineBasicBlock *BB) {
776794 std::fill(RegPressure.begin(), RegPressure.end(), 0);
777795
778796 // If the preheader has only a single predecessor and it ends with a
791809 }
792810
793811 /// Update estimate of register pressure after the specified instruction.
794 void MachineLICM::UpdateRegPressure(const MachineInstr *MI,
795 bool ConsiderUnseenAsDef) {
812 void MachineLICMBase::UpdateRegPressure(const MachineInstr *MI,
813 bool ConsiderUnseenAsDef) {
796814 auto Cost = calcRegisterCost(MI, /*ConsiderSeen=*/true, ConsiderUnseenAsDef);
797815 for (const auto &RPIdAndCost : Cost) {
798816 unsigned Class = RPIdAndCost.first;
810828 /// figure out which usages are live-ins.
811829 /// FIXME: Figure out a way to consider 'RegSeen' from all code paths.
812830 DenseMap
813 MachineLICM::calcRegisterCost(const MachineInstr *MI, bool ConsiderSeen,
814 bool ConsiderUnseenAsDef) {
831 MachineLICMBase::calcRegisterCost(const MachineInstr *MI, bool ConsiderSeen,
832 bool ConsiderUnseenAsDef) {
815833 DenseMap Cost;
816834 if (MI->isImplicitDef())
817835 return Cost;
872890
873891 /// Returns true if the instruction may be a suitable candidate for LICM.
874892 /// e.g. If the instruction is a call, then it's obviously not safe to hoist it.
875 bool MachineLICM::IsLICMCandidate(MachineInstr &I) {
893 bool MachineLICMBase::IsLICMCandidate(MachineInstr &I) {
876894 // Check if it's safe to move the instruction.
877895 bool DontMoveAcrossStore = true;
878896 if (!I.isSafeToMove(AA, DontMoveAcrossStore))
895913 /// I.e., all virtual register operands are defined outside of the loop,
896914 /// physical registers aren't accessed explicitly, and there are no side
897915 /// effects that aren't captured by the operands or other flags.
898 bool MachineLICM::IsLoopInvariantInst(MachineInstr &I) {
916 bool MachineLICMBase::IsLoopInvariantInst(MachineInstr &I) {
899917 if (!IsLICMCandidate(I))
900918 return false;
901919
948966
949967 /// Return true if the specified instruction is used by a phi node and hoisting
950968 /// it could cause a copy to be inserted.
951 bool MachineLICM::HasLoopPHIUse(const MachineInstr *MI) const {
969 bool MachineLICMBase::HasLoopPHIUse(const MachineInstr *MI) const {
952970 SmallVector Work(1, MI);
953971 do {
954972 MI = Work.pop_back_val();
9831001
9841002 /// Compute operand latency between a def of 'Reg' and an use in the current
9851003 /// loop, return true if the target considered it high.
986 bool MachineLICM::HasHighOperandLatency(MachineInstr &MI,
987 unsigned DefIdx, unsigned Reg) const {
1004 bool MachineLICMBase::HasHighOperandLatency(MachineInstr &MI,
1005 unsigned DefIdx,
1006 unsigned Reg) const {
9881007 if (MRI->use_nodbg_empty(Reg))
9891008 return false;
9901009
10141033
10151034 /// Return true if the instruction is marked "cheap" or the operand latency
10161035 /// between its def and a use is one or less.
1017 bool MachineLICM::IsCheapInstruction(MachineInstr &MI) const {
1036 bool MachineLICMBase::IsCheapInstruction(MachineInstr &MI) const {
10181037 if (TII->isAsCheapAsAMove(MI) || MI.isCopyLike())
10191038 return true;
10201039
10391058
10401059 /// Visit BBs from header to current BB, check if hoisting an instruction of the
10411060 /// given cost matrix can cause high register pressure.
1042 bool MachineLICM::CanCauseHighRegPressure(const DenseMap& Cost,
1043 bool CheapInstr) {
1061 bool
1062 MachineLICMBase::CanCauseHighRegPressure(const DenseMap& Cost,
1063 bool CheapInstr) {
10441064 for (const auto &RPIdAndCost : Cost) {
10451065 if (RPIdAndCost.second <= 0)
10461066 continue;
10641084 /// Traverse the back trace from header to the current block and update their
10651085 /// register pressures to reflect the effect of hoisting MI from the current
10661086 /// block to the preheader.
1067 void MachineLICM::UpdateBackTraceRegPressure(const MachineInstr *MI) {
1087 void MachineLICMBase::UpdateBackTraceRegPressure(const MachineInstr *MI) {
10681088 // First compute the 'cost' of the instruction, i.e. its contribution
10691089 // to register pressure.
10701090 auto Cost = calcRegisterCost(MI, /*ConsiderSeen=*/false,
10781098
10791099 /// Return true if it is potentially profitable to hoist the given loop
10801100 /// invariant.
1081 bool MachineLICM::IsProfitableToHoist(MachineInstr &MI) {
1101 bool MachineLICMBase::IsProfitableToHoist(MachineInstr &MI) {
10821102 if (MI.isImplicitDef())
10831103 return true;
10841104
11701190 /// Unfold a load from the given machineinstr if the load itself could be
11711191 /// hoisted. Return the unfolded and hoistable load, or null if the load
11721192 /// couldn't be unfolded or if it wouldn't be hoistable.
1173 MachineInstr *MachineLICM::ExtractHoistableLoad(MachineInstr *MI) {
1193 MachineInstr *MachineLICMBase::ExtractHoistableLoad(MachineInstr *MI) {
11741194 // Don't unfold simple loads.
11751195 if (MI->canFoldAsLoad())
11761196 return nullptr;
12281248 /// Initialize the CSE map with instructions that are in the current loop
12291249 /// preheader that may become duplicates of instructions that are hoisted
12301250 /// out of the loop.
1231 void MachineLICM::InitCSEMap(MachineBasicBlock *BB) {
1251 void MachineLICMBase::InitCSEMap(MachineBasicBlock *BB) {
12321252 for (MachineInstr &MI : *BB)
12331253 CSEMap[MI.getOpcode()].push_back(&MI);
12341254 }
12361256 /// Find an instruction amount PrevMIs that is a duplicate of MI.
12371257 /// Return this instruction if it's found.
12381258 const MachineInstr*
1239 MachineLICM::LookForDuplicate(const MachineInstr *MI,
1240 std::vector &PrevMIs) {
1259 MachineLICMBase::LookForDuplicate(const MachineInstr *MI,
1260 std::vector &PrevMIs) {
12411261 for (const MachineInstr *PrevMI : PrevMIs)
12421262 if (TII->produceSameValue(*MI, *PrevMI, (PreRegAlloc ? MRI : nullptr)))
12431263 return PrevMI;
12491269 /// computes the same value. If it's found, do a RAU on with the definition of
12501270 /// the existing instruction rather than hoisting the instruction to the
12511271 /// preheader.
1252 bool MachineLICM::EliminateCSE(MachineInstr *MI,
1253 DenseMap>::iterator &CI) {
1272 bool MachineLICMBase::EliminateCSE(MachineInstr *MI,
1273 DenseMap>::iterator &CI) {
12541274 // Do not CSE implicit_def so ProcessImplicitDefs can properly propagate
12551275 // the undef property onto uses.
12561276 if (CI == CSEMap.end() || MI->isImplicitDef())
13071327
13081328 /// Return true if the given instruction will be CSE'd if it's hoisted out of
13091329 /// the loop.
1310 bool MachineLICM::MayCSE(MachineInstr *MI) {
1330 bool MachineLICMBase::MayCSE(MachineInstr *MI) {
13111331 unsigned Opcode = MI->getOpcode();
13121332 DenseMap>::iterator
13131333 CI = CSEMap.find(Opcode);
13221342 /// When an instruction is found to use only loop invariant operands
13231343 /// that are safe to hoist, this instruction is called to do the dirty work.
13241344 /// It returns true if the instruction is hoisted.
1325 bool MachineLICM::Hoist(MachineInstr *MI, MachineBasicBlock *Preheader) {
1345 bool MachineLICMBase::Hoist(MachineInstr *MI, MachineBasicBlock *Preheader) {
13261346 // First check whether we should hoist this instruction.
13271347 if (!IsLoopInvariantInst(*MI) || !IsProfitableToHoist(*MI)) {
13281348 // If not, try unfolding a hoistable load.
13851405 }
13861406
13871407 /// Get the preheader for the current loop, splitting a critical edge if needed.
1388 MachineBasicBlock *MachineLICM::getCurPreheader() {
1408 MachineBasicBlock *MachineLICMBase::getCurPreheader() {
13891409 // Determine the block to which to hoist instructions. If we can't find a
13901410 // suitable loop predecessor, we can't do any hoisting.
13911411
240240 if (StandardID == &EarlyIfConverterID)
241241 return applyDisable(TargetID, DisableEarlyIfConversion);
242242
243 if (StandardID == &MachineLICMID)
243 if (StandardID == &EarlyMachineLICMID)
244244 return applyDisable(TargetID, DisableMachineLICM);
245245
246246 if (StandardID == &MachineCSEID)
247247 return applyDisable(TargetID, DisableMachineCSE);
248248
249 if (StandardID == &TargetPassConfig::PostRAMachineLICMID)
249 if (StandardID == &MachineLICMID)
250250 return applyDisable(TargetID, DisablePostRAMachineLICM);
251251
252252 if (StandardID == &MachineSinkingID)
265265 INITIALIZE_PASS(TargetPassConfig, "targetpassconfig",
266266 "Target Pass Configuration", false, false)
267267 char TargetPassConfig::ID = 0;
268
269 // Pseudo Pass IDs.
270 char TargetPassConfig::PostRAMachineLICMID = 0;
271268
272269 namespace {
273270
363360 // Also register alias analysis passes required by codegen passes.
364361 initializeBasicAAWrapperPassPass(*PassRegistry::getPassRegistry());
365362 initializeAAResultsWrapperPassPass(*PassRegistry::getPassRegistry());
366
367 // Substitute Pseudo Pass IDs for real ones.
368 substitutePass(&PostRAMachineLICMID, &MachineLICMID);
369363
370364 if (StringRef(PrintMachineInstrs.getValue()).equals(""))
371365 TM.Options.PrintMachineCode = true;
932926 // loop info, just like LICM and CSE below.
933927 addILPOpts();
934928
935 addPass(&MachineLICMID, false);
929 addPass(&EarlyMachineLICMID, false);
936930 addPass(&MachineCSEID, false);
937931
938932 addPass(&MachineSinkingID);
10841078 // Run post-ra machine LICM to hoist reloads / remats.
10851079 //
10861080 // FIXME: can this move into MachineLateOptimization?
1087 addPass(&PostRAMachineLICMID);
1081 addPass(&MachineLICMID);
10881082 }
10891083 }
10901084
781781 addPass(&SILoadStoreOptimizerID);
782782 if (EnableSDWAPeephole) {
783783 addPass(&SIPeepholeSDWAID);
784 addPass(&MachineLICMID);
784 addPass(&EarlyMachineLICMID);
785785 addPass(&MachineCSEID);
786786 addPass(&SIFoldOperandsID);
787787 addPass(&DeadMachineInstructionElimID);
322322 addPass(&StackSlotColoringID);
323323
324324 // FIXME: Needs physical registers
325 //addPass(&PostRAMachineLICMID);
325 //addPass(&MachineLICMID);
326326
327327 printAndVerify("After StackSlotColoring");
328328 }
357357 if (addILPOpts())
358358 printAndVerify("After ILP optimizations");
359359
360 addPass(&MachineLICMID);
360 addPass(&EarlyMachineLICMID);
361361 addPass(&MachineCSEID);
362362
363363 addPass(&MachineSinkingID);