clang 17.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"
29#include "llvm/ADT/STLExtras.h"
30#include "llvm/Support/Casting.h"
31#include "llvm/Support/ErrorHandling.h"
32#include <cassert>
33#include <memory>
34#include <tuple>
35
36namespace clang {
37namespace dataflow {
38
40 auto BlockIt = CFCtx.getStmtToBlock().find(&ignoreCFGOmittedNodes(S));
41 assert(BlockIt != CFCtx.getStmtToBlock().end());
42 if (!CFCtx.isBlockReachable(*BlockIt->getSecond()))
43 return nullptr;
44 const auto &State = BlockToState[BlockIt->getSecond()->getBlockID()];
45 assert(State);
46 return &State->Env;
47}
48
49static BoolValue &evaluateBooleanEquality(const Expr &LHS, const Expr &RHS,
51 if (auto *LHSValue = dyn_cast_or_null<BoolValue>(Env.getValueStrict(LHS)))
52 if (auto *RHSValue = dyn_cast_or_null<BoolValue>(Env.getValueStrict(RHS)))
53 return Env.makeIff(*LHSValue, *RHSValue);
54
55 return Env.makeAtomicBoolValue();
56}
57
58// Functionally updates `V` such that any instances of `TopBool` are replaced
59// with fresh atomic bools. Note: This implementation assumes that `B` is a
60// tree; if `B` is a DAG, it will lose any sharing between subvalues that was
61// present in the original .
62static BoolValue &unpackValue(BoolValue &V, Environment &Env);
63
64template <typename Derived, typename M>
66 auto &V = *cast<Derived>(&B);
67 BoolValue &Left = V.getLeftSubValue();
68 BoolValue &Right = V.getRightSubValue();
69 BoolValue &ULeft = unpackValue(Left, Env);
70 BoolValue &URight = unpackValue(Right, Env);
71
72 if (&ULeft == &Left && &URight == &Right)
73 return V;
74
75 return (Env.*build)(ULeft, URight);
76}
77
79 switch (V.getKind()) {
84 llvm_unreachable("BoolValue cannot have any of these kinds.");
85
87 return V;
88
90 // Unpack `TopBool` into a fresh atomic bool.
91 return Env.makeAtomicBoolValue();
92
94 auto &N = *cast<NegationValue>(&V);
95 BoolValue &Sub = N.getSubVal();
96 BoolValue &USub = unpackValue(Sub, Env);
97
98 if (&USub == &Sub)
99 return V;
100 return Env.makeNot(USub);
101 }
103 return unpackBinaryBoolValue<ConjunctionValue>(Env, V,
106 return unpackBinaryBoolValue<DisjunctionValue>(Env, V,
109 return unpackBinaryBoolValue<ImplicationValue>(
112 return unpackBinaryBoolValue<BiconditionalValue>(Env, V,
114 }
115 llvm_unreachable("All reachable cases in switch return");
116}
117
118// Unpacks the value (if any) associated with `E` and updates `E` to the new
119// value, if any unpacking occured. Also, does the lvalue-to-rvalue conversion,
120// by skipping past the reference.
122 auto *Loc = Env.getStorageLocationStrict(E);
123 if (Loc == nullptr)
124 return nullptr;
125 auto *Val = Env.getValue(*Loc);
126
127 auto *B = dyn_cast_or_null<BoolValue>(Val);
128 if (B == nullptr)
129 return Val;
130
131 auto &UnpackedVal = unpackValue(*B, Env);
132 if (&UnpackedVal == Val)
133 return Val;
134 Env.setValue(*Loc, UnpackedVal);
135 return &UnpackedVal;
136}
137
138static void propagateValue(const Expr &From, const Expr &To, Environment &Env) {
139 if (auto *Val = Env.getValueStrict(From))
140 Env.setValueStrict(To, *Val);
141}
142
143static void propagateStorageLocation(const Expr &From, const Expr &To,
144 Environment &Env) {
145 if (auto *Loc = Env.getStorageLocationStrict(From))
147}
148
149// Forwards the value or storage location of `From` to `To` in cases where
150// `From` may be either a glvalue or a prvalue. `To` must be a glvalue iff
151// `From` is a glvalue.
152static void propagateValueOrStorageLocation(const Expr &From, const Expr &To,
153 Environment &Env) {
154 assert(From.isGLValue() == To.isGLValue());
155 if (From.isGLValue())
156 propagateStorageLocation(From, To, Env);
157 else
158 propagateValue(From, To, Env);
159}
160
161namespace {
162
163class TransferVisitor : public ConstStmtVisitor<TransferVisitor> {
164public:
165 TransferVisitor(const StmtToEnvMap &StmtToEnv, Environment &Env)
166 : StmtToEnv(StmtToEnv), Env(Env) {}
167
168 void VisitBinaryOperator(const BinaryOperator *S) {
169 const Expr *LHS = S->getLHS();
170 assert(LHS != nullptr);
171
172 const Expr *RHS = S->getRHS();
173 assert(RHS != nullptr);
174
175 switch (S->getOpcode()) {
176 case BO_Assign: {
177 auto *LHSLoc = Env.getStorageLocationStrict(*LHS);
178 if (LHSLoc == nullptr)
179 break;
180
181 auto *RHSVal = Env.getValueStrict(*RHS);
182 if (RHSVal == nullptr)
183 break;
184
185 // Assign a value to the storage location of the left-hand side.
186 Env.setValue(*LHSLoc, *RHSVal);
187
188 // Assign a storage location for the whole expression.
189 Env.setStorageLocation(*S, *LHSLoc);
190 break;
191 }
192 case BO_LAnd:
193 case BO_LOr: {
194 auto &Loc = Env.createStorageLocation(*S);
195 Env.setStorageLocation(*S, Loc);
196
197 BoolValue &LHSVal = getLogicOperatorSubExprValue(*LHS);
198 BoolValue &RHSVal = getLogicOperatorSubExprValue(*RHS);
199
200 if (S->getOpcode() == BO_LAnd)
201 Env.setValue(Loc, Env.makeAnd(LHSVal, RHSVal));
202 else
203 Env.setValue(Loc, Env.makeOr(LHSVal, RHSVal));
204 break;
205 }
206 case BO_NE:
207 case BO_EQ: {
208 auto &LHSEqRHSValue = evaluateBooleanEquality(*LHS, *RHS, Env);
209 auto &Loc = Env.createStorageLocation(*S);
210 Env.setStorageLocation(*S, Loc);
211 Env.setValue(Loc, S->getOpcode() == BO_EQ ? LHSEqRHSValue
212 : Env.makeNot(LHSEqRHSValue));
213 break;
214 }
215 case BO_Comma: {
216 propagateValueOrStorageLocation(*RHS, *S, Env);
217 break;
218 }
219 default:
220 break;
221 }
222 }
223
224 void VisitDeclRefExpr(const DeclRefExpr *S) {
225 const ValueDecl *VD = S->getDecl();
226 assert(VD != nullptr);
227 auto *DeclLoc = Env.getStorageLocation(*VD);
228 if (DeclLoc == nullptr)
229 return;
230
231 Env.setStorageLocationStrict(*S, *DeclLoc);
232 }
233
234 void VisitDeclStmt(const DeclStmt *S) {
235 // Group decls are converted into single decls in the CFG so the cast below
236 // is safe.
237 const auto &D = *cast<VarDecl>(S->getSingleDecl());
238
239 ProcessVarDecl(D);
240 }
241
242 void ProcessVarDecl(const VarDecl &D) {
243 // Static local vars are already initialized in `Environment`.
244 if (D.hasGlobalStorage())
245 return;
246
247 if (D.getType()->isReferenceType()) {
248 // If this is the holding variable for a `BindingDecl`, we may already
249 // have a storage location set up -- so check. (See also explanation below
250 // where we process the `BindingDecl`.)
251 if (Env.getStorageLocation(D) == nullptr) {
252 const Expr *InitExpr = D.getInit();
253 assert(InitExpr != nullptr);
254 if (auto *InitExprLoc =
255 Env.getStorageLocation(*InitExpr, SkipPast::Reference)) {
256 Env.setStorageLocation(D, *InitExprLoc);
257 } else {
258 // Even though we have an initializer, we might not get an
259 // InitExprLoc, for example if the InitExpr is a CallExpr for which we
260 // don't have a function body. In this case, we just invent a storage
261 // location and value -- it's the best we can do.
262 StorageLocation &Loc =
263 Env.createStorageLocation(D.getType().getNonReferenceType());
264 Env.setStorageLocation(D, Loc);
265 if (Value *Val = Env.createValue(D.getType().getNonReferenceType()))
266 Env.setValue(Loc, *Val);
267 }
268 }
269 } else {
270 // Not a reference type.
271
272 assert(Env.getStorageLocation(D) == nullptr);
273 StorageLocation &Loc = Env.createStorageLocation(D);
274 Env.setStorageLocation(D, Loc);
275
276 const Expr *InitExpr = D.getInit();
277 if (InitExpr == nullptr) {
278 // No initializer expression - associate `Loc` with a new value.
279 if (Value *Val = Env.createValue(D.getType()))
280 Env.setValue(Loc, *Val);
281 return;
282 }
283
284 if (auto *InitExprVal = Env.getValueStrict(*InitExpr))
285 Env.setValue(Loc, *InitExprVal);
286
287 if (Env.getValue(Loc) == nullptr) {
288 // We arrive here in (the few) cases where an expression is
289 // intentionally "uninterpreted". There are two ways to handle this
290 // situation: propagate the status, so that uninterpreted initializers
291 // result in uninterpreted variables, or provide a default value. We
292 // choose the latter so that later refinements of the variable can be
293 // used for reasoning about the surrounding code.
294 //
295 // FIXME. If and when we interpret all language cases, change this to
296 // assert that `InitExpr` is interpreted, rather than supplying a
297 // default value (assuming we don't update the environment API to return
298 // references).
299 if (Value *Val = Env.createValue(D.getType()))
300 Env.setValue(Loc, *Val);
301 }
302 }
303
304 // `DecompositionDecl` must be handled after we've interpreted the loc
305 // itself, because the binding expression refers back to the
306 // `DecompositionDecl` (even though it has no written name).
307 if (const auto *Decomp = dyn_cast<DecompositionDecl>(&D)) {
308 // If VarDecl is a DecompositionDecl, evaluate each of its bindings. This
309 // needs to be evaluated after initializing the values in the storage for
310 // VarDecl, as the bindings refer to them.
311 // FIXME: Add support for ArraySubscriptExpr.
312 // FIXME: Consider adding AST nodes used in BindingDecls to the CFG.
313 for (const auto *B : Decomp->bindings()) {
314 if (auto *ME = dyn_cast_or_null<MemberExpr>(B->getBinding())) {
315 auto *DE = dyn_cast_or_null<DeclRefExpr>(ME->getBase());
316 if (DE == nullptr)
317 continue;
318
319 // ME and its base haven't been visited because they aren't included
320 // in the statements of the CFG basic block.
321 VisitDeclRefExpr(DE);
322 VisitMemberExpr(ME);
323
324 if (auto *Loc = Env.getStorageLocation(*ME, SkipPast::Reference))
325 Env.setStorageLocation(*B, *Loc);
326 } else if (auto *VD = B->getHoldingVar()) {
327 // Holding vars are used to back the `BindingDecl`s of tuple-like
328 // types. The holding var declarations appear after the
329 // `DecompositionDecl`, so we have to explicitly process them here
330 // to know their storage location. They will be processed a second
331 // time when we visit their `VarDecl`s, so we have code that protects
332 // against this above.
333 ProcessVarDecl(*VD);
334 auto *VDLoc = Env.getStorageLocation(*VD);
335 assert(VDLoc != nullptr);
336 Env.setStorageLocation(*B, *VDLoc);
337 }
338 }
339 }
340 }
341
342 void VisitImplicitCastExpr(const ImplicitCastExpr *S) {
343 const Expr *SubExpr = S->getSubExpr();
344 assert(SubExpr != nullptr);
345
346 switch (S->getCastKind()) {
347 case CK_IntegralToBoolean: {
348 // This cast creates a new, boolean value from the integral value. We
349 // model that with a fresh value in the environment, unless it's already a
350 // boolean.
351 if (auto *SubExprVal =
352 dyn_cast_or_null<BoolValue>(Env.getValueStrict(*SubExpr)))
353 Env.setValueStrict(*S, *SubExprVal);
354 else
355 // FIXME: If integer modeling is added, then update this code to create
356 // the boolean based on the integer model.
357 Env.setValueStrict(*S, Env.makeAtomicBoolValue());
358 break;
359 }
360
361 case CK_LValueToRValue: {
362 // When an L-value is used as an R-value, it may result in sharing, so we
363 // need to unpack any nested `Top`s. We also need to strip off the
364 // `ReferenceValue` associated with the lvalue.
365 auto *SubExprVal = maybeUnpackLValueExpr(*SubExpr, Env);
366 if (SubExprVal == nullptr)
367 break;
368
369 auto &ExprLoc = Env.createStorageLocation(*S);
370 Env.setStorageLocation(*S, ExprLoc);
371 Env.setValue(ExprLoc, *SubExprVal);
372 break;
373 }
374
375 case CK_IntegralCast:
376 // FIXME: This cast creates a new integral value from the
377 // subexpression. But, because we don't model integers, we don't
378 // distinguish between this new value and the underlying one. If integer
379 // modeling is added, then update this code to create a fresh location and
380 // value.
381 case CK_UncheckedDerivedToBase:
382 case CK_ConstructorConversion:
383 case CK_UserDefinedConversion:
384 // FIXME: Add tests that excercise CK_UncheckedDerivedToBase,
385 // CK_ConstructorConversion, and CK_UserDefinedConversion.
386 case CK_NoOp: {
387 // FIXME: Consider making `Environment::getStorageLocation` skip noop
388 // expressions (this and other similar expressions in the file) instead
389 // of assigning them storage locations.
390 propagateValueOrStorageLocation(*SubExpr, *S, Env);
391 break;
392 }
393 case CK_NullToPointer:
394 case CK_NullToMemberPointer: {
395 auto &Loc = Env.createStorageLocation(S->getType());
396 Env.setStorageLocation(*S, Loc);
397
398 auto &NullPointerVal =
399 Env.getOrCreateNullPointerValue(S->getType()->getPointeeType());
400 Env.setValue(Loc, NullPointerVal);
401 break;
402 }
403 case CK_FunctionToPointerDecay: {
404 StorageLocation *PointeeLoc =
405 Env.getStorageLocation(*SubExpr, SkipPast::Reference);
406 if (PointeeLoc == nullptr)
407 break;
408
409 auto &PointerLoc = Env.createStorageLocation(*S);
410 auto &PointerVal = Env.create<PointerValue>(*PointeeLoc);
411 Env.setStorageLocation(*S, PointerLoc);
412 Env.setValue(PointerLoc, PointerVal);
413 break;
414 }
415 default:
416 break;
417 }
418 }
419
420 void VisitUnaryOperator(const UnaryOperator *S) {
421 const Expr *SubExpr = S->getSubExpr();
422 assert(SubExpr != nullptr);
423
424 switch (S->getOpcode()) {
425 case UO_Deref: {
426 const auto *SubExprVal =
427 cast_or_null<PointerValue>(Env.getValueStrict(*SubExpr));
428 if (SubExprVal == nullptr)
429 break;
430
431 Env.setStorageLocationStrict(*S, SubExprVal->getPointeeLoc());
432 break;
433 }
434 case UO_AddrOf: {
435 // Do not form a pointer to a reference. If `SubExpr` is assigned a
436 // `ReferenceValue` then form a value that points to the location of its
437 // pointee.
438 StorageLocation *PointeeLoc = Env.getStorageLocationStrict(*SubExpr);
439 if (PointeeLoc == nullptr)
440 break;
441
442 Env.setValueStrict(*S, Env.create<PointerValue>(*PointeeLoc));
443 break;
444 }
445 case UO_LNot: {
446 auto *SubExprVal =
447 dyn_cast_or_null<BoolValue>(Env.getValueStrict(*SubExpr));
448 if (SubExprVal == nullptr)
449 break;
450
451 auto &ExprLoc = Env.createStorageLocation(*S);
452 Env.setStorageLocation(*S, ExprLoc);
453 Env.setValue(ExprLoc, Env.makeNot(*SubExprVal));
454 break;
455 }
456 default:
457 break;
458 }
459 }
460
461 void VisitCXXThisExpr(const CXXThisExpr *S) {
462 auto *ThisPointeeLoc = Env.getThisPointeeStorageLocation();
463 if (ThisPointeeLoc == nullptr)
464 // Unions are not supported yet, and will not have a location for the
465 // `this` expression's pointee.
466 return;
467
468 auto &Loc = Env.createStorageLocation(*S);
469 Env.setStorageLocation(*S, Loc);
470 Env.setValue(Loc, Env.create<PointerValue>(*ThisPointeeLoc));
471 }
472
473 void VisitCXXNewExpr(const CXXNewExpr *S) {
474 auto &Loc = Env.createStorageLocation(*S);
475 Env.setStorageLocation(*S, Loc);
476 if (Value *Val = Env.createValue(S->getType()))
477 Env.setValue(Loc, *Val);
478 }
479
480 void VisitCXXDeleteExpr(const CXXDeleteExpr *S) {
481 // Empty method.
482 // We consciously don't do anything on deletes. Diagnosing double deletes
483 // (for example) should be done by a specific analysis, not by the
484 // framework.
485 }
486
487 void VisitReturnStmt(const ReturnStmt *S) {
488 if (!Env.getDataflowAnalysisContext().getOptions().ContextSensitiveOpts)
489 return;
490
491 auto *Ret = S->getRetValue();
492 if (Ret == nullptr)
493 return;
494
495 if (Ret->isPRValue()) {
496 auto *Val = Env.getValueStrict(*Ret);
497 if (Val == nullptr)
498 return;
499
500 // FIXME: Model NRVO.
501 Env.setReturnValue(Val);
502 } else {
503 auto *Loc = Env.getStorageLocationStrict(*Ret);
504 if (Loc == nullptr)
505 return;
506
507 // FIXME: Model NRVO.
508 Env.setReturnStorageLocation(Loc);
509 }
510 }
511
512 void VisitMemberExpr(const MemberExpr *S) {
513 ValueDecl *Member = S->getMemberDecl();
514 assert(Member != nullptr);
515
516 // FIXME: Consider assigning pointer values to function member expressions.
517 if (Member->isFunctionOrFunctionTemplate())
518 return;
519
520 // FIXME: if/when we add support for modeling enums, use that support here.
521 if (isa<EnumConstantDecl>(Member))
522 return;
523
524 if (auto *D = dyn_cast<VarDecl>(Member)) {
525 if (D->hasGlobalStorage()) {
526 auto *VarDeclLoc = Env.getStorageLocation(*D);
527 if (VarDeclLoc == nullptr)
528 return;
529
530 Env.setStorageLocation(*S, *VarDeclLoc);
531 return;
532 }
533 }
534
535 AggregateStorageLocation *BaseLoc = getBaseObjectLocation(*S, Env);
536 if (BaseLoc == nullptr)
537 return;
538
539 auto &MemberLoc = BaseLoc->getChild(*Member);
540 if (MemberLoc.getType()->isReferenceType()) {
541 // Based on its type, `MemberLoc` must be mapped either to nothing or to a
542 // `ReferenceValue`. For the former, we won't set a storage location for
543 // this expression, so as to maintain an invariant lvalue expressions;
544 // namely, that their location maps to a `ReferenceValue`. In this,
545 // lvalues are unlike other expressions, where it is valid for their
546 // location to map to nothing (because they are not modeled).
547 //
548 // Note: we need this invariant for lvalues so that, when accessing a
549 // value, we can distinguish an rvalue from an lvalue. An alternative
550 // design, which takes the expression's value category into account, would
551 // avoid the need for this invariant.
552 if (auto *V = Env.getValue(MemberLoc)) {
553 assert(isa<ReferenceValue>(V) &&
554 "reference-typed declarations map to `ReferenceValue`s");
555 Env.setStorageLocation(*S, MemberLoc);
556 }
557 } else {
558 auto &Loc = Env.createStorageLocation(*S);
559 Env.setStorageLocation(*S, Loc);
560 Env.setValue(Loc, Env.create<ReferenceValue>(MemberLoc));
561 }
562 }
563
564 void VisitCXXDefaultInitExpr(const CXXDefaultInitExpr *S) {
565 const Expr *InitExpr = S->getExpr();
566 assert(InitExpr != nullptr);
567
568 Value *InitExprVal = Env.getValue(*InitExpr, SkipPast::None);
569 if (InitExprVal == nullptr)
570 return;
571
572 const FieldDecl *Field = S->getField();
573 assert(Field != nullptr);
574
575 auto &ThisLoc =
576 *cast<AggregateStorageLocation>(Env.getThisPointeeStorageLocation());
577 auto &FieldLoc = ThisLoc.getChild(*Field);
578 Env.setValue(FieldLoc, *InitExprVal);
579 }
580
581 void VisitCXXConstructExpr(const CXXConstructExpr *S) {
582 const CXXConstructorDecl *ConstructorDecl = S->getConstructor();
583 assert(ConstructorDecl != nullptr);
584
585 if (ConstructorDecl->isCopyOrMoveConstructor()) {
586 // It is permissible for a copy/move constructor to have additional
587 // parameters as long as they have default arguments defined for them.
588 assert(S->getNumArgs() != 0);
589
590 const Expr *Arg = S->getArg(0);
591 assert(Arg != nullptr);
592
593 if (S->isElidable()) {
594 auto *ArgLoc = Env.getStorageLocation(*Arg, SkipPast::Reference);
595 if (ArgLoc == nullptr)
596 return;
597
598 Env.setStorageLocation(*S, *ArgLoc);
599 } else if (auto *ArgVal = Env.getValue(*Arg, SkipPast::Reference)) {
600 auto &Loc = Env.createStorageLocation(*S);
601 Env.setStorageLocation(*S, Loc);
602 Env.setValue(Loc, *ArgVal);
603 }
604 return;
605 }
606
607 auto &Loc = Env.createStorageLocation(*S);
608 Env.setStorageLocation(*S, Loc);
609 if (Value *Val = Env.createValue(S->getType()))
610 Env.setValue(Loc, *Val);
611
612 transferInlineCall(S, ConstructorDecl);
613 }
614
615 void VisitCXXOperatorCallExpr(const CXXOperatorCallExpr *S) {
616 if (S->getOperator() == OO_Equal) {
617 assert(S->getNumArgs() == 2);
618
619 const Expr *Arg0 = S->getArg(0);
620 assert(Arg0 != nullptr);
621
622 const Expr *Arg1 = S->getArg(1);
623 assert(Arg1 != nullptr);
624
625 // Evaluate only copy and move assignment operators.
626 const auto *Method =
627 dyn_cast_or_null<CXXMethodDecl>(S->getDirectCallee());
628 if (!Method)
629 return;
630 if (!Method->isCopyAssignmentOperator() &&
631 !Method->isMoveAssignmentOperator())
632 return;
633
634 auto *ObjectLoc = Env.getStorageLocation(*Arg0, SkipPast::Reference);
635 if (ObjectLoc == nullptr)
636 return;
637
638 auto *Val = Env.getValue(*Arg1, SkipPast::Reference);
639 if (Val == nullptr)
640 return;
641
642 // Assign a value to the storage location of the object.
643 Env.setValue(*ObjectLoc, *Val);
644
645 // FIXME: Add a test for the value of the whole expression.
646 // Assign a storage location for the whole expression.
647 Env.setStorageLocation(*S, *ObjectLoc);
648 }
649 }
650
651 void VisitCXXFunctionalCastExpr(const CXXFunctionalCastExpr *S) {
652 if (S->getCastKind() == CK_ConstructorConversion) {
653 const Expr *SubExpr = S->getSubExpr();
654 assert(SubExpr != nullptr);
655
656 propagateValue(*SubExpr, *S, Env);
657 }
658 }
659
660 void VisitCXXTemporaryObjectExpr(const CXXTemporaryObjectExpr *S) {
661 if (Value *Val = Env.createValue(S->getType()))
662 Env.setValueStrict(*S, *Val);
663 }
664
665 void VisitCallExpr(const CallExpr *S) {
666 // Of clang's builtins, only `__builtin_expect` is handled explicitly, since
667 // others (like trap, debugtrap, and unreachable) are handled by CFG
668 // construction.
669 if (S->isCallToStdMove()) {
670 assert(S->getNumArgs() == 1);
671
672 const Expr *Arg = S->getArg(0);
673 assert(Arg != nullptr);
674
675 auto *ArgLoc = Env.getStorageLocation(*Arg, SkipPast::None);
676 if (ArgLoc == nullptr)
677 return;
678
679 Env.setStorageLocation(*S, *ArgLoc);
680 } else if (S->getDirectCallee() != nullptr &&
681 S->getDirectCallee()->getBuiltinID() ==
682 Builtin::BI__builtin_expect) {
683 assert(S->getNumArgs() > 0);
684 assert(S->getArg(0) != nullptr);
685 // `__builtin_expect` returns by-value, so strip away any potential
686 // references in the argument.
687 auto *ArgLoc = Env.getStorageLocation(*S->getArg(0), SkipPast::Reference);
688 if (ArgLoc == nullptr)
689 return;
690 Env.setStorageLocation(*S, *ArgLoc);
691 } else if (const FunctionDecl *F = S->getDirectCallee()) {
692 transferInlineCall(S, F);
693 }
694 }
695
696 void VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *S) {
697 const Expr *SubExpr = S->getSubExpr();
698 assert(SubExpr != nullptr);
699
700 Value *SubExprVal = Env.getValueStrict(*SubExpr);
701 if (SubExprVal == nullptr)
702 return;
703
704 auto &Loc = Env.createStorageLocation(*S);
705 Env.setStorageLocationStrict(*S, Loc);
706 Env.setValue(Loc, *SubExprVal);
707 }
708
709 void VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr *S) {
710 const Expr *SubExpr = S->getSubExpr();
711 assert(SubExpr != nullptr);
712
713 propagateValue(*SubExpr, *S, Env);
714 }
715
716 void VisitCXXStaticCastExpr(const CXXStaticCastExpr *S) {
717 if (S->getCastKind() == CK_NoOp) {
718 const Expr *SubExpr = S->getSubExpr();
719 assert(SubExpr != nullptr);
720
721 propagateValueOrStorageLocation(*SubExpr, *S, Env);
722 }
723 }
724
725 void VisitConditionalOperator(const ConditionalOperator *S) {
726 // FIXME: Revisit this once flow conditions are added to the framework. For
727 // `a = b ? c : d` we can add `b => a == c && !b => a == d` to the flow
728 // condition.
729 if (S->isGLValue()) {
730 auto &Loc = Env.createStorageLocation(*S);
731 Env.setStorageLocationStrict(*S, Loc);
732 if (Value *Val = Env.createValue(S->getType()))
733 Env.setValue(Loc, *Val);
734 } else if (Value *Val = Env.createValue(S->getType())) {
735 Env.setValueStrict(*S, *Val);
736 }
737 }
738
739 void VisitInitListExpr(const InitListExpr *S) {
740 QualType Type = S->getType();
741
742 auto &Loc = Env.createStorageLocation(*S);
743 Env.setStorageLocation(*S, Loc);
744
745 auto *Val = Env.createValue(Type);
746 if (Val == nullptr)
747 return;
748
749 Env.setValue(Loc, *Val);
750
751 if (Type->isStructureOrClassType()) {
752 // Unnamed bitfields are only used for padding and are not appearing in
753 // `InitListExpr`'s inits. However, those fields do appear in RecordDecl's
754 // field list, and we thus need to remove them before mapping inits to
755 // fields to avoid mapping inits to the wrongs fields.
756 std::vector<FieldDecl *> Fields;
757 llvm::copy_if(
758 Type->getAsRecordDecl()->fields(), std::back_inserter(Fields),
759 [](const FieldDecl *Field) { return !Field->isUnnamedBitfield(); });
760 for (auto It : llvm::zip(Fields, S->inits())) {
761 const FieldDecl *Field = std::get<0>(It);
762 assert(Field != nullptr);
763
764 const Expr *Init = std::get<1>(It);
765 assert(Init != nullptr);
766
767 if (Value *InitVal = Env.getValue(*Init, SkipPast::None))
768 cast<StructValue>(Val)->setChild(*Field, *InitVal);
769 }
770 }
771 // FIXME: Implement array initialization.
772 }
773
774 void VisitCXXBoolLiteralExpr(const CXXBoolLiteralExpr *S) {
775 Env.setValueStrict(*S, Env.getBoolLiteralValue(S->getValue()));
776 }
777
778 void VisitParenExpr(const ParenExpr *S) {
779 // The CFG does not contain `ParenExpr` as top-level statements in basic
780 // blocks, however manual traversal to sub-expressions may encounter them.
781 // Redirect to the sub-expression.
782 auto *SubExpr = S->getSubExpr();
783 assert(SubExpr != nullptr);
784 Visit(SubExpr);
785 }
786
787 void VisitExprWithCleanups(const ExprWithCleanups *S) {
788 // The CFG does not contain `ExprWithCleanups` as top-level statements in
789 // basic blocks, however manual traversal to sub-expressions may encounter
790 // them. Redirect to the sub-expression.
791 auto *SubExpr = S->getSubExpr();
792 assert(SubExpr != nullptr);
793 Visit(SubExpr);
794 }
795
796private:
797 /// Returns the value for the sub-expression `SubExpr` of a logic operator.
798 BoolValue &getLogicOperatorSubExprValue(const Expr &SubExpr) {
799 // `SubExpr` and its parent logic operator might be part of different basic
800 // blocks. We try to access the value that is assigned to `SubExpr` in the
801 // corresponding environment.
802 if (const Environment *SubExprEnv = StmtToEnv.getEnvironment(SubExpr))
803 if (auto *Val =
804 dyn_cast_or_null<BoolValue>(SubExprEnv->getValueStrict(SubExpr)))
805 return *Val;
806
807 // The sub-expression may lie within a basic block that isn't reachable,
808 // even if we need it to evaluate the current (reachable) expression
809 // (see https://discourse.llvm.org/t/70775). In this case, visit `SubExpr`
810 // within the current environment and then try to get the value that gets
811 // assigned to it.
812 if (Env.getValueStrict(SubExpr) == nullptr)
813 Visit(&SubExpr);
814 if (auto *Val = dyn_cast_or_null<BoolValue>(Env.getValueStrict(SubExpr)))
815 return *Val;
816
817 // If the value of `SubExpr` is still unknown, we create a fresh symbolic
818 // boolean value for it.
819 return Env.makeAtomicBoolValue();
820 }
821
822 // If context sensitivity is enabled, try to analyze the body of the callee
823 // `F` of `S`. The type `E` must be either `CallExpr` or `CXXConstructExpr`.
824 template <typename E>
825 void transferInlineCall(const E *S, const FunctionDecl *F) {
826 const auto &Options = Env.getDataflowAnalysisContext().getOptions();
827 if (!(Options.ContextSensitiveOpts &&
828 Env.canDescend(Options.ContextSensitiveOpts->Depth, F)))
829 return;
830
831 const ControlFlowContext *CFCtx =
832 Env.getDataflowAnalysisContext().getControlFlowContext(F);
833 if (!CFCtx)
834 return;
835
836 // FIXME: We don't support context-sensitive analysis of recursion, so
837 // we should return early here if `F` is the same as the `FunctionDecl`
838 // holding `S` itself.
839
840 auto ExitBlock = CFCtx->getCFG().getExit().getBlockID();
841
842 auto CalleeEnv = Env.pushCall(S);
843
844 // FIXME: Use the same analysis as the caller for the callee. Note,
845 // though, that doing so would require support for changing the analysis's
846 // ASTContext.
847 assert(CFCtx->getDecl() != nullptr &&
848 "ControlFlowContexts in the environment should always carry a decl");
849 auto Analysis = NoopAnalysis(CFCtx->getDecl()->getASTContext(),
850 DataflowAnalysisOptions{Options});
851
852 auto BlockToOutputState =
854 assert(BlockToOutputState);
855 assert(ExitBlock < BlockToOutputState->size());
856
857 auto ExitState = (*BlockToOutputState)[ExitBlock];
858 assert(ExitState);
859
860 Env.popCall(S, ExitState->Env);
861 }
862
863 const StmtToEnvMap &StmtToEnv;
864 Environment &Env;
865};
866
867} // namespace
868
869void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env) {
870 TransferVisitor(StmtToEnv, Env).Visit(&S);
871}
872
873} // namespace dataflow
874} // namespace clang
#define V(N, I)
Definition: ASTContext.h:3230
MatchType Type
Defines enum values for all the target-independent builtin functions.
Defines the C++ Decl subclasses, other than those for templates (found in DeclTemplate....
Defines the clang::Expr interface and subclasses for C++ expressions.
const Environment & Env
Definition: HTMLLogger.cpp:170
Defines an enumeration for C++ overloaded operators.
const ControlFlowContext & CFCtx
Contains the CFG being analyzed.
TypeErasedDataflowAnalysis & Analysis
The analysis to be run.
ConstStmtVisitor - This class implements a simple visitor for Stmt subclasses.
Definition: StmtVisitor.h:194
This represents one expression.
Definition: Expr.h:110
bool isGLValue() const
Definition: Expr.h:274
Stmt - This represents one statement.
Definition: Stmt.h:72
Models a boolean.
Definition: Value.h:98
bool isBlockReachable(const CFGBlock &B) const
Returns whether B is reachable from the entry block.
const llvm::DenseMap< const Stmt *, const CFGBlock * > & getStmtToBlock() const
Returns a mapping from statements to basic blocks that contain them.
Holds the state of the program (store and heap) at a given program point.
BoolValue & makeAnd(BoolValue &LHS, BoolValue &RHS) const
Returns a boolean value that represents the conjunction of LHS and RHS.
BoolValue & makeIff(BoolValue &LHS, BoolValue &RHS) const
Returns a boolean value represents LHS <=> RHS.
BoolValue & makeAtomicBoolValue() const
Returns an atomic boolean value.
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...
void setValueStrict(const Expr &E, Value &Val)
Assigns Val as the value of the prvalue E in the environment.
StorageLocation * getStorageLocationStrict(const Expr &E) const
Returns the storage location assigned to the glvalue E in the environment, or null if E isn't assigne...
Value * getValueStrict(const Expr &E) const
Returns the Value assigned to the prvalue E in the environment, or null if E isn't assigned a value i...
void setValue(const StorageLocation &Loc, Value &Val)
Assigns Val as the value of Loc in the environment.
void setStorageLocationStrict(const Expr &E, StorageLocation &Loc)
Assigns Loc as the storage location of the glvalue E in the environment.
BoolValue & makeNot(BoolValue &Val) const
Returns a boolean value that represents the negation of Val.
BoolValue & makeOr(BoolValue &LHS, BoolValue &RHS) const
Returns a boolean value that represents the disjunction of LHS and RHS.
BoolValue & makeImplication(BoolValue &LHS, BoolValue &RHS) const
Returns a boolean value represents LHS => RHS.
Maps statements to the environments of basic blocks that contain them.
Definition: Transfer.h:26
const Environment * getEnvironment(const Stmt &S) const
Returns the environment of the basic block that contains S.
Definition: Transfer.cpp:39
Base class for all values computed by abstract interpretation.
Definition: Value.h:33
BoolValue & unpackBinaryBoolValue(Environment &Env, BoolValue &B, M build)
Definition: Transfer.cpp:65
static void propagateValueOrStorageLocation(const Expr &From, const Expr &To, Environment &Env)
Definition: Transfer.cpp:152
static void propagateStorageLocation(const Expr &From, const Expr &To, Environment &Env)
Definition: Transfer.cpp:143
AggregateStorageLocation * getBaseObjectLocation(const MemberExpr &ME, const Environment &Env)
Returns the storage location for the base object of a MemberExpr, or null if none is defined in the e...
llvm::Expected< std::vector< std::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...
static void propagateValue(const Expr &From, const Expr &To, Environment &Env)
Definition: Transfer.cpp:138
void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env)
Evaluates S and updates Env accordingly.
Definition: Transfer.cpp:869
static Value * maybeUnpackLValueExpr(const Expr &E, Environment &Env)
Definition: Transfer.cpp:121
static BoolValue & unpackValue(BoolValue &V, Environment &Env)
Definition: Transfer.cpp:78
static BoolValue & evaluateBooleanEquality(const Expr &LHS, const Expr &RHS, Environment &Env)
Definition: Transfer.cpp:49
@ Reference
An optional reference should be skipped past.
@ None
No indirections should be skipped past.
const Expr & ignoreCFGOmittedNodes(const Expr &E)
Skip past nodes that the CFG does not emit.
bool Ret(InterpState &S, CodePtr &PC, APValue &Result)
Definition: Interp.h:164