[clang][dataflow] Add support for noreturn destructor calls

[sgatev]

Summary

This is part of the implementation of the dataflow analysis framework.
See "[RFC] A dataflow analysis framework for Clang AST" on cfe-dev.

[sgatev]

Remove anonymous namespace.

[xazax.hun]

clang/include/clang/Analysis/FlowSensitive/ControlFlowContext.h

51

There is a special class for this at clang/lib/Analysis/CFGStmtMap.cpp. That also does some special handling of the terminators. I wonder if we need to do something similar here (or just use that class as is?).

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

51

This comment might be a bit hard to understand without a code example. Admittedly, including an example here could get very chatty, but we could refer to the name of the corresponding test.

I wonder whether naming the blocks like The first successor of block 'A' would make this clearer.

[xazax.hun]

I am looking at the CFG and wonder if this change is what we what to do in the first place:

[B7 (ENTRY)]
   Succs (1): B6

 [B1]
   1: 0
   2: (void)[B1.1] (CStyleCastExpr, ToVoid, void)
   Preds (2): B2(Unreachable) B3
   Succs (1): B0

 [B2 (NORETURN)]
   1: ~Fatal() (Temporary object destructor)
   Preds (1): B3
   Succs (1): B0

 [B3]
   1: [B6.2] ? [B4.3] : [B5.5]
   2: int value = b ? foo() : Fatal().bar();
   T: (Temp Dtor) [B5.2]
   Preds (2): B4 B5
   Succs (2): B2 B1

 [B4]
   1: foo
   2: [B4.1] (ImplicitCastExpr, FunctionToPointerDecay, int (*)(void))
   3: [B4.2]()
   Preds (1): B6
   Succs (1): B3

 [B5]
   1: Fatal() (CXXConstructExpr, [B5.2], [B5.3], class Fatal)
   2: [B5.1] (BindTemporary)
   3: [B5.2]
   4: [B5.3].bar
   5: [B5.4]()
   Preds (1): B6
   Succs (1): B3

 [B6]
   1: b
   2: [B6.1] (ImplicitCastExpr, LValueToRValue, _Bool)
   T: [B6.2] ? ... : ...
   Preds (1): B7
   Succs (2): B4 B5

 [B0 (EXIT)]
   Preds (2): B1 B2

To summarize the problem, and let me know if I'm wrong:

• In the CFG the noreturn block works as expected, its only successor is the exit block, this is great
• The source of the problem is that we have a join node, where we do a merge BEFORE reaching the noreturn block, so we end up propagating the states from the noreturn block.
• This code tries to pattern match this particular pattern in the CFG and introduce a small degree of local path-sensitivity.

How resilient is this pattern matching? Will this work if we swap the branches of the ternary operator? Will this work if there are multiple dtors in either/both branches? Will this work if there are dtors coming from the condition? Will this work of I start nesting ternary operators? I think this needs more coverage.

Also, I wonder if concentrating on noreturn is the right approach here. The root cause of this problem has relatively little to do with noreturn, and we could probably come up with a poorly behaving analysis even without having a single noreturn destructor. The root cause is the overly eager merge in the CFG.
Some alternative approaches:

• Duplicate the B3 block to avoid having a join node in the CFG.
• Do a proper pattern matching, match blocks containing the dtor calls with the branches of the ternary, and only propagate the states from the corresponding branches. I.e., do the correct state propagation even when we have no noreturn dtors.

[gribozavr2]

clang/include/clang/Analysis/FlowSensitive/ControlFlowContext.h

51

The only downside I see is that CFGStmtMap needs a ParentMap, which is not cheap to make, but we don't need. Maybe we need to make it optional in CFGStmtMap?

clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h

103

I'd suggest a more verbose name like CFCtx, since Ctx is most often used in Clang for ASTContext. (Here and elsewhere in the patch.)

clang/lib/Analysis/FlowSensitive/ControlFlowContext.cpp

2

Please add a license comment.

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

47

Use llvm::cantFail to unwrap the Expected?

[gribozavr2]

How resilient is this pattern matching?

Possibly it is not very robust. However it is very important for a certain style of precondition verification macros used by various Google projects. I can't find an exact open source copy, but they are generally similar to this one, but usually use a ternary instead of an if statement:

https://source.chromium.org/chromium/chromium/src/+/main:third_party/re2/src/util/logging.h

