1a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek//===--- CFGStmtMap.h - Map from Stmt* to CFGBlock* -----------*- C++ -*-===// 2a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek// 3a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek// The LLVM Compiler Infrastructure 4a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek// 5a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek// This file is distributed under the University of Illinois Open Source 6a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek// License. See LICENSE.TXT for details. 7a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek// 8a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek//===----------------------------------------------------------------------===// 9a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek// 10a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek// This file defines the CFGStmtMap class, which defines a mapping from 11a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek// Stmt* to CFGBlock* 12a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek// 13a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek//===----------------------------------------------------------------------===// 14a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek 15a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek#include "llvm/ADT/DenseMap.h" 16a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek#include "clang/AST/ParentMap.h" 17a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek#include "clang/Analysis/CFG.h" 18a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek#include "clang/Analysis/CFGStmtMap.h" 19a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek 20a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenekusing namespace clang; 21a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek 22f1d10d939739f1a4544926d807e4f0f9fb64be61Ted Kremenektypedef llvm::DenseMap<const Stmt*, CFGBlock*> SMap; 23a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenekstatic SMap *AsMap(void *m) { return (SMap*) m; } 24a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek 25a6d69302d7c86b1c71b9c18493bb811f7d152075Ted KremenekCFGStmtMap::~CFGStmtMap() { delete AsMap(M); } 26a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek 27a6d69302d7c86b1c71b9c18493bb811f7d152075Ted KremenekCFGBlock *CFGStmtMap::getBlock(Stmt *S) { 28a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek SMap *SM = AsMap(M); 29a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek Stmt *X = S; 30a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek 31a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek // If 'S' isn't in the map, walk the ParentMap to see if one of its ancestors 32a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek // is in the map. 33a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek while (X) { 34b5049d83fd83bd0dc8b19e94b5c05f38ea64d7ceTom Care SMap::iterator I = SM->find(X); 35a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek if (I != SM->end()) { 36a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek CFGBlock *B = I->second; 37a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek // Memoize this lookup. 38a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek if (X != S) 39a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek (*SM)[X] = B; 40a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek return B; 41a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek } 42a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek 43eea0d9361de0c400a58bd7c1f23e3edee7b028d9Ted Kremenek X = PM->getParentIgnoreParens(X); 44a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek } 456bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 466bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return nullptr; 47a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek} 48a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek 49a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenekstatic void Accumulate(SMap &SM, CFGBlock *B) { 50a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek // First walk the block-level expressions. 51a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek for (CFGBlock::iterator I = B->begin(), E = B->end(); I != E; ++I) { 52a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek const CFGElement &CE = *I; 53b07805485c603be3d8011f72611465324c9e664bDavid Blaikie Optional<CFGStmt> CS = CE.getAs<CFGStmt>(); 543c0349e87cdbd7316d06d2411d86ee1086e717a5Ted Kremenek if (!CS) 55b36cd3e1757fb4fcd9509f35558c847b04bef35fZhongxing Xu continue; 56b36cd3e1757fb4fcd9509f35558c847b04bef35fZhongxing Xu 57b07805485c603be3d8011f72611465324c9e664bDavid Blaikie CFGBlock *&Entry = SM[CS->getStmt()]; 58b36cd3e1757fb4fcd9509f35558c847b04bef35fZhongxing Xu // If 'Entry' is already initialized (e.g., a terminator was already), 59b36cd3e1757fb4fcd9509f35558c847b04bef35fZhongxing Xu // skip. 60b36cd3e1757fb4fcd9509f35558c847b04bef35fZhongxing Xu if (Entry) 61b36cd3e1757fb4fcd9509f35558c847b04bef35fZhongxing Xu continue; 62a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek 63b36cd3e1757fb4fcd9509f35558c847b04bef35fZhongxing Xu Entry = B; 64b36cd3e1757fb4fcd9509f35558c847b04bef35fZhongxing Xu 65a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek } 66a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek 67a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek // Look at the label of the block. 68a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek if (Stmt *Label = B->getLabel()) 69a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek SM[Label] = B; 70a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek 71a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek // Finally, look at the terminator. If the terminator was already added 72a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek // because it is a block-level expression in another block, overwrite 73a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek // that mapping. 74a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek if (Stmt *Term = B->getTerminator()) 75a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek SM[Term] = B; 76a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek} 77a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek 78a6d69302d7c86b1c71b9c18493bb811f7d152075Ted KremenekCFGStmtMap *CFGStmtMap::Build(CFG *C, ParentMap *PM) { 79a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek if (!C || !PM) 806bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return nullptr; 81a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek 82a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek SMap *SM = new SMap(); 83a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek 84a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek // Walk all blocks, accumulating the block-level expressions, labels, 85a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek // and terminators. 86a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek for (CFG::iterator I = C->begin(), E = C->end(); I != E; ++I) 87a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek Accumulate(*SM, *I); 88a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek 89a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek return new CFGStmtMap(PM, SM); 90a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek} 91a6d69302d7c86b1c71b9c18493bb811f7d152075Ted Kremenek 92