1d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis//==- BlockCounter.h - ADT for counting block visits -------------*- C++ -*-// 21eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump// 38e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek// The LLVM Compiler Infrastructure 48e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek// 58e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek// This file is distributed under the University of Illinois Open Source 68e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek// License. See LICENSE.TXT for details. 78e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek// 88e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek//===----------------------------------------------------------------------===// 98e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek// 10d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis// This file defines BlockCounter, an abstract data type used to count 118e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek// the number of times a given block has been visited along a path 12d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis// analyzed by CoreEngine. 138e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek// 148e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek//===----------------------------------------------------------------------===// 158e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek 169b663716449b618ba0390b1dbebc54fa8e971124Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h" 178e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek#include "llvm/ADT/ImmutableMap.h" 188e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek 198e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenekusing namespace clang; 209ef6537a894c33003359b1f9b9676e9178e028b7Ted Kremenekusing namespace ento; 218e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek 22d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xunamespace { 23d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu 24d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xuclass CountKey { 25d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu const StackFrameContext *CallSite; 26d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu unsigned BlockID; 27d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu 28d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xupublic: 29d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu CountKey(const StackFrameContext *CS, unsigned ID) 30d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu : CallSite(CS), BlockID(ID) {} 31d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu 32d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu bool operator==(const CountKey &RHS) const { 33d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu return (CallSite == RHS.CallSite) && (BlockID == RHS.BlockID); 34d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu } 35d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu 36d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu bool operator<(const CountKey &RHS) const { 37651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return std::tie(CallSite, BlockID) < std::tie(RHS.CallSite, RHS.BlockID); 38d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu } 39d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu 40d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu void Profile(llvm::FoldingSetNodeID &ID) const { 41d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu ID.AddPointer(CallSite); 42d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu ID.AddInteger(BlockID); 43d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu } 44d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu}; 45d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu 46d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu} 47d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu 48d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xutypedef llvm::ImmutableMap<CountKey, unsigned> CountMap; 498e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek 509c378f705405d37f49795d5e915989de774fe11fTed Kremenekstatic inline CountMap GetMap(void *D) { 518e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek return CountMap(static_cast<CountMap::TreeTy*>(D)); 528e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek} 538e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek 549c378f705405d37f49795d5e915989de774fe11fTed Kremenekstatic inline CountMap::Factory& GetFactory(void *F) { 558e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek return *static_cast<CountMap::Factory*>(F); 568e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek} 578e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek 58d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisunsigned BlockCounter::getNumVisited(const StackFrameContext *CallSite, 59d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu unsigned BlockID) const { 608e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek CountMap M = GetMap(Data); 61d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu CountMap::data_type* T = M.lookup(CountKey(CallSite, BlockID)); 62e8fdc83ee4819336f5b201e2aa14d0dddcf14b63Ted Kremenek return T ? *T : 0; 638e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek} 648e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek 65d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios KyrtzidisBlockCounter::Factory::Factory(llvm::BumpPtrAllocator& Alloc) { 668e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek F = new CountMap::Factory(Alloc); 678e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek} 688e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek 69d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios KyrtzidisBlockCounter::Factory::~Factory() { 705617fae5418ad2dcaf69e2422f8087a2bdb82a76Ted Kremenek delete static_cast<CountMap::Factory*>(F); 718e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek} 728e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek 73d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios KyrtzidisBlockCounter 74d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios KyrtzidisBlockCounter::Factory::IncrementCount(BlockCounter BC, 75d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu const StackFrameContext *CallSite, 76d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu unsigned BlockID) { 77d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis return BlockCounter(GetFactory(F).add(GetMap(BC.Data), 78d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu CountKey(CallSite, BlockID), 79d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu BC.getNumVisited(CallSite, BlockID)+1).getRoot()); 808e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek} 818e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek 82d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios KyrtzidisBlockCounter 83d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios KyrtzidisBlockCounter::Factory::GetEmptyCounter() { 84d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis return BlockCounter(GetFactory(F).getEmptyMap().getRoot()); 858e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek} 86