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 = get_irn_n(n, i);
313 ir_node *skipped_pred = skip_Tuple(pred);
315 if (skipped_pred != pred) {
316 set_irn_n(n, i, skipped_pred);
319 /* count Def-Use edges for predecessors */
320 if (irn_not_visited(skipped_pred))
321 res += _count_outs(skipped_pred);
323 /*count my Def-Use edges */
324 skipped_pred->out = INT_TO_PTR(PTR_TO_INT(skipped_pred->out) + 1);
330 /** Returns the amount of out edges for not yet visited successors.
331 * This version handles some special nodes like irg_frame, irg_args etc.
333 static int count_outs(ir_graph *irg) {
337 inc_irg_visited(irg);
338 res = _count_outs(get_irg_end(irg));
340 /* Now handle anchored nodes. We need the out count of those
341 even if they are not visible. */
342 for (i = anchor_last - 1; i >= 0; --i) {
343 n = get_irg_anchor(irg, i);
344 if (irn_not_visited(n)) {
347 n->out = INT_TO_PTR(1);
355 * Enter memory for the outs to a node.
357 * @param use current node
358 * @param free current free address in the chunk allocated for the outs
360 * @return The next free address
362 static ir_def_use_edge *_set_out_edges(ir_node *use, ir_def_use_edge *free) {
363 int n_outs, start, i, irn_arity, pos;
365 mark_irn_visited(use);
367 /* Allocate my array */
368 n_outs = PTR_TO_INT(use->out);
372 #endif /* defined DEBUG_libfirm */
374 /* We count the successors again, the space will be sufficient.
375 We use this counter to remember the position for the next back
379 start = is_Block(use) ? 0 : -1;
380 irn_arity = get_irn_arity(use);
382 for (i = start; i < irn_arity; ++i) {
383 ir_node *def = get_irn_n(use, i);
386 if (irn_not_visited(def))
387 free = _set_out_edges(def, free);
389 /* Remember this Def-Use edge */
390 pos = def->out[0].pos + 1;
391 def->out[pos].use = use;
392 def->out[pos].pos = i;
394 /* increase the number of Def-Use edges so far */
395 def->out[0].pos = pos;
401 * Enter memory for the outs to a node. Handles special nodes
403 * @param irg the graph
404 * @param free current free address in the chunk allocated for the outs
406 * @return The next free address
408 static ir_def_use_edge *set_out_edges(ir_graph *irg, ir_def_use_edge *free) {
412 inc_irg_visited(irg);
413 free = _set_out_edges(get_irg_end(irg), free);
415 /* handle anchored nodes */
416 for (i = anchor_last - 1; i >= 0; --i) {
417 n = get_irg_anchor(irg, i);
418 if (irn_not_visited(n)) {
421 n_outs = PTR_TO_INT(n->out);
425 #endif /* defined DEBUG_libfirm */
435 * We want that the out of ProjX from Start contains the next block at
436 * position 1, the Start block at position 2. This is necessary for
437 * the out block walker.
439 static INLINE void fix_start_proj(ir_graph *irg) {
440 ir_node *proj = NULL;
442 ir_node *startbl = get_irg_start_block(irg);
443 int i, block_pos, other_pos;
445 if (get_Block_n_cfg_outs(startbl)) {
446 for (i = get_irn_n_outs(startbl) - 1; i >= 0; --i)
447 if (get_irn_mode(get_irn_out(startbl, i)) == mode_X) {
448 proj = get_irn_out(startbl, i);
452 if (get_irn_out_ex(proj, 0, &block_pos) == startbl) {
453 assert(get_irn_n_outs(proj) == 2);
454 irn = get_irn_out_ex(proj, 1, &other_pos);
455 set_irn_out(proj, 0, irn, other_pos);
456 set_irn_out(proj, 1, startbl, block_pos);
461 /* compute the outs for a given graph */
462 void compute_irg_outs(ir_graph *irg) {
463 ir_graph *rem = current_ir_graph;
465 ir_def_use_edge *end = NULL; /* Only for debugging */
467 current_ir_graph = irg;
469 /* Update graph state */
470 assert(get_irg_phase_state(current_ir_graph) != phase_building);
472 if (current_ir_graph->outs_state != outs_none)
473 free_irg_outs(current_ir_graph);
475 /* This first iteration counts the overall number of out edges and the
476 number of out edges for each node. */
477 n_out_edges = count_outs(irg);
479 /* allocate memory for all out edges. */
480 irg->outs = xcalloc(n_out_edges, sizeof(irg->outs[0]));
482 irg->n_outs = n_out_edges;
483 #endif /* defined DEBUG_libfirm */
485 /* The second iteration splits the irg->outs array into smaller arrays
486 for each node and writes the back edges into this array. */
487 end = set_out_edges(irg, irg->outs);
489 /* Check how much memory we have used */
490 assert (end == (irg->outs + n_out_edges));
492 /* We want that the out of ProjX from Start contains the next block at
493 position 1, the Start block at position 2. This is necessary for
494 the out block walker. */
497 current_ir_graph->outs_state = outs_consistent;
498 current_ir_graph = rem;
501 void assure_irg_outs(ir_graph *irg) {
502 if (get_irg_outs_state(irg) != outs_consistent)
503 compute_irg_outs(irg);
506 void compute_irp_outs(void) {
508 for (i = get_irp_n_irgs() -1; i >= 0; --i)
509 compute_irg_outs(get_irp_irg(i));
512 void free_irp_outs(void) {
514 for (i = get_irp_n_irgs() -1; i >= 0; --i)
515 free_irg_outs(get_irp_irg(i));
519 /*------------------------------------------------------------*
520 * This computes the outedges for in interprocedural graph. *
521 * There is one quirk: *
522 * The number of the outedges for each node is saved in *
523 * the first member of the ir_node** array. Maybe we should *
524 * change this to make it more portable... *
525 *------------------------------------------------------------*/
528 #ifdef INTERPROCEDURAL_VIEW
530 * Inits the number of outedges for each node
533 static void init_count(ir_node * node, void *env) {
535 node->out = (ir_node **) 1; /* 1 for the array size */
540 * Adjusts the out edge count for its predecessors
541 * and adds the current arity to the overall count,
542 * which is saved in "env"
544 static void node_arity_count(ir_node * node, void * env) {
545 int *anz = (int *) env, arity, n_outs, i, start;
548 arity = get_irn_arity(node);
549 start = (is_Block(node)) ? 0 : -1;
551 n_outs = 1 + arity + (-start); // ((is_Block(node)) ? 0 : 1); // Why + 1??
554 for(i = start; i < arity; i++) {
555 succ = get_irn_n(node, i);
556 succ->out = (ir_node **)INT_TO_PTR(PTR_TO_INT(succ->out) + 1);
561 * Inits all nodes for setting the outedges
562 * Returns the overall count of edges
564 int count_ip_outs(void) {
567 cg_walk(init_count, node_arity_count, &res);
572 static int dummy_count = 0, global_count; /* Only for debugging */
575 * For each node: Sets the pointer to array
576 * in which the outedges are written later.
577 * The current array start is transported in env
579 static void set_array_pointer(ir_node *node, void *env) {
581 ir_node ***free = (ir_node ***) env;
583 /* Allocate my array */
584 n_outs = PTR_TO_INT(node->out); /* We wrote the count here in count_ip_outs */
585 dummy_count += n_outs;
586 assert(dummy_count <= global_count && "More outedges than initially counted!");
588 *free = &((*free)[n_outs]);
589 /* We count the successors again, the space will be sufficient.
590 We use this counter to remember the position for the next back
592 node -> out[0] = (ir_node *) 0;
597 * Adds an outedge from the predecessor to the
600 static void set_out_pointer(ir_node * node, void *env) {
601 int i, arity = get_irn_arity(node);
603 int start = (!is_Block(node)) ? -1 : 0;
606 for (i = start; i < arity; ++i) {
607 succ = get_irn_n(node, i);
608 succ->out[get_irn_n_outs(succ)+1] = node;
609 succ->out[0] = INT_TO_PTR(get_irn_n_outs(succ) + 1);
615 * Sets the outedges for all nodes.
617 void set_ip_outs(void) {
618 ir_node **outedge_array = get_irp_ip_outedges();
619 cg_walk(set_array_pointer, set_out_pointer, (void *) &outedge_array);
625 * Counts the outedges, allocates memory to save the
626 * outedges and fills this outedge array in interprocedural
629 void compute_ip_outs(void) {
633 assert(get_irp_ip_view_state() == ip_view_valid &&
634 "Cannot construct outs for invalid ip view.");
636 if (irp->outs_state != outs_none) {
640 global_count = n_out_edges = count_ip_outs();
641 out_edges = xcalloc(n_out_edges, sizeof(out_edges[0]));
642 set_irp_ip_outedges(out_edges);
646 void free_ip_outs(void) {
647 ir_node **out_edges = get_irp_ip_outedges();
648 if (out_edges != NULL) {
650 set_irp_ip_outedges(NULL);
652 irp->outs_state = outs_none;
657 void free_irg_outs(ir_graph *irg) {
658 /* current_ir_graph->outs_state = outs_none; */
659 irg->outs_state = outs_none;
663 memset(irg->outs, 0, irg->n_outs);
664 #endif /* defined DEBUG_libfirm */
669 #endif /* defined DEBUG_libfirm */
673 /* when debugging, *always* reset all nodes' outs! irg->outs might
674 have been lying to us */
675 irg_walk_graph (irg, reset_outs, NULL, NULL);
676 #endif /* defined DEBUG_libfirm */