 |
|
 |
|
| Files: |
1 |
|
Branches Taken: |
48.8% |
40 / 82 |
| Generated: |
2009-05-17 22:47 |
|
Branches Executed: |
78.0% |
64 / 82 |
| |
|
Line Coverage: |
63.6% |
56 / 88 |
| |
 |
|
 |
1 : /* -*- mode: c++; c-basic-offset: 2; -*- */
2 :
3 : #include "Common.h"
4 :
5 : #include "UserSearcher.h"
6 :
7 : #include "Searcher.h"
8 :
9 : #include "llvm/Support/CommandLine.h"
10 :
11 : using namespace llvm;
12 : using namespace klee;
13 :
14 : namespace {
15 : cl::opt<bool>
16 103: UseRandomSearch("use-random-search");
17 :
18 : cl::opt<bool>
19 103: UseInterleavedRS("use-interleaved-RS");
20 :
21 : cl::opt<bool>
22 103: UseInterleavedNURS("use-interleaved-NURS");
23 :
24 : cl::opt<bool>
25 103: UseInterleavedMD2UNURS("use-interleaved-MD2U-NURS");
26 :
27 : cl::opt<bool>
28 103: UseInterleavedInstCountNURS("use-interleaved-icnt-NURS");
29 :
30 : cl::opt<bool>
31 103: UseInterleavedCPInstCountNURS("use-interleaved-cpicnt-NURS");
32 :
33 : cl::opt<bool>
34 103: UseInterleavedQueryCostNURS("use-interleaved-query-cost-NURS");
35 :
36 : cl::opt<bool>
37 103: UseInterleavedCovNewNURS("use-interleaved-covnew-NURS");
38 :
39 : cl::opt<bool>
40 103: UseNonUniformRandomSearch("use-non-uniform-random-search");
41 :
42 : cl::opt<bool>
43 103: UseRandomPathSearch("use-random-path");
44 :
45 : cl::opt<bool>
46 103: UsePGSearch("use-pg-search");
47 :
48 : // fun - chain a PGSupervisedSearcher together with something else :)
49 : // (don't need --use-pg-search to also be true for this to work)
50 : cl::opt<bool>
51 103: UseSupervisedPGSearch("use-supervised-pg-search");
52 :
53 : // chains a PGSearcher with the Klee default 'good' searcher, which is:
54 : // --use-random-path --use-interleaved-covnew-NURS
55 : // --use-batching-search --batch-instructions 10000
56 : cl::opt<bool>
57 103: UseSupervisedPGPlusDefaultSearch("use-supervised-pg-search-plus-default");
58 :
59 : // when using with PGSupervisedSearcher, put PGSearcher LAST
60 : // so that other searchers get to run their course first ...
61 : cl::opt<bool>
62 103: PutPGSearcherLast("put-pg-searcher-last");
63 :
64 : cl::opt<WeightedRandomSearcher::WeightType>
65 103: WeightType("weight-type", cl::desc("Set the weight type for --use-non-uniform-random-search"),
66 : cl::values(clEnumValN(WeightedRandomSearcher::Depth, "none", "use (2^depth)"),
67 : clEnumValN(WeightedRandomSearcher::InstCount, "icnt", "use current pc exec count"),
68 : clEnumValN(WeightedRandomSearcher::CPInstCount, "cpicnt", "use current pc exec count"),
69 : clEnumValN(WeightedRandomSearcher::QueryCost, "query-cost", "use query cost"),
70 : clEnumValN(WeightedRandomSearcher::MinDistToUncovered, "md2u", "use min dist to uncovered"),
71 : clEnumValN(WeightedRandomSearcher::CoveringNew, "covnew", "use min dist to uncovered + coveringNew flag"),
72 103: clEnumValEnd));
73 :
74 : cl::opt<bool>
75 103: UseMerge("use-merge",
76 : cl::desc("Enable support for klee_merge() (experimental)"));
77 :
78 : cl::opt<bool>
79 103: UseBumpMerge("use-bump-merge",
80 : cl::desc("Enable support for klee_merge() (extra experimental)"));
81 :
82 : cl::opt<bool>
83 103: UseOwningSearch("use-owning-search",
84 : cl::desc("(experimental)"));
85 :
86 : cl::opt<bool>
87 103: UseIterativeDeepeningTimeSearch("use-iterative-deepening-time-search",
88 : cl::desc("(experimental)"));
89 :
90 : cl::opt<bool>
91 103: UseBatchingSearch("use-batching-search",
92 : cl::desc("Use batching searcher (keep running selected state for N instructions/time, see --batch-instructions and --batch-time"));
93 :
94 : cl::opt<unsigned>
95 103: BatchInstructions("batch-instructions",
96 : cl::desc("Number of instructions to batch when using --use-batching-search"),
97 103: cl::init(10000));
98 :
99 : cl::opt<double>
100 103: BatchTime("batch-time",
101 : cl::desc("Amount of time to batch when using --use-batching-search"),
102 103: cl::init(5.0));
103 : }
104 :
105 103: bool klee::userSearcherRequiresMD2U() {
106 : return (WeightType==WeightedRandomSearcher::MinDistToUncovered ||
107 : WeightType==WeightedRandomSearcher::CoveringNew ||
108 : UseInterleavedMD2UNURS ||
109 : UseInterleavedCovNewNURS ||
110 : UseInterleavedInstCountNURS ||
111 : UseInterleavedCPInstCountNURS ||
103: branch 0 taken
0: branch 1 not taken
103: branch 2 taken
0: branch 3 not taken
103: branch 4 taken
0: branch 5 not taken
103: branch 6 taken
0: branch 7 not taken
103: branch 8 taken
0: branch 9 not taken
103: branch 10 taken
0: branch 11 not taken
0: branch 12 not taken
103: branch 13 taken
112 721: UseInterleavedQueryCostNURS);
113 : }
114 :
115 848739: bool klee::userSearcherRequiresBranchSequences() {
848739: branch 0 taken
0: branch 1 not taken
0: branch 2 not taken
848739: branch 3 taken
116 1697478: return UsePGSearch || UseSupervisedPGSearch;
117 : }
118 :
119 103: Searcher *klee::constructUserSearcher(Executor &executor) {
120 103: Searcher *searcher = 0;
121 :
122 : // UseSupervisedPGPlusDefaultSearch is a shorthand convenience
123 : // for chaining together several searchers:
0: branch 0 not taken
103: branch 1 taken
124 103: if (UseSupervisedPGPlusDefaultSearch) {
125 0: UseSupervisedPGSearch = true;
126 0: UseInterleavedCovNewNURS = true;
127 0: UseRandomPathSearch = true;
128 0: UseBatchingSearch = true;
129 0: BatchInstructions = 10000;
130 : }
131 :
0: branch 0 not taken
103: branch 1 taken
132 103: if (UseRandomPathSearch) {
133 0: searcher = new RandomPathSearcher(executor);
10: branch 0 taken
93: branch 1 taken
134 103: } else if (UseNonUniformRandomSearch) {
135 10: searcher = new WeightedRandomSearcher(executor, WeightType);
7: branch 0 taken
86: branch 1 taken
136 93: } else if (UseRandomSearch) {
137 14: searcher = new RandomSearcher();
138 : // if UseSupervisedPGSearch, we want to explicitly chain PGSearcher()
139 : // to whatever other searchers the user has specified
0: branch 0 not taken
86: branch 1 taken
86: branch 2 taken
86: branch 3 taken
0: branch 4 not taken
86: branch 5 taken
140 86: } else if (UsePGSearch && !UseSupervisedPGSearch) {
141 0: searcher = new PGSearcher();
142 : } else {
143 172: searcher = new DFSSearcher();
144 : }
145 :
12: branch 0 taken
91: branch 1 taken
146 103: if (UseOwningSearch) {
147 12: searcher = new OwningSearcher(executor, searcher);
148 : }
149 :
103: branch 0 taken
0: branch 1 not taken
103: branch 2 taken
0: branch 3 not taken
103: branch 4 taken
0: branch 5 not taken
103: branch 6 taken
0: branch 7 not taken
103: branch 8 taken
0: branch 9 not taken
103: branch 10 taken
0: branch 11 not taken
0: branch 12 not taken
103: branch 13 taken
0: branch 14 not taken
103: branch 15 taken
150 721: if (UseInterleavedNURS || UseInterleavedMD2UNURS || UseInterleavedRS ||
151 : UseInterleavedCovNewNURS || UseInterleavedInstCountNURS ||
152 : UseInterleavedCPInstCountNURS || UseInterleavedQueryCostNURS) {
153 : std::vector<Searcher *> s;
154 0: s.push_back(searcher);
155 :
0: branch 0 not taken
0: branch 1 not taken
156 0: if (UseInterleavedNURS)
157 : s.push_back(new WeightedRandomSearcher(executor,
158 0: WeightedRandomSearcher::Depth));
0: branch 0 not taken
0: branch 1 not taken
159 0: if (UseInterleavedMD2UNURS)
160 : s.push_back(new WeightedRandomSearcher(executor,
161 0: WeightedRandomSearcher::MinDistToUncovered));
162 :
0: branch 0 not taken
0: branch 1 not taken
163 0: if (UseInterleavedCovNewNURS)
164 : s.push_back(new WeightedRandomSearcher(executor,
165 0: WeightedRandomSearcher::CoveringNew));
166 :
0: branch 0 not taken
0: branch 1 not taken
167 0: if (UseInterleavedInstCountNURS)
168 : s.push_back(new WeightedRandomSearcher(executor,
169 0: WeightedRandomSearcher::InstCount));
170 :
0: branch 0 not taken
0: branch 1 not taken
171 0: if (UseInterleavedCPInstCountNURS)
172 : s.push_back(new WeightedRandomSearcher(executor,
173 0: WeightedRandomSearcher::CPInstCount));
174 :
0: branch 0 not taken
0: branch 1 not taken
175 0: if (UseInterleavedQueryCostNURS)
176 : s.push_back(new WeightedRandomSearcher(executor,
177 0: WeightedRandomSearcher::QueryCost));
178 :
0: branch 0 not taken
0: branch 1 not taken
179 0: if (UseInterleavedRS)
180 0: s.push_back(new RandomSearcher());
181 :
182 0: searcher = new InterleavedSearcher(s);
183 : }
184 :
16: branch 0 taken
87: branch 1 taken
185 103: if (UseBatchingSearch) {
186 32: searcher = new BatchingSearcher(searcher, BatchTime, BatchInstructions);
187 : }
188 :
5: branch 0 taken
98: branch 1 taken
189 103: if (UseMerge) {
0: branch 0 not taken
5: branch 1 taken
190 5: assert(!UseBumpMerge);
191 5: searcher = new MergingSearcher(executor, searcher);
0: branch 0 not taken
98: branch 1 taken
192 98: } else if (UseBumpMerge) {
193 0: searcher = new BumpMergingSearcher(executor, searcher);
194 : }
195 :
4: branch 0 taken
99: branch 1 taken
196 103: if (UseIterativeDeepeningTimeSearch) {
197 4: searcher = new IterativeDeepeningTimeSearcher(searcher);
198 : }
199 :
200 : // pg - I dunno how PGSupervisedSearcher will play with
201 : // UseMerge, UseBumpMerge, or UseIterativeDeepeningTimeSearch,
202 : // but I don't care for now ...
0: branch 0 not taken
103: branch 1 taken
203 103: if (UseSupervisedPGSearch) {
204 : std::vector<Searcher *> s;
205 :
0: branch 0 not taken
0: branch 1 not taken
206 0: if (PutPGSearcherLast) {
207 0: PGSearcher* p = new PGSearcher();
208 0: p->deactivate();
209 0: s.push_back(searcher);
210 0: s.push_back(p); // put PGSearcher last!
211 : }
212 : else {
213 : // make sure PGSearcher goes first :)
214 0: s.push_back(new PGSearcher());
215 : // followed by whatever searcher the user has concocted:
216 0: s.push_back(searcher);
217 : }
218 :
219 0: searcher = new PGSupervisedSearcher(s);
220 : }
221 :
222 103: klee_message("BEGIN searcher description");
223 103: searcher->printName();
224 103: klee_message("END searcher description");
225 :
226 103: return searcher;
103: branch 0 taken
0: branch 1 not taken
103: branch 2 taken
0: branch 3 not taken
227 309: }
Generated: 2009-05-17 22:47 by zcov