2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Compute and access out edges (also called def-use edges).
23 * @author Goetz Lindenmaier, Michael Beck
38 #include "irgraph_t.h"
44 /* Note: ir_node.out_valid and ir_graph.n_outs are only present when DEBUG_libfirm is defined */
45 /* Accesses to out_valid and n_outs are fenced out to avoid breakage
46 when compiling with neither DEBUG_libfirm or NDEBUG defined */
47 #endif /* defined DEBUG_libfirm */
49 /*--------------------------------------------------------------------*/
50 /** Accessing the out datastructures **/
51 /*--------------------------------------------------------------------*/
54 /** Clear the outs of a node */
55 static void reset_outs(ir_node *node, void *unused) {
62 int get_irn_outs_computed(const ir_node *node)
64 return node->out != NULL;
67 /* returns the number of successors of the node: */
68 int get_irn_n_outs(ir_node *node) {
69 assert(node && node->kind == k_ir_node);
71 /* assert(node->out_valid); */
72 #endif /* defined DEBUG_libfirm */
73 /* we misuse the first for the size info of the out array */
74 return node->out[0].pos;
77 /* Access successor n */
78 ir_node *get_irn_out(ir_node *def, int pos) {
79 assert(pos >= 0 && pos < get_irn_n_outs(def));
81 /* assert(def->out_valid); */
82 #endif /* defined DEBUG_libfirm */
83 return def->out[pos+1].use;
86 /* Access successor n */
87 ir_node *get_irn_out_ex(ir_node *def, int pos, int *in_pos) {
88 assert(pos >= 0 && pos < get_irn_n_outs(def));
90 /* assert(def->out_valid); */
91 #endif /* defined DEBUG_libfirm */
92 *in_pos = def->out[pos+1].pos;
93 return def->out[pos+1].use;
96 void set_irn_out(ir_node *def, int pos, ir_node *use, int in_pos) {
98 assert(pos >= 0 && pos < get_irn_n_outs(def));
100 def->out_valid = 1; /* assume that this function is used correctly */
101 #endif /* defined DEBUG_libfirm */
102 def->out[pos+1].use = use;
103 def->out[pos+1].pos = in_pos;
106 /* Return the number of control flow successors, ignore keep-alives. */
107 int get_Block_n_cfg_outs(ir_node *bl) {
108 int i, n_cfg_outs = 0;
109 assert(bl && is_Block(bl));
111 assert(bl->out_valid);
112 #endif /* defined DEBUG_libfirm */
113 for (i = 1; i <= bl->out[0].pos; ++i) {
114 ir_node *succ = bl->out[i].use;
115 if (get_irn_mode(succ) == mode_X && !is_End(succ))
116 n_cfg_outs += succ->out[0].pos;
121 /* Return the number of control flow successors, honor keep-alives. */
122 int get_Block_n_cfg_outs_ka(ir_node *bl) {
123 int i, n_cfg_outs = 0;
124 assert(bl && is_Block(bl));
126 assert(bl->out_valid);
127 #endif /* defined DEBUG_libfirm */
128 for (i = 1; i <= bl->out[0].pos; ++i) {
129 ir_node *succ = bl->out[i].use;
130 if (get_irn_mode(succ) == mode_X) {
133 /* ignore End if we are in the Endblock */
134 if (get_nodes_block(succ) == bl)
136 else /* count Keep-alive as one */
139 n_cfg_outs += succ->out[0].pos;
145 /* Access predecessor n, ignore keep-alives. */
146 ir_node *get_Block_cfg_out(ir_node *bl, int pos) {
148 assert(bl && is_Block(bl));
150 assert(bl->out_valid);
151 #endif /* defined DEBUG_libfirm */
152 for (i = 1; i <= bl->out[0].pos; ++i) {
153 ir_node *succ = bl->out[i].use;
154 if (get_irn_mode(succ) == mode_X && !is_End(succ)) {
155 int n_outs = succ->out[0].pos;
157 return succ->out[pos + 1].use;
165 /* Access predecessor n, honor keep-alives. */
166 ir_node *get_Block_cfg_out_ka(ir_node *bl, int pos) {
168 assert(bl && is_Block(bl));
170 assert (bl->out_valid);
171 #endif /* defined DEBUG_libfirm */
172 for (i = 1; i <= bl->out[0].pos; ++i) {
173 ir_node *succ = bl->out[i].use;
174 if (get_irn_mode(succ) == mode_X) {
176 ir_node *end_bl = get_nodes_block(succ);
178 /* ignore End if we are in the Endblock */
182 /* handle keep-alive here: return the Endblock instead of the End node */
187 n_outs = succ->out[0].pos;
189 return succ->out[pos + 1].use;
198 static void irg_out_walk_2(ir_node *node, irg_walk_func *pre,
199 irg_walk_func *post, void *env) {
204 assert(get_irn_visited(node) < get_irg_visited(current_ir_graph));
206 set_irn_visited(node, get_irg_visited(current_ir_graph));
208 if (pre) pre(node, env);
210 for (i = 0, n = get_irn_n_outs(node); i < n; ++i) {
211 succ = get_irn_out(node, i);
212 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
213 irg_out_walk_2(succ, pre, post, env);
216 if (post) post(node, env);
221 void irg_out_walk(ir_node *node,
222 irg_walk_func *pre, irg_walk_func *post,
225 if (get_irg_outs_state(current_ir_graph) != outs_none) {
226 inc_irg_visited (current_ir_graph);
227 irg_out_walk_2(node, pre, post, env);
232 static void irg_out_block_walk2(ir_node *bl,
233 irg_walk_func *pre, irg_walk_func *post,
237 if (Block_not_block_visited(bl)) {
238 mark_Block_block_visited(bl);
243 for (i = 0, n = get_Block_n_cfg_outs(bl); i < n; ++i) {
244 /* find the corresponding predecessor block. */
245 ir_node *pred = get_Block_cfg_out(bl, i);
247 irg_out_block_walk2(pred, pre, post, env);
255 /* Walks only over Block nodes in the graph. Has it's own visited
256 flag, so that it can be interleaved with the other walker. */
257 void irg_out_block_walk(ir_node *node,
258 irg_walk_func *pre, irg_walk_func *post,
261 assert(is_Block(node) || (get_irn_mode(node) == mode_X));
263 inc_irg_block_visited(current_ir_graph);
265 if (get_irn_mode(node) == mode_X) {
268 for (i = 0, n = get_irn_n_outs(node); i < n; ++i) {
269 ir_node *succ = get_irn_out(node, i);
270 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
271 irg_out_walk_2(succ, pre, post, env);
275 irg_out_block_walk2(node, pre, post, env);
279 /*--------------------------------------------------------------------*/
280 /** Building and Removing the out datastructure **/
282 /** The outs of a graph are allocated in a single, large array. **/
283 /** This allows to allocate and deallocate the memory for the outs **/
284 /** on demand. The large array is separated into many small ones **/
285 /** for each node. Only a single field to reference the out array **/
286 /** is stored in each node and a field referencing the large out **/
287 /** array in irgraph. The 0 field of each out array contains the **/
288 /** size of this array. This saves memory in the irnodes themselves.**/
289 /** The construction does two passes over the graph. The first pass **/
290 /** counts the overall number of outs and the outs of each node. It **/
291 /** stores the outs of each node in the out reference of the node. **/
292 /** Then the large array is allocated. The second iteration chops **/
293 /** the large array into smaller parts, sets the out edges and **/
294 /** recounts the out edges. **/
295 /** Removes Tuple nodes! **/
296 /*--------------------------------------------------------------------*/
299 /** Returns the amount of out edges for not yet visited successors. */
300 static int _count_outs(ir_node *n) {
301 int start, i, res, irn_arity;
304 n->out = INT_TO_PTR(1); /* Space for array size. */
306 start = is_Block(n) ? 0 : -1;
307 irn_arity = get_irn_arity(n);
308 res = irn_arity - start + 1; /* --1 or --0; 1 for array size. */
310 for (i = start; i < irn_arity; ++i) {
311 /* Optimize Tuples. They annoy if walking the cfg. */
312 ir_node *pred = skip_Tuple(get_irn_n(n, i));
313 set_irn_n(n, i, pred);
315 /* count Def-Use edges for predecessors */
316 if (irn_not_visited(pred))
317 res += _count_outs(pred);
319 /*count my Def-Use edges */
320 pred->out = INT_TO_PTR(PTR_TO_INT(pred->out) + 1);
326 /** Returns the amount of out edges for not yet visited successors.
327 * This version handles some special nodes like irg_frame, irg_args etc.
329 static int count_outs(ir_graph *irg) {
333 inc_irg_visited(irg);
334 res = _count_outs(get_irg_end(irg));
336 /* Now handle anchored nodes. We need the out count of those
337 even if they are not visible. */
338 for (i = anchor_last - 1; i >= 0; --i) {
339 n = get_irg_anchor(irg, i);
340 if (irn_not_visited(n)) {
343 n->out = INT_TO_PTR(1);
351 * Enter memory for the outs to a node.
353 * @param use current node
354 * @param free current free address in the chunk allocated for the outs
356 * @return The next free address
358 static ir_def_use_edge *_set_out_edges(ir_node *use, ir_def_use_edge *free) {
359 int n_outs, start, i, irn_arity, pos;
361 mark_irn_visited(use);
363 /* Allocate my array */
364 n_outs = PTR_TO_INT(use->out);
368 #endif /* defined DEBUG_libfirm */
370 /* We count the successors again, the space will be sufficient.
371 We use this counter to remember the position for the next back
375 start = is_Block(use) ? 0 : -1;
376 irn_arity = get_irn_arity(use);
378 for (i = start; i < irn_arity; ++i) {
379 ir_node *def = get_irn_n(use, i);
382 if (irn_not_visited(def))
383 free = _set_out_edges(def, free);
385 /* Remember this Def-Use edge */
386 pos = def->out[0].pos + 1;
387 def->out[pos].use = use;
388 def->out[pos].pos = i;
390 /* increase the number of Def-Use edges so far */
391 def->out[0].pos = pos;
397 * Enter memory for the outs to a node. Handles special nodes
399 * @param irg the graph
400 * @param free current free address in the chunk allocated for the outs
402 * @return The next free address
404 static ir_def_use_edge *set_out_edges(ir_graph *irg, ir_def_use_edge *free) {
408 inc_irg_visited(irg);
409 free = _set_out_edges(get_irg_end(irg), free);
411 /* handle anchored nodes */
412 for (i = anchor_last - 1; i >= 0; --i) {
413 n = get_irg_anchor(irg, i);
414 if (irn_not_visited(n)) {
417 n_outs = PTR_TO_INT(n->out);
421 #endif /* defined DEBUG_libfirm */
431 * We want that the out of ProjX from Start contains the next block at
432 * position 1, the Start block at position 2. This is necessary for
433 * the out block walker.
435 static INLINE void fix_start_proj(ir_graph *irg) {
436 ir_node *proj = NULL;
438 ir_node *startbl = get_irg_start_block(irg);
439 int i, block_pos, other_pos;
441 if (get_Block_n_cfg_outs(startbl)) {
442 for (i = get_irn_n_outs(startbl) - 1; i >= 0; --i)
443 if (get_irn_mode(get_irn_out(startbl, i)) == mode_X) {
444 proj = get_irn_out(startbl, i);
448 if (get_irn_out_ex(proj, 0, &block_pos) == startbl) {
449 assert(get_irn_n_outs(proj) == 2);
450 irn = get_irn_out_ex(proj, 1, &other_pos);
451 set_irn_out(proj, 0, irn, other_pos);
452 set_irn_out(proj, 1, startbl, block_pos);
457 /* compute the outs for a given graph */
458 void compute_irg_outs(ir_graph *irg) {
459 ir_graph *rem = current_ir_graph;
461 ir_def_use_edge *end = NULL; /* Only for debugging */
463 current_ir_graph = irg;
465 /* Update graph state */
466 assert(get_irg_phase_state(current_ir_graph) != phase_building);
468 if (current_ir_graph->outs_state != outs_none)
469 free_irg_outs(current_ir_graph);
471 /* This first iteration counts the overall number of out edges and the
472 number of out edges for each node. */
473 n_out_edges = count_outs(irg);
475 /* allocate memory for all out edges. */
476 irg->outs = xcalloc(n_out_edges, sizeof(irg->outs[0]));
478 irg->n_outs = n_out_edges;
479 #endif /* defined DEBUG_libfirm */
481 /* The second iteration splits the irg->outs array into smaller arrays
482 for each node and writes the back edges into this array. */
483 end = set_out_edges(irg, irg->outs);
485 /* Check how much memory we have used */
486 assert (end == (irg->outs + n_out_edges));
488 /* We want that the out of ProjX from Start contains the next block at
489 position 1, the Start block at position 2. This is necessary for
490 the out block walker. */
493 current_ir_graph->outs_state = outs_consistent;
494 current_ir_graph = rem;
497 void assure_irg_outs(ir_graph *irg) {
498 if (get_irg_outs_state(irg) != outs_consistent)
499 compute_irg_outs(irg);
502 void compute_irp_outs(void) {
504 for (i = get_irp_n_irgs() -1; i >= 0; --i)
505 compute_irg_outs(get_irp_irg(i));
508 void free_irp_outs(void) {
510 for (i = get_irp_n_irgs() -1; i >= 0; --i)
511 free_irg_outs(get_irp_irg(i));
515 /*------------------------------------------------------------*
516 * This computes the outedges for in interprocedural graph. *
517 * There is one quirk: *
518 * The number of the outedges for each node is saved in *
519 * the first member of the ir_node** array. Maybe we should *
520 * change this to make it more portable... *
521 *------------------------------------------------------------*/
524 #ifdef INTERPROCEDURAL_VIEW
526 * Inits the number of outedges for each node
529 static void init_count(ir_node * node, void *env) {
531 node->out = (ir_node **) 1; /* 1 for the array size */
536 * Adjusts the out edge count for its predecessors
537 * and adds the current arity to the overall count,
538 * which is saved in "env"
540 static void node_arity_count(ir_node * node, void * env) {
541 int *anz = (int *) env, arity, n_outs, i, start;
544 arity = get_irn_arity(node);
545 start = (is_Block(node)) ? 0 : -1;
547 n_outs = 1 + arity + (-start); // ((is_Block(node)) ? 0 : 1); // Why + 1??
550 for(i = start; i < arity; i++) {
551 succ = get_irn_n(node, i);
552 succ->out = (ir_node **)INT_TO_PTR(PTR_TO_INT(succ->out) + 1);
557 * Inits all nodes for setting the outedges
558 * Returns the overall count of edges
560 int count_ip_outs(void) {
563 cg_walk(init_count, node_arity_count, &res);
568 static int dummy_count = 0, global_count; /* Only for debugging */
571 * For each node: Sets the pointer to array
572 * in which the outedges are written later.
573 * The current array start is transported in env
575 static void set_array_pointer(ir_node *node, void *env) {
577 ir_node ***free = (ir_node ***) env;
579 /* Allocate my array */
580 n_outs = PTR_TO_INT(node->out); /* We wrote the count here in count_ip_outs */
581 dummy_count += n_outs;
582 assert(dummy_count <= global_count && "More outedges than initially counted!");
584 *free = &((*free)[n_outs]);
585 /* We count the successors again, the space will be sufficient.
586 We use this counter to remember the position for the next back
588 node -> out[0] = (ir_node *) 0;
593 * Adds an outedge from the predecessor to the
596 static void set_out_pointer(ir_node * node, void *env) {
597 int i, arity = get_irn_arity(node);
599 int start = (!is_Block(node)) ? -1 : 0;
602 for (i = start; i < arity; ++i) {
603 succ = get_irn_n(node, i);
604 succ->out[get_irn_n_outs(succ)+1] = node;
605 succ->out[0] = INT_TO_PTR(get_irn_n_outs(succ) + 1);
611 * Sets the outedges for all nodes.
613 void set_ip_outs(void) {
614 ir_node **outedge_array = get_irp_ip_outedges();
615 cg_walk(set_array_pointer, set_out_pointer, (void *) &outedge_array);
621 * Counts the outedges, allocates memory to save the
622 * outedges and fills this outedge array in interprocedural
625 void compute_ip_outs(void) {
629 assert(get_irp_ip_view_state() == ip_view_valid &&
630 "Cannot construct outs for invalid ip view.");
632 if (irp->outs_state != outs_none) {
636 global_count = n_out_edges = count_ip_outs();
637 out_edges = xcalloc(n_out_edges, sizeof(out_edges[0]));
638 set_irp_ip_outedges(out_edges);
642 void free_ip_outs(void) {
643 ir_node **out_edges = get_irp_ip_outedges();
644 if (out_edges != NULL) {
646 set_irp_ip_outedges(NULL);
648 irp->outs_state = outs_none;
653 void free_irg_outs(ir_graph *irg) {
654 /* current_ir_graph->outs_state = outs_none; */
655 irg->outs_state = outs_none;
659 memset(irg->outs, 0, irg->n_outs);
660 #endif /* defined DEBUG_libfirm */
665 #endif /* defined DEBUG_libfirm */
669 /* when debugging, *always* reset all nodes' outs! irg->outs might
670 have been lying to us */
671 irg_walk_graph (irg, reset_outs, NULL, NULL);
672 #endif /* defined DEBUG_libfirm */