xref: /llvm-project/clang/unittests/Analysis/FlowSensitive/SignAnalysisTest.cpp (revision 672fb27b267edc5dec4939b0295c8eebcdc57467) 
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 
getSign(int64_t V)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 
initNegative(Value & Val,Environment & Env)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 }
initPositive(Value & Val,Environment & Env)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 }
initZero(Value & Val,Environment & Env)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 };
setSignProperties(Value & Val,const SignProperties & Ps)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 }
initUnknown(Value & Val,Environment & Env)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 }
getSignProperties(const Value & Val,const Environment & Env)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 
transferUninitializedInt(const DeclStmt * D,const MatchFinder::MatchResult & M,LatticeTransferState & State)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>
getValueAndSignProperties(const UnaryOperator * UO,const MatchFinder::MatchResult & M,LatticeTransferState & State)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 
transferBinary(const BinaryOperator * BO,const MatchFinder::MatchResult & M,LatticeTransferState & State)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 
transferUnaryMinus(const UnaryOperator * UO,const MatchFinder::MatchResult & M,LatticeTransferState & State)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 
transferUnaryNot(const UnaryOperator * UO,const MatchFinder::MatchResult & M,LatticeTransferState & State)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.
getOrCreateValue(const Expr * E,Environment & Env)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 
transferExpr(const Expr * E,const MatchFinder::MatchResult & M,LatticeTransferState & State)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 
refToVar()316 auto refToVar() { return declRefExpr(to(varDecl().bind(kVar))); }
317 
buildTransferMatchSwitch()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:
SignPropagationAnalysis(ASTContext & Context)357   SignPropagationAnalysis(ASTContext &Context)
358       : DataflowAnalysis<SignPropagationAnalysis, NoopLattice>(Context),
359         TransferMatchSwitch(buildTransferMatchSwitch()) {}
360 
initialElement()361   static NoopLattice initialElement() { return {}; }
362 
transfer(const CFGElement & Elt,NoopLattice & L,Environment & Env)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 
joinBoolValues(BoolValue & Bool1,const Environment & Env1,BoolValue & Bool2,const Environment & Env2,Environment & JoinedEnv)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 
join(QualType Type,const Value & Val1,const Environment & Env1,const Value & Val2,const Environment & Env2,Value & JoinedVal,Environment & JoinedEnv)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>
runDataflow(llvm::StringRef Code,Matcher Match,LangStandard::Kind Std=LangStandard::lang_cxx17,llvm::StringRef TargetFun="fun")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>
findFirst(ASTContext & ASTCtx,const MatcherType & M)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 *>
getProperty(const Environment & Env,ASTContext & ASTCtx,const Node * N,StringRef Property)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>
isPropertyImplied(const Environment & Env,ASTContext & ASTCtx,const Node * N,StringRef Property,bool Implies)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>
isNegative(const Node * N,ASTContext & ASTCtx,const Environment & Env)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>
isPositive(const Node * N,ASTContext & ASTCtx,const Environment & Env)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>
isZero(const Node * N,ASTContext & ASTCtx,const Environment & Env)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>
isTop(const Node * N,ASTContext & ASTCtx,const Environment & Env)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 
TEST(SignAnalysisTest,Init)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 
TEST(SignAnalysisTest,UnaryMinus)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 
TEST(SignAnalysisTest,UnaryNot)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 
TEST(SignAnalysisTest,UnaryNotInIf)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 
TEST(SignAnalysisTest,BinaryGT)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 
TEST(SignAnalysisTest,BinaryLT)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 
TEST(SignAnalysisTest,BinaryGE)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 
TEST(SignAnalysisTest,BinaryLE)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 
TEST(SignAnalysisTest,BinaryEQ)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 
TEST(SignAnalysisTest,ComplexLoopCondition)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 
TEST(SignAnalysisTest,JoinToTop)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 
TEST(SignAnalysisTest,JoinToNeg)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 
TEST(SignAnalysisTest,NestedIfs)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
1040