contrib/llvm/tools/clang/lib/Analysis/LiveVariables.cpp

   1 //=- LiveVariables.cpp - 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 #include "clang/Analysis/Analyses/LiveVariables.h"
  15 #include "clang/Basic/SourceManager.h"
  16 #include "clang/AST/ASTContext.h"
  17 #include "clang/AST/Expr.h"
  18 #include "clang/Analysis/CFG.h"
  19 #include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h"
  20 #include "clang/Analysis/FlowSensitive/DataflowSolver.h"
  21 #include "clang/Analysis/Support/SaveAndRestore.h"
  22 #include "clang/Analysis/AnalysisContext.h"
  23 #include "llvm/ADT/SmallPtrSet.h"
  24 #include "llvm/ADT/SmallVector.h"
  25 #include "llvm/Support/raw_ostream.h"
  26
  27 using namespace clang;
  28
  29 //===----------------------------------------------------------------------===//
  30 // Useful constants.
  31 //===----------------------------------------------------------------------===//
  32
  33 static const bool Alive = true;
  34 static const bool Dead = false;
  35
  36 //===----------------------------------------------------------------------===//
  37 // Dataflow initialization logic.
  38 //===----------------------------------------------------------------------===//
  39
  40 namespace {
  41 class RegisterDecls
  42   : public CFGRecStmtDeclVisitor<RegisterDecls> {
  43
  44   LiveVariables::AnalysisDataTy& AD;
  45
  46   typedef llvm::SmallVector<VarDecl*, 20> AlwaysLiveTy;
  47   AlwaysLiveTy AlwaysLive;
  48
  49
  50 public:
  51   RegisterDecls(LiveVariables::AnalysisDataTy& ad) : AD(ad) {}
  52
  53   ~RegisterDecls() {
  54
  55     AD.AlwaysLive.resetValues(AD);
  56
  57     for (AlwaysLiveTy::iterator I = AlwaysLive.begin(), E = AlwaysLive.end();
  58          I != E; ++ I)
  59       AD.AlwaysLive(*I, AD) = Alive;
  60   }
  61
  62   void VisitImplicitParamDecl(ImplicitParamDecl* IPD) {
  63     // Register the VarDecl for tracking.
  64     AD.Register(IPD);
  65   }
  66
  67   void VisitVarDecl(VarDecl* VD) {
  68     // Register the VarDecl for tracking.
  69     AD.Register(VD);
  70
  71     // Does the variable have global storage?  If so, it is always live.
  72     if (VD->hasGlobalStorage())
  73       AlwaysLive.push_back(VD);
  74   }
  75
  76   CFG& getCFG() { return AD.getCFG(); }
  77 };
  78 } // end anonymous namespace
  79
  80 LiveVariables::LiveVariables(AnalysisContext &AC, bool killAtAssign) {
  81   // Register all referenced VarDecls.
  82   CFG &cfg = *AC.getCFG();
  83   getAnalysisData().setCFG(cfg);
  84   getAnalysisData().setContext(AC.getASTContext());
  85   getAnalysisData().AC = &AC;
  86   getAnalysisData().killAtAssign = killAtAssign;
  87
  88   RegisterDecls R(getAnalysisData());
  89   cfg.VisitBlockStmts(R);
  90
  91   // Register all parameters even if they didn't occur in the function body.
  92   if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(AC.getDecl()))
  93     for (FunctionDecl::param_const_iterator PI = FD->param_begin(),
  94            PE = FD->param_end(); PI != PE; ++PI)
  95       getAnalysisData().Register(*PI);
  96 }
  97
  98 //===----------------------------------------------------------------------===//
  99 // Transfer functions.
 100 //===----------------------------------------------------------------------===//
 101
 102 namespace {
 103
 104 class TransferFuncs : public CFGRecStmtVisitor<TransferFuncs>{
 105   LiveVariables::AnalysisDataTy& AD;
 106   LiveVariables::ValTy LiveState;
 107   const CFGBlock *currentBlock;
 108 public:
 109   TransferFuncs(LiveVariables::AnalysisDataTy& ad) : AD(ad), currentBlock(0) {}
 110
 111   LiveVariables::ValTy& getVal() { return LiveState; }
 112   CFG& getCFG() { return AD.getCFG(); }
 113
 114   void VisitDeclRefExpr(DeclRefExpr* DR);
 115   void VisitBinaryOperator(BinaryOperator* B);
 116   void VisitBlockExpr(BlockExpr *B);
 117   void VisitAssign(BinaryOperator* B);
 118   void VisitDeclStmt(DeclStmt* DS);
 119   void BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S);
 120   void VisitUnaryOperator(UnaryOperator* U);
 121   void Visit(Stmt *S);
 122   void VisitTerminator(CFGBlock* B);
 123
 124   /// VisitConditionVariableInit - Handle the initialization of condition
 125   ///  variables at branches.  Valid statements include IfStmt, ForStmt,
 126   ///  WhileStmt, and SwitchStmt.
 127   void VisitConditionVariableInit(Stmt *S);
 128
 129   void SetTopValue(LiveVariables::ValTy& V) {
 130     V = AD.AlwaysLive;
 131   }
 132
 133   void setCurrentBlock(const CFGBlock *block) {
 134     currentBlock = block;
 135   }
 136 };
 137
 138 void TransferFuncs::Visit(Stmt *S) {
 139
 140   if (S == getCurrentBlkStmt()) {
 141
 142     if (AD.Observer)
 143       AD.Observer->ObserveStmt(S, currentBlock, AD, LiveState);
 144
 145     if (getCFG().isBlkExpr(S))
 146       LiveState(S, AD) = Dead;
 147
 148     StmtVisitor<TransferFuncs,void>::Visit(S);
 149   }
 150   else if (!getCFG().isBlkExpr(S)) {
 151
 152     if (AD.Observer)
 153       AD.Observer->ObserveStmt(S, currentBlock, AD, LiveState);
 154
 155     StmtVisitor<TransferFuncs,void>::Visit(S);
 156
 157   }
 158   else {
 159     // For block-level expressions, mark that they are live.
 160     LiveState(S, AD) = Alive;
 161   }
 162 }
 163
 164 void TransferFuncs::VisitConditionVariableInit(Stmt *S) {
 165   assert(!getCFG().isBlkExpr(S));
 166   CFGRecStmtVisitor<TransferFuncs>::VisitConditionVariableInit(S);
 167 }
 168
 169 void TransferFuncs::VisitTerminator(CFGBlock* B) {
 170
 171   const Stmt* E = B->getTerminatorCondition();
 172
 173   if (!E)
 174     return;
 175
 176   assert (getCFG().isBlkExpr(E));
 177   LiveState(E, AD) = Alive;
 178 }
 179
 180 void TransferFuncs::VisitDeclRefExpr(DeclRefExpr* DR) {
 181   if (VarDecl* V = dyn_cast<VarDecl>(DR->getDecl()))
 182     LiveState(V, AD) = Alive;
 183 }
 184
 185 void TransferFuncs::VisitBlockExpr(BlockExpr *BE) {
 186   AnalysisContext::referenced_decls_iterator I, E;
 187   llvm::tie(I, E) = AD.AC->getReferencedBlockVars(BE->getBlockDecl());
 188   for ( ; I != E ; ++I) {
 189     DeclBitVector_Types::Idx i = AD.getIdx(*I);
 190     if (i.isValid())
 191       LiveState.getBit(i) = Alive;
 192   }
 193 }
 194
 195 void TransferFuncs::VisitBinaryOperator(BinaryOperator* B) {
 196   if (B->isAssignmentOp()) VisitAssign(B);
 197   else VisitStmt(B);
 198 }
 199
 200 void
 201 TransferFuncs::BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) {
 202
 203   // This is a block-level expression.  Its value is 'dead' before this point.
 204   LiveState(S, AD) = Dead;
 205
 206   // This represents a 'use' of the collection.
 207   Visit(S->getCollection());
 208
 209   // This represents a 'kill' for the variable.
 210   Stmt* Element = S->getElement();
 211   DeclRefExpr* DR = 0;
 212   VarDecl* VD = 0;
 213
 214   if (DeclStmt* DS = dyn_cast<DeclStmt>(Element))
 215     VD = cast<VarDecl>(DS->getSingleDecl());
 216   else {
 217     Expr* ElemExpr = cast<Expr>(Element)->IgnoreParens();
 218     if ((DR = dyn_cast<DeclRefExpr>(ElemExpr)))
 219       VD = cast<VarDecl>(DR->getDecl());
 220     else {
 221       Visit(ElemExpr);
 222       return;
 223     }
 224   }
 225
 226   if (VD) {
 227     LiveState(VD, AD) = Dead;
 228     if (AD.Observer && DR) { AD.Observer->ObserverKill(DR); }
 229   }
 230 }
 231
 232
 233 void TransferFuncs::VisitUnaryOperator(UnaryOperator* U) {
 234   Expr *E = U->getSubExpr();
 235
 236   switch (U->getOpcode()) {
 237   case UO_PostInc:
 238   case UO_PostDec:
 239   case UO_PreInc:
 240   case UO_PreDec:
 241     // Walk through the subexpressions, blasting through ParenExprs
 242     // until we either find a DeclRefExpr or some non-DeclRefExpr
 243     // expression.
 244     if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E->IgnoreParens()))
 245       if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) {
 246         // Treat the --/++ operator as a kill.
 247         if (AD.Observer) { AD.Observer->ObserverKill(DR); }
 248         LiveState(VD, AD) = Alive;
 249         return VisitDeclRefExpr(DR);
 250       }
 251
 252     // Fall-through.
 253
 254   default:
 255     return Visit(E);
 256   }
 257 }
 258
 259 void TransferFuncs::VisitAssign(BinaryOperator* B) {
 260   Expr* LHS = B->getLHS();
 261
 262   // Assigning to a variable?
 263   if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS->IgnoreParens())) {
 264     // Assignments to references don't kill the ref's address
 265     if (DR->getDecl()->getType()->isReferenceType()) {
 266       VisitDeclRefExpr(DR);
 267     } else {
 268       if (AD.killAtAssign) {
 269         // Update liveness inforamtion.
 270         unsigned bit = AD.getIdx(DR->getDecl());
 271         LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit);
 272
 273         if (AD.Observer) { AD.Observer->ObserverKill(DR); }
 274       }
 275       // Handle things like +=, etc., which also generate "uses"
 276       // of a variable.  Do this just by visiting the subexpression.
 277       if (B->getOpcode() != BO_Assign)
 278         VisitDeclRefExpr(DR);
 279     }
 280   }
 281   else // Not assigning to a variable.  Process LHS as usual.
 282     Visit(LHS);
 283
 284   Visit(B->getRHS());
 285 }
 286
 287 void TransferFuncs::VisitDeclStmt(DeclStmt* DS) {
 288   // Declarations effectively "kill" a variable since they cannot
 289   // possibly be live before they are declared.
 290   for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE = DS->decl_end();
 291        DI != DE; ++DI)
 292     if (VarDecl* VD = dyn_cast<VarDecl>(*DI)) {
 293       // Update liveness information by killing the VarDecl.
 294       unsigned bit = AD.getIdx(VD);
 295       LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit);
 296
 297       // The initializer is evaluated after the variable comes into scope, but
 298       // before the DeclStmt (which binds the value to the variable).
 299       // Since this is a reverse dataflow analysis, we must evaluate the
 300       // transfer function for this expression after the DeclStmt.  If the
 301       // initializer references the variable (which is bad) then we extend
 302       // its liveness.
 303       if (Expr* Init = VD->getInit())
 304         Visit(Init);
 305
 306       if (const VariableArrayType* VT =
 307             AD.getContext().getAsVariableArrayType(VD->getType())) {
 308         StmtIterator I(const_cast<VariableArrayType*>(VT));
 309         StmtIterator E;
 310         for (; I != E; ++I) Visit(*I);
 311       }
 312     }
 313 }
 314
 315 } // end anonymous namespace
 316
 317 //===----------------------------------------------------------------------===//
 318 // Merge operator: if something is live on any successor block, it is live
 319 //  in the current block (a set union).
 320 //===----------------------------------------------------------------------===//
 321
 322 namespace {
 323   typedef StmtDeclBitVector_Types::Union Merge;
 324   typedef DataflowSolver<LiveVariables, TransferFuncs, Merge> Solver;
 325 } // end anonymous namespace
 326
 327 //===----------------------------------------------------------------------===//
 328 // External interface to run Liveness analysis.
 329 //===----------------------------------------------------------------------===//
 330
 331 void LiveVariables::runOnCFG(CFG& cfg) {
 332   Solver S(*this);
 333   S.runOnCFG(cfg);
 334 }
 335
 336 void LiveVariables::runOnAllBlocks(const CFG& cfg,
 337                                    LiveVariables::ObserverTy* Obs,
 338                                    bool recordStmtValues) {
 339   Solver S(*this);
 340   SaveAndRestore<LiveVariables::ObserverTy*> SRObs(getAnalysisData().Observer,
 341                                                    Obs);
 342   S.runOnAllBlocks(cfg, recordStmtValues);
 343 }
 344
 345 //===----------------------------------------------------------------------===//
 346 // liveness queries
 347 //
 348
 349 bool LiveVariables::isLive(const CFGBlock* B, const VarDecl* D) const {
 350   DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D);
 351   return i.isValid() ? getBlockData(B).getBit(i) : false;
 352 }
 353
 354 bool LiveVariables::isLive(const ValTy& Live, const VarDecl* D) const {
 355   DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D);
 356   return i.isValid() ? Live.getBit(i) : false;
 357 }
 358
 359 bool LiveVariables::isLive(const Stmt* Loc, const Stmt* StmtVal) const {
 360   return getStmtData(Loc)(StmtVal,getAnalysisData());
 361 }
 362
 363 bool LiveVariables::isLive(const Stmt* Loc, const VarDecl* D) const {
 364   return getStmtData(Loc)(D,getAnalysisData());
 365 }
 366
 367 //===----------------------------------------------------------------------===//
 368 // printing liveness state for debugging
 369 //
 370
 371 void LiveVariables::dumpLiveness(const ValTy& V, const SourceManager& SM) const {
 372   const AnalysisDataTy& AD = getAnalysisData();
 373
 374   for (AnalysisDataTy::decl_iterator I = AD.begin_decl(),
 375                                      E = AD.end_decl(); I!=E; ++I)
 376     if (V.getDeclBit(I->second)) {
 377       llvm::errs() << "  " << I->first->getIdentifier()->getName() << " <";
 378       I->first->getLocation().dump(SM);
 379       llvm::errs() << ">\n";
 380     }
 381 }
 382
 383 void LiveVariables::dumpBlockLiveness(const SourceManager& M) const {
 384   for (BlockDataMapTy::const_iterator I = getBlockDataMap().begin(),
 385        E = getBlockDataMap().end(); I!=E; ++I) {
 386     llvm::errs() << "\n[ B" << I->first->getBlockID()
 387                  << " (live variables at block exit) ]\n";
 388     dumpLiveness(I->second,M);
 389   }
 390
 391   llvm::errs() << "\n";
 392 }