1 //===- LiveVariables.h - Live Variable Analysis for Source CFGs -*- 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 implements Live Variables analysis for source-level CFGs. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_LIVEVARIABLES_H 14 #define LLVM_CLANG_ANALYSIS_ANALYSES_LIVEVARIABLES_H 15 16 #include "clang/AST/Decl.h" 17 #include "clang/Analysis/AnalysisDeclContext.h" 18 #include "llvm/ADT/ImmutableSet.h" 19 20 namespace clang { 21 22 class CFG; 23 class CFGBlock; 24 class Stmt; 25 class DeclRefExpr; 26 class SourceManager; 27 28 class LiveVariables : public ManagedAnalysis { 29 public: 30 class LivenessValues { 31 public: 32 33 llvm::ImmutableSet<const Expr *> liveExprs; 34 llvm::ImmutableSet<const VarDecl *> liveDecls; 35 llvm::ImmutableSet<const BindingDecl *> liveBindings; 36 37 bool equals(const LivenessValues &V) const; 38 LivenessValues()39 LivenessValues() 40 : liveExprs(nullptr), liveDecls(nullptr), liveBindings(nullptr) {} 41 LivenessValues(llvm::ImmutableSet<const Expr * > liveExprs,llvm::ImmutableSet<const VarDecl * > LiveDecls,llvm::ImmutableSet<const BindingDecl * > LiveBindings)42 LivenessValues(llvm::ImmutableSet<const Expr *> liveExprs, 43 llvm::ImmutableSet<const VarDecl *> LiveDecls, 44 llvm::ImmutableSet<const BindingDecl *> LiveBindings) 45 : liveExprs(liveExprs), liveDecls(LiveDecls), 46 liveBindings(LiveBindings) {} 47 48 bool isLive(const Expr *E) const; 49 bool isLive(const VarDecl *D) const; 50 51 friend class LiveVariables; 52 }; 53 54 class Observer { 55 virtual void anchor(); 56 public: ~Observer()57 virtual ~Observer() {} 58 59 /// A callback invoked right before invoking the 60 /// liveness transfer function on the given statement. observeStmt(const Stmt * S,const CFGBlock * currentBlock,const LivenessValues & V)61 virtual void observeStmt(const Stmt *S, 62 const CFGBlock *currentBlock, 63 const LivenessValues& V) {} 64 65 /// Called when the live variables analysis registers 66 /// that a variable is killed. observerKill(const DeclRefExpr * DR)67 virtual void observerKill(const DeclRefExpr *DR) {} 68 }; 69 70 ~LiveVariables() override; 71 72 /// Compute the liveness information for a given CFG. 73 static std::unique_ptr<LiveVariables> 74 computeLiveness(AnalysisDeclContext &analysisContext, bool killAtAssign); 75 76 /// Return true if a variable is live at the end of a 77 /// specified block. 78 bool isLive(const CFGBlock *B, const VarDecl *D); 79 80 /// Returns true if a variable is live at the beginning of the 81 /// the statement. This query only works if liveness information 82 /// has been recorded at the statement level (see runOnAllBlocks), and 83 /// only returns liveness information for block-level expressions. 84 bool isLive(const Stmt *S, const VarDecl *D); 85 86 /// Returns true the block-level expression value is live 87 /// before the given block-level expression (see runOnAllBlocks). 88 bool isLive(const Stmt *Loc, const Expr *Val); 89 90 /// Print to stderr the variable liveness information associated with 91 /// each basic block. 92 void dumpBlockLiveness(const SourceManager &M); 93 94 /// Print to stderr the expression liveness information associated with 95 /// each basic block. 96 void dumpExprLiveness(const SourceManager &M); 97 98 void runOnAllBlocks(Observer &obs); 99 100 static std::unique_ptr<LiveVariables> create(AnalysisDeclContext & analysisContext)101 create(AnalysisDeclContext &analysisContext) { 102 return computeLiveness(analysisContext, true); 103 } 104 105 static const void *getTag(); 106 107 private: 108 LiveVariables(void *impl); 109 void *impl; 110 }; 111 112 class RelaxedLiveVariables : public LiveVariables { 113 public: 114 static std::unique_ptr<LiveVariables> create(AnalysisDeclContext & analysisContext)115 create(AnalysisDeclContext &analysisContext) { 116 return computeLiveness(analysisContext, false); 117 } 118 119 static const void *getTag(); 120 }; 121 122 } // end namespace clang 123 124 #endif 125