[clang][CFG] Support construction of a weak topological ordering of the CFG.

[ymandel]

Summary

This patch adds support for building a weak topological ordering of the CFG
blocks, based on a limit flow graph constructed via (repeated) interval
partitioning of the CFG.

[ymandel]

fix some comments.

[ymandel]

Fix build break and add some field comments.

[ymandel]

more comment expansion.

[xazax.hun]

Could you rebase this patch to the latest tip of tree?

clang/include/clang/Analysis/Analyses/IntervalPartition.h

112

typo?

113

Is feedback edge a special terminology? I think we might simply call these back edges most of the time.

116

same typo here?

clang/lib/Analysis/IntervalPartition.cpp

23–48

What is the reason for putting a using statement in an anonymous namespace?

[ymandel]

Rebase and address some comments.

[ymandel]

Address more comments.

[ymandel]

Rebased, thanks!

clang/include/clang/Analysis/Analyses/IntervalPartition.h

113

That's the language from the paper but I prefer standard "back edge" terminology so updated to reflect.

clang/lib/Analysis/IntervalPartition.cpp

23–48

I... don't remember what I was thinking. Regardless, seems pointless for a template -- fixed.

[xazax.hun]

clang/unittests/Analysis/IntervalPartitionTest.cpp

21

Another redundant anonymous namespace here.

[xazax.hun]

clang/lib/Analysis/IntervalPartition.cpp

115

It would probably take for me some time to understand what is going on here, but I think this part might worth a comment. In particular, I have the impression that Graph.Intervals is the owner of all the intervals. But we use pointers to refer to these intervals. What would guarantee that those pointers are not being invalidated by this emplace_back operations?

[ymandel]

clang/lib/Analysis/IntervalPartition.cpp

115

Excellent question, not least because I *wasn't* careful the first around and indeed ran up against this as a memory bug. :) That's the reason I added IDs, so that I could _avoid_ taking the addresses of elements until after we finish growing the vector. See lines 148-165: after we finish building the intervals, we go through and take addresses.

I can add comments to this effect, but perhaps the safe option is to use a std::dequeue. What do you think?

[xazax.hun]

clang/include/clang/Analysis/Analyses/IntervalPartition.h

93–101

Correct me if I'm wrong but I have the impression that CFGInterval might either contain only CfgBlocks or other CfgIntervals, but these might never be mixed. The current representation does allow such mixing. In case do not need that, I think it might be cleaner to make CfgInterval itself templated and remove the std::variant.

127–129

I wonder if we still want to somehow enforce that within a loop/interval the we visit nodes in the RPO order.

clang/lib/Analysis/IntervalPartition.cpp

36

We have some convenience wrappers in LLVM: https://llvm.org/doxygen/namespacellvm.html#a086e9fbdb06276db7753101a08a63adf

115

Oh, thanks! I don't have a strong preference between a comment or a deque.

[sammccall]

Having (mostly!) understood what this is doing, the algorithm looks like it's doing the right thing.

High-level ideas would be:

• there are three different representations/sets of APIs exposed: intervals, ordering, and compare. It seems like we only have immediate plans to use compare, and maybe ordering in the future. Maybe we could hide the stuff we're not using, if it's necessary to test it then a narrower interface for testing might be enough? Like string printIntervalGraph(CFG, int iters) and then all of Interval could be hidden.
• the data structures for the interval graph are mechanically complicated (trees with differently templated node types etc), and dealing with this incidental complexity and the algorithm complexity is a lot. It may be possible to use simpler data structures, as we don't make use of everything in these ones.

clang/include/clang/Analysis/Analyses/IntervalPartition.h

68–69

Summarizing an offline discussion, IIUC...

• we build a tree of intervals that represents the whole sequence of interval graphs
• for the current worklist algorithm, we use only the total order and process the first invalid block, the tree is not needed
• the algorithm/data structure could be significantly simplified (no variants, templates, recursion...) if it didn't build the tree, just the interval graphs iteratively until a single node is reached
• however a different, non-worklist algorithm could use the tree information to determine which blocks to visit next. (Given a (b c d) e, after d we try only b or e). This avoids expensive "is invalid" checks
• so the motivation for preserving the full interval tree is future-proofing for using a different algorithm

I think it's worth documenting this motivation, and also considering not paying this complexity cost for a feature we aren't adding yet.

93

(Very optional idea, in case you like it)

This data structure is complicated: a tree of Intervals with CFGBlocks at the root, and at every level the Intervals have pred/succ edges that form part of one of the intermediate flow graphs.

