[PATCH] D153058: [clang][CFG] Support construction of a weak topological ordering of the CFG.
This revision was landed with ongoing or failed builds.
This revision was automatically updated to reflect the committed changes.
ymandel marked an inline comment as done.
Closed by commit rG26db5e651bb6: [clang][CFG] Support construction of a weak
topological ordering of the CFG. (authored by ymandel).
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D153058/new/
https://reviews.llvm.org/D153058
Files:
clang/include/clang/Analysis/Analyses/IntervalPartition.h
clang/lib/Analysis/IntervalPartition.cpp
clang/unittests/Analysis/IntervalPartitionTest.cpp
Index: clang/unittests/Analysis/IntervalPartitionTest.cpp
===
--- clang/unittests/Analysis/IntervalPartitionTest.cpp
+++ clang/unittests/Analysis/IntervalPartitionTest.cpp
@@ -8,15 +8,109 @@
#include "clang/Analysis/Analyses/IntervalPartition.h"
#include "CFGBuildResult.h"
+#include "clang/Analysis/CFG.h"
+#include "llvm/Support/raw_ostream.h"
#include "gmock/gmock.h"
#include "gtest/gtest.h"
+#include
+#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 = buildInt
[PATCH] D153058: [clang][CFG] Support construction of a weak topological ordering of the CFG.
ymandel marked 5 inline comments as done. ymandel added a comment. Thanks for the helpful suggestions! Comment at: clang/include/clang/Analysis/Analyses/IntervalPartition.h:104 +/// intervals) if and only if it is reducible (its limit flow graph has one +/// node). Returns `nullop` when `Cfg` is not reducible. +/// sammccall wrote: > sammccall wrote: > > nit: nullopt > what do we expect to do in practice when the CFG is not reducible? or do we > expect that to never happen? > > (mostly wondering if we need a fallback) good question -- I'm not really sure what to expect. In practice, any structured function will yield a reducible graph. But, creative use of goto's can undermine that. So, my guess is that we will not encounter these in practice, but I don't know for sure. As for fallback, RPO doesn't rely on reducibility. So, clients are free to use that instead when this fails. Comment at: clang/lib/Analysis/IntervalPartition.cpp:105 +void fillIntervalNode(CFGIntervalGraph &Graph, + std::map &Index, + std::queue &Successors, sammccall wrote: > std::map of pointers is a bit suspicious, densemap? I went with a vector mapping (implicitly) from Node IDs, like I did for the WTO. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D153058/new/ https://reviews.llvm.org/D153058 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D153058: [clang][CFG] Support construction of a weak topological ordering of the CFG.
ymandel updated this revision to Diff 544551.
ymandel marked 2 inline comments as done.
ymandel added a comment.
Addressed 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,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);
+
[PATCH] D153058: [clang][CFG] Support construction of a weak topological ordering of the CFG.
sammccall accepted this revision.
sammccall added a comment.
Thanks, this is much simpler!
Just nits & apologies for the delay.
Comment at: clang/include/clang/Analysis/Analyses/IntervalPartition.h:24
#include "llvm/ADT/DenseSet.h"
+#include
+#include
some of these added headers are now unused: map, set, variant
Comment at: clang/include/clang/Analysis/Analyses/IntervalPartition.h:32
namespace clang {
-
+namespace internal {
// An interval is a strongly-connected component of the CFG along with a
nit: `namespace internal` should probably be moved below the public API
Comment at: clang/include/clang/Analysis/Analyses/IntervalPartition.h:104
+/// intervals) if and only if it is reducible (its limit flow graph has one
+/// node). Returns `nullop` when `Cfg` is not reducible.
+///
nit: nullopt
Comment at: clang/include/clang/Analysis/Analyses/IntervalPartition.h:104
+/// intervals) if and only if it is reducible (its limit flow graph has one
+/// node). Returns `nullop` when `Cfg` is not reducible.
+///
sammccall wrote:
> nit: nullopt
what do we expect to do in practice when the CFG is not reducible? or do we
expect that to never happen?
(mostly wondering if we need a fallback)
Comment at: clang/lib/Analysis/IntervalPartition.cpp:36
+
+// Requires: `Node::succs()` and `Node::preds()`.
+template
Might be more useful to say concretely: Nodes are either CFGBlock or
CFGIntervalNode
Comment at: clang/lib/Analysis/IntervalPartition.cpp:105
+void fillIntervalNode(CFGIntervalGraph &Graph,
+ std::map &Index,
+ std::queue &Successors,
std::map of pointers is a bit suspicious, densemap?
Comment at: clang/unittests/Analysis/IntervalPartitionTest.cpp:91
+
+MATCHER_P(BlockID, ID, "") { return arg->getBlockID == ID; }
+MATCHER_P(IntervalID, ID, "") { return arg->ID == ID; }
nit: matcher factories are functions and so should be lowerCamelCase
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D153058/new/
https://reviews.llvm.org/D153058
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D153058: [clang][CFG] Support construction of a weak topological ordering of the CFG.
xazax.hun accepted this revision. xazax.hun added a comment. This revision is now accepted and ready to land. Thanks, looks good to me! Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D153058/new/ https://reviews.llvm.org/D153058 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D153058: [clang][CFG] Support construction of a weak topological ordering of the CFG.
ymandel added inline comments. Comment at: clang/include/clang/Analysis/Analyses/IntervalPartition.h:101-103 +/// 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 xazax.hun wrote: > ymandel wrote: > > xazax.hun wrote: > > > I wonder if we still want to somehow enforce that within a loop/interval > > > the we visit nodes in the RPO order. > > Starting with RPO should make this algorithm cheaper (and maybe simpler!). > > But, RPO construction isn't free. So, I think it is a matter of cost -- > > compare generating the RPO first and then using that here vs. just using > > this directly. I can put a note in the implementation as FIXME. WDYT? > Sounds good to me. Added a FIXME in `buildIntervals`. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D153058/new/ https://reviews.llvm.org/D153058 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D153058: [clang][CFG] Support construction of a weak topological ordering of the CFG.
ymandel updated this revision to Diff 543552.
ymandel marked 2 inline comments as done.
ymandel added a comment.
Addressed 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,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
+#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(BlockID, ID, "") { return arg->getBlockID == ID; }
+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 +127,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 +150,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 +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 I1 = buildInterval(EntryBlock);
+ EXPECT_THAT(I1, ElementsAre(EntryBlock, InitXBlock));
- CFGInterval I2 = buildInterv
[PATCH] D153058: [clang][CFG] Support construction of a weak topological ordering of the CFG.
xazax.hun added inline comments. Comment at: clang/include/clang/Analysis/Analyses/IntervalPartition.h:122 + + using BlockOrderTy = llvm::DenseMap; + BlockOrderTy BlockOrder; Would it make sense to have a vector instead and use block ids to get the order? Comment at: clang/include/clang/Analysis/Analyses/IntervalPartition.h:101-103 +/// 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 ymandel wrote: > xazax.hun wrote: > > I wonder if we still want to somehow enforce that within a loop/interval > > the we visit nodes in the RPO order. > Starting with RPO should make this algorithm cheaper (and maybe simpler!). > But, RPO construction isn't free. So, I think it is a matter of cost -- > compare generating the RPO first and then using that here vs. just using this > directly. I can put a note in the implementation as FIXME. WDYT? Sounds good to me. Comment at: clang/lib/Analysis/IntervalPartition.cpp:121 +Index.emplace(N, ID); + Graph.Intervals.emplace_back(ID, Header, std::move(Data.Nodes)); } ymandel wrote: > xazax.hun wrote: > > ymandel wrote: > > > xazax.hun wrote: > > > > It would probably take for me some time to understand what is going on > > > > here, but I think this part might worth a comment. In particular, I > > > > have the impression that `Graph.Intervals` is the owner of all the > > > > intervals. But we use pointers to refer to these intervals. What would > > > > guarantee that those pointers are not being invalidated by this > > > > `emplace_back` operations? > > > Excellent question, not least because I *wasn't* careful the first around > > > and indeed ran up against this as a memory bug. :) That's the reason I > > > added IDs, so that I could _avoid_ taking the addresses of elements until > > > after we finish growing the vector. See lines 148-165: after we finish > > > building the intervals, we go through and take addresses. > > > > > > I can add comments to this effect, but perhaps the safe option is to use > > > a std::dequeue. What do you think? > > Oh, thanks! I don't have a strong preference between a comment or a deque. > I ended up changing to a deque after almost making the same mistake again. > vector is just not safe when you want to be taking addresses. :) I've dropped > the use of IDs and added comments. Let me know if this clear enough. Looks good, thanks! I agree that the deque solution looks cleaner, probably we should get it first right and we can optimize later if there is a need for that. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D153058/new/ https://reviews.llvm.org/D153058 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D153058: [clang][CFG] Support construction of a weak topological ordering of the CFG.
ymandel added a comment.
Thanks for the very helpful feedback!
I think I've addressed all of the suggestions/concerns. I suspect there's yet
more room for improvement in the algorithm, but I think we're converging on
"good enough".
Comment at: clang/include/clang/Analysis/Analyses/IntervalPartition.h:38
+// interval.
struct CFGInterval {
+ CFGInterval() = default;
sammccall wrote:
> Summarizing an offline discussion, IIUC...
> - we build a tree of intervals that represents the whole sequence of interval
> graphs
> - for the current worklist algorithm, we use only the total order and process
> the first invalid block, the tree is not needed
> - the algorithm/data structure could be significantly simplified (no
> variants, templates, recursion...) if it didn't build the tree, just the
> interval graphs iteratively until a single node is reached
> - however a different, non-worklist algorithm could use the tree information
> to determine which blocks to visit next. (Given `a (b c d) e`, after `d` we
> try only `b` or `e`). This avoids expensive "is invalid" checks
> - so the motivation for preserving the full interval tree is future-proofing
> for using a different algorithm
>
> I think it's worth documenting this motivation, and also considering not
> paying this complexity cost for a feature we aren't adding yet.
Sam, I've radically simplified the implementation to only build exactly what's
needed -- the ordering. PTAL and let me know what further
comments/documentation would help.
Comment at: clang/include/clang/Analysis/Analyses/IntervalPartition.h:56
+
+ template struct NodeData {
+// The block from which the interval was constructed. It is either the
sammccall wrote:
> xazax.hun wrote:
> > Correct me if I'm wrong but I have the impression that `CFGInterval` might
> > either contain only `CfgBlock`s or other `CfgInterval`s, but these might
> > never be mixed. The current representation does allow such mixing. In case
> > do not need that, I think it might be cleaner to make `CfgInterval` itself
> > templated and remove the `std::variant`.
> (Very optional idea, in case you like it)
>
> This data structure is complicated: a tree of Intervals with CFGBlocks at the
> root, and at every level the Intervals have pred/succ edges that form part of
> one of the intermediate flow graphs.
>
> It seems nice to get rid of the tree if possible (ultimately we're using
> these for ordering) and the nested pred/succs - we seem to only need these
> for the top level interval (and in the end, we have one interval and
> pred/succs are empty.
>
> What if we made this a flat structure, preserving the bracket structure as
> some kind of back-edge?
>
> ```
> 1 ( 2 ( 3 4 ) ) 5
> becomes
> 1 2 3 4 !3 !2 5
> ```
>
> AIUI, the dataflow algorithm can basically treat this as a program, we move
> left to right and `!X` means "if (X is invalidated) goto X".
>
> This would give us something like:
> ```
> using Entry = PointerIntPair; // either an actual block, or a
> conditional jump
> struct Interval { vector Sequence; SmallDenseSet Preds,
> Succs; }
> using IntervalGraph = vector;
> ```
>
> I also suspect that this would let us avoid the core algorithms
> (buildInterval, addIntervalNode) being templated, simply wrap each CFGBlock
> in a trivial Interval to start with instead. I guess this is OK
> performance-wise, but the reason not to do it is ending up with those nodes
> polluting your final data structure?
>
>
> Anyway, all this is up to you - for me keeping more data/structure around
> than we're going to use is confusing, but it does seem closer to the textbook.
I went with this proposal and stripped it down to only track what we need. I
didn't even preserve the backedge structure, because we can't use that yet. If
and when we get there, I think you're approach or something similar, where we
avoid the tree structure, is a great idea.
Comment at: clang/include/clang/Analysis/Analyses/IntervalPartition.h:56-64
+ template 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 Nodes;
+ };
+ using IntervalData = std::variant, NodeData>;
ymandel wrote:
> sammccall wrote:
> > xazax.hun wrote:
> > > Correct me if I'm wrong but I have the impression that `CFGInterval`
> > > might either contain only `CfgBlock`s or other `CfgInterval`s, but these
> > > might never be mixed. The current representation does allow such mixing.
> > > In case do not need that, I think it might be cleaner to make
> > > `CfgInterval` itself templated and remove the `std::variant`.
> > (Very optional idea, in case you like it)
> >
> > This data structure is complicated: a tree of Intervals with CFGBlocks at
> > the
[PATCH] D153058: [clang][CFG] Support construction of a weak topological ordering of the CFG.
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
+#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(BlockID, ID, "") { return arg->getBlockID == ID; }
+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 +127,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 +150,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 +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 I1 = buildInterval(EntryBlock);
+ EXPECT_THAT(I1, ElementsAre(EntryBlock, InitXBlock));
- CFGInterval I2 = buildInterval(*cfg, *Lo
[PATCH] D153058: [clang][CFG] Support construction of a weak topological ordering of the CFG.
ymandel updated this revision to Diff 541141.
ymandel added a comment.
Radically simplify the code, per 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,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
+#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 details {
+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 details
+
namespace {
-TEST(BuildInterval, PartitionSimpleOneInterval) {
+using ::clang::analysis::BuildCFG;
+using ::clang::analysis::BuildResult;
+using ::clang::details::buildInterval;
+using ::clang::details::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 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 +127,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 +150,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 +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 I1 = buildInterval(EntryBlock);
+ EXPECT_THAT(I1, ElementsAre(EntryBlock, InitXBlock));
- CFGInterval I2 = buildInterval(*cfg, *LoopHeadBlock
[PATCH] D153058: [clang][CFG] Support construction of a weak topological ordering of the CFG.
sammccall added a comment.
Having (mostly!) understood what this is doing, the algorithm looks like it's
doing the right thing.
High-level ideas would be:
- there are three different representations/sets of APIs exposed: intervals,
ordering, and compare. It seems like we only have immediate plans to use
compare, and maybe ordering in the future. Maybe we could hide the stuff we're
not using, if it's necessary to test it then a narrower interface for testing
might be enough? Like `string printIntervalGraph(CFG, int iters)` and then all
of Interval could be hidden.
- the data structures for the interval graph are mechanically complicated
(trees with differently templated node types etc), and dealing with this
incidental complexity and the algorithm complexity is a lot. It may be possible
to use simpler data structures, as we don't make use of everything in these
ones.
Comment at: clang/include/clang/Analysis/Analyses/IntervalPartition.h:38
+// interval.
struct CFGInterval {
+ CFGInterval() = default;
Summarizing an offline discussion, IIUC...
- we build a tree of intervals that represents the whole sequence of interval
graphs
- for the current worklist algorithm, we use only the total order and process
the first invalid block, the tree is not needed
- the algorithm/data structure could be significantly simplified (no variants,
templates, recursion...) if it didn't build the tree, just the interval graphs
iteratively until a single node is reached
- however a different, non-worklist algorithm could use the tree information to
determine which blocks to visit next. (Given `a (b c d) e`, after `d` we try
only `b` or `e`). This avoids expensive "is invalid" checks
- so the motivation for preserving the full interval tree is future-proofing
for using a different algorithm
I think it's worth documenting this motivation, and also considering not paying
this complexity cost for a feature we aren't adding yet.
Comment at: clang/include/clang/Analysis/Analyses/IntervalPartition.h:56
+
+ template struct NodeData {
+// The block from which the interval was constructed. It is either the
xazax.hun wrote:
> Correct me if I'm wrong but I have the impression that `CFGInterval` might
> either contain only `CfgBlock`s or other `CfgInterval`s, but these might
> never be mixed. The current representation does allow such mixing. In case do
> not need that, I think it might be cleaner to make `CfgInterval` itself
> templated and remove the `std::variant`.
(Very optional idea, in case you like it)
This data structure is complicated: a tree of Intervals with CFGBlocks at the
root, and at every level the Intervals have pred/succ edges that form part of
one of the intermediate flow graphs.
It seems nice to get rid of the tree if possible (ultimately we're using these
for ordering) and the nested pred/succs - we seem to only need these for the
top level interval (and in the end, we have one interval and pred/succs are
empty.
What if we made this a flat structure, preserving the bracket structure as some
kind of back-edge?
```
1 ( 2 ( 3 4 ) ) 5
becomes
1 2 3 4 !3 !2 5
```
AIUI, the dataflow algorithm can basically treat this as a program, we move
left to right and `!X` means "if (X is invalidated) goto X".
This would give us something like:
```
using Entry = PointerIntPair; // either an actual block, or a
conditional jump
struct Interval { vector Sequence; SmallDenseSet Preds,
Succs; }
using IntervalGraph = vector;
```
I also suspect that this would let us avoid the core algorithms (buildInterval,
addIntervalNode) being templated, simply wrap each CFGBlock in a trivial
Interval to start with instead. I guess this is OK performance-wise, but the
reason not to do it is ending up with those nodes polluting your final data
structure?
Anyway, all this is up to you - for me keeping more data/structure around than
we're going to use is confusing, but it does seem closer to the textbook.
Comment at: clang/include/clang/Analysis/Analyses/IntervalPartition.h:123
+/// This WTO construction is described in Section 4.2 of [Bourdoncle1993].
+std::optional getIntervalWTO(const CFG &Cfg);
+
Naming is confusing here: `getWTO` is the internal function whose API involves
intervals, and `getIntervalWTO` be the main function whose API doesn't. I think
literally swapping them might be clearer!
in general it's hard to tell which parts of this API people are actually meant
to use.
Is it reasonable to wrap everything up to `WeakTopologicalOrdering` in
`namespace internal` or so? Or are there places this will be used outside tests?
Comment at: clang/include/clang/Analysis/Analyses/IntervalPartition.h:126
+/// Formats `WTO` as a human-readable string.
+std::string formatWTO(const WeakTopologicalOrdering &WTO);
+
consider instead exposing `prin
[PATCH] D153058: [clang][CFG] Support construction of a weak topological ordering of the CFG.
xazax.hun added inline comments.
Comment at: clang/include/clang/Analysis/Analyses/IntervalPartition.h:56-64
+ template 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 Nodes;
+ };
+ using IntervalData = std::variant, NodeData>;
Correct me if I'm wrong but I have the impression that `CFGInterval` might
either contain only `CfgBlock`s or other `CfgInterval`s, but these might never
be mixed. The current representation does allow such mixing. In case do not
need that, I think it might be cleaner to make `CfgInterval` itself templated
and remove the `std::variant`.
Comment at: clang/include/clang/Analysis/Analyses/IntervalPartition.h:101-103
+/// 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
I wonder if we still want to somehow enforce that within a loop/interval the we
visit nodes in the RPO order.
Comment at: clang/lib/Analysis/IntervalPartition.cpp:36
+bool inInterval(const Node *N, std::vector &Interval) {
+ return std::find(Interval.begin(), Interval.end(), N) != Interval.end();
+}
We have some convenience wrappers in LLVM:
https://llvm.org/doxygen/namespacellvm.html#a086e9fbdb06276db7753101a08a63adf
Comment at: clang/lib/Analysis/IntervalPartition.cpp:121
+Index.emplace(N, ID);
+ Graph.Intervals.emplace_back(ID, Header, std::move(Data.Nodes));
}
ymandel wrote:
> xazax.hun wrote:
> > It would probably take for me some time to understand what is going on
> > here, but I think this part might worth a comment. In particular, I have
> > the impression that `Graph.Intervals` is the owner of all the intervals.
> > But we use pointers to refer to these intervals. What would guarantee that
> > those pointers are not being invalidated by this `emplace_back` operations?
> Excellent question, not least because I *wasn't* careful the first around and
> indeed ran up against this as a memory bug. :) That's the reason I added IDs,
> so that I could _avoid_ taking the addresses of elements until after we
> finish growing the vector. See lines 148-165: after we finish building the
> intervals, we go through and take addresses.
>
> I can add comments to this effect, but perhaps the safe option is to use a
> std::dequeue. What do you think?
Oh, thanks! I don't have a strong preference between a comment or a deque.
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D153058/new/
https://reviews.llvm.org/D153058
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D153058: [clang][CFG] Support construction of a weak topological ordering of the CFG.
ymandel marked 2 inline comments as done. ymandel added inline comments. Comment at: clang/lib/Analysis/IntervalPartition.cpp:121 +Index.emplace(N, ID); + Graph.Intervals.emplace_back(ID, Header, std::move(Data.Nodes)); } xazax.hun wrote: > It would probably take for me some time to understand what is going on here, > but I think this part might worth a comment. In particular, I have the > impression that `Graph.Intervals` is the owner of all the intervals. But we > use pointers to refer to these intervals. What would guarantee that those > pointers are not being invalidated by this `emplace_back` operations? Excellent question, not least because I *wasn't* careful the first around and indeed ran up against this as a memory bug. :) That's the reason I added IDs, so that I could _avoid_ taking the addresses of elements until after we finish growing the vector. See lines 148-165: after we finish building the intervals, we go through and take addresses. I can add comments to this effect, but perhaps the safe option is to use a std::dequeue. What do you think? Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D153058/new/ https://reviews.llvm.org/D153058 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D153058: [clang][CFG] Support construction of a weak topological ordering of the CFG.
xazax.hun added inline comments. Comment at: clang/lib/Analysis/IntervalPartition.cpp:121 +Index.emplace(N, ID); + Graph.Intervals.emplace_back(ID, Header, std::move(Data.Nodes)); } It would probably take for me some time to understand what is going on here, but I think this part might worth a comment. In particular, I have the impression that `Graph.Intervals` is the owner of all the intervals. But we use pointers to refer to these intervals. What would guarantee that those pointers are not being invalidated by this `emplace_back` operations? Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D153058/new/ https://reviews.llvm.org/D153058 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D153058: [clang][CFG] Support construction of a weak topological ordering of the CFG.
xazax.hun added inline comments.
Comment at: clang/unittests/Analysis/IntervalPartitionTest.cpp:21
+namespace {
+template using NodeData = CFGInterval::NodeData;
+} // namespace
Another redundant anonymous namespace here.
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D153058/new/
https://reviews.llvm.org/D153058
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D153058: [clang][CFG] Support construction of a weak topological ordering of the CFG.
ymandel marked 4 inline comments as done.
ymandel added a comment.
Rebased, thanks!
Comment at: clang/include/clang/Analysis/Analyses/IntervalPartition.h:73
+
+ // Whether this node is the head of a feedback edge within the interval.
+ bool IsFeedbackHead = false;
xazax.hun wrote:
> Is feedback edge a special terminology? I think we might simply call these
> back edges most of the time.
That's the language from the paper but I prefer standard "back edge"
terminology so updated to reflect.
Comment at: clang/lib/Analysis/IntervalPartition.cpp:23-25
+namespace {
+template using NodeData = CFGInterval::NodeData;
+} // namespace
xazax.hun wrote:
> What is the reason for putting a using statement in an anonymous namespace?
I... don't remember what I was thinking. Regardless, seems pointless for a
template -- fixed.
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D153058/new/
https://reviews.llvm.org/D153058
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D153058: [clang][CFG] Support construction of a weak topological ordering of the CFG.
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
+#include
namespace clang {
-namespace analysis {
+
+namespace {
+template using NodeData = CFGInterval::NodeData;
+} // namespace
+
+llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
+ const CFGInterval::IntervalData &D) {
+ OS << "Nodes{";
+ if (std::holds_alternative>(D)) {
+auto &BlockData = std::get>(D);
+for (const auto *B : BlockData.Nodes)
+ OS << B->getBlockID() << ", ";
+ } else {
+assert(std::holds_alternative>(D));
+auto &IntervalData = std::get>(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
+auto BlockIDs(T... IDs) {
+ return UnorderedElementsAre(
+ ::testing::Property(&CFGBlock::getBlockID, IDs)...);
+}
+
+template
+auto IntervalIDs(T... IDs) {
+ return UnorderedElementsAre(
+ ::testing::Field(&CFGInterval::ID, IDs)...);
+}
+
+MATCHER_P3(IsBlockInterval, ID, Preds, Succs, "") {
+ if (!std::holds_alternative>(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>(arg.Data))
+return false;
+ auto &IntervalData = std::get>(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>(arg.Data))
+return false;
+ auto &IntervalData = std::get>(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 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 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 I1 = buildInterval(EntryBlock);
+ EXPECT_THAT(I1, UnorderedElementsAre(EntryBlock, InitXBlock));
- CFGInterval I2 = buil
[PATCH] D153058: [clang][CFG] Support construction of a weak topological ordering of the CFG.
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
+#include
namespace clang {
-namespace analysis {
+
+namespace {
+template using NodeData = CFGInterval::NodeData;
+} // namespace
+
+llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
+ const CFGInterval::IntervalData &D) {
+ OS << "Nodes{";
+ if (std::holds_alternative>(D)) {
+auto &BlockData = std::get>(D);
+for (const auto *B : BlockData.Nodes)
+ OS << B->getBlockID() << ", ";
+ } else {
+assert(std::holds_alternative>(D));
+auto &IntervalData = std::get>(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
+auto BlockIDs(T... IDs) {
+ return UnorderedElementsAre(
+ ::testing::Property(&CFGBlock::getBlockID, IDs)...);
+}
+
+template
+auto IntervalIDs(T... IDs) {
+ return UnorderedElementsAre(
+ ::testing::Field(&CFGInterval::ID, IDs)...);
+}
+
+MATCHER_P3(IsBlockInterval, ID, Preds, Succs, "") {
+ if (!std::holds_alternative>(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>(arg.Data))
+return false;
+ auto &IntervalData = std::get>(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>(arg.Data))
+return false;
+ auto &IntervalData = std::get>(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 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 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 I1 = buildInterval(EntryBlock);
+ EXPECT_THAT(I1, UnorderedElementsAre(EntryBlock, InitXBlock));
- CFGInterva
[PATCH] D153058: [clang][CFG] Support construction of a weak topological ordering of the CFG.
xazax.hun added a comment.
Could you rebase this patch to the latest tip of tree?
Comment at: clang/include/clang/Analysis/Analyses/IntervalPartition.h:73
+
+ // Whether this node is the head of a feedback edge within the interval.
+ bool IsFeedbackHead = false;
Is feedback edge a special terminology? I think we might simply call these back
edges most of the time.
Comment at: clang/include/clang/Analysis/Analyses/IntervalPartition.h:83
-// 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.
typo?
Comment at: clang/include/clang/Analysis/Analyses/IntervalPartition.h:87
+
+// (Further) partitions `Graph` into intervals and constructs a the graph of
the
+// intervals based on the edges between nodes (themselves intervals) in these
same typo here?
Comment at: clang/lib/Analysis/IntervalPartition.cpp:23-25
+namespace {
+template using NodeData = CFGInterval::NodeData;
+} // namespace
What is the reason for putting a using statement in an anonymous namespace?
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D153058/new/
https://reviews.llvm.org/D153058
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D153058: [clang][CFG] Support construction of a weak topological ordering of the CFG.
ymandel updated this revision to Diff 531874.
ymandel added a comment.
more comment expansion.
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
+#include
namespace clang {
-namespace analysis {
+
+namespace {
+template using NodeData = CFGInterval::NodeData;
+} // namespace
+
+llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
+ const CFGInterval::IntervalData &D) {
+ OS << "Nodes{";
+ if (std::holds_alternative>(D)) {
+auto &BlockData = std::get>(D);
+for (const auto *B : BlockData.Nodes)
+ OS << B->getBlockID() << ", ";
+ } else {
+assert(std::holds_alternative>(D));
+auto &IntervalData = std::get>(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
+auto BlockIDs(T... IDs) {
+ return UnorderedElementsAre(
+ ::testing::Property(&CFGBlock::getBlockID, IDs)...);
+}
+
+template
+auto IntervalIDs(T... IDs) {
+ return UnorderedElementsAre(
+ ::testing::Field(&CFGInterval::ID, IDs)...);
+}
+
+MATCHER_P3(IsBlockInterval, ID, Preds, Succs, "") {
+ if (!std::holds_alternative>(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>(arg.Data))
+return false;
+ auto &IntervalData = std::get>(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>(arg.Data))
+return false;
+ auto &IntervalData = std::get>(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(EntryBlock);
- EXPECT_EQ(I.Blocks.size(), 3u);
+ std::vector I = buildInterval(&EntryBlock);
+ EXPECT_EQ(I.size(), 3u);
}
TEST(BuildInterval, PartitionIfThenOneInterval) {
@@ -56,12 +162,10 @@
auto &EntryBlock = cfg->getEntry();
- CFGInterval I = buildInterval(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() {
@@ -80,11 +184,11 @@
CFGBlock *InitXBlock = *EntryBlock->succ_begin();
CFGBlock *LoopHeadBlock = *InitXBlock->succ_begin();
- CFGInterval I1 = buildInterval(*EntryBlock);
- EXPECT_THAT(I1.Blocks, UnorderedElementsAre(EntryBlock, InitXBlock));
+ std::vector I1 = buildInterval(EntryBlock);
+ EXPECT_THAT(I1, UnorderedElementsAre(EntryBlock, InitXBlock));
- CFGInterval I2 = buildInterval(*LoopHe
[PATCH] D153058: [clang][CFG] Support construction of a weak topological ordering of the CFG.
ymandel updated this revision to Diff 531865.
ymandel added a comment.
Fix build break and add some field 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
+#include
namespace clang {
-namespace analysis {
+
+namespace {
+template using NodeData = CFGInterval::NodeData;
+} // namespace
+
+llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
+ const CFGInterval::IntervalData &D) {
+ OS << "Nodes{";
+ if (std::holds_alternative>(D)) {
+auto &BlockData = std::get>(D);
+for (const auto *B : BlockData.Nodes)
+ OS << B->getBlockID() << ", ";
+ } else {
+assert(std::holds_alternative>(D));
+auto &IntervalData = std::get>(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
+auto BlockIDs(T... IDs) {
+ return UnorderedElementsAre(
+ ::testing::Property(&CFGBlock::getBlockID, IDs)...);
+}
+
+template
+auto IntervalIDs(T... IDs) {
+ return UnorderedElementsAre(
+ ::testing::Field(&CFGInterval::ID, IDs)...);
+}
+
+MATCHER_P3(IsBlockInterval, ID, Preds, Succs, "") {
+ if (!std::holds_alternative>(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>(arg.Data))
+return false;
+ auto &IntervalData = std::get>(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>(arg.Data))
+return false;
+ auto &IntervalData = std::get>(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(EntryBlock);
- EXPECT_EQ(I.Blocks.size(), 3u);
+ std::vector I = buildInterval(&EntryBlock);
+ EXPECT_EQ(I.size(), 3u);
}
TEST(BuildInterval, PartitionIfThenOneInterval) {
@@ -56,12 +162,10 @@
auto &EntryBlock = cfg->getEntry();
- CFGInterval I = buildInterval(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() {
@@ -80,11 +184,11 @@
CFGBlock *InitXBlock = *EntryBlock->succ_begin();
CFGBlock *LoopHeadBlock = *InitXBlock->succ_begin();
- CFGInterval I1 = buildInterval(*EntryBlock);
- EXPECT_THAT(I1.Blocks, UnorderedElementsAre(EntryBlock, InitXBlock));
+ std::vector I1 = buildInterval(EntryBlock);
+ EXPECT_THAT(I1, UnorderedElementsAre(EntryBlock, InitXBlock));
- CFGInterval I2 =
[PATCH] D153058: [clang][CFG] Support construction of a weak topological ordering of the CFG.
ymandel updated this revision to Diff 531843.
ymandel added a comment.
fix 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,115 @@
#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 CFGInterval::IntervalData &D) {
+ OS << "Nodes{";
+ if (std::holds_alternative>(D)) {
+auto &BlockData = std::get>(D);
+for (const auto *B : BlockData.Nodes)
+ OS << B->getBlockID() << ", ";
+ } else {
+assert(std::holds_alternative>(D));
+auto &IntervalData = std::get>(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
+auto BlockIDs(T... IDs) {
+ return UnorderedElementsAre(
+ ::testing::Property(&CFGBlock::getBlockID, IDs)...);
+}
+
+template
+auto IntervalIDs(T... IDs) {
+ return UnorderedElementsAre(
+ ::testing::Field(&CFGInterval::ID, IDs)...);
+}
+
+MATCHER_P3(IsBlockInterval, ID, Preds, Succs, "") {
+ if (!std::holds_alternative>(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>(arg.Data))
+return false;
+ auto &IntervalData = std::get>(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>(arg.Data))
+return false;
+ auto &IntervalData = std::get>(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 +134,8 @@
auto &EntryBlock = cfg->getEntry();
- CFGInterval I = buildInterval(EntryBlock);
- EXPECT_EQ(I.Blocks.size(), 3u);
+ std::vector I = buildInterval(&EntryBlock);
+ EXPECT_EQ(I.size(), 3u);
}
TEST(BuildInterval, PartitionIfThenOneInterval) {
@@ -56,12 +158,10 @@
auto &EntryBlock = cfg->getEntry();
- CFGInterval I = buildInterval(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() {
@@ -80,11 +180,11 @@
CFGBlock *InitXBlock = *EntryBlock->succ_begin();
CFGBlock *LoopHeadBlock = *InitXBlock->succ_begin();
- CFGInterval I1 = buildInterval(*EntryBlock);
- EXPECT_THAT(I1.Blocks, UnorderedElementsAre(EntryBlock, InitXBlock));
+ std::vector I1 = buildInterval(EntryBlock);
+ EXPECT_THAT(I1, UnorderedElementsAre(EntryBlock, InitXBlock));
- CFGInterval I2 = buildInterval(*LoopHeadBlock);
- EXPECT_EQ(I2.Blocks.size(), 5u);
+ std::vector I2 = buildInterval(LoopHead
[PATCH] D153058: [clang][CFG] Support construction of a weak topological ordering of the CFG.
ymandel created this revision.
ymandel added reviewers: xazax.hun, gribozavr.
Herald added a reviewer: NoQ.
Herald added a project: All.
ymandel requested review of this revision.
Herald added a project: clang.
This patch adds support for building a weak topological ordering of the CFG
blocks, based on a limit flow graph constructed via (repeated) interval
partitioning of the CFG.
Repository:
rG LLVM Github Monorepo
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,115 @@
#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 CFGInterval::IntervalData &D) {
+ OS << "Nodes{";
+ if (std::holds_alternative>(D)) {
+auto &BlockData = std::get>(D);
+for (const auto *B : BlockData.Nodes)
+ OS << B->getBlockID() << ", ";
+ } else {
+assert(std::holds_alternative>(D));
+auto &IntervalData = std::get>(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
+auto BlockIDs(T... IDs) {
+ return UnorderedElementsAre(
+ ::testing::Property(&CFGBlock::getBlockID, IDs)...);
+}
+
+template
+auto IntervalIDs(T... IDs) {
+ return UnorderedElementsAre(
+ ::testing::Field(&CFGInterval::ID, IDs)...);
+}
+
+MATCHER_P3(IsBlockInterval, ID, Preds, Succs, "") {
+ if (!std::holds_alternative>(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>(arg.Data))
+return false;
+ auto &IntervalData = std::get>(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>(arg.Data))
+return false;
+ auto &IntervalData = std::get>(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 +134,8 @@
auto &EntryBlock = cfg->getEntry();
- CFGInterval I = buildInterval(EntryBlock);
- EXPECT_EQ(I.Blocks.size(), 3u);
+ std::vector I = buildInterval(&EntryBlock);
+ EXPECT_EQ(I.size(), 3u);
}
TEST(BuildInterval, PartitionIfThenOneInterval) {
@@ -56,12 +158,10 @@
auto &EntryBlock = cfg->getEntry();
- CFGInterval I = buildInterval(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() {
@@ -80,11 +180,11 @@
CFGBlock *InitXBlock = *EntryBlock->succ_begin();
CFGBlock *LoopHeadBlock = *InitXBlock->succ_begin();
- CFGInterval I1 = buildInterval(*EntryBlock);
- EXPECT_THAT(I1.Blocks, UnorderedElementsAre(EntryBlock, InitXBlock));
+ std::vector I1
