mboehme created this revision.
Herald added subscribers: martong, xazax.hun.
Herald added a reviewer: NoQ.
Herald added a project: All.
mboehme requested review of this revision.
Herald added a project: clang.
Herald added a subscriber: cfe-commits.
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.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D146514
Files:
clang/include/clang/Analysis/FlowSensitive/ControlFlowContext.h
clang/include/clang/Analysis/FlowSensitive/Transfer.h
clang/lib/Analysis/FlowSensitive/ControlFlowContext.cpp
clang/lib/Analysis/FlowSensitive/Transfer.cpp
clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
clang/unittests/Analysis/FlowSensitive/TestingSupport.h
clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
Index: clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
===================================================================
--- clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
+++ clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
@@ -5104,4 +5104,70 @@
});
}
+// 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 = getValueFromDecl<BoolValue>(ASTCtx, Env, "b1");
+ EXPECT_TRUE(Env.flowConditionImplies(Env.makeNot(B1)));
+
+ auto &NoreturnOnRhsOfAnd =
+ getValueFromDecl<BoolValue>(ASTCtx, Env, "NoreturnOnRhsOfAnd");
+ EXPECT_TRUE(Env.flowConditionImplies(Env.makeNot(NoreturnOnRhsOfAnd)));
+
+ auto &B2 = getValueFromDecl<BoolValue>(ASTCtx, Env, "b2");
+ EXPECT_TRUE(Env.flowConditionImplies(B2));
+
+ auto &NoreturnOnRhsOfOr =
+ getValueFromDecl<BoolValue>(ASTCtx, Env, "NoreturnOnRhsOfOr");
+ EXPECT_TRUE(Env.flowConditionImplies(NoreturnOnRhsOfOr));
+
+ auto &NoreturnOnLhsMakesAndUnreachable = getValueFromDecl<BoolValue>(
+ ASTCtx, Env, "NoreturnOnLhsMakesAndUnreachable");
+ EXPECT_TRUE(Env.flowConditionImplies(NoreturnOnLhsMakesAndUnreachable));
+
+ auto &NoreturnOnLhsMakesOrUnreachable = getValueFromDecl<BoolValue>(
+ ASTCtx, Env, "NoreturnOnLhsMakesOrUnreachable");
+ EXPECT_TRUE(Env.flowConditionImplies(NoreturnOnLhsMakesOrUnreachable));
+ });
+}
+
} // namespace
Index: clang/unittests/Analysis/FlowSensitive/TestingSupport.h
===================================================================
--- clang/unittests/Analysis/FlowSensitive/TestingSupport.h
+++ clang/unittests/Analysis/FlowSensitive/TestingSupport.h
@@ -389,6 +389,20 @@
/// `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 &getValueFromDecl(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:
Index: clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
===================================================================
--- clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
+++ clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
@@ -51,6 +51,8 @@
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;
Index: clang/lib/Analysis/FlowSensitive/Transfer.cpp
===================================================================
--- clang/lib/Analysis/FlowSensitive/Transfer.cpp
+++ clang/lib/Analysis/FlowSensitive/Transfer.cpp
@@ -162,15 +162,27 @@
}
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, this implies that if we end up evaluating
+ // this BinaryOperator, 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:
@@ -779,15 +791,19 @@
}
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;
+
+ if (auto *Val = dyn_cast_or_null<BoolValue>(
+ SubExprEnv->getValue(SubExpr, SkipPast::Reference)))
+ return Val;
if (Env.getStorageLocation(SubExpr, SkipPast::None) == nullptr) {
// Sub-expressions that are logic operators are not added in basic blocks
@@ -800,11 +816,11 @@
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
Index: clang/lib/Analysis/FlowSensitive/ControlFlowContext.cpp
===================================================================
--- clang/lib/Analysis/FlowSensitive/ControlFlowContext.cpp
+++ clang/lib/Analysis/FlowSensitive/ControlFlowContext.cpp
@@ -16,6 +16,7 @@
#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>
@@ -44,6 +45,28 @@
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;
@@ -64,7 +87,11 @@
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
Index: clang/include/clang/Analysis/FlowSensitive/Transfer.h
===================================================================
--- clang/include/clang/Analysis/FlowSensitive/Transfer.h
+++ clang/include/clang/Analysis/FlowSensitive/Transfer.h
@@ -26,9 +26,9 @@
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;
};
Index: clang/include/clang/Analysis/FlowSensitive/ControlFlowContext.h
===================================================================
--- clang/include/clang/Analysis/FlowSensitive/ControlFlowContext.h
+++ clang/include/clang/Analysis/FlowSensitive/ControlFlowContext.h
@@ -18,6 +18,7 @@
#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>
@@ -47,18 +48,26 @@
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
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
