Debian Codegraph @

llvm-project/clang/unittests/Analysis/FlowSensitive/SignAnalysisTest.cpp

raw
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 =
92 State.Env.getStorageLocation(*Var, SkipPast::None);
93 Value *Val = State.Env.getValue(*Loc);
94 initUnknown(*Val, State.Env);
95 }
96
97 // Get the Value (1), the properties for the operand (2), and the properties
98 // for the unary operator (3). The return value is a tuple of (1,2,3).
99 //
100 // The returned Value (1) is a nullptr, if there is no Value associated to the
101 // operand of the unary operator, or if the properties are not set for that
102 // operand.
103 // Other than that, new sign properties are created for the Value of the
104 // unary operator and a new Value is created for the unary operator itself if
105 // it hadn't have any previously.
106 std::tuple<Value *, SignProperties, SignProperties>
107 getValueAndSignProperties(const UnaryOperator *UO,
108 const MatchFinder::MatchResult &M,
109 LatticeTransferState &State) {
110 // The DeclRefExpr refers to this variable in the operand.
111 const auto *OperandVar = M.Nodes.getNodeAs<clang::VarDecl>(kVar);
112 assert(OperandVar != nullptr);
113 const auto *OperandValue = State.Env.getValue(*OperandVar, SkipPast::None);
114 if (!OperandValue)
115 return {nullptr, {}, {}};
116
117 // Value of the unary op.
118 auto *UnaryOpValue = State.Env.getValue(*UO, SkipPast::None);
119 if (!UnaryOpValue) {
120 auto &Loc = State.Env.createStorageLocation(*UO);
121 State.Env.setStorageLocation(*UO, Loc);
122 UnaryOpValue = &State.Env.makeAtomicBoolValue();
123 State.Env.setValue(Loc, *UnaryOpValue);
124 }
125
126 // Properties for the operand (sub expression).
127 SignProperties OperandProps = getSignProperties(*OperandValue, State.Env);
128 if (OperandProps.Neg == nullptr)
129 return {nullptr, {}, {}};
130 // Properties for the operator expr itself.
131 SignProperties UnaryOpProps = initUnknown(*UnaryOpValue, State.Env);
132 return {UnaryOpValue, UnaryOpProps, OperandProps};
133 }
134
135 void transferBinary(const BinaryOperator *BO, const MatchFinder::MatchResult &M,
136 LatticeTransferState &State) {
137 StorageLocation *Loc = State.Env.getStorageLocation(*BO, SkipPast::None);
138 if (!Loc) {
139 Loc = &State.Env.createStorageLocation(*BO);
140 State.Env.setStorageLocation(*BO, *Loc);
141 }
142 BoolValue *Comp = cast_or_null<BoolValue>(State.Env.getValue(*Loc));
143 if (!Comp) {
144 Comp = &State.Env.makeAtomicBoolValue();
145 State.Env.setValue(*Loc, *Comp);
146 }
147
148 // FIXME Use this as well:
149 // auto *NegatedComp = &State.Env.makeNot(*Comp);
150
151 auto *LHS = State.Env.getValue(*BO->getLHS(), SkipPast::None);
152 auto *RHS = State.Env.getValue(*BO->getRHS(), SkipPast::None);
153
154 if (!LHS || !RHS)
155 return;
156
157 SignProperties LHSProps = getSignProperties(*LHS, State.Env);
158 SignProperties RHSProps = getSignProperties(*RHS, State.Env);
159 if (LHSProps.Neg == nullptr || RHSProps.Neg == nullptr)
160 return;
161
162 switch (BO->getOpcode()) {
163 case BO_GT:
164 // pos > pos
165 State.Env.addToFlowCondition(State.Env.makeImplication(
166 *Comp, State.Env.makeImplication(*RHSProps.Pos, *LHSProps.Pos)));
167 // pos > zero
168 State.Env.addToFlowCondition(State.Env.makeImplication(
169 *Comp, State.Env.makeImplication(*RHSProps.Zero, *LHSProps.Pos)));
170 break;
171 case BO_LT:
172 // neg < neg
173 State.Env.addToFlowCondition(State.Env.makeImplication(
174 *Comp, State.Env.makeImplication(*RHSProps.Neg, *LHSProps.Neg)));
175 // neg < zero
176 State.Env.addToFlowCondition(State.Env.makeImplication(
177 *Comp, State.Env.makeImplication(*RHSProps.Zero, *LHSProps.Neg)));
178 break;
179 case BO_GE:
180 // pos >= pos
181 State.Env.addToFlowCondition(State.Env.makeImplication(
182 *Comp, State.Env.makeImplication(*RHSProps.Pos, *LHSProps.Pos)));
183 break;
184 case BO_LE:
185 // neg <= neg
186 State.Env.addToFlowCondition(State.Env.makeImplication(
187 *Comp, State.Env.makeImplication(*RHSProps.Neg, *LHSProps.Neg)));
188 break;
189 case BO_EQ:
190 State.Env.addToFlowCondition(State.Env.makeImplication(
191 *Comp, State.Env.makeImplication(*RHSProps.Neg, *LHSProps.Neg)));
192 State.Env.addToFlowCondition(State.Env.makeImplication(
193 *Comp, State.Env.makeImplication(*RHSProps.Zero, *LHSProps.Zero)));
194 State.Env.addToFlowCondition(State.Env.makeImplication(
195 *Comp, State.Env.makeImplication(*RHSProps.Pos, *LHSProps.Pos)));
196 break;
197 case BO_NE: // Noop.
198 break;
199 default:
200 llvm_unreachable("not implemented");
201 }
202 }
203
204 void transferUnaryMinus(const UnaryOperator *UO,
205 const MatchFinder::MatchResult &M,
206 LatticeTransferState &State) {
207 auto [UnaryOpValue, UnaryOpProps, OperandProps] =
208 getValueAndSignProperties(UO, M, State);
209 if (!UnaryOpValue)
210 return;
211
212 // a is pos ==> -a is neg
213 State.Env.addToFlowCondition(
214 State.Env.makeImplication(*OperandProps.Pos, *UnaryOpProps.Neg));
215 // a is neg ==> -a is pos
216 State.Env.addToFlowCondition(
217 State.Env.makeImplication(*OperandProps.Neg, *UnaryOpProps.Pos));
218 // a is zero ==> -a is zero
219 State.Env.addToFlowCondition(
220 State.Env.makeImplication(*OperandProps.Zero, *UnaryOpProps.Zero));
221 }
222
223 void transferUnaryNot(const UnaryOperator *UO,
224 const MatchFinder::MatchResult &M,
225 LatticeTransferState &State) {
226 auto [UnaryOpValue, UnaryOpProps, OperandProps] =
227 getValueAndSignProperties(UO, M, State);
228 if (!UnaryOpValue)
229 return;
230
231 // a is neg or pos ==> !a is zero
232 State.Env.addToFlowCondition(State.Env.makeImplication(
233 State.Env.makeOr(*OperandProps.Pos, *OperandProps.Neg),
234 *UnaryOpProps.Zero));
235
236 // FIXME Handle this logic universally, not just for unary not. But Where to
237 // put the generic handler, transferExpr maybe?
238 if (auto *UOBoolVal = dyn_cast<BoolValue>(UnaryOpValue)) {
239 // !a <==> a is zero
240 State.Env.addToFlowCondition(
241 State.Env.makeIff(*UOBoolVal, *OperandProps.Zero));
242 // !a <==> !a is not zero
243 State.Env.addToFlowCondition(
244 State.Env.makeIff(*UOBoolVal, State.Env.makeNot(*UnaryOpProps.Zero)));
245 }
246 }
247
248 void transferExpr(const Expr *E, const MatchFinder::MatchResult &M,
249 LatticeTransferState &State) {
250 const ASTContext &Context = *M.Context;
251 StorageLocation *Loc = State.Env.getStorageLocation(*E, SkipPast::None);
252 if (!Loc) {
253 Loc = &State.Env.createStorageLocation(*E);
254 State.Env.setStorageLocation(*E, *Loc);
255 }
256 Value *Val = State.Env.getValue(*Loc);
257 if (!Val) {
258 Val = State.Env.createValue(Context.IntTy);
259 State.Env.setValue(*Loc, *Val);
260 }
261 // The sign symbolic values have been initialized already.
262 if (Val->getProperty("neg"))
263 return;
264
265 Expr::EvalResult R;
266 // An integer expression which we cannot evaluate.
267 if (!(E->EvaluateAsInt(R, Context) && R.Val.isInt())) {
268 initUnknown(*Val, State.Env);
269 return;
270 }
271
272 const Sign S = getSign(R.Val.getInt().getExtValue());
273 switch (S) {
274 case Sign::Negative:
275 initNegative(*Val, State.Env);
276 break;
277 case Sign::Zero:
278 initZero(*Val, State.Env);
279 break;
280 case Sign::Positive:
281 initPositive(*Val, State.Env);
282 break;
283 }
284 }
285
286 auto refToVar() { return declRefExpr(to(varDecl().bind(kVar))); }
287
288 auto buildTransferMatchSwitch() {
289 // Note, the order of the cases is important, the most generic should be
290 // added last.
291 // FIXME Discover what happens if there are multiple matching ASTMatchers for
292 // one Stmt? All matching case's handler should be called and in what order?
293 return CFGMatchSwitchBuilder<LatticeTransferState>()
294 // a op b (comparison)
295 .CaseOfCFGStmt<BinaryOperator>(binaryOperator(isComparisonOperator()),
296 transferBinary)
297
298 // FIXME handle binop +,-,*,/
299
300 // -a
301 .CaseOfCFGStmt<UnaryOperator>(
302 unaryOperator(hasOperatorName("-"),
303 hasUnaryOperand(hasDescendant(refToVar()))),
304 transferUnaryMinus)
305
306 // !a
307 .CaseOfCFGStmt<UnaryOperator>(
308 unaryOperator(hasOperatorName("!"),
309 hasUnaryOperand(hasDescendant(refToVar()))),
310 transferUnaryNot)
311
312 // int a;
313 .CaseOfCFGStmt<DeclStmt>(declStmt(hasSingleDecl(varDecl(
314 decl().bind(kVar), hasType(isInteger()),
315 unless(hasInitializer(expr()))))),
316 transferUninitializedInt)
317
318 // constexpr int
319 .CaseOfCFGStmt<Expr>(expr(hasType(isInteger())), transferExpr)
320
321 .Build();
322 }
323
324 class SignPropagationAnalysis
325 : public DataflowAnalysis<SignPropagationAnalysis, NoopLattice> {
326 public:
327 SignPropagationAnalysis(ASTContext &Context)
328 : DataflowAnalysis<SignPropagationAnalysis, NoopLattice>(Context),
329 TransferMatchSwitch(buildTransferMatchSwitch()) {}
330
331 static NoopLattice initialElement() { return {}; }
332
333 void transfer(const CFGElement *Elt, NoopLattice &L, Environment &Env) {
334 LatticeTransferState State(L, Env);
335 TransferMatchSwitch(*Elt, getASTContext(), State);
336 }
337 bool merge(QualType Type, const Value &Val1, const Environment &Env1,
338 const Value &Val2, const Environment &Env2, Value &MergedVal,
339 Environment &MergedEnv) override;
340
341 private:
342 CFGMatchSwitch<TransferState<NoopLattice>> TransferMatchSwitch;
343 };
344
345 // Copied from crubit.
346 BoolValue &mergeBoolValues(BoolValue &Bool1, const Environment &Env1,
347 BoolValue &Bool2, const Environment &Env2,
348 Environment &MergedEnv) {
349 if (&Bool1 == &Bool2) {
350 return Bool1;
351 }
352
353 auto &MergedBool = MergedEnv.makeAtomicBoolValue();
354
355 // If `Bool1` and `Bool2` is constrained to the same true / false value,
356 // `MergedBool` can be constrained similarly without needing to consider the
357 // path taken - this simplifies the flow condition tracked in `MergedEnv`.
358 // Otherwise, information about which path was taken is used to associate
359 // `MergedBool` with `Bool1` and `Bool2`.
360 if (Env1.flowConditionImplies(Bool1) && Env2.flowConditionImplies(Bool2)) {
361 MergedEnv.addToFlowCondition(MergedBool);
362 } else if (Env1.flowConditionImplies(Env1.makeNot(Bool1)) &&
363 Env2.flowConditionImplies(Env2.makeNot(Bool2))) {
364 MergedEnv.addToFlowCondition(MergedEnv.makeNot(MergedBool));
365 }
366 return MergedBool;
367 }
368
369 bool SignPropagationAnalysis::merge(QualType Type, const Value &Val1,
370 const Environment &Env1, const Value &Val2,
371 const Environment &Env2, Value &MergedVal,
372 Environment &MergedEnv) {
373 if (!Type->isIntegerType())
374 return false;
375 SignProperties Ps1 = getSignProperties(Val1, Env1);
376 SignProperties Ps2 = getSignProperties(Val2, Env2);
377 if (!Ps1.Neg || !Ps2.Neg)
378 return false;
379 BoolValue &MergedNeg =
380 mergeBoolValues(*Ps1.Neg, Env1, *Ps2.Neg, Env2, MergedEnv);
381 BoolValue &MergedZero =
382 mergeBoolValues(*Ps1.Zero, Env1, *Ps2.Zero, Env2, MergedEnv);
383 BoolValue &MergedPos =
384 mergeBoolValues(*Ps1.Pos, Env1, *Ps2.Pos, Env2, MergedEnv);
385 setSignProperties(MergedVal,
386 SignProperties{&MergedNeg, &MergedZero, &MergedPos});
387 return true;
388 }
389
390 template <typename Matcher>
391 void runDataflow(llvm::StringRef Code, Matcher Match,
392 LangStandard::Kind Std = LangStandard::lang_cxx17,
393 llvm::StringRef TargetFun = "fun") {
394 using ast_matchers::hasName;
395 ASSERT_THAT_ERROR(
396 checkDataflow<SignPropagationAnalysis>(
397 AnalysisInputs<SignPropagationAnalysis>(
398 Code, hasName(TargetFun),
399 [](ASTContext &C, Environment &) {
400 return SignPropagationAnalysis(C);
401 })
402 .withASTBuildArgs(
403 {"-fsyntax-only", "-fno-delayed-template-parsing",
404 "-std=" +
405 std::string(LangStandard::getLangStandardForKind(Std)
406 .getName())}),
407 /*VerifyResults=*/
408 [&Match](const llvm::StringMap<DataflowAnalysisState<NoopLattice>>
409 &Results,
410 const AnalysisOutputs &AO) { Match(Results, AO.ASTCtx); }),
411 llvm::Succeeded());
412 }
413
414 // FIXME add this to testing support.
415 template <typename NodeType, typename MatcherType>
416 const NodeType *findFirst(ASTContext &ASTCtx, const MatcherType &M) {
417 auto TargetNodes = match(M.bind("v"), ASTCtx);
418 assert(TargetNodes.size() == 1 && "Match must be unique");
419 auto *const Result = selectFirst<NodeType>("v", TargetNodes);
420 assert(Result != nullptr);
421 return Result;
422 }
423
424 template <typename Node>
425 std::pair<testing::AssertionResult, Value *>
426 getProperty(const Environment &Env, ASTContext &ASTCtx, const Node *N,
427 StringRef Property) {
428 if (!N)
429 return {testing::AssertionFailure() << "No node", nullptr};
430 const StorageLocation *Loc = Env.getStorageLocation(*N, SkipPast::None);
431 if (!isa_and_nonnull<ScalarStorageLocation>(Loc))
432 return {testing::AssertionFailure() << "No location", nullptr};
433 const Value *Val = Env.getValue(*Loc);
434 if (!Val)
435 return {testing::AssertionFailure() << "No value", nullptr};
436 auto *Prop = Val->getProperty(Property);
437 if (!isa_and_nonnull<BoolValue>(Prop))
438 return {testing::AssertionFailure() << "No property for " << Property,
439 nullptr};
440 return {testing::AssertionSuccess(), Prop};
441 }
442
443 // Test if the given property of the given node is implied by the flow
444 // condition. If 'Implies' is false then check if it is not implied.
445 template <typename Node>
446 testing::AssertionResult isPropertyImplied(const Environment &Env,
447 ASTContext &ASTCtx, const Node *N,
448 StringRef Property, bool Implies) {
449 auto [Result, Prop] = getProperty(Env, ASTCtx, N, Property);
450 if (!Prop)
451 return Result;
452 auto *BVProp = cast<BoolValue>(Prop);
453 if (Env.flowConditionImplies(*BVProp) != Implies)
454 return testing::AssertionFailure()
455 << Property << " is " << (Implies ? "not" : "") << " implied"
456 << ", but should " << (Implies ? "" : "not ") << "be";
457 return testing::AssertionSuccess();
458 }
459
460 template <typename Node>
461 testing::AssertionResult isNegative(const Node *N, ASTContext &ASTCtx,
462 const Environment &Env) {
463 testing::AssertionResult R = isPropertyImplied(Env, ASTCtx, N, "neg", true);
464 if (!R)
465 return R;
466 R = isPropertyImplied(Env, ASTCtx, N, "zero", false);
467 if (!R)
468 return R;
469 return isPropertyImplied(Env, ASTCtx, N, "pos", false);
470 }
471 template <typename Node>
472 testing::AssertionResult isPositive(const Node *N, ASTContext &ASTCtx,
473 const Environment &Env) {
474 testing::AssertionResult R = isPropertyImplied(Env, ASTCtx, N, "pos", true);
475 if (!R)
476 return R;
477 R = isPropertyImplied(Env, ASTCtx, N, "zero", false);
478 if (!R)
479 return R;
480 return isPropertyImplied(Env, ASTCtx, N, "neg", false);
481 }
482 template <typename Node>
483 testing::AssertionResult isZero(const Node *N, ASTContext &ASTCtx,
484 const Environment &Env) {
485 testing::AssertionResult R = isPropertyImplied(Env, ASTCtx, N, "zero", true);
486 if (!R)
487 return R;
488 R = isPropertyImplied(Env, ASTCtx, N, "pos", false);
489 if (!R)
490 return R;
491 return isPropertyImplied(Env, ASTCtx, N, "neg", false);
492 }
493 template <typename Node>
494 testing::AssertionResult isTop(const Node *N, ASTContext &ASTCtx,
495 const Environment &Env) {
496 testing::AssertionResult R = isPropertyImplied(Env, ASTCtx, N, "zero", false);
497 if (!R)
498 return R;
499 R = isPropertyImplied(Env, ASTCtx, N, "pos", false);
500 if (!R)
501 return R;
502 return isPropertyImplied(Env, ASTCtx, N, "neg", false);
503 }
504
505 TEST(SignAnalysisTest, Init) {
506 std::string Code = R"(
507 int foo();
508 void fun() {
509 int a = -1;
510 int b = 0;
511 int c = 1;
512 int d;
513 int e = foo();
514 int f = c;
515 // [[p]]
516 }
517 )";
518 runDataflow(
519 Code,
520 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
521 ASTContext &ASTCtx) {
522 // ASTCtx.getTranslationUnitDecl()->dump();
523 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
524 const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
525
526 const ValueDecl *A = findValueDecl(ASTCtx, "a");
527 const ValueDecl *B = findValueDecl(ASTCtx, "b");
528 const ValueDecl *C = findValueDecl(ASTCtx, "c");
529 const ValueDecl *D = findValueDecl(ASTCtx, "d");
530 const ValueDecl *E = findValueDecl(ASTCtx, "e");
531 const ValueDecl *F = findValueDecl(ASTCtx, "f");
532
533 EXPECT_TRUE(isNegative(A, ASTCtx, Env));
534 EXPECT_TRUE(isZero(B, ASTCtx, Env));
535 EXPECT_TRUE(isPositive(C, ASTCtx, Env));
536 EXPECT_TRUE(isTop(D, ASTCtx, Env));
537 EXPECT_TRUE(isTop(E, ASTCtx, Env));
538 EXPECT_TRUE(isPositive(F, ASTCtx, Env));
539 },
540 LangStandard::lang_cxx17);
541 }
542
543 TEST(SignAnalysisTest, UnaryMinus) {
544 std::string Code = R"(
545 void fun() {
546 int a = 1;
547 int b = -a;
548 // [[p]]
549 }
550 )";
551 runDataflow(
552 Code,
553 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
554 ASTContext &ASTCtx) {
555 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
556 const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
557
558 const ValueDecl *A = findValueDecl(ASTCtx, "a");
559 const ValueDecl *B = findValueDecl(ASTCtx, "b");
560 EXPECT_TRUE(isPositive(A, ASTCtx, Env));
561 EXPECT_TRUE(isNegative(B, ASTCtx, Env));
562 },
563 LangStandard::lang_cxx17);
564 }
565
566 TEST(SignAnalysisTest, UnaryNot) {
567 std::string Code = R"(
568 void fun() {
569 int a = 2;
570 int b = !a;
571 // [[p]]
572 }
573 )";
574 runDataflow(
575 Code,
576 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
577 ASTContext &ASTCtx) {
578 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
579 const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
580
581 const ValueDecl *A = findValueDecl(ASTCtx, "a");
582 const ValueDecl *B = findValueDecl(ASTCtx, "b");
583 EXPECT_TRUE(isPositive(A, ASTCtx, Env));
584 EXPECT_TRUE(isZero(B, ASTCtx, Env));
585 },
586 LangStandard::lang_cxx17);
587 }
588
589 TEST(SignAnalysisTest, UnaryNotInIf) {
590 std::string Code = R"(
591 int foo();
592 void fun() {
593 int a = foo();
594 if (!a) {
595 int b1;
596 int p_a = a;
597 int p_not_a = !a;
598 // [[p]]
599 } else {
600 int q_a = a;
601 int q_not_a = !a;
602 // [[q]]
603 }
604 }
605 )";
606 runDataflow(
607 Code,
608 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
609 ASTContext &ASTCtx) {
610 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q"));
611 const Environment &EnvP = getEnvironmentAtAnnotation(Results, "p");
612 const Environment &EnvQ = getEnvironmentAtAnnotation(Results, "q");
613
614 const ValueDecl *A = findValueDecl(ASTCtx, "a");
615 const ValueDecl *PA = findValueDecl(ASTCtx, "p_a");
616 const ValueDecl *PNA = findValueDecl(ASTCtx, "p_not_a");
617 const ValueDecl *QA = findValueDecl(ASTCtx, "q_a");
618 const ValueDecl *QNA = findValueDecl(ASTCtx, "q_not_a");
619
620 // p
621 EXPECT_TRUE(isZero(A, ASTCtx, EnvP));
622 EXPECT_TRUE(isZero(PA, ASTCtx, EnvP));
623 EXPECT_TRUE(isTop(PNA, ASTCtx, EnvP));
624
625 // q
626 EXPECT_TRUE(isTop(A, ASTCtx, EnvQ));
627 EXPECT_TRUE(isTop(QA, ASTCtx, EnvQ));
628 EXPECT_TRUE(isZero(QNA, ASTCtx, EnvQ));
629 },
630 LangStandard::lang_cxx17);
631 }
632
633 TEST(SignAnalysisTest, BinaryGT) {
634 std::string Code = R"(
635 int foo();
636 void fun() {
637 int a = foo();
638 int b = 1;
639 if (a > 1) {
640 (void)0;
641 // [[p]]
642 }
643 if (a > 0) {
644 (void)0;
645 // [[q]]
646 }
647 if (a > -1) {
648 (void)0;
649 // [[r]]
650 }
651 if (a > b) {
652 (void)0;
653 // [[s]]
654 }
655 }
656 )";
657 runDataflow(
658 Code,
659 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
660 ASTContext &ASTCtx) {
661 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q", "r", "s"));
662 const Environment &EnvP = getEnvironmentAtAnnotation(Results, "p");
663 const Environment &EnvQ = getEnvironmentAtAnnotation(Results, "q");
664 const Environment &EnvR = getEnvironmentAtAnnotation(Results, "r");
665 const Environment &EnvS = getEnvironmentAtAnnotation(Results, "s");
666
667 const ValueDecl *A = findValueDecl(ASTCtx, "a");
668
669 // p
670 EXPECT_TRUE(isPositive(A, ASTCtx, EnvP));
671 // q
672 EXPECT_TRUE(isPositive(A, ASTCtx, EnvQ));
673 // r
674 EXPECT_TRUE(isTop(A, ASTCtx, EnvR));
675 // s
676 EXPECT_TRUE(isPositive(A, ASTCtx, EnvS));
677 },
678 LangStandard::lang_cxx17);
679 }
680
681 TEST(SignAnalysisTest, BinaryLT) {
682 std::string Code = R"(
683 int foo();
684 void fun() {
685 int a = foo();
686 int b = -1;
687 if (a < -1) {
688 (void)0;
689 // [[p]]
690 }
691 if (a < 0) {
692 (void)0;
693 // [[q]]
694 }
695 if (a < 1) {
696 (void)0;
697 // [[r]]
698 }
699 if (a < b) {
700 (void)0;
701 // [[s]]
702 }
703 }
704 )";
705 runDataflow(
706 Code,
707 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
708 ASTContext &ASTCtx) {
709 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q", "r", "s"));
710 const Environment &EnvP = getEnvironmentAtAnnotation(Results, "p");
711 const Environment &EnvQ = getEnvironmentAtAnnotation(Results, "q");
712 const Environment &EnvR = getEnvironmentAtAnnotation(Results, "r");
713 const Environment &EnvS = getEnvironmentAtAnnotation(Results, "s");
714
715 const ValueDecl *A = findValueDecl(ASTCtx, "a");
716
717 // p
718 EXPECT_TRUE(isNegative(A, ASTCtx, EnvP));
719 // q
720 EXPECT_TRUE(isNegative(A, ASTCtx, EnvQ));
721 // r
722 EXPECT_TRUE(isTop(A, ASTCtx, EnvR));
723 // s
724 EXPECT_TRUE(isNegative(A, ASTCtx, EnvS));
725 },
726 LangStandard::lang_cxx17);
727 }
728
729 TEST(SignAnalysisTest, BinaryGE) {
730 std::string Code = R"(
731 int foo();
732 void fun() {
733 int a = foo();
734 int b = 1;
735 if (a >= 1) {
736 (void)0;
737 // [[p]]
738 }
739 if (a >= 0) {
740 (void)0;
741 // [[q]]
742 }
743 if (a >= -1) {
744 (void)0;
745 // [[r]]
746 }
747 if (a >= b) {
748 (void)0;
749 // [[s]]
750 }
751 }
752 )";
753 runDataflow(
754 Code,
755 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
756 ASTContext &ASTCtx) {
757 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q", "r", "s"));
758 const Environment &EnvP = getEnvironmentAtAnnotation(Results, "p");
759 const Environment &EnvQ = getEnvironmentAtAnnotation(Results, "q");
760 const Environment &EnvR = getEnvironmentAtAnnotation(Results, "r");
761 const Environment &EnvS = getEnvironmentAtAnnotation(Results, "s");
762
763 const ValueDecl *A = findValueDecl(ASTCtx, "a");
764
765 // p
766 EXPECT_TRUE(isPositive(A, ASTCtx, EnvP));
767 // q
768 EXPECT_TRUE(isTop(A, ASTCtx, EnvQ));
769 // r
770 EXPECT_TRUE(isTop(A, ASTCtx, EnvR));
771 // s
772 EXPECT_TRUE(isPositive(A, ASTCtx, EnvS));
773 },
774 LangStandard::lang_cxx17);
775 }
776
777 TEST(SignAnalysisTest, BinaryLE) {
778 std::string Code = R"(
779 int foo();
780 void fun() {
781 int a = foo();
782 int b = -1;
783 if (a <= -1) {
784 (void)0;
785 // [[p]]
786 }
787 if (a <= 0) {
788 (void)0;
789 // [[q]]
790 }
791 if (a <= 1) {
792 (void)0;
793 // [[r]]
794 }
795 if (a <= b) {
796 (void)0;
797 // [[s]]
798 }
799 }
800 )";
801 runDataflow(
802 Code,
803 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
804 ASTContext &ASTCtx) {
805 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q", "r", "s"));
806 const Environment &EnvP = getEnvironmentAtAnnotation(Results, "p");
807 const Environment &EnvQ = getEnvironmentAtAnnotation(Results, "q");
808 const Environment &EnvR = getEnvironmentAtAnnotation(Results, "r");
809 const Environment &EnvS = getEnvironmentAtAnnotation(Results, "s");
810
811 const ValueDecl *A = findValueDecl(ASTCtx, "a");
812
813 // p
814 EXPECT_TRUE(isNegative(A, ASTCtx, EnvP));
815 // q
816 EXPECT_TRUE(isTop(A, ASTCtx, EnvQ));
817 // r
818 EXPECT_TRUE(isTop(A, ASTCtx, EnvR));
819 // s
820 EXPECT_TRUE(isNegative(A, ASTCtx, EnvS));
821 },
822 LangStandard::lang_cxx17);
823 }
824
825 TEST(SignAnalysisTest, BinaryEQ) {
826 std::string Code = R"(
827 int foo();
828 void fun() {
829 int a = foo();
830 if (a == -1) {
831 (void)0;
832 // [[n]]
833 }
834 if (a == 0) {
835 (void)0;
836 // [[z]]
837 }
838 if (a == 1) {
839 (void)0;
840 // [[p]]
841 }
842 }
843 )";
844 runDataflow(
845 Code,
846 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
847 ASTContext &ASTCtx) {
848 ASSERT_THAT(Results.keys(), UnorderedElementsAre("n", "z", "p"));
849 const Environment &EnvN = getEnvironmentAtAnnotation(Results, "n");
850 const Environment &EnvZ = getEnvironmentAtAnnotation(Results, "z");
851 const Environment &EnvP = getEnvironmentAtAnnotation(Results, "p");
852
853 const ValueDecl *A = findValueDecl(ASTCtx, "a");
854
855 // n
856 EXPECT_TRUE(isNegative(A, ASTCtx, EnvN));
857 // z
858 EXPECT_TRUE(isZero(A, ASTCtx, EnvZ));
859 // p
860 EXPECT_TRUE(isPositive(A, ASTCtx, EnvP));
861 },
862 LangStandard::lang_cxx17);
863 }
864
865 TEST(SignAnalysisTest, JoinToTop) {
866 std::string Code = R"(
867 int foo();
868 void fun(bool b) {
869 int a = foo();
870 if (b) {
871 a = -1;
872 (void)0;
873 // [[p]]
874 } else {
875 a = 1;
876 (void)0;
877 // [[q]]
878 }
879 (void)0;
880 // [[r]]
881 }
882 )";
883 runDataflow(
884 Code,
885 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
886 ASTContext &ASTCtx) {
887 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q", "r"));
888 const Environment &EnvP = getEnvironmentAtAnnotation(Results, "p");
889 const Environment &EnvQ = getEnvironmentAtAnnotation(Results, "q");
890 const Environment &EnvR = getEnvironmentAtAnnotation(Results, "r");
891
892 const ValueDecl *A = findValueDecl(ASTCtx, "a");
893
894 // p
895 EXPECT_TRUE(isNegative(A, ASTCtx, EnvP));
896 // q
897 EXPECT_TRUE(isPositive(A, ASTCtx, EnvQ));
898 // r
899 EXPECT_TRUE(isTop(A, ASTCtx, EnvR));
900 },
901 LangStandard::lang_cxx17);
902 }
903
904 TEST(SignAnalysisTest, JoinToNeg) {
905 std::string Code = R"(
906 int foo();
907 void fun() {
908 int a = foo();
909 if (a < 1) {
910 a = -1;
911 (void)0;
912 // [[p]]
913 } else {
914 a = -1;
915 (void)0;
916 // [[q]]
917 }
918 (void)0;
919 // [[r]]
920 }
921 )";
922 runDataflow(
923 Code,
924 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
925 ASTContext &ASTCtx) {
926 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q", "r"));
927 const Environment &EnvP = getEnvironmentAtAnnotation(Results, "p");
928 const Environment &EnvQ = getEnvironmentAtAnnotation(Results, "q");
929 const Environment &EnvR = getEnvironmentAtAnnotation(Results, "r");
930
931 const ValueDecl *A = findValueDecl(ASTCtx, "a");
932
933 // p
934 EXPECT_TRUE(isNegative(A, ASTCtx, EnvP));
935 // q
936 EXPECT_TRUE(isNegative(A, ASTCtx, EnvQ));
937 // r
938 EXPECT_TRUE(isNegative(A, ASTCtx, EnvR));
939 },
940 LangStandard::lang_cxx17);
941 }
942
943 TEST(SignAnalysisTest, NestedIfs) {
944 std::string Code = R"(
945 int foo();
946 void fun() {
947 int a = foo();
948 if (a >= 0) {
949 (void)0;
950 // [[p]]
951 if (a == 0) {
952 (void)0;
953 // [[q]]
954 }
955 }
956 (void)0;
957 // [[r]]
958 }
959 )";
960 runDataflow(
961 Code,
962 [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
963 ASTContext &ASTCtx) {
964 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q", "r"));
965 const Environment &EnvP = getEnvironmentAtAnnotation(Results, "p");
966 const Environment &EnvQ = getEnvironmentAtAnnotation(Results, "q");
967 const Environment &EnvR = getEnvironmentAtAnnotation(Results, "r");
968
969 const ValueDecl *A = findValueDecl(ASTCtx, "a");
970
971 // p
972 EXPECT_TRUE(isTop(A, ASTCtx, EnvP));
973 // q
974 EXPECT_TRUE(isZero(A, ASTCtx, EnvQ));
975 // r
976 EXPECT_TRUE(isTop(A, ASTCtx, EnvR));
977 },
978 LangStandard::lang_cxx17);
979 }
980
981 } // namespace