| 1 |
//=- LiveVariables.cpp - Live Variable Analysis for Source CFGs ----------*-==// |
| 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 implements Live Variables analysis for source-level CFGs. |
| 10 |
// |
| 11 |
//===----------------------------------------------------------------------===// |
| 12 |
|
| 13 |
#include "clang/Analysis/Analyses/LiveVariables.h" |
| 14 |
#include "clang/AST/Stmt.h" |
| 15 |
#include "clang/AST/StmtVisitor.h" |
| 16 |
#include "clang/Analysis/AnalysisDeclContext.h" |
| 17 |
#include "clang/Analysis/CFG.h" |
| 18 |
#include "clang/Analysis/FlowSensitive/DataflowWorklist.h" |
| 19 |
#include "llvm/ADT/DenseMap.h" |
| 20 |
#include "llvm/Support/raw_ostream.h" |
| 21 |
#include <algorithm> |
| 22 |
#include <optional> |
| 23 |
#include <vector> |
| 24 |
|
| 25 |
using namespace clang; |
| 26 |
|
| 27 |
namespace { |
| 28 |
class LiveVariablesImpl { |
| 29 |
public: |
| 30 |
AnalysisDeclContext &analysisContext; |
| 31 |
llvm::ImmutableSet<const Expr *>::Factory ESetFact; |
| 32 |
llvm::ImmutableSet<const VarDecl *>::Factory DSetFact; |
| 33 |
llvm::ImmutableSet<const BindingDecl *>::Factory BSetFact; |
| 34 |
llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksEndToLiveness; |
| 35 |
llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksBeginToLiveness; |
| 36 |
llvm::DenseMap<const Stmt *, LiveVariables::LivenessValues> stmtsToLiveness; |
| 37 |
llvm::DenseMap<const DeclRefExpr *, unsigned> inAssignment; |
| 38 |
const bool killAtAssign; |
| 39 |
|
| 40 |
LiveVariables::LivenessValues |
| 41 |
merge(LiveVariables::LivenessValues valsA, |
| 42 |
LiveVariables::LivenessValues valsB); |
| 43 |
|
| 44 |
LiveVariables::LivenessValues |
| 45 |
runOnBlock(const CFGBlock *block, LiveVariables::LivenessValues val, |
| 46 |
LiveVariables::Observer *obs = nullptr); |
| 47 |
|
| 48 |
void dumpBlockLiveness(const SourceManager& M); |
| 49 |
void dumpExprLiveness(const SourceManager& M); |
| 50 |
|
| 51 |
LiveVariablesImpl(AnalysisDeclContext &ac, bool KillAtAssign) |
| 52 |
: analysisContext(ac), |
| 53 |
ESetFact(false), // Do not canonicalize ImmutableSets by default. |
| 54 |
DSetFact(false), // This is a *major* performance win. |
| 55 |
BSetFact(false), killAtAssign(KillAtAssign) {} |
| 56 |
}; |
| 57 |
} // namespace |
| 58 |
|
| 59 |
static LiveVariablesImpl &getImpl(void *x) { |
| 60 |
return *((LiveVariablesImpl *) x); |
| 61 |
} |
| 62 |
|
| 63 |
//===----------------------------------------------------------------------===// |
| 64 |
// Operations and queries on LivenessValues. |
| 65 |
//===----------------------------------------------------------------------===// |
| 66 |
|
| 67 |
bool LiveVariables::LivenessValues::isLive(const Expr *E) const { |
| 68 |
return liveExprs.contains(E); |
| 69 |
} |
| 70 |
|
| 71 |
bool LiveVariables::LivenessValues::isLive(const VarDecl *D) const { |
| 72 |
if (const auto *DD = dyn_cast<DecompositionDecl>(D)) { |
| 73 |
bool alive = false; |
| 74 |
for (const BindingDecl *BD : DD->bindings()) |
| 75 |
alive |= liveBindings.contains(BD); |
| 76 |
|
| 77 |
// Note: the only known case this condition is necessary, is when a bindig |
| 78 |
// to a tuple-like structure is created. The HoldingVar initializers have a |
| 79 |
// DeclRefExpr to the DecompositionDecl. |
| 80 |
alive |= liveDecls.contains(DD); |
| 81 |
return alive; |
| 82 |
} |
| 83 |
return liveDecls.contains(D); |
| 84 |
} |
| 85 |
|
| 86 |
namespace { |
| 87 |
template <typename SET> |
| 88 |
SET mergeSets(SET A, SET B) { |
| 89 |
if (A.isEmpty()) |
| 90 |
return B; |
| 91 |
|
| 92 |
for (typename SET::iterator it = B.begin(), ei = B.end(); it != ei; ++it) { |
| 93 |
A = A.add(*it); |
| 94 |
} |
| 95 |
return A; |
| 96 |
} |
| 97 |
} // namespace |
| 98 |
|
| 99 |
void LiveVariables::Observer::anchor() { } |
| 100 |
|
| 101 |
LiveVariables::LivenessValues |
| 102 |
LiveVariablesImpl::merge(LiveVariables::LivenessValues valsA, |
| 103 |
LiveVariables::LivenessValues valsB) { |
| 104 |
|
| 105 |
llvm::ImmutableSetRef<const Expr *> SSetRefA( |
| 106 |
valsA.liveExprs.getRootWithoutRetain(), ESetFact.getTreeFactory()), |
| 107 |
SSetRefB(valsB.liveExprs.getRootWithoutRetain(), |
| 108 |
ESetFact.getTreeFactory()); |
| 109 |
|
| 110 |
llvm::ImmutableSetRef<const VarDecl *> |
| 111 |
DSetRefA(valsA.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()), |
| 112 |
DSetRefB(valsB.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()); |
| 113 |
|
| 114 |
llvm::ImmutableSetRef<const BindingDecl *> |
| 115 |
BSetRefA(valsA.liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory()), |
| 116 |
BSetRefB(valsB.liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory()); |
| 117 |
|
| 118 |
SSetRefA = mergeSets(SSetRefA, SSetRefB); |
| 119 |
DSetRefA = mergeSets(DSetRefA, DSetRefB); |
| 120 |
BSetRefA = mergeSets(BSetRefA, BSetRefB); |
| 121 |
|
| 122 |
// asImmutableSet() canonicalizes the tree, allowing us to do an easy |
| 123 |
// comparison afterwards. |
| 124 |
return LiveVariables::LivenessValues(SSetRefA.asImmutableSet(), |
| 125 |
DSetRefA.asImmutableSet(), |
| 126 |
BSetRefA.asImmutableSet()); |
| 127 |
} |
| 128 |
|
| 129 |
bool LiveVariables::LivenessValues::equals(const LivenessValues &V) const { |
| 130 |
return liveExprs == V.liveExprs && liveDecls == V.liveDecls; |
| 131 |
} |
| 132 |
|
| 133 |
//===----------------------------------------------------------------------===// |
| 134 |
// Query methods. |
| 135 |
//===----------------------------------------------------------------------===// |
| 136 |
|
| 137 |
static bool isAlwaysAlive(const VarDecl *D) { |
| 138 |
return D->hasGlobalStorage(); |
| 139 |
} |
| 140 |
|
| 141 |
bool LiveVariables::isLive(const CFGBlock *B, const VarDecl *D) { |
| 142 |
return isAlwaysAlive(D) || getImpl(impl).blocksEndToLiveness[B].isLive(D); |
| 143 |
} |
| 144 |
|
| 145 |
bool LiveVariables::isLive(const Stmt *S, const VarDecl *D) { |
| 146 |
return isAlwaysAlive(D) || getImpl(impl).stmtsToLiveness[S].isLive(D); |
| 147 |
} |
| 148 |
|
| 149 |
bool LiveVariables::isLive(const Stmt *Loc, const Expr *Val) { |
| 150 |
return getImpl(impl).stmtsToLiveness[Loc].isLive(Val); |
| 151 |
} |
| 152 |
|
| 153 |
//===----------------------------------------------------------------------===// |
| 154 |
// Dataflow computation. |
| 155 |
//===----------------------------------------------------------------------===// |
| 156 |
|
| 157 |
namespace { |
| 158 |
class TransferFunctions : public StmtVisitor<TransferFunctions> { |
| 159 |
LiveVariablesImpl &LV; |
| 160 |
LiveVariables::LivenessValues &val; |
| 161 |
LiveVariables::Observer *observer; |
| 162 |
const CFGBlock *currentBlock; |
| 163 |
public: |
| 164 |
TransferFunctions(LiveVariablesImpl &im, |
| 165 |
LiveVariables::LivenessValues &Val, |
| 166 |
LiveVariables::Observer *Observer, |
| 167 |
const CFGBlock *CurrentBlock) |
| 168 |
: LV(im), val(Val), observer(Observer), currentBlock(CurrentBlock) {} |
| 169 |
|
| 170 |
void VisitBinaryOperator(BinaryOperator *BO); |
| 171 |
void VisitBlockExpr(BlockExpr *BE); |
| 172 |
void VisitDeclRefExpr(DeclRefExpr *DR); |
| 173 |
void VisitDeclStmt(DeclStmt *DS); |
| 174 |
void VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS); |
| 175 |
void VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE); |
| 176 |
void VisitUnaryOperator(UnaryOperator *UO); |
| 177 |
void Visit(Stmt *S); |
| 178 |
}; |
| 179 |
} // namespace |
| 180 |
|
| 181 |
static const VariableArrayType *FindVA(QualType Ty) { |
| 182 |
const Type *ty = Ty.getTypePtr(); |
| 183 |
while (const ArrayType *VT = dyn_cast<ArrayType>(ty)) { |
| 184 |
if (const VariableArrayType *VAT = dyn_cast<VariableArrayType>(VT)) |
| 185 |
if (VAT->getSizeExpr()) |
| 186 |
return VAT; |
| 187 |
|
| 188 |
ty = VT->getElementType().getTypePtr(); |
| 189 |
} |
| 190 |
|
| 191 |
return nullptr; |
| 192 |
} |
| 193 |
|
| 194 |
static const Expr *LookThroughExpr(const Expr *E) { |
| 195 |
while (E) { |
| 196 |
if (const Expr *Ex = dyn_cast<Expr>(E)) |
| 197 |
E = Ex->IgnoreParens(); |
| 198 |
if (const FullExpr *FE = dyn_cast<FullExpr>(E)) { |
| 199 |
E = FE->getSubExpr(); |
| 200 |
continue; |
| 201 |
} |
| 202 |
if (const OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(E)) { |
| 203 |
E = OVE->getSourceExpr(); |
| 204 |
continue; |
| 205 |
} |
| 206 |
break; |
| 207 |
} |
| 208 |
return E; |
| 209 |
} |
| 210 |
|
| 211 |
static void AddLiveExpr(llvm::ImmutableSet<const Expr *> &Set, |
| 212 |
llvm::ImmutableSet<const Expr *>::Factory &F, |
| 213 |
const Expr *E) { |
| 214 |
Set = F.add(Set, LookThroughExpr(E)); |
| 215 |
} |
| 216 |
|
| 217 |
void TransferFunctions::Visit(Stmt *S) { |
| 218 |
if (observer) |
| 219 |
observer->observeStmt(S, currentBlock, val); |
| 220 |
|
| 221 |
StmtVisitor<TransferFunctions>::Visit(S); |
| 222 |
|
| 223 |
if (const auto *E = dyn_cast<Expr>(S)) { |
| 224 |
val.liveExprs = LV.ESetFact.remove(val.liveExprs, E); |
| 225 |
} |
| 226 |
|
| 227 |
// Mark all children expressions live. |
| 228 |
|
| 229 |
switch (S->getStmtClass()) { |
| 230 |
default: |
| 231 |
break; |
| 232 |
case Stmt::StmtExprClass: { |
| 233 |
// For statement expressions, look through the compound statement. |
| 234 |
S = cast<StmtExpr>(S)->getSubStmt(); |
| 235 |
break; |
| 236 |
} |
| 237 |
case Stmt::CXXMemberCallExprClass: { |
| 238 |
// Include the implicit "this" pointer as being live. |
| 239 |
CXXMemberCallExpr *CE = cast<CXXMemberCallExpr>(S); |
| 240 |
if (Expr *ImplicitObj = CE->getImplicitObjectArgument()) { |
| 241 |
AddLiveExpr(val.liveExprs, LV.ESetFact, ImplicitObj); |
| 242 |
} |
| 243 |
break; |
| 244 |
} |
| 245 |
case Stmt::ObjCMessageExprClass: { |
| 246 |
// In calls to super, include the implicit "self" pointer as being live. |
| 247 |
ObjCMessageExpr *CE = cast<ObjCMessageExpr>(S); |
| 248 |
if (CE->getReceiverKind() == ObjCMessageExpr::SuperInstance) |
| 249 |
val.liveDecls = LV.DSetFact.add(val.liveDecls, |
| 250 |
LV.analysisContext.getSelfDecl()); |
| 251 |
break; |
| 252 |
} |
| 253 |
case Stmt::DeclStmtClass: { |
| 254 |
const DeclStmt *DS = cast<DeclStmt>(S); |
| 255 |
if (const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl())) { |
| 256 |
for (const VariableArrayType* VA = FindVA(VD->getType()); |
| 257 |
VA != nullptr; VA = FindVA(VA->getElementType())) { |
| 258 |
AddLiveExpr(val.liveExprs, LV.ESetFact, VA->getSizeExpr()); |
| 259 |
} |
| 260 |
} |
| 261 |
break; |
| 262 |
} |
| 263 |
case Stmt::PseudoObjectExprClass: { |
| 264 |
// A pseudo-object operation only directly consumes its result |
| 265 |
// expression. |
| 266 |
Expr *child = cast<PseudoObjectExpr>(S)->getResultExpr(); |
| 267 |
if (!child) return; |
| 268 |
if (OpaqueValueExpr *OV = dyn_cast<OpaqueValueExpr>(child)) |
| 269 |
child = OV->getSourceExpr(); |
| 270 |
child = child->IgnoreParens(); |
| 271 |
val.liveExprs = LV.ESetFact.add(val.liveExprs, child); |
| 272 |
return; |
| 273 |
} |
| 274 |
|
| 275 |
// FIXME: These cases eventually shouldn't be needed. |
| 276 |
case Stmt::ExprWithCleanupsClass: { |
| 277 |
S = cast<ExprWithCleanups>(S)->getSubExpr(); |
| 278 |
break; |
| 279 |
} |
| 280 |
case Stmt::CXXBindTemporaryExprClass: { |
| 281 |
S = cast<CXXBindTemporaryExpr>(S)->getSubExpr(); |
| 282 |
break; |
| 283 |
} |
| 284 |
case Stmt::UnaryExprOrTypeTraitExprClass: { |
| 285 |
// No need to unconditionally visit subexpressions. |
| 286 |
return; |
| 287 |
} |
| 288 |
case Stmt::IfStmtClass: { |
| 289 |
// If one of the branches is an expression rather than a compound |
| 290 |
// statement, it will be bad if we mark it as live at the terminator |
| 291 |
// of the if-statement (i.e., immediately after the condition expression). |
| 292 |
AddLiveExpr(val.liveExprs, LV.ESetFact, cast<IfStmt>(S)->getCond()); |
| 293 |
return; |
| 294 |
} |
| 295 |
case Stmt::WhileStmtClass: { |
| 296 |
// If the loop body is an expression rather than a compound statement, |
| 297 |
// it will be bad if we mark it as live at the terminator of the loop |
| 298 |
// (i.e., immediately after the condition expression). |
| 299 |
AddLiveExpr(val.liveExprs, LV.ESetFact, cast<WhileStmt>(S)->getCond()); |
| 300 |
return; |
| 301 |
} |
| 302 |
case Stmt::DoStmtClass: { |
| 303 |
// If the loop body is an expression rather than a compound statement, |
| 304 |
// it will be bad if we mark it as live at the terminator of the loop |
| 305 |
// (i.e., immediately after the condition expression). |
| 306 |
AddLiveExpr(val.liveExprs, LV.ESetFact, cast<DoStmt>(S)->getCond()); |
| 307 |
return; |
| 308 |
} |
| 309 |
case Stmt::ForStmtClass: { |
| 310 |
// If the loop body is an expression rather than a compound statement, |
| 311 |
// it will be bad if we mark it as live at the terminator of the loop |
| 312 |
// (i.e., immediately after the condition expression). |
| 313 |
AddLiveExpr(val.liveExprs, LV.ESetFact, cast<ForStmt>(S)->getCond()); |
| 314 |
return; |
| 315 |
} |
| 316 |
|
| 317 |
} |
| 318 |
|
| 319 |
// HACK + FIXME: What is this? One could only guess that this is an attempt to |
| 320 |
// fish for live values, for example, arguments from a call expression. |
| 321 |
// Maybe we could take inspiration from UninitializedVariable analysis? |
| 322 |
for (Stmt *Child : S->children()) { |
| 323 |
if (const auto *E = dyn_cast_or_null<Expr>(Child)) |
| 324 |
AddLiveExpr(val.liveExprs, LV.ESetFact, E); |
| 325 |
} |
| 326 |
} |
| 327 |
|
| 328 |
static bool writeShouldKill(const VarDecl *VD) { |
| 329 |
return VD && !VD->getType()->isReferenceType() && |
| 330 |
!isAlwaysAlive(VD); |
| 331 |
} |
| 332 |
|
| 333 |
void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) { |
| 334 |
if (LV.killAtAssign && B->getOpcode() == BO_Assign) { |
| 335 |
if (const auto *DR = dyn_cast<DeclRefExpr>(B->getLHS()->IgnoreParens())) { |
| 336 |
LV.inAssignment[DR] = 1; |
| 337 |
} |
| 338 |
} |
| 339 |
if (B->isAssignmentOp()) { |
| 340 |
if (!LV.killAtAssign) |
| 341 |
return; |
| 342 |
|
| 343 |
// Assigning to a variable? |
| 344 |
Expr *LHS = B->getLHS()->IgnoreParens(); |
| 345 |
|
| 346 |
if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) { |
| 347 |
const Decl* D = DR->getDecl(); |
| 348 |
bool Killed = false; |
| 349 |
|
| 350 |
if (const BindingDecl* BD = dyn_cast<BindingDecl>(D)) { |
| 351 |
Killed = !BD->getType()->isReferenceType(); |
| 352 |
if (Killed) { |
| 353 |
if (const auto *HV = BD->getHoldingVar()) |
| 354 |
val.liveDecls = LV.DSetFact.remove(val.liveDecls, HV); |
| 355 |
|
| 356 |
val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD); |
| 357 |
} |
| 358 |
} else if (const auto *VD = dyn_cast<VarDecl>(D)) { |
| 359 |
Killed = writeShouldKill(VD); |
| 360 |
if (Killed) |
| 361 |
val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); |
| 362 |
|
| 363 |
} |
| 364 |
|
| 365 |
if (Killed && observer) |
| 366 |
observer->observerKill(DR); |
| 367 |
} |
| 368 |
} |
| 369 |
} |
| 370 |
|
| 371 |
void TransferFunctions::VisitBlockExpr(BlockExpr *BE) { |
| 372 |
for (const VarDecl *VD : |
| 373 |
LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl())) { |
| 374 |
if (isAlwaysAlive(VD)) |
| 375 |
continue; |
| 376 |
val.liveDecls = LV.DSetFact.add(val.liveDecls, VD); |
| 377 |
} |
| 378 |
} |
| 379 |
|
| 380 |
void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) { |
| 381 |
const Decl* D = DR->getDecl(); |
| 382 |
bool InAssignment = LV.inAssignment[DR]; |
| 383 |
if (const auto *BD = dyn_cast<BindingDecl>(D)) { |
| 384 |
if (!InAssignment) { |
| 385 |
if (const auto *HV = BD->getHoldingVar()) |
| 386 |
val.liveDecls = LV.DSetFact.add(val.liveDecls, HV); |
| 387 |
|
| 388 |
val.liveBindings = LV.BSetFact.add(val.liveBindings, BD); |
| 389 |
} |
| 390 |
} else if (const auto *VD = dyn_cast<VarDecl>(D)) { |
| 391 |
if (!InAssignment && !isAlwaysAlive(VD)) |
| 392 |
val.liveDecls = LV.DSetFact.add(val.liveDecls, VD); |
| 393 |
} |
| 394 |
} |
| 395 |
|
| 396 |
void TransferFunctions::VisitDeclStmt(DeclStmt *DS) { |
| 397 |
for (const auto *DI : DS->decls()) { |
| 398 |
if (const auto *DD = dyn_cast<DecompositionDecl>(DI)) { |
| 399 |
for (const auto *BD : DD->bindings()) { |
| 400 |
if (const auto *HV = BD->getHoldingVar()) |
| 401 |
val.liveDecls = LV.DSetFact.remove(val.liveDecls, HV); |
| 402 |
|
| 403 |
val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD); |
| 404 |
} |
| 405 |
|
| 406 |
// When a bindig to a tuple-like structure is created, the HoldingVar |
| 407 |
// initializers have a DeclRefExpr to the DecompositionDecl. |
| 408 |
val.liveDecls = LV.DSetFact.remove(val.liveDecls, DD); |
| 409 |
} else if (const auto *VD = dyn_cast<VarDecl>(DI)) { |
| 410 |
if (!isAlwaysAlive(VD)) |
| 411 |
val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); |
| 412 |
} |
| 413 |
} |
| 414 |
} |
| 415 |
|
| 416 |
void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) { |
| 417 |
// Kill the iteration variable. |
| 418 |
DeclRefExpr *DR = nullptr; |
| 419 |
const VarDecl *VD = nullptr; |
| 420 |
|
| 421 |
Stmt *element = OS->getElement(); |
| 422 |
if (DeclStmt *DS = dyn_cast<DeclStmt>(element)) { |
| 423 |
VD = cast<VarDecl>(DS->getSingleDecl()); |
| 424 |
} |
| 425 |
else if ((DR = dyn_cast<DeclRefExpr>(cast<Expr>(element)->IgnoreParens()))) { |
| 426 |
VD = cast<VarDecl>(DR->getDecl()); |
| 427 |
} |
| 428 |
|
| 429 |
if (VD) { |
| 430 |
val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); |
| 431 |
if (observer && DR) |
| 432 |
observer->observerKill(DR); |
| 433 |
} |
| 434 |
} |
| 435 |
|
| 436 |
void TransferFunctions:: |
| 437 |
VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE) |
| 438 |
{ |
| 439 |
// While sizeof(var) doesn't technically extend the liveness of 'var', it |
| 440 |
// does extent the liveness of metadata if 'var' is a VariableArrayType. |
| 441 |
// We handle that special case here. |
| 442 |
if (UE->getKind() != UETT_SizeOf || UE->isArgumentType()) |
| 443 |
return; |
| 444 |
|
| 445 |
const Expr *subEx = UE->getArgumentExpr(); |
| 446 |
if (subEx->getType()->isVariableArrayType()) { |
| 447 |
assert(subEx->isLValue()); |
| 448 |
val.liveExprs = LV.ESetFact.add(val.liveExprs, subEx->IgnoreParens()); |
| 449 |
} |
| 450 |
} |
| 451 |
|
| 452 |
void TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) { |
| 453 |
// Treat ++/-- as a kill. |
| 454 |
// Note we don't actually have to do anything if we don't have an observer, |
| 455 |
// since a ++/-- acts as both a kill and a "use". |
| 456 |
if (!observer) |
| 457 |
return; |
| 458 |
|
| 459 |
switch (UO->getOpcode()) { |
| 460 |
default: |
| 461 |
return; |
| 462 |
case UO_PostInc: |
| 463 |
case UO_PostDec: |
| 464 |
case UO_PreInc: |
| 465 |
case UO_PreDec: |
| 466 |
break; |
| 467 |
} |
| 468 |
|
| 469 |
if (auto *DR = dyn_cast<DeclRefExpr>(UO->getSubExpr()->IgnoreParens())) { |
| 470 |
const Decl *D = DR->getDecl(); |
| 471 |
if (isa<VarDecl>(D) || isa<BindingDecl>(D)) { |
| 472 |
// Treat ++/-- as a kill. |
| 473 |
observer->observerKill(DR); |
| 474 |
} |
| 475 |
} |
| 476 |
} |
| 477 |
|
| 478 |
LiveVariables::LivenessValues |
| 479 |
LiveVariablesImpl::runOnBlock(const CFGBlock *block, |
| 480 |
LiveVariables::LivenessValues val, |
| 481 |
LiveVariables::Observer *obs) { |
| 482 |
|
| 483 |
TransferFunctions TF(*this, val, obs, block); |
| 484 |
|
| 485 |
// Visit the terminator (if any). |
| 486 |
if (const Stmt *term = block->getTerminatorStmt()) |
| 487 |
TF.Visit(const_cast<Stmt*>(term)); |
| 488 |
|
| 489 |
// Apply the transfer function for all Stmts in the block. |
| 490 |
for (CFGBlock::const_reverse_iterator it = block->rbegin(), |
| 491 |
ei = block->rend(); it != ei; ++it) { |
| 492 |
const CFGElement &elem = *it; |
| 493 |
|
| 494 |
if (std::optional<CFGAutomaticObjDtor> Dtor = |
| 495 |
elem.getAs<CFGAutomaticObjDtor>()) { |
| 496 |
val.liveDecls = DSetFact.add(val.liveDecls, Dtor->getVarDecl()); |
| 497 |
continue; |
| 498 |
} |
| 499 |
|
| 500 |
if (!elem.getAs<CFGStmt>()) |
| 501 |
continue; |
| 502 |
|
| 503 |
const Stmt *S = elem.castAs<CFGStmt>().getStmt(); |
| 504 |
TF.Visit(const_cast<Stmt*>(S)); |
| 505 |
stmtsToLiveness[S] = val; |
| 506 |
} |
| 507 |
return val; |
| 508 |
} |
| 509 |
|
| 510 |
void LiveVariables::runOnAllBlocks(LiveVariables::Observer &obs) { |
| 511 |
const CFG *cfg = getImpl(impl).analysisContext.getCFG(); |
| 512 |
for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) |
| 513 |
getImpl(impl).runOnBlock(*it, getImpl(impl).blocksEndToLiveness[*it], &obs); |
| 514 |
} |
| 515 |
|
| 516 |
LiveVariables::LiveVariables(void *im) : impl(im) {} |
| 517 |
|
| 518 |
LiveVariables::~LiveVariables() { |
| 519 |
delete (LiveVariablesImpl*) impl; |
| 520 |
} |
| 521 |
|
| 522 |
std::unique_ptr<LiveVariables> |
| 523 |
LiveVariables::computeLiveness(AnalysisDeclContext &AC, bool killAtAssign) { |
| 524 |
|
| 525 |
// No CFG? Bail out. |
| 526 |
CFG *cfg = AC.getCFG(); |
| 527 |
if (!cfg) |
| 528 |
return nullptr; |
| 529 |
|
| 530 |
// The analysis currently has scalability issues for very large CFGs. |
| 531 |
// Bail out if it looks too large. |
| 532 |
if (cfg->getNumBlockIDs() > 300000) |
| 533 |
return nullptr; |
| 534 |
|
| 535 |
LiveVariablesImpl *LV = new LiveVariablesImpl(AC, killAtAssign); |
| 536 |
|
| 537 |
// Construct the dataflow worklist. Enqueue the exit block as the |
| 538 |
// start of the analysis. |
| 539 |
BackwardDataflowWorklist worklist(*cfg, AC); |
| 540 |
llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs()); |
| 541 |
|
| 542 |
// FIXME: we should enqueue using post order. |
| 543 |
for (const CFGBlock *B : cfg->nodes()) { |
| 544 |
worklist.enqueueBlock(B); |
| 545 |
} |
| 546 |
|
| 547 |
while (const CFGBlock *block = worklist.dequeue()) { |
| 548 |
// Determine if the block's end value has changed. If not, we |
| 549 |
// have nothing left to do for this block. |
| 550 |
LivenessValues &prevVal = LV->blocksEndToLiveness[block]; |
| 551 |
|
| 552 |
// Merge the values of all successor blocks. |
| 553 |
LivenessValues val; |
| 554 |
for (CFGBlock::const_succ_iterator it = block->succ_begin(), |
| 555 |
ei = block->succ_end(); it != ei; ++it) { |
| 556 |
if (const CFGBlock *succ = *it) { |
| 557 |
val = LV->merge(val, LV->blocksBeginToLiveness[succ]); |
| 558 |
} |
| 559 |
} |
| 560 |
|
| 561 |
if (!everAnalyzedBlock[block->getBlockID()]) |
| 562 |
everAnalyzedBlock[block->getBlockID()] = true; |
| 563 |
else if (prevVal.equals(val)) |
| 564 |
continue; |
| 565 |
|
| 566 |
prevVal = val; |
| 567 |
|
| 568 |
// Update the dataflow value for the start of this block. |
| 569 |
LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val); |
| 570 |
|
| 571 |
// Enqueue the value to the predecessors. |
| 572 |
worklist.enqueuePredecessors(block); |
| 573 |
} |
| 574 |
|
| 575 |
return std::unique_ptr<LiveVariables>(new LiveVariables(LV)); |
| 576 |
} |
| 577 |
|
| 578 |
void LiveVariables::dumpBlockLiveness(const SourceManager &M) { |
| 579 |
getImpl(impl).dumpBlockLiveness(M); |
| 580 |
} |
| 581 |
|
| 582 |
void LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) { |
| 583 |
std::vector<const CFGBlock *> vec; |
| 584 |
for (llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues>::iterator |
| 585 |
it = blocksEndToLiveness.begin(), ei = blocksEndToLiveness.end(); |
| 586 |
it != ei; ++it) { |
| 587 |
vec.push_back(it->first); |
| 588 |
} |
| 589 |
llvm::sort(vec, [](const CFGBlock *A, const CFGBlock *B) { |
| 590 |
return A->getBlockID() < B->getBlockID(); |
| 591 |
}); |
| 592 |
|
| 593 |
std::vector<const VarDecl*> declVec; |
| 594 |
|
| 595 |
for (std::vector<const CFGBlock *>::iterator |
| 596 |
it = vec.begin(), ei = vec.end(); it != ei; ++it) { |
| 597 |
llvm::errs() << "\n[ B" << (*it)->getBlockID() |
| 598 |
<< " (live variables at block exit) ]\n"; |
| 599 |
|
| 600 |
LiveVariables::LivenessValues vals = blocksEndToLiveness[*it]; |
| 601 |
declVec.clear(); |
| 602 |
|
| 603 |
for (llvm::ImmutableSet<const VarDecl *>::iterator si = |
| 604 |
vals.liveDecls.begin(), |
| 605 |
se = vals.liveDecls.end(); si != se; ++si) { |
| 606 |
declVec.push_back(*si); |
| 607 |
} |
| 608 |
|
| 609 |
llvm::sort(declVec, [](const Decl *A, const Decl *B) { |
| 610 |
return A->getBeginLoc() < B->getBeginLoc(); |
| 611 |
}); |
| 612 |
|
| 613 |
for (std::vector<const VarDecl*>::iterator di = declVec.begin(), |
| 614 |
de = declVec.end(); di != de; ++di) { |
| 615 |
llvm::errs() << " " << (*di)->getDeclName().getAsString() |
| 616 |
<< " <"; |
| 617 |
(*di)->getLocation().print(llvm::errs(), M); |
| 618 |
llvm::errs() << ">\n"; |
| 619 |
} |
| 620 |
} |
| 621 |
llvm::errs() << "\n"; |
| 622 |
} |
| 623 |
|
| 624 |
void LiveVariables::dumpExprLiveness(const SourceManager &M) { |
| 625 |
getImpl(impl).dumpExprLiveness(M); |
| 626 |
} |
| 627 |
|
| 628 |
void LiveVariablesImpl::dumpExprLiveness(const SourceManager &M) { |
| 629 |
// Don't iterate over blockEndsToLiveness directly because it's not sorted. |
| 630 |
for (const CFGBlock *B : *analysisContext.getCFG()) { |
| 631 |
|
| 632 |
llvm::errs() << "\n[ B" << B->getBlockID() |
| 633 |
<< " (live expressions at block exit) ]\n"; |
| 634 |
for (const Expr *E : blocksEndToLiveness[B].liveExprs) { |
| 635 |
llvm::errs() << "\n"; |
| 636 |
E->dump(); |
| 637 |
} |
| 638 |
llvm::errs() << "\n"; |
| 639 |
} |
| 640 |
} |
| 641 |
|
| 642 |
const void *LiveVariables::getTag() { static int x; return &x; } |
| 643 |
const void *RelaxedLiveVariables::getTag() { static int x; return &x; } |