1 //===-- MergeHandler.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 "MergeHandler.h"
11
12 #include "CoreStats.h"
13 #include "ExecutionState.h"
14 #include "Executor.h"
15 #include "Searcher.h"
16
17 namespace klee {
18
19 /*** Test generation options ***/
20
21 llvm::cl::OptionCategory MergeCat("Path merging options",
22 "These options control path merging.");
23
24 llvm::cl::opt<bool> UseMerge(
25 "use-merge", llvm::cl::init(false),
26 llvm::cl::desc("Enable support for path merging via klee_open_merge() and "
27 "klee_close_merge() (default=false)"),
28 llvm::cl::cat(klee::MergeCat));
29
30 llvm::cl::opt<bool> DebugLogMerge(
31 "debug-log-merge", llvm::cl::init(false),
32 llvm::cl::desc("Debug information for path merging (default=false)"),
33 llvm::cl::cat(klee::MergeCat));
34
35 llvm::cl::opt<bool> UseIncompleteMerge(
36 "use-incomplete-merge", llvm::cl::init(false),
37 llvm::cl::desc("Heuristic-based path merging (default=false)"),
38 llvm::cl::cat(klee::MergeCat));
39
40 llvm::cl::opt<bool> DebugLogIncompleteMerge(
41 "debug-log-incomplete-merge", llvm::cl::init(false),
42 llvm::cl::desc("Debug information for incomplete path merging (default=false)"),
43 llvm::cl::cat(klee::MergeCat));
44
getMean()45 double MergeHandler::getMean() {
46 if (closedStateCount == 0)
47 return 0;
48
49 return closedMean;
50 }
51
getInstructionDistance(ExecutionState * es)52 unsigned MergeHandler::getInstructionDistance(ExecutionState *es){
53 return es->steppedInstructions - openInstruction;
54 }
55
getPrioritizeState()56 ExecutionState *MergeHandler::getPrioritizeState(){
57 for (ExecutionState *cur_state : openStates) {
58 bool stateIsClosed =
59 (executor->mergingSearcher->inCloseMerge.find(cur_state) !=
60 executor->mergingSearcher->inCloseMerge.end());
61
62 if (!stateIsClosed && (getInstructionDistance(cur_state) < 2 * getMean())) {
63 return cur_state;
64 }
65 }
66 return 0;
67 }
68
69
addOpenState(ExecutionState * es)70 void MergeHandler::addOpenState(ExecutionState *es){
71 openStates.push_back(es);
72 }
73
removeOpenState(ExecutionState * es)74 void MergeHandler::removeOpenState(ExecutionState *es){
75 auto it = std::find(openStates.begin(), openStates.end(), es);
76 assert(it != openStates.end());
77 std::swap(*it, openStates.back());
78 openStates.pop_back();
79 }
80
addClosedState(ExecutionState * es,llvm::Instruction * mp)81 void MergeHandler::addClosedState(ExecutionState *es,
82 llvm::Instruction *mp) {
83 // Update stats
84 ++closedStateCount;
85
86 // Incremental update of mean (travelling mean)
87 // https://math.stackexchange.com/a/1836447
88 closedMean += (static_cast<double>(getInstructionDistance(es)) - closedMean) /
89 closedStateCount;
90
91 // Remove from openStates
92 removeOpenState(es);
93
94 auto closePoint = reachedCloseMerge.find(mp);
95
96 // If no other state has yet encountered this klee_close_merge instruction,
97 // add a new element to the map
98 if (closePoint == reachedCloseMerge.end()) {
99 reachedCloseMerge[mp].push_back(es);
100 executor->mergingSearcher->pauseState(*es);
101 } else {
102 // Otherwise try to merge with any state in the map element for this
103 // instruction
104 auto &cpv = closePoint->second;
105 bool mergedSuccessful = false;
106
107 for (auto& mState: cpv) {
108 if (mState->merge(*es)) {
109 executor->terminateState(*es);
110 executor->mergingSearcher->inCloseMerge.erase(es);
111 mergedSuccessful = true;
112 break;
113 }
114 }
115 if (!mergedSuccessful) {
116 cpv.push_back(es);
117 executor->mergingSearcher->pauseState(*es);
118 }
119 }
120 }
121
releaseStates()122 void MergeHandler::releaseStates() {
123 for (auto& curMergeGroup: reachedCloseMerge) {
124 for (auto curState: curMergeGroup.second) {
125 executor->mergingSearcher->continueState(*curState);
126 executor->mergingSearcher->inCloseMerge.erase(curState);
127 }
128 }
129 reachedCloseMerge.clear();
130 }
131
hasMergedStates()132 bool MergeHandler::hasMergedStates() {
133 return (!reachedCloseMerge.empty());
134 }
135
MergeHandler(Executor * _executor,ExecutionState * es)136 MergeHandler::MergeHandler(Executor *_executor, ExecutionState *es)
137 : executor(_executor), openInstruction(es->steppedInstructions),
138 closedMean(0), closedStateCount(0) {
139 executor->mergingSearcher->mergeGroups.push_back(this);
140 addOpenState(es);
141 }
142
~MergeHandler()143 MergeHandler::~MergeHandler() {
144 auto it = std::find(executor->mergingSearcher->mergeGroups.begin(),
145 executor->mergingSearcher->mergeGroups.end(), this);
146 assert(it != executor->mergingSearcher->mergeGroups.end() &&
147 "All MergeHandlers should be registered in mergeGroups");
148 std::swap(*it, executor->mergingSearcher->mergeGroups.back());
149 executor->mergingSearcher->mergeGroups.pop_back();
150
151 releaseStates();
152 }
153 }
154