[clang][dataflow] Fix crash when RHS of `&&` or `||` calls `noreturn` func.

[mboehme]

Summary

The crash happened because the transfer fucntion for && and ||
unconditionally tried to retrieve the value of the RHS. However, if the RHS
is unreachable, there is no environment for it, and trying to retrieve the
operand's value causes an assertion failure.

See also the comments in the code for further details.

[gribozavr2]

clang/unittests/Analysis/FlowSensitive/TestingSupport.h

399

getValueForDecl?

A value corresponds to a decl, a value for the decl.

"From" suggests that the value is inside the decl, or that we transform the decl into a value.

[sgatev]

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

52

What do you think about making this a const reference? Alternatively, let's document that it must not be null?

[mboehme]

Changes in response to review comments.

[mboehme]

clang/unittests/Analysis/FlowSensitive/TestingSupport.h

399

Good point -- done!

[mboehme]

Changes in response to review comments.

[mboehme]

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

52

Good point -- done!

[ymandel]

Nice! Thank you.

clang/lib/Analysis/FlowSensitive/Transfer.cpp

174–175

nit. reworded (using A => B => C is the same as A & B => C). but, your call.

[xazax.hun]

This fix looks good for me for this particular problem, but I wonder whether the solution is general enough. In case the analysis figures out that a call would not return (e.g., the value method is called on a provably empty optional, and it would throw instead of returning), would this approach still work? Would the analysis update the BlockReachable bitvector on demand?

[mboehme]

In D146514#4209931, @xazax.hun wrote:

This fix looks good for me for this particular problem, but I wonder whether the solution is general enough. In case the analysis figures out that a call would not return (e.g., the value method is called on a provably empty optional, and it would throw instead of returning), would this approach still work? Would the analysis update the BlockReachable bitvector on demand?

No, I think this is a different case.

BlockReachable is intended to encode reachability solely as defined by the structure of the CFG. The whole problem we're trying to solve in this patch is that the CFG understands that noreturn functions don't return and therefore eliminates any successor edges from calls to noreturn functions. This means that some of the CFG nodes become unreachable; specifically, in our case, the RHS of the && and || become unreachable, and so the dataflow analysis never computes a value for them. We therefore need to make sure that we don't try to query the value of the RHS in this case.

The case of calling value on a provably empty optional is different: The CFG does not understand that such a call does not return and therefore generates successor edges as it would for any other function call.

A side effect of the logic that this patch adds is that we get some neat inference results, as demonstrated in the newly added test. However, generating these results isn't the main goal of this patch; the patch is merely intended to ensure that we can process CFGs containing unreachable nodes caused by noreturn functions.

It would certainly be nice to generate similar inference results in the example that you mention (value on a provably empty optional), but that would require more work and a different approach.

[mboehme]

Reworded comment.

[mboehme]

Reworded comment again.

[mboehme]

clang/lib/Analysis/FlowSensitive/Transfer.cpp

174–175

Thanks, this is easier to understand. Done!

[xazax.hun]

In D146514#4212528, @mboehme wrote:

No, I think this is a different case.

Sorry, I might have been unclear. I 100% agree that these are different cases. I was wondering whether we can/should have a single code path supporting both. But I do not insist since we do not seem to have precedent for the scenario I mentioned and do not want to block anything based on hypotheticals.

[mboehme]

In D146514#4213302, @xazax.hun wrote:

In D146514#4212528, @mboehme wrote:

No, I think this is a different case.

Sorry, I might have been unclear. I 100% agree that these are different cases. I was wondering whether we can/should have a single code path supporting both. But I do not insist since we do not seem to have precedent for the scenario I mentioned and do not want to block anything based on hypotheticals.

Got it, thanks!

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

 
 #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/BitVector.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/Support/Error.h"
 #include <memory>
 #include <utility>
 
 namespace clang {
 namespace dataflow {
 
public:
   /// Returns the CFG that is stored in this context.
   const CFG &getCFG() const { return *Cfg; }
 
   /// Returns a mapping from statements to basic blocks that contain them.
   const llvm::DenseMap<const Stmt *, const CFGBlock *> &getStmtToBlock() const {
     return StmtToBlock;
   }
 
+  /// Returns whether `B` is reachable from the entry block.
+  bool isBlockReachable(const CFGBlock &B) const {
+    return BlockReachable[B.getBlockID()];
+  }
+
 private:
   // FIXME: Once the deprecated `build` method is removed, mark `D` as "must not
   // be null" and add an assertion.
   ControlFlowContext(const Decl *D, std::unique_ptr<CFG> Cfg,
-                     llvm::DenseMap<const Stmt *, const CFGBlock *> StmtToBlock)
+                     llvm::DenseMap<const Stmt *, const CFGBlock *> StmtToBlock,
+                     llvm::BitVector BlockReachable)
       : ContainingDecl(D), Cfg(std::move(Cfg)),
-        StmtToBlock(std::move(StmtToBlock)) {}
+        StmtToBlock(std::move(StmtToBlock)),
+        BlockReachable(std::move(BlockReachable)) {}
 
   /// The `Decl` containing the statement used to construct the CFG.
   const Decl *ContainingDecl;
   std::unique_ptr<CFG> Cfg;
   llvm::DenseMap<const Stmt *, const CFGBlock *> StmtToBlock;
+  llvm::BitVector BlockReachable;
 };
 
 } // namespace dataflow
 } // namespace clang
 
 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_CONTROLFLOWCONTEXT_H

