clang/lib/Analysis/FlowSensitive/Transfer.cpp

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