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;
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))
99 ir_node *get_Block_cfg_out(ir_node *bl, int pos) {
101 assert(bl && (get_irn_op(bl) == op_Block));
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 (get_irn_op(bl->out[i]) != op_End)) {
108 if (out_pos == pos) {
109 ir_node *cfop = bl->out[i];
117 static void irg_out_walk_2(ir_node *node, irg_walk_func *pre,
118 irg_walk_func *post, void *env) {
123 assert(get_irn_visited(node) < get_irg_visited(current_ir_graph));
125 set_irn_visited(node, get_irg_visited(current_ir_graph));
127 if (pre) pre(node, env);
129 for (i = 0; i < get_irn_n_outs(node); i++) {
130 succ = get_irn_out(node, i);
131 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
132 irg_out_walk_2(succ, pre, post, env);
135 if (post) post(node, env);
140 void irg_out_walk(ir_node *node,
141 irg_walk_func *pre, irg_walk_func *post,
144 if (get_irg_outs_state(current_ir_graph) != outs_none) {
145 inc_irg_visited (current_ir_graph);
146 irg_out_walk_2(node, pre, post, env);
151 static void irg_out_block_walk2(ir_node *bl,
152 irg_walk_func *pre, irg_walk_func *post,
156 if(get_Block_block_visited(bl) < get_irg_block_visited(current_ir_graph)) {
157 set_Block_block_visited(bl, get_irg_block_visited(current_ir_graph));
162 for(i = 0; i < get_Block_n_cfg_outs(bl); i++) {
163 /* find the corresponding predecessor block. */
164 ir_node *pred = get_Block_cfg_out(bl, i);
166 irg_out_block_walk2(pred, pre, post, env);
175 /* Walks only over Block nodes in the graph. Has it's own visited
176 flag, so that it can be interleaved with the other walker. */
177 void irg_out_block_walk(ir_node *node,
178 irg_walk_func *pre, irg_walk_func *post,
181 assert((get_irn_op(node) == op_Block) || (get_irn_mode(node) == mode_X));
183 inc_irg_block_visited(current_ir_graph);
185 if (get_irn_mode(node) == mode_X) node = node->out[1];
187 irg_out_block_walk2(node, pre, post, env);
193 /*--------------------------------------------------------------------*/
194 /** Building and Removing the out datasturcture **/
196 /** The outs of a graph are allocated in a single, large array. **/
197 /** This allows to allocate and deallocate the memory for the outs **/
198 /** on demand. The large array is separated into many small ones **/
199 /** for each node. Only a single field to reference the out array **/
200 /** is stored in each node and a field referencing the large out **/
201 /** array in irgraph. The 0 field of each out array contains the **/
202 /** size of this array. This saves memory in the irnodes themselves.**/
203 /** The construction does two passes over the graph. The first pass **/
204 /** counts the overall number of outs and the outs of each node. It **/
205 /** stores the outs of each node in the out reference of the node. **/
206 /** Then the large array is allocated. The second iteration chops **/
207 /** the large array into smaller parts, sets the out edges and **/
208 /** recounts the out edges. **/
209 /** Removes Tuple nodes! **/
210 /*--------------------------------------------------------------------*/
213 /** Returns the amount of out edges for not yet visited successors. */
214 static int _count_outs(ir_node *n) {
215 int start, i, res, irn_arity;
218 n->out = (ir_node **) 1; /* Space for array size. */
220 start = is_Block(n) ? 0 : -1;
221 irn_arity = get_irn_arity(n);
222 res = irn_arity - start + 1; /* --1 or --0; 1 for array size. */
224 for (i = start; i < irn_arity; ++i) {
225 /* Optimize Tuples. They annoy if walking the cfg. */
226 ir_node *pred = skip_Tuple(get_irn_n(n, i));
227 set_irn_n(n, i, pred);
229 /* count outs for successors */
230 if (irn_not_visited(pred))
231 res += _count_outs(pred);
234 pred->out = (ir_node **)INT_TO_PTR(PTR_TO_INT(pred->out) + 1);
240 /** Returns the amount of out edges for not yet visited successors.
241 * This version handles some special nodes like irg_frame, irg_args etc.
243 static int count_outs(ir_graph *irg) {
247 inc_irg_visited(irg);
248 res = _count_outs(get_irg_end(irg));
250 /* now handle special nodes */
251 n = get_irg_frame(irg);
252 if (irn_not_visited(n)) {
253 n->out = (ir_node **)1;
257 n = get_irg_args(irg);
258 if (irn_not_visited(n)) {
259 n->out = (ir_node **)1;
267 * Enter memory for the outs to a node.
269 * @param n current node
270 * @param free current free address in the chunk allocated for the outs
272 * @return The next free address
274 static ir_node **_set_out_edges(ir_node *n, ir_node **free) {
275 int n_outs, start, i, irn_arity;
278 set_irn_visited(n, get_irg_visited(current_ir_graph));
280 /* Allocate my array */
281 n_outs = PTR_TO_INT(n->out);
285 #endif /* defined DEBUG_libfirm */
287 /* We count the successors again, the space will be sufficient.
288 We use this counter to remember the position for the next back
290 n->out[0] = (ir_node *)0;
292 start = is_Block(n) ? 0 : -1;
293 irn_arity = get_irn_arity(n);
295 for (i = start; i < irn_arity; i++) {
296 pred = get_irn_n(n, i);
298 if (get_irn_visited(pred) < get_irg_visited(current_ir_graph))
299 free = _set_out_edges(pred, free);
300 /* Remember our back edge */
301 pred->out[get_irn_n_outs(pred)+1] = n;
302 pred->out[0] = INT_TO_PTR(get_irn_n_outs(pred) + 1);
308 * Enter memory for the outs to a node. Handles special nodes
310 * @param irg the graph
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_graph *irg, ir_node **free) {
316 ir_node *n, *special[2];
319 inc_irg_visited(irg);
320 free = _set_out_edges(get_irg_end(irg), free);
322 /* handle special nodes */
323 special[0] = get_irg_frame(irg);
324 special[1] = get_irg_args(irg);
326 for (i = 1; i >= 0; --i) {
329 if (get_irn_visited(n) < get_irg_visited(current_ir_graph)) {
330 n_outs = PTR_TO_INT(n->out);
334 #endif /* defined DEBUG_libfirm */
343 /* We want that the out of ProjX from Start contains the next block at
344 position 1, the Start block at position 2. This is necessary for
345 the out block walker. */
346 static INLINE void fix_start_proj(ir_graph *irg) {
347 ir_node *proj = NULL;
348 ir_node *startbl = get_irg_start_block(irg);
351 if (get_Block_n_cfg_outs(startbl)) {
352 for (i = 0; i < get_irn_n_outs(startbl); i++)
353 if (get_irn_mode(get_irn_out(startbl, i)) == mode_X) {
354 proj = get_irn_out(startbl, i);
358 if (get_irn_out(proj, 0) == startbl) {
359 assert(get_irn_n_outs(proj) == 2);
360 set_irn_out(proj, 0, get_irn_out(proj, 1));
361 set_irn_out(proj, 1, startbl);
366 /* compute the outs for a given graph */
367 void compute_irg_outs(ir_graph *irg) {
368 ir_graph *rem = current_ir_graph;
370 ir_node **end = NULL; /* Only for debugging */
372 current_ir_graph = irg;
374 /* Update graph state */
375 assert(get_irg_phase_state(current_ir_graph) != phase_building);
377 if (current_ir_graph->outs_state != outs_none)
378 free_irg_outs(current_ir_graph);
379 current_ir_graph->outs_state = outs_consistent;
381 /* This first iteration counts the overall number of out edges and the
382 number of out edges for each node. */
383 n_out_edges = count_outs(irg);
385 /* allocate memory for all out edges. */
386 irg->outs = xcalloc(n_out_edges, sizeof(irg->outs[0]));
388 irg->n_outs = n_out_edges;
389 #endif /* defined DEBUG_libfirm */
391 /* The second iteration splits the irg->outs array into smaller arrays
392 for each node and writes the back edges into this array. */
393 end = set_out_edges(irg, irg->outs);
395 /* Check how much memory we have used */
396 assert (end == (irg->outs + n_out_edges));
398 /* We want that the out of ProjX from Start contains the next block at
399 position 1, the Start block at position 2. This is necessary for
400 the out block walker. */
403 current_ir_graph = rem;
406 void compute_irp_outs(void) {
407 int i, n_irgs = get_irp_n_irgs();
408 for (i = 0; i < n_irgs; ++i)
409 compute_irg_outs(get_irp_irg(i));
411 void free_irp_outs(void) {
412 int i, n_irgs = get_irp_n_irgs();
413 for (i = 0; i < n_irgs; ++i)
414 free_irg_outs(get_irp_irg(i));
418 /*------------------------------------------------------------*
419 * This computes the outedges for in interprocedural graph. *
420 * There is one quirk: *
421 * The number of the outedges for each node is saved in *
422 * the first member of the ir_node** array. Maybe we should *
423 * change this to make it more portable... *
424 *------------------------------------------------------------*/
428 * Inits the number of outedges for each node
431 static void init_count(ir_node * node, void *env) {
432 node->out = (ir_node **) 1; /* 1 for the array size */
437 * Adjusts the out edge count for its predecessors
438 * and adds the current arity to the overall count,
439 * which is saved in "env"
441 static void node_arity_count(ir_node * node, void * env)
443 int *anz = (int *) env, arity, n_outs, i, start;
446 arity = get_irn_arity(node);
447 start = (is_Block(node)) ? 0 : -1;
449 n_outs = 1 + arity + (-start); // ((is_Block(node)) ? 0 : 1); // Why + 1??
452 for(i = start; i < arity; i++) {
453 succ = get_irn_n(node, i);
454 succ->out = (ir_node **)INT_TO_PTR(PTR_TO_INT(succ->out) + 1);
460 * Inits all nodes for setting the outedges
461 * Returns the overall count of edges
463 int count_ip_outs(void) {
467 cg_walk(init_count, node_arity_count, &res);
472 static int dummy_count = 0, global_count; /* Only for debugging */
475 * For each node: Sets the pointer to array
476 * in which the outedges are written later.
477 * The current array start is transported in env
479 static void set_array_pointer(ir_node *node, void *env) {
482 ir_node ***free = (ir_node ***) env;
484 /* Allocate my array */
485 n_outs = PTR_TO_INT(node->out); /* We wrote the count here in count_ip_outs */
486 dummy_count += n_outs;
487 assert(dummy_count <= global_count && "More outedges than initially counted!");
489 *free = &((*free)[n_outs]);
490 /* We count the successors again, the space will be sufficient.
491 We use this counter to remember the position for the next back
493 node -> out[0] = (ir_node *) 0;
498 * Adds an outedge from the predecessor to the
501 static void set_out_pointer(ir_node * node, void * env) {
502 int i, arity = get_irn_arity(node);
504 int start = (!is_Block(node)) ? -1 : 0;
506 for (i = start; i < arity; i++) {
507 succ = get_irn_n(node, i);
508 succ->out[get_irn_n_outs(succ)+1] = node;
509 succ->out[0] = INT_TO_PTR(get_irn_n_outs(succ) + 1);
515 * Sets the outedges for all nodes.
517 void set_ip_outs(void)
519 ir_node **outedge_array = get_irp_ip_outedges();
520 cg_walk(set_array_pointer, set_out_pointer, (void *) &outedge_array);
526 * Counts the outedges, allocates memory to save the
527 * outedges and fills this outedge array in interprocedural
530 void compute_ip_outs(void) {
535 assert(get_irp_ip_view_state() == ip_view_valid &&
536 "Cannot construct outs for invalid ip view.");
538 if (irp->outs_state != outs_none) {
542 global_count = n_out_edges = count_ip_outs();
543 out_edges = xcalloc(n_out_edges, sizeof(out_edges[0]));
544 set_irp_ip_outedges(out_edges);
548 void free_ip_outs(void)
550 ir_node **out_edges = get_irp_ip_outedges();
551 if (out_edges != NULL) {
553 set_irp_ip_outedges(NULL);
555 irp->outs_state = outs_none;
559 void free_irg_outs(ir_graph *irg) {
561 /* current_ir_graph->outs_state = outs_none; */
562 irg->outs_state = outs_none;
566 memset(irg->outs, 0, irg->n_outs);
567 #endif /* defined DEBUG_libfirm */
572 #endif /* defined DEBUG_libfirm */
576 /* when debugging, *always* reset all nodes' outs! irg->outs might
577 have been lying to us */
578 irg_walk_graph (irg, reset_outs, NULL, NULL);
579 #endif /* defined DEBUG_libfirm */