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/AnalysisContext.h"
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/ImmutableSet.h"
21 
22 namespace clang {
23 
24 class CFG;
25 class CFGBlock;
26 class Stmt;
27 class DeclRefExpr;
28 class SourceManager;
29 
30 class LiveVariables : public ManagedAnalysis {
31 public:
32   class LivenessValues {
33   public:
34 
35     llvm::ImmutableSet<const Stmt *> liveStmts;
36     llvm::ImmutableSet<const VarDecl *> liveDecls;
37 
38     bool equals(const LivenessValues &V) const;
39 
LivenessValues()40     LivenessValues()
41       : liveStmts(nullptr), liveDecls(nullptr) {}
42 
LivenessValues(llvm::ImmutableSet<const Stmt * > LiveStmts,llvm::ImmutableSet<const VarDecl * > LiveDecls)43     LivenessValues(llvm::ImmutableSet<const Stmt *> LiveStmts,
44                    llvm::ImmutableSet<const VarDecl *> LiveDecls)
45       : liveStmts(LiveStmts), liveDecls(LiveDecls) {}
46 
~LivenessValues()47     ~LivenessValues() {}
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 
72   virtual ~LiveVariables();
73 
74   /// Compute the liveness information for a given CFG.
75   static LiveVariables *computeLiveness(AnalysisDeclContext &analysisContext,
76                                         bool killAtAssign);
77 
78   /// Return true if a variable is live at the end of a
79   /// specified block.
80   bool isLive(const CFGBlock *B, const VarDecl *D);
81 
82   /// Returns true if a variable is live at the beginning of the
83   ///  the statement.  This query only works if liveness information
84   ///  has been recorded at the statement level (see runOnAllBlocks), and
85   ///  only returns liveness information for block-level expressions.
86   bool isLive(const Stmt *S, const VarDecl *D);
87 
88   /// Returns true the block-level expression "value" is live
89   ///  before the given block-level expression (see runOnAllBlocks).
90   bool isLive(const Stmt *Loc, const Stmt *StmtVal);
91 
92   /// Print to stderr the liveness information associated with
93   /// each basic block.
94   void dumpBlockLiveness(const SourceManager& M);
95 
96   void runOnAllBlocks(Observer &obs);
97 
create(AnalysisDeclContext & analysisContext)98   static LiveVariables *create(AnalysisDeclContext &analysisContext) {
99     return computeLiveness(analysisContext, true);
100   }
101 
102   static const void *getTag();
103 
104 private:
105   LiveVariables(void *impl);
106   void *impl;
107 };
108 
109 class RelaxedLiveVariables : public LiveVariables {
110 public:
create(AnalysisDeclContext & analysisContext)111   static LiveVariables *create(AnalysisDeclContext &analysisContext) {
112     return computeLiveness(analysisContext, false);
113   }
114 
115   static const void *getTag();
116 };
117 
118 } // end namespace clang
119 
120 #endif
121