When checking whether the special handling for an addrec increment which

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

diff --git a/lib/Analysis/LoopDependenceAnalysis.cpp b/lib/Analysis/LoopDependenceAnalysis.cpp
index eb8ea0ebdb0b1cdc8bafd2fdad00d6e858a7efb8..e1019474cf4313f97997e0cb1530781970b4f03c 100644 (file)
--- a/lib/Analysis/LoopDependenceAnalysis.cpp
+++ b/lib/Analysis/LoopDependenceAnalysis.cpp
@@ -20,6 +20,7 @@
 //===----------------------------------------------------------------------===//
 
 #define DEBUG_TYPE "lda"
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/LoopDependenceAnalysis.h"
@@ -92,7 +93,7 @@ static AliasAnalysis::AliasResult UnderlyingObjectsAlias(AliasAnalysis *AA,
 }
 
 static inline const SCEV *GetZeroSCEV(ScalarEvolution *SE) {
-  return SE->getConstant(Type::Int32Ty, 0L);
+  return SE->getConstant(Type::getInt32Ty(SE->getContext()), 0L);
 }
 
 //===----------------------------------------------------------------------===//
@@ -118,17 +119,23 @@ bool LoopDependenceAnalysis::findOrInsertDependencePair(Value *A,
   P = Pairs.FindNodeOrInsertPos(id, insertPos);
   if (P) return true;
 
-  P = PairAllocator.Allocate<DependencePair>();
-  new (P) DependencePair(id, A, B);
+  P = new (PairAllocator) DependencePair(id, A, B);
   Pairs.InsertNode(P, insertPos);
   return false;
 }
 
-bool LoopDependenceAnalysis::isLoopInvariant(const SCEV *S) const {
+void LoopDependenceAnalysis::getLoops(const SCEV *S,
+                                      DenseSet<const Loop*>* Loops) const {
+  // Refactor this into an SCEVVisitor, if efficiency becomes a concern.
   for (const Loop *L = this->L; L != 0; L = L->getParentLoop())
     if (!S->isLoopInvariant(L))
-      return false;
-  return true;
+      Loops->insert(L);
+}
+
+bool LoopDependenceAnalysis::isLoopInvariant(const SCEV *S) const {
+  DenseSet<const Loop*> loops;
+  getLoops(S, &loops);
+  return loops.empty();
 }
 
 bool LoopDependenceAnalysis::isAffine(const SCEV *S) const {
@@ -140,6 +147,13 @@ bool LoopDependenceAnalysis::isZIVPair(const SCEV *A, const SCEV *B) const {
   return isLoopInvariant(A) && isLoopInvariant(B);
 }
 
+bool LoopDependenceAnalysis::isSIVPair(const SCEV *A, const SCEV *B) const {
+  DenseSet<const Loop*> loops;
+  getLoops(A, &loops);
+  getLoops(B, &loops);
+  return loops.size() == 1;
+}
+
 LoopDependenceAnalysis::DependenceResult
 LoopDependenceAnalysis::analyseZIV(const SCEV *A,
                                    const SCEV *B,
@@ -148,39 +162,53 @@ LoopDependenceAnalysis::analyseZIV(const SCEV *A,
   return A == B ? Dependent : Independent;
 }
 
+LoopDependenceAnalysis::DependenceResult
+LoopDependenceAnalysis::analyseSIV(const SCEV *A,
+                                   const SCEV *B,
+                                   Subscript *S) const {
+  return Unknown; // TODO: Implement.
+}
+
+LoopDependenceAnalysis::DependenceResult
+LoopDependenceAnalysis::analyseMIV(const SCEV *A,
+                                   const SCEV *B,
+                                   Subscript *S) const {
+  return Unknown; // TODO: Implement.
+}
+
 LoopDependenceAnalysis::DependenceResult
 LoopDependenceAnalysis::analyseSubscript(const SCEV *A,
                                          const SCEV *B,
                                          Subscript *S) const {
-  DEBUG(errs() << "  Testing subscript: " << *A << ", " << *B << "\n");
+  DEBUG(dbgs() << "  Testing subscript: " << *A << ", " << *B << "\n");
 
   if (A == B) {
-    DEBUG(errs() << "  -> [D] same SCEV\n");
+    DEBUG(dbgs() << "  -> [D] same SCEV\n");
     return Dependent;
   }
 
   if (!isAffine(A) || !isAffine(B)) {
-    DEBUG(errs() << "  -> [?] not affine\n");
+    DEBUG(dbgs() << "  -> [?] not affine\n");
     return Unknown;
   }
 
   if (isZIVPair(A, B))
     return analyseZIV(A, B, S);
 
-  // TODO: Implement SIV/MIV testers.
+  if (isSIVPair(A, B))
+    return analyseSIV(A, B, S);
 
-  DEBUG(errs() << "  -> [?] cannot analyse subscript\n");
-  return Unknown;
+  return analyseMIV(A, B, S);
 }
 
 LoopDependenceAnalysis::DependenceResult
 LoopDependenceAnalysis::analysePair(DependencePair *P) const {
-  DEBUG(errs() << "Analysing:\n" << *P->A << "\n" << *P->B << "\n");
+  DEBUG(dbgs() << "Analysing:\n" << *P->A << "\n" << *P->B << "\n");
 
   // We only analyse loads and stores but no possible memory accesses by e.g.
   // free, call, or invoke instructions.
   if (!IsLoadOrStoreInst(P->A) || !IsLoadOrStoreInst(P->B)) {
-    DEBUG(errs() << "--> [?] no load/store\n");
+    DEBUG(dbgs() << "--> [?] no load/store\n");
     return Unknown;
   }
 
@@ -190,12 +218,12 @@ LoopDependenceAnalysis::analysePair(DependencePair *P) const {
   switch (UnderlyingObjectsAlias(AA, aPtr, bPtr)) {
   case AliasAnalysis::MayAlias:
     // We can not analyse objects if we do not know about their aliasing.
-    DEBUG(errs() << "---> [?] may alias\n");
+    DEBUG(dbgs() << "---> [?] may alias\n");
     return Unknown;
 
   case AliasAnalysis::NoAlias:
     // If the objects noalias, they are distinct, accesses are independent.
-    DEBUG(errs() << "---> [I] no alias\n");
+    DEBUG(dbgs() << "---> [I] no alias\n");
     return Independent;
 
   case AliasAnalysis::MustAlias:
@@ -321,8 +349,3 @@ void LoopDependenceAnalysis::print(raw_ostream &OS, const Module*) const {
   // TODO: doc why const_cast is safe
   PrintLoopInfo(OS, const_cast<LoopDependenceAnalysis*>(this), this->L);
 }
-
-void LoopDependenceAnalysis::print(std::ostream &OS, const Module *M) const {
-  raw_os_ostream os(OS);
-  print(os, M);
-}