It seems nice to get rid of the tree if possible (ultimately we're using these for ordering) and the nested pred/succs - we seem to only need these for the top level interval (and in the end, we have one interval and pred/succs are empty.

What if we made this a flat structure, preserving the bracket structure as some kind of back-edge?

1  (  2  (  3  4  )  )  5
becomes
1     2     3  4 !3 !2  5

AIUI, the dataflow algorithm can basically treat this as a program, we move left to right and !X means "if (X is invalidated) goto X".

This would give us something like:

using Entry = PointerIntPair<CFGBlock*, 1>; // either an actual block, or a conditional jump
struct Interval { vector<Entry> Sequence; SmallDenseSet<Interval*> Preds, Succs; }
using IntervalGraph = vector<Interval>;

I also suspect that this would let us avoid the core algorithms (buildInterval, addIntervalNode) being templated, simply wrap each CFGBlock in a trivial Interval to start with instead. I guess this is OK performance-wise, but the reason not to do it is ending up with those nodes polluting your final data structure?

Anyway, all this is up to you - for me keeping more data/structure around than we're going to use is confusing, but it does seem closer to the textbook.

149

Naming is confusing here: getWTO is the internal function whose API involves intervals, and getIntervalWTO be the main function whose API doesn't. I think literally swapping them might be clearer!

in general it's hard to tell which parts of this API people are actually meant to use.
Is it reasonable to wrap everything up to WeakTopologicalOrdering in namespace internal or so? Or are there places this will be used outside tests?

152

consider instead exposing printWTO as operator<<.

Then you get formatWTO for free as llvm::to_string(), WeakTopologicalOrdering prints reasonably with gtest, you can log it directly, etc.

clang/lib/Analysis/IntervalPartition.cpp

30

remove commented out code

36

here specifically llvm::is_contained(Interval, N) can be used directly, this function is not needed

52

I'm confused, here and below why are successors allowed to be nullptr?

76–77

consider

bool AllInInterval = llvm::all_of(B->preds(), [&](const Node *P) {
  return inInterval(P, Interval.Nodes);
});

(usually i prefer the plain loop, but tracking booleans is annoying)

76–77

you always add to MaybeSuccessors this exactly once when AllInInterval ends up false, but that's not totally obvious.

Consider moving this below the loop, to the else in if (AllInInterval)

[ymandel]

Radically simplify the code, per comments.

[ymandel]

tweaks

[ymandel]

Thanks for the very helpful feedback!
I think I've addressed all of the suggestions/concerns. I suspect there's yet more room for improvement in the algorithm, but I think we're converging on "good enough".

clang/include/clang/Analysis/Analyses/IntervalPartition.h

68–69

Sam, I've radically simplified the implementation to only build exactly what's needed -- the ordering. PTAL and let me know what further comments/documentation would help.

93

I went with this proposal and stripped it down to only track what we need. I didn't even preserve the backedge structure, because we can't use that yet. If and when we get there, I think you're approach or something similar, where we avoid the tree structure, is a great idea.

93–101

True, but the Header field gets in the way, since it needs to have a recursive type (it's type is always one level down from the interval's type). So, somewhere you'll need a variant and a recursive type. The current version avoids this by dropping Header entirely, since it isn't needed in the output.

127–129

Starting with RPO should make this algorithm cheaper (and maybe simpler!). But, RPO construction isn't free. So, I think it is a matter of cost -- compare generating the RPO first and then using that here vs. just using this directly. I can put a note in the implementation as FIXME. WDYT?

149

Agreed. The only reason to expose is for tests.

clang/lib/Analysis/IntervalPartition.cpp

52

That's how the CFG encodes unreachable nodes. succs doesn't actually return CFGBlocks, but an intermediate type which encodes reachability info. When you (implicitly) cast it to CFGBlock*, unreachable nodes become a nullptr.

115

I ended up changing to a deque after almost making the same mistake again. vector is just not safe when you want to be taking addresses. :) I've dropped the use of IDs and added comments. Let me know if this clear enough.

[xazax.hun]

clang/include/clang/Analysis/Analyses/IntervalPartition.h

127–129

Sounds good to me.

157

Would it make sense to have a vector instead and use block ids to get the order?

clang/lib/Analysis/IntervalPartition.cpp

115

Looks good, thanks! I agree that the deque solution looks cleaner, probably we should get it first right and we can optimize later if there is a need for that.

[ymandel]

Addressed comments.

clang/include/clang/Analysis/Analyses/IntervalPartition.h

127–129

Added a FIXME in buildIntervals.

[xazax.hun]

Thanks, looks good to me!

[sammccall]

Thanks, this is much simpler!
Just nits & apologies for the delay.

clang/include/clang/Analysis/Analyses/IntervalPartition.h

24

some of these added headers are now unused: map, set, variant

51–67

nit: namespace internal should probably be moved below the public API

139

nit: nullopt

139

what do we expect to do in practice when the CFG is not reducible? or do we expect that to never happen?

(mostly wondering if we need a fallback)

clang/lib/Analysis/IntervalPartition.cpp

36

Might be more useful to say concretely: Nodes are either CFGBlock or CFGIntervalNode

105

std::map of pointers is a bit suspicious, densemap?

clang/unittests/Analysis/IntervalPartitionTest.cpp

91

nit: matcher factories are functions and so should be lowerCamelCase

[ymandel]

Addressed comments

[ymandel]

Thanks for the helpful suggestions!

clang/include/clang/Analysis/Analyses/IntervalPartition.h

139

good question -- I'm not really sure what to expect. In practice, any structured function will yield a reducible graph. But, creative use of goto's can undermine that. So, my guess is that we will not encounter these in practice, but I don't know for sure.

As for fallback, RPO doesn't rely on reducibility. So, clients are free to use that instead when this fails.

clang/lib/Analysis/IntervalPartition.cpp

105

I went with a vector mapping (implicitly) from Node IDs, like I did for the WTO.

clang/include/clang/Analysis/Analyses/IntervalPartition.h

 //===- IntervalPartition.h - CFG Partitioning into Intervals -----*- 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 functionality for partitioning a CFG into intervals. The
