Extend the ValuesAtScope cache to cover all expressions, not just

[oota-llvm.git] / lib / Analysis / LoopInfo.cpp

diff --git a/lib/Analysis/LoopInfo.cpp b/lib/Analysis/LoopInfo.cpp
index fb8027c14fdca8918636f77f87196c1aa24e431c..25264801193117f5a770219935d7d003a4bbbddb 100644 (file)
--- a/lib/Analysis/LoopInfo.cpp
+++ b/lib/Analysis/LoopInfo.cpp
@@ -20,7 +20,6 @@
 #include "llvm/Analysis/Dominators.h"
 #include "llvm/Assembly/Writer.h"
 #include "llvm/Support/CFG.h"
-#include "llvm/Support/Streams.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include <algorithm>
@@ -58,9 +57,10 @@ bool Loop::isLoopInvariant(Instruction *I) const {
 /// If InsertPt is specified, it is the point to hoist instructions to.
 /// If null, the terminator of the loop preheader is used.
 ///
-bool Loop::makeLoopInvariant(Value *V, Instruction *InsertPt) const {
+bool Loop::makeLoopInvariant(Value *V, bool &Changed,
+                             Instruction *InsertPt) const {
   if (Instruction *I = dyn_cast<Instruction>(V))
-    return makeLoopInvariant(I);
+    return makeLoopInvariant(I, Changed, InsertPt);
   return true;  // All non-instructions are loop-invariant.
 }
 
@@ -73,18 +73,14 @@ bool Loop::makeLoopInvariant(Value *V, Instruction *InsertPt) const {
 /// If InsertPt is specified, it is the point to hoist instructions to.
 /// If null, the terminator of the loop preheader is used.
 ///
-bool Loop::makeLoopInvariant(Instruction *I, Instruction *InsertPt) const {
+bool Loop::makeLoopInvariant(Instruction *I, bool &Changed,
+                             Instruction *InsertPt) const {
   // Test if the value is already loop-invariant.
   if (isLoopInvariant(I))
     return true;
-  // Don't hoist instructions with side-effects.
-  if (I->isTrapping())
+  if (!I->isSafeToSpeculativelyExecute())
     return false;
-  // Don't hoist PHI nodes.
-  if (isa<PHINode>(I))
-    return false;
-  // Don't hoist allocation instructions.
-  if (isa<AllocationInst>(I))
+  if (I->mayReadFromMemory())
     return false;
   // Determine the insertion point, unless one was given.
   if (!InsertPt) {
@@ -96,10 +92,11 @@ bool Loop::makeLoopInvariant(Instruction *I, Instruction *InsertPt) const {
   }
   // Don't hoist instructions with loop-variant operands.
   for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
-    if (!makeLoopInvariant(I->getOperand(i), InsertPt))
+    if (!makeLoopInvariant(I->getOperand(i), Changed, InsertPt))
       return false;
   // Hoist.
   I->moveBefore(InsertPt);
+  Changed = true;
   return true;
 }
 
@@ -273,6 +270,30 @@ bool Loop::isLCSSAForm() const {
 
   return true;
 }
+
+/// isLoopSimplifyForm - Return true if the Loop is in the form that
+/// the LoopSimplify form transforms loops to, which is sometimes called
+/// normal form.
+bool Loop::isLoopSimplifyForm() const {
+  // Normal-form loops have a preheader.
+  if (!getLoopPreheader())
+    return false;
+  // Normal-form loops have a single backedge.
+  if (!getLoopLatch())
+    return false;
+  // Each predecessor of each exit block of a normal loop is contained
+  // within the loop.
+  SmallVector<BasicBlock *, 4> ExitBlocks;
+  getExitBlocks(ExitBlocks);
+  for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i)
+    for (pred_iterator PI = pred_begin(ExitBlocks[i]),
+         PE = pred_end(ExitBlocks[i]); PI != PE; ++PI)
+      if (!contains(*PI))
+        return false;
+  // All the requirements are met.
+  return true;
+}
+
 //===----------------------------------------------------------------------===//
 // LoopInfo implementation
 //
@@ -286,3 +307,8 @@ void LoopInfo::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
   AU.addRequired<DominatorTree>();
 }
+
+void LoopInfo::print(raw_ostream &OS, const Module*) const {
+  LI.print(OS);
+}
+