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 = cast_or_null<BoolValue>(State.Env.getValue(*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   bool merge(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 // Copied from crubit.
 376 BoolValue &mergeBoolValues(BoolValue &Bool1, const Environment &Env1,
 377                            BoolValue &Bool2, const Environment &Env2,
 378                            Environment &MergedEnv) {
 379   if (&Bool1 == &Bool2) {
 380     return Bool1;
 381   }
 382
 383   auto &B1 = Bool1.formula();
 384   auto &B2 = Bool2.formula();
 385
 386   auto &A = MergedEnv.arena();
 387   auto &MergedBool = MergedEnv.makeAtomicBoolValue();
 388
 389   // If `Bool1` and `Bool2` is constrained to the same true / false value,
 390   // `MergedBool` can be constrained similarly without needing to consider the
 391   // path taken - this simplifies the flow condition tracked in `MergedEnv`.
 392   // Otherwise, information about which path was taken is used to associate
 393   // `MergedBool` with `Bool1` and `Bool2`.
 394   if (Env1.proves(B1) && Env2.proves(B2)) {
 395     MergedEnv.assume(MergedBool.formula());
 396   } else if (Env1.proves(A.makeNot(B1)) && Env2.proves(A.makeNot(B2))) {
 397     MergedEnv.assume(A.makeNot(MergedBool.formula()));
 398   }
 399   return MergedBool;
 400 }
 401
 402 bool SignPropagationAnalysis::merge(QualType Type, const Value &Val1,
 403                                     const Environment &Env1, const Value &Val2,
 404                                     const Environment &Env2, Value &MergedVal,
 405                                     Environment &MergedEnv) {
 406   if (!Type->isIntegerType())
 407     return false;
 408   SignProperties Ps1 = getSignProperties(Val1, Env1);
 409   SignProperties Ps2 = getSignProperties(Val2, Env2);
 410   if (!Ps1.Neg || !Ps2.Neg)
 411     return false;
 412   BoolValue &MergedNeg =
 413       mergeBoolValues(*Ps1.Neg, Env1, *Ps2.Neg, Env2, MergedEnv);
 414   BoolValue &MergedZero =
 415       mergeBoolValues(*Ps1.Zero, Env1, *Ps2.Zero, Env2, MergedEnv);
 416   BoolValue &MergedPos =
 417       mergeBoolValues(*Ps1.Pos, Env1, *Ps2.Pos, Env2, MergedEnv);
 418   setSignProperties(MergedVal,
 419                     SignProperties{&MergedNeg, &MergedZero, &MergedPos});
 420   return true;
 421 }
 422
 423 template <typename Matcher>
 424 void runDataflow(llvm::StringRef Code, Matcher Match,
 425                  LangStandard::Kind Std = LangStandard::lang_cxx17,
 426                  llvm::StringRef TargetFun = "fun") {
 427   using ast_matchers::hasName;
 428   ASSERT_THAT_ERROR(
 429       checkDataflow<SignPropagationAnalysis>(
 430           AnalysisInputs<SignPropagationAnalysis>(
 431               Code, hasName(TargetFun),
 432               [](ASTContext &C, Environment &) {
 433                 return SignPropagationAnalysis(C);
 434               })
 435               .withASTBuildArgs(
 436                   {"-fsyntax-only", "-fno-delayed-template-parsing",
 437                    "-std=" +
 438                        std::string(LangStandard::getLangStandardForKind(Std)
 439                                        .getName())}),
 440           /*VerifyResults=*/
 441           [&Match](const llvm::StringMap<DataflowAnalysisState<NoopLattice>>
 442                        &Results,
 443                    const AnalysisOutputs &AO) { Match(Results, AO.ASTCtx); }),
 444       llvm::Succeeded());
 445 }
 446
 447 // FIXME add this to testing support.
 448 template <typename NodeType, typename MatcherType>
 449 const NodeType *findFirst(ASTContext &ASTCtx, const MatcherType &M) {
 450   auto TargetNodes = match(M.bind("v"), ASTCtx);
 451   assert(TargetNodes.size() == 1 && "Match must be unique");
 452   auto *const Result = selectFirst<NodeType>("v", TargetNodes);
 453   assert(Result != nullptr);
 454   return Result;
 455 }
 456
 457 template <typename Node>
 458 std::pair<testing::AssertionResult, Value *>
 459 getProperty(const Environment &Env, ASTContext &ASTCtx, const Node *N,
 460             StringRef Property) {
 461   if (!N)
 462     return {testing::AssertionFailure() << "No node", nullptr};
 463   const StorageLocation *Loc = Env.getStorageLocation(*N);
 464   if (!isa_and_nonnull<ScalarStorageLocation>(Loc))
 465     return {testing::AssertionFailure() << "No location", nullptr};
 466   const Value *Val = Env.getValue(*Loc);
 467   if (!Val)
 468     return {testing::AssertionFailure() << "No value", nullptr};
 469   auto *Prop = Val->getProperty(Property);
 470   if (!isa_and_nonnull<BoolValue>(Prop))
 471     return {testing::AssertionFailure() << "No property for " << Property,
 472             nullptr};
 473   return {testing::AssertionSuccess(), Prop};
 474 }
 475
 476 // Test if the given property of the given node is implied by the flow
 477 // condition. If 'Implies' is false then check if it is not implied.
 478 template <typename Node>
 479 testing::AssertionResult isPropertyImplied(const Environment &Env,
 480                                            ASTContext &ASTCtx, const Node *N,
 481                                            StringRef Property, bool Implies) {
 482   auto [Result, Prop] = getProperty(Env, ASTCtx, N, Property);
 483   if (!Prop)
 484     return Result;
 485   auto *BVProp = cast<BoolValue>(Prop);
 486   if (Env.proves(BVProp->formula()) != Implies)
 487     return testing::AssertionFailure()
 488            << Property << " is " << (Implies ? "not" : "") << " implied"
 489            << ", but should " << (Implies ? "" : "not ") << "be";
 490   return testing::AssertionSuccess();
 491 }
 492
 493 template <typename Node>
 494 testing::AssertionResult isNegative(const Node *N, ASTContext &ASTCtx,
 495                                     const Environment &Env) {
 496   testing::AssertionResult R = isPropertyImplied(Env, ASTCtx, N, "neg", true);
 497   if (!R)
 498     return R;
 499   R = isPropertyImplied(Env, ASTCtx, N, "zero", false);
 500   if (!R)
 501     return R;
 502   return isPropertyImplied(Env, ASTCtx, N, "pos", false);
 503 }
 504 template <typename Node>
 505 testing::AssertionResult isPositive(const Node *N, ASTContext &ASTCtx,
 506                                     const Environment &Env) {
 507   testing::AssertionResult R = isPropertyImplied(Env, ASTCtx, N, "pos", true);
 508   if (!R)
 509     return R;
 510   R = isPropertyImplied(Env, ASTCtx, N, "zero", false);
 511   if (!R)
 512     return R;
 513   return isPropertyImplied(Env, ASTCtx, N, "neg", false);
 514 }
 515 template <typename Node>
 516 testing::AssertionResult isZero(const Node *N, ASTContext &ASTCtx,
 517                                 const Environment &Env) {
 518   testing::AssertionResult R = isPropertyImplied(Env, ASTCtx, N, "zero", true);
 519   if (!R)
 520     return R;
 521   R = isPropertyImplied(Env, ASTCtx, N, "pos", false);
 522   if (!R)
 523     return R;
 524   return isPropertyImplied(Env, ASTCtx, N, "neg", false);
 525 }
 526 template <typename Node>
 527 testing::AssertionResult isTop(const Node *N, ASTContext &ASTCtx,
 528                                const Environment &Env) {
 529   testing::AssertionResult R = isPropertyImplied(Env, ASTCtx, N, "zero", false);
 530   if (!R)
 531     return R;
 532   R = isPropertyImplied(Env, ASTCtx, N, "pos", false);
 533   if (!R)
 534     return R;
 535   return isPropertyImplied(Env, ASTCtx, N, "neg", false);
 536 }
 537
 538 TEST(SignAnalysisTest, Init) {
 539   std::string Code = R"(
 540     int foo();
 541     void fun() {
 542       int a = -1;
 543       int b = 0;
 544       int c = 1;
 545       int d;
 546       int e = foo();
 547       int f = c;
 548       // [[p]]
 549     }
 550   )";
 551   runDataflow(
 552       Code,
 553       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
 554          ASTContext &ASTCtx) {
 555         // ASTCtx.getTranslationUnitDecl()->dump();
 556         ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
 557         const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
 558
 559         const ValueDecl *A = findValueDecl(ASTCtx, "a");
 560         const ValueDecl *B = findValueDecl(ASTCtx, "b");
 561         const ValueDecl *C = findValueDecl(ASTCtx, "c");
 562         const ValueDecl *D = findValueDecl(ASTCtx, "d");
 563         const ValueDecl *E = findValueDecl(ASTCtx, "e");
 564         const ValueDecl *F = findValueDecl(ASTCtx, "f");
 565
 566         EXPECT_TRUE(isNegative(A, ASTCtx, Env));
 567         EXPECT_TRUE(isZero(B, ASTCtx, Env));
 568         EXPECT_TRUE(isPositive(C, ASTCtx, Env));
 569         EXPECT_TRUE(isTop(D, ASTCtx, Env));
 570         EXPECT_TRUE(isTop(E, ASTCtx, Env));
 571         EXPECT_TRUE(isPositive(F, ASTCtx, Env));
 572       },
 573       LangStandard::lang_cxx17);
 574 }
 575
 576 TEST(SignAnalysisTest, UnaryMinus) {
 577   std::string Code = R"(
 578     void fun() {
 579       int a = 1;
 580       int b = -a;
 581       // [[p]]
 582     }
 583   )";
 584   runDataflow(
 585       Code,
 586       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
 587          ASTContext &ASTCtx) {
 588         ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
 589         const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
 590
 591         const ValueDecl *A = findValueDecl(ASTCtx, "a");
 592         const ValueDecl *B = findValueDecl(ASTCtx, "b");
 593         EXPECT_TRUE(isPositive(A, ASTCtx, Env));
 594         EXPECT_TRUE(isNegative(B, ASTCtx, Env));
 595       },
 596       LangStandard::lang_cxx17);
 597 }
 598
 599 TEST(SignAnalysisTest, UnaryNot) {
 600   std::string Code = R"(
 601     void fun() {
 602       int a = 2;
 603       int b = !a;
 604       // [[p]]
 605     }
 606   )";
 607   runDataflow(
 608       Code,
 609       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
 610          ASTContext &ASTCtx) {
 611         ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
 612         const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
 613
 614         const ValueDecl *A = findValueDecl(ASTCtx, "a");
 615         const ValueDecl *B = findValueDecl(ASTCtx, "b");
 616         EXPECT_TRUE(isPositive(A, ASTCtx, Env));
 617         EXPECT_TRUE(isZero(B, ASTCtx, Env));
 618       },
 619       LangStandard::lang_cxx17);
 620 }
 621
 622 TEST(SignAnalysisTest, UnaryNotInIf) {
 623   std::string Code = R"(
 624     int foo();
 625     void fun() {
 626       int a = foo();
 627       if (!a) {
 628         int b1;
 629         int p_a = a;
 630         int p_not_a = !a;
 631         // [[p]]
 632       } else {
 633         int q_a = a;
 634         int q_not_a = !a;
 635         // [[q]]
 636       }
 637     }
 638   )";
 639   runDataflow(
 640       Code,
 641       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
 642          ASTContext &ASTCtx) {
 643         ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q"));
 644         const Environment &EnvP = getEnvironmentAtAnnotation(Results, "p");
 645         const Environment &EnvQ = getEnvironmentAtAnnotation(Results, "q");
 646
 647         const ValueDecl *A = findValueDecl(ASTCtx, "a");
 648         const ValueDecl *PA = findValueDecl(ASTCtx, "p_a");
 649         const ValueDecl *PNA = findValueDecl(ASTCtx, "p_not_a");
 650         const ValueDecl *QA = findValueDecl(ASTCtx, "q_a");
 651         const ValueDecl *QNA = findValueDecl(ASTCtx, "q_not_a");
 652
 653         // p
 654         EXPECT_TRUE(isZero(A, ASTCtx, EnvP));
 655         EXPECT_TRUE(isZero(PA, ASTCtx, EnvP));
 656         EXPECT_TRUE(isTop(PNA, ASTCtx, EnvP));
 657
 658         // q
 659         EXPECT_TRUE(isTop(A, ASTCtx, EnvQ));
 660         EXPECT_TRUE(isTop(QA, ASTCtx, EnvQ));
 661         EXPECT_TRUE(isZero(QNA, ASTCtx, EnvQ));
 662       },
 663       LangStandard::lang_cxx17);
 664 }
 665
 666 TEST(SignAnalysisTest, BinaryGT) {
 667   std::string Code = R"(
 668     int foo();
 669     void fun() {
 670       int a = foo();
 671       int b = 1;
 672       if (a > 1) {
 673         (void)0;
 674         // [[p]]
 675       }
 676       if (a > 0) {
 677         (void)0;
 678         // [[q]]
 679       }
 680       if (a > -1) {
 681         (void)0;
 682         // [[r]]
 683       }
 684       if (a > b) {
 685         (void)0;
 686         // [[s]]
 687       }
 688     }
 689   )";
 690   runDataflow(
 691       Code,
 692       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
 693          ASTContext &ASTCtx) {
 694         ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q", "r", "s"));
 695         const Environment &EnvP = getEnvironmentAtAnnotation(Results, "p");
 696         const Environment &EnvQ = getEnvironmentAtAnnotation(Results, "q");
 697         const Environment &EnvR = getEnvironmentAtAnnotation(Results, "r");
 698         const Environment &EnvS = getEnvironmentAtAnnotation(Results, "s");
 699
 700         const ValueDecl *A = findValueDecl(ASTCtx, "a");
 701
 702         // p
 703         EXPECT_TRUE(isPositive(A, ASTCtx, EnvP));
 704         // q
 705         EXPECT_TRUE(isPositive(A, ASTCtx, EnvQ));
 706         // r
 707         EXPECT_TRUE(isTop(A, ASTCtx, EnvR));
 708         // s
 709         EXPECT_TRUE(isPositive(A, ASTCtx, EnvS));
 710       },
 711       LangStandard::lang_cxx17);
 712 }
 713
 714 TEST(SignAnalysisTest, BinaryLT) {
 715   std::string Code = R"(
 716     int foo();
 717     void fun() {
 718       int a = foo();
 719       int b = -1;
 720       if (a < -1) {
 721         (void)0;
 722         // [[p]]
 723       }
 724       if (a < 0) {
 725         (void)0;
 726         // [[q]]
 727       }
 728       if (a < 1) {
 729         (void)0;
 730         // [[r]]
 731       }
 732       if (a < b) {
 733         (void)0;
 734         // [[s]]
 735       }
 736     }
 737   )";
 738   runDataflow(
 739       Code,
 740       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
 741          ASTContext &ASTCtx) {
 742         ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q", "r", "s"));
 743         const Environment &EnvP = getEnvironmentAtAnnotation(Results, "p");
 744         const Environment &EnvQ = getEnvironmentAtAnnotation(Results, "q");
 745         const Environment &EnvR = getEnvironmentAtAnnotation(Results, "r");
 746         const Environment &EnvS = getEnvironmentAtAnnotation(Results, "s");
 747
 748         const ValueDecl *A = findValueDecl(ASTCtx, "a");
 749
 750         // p
 751         EXPECT_TRUE(isNegative(A, ASTCtx, EnvP));
 752         // q
 753         EXPECT_TRUE(isNegative(A, ASTCtx, EnvQ));
 754         // r
 755         EXPECT_TRUE(isTop(A, ASTCtx, EnvR));
 756         // s
 757         EXPECT_TRUE(isNegative(A, ASTCtx, EnvS));
 758       },
 759       LangStandard::lang_cxx17);
 760 }
 761
 762 TEST(SignAnalysisTest, BinaryGE) {
 763   std::string Code = R"(
 764     int foo();
 765     void fun() {
 766       int a = foo();
 767       int b = 1;
 768       if (a >= 1) {
 769         (void)0;
 770         // [[p]]
 771       }
 772       if (a >= 0) {
 773         (void)0;
 774         // [[q]]
 775       }
 776       if (a >= -1) {
 777         (void)0;
 778         // [[r]]
 779       }
 780       if (a >= b) {
 781         (void)0;
 782         // [[s]]
 783       }
 784     }
 785   )";
 786   runDataflow(
 787       Code,
 788       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
 789          ASTContext &ASTCtx) {
 790         ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q", "r", "s"));
 791         const Environment &EnvP = getEnvironmentAtAnnotation(Results, "p");
 792         const Environment &EnvQ = getEnvironmentAtAnnotation(Results, "q");
 793         const Environment &EnvR = getEnvironmentAtAnnotation(Results, "r");
 794         const Environment &EnvS = getEnvironmentAtAnnotation(Results, "s");
 795
 796         const ValueDecl *A = findValueDecl(ASTCtx, "a");
 797
 798         // p
 799         EXPECT_TRUE(isPositive(A, ASTCtx, EnvP));
 800         // q
 801         EXPECT_TRUE(isTop(A, ASTCtx, EnvQ));
 802         // r
 803         EXPECT_TRUE(isTop(A, ASTCtx, EnvR));
 804         // s
 805         EXPECT_TRUE(isPositive(A, ASTCtx, EnvS));
 806       },
 807       LangStandard::lang_cxx17);
 808 }
 809
 810 TEST(SignAnalysisTest, BinaryLE) {
 811   std::string Code = R"(
 812     int foo();
 813     void fun() {
 814       int a = foo();
 815       int b = -1;
 816       if (a <= -1) {
 817         (void)0;
 818         // [[p]]
 819       }
 820       if (a <= 0) {
 821         (void)0;
 822         // [[q]]
 823       }
 824       if (a <= 1) {
 825         (void)0;
 826         // [[r]]
 827       }
 828       if (a <= b) {
 829         (void)0;
 830         // [[s]]
 831       }
 832     }
 833   )";
 834   runDataflow(
 835       Code,
 836       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
 837          ASTContext &ASTCtx) {
 838         ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q", "r", "s"));
 839         const Environment &EnvP = getEnvironmentAtAnnotation(Results, "p");
 840         const Environment &EnvQ = getEnvironmentAtAnnotation(Results, "q");
 841         const Environment &EnvR = getEnvironmentAtAnnotation(Results, "r");
 842         const Environment &EnvS = getEnvironmentAtAnnotation(Results, "s");
 843
 844         const ValueDecl *A = findValueDecl(ASTCtx, "a");
 845
 846         // p
 847         EXPECT_TRUE(isNegative(A, ASTCtx, EnvP));
 848         // q
 849         EXPECT_TRUE(isTop(A, ASTCtx, EnvQ));
 850         // r
 851         EXPECT_TRUE(isTop(A, ASTCtx, EnvR));
 852         // s
 853         EXPECT_TRUE(isNegative(A, ASTCtx, EnvS));
 854       },
 855       LangStandard::lang_cxx17);
 856 }
 857
 858 TEST(SignAnalysisTest, BinaryEQ) {
 859   std::string Code = R"(
 860     int foo();
 861     void fun() {
 862       int a = foo();
 863       if (a == -1) {
 864         (void)0;
 865         // [[n]]
 866       }
 867       if (a == 0) {
 868         (void)0;
 869         // [[z]]
 870       }
 871       if (a == 1) {
 872         (void)0;
 873         // [[p]]
 874       }
 875     }
 876   )";
 877   runDataflow(
 878       Code,
 879       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
 880          ASTContext &ASTCtx) {
 881         ASSERT_THAT(Results.keys(), UnorderedElementsAre("n", "z", "p"));
 882         const Environment &EnvN = getEnvironmentAtAnnotation(Results, "n");
 883         const Environment &EnvZ = getEnvironmentAtAnnotation(Results, "z");
 884         const Environment &EnvP = getEnvironmentAtAnnotation(Results, "p");
 885
 886         const ValueDecl *A = findValueDecl(ASTCtx, "a");
 887
 888         // n
 889         EXPECT_TRUE(isNegative(A, ASTCtx, EnvN));
 890         // z
 891         EXPECT_TRUE(isZero(A, ASTCtx, EnvZ));
 892         // p
 893         EXPECT_TRUE(isPositive(A, ASTCtx, EnvP));
 894       },
 895       LangStandard::lang_cxx17);
 896 }
 897
 898 TEST(SignAnalysisTest, JoinToTop) {
 899   std::string Code = R"(
 900     int foo();
 901     void fun(bool b) {
 902       int a = foo();
 903       if (b) {
 904         a = -1;
 905         (void)0;
 906         // [[p]]
 907       } else {
 908         a = 1;
 909         (void)0;
 910         // [[q]]
 911       }
 912       (void)0;
 913       // [[r]]
 914     }
 915   )";
 916   runDataflow(
 917       Code,
 918       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
 919          ASTContext &ASTCtx) {
 920         ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q", "r"));
 921         const Environment &EnvP = getEnvironmentAtAnnotation(Results, "p");
 922         const Environment &EnvQ = getEnvironmentAtAnnotation(Results, "q");
 923         const Environment &EnvR = getEnvironmentAtAnnotation(Results, "r");
 924
 925         const ValueDecl *A = findValueDecl(ASTCtx, "a");
 926
 927         // p
 928         EXPECT_TRUE(isNegative(A, ASTCtx, EnvP));
 929         // q
 930         EXPECT_TRUE(isPositive(A, ASTCtx, EnvQ));
 931         // r
 932         EXPECT_TRUE(isTop(A, ASTCtx, EnvR));
 933       },
 934       LangStandard::lang_cxx17);
 935 }
 936
 937 TEST(SignAnalysisTest, JoinToNeg) {
 938   std::string Code = R"(
 939     int foo();
 940     void fun() {
 941       int a = foo();
 942       if (a < 1) {
 943         a = -1;
 944         (void)0;
 945         // [[p]]
 946       } else {
 947         a = -1;
 948         (void)0;
 949         // [[q]]
 950       }
 951       (void)0;
 952       // [[r]]
 953     }
 954   )";
 955   runDataflow(
 956       Code,
 957       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
 958          ASTContext &ASTCtx) {
 959         ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q", "r"));
 960         const Environment &EnvP = getEnvironmentAtAnnotation(Results, "p");
 961         const Environment &EnvQ = getEnvironmentAtAnnotation(Results, "q");
 962         const Environment &EnvR = getEnvironmentAtAnnotation(Results, "r");
 963
 964         const ValueDecl *A = findValueDecl(ASTCtx, "a");
 965
 966         // p
 967         EXPECT_TRUE(isNegative(A, ASTCtx, EnvP));
 968         // q
 969         EXPECT_TRUE(isNegative(A, ASTCtx, EnvQ));
 970         // r
 971         EXPECT_TRUE(isNegative(A, ASTCtx, EnvR));
 972       },
 973       LangStandard::lang_cxx17);
 974 }
 975
 976 TEST(SignAnalysisTest, NestedIfs) {
 977   std::string Code = R"(
 978     int foo();
 979     void fun() {
 980       int a = foo();
 981       if (a >= 0) {
 982         (void)0;
 983         // [[p]]
 984         if (a == 0) {
 985           (void)0;
 986           // [[q]]
 987         }
 988       }
 989       (void)0;
 990       // [[r]]
 991     }
 992   )";
 993   runDataflow(
 994       Code,
 995       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
 996          ASTContext &ASTCtx) {
 997         ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q", "r"));
 998         const Environment &EnvP = getEnvironmentAtAnnotation(Results, "p");
 999         const Environment &EnvQ = getEnvironmentAtAnnotation(Results, "q");
1000         const Environment &EnvR = getEnvironmentAtAnnotation(Results, "r");
1001
1002         const ValueDecl *A = findValueDecl(ASTCtx, "a");
1003
1004         // p
1005         EXPECT_TRUE(isTop(A, ASTCtx, EnvP));
1006         // q
1007         EXPECT_TRUE(isZero(A, ASTCtx, EnvQ));
1008         // r
1009         EXPECT_TRUE(isTop(A, ASTCtx, EnvR));
1010       },
1011       LangStandard::lang_cxx17);
1012 }
1013
1014 } // namespace