[PATCH] D157033: [clang][CFG] Fix 2 memory errors in interval computation.
This revision was automatically updated to reflect the committed changes.
Closed by commit rGe21b1dd9cc53: [clang][CFG] Fix 2 memory errors in interval
computation. (authored by ymandel).
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D157033/new/
https://reviews.llvm.org/D157033
Files:
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
@@ -360,5 +360,38 @@
Optional(blockOrder(9, 8, 7, 6, 1, 0, 5, 4, 2, 3)));
}
+TEST(GetIntervalWTO, UnreachablePred) {
+ const char *Code = R"(
+ void target(bool Foo) {
+bool Bar = false;
+if (Foo)
+ Bar = Foo;
+else
+ __builtin_unreachable();
+(void)0;
+ })";
+ BuildResult Result = BuildCFG(Code);
+ ASSERT_EQ(BuildResult::BuiltCFG, Result.getStatus());
+ EXPECT_THAT(getIntervalWTO(*Result.getCFG()),
+ Optional(blockOrder(5, 4, 3, 2, 1, 0)));
+}
+
+TEST(WTOCompare, UnreachableBlock) {
+ const char *Code = R"(
+void target() {
+ while (true) {}
+ (void)0;
+ /*[[p]]*/
+})";
+ BuildResult Result = BuildCFG(Code);
+ ASSERT_EQ(BuildResult::BuiltCFG, Result.getStatus());
+ std::optional WTO = getIntervalWTO(*Result.getCFG());
+ ASSERT_THAT(WTO, Optional(blockOrder(4, 3, 2)));
+ auto Cmp = WTOCompare(*WTO);
+ const CFGBlock &Entry = Result.getCFG()->getEntry();
+ const CFGBlock &Exit = Result.getCFG()->getExit();
+ EXPECT_TRUE(Cmp(&Entry, &Exit));
+}
+
} // namespace
} // namespace clang
Index: clang/lib/Analysis/IntervalPartition.cpp
===
--- clang/lib/Analysis/IntervalPartition.cpp
+++ clang/lib/Analysis/IntervalPartition.cpp
@@ -16,7 +16,6 @@
#include "llvm/ADT/STLExtras.h"
#include
#include
-#include
#include
namespace clang {
@@ -24,23 +23,25 @@
// 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.
+ // number of nodes, vector should be sufficiently efficient. Elements must not
+ // be null.
std::vector Nodes;
+ // Elements must not be null.
llvm::SmallDenseSet Successors;
};
namespace internal {
-static unsigned getID(const CFGBlock *B) { return B->getBlockID(); }
-static unsigned getID(const CFGIntervalNode *I) { return I->ID; }
+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);
+ assert(Header != nullptr);
BuildResult Interval;
Interval.Nodes.push_back(Header);
- Partitioned.set(getID(Header));
+ Partitioned.set(getID(*Header));
// FIXME: Compare performance against using RPO to consider nodes, rather than
// following successors.
@@ -50,7 +51,7 @@
llvm::BitVector Workset(Partitioned.size(), false);
for (const Node *S : Header->succs())
if (S != nullptr)
- if (auto SID = getID(S); !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);
@@ -63,12 +64,12 @@
// 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.
+ // successors. Elements are never null.
std::vector MaybeSuccessors;
while (!Worklist.empty()) {
const auto *B = Worklist.front();
-auto ID = getID(B);
+auto ID = getID(*B);
Worklist.pop();
Workset.reset(ID);
@@ -82,7 +83,7 @@
Partitioned.set(ID);
for (const Node *S : B->succs())
if (S != nullptr)
- if (auto SID = getID(S);
+ if (auto SID = getID(*S);
!Partitioned.test(SID) && !Workset.test(SID)) {
Worklist.push(S);
Workset.set(SID);
@@ -116,8 +117,9 @@
// 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;
+assert(N != nullptr);
+assert(getID(*N) < Index.size());
+Index[getID(*N)] = &Interval;
}
if constexpr (std::is_same_v, CFGBlock>)
@@ -159,7 +161,8 @@
while (!Successors.empty()) {
const auto *
[PATCH] D157033: [clang][CFG] Fix 2 memory errors in interval computation.
ymandel updated this revision to Diff 547305.
ymandel added a comment.
rebase onto main
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D157033/new/
https://reviews.llvm.org/D157033
Files:
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
@@ -360,5 +360,38 @@
Optional(blockOrder(9, 8, 7, 6, 1, 0, 5, 4, 2, 3)));
}
+TEST(GetIntervalWTO, UnreachablePred) {
+ const char *Code = R"(
+ void target(bool Foo) {
+bool Bar = false;
+if (Foo)
+ Bar = Foo;
+else
+ __builtin_unreachable();
+(void)0;
+ })";
+ BuildResult Result = BuildCFG(Code);
+ ASSERT_EQ(BuildResult::BuiltCFG, Result.getStatus());
+ EXPECT_THAT(getIntervalWTO(*Result.getCFG()),
+ Optional(blockOrder(5, 4, 3, 2, 1, 0)));
+}
+
+TEST(WTOCompare, UnreachableBlock) {
+ const char *Code = R"(
+void target() {
+ while (true) {}
+ (void)0;
+ /*[[p]]*/
+})";
+ BuildResult Result = BuildCFG(Code);
+ ASSERT_EQ(BuildResult::BuiltCFG, Result.getStatus());
+ std::optional WTO = getIntervalWTO(*Result.getCFG());
+ ASSERT_THAT(WTO, Optional(blockOrder(4, 3, 2)));
+ auto Cmp = WTOCompare(*WTO);
+ const CFGBlock &Entry = Result.getCFG()->getEntry();
+ const CFGBlock &Exit = Result.getCFG()->getExit();
+ EXPECT_TRUE(Cmp(&Entry, &Exit));
+}
+
} // namespace
} // namespace clang
Index: clang/lib/Analysis/IntervalPartition.cpp
===
--- clang/lib/Analysis/IntervalPartition.cpp
+++ clang/lib/Analysis/IntervalPartition.cpp
@@ -16,7 +16,6 @@
#include "llvm/ADT/STLExtras.h"
#include
#include
-#include
#include
namespace clang {
@@ -24,23 +23,25 @@
// 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.
+ // number of nodes, vector should be sufficiently efficient. Elements must not
+ // be null.
std::vector Nodes;
+ // Elements must not be null.
llvm::SmallDenseSet Successors;
};
namespace internal {
-static unsigned getID(const CFGBlock *B) { return B->getBlockID(); }
-static unsigned getID(const CFGIntervalNode *I) { return I->ID; }
+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);
+ assert(Header != nullptr);
BuildResult Interval;
Interval.Nodes.push_back(Header);
- Partitioned.set(getID(Header));
+ Partitioned.set(getID(*Header));
// FIXME: Compare performance against using RPO to consider nodes, rather than
// following successors.
@@ -50,7 +51,7 @@
llvm::BitVector Workset(Partitioned.size(), false);
for (const Node *S : Header->succs())
if (S != nullptr)
- if (auto SID = getID(S); !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);
@@ -63,12 +64,12 @@
// 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.
+ // successors. Elements are never null.
std::vector MaybeSuccessors;
while (!Worklist.empty()) {
const auto *B = Worklist.front();
-auto ID = getID(B);
+auto ID = getID(*B);
Worklist.pop();
Workset.reset(ID);
@@ -82,7 +83,7 @@
Partitioned.set(ID);
for (const Node *S : B->succs())
if (S != nullptr)
- if (auto SID = getID(S);
+ if (auto SID = getID(*S);
!Partitioned.test(SID) && !Workset.test(SID)) {
Worklist.push(S);
Workset.set(SID);
@@ -116,8 +117,9 @@
// 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;
+assert(N != nullptr);
+assert(getID(*N) < Index.size());
+Index[getID(*N)] = &Interval;
}
if constexpr (std::is_same_v, CFGBlock>)
@@ -159,7 +161,8 @@
while (!Successors.empty()) {
const auto *B = Successors.front();
Successors.pop();
-if (Partitioned.test(getID(B)))
+assert(B !
[PATCH] D157033: [clang][CFG] Fix 2 memory errors in interval computation.
ymandel updated this revision to Diff 547008.
ymandel added a comment.
rebase
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D157033/new/
https://reviews.llvm.org/D157033
Files:
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
@@ -360,5 +360,38 @@
Optional(blockOrder(9, 8, 7, 6, 1, 0, 5, 4, 2, 3)));
}
+TEST(GetIntervalWTO, UnreachablePred) {
+ const char *Code = R"(
+ void target(bool Foo) {
+bool Bar = false;
+if (Foo)
+ Bar = Foo;
+else
+ __builtin_unreachable();
+(void)0;
+ })";
+ BuildResult Result = BuildCFG(Code);
+ ASSERT_EQ(BuildResult::BuiltCFG, Result.getStatus());
+ EXPECT_THAT(getIntervalWTO(*Result.getCFG()),
+ Optional(blockOrder(5, 4, 3, 2, 1, 0)));
+}
+
+TEST(WTOCompare, UnreachableBlock) {
+ const char *Code = R"(
+void target() {
+ while (true) {}
+ (void)0;
+ /*[[p]]*/
+})";
+ BuildResult Result = BuildCFG(Code);
+ ASSERT_EQ(BuildResult::BuiltCFG, Result.getStatus());
+ std::optional WTO = getIntervalWTO(*Result.getCFG());
+ ASSERT_THAT(WTO, Optional(blockOrder(4, 3, 2)));
+ auto Cmp = WTOCompare(*WTO);
+ const CFGBlock &Entry = Result.getCFG()->getEntry();
+ const CFGBlock &Exit = Result.getCFG()->getExit();
+ EXPECT_TRUE(Cmp(&Entry, &Exit));
+}
+
} // namespace
} // namespace clang
Index: clang/lib/Analysis/IntervalPartition.cpp
===
--- clang/lib/Analysis/IntervalPartition.cpp
+++ clang/lib/Analysis/IntervalPartition.cpp
@@ -16,7 +16,6 @@
#include "llvm/ADT/STLExtras.h"
#include
#include
-#include
#include
namespace clang {
@@ -24,23 +23,25 @@
// 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.
+ // number of nodes, vector should be sufficiently efficient. Elements must not
+ // be null.
std::vector Nodes;
+ // Elements must not be null.
llvm::SmallDenseSet Successors;
};
namespace internal {
-static unsigned getID(const CFGBlock *B) { return B->getBlockID(); }
-static unsigned getID(const CFGIntervalNode *I) { return I->ID; }
+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);
+ assert(Header != nullptr);
BuildResult Interval;
Interval.Nodes.push_back(Header);
- Partitioned.set(getID(Header));
+ Partitioned.set(getID(*Header));
// FIXME: Compare performance against using RPO to consider nodes, rather than
// following successors.
@@ -50,7 +51,7 @@
llvm::BitVector Workset(Partitioned.size(), false);
for (const Node *S : Header->succs())
if (S != nullptr)
- if (auto SID = getID(S); !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);
@@ -63,12 +64,12 @@
// 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.
+ // successors. Elements are never null.
std::vector MaybeSuccessors;
while (!Worklist.empty()) {
const auto *B = Worklist.front();
-auto ID = getID(B);
+auto ID = getID(*B);
Worklist.pop();
Workset.reset(ID);
@@ -82,7 +83,7 @@
Partitioned.set(ID);
for (const Node *S : B->succs())
if (S != nullptr)
- if (auto SID = getID(S);
+ if (auto SID = getID(*S);
!Partitioned.test(SID) && !Workset.test(SID)) {
Worklist.push(S);
Workset.set(SID);
@@ -116,8 +117,9 @@
// 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;
+assert(N != nullptr);
+assert(getID(*N) < Index.size());
+Index[getID(*N)] = &Interval;
}
if constexpr (std::is_same_v, CFGBlock>)
@@ -159,7 +161,8 @@
while (!Successors.empty()) {
const auto *B = Successors.front();
Successors.pop();
-if (Partitioned.test(getID(B)))
+assert(B != nullptr)
[PATCH] D157033: [clang][CFG] Fix 2 memory errors in interval computation.
ymandel created this revision.
ymandel added a reviewer: xazax.hun.
Herald added a reviewer: NoQ.
Herald added a project: All.
ymandel requested review of this revision.
Herald added a project: clang.
This fixes 2 bugs and adds corresponding tests. Both related to unreachable
blocks. One occured in the `WTOCompare` construction, which assumed the size of
the order was the same as the number of blocks in the CFG, which isn't true when
some blocks are unreachable. The other assumed predecessor pointers were
non-null, which can be false for blocks with unreachable predecessors.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D157033
Files:
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
@@ -360,5 +360,38 @@
Optional(blockOrder(9, 8, 7, 6, 1, 0, 5, 4, 2, 3)));
}
+TEST(GetIntervalWTO, UnreachablePred) {
+ const char *Code = R"(
+ void target(bool Foo) {
+bool Bar = false;
+if (Foo)
+ Bar = Foo;
+else
+ __builtin_unreachable();
+(void)0;
+ })";
+ BuildResult Result = BuildCFG(Code);
+ ASSERT_EQ(BuildResult::BuiltCFG, Result.getStatus());
+ EXPECT_THAT(getIntervalWTO(*Result.getCFG()),
+ Optional(blockOrder(5, 4, 3, 2, 1, 0)));
+}
+
+TEST(WTOCompare, UnreachableBlock) {
+ const char *Code = R"(
+void target() {
+ while (true) {}
+ (void)0;
+ /*[[p]]*/
+})";
+ BuildResult Result = BuildCFG(Code);
+ ASSERT_EQ(BuildResult::BuiltCFG, Result.getStatus());
+ std::optional WTO = getIntervalWTO(*Result.getCFG());
+ ASSERT_THAT(WTO, Optional(blockOrder(4, 3, 2)));
+ auto Cmp = WTOCompare(*WTO);
+ const CFGBlock &Entry = Result.getCFG()->getEntry();
+ const CFGBlock &Exit = Result.getCFG()->getExit();
+ EXPECT_TRUE(Cmp(&Entry, &Exit));
+}
+
} // namespace
} // namespace clang
Index: clang/lib/Analysis/IntervalPartition.cpp
===
--- clang/lib/Analysis/IntervalPartition.cpp
+++ clang/lib/Analysis/IntervalPartition.cpp
@@ -16,7 +16,6 @@
#include "llvm/ADT/STLExtras.h"
#include
#include
-#include
#include
namespace clang {
@@ -24,23 +23,25 @@
// 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.
+ // number of nodes, vector should be sufficiently efficient. Elements must not
+ // be null.
std::vector Nodes;
+ // Elements must not be null.
llvm::SmallDenseSet Successors;
};
namespace internal {
-static unsigned getID(const CFGBlock *B) { return B->getBlockID(); }
-static unsigned getID(const CFGIntervalNode *I) { return I->ID; }
+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);
+ assert(Header != nullptr);
BuildResult Interval;
Interval.Nodes.push_back(Header);
- Partitioned.set(getID(Header));
+ Partitioned.set(getID(*Header));
// FIXME: Compare performance against using RPO to consider nodes, rather than
// following successors.
@@ -50,7 +51,7 @@
llvm::BitVector Workset(Partitioned.size(), false);
for (const Node *S : Header->succs())
if (S != nullptr)
- if (auto SID = getID(S); !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);
@@ -63,12 +64,12 @@
// 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.
+ // successors. Elements are never null.
std::vector MaybeSuccessors;
while (!Worklist.empty()) {
const auto *B = Worklist.front();
-auto ID = getID(B);
+auto ID = getID(*B);
Worklist.pop();
Workset.reset(ID);
@@ -82,7 +83,7 @@
Partitioned.set(ID);
for (const Node *S : B->succs())
if (S != nullptr)
- if (auto SID = getID(S);
+ if (auto SID = getID(*S);
!Partitioned.test(SID) && !Workset.test(SID)) {
Worklist.push(S);
Workset.set(SID);
@@ -116,8 +117,9 @@
// graph. In this case, the new interval has identifier `ID` so all of its
// nodes (`Result.Nodes`) map to `ID`.
fo
