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
25 #endif /* defined HAVE_CONFIG_H */
29 #include "irgraph_t.h"
35 /* Note: ir_node.out_valid and ir_graph.n_outs are only present when DEBUG_libfirm is defined */
36 /* Accesses to out_valid and n_outs are fenced out to avoid breakage
37 when compiling with neither DEBUG_libfirm or NDEBUG defined */
38 #endif /* defined DEBUG_libfirm */
40 /*--------------------------------------------------------------------*/
41 /** Accessing the out datastructures **/
42 /*--------------------------------------------------------------------*/
44 /** Clear the outs of a node */
45 static void reset_outs (ir_node *node, void *unused)
50 #endif /* defined DEBUG_libfirm */
53 /* returns the number of successors of the node: */
54 INLINE int get_irn_n_outs (ir_node *node) {
56 /* assert (node->out_valid); */
57 #endif /* defined DEBUG_libfirm */
58 return (int)(node->out[0]);
61 /* Access successor n */
62 INLINE ir_node *get_irn_out (ir_node *node, int pos) {
64 assert(pos >= 0 && pos < get_irn_n_outs(node));
66 /* assert (node->out_valid); */
67 #endif /* defined DEBUG_libfirm */
68 return node->out[pos+1];
71 INLINE void set_irn_out (ir_node *node, int pos, ir_node *out) {
73 assert(pos >= 0 && pos < get_irn_n_outs(node));
75 node->out_valid = 1; /* assume that this function is used correctly */
76 #endif /* defined DEBUG_libfirm */
77 node->out[pos+1] = out;
81 INLINE int get_Block_n_cfg_outs (ir_node *bl) {
82 int i, n_cfg_outs = 0;
83 assert(bl && (get_irn_op(bl) == op_Block));
85 assert (bl->out_valid);
86 #endif /* defined DEBUG_libfirm */
87 for (i = 0; i < (int)bl->out[0]; i++)
88 if ((get_irn_mode(bl->out[i+1]) == mode_X) &&
89 (get_irn_op(bl->out[i+1]) != op_End))
95 INLINE ir_node *get_Block_cfg_out (ir_node *bl, int pos) {
97 assert(bl && (get_irn_op(bl) == op_Block));
99 assert (bl->out_valid);
100 #endif /* defined DEBUG_libfirm */
101 for (i = 0; i < (int)bl->out[0]; i++)
102 if ((get_irn_mode(bl->out[i+1]) == mode_X) &&
103 (get_irn_op(bl->out[i+1]) != op_End)) {
104 if (out_pos == pos) {
105 ir_node *cfop = bl->out[i+1];
106 return cfop->out[0+1];
114 static void irg_out_walk_2(ir_node *node, irg_walk_func *pre,
115 irg_walk_func *post, void *env) {
120 assert(get_irn_visited(node) < get_irg_visited(current_ir_graph));
122 set_irn_visited(node, get_irg_visited(current_ir_graph));
124 if (pre) pre(node, env);
126 for (i = 0; i < get_irn_n_outs(node); i++) {
127 succ = get_irn_out(node, i);
128 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
129 irg_out_walk_2(succ, pre, post, env);
132 if (post) post(node, env);
137 void irg_out_walk(ir_node *node,
138 irg_walk_func *pre, irg_walk_func *post,
141 if (get_irg_outs_state(current_ir_graph) != outs_none) {
142 inc_irg_visited (current_ir_graph);
143 irg_out_walk_2(node, pre, post, env);
148 static void irg_out_block_walk2(ir_node *bl,
149 irg_walk_func *pre, irg_walk_func *post,
153 if(get_Block_block_visited(bl) < get_irg_block_visited(current_ir_graph)) {
154 set_Block_block_visited(bl, get_irg_block_visited(current_ir_graph));
159 for(i = 0; i < get_Block_n_cfg_outs(bl); i++) {
160 /* find the corresponding predecessor block. */
161 ir_node *pred = get_Block_cfg_out(bl, i);
163 irg_out_block_walk2(pred, pre, post, env);
172 /* Walks only over Block nodes in the graph. Has it's own visited
173 flag, so that it can be interleaved with the other walker. */
174 void irg_out_block_walk(ir_node *node,
175 irg_walk_func *pre, irg_walk_func *post,
178 assert((get_irn_op(node) == op_Block) || (get_irn_mode(node) == mode_X));
180 inc_irg_block_visited(current_ir_graph);
182 if (get_irn_mode(node) == mode_X) node = node->out[1];
184 irg_out_block_walk2(node, pre, post, env);
190 /*--------------------------------------------------------------------*/
191 /** Building and Removing the out datasturcture **/
193 /** The outs of a graph are allocated in a single, large array. **/
194 /** This allows to allocate and deallocate the memory for the outs **/
195 /** on demand. The large array is separated into many small ones **/
196 /** for each node. Only a single field to reference the out array **/
197 /** is stored in each node and a field referencing the large out **/
198 /** array in irgraph. The 0 field of each out array contains the **/
199 /** size of this array. This saves memory in the irnodes themselves.**/
200 /** The construction does two passes over the graph. The first pass **/
201 /** counts the overall number of outs and the outs of each node. It **/
202 /** stores the outs of each node in the out reference of the node. **/
203 /** Then the large array is allocated. The second iteration chops **/
204 /** the large array into smaller parts, sets the out edges and **/
205 /** recounts the out edges. **/
206 /** Removes Tuple nodes! **/
207 /*--------------------------------------------------------------------*/
210 /** Returns the amount of out edges for not yet visited successors. */
211 static int count_outs(ir_node *n) {
212 int start, i, res, irn_arity;
214 set_irn_visited(n, get_irg_visited(current_ir_graph));
215 n->out = (ir_node **) 1; /* Space for array size. */
217 start = is_Block(n) ? 0 : -1;
218 irn_arity = get_irn_arity(n);
219 res = irn_arity - start + 1; /* --1 or --0; 1 for array size. */
221 for (i = start; i < irn_arity; i++) {
222 /* Optimize Tuples. They annoy if walking the cfg. */
223 ir_node *succ = skip_Tuple(get_irn_n(n, i));
224 set_irn_n(n, i, succ);
226 /* count outs for successors */
227 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph)) {
228 res += count_outs(succ);
231 succ->out = (ir_node **)( (int)succ->out + 1);
237 * Enter memory for the outs to a node.
239 * @param n current node
240 * @param free current free address in the chunk allocated for the outs
242 * @return The next free address
244 static ir_node **set_out_edges(ir_node *n, ir_node **free) {
245 int n_outs, start, i, irn_arity;
248 set_irn_visited(n, get_irg_visited(current_ir_graph));
250 /* Allocate my array */
251 n_outs = (int) n->out;
255 #endif /* defined DEBUG_libfirm */
257 /* We count the successors again, the space will be sufficient.
258 We use this counter to remember the position for the next back
260 n->out[0] = (ir_node *)0;
262 start = is_Block(n) ? 0 : -1;
263 irn_arity = get_irn_arity(n);
265 for (i = start; i < irn_arity; i++) {
266 succ = get_irn_n(n, i);
268 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
269 free = set_out_edges(succ, free);
270 /* Remember our back edge */
271 succ->out[get_irn_n_outs(succ)+1] = n;
272 succ->out[0] = (ir_node *) (get_irn_n_outs(succ) + 1);
277 /* We want that the out of ProjX from Start contains the next block at
278 position 1, the Start block at position 2. This is necessary for
279 the out block walker. */
280 static INLINE void fix_start_proj(ir_graph *irg) {
281 ir_node *proj = NULL;
282 ir_node *startbl = get_irg_start_block(irg);
285 if (get_Block_n_cfg_outs(startbl)) {
286 for (i = 0; i < get_irn_n_outs(startbl); i++)
287 if (get_irn_mode(get_irn_out(startbl, i)) == mode_X) {
288 proj = get_irn_out(startbl, i);
292 if (get_irn_out(proj, 0) == startbl) {
293 assert(get_irn_n_outs(proj) == 2);
294 set_irn_out(proj, 0, get_irn_out(proj, 1));
295 set_irn_out(proj, 1, startbl);
300 /* compute the outs for a given graph */
301 void compute_outs(ir_graph *irg) {
302 ir_graph *rem = current_ir_graph;
304 ir_node **end = NULL; /* Only for debugging */
306 current_ir_graph = irg;
308 /* Update graph state */
309 assert(get_irg_phase_state(current_ir_graph) != phase_building);
311 if (current_ir_graph->outs_state != outs_none)
312 free_outs(current_ir_graph);
313 current_ir_graph->outs_state = outs_consistent;
315 /* This first iteration counts the overall number of out edges and the
316 number of out edges for each node. */
317 inc_irg_visited(irg);
318 n_out_edges = count_outs(get_irg_end(irg));
320 /* allocate memory for all out edges. */
321 irg->outs = (ir_node **) xmalloc (n_out_edges * sizeof(ir_node *));
323 irg->n_outs = n_out_edges;
324 #endif /* defined DEBUG_libfirm */
326 /* The second iteration splits the irg->outs array into smaller arrays
327 for each node and writes the back edges into this array. */
328 inc_irg_visited(irg);
329 end = set_out_edges(get_irg_end(irg), irg->outs);
331 /* Check how much memory we have used */
332 assert (end == (irg->outs + n_out_edges));
334 /* We want that the out of ProjX from Start contains the next block at
335 position 1, the Start block at position 2. This is necessary for
336 the out block walker. */
339 current_ir_graph = rem;
345 /*------------------------------------------------------------*
346 * This computes the outedges for in interprocedural graph. *
347 * There is one quirk: *
348 * The number of the outedges for each node is saved in *
349 * the first member of the ir_node** array. Maybe we should *
350 * change this to make it more portable... *
351 *------------------------------------------------------------*/
355 * Inits the number of outedges for each node
358 static void init_count(ir_node * node, void *env) {
359 node->out = (ir_node **) 1; /* 1 for the array size */
364 * Adjusts the out edge count for its predecessors
365 * and adds the current arity to the overall count,
366 * which is saved in "env"
368 static void node_arity_count(ir_node * node, void * env)
370 int *anz = (int *) env, arity, n_outs, i, start;
373 arity = get_irn_arity(node);
374 start = (is_Block(node)) ? 0 : -1;
376 n_outs = 1 + arity + (-start); // ((is_Block(node)) ? 0 : 1); // Why + 1??
379 for(i = start; i < arity; i++) {
380 succ = get_irn_n(node, i);
381 succ->out = (ir_node **)((int)succ->out + 1);
387 * Inits all nodes for setting the outedges
388 * Returns the overall count of edges
390 int count_ip_outs(void) {
394 cg_walk(init_count, node_arity_count, &res);
399 static int dummy_count = 0, global_count; /* Only for debugging */
402 * For each node: Sets the pointer to array
403 * in which the outedges are written later.
404 * The current array start is transported in env
406 static void set_array_pointer(ir_node *node, void *env) {
409 ir_node ***free = (ir_node ***) env;
411 /* Allocate my array */
412 n_outs = (int) node -> out; /* We wrote the count here in count_ip_outs */
413 dummy_count += n_outs;
414 assert(dummy_count <= global_count && "More outedges than initially counted!");
416 *free = &((*free)[n_outs]);
417 /* We count the successors again, the space will be sufficient.
418 We use this counter to remember the position for the next back
420 node -> out[0] = (ir_node *) 0;
425 * Adds an outedge from the predecessor to the
428 static void set_out_pointer(ir_node * node, void * env) {
429 int i, arity = get_irn_arity(node);
431 int start = (!is_Block(node)) ? -1 : 0;
433 for(i = start; i < arity; i++) {
434 succ = get_irn_n(node, i);
435 succ->out[get_irn_n_outs(succ)+1] = node;
436 succ->out[0] = (ir_node *) (get_irn_n_outs(succ) + 1);
442 * Sets the outedges for all nodes.
444 void set_ip_outs(void)
446 ir_node **outedge_array = get_irp_ip_outedges();
447 cg_walk(set_array_pointer, set_out_pointer, (void *) &outedge_array);
453 * Counts the outedges, allocates memory to save the
454 * outedges and fills this outedge array in interprocedural
457 void compute_ip_outs(void) {
462 assert(get_irp_ip_view_state() == ip_view_valid &&
463 "Cannot construct outs for invalid ip view.");
465 if (irp->outs_state != outs_none) {
469 global_count = n_out_edges = count_ip_outs();
470 out_edges = (ir_node **) malloc (n_out_edges * sizeof(ir_node *));
471 set_irp_ip_outedges(out_edges);
475 void free_ip_outs(void)
477 ir_node **out_edges = get_irp_ip_outedges();
478 if (out_edges != NULL) {
480 set_irp_ip_outedges(NULL);
482 irp->outs_state = outs_none;
486 void free_outs(ir_graph *irg) {
488 /* current_ir_graph->outs_state = outs_none; */
489 irg->outs_state = outs_none;
493 memset(irg->outs, 0, irg->n_outs);
494 #endif /* defined DEBUG_libfirm */
499 #endif /* defined DEBUG_libfirm */
503 /* when debugging, *always* reset all nodes' outs! irg->outs might
504 have been lying to us */
505 irg_walk_graph (irg, reset_outs, NULL, NULL);
506 #endif /* defined DEBUG_libfirm */