//
//===----------------------------------------------------------------------===//
//
-// This pass is a simple loop invariant code motion pass. An interesting aspect
-// of this pass is that it uses alias analysis for two purposes:
+// This pass performs loop invariant code motion, attempting to remove as much
+// code from the body of a loop as possible. It does this by either hoisting
+// code into the preheader block, or by sinking code to the exit blocks if it is
+// safe. This pass also promotes must-aliased memory locations in the loop to
+// live in registers.
+//
+// This pass uses alias analysis for two purposes:
//
// 1. Moving loop invariant loads out of loops. If we can determine that a
// load inside of a loop never aliases anything stored to, we can hoist it
-// like any other instruction.
+// or sink it like any other instruction.
// 2. Scalar Promotion of Memory - If there is a store instruction inside of
// the loop, we try to move the store to happen AFTER the loop instead of
// inside of the loop. This can only happen if a few conditions are true:
#include "llvm/Instructions.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Target/TargetData.h"
-#include "llvm/Support/InstVisitor.h"
#include "llvm/Support/CFG.h"
#include "Support/CommandLine.h"
#include "Support/Debug.h"
#include "Support/Statistic.h"
#include "llvm/Assembly/Writer.h"
#include <algorithm>
-
-namespace llvm {
+using namespace llvm;
namespace {
cl::opt<bool>
Statistic<> NumPromoted("licm",
"Number of memory locations promoted to registers");
- struct LICM : public FunctionPass, public InstVisitor<LICM> {
+ struct LICM : public FunctionPass {
virtual bool runOnFunction(Function &F);
/// This transformation requires natural loop information & requires that
}
private:
- LoopInfo *LI; // Current LoopInfo
+ // Various analyses that we use...
AliasAnalysis *AA; // Current AliasAnalysis information
+ LoopInfo *LI; // Current LoopInfo
+ DominatorTree *DT; // Dominator Tree for the current Loop...
DominanceFrontier *DF; // Current Dominance Frontier
+
+ // State that is updated as we process loops
bool Changed; // Set to true when we change anything.
BasicBlock *Preheader; // The preheader block of the current loop...
Loop *CurLoop; // The current loop we are working on...
AliasSetTracker *CurAST; // AliasSet information for the current loop...
- DominatorTree *DT; // Dominator Tree for the current Loop...
/// visitLoop - Hoist expressions out of the specified loop...
///
return !CurLoop->contains(I->getParent());
return true; // All non-instructions are loop invariant
}
+ bool isLoopInvariantInst(Instruction &Inst);
/// PromoteValuesInLoop - Look at the stores in the loop and promote as many
/// to scalars as we can.
void findPromotableValuesInLoop(
std::vector<std::pair<AllocaInst*, Value*> > &PromotedValues,
std::map<Value*, AllocaInst*> &Val2AlMap);
-
-
- /// Instruction visitation handlers... these basically control whether or
- /// not the specified instruction types are hoisted.
- ///
- friend class InstVisitor<LICM>;
- void visitBinaryOperator(Instruction &I) {
- if (isLoopInvariant(I.getOperand(0)) &&
- isLoopInvariant(I.getOperand(1)) && SafeToHoist(I))
- hoist(I);
- }
- void visitCastInst(CastInst &CI) {
- Instruction &I = (Instruction&)CI;
- if (isLoopInvariant(I.getOperand(0)) && SafeToHoist(CI)) hoist(I);
- }
- void visitShiftInst(ShiftInst &I) { visitBinaryOperator((Instruction&)I); }
-
- void visitLoadInst(LoadInst &LI);
-
- void visitGetElementPtrInst(GetElementPtrInst &GEPI) {
- Instruction &I = (Instruction&)GEPI;
- for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i)
- if (!isLoopInvariant(I.getOperand(i))) return;
- if(SafeToHoist(GEPI))
- hoist(I);
- }
};
RegisterOpt<LICM> X("licm", "Loop Invariant Code Motion");
}
-FunctionPass *createLICMPass() { return new LICM(); }
+FunctionPass *llvm::createLICMPass() { return new LICM(); }
/// runOnFunction - For LICM, this simply traverses the loop structure of the
/// function, hoisting expressions out of loops if possible.
for (std::vector<Loop*>::const_iterator I = TopLevelLoops.begin(),
E = TopLevelLoops.end(); I != E; ++I) {
AliasSetTracker AST(*AA);
- LICM::visitLoop(*I, AST);
+ visitLoop(*I, AST);
}
return Changed;
}
for (std::vector<Loop*>::const_iterator I = L->getSubLoops().begin(),
E = L->getSubLoops().end(); I != E; ++I) {
AliasSetTracker SubAST(*AA);
- LICM::visitLoop(*I, SubAST);
+ visitLoop(*I, SubAST);
// Incorporate information about the subloops into this loop...
AST.add(SubAST);
///
void LICM::HoistRegion(DominatorTree::Node *N) {
assert(N != 0 && "Null dominator tree node?");
+ BasicBlock *BB = N->getBlock();
// If this subregion is not in the top level loop at all, exit.
- if (!CurLoop->contains(N->getBlock())) return;
+ if (!CurLoop->contains(BB)) return;
// Only need to hoist the contents of this block if it is not part of a
// subloop (which would already have been hoisted)
- if (!inSubLoop(N->getBlock()))
- visit(*N->getBlock());
+ if (!inSubLoop(BB))
+ for (BasicBlock::iterator I = BB->begin(), E = --BB->end(); I != E; ) {
+ Instruction &Inst = *I++;
+ if (isLoopInvariantInst(Inst) && SafeToHoist(Inst))
+ hoist(Inst);
+ }
const std::vector<DominatorTree::Node*> &Children = N->getChildren();
for (unsigned i = 0, e = Children.size(); i != e; ++i)
HoistRegion(Children[i]);
}
+bool LICM::isLoopInvariantInst(Instruction &I) {
+ assert(!isa<TerminatorInst>(I) && "Can't hoist terminator instructions!");
+
+ // We can only hoist simple expressions...
+ if (!isa<BinaryOperator>(I) && !isa<ShiftInst>(I) && !isa<LoadInst>(I) &&
+ !isa<GetElementPtrInst>(I) && !isa<CastInst>(I) && !isa<VANextInst>(I) &&
+ !isa<VAArgInst>(I))
+ return false;
+
+ // The instruction is loop invariant if all of its operands are loop-invariant
+ for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i)
+ if (!isLoopInvariant(I.getOperand(i)))
+ return false;
+
+ // Loads have extra constraints we have to verify before we can hoist them.
+ if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
+ if (LI->isVolatile())
+ return false; // Don't hoist volatile loads!
+
+ // Don't hoist loads which have may-aliased stores in loop.
+ if (pointerInvalidatedByLoop(I.getOperand(0)))
+ 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.
WriteAsOperand(std::cerr, Preheader, false);
std::cerr << ": " << Inst);
+ if (isa<LoadInst>(Inst))
+ ++NumHoistedLoads;
+
// Remove the instruction from its current basic block... but don't delete the
// instruction.
Inst.getParent()->getInstList().remove(&Inst);
/// or if it is a trapping instruction and is guaranteed to execute
///
bool LICM::SafeToHoist(Instruction &Inst) {
+ // If it is not a trapping instruction, it is always safe to hoist.
+ if (!Inst.isTrapping()) return true;
+
+ // Otherwise we have to check to make sure that the instruction dominates all
+ // of the exit blocks. If it doesn't, then there is a path out of the loop
+ // which does not execute this instruction, so we can't hoist it.
+
+ // If the instruction is in the header block for the loop (which is very
+ // common), it is always guaranteed to dominate the exit blocks. Since this
+ // is a common case, and can save some work, check it now.
+ BasicBlock *LoopHeader = CurLoop->getHeader();
+ if (Inst.getParent() == LoopHeader)
+ return true;
+
+ // Get the Dominator Tree Node for the instruction's basic block.
+ DominatorTree::Node *InstDTNode = DT->getNode(Inst.getParent());
+
+ // Get the exit blocks for the current loop.
+ const std::vector<BasicBlock* > &ExitBlocks = CurLoop->getExitBlocks();
- //If it is a trapping instruction, then check if its guaranteed to execute.
- if(Inst.isTrapping()) {
-
- //Get the instruction's basic block.
- BasicBlock *InstBB = Inst.getParent();
+ // For each exit block, get the DT node and walk up the DT until the
+ // instruction's basic block is found or we exit the loop.
+ for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
+ DominatorTree::Node *IDom = DT->getNode(ExitBlocks[i]);
- //Get the Dominator Tree Node for the instruction's basic block/
- DominatorTree::Node *InstDTNode = DT->getNode(InstBB);
-
- //Get the exit blocks for the current loop.
- const std::vector<BasicBlock* > &ExitBlocks = CurLoop->getExitBlocks();
-
- //For each exit block, get the DT node and walk up the DT until
- //the instruction's basic block is found or we exit the loop.
- for(unsigned i=0; i < ExitBlocks.size(); ++i) {
- DominatorTree::Node *IDom = DT->getNode(ExitBlocks[i]);
-
- while(IDom != InstDTNode) {
-
- //Get next Immediate Dominator.
- IDom = IDom->getIDom();
-
- //See if we exited the loop.
- if(!CurLoop->contains(IDom->getBlock()))
- return false;
- }
- }
+ do {
+ // Get next Immediate Dominator.
+ IDom = IDom->getIDom();
+
+ // If we have got to the header of the loop, then the instructions block
+ // did not dominate the exit node, so we can't hoist it.
+ if (IDom->getBlock() == LoopHeader)
+ return false;
+
+ } while(IDom != InstDTNode);
}
return true;
}
-void LICM::visitLoadInst(LoadInst &LI) {
- if (isLoopInvariant(LI.getOperand(0)) && !LI.isVolatile() &&
- !pointerInvalidatedByLoop(LI.getOperand(0)) && SafeToHoist(LI)) {
- hoist(LI);
- ++NumHoistedLoads;
- }
-}
-
/// PromoteValuesInLoop - Try to promote memory values to scalars by sinking
/// stores out of the loop and moving loads to before the loop. We do this by
/// looping over the stores in the loop, looking for stores to Must pointers
}
}
}
-
-} // End llvm namespace
projects / oota-llvm.git / blobdiff