Author: Yitzhak Mandelbaum Date: 2023-01-12T20:36:37Z New Revision: d34fbf2d9bf4d372d25087d2ded9573b17ce7632
URL: https://github.com/llvm/llvm-project/commit/d34fbf2d9bf4d372d25087d2ded9573b17ce7632 DIFF: https://github.com/llvm/llvm-project/commit/d34fbf2d9bf4d372d25087d2ded9573b17ce7632.diff LOG: [clang][dataflow] In optional model, implement `widen` and make `compare` sound. This patch includes two related changes: 1. Rewrite `compare` operation to be sound. Current version checks for equality of `isNonEmptyOptional` on both values, judging the values `Same` when the results are equal. While that works when both are true, it is problematic when they are both false, because there are four cases in which that's can occur: both empty, one empty and one unknown (which is two cases), and both unknown. In the latter three cases, it is unsound to judge them `Same`. This patch changes `compare` to explicitly check for case of `both empty` and then judge any other case `Different`. 2. With the change to `compare`, a number of common cases will no longer terminate. So, we also implement widening to properly handle those cases and recover termination. Drive-by: improve performance of `merge` operation. Of the new tests, the code before the patch fails * ReassignValueInLoopToSetUnsafe, and * ReassignValueInLoopToUnknownUnsafe. Differential Revision: https://reviews.llvm.org/D140344 Added: Modified: clang/include/clang/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.h clang/lib/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.cpp clang/unittests/Analysis/FlowSensitive/UncheckedOptionalAccessModelTest.cpp Removed: ################################################################################ diff --git a/clang/include/clang/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.h b/clang/include/clang/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.h index 037858fe752e9..2d52ee5fc846d 100644 --- a/clang/include/clang/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.h +++ b/clang/include/clang/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.h @@ -62,6 +62,9 @@ class UncheckedOptionalAccessModel const Value &Val2, const Environment &Env2, Value &MergedVal, Environment &MergedEnv) override; + Value *widen(QualType Type, Value &Prev, const Environment &PrevEnv, + Value &Current, Environment &CurrentEnv) override; + private: CFGMatchSwitch<TransferState<NoopLattice>> TransferMatchSwitch; }; diff --git a/clang/lib/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.cpp b/clang/lib/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.cpp index 10b9866d5c23c..94e0b513af844 100644 --- a/clang/lib/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.cpp +++ b/clang/lib/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.cpp @@ -27,6 +27,7 @@ #include "clang/Basic/SourceLocation.h" #include "llvm/ADT/StringRef.h" #include "llvm/Support/Casting.h" +#include "llvm/Support/ErrorHandling.h" #include <cassert> #include <memory> #include <utility> @@ -835,7 +836,14 @@ ComparisonResult UncheckedOptionalAccessModel::compare( const Value &Val2, const Environment &Env2) { if (!isOptionalType(Type)) return ComparisonResult::Unknown; - return isNonEmptyOptional(Val1, Env1) == isNonEmptyOptional(Val2, Env2) + bool MustNonEmpty1 = isNonEmptyOptional(Val1, Env1); + bool MustNonEmpty2 = isNonEmptyOptional(Val2, Env2); + if (MustNonEmpty1 && MustNonEmpty2) return ComparisonResult::Same; + // If exactly one is true, then they're diff erent, no reason to check whether + // they're definitely empty. + if (MustNonEmpty1 || MustNonEmpty2) return ComparisonResult::Different; + // Check if they're both definitely empty. + return (isEmptyOptional(Val1, Env1) && isEmptyOptional(Val2, Env2)) ? ComparisonResult::Same : ComparisonResult::Different; } @@ -848,16 +856,48 @@ bool UncheckedOptionalAccessModel::merge(QualType Type, const Value &Val1, Environment &MergedEnv) { if (!isOptionalType(Type)) return true; - + // FIXME: uses same approach as join for `BoolValues`. Requires non-const + // values, though, so will require updating the interface. auto &HasValueVal = MergedEnv.makeAtomicBoolValue(); - if (isNonEmptyOptional(Val1, Env1) && isNonEmptyOptional(Val2, Env2)) + bool MustNonEmpty1 = isNonEmptyOptional(Val1, Env1); + bool MustNonEmpty2 = isNonEmptyOptional(Val2, Env2); + if (MustNonEmpty1 && MustNonEmpty2) MergedEnv.addToFlowCondition(HasValueVal); - else if (isEmptyOptional(Val1, Env1) && isEmptyOptional(Val2, Env2)) + else if ( + // Only make the costly calls to `isEmptyOptional` if we got "unknown" + // (false) for both calls to `isNonEmptyOptional`. + !MustNonEmpty1 && !MustNonEmpty2 && isEmptyOptional(Val1, Env1) && + isEmptyOptional(Val2, Env2)) MergedEnv.addToFlowCondition(MergedEnv.makeNot(HasValueVal)); setHasValue(MergedVal, HasValueVal); return true; } +Value *UncheckedOptionalAccessModel::widen(QualType Type, Value &Prev, + const Environment &PrevEnv, + Value &Current, + Environment &CurrentEnv) { + switch (compare(Type, Prev, PrevEnv, Current, CurrentEnv)) { + case ComparisonResult::Same: + return &Prev; + case ComparisonResult::Different: + if (auto *PrevHasVal = + cast_or_null<BoolValue>(Prev.getProperty("has_value"))) { + if (isa<TopBoolValue>(PrevHasVal)) + return &Prev; + } + if (auto *CurrentHasVal = + cast_or_null<BoolValue>(Current.getProperty("has_value"))) { + if (isa<TopBoolValue>(CurrentHasVal)) + return &Current; + } + return &createOptionalValue(CurrentEnv, CurrentEnv.makeTopBoolValue()); + case ComparisonResult::Unknown: + return nullptr; + } + llvm_unreachable("all cases covered in switch"); +} + UncheckedOptionalAccessDiagnoser::UncheckedOptionalAccessDiagnoser( UncheckedOptionalAccessModelOptions Options) : DiagnoseMatchSwitch(buildDiagnoseMatchSwitch(Options)) {} diff --git a/clang/unittests/Analysis/FlowSensitive/UncheckedOptionalAccessModelTest.cpp b/clang/unittests/Analysis/FlowSensitive/UncheckedOptionalAccessModelTest.cpp index 2d108e8d24832..51bb3aefd09df 100644 --- a/clang/unittests/Analysis/FlowSensitive/UncheckedOptionalAccessModelTest.cpp +++ b/clang/unittests/Analysis/FlowSensitive/UncheckedOptionalAccessModelTest.cpp @@ -2748,19 +2748,6 @@ TEST_P(UncheckedOptionalAccessTest, CorrelatedBranches) { } } )"); - - // FIXME: Add support for operator==. - // ExpectDiagnosticsFor(R"( - // #include "unchecked_optional_access_test.h" - // - // void target($ns::$optional<int> opt1, $ns::$optional<int> opt2) { - // if (opt1 == opt2) { - // if (opt1.has_value()) { - // opt2.value(); - // } - // } - // } - // )"); } TEST_P(UncheckedOptionalAccessTest, JoinDistinctValues) { @@ -2846,7 +2833,7 @@ TEST_P(UncheckedOptionalAccessTest, JoinDistinctValues) { )code"); } -TEST_P(UncheckedOptionalAccessTest, ReassignValueInLoop) { +TEST_P(UncheckedOptionalAccessTest, AccessValueInLoop) { ExpectDiagnosticsFor(R"( #include "unchecked_optional_access_test.h" @@ -2857,7 +2844,9 @@ TEST_P(UncheckedOptionalAccessTest, ReassignValueInLoop) { } } )"); +} +TEST_P(UncheckedOptionalAccessTest, ReassignValueInLoopWithCheckSafe) { ExpectDiagnosticsFor(R"( #include "unchecked_optional_access_test.h" @@ -2871,7 +2860,9 @@ TEST_P(UncheckedOptionalAccessTest, ReassignValueInLoop) { } } )"); +} +TEST_P(UncheckedOptionalAccessTest, ReassignValueInLoopNoCheckUnsafe) { ExpectDiagnosticsFor( R"( #include "unchecked_optional_access_test.h" @@ -2885,7 +2876,60 @@ TEST_P(UncheckedOptionalAccessTest, ReassignValueInLoop) { } } )"); +} + +TEST_P(UncheckedOptionalAccessTest, ReassignValueInLoopToUnsetUnsafe) { + ExpectDiagnosticsFor( + R"( + #include "unchecked_optional_access_test.h" + + void target() { + $ns::$optional<int> opt = 3; + while (Make<bool>()) + opt = $ns::nullopt; + $ns::$optional<int> opt2 = $ns::nullopt; + if (opt.has_value()) + opt2 = $ns::$optional<int>(3); + opt2.value(); // [[unsafe]] + } + )"); +} + +TEST_P(UncheckedOptionalAccessTest, ReassignValueInLoopToSetUnsafe) { + ExpectDiagnosticsFor( + R"( + #include "unchecked_optional_access_test.h" + + void target() { + $ns::$optional<int> opt = $ns::nullopt; + while (Make<bool>()) + opt = $ns::$optional<int>(3); + $ns::$optional<int> opt2 = $ns::nullopt; + if (!opt.has_value()) + opt2 = $ns::$optional<int>(3); + opt2.value(); // [[unsafe]] + } + )"); +} + +TEST_P(UncheckedOptionalAccessTest, ReassignValueInLoopToUnknownUnsafe) { + ExpectDiagnosticsFor( + R"( + #include "unchecked_optional_access_test.h" + + void target() { + $ns::$optional<int> opt = $ns::nullopt; + while (Make<bool>()) + opt = Make<$ns::$optional<int>>(); + $ns::$optional<int> opt2 = $ns::nullopt; + if (!opt.has_value()) + opt2 = $ns::$optional<int>(3); + opt2.value(); // [[unsafe]] + } + )"); +} +TEST_P(UncheckedOptionalAccessTest, ReassignValueInLoopBadConditionUnsafe) { ExpectDiagnosticsFor( R"( #include "unchecked_optional_access_test.h" _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
