This revision was landed with ongoing or failed builds.
This revision was automatically updated to reflect the committed changes.
ymandel marked an inline comment as done.
Closed by commit rG26db5e651bb6: [clang][CFG] Support construction of a weak
topological ordering of the CFG. (authored by ymandel).
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D153058/new/
https://reviews.llvm.org/D153058
Files:
clang/include/clang/Analysis/Analyses/IntervalPartition.h
clang/lib/Analysis/IntervalPartition.cpp
clang/unittests/Analysis/IntervalPartitionTest.cpp
Index: clang/unittests/Analysis/IntervalPartitionTest.cpp
===================================================================
--- clang/unittests/Analysis/IntervalPartitionTest.cpp
+++ clang/unittests/Analysis/IntervalPartitionTest.cpp
@@ -8,15 +8,109 @@
#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;
@@ -32,12 +126,11 @@
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)
@@ -56,14 +149,11 @@
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)
@@ -80,11 +170,11 @@
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) {
@@ -99,11 +189,9 @@
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) {
@@ -116,11 +204,12 @@
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) {
@@ -136,9 +225,15 @@
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) {
@@ -154,11 +249,116 @@
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
Index: clang/lib/Analysis/IntervalPartition.cpp
===================================================================
--- clang/lib/Analysis/IntervalPartition.cpp
+++ clang/lib/Analysis/IntervalPartition.cpp
@@ -13,23 +13,44 @@
#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);
@@ -42,75 +63,173 @@
// 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);
-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));
+ CFGIntervalNode &Interval = Graph.emplace_back(Graph.size());
- std::queue<const CFGBlock *> Successors;
- for (const auto *S : Intervals[0].Successors)
- Successors.push(S);
+ // 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);
+ }
+}
+
+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;
+
+ 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
Index: clang/include/clang/Analysis/Analyses/IntervalPartition.h
===================================================================
--- clang/include/clang/Analysis/Analyses/IntervalPartition.h
+++ clang/include/clang/Analysis/Analyses/IntervalPartition.h
@@ -6,9 +6,13 @@
//
//===----------------------------------------------------------------------===//
//
-// 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]).
//
//===----------------------------------------------------------------------===//
@@ -17,34 +21,103 @@
#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}) {}
+// 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) {}
- // 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;
+ CFGIntervalNode(unsigned ID, std::vector<const CFGBlock *> Nodes)
+ : ID(ID), Nodes(std::move(Nodes)) {}
- llvm::SmallDenseSet<const CFGBlock *> Blocks;
+ const llvm::SmallDenseSet<const CFGIntervalNode *> &preds() const {
+ return Predecessors;
+ }
+ const llvm::SmallDenseSet<const CFGIntervalNode *> &succs() const {
+ return Successors;
+ }
- // Successor blocks of the *interval*: blocks outside the interval for
- // reachable (in one edge) from within the interval.
- llvm::SmallDenseSet<const CFGBlock *> 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
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
