[MustExecute] Use MustBeExecutedInterval to eliminate work duplication

[jdoerfert]

Summary

Must be executed intervals are stretches of instructions that are
guaranteed to be executed together without any other instruction
executed in-between. In addition, an interval I can end in a link into
another interval J. This means that the instructions of the interval
J, starting from the position the link points to, are always executed
before or respectively after the instruction in I. Note that there
might be other instructions executed in-between linked intervals.

With this patch the must-be-executed-context explorer will created an
overlay of the CFG using partially connected intervals. In contrast to
the old scheme, we do not need to recompute join points or next/previous
instructions more than once, the information is part of the interval
web. Furthermore, iterators are changed to be lightweight, only
containing the position on the forward and backward web of intervals as
well as pointer to the explorer. The latter could potentially be
removed as well.

The interface of the explorer was changed because the users do not need
to create and hold on to iterators anymore.

Early test results show significant improvements wrt. compile time and
no changes to the context.

[jdoerfert]

Include test changes in the Attributor

[jdoerfert]

rebase and new test changes

[lebedev.ri]

@jdoerfert What is happening with this patch?

[jdoerfert]

In D78283#2095332, @lebedev.ri wrote:

@jdoerfert What is happening with this patch?

Waiting on review... ping?

[lebedev.ri]

Early test results show significant improvements wrt. compile time and no changes to the context.

But the tests are changed.
Can this be split up into NFC refactoring + some other patches that change tests?

[lebedev.ri]

Alright, this has been up for review long enough :)

Large diffs are indeed scary, and impossible to review,
and there is not really a way for people to mark parts
as reviewed so if i'm not the first one reviewing,
i guess no one has spotted anything bad yet.

This is pretty self-contained, in a pretty new (attributor) area.
Cursory examination suggests that this looks about right.
I suspect the perf story is indeed better than what there currently is :S

So i feel like i'm okay with rubber-stamping it.

[lebedev.ri]

This review seems to be stuck/dead, consider abandoning if no longer relevant.

llvm/include/llvm/Analysis/MustExecute.h

 /// Please refer to the class comments for more information.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_MUSTEXECUTE_H
 #define LLVM_ANALYSIS_MUSTEXECUTE_H
 
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/Analysis/EHPersonalities.h"
 #include "llvm/Analysis/InstructionPrecedenceTracking.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instruction.h"
