This revision was landed with ongoing or failed builds.
This revision was automatically updated to reflect the committed changes.
Closed by commit rGbbcf11f5af98: [clang][dataflow] Weaken abstract comparison
to enable loop termination. (authored by ymandel).
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D123586/new/
https://reviews.llvm.org/D123586
Files:
clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
Index: clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
===================================================================
--- clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
+++ clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
@@ -365,8 +365,10 @@
if (HasValue2 == nullptr)
return false;
- assert(HasValue1 != HasValue2);
- cast<StructValue>(&MergedVal)->setProperty("has_value", HasValueTop);
+ if (HasValue1 == HasValue2)
+ cast<StructValue>(&MergedVal)->setProperty("has_value", *HasValue1);
+ else
+ cast<StructValue>(&MergedVal)->setProperty("has_value", HasValueTop);
return true;
}
Index: clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
===================================================================
--- clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
+++ clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
@@ -2944,4 +2944,71 @@
});
}
+TEST_F(TransferTest, LoopWithAssignmentConverges) {
+ std::string Code = R"(
+
+ bool &foo();
+
+ void target() {
+ do {
+ bool Bar = foo();
+ if (Bar) break;
+ (void)Bar;
+ /*[[p]]*/
+ } while (true);
+ }
+ )";
+ // 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, [](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 *BarDecl = findValueDecl(ASTCtx, "Bar");
+ ASSERT_THAT(BarDecl, NotNull());
+
+ auto &BarVal = *cast<BoolValue>(Env.getValue(*BarDecl, SkipPast::None));
+ EXPECT_TRUE(Env.flowConditionImplies(Env.makeNot(BarVal)));
+ });
+}
+
+TEST_F(TransferTest, LoopWithReferenceAssignmentConverges) {
+ std::string Code = R"(
+
+ bool &foo();
+
+ void target() {
+ do {
+ bool& Bar = foo();
+ if (Bar) break;
+ (void)Bar;
+ /*[[p]]*/
+ } while (true);
+ }
+ )";
+ // 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, [](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 *BarDecl = findValueDecl(ASTCtx, "Bar");
+ ASSERT_THAT(BarDecl, NotNull());
+
+ auto &BarVal =
+ *cast<BoolValue>(Env.getValue(*BarDecl, SkipPast::Reference));
+ EXPECT_TRUE(Env.flowConditionImplies(Env.makeNot(BarVal)));
+ });
+}
+
} // namespace
Index: clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
===================================================================
--- clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
+++ clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
@@ -59,7 +59,8 @@
if (auto *IndVal1 = dyn_cast<IndirectionValue>(Val1)) {
auto *IndVal2 = cast<IndirectionValue>(Val2);
assert(IndVal1->getKind() == IndVal2->getKind());
- return &IndVal1->getPointeeLoc() == &IndVal2->getPointeeLoc();
+ if (&IndVal1->getPointeeLoc() == &IndVal2->getPointeeLoc())
+ return true;
}
return Model.compareEquivalent(Type, *Val1, Env1, *Val2, Env2);
@@ -88,6 +89,9 @@
// depends on `FC1` and `FC2`) and modify `flowConditionImplies` to construct
// a formula that includes the bi-conditionals for all flow condition atoms in
// the transitive set, before invoking the solver.
+ //
+ // FIXME: Does not work for backedges, since the two (or more) paths will not
+ // have mutually exclusive conditions.
if (auto *Expr1 = dyn_cast<BoolValue>(Val1)) {
for (BoolValue *Constraint : Env1.getFlowConditionConstraints()) {
Expr1 = &Env1.makeAnd(*Expr1, *Constraint);
@@ -285,9 +289,7 @@
if (MemberLocToStruct != Other.MemberLocToStruct)
return false;
- if (LocToVal.size() != Other.LocToVal.size())
- return false;
-
+ // Compare the contents for the intersection of their domains.
for (auto &Entry : LocToVal) {
const StorageLocation *Loc = Entry.first;
assert(Loc != nullptr);
@@ -297,7 +299,7 @@
auto It = Other.LocToVal.find(Loc);
if (It == Other.LocToVal.end())
- return false;
+ continue;
assert(It->second != nullptr);
if (!equivalentValues(Loc->getType(), Val, *this, It->second, Other, Model))
@@ -346,8 +348,7 @@
continue;
assert(It->second != nullptr);
- if (equivalentValues(Loc->getType(), Val, *this, It->second, Other,
- Model)) {
+ if (Val == It->second) {
LocToVal.insert({Loc, Val});
continue;
}
Index: clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
===================================================================
--- clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
+++ clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
@@ -77,7 +77,11 @@
const Environment &Env2) {
// FIXME: Consider adding QualType to StructValue and removing the Type
// argument here.
- return false;
+ //
+ // FIXME: default to a sound comparison and/or expand the comparison logic
+ // built into the framework to support broader forms of equivalence than
+ // strict pointer equality.
+ return true;
}
/// Modifies `MergedVal` to approximate both `Val1` and `Val2`. This could
@@ -101,7 +105,7 @@
const Environment &Env1, const Value &Val2,
const Environment &Env2, Value &MergedVal,
Environment &MergedEnv) {
- return false;
+ return true;
}
};
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
