1742 lines · cpp
1//===- MachineLICM.cpp - Machine Loop Invariant Code Motion Pass ----------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This pass performs loop invariant code motion on machine instructions. We10// attempt to remove as much code from the body of a loop as possible.11//12// This pass is not intended to be a replacement or a complete alternative13// for the LLVM-IR-level LICM pass. It is only designed to hoist simple14// constructs that are not exposed before lowering and instruction selection.15//16//===----------------------------------------------------------------------===//17 18#include "llvm/CodeGen/MachineLICM.h"19#include "llvm/ADT/BitVector.h"20#include "llvm/ADT/DenseMap.h"21#include "llvm/ADT/STLExtras.h"22#include "llvm/ADT/SmallVector.h"23#include "llvm/ADT/Statistic.h"24#include "llvm/Analysis/AliasAnalysis.h"25#include "llvm/CodeGen/MachineBasicBlock.h"26#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"27#include "llvm/CodeGen/MachineDomTreeUpdater.h"28#include "llvm/CodeGen/MachineDominators.h"29#include "llvm/CodeGen/MachineFrameInfo.h"30#include "llvm/CodeGen/MachineFunction.h"31#include "llvm/CodeGen/MachineFunctionPass.h"32#include "llvm/CodeGen/MachineInstr.h"33#include "llvm/CodeGen/MachineLoopInfo.h"34#include "llvm/CodeGen/MachineMemOperand.h"35#include "llvm/CodeGen/MachineOperand.h"36#include "llvm/CodeGen/MachineRegisterInfo.h"37#include "llvm/CodeGen/PseudoSourceValue.h"38#include "llvm/CodeGen/TargetInstrInfo.h"39#include "llvm/CodeGen/TargetLowering.h"40#include "llvm/CodeGen/TargetRegisterInfo.h"41#include "llvm/CodeGen/TargetSchedule.h"42#include "llvm/CodeGen/TargetSubtargetInfo.h"43#include "llvm/IR/DebugLoc.h"44#include "llvm/InitializePasses.h"45#include "llvm/MC/MCInstrDesc.h"46#include "llvm/MC/MCRegister.h"47#include "llvm/Pass.h"48#include "llvm/Support/Casting.h"49#include "llvm/Support/CommandLine.h"50#include "llvm/Support/Debug.h"51#include "llvm/Support/raw_ostream.h"52#include <cassert>53#include <limits>54#include <vector>55 56using namespace llvm;57 58#define DEBUG_TYPE "machinelicm"59 60static cl::opt<bool>61AvoidSpeculation("avoid-speculation",62 cl::desc("MachineLICM should avoid speculation"),63 cl::init(true), cl::Hidden);64 65static cl::opt<bool>66HoistCheapInsts("hoist-cheap-insts",67 cl::desc("MachineLICM should hoist even cheap instructions"),68 cl::init(false), cl::Hidden);69 70static cl::opt<bool>71HoistConstStores("hoist-const-stores",72 cl::desc("Hoist invariant stores"),73 cl::init(true), cl::Hidden);74 75static cl::opt<bool> HoistConstLoads("hoist-const-loads",76 cl::desc("Hoist invariant loads"),77 cl::init(true), cl::Hidden);78 79// The default threshold of 100 (i.e. if target block is 100 times hotter)80// is based on empirical data on a single target and is subject to tuning.81static cl::opt<unsigned>82BlockFrequencyRatioThreshold("block-freq-ratio-threshold",83 cl::desc("Do not hoist instructions if target"84 "block is N times hotter than the source."),85 cl::init(100), cl::Hidden);86 87enum class UseBFI { None, PGO, All };88 89static cl::opt<UseBFI>90DisableHoistingToHotterBlocks("disable-hoisting-to-hotter-blocks",91 cl::desc("Disable hoisting instructions to"92 " hotter blocks"),93 cl::init(UseBFI::PGO), cl::Hidden,94 cl::values(clEnumValN(UseBFI::None, "none",95 "disable the feature"),96 clEnumValN(UseBFI::PGO, "pgo",97 "enable the feature when using profile data"),98 clEnumValN(UseBFI::All, "all",99 "enable the feature with/wo profile data")));100 101STATISTIC(NumHoisted,102 "Number of machine instructions hoisted out of loops");103STATISTIC(NumLowRP,104 "Number of instructions hoisted in low reg pressure situation");105STATISTIC(NumHighLatency,106 "Number of high latency instructions hoisted");107STATISTIC(NumCSEed,108 "Number of hoisted machine instructions CSEed");109STATISTIC(NumPostRAHoisted,110 "Number of machine instructions hoisted out of loops post regalloc");111STATISTIC(NumStoreConst,112 "Number of stores of const phys reg hoisted out of loops");113STATISTIC(NumNotHoistedDueToHotness,114 "Number of instructions not hoisted due to block frequency");115 116namespace {117 enum HoistResult { NotHoisted = 1, Hoisted = 2, ErasedMI = 4 };118 119 class MachineLICMImpl {120 const TargetInstrInfo *TII = nullptr;121 const TargetLoweringBase *TLI = nullptr;122 const TargetRegisterInfo *TRI = nullptr;123 const MachineFrameInfo *MFI = nullptr;124 MachineRegisterInfo *MRI = nullptr;125 TargetSchedModel SchedModel;126 bool PreRegAlloc = false;127 bool HasProfileData = false;128 Pass *LegacyPass;129 MachineFunctionAnalysisManager *MFAM;130 131 // Various analyses that we use...132 AliasAnalysis *AA = nullptr; // Alias analysis info.133 MachineBlockFrequencyInfo *MBFI = nullptr; // Machine block frequncy info134 MachineLoopInfo *MLI = nullptr; // Current MachineLoopInfo135 MachineDomTreeUpdater *MDTU = nullptr; // Wraps current dominator tree136 137 // State that is updated as we process loops138 bool Changed = false; // True if a loop is changed.139 bool FirstInLoop = false; // True if it's the first LICM in the loop.140 141 // Holds information about whether it is allowed to move load instructions142 // out of the loop143 SmallDenseMap<MachineLoop *, bool> AllowedToHoistLoads;144 145 // Exit blocks of each Loop.146 DenseMap<MachineLoop *, SmallVector<MachineBasicBlock *, 8>> ExitBlockMap;147 148 bool isExitBlock(MachineLoop *CurLoop, const MachineBasicBlock *MBB) {149 auto [It, Inserted] = ExitBlockMap.try_emplace(CurLoop);150 if (Inserted) {151 SmallVector<MachineBasicBlock *, 8> ExitBlocks;152 CurLoop->getExitBlocks(ExitBlocks);153 It->second = std::move(ExitBlocks);154 }155 return is_contained(It->second, MBB);156 }157 158 // Track 'estimated' register pressure.159 SmallDenseSet<Register> RegSeen;160 SmallVector<unsigned, 8> RegPressure;161 162 // Register pressure "limit" per register pressure set. If the pressure163 // is higher than the limit, then it's considered high.164 SmallVector<unsigned, 8> RegLimit;165 166 // Register pressure on path leading from loop preheader to current BB.167 SmallVector<SmallVector<unsigned, 8>, 16> BackTrace;168 169 // For each opcode per preheader, keep a list of potential CSE instructions.170 DenseMap<MachineBasicBlock *,171 DenseMap<unsigned, std::vector<MachineInstr *>>>172 CSEMap;173 174 enum {175 SpeculateFalse = 0,176 SpeculateTrue = 1,177 SpeculateUnknown = 2178 };179 180 // If a MBB does not dominate loop exiting blocks then it may not safe181 // to hoist loads from this block.182 // Tri-state: 0 - false, 1 - true, 2 - unknown183 unsigned SpeculationState = SpeculateUnknown;184 185 public:186 MachineLICMImpl(bool PreRegAlloc, Pass *LegacyPass,187 MachineFunctionAnalysisManager *MFAM)188 : PreRegAlloc(PreRegAlloc), LegacyPass(LegacyPass), MFAM(MFAM) {189 assert((LegacyPass || MFAM) && "LegacyPass or MFAM must be provided");190 assert(!(LegacyPass && MFAM) &&191 "LegacyPass and MFAM cannot be provided at the same time");192 }193 194 bool run(MachineFunction &MF);195 196 void releaseMemory() {197 RegSeen.clear();198 RegPressure.clear();199 RegLimit.clear();200 BackTrace.clear();201 CSEMap.clear();202 ExitBlockMap.clear();203 }204 205 private:206 /// Keep track of information about hoisting candidates.207 struct CandidateInfo {208 MachineInstr *MI;209 Register Def;210 int FI;211 212 CandidateInfo(MachineInstr *mi, Register def, int fi)213 : MI(mi), Def(def), FI(fi) {}214 };215 216 void HoistRegionPostRA(MachineLoop *CurLoop);217 218 void HoistPostRA(MachineInstr *MI, Register Def, MachineLoop *CurLoop);219 220 void ProcessMI(MachineInstr *MI, BitVector &RUDefs, BitVector &RUClobbers,221 SmallDenseSet<int> &StoredFIs,222 SmallVectorImpl<CandidateInfo> &Candidates,223 MachineLoop *CurLoop);224 225 void AddToLiveIns(MCRegister Reg, MachineLoop *CurLoop);226 227 bool IsLICMCandidate(MachineInstr &I, MachineLoop *CurLoop);228 229 bool IsLoopInvariantInst(MachineInstr &I, MachineLoop *CurLoop);230 231 bool HasLoopPHIUse(const MachineInstr *MI, MachineLoop *CurLoop);232 233 bool HasHighOperandLatency(MachineInstr &MI, unsigned DefIdx, Register Reg,234 MachineLoop *CurLoop) const;235 236 bool IsCheapInstruction(MachineInstr &MI) const;237 238 bool CanCauseHighRegPressure(const SmallDenseMap<unsigned, int> &Cost,239 bool Cheap);240 241 void UpdateBackTraceRegPressure(const MachineInstr *MI);242 243 bool IsProfitableToHoist(MachineInstr &MI, MachineLoop *CurLoop);244 245 bool IsGuaranteedToExecute(MachineBasicBlock *BB, MachineLoop *CurLoop);246 247 void EnterScope(MachineBasicBlock *MBB);248 249 void ExitScope(MachineBasicBlock *MBB);250 251 void ExitScopeIfDone(252 MachineDomTreeNode *Node,253 DenseMap<MachineDomTreeNode *, unsigned> &OpenChildren,254 const DenseMap<MachineDomTreeNode *, MachineDomTreeNode *> &ParentMap);255 256 void HoistOutOfLoop(MachineDomTreeNode *HeaderN, MachineLoop *CurLoop);257 258 void InitRegPressure(MachineBasicBlock *BB);259 260 SmallDenseMap<unsigned, int> calcRegisterCost(const MachineInstr *MI,261 bool ConsiderSeen,262 bool ConsiderUnseenAsDef);263 264 void UpdateRegPressure(const MachineInstr *MI,265 bool ConsiderUnseenAsDef = false);266 267 MachineInstr *ExtractHoistableLoad(MachineInstr *MI, MachineLoop *CurLoop);268 269 MachineInstr *LookForDuplicate(const MachineInstr *MI,270 std::vector<MachineInstr *> &PrevMIs);271 272 bool273 EliminateCSE(MachineInstr *MI,274 DenseMap<unsigned, std::vector<MachineInstr *>>::iterator &CI);275 276 bool MayCSE(MachineInstr *MI);277 278 unsigned Hoist(MachineInstr *MI, MachineBasicBlock *Preheader,279 MachineLoop *CurLoop);280 281 void InitCSEMap(MachineBasicBlock *BB);282 283 void InitializeLoadsHoistableLoops();284 285 bool isTgtHotterThanSrc(MachineBasicBlock *SrcBlock,286 MachineBasicBlock *TgtBlock);287 MachineBasicBlock *getOrCreatePreheader(MachineLoop *CurLoop);288 };289 290 class MachineLICMBase : public MachineFunctionPass {291 bool PreRegAlloc;292 293 public:294 MachineLICMBase(char &ID, bool PreRegAlloc)295 : MachineFunctionPass(ID), PreRegAlloc(PreRegAlloc) {}296 297 bool runOnMachineFunction(MachineFunction &MF) override;298 299 void getAnalysisUsage(AnalysisUsage &AU) const override {300 AU.addRequired<MachineLoopInfoWrapperPass>();301 if (DisableHoistingToHotterBlocks != UseBFI::None)302 AU.addRequired<MachineBlockFrequencyInfoWrapperPass>();303 AU.addRequired<MachineDominatorTreeWrapperPass>();304 AU.addRequired<AAResultsWrapperPass>();305 AU.addPreserved<MachineLoopInfoWrapperPass>();306 MachineFunctionPass::getAnalysisUsage(AU);307 }308 };309 310 class MachineLICM : public MachineLICMBase {311 public:312 static char ID;313 MachineLICM() : MachineLICMBase(ID, false) {314 initializeMachineLICMPass(*PassRegistry::getPassRegistry());315 }316 };317 318 class EarlyMachineLICM : public MachineLICMBase {319 public:320 static char ID;321 EarlyMachineLICM() : MachineLICMBase(ID, true) {322 initializeEarlyMachineLICMPass(*PassRegistry::getPassRegistry());323 }324 };325 326} // end anonymous namespace327 328char MachineLICM::ID;329char EarlyMachineLICM::ID;330 331char &llvm::MachineLICMID = MachineLICM::ID;332char &llvm::EarlyMachineLICMID = EarlyMachineLICM::ID;333 334INITIALIZE_PASS_BEGIN(MachineLICM, DEBUG_TYPE,335 "Machine Loop Invariant Code Motion", false, false)336INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)337INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfoWrapperPass)338INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)339INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)340INITIALIZE_PASS_END(MachineLICM, DEBUG_TYPE,341 "Machine Loop Invariant Code Motion", false, false)342 343INITIALIZE_PASS_BEGIN(EarlyMachineLICM, "early-machinelicm",344 "Early Machine Loop Invariant Code Motion", false, false)345INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)346INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfoWrapperPass)347INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)348INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)349INITIALIZE_PASS_END(EarlyMachineLICM, "early-machinelicm",350 "Early Machine Loop Invariant Code Motion", false, false)351 352bool MachineLICMBase::runOnMachineFunction(MachineFunction &MF) {353 if (skipFunction(MF.getFunction()))354 return false;355 356 MachineLICMImpl Impl(PreRegAlloc, this, nullptr);357 return Impl.run(MF);358}359 360#define GET_RESULT(RESULT, GETTER, INFIX) \361 ((LegacyPass) \362 ? &LegacyPass->getAnalysis<RESULT##INFIX##WrapperPass>().GETTER() \363 : &MFAM->getResult<RESULT##Analysis>(MF))364 365bool MachineLICMImpl::run(MachineFunction &MF) {366 AA = MFAM != nullptr367 ? &MFAM->getResult<FunctionAnalysisManagerMachineFunctionProxy>(MF)368 .getManager()369 .getResult<AAManager>(MF.getFunction())370 : &LegacyPass->getAnalysis<AAResultsWrapperPass>().getAAResults();371 MachineDomTreeUpdater DTU(GET_RESULT(MachineDominatorTree, getDomTree, ),372 MachineDomTreeUpdater::UpdateStrategy::Lazy);373 MDTU = &DTU;374 MLI = GET_RESULT(MachineLoop, getLI, Info);375 MBFI = DisableHoistingToHotterBlocks != UseBFI::None376 ? GET_RESULT(MachineBlockFrequency, getMBFI, Info)377 : nullptr;378 379 Changed = FirstInLoop = false;380 const TargetSubtargetInfo &ST = MF.getSubtarget();381 TII = ST.getInstrInfo();382 TLI = ST.getTargetLowering();383 TRI = ST.getRegisterInfo();384 MFI = &MF.getFrameInfo();385 MRI = &MF.getRegInfo();386 SchedModel.init(&ST);387 388 HasProfileData = MF.getFunction().hasProfileData();389 390 if (PreRegAlloc)391 LLVM_DEBUG(dbgs() << "******** Pre-regalloc Machine LICM: ");392 else393 LLVM_DEBUG(dbgs() << "******** Post-regalloc Machine LICM: ");394 LLVM_DEBUG(dbgs() << MF.getName() << " ********\n");395 396 if (PreRegAlloc) {397 // Estimate register pressure during pre-regalloc pass.398 unsigned NumRPS = TRI->getNumRegPressureSets();399 RegPressure.resize(NumRPS);400 llvm::fill(RegPressure, 0);401 RegLimit.resize(NumRPS);402 for (unsigned i = 0, e = NumRPS; i != e; ++i)403 RegLimit[i] = TRI->getRegPressureSetLimit(MF, i);404 }405 406 if (HoistConstLoads)407 InitializeLoadsHoistableLoops();408 409 SmallVector<MachineLoop *, 8> Worklist(MLI->begin(), MLI->end());410 while (!Worklist.empty()) {411 MachineLoop *CurLoop = Worklist.pop_back_val();412 413 if (!PreRegAlloc) {414 HoistRegionPostRA(CurLoop);415 } else {416 // CSEMap is initialized for loop header when the first instruction is417 // being hoisted.418 MachineDomTreeNode *N = MDTU->getDomTree().getNode(CurLoop->getHeader());419 FirstInLoop = true;420 HoistOutOfLoop(N, CurLoop);421 CSEMap.clear();422 }423 }424 releaseMemory();425 return Changed;426}427 428/// Return true if instruction stores to the specified frame.429static bool InstructionStoresToFI(const MachineInstr *MI, int FI) {430 // Check mayStore before memory operands so that e.g. DBG_VALUEs will return431 // true since they have no memory operands.432 if (!MI->mayStore())433 return false;434 // If we lost memory operands, conservatively assume that the instruction435 // writes to all slots.436 if (MI->memoperands_empty())437 return true;438 for (const MachineMemOperand *MemOp : MI->memoperands()) {439 if (!MemOp->isStore() || !MemOp->getPseudoValue())440 continue;441 if (const FixedStackPseudoSourceValue *Value =442 dyn_cast<FixedStackPseudoSourceValue>(MemOp->getPseudoValue())) {443 if (Value->getFrameIndex() == FI)444 return true;445 }446 }447 return false;448}449 450static void applyBitsNotInRegMaskToRegUnitsMask(const TargetRegisterInfo &TRI,451 BitVector &RUs,452 const uint32_t *Mask) {453 // FIXME: This intentionally works in reverse due to some issues with the454 // Register Units infrastructure.455 //456 // This is used to apply callee-saved-register masks to the clobbered regunits457 // mask.458 //459 // The right way to approach this is to start with a BitVector full of ones,460 // then reset all the bits of the regunits of each register that is set in the461 // mask (registers preserved), then OR the resulting bits with the Clobbers462 // mask. This correctly prioritizes the saved registers, so if a RU is shared463 // between a register that is preserved, and one that is NOT preserved, that464 // RU will not be set in the output vector (the clobbers).465 //466 // What we have to do for now is the opposite: we have to assume that the467 // regunits of all registers that are NOT preserved are clobbered, even if468 // those regunits are preserved by another register. So if a RU is shared469 // like described previously, that RU will be set.470 //471 // This is to work around an issue which appears in AArch64, but isn't472 // exclusive to that target: AArch64's Qn registers (128 bits) have Dn473 // register (lower 64 bits). A few Dn registers are preserved by some calling474 // conventions, but Qn and Dn share exactly the same reg units.475 //476 // If we do this the right way, Qn will be marked as NOT clobbered even though477 // its upper 64 bits are NOT preserved. The conservative approach handles this478 // correctly at the cost of some missed optimizations on other targets.479 //480 // This is caused by how RegUnits are handled within TableGen. Ideally, Qn481 // should have an extra RegUnit to model the "unknown" bits not covered by the482 // subregs.483 BitVector RUsFromRegsNotInMask(TRI.getNumRegUnits());484 const unsigned NumRegs = TRI.getNumRegs();485 const unsigned MaskWords = (NumRegs + 31) / 32;486 for (unsigned K = 0; K < MaskWords; ++K) {487 const uint32_t Word = Mask[K];488 for (unsigned Bit = 0; Bit < 32; ++Bit) {489 const unsigned PhysReg = (K * 32) + Bit;490 if (PhysReg == NumRegs)491 break;492 493 if (PhysReg && !((Word >> Bit) & 1)) {494 for (MCRegUnit Unit : TRI.regunits(PhysReg))495 RUsFromRegsNotInMask.set(static_cast<unsigned>(Unit));496 }497 }498 }499 500 RUs |= RUsFromRegsNotInMask;501}502 503/// Examine the instruction for potential LICM candidate. Also504/// gather register def and frame object update information.505void MachineLICMImpl::ProcessMI(MachineInstr *MI, BitVector &RUDefs,506 BitVector &RUClobbers,507 SmallDenseSet<int> &StoredFIs,508 SmallVectorImpl<CandidateInfo> &Candidates,509 MachineLoop *CurLoop) {510 bool RuledOut = false;511 bool HasNonInvariantUse = false;512 Register Def;513 for (const MachineOperand &MO : MI->operands()) {514 if (MO.isFI()) {515 // Remember if the instruction stores to the frame index.516 int FI = MO.getIndex();517 if (!StoredFIs.count(FI) &&518 MFI->isSpillSlotObjectIndex(FI) &&519 InstructionStoresToFI(MI, FI))520 StoredFIs.insert(FI);521 HasNonInvariantUse = true;522 continue;523 }524 525 // We can't hoist an instruction defining a physreg that is clobbered in526 // the loop.527 if (MO.isRegMask()) {528 applyBitsNotInRegMaskToRegUnitsMask(*TRI, RUClobbers, MO.getRegMask());529 continue;530 }531 532 if (!MO.isReg())533 continue;534 Register Reg = MO.getReg();535 if (!Reg)536 continue;537 assert(Reg.isPhysical() && "Not expecting virtual register!");538 539 if (!MO.isDef()) {540 if (!HasNonInvariantUse) {541 for (MCRegUnit Unit : TRI->regunits(Reg)) {542 // If it's using a non-loop-invariant register, then it's obviously543 // not safe to hoist.544 if (RUDefs.test(static_cast<unsigned>(Unit)) ||545 RUClobbers.test(static_cast<unsigned>(Unit))) {546 HasNonInvariantUse = true;547 break;548 }549 }550 }551 continue;552 }553 554 // FIXME: For now, avoid instructions with multiple defs, unless it's dead.555 if (!MO.isDead()) {556 if (Def)557 RuledOut = true;558 else559 Def = Reg;560 }561 562 // If we have already seen another instruction that defines the same563 // register, then this is not safe. Two defs is indicated by setting a564 // PhysRegClobbers bit.565 for (MCRegUnit Unit : TRI->regunits(Reg)) {566 if (RUDefs.test(static_cast<unsigned>(Unit))) {567 RUClobbers.set(static_cast<unsigned>(Unit));568 RuledOut = true;569 } else if (RUClobbers.test(static_cast<unsigned>(Unit))) {570 // MI defined register is seen defined by another instruction in571 // the loop, it cannot be a LICM candidate.572 RuledOut = true;573 }574 575 RUDefs.set(static_cast<unsigned>(Unit));576 }577 }578 579 // Only consider reloads for now and remats which do not have register580 // operands. FIXME: Consider unfold load folding instructions.581 if (Def && !RuledOut) {582 int FI = std::numeric_limits<int>::min();583 if ((!HasNonInvariantUse && IsLICMCandidate(*MI, CurLoop)) ||584 (TII->isLoadFromStackSlot(*MI, FI) && MFI->isSpillSlotObjectIndex(FI)))585 Candidates.push_back(CandidateInfo(MI, Def, FI));586 }587}588 589/// Walk the specified region of the CFG and hoist loop invariants out to the590/// preheader.591void MachineLICMImpl::HoistRegionPostRA(MachineLoop *CurLoop) {592 MachineBasicBlock *Preheader = getOrCreatePreheader(CurLoop);593 if (!Preheader)594 return;595 596 unsigned NumRegUnits = TRI->getNumRegUnits();597 BitVector RUDefs(NumRegUnits); // RUs defined once in the loop.598 BitVector RUClobbers(NumRegUnits); // RUs defined more than once.599 600 SmallVector<CandidateInfo, 32> Candidates;601 SmallDenseSet<int> StoredFIs;602 603 // Walk the entire region, count number of defs for each register, and604 // collect potential LICM candidates.605 for (MachineBasicBlock *BB : CurLoop->getBlocks()) {606 // If the header of the loop containing this basic block is a landing pad,607 // then don't try to hoist instructions out of this loop.608 const MachineLoop *ML = MLI->getLoopFor(BB);609 if (ML && ML->getHeader()->isEHPad()) continue;610 611 // Conservatively treat live-in's as an external def.612 // FIXME: That means a reload that're reused in successor block(s) will not613 // be LICM'ed.614 for (const auto &LI : BB->liveins()) {615 for (MCRegUnit Unit : TRI->regunits(LI.PhysReg))616 RUDefs.set(static_cast<unsigned>(Unit));617 }618 619 // Funclet entry blocks will clobber all registers620 if (const uint32_t *Mask = BB->getBeginClobberMask(TRI))621 applyBitsNotInRegMaskToRegUnitsMask(*TRI, RUClobbers, Mask);622 623 // EH landing pads clobber exception pointer/selector registers.624 if (BB->isEHPad()) {625 const MachineFunction &MF = *BB->getParent();626 const Constant *PersonalityFn = MF.getFunction().getPersonalityFn();627 const TargetLowering &TLI = *MF.getSubtarget().getTargetLowering();628 if (MCRegister Reg = TLI.getExceptionPointerRegister(PersonalityFn))629 for (MCRegUnit Unit : TRI->regunits(Reg))630 RUClobbers.set(static_cast<unsigned>(Unit));631 if (MCRegister Reg = TLI.getExceptionSelectorRegister(PersonalityFn))632 for (MCRegUnit Unit : TRI->regunits(Reg))633 RUClobbers.set(static_cast<unsigned>(Unit));634 }635 636 SpeculationState = SpeculateUnknown;637 for (MachineInstr &MI : *BB)638 ProcessMI(&MI, RUDefs, RUClobbers, StoredFIs, Candidates, CurLoop);639 }640 641 // Gather the registers read / clobbered by the terminator.642 BitVector TermRUs(NumRegUnits);643 MachineBasicBlock::iterator TI = Preheader->getFirstTerminator();644 if (TI != Preheader->end()) {645 for (const MachineOperand &MO : TI->operands()) {646 if (!MO.isReg())647 continue;648 Register Reg = MO.getReg();649 if (!Reg)650 continue;651 for (MCRegUnit Unit : TRI->regunits(Reg))652 TermRUs.set(static_cast<unsigned>(Unit));653 }654 }655 656 // Now evaluate whether the potential candidates qualify.657 // 1. Check if the candidate defined register is defined by another658 // instruction in the loop.659 // 2. If the candidate is a load from stack slot (always true for now),660 // check if the slot is stored anywhere in the loop.661 // 3. Make sure candidate def should not clobber662 // registers read by the terminator. Similarly its def should not be663 // clobbered by the terminator.664 for (CandidateInfo &Candidate : Candidates) {665 if (Candidate.FI != std::numeric_limits<int>::min() &&666 StoredFIs.count(Candidate.FI))667 continue;668 669 Register Def = Candidate.Def;670 bool Safe = true;671 for (MCRegUnit Unit : TRI->regunits(Def)) {672 if (RUClobbers.test(static_cast<unsigned>(Unit)) ||673 TermRUs.test(static_cast<unsigned>(Unit))) {674 Safe = false;675 break;676 }677 }678 679 if (!Safe)680 continue;681 682 MachineInstr *MI = Candidate.MI;683 for (const MachineOperand &MO : MI->all_uses()) {684 if (!MO.getReg())685 continue;686 for (MCRegUnit Unit : TRI->regunits(MO.getReg())) {687 if (RUDefs.test(static_cast<unsigned>(Unit)) ||688 RUClobbers.test(static_cast<unsigned>(Unit))) {689 // If it's using a non-loop-invariant register, then it's obviously690 // not safe to hoist.691 Safe = false;692 break;693 }694 }695 696 if (!Safe)697 break;698 }699 700 if (Safe)701 HoistPostRA(MI, Candidate.Def, CurLoop);702 }703}704 705/// Add register 'Reg' to the livein sets of BBs in the current loop, and make706/// sure it is not killed by any instructions in the loop.707void MachineLICMImpl::AddToLiveIns(MCRegister Reg, MachineLoop *CurLoop) {708 for (MachineBasicBlock *BB : CurLoop->getBlocks()) {709 if (!BB->isLiveIn(Reg))710 BB->addLiveIn(Reg);711 for (MachineInstr &MI : *BB) {712 for (MachineOperand &MO : MI.all_uses()) {713 if (!MO.getReg())714 continue;715 if (TRI->regsOverlap(Reg, MO.getReg()))716 MO.setIsKill(false);717 }718 }719 }720}721 722/// When an instruction is found to only use loop invariant operands that is723/// safe to hoist, this instruction is called to do the dirty work.724void MachineLICMImpl::HoistPostRA(MachineInstr *MI, Register Def,725 MachineLoop *CurLoop) {726 MachineBasicBlock *Preheader = CurLoop->getLoopPreheader();727 728 // Now move the instructions to the predecessor, inserting it before any729 // terminator instructions.730 LLVM_DEBUG(dbgs() << "Hoisting to " << printMBBReference(*Preheader)731 << " from " << printMBBReference(*MI->getParent()) << ": "732 << *MI);733 734 // Splice the instruction to the preheader.735 MachineBasicBlock *MBB = MI->getParent();736 Preheader->splice(Preheader->getFirstTerminator(), MBB, MI);737 738 // Since we are moving the instruction out of its basic block, we do not739 // retain its debug location. Doing so would degrade the debugging740 // experience and adversely affect the accuracy of profiling information.741 assert(!MI->isDebugInstr() && "Should not hoist debug inst");742 MI->setDebugLoc(DebugLoc());743 744 // Add register to livein list to all the BBs in the current loop since a745 // loop invariant must be kept live throughout the whole loop. This is746 // important to ensure later passes do not scavenge the def register.747 AddToLiveIns(Def, CurLoop);748 749 ++NumPostRAHoisted;750 Changed = true;751}752 753/// Check if this mbb is guaranteed to execute. If not then a load from this mbb754/// may not be safe to hoist.755bool MachineLICMImpl::IsGuaranteedToExecute(MachineBasicBlock *BB,756 MachineLoop *CurLoop) {757 if (SpeculationState != SpeculateUnknown)758 return SpeculationState == SpeculateFalse;759 760 if (BB != CurLoop->getHeader()) {761 // Check loop exiting blocks.762 SmallVector<MachineBasicBlock*, 8> CurrentLoopExitingBlocks;763 CurLoop->getExitingBlocks(CurrentLoopExitingBlocks);764 for (MachineBasicBlock *CurrentLoopExitingBlock : CurrentLoopExitingBlocks)765 if (!MDTU->getDomTree().dominates(BB, CurrentLoopExitingBlock)) {766 SpeculationState = SpeculateTrue;767 return false;768 }769 }770 771 SpeculationState = SpeculateFalse;772 return true;773}774 775void MachineLICMImpl::EnterScope(MachineBasicBlock *MBB) {776 LLVM_DEBUG(dbgs() << "Entering " << printMBBReference(*MBB) << '\n');777 778 // Remember livein register pressure.779 BackTrace.push_back(RegPressure);780}781 782void MachineLICMImpl::ExitScope(MachineBasicBlock *MBB) {783 LLVM_DEBUG(dbgs() << "Exiting " << printMBBReference(*MBB) << '\n');784 BackTrace.pop_back();785}786 787/// Destroy scope for the MBB that corresponds to the given dominator tree node788/// if its a leaf or all of its children are done. Walk up the dominator tree to789/// destroy ancestors which are now done.790void MachineLICMImpl::ExitScopeIfDone(791 MachineDomTreeNode *Node,792 DenseMap<MachineDomTreeNode *, unsigned> &OpenChildren,793 const DenseMap<MachineDomTreeNode *, MachineDomTreeNode *> &ParentMap) {794 if (OpenChildren[Node])795 return;796 797 for(;;) {798 ExitScope(Node->getBlock());799 // Now traverse upwards to pop ancestors whose offsprings are all done.800 MachineDomTreeNode *Parent = ParentMap.lookup(Node);801 if (!Parent || --OpenChildren[Parent] != 0)802 break;803 Node = Parent;804 }805}806 807/// Walk the specified loop in the CFG (defined by all blocks dominated by the808/// specified header block, and that are in the current loop) in depth first809/// order w.r.t the DominatorTree. This allows us to visit definitions before810/// uses, allowing us to hoist a loop body in one pass without iteration.811void MachineLICMImpl::HoistOutOfLoop(MachineDomTreeNode *HeaderN,812 MachineLoop *CurLoop) {813 MachineBasicBlock *Preheader = getOrCreatePreheader(CurLoop);814 if (!Preheader)815 return;816 817 SmallVector<MachineDomTreeNode*, 32> Scopes;818 SmallVector<MachineDomTreeNode*, 8> WorkList;819 DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> ParentMap;820 DenseMap<MachineDomTreeNode*, unsigned> OpenChildren;821 822 // Perform a DFS walk to determine the order of visit.823 WorkList.push_back(HeaderN);824 while (!WorkList.empty()) {825 MachineDomTreeNode *Node = WorkList.pop_back_val();826 assert(Node && "Null dominator tree node?");827 MachineBasicBlock *BB = Node->getBlock();828 829 // If the header of the loop containing this basic block is a landing pad,830 // then don't try to hoist instructions out of this loop.831 const MachineLoop *ML = MLI->getLoopFor(BB);832 if (ML && ML->getHeader()->isEHPad())833 continue;834 835 // If this subregion is not in the top level loop at all, exit.836 if (!CurLoop->contains(BB))837 continue;838 839 Scopes.push_back(Node);840 unsigned NumChildren = Node->getNumChildren();841 842 // Don't hoist things out of a large switch statement. This often causes843 // code to be hoisted that wasn't going to be executed, and increases844 // register pressure in a situation where it's likely to matter.845 if (BB->succ_size() >= 25)846 NumChildren = 0;847 848 OpenChildren[Node] = NumChildren;849 if (NumChildren) {850 // Add children in reverse order as then the next popped worklist node is851 // the first child of this node. This means we ultimately traverse the852 // DOM tree in exactly the same order as if we'd recursed.853 for (MachineDomTreeNode *Child : reverse(Node->children())) {854 ParentMap[Child] = Node;855 WorkList.push_back(Child);856 }857 }858 }859 860 if (Scopes.size() == 0)861 return;862 863 // Compute registers which are livein into the loop headers.864 RegSeen.clear();865 BackTrace.clear();866 InitRegPressure(Preheader);867 868 // Now perform LICM.869 for (MachineDomTreeNode *Node : Scopes) {870 MachineBasicBlock *MBB = Node->getBlock();871 872 EnterScope(MBB);873 874 // Process the block875 SpeculationState = SpeculateUnknown;876 for (MachineInstr &MI : llvm::make_early_inc_range(*MBB)) {877 unsigned HoistRes = HoistResult::NotHoisted;878 HoistRes = Hoist(&MI, Preheader, CurLoop);879 if (HoistRes & HoistResult::NotHoisted) {880 // We have failed to hoist MI to outermost loop's preheader. If MI is in881 // a subloop, try to hoist it to subloop's preheader.882 SmallVector<MachineLoop *> InnerLoopWorkList;883 for (MachineLoop *L = MLI->getLoopFor(MI.getParent()); L != CurLoop;884 L = L->getParentLoop())885 InnerLoopWorkList.push_back(L);886 887 while (!InnerLoopWorkList.empty()) {888 MachineLoop *InnerLoop = InnerLoopWorkList.pop_back_val();889 MachineBasicBlock *InnerLoopPreheader = InnerLoop->getLoopPreheader();890 if (InnerLoopPreheader) {891 HoistRes = Hoist(&MI, InnerLoopPreheader, InnerLoop);892 if (HoistRes & HoistResult::Hoisted)893 break;894 }895 }896 }897 898 if (HoistRes & HoistResult::ErasedMI)899 continue;900 901 UpdateRegPressure(&MI);902 }903 904 // If it's a leaf node, it's done. Traverse upwards to pop ancestors.905 ExitScopeIfDone(Node, OpenChildren, ParentMap);906 }907}908 909static bool isOperandKill(const MachineOperand &MO, MachineRegisterInfo *MRI) {910 return MO.isKill() || MRI->hasOneNonDBGUse(MO.getReg());911}912 913/// Find all virtual register references that are liveout of the preheader to914/// initialize the starting "register pressure". Note this does not count live915/// through (livein but not used) registers.916void MachineLICMImpl::InitRegPressure(MachineBasicBlock *BB) {917 llvm::fill(RegPressure, 0);918 919 // If the preheader has only a single predecessor and it ends with a920 // fallthrough or an unconditional branch, then scan its predecessor for live921 // defs as well. This happens whenever the preheader is created by splitting922 // the critical edge from the loop predecessor to the loop header.923 if (BB->pred_size() == 1) {924 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;925 SmallVector<MachineOperand, 4> Cond;926 if (!TII->analyzeBranch(*BB, TBB, FBB, Cond, false) && Cond.empty())927 InitRegPressure(*BB->pred_begin());928 }929 930 for (const MachineInstr &MI : *BB)931 UpdateRegPressure(&MI, /*ConsiderUnseenAsDef=*/true);932}933 934/// Update estimate of register pressure after the specified instruction.935void MachineLICMImpl::UpdateRegPressure(const MachineInstr *MI,936 bool ConsiderUnseenAsDef) {937 auto Cost = calcRegisterCost(MI, /*ConsiderSeen=*/true, ConsiderUnseenAsDef);938 for (const auto &[Class, Weight] : Cost) {939 if (static_cast<int>(RegPressure[Class]) < -Weight)940 RegPressure[Class] = 0;941 else942 RegPressure[Class] += Weight;943 }944}945 946/// Calculate the additional register pressure that the registers used in MI947/// cause.948///949/// If 'ConsiderSeen' is true, updates 'RegSeen' and uses the information to950/// figure out which usages are live-ins.951/// FIXME: Figure out a way to consider 'RegSeen' from all code paths.952SmallDenseMap<unsigned, int>953MachineLICMImpl::calcRegisterCost(const MachineInstr *MI, bool ConsiderSeen,954 bool ConsiderUnseenAsDef) {955 SmallDenseMap<unsigned, int> Cost;956 if (MI->isImplicitDef())957 return Cost;958 for (unsigned i = 0, e = MI->getDesc().getNumOperands(); i != e; ++i) {959 const MachineOperand &MO = MI->getOperand(i);960 if (!MO.isReg() || MO.isImplicit())961 continue;962 Register Reg = MO.getReg();963 if (!Reg.isVirtual())964 continue;965 966 // FIXME: It seems bad to use RegSeen only for some of these calculations.967 bool isNew = ConsiderSeen ? RegSeen.insert(Reg).second : false;968 const TargetRegisterClass *RC = MRI->getRegClass(Reg);969 970 RegClassWeight W = TRI->getRegClassWeight(RC);971 int RCCost = 0;972 if (MO.isDef())973 RCCost = W.RegWeight;974 else {975 bool isKill = isOperandKill(MO, MRI);976 if (isNew && !isKill && ConsiderUnseenAsDef)977 // Haven't seen this, it must be a livein.978 RCCost = W.RegWeight;979 else if (!isNew && isKill)980 RCCost = -W.RegWeight;981 }982 if (RCCost == 0)983 continue;984 const int *PS = TRI->getRegClassPressureSets(RC);985 for (; *PS != -1; ++PS)986 Cost[*PS] += RCCost;987 }988 return Cost;989}990 991/// Return true if this machine instruction loads from global offset table or992/// constant pool.993static bool mayLoadFromGOTOrConstantPool(MachineInstr &MI) {994 assert(MI.mayLoad() && "Expected MI that loads!");995 996 // If we lost memory operands, conservatively assume that the instruction997 // reads from everything..998 if (MI.memoperands_empty())999 return true;1000 1001 for (MachineMemOperand *MemOp : MI.memoperands())1002 if (const PseudoSourceValue *PSV = MemOp->getPseudoValue())1003 if (PSV->isGOT() || PSV->isConstantPool())1004 return true;1005 1006 return false;1007}1008 1009// This function iterates through all the operands of the input store MI and1010// checks that each register operand statisfies isCallerPreservedPhysReg.1011// This means, the value being stored and the address where it is being stored1012// is constant throughout the body of the function (not including prologue and1013// epilogue). When called with an MI that isn't a store, it returns false.1014// A future improvement can be to check if the store registers are constant1015// throughout the loop rather than throughout the funtion.1016static bool isInvariantStore(const MachineInstr &MI,1017 const TargetRegisterInfo *TRI,1018 const MachineRegisterInfo *MRI) {1019 1020 bool FoundCallerPresReg = false;1021 if (!MI.mayStore() || MI.hasUnmodeledSideEffects() ||1022 (MI.getNumOperands() == 0))1023 return false;1024 1025 // Check that all register operands are caller-preserved physical registers.1026 for (const MachineOperand &MO : MI.operands()) {1027 if (MO.isReg()) {1028 Register Reg = MO.getReg();1029 // If operand is a virtual register, check if it comes from a copy of a1030 // physical register.1031 if (Reg.isVirtual())1032 Reg = TRI->lookThruCopyLike(MO.getReg(), MRI);1033 if (Reg.isVirtual())1034 return false;1035 if (!TRI->isCallerPreservedPhysReg(Reg.asMCReg(), *MI.getMF()))1036 return false;1037 else1038 FoundCallerPresReg = true;1039 } else if (!MO.isImm()) {1040 return false;1041 }1042 }1043 return FoundCallerPresReg;1044}1045 1046// Return true if the input MI is a copy instruction that feeds an invariant1047// store instruction. This means that the src of the copy has to satisfy1048// isCallerPreservedPhysReg and atleast one of it's users should satisfy1049// isInvariantStore.1050static bool isCopyFeedingInvariantStore(const MachineInstr &MI,1051 const MachineRegisterInfo *MRI,1052 const TargetRegisterInfo *TRI) {1053 1054 // FIXME: If targets would like to look through instructions that aren't1055 // pure copies, this can be updated to a query.1056 if (!MI.isCopy())1057 return false;1058 1059 const MachineFunction *MF = MI.getMF();1060 // Check that we are copying a constant physical register.1061 Register CopySrcReg = MI.getOperand(1).getReg();1062 if (CopySrcReg.isVirtual())1063 return false;1064 1065 if (!TRI->isCallerPreservedPhysReg(CopySrcReg.asMCReg(), *MF))1066 return false;1067 1068 Register CopyDstReg = MI.getOperand(0).getReg();1069 // Check if any of the uses of the copy are invariant stores.1070 assert(CopyDstReg.isVirtual() && "copy dst is not a virtual reg");1071 1072 for (MachineInstr &UseMI : MRI->use_instructions(CopyDstReg)) {1073 if (UseMI.mayStore() && isInvariantStore(UseMI, TRI, MRI))1074 return true;1075 }1076 return false;1077}1078 1079/// Returns true if the instruction may be a suitable candidate for LICM.1080/// e.g. If the instruction is a call, then it's obviously not safe to hoist it.1081bool MachineLICMImpl::IsLICMCandidate(MachineInstr &I, MachineLoop *CurLoop) {1082 // Check if it's safe to move the instruction.1083 bool DontMoveAcrossStore = !HoistConstLoads || !AllowedToHoistLoads[CurLoop];1084 if ((!I.isSafeToMove(DontMoveAcrossStore)) &&1085 !(HoistConstStores && isInvariantStore(I, TRI, MRI))) {1086 LLVM_DEBUG(dbgs() << "LICM: Instruction not safe to move.\n");1087 return false;1088 }1089 1090 // If it is a load then check if it is guaranteed to execute by making sure1091 // that it dominates all exiting blocks. If it doesn't, then there is a path1092 // out of the loop which does not execute this load, so we can't hoist it.1093 // Loads from constant memory are safe to speculate, for example indexed load1094 // from a jump table.1095 // Stores and side effects are already checked by isSafeToMove.1096 if (I.mayLoad() && !mayLoadFromGOTOrConstantPool(I) &&1097 !IsGuaranteedToExecute(I.getParent(), CurLoop)) {1098 LLVM_DEBUG(dbgs() << "LICM: Load not guaranteed to execute.\n");1099 return false;1100 }1101 1102 // Convergent attribute has been used on operations that involve inter-thread1103 // communication which results are implicitly affected by the enclosing1104 // control flows. It is not safe to hoist or sink such operations across1105 // control flow.1106 if (I.isConvergent())1107 return false;1108 1109 if (!TII->shouldHoist(I, CurLoop))1110 return false;1111 1112 return true;1113}1114 1115/// Returns true if the instruction is loop invariant.1116bool MachineLICMImpl::IsLoopInvariantInst(MachineInstr &I,1117 MachineLoop *CurLoop) {1118 if (!IsLICMCandidate(I, CurLoop)) {1119 LLVM_DEBUG(dbgs() << "LICM: Instruction not a LICM candidate\n");1120 return false;1121 }1122 return CurLoop->isLoopInvariant(I);1123}1124 1125/// Return true if the specified instruction is used by a phi node and hoisting1126/// it could cause a copy to be inserted.1127bool MachineLICMImpl::HasLoopPHIUse(const MachineInstr *MI,1128 MachineLoop *CurLoop) {1129 SmallVector<const MachineInstr *, 8> Work(1, MI);1130 do {1131 MI = Work.pop_back_val();1132 for (const MachineOperand &MO : MI->all_defs()) {1133 Register Reg = MO.getReg();1134 if (!Reg.isVirtual())1135 continue;1136 for (MachineInstr &UseMI : MRI->use_instructions(Reg)) {1137 // A PHI may cause a copy to be inserted.1138 if (UseMI.isPHI()) {1139 // A PHI inside the loop causes a copy because the live range of Reg is1140 // extended across the PHI.1141 if (CurLoop->contains(&UseMI))1142 return true;1143 // A PHI in an exit block can cause a copy to be inserted if the PHI1144 // has multiple predecessors in the loop with different values.1145 // For now, approximate by rejecting all exit blocks.1146 if (isExitBlock(CurLoop, UseMI.getParent()))1147 return true;1148 continue;1149 }1150 // Look past copies as well.1151 if (UseMI.isCopy() && CurLoop->contains(&UseMI))1152 Work.push_back(&UseMI);1153 }1154 }1155 } while (!Work.empty());1156 return false;1157}1158 1159/// Compute operand latency between a def of 'Reg' and an use in the current1160/// loop, return true if the target considered it high.1161bool MachineLICMImpl::HasHighOperandLatency(MachineInstr &MI, unsigned DefIdx,1162 Register Reg,1163 MachineLoop *CurLoop) const {1164 if (MRI->use_nodbg_empty(Reg))1165 return false;1166 1167 for (MachineInstr &UseMI : MRI->use_nodbg_instructions(Reg)) {1168 if (UseMI.isCopyLike())1169 continue;1170 if (!CurLoop->contains(UseMI.getParent()))1171 continue;1172 for (unsigned i = 0, e = UseMI.getNumOperands(); i != e; ++i) {1173 const MachineOperand &MO = UseMI.getOperand(i);1174 if (!MO.isReg() || !MO.isUse())1175 continue;1176 Register MOReg = MO.getReg();1177 if (MOReg != Reg)1178 continue;1179 1180 if (TII->hasHighOperandLatency(SchedModel, MRI, MI, DefIdx, UseMI, i))1181 return true;1182 }1183 1184 // Only look at the first in loop use.1185 break;1186 }1187 1188 return false;1189}1190 1191/// Return true if the instruction is marked "cheap" or the operand latency1192/// between its def and a use is one or less.1193bool MachineLICMImpl::IsCheapInstruction(MachineInstr &MI) const {1194 if (TII->isAsCheapAsAMove(MI) || MI.isSubregToReg())1195 return true;1196 1197 bool isCheap = false;1198 unsigned NumDefs = MI.getDesc().getNumDefs();1199 for (unsigned i = 0, e = MI.getNumOperands(); NumDefs && i != e; ++i) {1200 MachineOperand &DefMO = MI.getOperand(i);1201 if (!DefMO.isReg() || !DefMO.isDef())1202 continue;1203 --NumDefs;1204 Register Reg = DefMO.getReg();1205 if (Reg.isPhysical())1206 continue;1207 1208 if (!TII->hasLowDefLatency(SchedModel, MI, i))1209 return false;1210 isCheap = true;1211 }1212 1213 return isCheap;1214}1215 1216/// Visit BBs from header to current BB, check if hoisting an instruction of the1217/// given cost matrix can cause high register pressure.1218bool MachineLICMImpl::CanCauseHighRegPressure(1219 const SmallDenseMap<unsigned, int> &Cost, bool CheapInstr) {1220 for (const auto &[Class, Weight] : Cost) {1221 if (Weight <= 0)1222 continue;1223 1224 int Limit = RegLimit[Class];1225 1226 // Don't hoist cheap instructions if they would increase register pressure,1227 // even if we're under the limit.1228 if (CheapInstr && !HoistCheapInsts)1229 return true;1230 1231 for (const auto &RP : BackTrace)1232 if (static_cast<int>(RP[Class]) + Weight >= Limit)1233 return true;1234 }1235 1236 return false;1237}1238 1239/// Traverse the back trace from header to the current block and update their1240/// register pressures to reflect the effect of hoisting MI from the current1241/// block to the preheader.1242void MachineLICMImpl::UpdateBackTraceRegPressure(const MachineInstr *MI) {1243 // First compute the 'cost' of the instruction, i.e. its contribution1244 // to register pressure.1245 auto Cost = calcRegisterCost(MI, /*ConsiderSeen=*/false,1246 /*ConsiderUnseenAsDef=*/false);1247 1248 // Update register pressure of blocks from loop header to current block.1249 for (auto &RP : BackTrace)1250 for (const auto &[Class, Weight] : Cost)1251 RP[Class] += Weight;1252}1253 1254/// Return true if it is potentially profitable to hoist the given loop1255/// invariant.1256bool MachineLICMImpl::IsProfitableToHoist(MachineInstr &MI,1257 MachineLoop *CurLoop) {1258 if (MI.isImplicitDef())1259 return true;1260 1261 // Besides removing computation from the loop, hoisting an instruction has1262 // these effects:1263 //1264 // - The value defined by the instruction becomes live across the entire1265 // loop. This increases register pressure in the loop.1266 //1267 // - If the value is used by a PHI in the loop, a copy will be required for1268 // lowering the PHI after extending the live range.1269 //1270 // - When hoisting the last use of a value in the loop, that value no longer1271 // needs to be live in the loop. This lowers register pressure in the loop.1272 1273 if (HoistConstStores && isCopyFeedingInvariantStore(MI, MRI, TRI))1274 return true;1275 1276 bool CheapInstr = IsCheapInstruction(MI);1277 bool CreatesCopy = HasLoopPHIUse(&MI, CurLoop);1278 1279 // Don't hoist a cheap instruction if it would create a copy in the loop.1280 if (CheapInstr && CreatesCopy) {1281 LLVM_DEBUG(dbgs() << "Won't hoist cheap instr with loop PHI use: " << MI);1282 return false;1283 }1284 1285 // Trivially rematerializable instructions should always be hoisted1286 // providing the register allocator can just pull them down again when needed.1287 if (TII->isTriviallyReMaterializable(MI))1288 return true;1289 1290 // FIXME: If there are long latency loop-invariant instructions inside the1291 // loop at this point, why didn't the optimizer's LICM hoist them?1292 for (unsigned i = 0, e = MI.getDesc().getNumOperands(); i != e; ++i) {1293 const MachineOperand &MO = MI.getOperand(i);1294 if (!MO.isReg() || MO.isImplicit())1295 continue;1296 Register Reg = MO.getReg();1297 if (!Reg.isVirtual())1298 continue;1299 if (MO.isDef() && HasHighOperandLatency(MI, i, Reg, CurLoop)) {1300 LLVM_DEBUG(dbgs() << "Hoist High Latency: " << MI);1301 ++NumHighLatency;1302 return true;1303 }1304 }1305 1306 // Estimate register pressure to determine whether to LICM the instruction.1307 // In low register pressure situation, we can be more aggressive about1308 // hoisting. Also, favors hoisting long latency instructions even in1309 // moderately high pressure situation.1310 // Cheap instructions will only be hoisted if they don't increase register1311 // pressure at all.1312 auto Cost = calcRegisterCost(&MI, /*ConsiderSeen=*/false,1313 /*ConsiderUnseenAsDef=*/false);1314 1315 // Visit BBs from header to current BB, if hoisting this doesn't cause1316 // high register pressure, then it's safe to proceed.1317 if (!CanCauseHighRegPressure(Cost, CheapInstr)) {1318 LLVM_DEBUG(dbgs() << "Hoist non-reg-pressure: " << MI);1319 ++NumLowRP;1320 return true;1321 }1322 1323 // Don't risk increasing register pressure if it would create copies.1324 if (CreatesCopy) {1325 LLVM_DEBUG(dbgs() << "Won't hoist instr with loop PHI use: " << MI);1326 return false;1327 }1328 1329 // Do not "speculate" in high register pressure situation. If an1330 // instruction is not guaranteed to be executed in the loop, it's best to be1331 // conservative.1332 if (AvoidSpeculation &&1333 (!IsGuaranteedToExecute(MI.getParent(), CurLoop) && !MayCSE(&MI))) {1334 LLVM_DEBUG(dbgs() << "Won't speculate: " << MI);1335 return false;1336 }1337 1338 // If we have a COPY with other uses in the loop, hoist to allow the users to1339 // also be hoisted.1340 // TODO: Handle all isCopyLike?1341 if (MI.isCopy() || MI.isRegSequence()) {1342 Register DefReg = MI.getOperand(0).getReg();1343 if (DefReg.isVirtual() &&1344 all_of(MI.uses(),1345 [this](const MachineOperand &UseOp) {1346 return !UseOp.isReg() || UseOp.getReg().isVirtual() ||1347 MRI->isConstantPhysReg(UseOp.getReg());1348 }) &&1349 IsLoopInvariantInst(MI, CurLoop) &&1350 any_of(MRI->use_nodbg_instructions(DefReg),1351 [&CurLoop, this, DefReg,1352 Cost = std::move(Cost)](MachineInstr &UseMI) {1353 if (!CurLoop->contains(&UseMI))1354 return false;1355 1356 // COPY is a cheap instruction, but if moving it won't cause1357 // high RP we're fine to hoist it even if the user can't be1358 // hoisted later Otherwise we want to check the user if it's1359 // hoistable1360 if (CanCauseHighRegPressure(Cost, false) &&1361 !CurLoop->isLoopInvariant(UseMI, DefReg))1362 return false;1363 1364 return true;1365 }))1366 return true;1367 }1368 1369 // High register pressure situation, only hoist if the instruction is going1370 // to be remat'ed.1371 if (!TII->isTriviallyReMaterializable(MI) &&1372 !MI.isDereferenceableInvariantLoad()) {1373 LLVM_DEBUG(dbgs() << "Can't remat / high reg-pressure: " << MI);1374 return false;1375 }1376 1377 return true;1378}1379 1380/// Unfold a load from the given machineinstr if the load itself could be1381/// hoisted. Return the unfolded and hoistable load, or null if the load1382/// couldn't be unfolded or if it wouldn't be hoistable.1383MachineInstr *MachineLICMImpl::ExtractHoistableLoad(MachineInstr *MI,1384 MachineLoop *CurLoop) {1385 // Don't unfold simple loads.1386 if (MI->canFoldAsLoad())1387 return nullptr;1388 1389 // If not, we may be able to unfold a load and hoist that.1390 // First test whether the instruction is loading from an amenable1391 // memory location.1392 if (!MI->isDereferenceableInvariantLoad())1393 return nullptr;1394 1395 // Next determine the register class for a temporary register.1396 unsigned LoadRegIndex;1397 unsigned NewOpc =1398 TII->getOpcodeAfterMemoryUnfold(MI->getOpcode(),1399 /*UnfoldLoad=*/true,1400 /*UnfoldStore=*/false,1401 &LoadRegIndex);1402 if (NewOpc == 0) return nullptr;1403 const MCInstrDesc &MID = TII->get(NewOpc);1404 MachineFunction &MF = *MI->getMF();1405 const TargetRegisterClass *RC = TII->getRegClass(MID, LoadRegIndex);1406 // Ok, we're unfolding. Create a temporary register and do the unfold.1407 Register Reg = MRI->createVirtualRegister(RC);1408 1409 SmallVector<MachineInstr *, 2> NewMIs;1410 bool Success = TII->unfoldMemoryOperand(MF, *MI, Reg,1411 /*UnfoldLoad=*/true,1412 /*UnfoldStore=*/false, NewMIs);1413 (void)Success;1414 assert(Success &&1415 "unfoldMemoryOperand failed when getOpcodeAfterMemoryUnfold "1416 "succeeded!");1417 assert(NewMIs.size() == 2 &&1418 "Unfolded a load into multiple instructions!");1419 MachineBasicBlock *MBB = MI->getParent();1420 MachineBasicBlock::iterator Pos = MI;1421 MBB->insert(Pos, NewMIs[0]);1422 MBB->insert(Pos, NewMIs[1]);1423 // If unfolding produced a load that wasn't loop-invariant or profitable to1424 // hoist, discard the new instructions and bail.1425 if (!IsLoopInvariantInst(*NewMIs[0], CurLoop) ||1426 !IsProfitableToHoist(*NewMIs[0], CurLoop)) {1427 NewMIs[0]->eraseFromParent();1428 NewMIs[1]->eraseFromParent();1429 return nullptr;1430 }1431 1432 // Update register pressure for the unfolded instruction.1433 UpdateRegPressure(NewMIs[1]);1434 1435 // Otherwise we successfully unfolded a load that we can hoist.1436 1437 // Update the call info.1438 if (MI->shouldUpdateAdditionalCallInfo())1439 MF.eraseAdditionalCallInfo(MI);1440 1441 MI->eraseFromParent();1442 return NewMIs[0];1443}1444 1445/// Initialize the CSE map with instructions that are in the current loop1446/// preheader that may become duplicates of instructions that are hoisted1447/// out of the loop.1448void MachineLICMImpl::InitCSEMap(MachineBasicBlock *BB) {1449 for (MachineInstr &MI : *BB)1450 CSEMap[BB][MI.getOpcode()].push_back(&MI);1451}1452 1453/// Initialize AllowedToHoistLoads with information about whether invariant1454/// loads can be moved outside a given loop1455void MachineLICMImpl::InitializeLoadsHoistableLoops() {1456 SmallVector<MachineLoop *, 8> Worklist(MLI->begin(), MLI->end());1457 SmallVector<MachineLoop *, 8> LoopsInPreOrder;1458 1459 // Mark all loops as hoistable initially and prepare a list of loops in1460 // pre-order DFS.1461 while (!Worklist.empty()) {1462 auto *L = Worklist.pop_back_val();1463 AllowedToHoistLoads[L] = true;1464 LoopsInPreOrder.push_back(L);1465 llvm::append_range(Worklist, L->getSubLoops());1466 }1467 1468 // Going from the innermost to outermost loops, check if a loop has1469 // instructions preventing invariant load hoisting. If such instruction is1470 // found, mark this loop and its parent as non-hoistable and continue1471 // investigating the next loop.1472 // Visiting in a reversed pre-ordered DFS manner1473 // allows us to not process all the instructions of the outer loop if the1474 // inner loop is proved to be non-load-hoistable.1475 for (auto *Loop : reverse(LoopsInPreOrder)) {1476 for (auto *MBB : Loop->blocks()) {1477 // If this loop has already been marked as non-hoistable, skip it.1478 if (!AllowedToHoistLoads[Loop])1479 continue;1480 for (auto &MI : *MBB) {1481 if (!MI.isLoadFoldBarrier() && !MI.mayStore() && !MI.isCall() &&1482 !(MI.mayLoad() && MI.hasOrderedMemoryRef()))1483 continue;1484 for (MachineLoop *L = Loop; L != nullptr; L = L->getParentLoop())1485 AllowedToHoistLoads[L] = false;1486 break;1487 }1488 }1489 }1490}1491 1492/// Find an instruction amount PrevMIs that is a duplicate of MI.1493/// Return this instruction if it's found.1494MachineInstr *1495MachineLICMImpl::LookForDuplicate(const MachineInstr *MI,1496 std::vector<MachineInstr *> &PrevMIs) {1497 for (MachineInstr *PrevMI : PrevMIs)1498 if (TII->produceSameValue(*MI, *PrevMI, (PreRegAlloc ? MRI : nullptr)))1499 return PrevMI;1500 1501 return nullptr;1502}1503 1504/// Given a LICM'ed instruction, look for an instruction on the preheader that1505/// computes the same value. If it's found, do a RAU on with the definition of1506/// the existing instruction rather than hoisting the instruction to the1507/// preheader.1508bool MachineLICMImpl::EliminateCSE(1509 MachineInstr *MI,1510 DenseMap<unsigned, std::vector<MachineInstr *>>::iterator &CI) {1511 // Do not CSE implicit_def so ProcessImplicitDefs can properly propagate1512 // the undef property onto uses.1513 if (MI->isImplicitDef())1514 return false;1515 1516 // Do not CSE normal loads because between them could be store instructions1517 // that change the loaded value1518 if (MI->mayLoad() && !MI->isDereferenceableInvariantLoad())1519 return false;1520 1521 if (MachineInstr *Dup = LookForDuplicate(MI, CI->second)) {1522 LLVM_DEBUG(dbgs() << "CSEing " << *MI << " with " << *Dup);1523 1524 // Replace virtual registers defined by MI by their counterparts defined1525 // by Dup.1526 SmallVector<unsigned, 2> Defs;1527 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {1528 const MachineOperand &MO = MI->getOperand(i);1529 1530 // Physical registers may not differ here.1531 assert((!MO.isReg() || MO.getReg() == 0 || !MO.getReg().isPhysical() ||1532 MO.getReg() == Dup->getOperand(i).getReg()) &&1533 "Instructions with different phys regs are not identical!");1534 1535 if (MO.isReg() && MO.isDef() && !MO.getReg().isPhysical())1536 Defs.push_back(i);1537 }1538 1539 SmallVector<const TargetRegisterClass*, 2> OrigRCs;1540 for (unsigned i = 0, e = Defs.size(); i != e; ++i) {1541 unsigned Idx = Defs[i];1542 Register Reg = MI->getOperand(Idx).getReg();1543 Register DupReg = Dup->getOperand(Idx).getReg();1544 OrigRCs.push_back(MRI->getRegClass(DupReg));1545 1546 if (!MRI->constrainRegClass(DupReg, MRI->getRegClass(Reg))) {1547 // Restore old RCs if more than one defs.1548 for (unsigned j = 0; j != i; ++j)1549 MRI->setRegClass(Dup->getOperand(Defs[j]).getReg(), OrigRCs[j]);1550 return false;1551 }1552 }1553 1554 for (unsigned Idx : Defs) {1555 Register Reg = MI->getOperand(Idx).getReg();1556 Register DupReg = Dup->getOperand(Idx).getReg();1557 MRI->replaceRegWith(Reg, DupReg);1558 MRI->clearKillFlags(DupReg);1559 // Clear Dup dead flag if any, we reuse it for Reg.1560 if (!MRI->use_nodbg_empty(DupReg))1561 Dup->getOperand(Idx).setIsDead(false);1562 }1563 1564 MI->eraseFromParent();1565 ++NumCSEed;1566 return true;1567 }1568 return false;1569}1570 1571/// Return true if the given instruction will be CSE'd if it's hoisted out of1572/// the loop.1573bool MachineLICMImpl::MayCSE(MachineInstr *MI) {1574 if (MI->mayLoad() && !MI->isDereferenceableInvariantLoad())1575 return false;1576 1577 unsigned Opcode = MI->getOpcode();1578 for (auto &Map : CSEMap) {1579 // Check this CSEMap's preheader dominates MI's basic block.1580 if (MDTU->getDomTree().dominates(Map.first, MI->getParent())) {1581 DenseMap<unsigned, std::vector<MachineInstr *>>::iterator CI =1582 Map.second.find(Opcode);1583 // Do not CSE implicit_def so ProcessImplicitDefs can properly propagate1584 // the undef property onto uses.1585 if (CI == Map.second.end() || MI->isImplicitDef())1586 continue;1587 if (LookForDuplicate(MI, CI->second) != nullptr)1588 return true;1589 }1590 }1591 1592 return false;1593}1594 1595/// When an instruction is found to use only loop invariant operands1596/// that are safe to hoist, this instruction is called to do the dirty work.1597/// It returns true if the instruction is hoisted.1598unsigned MachineLICMImpl::Hoist(MachineInstr *MI, MachineBasicBlock *Preheader,1599 MachineLoop *CurLoop) {1600 MachineBasicBlock *SrcBlock = MI->getParent();1601 1602 // Disable the instruction hoisting due to block hotness1603 if ((DisableHoistingToHotterBlocks == UseBFI::All ||1604 (DisableHoistingToHotterBlocks == UseBFI::PGO && HasProfileData)) &&1605 isTgtHotterThanSrc(SrcBlock, Preheader)) {1606 ++NumNotHoistedDueToHotness;1607 return HoistResult::NotHoisted;1608 }1609 // First check whether we should hoist this instruction.1610 bool HasExtractHoistableLoad = false;1611 if (!IsLoopInvariantInst(*MI, CurLoop) ||1612 !IsProfitableToHoist(*MI, CurLoop)) {1613 // If not, try unfolding a hoistable load.1614 MI = ExtractHoistableLoad(MI, CurLoop);1615 if (!MI)1616 return HoistResult::NotHoisted;1617 HasExtractHoistableLoad = true;1618 }1619 1620 // If we have hoisted an instruction that may store, it can only be a constant1621 // store.1622 if (MI->mayStore())1623 NumStoreConst++;1624 1625 // Now move the instructions to the predecessor, inserting it before any1626 // terminator instructions.1627 LLVM_DEBUG({1628 dbgs() << "Hoisting " << *MI;1629 if (MI->getParent()->getBasicBlock())1630 dbgs() << " from " << printMBBReference(*MI->getParent());1631 if (Preheader->getBasicBlock())1632 dbgs() << " to " << printMBBReference(*Preheader);1633 dbgs() << "\n";1634 });1635 1636 // If this is the first instruction being hoisted to the preheader,1637 // initialize the CSE map with potential common expressions.1638 if (FirstInLoop) {1639 InitCSEMap(Preheader);1640 FirstInLoop = false;1641 }1642 1643 // Look for opportunity to CSE the hoisted instruction.1644 unsigned Opcode = MI->getOpcode();1645 bool HasCSEDone = false;1646 for (auto &Map : CSEMap) {1647 // Check this CSEMap's preheader dominates MI's basic block.1648 if (MDTU->getDomTree().dominates(Map.first, MI->getParent())) {1649 DenseMap<unsigned, std::vector<MachineInstr *>>::iterator CI =1650 Map.second.find(Opcode);1651 if (CI != Map.second.end()) {1652 if (EliminateCSE(MI, CI)) {1653 HasCSEDone = true;1654 break;1655 }1656 }1657 }1658 }1659 1660 if (!HasCSEDone) {1661 // Otherwise, splice the instruction to the preheader.1662 Preheader->splice(Preheader->getFirstTerminator(),MI->getParent(),MI);1663 1664 // Since we are moving the instruction out of its basic block, we do not1665 // retain its debug location. Doing so would degrade the debugging1666 // experience and adversely affect the accuracy of profiling information.1667 assert(!MI->isDebugInstr() && "Should not hoist debug inst");1668 MI->setDebugLoc(DebugLoc());1669 1670 // Update register pressure for BBs from header to this block.1671 UpdateBackTraceRegPressure(MI);1672 1673 // Clear the kill flags of any register this instruction defines,1674 // since they may need to be live throughout the entire loop1675 // rather than just live for part of it.1676 for (MachineOperand &MO : MI->all_defs())1677 if (!MO.isDead())1678 MRI->clearKillFlags(MO.getReg());1679 1680 CSEMap[Preheader][Opcode].push_back(MI);1681 }1682 1683 ++NumHoisted;1684 Changed = true;1685 1686 if (HasCSEDone || HasExtractHoistableLoad)1687 return HoistResult::Hoisted | HoistResult::ErasedMI;1688 return HoistResult::Hoisted;1689}1690 1691/// Get the preheader for the current loop, splitting a critical edge if needed.1692MachineBasicBlock *MachineLICMImpl::getOrCreatePreheader(MachineLoop *CurLoop) {1693 // Determine the block to which to hoist instructions. If we can't find a1694 // suitable loop predecessor, we can't do any hoisting.1695 if (MachineBasicBlock *Preheader = CurLoop->getLoopPreheader())1696 return Preheader;1697 1698 // Try forming a preheader by splitting the critical edge between the single1699 // predecessor and the loop header.1700 if (MachineBasicBlock *Pred = CurLoop->getLoopPredecessor()) {1701 MachineBasicBlock *NewPreheader = Pred->SplitCriticalEdge(1702 CurLoop->getHeader(), LegacyPass, MFAM, nullptr, MDTU);1703 if (NewPreheader)1704 Changed = true;1705 return NewPreheader;1706 }1707 1708 return nullptr;1709}1710 1711/// Is the target basic block at least "BlockFrequencyRatioThreshold"1712/// times hotter than the source basic block.1713bool MachineLICMImpl::isTgtHotterThanSrc(MachineBasicBlock *SrcBlock,1714 MachineBasicBlock *TgtBlock) {1715 // Parse source and target basic block frequency from MBFI1716 uint64_t SrcBF = MBFI->getBlockFreq(SrcBlock).getFrequency();1717 uint64_t DstBF = MBFI->getBlockFreq(TgtBlock).getFrequency();1718 1719 // Disable the hoisting if source block frequency is zero1720 if (!SrcBF)1721 return true;1722 1723 double Ratio = (double)DstBF / SrcBF;1724 1725 // Compare the block frequency ratio with the threshold1726 return Ratio > BlockFrequencyRatioThreshold;1727}1728 1729template <typename DerivedT, bool PreRegAlloc>1730PreservedAnalyses MachineLICMBasePass<DerivedT, PreRegAlloc>::run(1731 MachineFunction &MF, MachineFunctionAnalysisManager &MFAM) {1732 bool Changed = MachineLICMImpl(PreRegAlloc, nullptr, &MFAM).run(MF);1733 if (!Changed)1734 return PreservedAnalyses::all();1735 auto PA = getMachineFunctionPassPreservedAnalyses();1736 PA.preserve<MachineLoopAnalysis>();1737 return PA;1738}1739 1740template class llvm::MachineLICMBasePass<EarlyMachineLICMPass, true>;1741template class llvm::MachineLICMBasePass<MachineLICMPass, false>;1742