-//  concepts and implementations are based on the presentation in "Compilers" by
-//  Aho, Sethi and Ullman (the "dragon book"), pages 664-666.
+//  This file defines functionality for partitioning a CFG into intervals and
+//  building a weak topological order (WTO) of the nodes, based on the
+//  partitioning. The concepts and implementations for the graph partitioning
+//  are based on the presentation in "Compilers" by Aho, Sethi and Ullman (the
+//  "dragon book"), pages 664-666. The concepts around WTOs is taken from the
+//  paper "Efficient chaotic iteration strategies with widenings," by
+//  F. Bourdoncle ([Bourdoncle1993]).
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_INTERVALPARTITION_H
 #define LLVM_CLANG_ANALYSIS_ANALYSES_INTERVALPARTITION_H
 
 #include "clang/Analysis/CFG.h"
 #include "llvm/ADT/DenseSet.h"
+#include <deque>
+#include <memory>
 #include <vector>
 
 namespace clang {
+/// A _weak topological ordering_ (WTO) of CFG nodes provides a total order over
+/// the CFG (defined in `WTOCompare`, below), which can guide the order in which
+/// to visit nodes in fixpoint computations over the CFG.
+///
+/// Roughly, a WTO a) groups the blocks so that loop heads are grouped with
+/// their bodies and any nodes they dominate after the loop and b) orders the
+/// groups topologically. As a result, the blocks in a series of loops are
+/// ordered such that all nodes in loop `i` are earlier in the order than nodes
+/// in loop `j`. This ordering, when combined with widening, bounds the number
+/// of times a node must be visited for a dataflow algorithm to reach a
+/// fixpoint. For the precise definition of a WTO and its properties, see
+/// [Bourdoncle1993].
+///
+/// Here, we provide a simplified WTO which drops its nesting structure,
+/// maintaining only the ordering itself. The ordering is built from the limit
+/// flow graph of `Cfg` (derived from iteratively partitioning it into
+/// intervals) if and only if it is reducible (its limit flow graph has one
+/// node). Returns `nullopt` when `Cfg` is not reducible.
+///
+/// This WTO construction is described in Section 4.2 of [Bourdoncle1993].
+using WeakTopologicalOrdering = std::vector<const CFGBlock *>;
+std::optional<WeakTopologicalOrdering> getIntervalWTO(const CFG &Cfg);
+
+struct WTOCompare {
+  WTOCompare(const WeakTopologicalOrdering &WTO);
+
+  bool operator()(const CFGBlock *B1, const CFGBlock *B2) const {
+    auto ID1 = B1->getBlockID();
+    auto ID2 = B2->getBlockID();
+
+    unsigned V1 = ID1 >= BlockOrder.size() ? 0 : BlockOrder[ID1];
+    unsigned V2 = ID2 >= BlockOrder.size() ? 0 : BlockOrder[ID2];
+    return V1 > V2;
+  }
 
+  std::vector<unsigned> BlockOrder;
+};
+
+namespace internal {
 // An interval is a strongly-connected component of the CFG along with a
-// trailing acyclic structure. The _header_ of the interval is either the CFG
-// entry block or has at least one predecessor outside of the interval. All
-// other blocks in the interval have only predecessors also in the interval.
-struct CFGInterval {
-  CFGInterval(const CFGBlock *Header) : Header(Header), Blocks({Header}) {}
-
-  // The block from which the interval was constructed. Is either the CFG entry
-  // block or has at least one predecessor outside the interval.
-  const CFGBlock *Header;
-
-  llvm::SmallDenseSet<const CFGBlock *> Blocks;
-
-  // Successor blocks of the *interval*: blocks outside the interval for
-  // reachable (in one edge) from within the interval.
-  llvm::SmallDenseSet<const CFGBlock *> Successors;
+// trailing acyclic structure. An interval can be constructed directly from CFG
+// blocks or from a graph of other intervals. Each interval has one _header_
+// block, from which the interval is built. The _header_ of the interval is
+// either the graph's entry block or has at least one predecessor outside of the
+// interval. All other blocks in the interval have only predecessors also in the
+// interval.
+struct CFGIntervalNode {
+  CFGIntervalNode() = default;
+  CFGIntervalNode(unsigned ID) : ID(ID) {}
+
+  CFGIntervalNode(unsigned ID, std::vector<const CFGBlock *> Nodes)
+      : ID(ID), Nodes(std::move(Nodes)) {}
+
+  const llvm::SmallDenseSet<const CFGIntervalNode *> &preds() const {
+    return Predecessors;
+  }
+  const llvm::SmallDenseSet<const CFGIntervalNode *> &succs() const {
+    return Successors;
+  }
+
+  // Unique identifier of this interval relative to other intervals in the same
+  // graph.
+  unsigned ID;
+
+  std::vector<const CFGBlock *> Nodes;
+
+  // Predessor intervals of this interval: those intervals for which there
+  // exists an edge from a node in that other interval to the head of this
+  // interval.
+  llvm::SmallDenseSet<const CFGIntervalNode *> Predecessors;
+
+  // Successor intervals of this interval: those intervals for which there
+  // exists an edge from a node in this interval to the head of that other
+  // interval.
+  llvm::SmallDenseSet<const CFGIntervalNode *> Successors;
 };
 
-CFGInterval buildInterval(const CFG &Cfg, const CFGBlock &Header);
+// Since graphs are built from pointers to nodes, we use a deque to ensure
+// pointer stability.
+using CFGIntervalGraph = std::deque<CFGIntervalNode>;
+
+std::vector<const CFGBlock *> buildInterval(const CFGBlock *Header);
 
-// Partitions `Cfg` into intervals and constructs a graph of the intervals,
+// Partitions `Cfg` into intervals and constructs the graph of the intervals
 // based on the edges between nodes in these intervals.
-std::vector<CFGInterval> partitionIntoIntervals(const CFG &Cfg);
+CFGIntervalGraph partitionIntoIntervals(const CFG &Cfg);
 
+// (Further) partitions `Graph` into intervals and constructs the graph of the
+// intervals based on the edges between nodes (themselves intervals) in these
+// intervals.
+CFGIntervalGraph partitionIntoIntervals(const CFGIntervalGraph &Graph);
+} // namespace internal
 } // namespace clang
 
 #endif // LLVM_CLANG_ANALYSIS_ANALYSES_INTERVALPARTITION_H

clang/lib/Analysis/IntervalPartition.cpp

 //===- IntervalPartition.cpp - CFG Partitioning into Intervals --*- 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 functionality for partitioning a CFG into intervals.
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/Analysis/Analyses/IntervalPartition.h"
 #include "clang/Analysis/CFG.h"
 #include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/STLExtras.h"
+#include <optional>
 #include <queue>
 #include <set>
 #include <vector>
 
 namespace clang {
 
-static CFGInterval buildInterval(llvm::BitVector &Partitioned,
-                                 const CFGBlock &Header) {
-  CFGInterval Interval(&Header);
-  Partitioned.set(Header.getBlockID());
+// Intermediate data used in constructing a CFGIntervalNode.
+template <typename Node> struct BuildResult {
+  // Use a vector to maintain the insertion order. Given the expected small
+  // number of nodes, vector should be sufficiently efficient.
+  std::vector<const Node *> Nodes;
+  llvm::SmallDenseSet<const Node *> Successors;
+};
+
+namespace internal {
+static unsigned getID(const CFGBlock *B) { return B->getBlockID(); }
+static unsigned getID(const CFGIntervalNode *I) { return I->ID; }
+
+// `Node` must be one of `CFGBlock` or `CFGIntervalNode`.
+template <typename Node>
+BuildResult<Node> buildInterval(llvm::BitVector &Partitioned,
+                                const Node *Header) {
+  assert(Header);
+  BuildResult<Node> Interval;
+  Interval.Nodes.push_back(Header);
+  Partitioned.set(getID(Header));
 
+  // FIXME: Compare performance against using RPO to consider nodes, rather than
+  // following successors.
+  //
   // Elements must not be null. Duplicates are prevented using `Workset`, below.
-  std::queue<const CFGBlock *> Worklist;
-  llvm::BitVector Workset(Header.getParent()->getNumBlockIDs(), false);
-  for (const CFGBlock *S : Header.succs())
+  std::queue<const Node *> Worklist;
+  llvm::BitVector Workset(Partitioned.size(), false);
+  for (const Node *S : Header->succs())
     if (S != nullptr)
-      if (auto SID = S->getBlockID(); !Partitioned.test(SID)) {
+      if (auto SID = getID(S); !Partitioned.test(SID)) {
         // Successors are unique, so we don't test against `Workset` before
         // adding to `Worklist`.
         Worklist.push(S);
         Workset.set(SID);
       }
 
   // Contains successors of blocks in the interval that couldn't be added to the
   // interval on their first encounter. This occurs when they have a predecessor
   // that is either definitively outside the interval or hasn't been considered
   // yet. In the latter case, we'll revisit the block through some other path
   // from the interval. At the end of processing the worklist, we filter out any
   // that ended up in the interval to produce the output set of interval
-  // successors. It may contain duplicates -- ultimately, all relevant elements
-  // are added to `Interval.Successors`, which is a set.
-  std::vector<const CFGBlock *> MaybeSuccessors;
+  // successors.
+  std::vector<const Node *> MaybeSuccessors;
 
   while (!Worklist.empty()) {
     const auto *B = Worklist.front();
-    auto ID = B->getBlockID();
+    auto ID = getID(B);
     Worklist.pop();
     Workset.reset(ID);
 
     // Check whether all predecessors are in the interval, in which case `B`
     // is included as well.
-    bool AllInInterval = true;
-    for (const CFGBlock *P : B->preds())
-      if (Interval.Blocks.find(P) == Interval.Blocks.end()) {
-        MaybeSuccessors.push_back(B);
-        AllInInterval = false;
-        break;
-      }
+    bool AllInInterval = llvm::all_of(B->preds(), [&](const Node *P) {
+      return llvm::is_contained(Interval.Nodes, P);
+    });
     if (AllInInterval) {
-      Interval.Blocks.insert(B);
+      Interval.Nodes.push_back(B);
       Partitioned.set(ID);
-      for (const CFGBlock *S : B->succs())
+      for (const Node *S : B->succs())
         if (S != nullptr)
-          if (auto SID = S->getBlockID();
+          if (auto SID = getID(S);
               !Partitioned.test(SID) && !Workset.test(SID)) {
             Worklist.push(S);
             Workset.set(SID);
           }
+    } else {
+      MaybeSuccessors.push_back(B);
     }
   }
 
   // Any block successors not in the current interval are interval successors.
-  for (const CFGBlock *B : MaybeSuccessors)
-    if (Interval.Blocks.find(B) == Interval.Blocks.end())
+  for (const Node *B : MaybeSuccessors)
+    if (!llvm::is_contained(Interval.Nodes, B))
       Interval.Successors.insert(B);
 
   return Interval;
 }
 
-CFGInterval buildInterval(const CFG &Cfg, const CFGBlock &Header) {
-  llvm::BitVector Partitioned(Cfg.getNumBlockIDs(), false);
-  return buildInterval(Partitioned, Header);
+template <typename Node>
+void fillIntervalNode(CFGIntervalGraph &Graph,
+                      std::vector<CFGIntervalNode *> &Index,
+                      std::queue<const Node *> &Successors,
+                      llvm::BitVector &Partitioned, const Node *Header) {
+  BuildResult<Node> Result = buildInterval(Partitioned, Header);
+  for (const auto *S : Result.Successors)
+    Successors.push(S);
+
+  CFGIntervalNode &Interval = Graph.emplace_back(Graph.size());
+
+  // Index the nodes of the new interval. The index maps nodes from the input
+  // graph (specifically, `Result.Nodes`) to identifiers of nodes in the output
+  // graph. In this case, the new interval has identifier `ID` so all of its
+  // nodes (`Result.Nodes`) map to `ID`.
+  for (const auto *N : Result.Nodes) {
+    assert(getID(N) < Index.size());
+    Index[getID(N)] = &Interval;
+  }
+
+  if constexpr (std::is_same_v<std::decay_t<Node>, CFGBlock>)
+    Interval.Nodes = std::move(Result.Nodes);
+  else {
+    std::vector<const CFGBlock *> Nodes;
+    // Flatten the sub vectors into a single list.
+    size_t Count = 0;
+    for (auto &N : Result.Nodes)
+      Count += N->Nodes.size();
+    Nodes.reserve(Count);
+    for (auto &N : Result.Nodes)
+      Nodes.insert(Nodes.end(), N->Nodes.begin(), N->Nodes.end());
+    Interval.Nodes = std::move(Nodes);
+  }
 }
 
-std::vector<CFGInterval> partitionIntoIntervals(const CFG &Cfg) {
-  std::vector<CFGInterval> Intervals;
-  llvm::BitVector Partitioned(Cfg.getNumBlockIDs(), false);
-  auto &EntryBlock = Cfg.getEntry();
-  Intervals.push_back(buildInterval(Partitioned, EntryBlock));
+template <typename Node>
+CFGIntervalGraph partitionIntoIntervalsImpl(unsigned NumBlockIDs,
+                                            const Node *EntryBlock) {
+  assert(EntryBlock != nullptr);
+  CFGIntervalGraph Graph;
+  // `Index` maps all of the nodes of the input graph to the interval to which
+  // they are assigned in the output graph. The values (interval pointers) are
+  // never null.
+  std::vector<CFGIntervalNode *> Index(NumBlockIDs, nullptr);
+
+  // Lists header nodes (from the input graph) and their associated
+  // interval. Since header nodes can vary in type and are only needed within
+  // this function, we record them separately from `CFGIntervalNode`. This
+  // choice enables to express `CFGIntervalNode` without using a variant.
+  std::vector<std::pair<const Node *, CFGIntervalNode *>> Intervals;
+  llvm::BitVector Partitioned(NumBlockIDs, false);
+  std::queue<const Node *> Successors;
 
-  std::queue<const CFGBlock *> Successors;
-  for (const auto *S : Intervals[0].Successors)
-    Successors.push(S);
+  fillIntervalNode(Graph, Index, Successors, Partitioned, EntryBlock);
+  Intervals.emplace_back(EntryBlock, &Graph.back());
 
   while (!Successors.empty()) {
     const auto *B = Successors.front();
     Successors.pop();
-    if (Partitioned.test(B->getBlockID()))
+    if (Partitioned.test(getID(B)))
       continue;
 
-    // B has not been partitioned, but it has a predecessor that has.
-    CFGInterval I = buildInterval(Partitioned, *B);
-    for (const auto *S : I.Successors)
-      Successors.push(S);
-    Intervals.push_back(std::move(I));
+    // B has not been partitioned, but it has a predecessor that has. Create a
+    // new interval from `B`.
+    fillIntervalNode(Graph, Index, Successors, Partitioned, B);
+    Intervals.emplace_back(B, &Graph.back());
   }
 
-  return Intervals;
+  // Go back and patch up all the Intervals -- the successors and predecessors.
+  for (auto [H, N] : Intervals) {
+    // Map input-graph predecessors to output-graph nodes and mark those as
+    // predecessors of `N`. Then, mark `N` as a successor of said predecessor.
+    for (const Node *P : H->preds()) {
+      assert(getID(P) < NumBlockIDs);
+      CFGIntervalNode *Pred = Index[getID(P)];
+      if (Pred == nullptr)
+        // Unreachable node.
+        continue;
+      if (Pred != N // Not a backedge.
+          && N->Predecessors.insert(Pred).second)
+        // Note: given the guard above, which guarantees we only ever insert
+        // unique elements, we could use a simple list (like `vector`) for
+        // `Successors`, rather than a set.
+        Pred->Successors.insert(N);
+    }
   }
 
+  return Graph;
+}
+
+std::vector<const CFGBlock *> buildInterval(const CFGBlock *Header) {
+  llvm::BitVector Partitioned(Header->getParent()->getNumBlockIDs(), false);
+  return buildInterval(Partitioned, Header).Nodes;
+}
+
+CFGIntervalGraph partitionIntoIntervals(const CFG &Cfg) {
+  return partitionIntoIntervalsImpl(Cfg.getNumBlockIDs(), &Cfg.getEntry());
+}
+
+CFGIntervalGraph partitionIntoIntervals(const CFGIntervalGraph &Graph) {
+  return partitionIntoIntervalsImpl(Graph.size(), &Graph[0]);
+}
+} // namespace internal
+
+std::optional<std::vector<const CFGBlock *>> getIntervalWTO(const CFG &Cfg) {
+  // Backing storage for the allocated nodes in each graph.
+  unsigned PrevSize = Cfg.size();
+  if (PrevSize == 0)
+    return {};
+  internal::CFGIntervalGraph Graph = internal::partitionIntoIntervals(Cfg);
+  unsigned Size = Graph.size();
+  while (Size > 1 && Size < PrevSize) {
+    PrevSize = Graph.size();
+    Graph = internal::partitionIntoIntervals(Graph);
+    Size = Graph.size();
+  }
+  if (Size > 1)
+    // Not reducible.
+    return std::nullopt;
+
+  assert(Size != 0);
+  return std::move(Graph[0].Nodes);
+}
+
+WTOCompare::WTOCompare(const WeakTopologicalOrdering &WTO) {
+  if (WTO.empty())
+    return;
+  auto N = WTO[0]->getParent()->getNumBlockIDs();
+  BlockOrder.resize(N, 0);
+  for (unsigned I = 0; I < N; ++I)
+    BlockOrder[WTO[I]->getBlockID()] = I + 1;
+}
 } // namespace clang

clang/unittests/Analysis/IntervalPartitionTest.cpp

 //===- unittests/Analysis/IntervalPartitionTest.cpp -----------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/Analysis/Analyses/IntervalPartition.h"
 #include "CFGBuildResult.h"
+#include "clang/Analysis/CFG.h"
+#include "llvm/Support/raw_ostream.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
+#include <type_traits>
+#include <variant>
 
 namespace clang {
-namespace analysis {
+
+llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
+                              const std::vector<const CFGBlock *> &Nodes) {
+  OS << "Blocks{";
+  for (const auto *B : Nodes)
+    OS << B->getBlockID() << ", ";
+  OS << "}";
+  return OS;
+}
+
+void PrintTo(const std::vector<const CFGBlock *> &Nodes, std::ostream *OS) {
+  std::string Result;
+  llvm::raw_string_ostream StringOS(Result);
+  StringOS << Nodes;
+  *OS << Result;
+}
+
+namespace internal {
+llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const CFGIntervalNode &I) {
+  OS << "Interval{ID = " << I.ID << ", ";
+  OS << "Blocks{";
+  for (const auto *B : I.Nodes)
+    OS << B->getBlockID() << ", ";
+  OS << "}, Pre{";
+  for (const auto *P : I.Predecessors)
+    OS << P->ID << ",";
+  OS << "}, Succ{";
+  for (const auto *P : I.Successors)
+    OS << P->ID << ",";
+  OS << "}}";
+  return OS;
+}
+
+llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
+                              const CFGIntervalGraph &G) {
+  OS << "Intervals{";
+  for (const auto &I : G) {
+    OS << I << ", ";
+  }
+  OS << "}";
+  return OS;
+}
+
+void PrintTo(const CFGIntervalNode &I, std::ostream *OS) {
+  std::string Result;
+  llvm::raw_string_ostream StringOS(Result);
+  StringOS << I;
+  *OS << Result;
+}
+
+void PrintTo(const CFGIntervalGraph &G, std::ostream *OS) {
+  *OS << "Intervals{";
+  for (const auto &I : G) {
+    PrintTo(I, OS);
+    *OS << ", ";
+  }
+  *OS << "}";
+}
+} // namespace internal
+
 namespace {
 
-TEST(BuildInterval, PartitionSimpleOneInterval) {
+using ::clang::analysis::BuildCFG;
+using ::clang::analysis::BuildResult;
+using ::clang::internal::buildInterval;
+using ::clang::internal::partitionIntoIntervals;
+using ::testing::ElementsAre;
+using ::testing::IsEmpty;
+using ::testing::Optional;
+using ::testing::Property;
+using ::testing::UnorderedElementsAre;
+
+MATCHER_P(intervalID, ID, "") { return arg->ID == ID; }
+
+template <typename... T> auto blockIDs(T... IDs) {
+  return UnorderedElementsAre(Property(&CFGBlock::getBlockID, IDs)...);
+}
+
+template <typename... T> auto blockOrder(T... IDs) {
+  return ElementsAre(Property(&CFGBlock::getBlockID, IDs)...);
+}
+
+MATCHER_P3(isInterval, ID, Preds, Succs, "") {
+  return testing::Matches(ID)(arg.ID) &&
+         testing::Matches(Preds)(arg.Predecessors) &&
+         testing::Matches(Succs)(arg.Successors);
+}
 
+MATCHER_P4(isInterval, ID, Nodes, Preds, Succs, "") {
+  return testing::Matches(ID)(arg.ID) && testing::Matches(Nodes)(arg.Nodes) &&
+         testing::Matches(Preds)(arg.Predecessors) &&
+         testing::Matches(Succs)(arg.Successors);
+}
+
+TEST(BuildInterval, PartitionSimpleOneInterval) {
   const char *Code = R"(void f() {
                           int x = 3;
                           int y = 7;
                           x = y + x;
                         })";
   BuildResult Result = BuildCFG(Code);
   EXPECT_EQ(BuildResult::BuiltCFG, Result.getStatus());
 
   CFG *cfg = Result.getCFG();
 
   // Basic correctness checks.
   ASSERT_EQ(cfg->size(), 3u);
 
   auto &EntryBlock = cfg->getEntry();
 
-  CFGInterval I = buildInterval(*cfg, EntryBlock);
-  EXPECT_EQ(I.Blocks.size(), 3u);
+  std::vector<const CFGBlock *> I = buildInterval(&EntryBlock);
+  EXPECT_EQ(I.size(), 3u);
 }
 
 TEST(BuildInterval, PartitionIfThenOneInterval) {
-
   const char *Code = R"(void f() {
                           int x = 3;
                           if (x > 3)
                             x = 2;
                           else
                             x = 7;
                           x = x + x;
                         })";
   BuildResult Result = BuildCFG(Code);
   EXPECT_EQ(BuildResult::BuiltCFG, Result.getStatus());
 
   CFG *cfg = Result.getCFG();
 
   // Basic correctness checks.
   ASSERT_EQ(cfg->size(), 6u);
 
   auto &EntryBlock = cfg->getEntry();
 
-  CFGInterval I = buildInterval(*cfg, EntryBlock);
-  EXPECT_EQ(I.Blocks.size(), 6u);
+  std::vector<const CFGBlock *> I = buildInterval(&EntryBlock);
+  EXPECT_EQ(I.size(), 6u);
 }
 
-using ::testing::UnorderedElementsAre;
-
 TEST(BuildInterval, PartitionWhileMultipleIntervals) {
-
   const char *Code = R"(void f() {
                           int x = 3;
                           while (x >= 3)
                             --x;
                           x = x + x;
                         })";
   BuildResult Result = BuildCFG(Code);
   ASSERT_EQ(BuildResult::BuiltCFG, Result.getStatus());
 
   CFG *cfg = Result.getCFG();
   ASSERT_EQ(cfg->size(), 7u);
 
   auto *EntryBlock = &cfg->getEntry();
   CFGBlock *InitXBlock = *EntryBlock->succ_begin();
   CFGBlock *LoopHeadBlock = *InitXBlock->succ_begin();
 
-  CFGInterval I1 = buildInterval(*cfg, *EntryBlock);
-  EXPECT_THAT(I1.Blocks, UnorderedElementsAre(EntryBlock, InitXBlock));
+  std::vector<const CFGBlock *> I1 = buildInterval(EntryBlock);
+  EXPECT_THAT(I1, ElementsAre(EntryBlock, InitXBlock));
 
-  CFGInterval I2 = buildInterval(*cfg, *LoopHeadBlock);
-  EXPECT_EQ(I2.Blocks.size(), 5u);
+  std::vector<const CFGBlock *> I2 = buildInterval(LoopHeadBlock);
+  EXPECT_EQ(I2.size(), 5u);
 }
 
 TEST(PartitionIntoIntervals, PartitionIfThenOneInterval) {
   const char *Code = R"(void f() {
                           int x = 3;
                           if (x > 3)
                             x = 2;
                           else
                             x = 7;
                           x = x + x;
                         })";
   BuildResult Result = BuildCFG(Code);
   ASSERT_EQ(BuildResult::BuiltCFG, Result.getStatus());
 
