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.
15 /* Copyright (C) 2002 by Universitaet Karlsruhe
16 * All rights reserved.
18 * Authors: Goetz Lindenmaier
20 * irouts.c --- Compute out edges for ir nodes (also called def-use
28 #endif /* defined HAVE_CONFIG_H */
32 #include "irgraph_t.h" /* To access irg->outs field (which is private to this module)
33 without public access routine */
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 static void reset_outs (ir_node *node, void *unused)
53 #endif /* defined DEBUG_libfirm */
56 /* returns the number of successors of the node: */
57 INLINE int get_irn_n_outs (ir_node *node) {
59 assert (node->out_valid);
60 #endif /* defined DEBUG_libfirm */
61 return (int)(node->out[0]);
64 /* Access successor n */
65 INLINE 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 INLINE void set_irn_out (ir_node *node, int pos, ir_node *out) {
76 assert(pos >= 0 && pos < get_irn_n_outs(node));
78 assert (node->out_valid);
79 #endif /* defined DEBUG_libfirm */
80 node->out[pos+1] = out;
84 INLINE int get_Block_n_cfg_outs (ir_node *bl) {
85 int i, n_cfg_outs = 0;
86 assert(bl && (get_irn_op(bl) == op_Block));
88 assert (bl->out_valid);
89 #endif /* defined DEBUG_libfirm */
90 for (i = 0; i < (int)bl->out[0]; i++)
91 if ((get_irn_mode(bl->out[i+1]) == mode_X) &&
92 (get_irn_op(bl->out[i+1]) != op_End)) n_cfg_outs++;
97 INLINE ir_node *get_Block_cfg_out (ir_node *bl, int pos) {
99 assert(bl && (get_irn_op(bl) == op_Block));
101 assert (bl->out_valid);
102 #endif /* defined DEBUG_libfirm */
103 for (i = 0; i < (int)bl->out[0]; i++)
104 if ((get_irn_mode(bl->out[i+1]) == mode_X) &&
105 (get_irn_op(bl->out[i+1]) != op_End)) {
106 if (out_pos == pos) {
107 ir_node *cfop = bl->out[i+1];
108 return cfop->out[0+1];
116 void irg_out_walk_2(ir_node *node, irg_walk_func *pre,
117 irg_walk_func *post, void *env) {
122 assert(get_irn_visited(node) < get_irg_visited(current_ir_graph));
124 set_irn_visited(node, get_irg_visited(current_ir_graph));
126 if (pre) pre(node, env);
128 for (i = 0; i < get_irn_n_outs(node); i++) {
129 succ = get_irn_out(node, i);
130 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
131 irg_out_walk_2(succ, pre, post, env);
134 if (post) post(node, env);
139 void irg_out_walk(ir_node *node,
140 irg_walk_func *pre, irg_walk_func *post,
143 if (get_irg_outs_state(current_ir_graph) != no_outs) {
144 inc_irg_visited (current_ir_graph);
145 irg_out_walk_2(node, pre, post, env);
150 void irg_out_block_walk2(ir_node *bl,
151 irg_walk_func *pre, irg_walk_func *post,
155 if(get_Block_block_visited(bl) < get_irg_block_visited(current_ir_graph)) {
156 set_Block_block_visited(bl, get_irg_block_visited(current_ir_graph));
161 for(i = 0; i < get_Block_n_cfg_outs(bl); i++) {
162 /* find the corresponding predecessor block. */
163 ir_node *pred = get_Block_cfg_out(bl, i);
165 irg_out_block_walk2(pred, pre, post, env);
174 /* Walks only over Block nodes in the graph. Has it's own visited
175 flag, so that it can be interleaved with the other walker. */
176 void irg_out_block_walk(ir_node *node,
177 irg_walk_func *pre, irg_walk_func *post,
180 assert((get_irn_op(node) == op_Block) || (get_irn_mode(node) == mode_X));
182 inc_irg_block_visited(current_ir_graph);
184 if (get_irn_mode(node) == mode_X) node = node->out[1];
186 irg_out_block_walk2(node, pre, post, env);
192 /**********************************************************************/
193 /** Building and Removing the out datasturcture **/
195 /** The outs of a graph are allocated in a single, large array. **/
196 /** This allows to allocate and deallocate the memory for the outs **/
197 /** on demand. The large array is separated into many small ones **/
198 /** for each node. Only a single field to reference the out array **/
199 /** is stored in each node and a field referencing the large out **/
200 /** array in irgraph. The 0 field of each out array contains the **/
201 /** size of this array. This saves memory in the irnodes themselves.**/
202 /** The construction does two passes over the graph. The first pass **/
203 /** counts the overall number of outs and the outs of each node. It **/
204 /** stores the outs of each node in the out reference of the node. **/
205 /** Then the large array is allocated. The second iteration chops **/
206 /** the large array into smaller parts, sets the out edges and **/
207 /** recounts the out edges. **/
208 /** Removes Tuple nodes! **/
209 /**********************************************************************/
212 /* Returns the amount of out edges for not yet visited successors. */
213 static int count_outs(ir_node *n) {
214 int start, i, res, irn_arity;
217 set_irn_visited(n, get_irg_visited(current_ir_graph));
218 n->out = (ir_node **) 1; /* Space for array size. */
220 start = get_irn_op(n) == op_Block ? 0 : -1;
221 irn_arity = get_irn_arity(n);
222 res = irn_arity - start +1; /* --1 or --0; 1 for array size. */
223 for (i = start; i < irn_arity; i++) {
224 /* Optimize Tuples. They annoy if walking the cfg. */
225 succ = skip_Tuple(get_irn_n(n, i));
226 set_irn_n(n, i, succ);
227 /* count outs for successors */
228 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph)) {
229 res += count_outs(succ);
232 succ->out = (ir_node **)( (int)succ->out +1);
237 static ir_node **set_out_edges(ir_node *n, ir_node **free) {
238 int n_outs, start, i, irn_arity;
241 set_irn_visited(n, get_irg_visited(current_ir_graph));
243 /* Allocate my array */
244 n_outs = (int) n->out;
248 #endif /* defined DEBUG_libfirm */
249 free = &free[n_outs];
250 /* We count the successors again, the space will be sufficient.
251 We use this counter to remember the position for the next back
253 n->out[0] = (ir_node *)0;
255 if (get_irn_op(n) == op_Block) start = 0; else start = -1;
256 irn_arity = get_irn_arity(n);
257 for (i = start; i < irn_arity; i++) {
258 succ = get_irn_n(n, i);
260 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
261 free = set_out_edges(succ, free);
262 /* Remember our back edge */
263 succ->out[get_irn_n_outs(succ)+1] = n;
264 succ->out[0] = (ir_node *) (get_irn_n_outs(succ) + 1);
269 static INLINE void fix_start_proj(ir_graph *irg) {
270 ir_node *proj = NULL, *startbl;
272 if (get_Block_n_cfg_outs(get_irg_start_block(irg))) {
273 startbl = get_irg_start_block(irg);
274 for (i = 0; i < get_irn_n_outs(startbl); i++)
275 if (get_irn_mode(get_irn_out(startbl, i)) == mode_X)
276 proj = get_irn_out(startbl, i);
277 if (get_irn_out(proj, 0) == startbl) {
278 assert(get_irn_n_outs(proj) == 2);
279 set_irn_out(proj, 0, get_irn_out(proj, 1));
280 set_irn_out(proj, 1, startbl);
285 void compute_outs(ir_graph *irg) {
286 ir_graph *rem = current_ir_graph;
288 ir_node **end = NULL; /* Only for debugging */
290 current_ir_graph = irg;
292 /* Update graph state */
293 assert(get_irg_phase_state(current_ir_graph) != phase_building);
294 if (current_ir_graph->outs_state != no_outs) free_outs(current_ir_graph);
295 current_ir_graph->outs_state = outs_consistent;
297 /* This first iteration counts the overall number of out edges and the
298 number of out edges for each node. */
299 inc_irg_visited(irg);
300 n_out_edges = count_outs(get_irg_end(irg));
302 /* allocate memory for all out edges. */
303 irg->outs = (ir_node **) xmalloc (n_out_edges * sizeof(ir_node *));
305 irg->n_outs = n_out_edges;
306 #endif /* defined DEBUG_libfirm */
308 /* The second iteration splits the irg->outs array into smaller arrays
309 for each node and writes the back edges into this array. */
310 inc_irg_visited(irg);
311 end = set_out_edges(get_irg_end(irg), irg->outs);
314 /* Check how much memory we have used */
315 assert (end == (irg->outs + n_out_edges));
316 #endif /* defined DEBUG_libfirm */
318 /* We want that the out of ProjX from Start contains the next block at
319 position 1, the Start block at position 2. This is necessary for
320 the out block walker. */
323 current_ir_graph = rem;
329 /*------------------------------------------------------------*
330 * This computes the outedges for in interprocedural graph. *
331 * There is one quirk: *
332 * The number of the outedges for each node is saved in *
333 * the first member of the ir_node** array. Maybe we should *
334 * change this to make it more portable... *
335 *------------------------------------------------------------*/
338 /* ------------------------------------------
339 Inits the number of outedges for each node
341 ------------------------------------------ */
343 static void init_count(ir_node * node, void * env)
345 node->out = (ir_node **) 1; /* 1 for the array size */
349 /* -----------------------------------------------
350 Adjusts the out edge count for its predecessors
351 and adds the current arity to the overall count,
352 which is saved in "env"
353 ------------------------------------------------ */
355 static void node_arity_count(ir_node * node, void * env)
357 int *anz = (int *) env, arity, i, start;
360 arity = 1 + get_irn_arity(node)
361 + ((is_Block(node)) ? 0 : 1);
364 start = (is_Block(node)) ? 0 : -1;
365 for(i = start; i < get_irn_arity(node); i++) {
366 succ = get_irn_n(node, i);
367 succ->out = (ir_node **)((int)succ->out + 1);
372 /* ----------------------------------------
373 Inits all nodes for setting the outedges
374 Returns the overall count of edges
375 ---------------------------------------- */
377 int count_ip_outs(void) {
381 cg_walk(init_count, node_arity_count, &res);
386 int dummy_count = 0, global_count; /* Only for debugging */
388 /* ---------------------------------------------
389 For each node: Sets the pointer to array
390 in which the outedges are written later.
391 The current array start is transported in env
392 --------------------------------------------- */
394 static void set_array_pointer(ir_node *node, void *env) {
397 ir_node ***free = (ir_node ***) env;
399 /* Allocate my array */
400 n_outs = (int) node -> out; /* We wrote the count here in count_ip_outs */
401 dummy_count += n_outs;
402 assert(dummy_count <= global_count && "More outedges than initially counted!");
404 *free = &((*free)[n_outs]);
405 /* We count the successors again, the space will be sufficient.
406 We use this counter to remember the position for the next back
408 node -> out[0] = (ir_node *) 0;
412 /* -------------------------------------------
413 Adds an outedge from the predecessor to the
415 ------------------------------------------- */
417 static void set_out_pointer(ir_node * node, void * env) {
420 int start = (!is_Block(node)) ? -1 : 0;
422 for(i = start; i < get_irn_arity(node); i++) {
423 succ = get_irn_n(node, i);
424 succ->out[get_irn_n_outs(succ)+1] = node;
425 succ->out[0] = (ir_node *) (get_irn_n_outs(succ) + 1);
430 /* -------------------------------
431 Sets the outedges for all nodes.
432 -------------------------------- */
434 void set_ip_outs(void)
436 ir_node **outedge_array = get_irp_ip_outedges();
437 cg_walk(set_array_pointer, set_out_pointer, (void *) &outedge_array);
442 /* --------------------------------------------------------
443 Counts the outedges, allocates memory to save the
444 outedges and fills this outedge array in interprocedural
446 -------------------------------------------------------- */
448 void compute_ip_outs(void) {
453 assert(get_irp_ip_view_state() == ip_view_valid &&
454 "Cannot construct outs for invalid ip view.");
456 if (irp->outs_state != no_outs) {
460 global_count = n_out_edges = count_ip_outs();
461 out_edges = (ir_node **) malloc (n_out_edges * sizeof(ir_node *));
462 set_irp_ip_outedges(out_edges);
466 void free_ip_outs(void)
468 ir_node **out_edges = get_irp_ip_outedges();
469 if (out_edges != NULL) {
471 set_irp_ip_outedges(NULL);
473 irp->outs_state = no_outs;
477 void free_outs(ir_graph *irg) {
479 /* current_ir_graph->outs_state = no_outs; */
480 irg->outs_state = no_outs;
484 memset(irg->outs, 0, irg->n_outs);
485 #endif /* defined DEBUG_libfirm */
490 #endif /* defined DEBUG_libfirm */
494 /* when debugging, *always* reset all nodes' outs! irg->outs might
495 have been lying to us */
496 irg_walk_graph (irg, reset_outs, NULL, NULL);
497 #endif /* defined DEBUG_libfirm */