Author: martinboehme Date: 2023-11-27T14:55:49+01:00 New Revision: 5bd643e1456bd2acc53ac0bf594d285be89a44fe
URL: https://github.com/llvm/llvm-project/commit/5bd643e1456bd2acc53ac0bf594d285be89a44fe DIFF: https://github.com/llvm/llvm-project/commit/5bd643e1456bd2acc53ac0bf594d285be89a44fe.diff LOG: [clang][dataflow] Strengthen widening of boolean values. (#73484) Before we widen to top, we now check if both values can be proved either true or false in their respective environments; if so, widening returns a true or false literal. The idea is that we avoid losing information if posssible. This patch includes a test that fails without this change to widening. This change does mean that we call the SAT solver in more places, but this seems acceptable given the additional precision we gain. In tests on an internal codebase, the number of SAT solver timeouts we observe with Crubit's nullability checker does increase by about 25%. They can be brought back to the previous level by doubling the SAT solver work limit. Added: Modified: clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp clang/unittests/Analysis/FlowSensitive/TransferTest.cpp Removed: ################################################################################ diff --git a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp index 1a38be9c1374f65..525ab188b01b8aa 100644 --- a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp +++ b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp @@ -157,12 +157,25 @@ static Value &widenDistinctValues(QualType Type, Value &Prev, Environment &CurrentEnv, Environment::ValueModel &Model) { // Boolean-model widening. - if (isa<BoolValue>(&Prev)) { - assert(isa<BoolValue>(Current)); - // Widen to Top, because we know they are diff erent values. If previous was - // already Top, re-use that to (implicitly) indicate that no change occured. + if (auto *PrevBool = dyn_cast<BoolValue>(&Prev)) { + // If previous value was already Top, re-use that to (implicitly) indicate + // that no change occurred. if (isa<TopBoolValue>(Prev)) return Prev; + + // We may need to widen to Top, but before we do so, check whether both + // values are implied to be either true or false in the current environment. + // In that case, we can simply return a literal instead. + auto &CurBool = cast<BoolValue>(Current); + bool TruePrev = PrevEnv.proves(PrevBool->formula()); + bool TrueCur = CurrentEnv.proves(CurBool.formula()); + if (TruePrev && TrueCur) + return CurrentEnv.getBoolLiteralValue(true); + if (!TruePrev && !TrueCur && + PrevEnv.proves(PrevEnv.arena().makeNot(PrevBool->formula())) && + CurrentEnv.proves(CurrentEnv.arena().makeNot(CurBool.formula()))) + return CurrentEnv.getBoolLiteralValue(false); + return CurrentEnv.makeTopBoolValue(); } diff --git a/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp b/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp index ade0d202ced2f37..8da55953a329869 100644 --- a/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp +++ b/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp @@ -4167,6 +4167,34 @@ TEST(TransferTest, LoopWithShortCircuitedConditionConverges) { ASSERT_THAT_ERROR(checkDataflowWithNoopAnalysis(Code), llvm::Succeeded()); } +TEST(TransferTest, LoopCanProveInvariantForBoolean) { + // Check that we can prove `b` is always false in the loop. + // This test exercises the logic in `widenDistinctValues()` that preserves + // information if the boolean can be proved to be either true or false in both + // the previous and current iteration. + std::string Code = R"cc( + int return_int(); + void target() { + bool b = return_int() == 0; + if (b) return; + while (true) { + b; + // [[p]] + b = return_int() == 0; + if (b) return; + } + } + )cc"; + runDataflow( + Code, + [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results, + ASTContext &ASTCtx) { + const Environment &Env = getEnvironmentAtAnnotation(Results, "p"); + auto &BVal = getValueForDecl<BoolValue>(ASTCtx, Env, "b"); + EXPECT_TRUE(Env.proves(Env.arena().makeNot(BVal.formula()))); + }); +} + TEST(TransferTest, DoesNotCrashOnUnionThisExpr) { std::string Code = R"( union Union { _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
