separate_back_forward.patch

gistfile1.txt

diff --git a/llvm/include/llvm/Transforms/IPO/Attributor.h b/llvm/include/llvm/Transforms/IPO/Attributor.h
index 01d09105e..6ea831f5f 100644
--- a/llvm/include/llvm/Transforms/IPO/Attributor.h
+++ b/llvm/include/llvm/Transforms/IPO/Attributor.h
@@ -120,6 +120,11 @@ ChangeStatus operator|(ChangeStatus l, ChangeStatus r);
 ChangeStatus operator&(ChangeStatus l, ChangeStatus r);
 ///}
 
+enum Direction {
+  FORWARD = 0,
+  BACKWARD = 1,
+};
+
 /// Helper to describe and deal with positions in the LLVM-IR.
 ///
 /// A position in the IR is described by an anchor value and an "offset" that
@@ -718,6 +723,10 @@ struct Attributor {
   /// Return the data layout associated with the anchor scope.
   const DataLayout &getDataLayout() const { return InfoCache.DL; }
 
+  Direction getDirection() const { return Dir; }
+
+  void flipDirection() { Dir = Dir == FORWARD ? BACKWARD : FORWARD; }
+
 private:
   /// The set of all abstract attributes.
   ///{
@@ -744,6 +753,9 @@ private:
 
   /// The information cache that holds pre-processed (LLVM-IR) information.
   InformationCache &InfoCache;
+
+  /// Current deduction direction.
+  Direction Dir = BACKWARD;
 };
 
 /// An interface to query the internal state of an abstract attribute.
@@ -788,6 +800,8 @@ struct AbstractState {
   ///
   /// \returns ChangeStatus::CHANGED as the assumed value may change.
   virtual ChangeStatus indicatePessimisticFixpoint() = 0;
+
+  virtual bool toBestState() = 0;
 };
 
 /// Simple state with integers encoding.
@@ -805,11 +819,20 @@ struct IntegerState : public AbstractState {
   using base_t = uint32_t;
 
   /// Initialize the (best) state.
-  IntegerState(base_t BestState = ~0) : Assumed(BestState) {}
+  IntegerState(base_t BestState = ~0)
+      : Assumed(BestState), BestState(BestState) {}
 
   /// Return the worst possible representable state.
   static constexpr base_t getWorstState() { return 0; }
 
+  bool toBestState() override {
+    if (Assumed == BestState)
+      return false;
+
+    Assumed = BestState;
+    return true;
+  }
+
   /// See AbstractState::isValidState()
   /// NOTE: For now we simply pretend that the worst possible state is invalid.
   bool isValidState() const override { return Assumed != getWorstState(); }
@@ -922,6 +945,9 @@ private:
 
   /// The assumed state encoding in an integer of type base_t.
   base_t Assumed;
+
+  /// The best possible state .
+  base_t BestState;
 };
 
 /// Simple wrapper for a single bit (boolean) state.
@@ -1092,6 +1118,10 @@ protected:
   ///
   /// \Return CHANGED if the internal state changed, otherwise UNCHANGED.
   virtual ChangeStatus updateImpl(Attributor &A) = 0;
+
+  virtual ChangeStatus updateBackwardImpl(Attributor &A) {
+    return ChangeStatus::UNCHANGED;
+  }
 };
 
 /// Forward declarations of output streams for debug purposes.
@@ -1367,6 +1397,9 @@ struct DerefState : AbstractState {
            (DerefBytesState.isAtFixpoint() && GlobalState.isAtFixpoint());
   }
 
+  bool toBestState() override {
+    return DerefBytesState.toBestState() | GlobalState.toBestState();
+  }
   /// See AbstractState::indicateOptimisticFixpoint(...)
   ChangeStatus indicateOptimisticFixpoint() override {
     DerefBytesState.indicateOptimisticFixpoint();
diff --git a/llvm/lib/Transforms/IPO/Attributor.cpp b/llvm/lib/Transforms/IPO/Attributor.cpp
index 029017a56..9a51ea69a 100644
--- a/llvm/lib/Transforms/IPO/Attributor.cpp
+++ b/llvm/lib/Transforms/IPO/Attributor.cpp
@@ -264,7 +264,8 @@ ChangeStatus AbstractAttribute::update(Attributor &A) {
 
   LLVM_DEBUG(dbgs() << "[Attributor] Update: " << *this << "\n");
 
-  HasChanged = updateImpl(A);
+  HasChanged = A.getDirection() == Direction::FORWARD ? updateImpl(A)
+                                                      : updateBackwardImpl(A);
 
   LLVM_DEBUG(dbgs() << "[Attributor] Update " << HasChanged << " " << *this
                     << "\n");
@@ -727,6 +728,7 @@ public:
       }
     }
   }
+  bool toBestState() override { return true; }
 
   /// See AbstractAttribute::manifest(...).
   ChangeStatus manifest(Attributor &A) override;
