[clang][CFG] Fix 2 memory errors in interval computation.

[ymandel]

Summary

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.

[ymandel]

rebase

[ymandel]

rebase onto main

clang/lib/Analysis/IntervalPartition.cpp

 //===----------------------------------------------------------------------===//
 
 #include "clang/Analysis/Analyses/IntervalPartition.h"
 #include "clang/Analysis/CFG.h"
 #include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/STLExtras.h"
 #include <optional>
 #include <queue>
-#include <set>
 #include <vector>
 
 namespace clang {
 
 // 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.
   //
   // Elements must not be null. Duplicates are prevented using `Workset`, below.
   std::queue<const Node *> Worklist;
   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);
         Workset.set(SID);
       }
 
   // Contains successors of blocks in the interval that couldn't be added to the
   // interval on their first encounter. This occurs when they have a predecessor
   // that is either definitively outside the interval or hasn't been considered
   // 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);
 
     // Check whether all predecessors are in the interval, in which case `B`
     // is included as well.
     bool AllInInterval = llvm::all_of(B->preds(), [&](const Node *P) {
       return llvm::is_contained(Interval.Nodes, P);
     });
     if (AllInInterval) {
       Interval.Nodes.push_back(B);
       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);
           }
     } else {
       MaybeSuccessors.push_back(B);
     }
   }
void fillIntervalNode(CFGIntervalGraph &Graph,
 
   CFGIntervalNode &Interval = Graph.emplace_back(Graph.size());
 
   // Index the nodes of the new interval. The index maps nodes from the input
   // graph (specifically, `Result.Nodes`) to identifiers of nodes in the output
   // graph. In this case, the new interval has identifier `ID` so all of its
   // nodes (`Result.Nodes`) map to `ID`.
   for (const auto *N : Result.Nodes) {
-    assert(getID(N) < Index.size());
-    Index[getID(N)] = &Interval;
+    assert(N != nullptr);
+    assert(getID(*N) < Index.size());
+    Index[getID(*N)] = &Interval;
   }
 
   if constexpr (std::is_same_v<std::decay_t<Node>, CFGBlock>)
     Interval.Nodes = std::move(Result.Nodes);
   else {
     std::vector<const CFGBlock *> Nodes;
     // Flatten the sub vectors into a single list.
     size_t Count = 0;
CFGIntervalGraph partitionIntoIntervalsImpl(unsigned NumBlockIDs,
   std::queue<const Node *> Successors;
 
   fillIntervalNode(Graph, Index, Successors, Partitioned, EntryBlock);
   Intervals.emplace_back(EntryBlock, &Graph.back());
 
   while (!Successors.empty()) {
     const auto *B = Successors.front();
     Successors.pop();
-    if (Partitioned.test(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
     // new interval from `B`.
     fillIntervalNode(Graph, Index, Successors, Partitioned, B);
     Intervals.emplace_back(B, &Graph.back());
   }
 
   // Go back and patch up all the Intervals -- the successors and predecessors.
   for (auto [H, N] : Intervals) {
     // Map input-graph predecessors to output-graph nodes and mark those as
     // predecessors of `N`. Then, mark `N` as a successor of said predecessor.
     for (const Node *P : H->preds()) {
-      assert(getID(P) < NumBlockIDs);
-      CFGIntervalNode *Pred = Index[getID(P)];
+      if (P == nullptr)
+        continue;
+
+      assert(getID(*P) < NumBlockIDs);
+      CFGIntervalNode *Pred = Index[getID(*P)];
       if (Pred == nullptr)
         // Unreachable node.
         continue;
       if (Pred != N // Not a backedge.
           && N->Predecessors.insert(Pred).second)
         // Note: given the guard above, which guarantees we only ever insert
         // unique elements, we could use a simple list (like `vector`) for
         // `Successors`, rather than a set.
std::optional<std::vector<const CFGBlock *>> getIntervalWTO(const CFG &Cfg) {
   return std::move(Graph[0].Nodes);
 }
 
 WTOCompare::WTOCompare(const WeakTopologicalOrdering &WTO) {
   if (WTO.empty())
     return;
   auto N = WTO[0]->getParent()->getNumBlockIDs();
   BlockOrder.resize(N, 0);
-  for (unsigned I = 0; I < N; ++I)
+  for (unsigned I = 0, S = WTO.size(); I < S; ++I)
     BlockOrder[WTO[I]->getBlockID()] = I + 1;
 }
 } // namespace clang

clang/unittests/Analysis/IntervalPartitionTest.cpp

const char *Code = R"(void f() {
                           x = x + x;
                         })";
   BuildResult Result = BuildCFG(Code);
   ASSERT_EQ(BuildResult::BuiltCFG, Result.getStatus());
   EXPECT_THAT(getIntervalWTO(*Result.getCFG()),
               Optional(blockOrder(9, 8, 7, 6, 1, 0, 5, 4, 2, 3)));
 }
 
+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