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<WeakTopologicalOrdering> 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 <optional>
#include <queue>
-#include <set>
#include <vector>
namespace clang {
@@ -24,23 +23,25 @@
// Intermediate data used in constructing a CFGIntervalNode.
template <typename Node> struct BuildResult {
// Use a vector to maintain the insertion order. Given the expected small
- // number of nodes, vector should be sufficiently efficient.
+ // number of nodes, vector should be sufficiently efficient. Elements must not
+ // be null.
std::vector<const Node *> Nodes;
+ // Elements must not be null.
llvm::SmallDenseSet<const Node *> 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 <typename Node>
BuildResult<Node> buildInterval(llvm::BitVector &Partitioned,
const Node *Header) {
- assert(Header);
+ assert(Header != nullptr);
BuildResult<Node> 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<const Node *> 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<std::decay_t<Node>, CFGBlock>)
@@ -159,7 +161,8 @@
while (!Successors.empty()) {
const auto *B = Successors.front();
Successors.pop();
- if (Partitioned.test(getID(B)))
+ assert(B != nullptr);
+ if (Partitioned.test(getID(*B)))
continue;
// B has not been partitioned, but it has a predecessor that has. Create a
@@ -173,8 +176,11 @@
// Map input-graph predecessors to output-graph nodes and mark those as
// predecessors of `N`. Then, mark `N` as a successor of said predecessor.
for (const Node *P : H->preds()) {
- assert(getID(P) < NumBlockIDs);
- CFGIntervalNode *Pred = Index[getID(P)];
+ if (P == nullptr)
+ continue;
+
+ assert(getID(*P) < NumBlockIDs);
+ CFGIntervalNode *Pred = Index[getID(*P)];
if (Pred == nullptr)
// Unreachable node.
continue;
@@ -229,7 +235,7 @@
return;
auto N = WTO[0]->getParent()->getNumBlockIDs();
BlockOrder.resize(N, 0);
- for (unsigned I = 0; I < N; ++I)
+ for (unsigned I = 0, S = WTO.size(); I < S; ++I)
BlockOrder[WTO[I]->getBlockID()] = I + 1;
}
} // namespace clang
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
