ReachableCode.cpp revision 3d2eed823d534ee370cfd7742c1e96ab3ee9a80b 
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/Analysis/Analyses/ReachableCode.h"
18#include "clang/Analysis/CFG.h"
19
20using namespace clang;
21
22/// ScanReachableFromBlock - Mark all blocks reachable from Start.
23/// Returns the total number of blocks that were marked reachable.
24unsigned clang::ScanReachableFromBlock(const CFGBlock &Start,
25                                       llvm::BitVector &Reachable) {
26  unsigned count = 0;
27  llvm::SmallVector<const CFGBlock*, 12> WL;
28
29  // Prep work queue
30  Reachable.set(Start.getBlockID());
31  ++count;
32  WL.push_back(&Start);
33
34  // Find the reachable blocks from 'Start'.
35  while (!WL.empty()) {
36    const CFGBlock *item = WL.back();
37    WL.pop_back();
38
39    // Look at the successors and mark then reachable.
40    for (CFGBlock::const_succ_iterator I=item->succ_begin(), E=item->succ_end();
41         I != E; ++I)
42      if (const CFGBlock *B = *I) {
43        unsigned blockID = B->getBlockID();
44        if (!Reachable[blockID]) {
45          Reachable.set(blockID);
46          ++count;
47          WL.push_back(B);
48        }
49      }
50  }
51  return count;
52}
53