1 // -*- mode: C++ -*-
2 //
3 // Copyright (c) 2007, 2008, 2010, 2011, 2013, 2015, 2017 The University of Utah
4 // All rights reserved.
5 //
6 // This file is part of `csmith', a random generator of C programs.
7 //
8 // Redistribution and use in source and binary forms, with or without
9 // modification, are permitted provided that the following conditions are met:
10 //
11 // * Redistributions of source code must retain the above copyright notice,
12 // this list of conditions and the following disclaimer.
13 //
14 // * Redistributions in binary form must reproduce the above copyright
15 // notice, this list of conditions and the following disclaimer in the
16 // documentation and/or other materials provided with the distribution.
17 //
18 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
22 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
23 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
24 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
25 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
26 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
27 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
28 // POSSIBILITY OF SUCH DAMAGE.
29
30 #if HAVE_CONFIG_H
31 # include <config.h>
32 #endif
33
34 #ifdef WIN32
35 #pragma warning(disable : 4786) /* Disable annoying warning messages */
36 #endif
37
38 #include "Bookkeeper.h"
39 #include <cassert>
40 #include <iostream>
41 #include "Variable.h"
42 #include "Type.h"
43 #include "Function.h"
44 #include "Expression.h"
45 #include "ExpressionVariable.h"
46 #include "Fact.h"
47 #include "FactPointTo.h"
48 #include "FactMgr.h"
49 #include "CVQualifiers.h"
50 #include "Statement.h"
51 #include "Block.h"
52 #include "CGOptions.h"
53
54 using namespace std;
55
56 ///////////////////////////////////////////////////////////////////////////////
57
58 // counter for all levels of struct depth
59 std::vector<int> Bookkeeper::struct_depth_cnts;
60 int Bookkeeper::union_var_cnt = 0;
61 std::vector<int> Bookkeeper::expr_depth_cnts;
62 std::vector<int> Bookkeeper::blk_depth_cnts;
63 std::vector<int> Bookkeeper::dereference_level_cnts;
64 int Bookkeeper::address_taken_cnt = 0;
65 std::vector<int> Bookkeeper::read_dereference_cnts;
66 std::vector<int> Bookkeeper::write_dereference_cnts;
67 int Bookkeeper::cmp_ptr_to_null = 0;
68 int Bookkeeper::cmp_ptr_to_ptr = 0;
69 int Bookkeeper::cmp_ptr_to_addr = 0;
70 int Bookkeeper::read_volatile_cnt = 0;
71 int Bookkeeper::write_volatile_cnt = 0;
72 int Bookkeeper::read_non_volatile_cnt = 0;
73 int Bookkeeper::write_non_volatile_cnt = 0;
74 int Bookkeeper::read_volatile_thru_ptr_cnt = 0;
75 int Bookkeeper::write_volatile_thru_ptr_cnt = 0;
76 int Bookkeeper::pointer_avail_for_dereference = 0;
77 int Bookkeeper::volatile_avail = 0;
78 int Bookkeeper::structs_with_bitfields = 0;
79 std::vector<int> Bookkeeper::vars_with_bitfields;
80 std::vector<int> Bookkeeper::vars_with_full_bitfields;
81 int Bookkeeper::vars_with_bitfields_address_taken_cnt = 0;
82 int Bookkeeper::bitfields_in_total = 0;
83 int Bookkeeper::unamed_bitfields_in_total = 0;
84 int Bookkeeper::const_bitfields_in_total = 0;
85 int Bookkeeper::volatile_bitfields_in_total = 0;
86 int Bookkeeper::lhs_bitfields_structs_vars_cnt = 0;
87 int Bookkeeper::rhs_bitfields_structs_vars_cnt = 0;
88 int Bookkeeper::lhs_bitfield_cnt = 0;
89 int Bookkeeper::rhs_bitfield_cnt = 0;
90 int Bookkeeper::forward_jump_cnt = 0;
91 int Bookkeeper::backward_jump_cnt = 0;
92 int Bookkeeper::use_new_var_cnt = 0;
93 int Bookkeeper::use_old_var_cnt = 0;
94 bool Bookkeeper::rely_on_int_size = false;
95 bool Bookkeeper::rely_on_ptr_size = false;
96
97 /*
98 *
99 */
Bookkeeper()100 Bookkeeper::Bookkeeper()
101 {
102 }
103
104 /*
105 *
106 */
~Bookkeeper(void)107 Bookkeeper::~Bookkeeper(void)
108 {
109 // Nothing to do.
110 }
111
112 static void
formated_output(std::ostream & out,const char * msg,int num)113 formated_output(std::ostream &out, const char* msg, int num)
114 {
115 out << "XXX " << msg << num << endl;
116 }
117
118 static void
formated_outputf(std::ostream & out,const char * msg,double num)119 formated_outputf(std::ostream &out, const char* msg, double num)
120 {
121 out << "XXX " << msg << num << endl;
122 }
123
124 void
doFinalization()125 Bookkeeper::doFinalization()
126 {
127 Bookkeeper::struct_depth_cnts.clear();
128 Bookkeeper::expr_depth_cnts.clear();
129 Bookkeeper::dereference_level_cnts.clear();
130 Bookkeeper::address_taken_cnt = 0;
131 Bookkeeper::write_dereference_cnts.clear();
132 Bookkeeper::read_dereference_cnts.clear();
133 Bookkeeper::cmp_ptr_to_null = 0;
134 Bookkeeper::cmp_ptr_to_ptr = 0;
135 Bookkeeper::cmp_ptr_to_addr = 0;
136
137 }
138
139 int
stat_blk_depths_for_stmt(const Statement * s)140 Bookkeeper::stat_blk_depths_for_stmt(const Statement* s)
141 {
142 size_t i, j;
143 int cnt = 0;
144 if (s->eType != eBlock) {
145 incr_counter(blk_depth_cnts, s->get_blk_depth() -1);
146 cnt++;
147 }
148 vector<const Block*> blks;
149 s->get_blocks(blks);
150 for (i=0; i<blks.size(); i++) {
151 for (j=0; j<blks[i]->stms.size(); j++) {
152 cnt += stat_blk_depths_for_stmt(blks[i]->stms[j]);
153 }
154 }
155 return cnt;
156 }
157
158 int
stat_blk_depths(void)159 Bookkeeper::stat_blk_depths(void)
160 {
161 const vector<Function*>& funcs = get_all_functions();
162 int cnt = 0;
163 for (size_t i=0; i<funcs.size(); i++) {
164 if (funcs[i]->is_builtin)
165 continue;
166 cnt += stat_blk_depths_for_stmt(funcs[i]->body);
167 }
168 return cnt;
169 }
170
171 void
output_stmts_statistics(std::ostream & out)172 Bookkeeper::output_stmts_statistics(std::ostream &out)
173 {
174 size_t i;
175 int stmt_cnt = stat_blk_depths();
176 formated_output(out, "stmts: ", stmt_cnt);
177 formated_output(out, "max block depth: ", (blk_depth_cnts.size() - 1));
178 out << "breakdown:" << endl;
179 for (i=0; i<blk_depth_cnts.size(); i++) {
180 if (blk_depth_cnts[i]) {
181 out << " depth: " << i << ", occurrence: " << blk_depth_cnts[i] << endl;
182 }
183 }
184 }
185
186 void
output_statistics(std::ostream & out)187 Bookkeeper::output_statistics(std::ostream &out)
188 {
189 output_struct_union_statistics(out);
190 out << endl;
191 output_expr_statistics(out);
192 out << endl;
193 output_pointer_statistics(out);
194 out << endl;
195 output_volatile_access_statistics(out);
196 out << endl;
197 output_jump_statistics(out);
198 out << endl;
199 output_stmts_statistics(out);
200 out << endl;
201 output_var_freshness(out);
202 if (rely_on_int_size) {
203 out << "FYI: the random generator makes assumptions about the integer size. See ";
204 out << PLATFORM_CONFIG_FILE << " for more details." << endl;
205 }
206 if (rely_on_ptr_size) {
207 out << "FYI: the random generator makes assumptions about the pointer size. See ";
208 out << PLATFORM_CONFIG_FILE << " for more details." << endl;
209 }
210 }
211
212 void
output_struct_union_statistics(std::ostream & out)213 Bookkeeper::output_struct_union_statistics(std::ostream &out)
214 {
215 formated_output(out, "max struct depth: ", (struct_depth_cnts.size()-1));
216 out << "breakdown:" << endl;
217 for (size_t i=0; i<struct_depth_cnts.size(); i++) {
218 out << " depth: " << i << ", occurrence: " << struct_depth_cnts[i] << endl;
219 }
220 formated_output(out, "total union variables: ", union_var_cnt);
221 Bookkeeper::output_bitfields(out);
222 }
223
224 void
stat_expr_depths_for_stmt(const Statement * s)225 Bookkeeper::stat_expr_depths_for_stmt(const Statement* s)
226 {
227 size_t i, j;
228 vector<const Expression*> exprs;
229 vector<const Block*> blks;
230 s->get_exprs(exprs);
231 for (i=0; i<exprs.size(); i++) {
232 incr_counter(expr_depth_cnts, exprs[i]->get_complexity());
233 }
234 s->get_blocks(blks);
235 for (i=0; i<blks.size(); i++) {
236 for (j=0; j<blks[i]->stms.size(); j++) {
237 stat_expr_depths_for_stmt(blks[i]->stms[j]);
238 }
239 }
240 }
241
242 void
stat_expr_depths(void)243 Bookkeeper::stat_expr_depths(void)
244 {
245 const vector<Function*>& funcs = get_all_functions();
246 for (size_t i=0; i<funcs.size(); i++) {
247 if (funcs[i]->is_builtin)
248 continue;
249 stat_expr_depths_for_stmt(funcs[i]->body);
250 }
251 }
252
253 void
output_expr_statistics(std::ostream & out)254 Bookkeeper::output_expr_statistics(std::ostream &out)
255 {
256 size_t i;
257 stat_expr_depths();
258 formated_output(out, "max expression depth: ", (expr_depth_cnts.size() - 1));
259 out << "breakdown:" << endl;
260 for (i=0; i<expr_depth_cnts.size(); i++) {
261 if (expr_depth_cnts[i]) {
262 out << " depth: " << i << ", occurrence: " << expr_depth_cnts[i] << endl;
263 }
264 }
265 }
266
267 void
output_pointer_statistics(std::ostream & out)268 Bookkeeper::output_pointer_statistics(std::ostream &out)
269 {
270 size_t i;
271 int total_alias_cnt = 0;
272 int total_has_null_ptr = 0;
273 int point_to_scalar = 0;
274 int point_to_struct = 0;
275 int point_to_pointer = 0;
276 const vector<const Variable*>& ptrs = FactPointTo::all_ptrs;
277 const vector<vector<const Variable*> >& aliases = FactPointTo::all_aliases;
278 for (i=0; i<ptrs.size(); i++) {
279 total_alias_cnt += aliases[i].size();
280 if (find_variable_in_set(aliases[i], FactPointTo::null_ptr) >= 0) {
281 total_has_null_ptr++;
282 }
283 const Variable* var = ptrs[i];
284 const Type* t = var->type;
285 assert(t->eType == ePointer);
286 if (t->get_indirect_level() > 1) {
287 point_to_pointer++;
288 }
289 else if (t->ptr_type->eType == eSimple) {
290 point_to_scalar++;
291 }
292 else if (t->ptr_type->eType == eStruct) {
293 point_to_struct++;
294 }
295 }
296
297 formated_output(out, "total number of pointers: ", ptrs.size());
298 if (ptrs.size() > 0) {
299 out << endl;
300 formated_output(out, "times a variable address is taken: ", address_taken_cnt);
301 formated_output(out, "times a pointer is dereferenced on RHS: ", calc_total(read_dereference_cnts));
302 out << "breakdown:" << endl;
303 for (i=1; i<read_dereference_cnts.size(); i++) {
304 out << " depth: " << i << ", occurrence: " << read_dereference_cnts[i] << endl;
305 }
306 formated_output(out, "times a pointer is dereferenced on LHS: ", calc_total(write_dereference_cnts));
307 out << "breakdown:" << endl;
308 for (i=1; i<write_dereference_cnts.size(); i++) {
309 out << " depth: " << i << ", occurrence: " << write_dereference_cnts[i] << endl;
310 }
311 formated_output(out, "times a pointer is compared with null: ", cmp_ptr_to_null);
312 formated_output(out, "times a pointer is compared with address of another variable: ", cmp_ptr_to_addr);
313 formated_output(out, "times a pointer is compared with another pointer: ", cmp_ptr_to_ptr);
314 formated_output(out, "times a pointer is qualified to be dereferenced: ", pointer_avail_for_dereference);
315
316 // if there are dereferenced pointers
317 if (dereference_level_cnts.size()) {
318 out << endl;
319 formated_output(out, "max dereference level: ", dereference_level_cnts.size()-1);
320 out << "breakdown:" << endl;
321 for (i=0; i<dereference_level_cnts.size(); i++) {
322 out << " level: " << i << ", occurrence: " << dereference_level_cnts[i] << endl;
323 }
324 }
325 formated_output(out, "number of pointers point to pointers: ", point_to_pointer);
326 formated_output(out, "number of pointers point to scalars: ", point_to_scalar);
327 formated_output(out, "number of pointers point to structs: ", point_to_struct);
328 out.precision(3);
329 formated_outputf(out, "percent of pointers has null in alias set: ", total_has_null_ptr*100.0/ptrs.size());
330 formated_outputf(out, "average alias set size: ", total_alias_cnt*1.0 / ptrs.size());
331 }
332 }
333
334 void
record_address_taken(const Variable * var)335 Bookkeeper::record_address_taken(const Variable *var)
336 {
337 assert(var);
338 assert(var->type);
339 const Type *type = var->type;
340
341 // explicitly removing const-ness is a little bit ugly,
342 // but changing record_address_taken interface involves
343 // a lot of code change...
344 Variable *addrTakenVar = const_cast<Variable*>(var);
345 addrTakenVar->isAddrTaken = true;
346
347 Bookkeeper::address_taken_cnt++;
348 if (type->has_bitfields())
349 Bookkeeper::vars_with_bitfields_address_taken_cnt++;
350 }
351
352 void
record_bitfields_reads(const Variable * var)353 Bookkeeper::record_bitfields_reads(const Variable *var)
354 {
355 assert(var);
356 assert(var->type);
357 const Type *type = var->type;
358
359 if (type->has_bitfields())
360 Bookkeeper::rhs_bitfields_structs_vars_cnt++;
361 if (var->isBitfield_)
362 Bookkeeper::rhs_bitfield_cnt++;
363 }
364
365 void
record_bitfields_writes(const Variable * var)366 Bookkeeper::record_bitfields_writes(const Variable *var)
367 {
368 assert(var);
369 assert(var->type);
370 const Type *type = var->type;
371
372 if (type->has_bitfields())
373 Bookkeeper::lhs_bitfields_structs_vars_cnt++;
374 if (var->isBitfield_)
375 Bookkeeper::lhs_bitfield_cnt++;
376 }
377
378 /*
379 * record the LHS/RHS types of comparisons between pointers
380 */
381 void
record_pointer_comparisons(const Expression * lhs,const Expression * rhs)382 Bookkeeper::record_pointer_comparisons(const Expression* lhs, const Expression* rhs)
383 {
384 if (lhs->term_type != eFunction && rhs->term_type != eFunction) {
385 assert(lhs->get_type().eType == ePointer && rhs->get_type().eType == ePointer);
386 if ((lhs->term_type == eVariable && rhs->term_type == eConstant) ||
387 (rhs->term_type == eVariable && lhs->term_type == eConstant)) {
388 cmp_ptr_to_null++;
389 }
390 else if (lhs->term_type==eVariable && rhs->term_type==eVariable) {
391 const ExpressionVariable* left = (ExpressionVariable*)lhs;
392 const ExpressionVariable* right = (ExpressionVariable*)rhs;
393 if (left->get_indirect_level() == right->get_indirect_level()) {
394 cmp_ptr_to_ptr++;
395 }
396 else {
397 cmp_ptr_to_addr++;
398 }
399 }
400 }
401 }
402
403 /*
404 * count volatile/non-volatile reads/writes, specifically access thru pointers
405 */
406 void
record_volatile_access(const Variable * var,int deref_level,bool write)407 Bookkeeper::record_volatile_access(const Variable* var, int deref_level, bool write)
408 {
409 assert(var);
410 int i;
411 write ? record_bitfields_writes(var) : record_bitfields_reads(var);;
412 for (i=0; i<=deref_level; i++) {
413 if (write) {
414 if (var->qfer.is_volatile_after_deref(i)) {
415 if (i) {
416 Bookkeeper::write_volatile_thru_ptr_cnt++;
417 }
418 Bookkeeper::write_volatile_cnt++;
419 //var->OutputDef(cout);
420 }
421 else {
422 Bookkeeper::write_non_volatile_cnt++;
423 }
424 }
425 else {
426 if (var->qfer.is_volatile_after_deref(i)) {
427 if (i) {
428 Bookkeeper::read_volatile_thru_ptr_cnt++;
429 }
430 Bookkeeper::read_volatile_cnt++;
431 }
432 else {
433 Bookkeeper::read_non_volatile_cnt++;
434 }
435 }
436 }
437 }
438
439 void
output_volatile_access_statistics(std::ostream & out)440 Bookkeeper::output_volatile_access_statistics(std::ostream &out)
441 {
442 // size_t i;
443 formated_output(out, "times a non-volatile is read: ", read_non_volatile_cnt);
444 formated_output(out, "times a non-volatile is write: ", write_non_volatile_cnt);
445 formated_output(out, "times a volatile is read: ", read_volatile_cnt);
446 formated_output(out, " times read thru a pointer: ", read_volatile_thru_ptr_cnt);
447 formated_output(out, "times a volatile is write: ", write_volatile_cnt);
448 formated_output(out, " times written thru a pointer: ", write_volatile_thru_ptr_cnt);
449 double percentage = (read_non_volatile_cnt + write_non_volatile_cnt) * 100.0 /
450 (read_non_volatile_cnt + write_non_volatile_cnt + read_volatile_cnt + write_volatile_cnt);
451
452 formated_outputf(out, "times a volatile is available for access: ", volatile_avail);
453 out.precision(3);
454 formated_outputf(out, "percentage of non-volatile access: ", percentage);
455 }
456
457 void
output_bitfields(std::ostream & out)458 Bookkeeper::output_bitfields(std::ostream &out)
459 {
460 if (CGOptions::bitfields()) {
461 out << std::endl;
462 //formated_output(out, "structs with full-bitfields: ", structs_with_bitfields);
463 formated_output(out, "non-zero bitfields defined in structs: ", bitfields_in_total);
464 formated_output(out, "zero bitfields defined in structs: ", unamed_bitfields_in_total);
465 formated_output(out, "const bitfields defined in structs: ", const_bitfields_in_total);
466 formated_output(out, "volatile bitfields defined in structs: ", volatile_bitfields_in_total);
467 Bookkeeper::output_counters(out, "structs with bitfields in the program: ", "indirect level", vars_with_bitfields);
468 Bookkeeper::output_counters(out, "full-bitfields structs in the program: ", "indirect level", vars_with_full_bitfields);
469 formated_output(out, "times a bitfields struct's address is taken: ", vars_with_bitfields_address_taken_cnt);
470 formated_output(out, "times a bitfields struct on LHS: ", lhs_bitfields_structs_vars_cnt);
471 formated_output(out, "times a bitfields struct on RHS: ", rhs_bitfields_structs_vars_cnt);
472 formated_output(out, "times a single bitfield on LHS: ", lhs_bitfield_cnt);
473 formated_output(out, "times a single bitfield on RHS: ", rhs_bitfield_cnt);
474 }
475 }
476
477 void
record_vars_with_bitfields(const Type * type)478 Bookkeeper::record_vars_with_bitfields(const Type *type)
479 {
480 assert(type);
481 const Type *base_type = type->get_base_type();
482 if (!base_type->is_aggregate() ||
483 (!base_type->has_bitfields()))
484 return;
485
486 int level = type->get_indirect_level();
487 incr_counter(Bookkeeper::vars_with_bitfields, level);
488 if (type->is_full_bitfields_struct())
489 incr_counter(Bookkeeper::vars_with_full_bitfields, level);
490 }
491
492 void
record_type_with_bitfields(const Type * typ)493 Bookkeeper::record_type_with_bitfields(const Type *typ)
494 {
495 if (!typ->is_aggregate()) return;
496
497 if (typ->has_bitfields()) {
498 Bookkeeper::structs_with_bitfields++;
499 size_t len = typ->bitfields_length_.size();
500 assert(len == typ->fields.size());
501 for (size_t i = 0; i < len; ++i) {
502 if (!typ->is_bitfield(i))
503 continue;
504
505 Bookkeeper::bitfields_in_total++;
506 if (typ->bitfields_length_[i] == 0)
507 Bookkeeper::unamed_bitfields_in_total++;
508
509 CVQualifiers qual = typ->qfers_[i];
510 if (qual.is_const())
511 Bookkeeper::const_bitfields_in_total++;
512 if (qual.is_volatile())
513 Bookkeeper::volatile_bitfields_in_total++;
514 }
515 }
516 }
517
518 void
output_jump_statistics(std::ostream & out)519 Bookkeeper::output_jump_statistics(std::ostream &out)
520 {
521 formated_output(out, "forward jumps: ", forward_jump_cnt);
522 formated_output(out, "backward jumps: ", backward_jump_cnt);
523 }
524
525 void
output_var_freshness(std::ostream & out)526 Bookkeeper::output_var_freshness(std::ostream &out)
527 {
528 int total = use_new_var_cnt + use_old_var_cnt;
529 formated_outputf(out, "percentage a fresh-made variable is used: ", use_new_var_cnt * 100.0 / total);
530 formated_outputf(out, "percentage an existing variable is used: ", use_old_var_cnt * 100.0 / total);
531 }
532
533 void
output_counters(std::ostream & out,const char * prefix_msg,const char * breakdown_msg,const std::vector<int> & counters,int starting_pos)534 Bookkeeper::output_counters(std::ostream &out, const char* prefix_msg,
535 const char* breakdown_msg, const std::vector<int> &counters, int starting_pos)
536 {
537 assert(prefix_msg && breakdown_msg);
538 formated_output(out, prefix_msg, calc_total(counters));
539 out << "breakdown:" << std::endl;
540 for (size_t i=starting_pos; i<counters.size(); i++) {
541 out << " " << breakdown_msg << ": " << i << ", occurrence: " << counters[i] << endl;
542 }
543 }
544
incr_counter(std::vector<int> & counters,int pos)545 void incr_counter(std::vector<int>& counters, int pos)
546 {
547 size_t len = counters.size();
548 size_t index = (size_t)pos;
549 if (index >= len) {
550 counters.resize(index+1);
551 for (size_t i= len; i<=index; i++) {
552 counters[i] = 0;
553 }
554 }
555 counters[index]++;
556 }
557
calc_total(const std::vector<int> & counters)558 int calc_total(const std::vector<int>& counters)
559 {
560 size_t i;
561 int total = 0;
562 for (i=0; i<counters.size(); i++) {
563 total += counters[i];
564 }
565 return total;
566 }
567
568 ///////////////////////////////////////////////////////////////////////////////
569
570 // Local Bookkeepers:
571 // c-basic-offset: 4
572 // tab-width: 4
573 // End:
574
575 // End of file.
576