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
29namespace {
30
31using namespace clang;
32using namespace dataflow;
33using namespace ast_matchers;
34using namespace test;
35using ::testing::UnorderedElementsAre;
36
37enum class Sign : int { Negative, Zero, Positive };
38
39Sign getSign(int64_t V) {
40 return V == 0 ? Sign::Zero : (V < 0 ? Sign::Negative : Sign::Positive);
41}
42
43using LatticeTransferState = TransferState<NoopLattice>;
44
45constexpr char kVar[] = "var";
46
47void initNegative(Value &Val, Environment &Env) {
48 Val.setProperty(Name: "neg", Val&: Env.getBoolLiteralValue(Value: true));
49 Val.setProperty(Name: "zero", Val&: Env.getBoolLiteralValue(Value: false));
50 Val.setProperty(Name: "pos", Val&: Env.getBoolLiteralValue(Value: false));
51}
52void initPositive(Value &Val, Environment &Env) {
53 Val.setProperty(Name: "neg", Val&: Env.getBoolLiteralValue(Value: false));
54 Val.setProperty(Name: "zero", Val&: Env.getBoolLiteralValue(Value: false));
55 Val.setProperty(Name: "pos", Val&: Env.getBoolLiteralValue(Value: true));
56}
57void initZero(Value &Val, Environment &Env) {
58 Val.setProperty(Name: "neg", Val&: Env.getBoolLiteralValue(Value: false));
59 Val.setProperty(Name: "zero", Val&: Env.getBoolLiteralValue(Value: true));
60 Val.setProperty(Name: "pos", Val&: Env.getBoolLiteralValue(Value: 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.
66struct SignProperties {
67 BoolValue *Neg, *Zero, *Pos;
68};
69void setSignProperties(Value &Val, const SignProperties &Ps) {
70 Val.setProperty(Name: "neg", Val&: *Ps.Neg);
71 Val.setProperty(Name: "zero", Val&: *Ps.Zero);
72 Val.setProperty(Name: "pos", Val&: *Ps.Pos);
73}
74SignProperties initUnknown(Value &Val, Environment &Env) {
75 SignProperties Ps{.Neg: &Env.makeAtomicBoolValue(), .Zero: &Env.makeAtomicBoolValue(),
76 .Pos: &Env.makeAtomicBoolValue()};
77 setSignProperties(Val, Ps);
78 return Ps;
79}
80SignProperties getSignProperties(const Value &Val, const Environment &Env) {
81 return {.Neg: dyn_cast_or_null<BoolValue>(Val: Val.getProperty(Name: "neg")),
82 .Zero: dyn_cast_or_null<BoolValue>(Val: Val.getProperty(Name: "zero")),
83 .Pos: dyn_cast_or_null<BoolValue>(Val: Val.getProperty(Name: "pos"))};
84}
85
86void transferUninitializedInt(const DeclStmt *D,
87 const MatchFinder::MatchResult &M,
88 LatticeTransferState &State) {
89 const auto *Var = M.Nodes.getNodeAs<clang::VarDecl>(ID: kVar);
90 assert(Var != nullptr);
91 const StorageLocation *Loc = State.Env.getStorageLocation(*Var);
92 Value *Val = State.Env.getValue(Loc: *Loc);
93 initUnknown(Val&: *Val, Env&: 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.
105std::tuple<Value *, SignProperties, SignProperties>
106getValueAndSignProperties(const UnaryOperator *UO,
107 const MatchFinder::MatchResult &M,
108 LatticeTransferState &State) {
109 // The DeclRefExpr refers to this variable in the operand.
110 const auto *OperandVar = M.Nodes.getNodeAs<clang::VarDecl>(ID: kVar);
111 assert(OperandVar != nullptr);
112 const auto *OperandValue = State.Env.getValue(*OperandVar);
113 if (!OperandValue)
114 return {nullptr, {}, {}};
115
116 // Value of the unary op.
117 auto *UnaryOpValue = State.Env.getValue(*UO);
118 if (!UnaryOpValue) {
119 UnaryOpValue = &State.Env.makeAtomicBoolValue();
120 State.Env.setValue(*UO, *UnaryOpValue);
121 }
122
123 // Properties for the operand (sub expression).
124 SignProperties OperandProps = getSignProperties(*OperandValue, State.Env);
125 if (OperandProps.Neg == nullptr)
126 return {nullptr, {}, {}};
127 // Properties for the operator expr itself.
128 SignProperties UnaryOpProps = initUnknown(*UnaryOpValue, State.Env);
129 return {UnaryOpValue, UnaryOpProps, OperandProps};
130}
131
132void transferBinary(const BinaryOperator *BO, const MatchFinder::MatchResult &M,
133 LatticeTransferState &State) {
134 auto &A = State.Env.arena();
135 const Formula *Comp;
136 if (BoolValue *V = State.Env.get<BoolValue>(*BO)) {
137 Comp = &V->formula();
138 } else {
139 Comp = &A.makeAtomRef(A: 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(E: *BO->getLHS());
147 auto *RHS = State.Env.getValue(E: *BO->getRHS());
148
149 if (!LHS || !RHS)
150 return;
151
152 SignProperties LHSProps = getSignProperties(Val: *LHS, Env: State.Env);
153 SignProperties RHSProps = getSignProperties(Val: *RHS, Env: 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(LHS: *Comp, RHS: A.makeImplies(LHS: RHSProps.Pos->formula(),
162 RHS: LHSProps.Pos->formula())));
163 // pos > zero
164 State.Env.assume(
165 A.makeImplies(LHS: *Comp, RHS: A.makeImplies(LHS: RHSProps.Zero->formula(),
166 RHS: LHSProps.Pos->formula())));
167 break;
168 case BO_LT:
169 // neg < neg
170 State.Env.assume(
171 A.makeImplies(LHS: *Comp, RHS: A.makeImplies(LHS: RHSProps.Neg->formula(),
172 RHS: LHSProps.Neg->formula())));
173 // neg < zero
174 State.Env.assume(
175 A.makeImplies(LHS: *Comp, RHS: A.makeImplies(LHS: RHSProps.Zero->formula(),
176 RHS: LHSProps.Neg->formula())));
177 break;
178 case BO_GE:
179 // pos >= pos
180 State.Env.assume(
181 A.makeImplies(LHS: *Comp, RHS: A.makeImplies(LHS: RHSProps.Pos->formula(),
182 RHS: LHSProps.Pos->formula())));
183 break;
184 case BO_LE:
185 // neg <= neg
186 State.Env.assume(
187 A.makeImplies(LHS: *Comp, RHS: A.makeImplies(LHS: RHSProps.Neg->formula(),
188 RHS: LHSProps.Neg->formula())));
189 break;
190 case BO_EQ:
191 State.Env.assume(
192 A.makeImplies(LHS: *Comp, RHS: A.makeImplies(LHS: RHSProps.Neg->formula(),
193 RHS: LHSProps.Neg->formula())));
194 State.Env.assume(
195 A.makeImplies(LHS: *Comp, RHS: A.makeImplies(LHS: RHSProps.Zero->formula(),
196 RHS: LHSProps.Zero->formula())));
197 State.Env.assume(
198 A.makeImplies(LHS: *Comp, RHS: A.makeImplies(LHS: RHSProps.Pos->formula(),
199 RHS: LHSProps.Pos->formula())));
200 break;
201 case BO_NE: // Noop.
202 break;
203 default:
204 llvm_unreachable("not implemented");
205 }
206}
207
208void transferUnaryMinus(const UnaryOperator *UO,
209 const MatchFinder::MatchResult &M,
210 LatticeTransferState &State) {
211 auto &A = State.Env.arena();
212 auto [UnaryOpValue, UnaryOpProps, OperandProps] =
213 getValueAndSignProperties(UO, M, State);
214 if (!UnaryOpValue)
215 return;
216
217 // a is pos ==> -a is neg
218 State.Env.assume(
219 A.makeImplies(LHS: OperandProps.Pos->formula(), RHS: UnaryOpProps.Neg->formula()));
220 // a is neg ==> -a is pos
221 State.Env.assume(
222 A.makeImplies(LHS: OperandProps.Neg->formula(), RHS: UnaryOpProps.Pos->formula()));
223 // a is zero ==> -a is zero
224 State.Env.assume(A.makeImplies(LHS: OperandProps.Zero->formula(),
225 RHS: UnaryOpProps.Zero->formula()));
226}
227
228void transferUnaryNot(const UnaryOperator *UO,
229 const MatchFinder::MatchResult &M,
230 LatticeTransferState &State) {
231 auto &A = State.Env.arena();
232 auto [UnaryOpValue, UnaryOpProps, OperandProps] =
233 getValueAndSignProperties(UO, M, State);
234 if (!UnaryOpValue)
235 return;
236
237 // a is neg or pos ==> !a is zero
238 State.Env.assume(A.makeImplies(
239 LHS: A.makeOr(LHS: OperandProps.Pos->formula(), RHS: OperandProps.Neg->formula()),
240 RHS: 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>(Val: UnaryOpValue)) {
245 // !a <==> a is zero
246 State.Env.assume(
247 A.makeEquals(LHS: UOBoolVal->formula(), RHS: OperandProps.Zero->formula()));
248 // !a <==> !a is not zero
249 State.Env.assume(A.makeEquals(LHS: UOBoolVal->formula(),
250 RHS: A.makeNot(Val: 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.
260Value *getOrCreateValue(const Expr *E, Environment &Env) {
261 Value *Val = nullptr;
262 if (E->isGLValue()) {
263 StorageLocation *Loc = Env.getStorageLocation(E: *E);
264 if (!Loc) {
265 Loc = &Env.createStorageLocation(E: *E);
266 Env.setStorageLocation(E: *E, Loc&: *Loc);
267 }
268 Val = Env.getValue(Loc: *Loc);
269 if (!Val) {
270 Val = Env.createValue(Type: E->getType());
271 Env.setValue(Loc: *Loc, Val&: *Val);
272 }
273 } else {
274 Val = Env.getValue(E: *E);
275 if (!Val) {
276 Val = Env.createValue(Type: E->getType());
277 Env.setValue(E: *E, Val&: *Val);
278 }
279 }
280 assert(Val != nullptr);
281
282 return Val;
283}
284
285void transferExpr(const Expr *E, const MatchFinder::MatchResult &M,
286 LatticeTransferState &State) {
287 const ASTContext &Context = *M.Context;
288
289 Value *Val = getOrCreateValue(E, Env&: State.Env);
290
291 // The sign symbolic values have been initialized already.
292 if (Val->getProperty(Name: "neg"))
293 return;
294
295 Expr::EvalResult R;
296 // An integer expression which we cannot evaluate.
297 if (!(E->EvaluateAsInt(Result&: R, Ctx: Context) && R.Val.isInt())) {
298 initUnknown(Val&: *Val, Env&: State.Env);
299 return;
300 }
301
302 const Sign S = getSign(V: R.Val.getInt().getExtValue());
303 switch (S) {
304 case Sign::Negative:
305 initNegative(Val&: *Val, Env&: State.Env);
306 break;
307 case Sign::Zero:
308 initZero(Val&: *Val, Env&: State.Env);
309 break;
310 case Sign::Positive:
311 initPositive(Val&: *Val, Env&: State.Env);
312 break;
313 }
314}
315
316auto refToVar() { return declRefExpr(to(InnerMatcher: varDecl().bind(ID: kVar))); }
317
318auto 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>(M: binaryOperator(isComparisonOperator()),
326 A: transferBinary)
327
328 // FIXME handle binop +,-,*,/
329
330 // -a
331 .CaseOfCFGStmt<UnaryOperator>(
332 M: unaryOperator(hasOperatorName(Name: "-"),
333 hasUnaryOperand(InnerMatcher: hasDescendant(refToVar()))),
334 A: transferUnaryMinus)
335
336 // !a
337 .CaseOfCFGStmt<UnaryOperator>(
338 M: unaryOperator(hasOperatorName(Name: "!"),
339 hasUnaryOperand(InnerMatcher: hasDescendant(refToVar()))),
340 A: transferUnaryNot)
341
342 // int a;
343 .CaseOfCFGStmt<DeclStmt>(M: declStmt(hasSingleDecl(InnerMatcher: varDecl(
344 decl().bind(ID: kVar), hasType(InnerMatcher: isInteger()),
345 unless(hasInitializer(InnerMatcher: expr()))))),
346 A: transferUninitializedInt)
347
348 // constexpr int
349 .CaseOfCFGStmt<Expr>(M: expr(hasType(InnerMatcher: isInteger())), A: transferExpr)
350
351 .Build();
352}
353
354class SignPropagationAnalysis
355 : public DataflowAnalysis<SignPropagationAnalysis, NoopLattice> {
356public:
357 SignPropagationAnalysis(ASTContext &Context)
358 : DataflowAnalysis<SignPropagationAnalysis, NoopLattice>(Context),
359 TransferMatchSwitch(buildTransferMatchSwitch()) {}
360
361 static NoopLattice initialElement() { return {}; }
362
363 void transfer(const CFGElement &Elt, NoopLattice &L, Environment &Env) {
364 LatticeTransferState State(L, Env);
365 TransferMatchSwitch(Elt, getASTContext(), State);
366 }
367 void join(QualType Type, const Value &Val1, const Environment &Env1,
368 const Value &Val2, const Environment &Env2, Value &MergedVal,
369 Environment &MergedEnv) override;
370
371private:
372 CFGMatchSwitch<TransferState<NoopLattice>> TransferMatchSwitch;
373};
374
375BoolValue &joinBoolValues(BoolValue &Bool1, const Environment &Env1,
376 BoolValue &Bool2, const Environment &Env2,
377 Environment &JoinedEnv) {
378 if (&Bool1 == &Bool2) {
379 return Bool1;
380 }
381
382 auto &B1 = Bool1.formula();
383 auto &B2 = Bool2.formula();
384
385 auto &A = JoinedEnv.arena();
386 auto &JoinedBool = JoinedEnv.makeAtomicBoolValue();
387
388 // If `Bool1` and `Bool2` is constrained to the same true / false value,
389 // `JoinedBool` can be constrained similarly without needing to consider 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(Val: B1)) && Env2.proves(A.makeNot(Val: B2))) {
396 JoinedEnv.assume(A.makeNot(Val: JoinedBool.formula()));
397 }
398 return JoinedBool;
399}
400
401void SignPropagationAnalysis::join(QualType Type, const Value &Val1,
402 const Environment &Env1, const Value &Val2,
403 const Environment &Env2, Value &JoinedVal,
404 Environment &JoinedEnv) {
405 if (!Type->isIntegerType())
406 return;
407 SignProperties Ps1 = getSignProperties(Val: Val1, Env: Env1);
408 SignProperties Ps2 = getSignProperties(Val: Val2, Env: Env2);
409 if (!Ps1.Neg || !Ps2.Neg)
410 return;
411 BoolValue &JoinedNeg =
412 joinBoolValues(Bool1&: *Ps1.Neg, Env1, Bool2&: *Ps2.Neg, Env2, JoinedEnv);
413 BoolValue &JoinedZero =
414 joinBoolValues(Bool1&: *Ps1.Zero, Env1, Bool2&: *Ps2.Zero, Env2, JoinedEnv);
415 BoolValue &JoinedPos =
416 joinBoolValues(Bool1&: *Ps1.Pos, Env1, Bool2&: *Ps2.Pos, Env2, JoinedEnv);
417 setSignProperties(Val&: JoinedVal,
418 Ps: SignProperties{.Neg: &JoinedNeg, .Zero: &JoinedZero, .Pos: &JoinedPos});
419}
420
421template <typename Matcher>
422void runDataflow(llvm::StringRef Code, Matcher Match,
423 LangStandard::Kind Std = LangStandard::lang_cxx17,
424 llvm::StringRef TargetFun = "fun") {
425 using ast_matchers::hasName;
426 ASSERT_THAT_ERROR(
427 checkDataflow<SignPropagationAnalysis>(
428 AnalysisInputs<SignPropagationAnalysis>(
429 Code, hasName(TargetFun),
430 [](ASTContext &C, Environment &) {
431 return SignPropagationAnalysis(C);
432 })
433 .withASTBuildArgs(
434 {"-fsyntax-only", "-fno-delayed-template-parsing",
435 "-std=" +
436 std::string(LangStandard::getLangStandardForKind(Std)
437 .getName())}),
438 /*VerifyResults=*/
439 [&Match](const llvm::StringMap<DataflowAnalysisState<NoopLattice>>
440 &Results,
441 const AnalysisOutputs &AO) { Match(Results, AO.ASTCtx); }),
442 llvm::Succeeded());
443}
444
445// FIXME add this to testing support.
446template <typename NodeType, typename MatcherType>
447const NodeType *findFirst(ASTContext &ASTCtx, const MatcherType &M) {
448 auto TargetNodes = match(M.bind("v"), ASTCtx);
449 assert(TargetNodes.size() == 1 && "Match must be unique");
450 auto *const Result = selectFirst<NodeType>("v", TargetNodes);
451 assert(Result != nullptr);
452 return Result;
453}
454
455template <typename Node>
456std::pair<testing::AssertionResult, Value *>
457getProperty(const Environment &Env, ASTContext &ASTCtx, const Node *N,
458 StringRef Property) {
459 if (!N)
460 return {testing::AssertionFailure() << "No node", nullptr};
461 const StorageLocation *Loc = Env.getStorageLocation(*N);
462 if (!isa_and_nonnull<ScalarStorageLocation>(Val: Loc))
463 return {testing::AssertionFailure() << "No location", nullptr};
464 const Value *Val = Env.getValue(Loc: *Loc);
465 if (!Val)
466 return {testing::AssertionFailure() << "No value", nullptr};
467 auto *Prop = Val->getProperty(Name: Property);
468 if (!isa_and_nonnull<BoolValue>(Val: 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.
476template <typename Node>
477testing::AssertionResult isPropertyImplied(const Environment &Env,
478 ASTContext &ASTCtx, const Node *N,
479 StringRef Property, bool Implies) {
480 auto [Result, Prop] = getProperty(Env, ASTCtx, N, Property);
481 if (!Prop)
482 return Result;
483 auto *BVProp = cast<BoolValue>(Prop);
484 if (Env.proves(BVProp->formula()) != Implies)
485 return testing::AssertionFailure()
486 << Property << " is " << (Implies ? "not" : "") << " implied"
487 << ", but should " << (Implies ? "" : "not ") << "be";
488 return testing::AssertionSuccess();
489}
490
491template <typename Node>
492testing::AssertionResult isNegative(const Node *N, ASTContext &ASTCtx,
493 const Environment &Env) {
494 testing::AssertionResult R = isPropertyImplied(Env, ASTCtx, N, "neg", true);
495 if (!R)
496 return R;
497 R = isPropertyImplied(Env, ASTCtx, N, "zero", false);
498 if (!R)
499 return R;
500 return isPropertyImplied(Env, ASTCtx, N, "pos", false);
501}
502template <typename Node>
503testing::AssertionResult isPositive(const Node *N, ASTContext &ASTCtx,
504 const Environment &Env) {
505 testing::AssertionResult R = isPropertyImplied(Env, ASTCtx, N, "pos", true);
506 if (!R)
507 return R;
508 R = isPropertyImplied(Env, ASTCtx, N, "zero", false);
509 if (!R)
510 return R;
511 return isPropertyImplied(Env, ASTCtx, N, "neg", false);
512}
513template <typename Node>
514testing::AssertionResult isZero(const Node *N, ASTContext &ASTCtx,
515 const Environment &Env) {
516 testing::AssertionResult R = isPropertyImplied(Env, ASTCtx, N, "zero", true);
517 if (!R)
518 return R;
519 R = isPropertyImplied(Env, ASTCtx, N, "pos", false);
520 if (!R)
521 return R;
522 return isPropertyImplied(Env, ASTCtx, N, "neg", false);
523}
524template <typename Node>
525testing::AssertionResult isTop(const Node *N, ASTContext &ASTCtx,
526 const Environment &Env) {
527 testing::AssertionResult R = isPropertyImplied(Env, ASTCtx, N, "zero", false);
528 if (!R)
529 return R;
530 R = isPropertyImplied(Env, ASTCtx, N, "pos", false);
531 if (!R)
532 return R;
533 return isPropertyImplied(Env, ASTCtx, N, "neg", false);
534}
535
536TEST(SignAnalysisTest, Init) {
537 std::string Code = R"(
538 int foo();
539 void fun() {
540 int a = -1;
541 int b = 0;
542 int c = 1;
543 int d;
544 int e = foo();
545 int f = c;
546 // [[p]]
547 }
548 )";
549 runDataflow(
550 Code,
551 Match: [](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(AnnotationStates: Results, Annotation: "p");
556
557 const ValueDecl *A = findValueDecl(ASTCtx, Name: "a");
558 const ValueDecl *B = findValueDecl(ASTCtx, Name: "b");
559 const ValueDecl *C = findValueDecl(ASTCtx, Name: "c");
560 const ValueDecl *D = findValueDecl(ASTCtx, Name: "d");
561 const ValueDecl *E = findValueDecl(ASTCtx, Name: "e");
562 const ValueDecl *F = findValueDecl(ASTCtx, Name: "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 Std: LangStandard::lang_cxx17);
572}
573
574TEST(SignAnalysisTest, UnaryMinus) {
575 std::string Code = R"(
576 void fun() {
577 int a = 1;
578 int b = -a;
579 // [[p]]
580 }
581 )";
582 runDataflow(
583 Code,
584 Match: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
585 ASTContext &ASTCtx) {
586 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
587 const Environment &Env = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p");
588
589 const ValueDecl *A = findValueDecl(ASTCtx, Name: "a");
590 const ValueDecl *B = findValueDecl(ASTCtx, Name: "b");
591 EXPECT_TRUE(isPositive(A, ASTCtx, Env));
592 EXPECT_TRUE(isNegative(B, ASTCtx, Env));
593 },
594 Std: LangStandard::lang_cxx17);
595}
596
597TEST(SignAnalysisTest, UnaryNot) {
598 std::string Code = R"(
599 void fun() {
600 int a = 2;
601 int b = !a;
602 // [[p]]
603 }
604 )";
605 runDataflow(
606 Code,
607 Match: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
608 ASTContext &ASTCtx) {
609 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
610 const Environment &Env = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p");
611
612 const ValueDecl *A = findValueDecl(ASTCtx, Name: "a");
613 const ValueDecl *B = findValueDecl(ASTCtx, Name: "b");
614 EXPECT_TRUE(isPositive(A, ASTCtx, Env));
615 EXPECT_TRUE(isZero(B, ASTCtx, Env));
616 },
617 Std: LangStandard::lang_cxx17);
618}
619
620TEST(SignAnalysisTest, UnaryNotInIf) {
621 std::string Code = R"(
622 int foo();
623 void fun() {
624 int a = foo();
625 if (!a) {
626 int b1;
627 int p_a = a;
628 int p_not_a = !a;
629 // [[p]]
630 } else {
631 int q_a = a;
632 int q_not_a = !a;
633 // [[q]]
634 }
635 }
636 )";
637 runDataflow(
638 Code,
639 Match: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
640 ASTContext &ASTCtx) {
641 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q"));
642 const Environment &EnvP = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p");
643 const Environment &EnvQ = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "q");
644
645 const ValueDecl *A = findValueDecl(ASTCtx, Name: "a");
646 const ValueDecl *PA = findValueDecl(ASTCtx, Name: "p_a");
647 const ValueDecl *PNA = findValueDecl(ASTCtx, Name: "p_not_a");
648 const ValueDecl *QA = findValueDecl(ASTCtx, Name: "q_a");
649 const ValueDecl *QNA = findValueDecl(ASTCtx, Name: "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 Std: LangStandard::lang_cxx17);
662}
663
664TEST(SignAnalysisTest, BinaryGT) {
665 std::string Code = R"(
666 int foo();
667 void fun() {
668 int a = foo();
669 int b = 1;
670 if (a > 1) {
671 (void)0;
672 // [[p]]
673 }
674 if (a > 0) {
675 (void)0;
676 // [[q]]
677 }
678 if (a > -1) {
679 (void)0;
680 // [[r]]
681 }
682 if (a > b) {
683 (void)0;
684 // [[s]]
685 }
686 }
687 )";
688 runDataflow(
689 Code,
690 Match: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
691 ASTContext &ASTCtx) {
692 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q", "r", "s"));
693 const Environment &EnvP = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p");
694 const Environment &EnvQ = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "q");
695 const Environment &EnvR = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "r");
696 const Environment &EnvS = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "s");
697
698 const ValueDecl *A = findValueDecl(ASTCtx, Name: "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 Std: LangStandard::lang_cxx17);
710}
711
712TEST(SignAnalysisTest, BinaryLT) {
713 std::string Code = R"(
714 int foo();
715 void fun() {
716 int a = foo();
717 int b = -1;
718 if (a < -1) {
719 (void)0;
720 // [[p]]
721 }
722 if (a < 0) {
723 (void)0;
724 // [[q]]
725 }
726 if (a < 1) {
727 (void)0;
728 // [[r]]
729 }
730 if (a < b) {
731 (void)0;
732 // [[s]]
733 }
734 }
735 )";
736 runDataflow(
737 Code,
738 Match: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
739 ASTContext &ASTCtx) {
740 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q", "r", "s"));
741 const Environment &EnvP = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p");
742 const Environment &EnvQ = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "q");
743 const Environment &EnvR = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "r");
744 const Environment &EnvS = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "s");
745
746 const ValueDecl *A = findValueDecl(ASTCtx, Name: "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 Std: LangStandard::lang_cxx17);
758}
759
760TEST(SignAnalysisTest, BinaryGE) {
761 std::string Code = R"(
762 int foo();
763 void fun() {
764 int a = foo();
765 int b = 1;
766 if (a >= 1) {
767 (void)0;
768 // [[p]]
769 }
770 if (a >= 0) {
771 (void)0;
772 // [[q]]
773 }
774 if (a >= -1) {
775 (void)0;
776 // [[r]]
777 }
778 if (a >= b) {
779 (void)0;
780 // [[s]]
781 }
782 }
783 )";
784 runDataflow(
785 Code,
786 Match: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
787 ASTContext &ASTCtx) {
788 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q", "r", "s"));
789 const Environment &EnvP = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p");
790 const Environment &EnvQ = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "q");
791 const Environment &EnvR = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "r");
792 const Environment &EnvS = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "s");
793
794 const ValueDecl *A = findValueDecl(ASTCtx, Name: "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 Std: LangStandard::lang_cxx17);
806}
807
808TEST(SignAnalysisTest, BinaryLE) {
809 std::string Code = R"(
810 int foo();
811 void fun() {
812 int a = foo();
813 int b = -1;
814 if (a <= -1) {
815 (void)0;
816 // [[p]]
817 }
818 if (a <= 0) {
819 (void)0;
820 // [[q]]
821 }
822 if (a <= 1) {
823 (void)0;
824 // [[r]]
825 }
826 if (a <= b) {
827 (void)0;
828 // [[s]]
829 }
830 }
831 )";
832 runDataflow(
833 Code,
834 Match: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
835 ASTContext &ASTCtx) {
836 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q", "r", "s"));
837 const Environment &EnvP = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p");
838 const Environment &EnvQ = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "q");
839 const Environment &EnvR = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "r");
840 const Environment &EnvS = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "s");
841
842 const ValueDecl *A = findValueDecl(ASTCtx, Name: "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 Std: LangStandard::lang_cxx17);
854}
855
856TEST(SignAnalysisTest, BinaryEQ) {
857 std::string Code = R"(
858 int foo();
859 void fun() {
860 int a = foo();
861 if (a == -1) {
862 (void)0;
863 // [[n]]
864 }
865 if (a == 0) {
866 (void)0;
867 // [[z]]
868 }
869 if (a == 1) {
870 (void)0;
871 // [[p]]
872 }
873 }
874 )";
875 runDataflow(
876 Code,
877 Match: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
878 ASTContext &ASTCtx) {
879 ASSERT_THAT(Results.keys(), UnorderedElementsAre("n", "z", "p"));
880 const Environment &EnvN = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "n");
881 const Environment &EnvZ = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "z");
882 const Environment &EnvP = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p");
883
884 const ValueDecl *A = findValueDecl(ASTCtx, Name: "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 Std: LangStandard::lang_cxx17);
894}
895
896TEST(SignAnalysisTest, ComplexLoopCondition) {
897 std::string Code = R"(
898 int foo();
899 void fun() {
900 int a, b;
901 while ((a = foo()) > 0 && (b = foo()) > 0) {
902 a;
903 b;
904 // [[p]]
905 }
906 }
907 )";
908 runDataflow(
909 Code,
910 Match: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
911 ASTContext &ASTCtx) {
912 const Environment &Env = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p");
913
914 const ValueDecl *A = findValueDecl(ASTCtx, Name: "a");
915 const ValueDecl *B = findValueDecl(ASTCtx, Name: "b");
916
917 EXPECT_TRUE(isPositive(A, ASTCtx, Env));
918 EXPECT_TRUE(isPositive(B, ASTCtx, Env));
919 },
920 Std: LangStandard::lang_cxx17);
921}
922
923TEST(SignAnalysisTest, JoinToTop) {
924 std::string Code = R"(
925 int foo();
926 void fun(bool b) {
927 int a = foo();
928 if (b) {
929 a = -1;
930 (void)0;
931 // [[p]]
932 } else {
933 a = 1;
934 (void)0;
935 // [[q]]
936 }
937 (void)0;
938 // [[r]]
939 }
940 )";
941 runDataflow(
942 Code,
943 Match: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
944 ASTContext &ASTCtx) {
945 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q", "r"));
946 const Environment &EnvP = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p");
947 const Environment &EnvQ = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "q");
948 const Environment &EnvR = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "r");
949
950 const ValueDecl *A = findValueDecl(ASTCtx, Name: "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 Std: LangStandard::lang_cxx17);
960}
961
962TEST(SignAnalysisTest, JoinToNeg) {
963 std::string Code = R"(
964 int foo();
965 void fun() {
966 int a = foo();
967 if (a < 1) {
968 a = -1;
969 (void)0;
970 // [[p]]
971 } else {
972 a = -1;
973 (void)0;
974 // [[q]]
975 }
976 (void)0;
977 // [[r]]
978 }
979 )";
980 runDataflow(
981 Code,
982 Match: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
983 ASTContext &ASTCtx) {
984 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q", "r"));
985 const Environment &EnvP = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p");
986 const Environment &EnvQ = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "q");
987 const Environment &EnvR = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "r");
988
989 const ValueDecl *A = findValueDecl(ASTCtx, Name: "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 Std: LangStandard::lang_cxx17);
999}
1000
1001TEST(SignAnalysisTest, NestedIfs) {
1002 std::string Code = R"(
1003 int foo();
1004 void fun() {
1005 int a = foo();
1006 if (a >= 0) {
1007 (void)0;
1008 // [[p]]
1009 if (a == 0) {
1010 (void)0;
1011 // [[q]]
1012 }
1013 }
1014 (void)0;
1015 // [[r]]
1016 }
1017 )";
1018 runDataflow(
1019 Code,
1020 Match: [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
1021 ASTContext &ASTCtx) {
1022 ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q", "r"));
1023 const Environment &EnvP = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "p");
1024 const Environment &EnvQ = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "q");
1025 const Environment &EnvR = getEnvironmentAtAnnotation(AnnotationStates: Results, Annotation: "r");
1026
1027 const ValueDecl *A = findValueDecl(ASTCtx, Name: "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 Std: LangStandard::lang_cxx17);
1037}
1038
1039} // namespace
1040

source code of clang/unittests/Analysis/FlowSensitive/SignAnalysisTest.cpp