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