X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FMachineLICM.cpp;h=dd32977f90b6c6f6a8ec9b8ec38664b4a8097339;hb=0a1fcce09230e9b4bd30a8f07447aa075dce7470;hp=d0baaa87ae1beed2d477d98721c803d098e9af08;hpb=237dee125997dcaf16e391878465162cc680c0fa;p=oota-llvm.git diff --git a/lib/CodeGen/MachineLICM.cpp b/lib/CodeGen/MachineLICM.cpp index d0baaa87ae1..dd32977f90b 100644 --- a/lib/CodeGen/MachineLICM.cpp +++ b/lib/CodeGen/MachineLICM.cpp @@ -10,6 +10,14 @@ // 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" @@ -20,7 +28,7 @@ #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" -#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/Statistic.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Compiler.h" @@ -29,6 +37,7 @@ using namespace llvm; 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 { @@ -43,6 +52,11 @@ namespace { // 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. + 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(&ID) {} @@ -60,35 +74,12 @@ namespace { 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), @@ -96,24 +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); + /// 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 @@ -136,11 +112,24 @@ 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) { + const Function *F = MF.getFunction(); + if (F->hasFnAttr(Attribute::OptimizeForSize)) + return false; + DOUT << "******** Machine LICM ********\n"; Changed = false; @@ -156,10 +145,21 @@ 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())); } return Changed; @@ -177,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(); @@ -208,7 +205,7 @@ bool MachineLICM::IsLoopInvariantInst(MachineInstr &I) { 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 @@ -253,20 +250,16 @@ bool MachineLICM::IsLoopInvariantInst(MachineInstr &I) { if (!MO.isReg()) continue; - if (MO.isDef() && TargetRegisterInfo::isPhysicalRegister(MO.getReg())) - // Don't hoist an instruction that defines a physical register. - return false; - - if (!MO.isUse()) - continue; - unsigned Reg = MO.getReg(); if (Reg == 0) continue; - // Don't hoist instructions that access physical registers. + // Don't hoist an instruction that uses or defines a physical register. if (TargetRegisterInfo::isPhysicalRegister(Reg)) return false; + if (!MO.isUse()) + continue; + assert(RegInfo->getVRegDef(Reg) && "Machine instr not mapped for this vreg?!"); @@ -280,34 +273,66 @@ bool MachineLICM::IsLoopInvariantInst(MachineInstr &I) { return true; } -/// MoveInstToEndOfBlock - Moves the machine instruction to the bottom of the -/// predecessor basic block (but before the terminator instructions). -/// -void MachineLICM::MoveInstToEndOfBlock(MachineBasicBlock *ToMBB, - MachineBasicBlock *FromMBB, - MachineInstr *MI) { - DEBUG({ - DOUT << "Hoisting " << *MI; - if (ToMBB->getBasicBlock()) - DOUT << " to MachineBasicBlock " - << ToMBB->getBasicBlock()->getName(); - if (FromMBB->getBasicBlock()) - DOUT << " from MachineBasicBlock " - << FromMBB->getBasicBlock()->getName(); - DOUT << "\n"; - }); - MachineBasicBlock::iterator WhereIter = ToMBB->getFirstTerminator(); - MachineBasicBlock::iterator To, From = FromMBB->begin(); +/// 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; +} - while (&*From != MI) - ++From; +/// IsProfitableToHoist - Return true if it is potentially profitable to hoist +/// the given loop invariant. +bool MachineLICM::IsProfitableToHoist(MachineInstr &MI) { + const TargetInstrDesc &TID = MI.getDesc(); - assert(From != FromMBB->end() && "Didn't find instr in BB!"); + // 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; - To = From; - ToMBB->splice(WhereIter, FromMBB, From, ++To); - ++NumHoisted; + // 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 @@ -315,29 +340,57 @@ void MachineLICM::MoveInstToEndOfBlock(MachineBasicBlock *ToMBB, /// 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; }