-  CFG *cfg = Result.getCFG();
-  ASSERT_EQ(cfg->size(), 6u);
-
-  auto Intervals = partitionIntoIntervals(*cfg);
-  EXPECT_EQ(Intervals.size(), 1u);
+  auto Graph = partitionIntoIntervals(*Result.getCFG());
+  EXPECT_EQ(Graph.size(), 1u);
+  EXPECT_THAT(Graph, ElementsAre(isInterval(0, IsEmpty(), IsEmpty())));
 }
 
 TEST(PartitionIntoIntervals, PartitionWhileTwoIntervals) {
   const char *Code = R"(void f() {
                           int x = 3;
                           while (x >= 3)
                             --x;
                           x = x + x;
                         })";
   BuildResult Result = BuildCFG(Code);
   ASSERT_EQ(BuildResult::BuiltCFG, Result.getStatus());
 
-  CFG *cfg = Result.getCFG();
-  ASSERT_EQ(cfg->size(), 7u);
-
-  auto Intervals = partitionIntoIntervals(*cfg);
-  EXPECT_EQ(Intervals.size(), 2u);
+  auto Graph = partitionIntoIntervals(*Result.getCFG());
+  EXPECT_THAT(
+      Graph,
+      ElementsAre(
+          isInterval(0, IsEmpty(), UnorderedElementsAre(intervalID(1u))),
+          isInterval(1, UnorderedElementsAre(intervalID(0u)), IsEmpty())));
 }
 
 TEST(PartitionIntoIntervals, PartitionNestedWhileThreeIntervals) {
   const char *Code = R"(void f() {
                           int x = 3;
                           while (x >= 3) {
                             --x;
                             int y = x;
                             while (y > 0) --y;
                           }
                           x = x + x;
                         })";
   BuildResult Result = BuildCFG(Code);
   ASSERT_EQ(BuildResult::BuiltCFG, Result.getStatus());
 
