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 only entries in `ExprToLoc` that will be read by a different block are the
direct children of the block terminator (if one exists). For the purposes of
determining whether `ExprToLoc` has converged, it is therefore sufficient to
look at these entries, as any differences in other entries will not be seen by
other blocks.
The other entries in `ExprToLoc` are only read during processing of the block
that contains the corresponding expressions. To be clear, these entries can
affect the results of the block, but only indirectly, in one of two ways:
- If they are indirect descendants of the terminator and therefore affect the
values of the terminator's direct children.
- If they affect the entries in one of the other mappings in `Environment`.
Before this patch, we were comparing all entries in `ExprToLoc`, even if they
were never accessed by other blocks, which could cause non-convergence. This
patch adds two tests that demonstrate this; they do not converge without the
other changes in this patch.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D156658
Files:
clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.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
@@ -3836,6 +3836,58 @@
});
}
+TEST(TransferTest, LoopDereferencingChangingPointerConverges) {
+ std::string Code = R"cc(
+ bool some_condition();
+
+ void target(int i1, int i2) {
+ int *p = &i1;
+ while (true) {
+ (void)*p;
+ if (some_condition())
+ p = &i1;
+ else
+ p = &i2;
+ }
+ }
+ )cc";
+ // The key property that we are verifying is implicit in `runDataflow` --
+ // namely, that the analysis succeeds, rather than hitting the maximum number
+ // of iterations.
+ runDataflow(
+ Code,
+ [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
+ ASTContext &ASTCtx) {});
+}
+
+TEST(TransferTest, LoopDereferencingChangingRecordPointerConverges) {
+ std::string Code = R"cc(
+ struct Lookup {
+ int x;
+ };
+
+ bool some_condition();
+
+ void target(Lookup l1, Lookup l2) {
+ Lookup *l = &l1;
+ while (true) {
+ (void)l->x;
+ if (some_condition())
+ l = &l1;
+ else
+ l = &l2;
+ }
+ }
+ )cc";
+ // The key property that we are verifying is implicit in `runDataflow` --
+ // namely, that the analysis succeeds, rather than hitting the maximum number
+ // of iterations.
+ runDataflow(
+ Code,
+ [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
+ ASTContext &ASTCtx) {});
+}
+
TEST(TransferTest, DoesNotCrashOnUnionThisExpr) {
std::string Code = R"(
union Union {
Index: clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
===================================================================
--- clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
+++ clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
@@ -574,7 +574,8 @@
}
} else if (Analysis.isEqualTypeErased(OldBlockState->Lattice,
NewBlockState.Lattice) &&
- OldBlockState->Env.equivalentTo(NewBlockState.Env, Analysis)) {
+ OldBlockState->Env.equivalentTo(NewBlockState.Env, Analysis,
+ Block->getTerminatorStmt())) {
// The state of `Block` didn't change after transfer so there's no need
// to revisit its successors.
AC.Log.blockConverged();
Index: clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
===================================================================
--- clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
+++ clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
@@ -414,8 +414,33 @@
}
}
+static bool exprToLocEquivalent(const Environment &Env1,
+ const Environment &Env2,
+ const Stmt *Terminator) {
+ if (Terminator == nullptr)
+ return true;
+
+ for (const Stmt *Child : Terminator->children()) {
+ auto *E = dyn_cast<Expr>(Child);
+ if (E == nullptr)
+ continue;
+
+ if (E->isGLValue()) {
+ if (Env1.getStorageLocationStrict(*E) !=
+ Env2.getStorageLocationStrict(*E))
+ return false;
+ } else {
+ if (Env1.getValue(*E) != Env2.getValue(*E))
+ return false;
+ }
+ }
+
+ return true;
+}
+
bool Environment::equivalentTo(const Environment &Other,
- Environment::ValueModel &Model) const {
+ Environment::ValueModel &Model,
+ const Stmt *Terminator) const {
assert(DACtx == Other.DACtx);
if (ReturnVal != Other.ReturnVal)
@@ -430,7 +455,7 @@
if (DeclToLoc != Other.DeclToLoc)
return false;
- if (ExprToLoc != Other.ExprToLoc)
+ if (!exprToLocEquivalent(*this, Other, Terminator))
return false;
// Compare the contents for the intersection of their domains.
Index: clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
===================================================================
--- clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
+++ clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
@@ -208,18 +208,31 @@
void popCall(const CallExpr *Call, const Environment &CalleeEnv);
void popCall(const CXXConstructExpr *Call, const Environment &CalleeEnv);
- /// Returns true if and only if the environment is equivalent to `Other`, i.e
- /// the two environments:
+ /// Returns true if and only if the environment for a particular CFG block is
+ /// equivalent to `Other`, i.e the two environments:
/// - have the same mappings from declarations to storage locations,
- /// - have the same mappings from expressions to storage locations,
+ /// - have the same mappings from expressions accessed outside the block to
+ // storage locations,
/// - have the same or equivalent (according to `Model`) values assigned to
/// the same storage locations.
///
+ /// Note that the expressions accessed outside the block are exactly the
+ /// children of the block terminator. `Terminator` should be this block
+ /// terminator, or null if the block does not have a terminator.
+ ///
+ /// The storage locations for all other expressions are only accessed while
+ /// processing the block. They can still affect the results of the block, but
+ /// only indirectly, in one of two ways:
+ /// - If they are indirect descendants of the terminator and therefore affect
+ /// the values of the terminator's direct children.
+ /// - If they affect the entries in one of the other mappings.
+ ///
/// Requirements:
///
- /// `Other` and `this` must use the same `DataflowAnalysisContext`.
- bool equivalentTo(const Environment &Other,
- Environment::ValueModel &Model) const;
+ /// `Other` and `this` must be environments for the same block and must use
+ /// the same `DataflowAnalysisContext`.
+ bool equivalentTo(const Environment &Other, Environment::ValueModel &Model,
+ const Stmt *Terminator) const;
/// Joins two environments by taking the intersection of storage locations and
/// values that are stored in them. Distinct values that are assigned to the
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