clang/include/clang/Analysis/FlowSensitive/Transfer.h

 namespace clang {
 namespace dataflow {
 
 /// Maps statements to the environments of basic blocks that contain them.
 class StmtToEnvMap {
 public:
   virtual ~StmtToEnvMap() = default;
 
-  /// Returns the environment of the basic block that contains `S` or nullptr if
-  /// there isn't one.
-  /// FIXME: Ensure that the result can't be null and return a const reference.
+  /// Retrieves the environment of the basic block that contains `S`.
+  /// If `S` is reachable, returns a non-null pointer to the environment.
+  /// If `S` is not reachable, returns nullptr.
   virtual const Environment *getEnvironment(const Stmt &S) const = 0;
 };
 
 /// Evaluates `S` and updates `Env` accordingly.
 ///
 /// Requirements:
 ///
 ///  `S` must not be `ParenExpr` or `ExprWithCleanups`.
 void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env);
 
 } // namespace dataflow
 } // namespace clang
 
 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TRANSFER_H

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/BitVector.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/Support/Error.h"
 #include <utility>
 
 namespace clang {
 namespace dataflow {
 
 /// Returns a map from statements to basic blocks that contain them.
for (const CFGElement &Element : *Block) {
       StmtToBlock[Stmt->getStmt()] = Block;
     }
     if (const Stmt *TerminatorStmt = Block->getTerminatorStmt())
       StmtToBlock[TerminatorStmt] = Block;
   }
   return StmtToBlock;
 }
 
+static llvm::BitVector findReachableBlocks(const CFG &Cfg) {
+  llvm::BitVector BlockReachable(Cfg.getNumBlockIDs(), false);
+
+  llvm::SmallVector<const CFGBlock *> BlocksToVisit;
+  BlocksToVisit.push_back(&Cfg.getEntry());
+  while (!BlocksToVisit.empty()) {
+    const CFGBlock *Block = BlocksToVisit.back();
+    BlocksToVisit.pop_back();
+
+    if (BlockReachable[Block->getBlockID()])
+      continue;
+
+    BlockReachable[Block->getBlockID()] = true;
+
+    for (const CFGBlock *Succ : Block->succs())
+      if (Succ)
+        BlocksToVisit.push_back(Succ);
+  }
+
+  return BlockReachable;
+}
+
 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;
   Options.AddCXXDefaultInitExprInCtors = true;
 
   // Ensure that all sub-expressions in basic blocks 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(D, std::move(Cfg), std::move(StmtToBlock));
+
+  llvm::BitVector BlockReachable = findReachableBlocks(*Cfg);
+
+  return ControlFlowContext(D, std::move(Cfg), std::move(StmtToBlock),
+                            std::move(BlockReachable));
 }
 
 } // namespace dataflow
 } // namespace clang

clang/lib/Analysis/FlowSensitive/Transfer.cpp

