[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

76

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

86

typo?

90

same typo here?

clang/lib/Analysis/IntervalPartition.cpp

23–51

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

76

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

clang/lib/Analysis/IntervalPartition.cpp

23–51

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

121

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

121

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

56–64

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.

101–103

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

121

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

38

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.

56

(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.

123

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?

126

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

55

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

80

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)

83

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

38

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.

56

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.

56–64

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.

101–103

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?

123

Agreed. The only reason to expose is for tests.

clang/lib/Analysis/IntervalPartition.cpp

55

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.

121

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

101–103

Sounds good to me.

131

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

clang/lib/Analysis/IntervalPartition.cpp

121

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

101–103

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

31

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

113

nit: nullopt

113

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

62

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

124

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

clang/unittests/Analysis/IntervalPartitionTest.cpp

134

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

113

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

124

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 <map>
+#include <memory>
+#include <set>
+#include <variant>
 #include <vector>
 
 namespace clang {
 
 // 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.
+// trailing acyclic structure. An interval can be constructed directly from CFG
+// blocks or from a graph of other intervals. 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 CFGInterval {
-  CFGInterval(const CFGBlock *Header) : Header(Header), Blocks({Header}) {}
+  CFGInterval() = default;
 
-  // 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;
+  template <typename Node>
+  CFGInterval(int ID, const Node *Header, std::vector<const Node *> Nodes)
+      : ID(ID), Data(NodeData<Node>{Header, std::move(Nodes)}) {}
+
+  const llvm::SmallDenseSet<const CFGInterval *> &preds() const {
+    return Predecessors;
+  }
+  const llvm::SmallDenseSet<const CFGInterval *> &succs() const {
+    return Successors;
+  }
+
+  // Unique identifier of this interval relative to other intervals in the same
+  // graph.
+  unsigned ID;
+
+  template <typename Node> struct NodeData {
+    // The block from which the interval was constructed. It is either the
+    // graph's entry block or has at least one predecessor outside the interval.
+    const Node *Header;
+    std::vector<const Node *> Nodes;
+  };
+  using IntervalData = std::variant<NodeData<CFGBlock>, NodeData<CFGInterval>>;
+
+  IntervalData Data;
 
-  llvm::SmallDenseSet<const CFGBlock *> Blocks;
+  // 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 CFGInterval *> 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 CFGInterval *> Successors;
 
-  // Successor blocks of the *interval*: blocks outside the interval for
-  // reachable (in one edge) from within the interval.
-  llvm::SmallDenseSet<const CFGBlock *> Successors;
+  // Whether this node is the head of a back edge within the interval.
+  bool IsBackedgeHead = false;
 };
 
-CFGInterval buildInterval(const CFG &Cfg, const CFGBlock &Header);
+struct CFGIntervalGraph {
+  std::vector<CFGInterval> Intervals;
+};
 
-// Partitions `Cfg` into intervals and constructs a graph of the intervals,
+std::vector<const CFGBlock *> buildInterval(const CFGBlock *Header);
+
+// 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);
+
+/// 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].
+struct WeakTopologicalOrdering {
+  // `Elements` represents an ordered sequence and nested WTOs induce a
+  // hierarchy in the ordering. When built from a limit flow graph, the first
+  // element of a WTO corresponds to an interval header, which is usually a loop
+  // head (except for the CFG entry block).
+  std::vector<std::variant<const CFGBlock *, WeakTopologicalOrdering>> Elements;
+};
+
+/// Builds a WTO of the nodes in `I`, based on the structure of the intervals.
+WeakTopologicalOrdering getWTO(const CFGInterval &I);
+
+/// Builds a WTO 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 `nullop` when `Cfg` is not reducible.
+///
+/// This WTO construction is described in Section 4.2 of [Bourdoncle1993].
+std::optional<WeakTopologicalOrdering> getIntervalWTO(const CFG &Cfg);
+
+/// Formats `WTO` as a human-readable string.
+std::string formatWTO(const WeakTopologicalOrdering &WTO);
+
+struct WTOCompare {
+  WTOCompare(const WeakTopologicalOrdering &WTO);
+
+  bool operator()(const CFGBlock *B1, const CFGBlock *B2) const {
+    auto It1 = BlockOrder.find(B1);
+    auto It2 = BlockOrder.find(B2);
+
+    unsigned V1 = (It1 == BlockOrder.end()) ? 0 : It1->second;
+    unsigned V2 = (It2 == BlockOrder.end()) ? 0 : It2->second;
+    return V1 > V2;
+  }
+
+  using BlockOrderTy = llvm::DenseMap<const CFGBlock *, unsigned>;
+  BlockOrderTy BlockOrder;
+};
 
 } // 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 <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());
