- Expose passinfo from BreakCriticalEdges pass so that it may be "Required"

[oota-llvm.git] / lib / Transforms / Scalar / LICM.cpp

diff --git a/lib/Transforms/Scalar/LICM.cpp b/lib/Transforms/Scalar/LICM.cpp
index 99ee45e3cd76353e8a50dd1d052d775230185e8f..7bae9fd18a5a5b7ff8167f3f3b521c3d5cf8e7b6 100644 (file)
--- a/lib/Transforms/Scalar/LICM.cpp
+++ b/lib/Transforms/Scalar/LICM.cpp
@@ -18,8 +18,10 @@
 #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"
@@ -31,17 +33,17 @@ 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);
 
     // 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:
@@ -50,8 +52,9 @@ namespace {
     //
     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);
@@ -72,6 +75,11 @@ namespace {
     //
     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) {
       if (Instruction *I = dyn_cast<Instruction>(V))
@@ -86,17 +94,22 @@ namespace {
     // 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)))
         hoist(I);
     }
-
-    void visitCastInst(CastInst &I) { visitUnaryOperator((Instruction&)I); }
+    void visitCastInst(CastInst &CI) {
+      Instruction &I = (Instruction&)CI;
+      if (isLoopInvariant(I.getOperand(0))) hoist(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)
@@ -104,6 +117,8 @@ namespace {
       hoist(I);
     }
   };
+
+  RegisterOpt<LICM> X("licm", "Loop Invariant Code Motion");
 }
 
 Pass *createLICMPass() { return new LICM(); }
@@ -113,6 +128,9 @@ bool LICM::runOnFunction(Function &) {
   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.
   //
@@ -199,6 +217,9 @@ void LICM::hoist(Instruction &Inst) {
   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.
   //
@@ -220,10 +241,8 @@ void LICM::hoist(Instruction &Inst) {
     // 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) {
@@ -257,3 +276,13 @@ void LICM::hoist(Instruction &Inst) {
   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;
+}