10b57cec5SDimitry Andric //===- LiveVariables.h - Live Variable Analysis for Source CFGs -*- C++ --*-// 20b57cec5SDimitry Andric // 30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 60b57cec5SDimitry Andric // 70b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 80b57cec5SDimitry Andric // 90b57cec5SDimitry Andric // This file implements Live Variables analysis for source-level CFGs. 100b57cec5SDimitry Andric // 110b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 120b57cec5SDimitry Andric 130b57cec5SDimitry Andric #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_LIVEVARIABLES_H 140b57cec5SDimitry Andric #define LLVM_CLANG_ANALYSIS_ANALYSES_LIVEVARIABLES_H 150b57cec5SDimitry Andric 160b57cec5SDimitry Andric #include "clang/AST/Decl.h" 170b57cec5SDimitry Andric #include "clang/Analysis/AnalysisDeclContext.h" 180b57cec5SDimitry Andric #include "llvm/ADT/ImmutableSet.h" 190b57cec5SDimitry Andric 200b57cec5SDimitry Andric namespace clang { 210b57cec5SDimitry Andric 220b57cec5SDimitry Andric class CFG; 230b57cec5SDimitry Andric class CFGBlock; 240b57cec5SDimitry Andric class Stmt; 250b57cec5SDimitry Andric class DeclRefExpr; 260b57cec5SDimitry Andric class SourceManager; 270b57cec5SDimitry Andric 280b57cec5SDimitry Andric class LiveVariables : public ManagedAnalysis { 290b57cec5SDimitry Andric public: 300b57cec5SDimitry Andric class LivenessValues { 310b57cec5SDimitry Andric public: 320b57cec5SDimitry Andric 330b57cec5SDimitry Andric llvm::ImmutableSet<const Expr *> liveExprs; 340b57cec5SDimitry Andric llvm::ImmutableSet<const VarDecl *> liveDecls; 350b57cec5SDimitry Andric llvm::ImmutableSet<const BindingDecl *> liveBindings; 360b57cec5SDimitry Andric 370b57cec5SDimitry Andric bool equals(const LivenessValues &V) const; 380b57cec5SDimitry Andric LivenessValues()390b57cec5SDimitry Andric LivenessValues() 400b57cec5SDimitry Andric : liveExprs(nullptr), liveDecls(nullptr), liveBindings(nullptr) {} 410b57cec5SDimitry Andric LivenessValues(llvm::ImmutableSet<const Expr * > liveExprs,llvm::ImmutableSet<const VarDecl * > LiveDecls,llvm::ImmutableSet<const BindingDecl * > LiveBindings)420b57cec5SDimitry Andric LivenessValues(llvm::ImmutableSet<const Expr *> liveExprs, 430b57cec5SDimitry Andric llvm::ImmutableSet<const VarDecl *> LiveDecls, 440b57cec5SDimitry Andric llvm::ImmutableSet<const BindingDecl *> LiveBindings) 450b57cec5SDimitry Andric : liveExprs(liveExprs), liveDecls(LiveDecls), 460b57cec5SDimitry Andric liveBindings(LiveBindings) {} 470b57cec5SDimitry Andric 480b57cec5SDimitry Andric bool isLive(const Expr *E) const; 490b57cec5SDimitry Andric bool isLive(const VarDecl *D) const; 500b57cec5SDimitry Andric 510b57cec5SDimitry Andric friend class LiveVariables; 520b57cec5SDimitry Andric }; 530b57cec5SDimitry Andric 540b57cec5SDimitry Andric class Observer { 550b57cec5SDimitry Andric virtual void anchor(); 560b57cec5SDimitry Andric public: ~Observer()570b57cec5SDimitry Andric virtual ~Observer() {} 580b57cec5SDimitry Andric 590b57cec5SDimitry Andric /// A callback invoked right before invoking the 600b57cec5SDimitry Andric /// liveness transfer function on the given statement. observeStmt(const Stmt * S,const CFGBlock * currentBlock,const LivenessValues & V)610b57cec5SDimitry Andric virtual void observeStmt(const Stmt *S, 620b57cec5SDimitry Andric const CFGBlock *currentBlock, 630b57cec5SDimitry Andric const LivenessValues& V) {} 640b57cec5SDimitry Andric 650b57cec5SDimitry Andric /// Called when the live variables analysis registers 660b57cec5SDimitry Andric /// that a variable is killed. observerKill(const DeclRefExpr * DR)670b57cec5SDimitry Andric virtual void observerKill(const DeclRefExpr *DR) {} 680b57cec5SDimitry Andric }; 690b57cec5SDimitry Andric 700b57cec5SDimitry Andric ~LiveVariables() override; 710b57cec5SDimitry Andric 720b57cec5SDimitry Andric /// Compute the liveness information for a given CFG. 730b57cec5SDimitry Andric static std::unique_ptr<LiveVariables> 740b57cec5SDimitry Andric computeLiveness(AnalysisDeclContext &analysisContext, bool killAtAssign); 750b57cec5SDimitry Andric 760b57cec5SDimitry Andric /// Return true if a variable is live at the end of a 770b57cec5SDimitry Andric /// specified block. 780b57cec5SDimitry Andric bool isLive(const CFGBlock *B, const VarDecl *D); 790b57cec5SDimitry Andric 800b57cec5SDimitry Andric /// Returns true if a variable is live at the beginning of the 810b57cec5SDimitry Andric /// the statement. This query only works if liveness information 820b57cec5SDimitry Andric /// has been recorded at the statement level (see runOnAllBlocks), and 830b57cec5SDimitry Andric /// only returns liveness information for block-level expressions. 840b57cec5SDimitry Andric bool isLive(const Stmt *S, const VarDecl *D); 850b57cec5SDimitry Andric 860b57cec5SDimitry Andric /// Returns true the block-level expression value is live 870b57cec5SDimitry Andric /// before the given block-level expression (see runOnAllBlocks). 880b57cec5SDimitry Andric bool isLive(const Stmt *Loc, const Expr *Val); 890b57cec5SDimitry Andric 900b57cec5SDimitry Andric /// Print to stderr the variable liveness information associated with 910b57cec5SDimitry Andric /// each basic block. 920b57cec5SDimitry Andric void dumpBlockLiveness(const SourceManager &M); 930b57cec5SDimitry Andric 940b57cec5SDimitry Andric /// Print to stderr the expression liveness information associated with 950b57cec5SDimitry Andric /// each basic block. 960b57cec5SDimitry Andric void dumpExprLiveness(const SourceManager &M); 970b57cec5SDimitry Andric 980b57cec5SDimitry Andric void runOnAllBlocks(Observer &obs); 990b57cec5SDimitry Andric 1000b57cec5SDimitry Andric static std::unique_ptr<LiveVariables> create(AnalysisDeclContext & analysisContext)1010b57cec5SDimitry Andric create(AnalysisDeclContext &analysisContext) { 1020b57cec5SDimitry Andric return computeLiveness(analysisContext, true); 1030b57cec5SDimitry Andric } 1040b57cec5SDimitry Andric 1050b57cec5SDimitry Andric static const void *getTag(); 1060b57cec5SDimitry Andric 1070b57cec5SDimitry Andric private: 1080b57cec5SDimitry Andric LiveVariables(void *impl); 1090b57cec5SDimitry Andric void *impl; 1100b57cec5SDimitry Andric }; 1110b57cec5SDimitry Andric 1120b57cec5SDimitry Andric class RelaxedLiveVariables : public LiveVariables { 1130b57cec5SDimitry Andric public: 1140b57cec5SDimitry Andric static std::unique_ptr<LiveVariables> create(AnalysisDeclContext & analysisContext)1150b57cec5SDimitry Andric create(AnalysisDeclContext &analysisContext) { 1160b57cec5SDimitry Andric return computeLiveness(analysisContext, false); 1170b57cec5SDimitry Andric } 1180b57cec5SDimitry Andric 1190b57cec5SDimitry Andric static const void *getTag(); 1200b57cec5SDimitry Andric }; 1210b57cec5SDimitry Andric 1220b57cec5SDimitry Andric } // end namespace clang 123 124 #endif 125