#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/iOperators.h"
#include "llvm/iPHINode.h"
+#include "llvm/iMemory.h"
#include "llvm/Support/InstVisitor.h"
#include "llvm/Support/CFG.h"
#include "Support/STLExtras.h"
#include "Support/StatisticReporter.h"
#include <algorithm>
+using std::string;
static Statistic<> NumHoistedNPH("licm\t\t- Number of insts hoisted to multiple"
" loop preds (bad, no loop pre-header)");
static Statistic<> NumHoistedPH("licm\t\t- Number of insts hoisted to a loop "
"pre-header");
+static Statistic<> NumHoistedLoads("licm\t\t- Number of load insts hoisted");
namespace {
struct LICM : public FunctionPass, public InstVisitor<LICM> {
- const char *getPassName() const { return "Loop Invariant Code Motion"; }
-
- virtual bool runOnFunction(Function *F);
+ virtual bool runOnFunction(Function &F);
// This transformation requires natural loop information...
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.preservesCFG();
- AU.addRequired(LoopInfo::ID);
+ AU.addRequired<LoopInfo>();
+ AU.addRequired<AliasAnalysis>();
}
private:
//
std::vector<BasicBlock*> LoopPreds, LoopBackEdges;
- Loop *CurLoop; // The current loop we are working on...
- bool Changed; // Set to true when we change anything.
+ Loop *CurLoop; // The current loop we are working on...
+ bool Changed; // Set to true when we change anything.
+ AliasAnalysis *AA; // Currently AliasAnalysis information
// visitLoop - Hoist expressions out of the specified loop...
void visitLoop(Loop *L);
// 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.
//
- void hoist(Instruction *I);
+ void hoist(Instruction &I);
+
+ // pointerInvalidatedByLoop - Return true if the body of this loop may store
+ // into the memory location pointed to by V.
+ //
+ bool pointerInvalidatedByLoop(Value *V);
// isLoopInvariant - Return true if the specified value is loop invariant
inline bool isLoopInvariant(Value *V) {
// the specified instruction types are hoisted.
//
friend class InstVisitor<LICM>;
- void visitUnaryOperator(Instruction *I) {
- if (isLoopInvariant(I->getOperand(0))) hoist(I);
- }
- void visitBinaryOperator(Instruction *I) {
- if (isLoopInvariant(I->getOperand(0)) &&isLoopInvariant(I->getOperand(1)))
+ void visitBinaryOperator(Instruction &I) {
+ if (isLoopInvariant(I.getOperand(0)) && isLoopInvariant(I.getOperand(1)))
hoist(I);
}
+ void visitCastInst(CastInst &CI) {
+ Instruction &I = (Instruction&)CI;
+ if (isLoopInvariant(I.getOperand(0))) hoist(I);
+ }
+ void visitShiftInst(ShiftInst &I) { visitBinaryOperator((Instruction&)I); }
- void visitCastInst(CastInst *I) { visitUnaryOperator((Instruction*)I); }
- void visitShiftInst(ShiftInst *I) { visitBinaryOperator((Instruction*)I); }
+ void visitLoadInst(LoadInst &LI) {
+ if (isLoopInvariant(LI.getOperand(0)) &&
+ !pointerInvalidatedByLoop(LI.getOperand(0)))
+ hoist(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;
+ void visitGetElementPtrInst(GetElementPtrInst &GEPI) {
+ Instruction &I = (Instruction&)GEPI;
+ for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i)
+ if (!isLoopInvariant(I.getOperand(i))) return;
hoist(I);
}
};
+
+ RegisterOpt<LICM> X("licm", "Loop Invariant Code Motion");
}
Pass *createLICMPass() { return new LICM(); }
-bool LICM::runOnFunction(Function *F) {
+bool LICM::runOnFunction(Function &) {
// get our loop information...
const std::vector<Loop*> &TopLevelLoops =
getAnalysis<LoopInfo>().getTopLevelLoops();
+ // Get our alias analysis information...
+ AA = &getAnalysis<AliasAnalysis>();
+
// Traverse loops in postorder, hoisting expressions out of the deepest loops
// first.
//
}
void LICM::visitBasicBlock(BasicBlock *BB) {
- // This cannot use an iterator, because it might get invalidated when PHI
- // nodes are inserted!
- //
- for (unsigned i = 0; i < BB->size(); ) {
- visit(BB->begin()[i]);
+ for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
+ visit(*I);
- BasicBlock::iterator It = BB->begin()+i;
- if (dceInstruction(It))
+ if (dceInstruction(I))
Changed = true;
else
- ++i;
+ ++I;
}
}
-void LICM::hoist(Instruction *Inst) {
- if (Inst->use_empty()) return; // Don't (re) hoist dead instructions!
+void LICM::hoist(Instruction &Inst) {
+ if (Inst.use_empty()) return; // Don't (re) hoist dead instructions!
//cerr << "Hoisting " << Inst;
BasicBlock *Header = CurLoop->getHeader();
// Old instruction will be removed, so take it's name...
- string InstName = Inst->getName();
- Inst->setName("");
+ string InstName = Inst.getName();
+ Inst.setName("");
+
+ if (isa<LoadInst>(Inst))
+ ++NumHoistedLoads;
// The common case is that we have a pre-header. Generate special case code
// that is faster if that is the case.
BasicBlock *Pred = LoopPreds[0];
// Create a new copy of the instruction, for insertion into Pred.
- Instruction *New = Inst->clone();
+ Instruction *New = Inst.clone();
New->setName(InstName);
// Insert the new node in Pred, before the terminator.
- Pred->getInstList().insert(Pred->end()-1, New);
+ Pred->getInstList().insert(--Pred->end(), New);
- // Kill the old instruction.
- Inst->replaceAllUsesWith(New);
+ // Kill the old instruction...
+ Inst.replaceAllUsesWith(New);
++NumHoistedPH;
} else {
// No loop pre-header, insert a PHI node into header to capture all of the
// incoming versions of the value.
//
- PHINode *LoopVal = new PHINode(Inst->getType(), InstName+".phi");
-
- // Insert the new PHI node into the loop header...
- Header->getInstList().push_front(LoopVal);
+ PHINode *LoopVal = new PHINode(Inst.getType(), InstName+".phi",
+ Header->begin());
// Insert cloned versions of the instruction into all of the loop preds.
for (unsigned i = 0, e = LoopPreds.size(); i != e; ++i) {
BasicBlock *Pred = LoopPreds[i];
// Create a new copy of the instruction, for insertion into Pred.
- Instruction *New = Inst->clone();
+ Instruction *New = Inst.clone();
New->setName(InstName);
// Insert the new node in Pred, before the terminator.
- Pred->getInstList().insert(Pred->end()-1, New);
+ Pred->getInstList().insert(--Pred->end(), New);
// Add the incoming value to the PHI node.
LoopVal->addIncoming(New, Pred);
// entire loop body. The old definition was defined _inside_ of the loop,
// so the scope cannot extend outside of the loop, so we're ok.
//
- Inst->replaceAllUsesWith(LoopVal);
+ Inst.replaceAllUsesWith(LoopVal);
++NumHoistedNPH;
}
Changed = true;
}
+// pointerInvalidatedByLoop - Return true if the body of this loop may store
+// into the memory location pointed to by V.
+//
+bool LICM::pointerInvalidatedByLoop(Value *V) {
+ // Check to see if any of the basic blocks in CurLoop invalidate V.
+ for (unsigned i = 0, e = CurLoop->getBlocks().size(); i != e; ++i)
+ if (AA->canBasicBlockModify(*CurLoop->getBlocks()[i], V))
+ return true;
+ return false;
+}
projects / oota-llvm.git / blobdiff