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 //
31 // This file was derived from a random program generator written by Bryan
32 // Turner. The attributions in that file was:
33 //
34 // Random Program Generator
35 // Bryan Turner (bryan.turner@pobox.com)
36 // July, 2005
37 //
38
39 #if HAVE_CONFIG_H
40 # include <config.h>
41 #endif
42
43 #ifdef WIN32
44 #pragma warning(disable : 4786) /* Disable annoying warning messages */
45 #endif
46
47 #include "Statement.h"
48 #include <cassert>
49 #include <map>
50 #include <iostream>
51 #include "Common.h"
52
53 #include "CGContext.h"
54 #include "CGOptions.h"
55 #include "Function.h"
56 #include "Expression.h"
57 #include "ExpressionFuncall.h"
58 #include "FunctionInvocation.h"
59 #include "FunctionInvocationUser.h"
60 #include "FactPointTo.h"
61
62 #include "Block.h" // temporary; don't want to depend on subclases!
63 #include "StatementAssign.h" // temporary; don't want to depend on subclases!
64 #include "StatementExpr.h" // temporary; don't want to depend on subclases!
65 #include "StatementFor.h" // temporary; don't want to depend on subclases!
66 #include "StatementIf.h" // temporary; don't want to depend on subclases!
67 #include "StatementReturn.h" // temporary; don't want to depend on subclases!
68 #include "StatementBreak.h"
69 #include "StatementContinue.h"
70 #include "StatementGoto.h"
71 #include "StatementArrayOp.h"
72 #include "Variable.h"
73 #include "ArrayVariable.h"
74 #include "VectorFilter.h"
75 #include "ProbabilityTable.h"
76 #include "PartialExpander.h"
77 #include "random.h"
78 #include "Fact.h"
79 #include "FactMgr.h"
80 #include "CFGEdge.h"
81 #include "Error.h"
82 #include "DepthSpec.h"
83 #include "OutputMgr.h"
84 #include "util.h"
85 #include "StringUtils.h"
86 #include "VariableSelector.h"
87
88 using namespace std;
89 const Statement* Statement::failed_stm;
90
91 ///////////////////////////////////////////////////////////////////////////////
92 class StatementFilter : public Filter
93 {
94 public:
95 explicit StatementFilter(const CGContext &cg_context);
96
97 virtual ~StatementFilter(void);
98
99 virtual bool filter(int v) const;
100 private:
101 const CGContext &cg_context_;
102 };
103
StatementFilter(const CGContext & cg_context)104 StatementFilter::StatementFilter(const CGContext &cg_context)
105 : cg_context_(cg_context)
106 {
107
108 }
109
~StatementFilter(void)110 StatementFilter::~StatementFilter(void)
111 {
112
113 }
114
115 // use a table to define probabilities of different kinds of statements
116 // Must initialize it before use
117 ProbabilityTable<unsigned int, ProbName> *Statement::stmtTable_ = NULL;
118
119 void
InitProbabilityTable()120 Statement::InitProbabilityTable()
121 {
122 if (Statement::stmtTable_)
123 return;
124
125 Statement::stmtTable_ = new ProbabilityTable<unsigned int, ProbName>();
126 Statement::stmtTable_->initialize(pStatementProb);
127 }
128
129 eStatementType
number_to_type(unsigned int value)130 Statement::number_to_type(unsigned int value)
131 {
132 assert(Statement::stmtTable_);
133 assert(value < 100);
134 ProbName pname = Statement::stmtTable_->get_value(value);
135 eStatementType type = static_cast<eStatementType>(Probabilities::pname_to_type(pname));
136 return type;
137 }
138
filter(int value) const139 bool StatementFilter::filter(int value) const
140 {
141 assert(value != -1);
142
143 if (!this->valid_filter())
144 return false;
145
146 eStatementType type = Statement::number_to_type(value);
147
148 // If expand_check returns false, we filter out v.
149 if (!PartialExpander::expand_check(type))
150 return true;
151
152 const Type* return_type = cg_context_.get_current_func()->return_type;
153 bool no_return = (return_type->eType == eSimple && return_type->simple_type == eVoid);
154
155 if (type == eBlock) {
156 return true;
157 }
158 if ((type == eReturn) && no_return) {
159 return true;
160 }
161
162 if ( (type == eBreak || type == eContinue) && !(cg_context_.flags & IN_LOOP) ) {
163 return true;
164 }
165
166 // Limit Function complexity (depth of nested control structures)
167 if (cg_context_.blk_depth >= CGOptions::max_blk_depth()) {
168 return Statement::is_compound(type);
169 }
170 else if (Function::reach_max_functions_cnt()) { // Limit # of functions..
171 if (type != eInvoke)
172 return false;
173 else
174 return true;
175 }
176 else {
177 return false;
178 }
179
180 return false;
181 }
182
find_stm_in_set(const vector<const Statement * > & set,const Statement * s)183 int find_stm_in_set(const vector<const Statement*>& set, const Statement* s)
184 {
185 size_t i;
186 for (i=0; i<set.size(); i++) {
187 if (set[i] == s) {
188 return i;
189 }
190 }
191 return -1;
192 }
193
194 ///////////////////////////////////////////////////////////////////////////////
195
196 // -----------------------------------------------------------------------------
197 //
198 // TODO: Build probability tables for each decision point
199 // IE: Return statements less common than assignment statements, etc.
200 // Allow MIN, MAX and pluggable density functions (uniform, normal, guassian, ...)
201 //
202 // Like this:
203 /*
204 unsigned int probabilityStatement[eStatementType] =
205 {
206 100, // eAssign,
207 75, // eIfElse,
208 30, // eFor, // Make this a generic loop construct (while/for/do)
209 30, // eInvoke,
210 10, // eReturn,
211 }
212
213 probability probStatement
214 {
215 2, // Min
216 0, // Max
217 probabilityStatement // Pluggable Function (custom probability table, in this case)
218 }
219 */
220
221 static eStatementType
StatementProbability(const StatementFilter * filter)222 StatementProbability(const StatementFilter *filter)
223 {
224 int value = rnd_upto(100, filter);
225 ERROR_GUARD(MAX_STATEMENT_TYPE);
226 assert(value != -1);
227 assert(value >= 0 && value < 100);
228 return Statement::number_to_type(value);
229 }
230
231 int Statement::sid = 0;
232 /*
233 *
234 */
235 Statement *
make_random(CGContext & cg_context,eStatementType t)236 Statement::make_random(CGContext &cg_context,
237 eStatementType t)
238 {
239 DEPTH_GUARD_BY_TYPE_RETURN_WITH_FLAG(dtStatement, t, NULL);
240 // Should initialize table first
241 Statement::InitProbabilityTable();
242
243 if ((CGOptions::stop_by_stmt() >= 0) && (sid >= CGOptions::stop_by_stmt())) {
244 t = eReturn;
245 }
246
247 // Add more statements:
248 // for
249 // while
250 // library call (malloc, free, str*, mem*, etc..)?
251 // switch?
252 // ..?
253 if (t == MAX_STATEMENT_TYPE) {
254 StatementFilter filter(cg_context);
255 t = StatementProbability(&filter);
256 ERROR_GUARD(NULL);
257 }
258 FactMgr* fm = get_fact_mgr(&cg_context);
259 FactVec pre_facts = fm->global_facts;
260 Effect pre_effect = cg_context.get_accum_effect();
261 cg_context.get_effect_stm().clear();
262 cg_context.expr_depth = 0;
263 if (is_compound(t)) {
264 cg_context.blk_depth++;
265 }
266 // XXX: interim ickiness
267 Statement *s = 0;
268
269 switch (t) {
270 default:
271 assert(!"unknown Statement type");
272 break;
273 case eAssign:
274 s = StatementAssign::make_random(cg_context);
275 break;
276 case eBlock:
277 s = Block::make_random(cg_context);
278 break;
279 case eFor:
280 s = StatementFor::make_random(cg_context);
281 break;
282 case eIfElse:
283 s = StatementIf::make_random(cg_context);
284 break;
285 case eInvoke:
286 s = StatementExpr::make_random(cg_context);
287 break;
288 case eReturn:
289 s = StatementReturn::make_random(cg_context);
290 break;
291 case eBreak:
292 s = StatementBreak::make_random(cg_context);
293 break;
294 case eContinue:
295 s = StatementContinue::make_random(cg_context);
296 break;
297 case eGoto:
298 s = StatementGoto::make_random(cg_context);
299 break;
300 case eArrayOp:
301 s = StatementArrayOp::make_random(cg_context);
302 break;
303 }
304
305 ERROR_GUARD(NULL);
306 if (is_compound(t)) {
307 cg_context.blk_depth--;
308 }
309 // sometimes make_random may return 0 for various reasons. keep generating
310 if (s == 0) {
311 return make_random(cg_context);
312 }
313 s->func = cg_context.get_current_func();
314 s->parent = cg_context.get_current_block();
315 s->post_creation_analysis(pre_facts, pre_effect, cg_context);
316 return s;
317 }
318
319 std::vector<const ExpressionVariable*>
get_dereferenced_ptrs(void) const320 Statement::get_dereferenced_ptrs(void) const
321 {
322 // return a empty vector by default
323 std::vector<const ExpressionVariable*> empty;
324 return empty;
325 }
326
327 void
get_referenced_ptrs(std::vector<const Variable * > & ptrs) const328 Statement::get_referenced_ptrs(std::vector<const Variable*>& ptrs) const
329 {
330 size_t i;
331 vector<const Expression*> exprs;
332 vector<const Block*> blks;
333 get_exprs(exprs);
334 get_blocks(blks);
335 for (i=0; i<exprs.size(); i++) {
336 exprs[i]->get_referenced_ptrs(ptrs);
337 }
338 for (i=0; i<blks.size(); i++) {
339 for (size_t j=0; j<blks[i]->stms.size(); j++) {
340 const Statement* s = blks[i]->stms[j];
341 s->get_referenced_ptrs(ptrs);
342 }
343 }
344 }
345
346 int
get_blk_depth(void) const347 Statement::get_blk_depth(void) const
348 {
349 int depth = 0;
350 for (const Block* b = parent; b != NULL; b = b->parent) {
351 depth++;
352 }
353 return depth;
354 }
355
356 bool
is_ptr_used(void) const357 Statement::is_ptr_used(void) const
358 {
359 vector<const Variable*> ptrs;
360 get_referenced_ptrs(ptrs);
361 return !ptrs.empty();
362 }
363
364 /*
365 *
366 */
Statement(eStatementType st,Block * b)367 Statement::Statement(eStatementType st, Block* b)
368 : eType(st),
369 func(b ? b->func : 0),
370 parent(b)
371 {
372 stm_id = Statement::sid;
373 Statement::sid++;
374 }
375
376 /*
377 *
378 */
~Statement(void)379 Statement::~Statement(void)
380 {
381 // Nothing to do.
382 }
383
384 /*
385 * return true if statement is contained in block b
386 */
387 bool
in_block(const Block * b) const388 Statement::in_block(const Block* b) const
389 {
390 const Block* tmp = parent;
391 while (tmp) {
392 if (tmp == b) return true;
393 tmp = tmp->parent;
394 }
395 return false;
396 }
397
398 /*
399 * return true if this statement dominates s
400 */
401 bool
dominate(const Statement * s) const402 Statement::dominate(const Statement* s) const
403 {
404 if (s->parent == this) {
405 return true;
406 }
407 if (parent == s->parent) {
408 return stm_id <= s->stm_id;
409 }
410 const Statement* container = s->find_container_stm();
411 if (container == 0) {
412 container = s->parent;
413 }
414 if (container != 0) {
415 return dominate(container);
416 }
417 return false;
418 }
419
420 /*
421 * find the parent for-statement or while-statement (to be implemented)
422 * that contains this statement or block
423 */
424 const Statement*
find_container_stm(void) const425 Statement::find_container_stm(void) const
426 {
427 const Block* b = (eType == eBlock) ? (const Block*)this : parent;
428 if (b != 0 && b->parent != 0) {
429 for (size_t i=0; i<b->parent->stms.size(); i++) {
430 const Statement* s = b->parent->stms[i];
431 vector<const Block*> blks;
432 s->get_blocks(blks);
433 if (std::find(blks.begin(), blks.end(), b) != blks.end()) {
434 return s;
435 }
436 }
437 }
438 return 0;
439 }
440
441 /*
442 * return true if there is CFG edge(s) leading to this statement matching given attributes
443 */
444 bool
has_edge_in(bool post_dest,bool back_link) const445 Statement::has_edge_in(bool post_dest, bool back_link) const
446 {
447 if (func != 0) {
448 FactMgr* fm = get_fact_mgr_for_func(func);
449 assert(fm);
450 size_t i;
451 for (i=0; i<fm->cfg_edges.size(); i++) {
452 const CFGEdge* e = fm->cfg_edges[i];
453 if (e->dest == this && e->back_link == back_link && e->post_dest == post_dest) {
454 return true;
455 }
456 }
457 }
458 return false;
459 }
460
461 /*
462 * find CFG edges leading to this statement, found edges are stored in pass-in param "edges"
463 * return the number of edges found
464 */
465 int
find_edges_in(vector<const CFGEdge * > & edges,bool post_dest,bool back_link) const466 Statement::find_edges_in(vector<const CFGEdge*>& edges, bool post_dest, bool back_link) const
467 {
468 edges.clear();
469 if (func != 0) {
470 FactMgr* fm = get_fact_mgr_for_func(func);
471 assert(fm);
472 size_t i;
473 for (i=0; i<fm->cfg_edges.size(); i++) {
474 const CFGEdge* e = fm->cfg_edges[i];
475 if (e->dest == this && e->back_link == back_link && e->post_dest == post_dest) {
476 edges.push_back(e);
477 }
478 }
479 }
480 return edges.size();
481 }
482
483 /*
484 * return the label if this statement is the destination of a "goto" statement
485 */
486 std::string
find_jump_label(void) const487 Statement::find_jump_label(void) const
488 {
489 if (func != 0) {
490 FactMgr* fm = get_fact_mgr_for_func(func);
491 assert(fm);
492 size_t i;
493 for (i=0; i<fm->cfg_edges.size(); i++) {
494 const CFGEdge* e = fm->cfg_edges[i];
495 if (e->dest == this && e->src->eType == eGoto) {
496 const StatementGoto* sg = dynamic_cast<const StatementGoto*>(e->src);
497 assert(sg);
498 return sg->label;
499 }
500 }
501 }
502 return "";
503 }
504
505 /*
506 * find all "goto" statements that jumps to this statement
507 */
508 int
find_jump_sources(std::vector<const StatementGoto * > & gotos) const509 Statement::find_jump_sources(std::vector<const StatementGoto*>& gotos) const
510 {
511 if (func != 0) {
512 FactMgr* fm = get_fact_mgr_for_func(func);
513 assert(fm);
514 size_t i;
515 gotos.clear();
516 for (i=0; i<fm->cfg_edges.size(); i++) {
517 const CFGEdge* e = fm->cfg_edges[i];
518 if (e->dest == this && e->src->eType == eGoto) {
519 const StatementGoto* sg = dynamic_cast<const StatementGoto*>(e->src);
520 assert(sg);
521 gotos.push_back(sg);
522 }
523 }
524 }
525 return gotos.size();
526 }
527
528 /*
529 * a helper function for StatementFor and StatementIf
530 * include effect caused by block, and update the effect map for this statement in fact manager
531 */
532 void
set_accumulated_effect_after_block(Effect & eff,const Block * b,CGContext & cg_context) const533 Statement::set_accumulated_effect_after_block(Effect& eff, const Block* b, CGContext& cg_context) const
534 {
535 FactMgr* fm = get_fact_mgr(&cg_context);
536 eff.add_effect(fm->map_stm_effect[b]);
537 fm->map_stm_effect[this] = eff;
538 }
539
540 /*
541 * add back return_facts for skipped statement (see validate_and_update_facts)
542 */
543 void
add_back_return_facts(FactMgr * fm,std::vector<const Fact * > & facts) const544 Statement::add_back_return_facts(FactMgr* fm, std::vector<const Fact*>& facts) const
545 {
546 if (eType == eReturn) {
547 merge_facts(facts, fm->map_facts_out[this]);
548 } else {
549 vector<const Block*> blks;
550 get_blocks(blks);
551 for (size_t i=0; i<blks.size(); i++) {
552 for (size_t j=0; j<blks[i]->stms.size(); j++) {
553 blks[i]->stms[j]->add_back_return_facts(fm, facts);
554 }
555 }
556 }
557 }
558
559 /* return code:
560 * 0 means we successfully take a shortcut
561 * 1 means the shortcut fails due to effect conflict
562 * 2 means there is no shortcut
563 */
564 int
shortcut_analysis(vector<const Fact * > & inputs,CGContext & cg_context) const565 Statement::shortcut_analysis(vector<const Fact*>& inputs, CGContext& cg_context) const
566 {
567 FactMgr* fm = get_fact_mgr_for_func(func);
568 // the output facts of control statement (break/continue/goto) has removed local facts
569 // thus can not take this shortcut. (The facts we get should represent all variables
570 // visible in subsequent statement)
571 if (same_facts(inputs, fm->map_facts_in[this]) && !is_ctrl_stmt() && !contains_unfixed_goto())
572 {
573 //cg_context.get_effect_context().Output(cout);
574 //print_facts(inputs);
575 //fm->map_stm_effect[this].Output(cout);
576 if (cg_context.in_conflict(fm->map_stm_effect[this])) {
577 return 1;
578 }
579 inputs = fm->map_facts_out[this];
580 cg_context.add_effect(fm->map_stm_effect[this]);
581 fm->map_accum_effect[this] = *(cg_context.get_effect_accum());
582 return 0;
583 }
584 return 2;
585 }
586
587 /***************************************************************************************
588 * for a given input env, abstract a given statement, generate an output env, and
589 * update both input/output env for this statement
590 *
591 * shortcut: if this input env matches previous input env, use previous output env directly
592 ***************************************************************************************/
593 bool
validate_and_update_facts(vector<const Fact * > & inputs,CGContext & cg_context) const594 Statement::validate_and_update_facts(vector<const Fact*>& inputs, CGContext& cg_context) const
595 {
596 FactMgr* fm = get_fact_mgr_for_func(func);
597 int shortcut = shortcut_analysis(inputs, cg_context);
598 if (shortcut==0) {
599 /* mark the goto statements inside this statement as visited
600 this is to fix scenario like the following:
601
602 lbl: s1
603 for (...) {
604 goto lbl;
605 }
606
607 where the "for" statement is bypassed, but the output from "goto lbl"
608 must be feed into s1 in order to achieve a fixed point */
609 for (size_t i=0; i<fm->cfg_edges.size(); i++) {
610 const Statement* s = fm->cfg_edges[i]->src;
611 if (s->eType == eGoto && contains_stmt(s)) {
612 fm->map_visited[s] = true;
613 }
614 }
615 return true;
616 }
617 if (shortcut==1) return false;
618
619 vector<const Fact*> inputs_copy = inputs;
620 if (!stm_visit_facts(inputs, cg_context)) {
621 return false;
622 }
623 fm->set_fact_in(this, inputs_copy);
624 fm->set_fact_out(this, inputs);
625 return true;
626 }
627
628 bool
stm_visit_facts(vector<const Fact * > & inputs,CGContext & cg_context) const629 Statement::stm_visit_facts(vector<const Fact*>& inputs, CGContext& cg_context) const
630 {
631 cg_context.get_effect_stm().clear();
632 cg_context.curr_blk = parent;
633 FactMgr* fm = get_fact_mgr(&cg_context);
634 //static int g = 0;
635 //int h = g++;
636 bool ok = visit_facts(inputs, cg_context);
637
638
639 if (!ok && !is_compound(eType)) {
640 failed_stm = this;
641 }
642 //if (!FactPointTo::is_valid_ptr("g_75", inputs))
643 // Output(cout, fm);
644 fm->remove_rv_facts(inputs);
645 fm->map_accum_effect[this] = *(cg_context.get_effect_accum());
646 fm->map_visited[this] = true;
647 return ok;
648 }
649
650 /*
651 * find all the control flow manipulate statements, i.e. break/continue/goto
652 * (maybe return?) contained in this statement recursively
653 */
654 int
find_typed_stmts(vector<const Statement * > & stms,const vector<int> & stmt_types) const655 Statement::find_typed_stmts(vector<const Statement*>& stms, const vector<int>& stmt_types) const
656 {
657 if (std::find(stmt_types.begin(), stmt_types.end(), eType) != stmt_types.end()) {
658 stms.push_back(this);
659 }
660 vector<const Block*> blks;
661 get_blocks(blks);
662 for (size_t i=0; i<blks.size(); i++) {
663 for (size_t j=0; j<blks[i]->stms.size(); j++) {
664 const Statement* s = blks[i]->stms[j];
665 s->find_typed_stmts(stms, stmt_types);
666 }
667 }
668 return stms.size();
669 }
670
671 bool
is_1st_stm(void) const672 Statement::is_1st_stm(void) const
673 {
674 return parent && parent->stms.size() && parent->stms[0] == this;
675 }
676
677 bool
is_jump_target_from_other_blocks(void) const678 Statement::is_jump_target_from_other_blocks(void) const
679 {
680 vector<const StatementGoto*> gotos;
681 if (find_jump_sources(gotos)) {
682 size_t i;
683 for (i=0; i<gotos.size(); i++) {
684 if (gotos[i]->parent != this->parent) {
685 return true;
686 }
687 }
688 }
689 return false;
690 }
691
692 bool
read_union_field(void) const693 Statement::read_union_field(void) const
694 {
695 FactMgr* fm = get_fact_mgr_for_func(func);
696 assert(fm);
697 if (fm->map_stm_effect[this].union_field_is_read()) {
698 return true;
699 }
700 vector<const FunctionInvocationUser*> calls;
701 get_called_funcs(calls);
702 for (size_t i=0; i<calls.size(); i++) {
703 if (calls[i]->get_func()->union_field_read) {
704 return true;
705 }
706 }
707 return false;
708 }
709
710 /*
711 * return true if s is contained inside this statement
712 */
713 bool
contains_stmt(const Statement * s) const714 Statement::contains_stmt(const Statement* s) const
715 {
716 if (this == s) {
717 return true;
718 }
719 if (eType == eBlock) {
720 for (const Block* tmp = s->parent; tmp; tmp = tmp->parent) {
721 if (tmp == (const Block*)this) {
722 return true;
723 }
724 }
725 return false;
726 }
727 vector<const Block*> blks;
728 get_blocks(blks);
729 for (size_t i=0; i<blks.size(); i++) {
730 if (blks[i]->contains_stmt(s)) {
731 return true;
732 }
733 }
734 return false;
735 }
736
737 int
find_contained_labels(vector<string> & labels) const738 Statement::find_contained_labels(vector<string>& labels) const
739 {
740 string label = find_jump_label();
741 if (label != "") {
742 labels.push_back(label);
743 }
744
745 vector<const Block*> blks;
746 get_blocks(blks);
747 size_t i, j;
748 for (i=0; i<blks.size(); i++) {
749 for (j=0; j<blks[i]->stms.size(); j++) {
750 const Statement* s = blks[i]->stms[j];
751 s->find_contained_labels(labels);
752 }
753 }
754 return labels.size();
755 }
756
757 /*
758 * find all the functions directly called in this statement
759 */
760 const FunctionInvocation*
get_direct_invocation(void) const761 Statement::get_direct_invocation(void) const
762 {
763 if (eType == eAssign) {
764 const Expression* e = ((const StatementAssign*)this)->get_expr();
765 if (e->term_type == eFunction) {
766 return ((const ExpressionFuncall*)e)->get_invoke();
767 }
768 }
769 else if (eType == eInvoke) {
770 return ((const StatementExpr*)this)->get_invoke();
771 }
772 else if (eType == eIfElse) {
773 const StatementIf* si = (const StatementIf*)this;
774 const Expression* e = si->get_test();
775 if (e->term_type == eFunction) {
776 return ((const ExpressionFuncall*)e)->get_invoke();
777 }
778 }
779 return NULL;
780 }
781
782 /*
783 * find all the function calls in this statement
784 */
785 void
get_called_funcs(std::vector<const FunctionInvocationUser * > & funcs) const786 Statement::get_called_funcs(std::vector<const FunctionInvocationUser*>& funcs) const
787 {
788 size_t i;
789 vector<const Expression*> exprs;
790 vector<const Block*> blks;
791 get_exprs(exprs);
792 get_blocks(blks);
793 for (i=0; i<exprs.size(); i++) {
794 exprs[i]->get_called_funcs(funcs);
795 }
796 for (i=0; i<blks.size(); i++) {
797 for (size_t j=0; j<blks[i]->stms.size(); j++) {
798 const Statement* s = blks[i]->stms[j];
799 s->get_called_funcs(funcs);
800 }
801 }
802 }
803
804 /*
805 * return true if there are some goto statement contained in this statement
806 * that hasn't reached a fixed point
807 */
808 bool
contains_unfixed_goto(void) const809 Statement::contains_unfixed_goto(void) const
810 {
811 FactMgr* fm = get_fact_mgr_for_func(func);
812 assert(fm);
813 size_t i, j;
814 for (i=0; i<fm->cfg_edges.size(); i++) {
815 const CFGEdge* edge = fm->cfg_edges[i];
816 /* the following for-loop has to be analyzed at least once
817 label: ...
818 ...
819 for (...) {
820 goto label;
821 }
822 */
823 if (edge->src->eType == eGoto && contains_stmt(edge->src) && !fm->map_visited[edge->src] && !contains_stmt(edge->dest)) {
824 return true;
825 }
826 if (edge->src->eType == eGoto && fm->map_visited[edge->src] && contains_stmt(edge->dest)) {
827 // take care the special case caused by StatementGoto::visit_facts
828 if (!fm->map_facts_out[edge->src].empty() && fm->map_facts_in[edge->dest].empty()) {
829 return true;
830 }
831 for (j=0; j<fm->map_facts_in[edge->dest].size(); j++) {
832 const Fact* f = fm->map_facts_in[edge->dest][j];
833 // ignore return variable facts
834 if (!f->get_var()->is_rv()) {
835 const Fact* jump_src_f = find_related_fact(fm->map_facts_out[edge->src], f);
836 if (jump_src_f && !f->imply(*jump_src_f)) {
837 return true;
838 }
839 }
840 }
841 }
842 }
843 return false;
844 }
845
846 bool
analyze_with_edges_in(vector<const Fact * > & inputs,CGContext & cg_context) const847 Statement::analyze_with_edges_in(vector<const Fact*>& inputs, CGContext& cg_context) const
848 {
849 FactMgr* fm = get_fact_mgr(&cg_context);
850 size_t i;
851 vector<const CFGEdge*> edges;
852 if (find_jump_label()=="lbl_101")
853 i = 0;
854 // consider output from back edges. we should not merge them if this is the first time
855 if (fm->map_visited[this] && has_edge_in(false, true)) {
856 find_edges_in(edges, false, true);
857 for (i=0; i<edges.size(); i++) {
858 const Statement* src = edges[i]->src;
859 if (fm->map_visited[src]) {
860 FactMgr::merge_jump_facts(inputs, fm->map_facts_out[src]);
861 cg_context.add_effect(fm->map_accum_effect[src]);
862 }
863 }
864 }
865 // always consider output from forward edges
866 if (has_edge_in(false, false)) {
867 find_edges_in(edges, false, false);
868 for (i=0; i<edges.size(); i++) {
869 const Statement* src = edges[i]->src;
870 if (fm->map_visited[src]) {
871 FactMgr::merge_jump_facts(inputs, fm->map_facts_out[src]);
872 cg_context.add_effect(fm->map_accum_effect[src]);
873 }
874 }
875 }
876 return validate_and_update_facts(inputs, cg_context);
877 }
878
879 /****************************************************************************
880 * Entry point to pointer analysis and other DFA analysis for newly
881 * created statement. remember some analysis has already been done during the
882 * statement generation, some analysis work is only possible with a complete
883 * statement, we do it here
884 ****************************************************************************/
885 void
post_creation_analysis(vector<const Fact * > & pre_facts,const Effect & pre_effect,CGContext & cg_context) const886 Statement::post_creation_analysis(vector<const Fact*>& pre_facts, const Effect& pre_effect, CGContext& cg_context) const
887 {
888 FactMgr* fm = get_fact_mgr_for_func(func);
889 if (eType == eIfElse) {
890 ((const StatementIf*)this)->combine_branch_facts(pre_facts);
891 } else {
892 fm->makeup_new_var_facts(pre_facts, fm->global_facts);
893 }
894
895 // save the effect for this statement if this is a simple statement
896 // for compound statements, it's effect is saved in make_random
897 if (!is_compound(eType)) {
898 fm->map_stm_effect[this] = cg_context.get_effect_stm();
899 }
900
901 bool special_handled = false;
902 // special handling for non-looping statements in func_1, which we never re-visit to
903 // save run-time
904 if (cg_context.get_current_func()->name == "func_1" && !(cg_context.flags & IN_LOOP) ) {
905 if (has_uncertain_call_recursive()) {
906 FactVec outputs = pre_facts;
907 cg_context.reset_effect_accum(pre_effect);
908 //if (stm_id == 573)
909 /*if (this->eType == eAssign) {
910 ((const StatementAssign*)this)->get_rhs()->indented_output(cout, 0);
911 }
912 cout << endl;
913 Output(cout, fm);*/
914 //}
915 if (!validate_and_update_facts(outputs, cg_context)) {
916 assert(0);
917 }
918 fm->global_facts = outputs;
919 special_handled = true;
920 }
921 }
922
923 if (!special_handled) {
924 // for if...else..., we don't want to walk through the true branch and false branch again
925 // compute the output with consideration of return statement(s) in both branches
926 if (eType == eAssign) {
927 const StatementAssign* sa = (const StatementAssign*)this;
928 // abstract fact for assignment itself. No analysis on function calls
929 // on RHS since they are already handled during statement generation
930 FactMgr::update_fact_for_assign(sa, fm->global_facts);
931 }
932 else if (eType == eReturn) {
933 const StatementReturn* sr = (const StatementReturn*)this;
934 FactMgr::update_fact_for_return(sr, fm->global_facts);
935 }
936 }
937 fm->remove_rv_facts(fm->global_facts);
938 fm->set_fact_in(this, pre_facts);
939 fm->set_fact_out(this, fm->global_facts);
940 fm->map_accum_effect[this] = *(cg_context.get_effect_accum());
941 fm->map_visited[this] = true;
942 }
943
944 /*
945 * return: 1 means this is a goto target, 0 otherwise
946 */
947 int
pre_output(std::ostream & out,FactMgr *,int indent) const948 Statement::pre_output(std::ostream &out, FactMgr* /* fm */, int indent) const
949 {
950 // output label if this is a goto target
951 vector<const StatementGoto*> gotos;
952 if (find_jump_sources(gotos)) {
953 assert(gotos.size() > 0);
954 out << gotos[0]->label << ":" << endl;
955 return 1;
956 //for (j=0; j<gotos.size(); j++) {
957 // gotos[j]->output_skipped_var_inits(out, indent);
958 //}
959 }
960 // compute checksum and output, for Yang's delta
961 output_hash(out, indent);
962 return 0;
963 }
964
965 void
post_output(std::ostream & out,FactMgr * fm,int indent) const966 Statement::post_output(std::ostream &out, FactMgr* fm, int indent) const
967 {
968 // don't print facts after block because it would mess up "if ... else ..."
969 if (fm && CGOptions::paranoid() && !CGOptions::concise() && eType != eBlock) {
970 fm->output_assertions(out, this, indent, true);
971 }
972 }
973
974 void
output_hash(std::ostream & out,int indent) const975 Statement::output_hash(std::ostream &out, int indent) const
976 {
977 // compute checksum and print out the value
978 if (CGOptions::step_hash_by_stmt()) {
979 OutputMgr::OutputStepHashFuncInvocation(out, indent, stm_id);
980 }
981 }
982
983 ///////////////////////////////////////////////////////////////////////////////
984
985 // Local Variables:
986 // c-basic-offset: 4
987 // tab-width: 4
988 // End:
989
990 // End of file.
991