@@ -1323,8 +1325,8 @@ struct AANonNullFloating : AANonNullImpl {
       const auto &AA = A.getAAFor<AANonNull>(*this, IRPosition::value(V));
       if (!Stripped && this == &AA) {
         if (!isKnownNonZero(&V, DL, 0, /* TODO: AC */ nullptr,
-                         /* TODO: CtxI */ nullptr,
-                         /* TODO: DT */ nullptr))
+                            /* TODO: CtxI */ nullptr,
+                            /* TODO: DT */ nullptr))
           T.indicatePessimisticFixpoint();
       } else {
         // Use abstract attribute information.
@@ -1777,8 +1779,9 @@ struct AAIsDeadFunction final : public AAIsDeadImpl {
 
   /// See AbstractAttribute::trackStatistics()
   void trackStatistics() const override {
-    STATS_DECL(DeadInternalFunction, Function,
-               "Number of internal functions classified as dead (no live callsite)");
+    STATS_DECL(
+        DeadInternalFunction, Function,
+        "Number of internal functions classified as dead (no live callsite)");
     BUILD_STAT_NAME(DeadInternalFunction, Function) +=
         (getAssociatedFunction()->hasInternalLinkage() &&
          AssumedLiveBlocks.empty())
@@ -2076,7 +2079,7 @@ struct AADereferenceableArgument final
             IRP) {}
 
   /// See AbstractAttribute::trackStatistics()
-  void trackStatistics() const override{
+  void trackStatistics() const override {
     STATS_DECLTRACK_ARG_ATTR(dereferenceable)
   }
 };
@@ -2098,14 +2101,13 @@ using AADereferenceableCallSiteReturned = AADereferenceableReturned;
 // ------------------------ Align Argument Attribute ------------------------
 
 struct AAAlignImpl : AAAlign {
-  AAAlignImpl(const IRPosition &IRP) : AAAlign(IRP) {}
-
   // Max alignemnt value allowed in IR
   static const unsigned MAX_ALIGN = 1U << 29;
 
+  AAAlignImpl(const IRPosition &IRP) : AAAlign(IRP) {}
+
   /// See AbstractAttribute::initialize(...).
   void initialize(Attributor &A) override {
-    takeAssumedMinimum(MAX_ALIGN);
 
     SmallVector<Attribute, 4> Attrs;
     getAttrs({Attribute::Alignment}, Attrs);
@@ -2122,7 +2124,8 @@ struct AAAlignImpl : AAAlign {
   getDeducedAttributes(LLVMContext &Ctx,
                        SmallVectorImpl<Attribute> &Attrs) const override {
     if (getAssumedAlign() > 1)
-      Attrs.emplace_back(Attribute::getWithAlignment(Ctx, getAssumedAlign()));
+      Attrs.emplace_back(Attribute::getWithAlignment(
+          Ctx, std::min(getAssumedAlign(), MAX_ALIGN)));
   }
 
   /// See AbstractAttribute::getAsStr().
@@ -2464,42 +2467,47 @@ ChangeStatus Attributor::run() {
 
   SmallVector<AbstractAttribute *, 64> ChangedAAs;
   SetVector<AbstractAttribute *> Worklist;
-  Worklist.insert(AllAbstractAttributes.begin(), AllAbstractAttributes.end());
 
-  do {
-    // Remember the size to determine new attributes.
-    size_t NumAAs = AllAbstractAttributes.size();
-    LLVM_DEBUG(dbgs() << "\n\n[Attributor] #Iteration: " << IterationCounter
-                      << ", Worklist size: " << Worklist.size() << "\n");
-
-    // Add all abstract attributes that are potentially dependent on one that
-    // changed to the work list.
-    for (AbstractAttribute *ChangedAA : ChangedAAs) {
-      auto &QuerriedAAs = QueryMap[ChangedAA];
-      Worklist.insert(QuerriedAAs.begin(), QuerriedAAs.end());
-    }
+  for (unsigned I = 0; I < 2; I++) {
+    Worklist.insert(AllAbstractAttributes.begin(), AllAbstractAttributes.end());
+    do {
+      // Remember the size to determine new attributes.
+      size_t NumAAs = AllAbstractAttributes.size();
+      LLVM_DEBUG(dbgs() << "\n\n[Attributor] #Iteration: " << IterationCounter
+                        << ", Worklist size: " << Worklist.size() << "\n");
+
+      // Add all abstract attributes that are potentially dependent on one that
+      // changed to the work list.
+      for (AbstractAttribute *ChangedAA : ChangedAAs) {
+        auto &QuerriedAAs = QueryMap[ChangedAA];
+        Worklist.insert(QuerriedAAs.begin(), QuerriedAAs.end());
+      }
 
-    // Reset the changed set.
-    ChangedAAs.clear();
+      // Reset the changed set.
+      ChangedAAs.clear();
 
-    // Update all abstract attribute in the work list and record the ones that
-    // changed.
-    for (AbstractAttribute *AA : Worklist)
-      if (!isAssumedDead(*AA, nullptr))
-        if (AA->update(*this) == ChangeStatus::CHANGED)
-          ChangedAAs.push_back(AA);
+      // Update all abstract attribute in the work list and record the ones that
+      // changed.
+      for (AbstractAttribute *AA : Worklist)
+        if (!isAssumedDead(*AA, nullptr))
+          if (AA->update(*this) == ChangeStatus::CHANGED)
+            ChangedAAs.push_back(AA);
 
-    // Add attributes to the changed set if they have been created in the last
-    // iteration.
-    ChangedAAs.append(AllAbstractAttributes.begin() + NumAAs,
-                      AllAbstractAttributes.end());
+      // Add attributes to the changed set if they have been created in the last
+      // iteration.
+      ChangedAAs.append(AllAbstractAttributes.begin() + NumAAs,
+                        AllAbstractAttributes.end());
 
-    // Reset the work list and repopulate with the changed abstract attributes.
-    // Note that dependent ones are added above.
-    Worklist.clear();
-    Worklist.insert(ChangedAAs.begin(), ChangedAAs.end());
+      // Reset the work list and repopulate with the changed abstract
+      // attributes. Note that dependent ones are added above.
+      Worklist.clear();
+      Worklist.insert(ChangedAAs.begin(), ChangedAAs.end());
 
-  } while (!Worklist.empty() && ++IterationCounter < MaxFixpointIterations);
+    } while (!Worklist.empty() && ++IterationCounter < MaxFixpointIterations);
+
+    IterationCounter = 0;
+    flipDirection();
+  }
 
   size_t NumFinalAAs = AllAbstractAttributes.size();