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