3 * File name: ir/ana/irouts.c
4 * Purpose: Compute and access out edges.
5 * Author: Goetz Lindenmaier
9 * Copyright: (c) 2002-2003 Universität Karlsruhe
10 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
14 * @file irouts.c Compute out edges for ir nodes (also called def-use edges).
16 * Copyright (C) 2002 by Universitaet Karlsruhe
17 * All rights reserved.
19 * Authors: Goetz Lindenmaier
33 #include "irgraph_t.h"
39 /* Note: ir_node.out_valid and ir_graph.n_outs are only present when DEBUG_libfirm is defined */
40 /* Accesses to out_valid and n_outs are fenced out to avoid breakage
41 when compiling with neither DEBUG_libfirm or NDEBUG defined */
42 #endif /* defined DEBUG_libfirm */
44 /*--------------------------------------------------------------------*/
45 /** Accessing the out datastructures **/
46 /*--------------------------------------------------------------------*/
48 /** Clear the outs of a node */
49 static void reset_outs (ir_node *node, void *unused)
54 #endif /* defined DEBUG_libfirm */
57 /* returns the number of successors of the node: */
58 int get_irn_n_outs (ir_node *node) {
59 assert(node && node->kind == k_ir_node);
61 /* assert (node->out_valid); */
62 #endif /* defined DEBUG_libfirm */
63 return PTR_TO_INT(node->out[0]);
66 /* Access successor n */
67 ir_node *get_irn_out (ir_node *node, int pos) {
68 assert(pos >= 0 && pos < get_irn_n_outs(node));
70 /* assert (node->out_valid); */
71 #endif /* defined DEBUG_libfirm */
72 return node->out[pos+1];
75 void set_irn_out (ir_node *node, int pos, ir_node *out) {
77 assert(pos >= 0 && pos < get_irn_n_outs(node));
79 node->out_valid = 1; /* assume that this function is used correctly */
80 #endif /* defined DEBUG_libfirm */
81 node->out[pos+1] = out;
84 /* Return the number of control flow successors, ignore keep-alives. */
85 int get_Block_n_cfg_outs(ir_node *bl) {
86 int i, n_cfg_outs = 0;
87 assert(bl && is_Block(bl));
89 assert (bl->out_valid);
90 #endif /* defined DEBUG_libfirm */
91 for (i = 1; i <= PTR_TO_INT(bl->out[0]); i++)
92 if ((get_irn_mode(bl->out[i]) == mode_X) &&
93 (get_irn_op(bl->out[i]) != op_End))
98 /* Return the number of control flow successors, honor keep-alives. */
99 int get_Block_n_cfg_outs_ka(ir_node *bl) {
100 int i, n_cfg_outs = 0;
101 assert(bl && is_Block(bl));
103 assert (bl->out_valid);
104 #endif /* defined DEBUG_libfirm */
105 for (i = 1; i <= PTR_TO_INT(bl->out[0]); i++)
106 if (get_irn_mode(bl->out[i]) == mode_X) {
107 /* ignore End if we are in the Endblock */
108 if (get_irn_op(bl->out[i]) == op_End &&
109 get_irn_n(bl->out[i], -1) == bl)
117 /* Access predecessor n, ignore keep-alives. */
118 ir_node *get_Block_cfg_out(ir_node *bl, int pos) {
120 assert(bl && is_Block(bl));
122 assert (bl->out_valid);
123 #endif /* defined DEBUG_libfirm */
124 for (i = 1; i <= PTR_TO_INT(bl->out[0]); i++)
125 if ((get_irn_mode(bl->out[i]) == mode_X) &&
126 (get_irn_op(bl->out[i]) != op_End)) {
127 if (out_pos == pos) {
128 ir_node *cfop = bl->out[i];
136 /* Access predecessor n, honor keep-alives. */
137 ir_node *get_Block_cfg_out_ka(ir_node *bl, int pos) {
139 assert(bl && is_Block(bl));
141 assert (bl->out_valid);
142 #endif /* defined DEBUG_libfirm */
143 for (i = 1; i <= PTR_TO_INT(bl->out[0]); i++)
144 if (get_irn_mode(bl->out[i]) == mode_X) {
145 /* ignore End if we are in the Endblock */
146 if (get_irn_op(bl->out[i]) == op_End &&
147 get_irn_n(bl->out[i], -1) == bl)
149 if (out_pos == pos) {
150 ir_node *cfop = bl->out[i];
151 /* handle keep-alive here */
152 if (get_irn_op(cfop) == op_End)
153 return get_irn_n(cfop, -1);
161 static void irg_out_walk_2(ir_node *node, irg_walk_func *pre,
162 irg_walk_func *post, void *env) {
167 assert(get_irn_visited(node) < get_irg_visited(current_ir_graph));
169 set_irn_visited(node, get_irg_visited(current_ir_graph));
171 if (pre) pre(node, env);
173 for (i = 0, n = get_irn_n_outs(node); i < n; i++) {
174 succ = get_irn_out(node, i);
175 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
176 irg_out_walk_2(succ, pre, post, env);
179 if (post) post(node, env);
184 void irg_out_walk(ir_node *node,
185 irg_walk_func *pre, irg_walk_func *post,
188 if (get_irg_outs_state(current_ir_graph) != outs_none) {
189 inc_irg_visited (current_ir_graph);
190 irg_out_walk_2(node, pre, post, env);
195 static void irg_out_block_walk2(ir_node *bl,
196 irg_walk_func *pre, irg_walk_func *post,
200 if (Block_not_block_visited(bl)) {
201 mark_Block_block_visited(bl);
206 for (i = 0, n = get_Block_n_cfg_outs(bl); i < n; i++) {
207 /* find the corresponding predecessor block. */
208 ir_node *pred = get_Block_cfg_out(bl, i);
210 irg_out_block_walk2(pred, pre, post, env);
218 /* Walks only over Block nodes in the graph. Has it's own visited
219 flag, so that it can be interleaved with the other walker. */
220 void irg_out_block_walk(ir_node *node,
221 irg_walk_func *pre, irg_walk_func *post,
224 assert(is_Block(node) || (get_irn_mode(node) == mode_X));
226 inc_irg_block_visited(current_ir_graph);
228 if (get_irn_mode(node) == mode_X)
231 irg_out_block_walk2(node, pre, post, env);
234 /*--------------------------------------------------------------------*/
235 /** Building and Removing the out datasturcture **/
237 /** The outs of a graph are allocated in a single, large array. **/
238 /** This allows to allocate and deallocate the memory for the outs **/
239 /** on demand. The large array is separated into many small ones **/
240 /** for each node. Only a single field to reference the out array **/
241 /** is stored in each node and a field referencing the large out **/
242 /** array in irgraph. The 0 field of each out array contains the **/
243 /** size of this array. This saves memory in the irnodes themselves.**/
244 /** The construction does two passes over the graph. The first pass **/
245 /** counts the overall number of outs and the outs of each node. It **/
246 /** stores the outs of each node in the out reference of the node. **/
247 /** Then the large array is allocated. The second iteration chops **/
248 /** the large array into smaller parts, sets the out edges and **/
249 /** recounts the out edges. **/
250 /** Removes Tuple nodes! **/
251 /*--------------------------------------------------------------------*/
254 /** Returns the amount of out edges for not yet visited successors. */
255 static int _count_outs(ir_node *n) {
256 int start, i, res, irn_arity;
259 n->out = (ir_node **) 1; /* Space for array size. */
261 start = is_Block(n) ? 0 : -1;
262 irn_arity = get_irn_arity(n);
263 res = irn_arity - start + 1; /* --1 or --0; 1 for array size. */
265 for (i = start; i < irn_arity; ++i) {
266 /* Optimize Tuples. They annoy if walking the cfg. */
267 ir_node *pred = skip_Tuple(get_irn_n(n, i));
268 set_irn_n(n, i, pred);
270 /* count outs for successors */
271 if (irn_not_visited(pred))
272 res += _count_outs(pred);
275 pred->out = (ir_node **)INT_TO_PTR(PTR_TO_INT(pred->out) + 1);
281 /** Returns the amount of out edges for not yet visited successors.
282 * This version handles some special nodes like irg_frame, irg_args etc.
284 static int count_outs(ir_graph *irg) {
288 inc_irg_visited(irg);
289 res = _count_outs(get_irg_end(irg));
291 /* now handle special nodes */
292 n = get_irg_frame(irg);
293 if (irn_not_visited(n)) {
294 n->out = (ir_node **)1;
298 n = get_irg_args(irg);
299 if (irn_not_visited(n)) {
300 n->out = (ir_node **)1;
308 * Enter memory for the outs to a node.
310 * @param n current node
311 * @param free current free address in the chunk allocated for the outs
313 * @return The next free address
315 static ir_node **_set_out_edges(ir_node *n, ir_node **free) {
316 int n_outs, start, i, irn_arity;
319 set_irn_visited(n, get_irg_visited(current_ir_graph));
321 /* Allocate my array */
322 n_outs = PTR_TO_INT(n->out);
326 #endif /* defined DEBUG_libfirm */
328 /* We count the successors again, the space will be sufficient.
329 We use this counter to remember the position for the next back
331 n->out[0] = (ir_node *)0;
333 start = is_Block(n) ? 0 : -1;
334 irn_arity = get_irn_arity(n);
336 for (i = start; i < irn_arity; i++) {
337 pred = get_irn_n(n, i);
339 if (get_irn_visited(pred) < get_irg_visited(current_ir_graph))
340 free = _set_out_edges(pred, free);
341 /* Remember our back edge */
342 pred->out[get_irn_n_outs(pred)+1] = n;
343 pred->out[0] = INT_TO_PTR(get_irn_n_outs(pred) + 1);
349 * Enter memory for the outs to a node. Handles special nodes
351 * @param irg the graph
352 * @param free current free address in the chunk allocated for the outs
354 * @return The next free address
356 static ir_node **set_out_edges(ir_graph *irg, ir_node **free) {
357 ir_node *n, *special[2];
360 inc_irg_visited(irg);
361 free = _set_out_edges(get_irg_end(irg), free);
363 /* handle special nodes */
364 special[0] = get_irg_frame(irg);
365 special[1] = get_irg_args(irg);
367 for (i = 1; i >= 0; --i) {
370 if (get_irn_visited(n) < get_irg_visited(current_ir_graph)) {
371 n_outs = PTR_TO_INT(n->out);
375 #endif /* defined DEBUG_libfirm */
384 /* We want that the out of ProjX from Start contains the next block at
385 position 1, the Start block at position 2. This is necessary for
386 the out block walker. */
387 static INLINE void fix_start_proj(ir_graph *irg) {
388 ir_node *proj = NULL;
389 ir_node *startbl = get_irg_start_block(irg);
392 if (get_Block_n_cfg_outs(startbl)) {
393 for (i = get_irn_n_outs(startbl) - 1; i >= 0; --i)
394 if (get_irn_mode(get_irn_out(startbl, i)) == mode_X) {
395 proj = get_irn_out(startbl, i);
399 if (get_irn_out(proj, 0) == startbl) {
400 assert(get_irn_n_outs(proj) == 2);
401 set_irn_out(proj, 0, get_irn_out(proj, 1));
402 set_irn_out(proj, 1, startbl);
407 /* compute the outs for a given graph */
408 void compute_irg_outs(ir_graph *irg) {
409 ir_graph *rem = current_ir_graph;
411 ir_node **end = NULL; /* Only for debugging */
413 current_ir_graph = irg;
415 /* Update graph state */
416 assert(get_irg_phase_state(current_ir_graph) != phase_building);
418 if (current_ir_graph->outs_state != outs_none)
419 free_irg_outs(current_ir_graph);
421 /* This first iteration counts the overall number of out edges and the
422 number of out edges for each node. */
423 n_out_edges = count_outs(irg);
425 /* allocate memory for all out edges. */
426 irg->outs = xcalloc(n_out_edges, sizeof(irg->outs[0]));
428 irg->n_outs = n_out_edges;
429 #endif /* defined DEBUG_libfirm */
431 /* The second iteration splits the irg->outs array into smaller arrays
432 for each node and writes the back edges into this array. */
433 end = set_out_edges(irg, irg->outs);
435 /* Check how much memory we have used */
436 assert (end == (irg->outs + n_out_edges));
438 /* We want that the out of ProjX from Start contains the next block at
439 position 1, the Start block at position 2. This is necessary for
440 the out block walker. */
443 current_ir_graph->outs_state = outs_consistent;
444 current_ir_graph = rem;
447 void assure_irg_outs(ir_graph *irg) {
448 if (get_irg_outs_state(irg) != outs_consistent)
449 compute_irg_outs(irg);
452 void compute_irp_outs(void) {
453 int i, n_irgs = get_irp_n_irgs();
454 for (i = 0; i < n_irgs; ++i)
455 compute_irg_outs(get_irp_irg(i));
457 void free_irp_outs(void) {
458 int i, n_irgs = get_irp_n_irgs();
459 for (i = 0; i < n_irgs; ++i)
460 free_irg_outs(get_irp_irg(i));
464 /*------------------------------------------------------------*
465 * This computes the outedges for in interprocedural graph. *
466 * There is one quirk: *
467 * The number of the outedges for each node is saved in *
468 * the first member of the ir_node** array. Maybe we should *
469 * change this to make it more portable... *
470 *------------------------------------------------------------*/
474 * Inits the number of outedges for each node
477 static void init_count(ir_node * node, void *env) {
478 node->out = (ir_node **) 1; /* 1 for the array size */
483 * Adjusts the out edge count for its predecessors
484 * and adds the current arity to the overall count,
485 * which is saved in "env"
487 static void node_arity_count(ir_node * node, void * env)
489 int *anz = (int *) env, arity, n_outs, i, start;
492 arity = get_irn_arity(node);
493 start = (is_Block(node)) ? 0 : -1;
495 n_outs = 1 + arity + (-start); // ((is_Block(node)) ? 0 : 1); // Why + 1??
498 for(i = start; i < arity; i++) {
499 succ = get_irn_n(node, i);
500 succ->out = (ir_node **)INT_TO_PTR(PTR_TO_INT(succ->out) + 1);
506 * Inits all nodes for setting the outedges
507 * Returns the overall count of edges
509 int count_ip_outs(void) {
513 cg_walk(init_count, node_arity_count, &res);
518 static int dummy_count = 0, global_count; /* Only for debugging */
521 * For each node: Sets the pointer to array
522 * in which the outedges are written later.
523 * The current array start is transported in env
525 static void set_array_pointer(ir_node *node, void *env) {
528 ir_node ***free = (ir_node ***) env;
530 /* Allocate my array */
531 n_outs = PTR_TO_INT(node->out); /* We wrote the count here in count_ip_outs */
532 dummy_count += n_outs;
533 assert(dummy_count <= global_count && "More outedges than initially counted!");
535 *free = &((*free)[n_outs]);
536 /* We count the successors again, the space will be sufficient.
537 We use this counter to remember the position for the next back
539 node -> out[0] = (ir_node *) 0;
544 * Adds an outedge from the predecessor to the
547 static void set_out_pointer(ir_node * node, void * env) {
548 int i, arity = get_irn_arity(node);
550 int start = (!is_Block(node)) ? -1 : 0;
552 for (i = start; i < arity; i++) {
553 succ = get_irn_n(node, i);
554 succ->out[get_irn_n_outs(succ)+1] = node;
555 succ->out[0] = INT_TO_PTR(get_irn_n_outs(succ) + 1);
561 * Sets the outedges for all nodes.
563 void set_ip_outs(void)
565 ir_node **outedge_array = get_irp_ip_outedges();
566 cg_walk(set_array_pointer, set_out_pointer, (void *) &outedge_array);
572 * Counts the outedges, allocates memory to save the
573 * outedges and fills this outedge array in interprocedural
576 void compute_ip_outs(void) {
581 assert(get_irp_ip_view_state() == ip_view_valid &&
582 "Cannot construct outs for invalid ip view.");
584 if (irp->outs_state != outs_none) {
588 global_count = n_out_edges = count_ip_outs();
589 out_edges = xcalloc(n_out_edges, sizeof(out_edges[0]));
590 set_irp_ip_outedges(out_edges);
594 void free_ip_outs(void)
596 ir_node **out_edges = get_irp_ip_outedges();
597 if (out_edges != NULL) {
599 set_irp_ip_outedges(NULL);
601 irp->outs_state = outs_none;
605 void free_irg_outs(ir_graph *irg) {
607 /* current_ir_graph->outs_state = outs_none; */
608 irg->outs_state = outs_none;
612 memset(irg->outs, 0, irg->n_outs);
613 #endif /* defined DEBUG_libfirm */
618 #endif /* defined DEBUG_libfirm */
622 /* when debugging, *always* reset all nodes' outs! irg->outs might
623 have been lying to us */
624 irg_walk_graph (irg, reset_outs, NULL, NULL);
625 #endif /* defined DEBUG_libfirm */