1 // -*- mode: C++ -*-
2 //
3 // Copyright (c) 2007, 2008, 2010, 2011, 2013, 2015, 2016, 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 #include "Block.h"
47
48 #include <cassert>
49 #include <sstream>
50
51 #include "CGContext.h"
52 #include "CGOptions.h"
53 #include "Function.h"
54 #include "FunctionInvocationUser.h"
55 #include "Statement.h"
56 #include "StatementGoto.h"
57 #include "Variable.h"
58 #include "VariableSelector.h"
59 #include "FactMgr.h"
60 #include "random.h"
61 #include "util.h"
62 #include "DepthSpec.h"
63 #include "Error.h"
64 #include "CFGEdge.h"
65 #include "Expression.h"
66 #include "VectorFilter.h"
67
68 using namespace std;
69
70 ///////////////////////////////////////////////////////////////////////////////
find_block_by_id(int blk_id)71 Block* find_block_by_id(int blk_id)
72 {
73 const vector<Function*>& funcs = get_all_functions();
74 size_t i, j;
75 for (i=0; i<funcs.size(); i++) {
76 Function* f = funcs[i];
77 if (f->is_builtin)
78 continue;
79 for (j=0; j<f->blocks.size(); j++) {
80 if (f->blocks[j]->stm_id == blk_id) {
81 return f->blocks[j];
82 }
83 }
84 }
85 return NULL;
86 }
87
88 /*
89 *
90 */
91 static unsigned int
BlockProbability(Block & block)92 BlockProbability(Block &block)
93 {
94 vector<unsigned int> v;
95 v.push_back(block.block_size() - 1);
96 VectorFilter filter(v, NOT_FILTER_OUT);
97 filter.disable(fDefault);
98 return rnd_upto(block.block_size(), &filter);
99 }
100
101 Block *
make_dummy_block(CGContext & cg_context)102 Block::make_dummy_block(CGContext &cg_context)
103 {
104 Function *curr_func = cg_context.get_current_func();
105 assert(curr_func);
106
107 Block *b = new Block(cg_context.get_current_block(), 0);
108 b->func = curr_func;
109 b->in_array_loop = !(cg_context.iv_bounds.empty());
110 curr_func->blocks.push_back(b);
111 curr_func->stack.push_back(b);
112 FactMgr* fm = get_fact_mgr_for_func(curr_func);
113 fm->set_fact_in(b, fm->global_facts);
114 Effect pre_effect = cg_context.get_accum_effect();
115 b->post_creation_analysis(cg_context, pre_effect);
116 curr_func->stack.pop_back();
117 return b;
118 }
119
120 /*
121 *
122 */
123 Block *
make_random(CGContext & cg_context,bool looping)124 Block::make_random(CGContext &cg_context, bool looping)
125 {
126 //static int bid = 0;
127 DEPTH_GUARD_BY_TYPE_RETURN(dtBlock, NULL);
128
129 Function *curr_func = cg_context.get_current_func();
130 assert(curr_func);
131
132 Block *b = new Block(cg_context.get_current_block(), CGOptions::max_block_size());
133 b->func = curr_func;
134 b->looping = looping;
135 // if there are induction variables, we are in a loop that traverses array(s)
136 b->in_array_loop = !(cg_context.iv_bounds.empty());
137 //b->stm_id = bid++;
138
139 // Push this block onto the variable scope stack.
140 curr_func->stack.push_back(b);
141 curr_func->blocks.push_back(b);
142
143 // record global facts at this moment so that subsequent statement
144 // inside the block doesn't ruin it
145 FactMgr* fm = get_fact_mgr_for_func(curr_func);
146 fm->set_fact_in(b, fm->global_facts);
147 Effect pre_effect = cg_context.get_accum_effect();
148
149 unsigned int max = BlockProbability(*b);
150 if (Error::get_error() != SUCCESS) {
151 curr_func->stack.pop_back();
152 delete b;
153 return NULL;
154 }
155 unsigned int i;
156 if (b->stm_id == 1)
157 BREAK_NOP; // for debugging
158 for (i = 0; i <= max; ++i) {
159 Statement *s = Statement::make_random(cg_context);
160 // In the exhaustive mode, Statement::make_random could return NULL;
161 if (!s)
162 break;
163 b->stms.push_back(s);
164 if (s->must_return()) {
165 break;
166 }
167 }
168
169 if (Error::get_error() != SUCCESS) {
170 curr_func->stack.pop_back();
171 delete b;
172 return NULL;
173 }
174
175 // append nested loop if some must-read/write variables hasn't been accessed
176 if (b->need_nested_loop(cg_context) && cg_context.blk_depth < CGOptions::max_blk_depth()) {
177 b->append_nested_loop(cg_context);
178 }
179
180 // perform DFA analysis after creation
181 b->post_creation_analysis(cg_context, pre_effect);
182
183 if (Error::get_error() != SUCCESS) {
184 curr_func->stack.pop_back();
185 delete b;
186 return NULL;
187 }
188
189 curr_func->stack.pop_back();
190 if (Error::get_error() != SUCCESS) {
191 //curr_func->stack.pop_back();
192 delete b;
193 return NULL;
194 }
195
196 // ISSUE: in the exhaustive mode, do we need a return statement here
197 // if the last statement is not?
198 Error::set_error(SUCCESS);
199 return b;
200 }
201
202 /*
203 *
204 */
Block(Block * b,int block_size)205 Block::Block(Block* b, int block_size)
206 : Statement(eBlock, b),
207 need_revisit(false),
208 depth_protect(false),
209 block_size_(block_size)
210 {
211
212 }
213
214 #if 0
215 /*
216 * ISSUE:I guess we don't need it.
217 */
218 Block::Block(const Block &b)
219 : Statement(eBlock),
220 stms(b.stms),
221 local_vars(b.local_vars),
222 depth_protect(b.depth_protect)
223 {
224 // Nothing else to do.
225 }
226 #endif
227
228 /*
229 *
230 */
~Block(void)231 Block::~Block(void)
232 {
233 vector<Statement *>::iterator i;
234 for(i = stms.begin(); i != stms.end(); ++i) {
235 delete (*i);
236 }
237 stms.clear();
238
239 vector<Statement *>::iterator j;
240 for(j = deleted_stms.begin(); j != deleted_stms.end(); ++j) {
241 delete (*j);
242 }
243 deleted_stms.clear();
244
245 local_vars.clear();
246 macro_tmp_vars.clear();
247 }
248
249
250 std::string
create_new_tmp_var(enum eSimpleType type) const251 Block::create_new_tmp_var(enum eSimpleType type) const
252 {
253 string var_name = gensym("t_");
254 macro_tmp_vars[var_name] = type;
255 return var_name;
256 }
257
258 void
OutputTmpVariableList(std::ostream & out,int indent) const259 Block::OutputTmpVariableList(std::ostream &out, int indent) const
260 {
261 std::map<string, enum eSimpleType>::const_iterator i;
262 for (i = macro_tmp_vars.begin(); i != macro_tmp_vars.end(); ++i) {
263 std::string name = (*i).first;
264 enum eSimpleType type = (*i).second;
265 output_tab(out, indent);
266 Type::get_simple_type(type).Output(out);
267 out << " " << name << " = 0;" << std::endl;
268 }
269 }
270
271 /*
272 *
273 */
274 static void
OutputStatementList(const vector<Statement * > & stms,std::ostream & out,FactMgr * fm,int indent)275 OutputStatementList(const vector<Statement*> &stms, std::ostream &out, FactMgr* fm, int indent)
276 {
277 size_t i;
278 for (i=0; i<stms.size(); i++) {
279 const Statement* stm = stms[i];
280 stm->pre_output(out, fm, indent);
281 stm->Output(out, fm, indent);
282 stm->post_output(out, fm, indent);
283 }
284 }
285
286 /*
287 *
288 */
289 void
Output(std::ostream & out,FactMgr * fm,int indent) const290 Block::Output(std::ostream &out, FactMgr* fm, int indent) const
291 {
292 output_tab(out, indent);
293 out << "{ ";
294 std::ostringstream ss;
295 ss << "block id: " << stm_id;
296 output_comment_line(out, ss.str());
297
298 if (CGOptions::depth_protect()) {
299 out << "DEPTH++;" << endl;
300 }
301
302 indent++;
303 if (CGOptions::math_notmp())
304 OutputTmpVariableList(out, indent);
305
306 OutputVariableList(local_vars, out, indent);
307 OutputStatementList(stms, out, fm, indent);
308
309 if (CGOptions::depth_protect()) {
310 out << "DEPTH--;" << endl;
311 }
312 indent--;
313
314 output_tab(out, indent);
315 out << "}";
316 outputln(out);
317 }
318
319 /* find the last effective statement for this block, note
320 * a return statement terminates the block before reaching the
321 * the last statement
322 */
323 const Statement*
get_last_stm(void) const324 Block::get_last_stm(void) const
325 {
326 const Statement* s = 0;
327 for (size_t i=0; i<stms.size(); i++) {
328 s = stms[i];
329 if (s->eType == eReturn) {
330 break;
331 }
332 }
333 return s;
334 }
335
336 /*
337 * return a random parent block (including itself) or the global block (if 0 is returned)
338 */
339 Block*
random_parent_block(void)340 Block::random_parent_block(void)
341 {
342 vector<Block*> blks;
343 if (CGOptions::global_variables()) {
344 blks.push_back(NULL);
345 }
346 Block* tmp = this;
347 while (tmp) {
348 blks.push_back(tmp);
349 tmp = tmp->parent;
350 }
351 int index = rnd_upto(blks.size());
352 ERROR_GUARD(NULL);
353 return blks[index];
354 }
355
356 /*
357 * return true if there is no way out of this block other than function return
358 */
359 bool
must_return(void) const360 Block::must_return(void) const
361 {
362 if (stms.size() > 0 && break_stms.size() == 0 && get_last_stm()->must_return()) {
363 vector<const CFGEdge*> edges;
364 if (find_edges_in(edges, false, true)) {
365 // if there is a statement goes back to block (most likely "continue")
366 // then this block has a chance to escape the return statement at the end
367 for (size_t i=0; i<edges.size(); i++) {
368 if (edges[i]->src != this) {
369 return false;
370 }
371 }
372 }
373 return true;
374 }
375 return false;
376 }
377
378 /*
379 * return true if there is no way out of this block other than jump
380 */
381 bool
must_jump(void) const382 Block::must_jump(void) const
383 {
384 if (stms.size() > 0 && break_stms.size() == 0 && get_last_stm()->must_jump()) {
385 return true;
386 }
387 return false;
388 }
389
390 bool
must_break_or_return(void) const391 Block::must_break_or_return(void) const
392 {
393 if (stms.size() > 0 && get_last_stm()->must_return()) {
394 vector<const CFGEdge*> edges;
395 if (find_edges_in(edges, false, true)) {
396 // if there is a statement goes back to block (most likely "continue")
397 // then this block has a chance to escape the return statement at the end
398 for (size_t i=0; i<edges.size(); i++) {
399 if (edges[i]->src != this) {
400 return false;
401 }
402 }
403 }
404 return true;
405 }
406 return false;
407 }
408
409 /*
410 * check if there is a control flow edge from the tail to the head of the block
411 */
412 bool
from_tail_to_head(void) const413 Block::from_tail_to_head(void) const
414 {
415 if (looping && stms.size() > 0) {
416 const Statement* s = get_last_stm();
417 //if (s->is_ctrl_stmt() || s->must_return()) {
418 if (s->must_jump()) {
419 return false;
420 }
421 return true;
422 }
423 return false;
424 }
425
426 Statement*
append_return_stmt(CGContext & cg_context)427 Block::append_return_stmt(CGContext& cg_context)
428 {
429 FactMgr* fm = get_fact_mgr_for_func(func);
430 FactVec pre_facts = fm->global_facts;
431 cg_context.get_effect_stm().clear();
432 Statement* sr = Statement::make_random(cg_context, eReturn);
433 ERROR_GUARD(NULL);
434 stms.push_back(sr);
435 fm->makeup_new_var_facts(pre_facts, fm->global_facts);
436 bool visited = sr->visit_facts(fm->global_facts, cg_context);
437 assert(visited);
438
439 fm->set_fact_in(sr, pre_facts);
440 fm->set_fact_out(sr, fm->global_facts);
441 fm->map_accum_effect[sr] = *(cg_context.get_effect_accum());
442 fm->map_visited[sr] = true;
443 //sr->post_creation_analysis(pre_facts, cg_context);
444 fm->map_accum_effect[this] = *(cg_context.get_effect_accum());
445 fm->map_stm_effect[this].add_effect(fm->map_stm_effect[sr]);
446 return sr;
447 }
448
449 bool
need_nested_loop(const CGContext & cg_context)450 Block::need_nested_loop(const CGContext& cg_context)
451 {
452 size_t i;
453 const Statement* s = get_last_stm();
454 if (looping && (s == NULL || !s->must_jump()) && cg_context.rw_directive) {
455 RWDirective* rwd = cg_context.rw_directive;
456 for (i=0; i<rwd->must_read_vars.size(); i++) {
457 size_t dimen = rwd->must_read_vars[i]->get_dimension();
458 if (dimen > cg_context.iv_bounds.size()) {
459 return true;
460 } else if (dimen == cg_context.iv_bounds.size() && rnd_flipcoin(10)) {
461 return true;
462 }
463 }
464 for (i=0; i<rwd->must_write_vars.size(); i++) {
465 size_t dimen = rwd->must_write_vars[i]->get_dimension();
466 if (dimen > cg_context.iv_bounds.size()) {
467 return true;
468 } else if (dimen == cg_context.iv_bounds.size() && rnd_flipcoin(10)) {
469 return true;
470 }
471 }
472 }
473 return false;
474 }
475
476 Statement*
append_nested_loop(CGContext & cg_context)477 Block::append_nested_loop(CGContext& cg_context)
478 {
479 FactMgr* fm = get_fact_mgr_for_func(func);
480 FactVec pre_facts = fm->global_facts;
481 cg_context.get_effect_stm().clear();
482
483 Statement* sf = Statement::make_random(cg_context, eFor);
484 ERROR_GUARD(NULL);
485 stms.push_back(sf);
486 fm->makeup_new_var_facts(pre_facts, fm->global_facts);
487 //assert(sf->visit_facts(fm->global_facts, cg_context));
488
489 fm->set_fact_in(sf, pre_facts);
490 fm->set_fact_out(sf, fm->global_facts);
491 fm->map_accum_effect[sf] = *(cg_context.get_effect_accum());
492 fm->map_visited[sf] = true;
493 //sf->post_creation_analysis(pre_facts, cg_context);
494 fm->map_accum_effect[this] = *(cg_context.get_effect_accum());
495 fm->map_stm_effect[this].add_effect(fm->map_stm_effect[sf]);
496 return sf;
497 }
498
499 /* return true is var is local variable of this block or parent block,
500 * or var is parameter of function
501 */
502 bool
is_var_on_stack(const Variable * var) const503 Block::is_var_on_stack(const Variable* var) const
504 {
505 size_t i;
506 for (i=0; i<func->param.size(); i++) {
507 if (func->param[i]->match(var)) {
508 return true;
509 }
510 }
511 const Block* b = this;
512 while (b) {
513 if (find_variable_in_set(b->local_vars, var) != -1) {
514 return true;
515 }
516 b = b->parent;
517 }
518 return false;
519 }
520
521 std::vector<const ExpressionVariable*>
get_dereferenced_ptrs(void) const522 Block::get_dereferenced_ptrs(void) const
523 {
524 // return a empty vector by default
525 std::vector<const ExpressionVariable*> empty;
526 return empty;
527 }
528
529 bool
visit_facts(vector<const Fact * > & inputs,CGContext & cg_context) const530 Block::visit_facts(vector<const Fact*>& inputs, CGContext& cg_context) const
531 {
532 int dummy;
533 FactMgr* fm = get_fact_mgr(&cg_context);
534 vector<const Fact*> dummy_facts;
535 Effect pre_effect = cg_context.get_accum_effect();
536 if (!find_fixed_point(inputs, dummy_facts, cg_context, dummy, false)) {
537 cg_context.reset_effect_accum(pre_effect);
538 return false;
539 }
540 inputs = fm->map_facts_out[this];
541 fm->map_visited[this] = true;
542 return true;
543 }
544
545 /*
546 * return true if there are back edges leading to statement
547 * inside this block (but not in sub-blocks)
548 */
549 bool
contains_back_edge(void) const550 Block::contains_back_edge(void) const
551 {
552 if (func != 0) {
553 FactMgr* fm = get_fact_mgr_for_func(func);
554 size_t i;
555 for (i=0; i<fm->cfg_edges.size(); i++) {
556 const CFGEdge* edge = fm->cfg_edges[i];
557 if (edge->back_link && edge->dest->parent == this) {
558 return true;
559 }
560 }
561 }
562 return false;
563 }
564
565
566 /**************************************************************************************************
567 * DFA analysis for a block:
568 *
569 * we must considers all kinds of blocks: block for for-loops; block for if-true and if-false; block for
570 * function body; block that loops; block has jump destination insdie; block being a jump destination itself
571 * (in the case of "continue" in for-loops). All of them must be taken care in this function.
572 *
573 * params:
574 * inputs: the inputs env before entering block
575 * cg_context: code generation context
576 * fail_index: records which statement in this block caused analyzer to fail
577 * visit_one: when is true, the statements in this block must be visited at least once
578 ****************************************************************************************************/
579 bool
find_fixed_point(vector<const Fact * > inputs,vector<const Fact * > & post_facts,CGContext & cg_context,int & fail_index,bool visit_once) const580 Block::find_fixed_point(vector<const Fact*> inputs, vector<const Fact*>& post_facts, CGContext& cg_context, int& fail_index, bool visit_once) const
581 {
582 FactMgr* fm = get_fact_mgr(&cg_context);
583 // include outputs from all back edges leading to this block
584 size_t i;
585 static int g = 0;
586 vector<const CFGEdge*> edges;
587 int cnt = 0;
588 do {
589 // if we have never visited the block, force the visitor to go through all statements at least once
590 if (fm->map_visited[this]) {
591 if (cnt++ > 7) {
592 // takes too many iterations to reach a fixed point, must be something wrong
593 assert(0);
594 }
595 find_edges_in(edges, false, true);
596 for (i=0; i<edges.size(); i++) {
597 const Statement* src = edges[i]->src;
598 //assert(fm->map_visited[src]);
599 merge_facts(inputs, fm->map_facts_out[src]);
600 }
601 }
602 if (!visit_once) {
603 int shortcut = shortcut_analysis(inputs, cg_context);
604 if (shortcut == 0) return true;
605 }
606 //if (shortcut == 1) return false;
607
608 FactVec outputs = inputs;
609 // add facts for locals
610 for (i=0; i<local_vars.size(); i++) {
611 const Variable* v = local_vars[i];
612 FactMgr::add_new_var_fact(v, outputs);
613 }
614
615 // revisit statements with new inputs
616 for (i=0; i<stms.size(); i++) {
617 int h = g++;
618 if (h == 2585)
619 BREAK_NOP; // for debugging
620 if (!stms[i]->analyze_with_edges_in(outputs, cg_context)) {
621 fail_index = i;
622 return false;
623 }
624 }
625 fm->set_fact_in(this, inputs);
626 post_facts = outputs;
627 FactMgr::update_facts_for_oos_vars(local_vars, outputs);
628 fm->set_fact_out(this, outputs);
629 fm->map_visited[this] = true;
630 // compute accumulated effect
631 set_accumulated_effect(cg_context);
632 visit_once = false;
633 } while (true);
634 return true;
635 }
636
637 void
set_accumulated_effect(CGContext & cg_context) const638 Block::set_accumulated_effect(CGContext& cg_context) const
639 {
640 Effect eff;
641 FactMgr* fm = get_fact_mgr(&cg_context);
642 for (size_t i=0; i<stms.size(); i++) {
643 Statement* s = stms[i];
644 eff.add_effect(fm->map_stm_effect[s]);
645 }
646 //cg_context.get_effect_stm() = eff;
647 fm->map_stm_effect[this] = eff;
648 }
649
650 /*
651 * remove a statement from this block. this may trigger other events: deleting it from
652 * break_stms, deleting CFG edges linked to it, etc
653 */
654 size_t
remove_stmt(const Statement * s)655 Block::remove_stmt(const Statement* s)
656 {
657 int i, len, cnt;
658 cnt = 0;
659 assert(func);
660 FactMgr* fm = get_fact_mgr_for_func(func);
661 vector<const Statement*> cfg_stms;
662 vector<int> types;
663 types.push_back(eContinue);
664 types.push_back(eBreak);
665 types.push_back(eGoto);
666 //if (func->name == "func_109")
667 // s->Output(cout, fm);
668 if (s->find_typed_stmts(cfg_stms, types)) {
669 // remove from the break_stms list if it is or contains a break
670 Block* b;
671 for (b = this; b && !b->looping; b = b->parent) {
672 /* Empty. */
673 }
674 if (b != 0) {
675 len = b->break_stms.size();
676 for (i=0; i<len; i++) {
677 if (find_stm_in_set(cfg_stms, b->break_stms[i]) >= 0) {
678 b->break_stms.erase(b->break_stms.begin() + i);
679 i--;
680 len--;
681 }
682 }
683 }
684 // remove any CFG edges that has s (or flow-control statements inside s) as src
685 len = fm->cfg_edges.size();
686 for (i=0; i<len; i++) {
687 const CFGEdge* edge = fm->cfg_edges[i];
688 if (find_stm_in_set(cfg_stms, edge->src) >= 0) {
689 fm->cfg_edges.erase(fm->cfg_edges.begin() + i);
690 delete edge;
691 i--;
692 len--;
693 }
694 }
695 }
696
697 // remove any CFG edges that has s (or statements inside s) as dest
698 len = fm->cfg_edges.size();
699 for (i=0; i<len; i++) {
700 const CFGEdge* edge = fm->cfg_edges[i];
701 const Statement* src = edge->src;
702 if (s->contains_stmt(edge->dest)) {
703 fm->cfg_edges.erase(fm->cfg_edges.begin() + i);
704 delete edge;
705 i--;
706 len--;
707 // delete the source statement (most likely goto) as well
708 if (src->eType == eGoto) {
709 int deleted = src->parent->remove_stmt(src);
710 if (src->parent == this) {
711 cnt += deleted;
712 }
713 if ((int)fm->cfg_edges.size() != len) {
714 // re-iterate all edges from the beginning
715 i = -1;
716 len = fm->cfg_edges.size();
717 }
718 }
719 }
720 }
721
722 // delete all the blocks inside s
723 len = func->blocks.size();
724 for (i=0; i<len; i++) {
725 Block* b = func->blocks[i];
726 if (s->contains_stmt(b)) {
727 func->blocks.erase(func->blocks.begin() + i);
728 i--;
729 len--;
730 }
731 }
732 // delete the statment itself
733 for (i=0; i<(int)stms.size(); i++) {
734 if (stms[i] == s) {
735 deleted_stms.push_back(stms[i]);
736 stms.erase(stms.begin() + i);
737 cnt++;
738 break;
739 }
740 }
741 return cnt;
742 }
743
744 /**********************************************************************
745 * once generated the loop body, verify whether some statement caused
746 * the analyzer to fail during the 2nd iteration of the loop body (in
747 * most case, a null/dead pointer dereference would do it), if so, delete
748 * the statement in which analyzer fails and all subsequent statemets
749 *
750 * also performs effect analysis
751 *********************************************************************/
752 void
post_creation_analysis(CGContext & cg_context,const Effect & pre_effect)753 Block::post_creation_analysis(CGContext& cg_context, const Effect& pre_effect)
754 {
755 int index;
756 FactMgr* fm = get_fact_mgr(&cg_context);
757 fm->map_visited[this] = true;
758 // compute accumulated effect
759 set_accumulated_effect(cg_context);
760 //fm->print_facts(fm->global_facts);
761 vector<const Fact*> post_facts = fm->global_facts;
762 FactMgr::update_facts_for_oos_vars(local_vars, fm->global_facts);
763 fm->remove_rv_facts(fm->global_facts);
764 fm->set_fact_out(this, fm->global_facts);
765
766 // find out if fixed-point-searching is required
767 bool is_loop_body = !must_break_or_return() && looping;
768 bool self_back_edge = false;
769 if (is_loop_body || need_revisit || has_edge_in(false, true)) {
770 if (is_loop_body && from_tail_to_head()) {
771 self_back_edge = true;
772 fm->create_cfg_edge(this, this, false, true);
773 }
774 vector<const Fact*> facts_copy = fm->map_facts_in[this];
775 // reset the accumulative effect
776 cg_context.reset_effect_accum(pre_effect);
777 while (!find_fixed_point(facts_copy, post_facts, cg_context, index, need_revisit)) {
778 size_t i, len;
779 len = stms.size();
780 for (i=index; i<len; i++) {
781 remove_stmt(stms[i]);
782 i = index-1;
783 len = stms.size();
784 }
785 // if we delete some statements, next visit must go through statements (no shortcut)
786 need_revisit = true;
787 // clean up in/out map from previous analysis that might include facts caused by deleted statements
788 fm->reset_stm_fact_maps(this);
789 // sometimes a loop would emerge after we delete the "return" statement in body
790 if (!self_back_edge && from_tail_to_head()) {
791 self_back_edge = true;
792 fm->create_cfg_edge(this, this, false, true);
793 }
794 // reset incoming effects
795 cg_context.reset_effect_accum(pre_effect);
796 }
797 fm->global_facts = fm->map_facts_out[this];
798 }
799 // make sure we add back return statement for blocks that require it and had such statement deleted
800 // only do this for top-level block of a function which requires a return statement
801 if (parent == 0 && func->need_return_stmt() && !must_return()) {
802 fm->global_facts = post_facts;
803 Statement* sr = append_return_stmt(cg_context);
804 fm->set_fact_out(this, fm->map_facts_out[sr]);
805 }
806 }
807
808 ///////////////////////////////////////////////////////////////////////////////
809
810 // Local Variables:
811 // c-basic-offset: 4
812 // tab-width: 4
813 // End:
814
815 // End of file.
816