19 #include "llvm/ADT/DenseMap.h" 20 #include "llvm/ADT/PostOrderIterator.h" 21 #include "llvm/ADT/PriorityQueue.h" 22 #include "llvm/Support/raw_ostream.h" 26 using namespace clang;
30 class DataflowWorklist {
31 llvm::BitVector enqueuedBlocks;
33 llvm::PriorityQueue<const CFGBlock *, SmallVector<const CFGBlock *, 20>,
38 : enqueuedBlocks(cfg.getNumBlockIDs()),
40 worklist(POV->getComparator()) {}
42 void enqueueBlock(
const CFGBlock *block);
43 void enqueuePredecessors(
const CFGBlock *block);
51 if (block && !enqueuedBlocks[block->
getBlockID()]) {
57 void DataflowWorklist::enqueuePredecessors(
const clang::CFGBlock *block) {
59 E = block->
pred_end(); I != E; ++I) {
64 const CFGBlock *DataflowWorklist::dequeue() {
74 class LiveVariablesImpl {
77 llvm::ImmutableSet<const Stmt *>::Factory SSetFact;
78 llvm::ImmutableSet<const VarDecl *>::Factory DSetFact;
79 llvm::ImmutableSet<const BindingDecl *>::Factory BSetFact;
80 llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksEndToLiveness;
81 llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksBeginToLiveness;
82 llvm::DenseMap<const Stmt *, LiveVariables::LivenessValues> stmtsToLiveness;
83 llvm::DenseMap<const DeclRefExpr *, unsigned> inAssignment;
84 const bool killAtAssign;
98 : analysisContext(ac),
102 killAtAssign(KillAtAssign) {}
107 return *((LiveVariablesImpl *) x);
115 return liveStmts.contains(S);
119 if (
const auto *DD = dyn_cast<DecompositionDecl>(D)) {
122 alive |= liveBindings.contains(BD);
125 return liveDecls.contains(D);
129 template <
typename SET>
130 SET mergeSets(SET A, SET B) {
134 for (
typename SET::iterator it = B.begin(), ei = B.end(); it != ei; ++it) {
141 void LiveVariables::Observer::anchor() { }
147 llvm::ImmutableSetRef<const Stmt *>
148 SSetRefA(valsA.
liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory()),
149 SSetRefB(valsB.
liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory());
152 llvm::ImmutableSetRef<const VarDecl *>
153 DSetRefA(valsA.
liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()),
154 DSetRefB(valsB.
liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory());
156 llvm::ImmutableSetRef<const BindingDecl *>
157 BSetRefA(valsA.
liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory()),
158 BSetRefB(valsB.
liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory());
160 SSetRefA = mergeSets(SSetRefA, SSetRefB);
161 DSetRefA = mergeSets(DSetRefA, DSetRefB);
162 BSetRefA = mergeSets(BSetRefA, BSetRefB);
167 DSetRefA.asImmutableSet(),
168 BSetRefA.asImmutableSet());
192 return getImpl(impl).stmtsToLiveness[Loc].isLive(S);
200 class TransferFunctions :
public StmtVisitor<TransferFunctions> {
201 LiveVariablesImpl &LV;
206 TransferFunctions(LiveVariablesImpl &im,
210 : LV(im), val(Val), observer(Observer), currentBlock(CurrentBlock) {}
225 while (
const ArrayType *VT = dyn_cast<ArrayType>(ty)) {
227 if (VAT->getSizeExpr())
230 ty = VT->getElementType().getTypePtr();
238 if (
const Expr *Ex = dyn_cast<Expr>(S))
239 S = Ex->IgnoreParens();
240 if (
const FullExpr *FE = dyn_cast<FullExpr>(S)) {
241 S = FE->getSubExpr();
245 S = OVE->getSourceExpr();
254 llvm::ImmutableSet<const Stmt *>::Factory &F,
259 void TransferFunctions::Visit(
Stmt *S) {
261 observer->observeStmt(S, currentBlock, val);
266 val.liveStmts = LV.SSetFact.remove(val.liveStmts, S);
274 case Stmt::StmtExprClass: {
276 S = cast<StmtExpr>(S)->getSubStmt();
279 case Stmt::CXXMemberCallExprClass: {
283 AddLiveStmt(val.liveStmts, LV.SSetFact, ImplicitObj);
287 case Stmt::ObjCMessageExprClass: {
291 val.liveDecls = LV.DSetFact.add(val.liveDecls,
292 LV.analysisContext.getSelfDecl());
295 case Stmt::DeclStmtClass: {
296 const DeclStmt *DS = cast<DeclStmt>(S);
299 VA !=
nullptr; VA =
FindVA(VA->getElementType())) {
300 AddLiveStmt(val.liveStmts, LV.SSetFact, VA->getSizeExpr());
305 case Stmt::PseudoObjectExprClass: {
308 Expr *child = cast<PseudoObjectExpr>(S)->getResultExpr();
311 child = OV->getSourceExpr();
313 val.liveStmts = LV.SSetFact.add(val.liveStmts, child);
318 case Stmt::ExprWithCleanupsClass: {
319 S = cast<ExprWithCleanups>(S)->getSubExpr();
322 case Stmt::CXXBindTemporaryExprClass: {
323 S = cast<CXXBindTemporaryExpr>(S)->getSubExpr();
326 case Stmt::UnaryExprOrTypeTraitExprClass: {
330 case Stmt::IfStmtClass: {
334 AddLiveStmt(val.liveStmts, LV.SSetFact, cast<IfStmt>(S)->getCond());
337 case Stmt::WhileStmtClass: {
341 AddLiveStmt(val.liveStmts, LV.SSetFact, cast<WhileStmt>(S)->getCond());
344 case Stmt::DoStmtClass: {
348 AddLiveStmt(val.liveStmts, LV.SSetFact, cast<DoStmt>(S)->getCond());
351 case Stmt::ForStmtClass: {
355 AddLiveStmt(val.liveStmts, LV.SSetFact, cast<ForStmt>(S)->getCond());
374 if (!LV.killAtAssign)
380 if (
DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) {
381 const Decl* D = DR->getDecl();
384 if (
const BindingDecl* BD = dyn_cast<BindingDecl>(D)) {
385 Killed = !BD->getType()->isReferenceType();
387 val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD);
388 }
else if (
const auto *VD = dyn_cast<VarDecl>(D)) {
391 val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
395 if (Killed && observer)
396 observer->observerKill(DR);
401 void TransferFunctions::VisitBlockExpr(
BlockExpr *BE) {
403 LV.analysisContext.getReferencedBlockVars(BE->
getBlockDecl())) {
406 val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
410 void TransferFunctions::VisitDeclRefExpr(
DeclRefExpr *DR) {
412 bool InAssignment = LV.inAssignment[DR];
413 if (
const auto *BD = dyn_cast<BindingDecl>(D)) {
415 val.liveBindings = LV.BSetFact.
add(val.liveBindings, BD);
416 }
else if (
const auto *VD = dyn_cast<VarDecl>(D)) {
418 val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
422 void TransferFunctions::VisitDeclStmt(
DeclStmt *DS) {
423 for (
const auto *DI : DS->
decls()) {
424 if (
const auto *DD = dyn_cast<DecompositionDecl>(DI)) {
425 for (
const auto *BD : DD->bindings())
426 val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD);
427 }
else if (
const auto *VD = dyn_cast<VarDecl>(DI)) {
429 val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
440 if (
DeclStmt *DS = dyn_cast<DeclStmt>(element)) {
443 else if ((DR = dyn_cast<DeclRefExpr>(cast<Expr>(element)->IgnoreParens()))) {
444 VD = cast<VarDecl>(DR->
getDecl());
448 val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
450 observer->observerKill(DR);
454 void TransferFunctions::
466 val.liveStmts = LV.SSetFact.add(val.liveStmts, subEx->
IgnoreParens());
470 void TransferFunctions::VisitUnaryOperator(
UnaryOperator *UO) {
489 if (isa<VarDecl>(D) || isa<BindingDecl>(D)) {
491 observer->observerKill(DR);
501 TransferFunctions TF(*
this, val, obs, block);
505 TF.Visit(const_cast<Stmt*>(term));
509 ei = block->
rend(); it != ei; ++it) {
522 TF.Visit(const_cast<Stmt*>(S));
523 stmtsToLiveness[S] = val;
529 const CFG *cfg =
getImpl(impl).analysisContext.getCFG();
531 getImpl(impl).runOnBlock(*it,
getImpl(impl).blocksEndToLiveness[*it], &obs);
534 LiveVariables::LiveVariables(
void *im) : impl(im) {}
537 delete (LiveVariablesImpl*) impl;
554 LiveVariablesImpl *LV =
new LiveVariablesImpl(AC, killAtAssign);
558 DataflowWorklist worklist(*cfg, AC);
564 worklist.enqueueBlock(block);
575 if (
const auto *BO = dyn_cast<BinaryOperator>(stmt)) {
576 if (BO->getOpcode() == BO_Assign) {
578 dyn_cast<DeclRefExpr>(BO->getLHS()->IgnoreParens())) {
579 LV->inAssignment[DR] = 1;
587 while (
const CFGBlock *block = worklist.dequeue()) {
595 ei = block->
succ_end(); it != ei; ++it) {
597 val = LV->merge(val, LV->blocksBeginToLiveness[succ]);
602 everAnalyzedBlock[block->
getBlockID()] =
true;
603 else if (prevVal.
equals(val))
609 LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val);
612 worklist.enqueuePredecessors(block);
619 getImpl(impl).dumpBlockLiveness(M);
622 void LiveVariablesImpl::dumpBlockLiveness(
const SourceManager &M) {
623 std::vector<const CFGBlock *> vec;
624 for (llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues>::iterator
625 it = blocksEndToLiveness.begin(), ei = blocksEndToLiveness.end();
627 vec.push_back(it->first);
633 std::vector<const VarDecl*> declVec;
635 for (std::vector<const CFGBlock *>::iterator
636 it = vec.begin(), ei = vec.end(); it != ei; ++it) {
637 llvm::errs() <<
"\n[ B" << (*it)->getBlockID()
638 <<
" (live variables at block exit) ]\n";
643 for (llvm::ImmutableSet<const VarDecl *>::iterator si =
645 se = vals.
liveDecls.end(); si != se; ++si) {
646 declVec.push_back(*si);
649 llvm::sort(declVec, [](
const Decl *A,
const Decl *B) {
653 for (std::vector<const VarDecl*>::iterator di = declVec.begin(),
654 de = declVec.end(); di != de; ++di) {
655 llvm::errs() <<
" " << (*di)->getDeclName().getAsString()
657 (*di)->getLocation().print(llvm::errs(), M);
658 llvm::errs() <<
">\n";
661 llvm::errs() <<
"\n";
665 getImpl(impl).dumpStmtLiveness(M);
668 void LiveVariablesImpl::dumpStmtLiveness(
const SourceManager &M) {
670 for (
auto I : *analysisContext.getCFG()) {
672 llvm::errs() <<
"\n[ B" << I->getBlockID()
673 <<
" (live statements at block exit) ]\n";
674 for (
auto S : blocksEndToLiveness[I].liveStmts) {
675 llvm::errs() <<
"\n";
678 llvm::errs() <<
"\n";
The receiver is the instance of the superclass object.
const BlockDecl * getBlockDecl() const
static const VariableArrayType * FindVA(QualType Ty)
A (possibly-)qualified type.
static bool isAlwaysAlive(const VarDecl *D)
static const Stmt * LookThroughStmt(const Stmt *S)
AdjacentBlocks::const_iterator const_pred_iterator
static LiveVariables * computeLiveness(AnalysisDeclContext &analysisContext, bool killAtAssign)
Compute the liveness information for a given CFG.
const internal::VariadicAllOfMatcher< Stmt > stmt
Matches statements.
succ_iterator succ_begin()
Stmt - This represents one statement.
unsigned getBlockID() const
Decl - This represents one declaration (or definition), e.g.
Expr * getImplicitObjectArgument() const
Retrieve the implicit object argument for the member call.
SourceLocation getBeginLoc() const LLVM_READONLY
The base class of the type hierarchy.
Represents an array type, per C99 6.7.5.2 - Array Declarators.
T castAs() const
Convert to the specified CFGElement type, asserting that this CFGElement is of the desired type...
static const void * getTag()
Represents a variable declaration or definition.
llvm::ImmutableSet< const BindingDecl * > liveBindings
bool equals(const LivenessValues &V) const
static bool isAssignmentOp(Opcode Opc)
bool isVariableArrayType() const
FullExpr - Represents a "full-expression" node.
AnalysisDeclContext contains the context data for the function or method under analysis.
Represents C++ object destructor implicitly generated for automatic object or temporary bound to cons...
bool isReferenceType() const
void runOnAllBlocks(Observer &obs)
AdjacentBlocks::const_iterator const_succ_iterator
static bool runOnBlock(const CFGBlock *block, const CFG &cfg, AnalysisDeclContext &ac, CFGBlockValues &vals, const ClassifyRefs &classification, llvm::BitVector &wasAnalyzed, UninitVariablesHandler &handler)
bool isLive(const CFGBlock *B, const VarDecl *D)
Return true if a variable is live at the end of a specified block.
A builtin binary operation expression such as "x + y" or "x <= y".
const Type * getTypePtr() const
Retrieves a pointer to the underlying (unqualified) type.
A binding in a decomposition declaration.
~LiveVariables() override
CFGBlockListTy::const_iterator const_iterator
static const void * getTag()
UnaryExprOrTypeTraitExpr - expression with either a type or (unevaluated) expression operand...
Represents a single basic block in a source-level CFG.
This represents one expression.
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt...
BlockExpr - Adaptor class for mixing a BlockDecl with expressions.
ElementList::const_iterator const_iterator
An expression that sends a message to the given Objective-C object or class.
UnaryOperator - This represents the unary-expression's (except sizeof and alignof), the postinc/postdec operators from postfix-expression, and various extensions.
static LiveVariablesImpl & getImpl(void *x)
ReceiverKind getReceiverKind() const
Determine the kind of receiver that this message is being sent to.
reverse_iterator rbegin()
OpaqueValueExpr - An expression referring to an opaque object of a fixed type and value class...
void dumpBlockLiveness(const SourceManager &M)
Print to stderr the variable liveness information associated with each basic block.
Expr * getSubExpr() const
static void AddLiveStmt(llvm::ImmutableSet< const Stmt *> &Set, llvm::ImmutableSet< const Stmt *>::Factory &F, const Stmt *S)
Represents a call to a member function that may be written either with member call syntax (e...
DeclStmt - Adaptor class for mixing declarations with statements and expressions. ...
llvm::ImmutableSet< const VarDecl * > liveDecls
StmtVisitor - This class implements a simple visitor for Stmt subclasses.
bool hasGlobalStorage() const
Returns true for all variables that do not have local storage.
UnaryExprOrTypeTrait getKind() const
bool isLValue() const
isLValue - True if this expression is an "l-value" according to the rules of the current language...
unsigned getNumBlockIDs() const
Returns the total number of BlockIDs allocated (which start at 0).
bool isArgumentType() const
Optional< T > getAs() const
Convert to the specified CFGElement type, returning None if this CFGElement is not of the desired typ...
pred_iterator pred_begin()
Dataflow Directional Tag Classes.
bool isLive(const Stmt *S) const
StmtClass getStmtClass() const
const Decl * getSingleDecl() const
Stmt * getTerminatorStmt()
llvm::ImmutableSet< const Stmt * > liveStmts
void dump() const
Dumps the specified AST fragment and all subtrees to llvm::errs().
Represents Objective-C's collection statement.
void dumpStmtLiveness(const SourceManager &M)
Print to stderr the statement liveness information associated with each basic block.
Represents a top-level expression in a basic block.
RetTy Visit(PTR(Stmt) S, ParamTys... P)
A reference to a declared variable, function, enum, etc.
Represents a C array with a specified size that is not an integer-constant-expression.
static bool writeShouldKill(const VarDecl *VD)
This class handles loading and caching of source files into memory.
Expr * IgnoreParens() LLVM_READONLY
Skip past any parentheses which might surround this expression until reaching a fixed point...