-  CFG *cfg = Result.getCFG();
-  auto Intervals = partitionIntoIntervals(*cfg);
-  EXPECT_EQ(Intervals.size(), 3u);
+  auto Graph = partitionIntoIntervals(*Result.getCFG());
+  EXPECT_THAT(
+      Graph,
+      ElementsAre(
+          isInterval(0, IsEmpty(), UnorderedElementsAre(intervalID(1u))),
+          isInterval(1, UnorderedElementsAre(intervalID(0u), intervalID(2u)),
+                     UnorderedElementsAre(intervalID(2u))),
+          isInterval(2, UnorderedElementsAre(intervalID(1u)),
+                     UnorderedElementsAre(intervalID(1u)))));
 }
 
 TEST(PartitionIntoIntervals, PartitionSequentialWhileThreeIntervals) {
   const char *Code = R"(void f() {
                           int x = 3;
                           while (x >= 3) {
                             --x;
                           }
                           x = x + x;
                           int y = x;
                           while (y > 0) --y;
                         })";
   BuildResult Result = BuildCFG(Code);
   ASSERT_EQ(BuildResult::BuiltCFG, Result.getStatus());
 
-  CFG *cfg = Result.getCFG();
-  auto Intervals = partitionIntoIntervals(*cfg);
-  EXPECT_EQ(Intervals.size(), 3u);
+  auto Graph = partitionIntoIntervals(*Result.getCFG());
+  EXPECT_THAT(
+      Graph,
+      ElementsAre(
+          isInterval(0, IsEmpty(), UnorderedElementsAre(intervalID(1u))),
+          isInterval(1, UnorderedElementsAre(intervalID(0u)),
+                     UnorderedElementsAre(intervalID(2u))),
+          isInterval(2, UnorderedElementsAre(intervalID(1u)), IsEmpty())));
+}
+
+TEST(PartitionIntoIntervals, LimitReducibleSequentialWhile) {
+  const char *Code = R"(void f() {
+                          int x = 3;
+                          while (x >= 3) {
+                            --x;
+                          }
+                          x = x + x;
+                          int y = x;
+                          while (y > 0) --y;
+                        })";
+  BuildResult Result = BuildCFG(Code);
+  ASSERT_EQ(BuildResult::BuiltCFG, Result.getStatus());
+
+  auto Graph = partitionIntoIntervals(*Result.getCFG());
+  ASSERT_THAT(
+      Graph,
+      ElementsAre(isInterval(0, blockOrder(9, 8), IsEmpty(),
+                             UnorderedElementsAre(intervalID(1u))),
+                  isInterval(1, blockOrder(7, 6, 4, 5),
+                             UnorderedElementsAre(intervalID(0u)),
+                             UnorderedElementsAre(intervalID(2u))),
+                  isInterval(2, blockOrder(3, 2, 0, 1),
+                             UnorderedElementsAre(intervalID(1u)), IsEmpty())));
+
+  auto Graph2 = partitionIntoIntervals(Graph);
+  EXPECT_THAT(Graph2, ElementsAre(isInterval(
+                          0, blockOrder(9, 8, 7, 6, 4, 5, 3, 2, 0, 1),
+                          IsEmpty(), IsEmpty())));
+}
+
+TEST(PartitionIntoIntervals, LimitReducibleNestedWhile) {
+  const char *Code = R"(void f() {
+                          int x = 3;
+                          while (x >= 3) {
+                            --x;
+                            int y = x;
+                            while (y > 0) --y;
+                          }
+                          x = x + x;
+                        })";
+  BuildResult Result = BuildCFG(Code);
+  ASSERT_EQ(BuildResult::BuiltCFG, Result.getStatus());
+
+  auto Graph = partitionIntoIntervals(*Result.getCFG());
+  ASSERT_THAT(Graph,
+              ElementsAre(isInterval(0, blockOrder(9, 8), IsEmpty(),
+                                     UnorderedElementsAre(intervalID(1u))),
+                          isInterval(1, blockOrder(7, 6, 1, 0),
+                                     UnorderedElementsAre(intervalID(0u),
+                                                          intervalID(2u)),
+                                     UnorderedElementsAre(intervalID(2u))),
+                          isInterval(2, blockOrder(5, 4, 2, 3),
+                                     UnorderedElementsAre(intervalID(1u)),
+                                     UnorderedElementsAre(intervalID(1u)))));
+
+  auto Graph2 = partitionIntoIntervals(Graph);
+  EXPECT_THAT(
+      Graph2,
+      ElementsAre(isInterval(0, blockOrder(9, 8), IsEmpty(),
+                             UnorderedElementsAre(intervalID(1u))),
+                  isInterval(1, blockOrder(7, 6, 1, 0, 5, 4, 2, 3),
+                             UnorderedElementsAre(intervalID(0u)), IsEmpty())));
+
+  auto Graph3 = partitionIntoIntervals(Graph2);
+  EXPECT_THAT(Graph3, ElementsAre(isInterval(
+                          0, blockOrder(9, 8, 7, 6, 1, 0, 5, 4, 2, 3),
+                          IsEmpty(), IsEmpty())));
+}
+
+TEST(GetIntervalWTO, SequentialWhile) {
+  const char *Code = R"(void f() {
+                          int x = 3;
+                          while (x >= 3) {
+                            --x;
+                          }
+                          x = x + x;
+                          int y = x;
+                          while (y > 0) --y;
+                        })";
+  BuildResult Result = BuildCFG(Code);
+  ASSERT_EQ(BuildResult::BuiltCFG, Result.getStatus());
+  EXPECT_THAT(getIntervalWTO(*Result.getCFG()),
+              Optional(blockOrder(9, 8, 7, 6, 4, 5, 3, 2, 0, 1)));
+}
+
+TEST(GetIntervalWTO, NestedWhile) {
+  const char *Code = R"(void f() {
+                          int x = 3;
+                          while (x >= 3) {
+                            --x;
+                            int y = x;
+                            while (y > 0) --y;
+                          }
+                          x = x + x;
+                        })";
+  BuildResult Result = BuildCFG(Code);
+  ASSERT_EQ(BuildResult::BuiltCFG, Result.getStatus());
+  EXPECT_THAT(getIntervalWTO(*Result.getCFG()),
+              Optional(blockOrder(9, 8, 7, 6, 1, 0, 5, 4, 2, 3)));
 }
 
 } // namespace
-} // namespace analysis
 } // namespace clang