This is an archive of the discontinued LLVM Phabricator instance.

Differential D128183

[clang][dataflow] Extend flow condition in the body of a do/while loop
ClosedPublic

Authored by sgatev on Jun 20 2022, 4:10 AM.

Details

Reviewers
ymandel
xazax.hun
gribozavr2
Commits
rGe363c5963dc3: [clang][dataflow] Extend flow condition in the body of a do/while loop
Summary

Extend flow condition in the body of a do/while loop.

Diff Detail

Event Timeline

sgatev created this revision.Jun 20 2022, 4:10 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 20 2022, 4:10 AM
Herald added subscribers: martong, tschuett, rnkovacs. · View Herald Transcript
sgatev requested review of this revision.Jun 20 2022, 4:10 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 20 2022, 4:10 AM
Harbormaster completed remote builds in B170822: Diff 438336.Jun 20 2022, 4:10 AM
gribozavr2 accepted this revision.Jun 20 2022, 8:01 AM
gribozavr2 added inline comments.
clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
3700

Can we infer that after the loop bar is false?

This revision is now accepted and ready to land.Jun 20 2022, 8:01 AM
sgatev updated this revision to Diff 438427.Jun 20 2022, 9:17 AM

Address comments.

sgatev marked an inline comment as done.Jun 20 2022, 9:18 AM
sgatev added inline comments.
clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
3700

Yes!

xazax.hun accepted this revision.Jun 20 2022, 9:32 AM
gribozavr2 accepted this revision.Jun 20 2022, 10:15 AM
This revision was landed with ongoing or failed builds.Jun 20 2022, 10:31 AM
Closed by commit rGe363c5963dc3: [clang][dataflow] Extend flow condition in the body of a do/while loop (authored by sgatev). · Explain Why
This revision was automatically updated to reflect the committed changes.
sgatev marked an inline comment as done.
sgatev added a commit: rGe363c5963dc3: [clang][dataflow] Extend flow condition in the body of a do/while loop.
Harbormaster completed remote builds in B170891: Diff 438427.Jun 20 2022, 10:48 AM

Revision Contents

PathSize
clang/
lib/
Analysis/
FlowSensitive/
9 lines
6 lines
unittests/
Analysis/
FlowSensitive/
121 lines

Diff 438435

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