Also similar to this one, but with an object that has a noreturn destructor instead of inline assembly that causes a trap:

https://source.chromium.org/chromium/chromium/src/+/main:base/check.h

If it wasn't for this "curious" coding pattern that is stamped into many function thanks to the macro, we wouldn't be bothering with this pattern matching at this point.

[xazax.hun]

In D116022#3205478, @gribozavr2 wrote:

How resilient is this pattern matching?

Possibly it is not very robust. However it is very important for a certain style of precondition verification macros used by various Google projects. I can't find an exact open source copy, but they are generally similar to this one, but usually use a ternary instead of an if statement:

https://source.chromium.org/chromium/chromium/src/+/main:third_party/re2/src/util/logging.h

Also similar to this one, but with an object that has a noreturn destructor instead of inline assembly that causes a trap:

https://source.chromium.org/chromium/chromium/src/+/main:base/check.h

If it wasn't for this "curious" coding pattern that is stamped into many function thanks to the macro, we wouldn't be bothering with this pattern matching at this point.

I see. This makes sense as a temporary workaround, but in the long term I'd love to see a more general solution. I'm ok with this as is, but I'd love to see more tests that (possibly) does not provide the expected results along some TODOs and some comments about the specific coding patterns this is targeting.

[sgatev]

Address reviewers' comments.

[sgatev]

I also agree that the current approach isn't robust. I think that a proper solution would involve patching the CFG because in some cases it seems to be incorrect. For example, the call to qux is incorrectly deemed to be unreachable in the CFG of the following code:

int foo();

class Fatal {
 public:
  ~Fatal() __attribute__((noreturn));
  int bar();
  int baz();
};

void qux();

void target(bool b1, bool b2) {
  int value = b1 ? foo() : (b2 ? Fatal().bar() : Fatal().baz());
  qux();
}

I'd be happy to look into a solution for this as a follow up. I guess it would have an impact on other users of the CFG too.

clang/include/clang/Analysis/FlowSensitive/ControlFlowContext.h

51

The main reason for me not to use CFGStmtMap right away is that based on some tests it seems to behave differently compared to what's implemented here. I plan to look into that in detail and see if there's an opportunity to replace the logic here. It shouldn't be too difficult to do that in a follow up as getStmtToBlock is used in a single place.

clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h

103

Replaced Ctx with CFCtx across the patch.

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

51

I updated the comment and added more tests. Hopefully, that would be good enough for now and we can replace all of this with a more principled solution shortly.

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

47

Much better. Thanks!

[sgatev]

Change commit message.

[xazax.hun]

Thanks!

[gribozavr2]

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

193

DYM "Noreturn" instead of "Virtual"?

[sgatev]

Rename a test.

[sgatev]

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

193

Right. Renamed it.

[sgatev]

Thanks for the reviews!

clang/include/clang/Analysis/FlowSensitive/ControlFlowContext.h

+//===-- ControlFlowContext.h ------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defines a ControlFlowContext class that is used by dataflow
+//  analyses that run over Control-Flow Graphs (CFGs).
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_CONTROLFLOWCONTEXT_H
+#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_CONTROLFLOWCONTEXT_H
+
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/Decl.h"
+#include "clang/AST/Stmt.h"
+#include "clang/Analysis/CFG.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/Support/Error.h"
+#include <memory>
+
+namespace clang {
+namespace dataflow {
+
+/// Holds CFG and other derived context that is needed to perform dataflow
+/// analysis.
+class ControlFlowContext {
+public:
+  /// Builds a ControlFlowContext from an AST node.
+  static llvm::Expected<ControlFlowContext> build(const Decl *D, Stmt *S,
+                                                  ASTContext *C);
+
+  /// Returns the CFG that is stored in this context.
+  const CFG &getCFG() const { return *Cfg; }
+
+  /// Returns the mapping from statements to basic blocks that is stored in this
+  /// context.
+  const llvm::DenseMap<const Stmt *, const CFGBlock *> &getStmtToBlock() const {
+    return StmtToBlock;
+  }
+
+private:
+  ControlFlowContext(std::unique_ptr<CFG> Cfg,
+                     llvm::DenseMap<const Stmt *, const CFGBlock *> StmtToBlock)
+      : Cfg(std::move(Cfg)), StmtToBlock(std::move(StmtToBlock)) {}
+
+  std::unique_ptr<CFG> Cfg;
+  llvm::DenseMap<const Stmt *, const CFGBlock *> StmtToBlock;
+};
+
+} // namespace dataflow
+} // namespace clang
+
+#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_CONTROLFLOWCONTEXT_H

clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h

 
 #include <iterator>
 #include <utility>
 #include <vector>
 
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/Stmt.h"
 #include "clang/Analysis/CFG.h"
+#include "clang/Analysis/FlowSensitive/ControlFlowContext.h"
 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
 #include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h"
 #include "llvm/ADT/Any.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
 
 namespace clang {
 namespace dataflow {
template <typename LatticeT> struct DataflowAnalysisState {
 
   // Model of the state of the program (store and heap).
   Environment Env;
 };
 
 /// Performs dataflow analysis and returns a mapping from basic block IDs to
 /// dataflow analysis states that model the respective basic blocks. Indices
 /// of the returned vector correspond to basic block IDs.
-///
-/// Requirements:
-///
-///  `Cfg` must have been built with `CFG::BuildOptions::setAllAlwaysAdd()` to
-///  ensure that all sub-expressions in a basic block are evaluated.
 template <typename AnalysisT>
 std::vector<llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>
-runDataflowAnalysis(const CFG &Cfg, AnalysisT &Analysis,
+runDataflowAnalysis(const ControlFlowContext &Ctx, AnalysisT &Analysis,
                     const Environment &InitEnv) {
   auto TypeErasedBlockStates =
-      runTypeErasedDataflowAnalysis(Cfg, Analysis, InitEnv);
+      runTypeErasedDataflowAnalysis(Ctx, Analysis, InitEnv);
   std::vector<
       llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>
       BlockStates;
   BlockStates.reserve(TypeErasedBlockStates.size());
   llvm::transform(std::move(TypeErasedBlockStates),
                   std::back_inserter(BlockStates), [](auto &OptState) {
                     return std::move(OptState).map([](auto &&State) {
                       return DataflowAnalysisState<typename AnalysisT::Lattice>{

clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h

 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TYPEERASEDDATAFLOWANALYSIS_H
 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TYPEERASEDDATAFLOWANALYSIS_H
 
 #include <vector>
 
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/Stmt.h"
 #include "clang/Analysis/CFG.h"
+#include "clang/Analysis/FlowSensitive/ControlFlowContext.h"
 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
 #include "clang/Analysis/FlowSensitive/DataflowLattice.h"
 #include "llvm/ADT/Any.h"
 #include "llvm/ADT/Optional.h"
 
 namespace clang {
 namespace dataflow {
 

 /// applied to each statement in the block, after it is evaluated.
 ///
 /// Requirements:
 ///
 ///   All predecessors of `Block` except those with loop back edges must have
 ///   already been transferred. States in `BlockStates` that are set to
 ///   `llvm::None` represent basic blocks that are not evaluated yet.
 TypeErasedDataflowAnalysisState transferBlock(
+    const ControlFlowContext &Ctx,
     std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>> &BlockStates,
     const CFGBlock &Block, const Environment &InitEnv,
     TypeErasedDataflowAnalysis &Analysis,
     std::function<void(const CFGStmt &,
                        const TypeErasedDataflowAnalysisState &)>
         HandleTransferredStmt = nullptr);
 
 /// Performs dataflow analysis and returns a mapping from basic block IDs to
 /// dataflow analysis states that model the respective basic blocks. Indices
 /// of the returned vector correspond to basic block IDs.
-///
-/// Requirements:
-///
-///  `Cfg` must have been built with `CFG::BuildOptions::setAllAlwaysAdd()` to
-///  ensure that all sub-expressions in a basic block are evaluated.
 std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>>
-runTypeErasedDataflowAnalysis(const CFG &Cfg,
+runTypeErasedDataflowAnalysis(const ControlFlowContext &Ctx,
                               TypeErasedDataflowAnalysis &Analysis,
                               const Environment &InitEnv);
 
 } // namespace dataflow
 } // namespace clang
 
 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TYPEERASEDDATAFLOWANALYSIS_H

clang/lib/Analysis/FlowSensitive/CMakeLists.txt

 add_clang_library(clangAnalysisFlowSensitive
+  ControlFlowContext.cpp
   TypeErasedDataflowAnalysis.cpp
 
   LINK_LIBS
   clangAnalysis
   clangAST
   )

clang/lib/Analysis/FlowSensitive/ControlFlowContext.cpp

+#include "clang/Analysis/FlowSensitive/ControlFlowContext.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/Decl.h"
+#include "clang/AST/Stmt.h"
+#include "clang/Analysis/CFG.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/Support/Error.h"
+#include <utility>
+
+namespace clang {
+namespace dataflow {
+namespace {
+
+/// Returns a map from statements to basic blocks that contain them.
+llvm::DenseMap<const Stmt *, const CFGBlock *>
+buildStmtToBasicBlockMap(const CFG &Cfg) {
+  llvm::DenseMap<const Stmt *, const CFGBlock *> StmtToBlock;
+  for (const CFGBlock *Block : Cfg) {
+    if (Block == nullptr)
+      continue;
+
+    for (const CFGElement &Element : *Block) {
+      auto Stmt = Element.getAs<CFGStmt>();
+      if (!Stmt.hasValue())
+        continue;
+
+      StmtToBlock[Stmt.getValue().getStmt()] = Block;
+    }
+  }
+  return StmtToBlock;
+}
+
+} // namespace
+
+llvm::Expected<ControlFlowContext>
+ControlFlowContext::build(const Decl *D, Stmt *S, ASTContext *C) {
+  CFG::BuildOptions Options;
+  Options.PruneTriviallyFalseEdges = false;
+  Options.AddImplicitDtors = true;
+  Options.AddTemporaryDtors = true;
+  Options.AddInitializers = true;
+
+  // `Cfg` must be built with `CFG::BuildOptions::setAllAlwaysAdd()` to
+  // ensure that all sub-expressions in a basic block are evaluated.
+  Options.setAllAlwaysAdd();
+
+  auto Cfg = CFG::buildCFG(D, S, C, Options);
+  if (Cfg == nullptr)
+    return llvm::createStringError(
+        std::make_error_code(std::errc::invalid_argument),
+        "CFG::buildCFG failed");
+
+  llvm::DenseMap<const Stmt *, const CFGBlock *> StmtToBlock =
+      buildStmtToBasicBlockMap(*Cfg);
+  return ControlFlowContext(std::move(Cfg), std::move(StmtToBlock));
+}
+
+} // namespace dataflow
+} // namespace clang

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

 /// states of its predecessors.
 ///
 /// Requirements:
 ///
 ///   All predecessors of `Block` except those with loop back edges must have
 ///   already been transferred. States in `BlockStates` that are set to
 ///   `llvm::None` represent basic blocks that are not evaluated yet.
 static TypeErasedDataflowAnalysisState computeBlockInputState(
+    const ControlFlowContext &Ctx,
     std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>> &BlockStates,
     const CFGBlock &Block, const Environment &InitEnv,
     TypeErasedDataflowAnalysis &Analysis) {
   // FIXME: Consider passing `Block` to `Analysis.typeErasedInitialElement()`
   // to enable building analyses like computation of dominators that initialize
   // the state of each basic block differently.
   TypeErasedDataflowAnalysisState State = {Analysis.typeErasedInitialElement(),
                                            InitEnv};
-  for (const CFGBlock *Pred : Block.preds()) {
+
+  llvm::DenseSet<const CFGBlock *> Preds;
+  Preds.insert(Block.pred_begin(), Block.pred_end());
+  if (Block.getTerminator().isTemporaryDtorsBranch()) {
+    // The first successor of a block with a temporary destructor terminator is
+    // the block that evaluates the destructor. If that block has a noreturn
+    // element then the predecessor block that constructed the temporary object
+    // is effectively a noreturn block and its state should not be used as
+    // input.
+    if (Block.succ_begin()->getReachableBlock()->hasNoReturnElement()) {
+      auto StmtBlock = Ctx.getStmtToBlock().find(Block.getTerminatorStmt());
+      assert(StmtBlock != Ctx.getStmtToBlock().end());
+      Preds.erase(StmtBlock->getSecond());
+    }
+  }
+
+  for (const CFGBlock *Pred : Preds) {
     // Skip if the `Block` is unreachable or control flow cannot get past it.
     if (!Pred || Pred->hasNoReturnElement())
       continue;
 
     // Skip if `Pred` was not evaluated yet. This could happen if `Pred` has a
     // loop back edge to `Block`.
     const llvm::Optional<TypeErasedDataflowAnalysisState> &MaybePredState =
         BlockStates[Pred->getBlockID()];
     if (!MaybePredState.hasValue())
       continue;
 
     const TypeErasedDataflowAnalysisState &PredState =
         MaybePredState.getValue();
     Analysis.joinTypeErased(State.Lattice, PredState.Lattice);
     State.Env.join(PredState.Env);
   }
   return State;
 }
 
 TypeErasedDataflowAnalysisState transferBlock(
+    const ControlFlowContext &Ctx,
     std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>> &BlockStates,
     const CFGBlock &Block, const Environment &InitEnv,
     TypeErasedDataflowAnalysis &Analysis,
     std::function<void(const CFGStmt &,
                        const TypeErasedDataflowAnalysisState &)>
         HandleTransferredStmt) {
   TypeErasedDataflowAnalysisState State =
-      computeBlockInputState(BlockStates, Block, InitEnv, Analysis);
+      computeBlockInputState(Ctx, BlockStates, Block, InitEnv, Analysis);
   for (const CFGElement &Element : Block) {
     // FIXME: Evaluate other kinds of `CFGElement`.
     const llvm::Optional<CFGStmt> Stmt = Element.getAs<CFGStmt>();
     if (!Stmt.hasValue())
       continue;
 
     // FIXME: Evaluate the statement contained in `Stmt`.
 
     State.Lattice = Analysis.transferTypeErased(Stmt.getValue().getStmt(),
                                                 State.Lattice, State.Env);
     if (HandleTransferredStmt != nullptr)
       HandleTransferredStmt(Stmt.getValue(), State);
   }
   return State;
 }
 
 std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>>
-runTypeErasedDataflowAnalysis(const CFG &Cfg,
+runTypeErasedDataflowAnalysis(const ControlFlowContext &Ctx,
                               TypeErasedDataflowAnalysis &Analysis,
                               const Environment &InitEnv) {
   // FIXME: Consider enforcing that `Cfg` meets the requirements that
   // are specified in the header. This could be done by remembering
   // what options were used to build `Cfg` and asserting on them here.
 
-  PostOrderCFGView POV(&Cfg);
-  ForwardDataflowWorklist Worklist(Cfg, &POV);
+  PostOrderCFGView POV(&Ctx.getCFG());
+  ForwardDataflowWorklist Worklist(Ctx.getCFG(), &POV);
 
   std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>> BlockStates;
-  BlockStates.resize(Cfg.size(), llvm::None);
+  BlockStates.resize(Ctx.getCFG().size(), llvm::None);
 
   // The entry basic block doesn't contain statements so it can be skipped.
-  const CFGBlock &Entry = Cfg.getEntry();
+  const CFGBlock &Entry = Ctx.getCFG().getEntry();
   BlockStates[Entry.getBlockID()] = {Analysis.typeErasedInitialElement(),
                                      InitEnv};
   Worklist.enqueueSuccessors(&Entry);
 
   // Bugs in lattices and transfer functions can prevent the analysis from
   // converging. To limit the damage (infinite loops) that these bugs can cause,
   // limit the number of iterations.
   // FIXME: Consider making the maximum number of iterations configurable.
   // FIXME: Set up statistics (see llvm/ADT/Statistic.h) to count average number
   // of iterations, number of functions that time out, etc.
   unsigned Iterations = 0;
   static constexpr unsigned MaxIterations = 1 << 16;
   while (const CFGBlock *Block = Worklist.dequeue()) {
     if (++Iterations > MaxIterations) {
       llvm::errs() << "Maximum number of iterations reached, giving up.\n";
       break;
     }
 
     const llvm::Optional<TypeErasedDataflowAnalysisState> &OldBlockState =
         BlockStates[Block->getBlockID()];
     TypeErasedDataflowAnalysisState NewBlockState =
-        transferBlock(BlockStates, *Block, InitEnv, Analysis);
+        transferBlock(Ctx, BlockStates, *Block, InitEnv, Analysis);
 
     if (OldBlockState.hasValue() &&
         Analysis.isEqualTypeErased(OldBlockState.getValue().Lattice,
                                    NewBlockState.Lattice) &&
         OldBlockState->Env == NewBlockState.Env) {
       // The state of `Block` didn't change after transfer so there's no need to
       // revisit its successors.
       continue;

clang/unittests/Analysis/FlowSensitive/TestingSupport.h

 
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/Stmt.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
 #include "clang/ASTMatchers/ASTMatchers.h"
 #include "clang/ASTMatchers/ASTMatchersInternal.h"
 #include "clang/Analysis/CFG.h"
+#include "clang/Analysis/FlowSensitive/ControlFlowContext.h"
 #include "clang/Analysis/FlowSensitive/DataflowAnalysis.h"
 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
 #include "clang/Basic/LLVM.h"
 #include "clang/Tooling/Tooling.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"

 namespace test {
 
 // Returns assertions based on annotations that are present after statements in
 // `AnnotatedCode`.
 llvm::Expected<llvm::DenseMap<const Stmt *, std::string>>
 buildStatementToAnnotationMapping(const FunctionDecl *Func,
                                   llvm::Annotations AnnotatedCode);
 
-// Creates a CFG from the body of the function that matches `func_matcher`,
-// suitable to testing a dataflow analysis.
-std::pair<const FunctionDecl *, std::unique_ptr<CFG>>
-buildCFG(ASTContext &Context,
-         ast_matchers::internal::Matcher<FunctionDecl> FuncMatcher);
-
 // Runs dataflow on the body of the function that matches `func_matcher` in code
 // snippet `code`. Requires: `Analysis` contains a type `Lattice`.
 template <typename AnalysisT>
 void checkDataflow(
     llvm::StringRef Code,
     ast_matchers::internal::Matcher<FunctionDecl> FuncMatcher,
     std::function<AnalysisT(ASTContext &, Environment &)> MakeAnalysis,
     std::function<void(
void checkDataflow(
   auto Unit = tooling::buildASTFromCodeWithArgs(AnnotatedCode.code(), Args);
   auto &Context = Unit->getASTContext();
 
   if (Context.getDiagnostics().getClient()->getNumErrors() != 0) {
     FAIL() << "Source file has syntax or type errors, they were printed to "
               "the test log";
   }
 
-  std::pair<const FunctionDecl *, std::unique_ptr<CFG>> CFGResult =
-      buildCFG(Context, FuncMatcher);
-  const auto *F = CFGResult.first;
-  auto Cfg = std::move(CFGResult.second);
-  ASSERT_TRUE(F != nullptr) << "Could not find target function";
-  ASSERT_TRUE(Cfg != nullptr) << "Could not build control flow graph.";
+  const FunctionDecl *F = ast_matchers::selectFirst<FunctionDecl>(
+      "target",
+      ast_matchers::match(
+          ast_matchers::functionDecl(ast_matchers::isDefinition(), FuncMatcher)
+              .bind("target"),
+          Context));
+  ASSERT_TRUE(F != nullptr) << "Could not find target function.";
+
+  auto Ctx = ControlFlowContext::build(F, F->getBody(), &F->getASTContext());
+  ASSERT_TRUE((bool)Ctx) << "Could not build ControlFlowContext.";
 
   Environment Env;
   auto Analysis = MakeAnalysis(Context, Env);
 
   llvm::Expected<llvm::DenseMap<const clang::Stmt *, std::string>>
       StmtToAnnotations = buildStatementToAnnotationMapping(F, AnnotatedCode);
   if (auto E = StmtToAnnotations.takeError()) {
     FAIL() << "Failed to build annotation map: "
            << llvm::toString(std::move(E));
     return;
   }
   auto &Annotations = *StmtToAnnotations;
 
   std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>> BlockStates =
-      runTypeErasedDataflowAnalysis(*Cfg, Analysis, Env);
+      runTypeErasedDataflowAnalysis(*Ctx, Analysis, Env);
 
   if (BlockStates.empty()) {
     Expectations({}, Context);
     return;
   }
 
   // Compute a map from statement annotations to the state computed for
   // the program point immediately after the annotated statement.
   std::vector<std::pair<std::string, StateT>> Results;
-  for (const CFGBlock *Block : *Cfg) {
+  for (const CFGBlock *Block : Ctx->getCFG()) {
     // Skip blocks that were not evaluated.
     if (!BlockStates[Block->getBlockID()].hasValue())
       continue;
 
     transferBlock(
-        BlockStates, *Block, Env, Analysis,
+        *Ctx, BlockStates, *Block, Env, Analysis,
         [&Results, &Annotations](const clang::CFGStmt &Stmt,
                                  const TypeErasedDataflowAnalysisState &State) {
           auto It = Annotations.find(Stmt.getStmt());
           if (It == Annotations.end())
             return;
           if (auto *Lattice = llvm::any_cast<typename AnalysisT::Lattice>(
                   &State.Lattice.Value)) {
             Results.emplace_back(It->second, StateT{*Lattice, State.Env});

clang/unittests/Analysis/FlowSensitive/TestingSupport.cpp

return llvm::createStringError(
         SourceManager.getLocForStartOfFile(SourceManager.getMainFileID())
             .getLocWithOffset(Annotations[I].Begin)
             .printToString(SourceManager)
             .data());
   }
 
   return Result;
 }
-
-std::pair<const FunctionDecl *, std::unique_ptr<CFG>>
-test::buildCFG(ASTContext &Context,
-               ast_matchers::internal::Matcher<FunctionDecl> FuncMatcher) {
-  CFG::BuildOptions Options;
-  Options.PruneTriviallyFalseEdges = false;
-  Options.AddInitializers = true;
-  Options.AddImplicitDtors = true;
-  Options.AddTemporaryDtors = true;
-  Options.setAllAlwaysAdd();
-
-  const FunctionDecl *F = ast_matchers::selectFirst<FunctionDecl>(
-      "target",
-      ast_matchers::match(
-          ast_matchers::functionDecl(ast_matchers::isDefinition(), FuncMatcher)
-              .bind("target"),
-          Context));
-  if (F == nullptr)
-    return std::make_pair(nullptr, nullptr);
-
-  return std::make_pair(
-      F, clang::CFG::buildCFG(F, F->getBody(), &Context, Options));
-}

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

 //===- unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp ===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
+#include "TestingSupport.h"
 #include "clang/AST/Decl.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
 #include "clang/ASTMatchers/ASTMatchers.h"
 #include "clang/Analysis/CFG.h"
 #include "clang/Analysis/FlowSensitive/DataflowAnalysis.h"
 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
 #include "clang/Analysis/FlowSensitive/DataflowLattice.h"
 #include "clang/Tooling/Tooling.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/StringRef.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 #include <cassert>
 #include <memory>
+#include <ostream>
+#include <string>
 #include <vector>
 
 using namespace clang;
 using namespace dataflow;
+using ::testing::Pair;
+using ::testing::UnorderedElementsAre;
 
 template <typename AnalysisT>
 class AnalysisCallback : public ast_matchers::MatchFinder::MatchCallback {
 public:
   void run(const ast_matchers::MatchFinder::MatchResult &Result) override {
     assert(BlockStates.empty());
 
     const auto *Func = Result.Nodes.getNodeAs<FunctionDecl>("func");
     assert(Func != nullptr);
 
     Stmt *Body = Func->getBody();
     assert(Body != nullptr);
 
-    // FIXME: Consider providing a utility that returns a `CFG::BuildOptions`
-    // which is a good default for most clients or a utility that directly
-    // builds the `CFG` using default `CFG::BuildOptions`.
-    CFG::BuildOptions Options;
-    Options.AddImplicitDtors = true;
-    Options.AddTemporaryDtors = true;
-    Options.setAllAlwaysAdd();
-
-    std::unique_ptr<CFG> Cfg =
-        CFG::buildCFG(nullptr, Body, Result.Context, Options);
-    assert(Cfg != nullptr);
+    auto Ctx = ControlFlowContext::build(nullptr, Body, Result.Context);
+    assert(Ctx);
 
     AnalysisT Analysis(*Result.Context);
     Environment Env;
-    BlockStates = runDataflowAnalysis(*Cfg, Analysis, Env);
+    BlockStates = runDataflowAnalysis(*Ctx, Analysis, Env);
   }
 
   std::vector<
       llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>
       BlockStates;
 };
 
 template <typename AnalysisT>

 
 TEST(DataflowAnalysisTest, NonConvergingAnalysis) {
   auto BlockStates = runAnalysis<NonConvergingAnalysis>(R"(
     void target() {
       while(true) {}
     }
   )");
   EXPECT_EQ(BlockStates.size(), 4u);
-  EXPECT_FALSE(BlockStates[0].hasValue());
+  EXPECT_TRUE(BlockStates[0].hasValue());
   EXPECT_TRUE(BlockStates[1].hasValue());
   EXPECT_TRUE(BlockStates[2].hasValue());
   EXPECT_TRUE(BlockStates[3].hasValue());
 }
+
+struct FunctionCallLattice {
+  llvm::SmallSet<std::string, 8> CalledFunctions;
+
+  bool operator==(const FunctionCallLattice &Other) const {
+    return CalledFunctions == Other.CalledFunctions;
+  }
+
+  LatticeJoinEffect join(const FunctionCallLattice &Other) {
+    if (Other.CalledFunctions.empty())
+      return LatticeJoinEffect::Unchanged;
+    const size_t size_before = CalledFunctions.size();
+    CalledFunctions.insert(Other.CalledFunctions.begin(),
+                           Other.CalledFunctions.end());
+    return CalledFunctions.size() == size_before ? LatticeJoinEffect::Unchanged
+                                                 : LatticeJoinEffect::Changed;
+  }
+};
+
+std::ostream &operator<<(std::ostream &OS, const FunctionCallLattice &L) {
+  std::string result;
+  llvm::raw_string_ostream ROS(result);
+  llvm::interleaveComma(L.CalledFunctions, ROS);
+  return OS << "{" << result << "}";
+}
+
+class FunctionCallAnalysis
+    : public DataflowAnalysis<FunctionCallAnalysis, FunctionCallLattice> {
+public:
+  explicit FunctionCallAnalysis(ASTContext &Context)
+      : DataflowAnalysis<FunctionCallAnalysis, FunctionCallLattice>(Context) {}
+
+  static FunctionCallLattice initialElement() { return {}; }
+
+  FunctionCallLattice transfer(const Stmt *S, const FunctionCallLattice &E,
+                               Environment &Env) {
+    FunctionCallLattice R = E;
+    if (auto *C = dyn_cast<CallExpr>(S)) {
+      if (auto *F = dyn_cast<FunctionDecl>(C->getCalleeDecl())) {
+        R.CalledFunctions.insert(F->getNameInfo().getAsString());
+      }
+    }
+    return R;
+  }
+};
+
+class FunctionCallTest : public ::testing::Test {
+protected:
+  template <typename Matcher>
+  void RunDataflow(llvm::StringRef Code, Matcher Expectations) {
+    test::checkDataflow<FunctionCallAnalysis>(
+        Code, "target",
+        [](ASTContext &C, Environment &) { return FunctionCallAnalysis(C); },
+        [&Expectations](
+            llvm::ArrayRef<std::pair<
+                std::string, DataflowAnalysisState<FunctionCallLattice>>>
+                Results,
+            ASTContext &) { EXPECT_THAT(Results, Expectations); },
+        {"-fsyntax-only", "-std=c++17"});
+  }
+};
+
+MATCHER_P(HoldsFunctionCallLattice, m,
+          ((negation ? "doesn't hold" : "holds") +
+           llvm::StringRef(" a lattice element that ") +
+           ::testing::DescribeMatcher<FunctionCallLattice>(m, negation))
+              .str()) {
+  return ExplainMatchResult(m, arg.Lattice, result_listener);
+}
+
+MATCHER_P(HasCalledFunctions, m, "") {
+  return ExplainMatchResult(m, arg.CalledFunctions, result_listener);
+}
+
+TEST_F(FunctionCallTest, VirtualDestructor) {
+  std::string Code = R"(
+    int foo();
+
+    class NonFatal {
+     public:
+      ~NonFatal();
+      int bar();
+    };
+
+    void target(bool b) {
+      int value = b ? foo() : NonFatal().bar();
+      (void)0;
+      // [[p]]
+    }
+  )";
+  RunDataflow(Code, UnorderedElementsAre(
+                        Pair("p", HoldsFunctionCallLattice(HasCalledFunctions(
+                                      UnorderedElementsAre("foo", "bar"))))));
+}
+
+TEST_F(FunctionCallTest, VirtualDestructorNoReturn) {
+  std::string Code = R"(
+    int foo();
+
+    class Fatal {
+     public:
+      ~Fatal() __attribute__((noreturn));
+      int bar();
+    };
+
+    void target(bool b) {
+      int value = b ? foo() : Fatal().bar();
+      (void)0;
+      // [[p]]
+    }
+  )";
+  RunDataflow(Code, UnorderedElementsAre(
+                        Pair("p", HoldsFunctionCallLattice(HasCalledFunctions(
+                                      UnorderedElementsAre("foo"))))));
+}