//
// 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.
//
//===----------------------------------------------------------------------===//
//
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "machine-licm"
-#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"
-#include <map>
using namespace llvm;
-namespace {
- // Hidden options to help debugging
- cl::opt<bool>
- PerformLICM("machine-licm",
- cl::init(false), cl::Hidden);
-}
+STATISTIC(NumHoisted, "Number of machine instructions hoisted out of loops");
namespace {
class VISIBILITY_HIDDEN MachineLICM : public MachineFunctionPass {
- // Various analyses that we use...
- MachineLoopInfo *LI; // Current MachineLoopInfo
- MachineDominatorTree *DT; // Machine dominator tree for the current Loop
-
+ const TargetMachine *TM;
const TargetInstrInfo *TII;
+ MachineFunction *CurMF; // Current MachineFunction
- // 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.
+ // Various analyses that we use...
+ MachineLoopInfo *LI; // Current MachineLoopInfo
+ MachineDominatorTree *DT; // Machine dominator tree for the cur loop
+ MachineRegisterInfo *RegInfo; // Machine register information
- // Map the def of a virtual register to the machine instruction.
- std::map<unsigned, const MachineInstr*> VRegDefs;
+ // 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.
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<MachineLoopInfo>();
AU.addRequired<MachineDominatorTree>();
+ AU.addPreserved<MachineLoopInfo>();
+ AU.addPreserved<MachineDominatorTree>();
+ MachineFunctionPass::getAnalysisUsage(AU);
}
private:
- /// GatherAllLoops - Get all loops in depth first order.
+ /// VisitAllLoops - Visit all of the loops in depth first order and try to
+ /// hoist invariant instructions from them.
///
- void GatherAllLoops(MachineLoop *L, SmallVectorImpl<MachineLoop*> &Loops) {
+ void VisitAllLoops(MachineLoop *L) {
const std::vector<MachineLoop*> &SubLoops = L->getSubLoops();
for (MachineLoop::iterator
- I = SubLoops.begin(), E = SubLoops.end(); I != E; ++I)
- GatherAllLoops(*I, Loops);
+ I = SubLoops.begin(), E = SubLoops.end(); I != E; ++I) {
+ MachineLoop *ML = *I;
- Loops.push_back(L);
- }
+ // 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()));
+ }
- /// MapVirtualRegisterDefs - Create a map of which machine instruction
- /// defines a virtual register.
- ///
- void MapVirtualRegisterDefs(const MachineFunction &MF);
+ HoistRegion(DT->getNode(L->getHeader()));
+ }
- /// isInSubLoop - A little predicate that returns true if the specified
+ /// 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) {
+ bool IsInSubLoop(MachineBasicBlock *BB) {
assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop");
-
- for (MachineLoop::iterator
- I = CurLoop->begin(), E = CurLoop->end(); I != E; ++I)
- if ((*I)->contains(BB))
- return true; // A subloop actually contains this block!
-
- return false;
+ 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();
- 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
+ /// 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.
///
- bool isLoopInvariantInst(MachineInstr &I);
+ bool IsLoopInvariantInst(MachineInstr &I);
/// FindPredecessors - Get all of the predecessors of the loop that are not
/// back-edges.
///
- void FindPredecessors(std::vector<MachineBasicBlock*> &Preds){
+ void FindPredecessors(std::vector<MachineBasicBlock*> &Preds) {
const MachineBasicBlock *Header = CurLoop->getHeader();
for (MachineBasicBlock::const_pred_iterator
Preds.push_back(*I);
}
- /// MoveInstToBlock - Moves the machine instruction to the bottom of the
- /// predecessor basic block (but before the terminator instructions).
+ /// MoveInstToEndOfBlock - Moves the machine instruction to the bottom of
+ /// the predecessor basic block (but before the terminator instructions).
///
- void MoveInstToBlock(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;
}
/// HoistRegion - Walk the specified region of the CFG (defined by all
/// 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.
///
- bool Hoist(MachineInstr &MI);
+ void Hoist(MachineInstr &MI);
};
-
- char MachineLICM::ID = 0;
- RegisterPass<MachineLICM> X("machine-licm",
- "Machine Loop Invariant Code Motion");
} // end anonymous namespace
+char MachineLICM::ID = 0;
+static RegisterPass<MachineLICM>
+X("machine-licm", "Machine Loop Invariant Code Motion");
+
FunctionPass *llvm::createMachineLICMPass() { return new MachineLICM(); }
/// Hoist expressions out of the specified loop. Note, alias info for inner loop
/// loop.
///
bool MachineLICM::runOnMachineFunction(MachineFunction &MF) {
- if (!PerformLICM) return false; // For debugging.
+ DOUT << "******** Machine LICM ********\n";
Changed = false;
- TII = MF.getTarget().getInstrInfo();
+ CurMF = &MF;
+ TM = &CurMF->getTarget();
+ TII = TM->getInstrInfo();
+ RegInfo = &CurMF->getRegInfo();
// Get our Loop information...
LI = &getAnalysis<MachineLoopInfo>();
for (MachineLoopInfo::iterator
I = LI->begin(), E = LI->end(); I != E; ++I) {
- MachineLoop *L = *I;
- CurLoop = L;
+ 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.
- SmallVector<MachineLoop*, 16> Loops;
- GatherAllLoops(L, Loops);
-
- for (SmallVector<MachineLoop*, 8>::iterator
- II = Loops.begin(), IE = Loops.end(); II != IE; ++II) {
- L = *II;
-
- // 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.
- HoistRegion(DT->getNode(L->getHeader()));
- }
+ VisitAllLoops(CurLoop);
}
return Changed;
}
-/// MapVirtualRegisterDefs - Create a map of which machine instruction defines a
-/// virtual register.
-///
-void MachineLICM::MapVirtualRegisterDefs(const MachineFunction &MF) {
- for (MachineFunction::const_iterator
- I = MF.begin(), E = MF.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;
-
- if (MI.getNumOperands() > 0) {
- const MachineOperand &MO = MI.getOperand(0);
-
- 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
// 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))
+ 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.
- if (Hoist(MI))
- // Hoisting was successful! Remove bothersome instruction now.
- MI.getParent()->remove(&MI);
+ Hoist(MI);
}
const std::vector<MachineDomTreeNode*> &Children = N->getChildren();
HoistRegion(Children[I]);
}
-/// isLoopInvariantInst - Returns true if the instruction is loop
+/// 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) {
- const TargetInstrDescriptor *TID = I.getInstrDescriptor();
+bool MachineLICM::IsLoopInvariantInst(MachineInstr &I) {
+ 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, 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.getDesc().getImplicitUses()) {
+ DOUT << " * Instruction has implicit uses:\n";
- // Don't hoist if this instruction implicitly reads physical registers or
- // doesn't take any operands.
- if (TID->ImplicitUses || !I.getNumOperands()) return false;
+ const TargetRegisterInfo *TRI = TM->getRegisterInfo();
+ for (const unsigned *ImpUses = I.getDesc().getImplicitUses();
+ *ImpUses; ++ImpUses)
+ DOUT << " -> " << TRI->getName(*ImpUses) << "\n";
+ }
- if (!CanHoistInst(I)) return false;
+ if (I.getDesc().getImplicitDefs()) {
+ DOUT << " * Instruction has implicit defines:\n";
- // The instruction is loop invariant if all of its operands are loop-invariant
+ const TargetRegisterInfo *TRI = TM->getRegisterInfo();
+ for (const unsigned *ImpDefs = I.getDesc().getImplicitDefs();
+ *ImpDefs; ++ImpDefs)
+ DOUT << " -> " << TRI->getName(*ImpDefs) << "\n";
+ }
+ });
+
+ // 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);
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;
}
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.
+/// 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.
///
-bool MachineLICM::Hoist(MachineInstr &MI) {
- if (!isLoopInvariantInst(MI)) return false;
+void MachineLICM::Hoist(MachineInstr &MI) {
+ if (!IsLoopInvariantInst(MI)) return;
std::vector<MachineBasicBlock*> Preds;
// Non-back-edge predecessors.
FindPredecessors(Preds);
- if (Preds.empty()) return false;
-
- // Check that the predecessors are qualified to take the hoisted
- // instruction. I.e., there is only one edge from each predecessor, and it's
- // to the loop header.
- for (std::vector<MachineBasicBlock*>::iterator
- I = Preds.begin(), E = Preds.end(); I != E; ++I) {
- MachineBasicBlock *MBB = *I;
-
- // FIXME: We are assuming at first that the basic blocks coming into this
- // loop have only one successor each. This isn't the case in general because
- // we haven't broken critical edges or added preheaders.
- if (MBB->succ_size() != 1) return false;
- assert(*MBB->succ_begin() == CurLoop->getHeader() &&
- "The predecessor doesn't feed directly into the loop header!");
- }
- // Now move the instructions to the predecessors.
- for (std::vector<MachineBasicBlock*>::iterator
- I = Preds.begin(), E = Preds.end(); I != E; ++I)
- MoveInstToBlock(*I, MI.clone());
+ // Either we don't have any predecessors(?!) or we have more than one, which
+ // is forbidden.
+ if (Preds.empty() || Preds.size() != 1) return;
+ // 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();
+
+ // 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!");
+
+ // Now move the instructions to the predecessor.
+ MoveInstToEndOfBlock(MBB, MI.getParent(), &MI);
Changed = true;
- return true;
}
projects / oota-llvm.git / blobdiff