1 /*
2 This file is part of KCachegrind.
3
4 SPDX-FileCopyrightText: 2002-2016 Josef Weidendorfer <Josef.Weidendorfer@gmx.de>
5
6 SPDX-License-Identifier: GPL-2.0-only
7 */
8
9 /*
10 * Function Coverage Analysis
11 */
12
13 #include "coverage.h"
14
15 //#define DEBUG_COVERAGE 1
16
17 EventType* Coverage::_costType;
18
19 const int Coverage::maxHistogramDepth = maxHistogramDepthValue;
20 const int Coverage::Rtti = 1;
21
Coverage()22 Coverage::Coverage()
23 {
24 }
25
init()26 void Coverage::init()
27 {
28 _self = 0.0;
29 _incl = 0.0;
30 _callCount = 0.0;
31 // should always be overwritten before usage
32 _firstPercentage = 1.0;
33 _minDistance = 9999;
34 _maxDistance = 0;
35 _active = false;
36 _inRecursion = false;
37 for (int i = 0;i<maxHistogramDepth;i++) {
38 _selfHisto[i] = 0.0;
39 _inclHisto[i] = 0.0;
40 }
41
42 _valid = true;
43 }
44
inclusiveMedian()45 int Coverage::inclusiveMedian()
46 {
47 double maxP = _inclHisto[0];
48 int medD = 0;
49 for (int i = 1;i<maxHistogramDepth;i++)
50 if (_inclHisto[i]>maxP) {
51 maxP = _inclHisto[i];
52 medD = i;
53 }
54
55 return medD;
56 }
57
selfMedian()58 int Coverage::selfMedian()
59 {
60 double maxP = _selfHisto[0];
61 int medD = 0;
62 for (int i = 1;i<maxHistogramDepth;i++)
63 if (_selfHisto[i]>maxP) {
64 maxP = _selfHisto[i];
65 medD = i;
66 }
67
68 return medD;
69 }
70
coverage(TraceFunction * f,CoverageMode m,EventType * ct)71 TraceFunctionList Coverage::coverage(TraceFunction* f, CoverageMode m,
72 EventType* ct)
73 {
74 invalidate(f->data(), Coverage::Rtti);
75
76 _costType = ct;
77
78 // function f takes ownership over c!
79 Coverage* c = new Coverage();
80 c->setFunction(f);
81 c->init();
82
83 TraceFunctionList l;
84
85 if (m == Caller)
86 c->addCallerCoverage(l, 1.0, 0);
87 else
88 c->addCallingCoverage(l, 1.0, 1.0, 0);
89
90 return l;
91 }
92
addCallerCoverage(TraceFunctionList & fList,double pBack,int d)93 void Coverage::addCallerCoverage(TraceFunctionList& fList,
94 double pBack, int d)
95 {
96 if (_inRecursion) return;
97
98 double incl;
99 incl = (double) (_function->inclusive()->subCost(_costType));
100
101 if (_active) {
102 #ifdef DEBUG_COVERAGE
103 qDebug("CallerCov: D %d, %s (was active, incl %f, self %f): newP %f", d,
104 qPrintable(_function->prettyName()), _incl, _self, pBack);
105 #endif
106 _inRecursion = true;
107 }
108 else {
109 _active = true;
110
111 // only add cost if this is no recursion
112
113 _incl += pBack;
114 _firstPercentage = pBack;
115
116 if (_minDistance > d) _minDistance = d;
117 if (_maxDistance < d) _maxDistance = d;
118 if (d<maxHistogramDepth) {
119 _inclHisto[d] += pBack;
120 }
121 else {
122 _inclHisto[maxHistogramDepth-1] += pBack;
123 }
124
125 #ifdef DEBUG_COVERAGE
126 qDebug("CallerCov: D %d, %s (now active, new incl %f): newP %f",
127 d, qPrintable(_function->prettyName()), _incl, pBack);
128 #endif
129 }
130
131 double callVal, pBackNew;
132
133 foreach(TraceCall* call, _function->callers()) {
134 if (call->inCycle()>0) continue;
135 if (call->isRecursion()) continue;
136
137 if (call->subCost(_costType)>0) {
138 TraceFunction* caller = call->caller();
139
140 Coverage* c = (Coverage*) caller->association(rtti());
141 if (!c) {
142 c = new Coverage();
143 c->setFunction(caller);
144 }
145 if (!c->isValid()) {
146 c->init();
147 fList.append(caller);
148 }
149
150 if (c->isActive()) continue;
151 if (c->inRecursion()) continue;
152
153 callVal = (double) call->subCost(_costType);
154 pBackNew = pBack * (callVal / incl);
155
156 // FIXME ?!?
157
158 if (!c->isActive()) {
159 if (d>=0)
160 c->callCount() += (double)call->callCount();
161 else
162 c->callCount() += _callCount;
163 }
164 else {
165 // adjust pNew by sum of geometric series of recursion factor.
166 // Thus we can avoid endless recursion here
167 pBackNew *= 1.0 / (1.0 - pBackNew / c->firstPercentage());
168 }
169
170 // Limit depth
171 if (pBackNew > 0.0001)
172 c->addCallerCoverage(fList, pBackNew, d+1);
173 }
174 }
175
176 if (_inRecursion)
177 _inRecursion = false;
178 else if (_active)
179 _active = false;
180 }
181
182 /**
183 * pForward is time on percent used,
184 * pBack is given to allow for calculation of call counts
185 */
addCallingCoverage(TraceFunctionList & fList,double pForward,double pBack,int d)186 void Coverage::addCallingCoverage(TraceFunctionList& fList,
187 double pForward, double pBack, int d)
188 {
189 if (_inRecursion) return;
190
191 #ifdef DEBUG_COVERAGE
192 static const char* spaces = " ";
193 #endif
194
195 double self, incl;
196 incl = (double) (_function->inclusive()->subCost(_costType));
197
198 #ifdef DEBUG_COVERAGE
199 qDebug("CngCov:%s - %s (incl %f, self %f): forward %f, back %f",
200 spaces+strlen(spaces)-d,
201 qPrintable(_function->prettyName()), _incl, _self, pForward, pBack);
202 #endif
203
204
205 if (_active) {
206 _inRecursion = true;
207
208 #ifdef DEBUG_COVERAGE
209 qDebug("CngCov:%s < %s: STOP (is active)",
210 spaces+strlen(spaces)-d,
211 qPrintable(_function->prettyName()));
212 #endif
213
214 }
215 else {
216 _active = true;
217
218 // only add cost if this is no recursion
219 self = pForward * (_function->subCost(_costType)) / incl;
220 _incl += pForward;
221 _self += self;
222 _firstPercentage = pForward;
223
224 if (_minDistance > d) _minDistance = d;
225 if (_maxDistance < d) _maxDistance = d;
226 if (d<maxHistogramDepth) {
227 _inclHisto[d] += pForward;
228 _selfHisto[d] += self;
229 }
230 else {
231 _inclHisto[maxHistogramDepth-1] += pForward;
232 _selfHisto[maxHistogramDepth-1] += self;
233 }
234
235 #ifdef DEBUG_COVERAGE
236 qDebug("CngCov:%s < %s (incl %f, self %f)",
237 spaces+strlen(spaces)-d,
238 qPrintable(_function->prettyName()), _incl, _self);
239 #endif
240 }
241
242 double callVal, pForwardNew, pBackNew;
243
244 foreach(TraceCall* call, _function->callings()) {
245 if (call->inCycle()>0) continue;
246 if (call->isRecursion()) continue;
247
248 if (call->subCost(_costType)>0) {
249 TraceFunction* calling = call->called();
250
251 Coverage* c = (Coverage*) calling->association(rtti());
252 if (!c) {
253 c = new Coverage();
254 c->setFunction(calling);
255 }
256 if (!c->isValid()) {
257 c->init();
258 fList.append(calling);
259 }
260
261 if (c->isActive()) continue;
262 if (c->inRecursion()) continue;
263
264 callVal = (double) call->subCost(_costType);
265 pForwardNew = pForward * (callVal / incl);
266 pBackNew = pBack * (callVal /
267 calling->inclusive()->subCost(_costType));
268
269 if (!c->isActive()) {
270 c->callCount() += pBack * call->callCount();
271
272 #ifdef DEBUG_COVERAGE
273 qDebug("CngCov:%s > %s: forward %f, back %f, calls %f -> %f, now %f",
274 spaces+strlen(spaces)-d,
275 qPrintable(calling->prettyName()),
276 pForwardNew, pBackNew,
277 (double)call->callCount(),
278 pBack * call->callCount(),
279 c->callCount());
280 #endif
281 }
282 else {
283 // adjust pNew by sum of geometric series of recursion factor.
284 // Thus we can avoid endless recursion here
285 double fFactor = 1.0 / (1.0 - pForwardNew / c->firstPercentage());
286 double bFactor = 1.0 / (1.0 - pBackNew);
287 #ifdef DEBUG_COVERAGE
288 qDebug("CngCov:%s Recursion - origP %f, actP %f => factor %f, newP %f",
289 spaces+strlen(spaces)-d,
290 c->firstPercentage(), pForwardNew,
291 fFactor, pForwardNew * fFactor);
292 #endif
293 pForwardNew *= fFactor;
294 pBackNew *= bFactor;
295
296 }
297
298 // Limit depth
299 if (pForwardNew > 0.0001)
300 c->addCallingCoverage(fList, pForwardNew, pBackNew, d+1);
301 }
302 }
303
304 if (_inRecursion)
305 _inRecursion = false;
306 else if (_active)
307 _active = false;
308 }
309
310