FunctionSummary.h revision 176edba5311f6eff0cad2631449885ddf4fbc9ea
1e62f048960645b79363408fdead53fec2a063c52Anna Zaks//== FunctionSummary.h - Stores summaries of functions. ------------*- C++ -*-// 2e62f048960645b79363408fdead53fec2a063c52Anna Zaks// 3e62f048960645b79363408fdead53fec2a063c52Anna Zaks// The LLVM Compiler Infrastructure 4e62f048960645b79363408fdead53fec2a063c52Anna Zaks// 5e62f048960645b79363408fdead53fec2a063c52Anna Zaks// This file is distributed under the University of Illinois Open Source 6e62f048960645b79363408fdead53fec2a063c52Anna Zaks// License. See LICENSE.TXT for details. 7e62f048960645b79363408fdead53fec2a063c52Anna Zaks// 8e62f048960645b79363408fdead53fec2a063c52Anna Zaks//===----------------------------------------------------------------------===// 9e62f048960645b79363408fdead53fec2a063c52Anna Zaks// 10992acb2269171b6ef68694d71a36f6b7408d8e82Jordan Rose// This file defines a summary of a function gathered/used by static analysis. 11e62f048960645b79363408fdead53fec2a063c52Anna Zaks// 12e62f048960645b79363408fdead53fec2a063c52Anna Zaks//===----------------------------------------------------------------------===// 13e62f048960645b79363408fdead53fec2a063c52Anna Zaks 14176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_FUNCTIONSUMMARY_H 15176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_FUNCTIONSUMMARY_H 16e62f048960645b79363408fdead53fec2a063c52Anna Zaks 17c9092bb5eb67d859122abb69a0ef61e9249500cdJordan Rose#include "clang/Basic/LLVM.h" 18e62f048960645b79363408fdead53fec2a063c52Anna Zaks#include "llvm/ADT/DenseMap.h" 19cb0a5039c243f5b0c178e70f424adac334e5789bTed Kremenek#include "llvm/ADT/DenseSet.h" 20c9092bb5eb67d859122abb69a0ef61e9249500cdJordan Rose#include "llvm/ADT/Optional.h" 21c9092bb5eb67d859122abb69a0ef61e9249500cdJordan Rose#include "llvm/ADT/SmallBitVector.h" 2230a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth#include <deque> 23e62f048960645b79363408fdead53fec2a063c52Anna Zaks 24e62f048960645b79363408fdead53fec2a063c52Anna Zaksnamespace clang { 25c9092bb5eb67d859122abb69a0ef61e9249500cdJordan Roseclass Decl; 26c9092bb5eb67d859122abb69a0ef61e9249500cdJordan Rose 27e62f048960645b79363408fdead53fec2a063c52Anna Zaksnamespace ento { 28577f14a34457032523e59dbbbacb88ca2cd4db57Ted Kremenektypedef std::deque<Decl*> SetOfDecls; 29cb0a5039c243f5b0c178e70f424adac334e5789bTed Kremenektypedef llvm::DenseSet<const Decl*> SetOfConstDecls; 30e62f048960645b79363408fdead53fec2a063c52Anna Zaks 31e62f048960645b79363408fdead53fec2a063c52Anna Zaksclass FunctionSummariesTy { 32c9092bb5eb67d859122abb69a0ef61e9249500cdJordan Rose class FunctionSummary { 33c9092bb5eb67d859122abb69a0ef61e9249500cdJordan Rose public: 34992acb2269171b6ef68694d71a36f6b7408d8e82Jordan Rose /// Marks the IDs of the basic blocks visited during the analyzes. 35992acb2269171b6ef68694d71a36f6b7408d8e82Jordan Rose llvm::SmallBitVector VisitedBasicBlocks; 36e62f048960645b79363408fdead53fec2a063c52Anna Zaks 37e62f048960645b79363408fdead53fec2a063c52Anna Zaks /// Total number of blocks in the function. 38c9092bb5eb67d859122abb69a0ef61e9249500cdJordan Rose unsigned TotalBasicBlocks : 30; 39e62f048960645b79363408fdead53fec2a063c52Anna Zaks 40c9092bb5eb67d859122abb69a0ef61e9249500cdJordan Rose /// True if this function has been checked against the rules for which 41c9092bb5eb67d859122abb69a0ef61e9249500cdJordan Rose /// functions may be inlined. 42c9092bb5eb67d859122abb69a0ef61e9249500cdJordan Rose unsigned InlineChecked : 1; 43c9092bb5eb67d859122abb69a0ef61e9249500cdJordan Rose 44c9092bb5eb67d859122abb69a0ef61e9249500cdJordan Rose /// True if this function may be inlined. 45c9092bb5eb67d859122abb69a0ef61e9249500cdJordan Rose unsigned MayInline : 1; 46e62f048960645b79363408fdead53fec2a063c52Anna Zaks 477959671d456c916706a5f61af609d8f1fc95decfAnna Zaks /// The number of times the function has been inlined. 48992acb2269171b6ef68694d71a36f6b7408d8e82Jordan Rose unsigned TimesInlined : 32; 497959671d456c916706a5f61af609d8f1fc95decfAnna Zaks 50e62f048960645b79363408fdead53fec2a063c52Anna Zaks FunctionSummary() : 51e62f048960645b79363408fdead53fec2a063c52Anna Zaks TotalBasicBlocks(0), 52c9092bb5eb67d859122abb69a0ef61e9249500cdJordan Rose InlineChecked(0), 537959671d456c916706a5f61af609d8f1fc95decfAnna Zaks TimesInlined(0) {} 54e62f048960645b79363408fdead53fec2a063c52Anna Zaks }; 55e62f048960645b79363408fdead53fec2a063c52Anna Zaks 56992acb2269171b6ef68694d71a36f6b7408d8e82Jordan Rose typedef llvm::DenseMap<const Decl *, FunctionSummary> MapTy; 57e62f048960645b79363408fdead53fec2a063c52Anna Zaks MapTy Map; 58e62f048960645b79363408fdead53fec2a063c52Anna Zaks 59e62f048960645b79363408fdead53fec2a063c52Anna Zakspublic: 60e62f048960645b79363408fdead53fec2a063c52Anna Zaks MapTy::iterator findOrInsertSummary(const Decl *D) { 61e62f048960645b79363408fdead53fec2a063c52Anna Zaks MapTy::iterator I = Map.find(D); 62e62f048960645b79363408fdead53fec2a063c52Anna Zaks if (I != Map.end()) 63e62f048960645b79363408fdead53fec2a063c52Anna Zaks return I; 64992acb2269171b6ef68694d71a36f6b7408d8e82Jordan Rose 65992acb2269171b6ef68694d71a36f6b7408d8e82Jordan Rose typedef std::pair<const Decl *, FunctionSummary> KVPair; 66992acb2269171b6ef68694d71a36f6b7408d8e82Jordan Rose I = Map.insert(KVPair(D, FunctionSummary())).first; 67e62f048960645b79363408fdead53fec2a063c52Anna Zaks assert(I != Map.end()); 68e62f048960645b79363408fdead53fec2a063c52Anna Zaks return I; 69e62f048960645b79363408fdead53fec2a063c52Anna Zaks } 70e62f048960645b79363408fdead53fec2a063c52Anna Zaks 71c9092bb5eb67d859122abb69a0ef61e9249500cdJordan Rose void markMayInline(const Decl *D) { 72e62f048960645b79363408fdead53fec2a063c52Anna Zaks MapTy::iterator I = findOrInsertSummary(D); 73c9092bb5eb67d859122abb69a0ef61e9249500cdJordan Rose I->second.InlineChecked = 1; 74c9092bb5eb67d859122abb69a0ef61e9249500cdJordan Rose I->second.MayInline = 1; 75e62f048960645b79363408fdead53fec2a063c52Anna Zaks } 76e62f048960645b79363408fdead53fec2a063c52Anna Zaks 77c9092bb5eb67d859122abb69a0ef61e9249500cdJordan Rose void markShouldNotInline(const Decl *D) { 78c9092bb5eb67d859122abb69a0ef61e9249500cdJordan Rose MapTy::iterator I = findOrInsertSummary(D); 79c9092bb5eb67d859122abb69a0ef61e9249500cdJordan Rose I->second.InlineChecked = 1; 80c9092bb5eb67d859122abb69a0ef61e9249500cdJordan Rose I->second.MayInline = 0; 81c9092bb5eb67d859122abb69a0ef61e9249500cdJordan Rose } 82c9092bb5eb67d859122abb69a0ef61e9249500cdJordan Rose 83c9092bb5eb67d859122abb69a0ef61e9249500cdJordan Rose void markReachedMaxBlockCount(const Decl *D) { 84c9092bb5eb67d859122abb69a0ef61e9249500cdJordan Rose markShouldNotInline(D); 85c9092bb5eb67d859122abb69a0ef61e9249500cdJordan Rose } 86c9092bb5eb67d859122abb69a0ef61e9249500cdJordan Rose 87c9092bb5eb67d859122abb69a0ef61e9249500cdJordan Rose Optional<bool> mayInline(const Decl *D) { 88c9092bb5eb67d859122abb69a0ef61e9249500cdJordan Rose MapTy::const_iterator I = Map.find(D); 89c9092bb5eb67d859122abb69a0ef61e9249500cdJordan Rose if (I != Map.end() && I->second.InlineChecked) 90c9092bb5eb67d859122abb69a0ef61e9249500cdJordan Rose return I->second.MayInline; 91c9092bb5eb67d859122abb69a0ef61e9249500cdJordan Rose return None; 92e62f048960645b79363408fdead53fec2a063c52Anna Zaks } 93e62f048960645b79363408fdead53fec2a063c52Anna Zaks 94e62f048960645b79363408fdead53fec2a063c52Anna Zaks void markVisitedBasicBlock(unsigned ID, const Decl* D, unsigned TotalIDs) { 95e62f048960645b79363408fdead53fec2a063c52Anna Zaks MapTy::iterator I = findOrInsertSummary(D); 96992acb2269171b6ef68694d71a36f6b7408d8e82Jordan Rose llvm::SmallBitVector &Blocks = I->second.VisitedBasicBlocks; 97e62f048960645b79363408fdead53fec2a063c52Anna Zaks assert(ID < TotalIDs); 98e62f048960645b79363408fdead53fec2a063c52Anna Zaks if (TotalIDs > Blocks.size()) { 99e62f048960645b79363408fdead53fec2a063c52Anna Zaks Blocks.resize(TotalIDs); 100992acb2269171b6ef68694d71a36f6b7408d8e82Jordan Rose I->second.TotalBasicBlocks = TotalIDs; 101e62f048960645b79363408fdead53fec2a063c52Anna Zaks } 102992acb2269171b6ef68694d71a36f6b7408d8e82Jordan Rose Blocks.set(ID); 103e62f048960645b79363408fdead53fec2a063c52Anna Zaks } 104e62f048960645b79363408fdead53fec2a063c52Anna Zaks 105e62f048960645b79363408fdead53fec2a063c52Anna Zaks unsigned getNumVisitedBasicBlocks(const Decl* D) { 106e62f048960645b79363408fdead53fec2a063c52Anna Zaks MapTy::const_iterator I = Map.find(D); 1077959671d456c916706a5f61af609d8f1fc95decfAnna Zaks if (I != Map.end()) 108992acb2269171b6ef68694d71a36f6b7408d8e82Jordan Rose return I->second.VisitedBasicBlocks.count(); 109e62f048960645b79363408fdead53fec2a063c52Anna Zaks return 0; 110e62f048960645b79363408fdead53fec2a063c52Anna Zaks } 111e62f048960645b79363408fdead53fec2a063c52Anna Zaks 1127959671d456c916706a5f61af609d8f1fc95decfAnna Zaks unsigned getNumTimesInlined(const Decl* D) { 1137959671d456c916706a5f61af609d8f1fc95decfAnna Zaks MapTy::const_iterator I = Map.find(D); 1147959671d456c916706a5f61af609d8f1fc95decfAnna Zaks if (I != Map.end()) 115992acb2269171b6ef68694d71a36f6b7408d8e82Jordan Rose return I->second.TimesInlined; 1167959671d456c916706a5f61af609d8f1fc95decfAnna Zaks return 0; 1177959671d456c916706a5f61af609d8f1fc95decfAnna Zaks } 1187959671d456c916706a5f61af609d8f1fc95decfAnna Zaks 1197959671d456c916706a5f61af609d8f1fc95decfAnna Zaks void bumpNumTimesInlined(const Decl* D) { 1207959671d456c916706a5f61af609d8f1fc95decfAnna Zaks MapTy::iterator I = findOrInsertSummary(D); 121992acb2269171b6ef68694d71a36f6b7408d8e82Jordan Rose I->second.TimesInlined++; 1227959671d456c916706a5f61af609d8f1fc95decfAnna Zaks } 1237959671d456c916706a5f61af609d8f1fc95decfAnna Zaks 124cd863466b97cee866370bc6ff75370628ab01d37Anna Zaks /// Get the percentage of the reachable blocks. 125cd863466b97cee866370bc6ff75370628ab01d37Anna Zaks unsigned getPercentBlocksReachable(const Decl *D) { 126cd863466b97cee866370bc6ff75370628ab01d37Anna Zaks MapTy::const_iterator I = Map.find(D); 127cd863466b97cee866370bc6ff75370628ab01d37Anna Zaks if (I != Map.end()) 128992acb2269171b6ef68694d71a36f6b7408d8e82Jordan Rose return ((I->second.VisitedBasicBlocks.count() * 100) / 129992acb2269171b6ef68694d71a36f6b7408d8e82Jordan Rose I->second.TotalBasicBlocks); 130cd863466b97cee866370bc6ff75370628ab01d37Anna Zaks return 0; 131cd863466b97cee866370bc6ff75370628ab01d37Anna Zaks } 132cd863466b97cee866370bc6ff75370628ab01d37Anna Zaks 133e62f048960645b79363408fdead53fec2a063c52Anna Zaks unsigned getTotalNumBasicBlocks(); 134e62f048960645b79363408fdead53fec2a063c52Anna Zaks unsigned getTotalNumVisitedBasicBlocks(); 135cd863466b97cee866370bc6ff75370628ab01d37Anna Zaks 136e62f048960645b79363408fdead53fec2a063c52Anna Zaks}; 137e62f048960645b79363408fdead53fec2a063c52Anna Zaks 138e62f048960645b79363408fdead53fec2a063c52Anna Zaks}} // end clang ento namespaces 139e62f048960645b79363408fdead53fec2a063c52Anna Zaks 140e62f048960645b79363408fdead53fec2a063c52Anna Zaks#endif 141