+template <typename Node> using NodeData = CFGInterval::NodeData<Node>;
+
+// 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 *> Nodes;
+  llvm::SmallDenseSet<const Node *> Successors;
+};
+
+template <typename Node>
+bool inInterval(const Node *N, std::vector<const Node *> &Interval) {
+  return std::find(Interval.begin(), Interval.end(), N) != Interval.end();
+}
+
+static unsigned getID(const CFGBlock *B) { return B->getBlockID(); }
+static unsigned getID(const CFGInterval *I) { return I->ID; }
+
+// Requires: `Node::succs()` and `Node::preds()`.
+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));
 
   // 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()) {
+    for (const Node *P : B->preds())
+      if (!inInterval(P, Interval.Nodes)) {
         MaybeSuccessors.push_back(B);
         AllInInterval = false;
         break;
       }
     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);
           }
     }
   }
 
   // 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 (!inInterval(B, Interval.Nodes))
       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 addIntervalNode(CFGIntervalGraph &Graph,
+                     std::map<const Node *, unsigned> &Index,
+                     std::queue<const Node *> &Successors,
+                     llvm::BitVector &Partitioned, const Node *Header) {
+  BuildResult<Node> Data = buildInterval(Partitioned, Header);
+  for (const auto *S : Data.Successors)
+    Successors.push(S);
+
+  // Index the nodes of the new interval.
+  int ID = Graph.Intervals.size();
+  for (const auto *N : Data.Nodes)
+    Index.emplace(N, ID);
+  Graph.Intervals.emplace_back(ID, Header, std::move(Data.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));
+// TODO: for Node = CFGInterval, we should collapse single-node intervals.
+template <typename Node>
+CFGIntervalGraph partitionIntoIntervalsImpl(unsigned NumBlockIDs,
+                                            const Node *EntryBlock) {
+  assert(EntryBlock != nullptr);
+  CFGIntervalGraph Graph;
+  // Records the ID of the header node associated with each node in the graph.
+  std::map<const Node *, unsigned> Index;
+  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);
+  addIntervalNode(Graph, Index, Successors, Partitioned, EntryBlock);
 
   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`.
+    addIntervalNode(Graph, Index, Successors, Partitioned, B);
+  }
+
+  // Go back and patch up all the Intervals -- the successors and predecessors.
+  for (auto &I : Graph.Intervals) {
+    assert(std::holds_alternative<NodeData<Node>>(I.Data));
+    auto &Data = std::get<NodeData<Node>>(I.Data);
+    // All external successors must be interval headers, because they
+    // have predecessors in multiple intervals.
+    for (const Node *N : Data.Header->preds()) {
+      auto It = Index.find(N);
+      if (It == Index.end())
+        // Unreachable block.
+        continue;
+      if (It->second == I.ID)
+        // This is a back edge, so mark `I` the head of this edge.
+        I.IsBackedgeHead = true;
+      else if (I.Predecessors.insert(&Graph.Intervals[It->second]).second)
+        Graph.Intervals[It->second].Successors.insert(&I);
+    }
+  }
+
+  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.Intervals.size(),
+                                    &Graph.Intervals[0]);
+}
+
+static void addToWTO(const CFGInterval &I, WeakTopologicalOrdering &Order);
+
+static void addToWTO(const CFGInterval::IntervalData &D,
+                     WeakTopologicalOrdering &Order) {
+  std::visit(
+      [&Order](auto &&D) {
+        for (const auto *N : D.Nodes) {
+          if constexpr (std::is_same_v<std::decay_t<decltype(D)>,
+                                       NodeData<CFGBlock>>) {
+            Order.Elements.emplace_back(N);
+          } else {
+            static_assert(std::is_same_v<std::decay_t<decltype(D)>,
+                                         NodeData<CFGInterval>>);
+            addToWTO(*N, Order);
+          }
+        }
+      },
+      D);
+}
+
+static void addToWTO(const CFGInterval &I, WeakTopologicalOrdering &Order) {
+  if (I.IsBackedgeHead) {
+    WeakTopologicalOrdering Nested;
+    addToWTO(I.Data, Nested);
+    Order.Elements.push_back(std::move(Nested));
+    return;
+  }
+  addToWTO(I.Data, Order);
+}
+
+WeakTopologicalOrdering getWTO(const CFGInterval &I) {
+  WeakTopologicalOrdering Order;
+  addToWTO(I, Order);
+  return Order;
+}
+
+std::optional<WeakTopologicalOrdering> getIntervalWTO(const CFG &Cfg) {
+  // Backing storage for the allocated nodes in each graph.
+  std::vector<CFGIntervalGraph> Graphs;
+  unsigned PrevSize = Cfg.size();
+  Graphs.push_back(partitionIntoIntervals(Cfg));
+  unsigned Size = Graphs.back().Intervals.size();
+  while (Size > 1 && Size < PrevSize) {
+    PrevSize = Graphs.back().Intervals.size();
+    Graphs.push_back(partitionIntoIntervals(Graphs.back()));
+    Size = Graphs.back().Intervals.size();
+  }
+  if (Size > 1)
+    // Not reducible.
+    return std::nullopt;
+
+  assert(Size != 0);
+  return getWTO(Graphs.back().Intervals[0]);
+}
+
+static void printWTO(const WeakTopologicalOrdering &O, llvm::raw_ostream &OS) {
+  bool First = true;
+  for (auto &E : O.Elements) {
+    if (!First)
+      OS << " ";
+    else
+      First = false;
+
+    std::visit(
+        [&OS](auto &&Value) {
+          if constexpr (std::is_same_v<std::decay_t<decltype(Value)>,
+                                       const CFGBlock *>) {
+            OS << Value->getBlockID();
+          } else {
+            static_assert(std::is_same_v<std::decay_t<decltype(Value)>,
+                                         WeakTopologicalOrdering>);
+            OS << "(";
+            printWTO(Value, OS);
+            OS << ")";
+          }
+        },
+        E);
+  }
 
-  return Intervals;
+std::string formatWTO(const WeakTopologicalOrdering &O) {
+  std::string Result;
+  llvm::raw_string_ostream OS(Result);
+  printWTO(O, OS);
+  return Result;
 }
 
+static void initWithWTO(llvm::DenseMap<const CFGBlock *, unsigned> &BlockOrder,
+                        const WeakTopologicalOrdering &WTO) {
+  for (auto &E : WTO.Elements) {
+    if (std::holds_alternative<WeakTopologicalOrdering>(E)) {
+      initWithWTO(BlockOrder, std::get<WeakTopologicalOrdering>(E));
+      continue;
+    }
+    const auto *B = std::get<const CFGBlock *>(E);
+    // Calculate J first so we don't depend on order of evaluation of the
+    // assignment's operands.
+    auto J = BlockOrder.size() + 1;
+    BlockOrder[B] = J;
+  }
+}
+
+WTOCompare::WTOCompare(const WeakTopologicalOrdering &WTO) {
+  initWithWTO(BlockOrder, WTO);
+}
 } // 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 {
+
+namespace {
+template <typename T> using NodeData = CFGInterval::NodeData<T>;
+}  // namespace
+
+llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
+                              const CFGInterval::IntervalData &D) {
+  OS << "Nodes{";
+  if (std::holds_alternative<NodeData<CFGBlock>>(D)) {
+    auto &BlockData = std::get<NodeData<CFGBlock>>(D);
+    for (const auto *B : BlockData.Nodes)
+      OS << B->getBlockID() << ", ";
+  } else {
+    assert(std::holds_alternative<NodeData<CFGInterval>>(D));
+    auto &IntervalData = std::get<NodeData<CFGInterval>>(D);
+    for (const auto *B : IntervalData.Nodes)
+      OS << B->ID << ", ";
+  }
+  OS << "}";
+  return OS;
+}
+
+llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const CFGInterval &I) {
+  OS << "Interval{ID = " << I.ID << ", ";
+  OS << I.Data;
+  OS << ", Pre{";
+  for (const auto *P : I.Predecessors)
+    OS << P->ID << ",";
+  OS << "}, Succ{";
+  for (const auto *P : I.Successors)
+    OS << P->ID << ",";
+  OS << "}}\n";
+  return OS;
+}
+
+void PrintTo(const CFGInterval::IntervalData &D, std::ostream *OS) {
+  std::string Result;
+  llvm::raw_string_ostream StringOS(Result);
+  StringOS << D;
+  *OS << Result;
+}
+
+void PrintTo(const CFGInterval &I, std::ostream *OS) {
+  std::string Result;
+  llvm::raw_string_ostream StringOS(Result);
+  StringOS << I;
+  *OS << Result;
+}
+
 namespace {
 
+using ::clang::analysis::BuildCFG;
+using ::clang::analysis::BuildResult;
+using ::testing::ElementsAre;
+using ::testing::Field;
+using ::testing::IsEmpty;
+using ::testing::Optional;
+using ::testing::UnorderedElementsAre;
+
+MATCHER_P(BlockID, ID, "") { return arg->getBlockID == ID; }
+MATCHER_P(IntervalID, ID, "") { return arg->ID == ID; }
+
+template <typename... T>
+auto BlockIDs(T... IDs) {
+  return UnorderedElementsAre(
+      ::testing::Property(&CFGBlock::getBlockID, IDs)...);
+}
+
+template <typename... T>
+auto IntervalIDs(T... IDs) {
+  return UnorderedElementsAre(
+      ::testing::Field(&CFGInterval::ID, IDs)...);
+}
+
+MATCHER_P3(IsBlockInterval, ID, Preds, Succs, "") {
+  if (!std::holds_alternative<NodeData<CFGBlock>>(arg.Data))
+    return false;
+
+  return testing::Matches(ID)(arg.ID) &&
+         testing::Matches(Preds)(arg.Predecessors) &&
+         testing::Matches(Succs)(arg.Successors);
+}
+
+MATCHER_P4(IsBlockInterval, ID, Nodes, Preds, Succs, "") {
+  if (!std::holds_alternative<NodeData<CFGBlock>>(arg.Data))
+    return false;
+  auto &IntervalData = std::get<NodeData<CFGBlock>>(arg.Data);
+
+  return testing::Matches(ID)(arg.ID) &&
+         testing::Matches(Nodes)(IntervalData.Nodes) &&
+         testing::Matches(Preds)(arg.Predecessors) &&
+         testing::Matches(Succs)(arg.Successors);
+}
+
+MATCHER_P4(IsNestedInterval, ID, Nodes, Preds, Succs, "") {
+  if (!std::holds_alternative<NodeData<CFGInterval>>(arg.Data))
+    return false;
+  auto &IntervalData = std::get<NodeData<CFGInterval>>(arg.Data);
+
+  return testing::Matches(ID)(arg.ID) &&
+         testing::Matches(Nodes)(IntervalData.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, UnorderedElementsAre(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.Intervals.size(), 1u);
+  EXPECT_THAT(Graph.Intervals,
+              ElementsAre(IsBlockInterval(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.Intervals,
+      ElementsAre(
+          IsBlockInterval(0, IsEmpty(), UnorderedElementsAre(IntervalID(1u))),
+          IsBlockInterval(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.Intervals,
+      ElementsAre(
+          IsBlockInterval(0, IsEmpty(), UnorderedElementsAre(IntervalID(1u))),
+          IsBlockInterval(1,
+                          UnorderedElementsAre(IntervalID(0u), IntervalID(2u)),
+                          UnorderedElementsAre(IntervalID(2u))),
+          IsBlockInterval(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.Intervals,
+      ElementsAre(
+          IsBlockInterval(0, IsEmpty(), UnorderedElementsAre(IntervalID(1u))),
+          IsBlockInterval(1, UnorderedElementsAre(IntervalID(0u)),
+                          UnorderedElementsAre(IntervalID(2u))),
+          IsBlockInterval(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.Intervals,
+      ElementsAre(
+          IsBlockInterval(0, IsEmpty(), UnorderedElementsAre(IntervalID(1u))),
+          IsBlockInterval(1, UnorderedElementsAre(IntervalID(0u)),
+                          UnorderedElementsAre(IntervalID(2u))),
+          IsBlockInterval(2, UnorderedElementsAre(IntervalID(1u)), IsEmpty())));
+
+  auto Graph2 = partitionIntoIntervals(Graph);
+  EXPECT_THAT(Graph2.Intervals,
+              ElementsAre(IsNestedInterval(0, IntervalIDs(0, 1, 2),
+                                           IsEmpty(), IsEmpty())));
+  EXPECT_EQ(formatWTO(getWTO(Graph2.Intervals[0])), "9 8 (7 6 4 5) (3 2 0 1)");
+}
+
+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.Intervals,
+      ElementsAre(
+          IsBlockInterval(0, BlockIDs(9, 8), IsEmpty(),
+                          UnorderedElementsAre(IntervalID(1u))),
+          IsBlockInterval(1, BlockIDs(7, 6, 1, 0),
+                          UnorderedElementsAre(IntervalID(0u), IntervalID(2u)),
+                          UnorderedElementsAre(IntervalID(2u))),
+          IsBlockInterval(2, BlockIDs(5, 4, 3, 2),
+                          UnorderedElementsAre(IntervalID(1u)),
+                          UnorderedElementsAre(IntervalID(1u)))));
+
+  auto Graph2 = partitionIntoIntervals(Graph);
+  EXPECT_THAT(Graph2.Intervals,
+              ElementsAre(IsNestedInterval(0, IntervalIDs(0), IsEmpty(),
+                                           UnorderedElementsAre(IntervalID(1u))),
+                          IsNestedInterval(1, IntervalIDs(1, 2),
+                                           UnorderedElementsAre(IntervalID(0u)),
+                                           IsEmpty())));
+
+  auto Graph3 = partitionIntoIntervals(Graph2);
+  EXPECT_THAT(Graph3.Intervals,
+              ElementsAre(IsNestedInterval(0, IntervalIDs(0, 1), IsEmpty(),
+                                           IsEmpty())));
+  EXPECT_EQ(formatWTO(getWTO(Graph3.Intervals[0])), "9 8 (7 6 1 0 (5 4 2 3))");
+}
+
+TEST(GetWTO, 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());
+
+  auto WTO = getIntervalWTO(*Result.getCFG());
+  ASSERT_NE(WTO, std::nullopt);
+  ASSERT_EQ(formatWTO(*WTO), "9 8 (7 6 1 0 (5 4 2 3))");
 }
 
 } // namespace
-} // namespace analysis
 } // namespace clang