ymandel updated this revision to Diff 535402. ymandel added a comment. Address more 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,47 @@ #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); @@ -42,31 +66,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 +98,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 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
_______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits