Index: llvm/lib/CodeGen/MachineLICM.cpp =================================================================== --- llvm/lib/CodeGen/MachineLICM.cpp +++ llvm/lib/CodeGen/MachineLICM.cpp @@ -69,11 +69,6 @@ cl::init(false), cl::Hidden); static cl::opt -SinkInstsToAvoidSpills("sink-insts-to-avoid-spills", - cl::desc("MachineLICM should sink instructions into " - "loops to avoid register spills"), - cl::init(false), cl::Hidden); -static cl::opt HoistConstStores("hoist-const-stores", cl::desc("Hoist invariant stores"), cl::init(true), cl::Hidden); @@ -246,8 +241,6 @@ void HoistOutOfLoop(MachineDomTreeNode *HeaderN); - void SinkIntoLoop(); - void InitRegPressure(MachineBasicBlock *BB); DenseMap calcRegisterCost(const MachineInstr *MI, @@ -395,9 +388,6 @@ FirstInLoop = true; HoistOutOfLoop(N); CSEMap.clear(); - - if (SinkInstsToAvoidSpills) - SinkIntoLoop(); } } @@ -787,88 +777,6 @@ } } -/// Sink instructions into loops if profitable. This especially tries to prevent -/// register spills caused by register pressure if there is little to no -/// overhead moving instructions into loops. -void MachineLICMBase::SinkIntoLoop() { - MachineBasicBlock *Preheader = getCurPreheader(); - if (!Preheader) - return; - - SmallVector Candidates; - for (MachineBasicBlock::instr_iterator I = Preheader->instr_begin(); - I != Preheader->instr_end(); ++I) { - // We need to ensure that we can safely move this instruction into the loop. - // As such, it must not have side-effects, e.g. such as a call has. - LLVM_DEBUG(dbgs() << "LICM: Analysing sink candidate: " << *I); - if (IsLoopInvariantInst(*I) && !HasLoopPHIUse(&*I)) { - LLVM_DEBUG(dbgs() << "LICM: Added as sink candidate.\n"); - Candidates.push_back(&*I); - continue; - } - LLVM_DEBUG(dbgs() << "LICM: Not added as sink candidate.\n"); - } - - for (MachineInstr *I : Candidates) { - const MachineOperand &MO = I->getOperand(0); - if (!MO.isDef() || !MO.isReg() || !MO.getReg()) - continue; - if (!MRI->hasOneDef(MO.getReg())) - continue; - bool CanSink = true; - MachineBasicBlock *SinkBlock = nullptr; - LLVM_DEBUG(dbgs() << "LICM: Try sinking: " << *I); - - for (MachineInstr &MI : MRI->use_instructions(MO.getReg())) { - LLVM_DEBUG(dbgs() << "LICM: Analysing use: "; MI.dump()); - // FIXME: Come up with a proper cost model that estimates whether sinking - // the instruction (and thus possibly executing it on every loop - // iteration) is more expensive than a register. - // For now assumes that copies are cheap and thus almost always worth it. - if (!MI.isCopy()) { - CanSink = false; - break; - } - if (!SinkBlock) { - SinkBlock = MI.getParent(); - LLVM_DEBUG(dbgs() << "LICM: Setting sink block to: " - << printMBBReference(*SinkBlock) << "\n"); - continue; - } - SinkBlock = DT->findNearestCommonDominator(SinkBlock, MI.getParent()); - if (!SinkBlock) { - LLVM_DEBUG(dbgs() << "LICM: Can't find nearest dominator\n"); - CanSink = false; - break; - } - LLVM_DEBUG(dbgs() << "LICM: Setting nearest common dom block: " << - printMBBReference(*SinkBlock) << "\n"); - } - if (!CanSink) { - LLVM_DEBUG(dbgs() << "LICM: Can't sink instruction.\n"); - continue; - } - if (!SinkBlock) { - LLVM_DEBUG(dbgs() << "LICM: Not sinking, can't find sink block.\n"); - continue; - } - if (SinkBlock == Preheader) { - LLVM_DEBUG(dbgs() << "LICM: Not sinking, sink block is the preheader\n"); - continue; - } - - LLVM_DEBUG(dbgs() << "LICM: Sinking to " << printMBBReference(*SinkBlock) - << " from " << printMBBReference(*I->getParent()) - << ": " << *I); - SinkBlock->splice(SinkBlock->getFirstNonPHI(), Preheader, I); - - // The instruction is moved from its basic block, so do not retain the - // debug information. - assert(!I->isDebugInstr() && "Should not sink debug inst"); - I->setDebugLoc(DebugLoc()); - } -} - static bool isOperandKill(const MachineOperand &MO, MachineRegisterInfo *MRI) { return MO.isKill() || MRI->hasOneNonDBGUse(MO.getReg()); } Index: llvm/lib/CodeGen/MachineSink.cpp =================================================================== --- llvm/lib/CodeGen/MachineSink.cpp +++ llvm/lib/CodeGen/MachineSink.cpp @@ -79,6 +79,12 @@ "splitted critical edge"), cl::init(40), cl::Hidden); +static cl::opt +SinkInstsIntoLoop("sink-insts-to-avoid-spills", + cl::desc("MachineLICM should sink instructions into " + "loops to avoid register spills"), + cl::init(false), cl::Hidden); + STATISTIC(NumSunk, "Number of machine instructions sunk"); STATISTIC(NumSplit, "Number of critical edges split"); STATISTIC(NumCoalesces, "Number of copies coalesced"); @@ -204,6 +210,13 @@ bool &LocalUse) const; MachineBasicBlock *FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB, bool &BreakPHIEdge, AllSuccsCache &AllSuccessors); + + bool IsGuaranteedToExecute(MachineLoop *L, MachineBasicBlock *BB); + void FindLoopSinkCandidates(MachineLoop *L, MachineBasicBlock *BB, + SmallVector &Candidates); + bool SinkIntoLoop(MachineInstr &I, MachineLoop *L, + MachineBasicBlock *Preheader); + bool isProfitableToSinkTo(Register Reg, MachineInstr &MI, MachineBasicBlock *MBB, MachineBasicBlock *SuccToSinkTo, @@ -328,6 +341,57 @@ return true; } +/// Return true if this machine instruction loads from global offset table or +/// constant pool. +static bool mayLoadFromGOTOrConstantPool(MachineInstr &MI) { + assert(MI.mayLoad() && "Expected MI that loads!"); + + // If we lost memory operands, conservatively assume that the instruction + // reads from everything.. + if (MI.memoperands_empty()) + return true; + + for (MachineMemOperand *MemOp : MI.memoperands()) + if (const PseudoSourceValue *PSV = MemOp->getPseudoValue()) + if (PSV->isGOT() || PSV->isConstantPool()) + return true; + + return false; +} + +void MachineSinking::FindLoopSinkCandidates(MachineLoop *L, MachineBasicBlock *BB, + SmallVector &Candidates) { + for (auto &MI : *BB) { + LLVM_DEBUG(dbgs() << "LoopSink: Analysing candidate: " << MI); + bool DontMoveAcrossStore = true; + if (!MI.isSafeToMove(AA, DontMoveAcrossStore)) + continue; + + if (MI.mayLoad() && !mayLoadFromGOTOrConstantPool(MI) && + !IsGuaranteedToExecute(L, BB)) { + LLVM_DEBUG(dbgs() << "LoopSink: Load not guaranteed to execute.\n"); + continue; + } + + if (MI.isConvergent()) + continue; + + if (!L->isLoopInvariant(MI)) { + LLVM_DEBUG(dbgs() << "LoopSink: Instruction not loop invariant\n"); + continue; + } + + const MachineOperand &MO = MI.getOperand(0); + if (!MO.isReg() || !MO.getReg() || !MO.isDef()) + continue; + if (!MRI->hasOneDef(MO.getReg())) + continue; + + LLVM_DEBUG(dbgs() << "LoopSink: Instruction added as candidate\n"); + Candidates.push_back(&MI); + } +} + bool MachineSinking::runOnMachineFunction(MachineFunction &MF) { if (skipFunction(MF.getFunction())) return false; @@ -377,6 +441,21 @@ EverMadeChange = true; } + if (SinkInstsIntoLoop) { + SmallVector Loops(LI->begin(), LI->end()); + for (auto *L : Loops) { + MachineBasicBlock *Preheader = LI->findLoopPreheader(L); + if (!Preheader) { + LLVM_DEBUG(dbgs() << "LoopSink: Can't find preheader\n"); + continue; + } + SmallVector Candidates; + FindLoopSinkCandidates(L, Preheader, Candidates); + for (auto *I : Candidates) + EverMadeChange |= SinkIntoLoop(*I, L, Preheader); + } + } + HasStoreCache.clear(); StoreInstrCache.clear(); @@ -390,7 +469,8 @@ bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) { // Can't sink anything out of a block that has less than two successors. - if (MBB.succ_size() <= 1 || MBB.empty()) return false; + if (MBB.succ_size() <= 1 || MBB.empty()) + return false; // Don't bother sinking code out of unreachable blocks. In addition to being // unprofitable, it can also lead to infinite looping, because in an @@ -1063,6 +1143,79 @@ return HasAliasedStore; } +// Check if this mbb is guaranteed to execute. If not then a load from this mbb +// may not be safe to hoist. +// TODO: create a machine loop helper utility for this. +bool MachineSinking::IsGuaranteedToExecute(MachineLoop *L, MachineBasicBlock *BB) { + if (BB != L->getHeader()) { + // Check loop exiting blocks. + SmallVector CurrentLoopExitingBlocks; + L->getExitingBlocks(CurrentLoopExitingBlocks); + for (MachineBasicBlock *CurrentLoopExitingBlock : CurrentLoopExitingBlocks) + if (!DT->dominates(BB, CurrentLoopExitingBlock)) { + return false; + } + } + return true; +} + +/// Sink instructions into loops if profitable. This especially tries to prevent +/// register spills caused by register pressure if there is little to no +/// overhead moving instructions into loops. +bool MachineSinking::SinkIntoLoop(MachineInstr &I, MachineLoop *Loop, + MachineBasicBlock *Preheader) { + LLVM_DEBUG(dbgs() << "LoopSink: Finding sink block for: " << I); + MachineBasicBlock *SinkBlock = nullptr; + bool CanSink = true; + const MachineOperand &MO = I.getOperand(0); + + for (MachineInstr &MI : MRI->use_instructions(MO.getReg())) { + LLVM_DEBUG(dbgs() << "LoopSink: Analysing use: "; MI.dump()); + + // FIXME: Come up with a proper cost model that estimates whether sinking + // the instruction (and thus possibly executing it on every loop + // iteration) is more expensive than a register. + // For now assumes that copies are cheap and thus almost always worth it. + if (!MI.isCopy()) { + CanSink = false; + break; + } + if (!SinkBlock) { + SinkBlock = MI.getParent(); + LLVM_DEBUG(dbgs() << "LoopSink: Setting sink block to: " + << printMBBReference(*SinkBlock) << "\n"); + continue; + } + SinkBlock = DT->findNearestCommonDominator(SinkBlock, MI.getParent()); + if (!SinkBlock) { + LLVM_DEBUG(dbgs() << "LoopSink: Can't find nearest dominator\n"); + CanSink = false; + break; + } + LLVM_DEBUG(dbgs() << "LoopSink: Setting nearest common dom block: " << + printMBBReference(*SinkBlock) << "\n"); + } + + if (!CanSink) { + LLVM_DEBUG(dbgs() << "LoopSink: Can't sink instruction.\n"); + return false; + } + if (!SinkBlock) { + LLVM_DEBUG(dbgs() << "LoopSink: Not sinking, can't find sink block.\n"); + return false; + } + if (SinkBlock == Preheader) { + LLVM_DEBUG(dbgs() << "LoopSink: Not sinking, sink block is the preheader\n"); + return false; + } + SinkBlock->splice(SinkBlock->getFirstNonPHI(), Preheader, I); + // The instruction is moved from its basic block, so do not retain the + // debug information. + assert(!I.isDebugInstr() && "Should not sink debug inst"); + I.setDebugLoc(DebugLoc()); + return true; +} + /// SinkInstruction - Determine whether it is safe to sink the specified machine /// instruction out of its current block into a successor. bool MachineSinking::SinkInstruction(MachineInstr &MI, bool &SawStore,