3 * File name: ir/ana/irouts.c
4 * Purpose: Compute and access out edges.
5 * Author: Goetz Lindenmaier
6 * Modified by: Michael Beck
9 * Copyright: (c) 2002-2007 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 /*--------------------------------------------------------------------*/
49 /** Clear the outs of a node */
50 static void reset_outs(ir_node *node, void *unused) {
56 /* returns the number of successors of the node: */
57 int get_irn_n_outs(ir_node *node) {
58 assert(node && node->kind == k_ir_node);
60 /* assert(node->out_valid); */
61 #endif /* defined DEBUG_libfirm */
62 return PTR_TO_INT(node->out[0]);
65 /* Access successor n */
66 ir_node *get_irn_out(ir_node *node, int pos) {
67 assert(pos >= 0 && pos < get_irn_n_outs(node));
69 /* assert(node->out_valid); */
70 #endif /* defined DEBUG_libfirm */
71 return node->out[pos+1];
74 void set_irn_out(ir_node *node, int pos, ir_node *out) {
76 assert(pos >= 0 && pos < get_irn_n_outs(node));
78 node->out_valid = 1; /* assume that this function is used correctly */
79 #endif /* defined DEBUG_libfirm */
80 node->out[pos+1] = out;
83 /* Return the number of control flow successors, ignore keep-alives. */
84 int get_Block_n_cfg_outs(ir_node *bl) {
85 int i, n_cfg_outs = 0;
86 assert(bl && is_Block(bl));
88 assert(bl->out_valid);
89 #endif /* defined DEBUG_libfirm */
90 for (i = 1; i <= PTR_TO_INT(bl->out[0]); ++i)
91 if ((get_irn_mode(bl->out[i]) == mode_X) &&
92 (get_irn_op(bl->out[i]) != op_End))
97 /* Return the number of control flow successors, honor keep-alives. */
98 int get_Block_n_cfg_outs_ka(ir_node *bl) {
99 int i, n_cfg_outs = 0;
100 assert(bl && is_Block(bl));
102 assert(bl->out_valid);
103 #endif /* defined DEBUG_libfirm */
104 for (i = 1; i <= PTR_TO_INT(bl->out[0]); ++i)
105 if (get_irn_mode(bl->out[i]) == mode_X) {
106 /* ignore End if we are in the Endblock */
107 if (get_irn_op(bl->out[i]) == op_End &&
108 get_irn_n(bl->out[i], -1) == bl)
116 /* Access predecessor n, ignore keep-alives. */
117 ir_node *get_Block_cfg_out(ir_node *bl, int pos) {
119 assert(bl && is_Block(bl));
121 assert (bl->out_valid);
122 #endif /* defined DEBUG_libfirm */
123 for (i = 1; i <= PTR_TO_INT(bl->out[0]); ++i)
124 if ((get_irn_mode(bl->out[i]) == mode_X) &&
125 (get_irn_op(bl->out[i]) != op_End)) {
126 if (out_pos == pos) {
127 ir_node *cfop = bl->out[i];
135 /* Access predecessor n, honor keep-alives. */
136 ir_node *get_Block_cfg_out_ka(ir_node *bl, int pos) {
138 assert(bl && is_Block(bl));
140 assert (bl->out_valid);
141 #endif /* defined DEBUG_libfirm */
142 for (i = 1; i <= PTR_TO_INT(bl->out[0]); ++i)
143 if (get_irn_mode(bl->out[i]) == mode_X) {
144 /* ignore End if we are in the Endblock */
145 if (get_irn_op(bl->out[i]) == op_End &&
146 get_irn_n(bl->out[i], -1) == bl)
148 if (out_pos == pos) {
149 ir_node *cfop = bl->out[i];
150 /* handle keep-alive here */
151 if (get_irn_op(cfop) == op_End)
152 return get_irn_n(cfop, -1);
160 static void irg_out_walk_2(ir_node *node, irg_walk_func *pre,
161 irg_walk_func *post, void *env) {
166 assert(get_irn_visited(node) < get_irg_visited(current_ir_graph));
168 set_irn_visited(node, get_irg_visited(current_ir_graph));
170 if (pre) pre(node, env);
172 for (i = 0, n = get_irn_n_outs(node); i < n; ++i) {
173 succ = get_irn_out(node, i);
174 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
175 irg_out_walk_2(succ, pre, post, env);
178 if (post) post(node, env);
183 void irg_out_walk(ir_node *node,
184 irg_walk_func *pre, irg_walk_func *post,
187 if (get_irg_outs_state(current_ir_graph) != outs_none) {
188 inc_irg_visited (current_ir_graph);
189 irg_out_walk_2(node, pre, post, env);
194 static void irg_out_block_walk2(ir_node *bl,
195 irg_walk_func *pre, irg_walk_func *post,
199 if (Block_not_block_visited(bl)) {
200 mark_Block_block_visited(bl);
205 for (i = 0, n = get_Block_n_cfg_outs(bl); i < n; ++i) {
206 /* find the corresponding predecessor block. */
207 ir_node *pred = get_Block_cfg_out(bl, i);
209 irg_out_block_walk2(pred, pre, post, env);
217 /* Walks only over Block nodes in the graph. Has it's own visited
218 flag, so that it can be interleaved with the other walker. */
219 void irg_out_block_walk(ir_node *node,
220 irg_walk_func *pre, irg_walk_func *post,
223 assert(is_Block(node) || (get_irn_mode(node) == mode_X));
225 inc_irg_block_visited(current_ir_graph);
227 if (get_irn_mode(node) == mode_X)
230 irg_out_block_walk2(node, pre, post, env);
233 /*--------------------------------------------------------------------*/
234 /** Building and Removing the out datasturcture **/
236 /** The outs of a graph are allocated in a single, large array. **/
237 /** This allows to allocate and deallocate the memory for the outs **/
238 /** on demand. The large array is separated into many small ones **/
239 /** for each node. Only a single field to reference the out array **/
240 /** is stored in each node and a field referencing the large out **/
241 /** array in irgraph. The 0 field of each out array contains the **/
242 /** size of this array. This saves memory in the irnodes themselves.**/
243 /** The construction does two passes over the graph. The first pass **/
244 /** counts the overall number of outs and the outs of each node. It **/
245 /** stores the outs of each node in the out reference of the node. **/
246 /** Then the large array is allocated. The second iteration chops **/
247 /** the large array into smaller parts, sets the out edges and **/
248 /** recounts the out edges. **/
249 /** Removes Tuple nodes! **/
250 /*--------------------------------------------------------------------*/
253 /** Returns the amount of out edges for not yet visited successors. */
254 static int _count_outs(ir_node *n) {
255 int start, i, res, irn_arity;
258 n->out = (ir_node **) 1; /* Space for array size. */
260 start = is_Block(n) ? 0 : -1;
261 irn_arity = get_irn_arity(n);
262 res = irn_arity - start + 1; /* --1 or --0; 1 for array size. */
264 for (i = start; i < irn_arity; ++i) {
265 /* Optimize Tuples. They annoy if walking the cfg. */
266 ir_node *pred = skip_Tuple(get_irn_n(n, i));
267 set_irn_n(n, i, pred);
269 /* count outs for successors */
270 if (irn_not_visited(pred))
271 res += _count_outs(pred);
274 pred->out = (ir_node **)INT_TO_PTR(PTR_TO_INT(pred->out) + 1);
280 /** Returns the amount of out edges for not yet visited successors.
281 * This version handles some special nodes like irg_frame, irg_args etc.
283 static int count_outs(ir_graph *irg) {
287 inc_irg_visited(irg);
288 res = _count_outs(get_irg_end(irg));
290 /* now handle special nodes */
291 n = get_irg_frame(irg);
292 if (irn_not_visited(n)) {
293 n->out = (ir_node **)1;
297 n = get_irg_args(irg);
298 if (irn_not_visited(n)) {
299 n->out = (ir_node **)1;
307 * Enter memory for the outs to a node.
309 * @param n current node
310 * @param free current free address in the chunk allocated for the outs
312 * @return The next free address
314 static ir_node **_set_out_edges(ir_node *n, ir_node **free) {
315 int n_outs, start, i, irn_arity;
318 set_irn_visited(n, get_irg_visited(current_ir_graph));
320 /* Allocate my array */
321 n_outs = PTR_TO_INT(n->out);
325 #endif /* defined DEBUG_libfirm */
327 /* We count the successors again, the space will be sufficient.
328 We use this counter to remember the position for the next back
330 n->out[0] = (ir_node *)0;
332 start = is_Block(n) ? 0 : -1;
333 irn_arity = get_irn_arity(n);
335 for (i = start; i < irn_arity; ++i) {
336 pred = get_irn_n(n, i);
338 if (get_irn_visited(pred) < get_irg_visited(current_ir_graph))
339 free = _set_out_edges(pred, free);
340 /* Remember our back edge */
341 pred->out[get_irn_n_outs(pred)+1] = n;
342 pred->out[0] = INT_TO_PTR(get_irn_n_outs(pred) + 1);
348 * Enter memory for the outs to a node. Handles special nodes
350 * @param irg the graph
351 * @param free current free address in the chunk allocated for the outs
353 * @return The next free address
355 static ir_node **set_out_edges(ir_graph *irg, ir_node **free) {
356 ir_node *n, *special[2];
359 inc_irg_visited(irg);
360 free = _set_out_edges(get_irg_end(irg), free);
362 /* handle special nodes */
363 special[0] = get_irg_frame(irg);
364 special[1] = get_irg_args(irg);
366 for (i = 1; i >= 0; --i) {
369 if (get_irn_visited(n) < get_irg_visited(current_ir_graph)) {
370 n_outs = PTR_TO_INT(n->out);
374 #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.
388 static INLINE void fix_start_proj(ir_graph *irg) {
389 ir_node *proj = NULL;
390 ir_node *startbl = get_irg_start_block(irg);
393 if (get_Block_n_cfg_outs(startbl)) {
394 for (i = get_irn_n_outs(startbl) - 1; i >= 0; --i)
395 if (get_irn_mode(get_irn_out(startbl, i)) == mode_X) {
396 proj = get_irn_out(startbl, i);
400 if (get_irn_out(proj, 0) == startbl) {
401 assert(get_irn_n_outs(proj) == 2);
402 set_irn_out(proj, 0, get_irn_out(proj, 1));
403 set_irn_out(proj, 1, startbl);
408 /* compute the outs for a given graph */
409 void compute_irg_outs(ir_graph *irg) {
410 ir_graph *rem = current_ir_graph;
412 ir_node **end = NULL; /* Only for debugging */
414 current_ir_graph = irg;
416 /* Update graph state */
417 assert(get_irg_phase_state(current_ir_graph) != phase_building);
419 if (current_ir_graph->outs_state != outs_none)
420 free_irg_outs(current_ir_graph);
422 /* This first iteration counts the overall number of out edges and the
423 number of out edges for each node. */
424 n_out_edges = count_outs(irg);
426 /* allocate memory for all out edges. */
427 irg->outs = xcalloc(n_out_edges, sizeof(irg->outs[0]));
429 irg->n_outs = n_out_edges;
430 #endif /* defined DEBUG_libfirm */
432 /* The second iteration splits the irg->outs array into smaller arrays
433 for each node and writes the back edges into this array. */
434 end = set_out_edges(irg, irg->outs);
436 /* Check how much memory we have used */
437 assert (end == (irg->outs + n_out_edges));
439 /* We want that the out of ProjX from Start contains the next block at
440 position 1, the Start block at position 2. This is necessary for
441 the out block walker. */
444 current_ir_graph->outs_state = outs_consistent;
445 current_ir_graph = rem;
448 void assure_irg_outs(ir_graph *irg) {
449 if (get_irg_outs_state(irg) != outs_consistent)
450 compute_irg_outs(irg);
453 void compute_irp_outs(void) {
455 for (i = get_irp_n_irgs() -1; i >= 0; --i)
456 compute_irg_outs(get_irp_irg(i));
459 void free_irp_outs(void) {
461 for (i = get_irp_n_irgs() -1; i >= 0; --i)
462 free_irg_outs(get_irp_irg(i));
466 /*------------------------------------------------------------*
467 * This computes the outedges for in interprocedural graph. *
468 * There is one quirk: *
469 * The number of the outedges for each node is saved in *
470 * the first member of the ir_node** array. Maybe we should *
471 * change this to make it more portable... *
472 *------------------------------------------------------------*/
476 * Inits the number of outedges for each node
479 static void init_count(ir_node * node, void *env) {
480 node->out = (ir_node **) 1; /* 1 for the array size */
485 * Adjusts the out edge count for its predecessors
486 * and adds the current arity to the overall count,
487 * which is saved in "env"
489 static void node_arity_count(ir_node * node, void * env) {
490 int *anz = (int *) env, arity, n_outs, i, start;
493 arity = get_irn_arity(node);
494 start = (is_Block(node)) ? 0 : -1;
496 n_outs = 1 + arity + (-start); // ((is_Block(node)) ? 0 : 1); // Why + 1??
499 for(i = start; i < arity; i++) {
500 succ = get_irn_n(node, i);
501 succ->out = (ir_node **)INT_TO_PTR(PTR_TO_INT(succ->out) + 1);
507 * Inits all nodes for setting the outedges
508 * Returns the overall count of edges
510 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) {
527 ir_node ***free = (ir_node ***) env;
529 /* Allocate my array */
530 n_outs = PTR_TO_INT(node->out); /* We wrote the count here in count_ip_outs */
531 dummy_count += n_outs;
532 assert(dummy_count <= global_count && "More outedges than initially counted!");
534 *free = &((*free)[n_outs]);
535 /* We count the successors again, the space will be sufficient.
536 We use this counter to remember the position for the next back
538 node -> out[0] = (ir_node *) 0;
543 * Adds an outedge from the predecessor to the
546 static void set_out_pointer(ir_node * node, void * env) {
547 int i, arity = get_irn_arity(node);
549 int start = (!is_Block(node)) ? -1 : 0;
551 for (i = start; i < arity; ++i) {
552 succ = get_irn_n(node, i);
553 succ->out[get_irn_n_outs(succ)+1] = node;
554 succ->out[0] = INT_TO_PTR(get_irn_n_outs(succ) + 1);
560 * Sets the outedges for all nodes.
562 void set_ip_outs(void) {
563 ir_node **outedge_array = get_irp_ip_outedges();
564 cg_walk(set_array_pointer, set_out_pointer, (void *) &outedge_array);
570 * Counts the outedges, allocates memory to save the
571 * outedges and fills this outedge array in interprocedural
574 void compute_ip_outs(void) {
578 assert(get_irp_ip_view_state() == ip_view_valid &&
579 "Cannot construct outs for invalid ip view.");
581 if (irp->outs_state != outs_none) {
585 global_count = n_out_edges = count_ip_outs();
586 out_edges = xcalloc(n_out_edges, sizeof(out_edges[0]));
587 set_irp_ip_outedges(out_edges);
591 void free_ip_outs(void) {
592 ir_node **out_edges = get_irp_ip_outedges();
593 if (out_edges != NULL) {
595 set_irp_ip_outedges(NULL);
597 irp->outs_state = outs_none;
601 void free_irg_outs(ir_graph *irg) {
602 /* current_ir_graph->outs_state = outs_none; */
603 irg->outs_state = outs_none;
607 memset(irg->outs, 0, irg->n_outs);
608 #endif /* defined DEBUG_libfirm */
613 #endif /* defined DEBUG_libfirm */
617 /* when debugging, *always* reset all nodes' outs! irg->outs might
618 have been lying to us */
619 irg_walk_graph (irg, reset_outs, NULL, NULL);
620 #endif /* defined DEBUG_libfirm */