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 
47     bool isLive(const Stmt *S) const;
48     bool isLive(const VarDecl *D) const;
49 
50     friend class LiveVariables;
51   };
52 
53   class Observer {
54     virtual void anchor();
55   public:
~Observer()56     virtual ~Observer() {}
57 
58     /// A callback invoked right before invoking the
59     ///  liveness transfer function on the given statement.
observeStmt(const Stmt * S,const CFGBlock * currentBlock,const LivenessValues & V)60     virtual void observeStmt(const Stmt *S,
61                              const CFGBlock *currentBlock,
62                              const LivenessValues& V) {}
63 
64     /// Called when the live variables analysis registers
65     /// that a variable is killed.
observerKill(const DeclRefExpr * DR)66     virtual void observerKill(const DeclRefExpr *DR) {}
67   };
68 
69   ~LiveVariables() override;
70 
71   /// Compute the liveness information for a given CFG.
72   static LiveVariables *computeLiveness(AnalysisDeclContext &analysisContext,
73                                         bool killAtAssign);
74 
75   /// Return true if a variable is live at the end of a
76   /// specified block.
77   bool isLive(const CFGBlock *B, const VarDecl *D);
78 
79   /// Returns true if a variable is live at the beginning of the
80   ///  the statement.  This query only works if liveness information
81   ///  has been recorded at the statement level (see runOnAllBlocks), and
82   ///  only returns liveness information for block-level expressions.
83   bool isLive(const Stmt *S, const VarDecl *D);
84 
85   /// Returns true the block-level expression "value" is live
86   ///  before the given block-level expression (see runOnAllBlocks).
87   bool isLive(const Stmt *Loc, const Stmt *StmtVal);
88 
89   /// Print to stderr the liveness information associated with
90   /// each basic block.
91   void dumpBlockLiveness(const SourceManager& M);
92 
93   void runOnAllBlocks(Observer &obs);
94 
create(AnalysisDeclContext & analysisContext)95   static LiveVariables *create(AnalysisDeclContext &analysisContext) {
96     return computeLiveness(analysisContext, true);
97   }
98 
99   static const void *getTag();
100 
101 private:
102   LiveVariables(void *impl);
103   void *impl;
104 };
105 
106 class RelaxedLiveVariables : public LiveVariables {
107 public:
create(AnalysisDeclContext & analysisContext)108   static LiveVariables *create(AnalysisDeclContext &analysisContext) {
109     return computeLiveness(analysisContext, false);
110   }
111 
112   static const void *getTag();
113 };
114 
115 } // end namespace clang
116 
117 #endif
118