case BO_Assign: {
       Env.setValue(*LHSLoc, *RHSVal);
 
       // Assign a storage location for the whole expression.
       Env.setStorageLocation(*S, *LHSLoc);
       break;
     }
     case BO_LAnd:
     case BO_LOr: {
-      BoolValue &LHSVal = getLogicOperatorSubExprValue(*LHS);
-      BoolValue &RHSVal = getLogicOperatorSubExprValue(*RHS);
-
       auto &Loc = Env.createStorageLocation(*S);
       Env.setStorageLocation(*S, Loc);
+
+      BoolValue *LHSVal = getLogicOperatorSubExprValue(*LHS);
+      // If the LHS was not reachable, this BinaryOperator would also not be
+      // reachable, and we would never get here.
+      assert(LHSVal != nullptr);
+      BoolValue *RHSVal = getLogicOperatorSubExprValue(*RHS);
+      if (RHSVal == nullptr) {
+        // If the RHS isn't reachable and we evaluate this BinaryOperator,
+        // then the value of the LHS must have triggered the short-circuit
+        // logic. This implies that the value of the entire expression must be
+        // equal to the value of the LHS.
+        Env.setValue(Loc, *LHSVal);
+        break;
+      }
+
       if (S->getOpcode() == BO_LAnd)
-        Env.setValue(Loc, Env.makeAnd(LHSVal, RHSVal));
+        Env.setValue(Loc, Env.makeAnd(*LHSVal, *RHSVal));
       else
-        Env.setValue(Loc, Env.makeOr(LHSVal, RHSVal));
+        Env.setValue(Loc, Env.makeOr(*LHSVal, *RHSVal));
       break;
     }
     case BO_NE:
     case BO_EQ: {
       auto &LHSEqRHSValue = evaluateBooleanEquality(*LHS, *RHS, Env);
       auto &Loc = Env.createStorageLocation(*S);
       Env.setStorageLocation(*S, Loc);
       Env.setValue(Loc, S->getOpcode() == BO_EQ ? LHSEqRHSValue
void VisitExprWithCleanups(const ExprWithCleanups *S) {
     // basic blocks, however manual traversal to sub-expressions may encounter
     // them. Redirect to the sub-expression.
     auto *SubExpr = S->getSubExpr();
     assert(SubExpr != nullptr);
     Visit(SubExpr);
   }
 
 private:
-  BoolValue &getLogicOperatorSubExprValue(const Expr &SubExpr) {
+  /// If `SubExpr` is reachable, returns a non-null pointer to the value for
+  /// `SubExpr`. If `SubExpr` is not reachable, returns nullptr.
+  BoolValue *getLogicOperatorSubExprValue(const Expr &SubExpr) {
     // `SubExpr` and its parent logic operator might be part of different basic
     // blocks. We try to access the value that is assigned to `SubExpr` in the
     // corresponding environment.
-    if (const Environment *SubExprEnv = StmtToEnv.getEnvironment(SubExpr)) {
-      if (auto *Val = dyn_cast_or_null<BoolValue>(
-              SubExprEnv->getValue(SubExpr, SkipPast::Reference)))
-        return *Val;
-    }
+    const Environment *SubExprEnv = StmtToEnv.getEnvironment(SubExpr);
+    if (!SubExprEnv)
+      return nullptr;
+
+      return Val;
 
     if (Env.getStorageLocation(SubExpr, SkipPast::None) == nullptr) {
       // Sub-expressions that are logic operators are not added in basic blocks
       // (e.g. see CFG for `bool d = a && (b || c);`). If `SubExpr` is a logic
       // operator, it may not have been evaluated and assigned a value yet. In
       // that case, we need to first visit `SubExpr` and then try to get the
       // value that gets assigned to it.
       Visit(&SubExpr);
     }
 
     if (auto *Val = dyn_cast_or_null<BoolValue>(
             Env.getValue(SubExpr, SkipPast::Reference)))
-      return *Val;
+      return Val;
 
     // If the value of `SubExpr` is still unknown, we create a fresh symbolic
     // boolean value for it.
-    return Env.makeAtomicBoolValue();
+    return &Env.makeAtomicBoolValue();
   }
 
   // If context sensitivity is enabled, try to analyze the body of the callee
   // `F` of `S`. The type `E` must be either `CallExpr` or `CXXConstructExpr`.
   template <typename E>
   void transferInlineCall(const E *S, const FunctionDecl *F) {
     const auto &Options = Env.getAnalysisOptions();
     if (!(Options.ContextSensitiveOpts &&

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

StmtToEnvMapImpl(
       const ControlFlowContext &CFCtx,
       llvm::ArrayRef<std::optional<TypeErasedDataflowAnalysisState>>
           BlockToState)
       : CFCtx(CFCtx), BlockToState(BlockToState) {}
 
   const Environment *getEnvironment(const Stmt &S) const override {
     auto BlockIt = CFCtx.getStmtToBlock().find(&ignoreCFGOmittedNodes(S));
     assert(BlockIt != CFCtx.getStmtToBlock().end());
+    if (!CFCtx.isBlockReachable(*BlockIt->getSecond()))
+      return nullptr;
     const auto &State = BlockToState[BlockIt->getSecond()->getBlockID()];
     assert(State);
     return &State->Env;
   }
 
 private:
   const ControlFlowContext &CFCtx;
   llvm::ArrayRef<std::optional<TypeErasedDataflowAnalysisState>> BlockToState;

clang/unittests/Analysis/FlowSensitive/TestingSupport.h

 
 /// Returns the `ValueDecl` for the given identifier.
 ///
 /// Requirements:
 ///
 ///   `Name` must be unique in `ASTCtx`.
 const ValueDecl *findValueDecl(ASTContext &ASTCtx, llvm::StringRef Name);
 
+/// Returns the value (of type `ValueT`) for the given identifier.
+/// `ValueT` must be a subclass of `Value` and must be of the appropriate type.
+///
+/// Requirements:
+///
+///   `Name` must be unique in `ASTCtx`.
+template <class ValueT>
+ValueT &getValueForDecl(ASTContext &ASTCtx, const Environment &Env,
+                        llvm::StringRef Name) {
+  const ValueDecl *VD = findValueDecl(ASTCtx, Name);
+  assert(VD != nullptr);
+  return *cast<ValueT>(Env.getValue(*VD, SkipPast::None));
+}
+
 /// Creates and owns constraints which are boolean values.
 class ConstraintContext {
 public:
   // Creates an atomic boolean value.
   BoolValue *atom() {
     Vals.push_back(std::make_unique<AtomicBoolValue>());
     return Vals.back().get();
   }

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

runDataflow(
       Code,
       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
          ASTContext &ASTCtx) {
         // This doesn't need a body because this test was crashing the framework
         // before handling correctly Unnamed bitfields in `InitListExpr`.
       });
 }
 
+// Repro for a crash that used to occur when we call a `noreturn` function
+// within one of the operands of a `&&` or `||` operator.
+TEST(TransferTest, NoReturnFunctionInsideShortCircuitedBooleanOp) {
+  std::string Code = R"(
+    __attribute__((noreturn)) int doesnt_return();
+    bool some_condition();
+    void target(bool b1, bool b2) {
+      // Neither of these should crash. In addition, if we don't terminate the
+      // program, we know that the operators need to trigger the short-circuit
+      // logic, so `NoreturnOnRhsOfAnd` will be false and `NoreturnOnRhsOfOr`
+      // will be true.
+      bool NoreturnOnRhsOfAnd = b1 && doesnt_return() > 0;
+      bool NoreturnOnRhsOfOr = b2 || doesnt_return() > 0;
+
+      // Calling a `noreturn` function on the LHS of an `&&` or `||` makes the
+      // entire expression unreachable. So we know that in both of the following
+      // cases, if `target()` terminates, the `else` branch was taken.
+      bool NoreturnOnLhsMakesAndUnreachable = false;
+      if (some_condition())
+         doesnt_return() > 0 && some_condition();
+      else
+         NoreturnOnLhsMakesAndUnreachable = true;
+
+      bool NoreturnOnLhsMakesOrUnreachable = false;
+      if (some_condition())
+         doesnt_return() > 0 || some_condition();
+      else
+         NoreturnOnLhsMakesOrUnreachable = true;
+
+      // [[p]]
+    }
+  )";
+  runDataflow(
+      Code,
+      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
+         ASTContext &ASTCtx) {
+        ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
+        const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
+
+        // Check that [[p]] is reachable with a non-false flow condition.
+        EXPECT_FALSE(Env.flowConditionImplies(Env.getBoolLiteralValue(false)));
+
+        auto &B1 = getValueForDecl<BoolValue>(ASTCtx, Env, "b1");
+        EXPECT_TRUE(Env.flowConditionImplies(Env.makeNot(B1)));
+
+        auto &NoreturnOnRhsOfAnd =
+            getValueForDecl<BoolValue>(ASTCtx, Env, "NoreturnOnRhsOfAnd");
+        EXPECT_TRUE(Env.flowConditionImplies(Env.makeNot(NoreturnOnRhsOfAnd)));
+
+        auto &B2 = getValueForDecl<BoolValue>(ASTCtx, Env, "b2");
+        EXPECT_TRUE(Env.flowConditionImplies(B2));
+
+        auto &NoreturnOnRhsOfOr =
+            getValueForDecl<BoolValue>(ASTCtx, Env, "NoreturnOnRhsOfOr");
+        EXPECT_TRUE(Env.flowConditionImplies(NoreturnOnRhsOfOr));
+
+        auto &NoreturnOnLhsMakesAndUnreachable = getValueForDecl<BoolValue>(
+            ASTCtx, Env, "NoreturnOnLhsMakesAndUnreachable");
+        EXPECT_TRUE(Env.flowConditionImplies(NoreturnOnLhsMakesAndUnreachable));
+
+        auto &NoreturnOnLhsMakesOrUnreachable = getValueForDecl<BoolValue>(
+            ASTCtx, Env, "NoreturnOnLhsMakesOrUnreachable");
+        EXPECT_TRUE(Env.flowConditionImplies(NoreturnOnLhsMakesOrUnreachable));
+      });
+}
+
 } // namespace