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 std::pair<const CFGBlock *, const Stmt *> *p1,
 114                   const std::pair<const CFGBlock *, const Stmt *> *p2) {
 115   if (p1->second->getLocStart() < p2->second->getLocStart())
 116     return -1;
 117   if (p2->second->getLocStart() < p1->second->getLocStart())
 118     return 1;
 119   return 0;
 120 }
 121
 122 unsigned DeadCodeScan::scanBackwards(const clang::CFGBlock *Start,
 123                                      clang::reachable_code::Callback &CB) {
 124
 125   unsigned count = 0;
 126   enqueue(Start);
 127
 128   while (!WorkList.empty()) {
 129     const CFGBlock *Block = WorkList.pop_back_val();
 130
 131     // It is possible that this block has been marked reachable after
 132     // it was enqueued.
 133     if (Reachable[Block->getBlockID()])
 134       continue;
 135
 136     // Look for any dead code within the block.
 137     const Stmt *S = findDeadCode(Block);
 138
 139     if (!S) {
 140       // No dead code.  Possibly an empty block.  Look at dead predecessors.
 141       for (CFGBlock::const_pred_iterator I = Block->pred_begin(),
 142            E = Block->pred_end(); I != E; ++I) {
 143         if (const CFGBlock *predBlock = *I)
 144           enqueue(predBlock);
 145       }
 146       continue;
 147     }
 148
 149     // Specially handle macro-expanded code.
 150     if (S->getLocStart().isMacroID()) {
 151       count += clang::reachable_code::ScanReachableFromBlock(Block, Reachable);
 152       continue;
 153     }
 154
 155     if (isDeadCodeRoot(Block)) {
 156       reportDeadCode(S, CB);
 157       count += clang::reachable_code::ScanReachableFromBlock(Block, Reachable);
 158     }
 159     else {
 160       // Record this statement as the possibly best location in a
 161       // strongly-connected component of dead code for emitting a
 162       // warning.
 163       DeferredLocs.push_back(std::make_pair(Block, S));
 164     }
 165   }
 166
 167   // If we didn't find a dead root, then report the dead code with the
 168   // earliest location.
 169   if (!DeferredLocs.empty()) {
 170     llvm::array_pod_sort(DeferredLocs.begin(), DeferredLocs.end(), SrcCmp);
 171     for (DeferredLocsTy::iterator I = DeferredLocs.begin(),
 172           E = DeferredLocs.end(); I != E; ++I) {
 173       const CFGBlock *block = I->first;
 174       if (Reachable[block->getBlockID()])
 175         continue;
 176       reportDeadCode(I->second, CB);
 177       count += clang::reachable_code::ScanReachableFromBlock(block, Reachable);
 178     }
 179   }
 180
 181   return count;
 182 }
 183
 184 static SourceLocation GetUnreachableLoc(const Stmt *S,
 185                                         SourceRange &R1,
 186                                         SourceRange &R2) {
 187   R1 = R2 = SourceRange();
 188
 189   if (const Expr *Ex = dyn_cast<Expr>(S))
 190     S = Ex->IgnoreParenImpCasts();
 191
 192   switch (S->getStmtClass()) {
 193     case Expr::BinaryOperatorClass: {
 194       const BinaryOperator *BO = cast<BinaryOperator>(S);
 195       return BO->getOperatorLoc();
 196     }
 197     case Expr::UnaryOperatorClass: {
 198       const UnaryOperator *UO = cast<UnaryOperator>(S);
 199       R1 = UO->getSubExpr()->getSourceRange();
 200       return UO->getOperatorLoc();
 201     }
 202     case Expr::CompoundAssignOperatorClass: {
 203       const CompoundAssignOperator *CAO = cast<CompoundAssignOperator>(S);
 204       R1 = CAO->getLHS()->getSourceRange();
 205       R2 = CAO->getRHS()->getSourceRange();
 206       return CAO->getOperatorLoc();
 207     }
 208     case Expr::BinaryConditionalOperatorClass:
 209     case Expr::ConditionalOperatorClass: {
 210       const AbstractConditionalOperator *CO =
 211         cast<AbstractConditionalOperator>(S);
 212       return CO->getQuestionLoc();
 213     }
 214     case Expr::MemberExprClass: {
 215       const MemberExpr *ME = cast<MemberExpr>(S);
 216       R1 = ME->getSourceRange();
 217       return ME->getMemberLoc();
 218     }
 219     case Expr::ArraySubscriptExprClass: {
 220       const ArraySubscriptExpr *ASE = cast<ArraySubscriptExpr>(S);
 221       R1 = ASE->getLHS()->getSourceRange();
 222       R2 = ASE->getRHS()->getSourceRange();
 223       return ASE->getRBracketLoc();
 224     }
 225     case Expr::CStyleCastExprClass: {
 226       const CStyleCastExpr *CSC = cast<CStyleCastExpr>(S);
 227       R1 = CSC->getSubExpr()->getSourceRange();
 228       return CSC->getLParenLoc();
 229     }
 230     case Expr::CXXFunctionalCastExprClass: {
 231       const CXXFunctionalCastExpr *CE = cast <CXXFunctionalCastExpr>(S);
 232       R1 = CE->getSubExpr()->getSourceRange();
 233       return CE->getLocStart();
 234     }
 235     case Stmt::CXXTryStmtClass: {
 236       return cast<CXXTryStmt>(S)->getHandler(0)->getCatchLoc();
 237     }
 238     case Expr::ObjCBridgedCastExprClass: {
 239       const ObjCBridgedCastExpr *CSC = cast<ObjCBridgedCastExpr>(S);
 240       R1 = CSC->getSubExpr()->getSourceRange();
 241       return CSC->getLParenLoc();
 242     }
 243     default: ;
 244   }
 245   R1 = S->getSourceRange();
 246   return S->getLocStart();
 247 }
 248
 249 void DeadCodeScan::reportDeadCode(const Stmt *S,
 250                                   clang::reachable_code::Callback &CB) {
 251   SourceRange R1, R2;
 252   SourceLocation Loc = GetUnreachableLoc(S, R1, R2);
 253   CB.HandleUnreachable(Loc, R1, R2);
 254 }
 255
 256 namespace clang { namespace reachable_code {
 257
 258 void Callback::anchor() { }
 259
 260 unsigned ScanReachableFromBlock(const CFGBlock *Start,
 261                                 llvm::BitVector &Reachable) {
 262   unsigned count = 0;
 263
 264   // Prep work queue
 265   SmallVector<const CFGBlock*, 32> WL;
 266
 267   // The entry block may have already been marked reachable
 268   // by the caller.
 269   if (!Reachable[Start->getBlockID()]) {
 270     ++count;
 271     Reachable[Start->getBlockID()] = true;
 272   }
 273
 274   WL.push_back(Start);
 275
 276   // Find the reachable blocks from 'Start'.
 277   while (!WL.empty()) {
 278     const CFGBlock *item = WL.pop_back_val();
 279
 280     // Look at the successors and mark then reachable.
 281     for (CFGBlock::const_succ_iterator I = item->succ_begin(),
 282          E = item->succ_end(); I != E; ++I)
 283       if (const CFGBlock *B = *I) {
 284         unsigned blockID = B->getBlockID();
 285         if (!Reachable[blockID]) {
 286           Reachable.set(blockID);
 287           WL.push_back(B);
 288           ++count;
 289         }
 290       }
 291   }
 292   return count;
 293 }
 294
 295 void FindUnreachableCode(AnalysisDeclContext &AC, Callback &CB) {
 296   CFG *cfg = AC.getCFG();
 297   if (!cfg)
 298     return;
 299
 300   // Scan for reachable blocks from the entrance of the CFG.
 301   // If there are no unreachable blocks, we're done.
 302   llvm::BitVector reachable(cfg->getNumBlockIDs());
 303   unsigned numReachable = ScanReachableFromBlock(&cfg->getEntry(), reachable);
 304   if (numReachable == cfg->getNumBlockIDs())
 305     return;
 306
 307   // If there aren't explicit EH edges, we should include the 'try' dispatch
 308   // blocks as roots.
 309   if (!AC.getCFGBuildOptions().AddEHEdges) {
 310     for (CFG::try_block_iterator I = cfg->try_blocks_begin(),
 311          E = cfg->try_blocks_end() ; I != E; ++I) {
 312       numReachable += ScanReachableFromBlock(*I, reachable);
 313     }
 314     if (numReachable == cfg->getNumBlockIDs())
 315       return;
 316   }
 317
 318   // There are some unreachable blocks.  We need to find the root blocks that
 319   // contain code that should be considered unreachable.
 320   for (CFG::iterator I = cfg->begin(), E = cfg->end(); I != E; ++I) {
 321     const CFGBlock *block = *I;
 322     // A block may have been marked reachable during this loop.
 323     if (reachable[block->getBlockID()])
 324       continue;
 325
 326     DeadCodeScan DS(reachable);
 327     numReachable += DS.scanBackwards(block, CB);
 328
 329     if (numReachable == cfg->getNumBlockIDs())
 330       return;
 331   }
 332 }
 333
 334 }} // end namespace clang::reachable_code