1 /*
2 flow.c
3
4 Flow graph analysis
5
6 Copyright (C) 2012 Bill Currie <bill@taniwha.org>
7
8 Author: Bill Currie <bill@taniwha.org>
9 Date: 2012/10/30
10
11 This program is free software; you can redistribute it and/or
12 modify it under the terms of the GNU General Public License
13 as published by the Free Software Foundation; either version 2
14 of the License, or (at your option) any later version.
15
16 This program is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
19
20 See the GNU General Public License for more details.
21
22 You should have received a copy of the GNU General Public License
23 along with this program; if not, write to:
24
25 Free Software Foundation, Inc.
26 59 Temple Place - Suite 330
27 Boston, MA 02111-1307, USA
28
29 */
30 #ifdef HAVE_CONFIG_H
31 # include "config.h"
32 #endif
33
34 #ifdef HAVE_STRING_H
35 # include <string.h>
36 #endif
37 #ifdef HAVE_STRINGS_H
38 # include <strings.h>
39 #endif
40 #include <stdlib.h>
41
42 #include "QF/alloc.h"
43 #include "QF/dstring.h"
44 #include "QF/set.h"
45 #include "QF/va.h"
46
47 #include "dags.h"
48 #include "def.h"
49 #include "defspace.h"
50 #include "diagnostic.h"
51 #include "dot.h"
52 #include "flow.h"
53 #include "function.h"
54 #include "options.h"
55 #include "qfcc.h"
56 #include "statements.h"
57 #include "symtab.h"
58 #include "type.h"
59
60 static flowvar_t *free_vars;
61 static flowloop_t *free_loops;
62 static flownode_t *free_nodes;
63 static flowgraph_t *free_graphs;
64
65 static struct {
66 const char *name;
67 operand_t op;
68 } flow_params[] = {
69 {".return", {0, op_def}},
70 {".param_0", {0, op_def}},
71 {".param_1", {0, op_def}},
72 {".param_2", {0, op_def}},
73 {".param_3", {0, op_def}},
74 {".param_4", {0, op_def}},
75 {".param_5", {0, op_def}},
76 {".param_6", {0, op_def}},
77 {".param_7", {0, op_def}},
78 };
79 static const int num_flow_params = sizeof(flow_params)/sizeof(flow_params[0]);
80
81 static flowvar_t *
new_flowvar(void)82 new_flowvar (void)
83 {
84 flowvar_t *var;
85 ALLOC (256, flowvar_t, vars, var);
86 var->use = set_new ();
87 var->define = set_new ();
88 return var;
89 }
90
91 static flowloop_t *
new_loop(void)92 new_loop (void)
93 {
94 flowloop_t *loop;
95 ALLOC (256, flowloop_t, loops, loop);
96 loop->nodes = set_new ();
97 return loop;
98 }
99
100 static void
delete_loop(flowloop_t * loop)101 delete_loop (flowloop_t *loop)
102 {
103 set_delete (loop->nodes);
104 FREE (loops, loop);
105 }
106
107 static flownode_t *
new_node(void)108 new_node (void)
109 {
110 flownode_t *node;
111 ALLOC (256, flownode_t, nodes, node);
112 return node;
113 }
114
115 static void
delete_node(flownode_t * node)116 delete_node (flownode_t *node)
117 {
118 if (node->predecessors)
119 set_delete (node->predecessors);
120 if (node->successors)
121 set_delete (node->successors);
122 if (node->edges)
123 set_delete (node->edges);
124 if (node->dom)
125 set_delete (node->dom);
126 FREE (nodes, node);
127 }
128
129 static flowgraph_t *
new_graph(void)130 new_graph (void)
131 {
132 flowgraph_t *graph;
133 ALLOC (256, flowgraph_t, graphs, graph);
134 return graph;
135 }
136
137 static void __attribute__((unused))
delete_graph(flowgraph_t * graph)138 delete_graph (flowgraph_t *graph)
139 {
140 int i;
141
142 if (graph->nodes) {
143 for (i = 0; i < graph->num_nodes; i++)
144 delete_node (graph->nodes[i]);
145 free (graph->nodes);
146 }
147 if (graph->edges)
148 free (graph->edges);
149 if (graph->dfst)
150 set_delete (graph->dfst);
151 if (graph->dfo)
152 free (graph->dfo);
153 FREE (graphs, graph);
154 }
155
156 static def_t *
flowvar_get_def(flowvar_t * var)157 flowvar_get_def (flowvar_t *var)
158 {
159 operand_t *op = var->op;
160
161 switch (op->op_type) {
162 case op_def:
163 return op->o.def;
164 case op_value:
165 case op_label:
166 return 0;
167 case op_temp:
168 return op->o.tempop.def;
169 case op_alias:
170 internal_error (0, "unexpected alias operand");
171 }
172 internal_error (0, "oops, blue pill");
173 return 0;
174 }
175
176 static int
flowvar_is_global(flowvar_t * var)177 flowvar_is_global (flowvar_t *var)
178 {
179 def_t *def;
180
181 if (var->op->op_type != op_def)
182 return 0;
183 def = var->op->o.def;
184 if (def->alias)
185 def = def->alias;
186 if (def->local)
187 return 0;
188 return 1;
189 }
190
191 static int
flowvar_is_param(flowvar_t * var)192 flowvar_is_param (flowvar_t *var)
193 {
194 def_t *def;
195
196 if (var->op->op_type != op_def)
197 return 0;
198 def = var->op->o.def;
199 if (def->alias)
200 def = def->alias;
201 if (!def->local)
202 return 0;
203 if (!def->param)
204 return 0;
205 return 1;
206 }
207 #if 0
208 static int
209 flowvar_is_initialized (flowvar_t *var)
210 {
211 def_t *def;
212
213 if (var->op->op_type != op_def)
214 return 0;
215 def = var->op->o.def;
216 return def->initialized;
217 }
218 #endif
219 flowvar_t *
flow_get_var(operand_t * op)220 flow_get_var (operand_t *op)
221 {
222 if (!op)
223 return 0;
224
225 if (op->op_type == op_temp) {
226 if (!op->o.tempop.flowvar)
227 op->o.tempop.flowvar = new_flowvar ();
228 return op->o.tempop.flowvar;
229 }
230 if (op->op_type == op_def) {
231 if (!op->o.def->flowvar)
232 op->o.def->flowvar = new_flowvar ();
233 return op->o.def->flowvar;
234 }
235 return 0;
236 }
237
238 static int
count_operand(operand_t * op)239 count_operand (operand_t *op)
240 {
241 flowvar_t *var;
242
243 if (!op)
244 return 0;
245 if (op->op_type == op_label)
246 return 0;
247
248 var = flow_get_var (op);
249 // flowvars are initialized with number == 0, and any global flowvar
250 // used by a function will always have a number >= 0 after flow analysis,
251 // and local flowvars will always be 0 before flow analysis, so use -1
252 // to indicate the variable has been counted.
253 //
254 // Also, since this is the beginning of flow analysis for this function,
255 // ensure the define/use sets for global vars are empty. However, as
256 // checking if a var is global is too much trouble, just clear them all.
257 if (var && var->number != -1) {
258 set_empty (var->use);
259 set_empty (var->define);
260 var->number = -1;
261 return 1;
262 }
263 return 0;
264 }
265
266 static void
add_operand(function_t * func,operand_t * op)267 add_operand (function_t *func, operand_t *op)
268 {
269 flowvar_t *var;
270
271 if (!op)
272 return;
273 if (op->op_type == op_label)
274 return;
275
276 var = flow_get_var (op);
277 // If the flowvar number is still -1, then the flowvar has not yet been
278 // added to the list of variables referenced by the function.
279 if (var && var->number == -1) {
280 var->number = func->num_vars++;
281 var->op = op;
282 func->vars[var->number] = var;
283 }
284 }
285
286 static symbol_t *
param_symbol(const char * name)287 param_symbol (const char *name)
288 {
289 symbol_t *sym;
290 sym = make_symbol (name, &type_param, pr.symtab->space, sc_extern);
291 if (!sym->table)
292 symtab_addsymbol (pr.symtab, sym);
293 return sym;
294 }
295
296 static void
flow_build_statements(function_t * func)297 flow_build_statements (function_t *func)
298 {
299 sblock_t *sblock;
300 statement_t *s;
301 int num_statements = 0;
302
303 for (sblock = func->sblock; sblock; sblock = sblock->next) {
304 for (s = sblock->statements; s; s = s->next)
305 s->number = num_statements++;
306 }
307 if (!num_statements)
308 return;
309
310 func->statements = malloc (num_statements * sizeof (statement_t *));
311 func->num_statements = num_statements;
312 for (sblock = func->sblock; sblock; sblock = sblock->next) {
313 for (s = sblock->statements; s; s = s->next)
314 func->statements[s->number] = s;
315 }
316 }
317
318 static void
flow_build_vars(function_t * func)319 flow_build_vars (function_t *func)
320 {
321 statement_t *s;
322 operand_t *operands[4];
323 int num_vars = 0;
324 int i, j;
325 set_t *stuse;
326 set_t *stdef;
327 set_iter_t *var_i;
328 flowvar_t *var;
329
330 // first, count .return and .param_[0-7] as they are always needed
331 for (i = 0; i < num_flow_params; i++) {
332 flow_params[i].op.o.def = param_symbol (flow_params[i].name)->s.def;
333 num_vars += count_operand (&flow_params[i].op);
334 }
335 // then run through the statements in the function looking for accessed
336 // variables
337 for (i = 0; i < func->num_statements; i++) {
338 s = func->statements[i];
339 flow_analyze_statement (s, 0, 0, 0, operands);
340 for (j = 0; j < 4; j++)
341 num_vars += count_operand (operands[j]);
342 }
343 if (!num_vars)
344 return;
345
346 func->vars = malloc (num_vars * sizeof (daglabel_t *));
347
348 stuse = set_new ();
349 stdef = set_new ();
350
351 func->num_vars = 0; // incremented by add_operand
352 // first, add .return and .param_[0-7] as they are always needed
353 for (i = 0; i < num_flow_params; i++)
354 add_operand (func, &flow_params[i].op);
355 // then run through the statements in the function adding accessed
356 // variables
357 for (i = 0; i < func->num_statements; i++) {
358 s = func->statements[i];
359 flow_analyze_statement (s, 0, 0, 0, operands);
360 for (j = 0; j < 4; j++)
361 add_operand (func, operands[j]);
362
363 flow_analyze_statement (s, stuse, stdef, 0, 0);
364 for (var_i = set_first (stdef); var_i; var_i = set_next (var_i)) {
365 var = func->vars[var_i->element];
366 set_add (var->define, i);
367 }
368 for (var_i = set_first (stuse); var_i; var_i = set_next (var_i)) {
369 var = func->vars[var_i->element];
370 set_add (var->use, i);
371 }
372 }
373 func->global_vars = set_new ();
374 // mark all global vars (except .return and .param_N)
375 for (i = num_flow_params; i < func->num_vars; i++) {
376 if (flowvar_is_global (func->vars[i]))
377 set_add (func->global_vars, i);
378 }
379 // create dummy defs for local vars
380 for (i = 0; i < func->num_vars; i++) {
381 int offset, size;
382 int j;
383
384 var = func->vars[i];
385 if (flowvar_is_global (var) || flowvar_is_param (var))
386 continue;
387 if (var->op->op_type == op_temp) {
388 j = func->symtab->space->size + var->number;
389 set_add (var->define, func->num_statements + j);
390 } else {
391 offset = def_offset (var->op->o.def);
392 size = def_size (var->op->o.def);
393 for (j = offset; j < offset + size; j++)
394 set_add (var->define, func->num_statements + j);
395 }
396 }
397
398 set_delete (stuse);
399 set_delete (stdef);
400 }
401
402 static int
flow_kill_aliases_visit(def_t * def,void * _kill)403 flow_kill_aliases_visit (def_t *def, void *_kill)
404 {
405 set_t *kill = (set_t *) _kill;
406 flowvar_t *var;
407 var = def->flowvar;
408 if (var)
409 set_union (kill, var->define);
410 return 0;
411 }
412
413 static void
flow_kill_aliases(set_t * kill,flowvar_t * var,const set_t * uninit)414 flow_kill_aliases (set_t *kill, flowvar_t *var, const set_t *uninit)
415 {
416 operand_t *op;
417 set_t *tmp;
418
419 set_union (kill, var->define);
420 op = var->op;
421 tmp = set_new ();
422 if (op->op_type == op_temp) {
423 if (op->o.tempop.alias) {
424 op = op->o.tempop.alias;
425 var = op->o.tempop.flowvar;
426 if (var)
427 set_union (tmp, var->define);
428 }
429 for (op = op->o.tempop.alias_ops; op; op = op->next) {
430 var = op->o.tempop.flowvar;
431 if (var)
432 set_union (tmp, var->define);
433 }
434 } else if (op->op_type == op_def) {
435 def_visit_all (op->o.def, 1, flow_kill_aliases_visit, tmp);
436 // don't allow aliases to kill definitions in the entry dummy block
437 set_difference (tmp, uninit);
438 }
439 // merge the alias kills with the current def's kills
440 set_union (kill, tmp);
441 }
442
443 static void
flow_reaching_defs(flowgraph_t * graph)444 flow_reaching_defs (flowgraph_t *graph)
445 {
446 int i;
447 int changed;
448 flownode_t *node;
449 statement_t *st;
450 set_t *stdef = set_new ();
451 set_t *stgen = set_new ();
452 set_t *stkill = set_new ();
453 set_t *oldout = set_new ();
454 set_t *gen, *kill, *in, *out, *uninit;
455 set_iter_t *var_i;
456 set_iter_t *pred_i;
457 flowvar_t *var;
458
459 // First, create out for the entry dummy node using fake statement numbers.
460 kill = set_new ();
461 for (i = 0; i < graph->func->num_statements; i++)
462 set_add (kill, i);
463 uninit = set_new ();
464 for (i = 0; i < graph->func->num_vars; i++) {
465 var = graph->func->vars[i];
466 set_union (uninit, var->define);// do not want alias handling here
467 set_difference (uninit, kill); // remove any gens from the function
468 }
469 graph->nodes[graph->num_nodes]->reaching_defs.out = uninit;
470 graph->nodes[graph->num_nodes]->reaching_defs.in = set_new ();
471 graph->nodes[graph->num_nodes]->reaching_defs.gen = set_new ();
472 graph->nodes[graph->num_nodes]->reaching_defs.kill = set_new ();
473
474 // Calculate gen and kill for each block, and initialize in and out
475 for (i = 0; i < graph->num_nodes; i++) {
476 node = graph->nodes[i];
477 gen = set_new ();
478 kill = set_new ();
479 for (st = node->sblock->statements; st; st = st->next) {
480 flow_analyze_statement (st, 0, stdef, 0, 0);
481 set_empty (stgen);
482 set_empty (stkill);
483 for (var_i = set_first (stdef); var_i; var_i = set_next (var_i)) {
484 var = graph->func->vars[var_i->element];
485 flow_kill_aliases (stkill, var, uninit);
486 set_remove (stkill, st->number);
487 set_add (stgen, st->number);
488 }
489
490 set_difference (gen, stkill);
491 set_union (gen, stgen);
492
493 set_difference (kill, stgen);
494 set_union (kill, stkill);
495 }
496 node->reaching_defs.gen = gen;
497 node->reaching_defs.kill = kill;
498 node->reaching_defs.in = set_new ();
499 node->reaching_defs.out = set_new ();
500 }
501
502 changed = 1;
503 while (changed) {
504 changed = 0;
505 // flow down the graph
506 for (i = 0; i < graph->num_nodes; i++) {
507 node = graph->nodes[graph->dfo[i]];
508 in = node->reaching_defs.in;
509 out = node->reaching_defs.out;
510 gen = node->reaching_defs.gen;
511 kill = node->reaching_defs.kill;
512 for (pred_i = set_first (node->predecessors); pred_i;
513 pred_i = set_next (pred_i)) {
514 flownode_t *pred = graph->nodes[pred_i->element];
515 set_union (in, pred->reaching_defs.out);
516 }
517 set_assign (oldout, out);
518 set_assign (out, in);
519 set_difference (out, kill);
520 set_union (out, gen);
521 if (!set_is_equivalent (out, oldout))
522 changed = 1;
523 }
524 }
525 set_delete (oldout);
526 set_delete (stdef);
527 set_delete (stgen);
528 set_delete (stkill);
529 }
530
531 static void
live_set_use(set_t * stuse,set_t * use,set_t * def)532 live_set_use (set_t *stuse, set_t *use, set_t *def)
533 {
534 // the variable is used before it is defined
535 set_difference (stuse, def);
536 set_union (use, stuse);
537 }
538
539 static void
live_set_def(set_t * stdef,set_t * use,set_t * def)540 live_set_def (set_t *stdef, set_t *use, set_t *def)
541 {
542 // the variable is defined before it is used
543 set_difference (stdef, use);
544 set_union (def, stdef);
545 }
546
547 static void
flow_live_vars(flowgraph_t * graph)548 flow_live_vars (flowgraph_t *graph)
549 {
550 int i, j;
551 flownode_t *node;
552 set_t *use;
553 set_t *def;
554 set_t *stuse = set_new ();
555 set_t *stdef = set_new ();
556 set_t *tmp = set_new ();
557 set_iter_t *succ;
558 statement_t *st;
559 int changed = 1;
560
561 // first, calculate use and def for each block, and initialize the in and
562 // out sets.
563 for (i = 0; i < graph->num_nodes; i++) {
564 node = graph->nodes[i];
565 use = set_new ();
566 def = set_new ();
567 for (st = node->sblock->statements; st; st = st->next) {
568 flow_analyze_statement (st, stuse, stdef, 0, 0);
569 live_set_use (stuse, use, def);
570 live_set_def (stdef, use, def);
571 }
572 node->live_vars.use = use;
573 node->live_vars.def = def;
574 node->live_vars.in = set_new ();
575 node->live_vars.out = set_new ();
576 }
577 // create in for the exit dummy block using the global vars used by the
578 // function
579 use = set_new ();
580 set_assign (use, graph->func->global_vars);
581 node = graph->nodes[graph->num_nodes + 1];
582 node->live_vars.in = use;
583 node->live_vars.out = set_new ();
584 node->live_vars.use = set_new ();
585 node->live_vars.def = set_new ();
586
587 while (changed) {
588 changed = 0;
589 // flow UP the graph because live variable analysis uses information
590 // from a node's successors rather than its predecessors.
591 for (j = graph->num_nodes - 1; j >= 0; j--) {
592 node = graph->nodes[graph->dfo[j]];
593 set_empty (tmp);
594 for (succ = set_first (node->successors); succ;
595 succ = set_next (succ))
596 set_union (tmp, graph->nodes[succ->element]->live_vars.in);
597 if (!set_is_equivalent (node->live_vars.out, tmp)) {
598 changed = 1;
599 set_assign (node->live_vars.out, tmp);
600 }
601 set_assign (node->live_vars.in, node->live_vars.out);
602 set_difference (node->live_vars.in, node->live_vars.def);
603 set_union (node->live_vars.in, node->live_vars.use);
604 }
605 }
606 set_delete (stuse);
607 set_delete (stdef);
608 set_delete (tmp);
609 }
610
611 static void
flow_uninit_scan_statements(flownode_t * node,set_t * defs,set_t * uninit)612 flow_uninit_scan_statements (flownode_t *node, set_t *defs, set_t *uninit)
613 {
614 set_t *stuse;
615 set_t *stdef;
616 statement_t *st;
617 set_iter_t *var_i;
618 flowvar_t *var;
619 operand_t *op;
620
621 // defs holds only reaching definitions. make it hold only reaching
622 // uninitialized definitions
623 set_intersection (defs, uninit);
624 stuse = set_new ();
625 stdef = set_new ();
626 for (st = node->sblock->statements; st; st = st->next) {
627 flow_analyze_statement (st, stuse, stdef, 0, 0);
628 for (var_i = set_first (stuse); var_i; var_i = set_next (var_i)) {
629 var = node->graph->func->vars[var_i->element];
630 if (set_is_intersecting (defs, var->define)) {
631 def_t *def = flowvar_get_def (var);
632 if (def) {
633 if (options.warnings.uninited_variable) {
634 warning (st->expr, "%s may be used uninitialized",
635 def->name);
636 }
637 } else {
638 bug (st->expr, "st %d, uninitialized temp %s",
639 st->number, operand_string (var->op));
640 }
641 }
642 // avoid repeat warnings in this node
643 set_difference (defs, var->define);
644 }
645 for (var_i = set_first (stdef); var_i; var_i = set_next (var_i)) {
646 var = node->graph->func->vars[var_i->element];
647 // kill any reaching uninitialized definitions for this variable
648 set_difference (defs, var->define);
649 if (var->op->op_type == op_temp) {
650 op = var->op;
651 if (op->o.tempop.alias) {
652 var = op->o.tempop.alias->o.tempop.flowvar;
653 if (var)
654 set_difference (defs, var->define);
655 }
656 for (op = op->o.tempop.alias_ops; op; op = op->next) {
657 var = op->o.tempop.flowvar;
658 if (var)
659 set_difference (defs, var->define);
660 }
661 }
662 }
663 }
664 set_delete (stuse);
665 set_delete (stdef);
666 }
667
668 static void
flow_uninitialized(flowgraph_t * graph)669 flow_uninitialized (flowgraph_t *graph)
670 {
671 int i;
672 flownode_t *node;
673 flowvar_t *var;
674 set_iter_t *var_i;
675 set_t *defs;
676 set_t *uninitialized;
677
678 uninitialized = set_new ();
679 node = graph->nodes[graph->num_nodes];
680 set_assign (uninitialized, node->reaching_defs.out);
681 defs = set_new ();
682
683 for (i = 0; i < graph->num_nodes; i++) {
684 node = graph->nodes[graph->dfo[i]];
685 set_empty (defs);
686 // collect definitions of all variables "used" in this node. use from
687 // the live vars analysis is perfect for the job
688 for (var_i = set_first (node->live_vars.use); var_i;
689 var_i = set_next (var_i)) {
690 var = graph->func->vars[var_i->element];
691 set_union (defs, var->define);
692 }
693 // interested in only those defintions that actually reach this node
694 set_intersection (defs, node->reaching_defs.in);
695 // if any of the definitions come from the entry dummy block, then
696 // the statements need to be scanned in case an aliasing definition
697 // kills the dummy definition before the usage, and also so the line
698 // number information can be obtained from the statement.
699 if (set_is_intersecting (defs, uninitialized))
700 flow_uninit_scan_statements (node, defs, uninitialized);
701 }
702 set_delete (defs);
703 }
704
705 static void
flow_build_dags(flowgraph_t * graph)706 flow_build_dags (flowgraph_t *graph)
707 {
708 int i;
709 flownode_t *node;
710
711 for (i = 0; i < graph->num_nodes; i++) {
712 node = graph->nodes[i];
713 node->dag = dag_create (node);
714 }
715 if (options.block_dot.dags)
716 dump_dot ("dags", graph, dump_dot_flow_dags);
717 }
718
719 static void
flow_cleanup_dags(flowgraph_t * graph)720 flow_cleanup_dags (flowgraph_t *graph)
721 {
722 int i;
723 flownode_t *node;
724
725 for (i = 0; i < graph->num_nodes; i++) {
726 node = graph->nodes[i];
727 dag_remove_dead_nodes (node->dag);
728 }
729 if (options.block_dot.dags)
730 dump_dot ("cleaned-dags", graph, dump_dot_flow_dags);
731 }
732
733 static sblock_t *
flow_generate(flowgraph_t * graph)734 flow_generate (flowgraph_t *graph)
735 {
736 int i;
737 sblock_t *code = 0;
738 sblock_t **tail = &code;
739
740 for (i = 0; i < graph->num_nodes; i++) {
741 ex_label_t *label;
742 sblock_t *block;
743
744 flownode_t *node = graph->nodes[i];
745 *tail = block = new_sblock ();
746 tail = &(*tail)->next;
747 // first, transfer any labels on the old node to the new
748 while ((label = node->sblock->labels)) {
749 node->sblock->labels = label->next;
750 label->next = block->labels;
751 block->labels = label;
752 label->dest = block;
753 }
754 // generate new statements from the dag;
755 dag_generate (node->dag, block);
756 }
757 if (options.block_dot.post)
758 dump_dot ("post", code, dump_dot_sblock);
759 return code;
760 }
761
762 static void
flow_add_op_var(set_t * set,operand_t * op)763 flow_add_op_var (set_t *set, operand_t *op)
764 {
765 flowvar_t *var;
766
767 if (!set)
768 return;
769 if (!(var = flow_get_var (op)))
770 return;
771 set_add (set, var->number);
772 }
773
774 void
flow_analyze_statement(statement_t * s,set_t * use,set_t * def,set_t * kill,operand_t * operands[4])775 flow_analyze_statement (statement_t *s, set_t *use, set_t *def, set_t *kill,
776 operand_t *operands[4])
777 {
778 int i, start, calln = -1;
779
780 if (use)
781 set_empty (use);
782 if (def)
783 set_empty (def);
784 if (kill)
785 set_empty (kill);
786 if (operands) {
787 for (i = 0; i < 4; i++)
788 operands[i] = 0;
789 }
790
791 switch (s->type) {
792 case st_none:
793 internal_error (s->expr, "not a statement");
794 case st_expr:
795 flow_add_op_var (def, s->opc);
796 flow_add_op_var (use, s->opa);
797 if (s->opb)
798 flow_add_op_var (use, s->opb);
799 if (operands) {
800 operands[0] = s->opc;
801 operands[1] = s->opa;
802 operands[2] = s->opb;
803 }
804 break;
805 case st_assign:
806 flow_add_op_var (def, s->opb);
807 flow_add_op_var (use, s->opa);
808 if (operands) {
809 operands[0] = s->opb;
810 operands[1] = s->opa;
811 }
812 break;
813 case st_ptrassign:
814 case st_move:
815 flow_add_op_var (use, s->opa);
816 flow_add_op_var (use, s->opb);
817 if (!strcmp (s->opcode, "<MOVE>")) {
818 flow_add_op_var (def, s->opc);
819 } else if (!strcmp (s->opcode, "<MOVEP>")) {
820 flow_add_op_var (use, s->opc);
821 if (s->opc->op_type == op_value
822 && s->opc->o.value->type == ev_pointer
823 && s->opc->o.value->v.pointer.def) {
824 operand_t *op;
825 ex_pointer_t *ptr = &s->opc->o.value->v.pointer;
826 op = def_operand (ptr->def, ptr->type);
827 flow_add_op_var (def, op);
828 if (operands)
829 operands[0] = op;
830 else
831 free_operand (op);
832 } else {
833 if (operands)
834 operands[3] = s->opc;
835 }
836 } else {
837 if (s->opc)
838 flow_add_op_var (use, s->opc);
839 }
840 if (kill) {
841 //FIXME set of everything
842 }
843 if (operands) {
844 if (!strcmp (s->opcode, "<MOVE>"))
845 operands[0] = s->opc;
846 operands[1] = s->opa;
847 operands[2] = s->opb;
848 if (strncmp (s->opcode, "<MOVE", 5))
849 operands[3] = s->opc;
850 }
851 break;
852 case st_state:
853 flow_add_op_var (use, s->opa);
854 flow_add_op_var (use, s->opb);
855 if (s->opc)
856 flow_add_op_var (use, s->opc);
857 //FIXME entity members
858 if (operands) {
859 operands[1] = s->opa;
860 operands[2] = s->opb;
861 operands[3] = s->opc;
862 }
863 break;
864 case st_func:
865 if (strcmp (s->opcode, "<RETURN>") == 0
866 || strcmp (s->opcode, "<DONE>") == 0) {
867 flow_add_op_var (use, s->opa);
868 } else if (strcmp (s->opcode, "<RETURN_V>") == 0) {
869 if (use)
870 set_add (use, 0); //FIXME assumes .return location
871 }
872 if (strncmp (s->opcode, "<CALL", 5) == 0) {
873 start = 0;
874 calln = s->opcode[5] - '0';
875 flow_add_op_var (use, s->opa);
876 } else if (strncmp (s->opcode, "<RCALL", 6) == 0) {
877 start = 2;
878 calln = s->opcode[6] - '0';
879 flow_add_op_var (use, s->opa);
880 flow_add_op_var (use, s->opb);
881 if (s->opc)
882 flow_add_op_var (use, s->opc);
883 }
884 if (calln >= 0) {
885 if (use) {
886 for (i = start; i < calln; i++)
887 set_add (use, i + 1);//FIXME assumes .param_N locations
888 }
889 if (kill)
890 set_add (kill, 0); //FIXME assumes .return location
891 }
892 if (operands) {
893 operands[1] = s->opa;
894 operands[2] = s->opb;
895 operands[3] = s->opc;
896 }
897 break;
898 case st_flow:
899 if (strcmp (s->opcode, "<GOTO>") != 0) {
900 flow_add_op_var (use, s->opa);
901 if (strcmp (s->opcode, "<JUMPB>") == 0)
902 flow_add_op_var (use, s->opb);
903 }
904 if (operands) {
905 operands[1] = s->opa;
906 operands[2] = s->opb;
907 }
908 break;
909 }
910 }
911
912 static void
flow_find_successors(flowgraph_t * graph)913 flow_find_successors (flowgraph_t *graph)
914 {
915 int i;
916 flownode_t *node;
917 sblock_t *sb;
918 statement_t *st;
919 sblock_t **target_list, **target;
920
921 // "convert" the basic blocks connections to flow-graph connections
922 for (i = 0; i < graph->num_nodes + 2; i++) {
923 node = graph->nodes[i];
924 set_empty (node->successors);
925 set_empty (node->predecessors);
926 set_empty (node->edges);
927 }
928 graph->num_edges = 0;
929
930 for (i = 0; i < graph->num_nodes; i++) {
931 node = graph->nodes[i];
932 sb = node->sblock;
933 st = 0;
934 if (sb->statements)
935 st = (statement_t *) sb->tail;
936 //NOTE: if st is null (the sblock has no statements), statement_is_*
937 //will return false
938 //FIXME jump/jumpb
939 if (statement_is_goto (st) || statement_is_jumpb (st)) {
940 // sb's next is never followed.
941 target_list = statement_get_targetlist (st);
942 for (target = target_list; *target; target++)
943 set_add (node->successors, (*target)->flownode->id);
944 free (target_list);
945 } else if (statement_is_cond (st)) {
946 // branch: either sb's next or the conditional statment's
947 // target will be followed.
948 set_add (node->successors, sb->next->flownode->id);
949 target_list = statement_get_targetlist (st);
950 for (target = target_list; *target; target++)
951 set_add (node->successors, (*target)->flownode->id);
952 free (target_list);
953 } else if (statement_is_return (st)) {
954 // exit from function (dead end)
955 // however, make the exit dummy block the node's successor
956 set_add (node->successors, graph->num_nodes + 1);
957 } else {
958 // there is no flow-control statement in sb, so sb's next
959 // must be followed
960 if (sb->next) {
961 set_add (node->successors, sb->next->flownode->id);
962 } else {
963 bug (0, "code drops off the end of the function");
964 // this shouldn't happen
965 // however, make the exit dummy block the node's successor
966 set_add (node->successors, graph->num_nodes + 1);
967 }
968 }
969 graph->num_edges += set_size (node->successors);
970 }
971 // set the successor for the entry dummy node to the real entry node
972 node = graph->nodes[graph->num_nodes];
973 set_add (node->successors, 0);
974 graph->num_edges += set_size (node->successors);
975 }
976
977 static void
flow_make_edges(flowgraph_t * graph)978 flow_make_edges (flowgraph_t *graph)
979 {
980 int i, j;
981 flownode_t *node;
982 set_iter_t *succ;
983
984 if (graph->edges);
985 free (graph->edges);
986 graph->edges = malloc (graph->num_edges * sizeof (flowedge_t *));
987 for (j = 0, i = 0; i < graph->num_nodes + 2; i++) {
988 node = graph->nodes[i];
989 for (succ = set_first (node->successors); succ;
990 succ = set_next (succ), j++) {
991 set_add (node->edges, j);
992 graph->edges[j].tail = i;
993 graph->edges[j].head = succ->element;
994 }
995 }
996 }
997
998 static void
flow_find_predecessors(flowgraph_t * graph)999 flow_find_predecessors (flowgraph_t *graph)
1000 {
1001 int i;
1002 flownode_t *node;
1003 set_iter_t *succ;
1004
1005 for (i = 0; i < graph->num_nodes + 2; i++) {
1006 node = graph->nodes[i];
1007 for (succ = set_first (node->successors); succ;
1008 succ = set_next (succ)) {
1009 set_add (graph->nodes[succ->element]->predecessors, i);
1010 }
1011 }
1012 }
1013
1014 static void
flow_find_dominators(flowgraph_t * graph)1015 flow_find_dominators (flowgraph_t *graph)
1016 {
1017 set_t *work;
1018 flownode_t *node;
1019 int i;
1020 set_iter_t *pred;
1021 int changed;
1022
1023 if (!graph->num_nodes)
1024 return;
1025
1026 // First, create a base set for the initial state of the non-initial nodes
1027 work = set_new ();
1028 for (i = 0; i < graph->num_nodes; i++)
1029 set_add (work, i);
1030
1031 set_add (graph->nodes[0]->dom, 0);
1032
1033 // initialize dom for the non-initial nodes
1034 for (i = 1; i < graph->num_nodes; i++) {
1035 set_assign (graph->nodes[i]->dom, work);
1036 }
1037
1038 do {
1039 changed = 0;
1040 for (i = 1; i < graph->num_nodes; i++) {
1041 node = graph->nodes[i];
1042 pred = set_first (node->predecessors);
1043 set_empty (work);
1044 for (pred = set_first (node->predecessors); pred;
1045 pred = set_next (pred))
1046 set_intersection (work, graph->nodes[pred->element]->dom);
1047 set_add (work, i);
1048 if (!set_is_equivalent (work, node->dom))
1049 changed = 1;
1050 set_assign (node->dom, work);
1051 }
1052 } while (changed);
1053 set_delete (work);
1054 }
1055
1056 static void
insert_loop_node(flowloop_t * loop,unsigned n,set_t * stack)1057 insert_loop_node (flowloop_t *loop, unsigned n, set_t *stack)
1058 {
1059 if (!set_is_member (loop->nodes, n)) {
1060 set_add (loop->nodes, n);
1061 set_add (stack, n);
1062 }
1063 }
1064
1065 static flowloop_t *
make_loop(flowgraph_t * graph,unsigned n,unsigned d)1066 make_loop (flowgraph_t *graph, unsigned n, unsigned d)
1067 {
1068 flowloop_t *loop = new_loop ();
1069 flownode_t *node;
1070 set_t *stack = set_new ();
1071 set_iter_t *pred;
1072
1073 loop->head = d;
1074 set_add (loop->nodes, d);
1075 insert_loop_node (loop, n, stack);
1076 while (!set_is_empty (stack)) {
1077 set_iter_t *ss = set_first (stack);
1078 unsigned m = ss->element;
1079 set_del_iter (ss);
1080 set_remove (stack, m);
1081 node = graph->nodes[m];
1082 for (pred = set_first (node->predecessors); pred;
1083 pred = set_next (pred))
1084 insert_loop_node (loop, pred->element, stack);
1085 }
1086 set_delete (stack);
1087 return loop;
1088 }
1089
1090 static void
flow_find_loops(flowgraph_t * graph)1091 flow_find_loops (flowgraph_t *graph)
1092 {
1093 flownode_t *node;
1094 set_iter_t *succ;
1095 flowloop_t *loop, *l;
1096 flowloop_t *loop_list = 0;
1097 int i;
1098
1099 for (i = 0; i < graph->num_nodes; i++) {
1100 node = graph->nodes[i];
1101 for (succ = set_first (node->successors); succ;
1102 succ = set_next (succ)) {
1103 if (set_is_member (node->dom, succ->element)) {
1104 loop = make_loop (graph, node->id, succ->element);
1105 for (l = loop_list; l; l = l->next) {
1106 if (l->head == loop->head
1107 && !set_is_subset (l->nodes, loop->nodes)
1108 && !set_is_subset (loop->nodes, l->nodes)) {
1109 set_union (l->nodes, loop->nodes);
1110 delete_loop (loop);
1111 loop = 0;
1112 break;
1113 }
1114 }
1115 if (loop) {
1116 loop->next = loop_list;
1117 loop_list = loop;
1118 }
1119 }
1120 }
1121 }
1122 graph->loops = loop_list;
1123 }
1124
1125 static void
df_search(flowgraph_t * graph,set_t * visited,int * i,int n)1126 df_search (flowgraph_t *graph, set_t *visited, int *i, int n)
1127 {
1128 flownode_t *node;
1129 set_iter_t *edge;
1130 int succ;
1131
1132 set_add (visited, n);
1133 node = graph->nodes[n];
1134 for (edge = set_first (node->edges); edge; edge = set_next (edge)) {
1135 succ = graph->edges[edge->element].head;
1136 if (!set_is_member (visited, succ)) {
1137 set_add (graph->dfst, edge->element);
1138 df_search (graph, visited, i, succ);
1139 }
1140 }
1141 node->dfn = --*i;
1142 graph->dfo[node->dfn] = n;
1143 }
1144
1145 static void
flow_build_dfst(flowgraph_t * graph)1146 flow_build_dfst (flowgraph_t *graph)
1147 {
1148 set_t *visited = set_new ();
1149 int i;
1150
1151 // mark the dummy nodes as visited to keep them out of the dfst
1152 set_add (visited, graph->num_nodes);
1153 set_add (visited, graph->num_nodes + 1);
1154
1155 if (graph->dfo)
1156 free (graph->dfo);
1157 if (graph->dfst)
1158 set_delete (graph->dfst);
1159 graph->dfo = calloc (graph->num_nodes, sizeof (int));
1160 graph->dfst = set_new ();
1161 i = graph->num_nodes;
1162 df_search (graph, visited, &i, 0);
1163 set_delete (visited);
1164 }
1165
1166 static int
flow_remove_unreachable_nodes(flowgraph_t * graph)1167 flow_remove_unreachable_nodes (flowgraph_t *graph)
1168 {
1169 int i, j;
1170 flownode_t *node;
1171
1172 for (i = 0, j = 0; i < graph->num_nodes; i++) {
1173 node = graph->nodes[i];
1174 if (node->dfn < 0) // skip over unreachable nodes
1175 continue;
1176 node->id = j; // new node number
1177 graph->nodes[j++] = node;
1178 }
1179 graph->nodes[j] = graph->nodes[i]; // copy entry dummy node
1180 graph->nodes[j + 1] = graph->nodes[i + 1]; // copy exit dummy node
1181
1182 // kill the pointers to unreachable nodes
1183 for (i = j; i < graph->num_nodes; i++)
1184 graph->nodes[i + 2] = 0;
1185
1186 if (j < graph->num_nodes) {
1187 graph->num_nodes = j;
1188 return 1;
1189 }
1190 return 0;
1191 }
1192
1193 static flownode_t *
flow_make_node(sblock_t * sblock,int id,function_t * func)1194 flow_make_node (sblock_t *sblock, int id, function_t *func)
1195 {
1196 flownode_t *node;
1197
1198 node = new_node ();
1199 node->predecessors = set_new ();
1200 node->successors = set_new ();
1201 node->edges = set_new ();
1202 node->dom = set_new ();
1203 node->global_vars = func->global_vars;
1204 node->id = id;
1205 node->sblock = sblock;
1206 if (sblock)
1207 sblock->flownode = node;
1208 node->graph = func->graph;
1209 // Mark the node as unreachable. flow_build_dfst() will mark reachable
1210 // nodes with a value >= 0
1211 node->dfn = -1;
1212 return node;
1213 }
1214
1215 static flowgraph_t *
flow_build_graph(function_t * func)1216 flow_build_graph (function_t *func)
1217 {
1218 sblock_t *sblock = func->sblock;
1219 flowgraph_t *graph;
1220 flownode_t *node;
1221 sblock_t *sb;
1222 int i;
1223 int pass = 0;
1224
1225 graph = new_graph ();
1226 graph->func = func;
1227 func->graph = graph;
1228 for (sb = sblock; sb; sb = sb->next)
1229 graph->num_nodes++;
1230 // + 2 for the uninitialized dummy head block and the live dummy end block
1231 graph->nodes = malloc ((graph->num_nodes + 2) * sizeof (flownode_t *));
1232 for (i = 0, sb = sblock; sb; i++, sb = sb->next)
1233 graph->nodes[i] = flow_make_node (sb, i, func);
1234 // Create the dummy node for detecting uninitialized variables
1235 node = flow_make_node (0, graph->num_nodes, func);
1236 graph->nodes[graph->num_nodes] = node;
1237 // Create the dummy node for making global vars live at function exit
1238 node = flow_make_node (0, graph->num_nodes + 1, func);
1239 graph->nodes[graph->num_nodes + 1] = node;
1240
1241 do {
1242 if (pass > 1)
1243 internal_error (0, "too many unreachable node passes");
1244 flow_find_successors (graph);
1245 flow_make_edges (graph);
1246 flow_build_dfst (graph);
1247 if (options.block_dot.flow)
1248 dump_dot (va ("flow-%d", pass), graph, dump_dot_flow);
1249 pass++;
1250 } while (flow_remove_unreachable_nodes (graph));
1251 flow_find_predecessors (graph);
1252 flow_find_dominators (graph);
1253 flow_find_loops (graph);
1254 return graph;
1255 }
1256
1257 void
flow_data_flow(function_t * func)1258 flow_data_flow (function_t *func)
1259 {
1260 flowgraph_t *graph;
1261
1262 flow_build_statements (func);
1263 flow_build_vars (func);
1264 graph = flow_build_graph (func);
1265 flow_reaching_defs (graph);
1266 if (options.block_dot.reaching)
1267 dump_dot ("reaching", graph, dump_dot_flow_reaching);
1268 flow_live_vars (graph);
1269 if (options.block_dot.live)
1270 dump_dot ("live", graph, dump_dot_flow_live);
1271 flow_uninitialized (graph);
1272 flow_build_dags (graph);
1273 flow_cleanup_dags (graph);
1274 func->sblock = flow_generate (graph);
1275 }
1276