1 files changed, 259 insertions, 0 deletions
diff --git a/clang-r353983e/include/llvm/Analysis/LoopIterator.h b/clang-r353983e/include/llvm/Analysis/LoopIterator.h
new file mode 100644
index 00000000..fa4da428
--- /dev/null
+++ b/clang-r353983e/include/llvm/Analysis/LoopIterator.h
@@ -0,0 +1,259 @@
+//===--------- LoopIterator.h - Iterate over loop blocks --------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+// This file defines iterators to visit the basic blocks within a loop.
+//
+// These iterators currently visit blocks within subloops as well.
+// Unfortunately we have no efficient way of summarizing loop exits which would
+// allow skipping subloops during traversal.
+//
+// If you want to visit all blocks in a loop and don't need an ordered traveral,
+// use Loop::block_begin() instead.
+//
+// This is intentionally designed to work with ill-formed loops in which the
+// backedge has been deleted. The only prerequisite is that all blocks
+// contained within the loop according to the most recent LoopInfo analysis are
+// reachable from the loop header.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_LOOPITERATOR_H
+#define LLVM_ANALYSIS_LOOPITERATOR_H
+
+#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/Analysis/LoopInfo.h"
+
+namespace llvm {
+
+class LoopBlocksTraversal;
+
+// A traits type that is intended to be used in graph algorithms. The graph
+// traits starts at the loop header, and traverses the BasicBlocks that are in
+// the loop body, but not the loop header. Since the loop header is skipped,
+// the back edges are excluded.
+//
+// TODO: Explore the possibility to implement LoopBlocksTraversal in terms of
+//       LoopBodyTraits, so that insertEdge doesn't have to be specialized.
+struct LoopBodyTraits {
+  using NodeRef = std::pair<const Loop *, BasicBlock *>;
+
+  // This wraps a const Loop * into the iterator, so we know which edges to
+  // filter out.
+  class WrappedSuccIterator
+      : public iterator_adaptor_base<
+            WrappedSuccIterator, succ_iterator,
+            typename std::iterator_traits<succ_iterator>::iterator_category,
+            NodeRef, std::ptrdiff_t, NodeRef *, NodeRef> {
+    using BaseT = iterator_adaptor_base<
+        WrappedSuccIterator, succ_iterator,
+        typename std::iterator_traits<succ_iterator>::iterator_category,
+        NodeRef, std::ptrdiff_t, NodeRef *, NodeRef>;
+
+    const Loop *L;
+
+  public:
+    WrappedSuccIterator(succ_iterator Begin, const Loop *L)
+        : BaseT(Begin), L(L) {}
+
+    NodeRef operator*() const { return {L, *I}; }
+  };
+
+  struct LoopBodyFilter {
+    bool operator()(NodeRef N) const {
+      const Loop *L = N.first;
+      return N.second != L->getHeader() && L->contains(N.second);
+    }
+  };
+
+  using ChildIteratorType =
+      filter_iterator<WrappedSuccIterator, LoopBodyFilter>;
+
+  static NodeRef getEntryNode(const Loop &G) { return {&G, G.getHeader()}; }
+
+  static ChildIteratorType child_begin(NodeRef Node) {
+    return make_filter_range(make_range<WrappedSuccIterator>(
+                                 {succ_begin(Node.second), Node.first},
+                                 {succ_end(Node.second), Node.first}),
+                             LoopBodyFilter{})
+        .begin();
+  }
+
+  static ChildIteratorType child_end(NodeRef Node) {
+    return make_filter_range(make_range<WrappedSuccIterator>(
+                                 {succ_begin(Node.second), Node.first},
+                                 {succ_end(Node.second), Node.first}),
+                             LoopBodyFilter{})
+        .end();
+  }
+};
+
+/// Store the result of a depth first search within basic blocks contained by a
+/// single loop.
+///
+/// TODO: This could be generalized for any CFG region, or the entire CFG.
+class LoopBlocksDFS {
+public:
+  /// Postorder list iterators.
+  typedef std::vector<BasicBlock*>::const_iterator POIterator;
+  typedef std::vector<BasicBlock*>::const_reverse_iterator RPOIterator;
+
+  friend class LoopBlocksTraversal;
+
+private:
+  Loop *L;
+
+  /// Map each block to its postorder number. A block is only mapped after it is
+  /// preorder visited by DFS. It's postorder number is initially zero and set
+  /// to nonzero after it is finished by postorder traversal.
+  DenseMap<BasicBlock*, unsigned> PostNumbers;
+  std::vector<BasicBlock*> PostBlocks;
+
+public:
+  LoopBlocksDFS(Loop *Container) :
+    L(Container), PostNumbers(NextPowerOf2(Container->getNumBlocks())) {
+    PostBlocks.reserve(Container->getNumBlocks());
+  }
+
+  Loop *getLoop() const { return L; }
+
+  /// Traverse the loop blocks and store the DFS result.
+  void perform(LoopInfo *LI);
+
+  /// Return true if postorder numbers are assigned to all loop blocks.
+  bool isComplete() const { return PostBlocks.size() == L->getNumBlocks(); }
+
+  /// Iterate over the cached postorder blocks.
+  POIterator beginPostorder() const {
+    assert(isComplete() && "bad loop DFS");
+    return PostBlocks.begin();
+  }
+  POIterator endPostorder() const { return PostBlocks.end(); }
+
+  /// Reverse iterate over the cached postorder blocks.
+  RPOIterator beginRPO() const {
+    assert(isComplete() && "bad loop DFS");
+    return PostBlocks.rbegin();
+  }
+  RPOIterator endRPO() const { return PostBlocks.rend(); }
+
+  /// Return true if this block has been preorder visited.
+  bool hasPreorder(BasicBlock *BB) const { return PostNumbers.count(BB); }
+
+  /// Return true if this block has a postorder number.
+  bool hasPostorder(BasicBlock *BB) const {
+    DenseMap<BasicBlock*, unsigned>::const_iterator I = PostNumbers.find(BB);
+    return I != PostNumbers.end() && I->second;
+  }
+
+  /// Get a block's postorder number.
+  unsigned getPostorder(BasicBlock *BB) const {
+    DenseMap<BasicBlock*, unsigned>::const_iterator I = PostNumbers.find(BB);
+    assert(I != PostNumbers.end() && "block not visited by DFS");
+    assert(I->second && "block not finished by DFS");
+    return I->second;
+  }
+
+  /// Get a block's reverse postorder number.
+  unsigned getRPO(BasicBlock *BB) const {
+    return 1 + PostBlocks.size() - getPostorder(BB);
+  }
+
+  void clear() {
+    PostNumbers.clear();
+    PostBlocks.clear();
+  }
+};
+
+/// Wrapper class to LoopBlocksDFS that provides a standard begin()/end()
+/// interface for the DFS reverse post-order traversal of blocks in a loop body.
+class LoopBlocksRPO {
+private:
+  LoopBlocksDFS DFS;
+
+public:
+  LoopBlocksRPO(Loop *Container) : DFS(Container) {}
+
+  /// Traverse the loop blocks and store the DFS result.
+  void perform(LoopInfo *LI) {
+    DFS.perform(LI);
+  }
+
+  /// Reverse iterate over the cached postorder blocks.
+  LoopBlocksDFS::RPOIterator begin() const { return DFS.beginRPO(); }
+  LoopBlocksDFS::RPOIterator end() const { return DFS.endRPO(); }
+};
+
+/// Specialize po_iterator_storage to record postorder numbers.
+template<> class po_iterator_storage<LoopBlocksTraversal, true> {
+  LoopBlocksTraversal &LBT;
+public:
+  po_iterator_storage(LoopBlocksTraversal &lbs) : LBT(lbs) {}
+  // These functions are defined below.
+  bool insertEdge(Optional<BasicBlock *> From, BasicBlock *To);
+  void finishPostorder(BasicBlock *BB);
+};
+
+/// Traverse the blocks in a loop using a depth-first search.
+class LoopBlocksTraversal {
+public:
+  /// Graph traversal iterator.
+  typedef po_iterator<BasicBlock*, LoopBlocksTraversal, true> POTIterator;
+
+private:
+  LoopBlocksDFS &DFS;
+  LoopInfo *LI;
+
+public:
+  LoopBlocksTraversal(LoopBlocksDFS &Storage, LoopInfo *LInfo) :
+    DFS(Storage), LI(LInfo) {}
+
+  /// Postorder traversal over the graph. This only needs to be done once.
+  /// po_iterator "automatically" calls back to visitPreorder and
+  /// finishPostorder to record the DFS result.
+  POTIterator begin() {
+    assert(DFS.PostBlocks.empty() && "Need clear DFS result before traversing");
+    assert(DFS.L->getNumBlocks() && "po_iterator cannot handle an empty graph");
+    return po_ext_begin(DFS.L->getHeader(), *this);
+  }
+  POTIterator end() {
+    // po_ext_end interface requires a basic block, but ignores its value.
+    return po_ext_end(DFS.L->getHeader(), *this);
+  }
+
+  /// Called by po_iterator upon reaching a block via a CFG edge. If this block
+  /// is contained in the loop and has not been visited, then mark it preorder
+  /// visited and return true.
+  ///
+  /// TODO: If anyone is interested, we could record preorder numbers here.
+  bool visitPreorder(BasicBlock *BB) {
+    if (!DFS.L->contains(LI->getLoopFor(BB)))
+      return false;
+
+    return DFS.PostNumbers.insert(std::make_pair(BB, 0)).second;
+  }
+
+  /// Called by po_iterator each time it advances, indicating a block's
+  /// postorder.
+  void finishPostorder(BasicBlock *BB) {
+    assert(DFS.PostNumbers.count(BB) && "Loop DFS skipped preorder");
+    DFS.PostBlocks.push_back(BB);
+    DFS.PostNumbers[BB] = DFS.PostBlocks.size();
+  }
+};
+
+inline bool po_iterator_storage<LoopBlocksTraversal, true>::insertEdge(
+    Optional<BasicBlock *> From, BasicBlock *To) {
+  return LBT.visitPreorder(To);
+}
+
+inline void po_iterator_storage<LoopBlocksTraversal, true>::
+finishPostorder(BasicBlock *BB) {
+  LBT.finishPostorder(BB);
+}
+
+} // End namespace llvm
+
+#endif