diff --git a/clang/include/clang/Analysis/Analyses/IntervalPartition.h b/clang/include/clang/Analysis/Analyses/IntervalPartition.h --- a/clang/include/clang/Analysis/Analyses/IntervalPartition.h +++ b/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 +#include #include 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; +std::optional 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 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 Nodes) + : ID(ID), Nodes(std::move(Nodes)) {} - llvm::SmallDenseSet Blocks; + const llvm::SmallDenseSet &preds() const { + return Predecessors; + } + const llvm::SmallDenseSet &succs() const { + return Successors; + } - // Successor blocks of the *interval*: blocks outside the interval for - // reachable (in one edge) from within the interval. - llvm::SmallDenseSet Successors; + // Unique identifier of this interval relative to other intervals in the same + // graph. + unsigned ID; + + std::vector 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 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 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; + +std::vector 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 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 diff --git a/clang/lib/Analysis/IntervalPartition.cpp b/clang/lib/Analysis/IntervalPartition.cpp --- a/clang/lib/Analysis/IntervalPartition.cpp +++ b/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 #include #include #include 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 struct BuildResult { + // Use a vector to maintain the insertion order. Given the expected small + // number of nodes, vector should be sufficiently efficient. + std::vector Nodes; + llvm::SmallDenseSet 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 +BuildResult buildInterval(llvm::BitVector &Partitioned, + const Node *Header) { + assert(Header); + BuildResult 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 Worklist; - llvm::BitVector Workset(Header.getParent()->getNumBlockIDs(), false); - for (const CFGBlock *S : Header.succs()) + std::queue 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 MaybeSuccessors; + // successors. + std::vector 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 +void fillIntervalNode(CFGIntervalGraph &Graph, + std::vector &Index, + std::queue &Successors, + llvm::BitVector &Partitioned, const Node *Header) { + BuildResult Result = buildInterval(Partitioned, Header); + for (const auto *S : Result.Successors) + Successors.push(S); -std::vector partitionIntoIntervals(const CFG &Cfg) { - std::vector 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 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, CFGBlock>) + Interval.Nodes = std::move(Result.Nodes); + else { + std::vector 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 +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 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> Intervals; + llvm::BitVector Partitioned(NumBlockIDs, false); + std::queue 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 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> 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 diff --git a/clang/unittests/Analysis/IntervalPartitionTest.cpp b/clang/unittests/Analysis/IntervalPartitionTest.cpp --- a/clang/unittests/Analysis/IntervalPartitionTest.cpp +++ b/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 +#include namespace clang { -namespace analysis { + +llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, + const std::vector &Nodes) { + OS << "Blocks{"; + for (const auto *B : Nodes) + OS << B->getBlockID() << ", "; + OS << "}"; + return OS; +} + +void PrintTo(const std::vector &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 auto blockIDs(T... IDs) { + return UnorderedElementsAre(Property(&CFGBlock::getBlockID, IDs)...); +} + +template 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 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 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 I1 = buildInterval(EntryBlock); + EXPECT_THAT(I1, ElementsAre(EntryBlock, InitXBlock)); - CFGInterval I2 = buildInterval(*cfg, *LoopHeadBlock); - EXPECT_EQ(I2.Blocks.size(), 5u); + std::vector 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