klee
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
StatsTracker.cpp
Go to the documentation of this file.
1 //===-- StatsTracker.cpp --------------------------------------------------===//
2 //
3 // The KLEE Symbolic Virtual Machine
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "Common.h"
11 
12 #include "StatsTracker.h"
13 
14 #include "klee/ExecutionState.h"
15 #include "klee/Statistics.h"
16 #include "klee/Config/Version.h"
22 
23 #include "CallPathManager.h"
24 #include "CoreStats.h"
25 #include "Executor.h"
26 #include "MemoryManager.h"
27 #include "UserSearcher.h"
28 #include "../Solver/SolverStats.h"
29 
30 #if LLVM_VERSION_CODE > LLVM_VERSION(3, 2)
31 #include "llvm/IR/BasicBlock.h"
32 #include "llvm/IR/Function.h"
33 #include "llvm/IR/Instructions.h"
34 #include "llvm/IR/IntrinsicInst.h"
35 #include "llvm/IR/InlineAsm.h"
36 #include "llvm/IR/Module.h"
37 #include "llvm/IR/Type.h"
38 #else
39 #include "llvm/BasicBlock.h"
40 #include "llvm/Function.h"
41 #include "llvm/Instructions.h"
42 #include "llvm/IntrinsicInst.h"
43 #include "llvm/InlineAsm.h"
44 #include "llvm/Module.h"
45 #include "llvm/Type.h"
46 #endif
47 #include "llvm/Support/CommandLine.h"
48 #include "llvm/Support/CFG.h"
49 #include "llvm/Support/Process.h"
50 #include "llvm/Support/Path.h"
51 #include "llvm/Support/FileSystem.h"
52 
53 #include <fstream>
54 #include <unistd.h>
55 
56 using namespace klee;
57 using namespace llvm;
58 
60 
61 namespace {
62  cl::opt<bool>
63  TrackInstructionTime("track-instruction-time",
64  cl::desc("Enable tracking of time for individual instructions"),
65  cl::init(false));
66 
67  cl::opt<bool>
68  OutputStats("output-stats",
69  cl::desc("Write running stats trace file"),
70  cl::init(true));
71 
72  cl::opt<bool>
73  OutputIStats("output-istats",
74  cl::desc("Write instruction level statistics (in callgrind format)"),
75  cl::init(true));
76 
77  cl::opt<double>
78  StatsWriteInterval("stats-write-interval",
79  cl::desc("Approximate number of seconds between stats writes (default: 1.0)"),
80  cl::init(1.));
81 
82  cl::opt<double>
83  IStatsWriteInterval("istats-write-interval",
84  cl::desc("Approximate number of seconds between istats writes (default: 10.0)"),
85  cl::init(10.));
86 
87  /*
88  cl::opt<double>
89  BranchCovCountsWriteInterval("branch-cov-counts-write-interval",
90  cl::desc("Approximate number of seconds between run.branches writes (default: 5.0)"),
91  cl::init(5.));
92  */
93 
94  // XXX I really would like to have dynamic rate control for something like this.
95  cl::opt<double>
96  UncoveredUpdateInterval("uncovered-update-interval",
97  cl::init(30.));
98 
99  cl::opt<bool>
100  UseCallPaths("use-call-paths",
101  cl::desc("Enable calltree tracking for instruction level statistics"),
102  cl::init(true));
103 
104 }
105 
107 
109  return OutputStats || OutputIStats;
110 }
111 
112 namespace klee {
115 
116  public:
117  WriteIStatsTimer(StatsTracker *_statsTracker) : statsTracker(_statsTracker) {}
119 
120  void run() { statsTracker->writeIStats(); }
121  };
122 
125 
126  public:
127  WriteStatsTimer(StatsTracker *_statsTracker) : statsTracker(_statsTracker) {}
129 
130  void run() { statsTracker->writeStatsLine(); }
131  };
132 
135 
136  public:
137  UpdateReachableTimer(StatsTracker *_statsTracker) : statsTracker(_statsTracker) {}
138 
139  void run() { statsTracker->computeReachableUncovered(); }
140  };
141 
142 }
143 
144 //
145 
150 static bool instructionIsCoverable(Instruction *i) {
151  if (i->getOpcode() == Instruction::Unreachable) {
152  BasicBlock *bb = i->getParent();
153  BasicBlock::iterator it(i);
154  if (it==bb->begin()) {
155  return true;
156  } else {
157  Instruction *prev = --it;
158  if (isa<CallInst>(prev) || isa<InvokeInst>(prev)) {
159  Function *target = getDirectCallTarget(prev);
160  if (target && target->doesNotReturn())
161  return false;
162  }
163  }
164  }
165 
166  return true;
167 }
168 
169 StatsTracker::StatsTracker(Executor &_executor, std::string _objectFilename,
170  bool _updateMinDistToUncovered)
171  : executor(_executor),
172  objectFilename(_objectFilename),
173  statsFile(0),
174  istatsFile(0),
175  startWallTime(util::getWallTime()),
176  numBranches(0),
177  fullBranches(0),
178  partialBranches(0),
179  updateMinDistToUncovered(_updateMinDistToUncovered) {
180  KModule *km = executor.kmodule;
181 
182  if (!sys::path::is_absolute(objectFilename)) {
183  SmallString<128> current(objectFilename);
184  if(sys::fs::make_absolute(current)) {
185  bool exists = false;
186  error_code ec = sys::fs::exists(current.str(), exists);
187  if (ec == errc::success && exists) {
188  objectFilename = current.c_str();
189  }
190  }
191  }
192 
193  if (OutputIStats)
195 
196  for (std::vector<KFunction*>::iterator it = km->functions.begin(),
197  ie = km->functions.end(); it != ie; ++it) {
198  KFunction *kf = *it;
199  kf->trackCoverage = 1;
200 
201  for (unsigned i=0; i<kf->numInstructions; ++i) {
202  KInstruction *ki = kf->instructions[i];
203 
204  if (OutputIStats) {
205  unsigned id = ki->info->id;
207  if (kf->trackCoverage && instructionIsCoverable(ki->inst))
209  }
210 
211  if (kf->trackCoverage) {
212  if (BranchInst *bi = dyn_cast<BranchInst>(ki->inst))
213  if (!bi->isUnconditional())
214  numBranches++;
215  }
216  }
217  }
218 
219  if (OutputStats) {
221  assert(statsFile && "unable to open statistics trace file");
223  writeStatsLine();
224 
225  executor.addTimer(new WriteStatsTimer(this), StatsWriteInterval);
226 
229  executor.addTimer(new UpdateReachableTimer(this), UncoveredUpdateInterval);
230  }
231  }
232 
233  if (OutputIStats) {
235  assert(istatsFile && "unable to open istats file");
236 
237  executor.addTimer(new WriteIStatsTimer(this), IStatsWriteInterval);
238  }
239 }
240 
242  if (statsFile)
243  delete statsFile;
244  if (istatsFile)
245  delete istatsFile;
246 }
247 
249  if (statsFile)
250  writeStatsLine();
251  if (OutputIStats)
252  writeIStats();
253 }
254 
256  if (OutputIStats) {
257  if (TrackInstructionTime) {
258  static sys::TimeValue lastNowTime(0,0),lastUserTime(0,0);
259 
260  if (lastUserTime.seconds()==0 && lastUserTime.nanoseconds()==0) {
261  sys::TimeValue sys(0,0);
262  sys::Process::GetTimeUsage(lastNowTime,lastUserTime,sys);
263  } else {
264  sys::TimeValue now(0,0),user(0,0),sys(0,0);
265  sys::Process::GetTimeUsage(now,user,sys);
266  sys::TimeValue delta = user - lastUserTime;
267  sys::TimeValue deltaNow = now - lastNowTime;
268  stats::instructionTime += delta.usec();
269  stats::instructionRealTime += deltaNow.usec();
270  lastUserTime = user;
271  lastNowTime = now;
272  }
273  }
274 
275  Instruction *inst = es.pc->inst;
276  const InstructionInfo &ii = *es.pc->info;
277  StackFrame &sf = es.stack.back();
279  if (UseCallPaths)
281 
282  if (es.instsSinceCovNew)
283  ++es.instsSinceCovNew;
284 
285  if (sf.kf->trackCoverage && instructionIsCoverable(inst)) {
287  // Checking for actual stoppoints avoids inconsistencies due
288  // to line number propogation.
289  //
290  // FIXME: This trick no longer works, we should fix this in the line
291  // number propogation.
292  es.coveredLines[&ii.file].insert(ii.line);
293  es.coveredNew = true;
294  es.instsSinceCovNew = 1;
296  stats::uncoveredInstructions += (uint64_t)-1;
297  }
298  }
299  }
300 }
301 
303 
304 /* Should be called _after_ the es->pushFrame() */
306  if (OutputIStats) {
307  StackFrame &sf = es.stack.back();
308 
309  if (UseCallPaths) {
310  CallPathNode *parent = parentFrame ? parentFrame->callPathNode : 0;
312  sf.caller ? sf.caller->inst : 0,
313  sf.kf->function);
314  sf.callPathNode = cp;
315  cp->count++;
316  }
317 
319  uint64_t minDistAtRA = 0;
320  if (parentFrame)
321  minDistAtRA = parentFrame->minDistToUncoveredOnReturn;
322 
324  computeMinDistToUncovered(sf.caller, minDistAtRA) : 0;
325  }
326  }
327 }
328 
329 /* Should be called _after_ the es->popFrame() */
331  // XXX remove me?
332 }
333 
334 
336  ExecutionState *visitedFalse) {
337  if (OutputIStats) {
338  unsigned id = theStatisticManager->getIndex();
340  uint64_t hasFalse = theStatisticManager->getIndexedValue(stats::falseBranches, id);
341  if (visitedTrue && !hasTrue) {
342  visitedTrue->coveredNew = true;
343  visitedTrue->instsSinceCovNew = 1;
345  if (hasFalse) { ++fullBranches; --partialBranches; }
346  else ++partialBranches;
347  hasTrue = 1;
348  }
349  if (visitedFalse && !hasFalse) {
350  visitedFalse->coveredNew = true;
351  visitedFalse->instsSinceCovNew = 1;
353  if (hasTrue) { ++fullBranches; --partialBranches; }
354  else ++partialBranches;
355  }
356  }
357 }
358 
360  *statsFile << "('Instructions',"
361  << "'FullBranches',"
362  << "'PartialBranches',"
363  << "'NumBranches',"
364  << "'UserTime',"
365  << "'NumStates',"
366  << "'MallocUsage',"
367  << "'NumQueries',"
368  << "'NumQueryConstructs',"
369  << "'NumObjects',"
370  << "'WallTime',"
371  << "'CoveredInstructions',"
372  << "'UncoveredInstructions',"
373  << "'QueryTime',"
374  << "'SolverTime',"
375  << "'CexCacheTime',"
376  << "'ForkTime',"
377  << "'ResolveTime',"
378 #ifdef DEBUG
379  << "'ArrayHashTime',"
380 #endif
381  << ")\n";
382  statsFile->flush();
383 }
384 
386  return util::getWallTime() - startWallTime;
387 }
388 
390  *statsFile << "(" << stats::instructions
391  << "," << fullBranches
392  << "," << partialBranches
393  << "," << numBranches
394  << "," << util::getUserTime()
395  << "," << executor.states.size()
396 #if LLVM_VERSION_CODE > LLVM_VERSION(3, 2)
397  << "," << sys::Process::GetMallocUsage()
398 #else
399  << "," << sys::Process::GetTotalMemoryUsage()
400 #endif
401  << "," << stats::queries
402  << "," << stats::queryConstructs
403  << "," << 0 // was numObjects
404  << "," << elapsed()
407  << "," << stats::queryTime / 1000000.
408  << "," << stats::solverTime / 1000000.
409  << "," << stats::cexCacheTime / 1000000.
410  << "," << stats::forkTime / 1000000.
411  << "," << stats::resolveTime / 1000000.
412 #ifdef DEBUG
413  << "," << stats::arrayHashTime / 1000000.
414 #endif
415  << ")\n";
416  statsFile->flush();
417 }
418 
419 void StatsTracker::updateStateStatistics(uint64_t addend) {
420  for (std::set<ExecutionState*>::iterator it = executor.states.begin(),
421  ie = executor.states.end(); it != ie; ++it) {
422  ExecutionState &state = **it;
423  const InstructionInfo &ii = *state.pc->info;
425  if (UseCallPaths)
426  state.stack.back().callPathNode->statistics.incrementValue(stats::states, addend);
427  }
428 }
429 
431  Module *m = executor.kmodule->module;
432  uint64_t istatsMask = 0;
433  llvm::raw_fd_ostream &of = *istatsFile;
434 
435  // We assume that we didn't move the file pointer
436  unsigned istatsSize = of.tell();
437 
438  of.seek(0);
439 
440  of << "version: 1\n";
441  of << "creator: klee\n";
442  of << "pid: " << getpid() << "\n";
443  of << "cmd: " << m->getModuleIdentifier() << "\n\n";
444  of << "\n";
445 
447  unsigned nStats = sm.getNumStatistics();
448 
449  // Max is 13, sadly
450  istatsMask |= 1<<sm.getStatisticID("Queries");
451  istatsMask |= 1<<sm.getStatisticID("QueriesValid");
452  istatsMask |= 1<<sm.getStatisticID("QueriesInvalid");
453  istatsMask |= 1<<sm.getStatisticID("QueryTime");
454  istatsMask |= 1<<sm.getStatisticID("ResolveTime");
455  istatsMask |= 1<<sm.getStatisticID("Instructions");
456  istatsMask |= 1<<sm.getStatisticID("InstructionTimes");
457  istatsMask |= 1<<sm.getStatisticID("InstructionRealTimes");
458  istatsMask |= 1<<sm.getStatisticID("Forks");
459  istatsMask |= 1<<sm.getStatisticID("CoveredInstructions");
460  istatsMask |= 1<<sm.getStatisticID("UncoveredInstructions");
461  istatsMask |= 1<<sm.getStatisticID("States");
462  istatsMask |= 1<<sm.getStatisticID("MinDistToUncovered");
463 
464  of << "positions: instr line\n";
465 
466  for (unsigned i=0; i<nStats; i++) {
467  if (istatsMask & (1<<i)) {
468  Statistic &s = sm.getStatistic(i);
469  of << "event: " << s.getShortName() << " : "
470  << s.getName() << "\n";
471  }
472  }
473 
474  of << "events: ";
475  for (unsigned i=0; i<nStats; i++) {
476  if (istatsMask & (1<<i))
477  of << sm.getStatistic(i).getShortName() << " ";
478  }
479  of << "\n";
480 
481  // set state counts, decremented after we process so that we don't
482  // have to zero all records each time.
483  if (istatsMask & (1<<stats::states.getID()))
485 
486  std::string sourceFile = "";
487 
488  CallSiteSummaryTable callSiteStats;
489  if (UseCallPaths)
490  callPathManager.getSummaryStatistics(callSiteStats);
491 
492  of << "ob=" << objectFilename << "\n";
493 
494  for (Module::iterator fnIt = m->begin(), fn_ie = m->end();
495  fnIt != fn_ie; ++fnIt) {
496  if (!fnIt->isDeclaration()) {
497  of << "fn=" << fnIt->getName().str() << "\n";
498  for (Function::iterator bbIt = fnIt->begin(), bb_ie = fnIt->end();
499  bbIt != bb_ie; ++bbIt) {
500  for (BasicBlock::iterator it = bbIt->begin(), ie = bbIt->end();
501  it != ie; ++it) {
502  Instruction *instr = &*it;
503  const InstructionInfo &ii = executor.kmodule->infos->getInfo(instr);
504  unsigned index = ii.id;
505  if (ii.file!=sourceFile) {
506  of << "fl=" << ii.file << "\n";
507  sourceFile = ii.file;
508  }
509  of << ii.assemblyLine << " ";
510  of << ii.line << " ";
511  for (unsigned i=0; i<nStats; i++)
512  if (istatsMask&(1<<i))
513  of << sm.getIndexedValue(sm.getStatistic(i), index) << " ";
514  of << "\n";
515 
516  if (UseCallPaths &&
517  (isa<CallInst>(instr) || isa<InvokeInst>(instr))) {
518  CallSiteSummaryTable::iterator it = callSiteStats.find(instr);
519  if (it!=callSiteStats.end()) {
520  for (std::map<llvm::Function*, CallSiteInfo>::iterator
521  fit = it->second.begin(), fie = it->second.end();
522  fit != fie; ++fit) {
523  Function *f = fit->first;
524  CallSiteInfo &csi = fit->second;
525  const InstructionInfo &fii =
527 
528  if (fii.file!="" && fii.file!=sourceFile)
529  of << "cfl=" << fii.file << "\n";
530  of << "cfn=" << f->getName().str() << "\n";
531  of << "calls=" << csi.count << " ";
532  of << fii.assemblyLine << " ";
533  of << fii.line << "\n";
534 
535  of << ii.assemblyLine << " ";
536  of << ii.line << " ";
537  for (unsigned i=0; i<nStats; i++) {
538  if (istatsMask&(1<<i)) {
539  Statistic &s = sm.getStatistic(i);
540  uint64_t value;
541 
542  // Hack, ignore things that don't make sense on
543  // call paths.
544  if (&s == &stats::uncoveredInstructions) {
545  value = 0;
546  } else {
547  value = csi.statistics.getValue(s);
548  }
549 
550  of << value << " ";
551  }
552  }
553  of << "\n";
554  }
555  }
556  }
557  }
558  }
559  }
560  }
561 
562  if (istatsMask & (1<<stats::states.getID()))
563  updateStateStatistics((uint64_t)-1);
564 
565  // Clear then end of the file if necessary (no truncate op?).
566  unsigned pos = of.tell();
567  for (unsigned i=pos; i<istatsSize; ++i)
568  of << '\n';
569 
570  of.flush();
571 }
572 
574 
575 typedef std::map<Instruction*, std::vector<Function*> > calltargets_ty;
576 
578 static std::map<Function*, std::vector<Instruction*> > functionCallers;
579 static std::map<Function*, unsigned> functionShortestPath;
580 
581 static std::vector<Instruction*> getSuccs(Instruction *i) {
582  BasicBlock *bb = i->getParent();
583  std::vector<Instruction*> res;
584 
585  if (i==bb->getTerminator()) {
586  for (succ_iterator it = succ_begin(bb), ie = succ_end(bb); it != ie; ++it)
587  res.push_back(it->begin());
588  } else {
589  res.push_back(++BasicBlock::iterator(i));
590  }
591 
592  return res;
593 }
594 
596  uint64_t minDistAtRA) {
598  if (minDistAtRA==0) { // unreachable on return, best is local
600  ki->info->id);
601  } else {
602  uint64_t minDistLocal = sm.getIndexedValue(stats::minDistToUncovered,
603  ki->info->id);
604  uint64_t distToReturn = sm.getIndexedValue(stats::minDistToReturn,
605  ki->info->id);
606 
607  if (distToReturn==0) { // return unreachable, best is local
608  return minDistLocal;
609  } else if (!minDistLocal) { // no local reachable
610  return distToReturn + minDistAtRA;
611  } else {
612  return std::min(minDistLocal, distToReturn + minDistAtRA);
613  }
614  }
615 }
616 
618  KModule *km = executor.kmodule;
619  Module *m = km->module;
620  static bool init = true;
621  const InstructionInfoTable &infos = *km->infos;
623 
624  if (init) {
625  init = false;
626 
627  // Compute call targets. It would be nice to use alias information
628  // instead of assuming all indirect calls hit all escaping
629  // functions, eh?
630  for (Module::iterator fnIt = m->begin(), fn_ie = m->end();
631  fnIt != fn_ie; ++fnIt) {
632  for (Function::iterator bbIt = fnIt->begin(), bb_ie = fnIt->end();
633  bbIt != bb_ie; ++bbIt) {
634  for (BasicBlock::iterator it = bbIt->begin(), ie = bbIt->end();
635  it != ie; ++it) {
636  if (isa<CallInst>(it) || isa<InvokeInst>(it)) {
637  CallSite cs(it);
638  if (isa<InlineAsm>(cs.getCalledValue())) {
639  // We can never call through here so assume no targets
640  // (which should be correct anyhow).
641  callTargets.insert(std::make_pair(it,
642  std::vector<Function*>()));
643  } else if (Function *target = getDirectCallTarget(cs)) {
644  callTargets[it].push_back(target);
645  } else {
646  callTargets[it] =
647  std::vector<Function*>(km->escapingFunctions.begin(),
648  km->escapingFunctions.end());
649  }
650  }
651  }
652  }
653  }
654 
655  // Compute function callers as reflexion of callTargets.
656  for (calltargets_ty::iterator it = callTargets.begin(),
657  ie = callTargets.end(); it != ie; ++it)
658  for (std::vector<Function*>::iterator fit = it->second.begin(),
659  fie = it->second.end(); fit != fie; ++fit)
660  functionCallers[*fit].push_back(it->first);
661 
662  // Initialize minDistToReturn to shortest paths through
663  // functions. 0 is unreachable.
664  std::vector<Instruction *> instructions;
665  for (Module::iterator fnIt = m->begin(), fn_ie = m->end();
666  fnIt != fn_ie; ++fnIt) {
667  if (fnIt->isDeclaration()) {
668  if (fnIt->doesNotReturn()) {
669  functionShortestPath[fnIt] = 0;
670  } else {
671  functionShortestPath[fnIt] = 1; // whatever
672  }
673  } else {
674  functionShortestPath[fnIt] = 0;
675  }
676 
677  // Not sure if I should bother to preorder here. XXX I should.
678  for (Function::iterator bbIt = fnIt->begin(), bb_ie = fnIt->end();
679  bbIt != bb_ie; ++bbIt) {
680  for (BasicBlock::iterator it = bbIt->begin(), ie = bbIt->end();
681  it != ie; ++it) {
682  instructions.push_back(it);
683  unsigned id = infos.getInfo(it).id;
685  id,
686  isa<ReturnInst>(it)
688  || isa<UnwindInst>(it)
689 #endif
690  );
691  }
692  }
693  }
694 
695  std::reverse(instructions.begin(), instructions.end());
696 
697  // I'm so lazy it's not even worklisted.
698  bool changed;
699  do {
700  changed = false;
701  for (std::vector<Instruction*>::iterator it = instructions.begin(),
702  ie = instructions.end(); it != ie; ++it) {
703  Instruction *inst = *it;
704  unsigned bestThrough = 0;
705 
706  if (isa<CallInst>(inst) || isa<InvokeInst>(inst)) {
707  std::vector<Function*> &targets = callTargets[inst];
708  for (std::vector<Function*>::iterator fnIt = targets.begin(),
709  ie = targets.end(); fnIt != ie; ++fnIt) {
710  uint64_t dist = functionShortestPath[*fnIt];
711  if (dist) {
712  dist = 1+dist; // count instruction itself
713  if (bestThrough==0 || dist<bestThrough)
714  bestThrough = dist;
715  }
716  }
717  } else {
718  bestThrough = 1;
719  }
720 
721  if (bestThrough) {
722  unsigned id = infos.getInfo(*it).id;
723  uint64_t best, cur = best = sm.getIndexedValue(stats::minDistToReturn, id);
724  std::vector<Instruction*> succs = getSuccs(*it);
725  for (std::vector<Instruction*>::iterator it2 = succs.begin(),
726  ie = succs.end(); it2 != ie; ++it2) {
727  uint64_t dist = sm.getIndexedValue(stats::minDistToReturn,
728  infos.getInfo(*it2).id);
729  if (dist) {
730  uint64_t val = bestThrough + dist;
731  if (best==0 || val<best)
732  best = val;
733  }
734  }
735  // there's a corner case here when a function only includes a single
736  // instruction (a ret). in that case, we MUST update
737  // functionShortestPath, or it will remain 0 (erroneously indicating
738  // that no return instructions are reachable)
739  Function *f = inst->getParent()->getParent();
740  if (best != cur
741  || (inst == f->begin()->begin()
742  && functionShortestPath[f] != best)) {
744  changed = true;
745 
746  // Update shortest path if this is the entry point.
747  if (inst==f->begin()->begin())
748  functionShortestPath[f] = best;
749  }
750  }
751  }
752  } while (changed);
753  }
754 
755  // compute minDistToUncovered, 0 is unreachable
756  std::vector<Instruction *> instructions;
757  for (Module::iterator fnIt = m->begin(), fn_ie = m->end();
758  fnIt != fn_ie; ++fnIt) {
759  // Not sure if I should bother to preorder here.
760  for (Function::iterator bbIt = fnIt->begin(), bb_ie = fnIt->end();
761  bbIt != bb_ie; ++bbIt) {
762  for (BasicBlock::iterator it = bbIt->begin(), ie = bbIt->end();
763  it != ie; ++it) {
764  unsigned id = infos.getInfo(it).id;
765  instructions.push_back(&*it);
767  id,
769  }
770  }
771  }
772 
773  std::reverse(instructions.begin(), instructions.end());
774 
775  // I'm so lazy it's not even worklisted.
776  bool changed;
777  do {
778  changed = false;
779  for (std::vector<Instruction*>::iterator it = instructions.begin(),
780  ie = instructions.end(); it != ie; ++it) {
781  Instruction *inst = *it;
782  uint64_t best, cur = best = sm.getIndexedValue(stats::minDistToUncovered,
783  infos.getInfo(inst).id);
784  unsigned bestThrough = 0;
785 
786  if (isa<CallInst>(inst) || isa<InvokeInst>(inst)) {
787  std::vector<Function*> &targets = callTargets[inst];
788  for (std::vector<Function*>::iterator fnIt = targets.begin(),
789  ie = targets.end(); fnIt != ie; ++fnIt) {
790  uint64_t dist = functionShortestPath[*fnIt];
791  if (dist) {
792  dist = 1+dist; // count instruction itself
793  if (bestThrough==0 || dist<bestThrough)
794  bestThrough = dist;
795  }
796 
797  if (!(*fnIt)->isDeclaration()) {
798  uint64_t calleeDist = sm.getIndexedValue(stats::minDistToUncovered,
799  infos.getFunctionInfo(*fnIt).id);
800  if (calleeDist) {
801  calleeDist = 1+calleeDist; // count instruction itself
802  if (best==0 || calleeDist<best)
803  best = calleeDist;
804  }
805  }
806  }
807  } else {
808  bestThrough = 1;
809  }
810 
811  if (bestThrough) {
812  std::vector<Instruction*> succs = getSuccs(inst);
813  for (std::vector<Instruction*>::iterator it2 = succs.begin(),
814  ie = succs.end(); it2 != ie; ++it2) {
815  uint64_t dist = sm.getIndexedValue(stats::minDistToUncovered,
816  infos.getInfo(*it2).id);
817  if (dist) {
818  uint64_t val = bestThrough + dist;
819  if (best==0 || val<best)
820  best = val;
821  }
822  }
823  }
824 
825  if (best != cur) {
827  infos.getInfo(inst).id,
828  best);
829  changed = true;
830  }
831  }
832  } while (changed);
833 
834  for (std::set<ExecutionState*>::iterator it = executor.states.begin(),
835  ie = executor.states.end(); it != ie; ++it) {
836  ExecutionState *es = *it;
837  uint64_t currentFrameMinDist = 0;
838  for (ExecutionState::stack_ty::iterator sfIt = es->stack.begin(),
839  sf_ie = es->stack.end(); sfIt != sf_ie; ++sfIt) {
840  ExecutionState::stack_ty::iterator next = sfIt + 1;
841  KInstIterator kii;
842 
843  if (next==es->stack.end()) {
844  kii = es->pc;
845  } else {
846  kii = next->caller;
847  ++kii;
848  }
849 
850  sfIt->minDistToUncoveredOnReturn = currentFrameMinDist;
851 
852  currentFrameMinDist = computeMinDistToUncovered(kii, currentFrameMinDist);
853  }
854  }
855 }
WriteIStatsTimer(StatsTracker *_statsTracker)
void framePopped(ExecutionState &es)
static bool instructionIsCoverable(Instruction *i)
InstructionInfoTable * infos
Definition: KModule.h:105
unsigned getNumStatistics()
Definition: Statistics.h:60
const InstructionInfo & getFunctionInfo(const llvm::Function *) const
StatsTracker * statsTracker
Statistic minDistToReturn
UpdateReachableTimer(StatsTracker *_statsTracker)
Statistic cexCacheTime
std::set< ExecutionState * > states
Definition: Executor.h:110
uint64_t getValue(const Statistic &s) const
Definition: Statistics.h:120
unsigned partialBranches
Definition: StatsTracker.h:43
StatisticManager * theStatisticManager
Definition: Statistics.cpp:57
const InstructionInfo * info
Definition: KInstruction.h:31
void setIndex(unsigned i)
Definition: Statistics.h:58
Executor & executor
Definition: StatsTracker.h:36
virtual llvm::raw_fd_ostream * openOutputFile(const std::string &filename)=0
Statistic forkTime
void setContext(StatisticRecord *sr)
Definition: Statistics.h:91
static calltargets_ty callTargets
StatisticRecord statistics
std::set< llvm::Function * > escapingFunctions
Definition: KModule.h:103
Statistic falseBranches
std::map< Instruction *, std::vector< Function * > > calltargets_ty
void addTimer(Timer *timer, double rate)
void run()
The event callback.
unsigned numBranches
Definition: StatsTracker.h:42
std::map< const std::string *, std::set< unsigned > > coveredLines
llvm::Function * getDirectCallTarget(llvm::CallSite)
double getWallTime()
Definition: Time.cpp:24
Statistic queries
const std::string & getName() const
getName - Get the statistic name.
Definition: Statistic.h:46
void markBranchVisited(ExecutionState *visitedTrue, ExecutionState *visitedFalse)
static std::map< Function *, unsigned > functionShortestPath
CallPathNode * callPathNode
StatsTracker * statsTracker
void framePushed(ExecutionState &es, StackFrame *parentFrame)
Statistic & getStatistic(unsigned i)
Definition: Statistics.h:61
Statistic trueBranches
uint64_t getIndexedValue(const Statistic &s, unsigned index) const
Definition: Statistics.h:142
void run()
The event callback.
StatisticRecord statistics
#define LLVM_VERSION_CODE
Definition: Version.h:16
#define LLVM_VERSION(major, minor)
Definition: Version.h:15
StatsTracker(Executor &_executor, std::string _objectFilename, bool _updateMinDistToUncovered)
static bool useStatistics()
void useIndexedStats(unsigned totalIndices)
Definition: Statistics.cpp:29
KFunction * kf
uint64_t computeMinDistToUncovered(const KInstruction *ki, uint64_t minDistAtRA)
CallPathManager callPathManager
Definition: StatsTracker.h:45
InterpreterHandler * interpreterHandler
Definition: Executor.h:104
Statistic minDistToUncovered
llvm::Function * function
Definition: KModule.h:44
llvm::Instruction * inst
Definition: KInstruction.h:30
void stepInstruction(ExecutionState &es)
bool updateMinDistToUncovered
Definition: StatsTracker.h:47
const InstructionInfo & getInfo(const llvm::Instruction *) const
std::string objectFilename
Definition: StatsTracker.h:37
KInstruction ** instructions
Definition: KModule.h:49
static std::vector< Instruction * > getSuccs(Instruction *i)
Statistic solverTime
Statistic resolveTime
Statistic instructionTime
void setIndexedValue(const Statistic &s, unsigned index, uint64_t value)
Definition: Statistics.h:147
KModule * kmodule
Definition: Executor.h:101
void updateStateStatistics(uint64_t addend)
Statistic instructionRealTime
const std::string & getShortName() const
Definition: Statistic.h:50
std::vector< KFunction * > functions
Definition: KModule.h:98
friend class WriteStatsTimer
Definition: StatsTracker.h:33
WriteStatsTimer(StatsTracker *_statsTracker)
unsigned fullBranches
Definition: StatsTracker.h:43
unsigned numInstructions
Definition: KModule.h:48
const std::string & file
KInstIterator caller
void computeReachableUncovered()
llvm::raw_fd_ostream * istatsFile
Definition: StatsTracker.h:39
CallPathNode * getCallPath(CallPathNode *parent, llvm::Instruction *callSite, llvm::Function *f)
double getUserTime()
Definition: Time.cpp:18
void incrementIndexedValue(const Statistic &s, unsigned index, uint64_t addend) const
Definition: Statistics.h:136
Statistic uncoveredInstructions
std::map< llvm::Instruction *, std::map< llvm::Function *, CallSiteInfo > > CallSiteSummaryTable
llvm::raw_fd_ostream * statsFile
Definition: StatsTracker.h:39
friend class WriteIStatsTimer
Definition: StatsTracker.h:34
void run()
The event callback.
bool trackCoverage
Definition: KModule.h:55
double elapsed()
Return time in seconds since execution start.
llvm::Module * module
Definition: KModule.h:87
Statistic queryTime
void getSummaryStatistics(CallSiteSummaryTable &result)
static std::map< Function *, std::vector< Instruction * > > functionCallers
Statistic instructions
int getStatisticID(const std::string &name) const
Definition: Statistics.cpp:43
Statistic coveredInstructions
unsigned minDistToUncoveredOnReturn
Statistic states
Statistic queryConstructs