Home | History | Annotate | Download | only in Analysis 
      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
    332