LiveVariables.h revision 79649dfed2fc4b8cf0f7b6890df69458dbceeb04 
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/ExprDeclBitVector.h"
19#include "clang/Analysis/FlowSensitive/DataflowValues.h"
20
21namespace clang {
22
23class Stmt;
24class DeclRefExpr;
25class SourceManager;
26
27struct LiveVariables_ValueTypes {
28
29  struct ObserverTy;
30
31
32  // We need to keep track of both declarations and CFGBlock-level expressions,
33  // (so that we don't explore such expressions twice), but we only need
34  // liveness information for declarations (hence
35  // ValTy = DeclBitVector_Types::ValTy instead of
36  // ValTy = ExprDeclBitVector_Types::ValTy).
37
38  struct AnalysisDataTy : public ExprDeclBitVector_Types::AnalysisDataTy {
39    ObserverTy* Observer;
40
41    AnalysisDataTy() : Observer(NULL) {}
42  };
43
44    // We only keep actual dataflow state for declarations.
45  typedef DeclBitVector_Types::ValTy ValTy;
46
47  //===-----------------------------------------------------===//
48  // ObserverTy - Observer for uninitialized values queries.
49  //===-----------------------------------------------------===//
50
51  struct ObserverTy {
52    virtual ~ObserverTy() {}
53
54    /// ObserveStmt - A callback invoked right before invoking the
55    ///  liveness transfer function on the given statement.
56    virtual void ObserveStmt(Stmt* S, const AnalysisDataTy& AD,
57                             const ValTy& V) {}
58
59    virtual void ObserverKill(DeclRefExpr* DR) {}
60  };
61};
62
63class LiveVariables : public DataflowValues<LiveVariables_ValueTypes,
64                                            dataflow::backward_analysis_tag> {
65public:
66  typedef LiveVariables_ValueTypes::ObserverTy ObserverTy;
67
68  LiveVariables(CFG& cfg) { getAnalysisData().setCFG(&cfg); }
69
70  /// IsLive - Return true if a variable is live at beginning of a
71  /// specified block.
72  bool isLive(const CFGBlock* B, const VarDecl* D) const;
73
74  /// IsLive - Returns true if a variable is live at the beginning of the
75  ///  the statement.  This query only works if liveness information
76  ///  has been recorded at the statement level (see runOnAllBlocks), and
77  ///  only returns liveness information for block-level expressions.
78  bool isLive(const Stmt* S, const VarDecl* D) const;
79
80  /// IsLive - Return true if a variable is live according to the
81  ///  provided livness bitvector.
82  bool isLive(const ValTy& V, const VarDecl* D) const;
83
84  /// dumpLiveness - Print to stderr the liveness information encoded
85  ///  by a specified bitvector.
86  void dumpLiveness(const ValTy& V, SourceManager& M) const;
87
88  /// dumpBlockLiveness - Print to stderr the liveness information
89  ///  associated with each basic block.
90  void dumpBlockLiveness(SourceManager& M) const;
91
92  /// getNumDecls - Return the number of variables (declarations) that
93  ///  whose liveness status is being tracked by the dataflow
94  ///  analysis.
95  unsigned getNumDecls() const { return getAnalysisData().getNumDecls(); }
96
97  /// IntializeValues - Create initial dataflow values and meta data for
98  ///  a given CFG.  This is intended to be called by the dataflow solver.
99  void InitializeValues(const CFG& cfg);
100
101  void runOnCFG(CFG& cfg);
102
103  /// runOnAllBlocks - Propagate the dataflow values once for each block,
104  ///  starting from the current dataflow values.  'recordStmtValues' indicates
105  ///  whether the method should store dataflow values per each individual
106  ///  block-level expression.
107  void runOnAllBlocks(const CFG& cfg, ObserverTy* Obs,
108                      bool recordStmtValues=false);
109};
110
111} // end namespace clang
112
113#endif
114