1 //===- FunctionSummary.h - Stores summaries of functions. -------*- 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 defines a summary of a function gathered/used by static analysis.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_FUNCTIONSUMMARY_H
15 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_FUNCTIONSUMMARY_H
16 
17 #include "clang/AST/Decl.h"
18 #include "clang/Basic/LLVM.h"
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/DenseSet.h"
21 #include "llvm/ADT/None.h"
22 #include "llvm/ADT/Optional.h"
23 #include "llvm/ADT/SmallBitVector.h"
24 #include <cassert>
25 #include <deque>
26 #include <utility>
27 
28 namespace clang {
29 namespace ento {
30 
31 using SetOfDecls = std::deque<Decl *>;
32 using SetOfConstDecls = llvm::DenseSet<const Decl *>;
33 
34 class FunctionSummariesTy {
35   class FunctionSummary {
36   public:
37     /// Marks the IDs of the basic blocks visited during the analyzes.
38     llvm::SmallBitVector VisitedBasicBlocks;
39 
40     /// Total number of blocks in the function.
41     unsigned TotalBasicBlocks : 30;
42 
43     /// True if this function has been checked against the rules for which
44     /// functions may be inlined.
45     unsigned InlineChecked : 1;
46 
47     /// True if this function may be inlined.
48     unsigned MayInline : 1;
49 
50     /// The number of times the function has been inlined.
51     unsigned TimesInlined : 32;
52 
FunctionSummary()53     FunctionSummary()
54         : TotalBasicBlocks(0), InlineChecked(0), MayInline(0),
55           TimesInlined(0) {}
56   };
57 
58   using MapTy = llvm::DenseMap<const Decl *, FunctionSummary>;
59   MapTy Map;
60 
61 public:
findOrInsertSummary(const Decl * D)62   MapTy::iterator findOrInsertSummary(const Decl *D) {
63     MapTy::iterator I = Map.find(D);
64     if (I != Map.end())
65       return I;
66 
67     using KVPair = std::pair<const Decl *, FunctionSummary>;
68 
69     I = Map.insert(KVPair(D, FunctionSummary())).first;
70     assert(I != Map.end());
71     return I;
72   }
73 
markMayInline(const Decl * D)74   void markMayInline(const Decl *D) {
75     MapTy::iterator I = findOrInsertSummary(D);
76     I->second.InlineChecked = 1;
77     I->second.MayInline = 1;
78   }
79 
markShouldNotInline(const Decl * D)80   void markShouldNotInline(const Decl *D) {
81     MapTy::iterator I = findOrInsertSummary(D);
82     I->second.InlineChecked = 1;
83     I->second.MayInline = 0;
84   }
85 
markReachedMaxBlockCount(const Decl * D)86   void markReachedMaxBlockCount(const Decl *D) {
87     markShouldNotInline(D);
88   }
89 
mayInline(const Decl * D)90   Optional<bool> mayInline(const Decl *D) {
91     MapTy::const_iterator I = Map.find(D);
92     if (I != Map.end() && I->second.InlineChecked)
93       return I->second.MayInline;
94     return None;
95   }
96 
markVisitedBasicBlock(unsigned ID,const Decl * D,unsigned TotalIDs)97   void markVisitedBasicBlock(unsigned ID, const Decl* D, unsigned TotalIDs) {
98     MapTy::iterator I = findOrInsertSummary(D);
99     llvm::SmallBitVector &Blocks = I->second.VisitedBasicBlocks;
100     assert(ID < TotalIDs);
101     if (TotalIDs > Blocks.size()) {
102       Blocks.resize(TotalIDs);
103       I->second.TotalBasicBlocks = TotalIDs;
104     }
105     Blocks.set(ID);
106   }
107 
getNumVisitedBasicBlocks(const Decl * D)108   unsigned getNumVisitedBasicBlocks(const Decl* D) {
109     MapTy::const_iterator I = Map.find(D);
110     if (I != Map.end())
111       return I->second.VisitedBasicBlocks.count();
112     return 0;
113   }
114 
getNumTimesInlined(const Decl * D)115   unsigned getNumTimesInlined(const Decl* D) {
116     MapTy::const_iterator I = Map.find(D);
117     if (I != Map.end())
118       return I->second.TimesInlined;
119     return 0;
120   }
121 
bumpNumTimesInlined(const Decl * D)122   void bumpNumTimesInlined(const Decl* D) {
123     MapTy::iterator I = findOrInsertSummary(D);
124     I->second.TimesInlined++;
125   }
126 
127   /// Get the percentage of the reachable blocks.
getPercentBlocksReachable(const Decl * D)128   unsigned getPercentBlocksReachable(const Decl *D) {
129     MapTy::const_iterator I = Map.find(D);
130       if (I != Map.end())
131         return ((I->second.VisitedBasicBlocks.count() * 100) /
132                  I->second.TotalBasicBlocks);
133     return 0;
134   }
135 
136   unsigned getTotalNumBasicBlocks();
137   unsigned getTotalNumVisitedBasicBlocks();
138 };
139 
140 } // namespace ento
141 } // namespace clang
142 
143 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_FUNCTIONSUMMARY_H
144