From e906921480beacea2dea2d5ce8156bc246ee12a7 Mon Sep 17 00:00:00 2001
From: Tobias Grosser <grosser@fim.uni-passau.de>
Date: Thu, 20 Jan 2011 21:03:22 +0000
Subject: [PATCH] Implement requiredTransitive

The PassManager did not implement the transitivity of requiredTransitive. This
was unnoticed since 2006.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123942 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/VMCore/PassManager.cpp                         | 33 +++++++++++++++++++++-
 .../2010-09-03-RequiredTransitive.ll               | 24 ++++++++++++++++
 2 files changed, 56 insertions(+), 1 deletion(-)
 create mode 100644 test/Analysis/ScalarEvolution/2010-09-03-RequiredTransitive.ll

diff --git a/lib/VMCore/PassManager.cpp b/lib/VMCore/PassManager.cpp
index d798d6bded9..8bfef9855ca 100644
--- a/lib/VMCore/PassManager.cpp
+++ b/lib/VMCore/PassManager.cpp
@@ -500,6 +500,10 @@ PMTopLevelManager::PMTopLevelManager(PMDataManager *PMDM) {
 void
 PMTopLevelManager::setLastUser(const SmallVectorImpl<Pass *> &AnalysisPasses,
                                Pass *P) {
+  unsigned PDepth = 0;
+  if (P->getResolver())
+    PDepth = P->getResolver()->getPMDataManager().getDepth();
+
   for (SmallVectorImpl<Pass *>::const_iterator I = AnalysisPasses.begin(),
          E = AnalysisPasses.end(); I != E; ++I) {
     Pass *AP = *I;
@@ -508,13 +512,40 @@ PMTopLevelManager::setLastUser(const SmallVectorImpl<Pass *> &AnalysisPasses,
     if (P == AP)
       continue;
 
+    // Update the last users of passes that are required transitive by AP.
+    AnalysisUsage *AnUsage = findAnalysisUsage(AP);
+    const AnalysisUsage::VectorType &IDs = AnUsage->getRequiredTransitiveSet();
+    SmallVector<Pass *, 12> LastUses;
+    SmallVector<Pass *, 12> LastPMUses;
+    for (AnalysisUsage::VectorType::const_iterator I = IDs.begin(),
+         E = IDs.end(); I != E; ++I) {
+      Pass *AnalysisPass = findAnalysisPass(*I);
+      assert(AnalysisPass && "Expected analysis pass to exist.");
+      AnalysisResolver *AR = AnalysisPass->getResolver();
+      assert(AR && "Expected analysis resolver to exist.");
+      unsigned APDepth = AR->getPMDataManager().getDepth();
+
+      if (PDepth == APDepth)
+        LastUses.push_back(AnalysisPass);
+      else if (PDepth > APDepth)
+        LastPMUses.push_back(AnalysisPass);
+    }
+
+    setLastUser(LastUses, P);
+
+    // If this pass has a corresponding pass manager, push higher level
+    // analysis to this pass manager.
+    if (P->getResolver())
+      setLastUser(LastPMUses, P->getResolver()->getPMDataManager().getAsPass());
+
+
     // If AP is the last user of other passes then make P last user of
     // such passes.
     for (DenseMap<Pass *, Pass *>::iterator LUI = LastUser.begin(),
            LUE = LastUser.end(); LUI != LUE; ++LUI) {
       if (LUI->second == AP)
         // DenseMap iterator is not invalidated here because
-        // this is just updating exisitng entry.
+        // this is just updating existing entries.
         LastUser[LUI->first] = P;
     }
   }
diff --git a/test/Analysis/ScalarEvolution/2010-09-03-RequiredTransitive.ll b/test/Analysis/ScalarEvolution/2010-09-03-RequiredTransitive.ll
new file mode 100644
index 00000000000..aba0ce74678
--- /dev/null
+++ b/test/Analysis/ScalarEvolution/2010-09-03-RequiredTransitive.ll
@@ -0,0 +1,24 @@
+; RUN: opt -indvars -scalar-evolution -analyze %s
+; This test checks if the SCEV analysis is printed out at all.
+; It failed once as the RequiredTransitive option was not implemented
+; correctly.
+
+define i32 @main() nounwind {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvar1 = phi i64 [ %indvar.next2, %for.inc ], [ 0, %entry ] ; <i64> [#uses=3]
+  %exitcond = icmp ne i64 %indvar1, 1024          ; <i1> [#uses=1]
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvar.next2 = add i64 %indvar1, 1             ; <i64> [#uses=1]
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret i32 0
+}
-- 
2.11.0