 |
|
 |
|
| Files: |
1 |
|
Branches Taken: |
36.2% |
152 / 420 |
| Generated: |
2009-05-17 22:47 |
|
Branches Executed: |
42.4% |
178 / 420 |
| |
|
Line Coverage: |
57.0% |
244 / 428 |
| |
 |
|
 |
1 : /* -*- mode: c++; c-basic-offset: 2; -*- */
2 :
3 : #include "Common.h"
4 :
5 : #include "StatsTracker.h"
6 :
7 : #include "klee/ExecutionState.h"
8 : #include "klee/Statistics.h"
9 : #include "klee/Internal/Module/InstructionInfoTable.h"
10 : #include "klee/Internal/Module/KModule.h"
11 : #include "klee/Internal/Module/KInstruction.h"
12 : #include "klee/Internal/Support/ModuleUtil.h"
13 : #include "klee/Internal/System/Time.h"
14 :
15 : #include "CallPathManager.h"
16 : #include "CoreStats.h"
17 : #include "Executor.h"
18 : #include "MemoryManager.h"
19 : #include "UserSearcher.h"
20 : #include "../Solver/SolverStats.h"
21 :
22 : #include "llvm/BasicBlock.h"
23 : #include "llvm/Function.h"
24 : #include "llvm/Instructions.h"
25 : #include "llvm/IntrinsicInst.h"
26 : #include "llvm/InlineAsm.h"
27 : #include "llvm/Module.h"
28 : #include "llvm/Type.h"
29 : #include "llvm/Support/CommandLine.h"
30 : #include "llvm/Support/CFG.h"
31 : #include "llvm/System/Process.h"
32 : #include "llvm/System/Path.h"
33 :
34 : #include <iostream>
35 : #include <fstream>
36 :
37 : #include "klee/Internal/FIXME/sugar.h"
38 :
39 : using namespace klee;
40 : using namespace llvm;
41 :
42 : ///
43 :
44 : namespace {
45 : cl::opt<bool>
46 103: TrackInstructionTime("track-instruction-time",
47 : cl::desc("Enable tracking of time for individual instructions"),
48 103: cl::init(false));
49 :
50 : cl::opt<bool>
51 103: OutputStats("output-stats",
52 : cl::desc("Write running stats trace file"),
53 103: cl::init(true));
54 :
55 : cl::opt<bool>
56 103: OutputIStats("output-istats",
57 : cl::desc("Write instruction level statistics (in callgrind format)"),
58 103: cl::init(true));
59 :
60 : cl::opt<double>
61 103: StatsWriteInterval("stats-write-interval",
62 : cl::desc("Approximate number of seconds between stats writes (default: 1.0)"),
63 103: cl::init(1.));
64 :
65 : cl::opt<double>
66 103: IStatsWriteInterval("istats-write-interval",
67 : cl::desc("Approximate number of seconds between istats writes (default: 10.0)"),
68 103: cl::init(10.));
69 :
70 :
71 : // termStates.branches: output branch sequence and coverage for each
72 : // terminated state
73 : cl::opt<bool>
74 103: OutputBranchCovCounts("output-branch-cov-counts",
75 : cl::desc("Output branch coverage details to termStates.branches"),
76 103: cl::init(false));
77 :
78 : cl::opt<bool>
79 103: OutputDetailedBranchCovCounts("detailed-branch-seqs",
80 : cl::desc("Add extra details to termStates.branches (that make file sizes much larger)"),
81 103: cl::init(false));
82 :
83 :
84 : /*
85 : cl::opt<double>
86 : BranchCovCountsWriteInterval("branch-cov-counts-write-interval",
87 : cl::desc("Approximate number of seconds between run.branches writes (default: 5.0)"),
88 : cl::init(5.));
89 : */
90 :
91 : // XXX I really would like to have dynamic rate control for something like this.
92 : cl::opt<double>
93 103: UncoveredUpdateInterval("uncovered-update-interval",
94 103: cl::init(30.));
95 :
96 : cl::opt<bool>
97 103: UseCallPaths("use-call-paths",
98 : cl::desc("Enable calltree tracking for instruction level statistics"),
99 103: cl::init(true));
100 :
101 : }
102 :
103 : ///
104 :
105 103: bool StatsTracker::useStatistics() {
0: branch 0 not taken
103: branch 1 taken
103: branch 2 taken
103: branch 3 taken
106 103: return OutputStats || OutputIStats;
107 : }
108 :
109 : namespace klee {
110 : class WriteIStatsTimer : public Executor::Timer {
111 : StatsTracker *statsTracker;
112 :
113 : public:
114 103: WriteIStatsTimer(StatsTracker *_statsTracker) : statsTracker(_statsTracker) {}
0: branch 1 not taken
0: branch 2 not taken
0: branch 5 not taken
0: branch 6 not taken
115 0: ~WriteIStatsTimer() {}
116 :
117 2: void run() { statsTracker->writeIStats(); }
118 : };
119 :
120 : class WriteStatsTimer : public Executor::Timer {
121 : StatsTracker *statsTracker;
122 :
123 : public:
124 103: WriteStatsTimer(StatsTracker *_statsTracker) : statsTracker(_statsTracker) {}
0: branch 1 not taken
0: branch 2 not taken
0: branch 5 not taken
0: branch 6 not taken
125 0: ~WriteStatsTimer() {}
126 :
127 33: void run() { statsTracker->writeStatsLine(); }
128 : };
129 :
0: branch 1 not taken
0: branch 2 not taken
0: branch 5 not taken
0: branch 6 not taken
130 0: class UpdateReachableTimer : public Executor::Timer {
131 : StatsTracker *statsTracker;
132 :
133 : public:
134 0: UpdateReachableTimer(StatsTracker *_statsTracker) : statsTracker(_statsTracker) {}
135 :
136 0: void run() { statsTracker->computeReachableUncovered(); }
137 : };
138 :
139 : }
140 :
141 : //
142 :
143 : /// Check for special cases where we statically know an instruction is
144 : /// uncoverable. Currently the case is an unreachable instruction
145 : /// following a noreturn call; the instruction is really only there to
146 : /// satisfy LLVM's termination requirement.
147 10484786: static bool instructionIsCoverable(Instruction *i) {
200: branch 0 taken
10484586: branch 1 taken
148 10484786: if (i->getOpcode() == Instruction::Unreachable) {
149 200: BasicBlock *bb = i->getParent();
150 : BasicBlock::iterator it(i);
0: branch 0 not taken
200: branch 1 taken
151 200: if (it==bb->begin()) {
152 0: return true;
153 : } else {
154 200: Instruction *prev = --it;
0: branch 0 not taken
200: branch 1 taken
200: branch 2 taken
200: branch 3 taken
200: branch 4 taken
0: branch 5 not taken
155 200: if (isa<CallInst>(prev) || isa<InvokeInst>(prev)) {
156 200: Function *target = getDirectCallTarget(prev);
200: branch 0 taken
0: branch 1 not taken
199: branch 2 taken
1: branch 3 taken
199: branch 4 taken
1: branch 5 taken
157 400: if (target && target->doesNotReturn())
158 199: return false;
159 : }
160 : }
161 : }
162 :
163 10484587: return true;
164 : }
165 :
166 848739: bool klee::trackBranchSeqDetails() {
848739: branch 1 taken
0: branch 2 not taken
0: branch 3 not taken
848739: branch 4 taken
167 1697478: return userSearcherRequiresBranchSequences() || OutputBranchCovCounts;
168 : }
169 :
170 : StatsTracker::StatsTracker(Executor &_executor, std::string _objectFilename,
171 : const std::vector<std::string> &excludeCovFiles,
172 103: bool _updateMinDistToUncovered)
173 : : executor(_executor),
174 : objectFilename(_objectFilename),
175 : statsFile(0),
176 : istatsFile(0),
177 : termStatesBranchesFile(0),
178 : startWallTime(util::getWallTime()),
179 : numBranches(0),
180 : fullBranches(0),
181 : partialBranches(0),
182 103: updateMinDistToUncovered(_updateMinDistToUncovered) {
183 103: KModule *km = executor.kmodule;
184 :
185 103: sys::Path module(objectFilename);
0: branch 2 not taken
103: branch 3 taken
0: branch 6 not taken
0: branch 7 not taken
186 206: if (!sys::Path(objectFilename).isAbsolute()) {
187 0: sys::Path current = sys::Path::GetCurrentDirectory();
188 0: current.appendComponent(objectFilename);
0: branch 1 not taken
0: branch 2 not taken
0: branch 4 not taken
0: branch 5 not taken
189 0: if (current.exists())
190 0: objectFilename = current.c_str();
191 : }
192 :
193 : std::set<std::string> excludeNames;
0: branch 2 not taken
103: branch 3 taken
0: branch 6 not taken
0: branch 7 not taken
194 206: foreach(it, excludeCovFiles.begin(), excludeCovFiles.end()) {
195 0: std::ifstream ifs(it->c_str());
0: branch 0 not taken
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
196 0: if (!ifs.good())
197 0: klee_error("file not found: %s", it->c_str());
198 :
199 : std::string line;
0: branch 0 not taken
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
200 0: while (!ifs.eof()) {
201 0: std::getline(ifs, line);
202 : excludeNames.insert(line);
203 : }
204 : }
205 :
206 : // make sure to ALWAYS use indexed stats when we need to
207 : // track branch cov.
0: branch 1 not taken
103: branch 2 taken
0: branch 4 not taken
0: branch 5 not taken
208 103: if (trackBranchSeqDetails()) {
209 0: OutputIStats = true;
210 : }
211 :
103: branch 0 taken
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
212 103: if (OutputIStats)
213 103: theStatisticManager->useIndexedStats(km->infos->getMaxID());
214 :
520: branch 1 taken
103: branch 2 taken
0: branch 4 not taken
0: branch 5 not taken
215 1349: foreach(it, km->functions.begin(), km->functions.end()) {
216 520: KFunction *kf = *it;
217 :
218 1040: const std::string &name = kf->function->getName();
219 520: let(lastNondigit, name.find_last_not_of("0123456789"));
220 : kf->trackCoverage = !(excludeNames.count(name) ||
520: branch 1 taken
0: branch 2 not taken
520: branch 5 taken
0: branch 6 not taken
520: branch 7 taken
0: branch 8 not taken
0: branch 11 not taken
0: branch 12 not taken
0: branch 15 not taken
0: branch 16 not taken
0: branch 17 not taken
0: branch 18 not taken
221 520: excludeNames.count(name.substr(0, lastNondigit+1)));
222 :
92853: branch 0 taken
520: branch 1 taken
520: branch 2 taken
520: branch 3 taken
223 93373: for (unsigned i=0; i<kf->numInstructions; ++i) {
224 92853: KInstruction *ki = kf->instructions[i];
225 :
92853: branch 0 taken
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
226 92853: if (OutputIStats) {
227 92853: unsigned id = ki->info->id;
228 92853: theStatisticManager->setIndex(id);
92853: branch 0 taken
0: branch 1 not taken
92654: branch 3 taken
199: branch 4 taken
92654: branch 5 taken
199: branch 6 taken
199: branch 7 taken
199: branch 8 taken
0: branch 10 not taken
0: branch 11 not taken
0: branch 12 not taken
0: branch 13 not taken
229 92853: if (kf->trackCoverage && instructionIsCoverable(ki->inst))
230 : ++stats::uncoveredInstructions;
231 : }
232 :
92853: branch 0 taken
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
233 92853: if (kf->trackCoverage) {
7915: branch 0 taken
84938: branch 1 taken
84938: branch 2 taken
84938: branch 3 taken
234 185706: if (BranchInst *bi = dyn_cast<BranchInst>(ki->inst))
3069: branch 0 taken
4846: branch 1 taken
4846: branch 2 taken
4846: branch 3 taken
235 7915: if (!bi->isUnconditional())
236 3069: numBranches++;
237 : }
238 : }
239 : }
240 :
103: branch 0 taken
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
241 103: if (OutputStats) {
242 206: statsFile = executor.interpreterHandler->openOutputFile("run.stats");
0: branch 0 not taken
103: branch 1 taken
0: branch 3 not taken
0: branch 4 not taken
243 103: assert(statsFile && "unable to open statistics trace file");
244 103: writeStatsHeader();
245 103: writeStatsLine();
246 :
247 206: executor.addTimer(new WriteStatsTimer(this), StatsWriteInterval);
248 :
0: branch 0 not taken
103: branch 1 taken
103: branch 2 taken
103: branch 3 taken
249 103: if (updateMinDistToUncovered)
250 0: executor.addTimer(new UpdateReachableTimer(this), UncoveredUpdateInterval);
251 : }
252 :
103: branch 0 taken
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
253 103: if (OutputIStats) {
254 206: istatsFile = executor.interpreterHandler->openOutputFile("run.istats");
0: branch 0 not taken
103: branch 1 taken
0: branch 3 not taken
0: branch 4 not taken
255 103: assert(istatsFile && "unable to open istats file");
256 :
257 206: executor.addTimer(new WriteIStatsTimer(this), IStatsWriteInterval);
258 : }
259 :
0: branch 0 not taken
103: branch 1 taken
103: branch 2 taken
103: branch 3 taken
260 103: if (OutputBranchCovCounts) {
261 0: termStatesBranchesFile = executor.interpreterHandler->openOutputFile("termStates.branches");
0: branch 0 not taken
0: branch 1 not taken
0: branch 3 not taken
0: branch 4 not taken
262 0: assert(termStatesBranchesFile && "unable to open termStates.branches file");
263 :
264 0: *termStatesBranchesFile << "# Each line contains a tuple with the following information for each terminated state (in termination order):" << std::endl;
265 :
0: branch 0 not taken
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
266 0: if (OutputDetailedBranchCovCounts) {
267 0: *termStatesBranchesFile << "# ( elapsed WallTime, # executed instructions, CoveredInstructions, UncoveredInstructions, covnew, branch sequence: (ID, True side taken, alreadyCoveredNew, isTwoWay)+ )" << std::endl;
268 : }
269 : else {
270 0: *termStatesBranchesFile << "# ( elapsed WallTime, # executed instructions, CoveredInstructions, UncoveredInstructions, covnew )" << std::endl;
271 : }
272 : }
273 103: }
274 :
275 103: StatsTracker::~StatsTracker() {
103: branch 0 taken
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
276 103: if (statsFile)
103: branch 0 taken
0: branch 1 not taken
103: branch 3 taken
103: branch 4 taken
277 103: delete statsFile;
103: branch 0 taken
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
278 103: if (istatsFile)
103: branch 0 taken
0: branch 1 not taken
103: branch 3 taken
103: branch 4 taken
279 103: delete istatsFile;
280 :
0: branch 0 not taken
103: branch 1 taken
103: branch 2 taken
103: branch 3 taken
281 103: if (termStatesBranchesFile)
0: branch 0 not taken
0: branch 1 not taken
0: branch 3 not taken
0: branch 4 not taken
282 0: delete termStatesBranchesFile;
283 103: }
284 :
285 103: void StatsTracker::done() {
103: branch 0 taken
0: branch 1 not taken
286 103: if (statsFile)
287 103: writeStatsLine();
103: branch 0 taken
0: branch 1 not taken
288 103: if (OutputIStats)
289 103: writeIStats();
290 103: }
291 :
292 10391933: void StatsTracker::stepInstruction(ExecutionState &es) {
10391933: branch 0 taken
0: branch 1 not taken
293 10391933: if (OutputIStats) {
0: branch 0 not taken
10391933: branch 1 taken
294 10391933: if (TrackInstructionTime) {
0: branch 0 not taken
0: branch 1 not taken
0: branch 3 not taken
0: branch 4 not taken
0: branch 6 not taken
0: branch 7 not taken
0: branch 9 not taken
0: branch 10 not taken
295 0: static sys::TimeValue lastNowTime(0,0),lastUserTime(0,0);
296 :
0: branch 0 not taken
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
0: branch 4 not taken
0: branch 5 not taken
297 0: if (lastUserTime.seconds()==0 && lastUserTime.nanoseconds()==0) {
298 : sys::TimeValue sys(0,0);
299 0: sys::Process::GetTimeUsage(lastNowTime,lastUserTime,sys);
300 : } else {
301 : sys::TimeValue now(0,0),user(0,0),sys(0,0);
302 0: sys::Process::GetTimeUsage(now,user,sys);
303 0: sys::TimeValue delta = user - lastUserTime;
304 0: sys::TimeValue deltaNow = now - lastNowTime;
305 0: stats::instructionTime += delta.usec();
306 0: stats::instructionRealTime += deltaNow.usec();
307 0: lastUserTime = user;
308 0: lastNowTime = now;
309 : }
310 : }
311 :
312 20783866: Instruction *inst = es.pc->inst;
313 20783866: const InstructionInfo &ii = *es.pc->info;
314 20783866: StackFrame &sf = es.stack.back();
315 10391933: theStatisticManager->setIndex(ii.id);
10391933: branch 0 taken
0: branch 1 not taken
316 10391933: if (UseCallPaths)
317 10391933: theStatisticManager->setContext(&sf.callPathNode->statistics);
318 :
10391830: branch 0 taken
103: branch 1 taken
319 10391933: if (es.instsSinceCovNew)
320 10391830: ++es.instsSinceCovNew;
321 :
10391933: branch 0 taken
0: branch 1 not taken
10391933: branch 3 taken
0: branch 4 not taken
10391933: branch 5 taken
0: branch 6 not taken
322 10391933: if (sf.kf->trackCoverage && instructionIsCoverable(inst)) {
31292: branch 0 taken
10360641: branch 1 taken
323 20783866: if (!theStatisticManager->getIndexedValue(stats::coveredInstructions, ii.id)) {
324 : // Checking for actual stoppoints avoids inconsistencies due
325 : // to line number propogation.
644: branch 0 taken
30648: branch 1 taken
326 31292: if (isa<DbgStopPointInst>(inst))
327 644: es.coveredLines[&ii.file].insert(ii.line);
328 31292: es.coveredNew = true;
329 31292: es.instsSinceCovNew = 1;
330 : ++stats::coveredInstructions;
331 31292: stats::uncoveredInstructions += (uint64_t)-1;
332 : }
333 : }
334 : }
335 10391933: }
336 :
337 : ///
338 :
339 : /* Should be called _after_ the es->pushFrame() */
340 1056: void StatsTracker::framePushed(ExecutionState &es, StackFrame *parentFrame) {
1056: branch 0 taken
0: branch 1 not taken
341 1056: if (OutputIStats) {
342 2112: StackFrame &sf = es.stack.back();
343 :
1056: branch 0 taken
0: branch 1 not taken
344 1056: if (UseCallPaths) {
953: branch 0 taken
103: branch 1 taken
345 1056: CallPathNode *parent = parentFrame ? parentFrame->callPathNode : 0;
346 : CallPathNode *cp = callPathManager.getCallPath(parent,
347 : sf.caller ? sf.caller->inst : 0,
953: branch 0 taken
103: branch 1 taken
348 3065: sf.kf->function);
349 1056: sf.callPathNode = cp;
350 1056: cp->count++;
351 : }
352 :
0: branch 0 not taken
1056: branch 1 taken
353 1056: if (updateMinDistToUncovered) {
354 0: uint64_t minDistAtRA = 0;
0: branch 0 not taken
0: branch 1 not taken
355 0: if (parentFrame)
356 0: minDistAtRA = parentFrame->minDistToUncoveredOnReturn;
357 :
358 : sf.minDistToUncoveredOnReturn = sf.caller ?
0: branch 0 not taken
0: branch 1 not taken
359 0: computeMinDistToUncovered(sf.caller, minDistAtRA) : 0;
360 : }
361 : }
362 1056: }
363 :
364 : /* Should be called _after_ the es->popFrame() */
365 1512: void StatsTracker::framePopped(ExecutionState &es) {
366 : // XXX remove me?
367 1512: }
368 :
369 :
370 : void StatsTracker::markBranchVisited(ExecutionState *visitedTrue,
371 847846: ExecutionState *visitedFalse) {
847846: branch 0 taken
0: branch 1 not taken
372 847846: if (OutputIStats) {
373 1695692: unsigned id = theStatisticManager->getIndex();
374 1695692: uint64_t hasTrue = theStatisticManager->getIndexedValue(stats::trueBranches, id);
375 1695692: uint64_t hasFalse = theStatisticManager->getIndexedValue(stats::falseBranches, id);
631: branch 0 taken
847215: branch 1 taken
376 847846: if (visitedTrue && !hasTrue) {
377 631: visitedTrue->coveredNew = true;
378 631: visitedTrue->instsSinceCovNew = 1;
379 : ++stats::trueBranches;
124: branch 0 taken
507: branch 1 taken
380 631: if (hasFalse) { ++fullBranches; --partialBranches; }
381 507: else ++partialBranches;
382 631: hasTrue = 1;
383 : }
670: branch 0 taken
847176: branch 1 taken
384 847846: if (visitedFalse && !hasFalse) {
385 670: visitedFalse->coveredNew = true;
386 670: visitedFalse->instsSinceCovNew = 1;
387 : ++stats::falseBranches;
273: branch 0 taken
397: branch 1 taken
388 670: if (hasTrue) { ++fullBranches; --partialBranches; }
389 397: else ++partialBranches;
390 : }
391 : }
392 847846: }
393 :
394 103: void StatsTracker::writeStatsHeader() {
395 : *statsFile << "('Instructions',"
396 : << "'FullBranches',"
397 : << "'PartialBranches',"
398 : << "'NumBranches',"
399 : << "'UserTime',"
400 : << "'NumStates',"
401 : << "'MallocUsage',"
402 : << "'NumQueries',"
403 : << "'NumQueryConstructs',"
404 : << "'NumObjects',"
405 : << "'WallTime',"
406 : << "'CoveredInstructions',"
407 : << "'UncoveredInstructions',"
408 : << "'QueryTime',"
409 : << "'SolverTime',"
410 : << "'CexCacheTime',"
411 : << "'ForkTime',"
412 : << "'ResolveTime',"
413 103: << ")\n";
414 103: statsFile->flush();
415 103: }
416 :
417 239: double StatsTracker::elapsed() {
418 239: return util::getWallTime() - startWallTime;
419 : }
420 :
421 239: void StatsTracker::writeStatsLine() {
422 : *statsFile << "(" << stats::instructions
423 : << "," << fullBranches
424 : << "," << partialBranches
425 : << "," << numBranches
426 : << "," << util::getUserTime()
427 : << "," << executor.states.size()
428 : << "," << sys::Process::GetTotalMemoryUsage()
429 : << "," << stats::queries
430 : << "," << stats::queryConstructs
431 : << "," << 0 // was numObjects
432 : << "," << elapsed()
433 : << "," << stats::coveredInstructions
434 : << "," << stats::uncoveredInstructions
435 : << "," << stats::queryTime / 1000000.
436 : << "," << stats::solverTime / 1000000.
437 : << "," << stats::cexCacheTime / 1000000.
438 : << "," << stats::forkTime / 1000000.
439 : << "," << stats::resolveTime / 1000000.
440 6214: << ")\n";
441 239: statsFile->flush();
442 239: }
443 :
444 210: void StatsTracker::updateStateStatistics(uint64_t addend) {
32: branch 0 taken
210: branch 1 taken
445 662: foreach(it, executor.states.begin(), executor.states.end()) {
446 32: ExecutionState &state = **it;
447 64: const InstructionInfo &ii = *state.pc->info;
448 32: theStatisticManager->incrementIndexedValue(stats::states, ii.id, addend);
32: branch 0 taken
0: branch 1 not taken
449 32: if (UseCallPaths)
450 64: state.stack.back().callPathNode->statistics.incrementValue(stats::states, addend);
451 : }
452 210: }
453 :
454 105: void StatsTracker::writeIStats() {
455 105: Module *m = executor.kmodule->module;
456 105: uint64_t istatsMask = 0;
457 105: std::ostream &of = *istatsFile;
458 :
459 105: of.seekp(0, std::ios::end);
460 210: unsigned istatsSize = of.tellp();
461 105: of.seekp(0);
462 :
463 105: of << "version: 1\n";
464 105: of << "creator: klee\n";
465 105: of << "pid: " << sys::Process::GetCurrentUserId() << "\n";
466 105: of << "cmd: " << m->getModuleIdentifier() << "\n\n";
467 105: of << "\n";
468 :
469 105: StatisticManager &sm = *theStatisticManager;
470 105: unsigned nStats = sm.getNumStatistics();
471 :
472 : // Max is 13, sadly
473 105: istatsMask |= 1<<sm.getStatisticID("Queries");
474 105: istatsMask |= 1<<sm.getStatisticID("QueriesValid");
475 105: istatsMask |= 1<<sm.getStatisticID("QueriesInvalid");
476 105: istatsMask |= 1<<sm.getStatisticID("QueryTime");
477 105: istatsMask |= 1<<sm.getStatisticID("ResolveTime");
478 105: istatsMask |= 1<<sm.getStatisticID("Instructions");
479 105: istatsMask |= 1<<sm.getStatisticID("InstructionTimes");
480 105: istatsMask |= 1<<sm.getStatisticID("InstructionRealTimes");
481 105: istatsMask |= 1<<sm.getStatisticID("Forks");
482 105: istatsMask |= 1<<sm.getStatisticID("CoveredInstructions");
483 105: istatsMask |= 1<<sm.getStatisticID("UncoveredInstructions");
484 105: istatsMask |= 1<<sm.getStatisticID("States");
485 105: istatsMask |= 1<<sm.getStatisticID("MinDistToUncovered");
486 :
487 105: of << "positions: instr line\n";
488 :
2730: branch 0 taken
105: branch 1 taken
489 2835: for (unsigned i=0; i<nStats; i++) {
1365: branch 0 taken
1365: branch 1 taken
490 2730: if (istatsMask & (1<<i)) {
491 1365: Statistic &s = sm.getStatistic(i);
492 : of << "event: " << s.getShortName() << " : "
493 1365: << s.getName() << "\n";
494 : }
495 : }
496 :
497 105: of << "events: ";
2730: branch 0 taken
105: branch 1 taken
498 2835: for (unsigned i=0; i<nStats; i++) {
1365: branch 0 taken
1365: branch 1 taken
499 2730: if (istatsMask & (1<<i))
500 1365: of << sm.getStatistic(i).getShortName() << " ";
501 : }
502 105: of << "\n";
503 :
504 : // set state counts, decremented after we process so that we don't
505 : // have to zero all records each time.
105: branch 0 taken
0: branch 1 not taken
506 105: if (istatsMask & (1<<stats::states.getID()))
507 105: updateStateStatistics(1);
508 :
509 105: std::string sourceFile = "";
510 :
511 : CallSiteSummaryTable callSiteStats;
105: branch 0 taken
0: branch 1 not taken
512 105: if (UseCallPaths)
513 105: callPathManager.getSummaryStatistics(callSiteStats);
514 :
515 105: of << "ob=" << objectFilename << "\n";
516 :
1134: branch 1 taken
105: branch 2 taken
517 2373: foreach(fnIt, m->begin(), m->end()) {
547: branch 1 taken
587: branch 2 taken
518 1134: if (!fnIt->isDeclaration()) {
519 1094: of << "fn=" << fnIt->getName() << "\n";
10790: branch 1 taken
547: branch 2 taken
520 22674: foreach(bbIt, fnIt->begin(), fnIt->end()) {
112790: branch 1 taken
10790: branch 2 taken
521 247160: foreach(it, bbIt->begin(), bbIt->end()) {
522 112790: Instruction *instr = &*it;
523 112790: const InstructionInfo &ii = executor.kmodule->infos->getInfo(instr);
524 112790: unsigned index = ii.id;
119: branch 0 taken
112671: branch 1 taken
525 225580: if (ii.file!=sourceFile) {
526 119: of << "fl=" << ii.file << "\n";
527 119: sourceFile = ii.file;
528 : }
529 225580: of << ii.assemblyLine << " ";
530 225580: of << ii.line << " ";
2932540: branch 0 taken
112790: branch 1 taken
531 3045330: for (unsigned i=0; i<nStats; i++)
1466270: branch 0 taken
1466270: branch 1 taken
532 2932540: if (istatsMask&(1<<i))
533 1466270: of << sm.getIndexedValue(sm.getStatistic(i), index) << " ";
534 112790: of << "\n";
535 :
112790: branch 0 taken
0: branch 1 not taken
110200: branch 2 taken
2590: branch 3 taken
2: branch 4 taken
110198: branch 5 taken
2592: branch 6 taken
110198: branch 7 taken
536 335780: if (UseCallPaths && (isa<CallInst>(instr) || isa<InvokeInst>(instr))) {
537 : let(it, callSiteStats.find(instr));
329: branch 0 taken
2263: branch 1 taken
538 2592: if (it!=callSiteStats.end()) {
330: branch 0 taken
329: branch 1 taken
539 1646: foreach(fit, it->second.begin(), it->second.end()) {
540 330: Function *f = fit->first;
541 330: CallSiteInfo &csi = fit->second;
542 330: const InstructionInfo &fii = executor.kmodule->infos->getFunctionInfo(f);
543 :
68: branch 0 taken
262: branch 1 taken
44: branch 2 taken
24: branch 3 taken
44: branch 4 taken
286: branch 5 taken
544 728: if (fii.file!="" && fii.file!=sourceFile)
545 44: of << "cfl=" << fii.file << "\n";
546 660: of << "cfn=" << f->getName() << "\n";
547 660: of << "calls=" << csi.count << " ";
548 660: of << fii.assemblyLine << " ";
549 660: of << fii.line << "\n";
550 :
551 660: of << ii.assemblyLine << " ";
552 660: of << ii.line << " ";
8580: branch 0 taken
330: branch 1 taken
553 8910: for (unsigned i=0; i<nStats; i++) {
4290: branch 0 taken
4290: branch 1 taken
554 8580: if (istatsMask&(1<<i)) {
555 4290: Statistic &s = sm.getStatistic(i);
556 : uint64_t value;
557 :
558 : // Hack, ignore things that don't make sense on
559 : // call paths.
330: branch 0 taken
3960: branch 1 taken
560 4290: if (&s == &stats::uncoveredInstructions) {
561 330: value = 0;
562 : } else {
563 7920: value = csi.statistics.getValue(s);
564 : }
565 :
566 4290: of << value << " ";
567 : }
568 : }
569 330: of << "\n";
570 : }
571 : }
572 : }
573 : }
574 : }
575 : }
576 : }
577 :
105: branch 0 taken
0: branch 1 not taken
578 105: if (istatsMask & (1<<stats::states.getID()))
579 105: updateStateStatistics((uint64_t)-1);
580 :
581 : // Clear then end of the file if necessary (no truncate op?).
582 210: unsigned pos = of.tellp();
0: branch 0 not taken
105: branch 1 taken
583 105: for (unsigned i=pos; i<istatsSize; ++i)
584 0: of << '\n';
585 :
586 210: of.flush();
587 105: }
588 :
589 : ///
590 :
591 103: static std::map<Instruction*, std::vector<Function*> > callTargets;
592 103: static std::map<Function*, std::vector<Instruction*> > functionCallers;
593 103: static std::map<Function*, unsigned> functionShortestPath;
594 :
595 0: static std::vector<Instruction*> getSuccs(Instruction *i) {
596 0: BasicBlock *bb = i->getParent();
597 0: std::vector<Instruction*> res;
598 :
0: branch 1 not taken
0: branch 2 not taken
599 0: if (i==bb->getTerminator()) {
0: branch 0 not taken
0: branch 1 not taken
600 0: foreach(it, succ_begin(bb), succ_end(bb)) {
601 0: res.push_back(it->begin());
602 : }
603 : } else {
604 0: res.push_back(++BasicBlock::iterator(i));
605 : }
606 :
607 : return res;
608 : }
609 :
610 : uint64_t klee::computeMinDistToUncovered(const KInstruction *ki,
611 0: uint64_t minDistAtRA) {
612 0: StatisticManager &sm = *theStatisticManager;
0: branch 0 not taken
0: branch 1 not taken
613 0: if (minDistAtRA==0) { // unreachable on return, best is local
614 : return sm.getIndexedValue(stats::minDistToUncovered,
615 0: ki->info->id);
616 : } else {
617 : uint64_t minDistLocal = sm.getIndexedValue(stats::minDistToUncovered,
618 0: ki->info->id);
619 : uint64_t distToReturn = sm.getIndexedValue(stats::minDistToReturn,
620 0: ki->info->id);
621 :
0: branch 0 not taken
0: branch 1 not taken
622 0: if (distToReturn==0) { // return unreachable, best is local
623 0: return minDistLocal;
0: branch 0 not taken
0: branch 1 not taken
624 0: } else if (!minDistLocal) { // no local reachable
625 0: return distToReturn + minDistAtRA;
626 : } else {
627 0: return std::min(minDistLocal, distToReturn + minDistAtRA);
628 : }
629 : }
630 : }
631 :
632 :
633 0: void StatsTracker::writeStateTerminationCounts(ExecutionState& state) {
634 : // punt if we don't want any output
0: branch 0 not taken
0: branch 1 not taken
635 0: if (!OutputBranchCovCounts) {
636 0: return;
637 : }
638 :
639 : *termStatesBranchesFile << "(" << elapsed()
640 : << "," << stats::instructions
641 : << "," << stats::coveredInstructions
642 : << "," << stats::uncoveredInstructions
643 0: << "," << state.coveredNew;
644 :
645 :
646 : // print out all the gory details of branchDecisionsSequence
0: branch 0 not taken
0: branch 1 not taken
647 0: if (OutputDetailedBranchCovCounts) {
648 0: unsigned n = state.branchDecisionsSequence.size();
0: branch 0 not taken
0: branch 1 not taken
649 0: assert(n == state.branchInfoSequence.size());
650 :
651 0: *termStatesBranchesFile << ",(";
652 :
0: branch 0 not taken
0: branch 1 not taken
653 0: for (unsigned i = 0; i < n; i++) {
654 : *termStatesBranchesFile << "("
655 : << state.branchDecisionsSequence[i].first
656 : << "," << state.branchDecisionsSequence[i].second
657 : << "," << state.branchInfoSequence[i].alreadyCoveredNew
658 : << "," << state.branchInfoSequence[i].isTwoWay
659 0: << "),";
660 : }
661 :
662 0: *termStatesBranchesFile << ")";
663 : }
664 :
665 0: *termStatesBranchesFile << ")\n";
666 :
667 0: termStatesBranchesFile->flush();
668 : }
669 :
670 :
671 0: void StatsTracker::computeReachableUncovered() {
672 0: KModule *km = executor.kmodule;
673 0: Module *m = km->module;
674 : static bool init = true;
675 0: const InstructionInfoTable &infos = *km->infos;
676 0: StatisticManager &sm = *theStatisticManager;
677 :
0: branch 0 not taken
0: branch 1 not taken
678 0: if (init) {
679 0: init = false;
680 :
681 : // Compute call targets. It would be nice to use alias information
682 : // instead of assuming all indirect calls hit all escaping
683 : // functions, eh?
0: branch 1 not taken
0: branch 2 not taken
684 0: foreach(fnIt, m->begin(), m->end()) {
0: branch 1 not taken
0: branch 2 not taken
685 0: foreach(bbIt, fnIt->begin(), fnIt->end()) {
0: branch 1 not taken
0: branch 2 not taken
686 0: foreach(it, bbIt->begin(), bbIt->end()) {
0: branch 0 not taken
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
0: branch 4 not taken
0: branch 5 not taken
687 0: if (isa<CallInst>(it) || isa<InvokeInst>(it)) {
0: branch 1 not taken
0: branch 2 not taken
688 0: if (isa<InlineAsm>(it->getOperand(0))) {
689 : // We can never call through here so assume no targets
690 : // (which should be correct anyhow).
691 : callTargets.insert(std::make_pair(it,
692 0: std::vector<Function*>()));
0: branch 2 not taken
0: branch 3 not taken
693 0: } else if (Function *target = getDirectCallTarget(it)) {
694 0: callTargets[it].push_back(target);
695 : } else {
696 : callTargets[it] = std::vector<Function*>(km->escapingFunctions.begin(),
697 0: km->escapingFunctions.end());
698 : }
699 : }
700 : }
701 : }
702 : }
703 :
704 : // Compute function callers as reflexion of callTargets.
0: branch 0 not taken
0: branch 1 not taken
705 0: foreach(it, callTargets.begin(), callTargets.end()) {
0: branch 0 not taken
0: branch 1 not taken
706 0: foreach(it2, it->second.begin(), it->second.end()) {
707 0: functionCallers[*it2].push_back(it->first);
708 : }
709 : }
710 :
711 : // Initialize minDistToReturn to shortest paths through
712 : // functions. 0 is unreachable.
713 : std::vector<Instruction *> instructions;
0: branch 1 not taken
0: branch 2 not taken
714 0: foreach(fnIt, m->begin(), m->end()) {
0: branch 1 not taken
0: branch 2 not taken
715 0: if (fnIt->isDeclaration()) {
0: branch 0 not taken
0: branch 1 not taken
716 0: if (fnIt->doesNotReturn()) {
717 0: functionShortestPath[fnIt] = 0;
718 : } else {
719 0: functionShortestPath[fnIt] = 1; // whatever
720 : }
721 : } else {
722 0: functionShortestPath[fnIt] = 0;
723 : }
724 :
725 : // Not sure if I should bother to preorder here. XXX I should.
0: branch 1 not taken
0: branch 2 not taken
726 0: foreach(bbIt, fnIt->begin(), fnIt->end()) {
0: branch 1 not taken
0: branch 2 not taken
727 0: foreach(it, bbIt->begin(), bbIt->end()) {
728 0: instructions.push_back(it);
729 0: unsigned id = infos.getInfo(it).id;
730 : sm.setIndexedValue(stats::minDistToReturn,
731 : id,
0: branch 0 not taken
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
732 0: isa<ReturnInst>(it) || isa<UnwindInst>(it));
733 : }
734 : }
735 : }
736 :
737 0: std::reverse(instructions.begin(), instructions.end());
738 :
739 : // I'm so lazy it's not even worklisted.
740 : bool changed;
0: branch 0 not taken
0: branch 1 not taken
741 0: do {
742 0: changed = false;
0: branch 0 not taken
0: branch 1 not taken
743 0: foreach(it, instructions.begin(), instructions.end()) {
744 0: Instruction *inst = *it;
745 0: unsigned bestThrough = 0;
746 :
0: branch 0 not taken
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
0: branch 4 not taken
0: branch 5 not taken
747 0: if (isa<CallInst>(inst) || isa<InvokeInst>(inst)) {
748 0: let(targets, callTargets[inst]);
0: branch 0 not taken
0: branch 1 not taken
749 0: foreach(fnIt, targets.begin(), targets.end()) {
750 0: uint64_t dist = functionShortestPath[*fnIt];
0: branch 0 not taken
0: branch 1 not taken
751 0: if (dist) {
752 0: dist = 1+dist; // count instruction itself
0: branch 0 not taken
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
753 0: if (bestThrough==0 || dist<bestThrough)
754 0: bestThrough = dist;
755 : }
756 0: }
757 : } else {
758 0: bestThrough = 1;
759 : }
760 :
0: branch 0 not taken
0: branch 1 not taken
761 0: if (bestThrough) {
762 0: unsigned id = infos.getInfo(*it).id;
763 0: uint64_t best, cur = best = sm.getIndexedValue(stats::minDistToReturn, id);
764 0: let(succs, getSuccs(*it));
0: branch 0 not taken
0: branch 1 not taken
765 0: foreach(it2, succs.begin(), succs.end()) {
766 : uint64_t dist = sm.getIndexedValue(stats::minDistToReturn,
767 0: infos.getInfo(*it2).id);
0: branch 0 not taken
0: branch 1 not taken
768 0: if (dist) {
769 0: uint64_t val = bestThrough + dist;
0: branch 0 not taken
0: branch 1 not taken
770 0: if (best==0 || val<best)
771 0: best = val;
772 : }
773 : }
0: branch 0 not taken
0: branch 1 not taken
774 0: if (best != cur) {
775 : sm.setIndexedValue(stats::minDistToReturn, id, best);
776 0: changed = true;
777 :
778 : // Update shortest path if this is the entry point.
779 0: Function *f = inst->getParent()->getParent();
0: branch 0 not taken
0: branch 1 not taken
780 0: if (inst==f->begin()->begin())
781 0: functionShortestPath[f] = best;
782 0: }
783 : }
784 : }
785 0: } while (changed);
786 : }
787 :
788 : // compute minDistToUncovered, 0 is unreachable
789 : std::vector<Instruction *> instructions;
0: branch 1 not taken
0: branch 2 not taken
790 0: foreach(fnIt, m->begin(), m->end()) {
791 : // Not sure if I should bother to preorder here.
0: branch 1 not taken
0: branch 2 not taken
792 0: foreach(bbIt, fnIt->begin(), fnIt->end()) {
0: branch 1 not taken
0: branch 2 not taken
793 0: foreach(it, bbIt->begin(), bbIt->end()) {
794 0: unsigned id = infos.getInfo(it).id;
795 0: instructions.push_back(&*it);
796 : sm.setIndexedValue(stats::minDistToUncovered,
797 : id,
798 : sm.getIndexedValue(stats::uncoveredInstructions, id));
799 : }
800 : }
801 : }
802 :
803 0: std::reverse(instructions.begin(), instructions.end());
804 :
805 : // I'm so lazy it's not even worklisted.
806 : bool changed;
0: branch 0 not taken
0: branch 1 not taken
807 0: do {
808 0: changed = false;
0: branch 0 not taken
0: branch 1 not taken
809 0: foreach(it, instructions.begin(), instructions.end()) {
810 0: Instruction *inst = *it;
811 : uint64_t best, cur = best = sm.getIndexedValue(stats::minDistToUncovered,
812 0: infos.getInfo(inst).id);
813 0: unsigned bestThrough = 0;
814 :
0: branch 0 not taken
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
0: branch 4 not taken
0: branch 5 not taken
815 0: if (isa<CallInst>(inst) || isa<InvokeInst>(inst)) {
816 0: let(targets, callTargets[inst]);
0: branch 0 not taken
0: branch 1 not taken
817 0: foreach(fnIt, targets.begin(), targets.end()) {
818 0: uint64_t dist = functionShortestPath[*fnIt];
0: branch 0 not taken
0: branch 1 not taken
819 0: if (dist) {
820 0: dist = 1+dist; // count instruction itself
0: branch 0 not taken
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
821 0: if (bestThrough==0 || dist<bestThrough)
822 0: bestThrough = dist;
823 : }
824 :
0: branch 1 not taken
0: branch 2 not taken
825 0: if (!(*fnIt)->isDeclaration()) {
826 : uint64_t calleeDist = sm.getIndexedValue(stats::minDistToUncovered,
827 0: infos.getFunctionInfo(*fnIt).id);
0: branch 0 not taken
0: branch 1 not taken
828 0: if (calleeDist) {
829 0: calleeDist = 1+calleeDist; // count instruction itself
0: branch 0 not taken
0: branch 1 not taken
830 0: if (best==0 || calleeDist<best)
831 0: best = calleeDist;
832 : }
833 : }
834 0: }
835 : } else {
836 0: bestThrough = 1;
837 : }
838 :
0: branch 0 not taken
0: branch 1 not taken
839 0: if (bestThrough) {
840 0: let(succs, getSuccs(inst));
0: branch 0 not taken
0: branch 1 not taken
841 0: foreach(it2, succs.begin(), succs.end()) {
842 : uint64_t dist = sm.getIndexedValue(stats::minDistToUncovered,
843 0: infos.getInfo(*it2).id);
0: branch 0 not taken
0: branch 1 not taken
844 0: if (dist) {
845 0: uint64_t val = bestThrough + dist;
0: branch 0 not taken
0: branch 1 not taken
846 0: if (best==0 || val<best)
847 0: best = val;
848 : }
849 0: }
850 : }
851 :
0: branch 0 not taken
0: branch 1 not taken
852 0: if (best != cur) {
853 : sm.setIndexedValue(stats::minDistToUncovered,
854 : infos.getInfo(inst).id,
855 0: best);
856 0: changed = true;
857 : }
858 : }
859 : } while (changed);
860 :
0: branch 0 not taken
0: branch 1 not taken
861 0: foreach(it, executor.states.begin(), executor.states.end()) {
862 0: ExecutionState *es = *it;
863 0: uint64_t currentFrameMinDist = 0;
0: branch 0 not taken
0: branch 1 not taken
864 0: foreach(sfIt, es->stack.begin(), es->stack.end()) {
865 0: let(next, sfIt+1);
866 : KInstIterator kii;
867 :
0: branch 0 not taken
0: branch 1 not taken
868 0: if (next==es->stack.end()) {
869 0: kii = es->pc;
870 : } else {
871 0: kii = next->caller;
872 : ++kii;
873 : }
874 :
875 0: sfIt->minDistToUncoveredOnReturn = currentFrameMinDist;
876 :
877 0: currentFrameMinDist = computeMinDistToUncovered(kii, currentFrameMinDist);
878 : }
879 :
880 : #if 0
881 : llvm::cerr << es << " ";
882 : foreach(sfIt, es->stack.begin(), es->stack.end()) {
883 : if (sfIt->caller) {
884 : llvm::cerr << infos.getInfo(sfIt->caller->inst).line << ",";
885 : }
886 : llvm::cerr << sfIt->f->getName() << ":";
887 : }
888 : llvm::cerr << " = " << currentFrameMinDist << "\n";
889 : #endif
890 0: }
891 :
892 : #if 0
893 : foreach(fnIt, m->begin(), m->end()) {
894 : foreach(bbIt, fnIt->begin(), fnIt->end()) {
895 : foreach(it, bbIt->begin(), bbIt->end()) {
896 : Instruction *instr = &*it;
897 : const InstructionInfo &ii = infos.getInfo(instr);
898 : sm.setIndexedValue(stats::reachableUncovered, ii.id, 0);
899 : }
900 : }
901 : }
902 : #endif
103: branch 0 taken
0: branch 1 not taken
103: branch 2 taken
0: branch 3 not taken
903 309: }
Generated: 2009-05-17 22:47 by zcov