LiveVariables.h revision 6bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89
1902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com//===- LiveVariables.h - Live Variable Analysis for Source CFGs -*- C++ --*-// 2902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com// 3902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com// The LLVM Compiler Infrastructure 4902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com// 5902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com// This file is distributed under the University of Illinois Open Source 6902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com// License. See LICENSE.TXT for details. 7902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com// 8902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com//===----------------------------------------------------------------------===// 9902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com// 10902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com// This file implements Live Variables analysis for source-level CFGs. 11902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com// 12902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com//===----------------------------------------------------------------------===// 13902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com 14902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com#ifndef LLVM_CLANG_LIVEVARIABLES_H 152a67e123a3e559774a16a58cbe5106bc0fb86740commit-bot@chromium.org#define LLVM_CLANG_LIVEVARIABLES_H 16902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com 178a1cdaece7e1d009befb84f21bb82370025bf4d6robertphillips@google.com#include "clang/AST/Decl.h" 1897cee9735350cb472249ce1a827ba1aa6b2a5f59chudy@google.com#include "clang/Analysis/AnalysisContext.h" 19902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com#include "llvm/ADT/DenseMap.h" 2032bbcf828d66ad244fa25b468bc3a229e531491frobertphillips@google.com#include "llvm/ADT/ImmutableSet.h" 2132bbcf828d66ad244fa25b468bc3a229e531491frobertphillips@google.com 2286681b37bd20204e47a492119b345c01d00bc939fmalita@google.comnamespace clang { 23902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com 2480a4a60f96c33ccd850f9b0eb4b69ab08c198196chudy@google.comclass CFG; 25f4741c1322944e194ca34a8f5cf8188fe2c0efe2robertphillips@google.comclass CFGBlock; 26902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.comclass Stmt; 27768ac85655017d4106444bf3ad044680a575ccaacommit-bot@chromium.orgclass DeclRefExpr; 28768ac85655017d4106444bf3ad044680a575ccaacommit-bot@chromium.orgclass SourceManager; 29768ac85655017d4106444bf3ad044680a575ccaacommit-bot@chromium.org 3057f74e0aa931e7784d47cba3ecc83020aa8e72b2commit-bot@chromium.orgclass LiveVariables : public ManagedAnalysis { 31902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.compublic: 32902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com class LivenessValues { 33f4741c1322944e194ca34a8f5cf8188fe2c0efe2robertphillips@google.com public: 34f4741c1322944e194ca34a8f5cf8188fe2c0efe2robertphillips@google.com 35f4741c1322944e194ca34a8f5cf8188fe2c0efe2robertphillips@google.com llvm::ImmutableSet<const Stmt *> liveStmts; 3657f74e0aa931e7784d47cba3ecc83020aa8e72b2commit-bot@chromium.org llvm::ImmutableSet<const VarDecl *> liveDecls; 3757f74e0aa931e7784d47cba3ecc83020aa8e72b2commit-bot@chromium.org 3857f74e0aa931e7784d47cba3ecc83020aa8e72b2commit-bot@chromium.org bool equals(const LivenessValues &V) const; 3957f74e0aa931e7784d47cba3ecc83020aa8e72b2commit-bot@chromium.org 4057f74e0aa931e7784d47cba3ecc83020aa8e72b2commit-bot@chromium.org LivenessValues() 412a67e123a3e559774a16a58cbe5106bc0fb86740commit-bot@chromium.org : liveStmts(nullptr), liveDecls(nullptr) {} 422a67e123a3e559774a16a58cbe5106bc0fb86740commit-bot@chromium.org 4357f74e0aa931e7784d47cba3ecc83020aa8e72b2commit-bot@chromium.org LivenessValues(llvm::ImmutableSet<const Stmt *> LiveStmts, 44f4741c1322944e194ca34a8f5cf8188fe2c0efe2robertphillips@google.com llvm::ImmutableSet<const VarDecl *> LiveDecls) 45f4741c1322944e194ca34a8f5cf8188fe2c0efe2robertphillips@google.com : liveStmts(LiveStmts), liveDecls(LiveDecls) {} 4632bbcf828d66ad244fa25b468bc3a229e531491frobertphillips@google.com 4732bbcf828d66ad244fa25b468bc3a229e531491frobertphillips@google.com ~LivenessValues() {} 48f84ad8f7fc0194389a8099da2c5e8fff9f092890skia.committer@gmail.com 4932bbcf828d66ad244fa25b468bc3a229e531491frobertphillips@google.com bool isLive(const Stmt *S) const; 5032bbcf828d66ad244fa25b468bc3a229e531491frobertphillips@google.com bool isLive(const VarDecl *D) const; 51902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com 52902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com friend class LiveVariables; 53902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com }; 54902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com 55902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com class Observer { 56902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com virtual void anchor(); 57902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com public: 58902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com virtual ~Observer() {} 59902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com 60902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com /// A callback invoked right before invoking the 610b5bbb0f82e022c8acfbcb6312f0ed18e1ab90cechudy@google.com /// liveness transfer function on the given statement. 620b5bbb0f82e022c8acfbcb6312f0ed18e1ab90cechudy@google.com virtual void observeStmt(const Stmt *S, 630b5bbb0f82e022c8acfbcb6312f0ed18e1ab90cechudy@google.com const CFGBlock *currentBlock, 64a9e937c7b712b024de108fa963f92d0e70e4a296chudy@google.com const LivenessValues& V) {} 65a9e937c7b712b024de108fa963f92d0e70e4a296chudy@google.com 66a9e937c7b712b024de108fa963f92d0e70e4a296chudy@google.com /// Called when the live variables analysis registers 67a9e937c7b712b024de108fa963f92d0e70e4a296chudy@google.com /// that a variable is killed. 68a9e937c7b712b024de108fa963f92d0e70e4a296chudy@google.com virtual void observerKill(const DeclRefExpr *DR) {} 69a9e937c7b712b024de108fa963f92d0e70e4a296chudy@google.com }; 70a9e937c7b712b024de108fa963f92d0e70e4a296chudy@google.com 71a9e937c7b712b024de108fa963f92d0e70e4a296chudy@google.com 72a9e937c7b712b024de108fa963f92d0e70e4a296chudy@google.com virtual ~LiveVariables(); 73a9e937c7b712b024de108fa963f92d0e70e4a296chudy@google.com 74a9e937c7b712b024de108fa963f92d0e70e4a296chudy@google.com /// Compute the liveness information for a given CFG. 75a9e937c7b712b024de108fa963f92d0e70e4a296chudy@google.com static LiveVariables *computeLiveness(AnalysisDeclContext &analysisContext, 76a9e937c7b712b024de108fa963f92d0e70e4a296chudy@google.com bool killAtAssign); 77a9e937c7b712b024de108fa963f92d0e70e4a296chudy@google.com 780b5bbb0f82e022c8acfbcb6312f0ed18e1ab90cechudy@google.com /// Return true if a variable is live at the end of a 790b5bbb0f82e022c8acfbcb6312f0ed18e1ab90cechudy@google.com /// specified block. 80830b8793bb1646bb76817bdc228dd8e2a92bef7dchudy@google.com bool isLive(const CFGBlock *B, const VarDecl *D); 81902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com 82902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com /// Returns true if a variable is live at the beginning of the 8350c84da68b17647371a81593402e897d639989e4robertphillips@google.com /// the statement. This query only works if liveness information 8450c84da68b17647371a81593402e897d639989e4robertphillips@google.com /// has been recorded at the statement level (see runOnAllBlocks), and 8550c84da68b17647371a81593402e897d639989e4robertphillips@google.com /// only returns liveness information for block-level expressions. 8650c84da68b17647371a81593402e897d639989e4robertphillips@google.com bool isLive(const Stmt *S, const VarDecl *D); 8750c84da68b17647371a81593402e897d639989e4robertphillips@google.com 8850c84da68b17647371a81593402e897d639989e4robertphillips@google.com /// Returns true the block-level expression "value" is live 89902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com /// before the given block-level expression (see runOnAllBlocks). 90902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com bool isLive(const Stmt *Loc, const Stmt *StmtVal); 91902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com 92902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com /// Print to stderr the liveness information associated with 93902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com /// each basic block. 94902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com void dumpBlockLiveness(const SourceManager& M); 9550c84da68b17647371a81593402e897d639989e4robertphillips@google.com 9650c84da68b17647371a81593402e897d639989e4robertphillips@google.com void runOnAllBlocks(Observer &obs); 9750c84da68b17647371a81593402e897d639989e4robertphillips@google.com 9850c84da68b17647371a81593402e897d639989e4robertphillips@google.com static LiveVariables *create(AnalysisDeclContext &analysisContext) { 9950c84da68b17647371a81593402e897d639989e4robertphillips@google.com return computeLiveness(analysisContext, true); 10050c84da68b17647371a81593402e897d639989e4robertphillips@google.com } 10150c84da68b17647371a81593402e897d639989e4robertphillips@google.com 102902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com static const void *getTag(); 103902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com 104902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.comprivate: 10597cee9735350cb472249ce1a827ba1aa6b2a5f59chudy@google.com LiveVariables(void *impl); 106902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com void *impl; 107902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com}; 1087e4cfbf144af7d530d552946cee2a21d30b9b50fchudy@google.com 1097e4cfbf144af7d530d552946cee2a21d30b9b50fchudy@google.comclass RelaxedLiveVariables : public LiveVariables { 1107e4cfbf144af7d530d552946cee2a21d30b9b50fchudy@google.compublic: 1117e4cfbf144af7d530d552946cee2a21d30b9b50fchudy@google.com static LiveVariables *create(AnalysisDeclContext &analysisContext) { 1127e4cfbf144af7d530d552946cee2a21d30b9b50fchudy@google.com return computeLiveness(analysisContext, false); 1137e4cfbf144af7d530d552946cee2a21d30b9b50fchudy@google.com } 114902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com 115902ebe5eb41a350b766238b3b103c22fe9fc0fb5chudy@google.com static const void *getTag(); 1164469938e92d779dff05e745559e67907bbf21e78reed@google.com}; 1178a1cdaece7e1d009befb84f21bb82370025bf4d6robertphillips@google.com 1182e71f1619d9a2c51c1292e618f42a56ad2da1de8skia.committer@gmail.com} // end namespace clang 119febc0ec41b4cff6ea69f2b89d72c0d330d198283robertphillips@google.com 120febc0ec41b4cff6ea69f2b89d72c0d330d198283robertphillips@google.com#endif 121febc0ec41b4cff6ea69f2b89d72c0d330d198283robertphillips@google.com