clang  16.0.0git
Transfer.cpp
Go to the documentation of this file.
1 //===-- Transfer.cpp --------------------------------------------*- C++ -*-===//
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 transfer functions that evaluate program statements and
10 // update an environment accordingly.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "clang/AST/Decl.h"
16 #include "clang/AST/DeclBase.h"
17 #include "clang/AST/DeclCXX.h"
18 #include "clang/AST/Expr.h"
19 #include "clang/AST/ExprCXX.h"
21 #include "clang/AST/Stmt.h"
22 #include "clang/AST/StmtVisitor.h"
27 #include "clang/Basic/Builtins.h"
29 #include "llvm/ADT/STLExtras.h"
30 #include "llvm/Support/Casting.h"
31 #include <cassert>
32 #include <memory>
33 #include <tuple>
34 
35 namespace clang {
36 namespace dataflow {
37 
38 static BoolValue &evaluateBooleanEquality(const Expr &LHS, const Expr &RHS,
39  Environment &Env) {
40  if (auto *LHSValue =
41  dyn_cast_or_null<BoolValue>(Env.getValue(LHS, SkipPast::Reference)))
42  if (auto *RHSValue =
43  dyn_cast_or_null<BoolValue>(Env.getValue(RHS, SkipPast::Reference)))
44  return Env.makeIff(*LHSValue, *RHSValue);
45 
46  return Env.makeAtomicBoolValue();
47 }
48 
49 class TransferVisitor : public ConstStmtVisitor<TransferVisitor> {
50 public:
51  TransferVisitor(const StmtToEnvMap &StmtToEnv, Environment &Env,
52  TransferOptions Options)
53  : StmtToEnv(StmtToEnv), Env(Env), Options(Options) {}
54 
56  const Expr *LHS = S->getLHS();
57  assert(LHS != nullptr);
58 
59  const Expr *RHS = S->getRHS();
60  assert(RHS != nullptr);
61 
62  switch (S->getOpcode()) {
63  case BO_Assign: {
64  auto *LHSLoc = Env.getStorageLocation(*LHS, SkipPast::Reference);
65  if (LHSLoc == nullptr)
66  break;
67 
68  auto *RHSVal = Env.getValue(*RHS, SkipPast::Reference);
69  if (RHSVal == nullptr)
70  break;
71 
72  // Assign a value to the storage location of the left-hand side.
73  Env.setValue(*LHSLoc, *RHSVal);
74 
75  // Assign a storage location for the whole expression.
76  Env.setStorageLocation(*S, *LHSLoc);
77  break;
78  }
79  case BO_LAnd:
80  case BO_LOr: {
81  BoolValue &LHSVal = getLogicOperatorSubExprValue(*LHS);
82  BoolValue &RHSVal = getLogicOperatorSubExprValue(*RHS);
83 
84  auto &Loc = Env.createStorageLocation(*S);
85  Env.setStorageLocation(*S, Loc);
86  if (S->getOpcode() == BO_LAnd)
87  Env.setValue(Loc, Env.makeAnd(LHSVal, RHSVal));
88  else
89  Env.setValue(Loc, Env.makeOr(LHSVal, RHSVal));
90  break;
91  }
92  case BO_NE:
93  case BO_EQ: {
94  auto &LHSEqRHSValue = evaluateBooleanEquality(*LHS, *RHS, Env);
95  auto &Loc = Env.createStorageLocation(*S);
96  Env.setStorageLocation(*S, Loc);
97  Env.setValue(Loc, S->getOpcode() == BO_EQ ? LHSEqRHSValue
98  : Env.makeNot(LHSEqRHSValue));
99  break;
100  }
101  case BO_Comma: {
102  if (auto *Loc = Env.getStorageLocation(*RHS, SkipPast::None))
103  Env.setStorageLocation(*S, *Loc);
104  break;
105  }
106  default:
107  break;
108  }
109  }
110 
111  void VisitDeclRefExpr(const DeclRefExpr *S) {
112  assert(S->getDecl() != nullptr);
113  auto *DeclLoc = Env.getStorageLocation(*S->getDecl(), SkipPast::None);
114  if (DeclLoc == nullptr)
115  return;
116 
117  if (S->getDecl()->getType()->isReferenceType()) {
118  Env.setStorageLocation(*S, *DeclLoc);
119  } else {
120  auto &Loc = Env.createStorageLocation(*S);
121  auto &Val = Env.takeOwnership(std::make_unique<ReferenceValue>(*DeclLoc));
122  Env.setStorageLocation(*S, Loc);
123  Env.setValue(Loc, Val);
124  }
125  }
126 
127  void VisitDeclStmt(const DeclStmt *S) {
128  // Group decls are converted into single decls in the CFG so the cast below
129  // is safe.
130  const auto &D = *cast<VarDecl>(S->getSingleDecl());
131 
132  // Static local vars are already initialized in `Environment`.
133  if (D.hasGlobalStorage())
134  return;
135 
136  auto &Loc = Env.createStorageLocation(D);
137  Env.setStorageLocation(D, Loc);
138 
139  const Expr *InitExpr = D.getInit();
140  if (InitExpr == nullptr) {
141  // No initializer expression - associate `Loc` with a new value.
142  if (Value *Val = Env.createValue(D.getType()))
143  Env.setValue(Loc, *Val);
144  return;
145  }
146 
147  if (D.getType()->isReferenceType()) {
148  // Initializing a reference variable - do not create a reference to
149  // reference.
150  if (auto *InitExprLoc =
151  Env.getStorageLocation(*InitExpr, SkipPast::Reference)) {
152  auto &Val =
153  Env.takeOwnership(std::make_unique<ReferenceValue>(*InitExprLoc));
154  Env.setValue(Loc, Val);
155  }
156  } else if (auto *InitExprVal = Env.getValue(*InitExpr, SkipPast::None)) {
157  Env.setValue(Loc, *InitExprVal);
158  }
159 
160  if (Env.getValue(Loc) == nullptr) {
161  // We arrive here in (the few) cases where an expression is intentionally
162  // "uninterpreted". There are two ways to handle this situation: propagate
163  // the status, so that uninterpreted initializers result in uninterpreted
164  // variables, or provide a default value. We choose the latter so that
165  // later refinements of the variable can be used for reasoning about the
166  // surrounding code.
167  //
168  // FIXME. If and when we interpret all language cases, change this to
169  // assert that `InitExpr` is interpreted, rather than supplying a default
170  // value (assuming we don't update the environment API to return
171  // references).
172  if (Value *Val = Env.createValue(D.getType()))
173  Env.setValue(Loc, *Val);
174  }
175 
176  if (const auto *Decomp = dyn_cast<DecompositionDecl>(&D)) {
177  // If VarDecl is a DecompositionDecl, evaluate each of its bindings. This
178  // needs to be evaluated after initializing the values in the storage for
179  // VarDecl, as the bindings refer to them.
180  // FIXME: Add support for ArraySubscriptExpr.
181  // FIXME: Consider adding AST nodes that are used for structured bindings
182  // to the CFG.
183  for (const auto *B : Decomp->bindings()) {
184  auto *ME = dyn_cast_or_null<MemberExpr>(B->getBinding());
185  if (ME == nullptr)
186  continue;
187 
188  auto *DE = dyn_cast_or_null<DeclRefExpr>(ME->getBase());
189  if (DE == nullptr)
190  continue;
191 
192  // ME and its base haven't been visited because they aren't included in
193  // the statements of the CFG basic block.
194  VisitDeclRefExpr(DE);
195  VisitMemberExpr(ME);
196 
197  if (auto *Loc = Env.getStorageLocation(*ME, SkipPast::Reference))
198  Env.setStorageLocation(*B, *Loc);
199  }
200  }
201  }
202 
204  const Expr *SubExpr = S->getSubExpr();
205  assert(SubExpr != nullptr);
206 
207  switch (S->getCastKind()) {
208  case CK_IntegralToBoolean: {
209  // This cast creates a new, boolean value from the integral value. We
210  // model that with a fresh value in the environment, unless it's already a
211  // boolean.
212  auto &Loc = Env.createStorageLocation(*S);
213  Env.setStorageLocation(*S, Loc);
214  if (auto *SubExprVal = dyn_cast_or_null<BoolValue>(
215  Env.getValue(*SubExpr, SkipPast::Reference)))
216  Env.setValue(Loc, *SubExprVal);
217  else
218  // FIXME: If integer modeling is added, then update this code to create
219  // the boolean based on the integer model.
220  Env.setValue(Loc, Env.makeAtomicBoolValue());
221  break;
222  }
223 
224  case CK_LValueToRValue: {
225  auto *SubExprVal = Env.getValue(*SubExpr, SkipPast::Reference);
226  if (SubExprVal == nullptr)
227  break;
228 
229  auto &ExprLoc = Env.createStorageLocation(*S);
230  Env.setStorageLocation(*S, ExprLoc);
231  Env.setValue(ExprLoc, *SubExprVal);
232  break;
233  }
234 
235  case CK_IntegralCast:
236  // FIXME: This cast creates a new integral value from the
237  // subexpression. But, because we don't model integers, we don't
238  // distinguish between this new value and the underlying one. If integer
239  // modeling is added, then update this code to create a fresh location and
240  // value.
241  case CK_UncheckedDerivedToBase:
242  case CK_ConstructorConversion:
243  case CK_UserDefinedConversion:
244  // FIXME: Add tests that excercise CK_UncheckedDerivedToBase,
245  // CK_ConstructorConversion, and CK_UserDefinedConversion.
246  case CK_NoOp: {
247  // FIXME: Consider making `Environment::getStorageLocation` skip noop
248  // expressions (this and other similar expressions in the file) instead of
249  // assigning them storage locations.
250  auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
251  if (SubExprLoc == nullptr)
252  break;
253 
254  Env.setStorageLocation(*S, *SubExprLoc);
255  break;
256  }
257  case CK_NullToPointer:
258  case CK_NullToMemberPointer: {
259  auto &Loc = Env.createStorageLocation(S->getType());
260  Env.setStorageLocation(*S, Loc);
261 
262  auto &NullPointerVal =
263  Env.getOrCreateNullPointerValue(S->getType()->getPointeeType());
264  Env.setValue(Loc, NullPointerVal);
265  break;
266  }
267  default:
268  break;
269  }
270  }
271 
273  const Expr *SubExpr = S->getSubExpr();
274  assert(SubExpr != nullptr);
275 
276  switch (S->getOpcode()) {
277  case UO_Deref: {
278  // Skip past a reference to handle dereference of a dependent pointer.
279  const auto *SubExprVal = cast_or_null<PointerValue>(
280  Env.getValue(*SubExpr, SkipPast::Reference));
281  if (SubExprVal == nullptr)
282  break;
283 
284  auto &Loc = Env.createStorageLocation(*S);
285  Env.setStorageLocation(*S, Loc);
286  Env.setValue(Loc, Env.takeOwnership(std::make_unique<ReferenceValue>(
287  SubExprVal->getPointeeLoc())));
288  break;
289  }
290  case UO_AddrOf: {
291  // Do not form a pointer to a reference. If `SubExpr` is assigned a
292  // `ReferenceValue` then form a value that points to the location of its
293  // pointee.
294  StorageLocation *PointeeLoc =
296  if (PointeeLoc == nullptr)
297  break;
298 
299  auto &PointerLoc = Env.createStorageLocation(*S);
300  auto &PointerVal =
301  Env.takeOwnership(std::make_unique<PointerValue>(*PointeeLoc));
302  Env.setStorageLocation(*S, PointerLoc);
303  Env.setValue(PointerLoc, PointerVal);
304  break;
305  }
306  case UO_LNot: {
307  auto *SubExprVal =
308  dyn_cast_or_null<BoolValue>(Env.getValue(*SubExpr, SkipPast::None));
309  if (SubExprVal == nullptr)
310  break;
311 
312  auto &ExprLoc = Env.createStorageLocation(*S);
313  Env.setStorageLocation(*S, ExprLoc);
314  Env.setValue(ExprLoc, Env.makeNot(*SubExprVal));
315  break;
316  }
317  default:
318  break;
319  }
320  }
321 
322  void VisitCXXThisExpr(const CXXThisExpr *S) {
323  auto *ThisPointeeLoc = Env.getThisPointeeStorageLocation();
324  if (ThisPointeeLoc == nullptr)
325  // Unions are not supported yet, and will not have a location for the
326  // `this` expression's pointee.
327  return;
328 
329  auto &Loc = Env.createStorageLocation(*S);
330  Env.setStorageLocation(*S, Loc);
331  Env.setValue(Loc, Env.takeOwnership(
332  std::make_unique<PointerValue>(*ThisPointeeLoc)));
333  }
334 
335  void VisitReturnStmt(const ReturnStmt *S) {
336  auto *Ret = S->getRetValue();
337  if (Ret == nullptr)
338  return;
339 
340  auto *Val = Env.getValue(*Ret, SkipPast::None);
341  if (Val == nullptr)
342  return;
343 
344  // FIXME: Support reference-type returns.
345  if (Val->getKind() == Value::Kind::Reference)
346  return;
347 
348  auto *Loc = Env.getReturnStorageLocation();
349  assert(Loc != nullptr);
350  // FIXME: Model NRVO.
351  Env.setValue(*Loc, *Val);
352  }
353 
354  void VisitMemberExpr(const MemberExpr *S) {
355  ValueDecl *Member = S->getMemberDecl();
356  assert(Member != nullptr);
357 
358  // FIXME: Consider assigning pointer values to function member expressions.
359  if (Member->isFunctionOrFunctionTemplate())
360  return;
361 
362  if (auto *D = dyn_cast<VarDecl>(Member)) {
363  if (D->hasGlobalStorage()) {
364  auto *VarDeclLoc = Env.getStorageLocation(*D, SkipPast::None);
365  if (VarDeclLoc == nullptr)
366  return;
367 
368  if (VarDeclLoc->getType()->isReferenceType()) {
369  Env.setStorageLocation(*S, *VarDeclLoc);
370  } else {
371  auto &Loc = Env.createStorageLocation(*S);
372  Env.setStorageLocation(*S, Loc);
373  Env.setValue(Loc, Env.takeOwnership(
374  std::make_unique<ReferenceValue>(*VarDeclLoc)));
375  }
376  return;
377  }
378  }
379 
380  // The receiver can be either a value or a pointer to a value. Skip past the
381  // indirection to handle both cases.
382  auto *BaseLoc = cast_or_null<AggregateStorageLocation>(
384  if (BaseLoc == nullptr)
385  return;
386 
387  // FIXME: Add support for union types.
388  if (BaseLoc->getType()->isUnionType())
389  return;
390 
391  auto &MemberLoc = BaseLoc->getChild(*Member);
392  if (MemberLoc.getType()->isReferenceType()) {
393  Env.setStorageLocation(*S, MemberLoc);
394  } else {
395  auto &Loc = Env.createStorageLocation(*S);
396  Env.setStorageLocation(*S, Loc);
397  Env.setValue(
398  Loc, Env.takeOwnership(std::make_unique<ReferenceValue>(MemberLoc)));
399  }
400  }
401 
403  const Expr *InitExpr = S->getExpr();
404  assert(InitExpr != nullptr);
405 
406  Value *InitExprVal = Env.getValue(*InitExpr, SkipPast::None);
407  if (InitExprVal == nullptr)
408  return;
409 
410  const FieldDecl *Field = S->getField();
411  assert(Field != nullptr);
412 
413  auto &ThisLoc =
414  *cast<AggregateStorageLocation>(Env.getThisPointeeStorageLocation());
415  auto &FieldLoc = ThisLoc.getChild(*Field);
416  Env.setValue(FieldLoc, *InitExprVal);
417  }
418 
420  const CXXConstructorDecl *ConstructorDecl = S->getConstructor();
421  assert(ConstructorDecl != nullptr);
422 
423  if (ConstructorDecl->isCopyOrMoveConstructor()) {
424  assert(S->getNumArgs() == 1);
425 
426  const Expr *Arg = S->getArg(0);
427  assert(Arg != nullptr);
428 
429  if (S->isElidable()) {
430  auto *ArgLoc = Env.getStorageLocation(*Arg, SkipPast::Reference);
431  if (ArgLoc == nullptr)
432  return;
433 
434  Env.setStorageLocation(*S, *ArgLoc);
435  } else if (auto *ArgVal = Env.getValue(*Arg, SkipPast::Reference)) {
436  auto &Loc = Env.createStorageLocation(*S);
437  Env.setStorageLocation(*S, Loc);
438  Env.setValue(Loc, *ArgVal);
439  }
440  return;
441  }
442 
443  auto &Loc = Env.createStorageLocation(*S);
444  Env.setStorageLocation(*S, Loc);
445  if (Value *Val = Env.createValue(S->getType()))
446  Env.setValue(Loc, *Val);
447 
448  transferInlineCall(S, ConstructorDecl);
449  }
450 
452  if (S->getOperator() == OO_Equal) {
453  assert(S->getNumArgs() == 2);
454 
455  const Expr *Arg0 = S->getArg(0);
456  assert(Arg0 != nullptr);
457 
458  const Expr *Arg1 = S->getArg(1);
459  assert(Arg1 != nullptr);
460 
461  // Evaluate only copy and move assignment operators.
462  auto *Arg0Type = Arg0->getType()->getUnqualifiedDesugaredType();
463  auto *Arg1Type = Arg1->getType()->getUnqualifiedDesugaredType();
464  if (Arg0Type != Arg1Type)
465  return;
466 
467  auto *ObjectLoc = Env.getStorageLocation(*Arg0, SkipPast::Reference);
468  if (ObjectLoc == nullptr)
469  return;
470 
471  auto *Val = Env.getValue(*Arg1, SkipPast::Reference);
472  if (Val == nullptr)
473  return;
474 
475  // Assign a value to the storage location of the object.
476  Env.setValue(*ObjectLoc, *Val);
477 
478  // FIXME: Add a test for the value of the whole expression.
479  // Assign a storage location for the whole expression.
480  Env.setStorageLocation(*S, *ObjectLoc);
481  }
482  }
483 
485  if (S->getCastKind() == CK_ConstructorConversion) {
486  const Expr *SubExpr = S->getSubExpr();
487  assert(SubExpr != nullptr);
488 
489  auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
490  if (SubExprLoc == nullptr)
491  return;
492 
493  Env.setStorageLocation(*S, *SubExprLoc);
494  }
495  }
496 
498  auto &Loc = Env.createStorageLocation(*S);
499  Env.setStorageLocation(*S, Loc);
500  if (Value *Val = Env.createValue(S->getType()))
501  Env.setValue(Loc, *Val);
502  }
503 
504  void VisitCallExpr(const CallExpr *S) {
505  // Of clang's builtins, only `__builtin_expect` is handled explicitly, since
506  // others (like trap, debugtrap, and unreachable) are handled by CFG
507  // construction.
508  if (S->isCallToStdMove()) {
509  assert(S->getNumArgs() == 1);
510 
511  const Expr *Arg = S->getArg(0);
512  assert(Arg != nullptr);
513 
514  auto *ArgLoc = Env.getStorageLocation(*Arg, SkipPast::None);
515  if (ArgLoc == nullptr)
516  return;
517 
518  Env.setStorageLocation(*S, *ArgLoc);
519  } else if (S->getDirectCallee() != nullptr &&
520  S->getDirectCallee()->getBuiltinID() ==
521  Builtin::BI__builtin_expect) {
522  assert(S->getNumArgs() > 0);
523  assert(S->getArg(0) != nullptr);
524  // `__builtin_expect` returns by-value, so strip away any potential
525  // references in the argument.
526  auto *ArgLoc = Env.getStorageLocation(*S->getArg(0), SkipPast::Reference);
527  if (ArgLoc == nullptr)
528  return;
529  Env.setStorageLocation(*S, *ArgLoc);
530  } else if (const FunctionDecl *F = S->getDirectCallee()) {
531  transferInlineCall(S, F);
532  }
533  }
534 
536  const Expr *SubExpr = S->getSubExpr();
537  assert(SubExpr != nullptr);
538 
539  auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
540  if (SubExprLoc == nullptr)
541  return;
542 
543  Env.setStorageLocation(*S, *SubExprLoc);
544  }
545 
547  const Expr *SubExpr = S->getSubExpr();
548  assert(SubExpr != nullptr);
549 
550  auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
551  if (SubExprLoc == nullptr)
552  return;
553 
554  Env.setStorageLocation(*S, *SubExprLoc);
555  }
556 
558  if (S->getCastKind() == CK_NoOp) {
559  const Expr *SubExpr = S->getSubExpr();
560  assert(SubExpr != nullptr);
561 
562  auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
563  if (SubExprLoc == nullptr)
564  return;
565 
566  Env.setStorageLocation(*S, *SubExprLoc);
567  }
568  }
569 
571  // FIXME: Revisit this once flow conditions are added to the framework. For
572  // `a = b ? c : d` we can add `b => a == c && !b => a == d` to the flow
573  // condition.
574  auto &Loc = Env.createStorageLocation(*S);
575  Env.setStorageLocation(*S, Loc);
576  if (Value *Val = Env.createValue(S->getType()))
577  Env.setValue(Loc, *Val);
578  }
579 
581  QualType Type = S->getType();
582 
583  auto &Loc = Env.createStorageLocation(*S);
584  Env.setStorageLocation(*S, Loc);
585 
586  auto *Val = Env.createValue(Type);
587  if (Val == nullptr)
588  return;
589 
590  Env.setValue(Loc, *Val);
591 
592  if (Type->isStructureOrClassType()) {
593  for (auto It : llvm::zip(Type->getAsRecordDecl()->fields(), S->inits())) {
594  const FieldDecl *Field = std::get<0>(It);
595  assert(Field != nullptr);
596 
597  const Expr *Init = std::get<1>(It);
598  assert(Init != nullptr);
599 
600  if (Value *InitVal = Env.getValue(*Init, SkipPast::None))
601  cast<StructValue>(Val)->setChild(*Field, *InitVal);
602  }
603  }
604  // FIXME: Implement array initialization.
605  }
606 
608  auto &Loc = Env.createStorageLocation(*S);
609  Env.setStorageLocation(*S, Loc);
610  Env.setValue(Loc, Env.getBoolLiteralValue(S->getValue()));
611  }
612 
613  void VisitParenExpr(const ParenExpr *S) {
614  // The CFG does not contain `ParenExpr` as top-level statements in basic
615  // blocks, however manual traversal to sub-expressions may encounter them.
616  // Redirect to the sub-expression.
617  auto *SubExpr = S->getSubExpr();
618  assert(SubExpr != nullptr);
619  Visit(SubExpr);
620  }
621 
623  // The CFG does not contain `ExprWithCleanups` as top-level statements in
624  // basic blocks, however manual traversal to sub-expressions may encounter
625  // them. Redirect to the sub-expression.
626  auto *SubExpr = S->getSubExpr();
627  assert(SubExpr != nullptr);
628  Visit(SubExpr);
629  }
630 
631 private:
632  BoolValue &getLogicOperatorSubExprValue(const Expr &SubExpr) {
633  // `SubExpr` and its parent logic operator might be part of different basic
634  // blocks. We try to access the value that is assigned to `SubExpr` in the
635  // corresponding environment.
636  if (const Environment *SubExprEnv = StmtToEnv.getEnvironment(SubExpr)) {
637  if (auto *Val = dyn_cast_or_null<BoolValue>(
638  SubExprEnv->getValue(SubExpr, SkipPast::Reference)))
639  return *Val;
640  }
641 
642  if (Env.getStorageLocation(SubExpr, SkipPast::None) == nullptr) {
643  // Sub-expressions that are logic operators are not added in basic blocks
644  // (e.g. see CFG for `bool d = a && (b || c);`). If `SubExpr` is a logic
645  // operator, it may not have been evaluated and assigned a value yet. In
646  // that case, we need to first visit `SubExpr` and then try to get the
647  // value that gets assigned to it.
648  Visit(&SubExpr);
649  }
650 
651  if (auto *Val = dyn_cast_or_null<BoolValue>(
652  Env.getValue(SubExpr, SkipPast::Reference)))
653  return *Val;
654 
655  // If the value of `SubExpr` is still unknown, we create a fresh symbolic
656  // boolean value for it.
657  return Env.makeAtomicBoolValue();
658  }
659 
660  // If context sensitivity is enabled, try to analyze the body of the callee
661  // `F` of `S`. The type `E` must be either `CallExpr` or `CXXConstructExpr`.
662  template <typename E>
663  void transferInlineCall(const E *S, const FunctionDecl *F) {
664  if (!(Options.ContextSensitiveOpts &&
665  Env.canDescend(Options.ContextSensitiveOpts->Depth, F)))
666  return;
667 
668  const ControlFlowContext *CFCtx = Env.getControlFlowContext(F);
669  if (!CFCtx)
670  return;
671 
672  // FIXME: We don't support context-sensitive analysis of recursion, so
673  // we should return early here if `F` is the same as the `FunctionDecl`
674  // holding `S` itself.
675 
676  auto ExitBlock = CFCtx->getCFG().getExit().getBlockID();
677 
678  if (const auto *NonConstructExpr = dyn_cast<CallExpr>(S)) {
679  // Note that it is important for the storage location of `S` to be set
680  // before `pushCall`, because the latter uses it to set the storage
681  // location for `return`.
682  auto &ReturnLoc = Env.createStorageLocation(*S);
683  Env.setStorageLocation(*S, ReturnLoc);
684  }
685  auto CalleeEnv = Env.pushCall(S);
686 
687  // FIXME: Use the same analysis as the caller for the callee. Note,
688  // though, that doing so would require support for changing the analysis's
689  // ASTContext.
690  assert(CFCtx->getDecl() != nullptr &&
691  "ControlFlowContexts in the environment should always carry a decl");
692  auto Analysis = NoopAnalysis(CFCtx->getDecl()->getASTContext(),
693  DataflowAnalysisOptions{Options});
694 
695  auto BlockToOutputState =
696  dataflow::runDataflowAnalysis(*CFCtx, Analysis, CalleeEnv);
697  assert(BlockToOutputState);
698  assert(ExitBlock < BlockToOutputState->size());
699 
700  auto ExitState = (*BlockToOutputState)[ExitBlock];
701  assert(ExitState);
702 
703  Env.popCall(ExitState->Env);
704  }
705 
706  const StmtToEnvMap &StmtToEnv;
707  Environment &Env;
708  TransferOptions Options;
709 };
710 
711 void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env,
712  TransferOptions Options) {
713  TransferVisitor(StmtToEnv, Env, Options).Visit(&S);
714 }
715 
716 } // namespace dataflow
717 } // namespace clang
clang::dataflow::TransferVisitor::VisitCXXConstructExpr
void VisitCXXConstructExpr(const CXXConstructExpr *S)
Definition: Transfer.cpp:419
clang::dataflow::TransferVisitor::VisitMemberExpr
void VisitMemberExpr(const MemberExpr *S)
Definition: Transfer.cpp:354
clang::dataflow::TransferVisitor::VisitCXXFunctionalCastExpr
void VisitCXXFunctionalCastExpr(const CXXFunctionalCastExpr *S)
Definition: Transfer.cpp:484
clang::dataflow::evaluateBooleanEquality
static BoolValue & evaluateBooleanEquality(const Expr &LHS, const Expr &RHS, Environment &Env)
Definition: Transfer.cpp:38
clang::dataflow::Environment::getReturnStorageLocation
StorageLocation * getReturnStorageLocation() const
Returns the storage location of the return value or null, if unset.
Definition: DataflowEnvironment.cpp:434
Builtins.h
clang::dataflow::TransferOptions::ContextSensitiveOpts
llvm::Optional< ContextSensitiveOptions > ContextSensitiveOpts
Options for analyzing function bodies when present in the translation unit, or empty to disable conte...
Definition: Transfer.h:35
clang::CXXConstructorDecl
Represents a C++ constructor within a class.
Definition: DeclCXX.h:2436
clang::dataflow::Environment::getOrCreateNullPointerValue
PointerValue & getOrCreateNullPointerValue(QualType PointeeType)
Returns a pointer value that represents a null pointer.
Definition: DataflowEnvironment.cpp:438
clang::CXXBoolLiteralExpr
A boolean literal, per ([C++ lex.bool] Boolean literals).
Definition: ExprCXX.h:721
Ret
static bool Ret(InterpState &S, CodePtr &PC, APValue &Result)
Definition: Interp.cpp:34
clang::dataflow::Environment::getBoolLiteralValue
AtomicBoolValue & getBoolLiteralValue(bool Value) const
Returns a symbolic boolean value that models a boolean literal equal to Value
Definition: DataflowEnvironment.h:282
clang::CFGBlock::getBlockID
unsigned getBlockID() const
Definition: CFG.h:1075
clang::QualType
A (possibly-)qualified type.
Definition: Type.h:731
clang::dataflow::StorageLocation
Base class for elements of the local variable store and of the heap.
Definition: StorageLocation.h:28
clang::dataflow::TransferVisitor::VisitDeclStmt
void VisitDeclStmt(const DeclStmt *S)
Definition: Transfer.cpp:127
clang::FieldDecl
Represents a member of a struct/union/class.
Definition: Decl.h:2878
DeclCXX.h
clang::dataflow::TransferVisitor
Definition: Transfer.cpp:49
clang::dataflow::Environment::createStorageLocation
StorageLocation & createStorageLocation(QualType Type)
Creates a storage location appropriate for Type.
Definition: DataflowEnvironment.cpp:388
clang::dataflow::SkipPast::Reference
@ Reference
An optional reference should be skipped past.
clang::InitListExpr
Describes an C or C++ initializer list.
Definition: Expr.h:4787
clang::dataflow::Environment::createValue
Value * createValue(QualType Type)
Creates a value appropriate for Type, if Type is supported, otherwise return null.
Definition: DataflowEnvironment.cpp:494
clang::UnaryOperator
UnaryOperator - This represents the unary-expression's (except sizeof and alignof),...
Definition: Expr.h:2163
NoopAnalysis.h
clang::CXXStaticCastExpr
A C++ static_cast expression (C++ [expr.static.cast]).
Definition: ExprCXX.h:431
clang::dataflow::TransferVisitor::VisitMaterializeTemporaryExpr
void VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *S)
Definition: Transfer.cpp:535
clang::dataflow::TransferVisitor::VisitCXXBindTemporaryExpr
void VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr *S)
Definition: Transfer.cpp:546
clang::dataflow::Environment::setStorageLocation
void setStorageLocation(const ValueDecl &D, StorageLocation &Loc)
Assigns Loc as the storage location of D in the environment.
Definition: DataflowEnvironment.cpp:406
clang::Type
The base class of the type hierarchy.
Definition: Type.h:1559
Decl.h
clang::ConditionalOperator
ConditionalOperator - The ?: ternary operator.
Definition: Expr.h:4141
clang::CXXTemporaryObjectExpr
Represents a C++ functional cast expression that builds a temporary object.
Definition: ExprCXX.h:1797
clang::dataflow::TransferVisitor::VisitCXXDefaultInitExpr
void VisitCXXDefaultInitExpr(const CXXDefaultInitExpr *S)
Definition: Transfer.cpp:402
clang::dataflow::StmtToEnvMap::getEnvironment
virtual const Environment * getEnvironment(const Stmt &S) const =0
Returns the environment of the basic block that contains S or nullptr if there isn't one.
clang::CXXBindTemporaryExpr
Represents binding an expression to a temporary.
Definition: ExprCXX.h:1412
clang::BinaryOperator
A builtin binary operation expression such as "x + y" or "x <= y".
Definition: Expr.h:3803
DeclBase.h
clang::dataflow::Environment::makeOr
BoolValue & makeOr(BoolValue &LHS, BoolValue &RHS) const
Returns a boolean value that represents the disjunction of LHS and RHS.
Definition: DataflowEnvironment.h:303
OperatorKinds.h
clang::dataflow::StmtToEnvMap
Maps statements to the environments of basic blocks that contain them.
Definition: Transfer.h:39
clang::MaterializeTemporaryExpr
Represents a prvalue temporary that is written into memory so that a reference can bind to it.
Definition: ExprCXX.h:4479
clang::dataflow::TransferVisitor::VisitInitListExpr
void VisitInitListExpr(const InitListExpr *S)
Definition: Transfer.cpp:580
clang::DeclaratorContext::Member
@ Member
clang::dataflow::SkipPast::None
@ None
No indirections should be skipped past.
clang::dataflow::Value::Kind::Reference
@ Reference
clang::dataflow::TransferVisitor::VisitUnaryOperator
void VisitUnaryOperator(const UnaryOperator *S)
Definition: Transfer.cpp:272
clang::dataflow::Environment::setValue
void setValue(const StorageLocation &Loc, Value &Val)
Assigns Val as the value of Loc in the environment.
Definition: DataflowEnvironment.cpp:442
clang::dataflow::TransferVisitor::VisitReturnStmt
void VisitReturnStmt(const ReturnStmt *S)
Definition: Transfer.cpp:335
clang::StmtVisitorBase< llvm::make_const_ptr, TransferVisitor, void, ParamTys... >::Visit
void Visit(PTR(Stmt) S, ParamTys... P)
Definition: StmtVisitor.h:43
clang::dataflow::TransferVisitor::VisitBinaryOperator
void VisitBinaryOperator(const BinaryOperator *S)
Definition: Transfer.cpp:55
clang::CXXConstructorDecl::isCopyOrMoveConstructor
bool isCopyOrMoveConstructor(unsigned &TypeQuals) const
Determine whether this is a copy or move constructor.
Definition: DeclCXX.cpp:2679
Expr.h
clang::dataflow::TransferVisitor::VisitExprWithCleanups
void VisitExprWithCleanups(const ExprWithCleanups *S)
Definition: Transfer.cpp:622
clang::ExprWithCleanups
Represents an expression – generally a full-expression – that introduces cleanups to be run at the en...
Definition: ExprCXX.h:3359
clang::dataflow::TransferVisitor::TransferVisitor
TransferVisitor(const StmtToEnvMap &StmtToEnv, Environment &Env, TransferOptions Options)
Definition: Transfer.cpp:51
OperationKinds.h
ExprCXX.h
clang::CFG::getExit
CFGBlock & getExit()
Definition: CFG.h:1334
clang::dataflow::Environment::getThisPointeeStorageLocation
StorageLocation * getThisPointeeStorageLocation() const
Returns the storage location assigned to the this pointee in the environment or null if the this poin...
Definition: DataflowEnvironment.cpp:430
clang::dataflow::Environment::popCall
void popCall(const Environment &CalleeEnv)
Moves gathered information back into this from a CalleeEnv created via pushCall.
Definition: DataflowEnvironment.cpp:278
clang::dataflow::TransferVisitor::VisitCXXStaticCastExpr
void VisitCXXStaticCastExpr(const CXXStaticCastExpr *S)
Definition: Transfer.cpp:557
clang::dataflow::TransferVisitor::VisitCXXThisExpr
void VisitCXXThisExpr(const CXXThisExpr *S)
Definition: Transfer.cpp:322
clang::dataflow::BoolValue
Models a boolean.
Definition: Value.h:80
clang::dataflow::Environment::getValue
Value * getValue(const StorageLocation &Loc) const
Returns the value assigned to Loc in the environment or null if Loc isn't assigned a value in the env...
Definition: DataflowEnvironment.cpp:475
clang::dataflow::TransferVisitor::VisitImplicitCastExpr
void VisitImplicitCastExpr(const ImplicitCastExpr *S)
Definition: Transfer.cpp:203
clang::dataflow::Environment::canDescend
bool canDescend(unsigned MaxDepth, const DeclContext *Callee) const
Returns whether this Environment can be extended to analyze the given Callee (i.e.
Definition: DataflowEnvironment.cpp:206
clang::ValueDecl
Represent the declaration of a variable (in which case it is an lvalue) a function (in which case it ...
Definition: Decl.h:674
clang::ParenExpr
ParenExpr - This represents a parethesized expression, e.g.
Definition: Expr.h:2112
clang::RecordDecl::fields
field_range fields() const
Definition: Decl.h:4155
clang::CXXFunctionalCastExpr
Represents an explicit C++ type conversion that uses "functional" notation (C++ [expr....
Definition: ExprCXX.h:1726
StmtVisitor.h
clang::Type::getAsRecordDecl
RecordDecl * getAsRecordDecl() const
Retrieves the RecordDecl this type refers to.
Definition: Type.cpp:1763
clang::dataflow::SkipPast::ReferenceThenPointer
@ ReferenceThenPointer
An optional reference should be skipped past, then an optional pointer should be skipped past.
clang::dataflow::TransferVisitor::VisitCXXBoolLiteralExpr
void VisitCXXBoolLiteralExpr(const CXXBoolLiteralExpr *S)
Definition: Transfer.cpp:607
DataflowEnvironment.h
clang::ConstStmtVisitor
ConstStmtVisitor - This class implements a simple visitor for Stmt subclasses.
Definition: StmtVisitor.h:193
clang::dataflow::Environment::makeAtomicBoolValue
BoolValue & makeAtomicBoolValue() const
Returns an atomic boolean value.
Definition: DataflowEnvironment.h:287
clang::Type::isStructureOrClassType
bool isStructureOrClassType() const
Definition: Type.cpp:581
clang::DeclStmt
DeclStmt - Adaptor class for mixing declarations with statements and expressions.
Definition: Stmt.h:1299
clang::dataflow::TransferVisitor::VisitParenExpr
void VisitParenExpr(const ParenExpr *S)
Definition: Transfer.cpp:613
clang::CXXThisExpr
Represents the this expression in C++.
Definition: ExprCXX.h:1142
clang::dataflow::Environment::getControlFlowContext
const ControlFlowContext * getControlFlowContext(const FunctionDecl *F)
Returns the ControlFlowContext registered for F, if any.
Definition: DataflowEnvironment.h:360
ControlFlowContext.h
clang::dataflow::TransferVisitor::VisitCallExpr
void VisitCallExpr(const CallExpr *S)
Definition: Transfer.cpp:504
Transfer.h
clang
Definition: CalledOnceCheck.h:17
clang::dataflow::TransferVisitor::VisitCXXTemporaryObjectExpr
void VisitCXXTemporaryObjectExpr(const CXXTemporaryObjectExpr *S)
Definition: Transfer.cpp:497
clang::dataflow::TransferOptions
Definition: Transfer.h:30
clang::Stmt
Stmt - This represents one statement.
Definition: Stmt.h:70
clang::Expr::getType
QualType getType() const
Definition: Expr.h:141
clang::dataflow::Environment::makeAnd
BoolValue & makeAnd(BoolValue &LHS, BoolValue &RHS) const
Returns a boolean value that represents the conjunction of LHS and RHS.
Definition: DataflowEnvironment.h:295
clang::dataflow::Environment::takeOwnership
std::enable_if< std::is_base_of< StorageLocation, T >::value, T & >::type takeOwnership(std::unique_ptr< T > Loc)
Transfers ownership of Loc to the analysis context and returns a reference to it.
Definition: DataflowEnvironment.h:264
clang::Type::getUnqualifiedDesugaredType
const Type * getUnqualifiedDesugaredType() const
Return the specified type with any "sugar" removed from the type, removing any typedefs,...
Definition: Type.cpp:539
clang::dataflow::Value
Base class for all values computed by abstract interpretation.
Definition: Value.h:32
clang::dataflow::Environment::pushCall
Environment pushCall(const CallExpr *Call) const
Creates and returns an environment to use for an inline analysis of the callee.
Definition: DataflowEnvironment.cpp:211
clang::dataflow::Environment::makeIff
BoolValue & makeIff(BoolValue &LHS, BoolValue &RHS) const
Returns a boolean value represents LHS <=> RHS.
Definition: DataflowEnvironment.h:325
clang::ImplicitCastExpr
ImplicitCastExpr - Allows us to explicitly represent implicit type conversions, which have no direct ...
Definition: Expr.h:3615
clang::dataflow::transfer
void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env, TransferOptions Options)
Evaluates S and updates Env accordingly.
Definition: Transfer.cpp:711
clang::MemberExpr
MemberExpr - [C99 6.5.2.3] Structure and Union Members.
Definition: Expr.h:3160
clang::dataflow::TransferVisitor::VisitConditionalOperator
void VisitConditionalOperator(const ConditionalOperator *S)
Definition: Transfer.cpp:570
Stmt.h
clang::dataflow::Environment::getStorageLocation
StorageLocation * getStorageLocation(const ValueDecl &D, SkipPast SP) const
Returns the storage location assigned to D in the environment, applying the SP policy for skipping pa...
Definition: DataflowEnvironment.cpp:411
clang::dataflow::Environment
Holds the state of the program (store and heap) at a given program point.
Definition: DataflowEnvironment.h:57
clang::dataflow::TransferVisitor::VisitCXXOperatorCallExpr
void VisitCXXOperatorCallExpr(const CXXOperatorCallExpr *S)
Definition: Transfer.cpp:451
clang::Expr
This represents one expression.
Definition: Expr.h:109
clang::CXXDefaultInitExpr
A use of a default initializer in a constructor or in aggregate initialization.
Definition: ExprCXX.h:1318
clang::DeclRefExpr
A reference to a declared variable, function, enum, etc.
Definition: Expr.h:1223
clang::FunctionDecl
Represents a function declaration or definition.
Definition: Decl.h:1877
Value.h
clang::CallExpr
CallExpr - Represents a function call (C99 6.5.2.2, C++ [expr.call]).
Definition: Expr.h:2801
clang::dataflow::Environment::makeNot
BoolValue & makeNot(BoolValue &Val) const
Returns a boolean value that represents the negation of Val.
Definition: DataflowEnvironment.h:309
clang::dataflow::TransferVisitor::VisitDeclRefExpr
void VisitDeclRefExpr(const DeclRefExpr *S)
Definition: Transfer.cpp:111
clang::CXXOperatorCallExpr
A call to an overloaded operator written using operator syntax.
Definition: ExprCXX.h:82
clang::CXXConstructExpr
Represents a call to a C++ constructor.
Definition: ExprCXX.h:1460
clang::dataflow::runDataflowAnalysis
llvm::Expected< std::vector< llvm::Optional< DataflowAnalysisState< typename AnalysisT::Lattice > > > > runDataflowAnalysis(const ControlFlowContext &CFCtx, AnalysisT &Analysis, const Environment &InitEnv, std::function< void(const CFGElement &, const DataflowAnalysisState< typename AnalysisT::Lattice > &)> PostVisitCFG=nullptr)
Performs dataflow analysis and returns a mapping from basic block IDs to dataflow analysis states tha...
Definition: DataflowAnalysis.h:149
clang::ReturnStmt
ReturnStmt - This represents a return, optionally of an expression: return; return 4;.
Definition: Stmt.h:2792
clang::dataflow::ControlFlowContext::getCFG
const CFG & getCFG() const
Returns the CFG that is stored in this context.
Definition: ControlFlowContext.h:47