1//===--- CFGStmtMap.h - Map from Stmt* to CFGBlock* -----------*- C++ -*-===//
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 the CFGStmtMap class, which defines a mapping from
10//  Stmt* to CFGBlock*
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/ADT/DenseMap.h"
15#include "clang/AST/ParentMap.h"
16#include "clang/Analysis/CFG.h"
17#include "clang/Analysis/CFGStmtMap.h"
18
19using namespace clang;
20
21typedef llvm::DenseMap<const Stmt*, CFGBlock*> SMap;
22static SMap *AsMap(void *m) { return (SMap*) m; }
23
24CFGStmtMap::~CFGStmtMap() { delete AsMap(M); }
25
26CFGBlock *CFGStmtMap::getBlock(Stmt *S) {
27  SMap *SM = AsMap(M);
28  Stmt *X = S;
29
30  // If 'S' isn't in the map, walk the ParentMap to see if one of its ancestors
31  // is in the map.
32  while (X) {
33    SMap::iterator I = SM->find(X);
34    if (I != SM->end()) {
35      CFGBlock *B = I->second;
36      // Memoize this lookup.
37      if (X != S)
38        (*SM)[X] = B;
39      return B;
40    }
41
42    X = PM->getParentIgnoreParens(X);
43  }
44
45  return nullptr;
46}
47
48static void Accumulate(SMap &SM, CFGBlock *B) {
49  // First walk the block-level expressions.
50  for (CFGBlock::iterator I = B->begin(), E = B->end(); I != E; ++I) {
51    const CFGElement &CE = *I;
52    Optional<CFGStmt> CS = CE.getAs<CFGStmt>();
53    if (!CS)
54      continue;
55
56    CFGBlock *&Entry = SM[CS->getStmt()];
57    // If 'Entry' is already initialized (e.g., a terminator was already),
58    // skip.
59    if (Entry)
60      continue;
61
62    Entry = B;
63
64  }
65
66  // Look at the label of the block.
67  if (Stmt *Label = B->getLabel())
68    SM[Label] = B;
69
70  // Finally, look at the terminator.  If the terminator was already added
71  // because it is a block-level expression in another block, overwrite
72  // that mapping.
73  if (Stmt *Term = B->getTerminatorStmt())
74    SM[Term] = B;
75}
76
77CFGStmtMap *CFGStmtMap::Build(CFG *C, ParentMap *PM) {
78  if (!C || !PM)
79    return nullptr;
80
81  SMap *SM = new SMap();
82
83  // Walk all blocks, accumulating the block-level expressions, labels,
84  // and terminators.
85  for (CFG::iterator I = C->begin(), E = C->end(); I != E; ++I)
86    Accumulate(*SM, *I);
87
88  return new CFGStmtMap(PM, SM);
89}
90
91