clang/unittests/Analysis/FlowSensitive/SignAnalysisTest.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-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 //  This file defines a simplistic version of Sign Analysis as a demo of a
  10 //  forward, monotonic dataflow analysis. The implementation uses 3 boolean
  11 //  values to represent the sign lattice (negative, zero, positive). In
  12 //  practice, 2 booleans would be enough, however, this approach has the
  13 //  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
  29 namespace {
  30
  31 using namespace clang;
  32 using namespace dataflow;
  33 using namespace ast_matchers;
  34 using namespace test;
  35 using ::testing::UnorderedElementsAre;
  36
  37 enum class Sign : int { Negative, Zero, Positive };
  38
  39 Sign getSign(int64_t V) {
  40   return V == 0 ? Sign::Zero : (V < 0 ? Sign::Negative : Sign::Positive);
  41 }
  42
  43 using LatticeTransferState = TransferState<NoopLattice>;
  44
  45 constexpr char kVar[] = "var";
  46
  47 void 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 }
  52 void 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 }
  57 void 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 not
  64 // set then these are null pointers, otherwise, the pointed BoolValues are
  65 // owned by the Environment.
  66 struct SignProperties {
  67   BoolValue *Neg, *Zero, *Pos;
  68 };
  69 void 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 }
  74 SignProperties initUnknown(Value &Val, Environment &Env) {
  75   SignProperties Ps{&Env.makeAtomicBoolValue(), &Env.makeAtomicBoolValue(),
  76                     &Env.makeAtomicBoolValue()};
  77   setSignProperties(Val, Ps);
  78   return Ps;
  79 }
  80 SignProperties 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
  86 void 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 properties
  97 // 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 the
 100 // operand of the unary operator, or if the properties are not set for that
 101 // operand.
 102 // Other than that, new sign properties are created for the Value of the
 103 // unary operator and a new Value is created for the unary operator itself if
 104 // it hadn't have any previously.
 105 std::tuple<Value *, SignProperties, SignProperties>
 106 getValueAndSignProperties(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
 132 void 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 > pos
 160     State.Env.assume(
 161         A.makeImplies(*Comp, A.makeImplies(RHSProps.Pos->formula(),
 162                                            LHSProps.Pos->formula())));
 163     // pos > zero
 164     State.Env.assume(
 165         A.makeImplies(*Comp, A.makeImplies(RHSProps.Zero->formula(),
 166                                            LHSProps.Pos->formula())));
 167     break;
 168   case BO_LT:
 169     // neg < neg
 170     State.Env.assume(
 171         A.makeImplies(*Comp, A.makeImplies(RHSProps.Neg->formula(),
 172                                            LHSProps.Neg->formula())));
 173     // neg < zero
 174     State.Env.assume(
 175         A.makeImplies(*Comp, A.makeImplies(RHSProps.Zero->formula(),
 176                                            LHSProps.Neg->formula())));
 177     break;
 178   case BO_GE:
 179     // pos >= pos
 180     State.Env.assume(
 181         A.makeImplies(*Comp, A.makeImplies(RHSProps.Pos->formula(),
 182                                            LHSProps.Pos->formula())));
 183     break;
 184   case BO_LE:
 185     // neg <= neg
 186     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
 208 void 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 neg
 218   State.Env.assume(
 219       A.makeImplies(OperandProps.Pos->formula(), UnaryOpProps.Neg->formula()));
 220   // a is neg ==> -a is pos
 221   State.Env.assume(
 222       A.makeImplies(OperandProps.Neg->formula(), UnaryOpProps.Pos->formula()));
 223   // a is zero ==> -a is zero
 224   State.Env.assume(A.makeImplies(OperandProps.Zero->formula(),
 225                                  UnaryOpProps.Zero->formula()));
 226 }
 227
 228 void 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 zero
 238   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 to
 243   // put the generic handler, transferExpr maybe?
 244   if (auto *UOBoolVal = dyn_cast<BoolValue>(UnaryOpValue)) {
 245     // !a <==> a is zero
 246     State.Env.assume(
 247         A.makeEquals(UOBoolVal->formula(), OperandProps.Zero->formula()));
 248     // !a <==> !a is not zero
 249     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 or
 255 // glvalue). Creates a `Value` or `StorageLocation` as needed if `E` does not
 256 // have either of these associated with it yet.
 257 //
 258 // If this functionality turns out to be needed in more cases, this function
 259 // should be moved to a more central location.
 260 Value *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
 285 void 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
 316 auto refToVar() { return declRefExpr(to(varDecl().bind(kVar))); }
 317
 318 auto buildTransferMatchSwitch() {
 319   // Note, the order of the cases is important, the most generic should be
 320   // added last.
 321   // FIXME Discover what happens if there are multiple matching ASTMatchers for
 322   // 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       // -a
 331       .CaseOfCFGStmt<UnaryOperator>(
 332           unaryOperator(hasOperatorName("-"),
 333                         hasUnaryOperand(hasDescendant(refToVar()))),
 334           transferUnaryMinus)
 335
 336       // !a
 337       .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 int
 349       .CaseOfCFGStmt<Expr>(expr(hasType(isInteger())), transferExpr)
 350
 351       .Build();
 352 }
 353
 354 class SignPropagationAnalysis
 355     : public DataflowAnalysis<SignPropagationAnalysis, NoopLattice> {
 356 public:
 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
 371 private:
 372   CFGMatchSwitch<TransferState<NoopLattice>> TransferMatchSwitch;
 373 };
 374
 375 BoolValue &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 the
 390   // path taken - this simplifies the flow condition tracked in `JoinedEnv`.
 391   // Otherwise, information about which path was taken is used to associate
 392   // `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
 401 void 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
 421 template <typename Matcher>
 422 void 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.
 446 template <typename NodeType, typename MatcherType>
 447 const 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
 455 template <typename Node>
 456 std::pair<testing::AssertionResult, Value *>
 457 getProperty(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 flow
 475 // condition. If 'Implies' is false then check if it is not implied.
 476 template <typename Node>
 477 testing::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
 491 template <typename Node>
 492 testing::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 }
 502 template <typename Node>
 503 testing::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 }
 513 template <typename Node>
 514 testing::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 }
 524 template <typename Node>
 525 testing::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
 536 TEST(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
 574 TEST(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
 597 TEST(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
 620 TEST(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         // p
 652         EXPECT_TRUE(isZero(A, ASTCtx, EnvP));
 653         EXPECT_TRUE(isZero(PA, ASTCtx, EnvP));
 654         EXPECT_TRUE(isTop(PNA, ASTCtx, EnvP));
 655
 656         // q
 657         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
 664 TEST(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         // p
 701         EXPECT_TRUE(isPositive(A, ASTCtx, EnvP));
 702         // q
 703         EXPECT_TRUE(isPositive(A, ASTCtx, EnvQ));
 704         // r
 705         EXPECT_TRUE(isTop(A, ASTCtx, EnvR));
 706         // s
 707         EXPECT_TRUE(isPositive(A, ASTCtx, EnvS));
 708       },
 709       LangStandard::lang_cxx17);
 710 }
 711
 712 TEST(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         // p
 749         EXPECT_TRUE(isNegative(A, ASTCtx, EnvP));
 750         // q
 751         EXPECT_TRUE(isNegative(A, ASTCtx, EnvQ));
 752         // r
 753         EXPECT_TRUE(isTop(A, ASTCtx, EnvR));
 754         // s
 755         EXPECT_TRUE(isNegative(A, ASTCtx, EnvS));
 756       },
 757       LangStandard::lang_cxx17);
 758 }
 759
 760 TEST(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         // p
 797         EXPECT_TRUE(isPositive(A, ASTCtx, EnvP));
 798         // q
 799         EXPECT_TRUE(isTop(A, ASTCtx, EnvQ));
 800         // r
 801         EXPECT_TRUE(isTop(A, ASTCtx, EnvR));
 802         // s
 803         EXPECT_TRUE(isPositive(A, ASTCtx, EnvS));
 804       },
 805       LangStandard::lang_cxx17);
 806 }
 807
 808 TEST(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         // p
 845         EXPECT_TRUE(isNegative(A, ASTCtx, EnvP));
 846         // q
 847         EXPECT_TRUE(isTop(A, ASTCtx, EnvQ));
 848         // r
 849         EXPECT_TRUE(isTop(A, ASTCtx, EnvR));
 850         // s
 851         EXPECT_TRUE(isNegative(A, ASTCtx, EnvS));
 852       },
 853       LangStandard::lang_cxx17);
 854 }
 855
 856 TEST(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         // n
 887         EXPECT_TRUE(isNegative(A, ASTCtx, EnvN));
 888         // z
 889         EXPECT_TRUE(isZero(A, ASTCtx, EnvZ));
 890         // p
 891         EXPECT_TRUE(isPositive(A, ASTCtx, EnvP));
 892       },
 893       LangStandard::lang_cxx17);
 894 }
 895
 896 TEST(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
 923 TEST(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         // p
 953         EXPECT_TRUE(isNegative(A, ASTCtx, EnvP));
 954         // q
 955         EXPECT_TRUE(isPositive(A, ASTCtx, EnvQ));
 956         // r
 957         EXPECT_TRUE(isTop(A, ASTCtx, EnvR));
 958       },
 959       LangStandard::lang_cxx17);
 960 }
 961
 962 TEST(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         // p
 992         EXPECT_TRUE(isNegative(A, ASTCtx, EnvP));
 993         // q
 994         EXPECT_TRUE(isNegative(A, ASTCtx, EnvQ));
 995         // r
 996         EXPECT_TRUE(isNegative(A, ASTCtx, EnvR));
 997       },
 998       LangStandard::lang_cxx17);
 999 }
1000
1001 TEST(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         // p
1030         EXPECT_TRUE(isTop(A, ASTCtx, EnvP));
1031         // q
1032         EXPECT_TRUE(isZero(A, ASTCtx, EnvQ));
1033         // r
1034         EXPECT_TRUE(isTop(A, ASTCtx, EnvR));
1035       },
1036       LangStandard::lang_cxx17);
1037 }
1038
1039 } // namespace