mboehme updated this revision to Diff 507287.
mboehme added a comment.
Reworded comment.
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D146514/new/
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 = 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
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 &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:
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, 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:
@@ -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
