clang/lib/Analysis/CFGReachabilityAnalysis.cpp

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