clang 18.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"
30#include "llvm/Support/Casting.h"
31#include "llvm/Support/Debug.h"
32#include <assert.h>
33#include <cassert>
34
35#define DEBUG_TYPE "dataflow"
36
37namespace clang {
38namespace dataflow {
39
41 auto BlockIt = CFCtx.getStmtToBlock().find(&ignoreCFGOmittedNodes(S));
42 assert(BlockIt != CFCtx.getStmtToBlock().end());
43 if (!CFCtx.isBlockReachable(*BlockIt->getSecond()))
44 return nullptr;
45 const auto &State = BlockToState[BlockIt->getSecond()->getBlockID()];
46 if (!(State))
47 return nullptr;
48 return &State->Env;
49}
50
51static BoolValue &evaluateBooleanEquality(const Expr &LHS, const Expr &RHS,
53 Value *LHSValue = Env.getValue(LHS);
54 Value *RHSValue = Env.getValue(RHS);
55
56 if (LHSValue == RHSValue)
57 return Env.getBoolLiteralValue(true);
58
59 if (auto *LHSBool = dyn_cast_or_null<BoolValue>(LHSValue))
60 if (auto *RHSBool = dyn_cast_or_null<BoolValue>(RHSValue))
61 return Env.makeIff(*LHSBool, *RHSBool);
62
63 return Env.makeAtomicBoolValue();
64}
65
67 if (auto *Top = llvm::dyn_cast<TopBoolValue>(&V)) {
69 return A.makeBoolValue(A.makeAtomRef(Top->getAtom()));
70 }
71 return V;
72}
73
74// Unpacks the value (if any) associated with `E` and updates `E` to the new
75// value, if any unpacking occured. Also, does the lvalue-to-rvalue conversion,
76// by skipping past the reference.
78 auto *Loc = Env.getStorageLocation(E);
79 if (Loc == nullptr)
80 return nullptr;
81 auto *Val = Env.getValue(*Loc);
82
83 auto *B = dyn_cast_or_null<BoolValue>(Val);
84 if (B == nullptr)
85 return Val;
86
87 auto &UnpackedVal = unpackValue(*B, Env);
88 if (&UnpackedVal == Val)
89 return Val;
90 Env.setValue(*Loc, UnpackedVal);
91 return &UnpackedVal;
92}
93
94static void propagateValue(const Expr &From, const Expr &To, Environment &Env) {
95 if (auto *Val = Env.getValue(From))
96 Env.setValue(To, *Val);
97}
98
99static void propagateStorageLocation(const Expr &From, const Expr &To,
100 Environment &Env) {
101 if (auto *Loc = Env.getStorageLocation(From))
102 Env.setStorageLocation(To, *Loc);
103}
104
105// Propagates the value or storage location of `From` to `To` in cases where
106// `From` may be either a glvalue or a prvalue. `To` must be a glvalue iff
107// `From` is a glvalue.
108static void propagateValueOrStorageLocation(const Expr &From, const Expr &To,
109 Environment &Env) {
110 assert(From.isGLValue() == To.isGLValue());
111 if (From.isGLValue())
112 propagateStorageLocation(From, To, Env);
113 else
114 propagateValue(From, To, Env);
115}
116
117namespace {
118
119class TransferVisitor : public ConstStmtVisitor<TransferVisitor> {
120public:
121 TransferVisitor(const StmtToEnvMap &StmtToEnv, Environment &Env)
122 : StmtToEnv(StmtToEnv), Env(Env) {}
123
124 void VisitBinaryOperator(const BinaryOperator *S) {
125 const Expr *LHS = S->getLHS();
126 assert(LHS != nullptr);
127
128 const Expr *RHS = S->getRHS();
129 assert(RHS != nullptr);
130
131 switch (S->getOpcode()) {
132 case BO_Assign: {
133 auto *LHSLoc = Env.getStorageLocation(*LHS);
134 if (LHSLoc == nullptr)
135 break;
136
137 auto *RHSVal = Env.getValue(*RHS);
138 if (RHSVal == nullptr)
139 break;
140
141 // Assign a value to the storage location of the left-hand side.
142 Env.setValue(*LHSLoc, *RHSVal);
143
144 // Assign a storage location for the whole expression.
145 Env.setStorageLocation(*S, *LHSLoc);
146 break;
147 }
148 case BO_LAnd:
149 case BO_LOr: {
150 BoolValue &LHSVal = getLogicOperatorSubExprValue(*LHS);
151 BoolValue &RHSVal = getLogicOperatorSubExprValue(*RHS);
152
153 if (S->getOpcode() == BO_LAnd)
154 Env.setValue(*S, Env.makeAnd(LHSVal, RHSVal));
155 else
156 Env.setValue(*S, Env.makeOr(LHSVal, RHSVal));
157 break;
158 }
159 case BO_NE:
160 case BO_EQ: {
161 auto &LHSEqRHSValue = evaluateBooleanEquality(*LHS, *RHS, Env);
162 Env.setValue(*S, S->getOpcode() == BO_EQ ? LHSEqRHSValue
163 : Env.makeNot(LHSEqRHSValue));
164 break;
165 }
166 case BO_Comma: {
167 propagateValueOrStorageLocation(*RHS, *S, Env);
168 break;
169 }
170 default:
171 break;
172 }
173 }
174
175 void VisitDeclRefExpr(const DeclRefExpr *S) {
176 const ValueDecl *VD = S->getDecl();
177 assert(VD != nullptr);
178
179 // Some `DeclRefExpr`s aren't glvalues, so we can't associate them with a
180 // `StorageLocation`, and there's also no sensible `Value` that we can
181 // assign to them. Examples:
182 // - Non-static member variables
183 // - Non static member functions
184 // Note: Member operators are an exception to this, but apparently only
185 // if the `DeclRefExpr` is used within the callee of a
186 // `CXXOperatorCallExpr`. In other cases, for example when applying the
187 // address-of operator, the `DeclRefExpr` is a prvalue.
188 if (!S->isGLValue())
189 return;
190
191 auto *DeclLoc = Env.getStorageLocation(*VD);
192 if (DeclLoc == nullptr)
193 return;
194
195 Env.setStorageLocation(*S, *DeclLoc);
196 }
197
198 void VisitDeclStmt(const DeclStmt *S) {
199 // Group decls are converted into single decls in the CFG so the cast below
200 // is safe.
201 const auto &D = *cast<VarDecl>(S->getSingleDecl());
202
203 ProcessVarDecl(D);
204 }
205
206 void ProcessVarDecl(const VarDecl &D) {
207 // Static local vars are already initialized in `Environment`.
208 if (D.hasGlobalStorage())
209 return;
210
211 // If this is the holding variable for a `BindingDecl`, we may already
212 // have a storage location set up -- so check. (See also explanation below
213 // where we process the `BindingDecl`.)
214 if (D.getType()->isReferenceType() && Env.getStorageLocation(D) != nullptr)
215 return;
216
217 assert(Env.getStorageLocation(D) == nullptr);
218
219 Env.setStorageLocation(D, Env.createObject(D));
220
221 // `DecompositionDecl` must be handled after we've interpreted the loc
222 // itself, because the binding expression refers back to the
223 // `DecompositionDecl` (even though it has no written name).
224 if (const auto *Decomp = dyn_cast<DecompositionDecl>(&D)) {
225 // If VarDecl is a DecompositionDecl, evaluate each of its bindings. This
226 // needs to be evaluated after initializing the values in the storage for
227 // VarDecl, as the bindings refer to them.
228 // FIXME: Add support for ArraySubscriptExpr.
229 // FIXME: Consider adding AST nodes used in BindingDecls to the CFG.
230 for (const auto *B : Decomp->bindings()) {
231 if (auto *ME = dyn_cast_or_null<MemberExpr>(B->getBinding())) {
232 auto *DE = dyn_cast_or_null<DeclRefExpr>(ME->getBase());
233 if (DE == nullptr)
234 continue;
235
236 // ME and its base haven't been visited because they aren't included
237 // in the statements of the CFG basic block.
238 VisitDeclRefExpr(DE);
239 VisitMemberExpr(ME);
240
241 if (auto *Loc = Env.getStorageLocation(*ME))
242 Env.setStorageLocation(*B, *Loc);
243 } else if (auto *VD = B->getHoldingVar()) {
244 // Holding vars are used to back the `BindingDecl`s of tuple-like
245 // types. The holding var declarations appear after the
246 // `DecompositionDecl`, so we have to explicitly process them here
247 // to know their storage location. They will be processed a second
248 // time when we visit their `VarDecl`s, so we have code that protects
249 // against this above.
250 ProcessVarDecl(*VD);
251 auto *VDLoc = Env.getStorageLocation(*VD);
252 assert(VDLoc != nullptr);
253 Env.setStorageLocation(*B, *VDLoc);
254 }
255 }
256 }
257 }
258
259 void VisitImplicitCastExpr(const ImplicitCastExpr *S) {
260 const Expr *SubExpr = S->getSubExpr();
261 assert(SubExpr != nullptr);
262
263 switch (S->getCastKind()) {
264 case CK_IntegralToBoolean: {
265 // This cast creates a new, boolean value from the integral value. We
266 // model that with a fresh value in the environment, unless it's already a
267 // boolean.
268 if (auto *SubExprVal =
269 dyn_cast_or_null<BoolValue>(Env.getValue(*SubExpr)))
270 Env.setValue(*S, *SubExprVal);
271 else
272 // FIXME: If integer modeling is added, then update this code to create
273 // the boolean based on the integer model.
274 Env.setValue(*S, Env.makeAtomicBoolValue());
275 break;
276 }
277
278 case CK_LValueToRValue: {
279 // When an L-value is used as an R-value, it may result in sharing, so we
280 // need to unpack any nested `Top`s.
281 auto *SubExprVal = maybeUnpackLValueExpr(*SubExpr, Env);
282 if (SubExprVal == nullptr)
283 break;
284
285 Env.setValue(*S, *SubExprVal);
286 break;
287 }
288
289 case CK_IntegralCast:
290 // FIXME: This cast creates a new integral value from the
291 // subexpression. But, because we don't model integers, we don't
292 // distinguish between this new value and the underlying one. If integer
293 // modeling is added, then update this code to create a fresh location and
294 // value.
295 case CK_UncheckedDerivedToBase:
296 case CK_ConstructorConversion:
297 case CK_UserDefinedConversion:
298 // FIXME: Add tests that excercise CK_UncheckedDerivedToBase,
299 // CK_ConstructorConversion, and CK_UserDefinedConversion.
300 case CK_NoOp: {
301 // FIXME: Consider making `Environment::getStorageLocation` skip noop
302 // expressions (this and other similar expressions in the file) instead
303 // of assigning them storage locations.
304 propagateValueOrStorageLocation(*SubExpr, *S, Env);
305 break;
306 }
307 case CK_NullToPointer: {
308 auto &NullPointerVal =
309 Env.getOrCreateNullPointerValue(S->getType()->getPointeeType());
310 Env.setValue(*S, NullPointerVal);
311 break;
312 }
313 case CK_NullToMemberPointer:
314 // FIXME: Implement pointers to members. For now, don't associate a value
315 // with this expression.
316 break;
317 case CK_FunctionToPointerDecay: {
318 StorageLocation *PointeeLoc = Env.getStorageLocation(*SubExpr);
319 if (PointeeLoc == nullptr)
320 break;
321
322 Env.setValue(*S, Env.create<PointerValue>(*PointeeLoc));
323 break;
324 }
325 case CK_BuiltinFnToFnPtr:
326 // Despite its name, the result type of `BuiltinFnToFnPtr` is a function,
327 // not a function pointer. In addition, builtin functions can only be
328 // called directly; it is not legal to take their address. We therefore
329 // don't need to create a value or storage location for them.
330 break;
331 default:
332 break;
333 }
334 }
335
336 void VisitUnaryOperator(const UnaryOperator *S) {
337 const Expr *SubExpr = S->getSubExpr();
338 assert(SubExpr != nullptr);
339
340 switch (S->getOpcode()) {
341 case UO_Deref: {
342 const auto *SubExprVal =
343 cast_or_null<PointerValue>(Env.getValue(*SubExpr));
344 if (SubExprVal == nullptr)
345 break;
346
347 Env.setStorageLocation(*S, SubExprVal->getPointeeLoc());
348 break;
349 }
350 case UO_AddrOf: {
351 // FIXME: Model pointers to members.
352 if (S->getType()->isMemberPointerType())
353 break;
354
355 if (StorageLocation *PointeeLoc = Env.getStorageLocation(*SubExpr))
356 Env.setValue(*S, Env.create<PointerValue>(*PointeeLoc));
357 break;
358 }
359 case UO_LNot: {
360 auto *SubExprVal = dyn_cast_or_null<BoolValue>(Env.getValue(*SubExpr));
361 if (SubExprVal == nullptr)
362 break;
363
364 Env.setValue(*S, Env.makeNot(*SubExprVal));
365 break;
366 }
367 default:
368 break;
369 }
370 }
371
372 void VisitCXXThisExpr(const CXXThisExpr *S) {
373 auto *ThisPointeeLoc = Env.getThisPointeeStorageLocation();
374 if (ThisPointeeLoc == nullptr)
375 // Unions are not supported yet, and will not have a location for the
376 // `this` expression's pointee.
377 return;
378
379 Env.setValue(*S, Env.create<PointerValue>(*ThisPointeeLoc));
380 }
381
382 void VisitCXXNewExpr(const CXXNewExpr *S) {
383 if (Value *Val = Env.createValue(S->getType()))
384 Env.setValue(*S, *Val);
385 }
386
387 void VisitCXXDeleteExpr(const CXXDeleteExpr *S) {
388 // Empty method.
389 // We consciously don't do anything on deletes. Diagnosing double deletes
390 // (for example) should be done by a specific analysis, not by the
391 // framework.
392 }
393
394 void VisitReturnStmt(const ReturnStmt *S) {
395 if (!Env.getDataflowAnalysisContext().getOptions().ContextSensitiveOpts)
396 return;
397
398 auto *Ret = S->getRetValue();
399 if (Ret == nullptr)
400 return;
401
402 if (Ret->isPRValue()) {
403 auto *Val = Env.getValue(*Ret);
404 if (Val == nullptr)
405 return;
406
407 // FIXME: Model NRVO.
408 Env.setReturnValue(Val);
409 } else {
410 auto *Loc = Env.getStorageLocation(*Ret);
411 if (Loc == nullptr)
412 return;
413
414 // FIXME: Model NRVO.
415 Env.setReturnStorageLocation(Loc);
416 }
417 }
418
419 void VisitMemberExpr(const MemberExpr *S) {
420 ValueDecl *Member = S->getMemberDecl();
421 assert(Member != nullptr);
422
423 // FIXME: Consider assigning pointer values to function member expressions.
424 if (Member->isFunctionOrFunctionTemplate())
425 return;
426
427 // FIXME: if/when we add support for modeling enums, use that support here.
428 if (isa<EnumConstantDecl>(Member))
429 return;
430
431 if (auto *D = dyn_cast<VarDecl>(Member)) {
432 if (D->hasGlobalStorage()) {
433 auto *VarDeclLoc = Env.getStorageLocation(*D);
434 if (VarDeclLoc == nullptr)
435 return;
436
437 Env.setStorageLocation(*S, *VarDeclLoc);
438 return;
439 }
440 }
441
442 RecordStorageLocation *BaseLoc = getBaseObjectLocation(*S, Env);
443 if (BaseLoc == nullptr)
444 return;
445
446 auto *MemberLoc = BaseLoc->getChild(*Member);
447 if (MemberLoc == nullptr)
448 return;
449 Env.setStorageLocation(*S, *MemberLoc);
450 }
451
452 void VisitCXXDefaultInitExpr(const CXXDefaultInitExpr *S) {
453 const Expr *InitExpr = S->getExpr();
454 assert(InitExpr != nullptr);
455 propagateValueOrStorageLocation(*InitExpr, *S, Env);
456 }
457
458 void VisitCXXConstructExpr(const CXXConstructExpr *S) {
459 const CXXConstructorDecl *ConstructorDecl = S->getConstructor();
460 assert(ConstructorDecl != nullptr);
461
462 if (ConstructorDecl->isCopyOrMoveConstructor()) {
463 // It is permissible for a copy/move constructor to have additional
464 // parameters as long as they have default arguments defined for them.
465 assert(S->getNumArgs() != 0);
466
467 const Expr *Arg = S->getArg(0);
468 assert(Arg != nullptr);
469
470 auto *ArgLoc =
471 cast_or_null<RecordStorageLocation>(Env.getStorageLocation(*Arg));
472 if (ArgLoc == nullptr)
473 return;
474
475 if (S->isElidable()) {
476 if (Value *Val = Env.getValue(*ArgLoc))
477 Env.setValue(*S, *Val);
478 } else {
479 auto &Val = *cast<RecordValue>(Env.createValue(S->getType()));
480 Env.setValue(*S, Val);
481 copyRecord(*ArgLoc, Val.getLoc(), Env);
482 }
483 return;
484 }
485
486 // `CXXConstructExpr` can have array type if default-initializing an array
487 // of records, and we currently can't create values for arrays. So check if
488 // we've got a record type.
489 if (S->getType()->isRecordType()) {
490 auto &InitialVal = *cast<RecordValue>(Env.createValue(S->getType()));
491 Env.setValue(*S, InitialVal);
492 copyRecord(InitialVal.getLoc(), Env.getResultObjectLocation(*S), Env);
493 }
494
495 transferInlineCall(S, ConstructorDecl);
496 }
497
498 void VisitCXXOperatorCallExpr(const CXXOperatorCallExpr *S) {
499 if (S->getOperator() == OO_Equal) {
500 assert(S->getNumArgs() == 2);
501
502 const Expr *Arg0 = S->getArg(0);
503 assert(Arg0 != nullptr);
504
505 const Expr *Arg1 = S->getArg(1);
506 assert(Arg1 != nullptr);
507
508 // Evaluate only copy and move assignment operators.
509 const auto *Method =
510 dyn_cast_or_null<CXXMethodDecl>(S->getDirectCallee());
511 if (!Method)
512 return;
513 if (!Method->isCopyAssignmentOperator() &&
514 !Method->isMoveAssignmentOperator())
515 return;
516
517 RecordStorageLocation *LocSrc = nullptr;
518 if (Arg1->isPRValue()) {
519 if (auto *Val = cast_or_null<RecordValue>(Env.getValue(*Arg1)))
520 LocSrc = &Val->getLoc();
521 } else {
522 LocSrc =
523 cast_or_null<RecordStorageLocation>(Env.getStorageLocation(*Arg1));
524 }
525 auto *LocDst =
526 cast_or_null<RecordStorageLocation>(Env.getStorageLocation(*Arg0));
527
528 if (LocSrc == nullptr || LocDst == nullptr)
529 return;
530
531 // The assignment operators are different from the type of the destination
532 // in this model (i.e. in one of their base classes). This must be very
533 // rare and we just bail.
534 if (Method->getFunctionObjectParameterType()
535 .getCanonicalType()
536 .getUnqualifiedType() !=
537 LocDst->getType().getCanonicalType().getUnqualifiedType())
538 return;
539
540 copyRecord(*LocSrc, *LocDst, Env);
541 Env.setStorageLocation(*S, *LocDst);
542 }
543 }
544
545 void VisitCXXFunctionalCastExpr(const CXXFunctionalCastExpr *S) {
546 if (S->getCastKind() == CK_ConstructorConversion) {
547 const Expr *SubExpr = S->getSubExpr();
548 assert(SubExpr != nullptr);
549
550 propagateValue(*SubExpr, *S, Env);
551 }
552 }
553
554 void VisitCXXTemporaryObjectExpr(const CXXTemporaryObjectExpr *S) {
555 if (Value *Val = Env.createValue(S->getType()))
556 Env.setValue(*S, *Val);
557 }
558
559 void VisitCallExpr(const CallExpr *S) {
560 // Of clang's builtins, only `__builtin_expect` is handled explicitly, since
561 // others (like trap, debugtrap, and unreachable) are handled by CFG
562 // construction.
563 if (S->isCallToStdMove()) {
564 assert(S->getNumArgs() == 1);
565
566 const Expr *Arg = S->getArg(0);
567 assert(Arg != nullptr);
568
569 auto *ArgLoc = Env.getStorageLocation(*Arg);
570 if (ArgLoc == nullptr)
571 return;
572
573 Env.setStorageLocation(*S, *ArgLoc);
574 } else if (S->getDirectCallee() != nullptr &&
575 S->getDirectCallee()->getBuiltinID() ==
576 Builtin::BI__builtin_expect) {
577 assert(S->getNumArgs() > 0);
578 assert(S->getArg(0) != nullptr);
579 auto *ArgVal = Env.getValue(*S->getArg(0));
580 if (ArgVal == nullptr)
581 return;
582 Env.setValue(*S, *ArgVal);
583 } else if (const FunctionDecl *F = S->getDirectCallee()) {
584 transferInlineCall(S, F);
585 }
586 }
587
588 void VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *S) {
589 const Expr *SubExpr = S->getSubExpr();
590 assert(SubExpr != nullptr);
591
592 Value *SubExprVal = Env.getValue(*SubExpr);
593 if (SubExprVal == nullptr)
594 return;
595
596 if (RecordValue *RecordVal = dyn_cast<RecordValue>(SubExprVal)) {
597 Env.setStorageLocation(*S, RecordVal->getLoc());
598 return;
599 }
600
601 StorageLocation &Loc = Env.createStorageLocation(*S);
602 Env.setValue(Loc, *SubExprVal);
603 Env.setStorageLocation(*S, Loc);
604 }
605
606 void VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr *S) {
607 const Expr *SubExpr = S->getSubExpr();
608 assert(SubExpr != nullptr);
609
610 propagateValue(*SubExpr, *S, Env);
611 }
612
613 void VisitCXXStaticCastExpr(const CXXStaticCastExpr *S) {
614 if (S->getCastKind() == CK_NoOp) {
615 const Expr *SubExpr = S->getSubExpr();
616 assert(SubExpr != nullptr);
617
618 propagateValueOrStorageLocation(*SubExpr, *S, Env);
619 }
620 }
621
622 void VisitConditionalOperator(const ConditionalOperator *S) {
623 // FIXME: Revisit this once flow conditions are added to the framework. For
624 // `a = b ? c : d` we can add `b => a == c && !b => a == d` to the flow
625 // condition.
626 // When we do this, we will need to retrieve the values of the operands from
627 // the environments for the basic blocks they are computed in, in a similar
628 // way to how this is done for short-circuited logical operators in
629 // `getLogicOperatorSubExprValue()`.
630 if (S->isGLValue())
631 Env.setStorageLocation(*S, Env.createObject(S->getType()));
632 else if (Value *Val = Env.createValue(S->getType()))
633 Env.setValue(*S, *Val);
634 }
635
636 void VisitInitListExpr(const InitListExpr *S) {
637 QualType Type = S->getType();
638
639 if (!Type->isStructureOrClassType()) {
640 if (auto *Val = Env.createValue(Type))
641 Env.setValue(*S, *Val);
642
643 return;
644 }
645
646 // In case the initializer list is transparent, we just need to propagate
647 // the value that it contains.
648 if (S->isSemanticForm() && S->isTransparent()) {
649 propagateValue(*S->getInit(0), *S, Env);
650 return;
651 }
652
653 llvm::DenseMap<const ValueDecl *, StorageLocation *> FieldLocs;
654
655 // This only contains the direct fields for the given type.
656 std::vector<FieldDecl *> FieldsForInit =
657 getFieldsForInitListExpr(Type->getAsRecordDecl());
658
659 // `S->inits()` contains all the initializer epressions, including the
660 // ones for direct base classes.
661 auto Inits = S->inits();
662 size_t InitIdx = 0;
663
664 // Initialize base classes.
665 if (auto* R = S->getType()->getAsCXXRecordDecl()) {
666 assert(FieldsForInit.size() + R->getNumBases() == Inits.size());
667 for ([[maybe_unused]] const CXXBaseSpecifier &Base : R->bases()) {
668 assert(InitIdx < Inits.size());
669 auto Init = Inits[InitIdx++];
670 assert(Base.getType().getCanonicalType() ==
671 Init->getType().getCanonicalType());
672 auto* BaseVal = cast_or_null<RecordValue>(Env.getValue(*Init));
673 if (!BaseVal)
674 BaseVal = cast<RecordValue>(Env.createValue(Init->getType()));
675 // Take ownership of the fields of the `RecordValue` for the base class
676 // and incorporate them into the "flattened" set of fields for the
677 // derived class.
678 auto Children = BaseVal->getLoc().children();
679 FieldLocs.insert(Children.begin(), Children.end());
680 }
681 }
682
683 assert(FieldsForInit.size() == Inits.size() - InitIdx);
684 for (auto Field : FieldsForInit) {
685 assert(InitIdx < Inits.size());
686 auto Init = Inits[InitIdx++];
687 assert(
688 // The types are same, or
689 Field->getType().getCanonicalType().getUnqualifiedType() ==
690 Init->getType().getCanonicalType().getUnqualifiedType() ||
691 // The field's type is T&, and initializer is T
692 (Field->getType()->isReferenceType() &&
693 Field->getType().getCanonicalType()->getPointeeType() ==
694 Init->getType().getCanonicalType()));
695 auto& Loc = Env.createObject(Field->getType(), Init);
696 FieldLocs.insert({Field, &Loc});
697 }
698
699 // Check that we satisfy the invariant that a `RecordStorageLoation`
700 // contains exactly the set of modeled fields for that type.
701 // `ModeledFields` includes fields from all the bases, but only the
702 // modeled ones. However, if a class type is initialized with an
703 // `InitListExpr`, all fields in the class, including those from base
704 // classes, are included in the set of modeled fields. The code above
705 // should therefore populate exactly the modeled fields.
706 assert([&]() {
707 auto ModeledFields =
708 Env.getDataflowAnalysisContext().getModeledFields(Type);
709 if (ModeledFields.size() != FieldLocs.size())
710 return false;
711 for ([[maybe_unused]] auto [Field, Loc] : FieldLocs)
712 if (!ModeledFields.contains(cast_or_null<FieldDecl>(Field)))
713 return false;
714 return true;
715 }());
716
717 auto &Loc =
718 Env.getDataflowAnalysisContext().arena().create<RecordStorageLocation>(
719 Type, std::move(FieldLocs));
720 RecordValue &RecordVal = Env.create<RecordValue>(Loc);
721
722 Env.setValue(Loc, RecordVal);
723
724 Env.setValue(*S, RecordVal);
725
726 // FIXME: Implement array initialization.
727 }
728
729 void VisitCXXBoolLiteralExpr(const CXXBoolLiteralExpr *S) {
730 Env.setValue(*S, Env.getBoolLiteralValue(S->getValue()));
731 }
732
733 void VisitIntegerLiteral(const IntegerLiteral *S) {
734 Env.setValue(*S, Env.getIntLiteralValue(S->getValue()));
735 }
736
737 void VisitParenExpr(const ParenExpr *S) {
738 // The CFG does not contain `ParenExpr` as top-level statements in basic
739 // blocks, however manual traversal to sub-expressions may encounter them.
740 // Redirect to the sub-expression.
741 auto *SubExpr = S->getSubExpr();
742 assert(SubExpr != nullptr);
743 Visit(SubExpr);
744 }
745
746 void VisitExprWithCleanups(const ExprWithCleanups *S) {
747 // The CFG does not contain `ExprWithCleanups` as top-level statements in
748 // basic blocks, however manual traversal to sub-expressions may encounter
749 // them. Redirect to the sub-expression.
750 auto *SubExpr = S->getSubExpr();
751 assert(SubExpr != nullptr);
752 Visit(SubExpr);
753 }
754
755private:
756 /// Returns the value for the sub-expression `SubExpr` of a logic operator.
757 BoolValue &getLogicOperatorSubExprValue(const Expr &SubExpr) {
758 // `SubExpr` and its parent logic operator might be part of different basic
759 // blocks. We try to access the value that is assigned to `SubExpr` in the
760 // corresponding environment.
761 if (const Environment *SubExprEnv = StmtToEnv.getEnvironment(SubExpr))
762 if (auto *Val =
763 dyn_cast_or_null<BoolValue>(SubExprEnv->getValue(SubExpr)))
764 return *Val;
765
766 // The sub-expression may lie within a basic block that isn't reachable,
767 // even if we need it to evaluate the current (reachable) expression
768 // (see https://discourse.llvm.org/t/70775). In this case, visit `SubExpr`
769 // within the current environment and then try to get the value that gets
770 // assigned to it.
771 if (Env.getValue(SubExpr) == nullptr)
772 Visit(&SubExpr);
773 if (auto *Val = dyn_cast_or_null<BoolValue>(Env.getValue(SubExpr)))
774 return *Val;
775
776 // If the value of `SubExpr` is still unknown, we create a fresh symbolic
777 // boolean value for it.
778 return Env.makeAtomicBoolValue();
779 }
780
781 // If context sensitivity is enabled, try to analyze the body of the callee
782 // `F` of `S`. The type `E` must be either `CallExpr` or `CXXConstructExpr`.
783 template <typename E>
784 void transferInlineCall(const E *S, const FunctionDecl *F) {
785 const auto &Options = Env.getDataflowAnalysisContext().getOptions();
786 if (!(Options.ContextSensitiveOpts &&
787 Env.canDescend(Options.ContextSensitiveOpts->Depth, F)))
788 return;
789
790 const ControlFlowContext *CFCtx =
791 Env.getDataflowAnalysisContext().getControlFlowContext(F);
792 if (!CFCtx)
793 return;
794
795 // FIXME: We don't support context-sensitive analysis of recursion, so
796 // we should return early here if `F` is the same as the `FunctionDecl`
797 // holding `S` itself.
798
799 auto ExitBlock = CFCtx->getCFG().getExit().getBlockID();
800
801 auto CalleeEnv = Env.pushCall(S);
802
803 // FIXME: Use the same analysis as the caller for the callee. Note,
804 // though, that doing so would require support for changing the analysis's
805 // ASTContext.
806 auto Analysis = NoopAnalysis(CFCtx->getDecl().getASTContext(),
807 DataflowAnalysisOptions{Options});
808
809 auto BlockToOutputState =
811 assert(BlockToOutputState);
812 assert(ExitBlock < BlockToOutputState->size());
813
814 auto &ExitState = (*BlockToOutputState)[ExitBlock];
815 assert(ExitState);
816
817 Env.popCall(S, ExitState->Env);
818 }
819
820 const StmtToEnvMap &StmtToEnv;
821 Environment &Env;
822};
823
824} // namespace
825
826void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env) {
827 TransferVisitor(StmtToEnv, Env).Visit(&S);
828}
829
830} // namespace dataflow
831} // namespace clang
#define V(N, I)
Definition: ASTContext.h:3241
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:144
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:84
BoolValue & makeBoolValue(const Formula &)
Creates a BoolValue wrapping a particular formula.
Definition: Arena.cpp:112
Models a boolean.
Definition: Value.h:92
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 & makeIff(BoolValue &LHS, BoolValue &RHS) const
Returns a boolean value represents LHS <=> RHS.
StorageLocation * getStorageLocation(const ValueDecl &D) const
Returns the storage location assigned to D in the environment, or null if D isn't assigned a storage ...
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...
BoolValue & getBoolLiteralValue(bool Value) const
Returns a symbolic boolean value that models a boolean literal equal to Value
DataflowAnalysisContext & getDataflowAnalysisContext() const
Returns the DataflowAnalysisContext used by the environment.
void setStorageLocation(const ValueDecl &D, StorageLocation &Loc)
Assigns Loc as the storage location of D in the environment.
void setValue(const StorageLocation &Loc, Value &Val)
Assigns Val as the value of Loc in the environment.
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:40
Base class for all values computed by abstract interpretation.
Definition: Value.h:33
static void propagateValueOrStorageLocation(const Expr &From, const Expr &To, Environment &Env)
Definition: Transfer.cpp:108
static void propagateStorageLocation(const Expr &From, const Expr &To, Environment &Env)
Definition: Transfer.cpp:99
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:94
void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env)
Evaluates S and updates Env accordingly.
Definition: Transfer.cpp:826
static Value * maybeUnpackLValueExpr(const Expr &E, Environment &Env)
Definition: Transfer.cpp:77
void copyRecord(RecordStorageLocation &Src, RecordStorageLocation &Dst, Environment &Env)
Copies a record (struct, class, or union) from Src to Dst.
Definition: RecordOps.cpp:17
static BoolValue & unpackValue(BoolValue &V, Environment &Env)
Definition: Transfer.cpp:66
static BoolValue & evaluateBooleanEquality(const Expr &LHS, const Expr &RHS, Environment &Env)
Definition: Transfer.cpp:51
const Expr & ignoreCFGOmittedNodes(const Expr &E)
Skip past nodes that the CFG does not emit.
std::vector< FieldDecl * > getFieldsForInitListExpr(const RecordDecl *RD)
Returns the fields of RD that are initialized by an InitListExpr, in the order in which they appear i...
RecordStorageLocation * 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...
bool Ret(InterpState &S, CodePtr &PC, APValue &Result)
Definition: Interp.h:210
for(unsigned I=0, E=TL.getNumArgs();I !=E;++I)