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 "llvm/ADT/BitVector.h"
     16 #include "llvm/ADT/SmallVector.h"
     17 #include "clang/AST/Expr.h"
     18 #include "clang/AST/ExprCXX.h"
     19 #include "clang/AST/ExprObjC.h"
     20 #include "clang/AST/StmtCXX.h"
     21 #include "clang/Analysis/Analyses/ReachableCode.h"
     22 #include "clang/Analysis/CFG.h"
     23 #include "clang/Analysis/AnalysisContext.h"
     24 #include "clang/Basic/SourceManager.h"
     25 
     26 using namespace clang;
     27 
     28 namespace {
     29 class DeadCodeScan {
     30   llvm::BitVector Visited;
     31   llvm::BitVector &Reachable;
     32   llvm::SmallVector<const CFGBlock *, 10> WorkList;
     33 
     34   typedef llvm::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 (const 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     ((std::pair<const CFGBlock *, const Stmt *>*) p2)->second->getLocStart() <
    116     ((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 unsigned ScanReachableFromBlock(const CFGBlock *Start,
    256                                 llvm::BitVector &Reachable) {
    257   unsigned count = 0;
    258 
    259   // Prep work queue
    260   SmallVector<const CFGBlock*, 32> WL;
    261 
    262   // The entry block may have already been marked reachable
    263   // by the caller.
    264   if (!Reachable[Start->getBlockID()]) {
    265     ++count;
    266     Reachable[Start->getBlockID()] = true;
    267   }
    268 
    269   WL.push_back(Start);
    270 
    271   // Find the reachable blocks from 'Start'.
    272   while (!WL.empty()) {
    273     const CFGBlock *item = WL.pop_back_val();
    274 
    275     // Look at the successors and mark then reachable.
    276     for (CFGBlock::const_succ_iterator I = item->succ_begin(),
    277          E = item->succ_end(); I != E; ++I)
    278       if (const CFGBlock *B = *I) {
    279         unsigned blockID = B->getBlockID();
    280         if (!Reachable[blockID]) {
    281           Reachable.set(blockID);
    282           WL.push_back(B);
    283           ++count;
    284         }
    285       }
    286   }
    287   return count;
    288 }
    289 
    290 void FindUnreachableCode(AnalysisContext &AC, Callback &CB) {
    291   CFG *cfg = AC.getCFG();
    292   if (!cfg)
    293     return;
    294 
    295   // Scan for reachable blocks from the entrance of the CFG.
    296   // If there are no unreachable blocks, we're done.
    297   llvm::BitVector reachable(cfg->getNumBlockIDs());
    298   unsigned numReachable = ScanReachableFromBlock(&cfg->getEntry(), reachable);
    299   if (numReachable == cfg->getNumBlockIDs())
    300     return;
    301 
    302   // If there aren't explicit EH edges, we should include the 'try' dispatch
    303   // blocks as roots.
    304   if (!AC.getCFGBuildOptions().AddEHEdges) {
    305     for (CFG::try_block_iterator I = cfg->try_blocks_begin(),
    306          E = cfg->try_blocks_end() ; I != E; ++I) {
    307       numReachable += ScanReachableFromBlock(*I, reachable);
    308     }
    309     if (numReachable == cfg->getNumBlockIDs())
    310       return;
    311   }
    312 
    313   // There are some unreachable blocks.  We need to find the root blocks that
    314   // contain code that should be considered unreachable.
    315   for (CFG::iterator I = cfg->begin(), E = cfg->end(); I != E; ++I) {
    316     const CFGBlock *block = *I;
    317     // A block may have been marked reachable during this loop.
    318     if (reachable[block->getBlockID()])
    319       continue;
    320 
    321     DeadCodeScan DS(reachable);
    322     numReachable += DS.scanBackwards(block, CB);
    323 
    324     if (numReachable == cfg->getNumBlockIDs())
    325       return;
    326   }
    327 }
    328 
    329 }} // end namespace clang::reachable_code
    330