ymandel updated this revision to Diff 535397.
ymandel added a comment.
Rebase and address some comments.
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,13 +8,119 @@
#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() {
@@ -32,8 +138,8 @@
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) {
@@ -56,12 +162,10 @@
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() {
@@ -80,11 +184,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, 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) {
@@ -99,11 +203,10 @@
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) {
@@ -116,11 +219,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.Intervals,
+ ElementsAre(
+ IsBlockInterval(0, IsEmpty(), UnorderedElementsAre(IntervalID(1u))),
+ IsBlockInterval(1, UnorderedElementsAre(IntervalID(0u)), IsEmpty())));
}
TEST(PartitionIntoIntervals, PartitionNestedWhileThreeIntervals) {
@@ -136,9 +240,16 @@
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) {
@@ -154,11 +265,103 @@
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
Index: clang/lib/Analysis/IntervalPartition.cpp
===================================================================
--- clang/lib/Analysis/IntervalPartition.cpp
+++ clang/lib/Analysis/IntervalPartition.cpp
@@ -13,23 +13,49 @@
#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());
+namespace {
+template <typename Node> using NodeData = CFGInterval::NodeData<Node>;
+} // namespace
+
+// 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);
@@ -42,31 +68,30 @@
// 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);
@@ -75,42 +100,192 @@
}
// 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 Intervals;
+ 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);
+ }
+}
+
+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
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,125 @@
#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)}) {}
- llvm::SmallDenseSet<const CFGBlock *> Blocks;
+ const llvm::SmallDenseSet<const CFGInterval *> &preds() const {
+ return Predecessors;
+ }
+ const llvm::SmallDenseSet<const CFGInterval *> &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;
+
+ 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;
+
+ // 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;
+
+ // 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;
+};
+
+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 a 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 a 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
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
