diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h --- a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h +++ b/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 diff --git a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp --- a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp +++ b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp @@ -414,8 +414,45 @@ } } +static bool exprToLocEquivalent(const Environment &Env1, + const Environment &Env2, const Stmt *Terminator, + Environment::ValueModel &Model) { + if (Terminator == nullptr) + return true; + + for (const Stmt *Child : Terminator->children()) { + auto *E = dyn_cast(Child); + if (E == nullptr) + continue; + + if (E->isGLValue()) { + if (Env1.getStorageLocationStrict(*E) != + Env2.getStorageLocationStrict(*E)) + return false; + } else { + // For prvalues, locations don't matter -- just look at whether they map + // to equivalent values. + Value *Val1 = Env1.getValue(*E); + Value *Val2 = Env2.getValue(*E); + + if (Val1 == nullptr || Val2 == nullptr) { + if (Val1 == nullptr && Val2 == nullptr) + continue; + return false; + } + + if (!areEquivalentValues(*Val1, *Val2) && + !compareDistinctValues(E->getType(), *Val1, Env1, *Val2, Env2, Model)) + 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 +467,7 @@ if (DeclToLoc != Other.DeclToLoc) return false; - if (ExprToLoc != Other.ExprToLoc) + if (!exprToLocEquivalent(*this, Other, Terminator, Model)) return false; // Compare the contents for the intersection of their domains. diff --git a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp --- a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp +++ b/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(); diff --git a/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp b/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp --- a/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp +++ b/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> &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> &Results, + ASTContext &ASTCtx) {}); +} + TEST(TransferTest, DoesNotCrashOnUnionThisExpr) { std::string Code = R"( union Union {