X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FMachineLICM.cpp;h=ffcc02e3b8326f4e5e1d0b4aae55c7eee70b1d78;hb=d4e0af9f8945a1fb7b053f542ab114eb5908350d;hp=8f507e837e6c80cddd0819a508956d612944db78;hpb=a17ad59e13f5caafe33738bafc75af00ca354c9f;p=oota-llvm.git diff --git a/lib/CodeGen/MachineLICM.cpp b/lib/CodeGen/MachineLICM.cpp index 8f507e837e6..ffcc02e3b83 100644 --- a/lib/CodeGen/MachineLICM.cpp +++ b/lib/CodeGen/MachineLICM.cpp @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by Bill Wendling and is distributed under the -// University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -13,62 +13,51 @@ //===----------------------------------------------------------------------===// #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/Passes.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Support/CFG.h" +#include "llvm/Target/TargetMachine.h" +#include "llvm/ADT/SmallVector.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/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"); namespace { class VISIBILITY_HIDDEN MachineLICM : public MachineFunctionPass { - MachineFunction *CurMF;// Current MachineFunction + 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 - - const TargetInstrInfo *TII; + 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. - - // Map the def of a virtual register to the machine instruction. - IndexedMap VRegDefs; public: static char ID; // Pass identification, replacement for typeid MachineLICM() : MachineFunctionPass((intptr_t)&ID) {} virtual bool runOnMachineFunction(MachineFunction &MF); - /// FIXME: Loop preheaders? - /// + // 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 @@ -90,11 +79,6 @@ namespace { HoistRegion(DT->getNode(L->getHeader())); } - /// MapVirtualRegisterDefs - Create a map of which machine instruction - /// defines a virtual register. - /// - void MapVirtualRegisterDefs(); - /// 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. @@ -104,29 +88,6 @@ namespace { return LI->getLoopFor(BB) != CurLoop; } - /// CanHoistInst - Checks that this instructions is one that can be hoisted - /// out of the loop. I.e., it has no side effects, isn't a control flow - /// instr, etc. - /// - bool CanHoistInst(MachineInstr &I) const { - const TargetInstrDescriptor *TID = I.getInstrDescriptor(); - - // Don't hoist if this instruction implicitly reads physical registers. - if (TID->ImplicitUses) return false; - - MachineOpCode Opcode = TID->Opcode; - return TII->isTriviallyReMaterializable(&I) && - // FIXME: Below necessary? - !(TII->isReturn(Opcode) || - TII->isTerminatorInstr(Opcode) || - TII->isBranch(Opcode) || - TII->isIndirectBranch(Opcode) || - TII->isBarrier(Opcode) || - TII->isCall(Opcode) || - TII->isLoad(Opcode) || // TODO: Do loads and stores. - TII->isStore(Opcode)); - } - /// 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), @@ -149,9 +110,30 @@ namespace { /// MoveInstToEndOfBlock - Moves the machine instruction to the bottom of /// the predecessor basic block (but before the terminator instructions). /// - void MoveInstToEndOfBlock(MachineBasicBlock *MBB, MachineInstr *MI) { - MachineBasicBlock::iterator Iter = MBB->getFirstTerminator(); - MBB->insert(Iter, MI); + void 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(); + + while (&*From != MI) + ++From; + + assert(From != FromMBB->end() && "Didn't find instr in BB!"); + + To = From; + ToMBB->splice(WhereIter, FromMBB, From, ++To); ++NumHoisted; } @@ -181,20 +163,18 @@ FunctionPass *llvm::createMachineLICMPass() { return new MachineLICM(); } /// loop. /// bool MachineLICM::runOnMachineFunction(MachineFunction &MF) { - if (!PerformLICM) return false; // For debugging. - DOUT << "******** Machine LICM ********\n"; Changed = false; CurMF = &MF; - TII = CurMF->getTarget().getInstrInfo(); + TM = &CurMF->getTarget(); + TII = TM->getInstrInfo(); + RegInfo = &CurMF->getRegInfo(); // Get our Loop information... LI = &getAnalysis(); DT = &getAnalysis(); - MapVirtualRegisterDefs(); - for (MachineLoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) { CurLoop = *I; @@ -208,29 +188,6 @@ bool MachineLICM::runOnMachineFunction(MachineFunction &MF) { return Changed; } -/// MapVirtualRegisterDefs - Create a map of which machine instruction defines a -/// virtual register. -/// -void MachineLICM::MapVirtualRegisterDefs() { - for (MachineFunction::const_iterator - I = CurMF->begin(), E = CurMF->end(); I != E; ++I) { - const MachineBasicBlock &MBB = *I; - - for (MachineBasicBlock::const_iterator - II = MBB.begin(), IE = MBB.end(); II != IE; ++II) { - const MachineInstr &MI = *II; - - for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { - const MachineOperand &MO = MI.getOperand(i); - - if (MO.isRegister() && MO.isDef() && - MRegisterInfo::isVirtualRegister(MO.getReg())) - VRegDefs[MO.getReg()] = &MI; - } - } - } -} - /// HoistRegion - Walk the specified region of the CFG (defined by all blocks /// dominated by the specified block, and that are in the current loop) in depth /// first order w.r.t the DominatorTree. This allows us to visit definitions @@ -264,11 +221,52 @@ void MachineLICM::HoistRegion(MachineDomTreeNode *N) { /// 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), and the -/// instruction is hoistable. +/// loop, physical registers aren't accessed explicitly, and there are no side +/// effects that aren't captured by the operands or other flags. /// bool MachineLICM::IsLoopInvariantInst(MachineInstr &I) { - if (!CanHoistInst(I)) return false; + const TargetInstrDesc &TID = I.getDesc(); + + // Ignore stuff that we obviously can't hoist. + if (TID.mayStore() || TID.isCall() || TID.isReturn() || TID.isBranch() || + TID.hasUnmodeledSideEffects()) + return false; + + if (TID.mayLoad()) { + // Okay, this instruction does a load. As a refinement, 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.getDesc().getImplicitUses()) { + DOUT << " * Instruction has implicit uses:\n"; + + const TargetRegisterInfo *TRI = TM->getRegisterInfo(); + for (const unsigned *ImpUses = I.getDesc().getImplicitUses(); + *ImpUses; ++ImpUses) + DOUT << " -> " << TRI->getName(*ImpUses) << "\n"; + } + + if (I.getDesc().getImplicitDefs()) { + DOUT << " * Instruction has implicit defines:\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 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { @@ -278,16 +276,17 @@ bool MachineLICM::IsLoopInvariantInst(MachineInstr &I) { continue; unsigned Reg = MO.getReg(); + if (Reg == 0) continue; // Don't hoist instructions that access physical registers. - if (!MRegisterInfo::isVirtualRegister(Reg)) + if (TargetRegisterInfo::isPhysicalRegister(Reg)) return false; - assert(VRegDefs[Reg] && "Machine instr not mapped for this vreg?"); + 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. - if (CurLoop->contains(VRegDefs[Reg]->getParent())) + if (CurLoop->contains(RegInfo->getVRegDef(Reg)->getParent())) return false; } @@ -323,19 +322,6 @@ void MachineLICM::Hoist(MachineInstr &MI) { "The predecessor doesn't feed directly into the loop header!"); // Now move the instructions to the predecessor. - MachineInstr *NewMI = MI.clone(); - MoveInstToEndOfBlock(MBB, NewMI); - - // Update VRegDefs. - for (unsigned i = 0, e = NewMI->getNumOperands(); i != e; ++i) { - const MachineOperand &MO = NewMI->getOperand(i); - - if (MO.isRegister() && MO.isDef() && - MRegisterInfo::isVirtualRegister(MO.getReg())) - VRegDefs[MO.getReg()] = NewMI; - } - - // Hoisting was successful! Remove bothersome instruction now. - MI.getParent()->remove(&MI); + MoveInstToEndOfBlock(MBB, MI.getParent(), &MI); Changed = true; }