switch some std::vector's to smallvector. Reduce nesting.

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

diff --git a/lib/Analysis/IVUsers.cpp b/lib/Analysis/IVUsers.cpp
index 00622d360acbfdad79c01a2a28037ec86d9b5aad..df9e31c1d2534d801f21900b22fa2f1f7b1cd764 100644 (file)
--- a/lib/Analysis/IVUsers.cpp
+++ b/lib/Analysis/IVUsers.cpp
@@ -19,7 +19,6 @@
 #include "llvm/Type.h"
 #include "llvm/DerivedTypes.h"
 #include "llvm/Analysis/Dominators.h"
-#include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/ADT/STLExtras.h"
@@ -54,7 +53,7 @@ static bool containsAddRecFromDifferentLoop(const SCEV *S, Loop *L) {
       if (newLoop == L)
         return false;
       // if newLoop is an outer loop of L, this is OK.
-      if (!LoopInfo::isNotAlreadyContainedIn(L, newLoop))
+      if (newLoop->contains(L))
         return false;
     }
     return true;
@@ -122,14 +121,14 @@ static bool getSCEVStartAndStride(const SCEV *&SH, Loop *L, Loop *UseLoop,
 
   Start = SE->getAddExpr(Start, AddRecStart);
 
-  // If stride is an instruction, make sure it dominates the loop preheader.
+  // If stride is an instruction, make sure it properly dominates the header.
   // Otherwise we could end up with a use before def situation.
   if (!isa<SCEVConstant>(AddRecStride)) {
-    BasicBlock *Preheader = L->getLoopPreheader();
-    if (!AddRecStride->dominates(Preheader, DT))
+    BasicBlock *Header = L->getHeader();
+    if (!AddRecStride->properlyDominates(Header, DT))
       return false;
 
-    DEBUG(errs() << "[" << L->getHeader()->getName()
+    DEBUG(dbgs() << "[" << L->getHeader()->getName()
                  << "] Variable stride: " << *AddRec << "\n");
   }
 
@@ -149,9 +148,11 @@ static bool IVUseShouldUsePostIncValue(Instruction *User, Instruction *IV,
                                        Loop *L, LoopInfo *LI, DominatorTree *DT,
                                        Pass *P) {
   // If the user is in the loop, use the preinc value.
-  if (L->contains(User->getParent())) return false;
+  if (L->contains(User)) return false;
 
   BasicBlock *LatchBlock = L->getLoopLatch();
+  if (!LatchBlock)
+    return false;
 
   // Ok, the user is outside of the loop.  If it is dominated by the latch
   // block, use the post-inc value.
@@ -207,6 +208,10 @@ bool IVUsers::AddUsersIfInteresting(Instruction *I) {
   if (!getSCEVStartAndStride(ISE, L, UseLoop, Start, Stride, SE, DT))
     return false;  // Non-reducible symbolic expression, bail out.
 
+  // Keep things simple. Don't touch loop-variant strides.
+  if (!Stride->isLoopInvariant(L) && L->contains(I))
+    return false;
+
   SmallPtrSet<Instruction *, 4> UniqueUsers;
   for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
        UI != E; ++UI) {
@@ -228,14 +233,14 @@ bool IVUsers::AddUsersIfInteresting(Instruction *I) {
     if (LI->getLoopFor(User->getParent()) != L) {
       if (isa<PHINode>(User) || Processed.count(User) ||
           !AddUsersIfInteresting(User)) {
-        DOUT << "FOUND USER in other loop: " << *User << '\n'
-             << "   OF SCEV: " << *ISE << "\n";
+        DEBUG(dbgs() << "FOUND USER in other loop: " << *User << '\n'
+                     << "   OF SCEV: " << *ISE << '\n');
         AddUserToIVUsers = true;
       }
     } else if (Processed.count(User) ||
                !AddUsersIfInteresting(User)) {
-      DOUT << "FOUND USER: " << *User << '\n'
-           << "   OF SCEV: " << *ISE << "\n";
+      DEBUG(dbgs() << "FOUND USER: " << *User << '\n'
+                   << "   OF SCEV: " << *ISE << '\n');
       AddUserToIVUsers = true;
     }
 
@@ -257,7 +262,7 @@ bool IVUsers::AddUsersIfInteresting(Instruction *I) {
         const SCEV *NewStart = SE->getMinusSCEV(Start, Stride);
         StrideUses->addUser(NewStart, User, I);
         StrideUses->Users.back().setIsUseOfPostIncrementedValue(true);
-        DOUT << "   USING POSTINC SCEV, START=" << *NewStart<< "\n";
+        DEBUG(dbgs() << "   USING POSTINC SCEV, START=" << *NewStart<< "\n");
       } else {
         StrideUses->addUser(Start, User, I);
       }
@@ -266,6 +271,18 @@ bool IVUsers::AddUsersIfInteresting(Instruction *I) {
   return true;
 }
 
+void IVUsers::AddUser(const SCEV *Stride, const SCEV *Offset,
+                      Instruction *User, Value *Operand) {
+  IVUsersOfOneStride *StrideUses = IVUsesByStride[Stride];
+  if (!StrideUses) {    // First occurrence of this stride?
+    StrideOrder.push_back(Stride);
+    StrideUses = new IVUsersOfOneStride(Stride);
+    IVUses.push_back(StrideUses);
+    IVUsesByStride[Stride] = StrideUses;
+  }
+  IVUsesByStride[Stride]->addUser(Offset, User, Operand);
+}
+
 IVUsers::IVUsers()
  : LoopPass(&ID) {
 }
@@ -307,7 +324,7 @@ const SCEV *IVUsers::getReplacementExpr(const IVStrideUse &U) const {
   if (U.isUseOfPostIncrementedValue())
     RetVal = SE->getAddExpr(RetVal, U.getParent()->Stride);
   // Evaluate the expression out of the loop, if possible.
-  if (!L->contains(U.getUser()->getParent())) {
+  if (!L->contains(U.getUser())) {
     const SCEV *ExitVal = SE->getSCEVAtScope(RetVal, L->getParentLoop());
     if (ExitVal->isLoopInvariant(L))
       RetVal = ExitVal;
@@ -345,19 +362,15 @@ void IVUsers::print(raw_ostream &OS, const Module *M) const {
   }
 }
 
-void IVUsers::print(std::ostream &o, const Module *M) const {
-  raw_os_ostream OS(o);
-  print(OS, M);
-}
-
 void IVUsers::dump() const {
-  print(errs());
+  print(dbgs());
 }
 
 void IVUsers::releaseMemory() {
   IVUsesByStride.clear();
   StrideOrder.clear();
   Processed.clear();
+  IVUses.clear();
 }
 
 void IVStrideUse::deleted() {