+#include "llvm/Support/Allocator.h"
 
 namespace llvm {
 
 namespace {
 template <typename T> using GetterTy = std::function<T *(const Function &F)>;
 }
 
 class Instruction;

 struct MustBeExecutedContextExplorer;
 
 /// Enum that allows us to spell out the direction.
 enum class ExplorationDirection {
   BACKWARD = 0,
   FORWARD = 1,
 };
 
-/// Must be executed iterators visit stretches of instructions that are
-/// guaranteed to be executed together, potentially with other instruction
-/// executed in-between.
+/// Must be executed intervals are stretches of instructions that are
+/// guaranteed to be executed together without any other instruction
+/// executed in-between. In addition, an interval `I` can end in a link into
+/// another interval `J`. This means that the instructions of the interval
+/// `J`, starting from the position the link points to, are always executed
+/// before or respectively after the instruction in `I`. Note that there
+/// might be other instructions executed in-between linked intervals.
+///
+/// Given the following code, and assuming all statements are single
+/// instructions which transfer execution to the successor (see
+/// isGuaranteedToTransferExecutionToSuccessor), there are three intervals as
+/// shown in the table below.
+///
+/// \code
+///   A;
+///   B;
+///   if (...) {
+///     C;
+///     D;
+///   }
+///   E;
+/// \endcode
+///
+/// Int | Previous | Instructions | Next
+/// (1) |     None |        A ; B |  (3)
+/// (2) |      (1) |        C ; D |  (3)
+/// (3) |      (1) |            E | None
+///
+/// From the above table one can derive that C and D are always executed with
+/// A, B, and E. However, A, B, and E, are not necessarily executed with C and
+/// D but always together.
+///
+///
+/// Below is an extended example with instructions F and G and we assume F might
+/// not transfer execution to it's successor G. The resulting intervals are
+/// shown in the table below.
+///
+/// \code
+///   A;
+///   B;
+///   if (...) {
+///     C;
+///     D;
+///   }
+///   E;
+///   F;  // Might not transfer execution to its successor G.
+///   G;
+/// \endcode
+///
+/// Int | Previous | Instructions | Next
+/// (1) |     None |        A ; B |  (3)
+/// (2) |      (1) |        C ; D |  (3)
+/// (3) |      (1) |        E ; F | None
+/// (4) |      (3) |            G | None
+///
+/// As indicated by the table, E and F are executed always together with A and B
+/// but not C, D, or G. However, G is always executed with A, B, E, and F.
+///
+///
+/// A more complex example involving conditionals, loops, break, and continue
+/// is shown below. We again assume all instructions will transmit control to
+/// the successor and we assume we can prove the loops to be finite. We omit
+/// non-trivial branch conditions as the exploration is oblivious to them.
+/// Constant branches are assumed to be unconditional in the CFG. The resulting
+/// intervals are shown in the table below.
+///
+/// \code
+///   A;
+///   while (true) {
+///     B;
+///     if (...)
+///       C;
+///     if (...)
+///       continue;
+///     D;
+///     if (...)
+///       break;
+///     do {
+///       if (...)
+///         continue;
+///       E;
+///     } while (...)
+///     F;
+///   }
+///   G;
+/// \endcode
+///
+/// Int | Previous | Instructions | Next
+/// (1) |     None |            A |  (7)
+/// (2) |      (1) |            B |  (4)
+/// (3) |      (2) |            C |  (4)
+/// (4) |      (2) |            D |  (7)
+/// (5) |      (4) |            E |  (6)
+/// (6) |      (4) |            F |  (2)
+/// (7) |      (1) |            G | None
+///
+///
+/// Note that the examples show optimal intervals but not necessarily the ones
+/// derived by the implementation. Also note that an interval has a direction
+/// so there would be an interval for the forward direction and one for the
+/// backward direction. The former is linked as described by the Next column in
+/// the examples the latter as described by the Previous column.
+///
+struct MustBeExecutedInterval {
+
+  /// A position on an interval.
+  struct Position {
+
+    Position(MustBeExecutedInterval *Interval = nullptr)
+        : Interval(Interval), Offset(0) {}
+
+    /// Return the instruction at this position.
+    const Instruction *getInstruction() const {
+      assert(bool(*this) &&
+             "Invalid positions do not have an associated instruction!");
+      return (*Interval)[Offset];
+    }
+
+    /// Return the interval at this position.
+    MustBeExecutedInterval *getInterval() const { return Interval; }
+    unsigned getOffset() const { return Offset; }
+
+    /// Allow valid positions to evaluate to 'true' and invalid ones to 'false'
+    /// when a position is converted to a boolean.
+    operator bool() const { return Interval; }
+
+    /// Equality operator.
+    bool operator==(const Position &Other) const {
+      return Interval == Other.Interval && Offset == Other.Offset;
+    }
+
+    /// Advance the position in the direction \p Dir.
+    ///
+    /// If there is no next instruction in the direction, this will result in
+    /// an invalid position, hence the interval will be a nullptr.
+    ///{
+    Position &operator++() { return (*this) += 1; }
+
+    Position operator++(int) {
+      Position tmp(*this);
+      ++(*this);
+      return tmp;
+    }
+
+    Position &operator+=(unsigned N) {
+      if (!bool(*this))
+        return *this;
+
+      // If the offset adjusted wrt. direction is still in the associated
+      // interval, we adjust the offset and are done. Otherwise, we try to go to
+      // the linked interval in the direction and set the offset accordingly,
+      // hence to the very beginning or end depending on the direction. If there
+      // is no linked interval, all members will be set to NULL and the position
+      // becomes invalid.
+      if (Interval->isInbounds(Offset + N)) {
+        Offset += N;
+        return *this;
+      }
+
+      if (Interval->getPosInNextInterval()) {
+        unsigned Advanced = Interval->size() - Offset - 1;
+        assert(Interval->size() >= Offset + 1 && "Unexpected offset!");
+        assert(N >= Advanced + 1 && "Unexpected offset!");
+        *this = Interval->getPosInNextInterval();
+        return (*this) += N - Advanced - 1;
+      }
+
+      Interval = nullptr;
+      Offset = 0;
+      return *this;
+    }
+    ///}
+
+    /// Print method for debugging purposes.
+    void print(raw_ostream &OS, bool Detailed = false) const {
+      OS << "{" << Offset << "@";
+      if (Interval)
+        Interval->print(OS, false);
+      else
+        OS << "[NONE:NONE:N]";
+      OS << "}";
+    }
+
+  private:
+    /// The interval this position is currently associated with.
+    MustBeExecutedInterval *Interval;
+
+    /// The current offset from the beginning of the associated interval.
+    unsigned Offset;
+
+    friend struct MustBeExecutedContextExplorer;
+  };
+
+  /// Constructor for a new interval centered around \p I.
+  MustBeExecutedInterval(const Instruction &I, ExplorationDirection Dir)
+      : Dir(Dir) {
+    Insts.insert(&I);
+  }
+
+  /// Return the interval that contains the instructions executed after/before
+  /// the ones in this interval.
+  MustBeExecutedInterval *getNextInterval() const {
+    return PosInNextInterval.getInterval();
+  }
+
+  /// Return the position in the next interval at which execution is known to
+  /// continue.
+  const Position &getPosInNextInterval() const { return PosInNextInterval; }
+
+  /// Return the execution direction of this interval.
+  ExplorationDirection getDirection() const { return Dir; }
+
+  /// Return true if \p Offset is part of this interval, false otherwise.
+  bool isInbounds(unsigned Offset) { return Offset < size(); }
+
+  /// Subscript operator to allow easy access to the instructions based on their
+  /// offset.
+  const Instruction *operator[](unsigned Offset) const { return Insts[Offset]; }
+
+  /// Return true if \p I is in this interval
+  bool count(const Instruction &I) const { return Insts.count(&I); }
+
+  /// Print method for debugging purposes.
+  void print(raw_ostream &OS, bool Detailed = false) const {
+    OS << "[" << this << "(" << size() << ") + ";
+    PosInNextInterval.print(OS);
+    OS << " : " << unsigned(getDirection()) << "]";
+    if (Detailed) {
+      OS << "\n";
+      for (auto *I : Insts)
+        OS << "- " << *I << "\n";
+    }
+  }
+
+  /// Return the number of instructions contained in this interval.
+  unsigned size() const { return Insts.size(); }
+
+  /// Return true if this interval is final, that is no more extensions are
+  /// possible.
+  bool isFinalized() const { return IsFinalized; }
+
+private:
+  /// Indicate the interval is not going to be modified later on.
+  void finalize() {
+    assert(!IsFinalized && "Interval was marked finalized already!");
+    IsFinalized = true;
+  }
+
+  /// Set the next interval, return true if successful, false otherwise.
+  bool setPosInNextInterval(const Position &P) {
+    assert(!PosInNextInterval && "Interval already has a link to another one!");
+    assert(!IsFinalized && "Interval was marked finalized already!");
+
+    // Do not create cyclic lists. The check is potentially expensive but should
+    // not be in practise because we usually explore the context to the fullest
+    // which will prevent an extension after a "PrevInterval" was set. However,
+    // to prevent the quadratic worst case, we have a cut-off.
+    if (HasPrevInterval) {
+      unsigned MaxChainLength = 6;
+      MustBeExecutedInterval *MBEI = P.getInterval();
+      while (MBEI) {
+        if (MBEI == this || (--MaxChainLength == 0))
+          return false;
+        MBEI = MBEI->getNextInterval();
+      }
+    }
+
+    PosInNextInterval = P;
+    PosInNextInterval.getInterval()->HasPrevInterval = true;
+    return true;
+  }
+
+  /// Extend the interval by \p I
+  bool extend(const Instruction &I) {
+    assert(!PosInNextInterval &&
+           "Cannot advance the front if a next interval is already set!");
+    assert(!IsFinalized && "Interval was marked finalized already!");
+
+    // If we have seen the instruction we will not add it. This happens when we
+    // encountered an endless loop contained entirely in this interval.
+    return Insts.insert(&I);
+  }
+
+  /// The vectors that represent the instructions in the interval.
+  SmallSetVector<const Instruction *, 8> Insts;
+
+  /// The instruction executed next after the ones in Insts.
+  Position PosInNextInterval;
+
+  /// The direction in which the instruction in this interval are executed.
+  /// Forward means Insts[i] is executed before Insts[i+1], backward means it is
+  /// the other way around.
+  ExplorationDirection Dir;
+
+  /// A flag to indicate the interval is not going to change anymore. Used to
+  /// prevent us from trying to extend it after an earlier attempted failed.
+  bool IsFinalized = false;
+
+  /// Flag to indicate that another interval points into this one. Used to
+  /// determine if we need to check for potential endless loops or if there
+  /// cannot be any.
+  bool HasPrevInterval = false;
+
+  friend struct MustBeExecutedContextExplorer;
+};
+
+/// Must be executed iterators visit stretches of instructions, so called
+/// must-be-executed-intervals, that are guaranteed to be executed together,
+/// potentially with other instruction executed in-between.
+///
+/// See MustBeExecutedInterval for a discussion about the intervals of these
+/// examples.
 ///
 /// Given the following code, and assuming all statements are single
 /// instructions which transfer execution to the successor (see
 /// isGuaranteedToTransferExecutionToSuccessor), there are two possible
 /// outcomes. If we start the iterator at A, B, or E, we will visit only A, B,
 /// and E. If we start at C or D, we will visit all instructions A-E.
 ///
 /// \code

 ///                F     | A, B,    D,    F
 ///                   G  | A, B,    D,       G
 ///
 ///
 /// Note that the examples show optimal visist sets but not necessarily the ones
 /// derived by the explorer depending on the available CFG analyses (see
 /// MustBeExecutedContextExplorer). Also note that we, depending on the options,
 /// the visit set can contain instructions from other functions.
+///
+/// Depending on the template parameter \p CachedOnly, the iterator will either
+/// only visit existing instructions in the interval (\p CachedOnly == true) or
+/// also use the MustBeExecutedContextExplorer to extend the intervals if
+/// needed.
 struct MustBeExecutedIterator {
   /// Type declarations that make his class an input iterator.
   ///{
   typedef const Instruction *value_type;
   typedef std::ptrdiff_t difference_type;
   typedef const Instruction **pointer;
   typedef const Instruction *&reference;
   typedef std::input_iterator_tag iterator_category;
   ///}
 
-  using ExplorerTy = MustBeExecutedContextExplorer;
-
-  MustBeExecutedIterator(const MustBeExecutedIterator &Other)
-      : Visited(Other.Visited), Explorer(Other.Explorer),
-        CurInst(Other.CurInst), Head(Other.Head), Tail(Other.Tail) {}
-
-  MustBeExecutedIterator(MustBeExecutedIterator &&Other)
-      : Visited(std::move(Other.Visited)), Explorer(Other.Explorer),
-        CurInst(Other.CurInst), Head(Other.Head), Tail(Other.Tail) {}
-
-  MustBeExecutedIterator &operator=(MustBeExecutedIterator &&Other) {
-    if (this != &Other) {
-      std::swap(Visited, Other.Visited);
-      std::swap(CurInst, Other.CurInst);
-      std::swap(Head, Other.Head);
-      std::swap(Tail, Other.Tail);
-    }
-    return *this;
-  }
-
-  ~MustBeExecutedIterator() {}
-
-  /// Pre- and post-increment operators.
+  /// Pre- and post-increment operators. Both can cause the underlying intervals
+  /// to be extended if this is not a cached-only iterator, that is if an
+  /// explorer was provided at creation time.
   ///{
   MustBeExecutedIterator &operator++() {
-    CurInst = advance();
+    advance();
     return *this;
   }
 
   MustBeExecutedIterator operator++(int) {
     MustBeExecutedIterator tmp(*this);
     operator++();
     return tmp;
   }
   ///}
 
   /// Equality and inequality operators. Note that we ignore the history here.
   ///{
   bool operator==(const MustBeExecutedIterator &Other) const {
-    return CurInst == Other.CurInst && Head == Other.Head && Tail == Other.Tail;
+    return Pos[0] == Other.Pos[0] && Pos[1] == Other.Pos[1];
   }
 
   bool operator!=(const MustBeExecutedIterator &Other) const {
     return !(*this == Other);
   }
   ///}
 
   /// Return the underlying instruction.
-  const Instruction *&operator*() { return CurInst; }
-  const Instruction *getCurrentInst() const { return CurInst; }
+  const Instruction *operator*() const { return getCurrentInst(); }
+  const Instruction *getCurrentInst() const { return Pos[0].getInstruction(); }
+
+  /// Return true if \p I is known to be found by this iterator, thus to be
+  /// executed with the instruction this iterator was created for. If the known
+  /// context does not contain \p I, the non-const version will try to use the
+  /// Explorer, if available, to extend it.
+  bool isExecutedWith(const Instruction &I) const;
+
+  /// Configurable print method for debugging purposes.
+  ///
+  /// \param OS            The stream we print to.
+  /// \param PrintInst     If set, the current instruction is printed.
+  /// \param PrintInterval If set, the interval containing the current
+  ///                      instruction is printed.
+  void print(raw_ostream &OS, bool PrintInst, bool PrintInterval) const {
+    if (PrintInst && getCurrentInst())
+      OS << "[" << *getCurrentInst() << "]";
 
-  /// Return true if \p I was encountered by this iterator already.
-  bool count(const Instruction *I) const {
-    return Visited.count({I, ExplorationDirection::FORWARD}) ||
-           Visited.count({I, ExplorationDirection::BACKWARD});
+    if (PrintInterval)
+      Pos[0].print(OS, false);
   }
 
 private:
-  using VisitedSetTy =
-      DenseSet<PointerIntPair<const Instruction *, 1, ExplorationDirection>>;
-
   /// Private constructors.
-  MustBeExecutedIterator(ExplorerTy &Explorer, const Instruction *I);
-
-  /// Reset the iterator to its initial state pointing at \p I.
-  void reset(const Instruction *I);
-
-  /// Reset the iterator to point at \p I, keep cached state.
-  void resetInstruction(const Instruction *I);
-
-  /// Try to advance one of the underlying positions (Head or Tail).
-  ///
-  /// \return The next instruction in the must be executed context, or nullptr
-  ///         if none was found.
-  const Instruction *advance();
-
-  /// A set to track the visited instructions in order to deal with endless
-  /// loops and recursion.
-  VisitedSetTy Visited;
-
-  /// A reference to the explorer that created this iterator.
-  ExplorerTy &Explorer;
-
-  /// The instruction we are currently exposing to the user. There is always an
-  /// instruction that we know is executed with the given program point,
-  /// initially the program point itself.
-  const Instruction *CurInst;
-
-  /// Two positions that mark the program points where this iterator will look
-  /// for the next instruction. Note that the current instruction is either the
-  /// one pointed to by Head, Tail, or both.
-  const Instruction *Head, *Tail;
+  MustBeExecutedIterator() {}
+  MustBeExecutedIterator(const MustBeExecutedInterval::Position &FwdPos,
+                         const MustBeExecutedInterval::Position &BwdPos,
+                         MustBeExecutedContextExplorer *Explorer)
+      : Explorer(Explorer) {
+    Pos[0] = FwdPos;
+    Pos[1] = BwdPos;
+  }
+
+  /// Advance one of the underlying positions (Head or Tail) potentially after
+  /// exploring the context further (using Explorer). If this is not possible
+  /// the positions (Pos) are invalidated.
+  bool advance();
+
+  /// The explorer that can be used to explore the context further if an end is
+  /// found. If none is given the iterator will only traverse the
+  /// existing/cached context otherwise the explorer is used to explore further.
+  ///
+  /// TODO: Determine if we should pass the explorer where needed.
+  MustBeExecutedContextExplorer *Explorer = nullptr;
+
+  /// Two interval positions that mark the program points where this iterator
+  /// will look for the next instruction. Note that the current instruction is
+  /// the one pointed to by Pos[0]. Once Pos[0] is explored to the fullest and
+  /// becomes invalid we swap the two positions. If both positions are invalid
+  /// the iterator traversed the entire context.
+  MustBeExecutedInterval::Position Pos[2];
 
   friend struct MustBeExecutedContextExplorer;
 };
 
 /// A "must be executed context" for a given program point PP is the set of
 /// instructions, potentially before and after PP, that are executed always when
 /// PP is reached. The MustBeExecutedContextExplorer an interface to explore
 /// "must be executed contexts" in a module through the use of
 /// MustBeExecutedIterator.
 ///
 /// The explorer exposes "must be executed iterators" that traverse the must be
 /// executed context. There is little information sharing between iterators as
 /// the expected use case involves few iterators for "far apart" instructions.
 /// If that changes, we should consider caching more intermediate results.
 struct MustBeExecutedContextExplorer {
+  using IntervalPosition = MustBeExecutedInterval::Position;
 
   /// In the description of the parameters we use PP to denote a program point
   /// for which the must be executed context is explored, or put differently,
   /// for which the MustBeExecutedIterator is created.
   ///
   /// \param ExploreInterBlock    Flag to indicate if instructions in blocks
   ///                             other than the parent of PP should be
   ///                             explored.
MustBeExecutedContextExplorer(
           [](const Function &) { return nullptr; },
       GetterTy<const DominatorTree> DTGetter =
           [](const Function &) { return nullptr; },
       GetterTy<const PostDominatorTree> PDTGetter =
           [](const Function &) { return nullptr; })
       : ExploreInterBlock(ExploreInterBlock),
         ExploreCFGForward(ExploreCFGForward),
         ExploreCFGBackward(ExploreCFGBackward), LIGetter(LIGetter),
-        DTGetter(DTGetter), PDTGetter(PDTGetter), EndIterator(*this, nullptr) {}
-
-  /// Clean up the dynamically allocated iterators.
-  ~MustBeExecutedContextExplorer() {
-    DeleteContainerSeconds(InstructionIteratorMap);
-  }
+        DTGetter(DTGetter), PDTGetter(PDTGetter) {}
 
   /// Iterator-based interface. \see MustBeExecutedIterator.
   ///{
   using iterator = MustBeExecutedIterator;
   using const_iterator = const MustBeExecutedIterator;
 
   /// Return an iterator to explore the context around \p PP.
-  iterator &begin(const Instruction *PP) {
-    auto *&It = InstructionIteratorMap[PP];
-    if (!It)
-      It = new iterator(*this, PP);
-    return *It;
+  iterator begin(const Instruction &PP) {
+    return iterator(
+        getOrCreateIntervalPosition(PP, ExplorationDirection::FORWARD),
+        getOrCreateIntervalPosition(PP, ExplorationDirection::BACKWARD), this);
   }
 
   /// Return an iterator to explore the cached context around \p PP.
-  const_iterator &begin(const Instruction *PP) const {
-    return *InstructionIteratorMap.lookup(PP);
+  const_iterator cached_begin(const Instruction &PP) const {
+    return iterator(lookupIntervalPosition(PP, ExplorationDirection::FORWARD),
+                    lookupIntervalPosition(PP, ExplorationDirection::BACKWARD),
+                    nullptr);
   }
 
   /// Return an universal end iterator.
   ///{
-  iterator &end() { return EndIterator; }
-  iterator &end(const Instruction *) { return EndIterator; }
+  iterator end() { return iterator(); }
+  iterator end(const Instruction &) { return iterator(); }
 
-  const_iterator &end() const { return EndIterator; }
-  const_iterator &end(const Instruction *) const { return EndIterator; }
+  const_iterator cached_end() const { return const_iterator(); }
+  const_iterator cached_end(const Instruction &) const {
+    return const_iterator();
+  }
   ///}
 
   /// Return an iterator range to explore the context around \p PP.
-  llvm::iterator_range<iterator> range(const Instruction *PP) {
+  llvm::iterator_range<iterator> range(const Instruction &PP) {
     return llvm::make_range(begin(PP), end(PP));
   }
 
   /// Return an iterator range to explore the cached context around \p PP.
-  llvm::iterator_range<const_iterator> range(const Instruction *PP) const {
-    return llvm::make_range(begin(PP), end(PP));
+  llvm::iterator_range<const_iterator>
+  cached_range(const Instruction &PP) const {
+    return llvm::make_range(cached_begin(PP), cached_end(PP));
   }
   ///}
 
   /// Check \p Pred on all instructions in the context.
   ///
   /// This method will evaluate \p Pred and return
   /// true if \p Pred holds in every instruction.
-  bool checkForAllContext(const Instruction *PP,
+  ///
+  ///{
+  bool checkForAllInContext(const Instruction &PP,
                             function_ref<bool(const Instruction *)> Pred) {
-    for (auto EIt = begin(PP), EEnd = end(PP); EIt != EEnd; ++EIt)
-      if (!Pred(*EIt))
-        return false;
-    return true;
+    return llvm::all_of(range(PP), Pred);
   }
-
-  /// Helper to look for \p I in the context of \p PP.
-  ///
-  /// The context is expanded until \p I was found or no more expansion is
-  /// possible.
-  ///
-  /// \returns True, iff \p I was found.
-  bool findInContextOf(const Instruction *I, const Instruction *PP) {
-    auto EIt = begin(PP), EEnd = end(PP);
-    return findInContextOf(I, EIt, EEnd);
+  bool
+  checkForCachedInContext(const Instruction &PP,
+                          function_ref<bool(const Instruction *)> Pred) const {
+    return llvm::all_of(cached_range(PP), Pred);
   }
+  ///}
 
-  /// Helper to look for \p I in the context defined by \p EIt and \p EEnd.
+  /// Helper to look for \p I in the context of \p PP.
   ///
-  /// The context is expanded until \p I was found or no more expansion is
-  /// possible.
+  /// In the non-const variant the context is expanded until \p I was found or
+  /// no more expansion is possible. If a dominator tree getter was provided it
+  /// is used to circumvent the search.
   ///
   /// \returns True, iff \p I was found.
-  bool findInContextOf(const Instruction *I, iterator &EIt, iterator &EEnd) {
-    bool Found = EIt.count(I);
-    while (!Found && EIt != EEnd)
-      Found = (++EIt).getCurrentInst() == I;
-    return Found;
+  bool findInContextOf(const Instruction &I, const Instruction &PP) {
+    const DominatorTree *DT = DTGetter(*I.getFunction());
+    if (DT && DT->dominates(&I, &PP))
+      return true;
+    return begin(PP).isExecutedWith(I);
   }
 
   /// Return the next instruction that is guaranteed to be executed after \p PP.
   ///
-  /// \param It              The iterator that is used to traverse the must be
-  ///                        executed context.
   /// \param PP              The program point for which the next instruction
   ///                        that is guaranteed to execute is determined.
-  const Instruction *
-  getMustBeExecutedNextInstruction(MustBeExecutedIterator &It,
-                                   const Instruction *PP);
+  const Instruction *getMustBeExecutedNextInstruction(const Instruction &PP) {
+    const IntervalPosition &Pos =
+        getOrCreateIntervalPosition(PP, ExplorationDirection::FORWARD);
+    return (++iterator(Pos, IntervalPosition(), this)).getCurrentInst();
+  }
+
   /// Return the previous instr. that is guaranteed to be executed before \p PP.
   ///
-  /// \param It              The iterator that is used to traverse the must be
-  ///                        executed context.
   /// \param PP              The program point for which the previous instr.
   ///                        that is guaranteed to execute is determined.
-  const Instruction *
-  getMustBeExecutedPrevInstruction(MustBeExecutedIterator &It,
-                                   const Instruction *PP);
+  const Instruction *getMustBeExecutedPrevInstruction(const Instruction &PP) {
+    const IntervalPosition &Pos =
+        getOrCreateIntervalPosition(PP, ExplorationDirection::FORWARD);
+    return (++iterator(Pos, IntervalPosition(), this)).getCurrentInst();
+  }
 
   /// Find the next join point from \p InitBB in forward direction.
   const BasicBlock *findForwardJoinPoint(const BasicBlock *InitBB);
 
   /// Find the next join point from \p InitBB in backward direction.
   const BasicBlock *findBackwardJoinPoint(const BasicBlock *InitBB);
 
   /// Parameter that limit the performed exploration. See the constructor for
   /// their meaning.
   ///{
   const bool ExploreInterBlock;
   const bool ExploreCFGForward;
   const bool ExploreCFGBackward;
   ///}
 
+  /// Return the next position that is guaranteed to be executed (at some
+  /// point but for sure) after \p P in the direction of the underlying
+  /// interval. If none is known returns an invalid position. Note that \p P has
+  /// to be a valid position.
+  IntervalPosition exploreNextPosition(const IntervalPosition &P);
+
 private:
+  /// Return an instruction that is known to be executed after \p PP.
+  const Instruction *exploreNextExecutedInstruction(const Instruction &PP);
+
+  /// Return an instruction that is known to be executed before \p PP.
+  const Instruction *explorePrevExecutedInstruction(const Instruction &PP);
+
+  /// Lookup the interval position for the instruction \p PP.
+  IntervalPosition lookupIntervalPosition(const Instruction &PP,
+                                          ExplorationDirection Dir) const {
+    return InstPositionMap[unsigned(Dir)].lookup(&PP);
+  }
+
+  /// Lookup or create a new interval position for the instruction \p PP.
+  ///
+  /// If \p PP was explored before, its interval position already exists and it
+  /// is returned. If \p PP was not explored before, we create a new interval
+  /// for it and make \p PP the center of the interval, thus the position at
+  /// offset 0. The new position is cached.
+  ///
+  /// \returns A position for which the current instruction is \p PP.
+  IntervalPosition getOrCreateIntervalPosition(const Instruction &PP,
+                                               ExplorationDirection Dir) {
+    IntervalPosition &Pos = InstPositionMap[unsigned(Dir)][&PP];
+
+    if (!Pos) {
+      MustBeExecutedInterval *Interval =
+          new (Allocator) MustBeExecutedInterval(PP, Dir);
+      Pos = IntervalPosition(Interval);
+    }
+
+    assert(Pos.getInstruction() == &PP &&
+           "Unexpected instruction at position!");
+    return Pos;
+  }
+
   /// Getters for common CFG analyses: LoopInfo, DominatorTree, and
   /// PostDominatorTree.
   ///{
   GetterTy<const LoopInfo> LIGetter;
   GetterTy<const DominatorTree> DTGetter;
   GetterTy<const PostDominatorTree> PDTGetter;
   ///}
 
-  /// Map to cache isGuaranteedToTransferExecutionToSuccessor results.
-  DenseMap<const BasicBlock *, Optional<bool>> BlockTransferMap;
-
   /// Map to cache containsIrreducibleCFG results.
-  DenseMap<const Function*, Optional<bool>> IrreducibleControlMap;
+  DenseMap<const Function *, Optional<bool>> IrreducibleControlMap;
 
-  /// Map from instructions to associated must be executed iterators.
-  DenseMap<const Instruction *, MustBeExecutedIterator *>
-      InstructionIteratorMap;
+  /// Two map from instructions to associated positions, one for each direction.
+  DenseMap<const Instruction *, IntervalPosition> InstPositionMap[2];
 
-  /// A unique end iterator.
-  MustBeExecutedIterator EndIterator;
+  /// The allocator used to allocate memory, e.g. for intervals.
+  BumpPtrAllocator Allocator;
 };
 
 } // namespace llvm
 
 #endif

llvm/lib/Analysis/MustExecute.cpp

bool MustBeExecutedContextPrinter::runOnModule(Module &M) {
   MustBeExecutedContextExplorer Explorer(
       /* ExploreInterBlock */ true,
       /* ExploreCFGForward */ true,
       /* ExploreCFGBackward */ true, LIGetter, DTGetter, PDTGetter);
 
   for (Function &F : M) {
     for (Instruction &I : instructions(F)) {
       dbgs() << "-- Explore context of: " << I << "\n";
-      for (const Instruction *CI : Explorer.range(&I))
+      for (const Instruction *CI : Explorer.range(I))
         dbgs() << "  [F: " << CI->getFunction()->getName() << "] " << *CI
                << "\n";
     }
   }
 
   DeleteContainerPointers(PDTs);
   DeleteContainerPointers(LIs);
   DeleteContainerPointers(DTs);
MustBeExecutedContextExplorer::findForwardJoinPoint(const BasicBlock *InitBB) {
   // are: infinite loops and instructions that do not necessarily transfer
   // execution to their successor. To check for them we traverse the CFG from
   // the adjacent blocks to the JoinBB, looking at all intermediate blocks.
 
   // If we know the function is "will-return" and "no-throw" there is no need
   // for futher checks.
   if (!F.hasFnAttribute(Attribute::WillReturn) || !F.doesNotThrow()) {
 
-    auto BlockTransfersExecutionToSuccessor = [](const BasicBlock *BB) {
-      return isGuaranteedToTransferExecutionToSuccessor(BB);
-    };
-
     SmallPtrSet<const BasicBlock *, 16> Visited;
     while (!Worklist.empty()) {
       const BasicBlock *ToBB = Worklist.pop_back_val();
       if (ToBB == JoinBB)
         continue;
 
       // Make sure all loops in-between are finite.
       if (!Visited.insert(ToBB).second) {
while (!Worklist.empty()) {
             return nullptr;
         }
 
         continue;
       }
 
       // Make sure the block has no instructions that could stop control
       // transfer.
-      bool TransfersExecution = getOrCreateCachedOptional(
-          ToBB, BlockTransferMap, BlockTransfersExecutionToSuccessor, ToBB);
+      bool TransfersExecution = isGuaranteedToTransferExecutionToSuccessor(ToBB);
       if (!TransfersExecution)
         return nullptr;
 
       for (const BasicBlock *AdjacentBB : successors(ToBB))
         Worklist.push_back(AdjacentBB);
     }
   }
 
   LLVM_DEBUG(dbgs() << "\tJoin block: " << JoinBB->getName() << "\n");
   return JoinBB;
 }
+
 const BasicBlock *
 MustBeExecutedContextExplorer::findBackwardJoinPoint(const BasicBlock *InitBB) {
   const LoopInfo *LI = LIGetter(*InitBB->getParent());
   const DominatorTree *DT = DTGetter(*InitBB->getParent());
   LLVM_DEBUG(dbgs() << "\tFind backward join point for " << InitBB->getName()
                     << (LI ? " [LI]" : "") << (DT ? " [DT]" : ""));
 
   // Try to determine a join block through the help of the dominance tree. If no
MustBeExecutedContextExplorer::findBackwardJoinPoint(const BasicBlock *InitBB) {
 
   // In backwards direction there is no need to show termination of previous
   // instructions. If they do not terminate, the code afterward is dead, making
   // any information/transformation correct anyway.
   return JoinBB;
 }
 
 const Instruction *
-MustBeExecutedContextExplorer::getMustBeExecutedNextInstruction(
-    MustBeExecutedIterator &It, const Instruction *PP) {
-  if (!PP)
-    return PP;
-  LLVM_DEBUG(dbgs() << "Find next instruction for " << *PP << "\n");
+MustBeExecutedContextExplorer::exploreNextExecutedInstruction(
+    const Instruction &PP) {
+  LLVM_DEBUG(dbgs() << "Find next instruction for " << PP << "\n");
 
   // If we explore only inside a given basic block we stop at terminators.
-  if (!ExploreInterBlock && PP->isTerminator()) {
+  if (!ExploreInterBlock && PP.isTerminator()) {
     LLVM_DEBUG(dbgs() << "\tReached terminator in intra-block mode, done\n");
     return nullptr;
   }
 
   // If we do not traverse the call graph we check if we can make progress in
   // the current function. First, check if the instruction is guaranteed to
   // transfer execution to the successor.
-  bool TransfersExecution = isGuaranteedToTransferExecutionToSuccessor(PP);
+  bool TransfersExecution = isGuaranteedToTransferExecutionToSuccessor(&PP);
   if (!TransfersExecution)
     return nullptr;
 
   // If this is not a terminator we know that there is a single instruction
   // after this one that is executed next if control is transfered. If not,
   // we can try to go back to a call site we entered earlier. If none exists, we
   // do not know any instruction that has to be executd next.
-  if (!PP->isTerminator()) {
-    const Instruction *NextPP = PP->getNextNode();
-    LLVM_DEBUG(dbgs() << "\tIntermediate instruction does transfer control\n");
+  if (!PP.isTerminator()) {
+    const Instruction *NextPP = PP.getNextNode();
+    LLVM_DEBUG(dbgs() << "\tIntermediate instruction does transfer control: "
+                      << *NextPP << "\n");
     return NextPP;
   }
 
   // Finally, we have to handle terminators, trivial ones first.
-  assert(PP->isTerminator() && "Expected a terminator!");
+  assert(PP.isTerminator() && "Expected a terminator!");
 
   // A terminator without a successor is not handled yet.
-  if (PP->getNumSuccessors() == 0) {
+  unsigned NumSuccBBs = PP.getNumSuccessors();
+  if (NumSuccBBs == 0) {
     LLVM_DEBUG(dbgs() << "\tUnhandled terminator\n");
     return nullptr;
   }
 
   // A terminator with a single successor, we will continue at the beginning of
   // that one.
-  if (PP->getNumSuccessors() == 1) {
-    LLVM_DEBUG(
-        dbgs() << "\tUnconditional terminator, continue with successor\n");
-    return &PP->getSuccessor(0)->front();
+  if (NumSuccBBs == 1) {
+    const Instruction *NextPP = &PP.getSuccessor(0)->front();
+    LLVM_DEBUG(dbgs() << "\tUnconditional terminator, continue with successor: "
+                      << *NextPP << "\n");
+    return NextPP;
   }
 
   // Multiple successors mean we need to find the join point where control flow
   // converges again. We use the findForwardJoinPoint helper function with
   // information about the function and helper analyses, if available.
-  if (const BasicBlock *JoinBB = findForwardJoinPoint(PP->getParent()))
+  if (const BasicBlock *JoinBB = findForwardJoinPoint(PP.getParent()))
     return &JoinBB->front();
 
   LLVM_DEBUG(dbgs() << "\tNo join point found\n");
   return nullptr;
 }
 
 const Instruction *
-MustBeExecutedContextExplorer::getMustBeExecutedPrevInstruction(
-    MustBeExecutedIterator &It, const Instruction *PP) {
-  if (!PP)
-    return PP;
-
-  bool IsFirst = !(PP->getPrevNode());
-  LLVM_DEBUG(dbgs() << "Find next instruction for " << *PP
-                    << (IsFirst ? " [IsFirst]" : "") << "\n");
+MustBeExecutedContextExplorer::explorePrevExecutedInstruction(
+    const Instruction &PP) {
+
+  const Instruction *PrevPP = PP.getPrevNode();
+  LLVM_DEBUG(dbgs() << "Find previous instruction for " << PP
+                    << (!PrevPP ? " [IsFirst]" : "") << "\n");
 
   // If we explore only inside a given basic block we stop at the first
   // instruction.
-  if (!ExploreInterBlock && IsFirst) {
+  if (!ExploreInterBlock && !PrevPP) {
     LLVM_DEBUG(dbgs() << "\tReached block front in intra-block mode, done\n");
     return nullptr;
   }
 
   // The block and function that contains the current position.
-  const BasicBlock *PPBlock = PP->getParent();
+  const BasicBlock *PPBlock = PP.getParent();
 
   // If we are inside a block we know what instruction was executed before, the
   // previous one.
-  if (!IsFirst) {
-    const Instruction *PrevPP = PP->getPrevNode();
-    LLVM_DEBUG(
-        dbgs() << "\tIntermediate instruction, continue with previous\n");
-    // We did not enter a callee so we simply return the previous instruction.
+  if (PrevPP) {
+    LLVM_DEBUG(dbgs() << "\tIntermediate instruction, continue with previous: "
+                      << *PrevPP << "\n");
     return PrevPP;
   }
 
   // Finally, we have to handle the case where the program point is the first in
   // a block but not in the function. We use the findBackwardJoinPoint helper
   // function with information about the function and helper analyses, if
   // available.
   if (const BasicBlock *JoinBB = findBackwardJoinPoint(PPBlock))
     return &JoinBB->back();
 
   LLVM_DEBUG(dbgs() << "\tNo join point found\n");
   return nullptr;
 }
 
-MustBeExecutedIterator::MustBeExecutedIterator(
-    MustBeExecutedContextExplorer &Explorer, const Instruction *I)
-    : Explorer(Explorer), CurInst(I) {
-  reset(I);
-}
-
-void MustBeExecutedIterator::reset(const Instruction *I) {
-  Visited.clear();
-  resetInstruction(I);
-}
-
-void MustBeExecutedIterator::resetInstruction(const Instruction *I) {
-  CurInst = I;
-  Head = Tail = nullptr;
-  Visited.insert({I, ExplorationDirection::FORWARD});
-  Visited.insert({I, ExplorationDirection::BACKWARD});
-  if (Explorer.ExploreCFGForward)
-    Head = I;
-  if (Explorer.ExploreCFGBackward)
-    Tail = I;
-}
-
-const Instruction *MustBeExecutedIterator::advance() {
-  assert(CurInst && "Cannot advance an end iterator!");
-  Head = Explorer.getMustBeExecutedNextInstruction(*this, Head);
-  if (Head && Visited.insert({Head, ExplorationDirection ::FORWARD}).second)
-    return Head;
-  Head = nullptr;
-
-  Tail = Explorer.getMustBeExecutedPrevInstruction(*this, Tail);
-  if (Tail && Visited.insert({Tail, ExplorationDirection ::BACKWARD}).second)
-    return Tail;
-  Tail = nullptr;
-  return nullptr;
+MustBeExecutedContextExplorer::IntervalPosition
+MustBeExecutedContextExplorer::exploreNextPosition(const IntervalPosition &P) {
+  assert(P.getInterval() && P.getInstruction() && "Unexpected position state!");
+
+  assert(!(++IntervalPosition(P)) &&
+         "Exploration called on already explored interval");
+
+  MustBeExecutedInterval &Interval = *P.getInterval();
+  assert(!Interval.getNextInterval() &&
+         "Exploration called on already explored interval");
+  if (Interval.isFinalized())
+    return IntervalPosition();
+
+  const Instruction *NewI = nullptr;
+  ExplorationDirection Dir = Interval.getDirection();
+  if (Dir == ExplorationDirection::FORWARD)
+    NewI = exploreNextExecutedInstruction(*P.getInstruction());
+  else
+    NewI = explorePrevExecutedInstruction(*P.getInstruction());
+
+  if (NewI) {
+    // We found an instruction executed after/before the given position P. If
+    // the instruction is not part of an interval yet we add it to the one of
+    // the position P, otherwise the one of the position Pis linked to the
+    // position of the instruction executed after/before.
+    IntervalPosition &NewIPos = InstPositionMap[unsigned(Dir)][NewI];
+    if (!NewIPos && Interval.extend(*NewI)) {
+      NewIPos = P;
+      return ++NewIPos;
+    }
+
+    if (NewIPos && Interval.setPosInNextInterval(NewIPos))
+      return NewIPos;
+  }
+
+  // We failed to extend the interval so we finalize it and never try again.
+  Interval.finalize();
+  return IntervalPosition();
+}
+
+bool MustBeExecutedIterator::advance() {
+  if (!Pos[0]) {
+    assert(!Pos[1] && "Unexpected iterator state!");
+    return false;
+  }
+
+  // First, check if we explored a new position already. We have to be careful
+  // not to forget the old position if we cannot advance it.
+  MustBeExecutedInterval::Position Tmp = Pos[0];
+  if (++Tmp) {
+    Pos[0] = Tmp;
+    return true;
+  }
+
+  // We reached the boundaries of the known underlying interval and need to
+  // explore further. Note that exploration can fail, e.g., there is no known
+  // "next" instruction. If it does succeed, the interval is either extended
+  // or linked to another one by the explorer. In either case we need to
+  // advance to the new position.
+  if (Explorer)
+    if ((Pos[0] = Explorer->exploreNextPosition(Pos[0])))
+      return true;
+
+  assert(!Pos[0] && "Inconsistent state!");
+  std::swap(Pos[0], Pos[1]);
+  return advance();
+}
+
+bool MustBeExecutedIterator::isExecutedWith(const Instruction &I) const {
+  auto Tmp = *this;
+  do {
+    if (Tmp.getCurrentInst() == &I)
+      return true;
+  } while (Tmp.advance());
+  return false;
 }

llvm/lib/Transforms/IPO/Attributor.cpp

bool IRPosition::getAttrsFromAssumes(Attribute::AttrKind AK,
   // explorer iterators.
   if (A2K.empty())
     return false;
 
   LLVMContext &Ctx = AssociatedValue.getContext();
   unsigned AttrsSize = Attrs.size();
   MustBeExecutedContextExplorer &Explorer =
       A.getInfoCache().getMustBeExecutedContextExplorer();
-  auto EIt = Explorer.begin(getCtxI()), EEnd = Explorer.end(getCtxI());
+  Instruction &CtxI = *getCtxI();
   for (auto &It : A2K)
-    if (Explorer.findInContextOf(It.first, EIt, EEnd))
+    if (Explorer.findInContextOf(*It.first, CtxI))
       Attrs.push_back(Attribute::get(Ctx, AK, It.second.Max));
   return AttrsSize != Attrs.size();
 }
 
 void IRPosition::verify() {
   switch (KindOrArgNo) {
   default:
     assert(KindOrArgNo >= 0 && "Expected argument or call site argument!");

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

void initialize(Attributor &A) override {
     //      if (b) {
     //        *ptr = 0;
     //      } else {
     //        *ptr = 1;
     //      }
     //    }
     // }
 
-    Explorer.checkForAllContext(CtxI, Pred);
+    Explorer.checkForAllInContext(*CtxI, Pred);
     for (const BranchInst *Br : BrInsts) {
       StateType ParentState;
 
       // The known state of the parent state is a conjunction of children's
       // known states so it is initialized with a best state.
       ParentState.indicateOptimisticFixpoint();
 
       for (const BasicBlock *BB : Br->successors()) {
ChangeStatus updateImpl(Attributor &A) override {
     return ChangeStatus::UNCHANGED;
   }
 
   /// Helper function to accumulate uses.
   void followUsesInContext(Attributor &A,
                            MustBeExecutedContextExplorer &Explorer,
                            const Instruction *CtxI,
                            SetVector<const Use *> &Uses, StateType &State) {
-    auto EIt = Explorer.begin(CtxI), EEnd = Explorer.end(CtxI);
     for (unsigned u = 0; u < Uses.size(); ++u) {
       const Use *U = Uses[u];
       if (const Instruction *UserI = dyn_cast<Instruction>(U->getUser())) {
-        bool Found = Explorer.findInContextOf(UserI, EIt, EEnd);
+        bool Found = Explorer.findInContextOf(*UserI, *CtxI);
         if (Found && Base::followUse(A, U, UserI, State))
           for (const Use &Us : UserI->uses())
             Uses.insert(&Us);
       }
     }
   }
 };
 
ChangeStatus AAHeapToStackImpl::updateImpl(Attributor &A) {
   MustBeExecutedContextExplorer &Explorer =
       A.getInfoCache().getMustBeExecutedContextExplorer();
 
   auto FreeCheck = [&](Instruction &I) {
     const auto &Frees = FreesForMalloc.lookup(&I);
     if (Frees.size() != 1)
       return false;
     Instruction *UniqueFree = *Frees.begin();
-    return Explorer.findInContextOf(UniqueFree, I.getNextNode());
+    return Explorer.findInContextOf(*UniqueFree, *I.getNextNode());
   };
 
   auto UsesCheck = [&](Instruction &I) {
     bool ValidUsesOnly = true;
     bool MustUse = true;
     auto Pred = [&](const Use &U, bool &Follow) -> bool {
       Instruction *UserI = cast<Instruction>(U.getUser());
       if (isa<LoadInst>(UserI))