LiveVariables.h revision 848ec83483ca4ba52ed72c7e29ebc330f8c87252 
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_LIVEVARIABLES_H
15#define LLVM_CLANG_LIVEVARIABLES_H
16
17#include "clang/AST/Decl.h"
18#include "clang/Analysis/Support/BlkExprDeclBitVector.h"
19#include "clang/Analysis/FlowSensitive/DataflowValues.h"
20
21namespace clang {
22
23class Stmt;
24class DeclRefExpr;
25class SourceManager;
26class AnalysisContext;
27
28struct LiveVariables_ValueTypes {
29
30  struct ObserverTy;
31
32  // We keep dataflow state for declarations and block-level expressions;
33  typedef StmtDeclBitVector_Types::ValTy ValTy;
34
35  // We need to keep track of both declarations and CFGBlock-level expressions,
36  // (so that we don't explore such expressions twice).  We also want
37  // to compute liveness information for block-level expressions, since these
38  // act as "temporary" values.
39
40  struct AnalysisDataTy : public StmtDeclBitVector_Types::AnalysisDataTy {
41    ObserverTy* Observer;
42    ValTy AlwaysLive;
43    AnalysisContext *AC;
44    bool killAtAssign;
45
46    AnalysisDataTy() : Observer(NULL), AC(NULL), killAtAssign(true) {}
47  };
48
49  //===-----------------------------------------------------===//
50  // ObserverTy - Observer for uninitialized values queries.
51  //===-----------------------------------------------------===//
52
53  struct ObserverTy {
54    virtual ~ObserverTy() {}
55
56    /// ObserveStmt - A callback invoked right before invoking the
57    ///  liveness transfer function on the given statement.
58    virtual void ObserveStmt(Stmt* S, const CFGBlock *currentBlock,
59                             const AnalysisDataTy& AD,
60                             const ValTy& V) {}
61
62    virtual void ObserverKill(DeclRefExpr* DR) {}
63  };
64};
65
66class LiveVariables : public DataflowValues<LiveVariables_ValueTypes,
67                                            dataflow::backward_analysis_tag> {
68
69
70public:
71  typedef LiveVariables_ValueTypes::ObserverTy ObserverTy;
72
73  LiveVariables(AnalysisContext &AC, bool killAtAssign = true);
74
75  /// IsLive - Return true if a variable is live at the end of a
76  /// specified block.
77  bool isLive(const CFGBlock* B, const VarDecl* D) const;
78
79  /// IsLive - 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) const;
84
85  /// IsLive - 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) const;
88
89  /// IsLive - Return true if a variable is live according to the
90  ///  provided livness bitvector.
91  bool isLive(const ValTy& V, const VarDecl* D) const;
92
93  /// dumpLiveness - Print to stderr the liveness information encoded
94  ///  by a specified bitvector.
95  void dumpLiveness(const ValTy& V, const SourceManager& M) const;
96
97  /// dumpBlockLiveness - Print to stderr the liveness information
98  ///  associated with each basic block.
99  void dumpBlockLiveness(const SourceManager& M) const;
100
101  /// getNumDecls - Return the number of variables (declarations) that
102  ///  whose liveness status is being tracked by the dataflow
103  ///  analysis.
104  unsigned getNumDecls() const { return getAnalysisData().getNumDecls(); }
105
106  /// IntializeValues - This routine can perform extra initialization, but
107  ///  for LiveVariables this does nothing since all that logic is in
108  ///  the constructor.
109  void InitializeValues(const CFG& cfg) {}
110
111  void runOnCFG(CFG& cfg);
112
113  /// runOnAllBlocks - Propagate the dataflow values once for each block,
114  ///  starting from the current dataflow values.  'recordStmtValues' indicates
115  ///  whether the method should store dataflow values per each individual
116  ///  block-level expression.
117  void runOnAllBlocks(const CFG& cfg, ObserverTy* Obs,
118                      bool recordStmtValues=false);
119};
120
121} // end namespace clang
122
123#endif
124