samestep created this revision.
Herald added subscribers: martong, tschuett, xazax.hun.
Herald added a reviewer: NoQ.
Herald added a project: All.
samestep requested review of this revision.
Herald added a project: clang.
Herald added a subscriber: cfe-commits.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D130593
Files:
clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h
clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp
clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
clang/lib/Analysis/FlowSensitive/Transfer.cpp
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
@@ -3960,4 +3960,45 @@
/*.BuiltinTransferOptions=*/{/*.ContextSensitive=*/true}});
}
+TEST(TransferTest, ContextSensitiveSetBothTrueAndFalse) {
+ std::string Code = R"(
+ bool GiveBool();
+ void SetBool(bool &Var, bool Val) { Var = Val; }
+
+ void target() {
+ bool Foo = GiveBool();
+ bool Bar = GiveBool();
+ SetBool(Foo, true);
+ SetBool(Bar, false);
+ // [[p]]
+ }
+ )";
+ runDataflow(Code,
+ [](llvm::ArrayRef<
+ std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+ Results,
+ ASTContext &ASTCtx) {
+ ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
+ const Environment &Env = Results[0].second.Env;
+
+ const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
+ ASSERT_THAT(FooDecl, NotNull());
+
+ const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
+ ASSERT_THAT(BarDecl, NotNull());
+
+ auto &FooVal =
+ *cast<BoolValue>(Env.getValue(*FooDecl, SkipPast::None));
+ EXPECT_TRUE(Env.flowConditionImplies(FooVal));
+ EXPECT_FALSE(Env.flowConditionImplies(Env.makeNot(FooVal)));
+
+ auto &BarVal =
+ *cast<BoolValue>(Env.getValue(*BarDecl, SkipPast::None));
+ EXPECT_FALSE(Env.flowConditionImplies(BarVal));
+ EXPECT_TRUE(Env.flowConditionImplies(Env.makeNot(BarVal)));
+ },
+ {/*.ApplyBuiltinTransfer=*/true,
+ /*.BuiltinTransferOptions=*/{/*.ContextSensitive=*/true}});
+}
+
} // namespace
Index: clang/lib/Analysis/FlowSensitive/Transfer.cpp
===================================================================
--- clang/lib/Analysis/FlowSensitive/Transfer.cpp
+++ clang/lib/Analysis/FlowSensitive/Transfer.cpp
@@ -534,7 +534,7 @@
auto ExitState = (*BlockToOutputState)[ExitBlock];
assert(ExitState);
- Env = ExitState->Env;
+ Env.popCall(ExitState->Env);
}
}
Index: clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
===================================================================
--- clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
+++ clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
@@ -154,7 +154,7 @@
: DACtx(&DACtx), FlowConditionToken(&DACtx.makeFlowConditionToken()) {}
Environment::Environment(const Environment &Other)
- : DACtx(Other.DACtx), DeclToLoc(Other.DeclToLoc),
+ : DACtx(Other.DACtx), CallStr(Other.CallStr), DeclToLoc(Other.DeclToLoc),
ExprToLoc(Other.ExprToLoc), LocToVal(Other.LocToVal),
MemberLocToStruct(Other.MemberLocToStruct),
FlowConditionToken(&DACtx->forkFlowCondition(*Other.FlowConditionToken)) {
@@ -192,7 +192,7 @@
// FIXME: Add support for union types.
if (!ThisPointeeType->isUnionType()) {
auto &ThisPointeeLoc = createStorageLocation(ThisPointeeType);
- DACtx.setThisPointeeStorageLocation(ThisPointeeLoc);
+ DACtx.getFrame(CallStr).setThisPointeeStorageLocation(ThisPointeeLoc);
if (Value *ThisPointeeVal = createValue(ThisPointeeType))
setValue(ThisPointeeLoc, *ThisPointeeVal);
}
@@ -202,6 +202,7 @@
Environment Environment::pushCall(const CallExpr *Call) const {
Environment Env(*this);
+ Env.CallStr.push_back(Call);
// FIXME: Currently this only works if the callee is never a method and the
// same callee is never analyzed from multiple separate callsites. To
@@ -238,6 +239,17 @@
return Env;
}
+void Environment::popCall(const Environment &CalleeEnv) {
+ // We ignore `DACtx` because it's already the same in both. We don't want the
+ // callee's `CallStr` because it is one level deeper than ours. We don't bring
+ // back `DeclToLoc` and `ExprToLoc` because their mappings are only valid for
+ // the `CallStr` in `CalleeEnv`, and we want to be able to later analyze the
+ // same callee in a different context.
+ this->LocToVal = std::move(CalleeEnv.LocToVal);
+ this->MemberLocToStruct = std::move(CalleeEnv.MemberLocToStruct);
+ this->FlowConditionToken = std::move(CalleeEnv.FlowConditionToken);
+}
+
bool Environment::equivalentTo(const Environment &Other,
Environment::ValueModel &Model) const {
assert(DACtx == Other.DACtx);
@@ -323,21 +335,21 @@
}
StorageLocation &Environment::createStorageLocation(QualType Type) {
- return DACtx->getStableStorageLocation(Type);
+ return DACtx->getStableStorageLocation(CallStr, Type);
}
StorageLocation &Environment::createStorageLocation(const VarDecl &D) {
// Evaluated declarations are always assigned the same storage locations to
// ensure that the environment stabilizes across loop iterations. Storage
// locations for evaluated declarations are stored in the analysis context.
- return DACtx->getStableStorageLocation(D);
+ return DACtx->getStableStorageLocation(CallStr, D);
}
StorageLocation &Environment::createStorageLocation(const Expr &E) {
// Evaluated expressions are always assigned the same storage locations to
// ensure that the environment stabilizes across loop iterations. Storage
// locations for evaluated expressions are stored in the analysis context.
- return DACtx->getStableStorageLocation(E);
+ return DACtx->getStableStorageLocation(CallStr, E);
}
void Environment::setStorageLocation(const ValueDecl &D, StorageLocation &Loc) {
@@ -365,7 +377,7 @@
}
StorageLocation *Environment::getThisPointeeStorageLocation() const {
- return DACtx->getThisPointeeStorageLocation();
+ return DACtx->getFrame(CallStr).getThisPointeeStorageLocation();
}
PointerValue &Environment::getOrCreateNullPointerValue(QualType PointeeType) {
Index: clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp
===================================================================
--- clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp
+++ clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp
@@ -25,14 +25,16 @@
namespace dataflow {
StorageLocation &
-DataflowAnalysisContext::getStableStorageLocation(QualType Type) {
+DataflowAnalysisContext::getStableStorageLocation(const CallString &CallStr,
+ QualType Type) {
if (!Type.isNull() &&
(Type->isStructureOrClassType() || Type->isUnionType())) {
// FIXME: Explore options to avoid eager initialization of fields as some of
// them might not be needed for a particular analysis.
llvm::DenseMap<const ValueDecl *, StorageLocation *> FieldLocs;
for (const FieldDecl *Field : getObjectFields(Type))
- FieldLocs.insert({Field, &getStableStorageLocation(Field->getType())});
+ FieldLocs.insert(
+ {Field, &getStableStorageLocation(CallStr, Field->getType())});
return takeOwnership(
std::make_unique<AggregateStorageLocation>(Type, std::move(FieldLocs)));
}
@@ -40,30 +42,39 @@
}
StorageLocation &
-DataflowAnalysisContext::getStableStorageLocation(const VarDecl &D) {
- if (auto *Loc = getStorageLocation(D))
+DataflowAnalysisContext::getStableStorageLocation(const CallString &CallStr,
+ const VarDecl &D) {
+ StorageFrame &Frame = getFrame(CallStr);
+ if (auto *Loc = Frame.getStorageLocation(D))
return *Loc;
- auto &Loc = getStableStorageLocation(D.getType());
- setStorageLocation(D, Loc);
+ auto &Loc = getStableStorageLocation(CallStr, D.getType());
+ Frame.setStorageLocation(D, Loc);
return Loc;
}
StorageLocation &
-DataflowAnalysisContext::getStableStorageLocation(const Expr &E) {
- if (auto *Loc = getStorageLocation(E))
+DataflowAnalysisContext::getStableStorageLocation(const CallString &CallStr,
+ const Expr &E) {
+ StorageFrame &Frame = getFrame(CallStr);
+ if (auto *Loc = Frame.getStorageLocation(E))
return *Loc;
- auto &Loc = getStableStorageLocation(E.getType());
- setStorageLocation(E, Loc);
+ auto &Loc = getStableStorageLocation(CallStr, E.getType());
+ Frame.setStorageLocation(E, Loc);
return Loc;
}
+StorageFrame &DataflowAnalysisContext::getFrame(const CallString &CallStr) {
+ return Frames.try_emplace(CallStr).first->second;
+}
+
PointerValue &
DataflowAnalysisContext::getOrCreateNullPointerValue(QualType PointeeType) {
auto CanonicalPointeeType =
PointeeType.isNull() ? PointeeType : PointeeType.getCanonicalType();
auto Res = NullPointerVals.try_emplace(CanonicalPointeeType, nullptr);
if (Res.second) {
- auto &PointeeLoc = getStableStorageLocation(CanonicalPointeeType);
+ // We arbitrarily put this in the outermost context; doesn't really matter.
+ auto &PointeeLoc = getStableStorageLocation({}, CanonicalPointeeType);
Res.first->second =
&takeOwnership(std::make_unique<PointerValue>(PointeeLoc));
}
Index: clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
===================================================================
--- clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
+++ clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
@@ -143,6 +143,10 @@
/// Each argument of `Call` must already have a `StorageLocation`.
Environment pushCall(const CallExpr *Call) const;
+ /// Moves gathered information back into `this` from a `CalleeEnv` created via
+ /// `pushCall`.
+ void popCall(const Environment &CalleeEnv);
+
/// Returns true if and only if the environment is equivalent to `Other`, i.e
/// the two environments:
/// - have the same mappings from declarations to storage locations,
@@ -362,6 +366,7 @@
// `DACtx` is not null and not owned by this object.
DataflowAnalysisContext *DACtx;
+ CallString CallStr;
// Maps from program declarations and statements to storage locations that are
// assigned to them. Unlike the maps in `DataflowAnalysisContext`, these
Index: clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h
===================================================================
--- clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h
+++ clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h
@@ -25,6 +25,7 @@
#include "llvm/ADT/DenseSet.h"
#include "llvm/Support/Compiler.h"
#include <cassert>
+#include <map>
#include <memory>
#include <type_traits>
#include <utility>
@@ -49,60 +50,12 @@
/// Returns the set of all fields in the type.
llvm::DenseSet<const FieldDecl *> getObjectFields(QualType Type);
-/// Owns objects that encompass the state of a program and stores context that
-/// is used during dataflow analysis.
-class DataflowAnalysisContext {
-public:
- /// Constructs a dataflow analysis context.
- ///
- /// Requirements:
- ///
- /// `S` must not be null.
- DataflowAnalysisContext(std::unique_ptr<Solver> S)
- : S(std::move(S)), TrueVal(createAtomicBoolValue()),
- FalseVal(createAtomicBoolValue()) {
- assert(this->S != nullptr);
- }
-
- /// Takes ownership of `Loc` and returns a reference to it.
- ///
- /// Requirements:
- ///
- /// `Loc` must not be null.
- template <typename T>
- typename std::enable_if<std::is_base_of<StorageLocation, T>::value, T &>::type
- takeOwnership(std::unique_ptr<T> Loc) {
- assert(Loc != nullptr);
- Locs.push_back(std::move(Loc));
- return *cast<T>(Locs.back().get());
- }
-
- /// Takes ownership of `Val` and returns a reference to it.
- ///
- /// Requirements:
- ///
- /// `Val` must not be null.
- template <typename T>
- typename std::enable_if<std::is_base_of<Value, T>::value, T &>::type
- takeOwnership(std::unique_ptr<T> Val) {
- assert(Val != nullptr);
- Vals.push_back(std::move(Val));
- return *cast<T>(Vals.back().get());
- }
-
- /// Returns a stable storage location appropriate for `Type`.
- ///
- /// Requirements:
- ///
- /// `Type` must not be null.
- StorageLocation &getStableStorageLocation(QualType Type);
-
- /// Returns a stable storage location for `D`.
- StorageLocation &getStableStorageLocation(const VarDecl &D);
-
- /// Returns a stable storage location for `E`.
- StorageLocation &getStableStorageLocation(const Expr &E);
+/// A sequence of method calls that resembles the call stack.
+using CallString = std::vector<const CallExpr *>;
+/// Holds stable storage locations in the context of a particular `CallString`.
+class StorageFrame {
+public:
/// Assigns `Loc` as the storage location of `D`.
///
/// Requirements:
@@ -154,6 +107,77 @@
return ThisPointeeLoc;
}
+private:
+ // Maps from program declarations and statements to storage locations that are
+ // assigned to them. These assignments are global (aggregated across all basic
+ // blocks) and are used to produce stable storage locations when the same
+ // basic blocks are evaluated multiple times. The storage locations that are
+ // in scope for a particular basic block are stored in `Environment`.
+ llvm::DenseMap<const ValueDecl *, StorageLocation *> DeclToLoc;
+ llvm::DenseMap<const Expr *, StorageLocation *> ExprToLoc;
+
+ StorageLocation *ThisPointeeLoc = nullptr;
+};
+
+/// Owns objects that encompass the state of a program and stores context that
+/// is used during dataflow analysis.
+class DataflowAnalysisContext {
+public:
+ /// Constructs a dataflow analysis context.
+ ///
+ /// Requirements:
+ ///
+ /// `S` must not be null.
+ DataflowAnalysisContext(std::unique_ptr<Solver> S)
+ : S(std::move(S)), TrueVal(createAtomicBoolValue()),
+ FalseVal(createAtomicBoolValue()) {
+ assert(this->S != nullptr);
+ }
+
+ /// Takes ownership of `Loc` and returns a reference to it.
+ ///
+ /// Requirements:
+ ///
+ /// `Loc` must not be null.
+ template <typename T>
+ typename std::enable_if<std::is_base_of<StorageLocation, T>::value, T &>::type
+ takeOwnership(std::unique_ptr<T> Loc) {
+ assert(Loc != nullptr);
+ Locs.push_back(std::move(Loc));
+ return *cast<T>(Locs.back().get());
+ }
+
+ /// Takes ownership of `Val` and returns a reference to it.
+ ///
+ /// Requirements:
+ ///
+ /// `Val` must not be null.
+ template <typename T>
+ typename std::enable_if<std::is_base_of<Value, T>::value, T &>::type
+ takeOwnership(std::unique_ptr<T> Val) {
+ assert(Val != nullptr);
+ Vals.push_back(std::move(Val));
+ return *cast<T>(Vals.back().get());
+ }
+
+ /// Returns a stable storage location appropriate for `Type`.
+ ///
+ /// Requirements:
+ ///
+ /// `Type` must not be null.
+ StorageLocation &getStableStorageLocation(const CallString &CallStr,
+ QualType Type);
+
+ /// Returns a stable storage location for `D`.
+ StorageLocation &getStableStorageLocation(const CallString &CallStr,
+ const VarDecl &D);
+
+ /// Returns a stable storage location for `E`.
+ StorageLocation &getStableStorageLocation(const CallString &CallStr,
+ const Expr &E);
+
+ StorageFrame &getFrame(const CallString &CallStr);
+
/// Returns a pointer value that represents a null pointer. Calls with
/// `PointeeType` that are canonically equivalent will return the same result.
/// A null `PointeeType` can be used for the pointee of `std::nullptr_t`.
@@ -311,15 +335,7 @@
std::vector<std::unique_ptr<StorageLocation>> Locs;
std::vector<std::unique_ptr<Value>> Vals;
- // Maps from program declarations and statements to storage locations that are
- // assigned to them. These assignments are global (aggregated across all basic
- // blocks) and are used to produce stable storage locations when the same
- // basic blocks are evaluated multiple times. The storage locations that are
- // in scope for a particular basic block are stored in `Environment`.
- llvm::DenseMap<const ValueDecl *, StorageLocation *> DeclToLoc;
- llvm::DenseMap<const Expr *, StorageLocation *> ExprToLoc;
-
- StorageLocation *ThisPointeeLoc = nullptr;
+ std::map<CallString, StorageFrame> Frames;
// Null pointer values, keyed by the canonical pointee type.
//
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
