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

   1 //=- ReachableCodePathInsensitive.cpp ---------------------------*- 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 a flow-sensitive, path-insensitive analysis of
  11 // determining reachable blocks within a CFG.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "clang/Analysis/Analyses/ReachableCode.h"
  16 #include "clang/AST/Expr.h"
  17 #include "clang/AST/ExprCXX.h"
  18 #include "clang/AST/ExprObjC.h"
  19 #include "clang/AST/StmtCXX.h"
  20 #include "clang/Analysis/AnalysisContext.h"
  21 #include "clang/Analysis/CFG.h"
  22 #include "clang/Basic/SourceManager.h"
  23 #include "llvm/ADT/BitVector.h"
  24 #include "llvm/ADT/SmallVector.h"
  25
  26 using namespace clang;
  27
  28 namespace {
  29 class DeadCodeScan {
  30   llvm::BitVector Visited;
  31   llvm::BitVector &Reachable;
  32   SmallVector<const CFGBlock *, 10> WorkList;
  33
  34   typedef SmallVector<std::pair<const CFGBlock *, const Stmt *>, 12>
  35       DeferredLocsTy;
  36
  37   DeferredLocsTy DeferredLocs;
  38
  39 public:
  40   DeadCodeScan(llvm::BitVector &reachable)
  41     : Visited(reachable.size()),
  42       Reachable(reachable) {}
  43
  44   void enqueue(const CFGBlock *block);
  45   unsigned scanBackwards(const CFGBlock *Start,
  46                          clang::reachable_code::Callback &CB);
  47
  48   bool isDeadCodeRoot(const CFGBlock *Block);
  49
  50   const Stmt *findDeadCode(const CFGBlock *Block);
  51
  52   void reportDeadCode(const Stmt *S,
  53                       clang::reachable_code::Callback &CB);
  54 };
  55 }
  56
  57 void DeadCodeScan::enqueue(const CFGBlock *block) {
  58   unsigned blockID = block->getBlockID();
  59   if (Reachable[blockID] || Visited[blockID])
  60     return;
  61   Visited[blockID] = true;
  62   WorkList.push_back(block);
  63 }
  64
  65 bool DeadCodeScan::isDeadCodeRoot(const clang::CFGBlock *Block) {
  66   bool isDeadRoot = true;
  67
  68   for (CFGBlock::const_pred_iterator I = Block->pred_begin(),
  69         E = Block->pred_end(); I != E; ++I) {
  70     if (const CFGBlock *PredBlock = *I) {
  71       unsigned blockID = PredBlock->getBlockID();
  72       if (Visited[blockID]) {
  73         isDeadRoot = false;
  74         continue;
  75       }
  76       if (!Reachable[blockID]) {
  77         isDeadRoot = false;
  78         Visited[blockID] = true;
  79         WorkList.push_back(PredBlock);
  80         continue;
  81       }
  82     }
  83   }
  84
  85   return isDeadRoot;
  86 }
  87
  88 static bool isValidDeadStmt(const Stmt *S) {
  89   if (S->getLocStart().isInvalid())
  90     return false;
  91   if (const BinaryOperator *BO = dyn_cast<BinaryOperator>(S))
  92     return BO->getOpcode() != BO_Comma;
  93   return true;
  94 }
  95
  96 const Stmt *DeadCodeScan::findDeadCode(const clang::CFGBlock *Block) {
  97   for (CFGBlock::const_iterator I = Block->begin(), E = Block->end(); I!=E; ++I)
  98     if (Optional<CFGStmt> CS = I->getAs<CFGStmt>()) {
  99       const Stmt *S = CS->getStmt();
 100       if (isValidDeadStmt(S))
 101         return S;
 102     }
 103
 104   if (CFGTerminator T = Block->getTerminator()) {
 105     const Stmt *S = T.getStmt();
 106     if (isValidDeadStmt(S))
 107       return S;
 108   }
 109
 110   return 0;
 111 }
 112
 113 static int SrcCmp(const void *p1, const void *p2) {
 114   return
 115     ((const std::pair<const CFGBlock *, const Stmt *>*) p2)->second->getLocStart() <
 116     ((const std::pair<const CFGBlock *, const Stmt *>*) p1)->second->getLocStart();
 117 }
 118
 119 unsigned DeadCodeScan::scanBackwards(const clang::CFGBlock *Start,
 120                                      clang::reachable_code::Callback &CB) {
 121
 122   unsigned count = 0;
 123   enqueue(Start);
 124
 125   while (!WorkList.empty()) {
 126     const CFGBlock *Block = WorkList.pop_back_val();
 127
 128     // It is possible that this block has been marked reachable after
 129     // it was enqueued.
 130     if (Reachable[Block->getBlockID()])
 131       continue;
 132
 133     // Look for any dead code within the block.
 134     const Stmt *S = findDeadCode(Block);
 135
 136     if (!S) {
 137       // No dead code.  Possibly an empty block.  Look at dead predecessors.
 138       for (CFGBlock::const_pred_iterator I = Block->pred_begin(),
 139            E = Block->pred_end(); I != E; ++I) {
 140         if (const CFGBlock *predBlock = *I)
 141           enqueue(predBlock);
 142       }
 143       continue;
 144     }
 145
 146     // Specially handle macro-expanded code.
 147     if (S->getLocStart().isMacroID()) {
 148       count += clang::reachable_code::ScanReachableFromBlock(Block, Reachable);
 149       continue;
 150     }
 151
 152     if (isDeadCodeRoot(Block)) {
 153       reportDeadCode(S, CB);
 154       count += clang::reachable_code::ScanReachableFromBlock(Block, Reachable);
 155     }
 156     else {
 157       // Record this statement as the possibly best location in a
 158       // strongly-connected component of dead code for emitting a
 159       // warning.
 160       DeferredLocs.push_back(std::make_pair(Block, S));
 161     }
 162   }
 163
 164   // If we didn't find a dead root, then report the dead code with the
 165   // earliest location.
 166   if (!DeferredLocs.empty()) {
 167     llvm::array_pod_sort(DeferredLocs.begin(), DeferredLocs.end(), SrcCmp);
 168     for (DeferredLocsTy::iterator I = DeferredLocs.begin(),
 169           E = DeferredLocs.end(); I != E; ++I) {
 170       const CFGBlock *block = I->first;
 171       if (Reachable[block->getBlockID()])
 172         continue;
 173       reportDeadCode(I->second, CB);
 174       count += clang::reachable_code::ScanReachableFromBlock(block, Reachable);
 175     }
 176   }
 177
 178   return count;
 179 }
 180
 181 static SourceLocation GetUnreachableLoc(const Stmt *S,
 182                                         SourceRange &R1,
 183                                         SourceRange &R2) {
 184   R1 = R2 = SourceRange();
 185
 186   if (const Expr *Ex = dyn_cast<Expr>(S))
 187     S = Ex->IgnoreParenImpCasts();
 188
 189   switch (S->getStmtClass()) {
 190     case Expr::BinaryOperatorClass: {
 191       const BinaryOperator *BO = cast<BinaryOperator>(S);
 192       return BO->getOperatorLoc();
 193     }
 194     case Expr::UnaryOperatorClass: {
 195       const UnaryOperator *UO = cast<UnaryOperator>(S);
 196       R1 = UO->getSubExpr()->getSourceRange();
 197       return UO->getOperatorLoc();
 198     }
 199     case Expr::CompoundAssignOperatorClass: {
 200       const CompoundAssignOperator *CAO = cast<CompoundAssignOperator>(S);
 201       R1 = CAO->getLHS()->getSourceRange();
 202       R2 = CAO->getRHS()->getSourceRange();
 203       return CAO->getOperatorLoc();
 204     }
 205     case Expr::BinaryConditionalOperatorClass:
 206     case Expr::ConditionalOperatorClass: {
 207       const AbstractConditionalOperator *CO =
 208         cast<AbstractConditionalOperator>(S);
 209       return CO->getQuestionLoc();
 210     }
 211     case Expr::MemberExprClass: {
 212       const MemberExpr *ME = cast<MemberExpr>(S);
 213       R1 = ME->getSourceRange();
 214       return ME->getMemberLoc();
 215     }
 216     case Expr::ArraySubscriptExprClass: {
 217       const ArraySubscriptExpr *ASE = cast<ArraySubscriptExpr>(S);
 218       R1 = ASE->getLHS()->getSourceRange();
 219       R2 = ASE->getRHS()->getSourceRange();
 220       return ASE->getRBracketLoc();
 221     }
 222     case Expr::CStyleCastExprClass: {
 223       const CStyleCastExpr *CSC = cast<CStyleCastExpr>(S);
 224       R1 = CSC->getSubExpr()->getSourceRange();
 225       return CSC->getLParenLoc();
 226     }
 227     case Expr::CXXFunctionalCastExprClass: {
 228       const CXXFunctionalCastExpr *CE = cast <CXXFunctionalCastExpr>(S);
 229       R1 = CE->getSubExpr()->getSourceRange();
 230       return CE->getTypeBeginLoc();
 231     }
 232     case Stmt::CXXTryStmtClass: {
 233       return cast<CXXTryStmt>(S)->getHandler(0)->getCatchLoc();
 234     }
 235     case Expr::ObjCBridgedCastExprClass: {
 236       const ObjCBridgedCastExpr *CSC = cast<ObjCBridgedCastExpr>(S);
 237       R1 = CSC->getSubExpr()->getSourceRange();
 238       return CSC->getLParenLoc();
 239     }
 240     default: ;
 241   }
 242   R1 = S->getSourceRange();
 243   return S->getLocStart();
 244 }
 245
 246 void DeadCodeScan::reportDeadCode(const Stmt *S,
 247                                   clang::reachable_code::Callback &CB) {
 248   SourceRange R1, R2;
 249   SourceLocation Loc = GetUnreachableLoc(S, R1, R2);
 250   CB.HandleUnreachable(Loc, R1, R2);
 251 }
 252
 253 namespace clang { namespace reachable_code {
 254
 255 void Callback::anchor() { }
 256
 257 unsigned ScanReachableFromBlock(const CFGBlock *Start,
 258                                 llvm::BitVector &Reachable) {
 259   unsigned count = 0;
 260
 261   // Prep work queue
 262   SmallVector<const CFGBlock*, 32> WL;
 263
 264   // The entry block may have already been marked reachable
 265   // by the caller.
 266   if (!Reachable[Start->getBlockID()]) {
 267     ++count;
 268     Reachable[Start->getBlockID()] = true;
 269   }
 270
 271   WL.push_back(Start);
 272
 273   // Find the reachable blocks from 'Start'.
 274   while (!WL.empty()) {
 275     const CFGBlock *item = WL.pop_back_val();
 276
 277     // Look at the successors and mark then reachable.
 278     for (CFGBlock::const_succ_iterator I = item->succ_begin(),
 279          E = item->succ_end(); I != E; ++I)
 280       if (const CFGBlock *B = *I) {
 281         unsigned blockID = B->getBlockID();
 282         if (!Reachable[blockID]) {
 283           Reachable.set(blockID);
 284           WL.push_back(B);
 285           ++count;
 286         }
 287       }
 288   }
 289   return count;
 290 }
 291
 292 void FindUnreachableCode(AnalysisDeclContext &AC, Callback &CB) {
 293   CFG *cfg = AC.getCFG();
 294   if (!cfg)
 295     return;
 296
 297   // Scan for reachable blocks from the entrance of the CFG.
 298   // If there are no unreachable blocks, we're done.
 299   llvm::BitVector reachable(cfg->getNumBlockIDs());
 300   unsigned numReachable = ScanReachableFromBlock(&cfg->getEntry(), reachable);
 301   if (numReachable == cfg->getNumBlockIDs())
 302     return;
 303
 304   // If there aren't explicit EH edges, we should include the 'try' dispatch
 305   // blocks as roots.
 306   if (!AC.getCFGBuildOptions().AddEHEdges) {
 307     for (CFG::try_block_iterator I = cfg->try_blocks_begin(),
 308          E = cfg->try_blocks_end() ; I != E; ++I) {
 309       numReachable += ScanReachableFromBlock(*I, reachable);
 310     }
 311     if (numReachable == cfg->getNumBlockIDs())
 312       return;
 313   }
 314
 315   // There are some unreachable blocks.  We need to find the root blocks that
 316   // contain code that should be considered unreachable.
 317   for (CFG::iterator I = cfg->begin(), E = cfg->end(); I != E; ++I) {
 318     const CFGBlock *block = *I;
 319     // A block may have been marked reachable during this loop.
 320     if (reachable[block->getBlockID()])
 321       continue;
 322
 323     DeadCodeScan DS(reachable);
 324     numReachable += DS.scanBackwards(block, CB);
 325
 326     if (numReachable == cfg->getNumBlockIDs())
 327       return;
 328   }
 329 }
 330
 331 }} // end namespace clang::reachable_code