ymandel updated this revision to Diff 541153.
ymandel marked 12 inline comments as done.
ymandel added a comment.
tweaks
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,110 @@
#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(BlockID, ID, "") { return arg->getBlockID == ID; }
+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 +127,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 +150,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 +171,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 +190,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 +205,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 +226,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 +250,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,41 @@
#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; }
+
+// 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);
@@ -42,75 +60,170 @@
// 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::map<const Node *, 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());
+
+ // 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)
+ Index.emplace(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::queue<const CFGBlock *> Successors;
- for (const auto *S : Intervals[0].Successors)
- Successors.push(S);
+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::map<const Node *, CFGIntervalNode *> Index;
+ // 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());
+ }
+
+ // 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()) {
+ auto It = Index.find(P);
+ if (It == Index.end())
+ // Unreachable node.
+ continue;
+ CFGIntervalNode *Pred = It->second;
+ 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;
- return Intervals;
+ assert(Size != 0);
+ return std::move(Graph[0].Nodes);
}
+WTOCompare::WTOCompare(const WeakTopologicalOrdering &WTO) {
+ for (const CFGBlock *B : WTO) {
+ // 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;
+ }
+}
} // 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,33 +21,107 @@
#include "clang/Analysis/CFG.h"
#include "llvm/ADT/DenseSet.h"
+#include <deque>
+#include <map>
+#include <memory>
+#include <set>
+#include <variant>
#include <vector>
namespace clang {
-
+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) {}
+
+ 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;
+ }
- // 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;
+ // Unique identifier of this interval relative to other intervals in the same
+ // graph.
+ unsigned ID;
- llvm::SmallDenseSet<const CFGBlock *> Blocks;
+ std::vector<const CFGBlock *> Nodes;
- // Successor blocks of the *interval*: blocks outside the interval for
- // reachable (in one edge) from within the interval.
- llvm::SmallDenseSet<const CFGBlock *> Successors;
+ // 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
+
+/// 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 `nullop` 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 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
_______________________________________________
cfe-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