Show First 20 Lines • Show All 81 Lines • ▼ Show 20 Linesstatic Value *mergeDistinctValues(QualType Type, Value *Val1,
Environment::ValueModel &Model) { Environment::ValueModel &Model) {
// Join distinct boolean values preserving information about the constraints // Join distinct boolean values preserving information about the constraints
// in the respective path conditions. // in the respective path conditions.
// //
// FIXME: Does not work for backedges, since the two (or more) paths will not // FIXME: Does not work for backedges, since the two (or more) paths will not
// have mutually exclusive conditions. // have mutually exclusive conditions.
if (auto *Expr1 = dyn_cast<BoolValue>(Val1)) { if (auto *Expr1 = dyn_cast<BoolValue>(Val1)) {
auto *Expr2 = cast<BoolValue>(Val2); auto *Expr2 = cast<BoolValue>(Val2);
return &Env1.makeOr(Env1.makeAnd(Env1.getFlowConditionToken(), *Expr1), auto &MergedVal = MergedEnv.makeAtomicBoolValue();
Env1.makeAnd(Env2.getFlowConditionToken(), *Expr2)); MergedEnv.addToFlowCondition(MergedEnv.makeOr(
MergedEnv.makeAnd(Env1.getFlowConditionToken(),
MergedEnv.makeIff(MergedVal, *Expr1)),
MergedEnv.makeAnd(Env2.getFlowConditionToken(),
MergedEnv.makeIff(MergedVal, *Expr2))));
return &MergedVal;
} }
// FIXME: add unit tests that cover this statement. // FIXME: add unit tests that cover this statement.
if (areEquivalentIndirectionValues(Val1, Val2)) { if (areEquivalentIndirectionValues(Val1, Val2)) {
return Val1; return Val1;
} }
// FIXME: Consider destroying `MergedValue` immediately if `ValueModel::merge` // FIXME: Consider destroying `MergedValue` immediately if `ValueModel::merge`
▲ Show 20 Lines • Show All 449 Lines • Show Last 20 Lines

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

Show First 20 Lines • Show All 83 Lines • ▼ Show 20 Linespublic:
} }
void VisitWhileStmt(const WhileStmt *S) { void VisitWhileStmt(const WhileStmt *S) {
auto *Cond = S->getCond(); auto *Cond = S->getCond();
assert(Cond != nullptr); assert(Cond != nullptr);
extendFlowCondition(*Cond); extendFlowCondition(*Cond);
} }
void VisitDoStmt(const DoStmt *S) {
auto *Cond = S->getCond();
assert(Cond != nullptr);
extendFlowCondition(*Cond);
}
void VisitForStmt(const ForStmt *S) { void VisitForStmt(const ForStmt *S) {
auto *Cond = S->getCond(); auto *Cond = S->getCond();
assert(Cond != nullptr); assert(Cond != nullptr);
extendFlowCondition(*Cond); extendFlowCondition(*Cond);
} }
void VisitBinaryOperator(const BinaryOperator *S) { void VisitBinaryOperator(const BinaryOperator *S) {
assert(S->getOpcode() == BO_LAnd || S->getOpcode() == BO_LOr); assert(S->getOpcode() == BO_LAnd || S->getOpcode() == BO_LOr);
▲ Show 20 Lines • Show All 289 Lines • Show Last 20 Lines

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

Show First 20 Lines • Show All 3,622 Lines • ▼ Show 20 Lines runDataflow(
}); });
} }
TEST_F(TransferTest, WhileStmtBranchExtendsFlowCondition) { TEST_F(TransferTest, WhileStmtBranchExtendsFlowCondition) {
std::string Code = R"( std::string Code = R"(
void target(bool Foo) { void target(bool Foo) {
while (Foo) { while (Foo) {
(void)0; (void)0;
// [[while_branch]] // [[loop_body]]
} }
(void)0;
// [[after_loop]]
} }
)"; )";
runDataflow(Code, runDataflow(
[](llvm::ArrayRef< Code, [](llvm::ArrayRef<
std::pair<std::string, DataflowAnalysisState<NoopLattice>>> std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
Results, Results,
ASTContext &ASTCtx) { ASTContext &ASTCtx) {
ASSERT_THAT(Results, ElementsAre(Pair("while_branch", _))); ASSERT_THAT(Results,
const Environment &Env = Results[0].second.Env; ElementsAre(Pair("after_loop", _), Pair("loop_body", _)));
const Environment &LoopBodyEnv = Results[1].second.Env;
const Environment &AfterLoopEnv = Results[0].second.Env;
const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
ASSERT_THAT(FooDecl, NotNull());
BoolValue &LoopBodyFooVal =
*cast<BoolValue>(LoopBodyEnv.getValue(*FooDecl, SkipPast::None));
EXPECT_TRUE(LoopBodyEnv.flowConditionImplies(LoopBodyFooVal));
BoolValue &AfterLoopFooVal =
*cast<BoolValue>(AfterLoopEnv.getValue(*FooDecl, SkipPast::None));
EXPECT_TRUE(AfterLoopEnv.flowConditionImplies(
AfterLoopEnv.makeNot(AfterLoopFooVal)));
});
}
TEST_F(TransferTest, DoWhileStmtBranchExtendsFlowCondition) {
std::string Code = R"(
void target(bool Foo) {
bool Bar = true;
do {
(void)0;
// [[loop_body]]
Bar = false;
} while (Foo);
(void)0;
// [[after_loop]]
}
)";
runDataflow(
Code, [](llvm::ArrayRef<
std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
Results,
ASTContext &ASTCtx) {
ASSERT_THAT(Results,
ElementsAre(Pair("after_loop", _), Pair("loop_body", _)));
const Environment &LoopBodyEnv = Results[1].second.Env;
const Environment &AfterLoopEnv = Results[0].second.Env;
const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo"); const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
ASSERT_THAT(FooDecl, NotNull()); ASSERT_THAT(FooDecl, NotNull());
BoolValue &FooVal = const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
*cast<BoolValue>(Env.getValue(*FooDecl, SkipPast::None)); ASSERT_THAT(BarDecl, NotNull());
EXPECT_TRUE(Env.flowConditionImplies(FooVal));
BoolValue &LoopBodyFooVal =
*cast<BoolValue>(LoopBodyEnv.getValue(*FooDecl, SkipPast::None));
BoolValue &LoopBodyBarVal =
*cast<BoolValue>(LoopBodyEnv.getValue(*BarDecl, SkipPast::None));
EXPECT_TRUE(LoopBodyEnv.flowConditionImplies(
LoopBodyEnv.makeOr(LoopBodyBarVal, LoopBodyFooVal)));
BoolValue &AfterLoopFooVal =
*cast<BoolValue>(AfterLoopEnv.getValue(*FooDecl, SkipPast::None));
BoolValue &AfterLoopBarVal =
*cast<BoolValue>(AfterLoopEnv.getValue(*BarDecl, SkipPast::None));
gribozavr2Unsubmitted
Done
ReplyInline Actions

Can we infer that after the loop bar is false?

gribozavr2: Can we infer that after the loop bar is false?
sgatevAuthorUnsubmitted
Done
ReplyInline Actions

Yes!

sgatev: Yes!
EXPECT_TRUE(AfterLoopEnv.flowConditionImplies(
AfterLoopEnv.makeNot(AfterLoopFooVal)));
EXPECT_TRUE(AfterLoopEnv.flowConditionImplies(
AfterLoopEnv.makeNot(AfterLoopBarVal)));
}); });
} }
TEST_F(TransferTest, ForStmtBranchExtendsFlowCondition) { TEST_F(TransferTest, ForStmtBranchExtendsFlowCondition) {
std::string Code = R"( std::string Code = R"(
void target(bool Foo) { void target(bool Foo) {
for (; Foo;) { for (; Foo;) {
(void)0; (void)0;
// [[for_branch]] // [[loop_body]]
} }
(void)0;
// [[after_loop]]
} }
)"; )";
runDataflow(Code, runDataflow(
[](llvm::ArrayRef< Code, [](llvm::ArrayRef<
std::pair<std::string, DataflowAnalysisState<NoopLattice>>> std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
Results, Results,
ASTContext &ASTCtx) { ASTContext &ASTCtx) {
ASSERT_THAT(Results, ElementsAre(Pair("for_branch", _))); ASSERT_THAT(Results,
const Environment &Env = Results[0].second.Env; ElementsAre(Pair("after_loop", _), Pair("loop_body", _)));
const Environment &LoopBodyEnv = Results[1].second.Env;
const Environment &AfterLoopEnv = Results[0].second.Env;
const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo"); const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
ASSERT_THAT(FooDecl, NotNull()); ASSERT_THAT(FooDecl, NotNull());
BoolValue &FooVal = BoolValue &LoopBodyFooVal =
*cast<BoolValue>(Env.getValue(*FooDecl, SkipPast::None)); *cast<BoolValue>(LoopBodyEnv.getValue(*FooDecl, SkipPast::None));
EXPECT_TRUE(Env.flowConditionImplies(FooVal)); EXPECT_TRUE(LoopBodyEnv.flowConditionImplies(LoopBodyFooVal));
BoolValue &AfterLoopFooVal =
*cast<BoolValue>(AfterLoopEnv.getValue(*FooDecl, SkipPast::None));
EXPECT_TRUE(AfterLoopEnv.flowConditionImplies(
AfterLoopEnv.makeNot(AfterLoopFooVal)));
}); });
} }
} // namespace } // namespace