martong created this revision.
martong added reviewers: xazax.hun, gribozavr2, sgatev, ymandel, samestep.
Herald added subscribers: steakhal, gamesh411, Szelethus, dkrupp, rnkovacs,
mgorny.
Herald added a reviewer: Szelethus.
Herald added a reviewer: NoQ.
Herald added a project: All.
martong requested review of this revision.
Herald added a project: clang.
Herald added a subscriber: cfe-commits.
This patch is an auxiliary material for an RFC on discourse.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D133698
Files:
clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h
clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h
clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
clang/unittests/Analysis/FlowSensitive/CMakeLists.txt
clang/unittests/Analysis/FlowSensitive/SignAnalysisTest.cpp
clang/unittests/Analysis/FlowSensitive/TestingSupport.h
Index: clang/unittests/Analysis/FlowSensitive/TestingSupport.h
===================================================================
--- clang/unittests/Analysis/FlowSensitive/TestingSupport.h
+++ clang/unittests/Analysis/FlowSensitive/TestingSupport.h
@@ -344,6 +344,7 @@
llvm::any_cast<typename AnalysisT::Lattice>(&State.Lattice.Value);
auto [_, InsertSuccess] =
AnnotationStates.insert({It->second, StateT{*Lattice, State.Env}});
+ (void)_;
(void)InsertSuccess;
assert(InsertSuccess);
};
Index: clang/unittests/Analysis/FlowSensitive/SignAnalysisTest.cpp
===================================================================
--- /dev/null
+++ clang/unittests/Analysis/FlowSensitive/SignAnalysisTest.cpp
@@ -0,0 +1,590 @@
+//===- unittests/Analysis/FlowSensitive/SignAnalysisTest.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
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines a simplistic version of Sign Analysis as an example
+// of a forward, monotonic dataflow analysis. The analysis tracks all
+// variables in the scope, but lacks escape analysis.
+//
+//===----------------------------------------------------------------------===//
+
+#include "TestingSupport.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/Decl.h"
+#include "clang/AST/Expr.h"
+#include "clang/AST/Stmt.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/ASTMatchers/ASTMatchers.h"
+#include "clang/Analysis/FlowSensitive/DataflowAnalysis.h"
+#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
+#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
+#include "clang/Analysis/FlowSensitive/MapLattice.h"
+#include "clang/Tooling/Tooling.h"
+#include "llvm/ADT/None.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/Twine.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Testing/Support/Annotations.h"
+#include "llvm/Testing/Support/Error.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include <cstdint>
+#include <memory>
+#include <ostream>
+#include <string>
+#include <utility>
+
+namespace clang {
+namespace dataflow {
+namespace {
+using namespace ast_matchers;
+
+// Models the signedness of a variable, for all paths through
+// the program.
+struct SignLattice {
+ enum class SignState : int {
+ Bottom,
+ Negative,
+ Zero,
+ Positive,
+ Top,
+ };
+ SignState State;
+
+ constexpr SignLattice() : State(SignState::Bottom) {}
+ constexpr SignLattice(int64_t V)
+ : State(V == 0 ? SignState::Zero
+ : (V < 0 ? SignState::Negative : SignState::Positive)) {}
+ constexpr SignLattice(SignState S) : State(S) {}
+
+ static constexpr SignLattice bottom() {
+ return SignLattice(SignState::Bottom);
+ }
+ static constexpr SignLattice negative() {
+ return SignLattice(SignState::Negative);
+ }
+ static constexpr SignLattice zero() { return SignLattice(SignState::Zero); }
+ static constexpr SignLattice positive() {
+ return SignLattice(SignState::Positive);
+ }
+ static constexpr SignLattice top() { return SignLattice(SignState::Top); }
+
+ friend bool operator==(const SignLattice &Lhs, const SignLattice &Rhs) {
+ return Lhs.State == Rhs.State;
+ }
+ friend bool operator!=(const SignLattice &Lhs, const SignLattice &Rhs) {
+ return !(Lhs == Rhs);
+ }
+
+ LatticeJoinEffect join(const SignLattice &Other) {
+ if (*this == Other || Other == bottom() || *this == top())
+ return LatticeJoinEffect::Unchanged;
+
+ if (*this == bottom()) {
+ *this = Other;
+ return LatticeJoinEffect::Changed;
+ }
+
+ *this = top();
+ return LatticeJoinEffect::Changed;
+ }
+};
+
+std::ostream &operator<<(std::ostream &OS, const SignLattice &L) {
+ switch (L.State) {
+ case SignLattice::SignState::Bottom:
+ return OS << "Bottom";
+ case SignLattice::SignState::Negative:
+ return OS << "Negative";
+ case SignLattice::SignState::Zero:
+ return OS << "Zero";
+ case SignLattice::SignState::Positive:
+ return OS << "Positive";
+ case SignLattice::SignState::Top:
+ return OS << "Top";
+ }
+ llvm_unreachable("unknown SignState!");
+}
+
+using SignPropagationLattice = VarMapLattice<SignLattice>;
+
+constexpr char kDecl[] = "decl";
+constexpr char kVar[] = "var";
+constexpr char kRHSVar[] = "rhsvar";
+constexpr char kInit[] = "init";
+constexpr char kJustAssignment[] = "just-assignment";
+constexpr char kAssignment[] = "assignment";
+constexpr char kComparison[] = "comparison";
+constexpr char kRHS[] = "rhs";
+
+auto refToVar(StringRef V) { return declRefExpr(to(varDecl().bind(V))); }
+
+// N.B. This analysis is deliberately simplistic, leaving out many important
+// details needed for a real analysis. Most notably, the transfer function does
+// not account for the variable's address possibly escaping, which would
+// invalidate the analysis. It also could be optimized to drop out-of-scope
+// variables from the map.
+class SignPropagationAnalysis
+ : public DataflowAnalysis<SignPropagationAnalysis, SignPropagationLattice> {
+public:
+ explicit SignPropagationAnalysis(ASTContext &Context)
+ : DataflowAnalysis<SignPropagationAnalysis, SignPropagationLattice>(
+ Context) {}
+
+ static SignPropagationLattice initialElement() {
+ return SignPropagationLattice::bottom();
+ }
+
+ void branchTransfer(bool Branch, const Stmt *S, SignPropagationLattice &Vars,
+ Environment &Env) {
+ auto matcher = binaryOperator(isComparisonOperator(),
+ hasLHS(hasDescendant(refToVar(kVar))),
+ hasRHS(expr().bind(kRHS)))
+ .bind(kComparison);
+ ASTContext &Context = getASTContext();
+ auto Results = match(matcher, *S, Context);
+ if (Results.empty())
+ return;
+ const BoundNodes &Nodes = Results[0];
+
+ const auto *Var = Nodes.getNodeAs<clang::VarDecl>(kVar);
+ assert(Var != nullptr);
+ if (const auto *BinOp =
+ Nodes.getNodeAs<clang::BinaryOperator>(kComparison)) {
+ const auto *RHS = Nodes.getNodeAs<clang::Expr>(kRHS);
+ assert(RHS != nullptr);
+
+ Expr::EvalResult R;
+ if (!(RHS->EvaluateAsInt(R, Context) && R.Val.isInt()))
+ return;
+ auto V = SignLattice(R.Val.getInt().getExtValue());
+ auto OpCode =
+ Branch ? BinOp->getOpcode()
+ : BinaryOperator::negateComparisonOp(BinOp->getOpcode());
+ switch (OpCode) {
+ case BO_LT:
+ if (V == SignLattice::positive()) {
+ Vars[Var] = SignLattice::top();
+ } else {
+ // Var is less than 0 or a negative number.
+ Vars[Var] = SignLattice::negative();
+ }
+ break;
+ case BO_LE:
+ // Var is less than or equal to a negative number.
+ if (V == SignLattice::negative()) {
+ Vars[Var] = SignLattice::negative();
+ } else {
+ // Var is less than or equal to 0 or a positive number.
+ Vars[Var] = SignLattice::top();
+ }
+ break;
+ case BO_GT:
+ if (V == SignLattice::negative()) {
+ Vars[Var] = SignLattice::top();
+ } else {
+ // Var is greater than 0 or a positive number.
+ Vars[Var] = SignLattice::positive();
+ }
+ break;
+ case BO_GE:
+ // Var is greater than or equal to a positive number.
+ if (V == SignLattice::positive()) {
+ Vars[Var] = SignLattice::positive();
+ } else {
+ // Var is greater than or equal to 0 or a negative number.
+ Vars[Var] = SignLattice::top();
+ }
+ break;
+ case BO_EQ:
+ Vars[Var] = V;
+ break;
+ case BO_NE: // Noop.
+ break;
+ default:
+ llvm_unreachable("not implemented");
+ }
+ }
+ }
+
+ void transfer(const Stmt *S, SignPropagationLattice &Vars, Environment &Env) {
+ auto matcher = stmt(
+ anyOf(declStmt(hasSingleDecl(
+ varDecl(decl().bind(kVar), hasType(isInteger()),
+ optionally(hasInitializer(expr().bind(kInit))))
+ .bind(kDecl))),
+ binaryOperator(hasOperatorName("="), hasLHS(refToVar(kVar)),
+ hasRHS(hasDescendant(refToVar(kRHSVar))))
+ .bind(kJustAssignment),
+ binaryOperator(isAssignmentOperator(), hasLHS(refToVar(kVar)))
+ .bind(kAssignment)));
+
+ ASTContext &Context = getASTContext();
+ auto Results = match(matcher, *S, Context);
+ if (Results.empty())
+ return;
+ const BoundNodes &Nodes = Results[0];
+
+ const auto *Var = Nodes.getNodeAs<clang::VarDecl>(kVar);
+ assert(Var != nullptr);
+
+ if (Nodes.getNodeAs<clang::VarDecl>(kDecl) != nullptr) {
+ if (const auto *E = Nodes.getNodeAs<clang::Expr>(kInit)) {
+ Expr::EvalResult R;
+ Vars[Var] = (E->EvaluateAsInt(R, Context) && R.Val.isInt())
+ ? SignLattice(R.Val.getInt().getExtValue())
+ : SignLattice::bottom();
+ } else {
+ // An unitialized variable holds *some* value, but we don't know what it
+ // is (it is implementation defined), so we set it to top.
+ Vars[Var] = SignLattice::top();
+ }
+ // Assign one variable to another.
+ } else if (Nodes.getNodeAs<clang::Expr>(kJustAssignment)) {
+ const auto *RHSVar = Nodes.getNodeAs<clang::VarDecl>(kRHSVar);
+ assert(RHSVar);
+ auto It = Vars.find(RHSVar);
+ if (It != Vars.end())
+ Vars[Var] = It->second;
+ else
+ Vars[Var] = SignLattice::top();
+ // Assign a constant to a variable.
+ } else if (const auto *BinOp =
+ Nodes.getNodeAs<clang::BinaryOperator>(kAssignment)) {
+ const auto *RHS = BinOp->getRHS();
+ Expr::EvalResult R;
+ // Not a constant.
+ if (!(RHS->EvaluateAsInt(R, Context) && R.Val.isInt())) {
+ Vars[Var] = SignLattice::top();
+ return;
+ }
+ Vars[Var] = SignLattice(R.Val.getInt().getExtValue());
+ }
+ }
+};
+
+using ::testing::IsEmpty;
+using ::testing::Pair;
+using ::testing::UnorderedElementsAre;
+
+MATCHER_P(Var, name,
+ (llvm::Twine(negation ? "isn't" : "is") + " a variable named `" +
+ name + "`")
+ .str()) {
+ assert(isa<VarDecl>(arg));
+ return arg->getName() == name;
+}
+
+MATCHER(Bottom, "") { return arg == arg.bottom(); }
+MATCHER(Negative, "") { return arg == arg.negative(); }
+MATCHER(Zero, "") { return arg == arg.zero(); }
+MATCHER(Positive, "") { return arg == arg.positive(); }
+MATCHER(Top, "") { return arg == arg.top(); }
+
+MATCHER_P(HoldsSignLattice, m,
+ ((negation ? "doesn't hold" : "holds") +
+ llvm::StringRef(" a lattice element that ") +
+ ::testing::DescribeMatcher<SignPropagationLattice>(m, negation))
+ .str()) {
+ return ExplainMatchResult(m, arg.Lattice, result_listener);
+}
+
+template <typename Matcher>
+void RunDataflow(llvm::StringRef Code, Matcher Expectations) {
+ ASSERT_THAT_ERROR(
+ test::checkDataflow<SignPropagationAnalysis>(
+ Code, "fun",
+ [](ASTContext &C, Environment &) {
+ return SignPropagationAnalysis(C);
+ },
+ [&Expectations](
+ llvm::ArrayRef<std::pair<
+ std::string,
+ DataflowAnalysisState<SignPropagationAnalysis::Lattice>>>
+ Results,
+ ASTContext &) { EXPECT_THAT(Results, Expectations); },
+ {"-fsyntax-only", "-std=c++17"}),
+ llvm::Succeeded());
+}
+
+TEST(SignAnalysisTest, Init) {
+ std::string Code = R"(
+ void fun() {
+ int neg = -1;
+ int zero = 0;
+ int pos = 1;
+ int uninited;
+ // [[p]]
+ }
+ )";
+ RunDataflow(Code, UnorderedElementsAre(
+ Pair("p", HoldsSignLattice(UnorderedElementsAre(
+ Pair(Var("neg"), Negative()),
+ Pair(Var("zero"), Zero()),
+ Pair(Var("pos"), Positive()),
+ Pair(Var("uninited"), Top()))))));
+}
+
+TEST(SignAnalysisTest, Assignment) {
+ std::string Code = R"(
+ void fun() {
+ int neg, zero, pos;
+ neg = -1;
+ zero = 0;
+ pos = 1;
+ // [[p]]
+ }
+ )";
+ RunDataflow(Code, UnorderedElementsAre(
+ Pair("p", HoldsSignLattice(UnorderedElementsAre(
+ Pair(Var("neg"), Negative()),
+ Pair(Var("zero"), Zero()),
+ Pair(Var("pos"), Positive()))))));
+}
+
+TEST(SignAnalysisTest, InitToBottom) {
+ std::string Code = R"(
+ int foo();
+ void fun() {
+ int a = foo();
+ // [[p]]
+ }
+ )";
+ RunDataflow(Code, UnorderedElementsAre(
+ Pair("p", HoldsSignLattice(UnorderedElementsAre(
+ Pair(Var("a"), Bottom()))))));
+}
+
+TEST(SignAnalysisTest, AssignmentAfterBottom) {
+ std::string Code = R"(
+ int foo();
+ void fun(bool b) {
+ int a = foo();
+ a = -1;
+ // [[p]]
+ }
+ )";
+ RunDataflow(Code, UnorderedElementsAre(
+ Pair("p", HoldsSignLattice(UnorderedElementsAre(
+ Pair(Var("a"), Negative()))))));
+}
+
+TEST(SignAnalysisTest, GreaterThan) {
+ std::string Code = R"(
+ int foo();
+ void fun() {
+ int a = foo();
+ if (a > 0) {
+ (void)0;
+ // [[p]]
+ }
+ if (a > -1) {
+ (void)0;
+ // [[q]]
+ }
+ }
+ )";
+ RunDataflow(Code, UnorderedElementsAre(
+ Pair("p", HoldsSignLattice(UnorderedElementsAre(
+ Pair(Var("a"), Positive())))),
+ Pair("q", HoldsSignLattice(UnorderedElementsAre(
+ Pair(Var("a"), Top()))))));
+}
+
+TEST(SignAnalysisTest, GreaterThanIfElse) {
+ std::string Code = R"(
+ void fun(int a) {
+ if (a > 0) {
+ (void)1;
+ // [[p]]
+ } else {
+ (void)0;
+ // [[q]]
+ }
+ }
+ )";
+ RunDataflow(Code, UnorderedElementsAre(
+ Pair("p", HoldsSignLattice(UnorderedElementsAre(
+ Pair(Var("a"), Positive())))),
+ Pair("q", HoldsSignLattice(UnorderedElementsAre(
+ Pair(Var("a"), Top()))))));
+}
+
+TEST(SignAnalysisTest, LessThan) {
+ std::string Code = R"(
+ int foo();
+ void fun() {
+ int a = foo();
+ if (a < 0) {
+ (void)0;
+ // [[p]]
+ }
+ if (a < 1) {
+ (void)0;
+ // [[q]]
+ }
+ }
+ )";
+ RunDataflow(Code, UnorderedElementsAre(
+ Pair("p", HoldsSignLattice(UnorderedElementsAre(
+ Pair(Var("a"), Negative())))),
+ Pair("q", HoldsSignLattice(UnorderedElementsAre(
+ Pair(Var("a"), Top()))))));
+}
+
+TEST(SignAnalysisTest, LessThanIfElse) {
+ std::string Code = R"(
+ void fun(int a) {
+ if (a < 0) {
+ (void)1;
+ // [[p]]
+ } else {
+ (void)0;
+ // [[q]]
+ }
+ }
+ )";
+ RunDataflow(Code, UnorderedElementsAre(
+ Pair("p", HoldsSignLattice(UnorderedElementsAre(
+ Pair(Var("a"), Negative())))),
+ Pair("q", HoldsSignLattice(UnorderedElementsAre(
+ Pair(Var("a"), Top()))))));
+}
+
+TEST(SignAnalysisTest, Equality) {
+ std::string Code = R"(
+ int foo();
+ void fun() {
+ int a = foo();
+ if (a == -1) {
+ (void)0;
+ // [[n]]
+ }
+ if (a == 0) {
+ (void)0;
+ // [[z]]
+ }
+ if (a == 1) {
+ (void)0;
+ // [[p]]
+ }
+ }
+ )";
+ RunDataflow(Code, UnorderedElementsAre(
+ Pair("n", HoldsSignLattice(UnorderedElementsAre(
+ Pair(Var("a"), Negative())))),
+ Pair("z", HoldsSignLattice(UnorderedElementsAre(
+ Pair(Var("a"), Zero())))),
+ Pair("p", HoldsSignLattice(UnorderedElementsAre(
+ Pair(Var("a"), Positive()))))));
+}
+
+TEST(SignAnalysisTest, SymbolicAssignment) {
+ std::string Code = R"(
+ int foo();
+ void fun() {
+ int a = foo();
+ int b = foo();
+ if (a < 0) {
+ b = a;
+ (void)0;
+ // [[p]]
+ }
+ }
+ )";
+ RunDataflow(Code, UnorderedElementsAre(
+ Pair("p", HoldsSignLattice(UnorderedElementsAre(
+ Pair(Var("a"), Negative()),
+ Pair(Var("b"), Negative()))))));
+}
+
+TEST(SignAnalysisTest, JoinToTop) {
+ std::string Code = R"(
+ int foo();
+ void fun(bool b) {
+ int a = foo();
+ if (b) {
+ a = -1;
+ (void)0;
+ // [[p]]
+ } else {
+ a = 1;
+ (void)0;
+ // [[q]]
+ }
+ (void)0;
+ // [[r]]
+ }
+ )";
+ RunDataflow(Code, UnorderedElementsAre(
+ Pair("p", HoldsSignLattice(UnorderedElementsAre(
+ Pair(Var("a"), Negative())))),
+ Pair("q", HoldsSignLattice(UnorderedElementsAre(
+ Pair(Var("a"), Positive())))),
+ Pair("r", HoldsSignLattice(UnorderedElementsAre(
+ Pair(Var("a"), Top()))))));
+}
+
+TEST(SignAnalysisTest, JoinToNeg) {
+ std::string Code = R"(
+ int foo();
+ void fun() {
+ int a = foo();
+ if (a < 1) {
+ a = -1;
+ (void)0;
+ // [[p]]
+ } else {
+ a = -1;
+ (void)0;
+ // [[q]]
+ }
+ (void)0;
+ // [[r]]
+ }
+ )";
+ RunDataflow(Code, UnorderedElementsAre(
+ Pair("p", HoldsSignLattice(UnorderedElementsAre(
+ Pair(Var("a"), Negative())))),
+ Pair("q", HoldsSignLattice(UnorderedElementsAre(
+ Pair(Var("a"), Negative())))),
+ Pair("r", HoldsSignLattice(UnorderedElementsAre(
+ Pair(Var("a"), Negative()))))));
+}
+
+TEST(SignAnalysisTest, NestedIfs) {
+ std::string Code = R"(
+ int foo();
+ void fun() {
+ int a = foo();
+ if (a >= 0) {
+ (void)0;
+ // [[p]]
+ if (a == 0) {
+ (void)0;
+ // [[q]]
+ }
+ }
+ (void)0;
+ // [[r]]
+ }
+ )";
+ RunDataflow(
+ Code,
+ UnorderedElementsAre(
+ Pair("p",
+ HoldsSignLattice(UnorderedElementsAre(Pair(Var("a"), Top())))),
+ Pair("q",
+ HoldsSignLattice(UnorderedElementsAre(Pair(Var("a"), Zero())))),
+ Pair("r",
+ HoldsSignLattice(UnorderedElementsAre(Pair(Var("a"), Top()))))));
+}
+
+} // namespace
+} // namespace dataflow
+} // namespace clang
Index: clang/unittests/Analysis/FlowSensitive/CMakeLists.txt
===================================================================
--- clang/unittests/Analysis/FlowSensitive/CMakeLists.txt
+++ clang/unittests/Analysis/FlowSensitive/CMakeLists.txt
@@ -12,12 +12,13 @@
MapLatticeTest.cpp
MatchSwitchTest.cpp
MultiVarConstantPropagationTest.cpp
+ SignAnalysisTest.cpp
SingleVarConstantPropagationTest.cpp
+ SolverTest.cpp
TestingSupport.cpp
TestingSupportTest.cpp
TransferTest.cpp
TypeErasedDataflowAnalysisTest.cpp
- SolverTest.cpp
UncheckedOptionalAccessModelTest.cpp
)
Index: clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
===================================================================
--- clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
+++ clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
@@ -71,52 +71,57 @@
/// Extends the flow condition of an environment based on a terminator
/// statement.
-class TerminatorVisitor : public ConstStmtVisitor<TerminatorVisitor> {
+class TerminatorVisitor
+ : public ConstStmtVisitor<TerminatorVisitor,
+ std::pair<const Expr *, bool>> {
public:
- TerminatorVisitor(const StmtToEnvMap &StmtToEnv, Environment &Env,
+ using RetTy = std::pair<const Expr *, bool>;
+ TerminatorVisitor(TypeErasedDataflowAnalysis &Analysis,
+ const StmtToEnvMap &StmtToEnv, Environment &Env,
int BlockSuccIdx, TransferOptions TransferOpts)
- : StmtToEnv(StmtToEnv), Env(Env), BlockSuccIdx(BlockSuccIdx),
- TransferOpts(TransferOpts) {}
+ : Analysis(Analysis), StmtToEnv(StmtToEnv), Env(Env),
+ BlockSuccIdx(BlockSuccIdx), TransferOpts(TransferOpts) {}
- void VisitIfStmt(const IfStmt *S) {
+ RetTy VisitIfStmt(const IfStmt *S) {
auto *Cond = S->getCond();
assert(Cond != nullptr);
- extendFlowCondition(*Cond);
+ return extendFlowCondition(*Cond);
}
- void VisitWhileStmt(const WhileStmt *S) {
+ RetTy VisitWhileStmt(const WhileStmt *S) {
auto *Cond = S->getCond();
assert(Cond != nullptr);
- extendFlowCondition(*Cond);
+ return extendFlowCondition(*Cond);
}
- void VisitDoStmt(const DoStmt *S) {
+ RetTy VisitDoStmt(const DoStmt *S) {
auto *Cond = S->getCond();
assert(Cond != nullptr);
- extendFlowCondition(*Cond);
+ return extendFlowCondition(*Cond);
}
- void VisitForStmt(const ForStmt *S) {
+ RetTy VisitForStmt(const ForStmt *S) {
auto *Cond = S->getCond();
if (Cond != nullptr)
- extendFlowCondition(*Cond);
+ return extendFlowCondition(*Cond);
+ return {nullptr, false};
}
- void VisitBinaryOperator(const BinaryOperator *S) {
+ RetTy VisitBinaryOperator(const BinaryOperator *S) {
assert(S->getOpcode() == BO_LAnd || S->getOpcode() == BO_LOr);
auto *LHS = S->getLHS();
assert(LHS != nullptr);
- extendFlowCondition(*LHS);
+ return extendFlowCondition(*LHS);
}
- void VisitConditionalOperator(const ConditionalOperator *S) {
+ RetTy VisitConditionalOperator(const ConditionalOperator *S) {
auto *Cond = S->getCond();
assert(Cond != nullptr);
- extendFlowCondition(*Cond);
+ return extendFlowCondition(*Cond);
}
private:
- void extendFlowCondition(const Expr &Cond) {
+ RetTy extendFlowCondition(const Expr &Cond) {
// The terminator sub-expression might not be evaluated.
if (Env.getStorageLocation(Cond, SkipPast::None) == nullptr)
transfer(StmtToEnv, Cond, Env, TransferOpts);
@@ -140,14 +145,19 @@
Env.setValue(*Loc, *Val);
}
+ bool Assumption = true;
// The condition must be inverted for the successor that encompasses the
// "else" branch, if such exists.
- if (BlockSuccIdx == 1)
+ if (BlockSuccIdx == 1) {
Val = &Env.makeNot(*Val);
+ Assumption = false;
+ }
Env.addToFlowCondition(*Val);
+ return {&Cond, Assumption};
}
+ TypeErasedDataflowAnalysis &Analysis;
const StmtToEnvMap &StmtToEnv;
Environment &Env;
int BlockSuccIdx;
@@ -239,10 +249,14 @@
if (BuiltinTransferOpts) {
if (const Stmt *PredTerminatorStmt = Pred->getTerminatorStmt()) {
const StmtToEnvMapImpl StmtToEnv(AC.CFCtx, AC.BlockStates);
- TerminatorVisitor(StmtToEnv, PredState.Env,
- blockIndexInPredecessor(*Pred, Block),
- *BuiltinTransferOpts)
- .Visit(PredTerminatorStmt);
+ auto [Cond, Assumption] =
+ TerminatorVisitor(Analysis, StmtToEnv, PredState.Env,
+ blockIndexInPredecessor(*Pred, Block),
+ *BuiltinTransferOpts)
+ .Visit(PredTerminatorStmt);
+ if (Cond)
+ Analysis.branchTransferTypeErased(Assumption, Cond, PredState.Lattice,
+ PredState.Env);
}
}
Index: clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h
===================================================================
--- clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h
+++ clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h
@@ -83,6 +83,8 @@
/// element and type-erased lattice element.
virtual void transferTypeErased(const CFGElement *, TypeErasedLattice &,
Environment &) = 0;
+ virtual void branchTransferTypeErased(bool Branch, const Stmt *,
+ TypeErasedLattice &, Environment &) = 0;
/// If the built-in transfer functions (which model the heap and stack in the
/// `Environment`) are to be applied, returns the options to be passed to
Index: clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h
===================================================================
--- clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h
+++ clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h
@@ -123,6 +123,16 @@
}
}
+ // Default implementation is a Noop.
+ virtual void branchTransfer(bool Branch, const Stmt *S, Lattice &L,
+ Environment &Env) {}
+
+ void branchTransferTypeErased(bool Branch, const Stmt *Stmt,
+ TypeErasedLattice &E, Environment &Env) final {
+ Lattice &L = llvm::any_cast<Lattice &>(E.Value);
+ branchTransfer(Branch, Stmt, L, Env);
+ }
+
private:
ASTContext &Context;
};
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
