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

   1 //===- CFGReachabilityAnalysis.cpp - Basic reachability analysis ----------===//
   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 defines a flow-sensitive, (mostly) path-insensitive reachability
  11 // analysis based on Clang's CFGs.  Clients can query if a given basic block
  12 // is reachable within the CFG.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h"
  17 #include "clang/Analysis/CFG.h"
  18 #include "llvm/ADT/BitVector.h"
  19 #include "llvm/ADT/SmallVector.h"
  20
  21 using namespace clang;
  22
  23 CFGReverseBlockReachabilityAnalysis::CFGReverseBlockReachabilityAnalysis(
  24     const CFG &cfg)
  25     : analyzed(cfg.getNumBlockIDs(), false) {}
  26
  27 bool CFGReverseBlockReachabilityAnalysis::isReachable(const CFGBlock *Src,
  28                                           const CFGBlock *Dst) {
  29   const unsigned DstBlockID = Dst->getBlockID();
  30
  31   // If we haven't analyzed the destination node, run the analysis now
  32   if (!analyzed[DstBlockID]) {
  33     mapReachability(Dst);
  34     analyzed[DstBlockID] = true;
  35   }
  36
  37   // Return the cached result
  38   return reachable[DstBlockID][Src->getBlockID()];
  39 }
  40
  41 // Maps reachability to a common node by walking the predecessors of the
  42 // destination node.
  43 void CFGReverseBlockReachabilityAnalysis::mapReachability(const CFGBlock *Dst) {
  44   SmallVector<const CFGBlock *, 11> worklist;
  45   llvm::BitVector visited(analyzed.size());
  46
  47   ReachableSet &DstReachability = reachable[Dst->getBlockID()];
  48   DstReachability.resize(analyzed.size(), false);
  49
  50   // Start searching from the destination node, since we commonly will perform
  51   // multiple queries relating to a destination node.
  52   worklist.push_back(Dst);
  53   bool firstRun = true;
  54
  55   while (!worklist.empty()) {
  56     const CFGBlock *block = worklist.pop_back_val();
  57
  58     if (visited[block->getBlockID()])
  59       continue;
  60     visited[block->getBlockID()] = true;
  61
  62     // Update reachability information for this node -> Dst
  63     if (!firstRun) {
  64       // Don't insert Dst -> Dst unless it was a predecessor of itself
  65       DstReachability[block->getBlockID()] = true;
  66     }
  67     else
  68       firstRun = false;
  69
  70     // Add the predecessors to the worklist.
  71     for (CFGBlock::const_pred_iterator i = block->pred_begin(),
  72          e = block->pred_end(); i != e; ++i) {
  73       if (*i)
  74         worklist.push_back(*i);
  75     }
  76   }
  77 }