644 lines · 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-exception6//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 "clang/Basic/SourceManager.h"20#include "llvm/ADT/DenseMap.h"21#include "llvm/ADT/DenseSet.h"22#include "llvm/ADT/STLExtras.h"23#include "llvm/Support/raw_ostream.h"24#include <optional>25#include <vector>26 27using namespace clang;28 29namespace {30class LiveVariablesImpl {31public:32 AnalysisDeclContext &analysisContext;33 llvm::ImmutableSet<const Expr *>::Factory ESetFact;34 llvm::ImmutableSet<const VarDecl *>::Factory DSetFact;35 llvm::ImmutableSet<const BindingDecl *>::Factory BSetFact;36 llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksEndToLiveness;37 llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksBeginToLiveness;38 llvm::DenseMap<const Stmt *, LiveVariables::LivenessValues> stmtsToLiveness;39 llvm::DenseSet<const DeclRefExpr *> inAssignment;40 const bool killAtAssign;41 42 LiveVariables::LivenessValues43 merge(LiveVariables::LivenessValues valsA,44 LiveVariables::LivenessValues valsB);45 46 LiveVariables::LivenessValues47 runOnBlock(const CFGBlock *block, LiveVariables::LivenessValues val,48 LiveVariables::Observer *obs = nullptr);49 50 void dumpBlockLiveness(const SourceManager& M);51 void dumpExprLiveness(const SourceManager& M);52 53 LiveVariablesImpl(AnalysisDeclContext &ac, bool KillAtAssign)54 : analysisContext(ac),55 ESetFact(false), // Do not canonicalize ImmutableSets by default.56 DSetFact(false), // This is a *major* performance win.57 BSetFact(false), killAtAssign(KillAtAssign) {}58};59} // namespace60 61static LiveVariablesImpl &getImpl(void *x) {62 return *((LiveVariablesImpl *) x);63}64 65//===----------------------------------------------------------------------===//66// Operations and queries on LivenessValues.67//===----------------------------------------------------------------------===//68 69bool LiveVariables::LivenessValues::isLive(const Expr *E) const {70 return liveExprs.contains(E);71}72 73bool LiveVariables::LivenessValues::isLive(const VarDecl *D) const {74 if (const auto *DD = dyn_cast<DecompositionDecl>(D)) {75 // Note: the only known case this condition is necessary, is when a bindig76 // to a tuple-like structure is created. The HoldingVar initializers have a77 // DeclRefExpr to the DecompositionDecl.78 if (liveDecls.contains(DD))79 return true;80 81 for (const BindingDecl *BD : DD->bindings()) {82 if (liveBindings.contains(BD))83 return true;84 }85 return false;86 }87 return liveDecls.contains(D);88}89 90namespace {91 template <typename SET>92 SET mergeSets(SET A, SET B) {93 if (A.isEmpty())94 return B;95 96 for (const auto *Elem : B) {97 A = A.add(Elem);98 }99 return A;100 }101} // namespace102 103void LiveVariables::Observer::anchor() { }104 105LiveVariables::LivenessValues106LiveVariablesImpl::merge(LiveVariables::LivenessValues valsA,107 LiveVariables::LivenessValues valsB) {108 109 llvm::ImmutableSetRef<const Expr *> SSetRefA(110 valsA.liveExprs.getRootWithoutRetain(), ESetFact.getTreeFactory()),111 SSetRefB(valsB.liveExprs.getRootWithoutRetain(),112 ESetFact.getTreeFactory());113 114 llvm::ImmutableSetRef<const VarDecl *>115 DSetRefA(valsA.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()),116 DSetRefB(valsB.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory());117 118 llvm::ImmutableSetRef<const BindingDecl *>119 BSetRefA(valsA.liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory()),120 BSetRefB(valsB.liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory());121 122 SSetRefA = mergeSets(SSetRefA, SSetRefB);123 DSetRefA = mergeSets(DSetRefA, DSetRefB);124 BSetRefA = mergeSets(BSetRefA, BSetRefB);125 126 // asImmutableSet() canonicalizes the tree, allowing us to do an easy127 // comparison afterwards.128 return LiveVariables::LivenessValues(SSetRefA.asImmutableSet(),129 DSetRefA.asImmutableSet(),130 BSetRefA.asImmutableSet());131}132 133bool LiveVariables::LivenessValues::operator==(const LivenessValues &V) const {134 return liveExprs == V.liveExprs && liveDecls == V.liveDecls &&135 liveBindings == V.liveBindings;136}137 138//===----------------------------------------------------------------------===//139// Query methods.140//===----------------------------------------------------------------------===//141 142static bool isAlwaysAlive(const VarDecl *D) {143 return D->hasGlobalStorage();144}145 146bool LiveVariables::isLive(const CFGBlock *B, const VarDecl *D) {147 return isAlwaysAlive(D) || getImpl(impl).blocksEndToLiveness[B].isLive(D);148}149 150bool LiveVariables::isLive(const Stmt *S, const VarDecl *D) {151 return isAlwaysAlive(D) || getImpl(impl).stmtsToLiveness[S].isLive(D);152}153 154bool LiveVariables::isLive(const Stmt *Loc, const Expr *Val) {155 return getImpl(impl).stmtsToLiveness[Loc].isLive(Val);156}157 158//===----------------------------------------------------------------------===//159// Dataflow computation.160//===----------------------------------------------------------------------===//161 162namespace {163class TransferFunctions : public StmtVisitor<TransferFunctions> {164 LiveVariablesImpl &LV;165 LiveVariables::LivenessValues &val;166 LiveVariables::Observer *observer;167 const CFGBlock *currentBlock;168public:169 TransferFunctions(LiveVariablesImpl &im,170 LiveVariables::LivenessValues &Val,171 LiveVariables::Observer *Observer,172 const CFGBlock *CurrentBlock)173 : LV(im), val(Val), observer(Observer), currentBlock(CurrentBlock) {}174 175 void VisitBinaryOperator(BinaryOperator *BO);176 void VisitBlockExpr(BlockExpr *BE);177 void VisitDeclRefExpr(DeclRefExpr *DR);178 void VisitDeclStmt(DeclStmt *DS);179 void VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS);180 void VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE);181 void Visit(Stmt *S);182};183} // namespace184 185static const VariableArrayType *FindVA(QualType Ty) {186 const Type *ty = Ty.getTypePtr();187 while (const ArrayType *VT = dyn_cast<ArrayType>(ty)) {188 if (const VariableArrayType *VAT = dyn_cast<VariableArrayType>(VT))189 if (VAT->getSizeExpr())190 return VAT;191 192 ty = VT->getElementType().getTypePtr();193 }194 195 return nullptr;196}197 198static const Expr *LookThroughExpr(const Expr *E) {199 while (E) {200 if (const Expr *Ex = dyn_cast<Expr>(E))201 E = Ex->IgnoreParens();202 if (const FullExpr *FE = dyn_cast<FullExpr>(E)) {203 E = FE->getSubExpr();204 continue;205 }206 if (const OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(E)) {207 E = OVE->getSourceExpr();208 continue;209 }210 break;211 }212 return E;213}214 215static void AddLiveExpr(llvm::ImmutableSet<const Expr *> &Set,216 llvm::ImmutableSet<const Expr *>::Factory &F,217 const Expr *E) {218 Set = F.add(Set, LookThroughExpr(E));219}220 221/// Add as a live expression all individual conditions in a logical expression.222/// For example, for the expression:223/// "(a < b) || (c && d && ((e || f) != (g && h)))"224/// the following expressions will be added as live:225/// "a < b", "c", "d", "((e || f) != (g && h))"226static void AddAllConditionalTerms(llvm::ImmutableSet<const Expr *> &Set,227 llvm::ImmutableSet<const Expr *>::Factory &F,228 const Expr *Cond) {229 AddLiveExpr(Set, F, Cond);230 if (auto const *BO = dyn_cast<BinaryOperator>(Cond->IgnoreParens());231 BO && BO->isLogicalOp()) {232 AddAllConditionalTerms(Set, F, BO->getLHS());233 AddAllConditionalTerms(Set, F, BO->getRHS());234 }235}236 237void TransferFunctions::Visit(Stmt *S) {238 if (observer)239 observer->observeStmt(S, currentBlock, val);240 241 StmtVisitor<TransferFunctions>::Visit(S);242 243 if (const auto *E = dyn_cast<Expr>(S)) {244 val.liveExprs = LV.ESetFact.remove(val.liveExprs, E);245 }246 247 // Mark all children expressions live.248 249 switch (S->getStmtClass()) {250 default:251 break;252 case Stmt::StmtExprClass: {253 // For statement expressions, look through the compound statement.254 S = cast<StmtExpr>(S)->getSubStmt();255 break;256 }257 case Stmt::CXXMemberCallExprClass: {258 // Include the implicit "this" pointer as being live.259 CXXMemberCallExpr *CE = cast<CXXMemberCallExpr>(S);260 if (Expr *ImplicitObj = CE->getImplicitObjectArgument()) {261 AddLiveExpr(val.liveExprs, LV.ESetFact, ImplicitObj);262 }263 break;264 }265 case Stmt::ObjCMessageExprClass: {266 // In calls to super, include the implicit "self" pointer as being live.267 ObjCMessageExpr *CE = cast<ObjCMessageExpr>(S);268 if (CE->getReceiverKind() == ObjCMessageExpr::SuperInstance)269 val.liveDecls = LV.DSetFact.add(val.liveDecls,270 LV.analysisContext.getSelfDecl());271 break;272 }273 case Stmt::DeclStmtClass: {274 const DeclStmt *DS = cast<DeclStmt>(S);275 if (const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl())) {276 for (const VariableArrayType* VA = FindVA(VD->getType());277 VA != nullptr; VA = FindVA(VA->getElementType())) {278 AddLiveExpr(val.liveExprs, LV.ESetFact, VA->getSizeExpr());279 }280 }281 break;282 }283 case Stmt::PseudoObjectExprClass: {284 // A pseudo-object operation only directly consumes its result285 // expression.286 Expr *child = cast<PseudoObjectExpr>(S)->getResultExpr();287 if (!child) return;288 if (OpaqueValueExpr *OV = dyn_cast<OpaqueValueExpr>(child))289 child = OV->getSourceExpr();290 child = child->IgnoreParens();291 val.liveExprs = LV.ESetFact.add(val.liveExprs, child);292 return;293 }294 295 // FIXME: These cases eventually shouldn't be needed.296 case Stmt::ExprWithCleanupsClass: {297 S = cast<ExprWithCleanups>(S)->getSubExpr();298 break;299 }300 case Stmt::CXXBindTemporaryExprClass: {301 S = cast<CXXBindTemporaryExpr>(S)->getSubExpr();302 break;303 }304 case Stmt::UnaryExprOrTypeTraitExprClass: {305 // No need to unconditionally visit subexpressions.306 return;307 }308 case Stmt::IfStmtClass: {309 // If one of the branches is an expression rather than a compound310 // statement, it will be bad if we mark it as live at the terminator311 // of the if-statement (i.e., immediately after the condition expression).312 AddLiveExpr(val.liveExprs, LV.ESetFact, cast<IfStmt>(S)->getCond());313 return;314 }315 case Stmt::WhileStmtClass: {316 // If the loop body is an expression rather than a compound statement,317 // it will be bad if we mark it as live at the terminator of the loop318 // (i.e., immediately after the condition expression).319 AddLiveExpr(val.liveExprs, LV.ESetFact, cast<WhileStmt>(S)->getCond());320 return;321 }322 case Stmt::DoStmtClass: {323 // If the loop body is an expression rather than a compound statement,324 // it will be bad if we mark it as live at the terminator of the loop325 // (i.e., immediately after the condition expression).326 AddLiveExpr(val.liveExprs, LV.ESetFact, cast<DoStmt>(S)->getCond());327 return;328 }329 case Stmt::ForStmtClass: {330 // If the loop body is an expression rather than a compound statement,331 // it will be bad if we mark it as live at the terminator of the loop332 // (i.e., immediately after the condition expression).333 AddLiveExpr(val.liveExprs, LV.ESetFact, cast<ForStmt>(S)->getCond());334 return;335 }336 case Stmt::ConditionalOperatorClass: {337 // Keep not only direct children alive, but also all the short-circuited338 // parts of the condition. Short-circuiting evaluation may cause the339 // conditional operator evaluation to skip the evaluation of the entire340 // condtion expression, so the value of the entire condition expression is341 // never computed.342 //343 // This makes a difference when we compare exploded nodes coming from true344 // and false expressions with no side effects: the only difference in the345 // state is the value of (part of) the condition.346 //347 // BinaryConditionalOperatorClass ('x ?: y') is not affected because it348 // explicitly calculates the value of the entire condition expression (to349 // possibly use as a value for the "true expr") even if it is350 // short-circuited.351 auto const *CO = cast<ConditionalOperator>(S);352 AddAllConditionalTerms(val.liveExprs, LV.ESetFact, CO->getCond());353 AddLiveExpr(val.liveExprs, LV.ESetFact, CO->getTrueExpr());354 AddLiveExpr(val.liveExprs, LV.ESetFact, CO->getFalseExpr());355 return;356 }357 }358 359 // HACK + FIXME: What is this? One could only guess that this is an attempt to360 // fish for live values, for example, arguments from a call expression.361 // Maybe we could take inspiration from UninitializedVariable analysis?362 for (Stmt *Child : S->children()) {363 if (const auto *E = dyn_cast_or_null<Expr>(Child))364 AddLiveExpr(val.liveExprs, LV.ESetFact, E);365 }366}367 368static bool writeShouldKill(const VarDecl *VD) {369 return VD && !VD->getType()->isReferenceType() &&370 !isAlwaysAlive(VD);371}372 373void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) {374 if (LV.killAtAssign && B->getOpcode() == BO_Assign) {375 if (const auto *DR = dyn_cast<DeclRefExpr>(B->getLHS()->IgnoreParens())) {376 LV.inAssignment.insert(DR);377 }378 }379 if (B->isAssignmentOp()) {380 if (!LV.killAtAssign)381 return;382 383 // Assigning to a variable?384 Expr *LHS = B->getLHS()->IgnoreParens();385 386 if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) {387 const Decl* D = DR->getDecl();388 bool Killed = false;389 390 if (const BindingDecl* BD = dyn_cast<BindingDecl>(D)) {391 Killed = !BD->getType()->isReferenceType();392 if (Killed) {393 if (const auto *HV = BD->getHoldingVar())394 val.liveDecls = LV.DSetFact.remove(val.liveDecls, HV);395 396 val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD);397 }398 } else if (const auto *VD = dyn_cast<VarDecl>(D)) {399 Killed = writeShouldKill(VD);400 if (Killed)401 val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);402 }403 }404 }405}406 407void 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 416void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) {417 const Decl* D = DR->getDecl();418 bool InAssignment = LV.inAssignment.contains(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 432void 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 HoldingVar443 // 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 452void 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 }468}469 470void TransferFunctions::471VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE)472{473 // While sizeof(var) doesn't technically extend the liveness of 'var', it474 // does extent the liveness of metadata if 'var' is a VariableArrayType.475 // We handle that special case here.476 if (UE->getKind() != UETT_SizeOf || UE->isArgumentType())477 return;478 479 const Expr *subEx = UE->getArgumentExpr();480 if (subEx->getType()->isVariableArrayType()) {481 assert(subEx->isLValue());482 val.liveExprs = LV.ESetFact.add(val.liveExprs, subEx->IgnoreParens());483 }484}485 486LiveVariables::LivenessValues487LiveVariablesImpl::runOnBlock(const CFGBlock *block,488 LiveVariables::LivenessValues val,489 LiveVariables::Observer *obs) {490 491 TransferFunctions TF(*this, val, obs, block);492 493 // Visit the terminator (if any).494 if (const Stmt *term = block->getTerminatorStmt())495 TF.Visit(const_cast<Stmt*>(term));496 497 // Apply the transfer function for all Stmts in the block.498 for (CFGBlock::const_reverse_iterator it = block->rbegin(),499 ei = block->rend(); it != ei; ++it) {500 const CFGElement &elem = *it;501 502 if (std::optional<CFGAutomaticObjDtor> Dtor =503 elem.getAs<CFGAutomaticObjDtor>()) {504 val.liveDecls = DSetFact.add(val.liveDecls, Dtor->getVarDecl());505 continue;506 }507 508 if (!elem.getAs<CFGStmt>())509 continue;510 511 const Stmt *S = elem.castAs<CFGStmt>().getStmt();512 TF.Visit(const_cast<Stmt*>(S));513 stmtsToLiveness[S] = val;514 }515 return val;516}517 518void LiveVariables::runOnAllBlocks(LiveVariables::Observer &obs) {519 const CFG *cfg = getImpl(impl).analysisContext.getCFG();520 for (CFGBlock *B : *cfg)521 getImpl(impl).runOnBlock(B, getImpl(impl).blocksEndToLiveness[B], &obs);522}523 524LiveVariables::LiveVariables(void *im) : impl(im) {}525 526LiveVariables::~LiveVariables() {527 delete (LiveVariablesImpl*) impl;528}529 530std::unique_ptr<LiveVariables>531LiveVariables::computeLiveness(AnalysisDeclContext &AC, bool killAtAssign) {532 533 // No CFG? Bail out.534 CFG *cfg = AC.getCFG();535 if (!cfg)536 return nullptr;537 538 // The analysis currently has scalability issues for very large CFGs.539 // Bail out if it looks too large.540 if (cfg->getNumBlockIDs() > 300000)541 return nullptr;542 543 LiveVariablesImpl *LV = new LiveVariablesImpl(AC, killAtAssign);544 545 // Construct the dataflow worklist. Enqueue the exit block as the546 // start of the analysis.547 BackwardDataflowWorklist worklist(*cfg, AC);548 llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs());549 550 // FIXME: we should enqueue using post order.551 for (const CFGBlock *B : cfg->nodes()) {552 worklist.enqueueBlock(B);553 }554 555 while (const CFGBlock *block = worklist.dequeue()) {556 // Determine if the block's end value has changed. If not, we557 // have nothing left to do for this block.558 LivenessValues &prevVal = LV->blocksEndToLiveness[block];559 560 // Merge the values of all successor blocks.561 LivenessValues val;562 for (const CFGBlock *succ : block->succs()) {563 if (succ) {564 val = LV->merge(val, LV->blocksBeginToLiveness[succ]);565 }566 }567 568 if (!everAnalyzedBlock[block->getBlockID()])569 everAnalyzedBlock[block->getBlockID()] = true;570 else if (prevVal == val)571 continue;572 573 prevVal = val;574 575 // Update the dataflow value for the start of this block.576 LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val);577 578 // Enqueue the value to the predecessors.579 worklist.enqueuePredecessors(block);580 }581 582 return std::unique_ptr<LiveVariables>(new LiveVariables(LV));583}584 585void LiveVariables::dumpBlockLiveness(const SourceManager &M) {586 getImpl(impl).dumpBlockLiveness(M);587}588 589void LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) {590 std::vector<const CFGBlock *> vec;591 vec.reserve(blocksEndToLiveness.size());592 llvm::append_range(vec, llvm::make_first_range(blocksEndToLiveness));593 llvm::sort(vec, [](const CFGBlock *A, const CFGBlock *B) {594 return A->getBlockID() < B->getBlockID();595 });596 597 std::vector<const VarDecl*> declVec;598 599 for (const CFGBlock *block : vec) {600 llvm::errs() << "\n[ B" << block->getBlockID()601 << " (live variables at block exit) ]\n";602 declVec.clear();603 llvm::append_range(declVec, blocksEndToLiveness[block].liveDecls);604 llvm::sort(declVec, [](const Decl *A, const Decl *B) {605 return A->getBeginLoc() < B->getBeginLoc();606 });607 608 for (const VarDecl *VD : declVec) {609 llvm::errs() << " " << VD->getDeclName().getAsString() << " <";610 VD->getLocation().print(llvm::errs(), M);611 llvm::errs() << ">\n";612 }613 }614 llvm::errs() << "\n";615}616 617void LiveVariables::dumpExprLiveness(const SourceManager &M) {618 getImpl(impl).dumpExprLiveness(M);619}620 621void LiveVariablesImpl::dumpExprLiveness(const SourceManager &M) {622 const ASTContext &Ctx = analysisContext.getASTContext();623 auto ByIDs = [&Ctx](const Expr *L, const Expr *R) {624 return L->getID(Ctx) < R->getID(Ctx);625 };626 627 // Don't iterate over blockEndsToLiveness directly because it's not sorted.628 for (const CFGBlock *B : *analysisContext.getCFG()) {629 llvm::errs() << "\n[ B" << B->getBlockID()630 << " (live expressions at block exit) ]\n";631 std::vector<const Expr *> LiveExprs;632 llvm::append_range(LiveExprs, blocksEndToLiveness[B].liveExprs);633 llvm::sort(LiveExprs, ByIDs);634 for (const Expr *E : LiveExprs) {635 llvm::errs() << "\n";636 E->dump();637 }638 llvm::errs() << "\n";639 }640}641 642const void *LiveVariables::getTag() { static int x; return &x; }643const void *RelaxedLiveVariables::getTag() { static int x; return &x; }644