clang/lib/Analysis/LiveVariables.cpp

   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 /// Add as a live expression all individual conditions in a logical expression.
 218 /// For example, for the expression:
 219 /// "(a < b) || (c && d && ((e || f) != (g && h)))"
 220 /// the following expressions will be added as live:
 221 /// "a < b", "c", "d", "((e || f) != (g && h))"
 222 static void AddAllConditionalTerms(llvm::ImmutableSet<const Expr *> &Set,
 223                                    llvm::ImmutableSet<const Expr *>::Factory &F,
 224                                    const Expr *Cond) {
 225   AddLiveExpr(Set, F, Cond);
 226   if (auto const *BO = dyn_cast<BinaryOperator>(Cond->IgnoreParens());
 227       BO && BO->isLogicalOp()) {
 228     AddAllConditionalTerms(Set, F, BO->getLHS());
 229     AddAllConditionalTerms(Set, F, BO->getRHS());
 230   }
 231 }
 232
 233 void TransferFunctions::Visit(Stmt *S) {
 234   if (observer)
 235     observer->observeStmt(S, currentBlock, val);
 236
 237   StmtVisitor<TransferFunctions>::Visit(S);
 238
 239   if (const auto *E = dyn_cast<Expr>(S)) {
 240     val.liveExprs = LV.ESetFact.remove(val.liveExprs, E);
 241   }
 242
 243   // Mark all children expressions live.
 244
 245   switch (S->getStmtClass()) {
 246     default:
 247       break;
 248     case Stmt::StmtExprClass: {
 249       // For statement expressions, look through the compound statement.
 250       S = cast<StmtExpr>(S)->getSubStmt();
 251       break;
 252     }
 253     case Stmt::CXXMemberCallExprClass: {
 254       // Include the implicit "this" pointer as being live.
 255       CXXMemberCallExpr *CE = cast<CXXMemberCallExpr>(S);
 256       if (Expr *ImplicitObj = CE->getImplicitObjectArgument()) {
 257         AddLiveExpr(val.liveExprs, LV.ESetFact, ImplicitObj);
 258       }
 259       break;
 260     }
 261     case Stmt::ObjCMessageExprClass: {
 262       // In calls to super, include the implicit "self" pointer as being live.
 263       ObjCMessageExpr *CE = cast<ObjCMessageExpr>(S);
 264       if (CE->getReceiverKind() == ObjCMessageExpr::SuperInstance)
 265         val.liveDecls = LV.DSetFact.add(val.liveDecls,
 266                                         LV.analysisContext.getSelfDecl());
 267       break;
 268     }
 269     case Stmt::DeclStmtClass: {
 270       const DeclStmt *DS = cast<DeclStmt>(S);
 271       if (const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl())) {
 272         for (const VariableArrayType* VA = FindVA(VD->getType());
 273              VA != nullptr; VA = FindVA(VA->getElementType())) {
 274           AddLiveExpr(val.liveExprs, LV.ESetFact, VA->getSizeExpr());
 275         }
 276       }
 277       break;
 278     }
 279     case Stmt::PseudoObjectExprClass: {
 280       // A pseudo-object operation only directly consumes its result
 281       // expression.
 282       Expr *child = cast<PseudoObjectExpr>(S)->getResultExpr();
 283       if (!child) return;
 284       if (OpaqueValueExpr *OV = dyn_cast<OpaqueValueExpr>(child))
 285         child = OV->getSourceExpr();
 286       child = child->IgnoreParens();
 287       val.liveExprs = LV.ESetFact.add(val.liveExprs, child);
 288       return;
 289     }
 290
 291     // FIXME: These cases eventually shouldn't be needed.
 292     case Stmt::ExprWithCleanupsClass: {
 293       S = cast<ExprWithCleanups>(S)->getSubExpr();
 294       break;
 295     }
 296     case Stmt::CXXBindTemporaryExprClass: {
 297       S = cast<CXXBindTemporaryExpr>(S)->getSubExpr();
 298       break;
 299     }
 300     case Stmt::UnaryExprOrTypeTraitExprClass: {
 301       // No need to unconditionally visit subexpressions.
 302       return;
 303     }
 304     case Stmt::IfStmtClass: {
 305       // If one of the branches is an expression rather than a compound
 306       // statement, it will be bad if we mark it as live at the terminator
 307       // of the if-statement (i.e., immediately after the condition expression).
 308       AddLiveExpr(val.liveExprs, LV.ESetFact, cast<IfStmt>(S)->getCond());
 309       return;
 310     }
 311     case Stmt::WhileStmtClass: {
 312       // If the loop body is an expression rather than a compound statement,
 313       // it will be bad if we mark it as live at the terminator of the loop
 314       // (i.e., immediately after the condition expression).
 315       AddLiveExpr(val.liveExprs, LV.ESetFact, cast<WhileStmt>(S)->getCond());
 316       return;
 317     }
 318     case Stmt::DoStmtClass: {
 319       // If the loop body is an expression rather than a compound statement,
 320       // it will be bad if we mark it as live at the terminator of the loop
 321       // (i.e., immediately after the condition expression).
 322       AddLiveExpr(val.liveExprs, LV.ESetFact, cast<DoStmt>(S)->getCond());
 323       return;
 324     }
 325     case Stmt::ForStmtClass: {
 326       // If the loop body is an expression rather than a compound statement,
 327       // it will be bad if we mark it as live at the terminator of the loop
 328       // (i.e., immediately after the condition expression).
 329       AddLiveExpr(val.liveExprs, LV.ESetFact, cast<ForStmt>(S)->getCond());
 330       return;
 331     }
 332     case Stmt::ConditionalOperatorClass: {
 333       // Keep not only direct children alive, but also all the short-circuited
 334       // parts of the condition. Short-circuiting evaluation may cause the
 335       // conditional operator evaluation to skip the evaluation of the entire
 336       // condtion expression, so the value of the entire condition expression is
 337       // never computed.
 338       //
 339       // This makes a difference when we compare exploded nodes coming from true
 340       // and false expressions with no side effects: the only difference in the
 341       // state is the value of (part of) the condition.
 342       //
 343       // BinaryConditionalOperatorClass ('x ?: y') is not affected because it
 344       // explicitly calculates the value of the entire condition expression (to
 345       // possibly use as a value for the "true expr") even if it is
 346       // short-circuited.
 347       auto const *CO = cast<ConditionalOperator>(S);
 348       AddAllConditionalTerms(val.liveExprs, LV.ESetFact, CO->getCond());
 349       AddLiveExpr(val.liveExprs, LV.ESetFact, CO->getTrueExpr());
 350       AddLiveExpr(val.liveExprs, LV.ESetFact, CO->getFalseExpr());
 351       return;
 352     }
 353   }
 354
 355   // HACK + FIXME: What is this? One could only guess that this is an attempt to
 356   // fish for live values, for example, arguments from a call expression.
 357   // Maybe we could take inspiration from UninitializedVariable analysis?
 358   for (Stmt *Child : S->children()) {
 359     if (const auto *E = dyn_cast_or_null<Expr>(Child))
 360       AddLiveExpr(val.liveExprs, LV.ESetFact, E);
 361   }
 362 }
 363
 364 static bool writeShouldKill(const VarDecl *VD) {
 365   return VD && !VD->getType()->isReferenceType() &&
 366     !isAlwaysAlive(VD);
 367 }
 368
 369 void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) {
 370   if (LV.killAtAssign && B->getOpcode() == BO_Assign) {
 371     if (const auto *DR = dyn_cast<DeclRefExpr>(B->getLHS()->IgnoreParens())) {
 372       LV.inAssignment[DR] = 1;
 373     }
 374   }
 375   if (B->isAssignmentOp()) {
 376     if (!LV.killAtAssign)
 377       return;
 378
 379     // Assigning to a variable?
 380     Expr *LHS = B->getLHS()->IgnoreParens();
 381
 382     if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) {
 383       const Decl* D = DR->getDecl();
 384       bool Killed = false;
 385
 386       if (const BindingDecl* BD = dyn_cast<BindingDecl>(D)) {
 387         Killed = !BD->getType()->isReferenceType();
 388         if (Killed) {
 389           if (const auto *HV = BD->getHoldingVar())
 390             val.liveDecls = LV.DSetFact.remove(val.liveDecls, HV);
 391
 392           val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD);
 393         }
 394       } else if (const auto *VD = dyn_cast<VarDecl>(D)) {
 395         Killed = writeShouldKill(VD);
 396         if (Killed)
 397           val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
 398
 399       }
 400
 401       if (Killed && observer)
 402         observer->observerKill(DR);
 403     }
 404   }
 405 }
 406
 407 void TransferFunctions::VisitBlockExpr(BlockExpr *BE) {
 408   for (const VarDecl *VD :
 409        LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl())) {
 410     if (isAlwaysAlive(VD))
 411       continue;
 412     val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
 413   }
 414 }
 415
 416 void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) {
 417   const Decl* D = DR->getDecl();
 418   bool InAssignment = LV.inAssignment[DR];
 419   if (const auto *BD = dyn_cast<BindingDecl>(D)) {
 420     if (!InAssignment) {
 421       if (const auto *HV = BD->getHoldingVar())
 422         val.liveDecls = LV.DSetFact.add(val.liveDecls, HV);
 423
 424       val.liveBindings = LV.BSetFact.add(val.liveBindings, BD);
 425     }
 426   } else if (const auto *VD = dyn_cast<VarDecl>(D)) {
 427     if (!InAssignment && !isAlwaysAlive(VD))
 428       val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
 429   }
 430 }
 431
 432 void TransferFunctions::VisitDeclStmt(DeclStmt *DS) {
 433   for (const auto *DI : DS->decls()) {
 434     if (const auto *DD = dyn_cast<DecompositionDecl>(DI)) {
 435       for (const auto *BD : DD->bindings()) {
 436         if (const auto *HV = BD->getHoldingVar())
 437           val.liveDecls = LV.DSetFact.remove(val.liveDecls, HV);
 438
 439         val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD);
 440       }
 441
 442       // When a bindig to a tuple-like structure is created, the HoldingVar
 443       // initializers have a DeclRefExpr to the DecompositionDecl.
 444       val.liveDecls = LV.DSetFact.remove(val.liveDecls, DD);
 445     } else if (const auto *VD = dyn_cast<VarDecl>(DI)) {
 446       if (!isAlwaysAlive(VD))
 447         val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
 448     }
 449   }
 450 }
 451
 452 void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) {
 453   // Kill the iteration variable.
 454   DeclRefExpr *DR = nullptr;
 455   const VarDecl *VD = nullptr;
 456
 457   Stmt *element = OS->getElement();
 458   if (DeclStmt *DS = dyn_cast<DeclStmt>(element)) {
 459     VD = cast<VarDecl>(DS->getSingleDecl());
 460   }
 461   else if ((DR = dyn_cast<DeclRefExpr>(cast<Expr>(element)->IgnoreParens()))) {
 462     VD = cast<VarDecl>(DR->getDecl());
 463   }
 464
 465   if (VD) {
 466     val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
 467     if (observer && DR)
 468       observer->observerKill(DR);
 469   }
 470 }
 471
 472 void TransferFunctions::
 473 VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE)
 474 {
 475   // While sizeof(var) doesn't technically extend the liveness of 'var', it
 476   // does extent the liveness of metadata if 'var' is a VariableArrayType.
 477   // We handle that special case here.
 478   if (UE->getKind() != UETT_SizeOf || UE->isArgumentType())
 479     return;
 480
 481   const Expr *subEx = UE->getArgumentExpr();
 482   if (subEx->getType()->isVariableArrayType()) {
 483     assert(subEx->isLValue());
 484     val.liveExprs = LV.ESetFact.add(val.liveExprs, subEx->IgnoreParens());
 485   }
 486 }
 487
 488 void TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) {
 489   // Treat ++/-- as a kill.
 490   // Note we don't actually have to do anything if we don't have an observer,
 491   // since a ++/-- acts as both a kill and a "use".
 492   if (!observer)
 493     return;
 494
 495   switch (UO->getOpcode()) {
 496   default:
 497     return;
 498   case UO_PostInc:
 499   case UO_PostDec:
 500   case UO_PreInc:
 501   case UO_PreDec:
 502     break;
 503   }
 504
 505   if (auto *DR = dyn_cast<DeclRefExpr>(UO->getSubExpr()->IgnoreParens())) {
 506     const Decl *D = DR->getDecl();
 507     if (isa<VarDecl>(D) || isa<BindingDecl>(D)) {
 508       // Treat ++/-- as a kill.
 509       observer->observerKill(DR);
 510     }
 511   }
 512 }
 513
 514 LiveVariables::LivenessValues
 515 LiveVariablesImpl::runOnBlock(const CFGBlock *block,
 516                               LiveVariables::LivenessValues val,
 517                               LiveVariables::Observer *obs) {
 518
 519   TransferFunctions TF(*this, val, obs, block);
 520
 521   // Visit the terminator (if any).
 522   if (const Stmt *term = block->getTerminatorStmt())
 523     TF.Visit(const_cast<Stmt*>(term));
 524
 525   // Apply the transfer function for all Stmts in the block.
 526   for (CFGBlock::const_reverse_iterator it = block->rbegin(),
 527        ei = block->rend(); it != ei; ++it) {
 528     const CFGElement &elem = *it;
 529
 530     if (std::optional<CFGAutomaticObjDtor> Dtor =
 531             elem.getAs<CFGAutomaticObjDtor>()) {
 532       val.liveDecls = DSetFact.add(val.liveDecls, Dtor->getVarDecl());
 533       continue;
 534     }
 535
 536     if (!elem.getAs<CFGStmt>())
 537       continue;
 538
 539     const Stmt *S = elem.castAs<CFGStmt>().getStmt();
 540     TF.Visit(const_cast<Stmt*>(S));
 541     stmtsToLiveness[S] = val;
 542   }
 543   return val;
 544 }
 545
 546 void LiveVariables::runOnAllBlocks(LiveVariables::Observer &obs) {
 547   const CFG *cfg = getImpl(impl).analysisContext.getCFG();
 548   for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it)
 549     getImpl(impl).runOnBlock(*it, getImpl(impl).blocksEndToLiveness[*it], &obs);
 550 }
 551
 552 LiveVariables::LiveVariables(void *im) : impl(im) {}
 553
 554 LiveVariables::~LiveVariables() {
 555   delete (LiveVariablesImpl*) impl;
 556 }
 557
 558 std::unique_ptr<LiveVariables>
 559 LiveVariables::computeLiveness(AnalysisDeclContext &AC, bool killAtAssign) {
 560
 561   // No CFG?  Bail out.
 562   CFG *cfg = AC.getCFG();
 563   if (!cfg)
 564     return nullptr;
 565
 566   // The analysis currently has scalability issues for very large CFGs.
 567   // Bail out if it looks too large.
 568   if (cfg->getNumBlockIDs() > 300000)
 569     return nullptr;
 570
 571   LiveVariablesImpl *LV = new LiveVariablesImpl(AC, killAtAssign);
 572
 573   // Construct the dataflow worklist.  Enqueue the exit block as the
 574   // start of the analysis.
 575   BackwardDataflowWorklist worklist(*cfg, AC);
 576   llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs());
 577
 578   // FIXME: we should enqueue using post order.
 579   for (const CFGBlock *B : cfg->nodes()) {
 580     worklist.enqueueBlock(B);
 581   }
 582
 583   while (const CFGBlock *block = worklist.dequeue()) {
 584     // Determine if the block's end value has changed.  If not, we
 585     // have nothing left to do for this block.
 586     LivenessValues &prevVal = LV->blocksEndToLiveness[block];
 587
 588     // Merge the values of all successor blocks.
 589     LivenessValues val;
 590     for (CFGBlock::const_succ_iterator it = block->succ_begin(),
 591                                        ei = block->succ_end(); it != ei; ++it) {
 592       if (const CFGBlock *succ = *it) {
 593         val = LV->merge(val, LV->blocksBeginToLiveness[succ]);
 594       }
 595     }
 596
 597     if (!everAnalyzedBlock[block->getBlockID()])
 598       everAnalyzedBlock[block->getBlockID()] = true;
 599     else if (prevVal.equals(val))
 600       continue;
 601
 602     prevVal = val;
 603
 604     // Update the dataflow value for the start of this block.
 605     LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val);
 606
 607     // Enqueue the value to the predecessors.
 608     worklist.enqueuePredecessors(block);
 609   }
 610
 611   return std::unique_ptr<LiveVariables>(new LiveVariables(LV));
 612 }
 613
 614 void LiveVariables::dumpBlockLiveness(const SourceManager &M) {
 615   getImpl(impl).dumpBlockLiveness(M);
 616 }
 617
 618 void LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) {
 619   std::vector<const CFGBlock *> vec;
 620   for (llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues>::iterator
 621        it = blocksEndToLiveness.begin(), ei = blocksEndToLiveness.end();
 622        it != ei; ++it) {
 623     vec.push_back(it->first);
 624   }
 625   llvm::sort(vec, [](const CFGBlock *A, const CFGBlock *B) {
 626     return A->getBlockID() < B->getBlockID();
 627   });
 628
 629   std::vector<const VarDecl*> declVec;
 630
 631   for (std::vector<const CFGBlock *>::iterator
 632         it = vec.begin(), ei = vec.end(); it != ei; ++it) {
 633     llvm::errs() << "\n[ B" << (*it)->getBlockID()
 634                  << " (live variables at block exit) ]\n";
 635
 636     LiveVariables::LivenessValues vals = blocksEndToLiveness[*it];
 637     declVec.clear();
 638
 639     for (llvm::ImmutableSet<const VarDecl *>::iterator si =
 640           vals.liveDecls.begin(),
 641           se = vals.liveDecls.end(); si != se; ++si) {
 642       declVec.push_back(*si);
 643     }
 644
 645     llvm::sort(declVec, [](const Decl *A, const Decl *B) {
 646       return A->getBeginLoc() < B->getBeginLoc();
 647     });
 648
 649     for (std::vector<const VarDecl*>::iterator di = declVec.begin(),
 650          de = declVec.end(); di != de; ++di) {
 651       llvm::errs() << " " << (*di)->getDeclName().getAsString()
 652                    << " <";
 653       (*di)->getLocation().print(llvm::errs(), M);
 654       llvm::errs() << ">\n";
 655     }
 656   }
 657   llvm::errs() << "\n";
 658 }
 659
 660 void LiveVariables::dumpExprLiveness(const SourceManager &M) {
 661   getImpl(impl).dumpExprLiveness(M);
 662 }
 663
 664 void LiveVariablesImpl::dumpExprLiveness(const SourceManager &M) {
 665   // Don't iterate over blockEndsToLiveness directly because it's not sorted.
 666   for (const CFGBlock *B : *analysisContext.getCFG()) {
 667
 668     llvm::errs() << "\n[ B" << B->getBlockID()
 669                  << " (live expressions at block exit) ]\n";
 670     for (const Expr *E : blocksEndToLiveness[B].liveExprs) {
 671       llvm::errs() << "\n";
 672       E->dump();
 673     }
 674     llvm::errs() << "\n";
 675   }
 676 }
 677
 678 const void *LiveVariables::getTag() { static int x; return &x; }
 679 const void *RelaxedLiveVariables::getTag() { static int x; return &x; }