X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FMachineLICM.cpp;h=e756dedff474733b44283e795d4c140fc0699c35;hb=80cc2598f89d09a6df2b84a5f8cea813b280b17b;hp=f6a08d362080a8a9d7051209b0a4135eeeb193d5;hpb=2e350479478ccf809e2142a4f0ad8062342577cc;p=oota-llvm.git diff --git a/lib/CodeGen/MachineLICM.cpp b/lib/CodeGen/MachineLICM.cpp index f6a08d36208..e756dedff47 100644 --- a/lib/CodeGen/MachineLICM.cpp +++ b/lib/CodeGen/MachineLICM.cpp @@ -37,10 +37,16 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/Statistic.h" +#include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" using namespace llvm; +static cl::opt +AvoidSpeculation("avoid-speculation", + cl::desc("MachineLICM should avoid speculation"), + cl::init(true), cl::Hidden); + STATISTIC(NumHoisted, "Number of machine instructions hoisted out of loops"); STATISTIC(NumLowRP, @@ -91,10 +97,16 @@ namespace { // For each opcode, keep a list of potential CSE instructions. DenseMap > CSEMap; + enum { + SpeculateFalse = 0, + SpeculateTrue = 1, + SpeculateUnknown = 2 + }; + // If a MBB does not dominate loop exiting blocks then it may not safe // to hoist loads from this block. - bool CurrentMBBDominatesLoopExitingBlocks; - bool NeedToCheckMBBDominance; + // Tri-state: 0 - false, 1 - true, 2 - unknown + unsigned SpeculationState; public: static char ID; // Pass identification, replacement for typeid @@ -245,6 +257,10 @@ namespace { bool EliminateCSE(MachineInstr *MI, DenseMap >::iterator &CI); + /// MayCSE - Return true if the given instruction will be CSE'd if it's + /// hoisted out of the loop. + bool MayCSE(MachineInstr *MI); + /// 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. /// It returns true if the instruction is hoisted. @@ -304,9 +320,6 @@ bool MachineLICM::runOnMachineFunction(MachineFunction &MF) { MRI = &MF.getRegInfo(); InstrItins = TM->getInstrItineraryData(); AllocatableSet = TRI->getAllocatableSet(MF); - // Stay conservative. - CurrentMBBDominatesLoopExitingBlocks = false; - NeedToCheckMBBDominance = true; if (PreRegAlloc) { // Estimate register pressure during pre-regalloc pass. @@ -460,6 +473,12 @@ void MachineLICM::HoistRegionPostRA() { const std::vector Blocks = CurLoop->getBlocks(); for (unsigned i = 0, e = Blocks.size(); i != e; ++i) { MachineBasicBlock *BB = Blocks[i]; + + // If the header of the loop containing this basic block is a landing pad, + // then don't try to hoist instructions out of this loop. + const MachineLoop *ML = MLI->getLoopFor(BB); + if (ML && ML->getHeader()->isLandingPad()) continue; + // Conservatively treat live-in's as an external def. // FIXME: That means a reload that're reused in successor block(s) will not // be LICM'ed. @@ -471,7 +490,7 @@ void MachineLICM::HoistRegionPostRA() { ++PhysRegDefs[*AS]; } - NeedToCheckMBBDominance = true; + SpeculationState = SpeculateUnknown; for (MachineBasicBlock::iterator MII = BB->begin(), E = BB->end(); MII != E; ++MII) { MachineInstr *MI = &*MII; @@ -568,25 +587,22 @@ void MachineLICM::HoistPostRA(MachineInstr *MI, unsigned Def) { // IsGuaranteedToExecute - Check if this mbb is guaranteed to execute. // If not then a load from this mbb may not be safe to hoist. bool MachineLICM::IsGuaranteedToExecute(MachineBasicBlock *BB) { - // Do not check if we already have checked it once. - if (NeedToCheckMBBDominance == false) - return CurrentMBBDominatesLoopExitingBlocks; - - NeedToCheckMBBDominance = false; - + if (SpeculationState != SpeculateUnknown) + return SpeculationState == SpeculateFalse; + if (BB != CurLoop->getHeader()) { // Check loop exiting blocks. SmallVector CurrentLoopExitingBlocks; CurLoop->getExitingBlocks(CurrentLoopExitingBlocks); for (unsigned i = 0, e = CurrentLoopExitingBlocks.size(); i != e; ++i) if (!DT->dominates(BB, CurrentLoopExitingBlocks[i])) { - CurrentMBBDominatesLoopExitingBlocks = false; - return CurrentMBBDominatesLoopExitingBlocks; + SpeculationState = SpeculateTrue; + return false; } } - CurrentMBBDominatesLoopExitingBlocks = true; - return CurrentMBBDominatesLoopExitingBlocks; + SpeculationState = SpeculateFalse; + return true; } /// HoistRegion - Walk the specified region of the CFG (defined by all blocks @@ -598,6 +614,11 @@ void MachineLICM::HoistRegion(MachineDomTreeNode *N, bool IsHeader) { assert(N != 0 && "Null dominator tree node?"); MachineBasicBlock *BB = N->getBlock(); + // If the header of the loop containing this basic block is a landing pad, + // then don't try to hoist instructions out of this loop. + const MachineLoop *ML = MLI->getLoopFor(BB); + if (ML && ML->getHeader()->isLandingPad()) return; + // If this subregion is not in the top level loop at all, exit. if (!CurLoop->contains(BB)) return; @@ -615,7 +636,7 @@ void MachineLICM::HoistRegion(MachineDomTreeNode *N, bool IsHeader) { // Remember livein register pressure. BackTrace.push_back(RegPressure); - NeedToCheckMBBDominance = true; + SpeculationState = SpeculateUnknown; for (MachineBasicBlock::iterator MII = BB->begin(), E = BB->end(); MII != E; ) { MachineBasicBlock::iterator NextMII = MII; ++NextMII; @@ -741,6 +762,21 @@ void MachineLICM::UpdateRegPressure(const MachineInstr *MI) { } } +/// isLoadFromGOTOrConstantPool - Return true if this machine instruction +/// loads from global offset table or constant pool. +static bool isLoadFromGOTOrConstantPool(MachineInstr &MI) { + assert (MI.getDesc().mayLoad() && "Expected MI that loads!"); + for (MachineInstr::mmo_iterator I = MI.memoperands_begin(), + E = MI.memoperands_end(); I != E; ++I) { + if (const Value *V = (*I)->getValue()) { + if (const PseudoSourceValue *PSV = dyn_cast(V)) + if (PSV == PSV->getGOT() || PSV == PSV->getConstantPool()) + return true; + } + } + return false; +} + /// IsLICMCandidate - Returns true if the instruction may be a suitable /// candidate for LICM. e.g. If the instruction is a call, then it's obviously /// not safe to hoist it. @@ -752,9 +788,12 @@ bool MachineLICM::IsLICMCandidate(MachineInstr &I) { // If it is load then check if it is guaranteed to execute by making sure that // it dominates all exiting blocks. If it doesn't, then there is a path out of - // the loop which does not execute this load, so we can't hoist it. + // the loop which does not execute this load, so we can't hoist it. Loads + // from constant memory are not safe to speculate all the time, for example + // indexed load from a jump table. // Stores and side effects are already checked by isSafeToMove. - if (I.getDesc().mayLoad() && !IsGuaranteedToExecute(I.getParent())) + if (I.getDesc().mayLoad() && !isLoadFromGOTOrConstantPool(I) && + !IsGuaranteedToExecute(I.getParent())) return false; return true; @@ -1037,6 +1076,13 @@ bool MachineLICM::IsProfitableToHoist(MachineInstr &MI) { return true; } + // Do not "speculate" in high register pressure situation. If an + // instruction is not guaranteed to be executed in the loop, it's best to be + // conservative. + if (AvoidSpeculation && + (!IsGuaranteedToExecute(MI.getParent()) && !MayCSE(&MI))) + return false; + // High register pressure situation, only hoist if the instruction is going to // be remat'ed. if (!TII->isTriviallyReMaterializable(&MI, AA) && @@ -1152,6 +1198,7 @@ bool MachineLICM::EliminateCSE(MachineInstr *MI, // Replace virtual registers defined by MI by their counterparts defined // by Dup. + SmallVector Defs; for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { const MachineOperand &MO = MI->getOperand(i); @@ -1162,11 +1209,33 @@ bool MachineLICM::EliminateCSE(MachineInstr *MI, "Instructions with different phys regs are not identical!"); if (MO.isReg() && MO.isDef() && - !TargetRegisterInfo::isPhysicalRegister(MO.getReg())) { - MRI->replaceRegWith(MO.getReg(), Dup->getOperand(i).getReg()); - MRI->clearKillFlags(Dup->getOperand(i).getReg()); + !TargetRegisterInfo::isPhysicalRegister(MO.getReg())) + Defs.push_back(i); + } + + SmallVector OrigRCs; + for (unsigned i = 0, e = Defs.size(); i != e; ++i) { + unsigned Idx = Defs[i]; + unsigned Reg = MI->getOperand(Idx).getReg(); + unsigned DupReg = Dup->getOperand(Idx).getReg(); + OrigRCs.push_back(MRI->getRegClass(DupReg)); + + if (!MRI->constrainRegClass(DupReg, MRI->getRegClass(Reg))) { + // Restore old RCs if more than one defs. + for (unsigned j = 0; j != i; ++j) + MRI->setRegClass(Dup->getOperand(Defs[j]).getReg(), OrigRCs[j]); + return false; } } + + for (unsigned i = 0, e = Defs.size(); i != e; ++i) { + unsigned Idx = Defs[i]; + unsigned Reg = MI->getOperand(Idx).getReg(); + unsigned DupReg = Dup->getOperand(Idx).getReg(); + MRI->replaceRegWith(Reg, DupReg); + MRI->clearKillFlags(DupReg); + } + MI->eraseFromParent(); ++NumCSEed; return true; @@ -1174,6 +1243,20 @@ bool MachineLICM::EliminateCSE(MachineInstr *MI, return false; } +/// MayCSE - Return true if the given instruction will be CSE'd if it's +/// hoisted out of the loop. +bool MachineLICM::MayCSE(MachineInstr *MI) { + unsigned Opcode = MI->getOpcode(); + DenseMap >::iterator + CI = CSEMap.find(Opcode); + // Do not CSE implicit_def so ProcessImplicitDefs can properly propagate + // the undef property onto uses. + if (CI == CSEMap.end() || MI->isImplicitDef()) + return false; + + return LookForDuplicate(MI, CI->second) != 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. ///