X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FMachineLICM.cpp;h=dd32977f90b6c6f6a8ec9b8ec38664b4a8097339;hb=0a1fcce09230e9b4bd30a8f07447aa075dce7470;hp=f7373bea86b350de4409bff8967903769ce7798d;hpb=a4b662272d2aa1a39025523fd9d1fdce9dfcbdb2;p=oota-llvm.git diff --git a/lib/CodeGen/MachineLICM.cpp b/lib/CodeGen/MachineLICM.cpp index f7373bea86b..dd32977f90b 100644 --- a/lib/CodeGen/MachineLICM.cpp +++ b/lib/CodeGen/MachineLICM.cpp @@ -10,94 +10,76 @@ // This pass performs loop invariant code motion on machine instructions. We // attempt to remove as much code from the body of a loop as possible. // +// This pass does not attempt to throttle itself to limit register pressure. +// The register allocation phases are expected to perform rematerialization +// to recover when register pressure is high. +// +// This pass is not intended to be a replacement or a complete alternative +// for the LLVM-IR-level LICM pass. It is only designed to hoist simple +// constructs that are not exposed before lowering and instruction selection. +// //===----------------------------------------------------------------------===// #define DEBUG_TYPE "machine-licm" -#include "llvm/ADT/IndexedMap.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/CodeGen/Passes.h" #include "llvm/CodeGen/MachineDominators.h" -#include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" -#include "llvm/CodeGen/Passes.h" -#include "llvm/Support/CFG.h" +#include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetMachine.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/Statistic.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" -#include "llvm/Target/MRegisterInfo.h" -#include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetMachine.h" using namespace llvm; -namespace { - // Hidden options to help debugging - cl::opt - PerformLICM("machine-licm", - cl::init(false), cl::Hidden, - cl::desc("Perform loop-invariant code motion on machine code")); -} - STATISTIC(NumHoisted, "Number of machine instructions hoisted out of loops"); +STATISTIC(NumCSEed, "Number of hoisted machine instructions CSEed"); namespace { class VISIBILITY_HIDDEN MachineLICM : public MachineFunctionPass { const TargetMachine *TM; const TargetInstrInfo *TII; - MachineFunction *CurMF; // Current MachineFunction // Various analyses that we use... - MachineLoopInfo *LI; // Current MachineLoopInfo - MachineDominatorTree *DT; // Machine dominator tree for the current Loop + MachineLoopInfo *LI; // Current MachineLoopInfo + MachineDominatorTree *DT; // Machine dominator tree for the cur loop MachineRegisterInfo *RegInfo; // Machine register information // State that is updated as we process loops - bool Changed; // True if a loop is changed. - MachineLoop *CurLoop; // The current loop we are working on. + bool Changed; // True if a loop is changed. + MachineLoop *CurLoop; // The current loop we are working on. + MachineBasicBlock *CurPreheader; // The preheader for CurLoop. + + // For each BB and opcode pair, keep a list of hoisted instructions. + DenseMap, + std::vector > CSEMap; public: static char ID; // Pass identification, replacement for typeid - MachineLICM() : MachineFunctionPass((intptr_t)&ID) {} + MachineLICM() : MachineFunctionPass(&ID) {} virtual bool runOnMachineFunction(MachineFunction &MF); - /// FIXME: Loop preheaders? - /// + const char *getPassName() const { return "Machine Instruction LICM"; } + + // FIXME: Loop preheaders? virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesCFG(); AU.addRequired(); AU.addRequired(); + AU.addPreserved(); + AU.addPreserved(); + MachineFunctionPass::getAnalysisUsage(AU); } - private: - /// VisitAllLoops - Visit all of the loops in depth first order and try to - /// hoist invariant instructions from them. - /// - void VisitAllLoops(MachineLoop *L) { - const std::vector &SubLoops = L->getSubLoops(); - - for (MachineLoop::iterator - I = SubLoops.begin(), E = SubLoops.end(); I != E; ++I) { - MachineLoop *ML = *I; - - // Traverse the body of the loop in depth first order on the dominator - // tree so that we are guaranteed to see definitions before we see uses. - VisitAllLoops(ML); - HoistRegion(DT->getNode(ML->getHeader())); - } - HoistRegion(DT->getNode(L->getHeader())); - } - - /// IsInSubLoop - A little predicate that returns true if the specified - /// basic block is in a subloop of the current one, not the current one - /// itself. - /// - bool IsInSubLoop(MachineBasicBlock *BB) { - assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop"); - return LI->getLoopFor(BB) != CurLoop; + virtual void releaseMemory() { + CSEMap.clear(); } + private: /// IsLoopInvariantInst - Returns true if the instruction is loop /// invariant. I.e., all virtual register operands are defined outside of /// the loop, physical registers aren't accessed (explicitly or implicitly), @@ -105,44 +87,9 @@ namespace { /// bool IsLoopInvariantInst(MachineInstr &I); - /// FindPredecessors - Get all of the predecessors of the loop that are not - /// back-edges. - /// - void FindPredecessors(std::vector &Preds) { - const MachineBasicBlock *Header = CurLoop->getHeader(); - - for (MachineBasicBlock::const_pred_iterator - I = Header->pred_begin(), E = Header->pred_end(); I != E; ++I) - if (!CurLoop->contains(*I)) - Preds.push_back(*I); - } - - /// MoveInstToEndOfBlock - Moves the machine instruction to the bottom of - /// the predecessor basic block (but before the terminator instructions). - /// - void MoveInstToEndOfBlock(MachineBasicBlock *ToMBB, - MachineBasicBlock *FromMBB, - MachineInstr *MI) { - DEBUG({ - DOUT << "Hoisting " << *MI; - if (ToMBB->getBasicBlock()) - DOUT << " to MachineBasicBlock " - << ToMBB->getBasicBlock()->getName(); - DOUT << "\n"; - }); - - MachineBasicBlock::iterator WhereIter = ToMBB->getFirstTerminator(); - MachineBasicBlock::iterator To, From = FromMBB->begin(); - - while (&*From != MI) - ++From; - - assert(From != FromMBB->end() && "Didn't find instr in BB!"); - - To = From; - ToMBB->splice(WhereIter, FromMBB, From, ++To); - ++NumHoisted; - } + /// IsProfitableToHoist - Return true if it is potentially profitable to + /// hoist the given loop invariant. + bool IsProfitableToHoist(MachineInstr &MI); /// HoistRegion - Walk the specified region of the CFG (defined by all /// blocks dominated by the specified block, and that are in the current @@ -157,28 +104,38 @@ namespace { /// void Hoist(MachineInstr &MI); }; - - char MachineLICM::ID = 0; - RegisterPass X("machine-licm", - "Machine Loop Invariant Code Motion"); } // end anonymous namespace +char MachineLICM::ID = 0; +static RegisterPass +X("machinelicm", "Machine Loop Invariant Code Motion"); + FunctionPass *llvm::createMachineLICMPass() { return new MachineLICM(); } +/// LoopIsOuterMostWithPreheader - Test if the given loop is the outer-most +/// loop that has a preheader. +static bool LoopIsOuterMostWithPreheader(MachineLoop *CurLoop) { + for (MachineLoop *L = CurLoop->getParentLoop(); L; L = L->getParentLoop()) + if (L->getLoopPreheader()) + return false; + return true; +} + /// Hoist expressions out of the specified loop. Note, alias info for inner loop /// is not preserved so it is not a good idea to run LICM multiple times on one /// loop. /// bool MachineLICM::runOnMachineFunction(MachineFunction &MF) { - if (!PerformLICM) return false; // For debugging. + const Function *F = MF.getFunction(); + if (F->hasFnAttr(Attribute::OptimizeForSize)) + return false; DOUT << "******** Machine LICM ********\n"; Changed = false; - CurMF = &MF; - TM = &CurMF->getTarget(); + TM = &MF.getTarget(); TII = TM->getInstrInfo(); - RegInfo = new MachineRegisterInfo(*TM->getRegisterInfo()); + RegInfo = &MF.getRegInfo(); // Get our Loop information... LI = &getAnalysis(); @@ -188,13 +145,23 @@ bool MachineLICM::runOnMachineFunction(MachineFunction &MF) { I = LI->begin(), E = LI->end(); I != E; ++I) { CurLoop = *I; - // Visit all of the instructions of the loop. We want to visit the subloops - // first, though, so that we can hoist their invariants first into their - // containing loop before we process that loop. - VisitAllLoops(CurLoop); + // Only visit outer-most preheader-sporting loops. + if (!LoopIsOuterMostWithPreheader(CurLoop)) + continue; + + // Determine the block to which to hoist instructions. If we can't find a + // suitable loop preheader, we can't do any hoisting. + // + // FIXME: We are only hoisting if the basic block coming into this loop + // has only one successor. This isn't the case in general because we haven't + // broken critical edges or added preheaders. + CurPreheader = CurLoop->getLoopPreheader(); + if (!CurPreheader) + continue; + + HoistRegion(DT->getNode(CurLoop->getHeader())); } - delete RegInfo; return Changed; } @@ -210,18 +177,15 @@ void MachineLICM::HoistRegion(MachineDomTreeNode *N) { // If this subregion is not in the top level loop at all, exit. if (!CurLoop->contains(BB)) return; - // Only need to process the contents of this block if it is not part of a - // subloop (which would already have been processed). - if (!IsInSubLoop(BB)) - for (MachineBasicBlock::iterator - I = BB->begin(), E = BB->end(); I != E; ) { - MachineInstr &MI = *I++; - - // Try hoisting the instruction out of the loop. We can only do this if - // all of the operands of the instruction are loop invariant and if it is - // safe to hoist the instruction. - Hoist(MI); - } + for (MachineBasicBlock::iterator + MII = BB->begin(), E = BB->end(); MII != E; ) { + MachineBasicBlock::iterator NextMII = MII; ++NextMII; + MachineInstr &MI = *MII; + + Hoist(MI); + + MII = NextMII; + } const std::vector &Children = N->getChildren(); @@ -235,46 +199,69 @@ void MachineLICM::HoistRegion(MachineDomTreeNode *N) { /// effects that aren't captured by the operands or other flags. /// bool MachineLICM::IsLoopInvariantInst(MachineInstr &I) { + const TargetInstrDesc &TID = I.getDesc(); + + // Ignore stuff that we obviously can't hoist. + if (TID.mayStore() || TID.isCall() || TID.isTerminator() || + TID.hasUnmodeledSideEffects()) + return false; + + if (TID.mayLoad()) { + // Okay, this instruction does a load. As a refinement, we allow the target + // to decide whether the loaded value is actually a constant. If so, we can + // actually use it as a load. + if (!TII->isInvariantLoad(&I)) + // FIXME: we should be able to sink loads with no other side effects if + // there is nothing that can change memory from here until the end of + // block. This is a trivial form of alias analysis. + return false; + } + DEBUG({ DOUT << "--- Checking if we can hoist " << I; - if (I.getInstrDescriptor()->ImplicitUses) { + if (I.getDesc().getImplicitUses()) { DOUT << " * Instruction has implicit uses:\n"; - const MRegisterInfo *MRI = TM->getRegisterInfo(); - const unsigned *ImpUses = I.getInstrDescriptor()->ImplicitUses; - - for (; *ImpUses; ++ImpUses) - DOUT << " -> " << MRI->getName(*ImpUses) << "\n"; + const TargetRegisterInfo *TRI = TM->getRegisterInfo(); + for (const unsigned *ImpUses = I.getDesc().getImplicitUses(); + *ImpUses; ++ImpUses) + DOUT << " -> " << TRI->getName(*ImpUses) << "\n"; } - if (I.getInstrDescriptor()->ImplicitDefs) { + if (I.getDesc().getImplicitDefs()) { DOUT << " * Instruction has implicit defines:\n"; - const MRegisterInfo *MRI = TM->getRegisterInfo(); - const unsigned *ImpDefs = I.getInstrDescriptor()->ImplicitDefs; - - for (; *ImpDefs; ++ImpDefs) - DOUT << " -> " << MRI->getName(*ImpDefs) << "\n"; + const TargetRegisterInfo *TRI = TM->getRegisterInfo(); + for (const unsigned *ImpDefs = I.getDesc().getImplicitDefs(); + *ImpDefs; ++ImpDefs) + DOUT << " -> " << TRI->getName(*ImpDefs) << "\n"; } - - if (TII->hasUnmodelledSideEffects(&I)) - DOUT << " * Instruction has side effects.\n"; }); - // The instruction is loop invariant if all of its operands are loop-invariant + if (I.getDesc().getImplicitDefs() || I.getDesc().getImplicitUses()) { + DOUT << "Cannot hoist with implicit defines or uses\n"; + return false; + } + + // The instruction is loop invariant if all of its operands are. for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { const MachineOperand &MO = I.getOperand(i); - if (!(MO.isRegister() && MO.getReg() && MO.isUse())) + if (!MO.isReg()) continue; unsigned Reg = MO.getReg(); + if (Reg == 0) continue; - // Don't hoist instructions that access physical registers. - if (!MRegisterInfo::isVirtualRegister(Reg)) + // Don't hoist an instruction that uses or defines a physical register. + if (TargetRegisterInfo::isPhysicalRegister(Reg)) return false; - assert(RegInfo->getVRegDef(Reg)&&"Machine instr not mapped for this vreg?"); + if (!MO.isUse()) + continue; + + assert(RegInfo->getVRegDef(Reg) && + "Machine instr not mapped for this vreg?!"); // If the loop contains the definition of an operand, then the instruction // isn't loop invariant. @@ -282,41 +269,128 @@ bool MachineLICM::IsLoopInvariantInst(MachineInstr &I) { return false; } - // Don't hoist something that has unmodelled side effects. - if (TII->hasUnmodelledSideEffects(&I)) return false; - // If we got this far, the instruction is loop invariant! return true; } -/// Hoist - When an instruction is found to only use loop invariant operands -/// that is safe to hoist, this instruction is called to do the dirty work. + +/// HasPHIUses - Return true if the specified register has any PHI use. +static bool HasPHIUses(unsigned Reg, MachineRegisterInfo *RegInfo) { + for (MachineRegisterInfo::use_iterator UI = RegInfo->use_begin(Reg), + UE = RegInfo->use_end(); UI != UE; ++UI) { + MachineInstr *UseMI = &*UI; + if (UseMI->getOpcode() == TargetInstrInfo::PHI) + return true; + } + return false; +} + +/// IsProfitableToHoist - Return true if it is potentially profitable to hoist +/// the given loop invariant. +bool MachineLICM::IsProfitableToHoist(MachineInstr &MI) { + const TargetInstrDesc &TID = MI.getDesc(); + + // FIXME: For now, only hoist re-materilizable instructions. LICM will + // increase register pressure. We want to make sure it doesn't increase + // spilling. + if (!TID.mayLoad() && (!TID.isRematerializable() || + !TII->isTriviallyReMaterializable(&MI))) + return false; + + // If result(s) of this instruction is used by PHIs, then don't hoist it. + // The presence of joins makes it difficult for current register allocator + // implementation to perform remat. + for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { + const MachineOperand &MO = MI.getOperand(i); + if (!MO.isReg() || !MO.isDef()) + continue; + if (HasPHIUses(MO.getReg(), RegInfo)) + return false; + } + + return true; +} + +static const MachineInstr *LookForDuplicate(const MachineInstr *MI, + std::vector &PrevMIs) { + unsigned NumOps = MI->getNumOperands(); + for (unsigned i = 0, e = PrevMIs.size(); i != e; ++i) { + const MachineInstr *PrevMI = PrevMIs[i]; + unsigned NumOps2 = PrevMI->getNumOperands(); + if (NumOps != NumOps2) + continue; + bool IsSame = true; + for (unsigned j = 0; j != NumOps; ++j) { + const MachineOperand &MO = MI->getOperand(j); + if (MO.isReg() && MO.isDef()) + continue; + if (!MO.isIdenticalTo(PrevMI->getOperand(j))) { + IsSame = false; + break; + } + } + if (IsSame) + return PrevMI; + } + return 0; +} + +/// Hoist - When an instruction is found to use only loop invariant operands +/// that are safe to hoist, this instruction is called to do the dirty work. /// void MachineLICM::Hoist(MachineInstr &MI) { if (!IsLoopInvariantInst(MI)) return; + if (!IsProfitableToHoist(MI)) return; - std::vector Preds; - - // Non-back-edge predecessors. - FindPredecessors(Preds); - - // Either we don't have any predecessors(?!) or we have more than one, which - // is forbidden. - if (Preds.empty() || Preds.size() != 1) return; + // Now move the instructions to the predecessor, inserting it before any + // terminator instructions. + DEBUG({ + DOUT << "Hoisting " << MI; + if (CurPreheader->getBasicBlock()) + DOUT << " to MachineBasicBlock " + << CurPreheader->getBasicBlock()->getName(); + if (MI.getParent()->getBasicBlock()) + DOUT << " from MachineBasicBlock " + << MI.getParent()->getBasicBlock()->getName(); + DOUT << "\n"; + }); - // Check that the predecessor is qualified to take the hoisted - // instruction. I.e., there is only one edge from the predecessor, and it's to - // the loop header. - MachineBasicBlock *MBB = Preds.front(); + // Look for opportunity to CSE the hoisted instruction. + std::pair BBOpcPair = + std::make_pair(CurPreheader->getNumber(), MI.getOpcode()); + DenseMap, + std::vector >::iterator CI = CSEMap.find(BBOpcPair); + bool DoneCSE = false; + if (CI != CSEMap.end()) { + const MachineInstr *Dup = LookForDuplicate(&MI, CI->second); + if (Dup) { + DOUT << "CSEing " << MI; + DOUT << " with " << *Dup; + for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { + const MachineOperand &MO = MI.getOperand(i); + if (MO.isReg() && MO.isDef()) + RegInfo->replaceRegWith(MO.getReg(), Dup->getOperand(i).getReg()); + } + MI.eraseFromParent(); + DoneCSE = true; + ++NumCSEed; + } + } - // FIXME: We are assuming at first that the basic block coming into this loop - // has only one successor. This isn't the case in general because we haven't - // broken critical edges or added preheaders. - if (MBB->succ_size() != 1) return; - assert(*MBB->succ_begin() == CurLoop->getHeader() && - "The predecessor doesn't feed directly into the loop header!"); + // Otherwise, splice the instruction to the preheader. + if (!DoneCSE) { + CurPreheader->splice(CurPreheader->getFirstTerminator(), + MI.getParent(), &MI); + // Add to the CSE map. + if (CI != CSEMap.end()) + CI->second.push_back(&MI); + else { + std::vector CSEMIs; + CSEMIs.push_back(&MI); + CSEMap.insert(std::make_pair(BBOpcPair, CSEMIs)); + } + } - // Now move the instructions to the predecessor. - MoveInstToEndOfBlock(MBB, MI.getParent(), &MI); + ++NumHoisted; Changed = true; }