1040 lines · cpp
1//===- unittests/Analysis/FlowSensitive/SignAnalysisTest.cpp --===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file defines a simplistic version of Sign Analysis as a demo of a10// forward, monotonic dataflow analysis. The implementation uses 3 boolean11// values to represent the sign lattice (negative, zero, positive). In12// practice, 2 booleans would be enough, however, this approach has the13// advantage of clarity over the optimized solution.14//15//===----------------------------------------------------------------------===//16 17#include "TestingSupport.h"18#include "clang/ASTMatchers/ASTMatchFinder.h"19#include "clang/ASTMatchers/ASTMatchers.h"20#include "clang/Analysis/FlowSensitive/CFGMatchSwitch.h"21#include "clang/Analysis/FlowSensitive/DataflowAnalysis.h"22#include "clang/Analysis/FlowSensitive/NoopLattice.h"23#include "llvm/ADT/StringRef.h"24#include "llvm/Testing/Annotations/Annotations.h"25#include "llvm/Testing/Support/Error.h"26#include "gtest/gtest.h"27#include <memory>28 29namespace {30 31using namespace clang;32using namespace dataflow;33using namespace ast_matchers;34using namespace test;35using ::testing::UnorderedElementsAre;36 37enum class Sign : int { Negative, Zero, Positive };38 39Sign getSign(int64_t V) {40 return V == 0 ? Sign::Zero : (V < 0 ? Sign::Negative : Sign::Positive);41}42 43using LatticeTransferState = TransferState<NoopLattice>;44 45constexpr char kVar[] = "var";46 47void initNegative(Value &Val, Environment &Env) {48 Val.setProperty("neg", Env.getBoolLiteralValue(true));49 Val.setProperty("zero", Env.getBoolLiteralValue(false));50 Val.setProperty("pos", Env.getBoolLiteralValue(false));51}52void initPositive(Value &Val, Environment &Env) {53 Val.setProperty("neg", Env.getBoolLiteralValue(false));54 Val.setProperty("zero", Env.getBoolLiteralValue(false));55 Val.setProperty("pos", Env.getBoolLiteralValue(true));56}57void initZero(Value &Val, Environment &Env) {58 Val.setProperty("neg", Env.getBoolLiteralValue(false));59 Val.setProperty("zero", Env.getBoolLiteralValue(true));60 Val.setProperty("pos", Env.getBoolLiteralValue(false));61}62 63// The boolean properties that are associated to a Value. If a property is not64// set then these are null pointers, otherwise, the pointed BoolValues are65// owned by the Environment.66struct SignProperties {67 BoolValue *Neg, *Zero, *Pos;68};69void setSignProperties(Value &Val, const SignProperties &Ps) {70 Val.setProperty("neg", *Ps.Neg);71 Val.setProperty("zero", *Ps.Zero);72 Val.setProperty("pos", *Ps.Pos);73}74SignProperties initUnknown(Value &Val, Environment &Env) {75 SignProperties Ps{&Env.makeAtomicBoolValue(), &Env.makeAtomicBoolValue(),76 &Env.makeAtomicBoolValue()};77 setSignProperties(Val, Ps);78 return Ps;79}80SignProperties getSignProperties(const Value &Val, const Environment &Env) {81 return {dyn_cast_or_null<BoolValue>(Val.getProperty("neg")),82 dyn_cast_or_null<BoolValue>(Val.getProperty("zero")),83 dyn_cast_or_null<BoolValue>(Val.getProperty("pos"))};84}85 86void transferUninitializedInt(const DeclStmt *D,87 const MatchFinder::MatchResult &M,88 LatticeTransferState &State) {89 const auto *Var = M.Nodes.getNodeAs<clang::VarDecl>(kVar);90 assert(Var != nullptr);91 const StorageLocation *Loc = State.Env.getStorageLocation(*Var);92 Value *Val = State.Env.getValue(*Loc);93 initUnknown(*Val, State.Env);94}95 96// Get the Value (1), the properties for the operand (2), and the properties97// for the unary operator (3). The return value is a tuple of (1,2,3).98//99// The returned Value (1) is a nullptr, if there is no Value associated to the100// operand of the unary operator, or if the properties are not set for that101// operand.102// Other than that, new sign properties are created for the Value of the103// unary operator and a new Value is created for the unary operator itself if104// it hadn't have any previously.105std::tuple<Value *, SignProperties, SignProperties>106getValueAndSignProperties(const UnaryOperator *UO,107 const MatchFinder::MatchResult &M,108 LatticeTransferState &State) {109 // The DeclRefExpr refers to this variable in the operand.110 const auto *OperandVar = M.Nodes.getNodeAs<clang::VarDecl>(kVar);111 assert(OperandVar != nullptr);112 const auto *OperandValue = State.Env.getValue(*OperandVar);113 if (!OperandValue)114 return {nullptr, {}, {}};115 116 // Value of the unary op.117 auto *UnaryOpValue = State.Env.getValue(*UO);118 if (!UnaryOpValue) {119 UnaryOpValue = &State.Env.makeAtomicBoolValue();120 State.Env.setValue(*UO, *UnaryOpValue);121 }122 123 // Properties for the operand (sub expression).124 SignProperties OperandProps = getSignProperties(*OperandValue, State.Env);125 if (OperandProps.Neg == nullptr)126 return {nullptr, {}, {}};127 // Properties for the operator expr itself.128 SignProperties UnaryOpProps = initUnknown(*UnaryOpValue, State.Env);129 return {UnaryOpValue, UnaryOpProps, OperandProps};130}131 132void transferBinary(const BinaryOperator *BO, const MatchFinder::MatchResult &M,133 LatticeTransferState &State) {134 auto &A = State.Env.arena();135 const Formula *Comp;136 if (BoolValue *V = State.Env.get<BoolValue>(*BO)) {137 Comp = &V->formula();138 } else {139 Comp = &A.makeAtomRef(A.makeAtom());140 State.Env.setValue(*BO, A.makeBoolValue(*Comp));141 }142 143 // FIXME Use this as well:144 // auto *NegatedComp = &State.Env.makeNot(*Comp);145 146 auto *LHS = State.Env.getValue(*BO->getLHS());147 auto *RHS = State.Env.getValue(*BO->getRHS());148 149 if (!LHS || !RHS)150 return;151 152 SignProperties LHSProps = getSignProperties(*LHS, State.Env);153 SignProperties RHSProps = getSignProperties(*RHS, State.Env);154 if (LHSProps.Neg == nullptr || RHSProps.Neg == nullptr)155 return;156 157 switch (BO->getOpcode()) {158 case BO_GT:159 // pos > pos160 State.Env.assume(161 A.makeImplies(*Comp, A.makeImplies(RHSProps.Pos->formula(),162 LHSProps.Pos->formula())));163 // pos > zero164 State.Env.assume(165 A.makeImplies(*Comp, A.makeImplies(RHSProps.Zero->formula(),166 LHSProps.Pos->formula())));167 break;168 case BO_LT:169 // neg < neg170 State.Env.assume(171 A.makeImplies(*Comp, A.makeImplies(RHSProps.Neg->formula(),172 LHSProps.Neg->formula())));173 // neg < zero174 State.Env.assume(175 A.makeImplies(*Comp, A.makeImplies(RHSProps.Zero->formula(),176 LHSProps.Neg->formula())));177 break;178 case BO_GE:179 // pos >= pos180 State.Env.assume(181 A.makeImplies(*Comp, A.makeImplies(RHSProps.Pos->formula(),182 LHSProps.Pos->formula())));183 break;184 case BO_LE:185 // neg <= neg186 State.Env.assume(187 A.makeImplies(*Comp, A.makeImplies(RHSProps.Neg->formula(),188 LHSProps.Neg->formula())));189 break;190 case BO_EQ:191 State.Env.assume(192 A.makeImplies(*Comp, A.makeImplies(RHSProps.Neg->formula(),193 LHSProps.Neg->formula())));194 State.Env.assume(195 A.makeImplies(*Comp, A.makeImplies(RHSProps.Zero->formula(),196 LHSProps.Zero->formula())));197 State.Env.assume(198 A.makeImplies(*Comp, A.makeImplies(RHSProps.Pos->formula(),199 LHSProps.Pos->formula())));200 break;201 case BO_NE: // Noop.202 break;203 default:204 llvm_unreachable("not implemented");205 }206}207 208void transferUnaryMinus(const UnaryOperator *UO,209 const MatchFinder::MatchResult &M,210 LatticeTransferState &State) {211 auto &A = State.Env.arena();212 auto [UnaryOpValue, UnaryOpProps, OperandProps] =213 getValueAndSignProperties(UO, M, State);214 if (!UnaryOpValue)215 return;216 217 // a is pos ==> -a is neg218 State.Env.assume(219 A.makeImplies(OperandProps.Pos->formula(), UnaryOpProps.Neg->formula()));220 // a is neg ==> -a is pos221 State.Env.assume(222 A.makeImplies(OperandProps.Neg->formula(), UnaryOpProps.Pos->formula()));223 // a is zero ==> -a is zero224 State.Env.assume(A.makeImplies(OperandProps.Zero->formula(),225 UnaryOpProps.Zero->formula()));226}227 228void transferUnaryNot(const UnaryOperator *UO,229 const MatchFinder::MatchResult &M,230 LatticeTransferState &State) {231 auto &A = State.Env.arena();232 auto [UnaryOpValue, UnaryOpProps, OperandProps] =233 getValueAndSignProperties(UO, M, State);234 if (!UnaryOpValue)235 return;236 237 // a is neg or pos ==> !a is zero238 State.Env.assume(A.makeImplies(239 A.makeOr(OperandProps.Pos->formula(), OperandProps.Neg->formula()),240 UnaryOpProps.Zero->formula()));241 242 // FIXME Handle this logic universally, not just for unary not. But Where to243 // put the generic handler, transferExpr maybe?244 if (auto *UOBoolVal = dyn_cast<BoolValue>(UnaryOpValue)) {245 // !a <==> a is zero246 State.Env.assume(247 A.makeEquals(UOBoolVal->formula(), OperandProps.Zero->formula()));248 // !a <==> !a is not zero249 State.Env.assume(A.makeEquals(UOBoolVal->formula(),250 A.makeNot(UnaryOpProps.Zero->formula())));251 }252}253 254// Returns the `Value` associated with `E` (which may be either a prvalue or255// glvalue). Creates a `Value` or `StorageLocation` as needed if `E` does not256// have either of these associated with it yet.257//258// If this functionality turns out to be needed in more cases, this function259// should be moved to a more central location.260Value *getOrCreateValue(const Expr *E, Environment &Env) {261 Value *Val = nullptr;262 if (E->isGLValue()) {263 StorageLocation *Loc = Env.getStorageLocation(*E);264 if (!Loc) {265 Loc = &Env.createStorageLocation(*E);266 Env.setStorageLocation(*E, *Loc);267 }268 Val = Env.getValue(*Loc);269 if (!Val) {270 Val = Env.createValue(E->getType());271 Env.setValue(*Loc, *Val);272 }273 } else {274 Val = Env.getValue(*E);275 if (!Val) {276 Val = Env.createValue(E->getType());277 Env.setValue(*E, *Val);278 }279 }280 assert(Val != nullptr);281 282 return Val;283}284 285void transferExpr(const Expr *E, const MatchFinder::MatchResult &M,286 LatticeTransferState &State) {287 const ASTContext &Context = *M.Context;288 289 Value *Val = getOrCreateValue(E, State.Env);290 291 // The sign symbolic values have been initialized already.292 if (Val->getProperty("neg"))293 return;294 295 Expr::EvalResult R;296 // An integer expression which we cannot evaluate.297 if (!(E->EvaluateAsInt(R, Context) && R.Val.isInt())) {298 initUnknown(*Val, State.Env);299 return;300 }301 302 const Sign S = getSign(R.Val.getInt().getExtValue());303 switch (S) {304 case Sign::Negative:305 initNegative(*Val, State.Env);306 break;307 case Sign::Zero:308 initZero(*Val, State.Env);309 break;310 case Sign::Positive:311 initPositive(*Val, State.Env);312 break;313 }314}315 316auto refToVar() { return declRefExpr(to(varDecl().bind(kVar))); }317 318auto buildTransferMatchSwitch() {319 // Note, the order of the cases is important, the most generic should be320 // added last.321 // FIXME Discover what happens if there are multiple matching ASTMatchers for322 // one Stmt? All matching case's handler should be called and in what order?323 return CFGMatchSwitchBuilder<LatticeTransferState>()324 // a op b (comparison)325 .CaseOfCFGStmt<BinaryOperator>(binaryOperator(isComparisonOperator()),326 transferBinary)327 328 // FIXME handle binop +,-,*,/329 330 // -a331 .CaseOfCFGStmt<UnaryOperator>(332 unaryOperator(hasOperatorName("-"),333 hasUnaryOperand(hasDescendant(refToVar()))),334 transferUnaryMinus)335 336 // !a337 .CaseOfCFGStmt<UnaryOperator>(338 unaryOperator(hasOperatorName("!"),339 hasUnaryOperand(hasDescendant(refToVar()))),340 transferUnaryNot)341 342 // int a;343 .CaseOfCFGStmt<DeclStmt>(declStmt(hasSingleDecl(varDecl(344 decl().bind(kVar), hasType(isInteger()),345 unless(hasInitializer(expr()))))),346 transferUninitializedInt)347 348 // constexpr int349 .CaseOfCFGStmt<Expr>(expr(hasType(isInteger())), transferExpr)350 351 .Build();352}353 354class SignPropagationAnalysis355 : public DataflowAnalysis<SignPropagationAnalysis, NoopLattice> {356public:357 SignPropagationAnalysis(ASTContext &Context)358 : DataflowAnalysis<SignPropagationAnalysis, NoopLattice>(Context),359 TransferMatchSwitch(buildTransferMatchSwitch()) {}360 361 static NoopLattice initialElement() { return {}; }362 363 void transfer(const CFGElement &Elt, NoopLattice &L, Environment &Env) {364 LatticeTransferState State(L, Env);365 TransferMatchSwitch(Elt, getASTContext(), State);366 }367 void join(QualType Type, const Value &Val1, const Environment &Env1,368 const Value &Val2, const Environment &Env2, Value &MergedVal,369 Environment &MergedEnv) override;370 371private:372 CFGMatchSwitch<TransferState<NoopLattice>> TransferMatchSwitch;373};374 375BoolValue &joinBoolValues(BoolValue &Bool1, const Environment &Env1,376 BoolValue &Bool2, const Environment &Env2,377 Environment &JoinedEnv) {378 if (&Bool1 == &Bool2) {379 return Bool1;380 }381 382 auto &B1 = Bool1.formula();383 auto &B2 = Bool2.formula();384 385 auto &A = JoinedEnv.arena();386 auto &JoinedBool = JoinedEnv.makeAtomicBoolValue();387 388 // If `Bool1` and `Bool2` is constrained to the same true / false value,389 // `JoinedBool` can be constrained similarly without needing to consider the390 // path taken - this simplifies the flow condition tracked in `JoinedEnv`.391 // Otherwise, information about which path was taken is used to associate392 // `JoinedBool` with `Bool1` and `Bool2`.393 if (Env1.proves(B1) && Env2.proves(B2)) {394 JoinedEnv.assume(JoinedBool.formula());395 } else if (Env1.proves(A.makeNot(B1)) && Env2.proves(A.makeNot(B2))) {396 JoinedEnv.assume(A.makeNot(JoinedBool.formula()));397 }398 return JoinedBool;399}400 401void SignPropagationAnalysis::join(QualType Type, const Value &Val1,402 const Environment &Env1, const Value &Val2,403 const Environment &Env2, Value &JoinedVal,404 Environment &JoinedEnv) {405 if (!Type->isIntegerType())406 return;407 SignProperties Ps1 = getSignProperties(Val1, Env1);408 SignProperties Ps2 = getSignProperties(Val2, Env2);409 if (!Ps1.Neg || !Ps2.Neg)410 return;411 BoolValue &JoinedNeg =412 joinBoolValues(*Ps1.Neg, Env1, *Ps2.Neg, Env2, JoinedEnv);413 BoolValue &JoinedZero =414 joinBoolValues(*Ps1.Zero, Env1, *Ps2.Zero, Env2, JoinedEnv);415 BoolValue &JoinedPos =416 joinBoolValues(*Ps1.Pos, Env1, *Ps2.Pos, Env2, JoinedEnv);417 setSignProperties(JoinedVal,418 SignProperties{&JoinedNeg, &JoinedZero, &JoinedPos});419}420 421template <typename Matcher>422void runDataflow(llvm::StringRef Code, Matcher Match,423 LangStandard::Kind Std = LangStandard::lang_cxx17,424 llvm::StringRef TargetFun = "fun") {425 using ast_matchers::hasName;426 ASSERT_THAT_ERROR(427 checkDataflow<SignPropagationAnalysis>(428 AnalysisInputs<SignPropagationAnalysis>(429 Code, hasName(TargetFun),430 [](ASTContext &C, Environment &) {431 return SignPropagationAnalysis(C);432 })433 .withASTBuildArgs(434 {"-fsyntax-only", "-fno-delayed-template-parsing",435 "-std=" +436 std::string(LangStandard::getLangStandardForKind(Std)437 .getName())}),438 /*VerifyResults=*/439 [&Match](const llvm::StringMap<DataflowAnalysisState<NoopLattice>>440 &Results,441 const AnalysisOutputs &AO) { Match(Results, AO.ASTCtx); }),442 llvm::Succeeded());443}444 445// FIXME add this to testing support.446template <typename NodeType, typename MatcherType>447const NodeType *findFirst(ASTContext &ASTCtx, const MatcherType &M) {448 auto TargetNodes = match(M.bind("v"), ASTCtx);449 assert(TargetNodes.size() == 1 && "Match must be unique");450 auto *const Result = selectFirst<NodeType>("v", TargetNodes);451 assert(Result != nullptr);452 return Result;453}454 455template <typename Node>456std::pair<testing::AssertionResult, Value *>457getProperty(const Environment &Env, ASTContext &ASTCtx, const Node *N,458 StringRef Property) {459 if (!N)460 return {testing::AssertionFailure() << "No node", nullptr};461 const StorageLocation *Loc = Env.getStorageLocation(*N);462 if (!isa_and_nonnull<ScalarStorageLocation>(Loc))463 return {testing::AssertionFailure() << "No location", nullptr};464 const Value *Val = Env.getValue(*Loc);465 if (!Val)466 return {testing::AssertionFailure() << "No value", nullptr};467 auto *Prop = Val->getProperty(Property);468 if (!isa_and_nonnull<BoolValue>(Prop))469 return {testing::AssertionFailure() << "No property for " << Property,470 nullptr};471 return {testing::AssertionSuccess(), Prop};472}473 474// Test if the given property of the given node is implied by the flow475// condition. If 'Implies' is false then check if it is not implied.476template <typename Node>477testing::AssertionResult isPropertyImplied(const Environment &Env,478 ASTContext &ASTCtx, const Node *N,479 StringRef Property, bool Implies) {480 auto [Result, Prop] = getProperty(Env, ASTCtx, N, Property);481 if (!Prop)482 return Result;483 auto *BVProp = cast<BoolValue>(Prop);484 if (Env.proves(BVProp->formula()) != Implies)485 return testing::AssertionFailure()486 << Property << " is " << (Implies ? "not" : "") << " implied"487 << ", but should " << (Implies ? "" : "not ") << "be";488 return testing::AssertionSuccess();489}490 491template <typename Node>492testing::AssertionResult isNegative(const Node *N, ASTContext &ASTCtx,493 const Environment &Env) {494 testing::AssertionResult R = isPropertyImplied(Env, ASTCtx, N, "neg", true);495 if (!R)496 return R;497 R = isPropertyImplied(Env, ASTCtx, N, "zero", false);498 if (!R)499 return R;500 return isPropertyImplied(Env, ASTCtx, N, "pos", false);501}502template <typename Node>503testing::AssertionResult isPositive(const Node *N, ASTContext &ASTCtx,504 const Environment &Env) {505 testing::AssertionResult R = isPropertyImplied(Env, ASTCtx, N, "pos", true);506 if (!R)507 return R;508 R = isPropertyImplied(Env, ASTCtx, N, "zero", false);509 if (!R)510 return R;511 return isPropertyImplied(Env, ASTCtx, N, "neg", false);512}513template <typename Node>514testing::AssertionResult isZero(const Node *N, ASTContext &ASTCtx,515 const Environment &Env) {516 testing::AssertionResult R = isPropertyImplied(Env, ASTCtx, N, "zero", true);517 if (!R)518 return R;519 R = isPropertyImplied(Env, ASTCtx, N, "pos", false);520 if (!R)521 return R;522 return isPropertyImplied(Env, ASTCtx, N, "neg", false);523}524template <typename Node>525testing::AssertionResult isTop(const Node *N, ASTContext &ASTCtx,526 const Environment &Env) {527 testing::AssertionResult R = isPropertyImplied(Env, ASTCtx, N, "zero", false);528 if (!R)529 return R;530 R = isPropertyImplied(Env, ASTCtx, N, "pos", false);531 if (!R)532 return R;533 return isPropertyImplied(Env, ASTCtx, N, "neg", false);534}535 536TEST(SignAnalysisTest, Init) {537 std::string Code = R"(538 int foo();539 void fun() {540 int a = -1;541 int b = 0;542 int c = 1;543 int d;544 int e = foo();545 int f = c;546 // [[p]]547 }548 )";549 runDataflow(550 Code,551 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,552 ASTContext &ASTCtx) {553 // ASTCtx.getTranslationUnitDecl()->dump();554 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));555 const Environment &Env = getEnvironmentAtAnnotation(Results, "p");556 557 const ValueDecl *A = findValueDecl(ASTCtx, "a");558 const ValueDecl *B = findValueDecl(ASTCtx, "b");559 const ValueDecl *C = findValueDecl(ASTCtx, "c");560 const ValueDecl *D = findValueDecl(ASTCtx, "d");561 const ValueDecl *E = findValueDecl(ASTCtx, "e");562 const ValueDecl *F = findValueDecl(ASTCtx, "f");563 564 EXPECT_TRUE(isNegative(A, ASTCtx, Env));565 EXPECT_TRUE(isZero(B, ASTCtx, Env));566 EXPECT_TRUE(isPositive(C, ASTCtx, Env));567 EXPECT_TRUE(isTop(D, ASTCtx, Env));568 EXPECT_TRUE(isTop(E, ASTCtx, Env));569 EXPECT_TRUE(isPositive(F, ASTCtx, Env));570 },571 LangStandard::lang_cxx17);572}573 574TEST(SignAnalysisTest, UnaryMinus) {575 std::string Code = R"(576 void fun() {577 int a = 1;578 int b = -a;579 // [[p]]580 }581 )";582 runDataflow(583 Code,584 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,585 ASTContext &ASTCtx) {586 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));587 const Environment &Env = getEnvironmentAtAnnotation(Results, "p");588 589 const ValueDecl *A = findValueDecl(ASTCtx, "a");590 const ValueDecl *B = findValueDecl(ASTCtx, "b");591 EXPECT_TRUE(isPositive(A, ASTCtx, Env));592 EXPECT_TRUE(isNegative(B, ASTCtx, Env));593 },594 LangStandard::lang_cxx17);595}596 597TEST(SignAnalysisTest, UnaryNot) {598 std::string Code = R"(599 void fun() {600 int a = 2;601 int b = !a;602 // [[p]]603 }604 )";605 runDataflow(606 Code,607 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,608 ASTContext &ASTCtx) {609 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));610 const Environment &Env = getEnvironmentAtAnnotation(Results, "p");611 612 const ValueDecl *A = findValueDecl(ASTCtx, "a");613 const ValueDecl *B = findValueDecl(ASTCtx, "b");614 EXPECT_TRUE(isPositive(A, ASTCtx, Env));615 EXPECT_TRUE(isZero(B, ASTCtx, Env));616 },617 LangStandard::lang_cxx17);618}619 620TEST(SignAnalysisTest, UnaryNotInIf) {621 std::string Code = R"(622 int foo();623 void fun() {624 int a = foo();625 if (!a) {626 int b1;627 int p_a = a;628 int p_not_a = !a;629 // [[p]]630 } else {631 int q_a = a;632 int q_not_a = !a;633 // [[q]]634 }635 }636 )";637 runDataflow(638 Code,639 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,640 ASTContext &ASTCtx) {641 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q"));642 const Environment &EnvP = getEnvironmentAtAnnotation(Results, "p");643 const Environment &EnvQ = getEnvironmentAtAnnotation(Results, "q");644 645 const ValueDecl *A = findValueDecl(ASTCtx, "a");646 const ValueDecl *PA = findValueDecl(ASTCtx, "p_a");647 const ValueDecl *PNA = findValueDecl(ASTCtx, "p_not_a");648 const ValueDecl *QA = findValueDecl(ASTCtx, "q_a");649 const ValueDecl *QNA = findValueDecl(ASTCtx, "q_not_a");650 651 // p652 EXPECT_TRUE(isZero(A, ASTCtx, EnvP));653 EXPECT_TRUE(isZero(PA, ASTCtx, EnvP));654 EXPECT_TRUE(isTop(PNA, ASTCtx, EnvP));655 656 // q657 EXPECT_TRUE(isTop(A, ASTCtx, EnvQ));658 EXPECT_TRUE(isTop(QA, ASTCtx, EnvQ));659 EXPECT_TRUE(isZero(QNA, ASTCtx, EnvQ));660 },661 LangStandard::lang_cxx17);662}663 664TEST(SignAnalysisTest, BinaryGT) {665 std::string Code = R"(666 int foo();667 void fun() {668 int a = foo();669 int b = 1;670 if (a > 1) {671 (void)0;672 // [[p]]673 }674 if (a > 0) {675 (void)0;676 // [[q]]677 }678 if (a > -1) {679 (void)0;680 // [[r]]681 }682 if (a > b) {683 (void)0;684 // [[s]]685 }686 }687 )";688 runDataflow(689 Code,690 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,691 ASTContext &ASTCtx) {692 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q", "r", "s"));693 const Environment &EnvP = getEnvironmentAtAnnotation(Results, "p");694 const Environment &EnvQ = getEnvironmentAtAnnotation(Results, "q");695 const Environment &EnvR = getEnvironmentAtAnnotation(Results, "r");696 const Environment &EnvS = getEnvironmentAtAnnotation(Results, "s");697 698 const ValueDecl *A = findValueDecl(ASTCtx, "a");699 700 // p701 EXPECT_TRUE(isPositive(A, ASTCtx, EnvP));702 // q703 EXPECT_TRUE(isPositive(A, ASTCtx, EnvQ));704 // r705 EXPECT_TRUE(isTop(A, ASTCtx, EnvR));706 // s707 EXPECT_TRUE(isPositive(A, ASTCtx, EnvS));708 },709 LangStandard::lang_cxx17);710}711 712TEST(SignAnalysisTest, BinaryLT) {713 std::string Code = R"(714 int foo();715 void fun() {716 int a = foo();717 int b = -1;718 if (a < -1) {719 (void)0;720 // [[p]]721 }722 if (a < 0) {723 (void)0;724 // [[q]]725 }726 if (a < 1) {727 (void)0;728 // [[r]]729 }730 if (a < b) {731 (void)0;732 // [[s]]733 }734 }735 )";736 runDataflow(737 Code,738 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,739 ASTContext &ASTCtx) {740 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q", "r", "s"));741 const Environment &EnvP = getEnvironmentAtAnnotation(Results, "p");742 const Environment &EnvQ = getEnvironmentAtAnnotation(Results, "q");743 const Environment &EnvR = getEnvironmentAtAnnotation(Results, "r");744 const Environment &EnvS = getEnvironmentAtAnnotation(Results, "s");745 746 const ValueDecl *A = findValueDecl(ASTCtx, "a");747 748 // p749 EXPECT_TRUE(isNegative(A, ASTCtx, EnvP));750 // q751 EXPECT_TRUE(isNegative(A, ASTCtx, EnvQ));752 // r753 EXPECT_TRUE(isTop(A, ASTCtx, EnvR));754 // s755 EXPECT_TRUE(isNegative(A, ASTCtx, EnvS));756 },757 LangStandard::lang_cxx17);758}759 760TEST(SignAnalysisTest, BinaryGE) {761 std::string Code = R"(762 int foo();763 void fun() {764 int a = foo();765 int b = 1;766 if (a >= 1) {767 (void)0;768 // [[p]]769 }770 if (a >= 0) {771 (void)0;772 // [[q]]773 }774 if (a >= -1) {775 (void)0;776 // [[r]]777 }778 if (a >= b) {779 (void)0;780 // [[s]]781 }782 }783 )";784 runDataflow(785 Code,786 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,787 ASTContext &ASTCtx) {788 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q", "r", "s"));789 const Environment &EnvP = getEnvironmentAtAnnotation(Results, "p");790 const Environment &EnvQ = getEnvironmentAtAnnotation(Results, "q");791 const Environment &EnvR = getEnvironmentAtAnnotation(Results, "r");792 const Environment &EnvS = getEnvironmentAtAnnotation(Results, "s");793 794 const ValueDecl *A = findValueDecl(ASTCtx, "a");795 796 // p797 EXPECT_TRUE(isPositive(A, ASTCtx, EnvP));798 // q799 EXPECT_TRUE(isTop(A, ASTCtx, EnvQ));800 // r801 EXPECT_TRUE(isTop(A, ASTCtx, EnvR));802 // s803 EXPECT_TRUE(isPositive(A, ASTCtx, EnvS));804 },805 LangStandard::lang_cxx17);806}807 808TEST(SignAnalysisTest, BinaryLE) {809 std::string Code = R"(810 int foo();811 void fun() {812 int a = foo();813 int b = -1;814 if (a <= -1) {815 (void)0;816 // [[p]]817 }818 if (a <= 0) {819 (void)0;820 // [[q]]821 }822 if (a <= 1) {823 (void)0;824 // [[r]]825 }826 if (a <= b) {827 (void)0;828 // [[s]]829 }830 }831 )";832 runDataflow(833 Code,834 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,835 ASTContext &ASTCtx) {836 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q", "r", "s"));837 const Environment &EnvP = getEnvironmentAtAnnotation(Results, "p");838 const Environment &EnvQ = getEnvironmentAtAnnotation(Results, "q");839 const Environment &EnvR = getEnvironmentAtAnnotation(Results, "r");840 const Environment &EnvS = getEnvironmentAtAnnotation(Results, "s");841 842 const ValueDecl *A = findValueDecl(ASTCtx, "a");843 844 // p845 EXPECT_TRUE(isNegative(A, ASTCtx, EnvP));846 // q847 EXPECT_TRUE(isTop(A, ASTCtx, EnvQ));848 // r849 EXPECT_TRUE(isTop(A, ASTCtx, EnvR));850 // s851 EXPECT_TRUE(isNegative(A, ASTCtx, EnvS));852 },853 LangStandard::lang_cxx17);854}855 856TEST(SignAnalysisTest, BinaryEQ) {857 std::string Code = R"(858 int foo();859 void fun() {860 int a = foo();861 if (a == -1) {862 (void)0;863 // [[n]]864 }865 if (a == 0) {866 (void)0;867 // [[z]]868 }869 if (a == 1) {870 (void)0;871 // [[p]]872 }873 }874 )";875 runDataflow(876 Code,877 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,878 ASTContext &ASTCtx) {879 ASSERT_THAT(Results.keys(), UnorderedElementsAre("n", "z", "p"));880 const Environment &EnvN = getEnvironmentAtAnnotation(Results, "n");881 const Environment &EnvZ = getEnvironmentAtAnnotation(Results, "z");882 const Environment &EnvP = getEnvironmentAtAnnotation(Results, "p");883 884 const ValueDecl *A = findValueDecl(ASTCtx, "a");885 886 // n887 EXPECT_TRUE(isNegative(A, ASTCtx, EnvN));888 // z889 EXPECT_TRUE(isZero(A, ASTCtx, EnvZ));890 // p891 EXPECT_TRUE(isPositive(A, ASTCtx, EnvP));892 },893 LangStandard::lang_cxx17);894}895 896TEST(SignAnalysisTest, ComplexLoopCondition) {897 std::string Code = R"(898 int foo();899 void fun() {900 int a, b;901 while ((a = foo()) > 0 && (b = foo()) > 0) {902 a;903 b;904 // [[p]]905 }906 }907 )";908 runDataflow(909 Code,910 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,911 ASTContext &ASTCtx) {912 const Environment &Env = getEnvironmentAtAnnotation(Results, "p");913 914 const ValueDecl *A = findValueDecl(ASTCtx, "a");915 const ValueDecl *B = findValueDecl(ASTCtx, "b");916 917 EXPECT_TRUE(isPositive(A, ASTCtx, Env));918 EXPECT_TRUE(isPositive(B, ASTCtx, Env));919 },920 LangStandard::lang_cxx17);921}922 923TEST(SignAnalysisTest, JoinToTop) {924 std::string Code = R"(925 int foo();926 void fun(bool b) {927 int a = foo();928 if (b) {929 a = -1;930 (void)0;931 // [[p]]932 } else {933 a = 1;934 (void)0;935 // [[q]]936 }937 (void)0;938 // [[r]]939 }940 )";941 runDataflow(942 Code,943 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,944 ASTContext &ASTCtx) {945 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q", "r"));946 const Environment &EnvP = getEnvironmentAtAnnotation(Results, "p");947 const Environment &EnvQ = getEnvironmentAtAnnotation(Results, "q");948 const Environment &EnvR = getEnvironmentAtAnnotation(Results, "r");949 950 const ValueDecl *A = findValueDecl(ASTCtx, "a");951 952 // p953 EXPECT_TRUE(isNegative(A, ASTCtx, EnvP));954 // q955 EXPECT_TRUE(isPositive(A, ASTCtx, EnvQ));956 // r957 EXPECT_TRUE(isTop(A, ASTCtx, EnvR));958 },959 LangStandard::lang_cxx17);960}961 962TEST(SignAnalysisTest, JoinToNeg) {963 std::string Code = R"(964 int foo();965 void fun() {966 int a = foo();967 if (a < 1) {968 a = -1;969 (void)0;970 // [[p]]971 } else {972 a = -1;973 (void)0;974 // [[q]]975 }976 (void)0;977 // [[r]]978 }979 )";980 runDataflow(981 Code,982 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,983 ASTContext &ASTCtx) {984 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q", "r"));985 const Environment &EnvP = getEnvironmentAtAnnotation(Results, "p");986 const Environment &EnvQ = getEnvironmentAtAnnotation(Results, "q");987 const Environment &EnvR = getEnvironmentAtAnnotation(Results, "r");988 989 const ValueDecl *A = findValueDecl(ASTCtx, "a");990 991 // p992 EXPECT_TRUE(isNegative(A, ASTCtx, EnvP));993 // q994 EXPECT_TRUE(isNegative(A, ASTCtx, EnvQ));995 // r996 EXPECT_TRUE(isNegative(A, ASTCtx, EnvR));997 },998 LangStandard::lang_cxx17);999}1000 1001TEST(SignAnalysisTest, NestedIfs) {1002 std::string Code = R"(1003 int foo();1004 void fun() {1005 int a = foo();1006 if (a >= 0) {1007 (void)0;1008 // [[p]]1009 if (a == 0) {1010 (void)0;1011 // [[q]]1012 }1013 }1014 (void)0;1015 // [[r]]1016 }1017 )";1018 runDataflow(1019 Code,1020 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,1021 ASTContext &ASTCtx) {1022 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q", "r"));1023 const Environment &EnvP = getEnvironmentAtAnnotation(Results, "p");1024 const Environment &EnvQ = getEnvironmentAtAnnotation(Results, "q");1025 const Environment &EnvR = getEnvironmentAtAnnotation(Results, "r");1026 1027 const ValueDecl *A = findValueDecl(ASTCtx, "a");1028 1029 // p1030 EXPECT_TRUE(isTop(A, ASTCtx, EnvP));1031 // q1032 EXPECT_TRUE(isZero(A, ASTCtx, EnvQ));1033 // r1034 EXPECT_TRUE(isTop(A, ASTCtx, EnvR));1035 },1036 LangStandard::lang_cxx17);1037}1038 1039} // namespace1040