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"
38 /* Note: ir_node.out_valid and ir_graph.n_outs are only present when DEBUG_libfirm is defined */
39 /* Accesses to out_valid and n_outs are fenced out to avoid breakage
40 when compiling with neither DEBUG_libfirm or NDEBUG defined */
41 #endif /* defined DEBUG_libfirm */
43 /**********************************************************************/
44 /** Accessing the out datastructures **/
45 /**********************************************************************/
47 static void reset_outs (ir_node *node, void *unused)
52 #endif /* defined DEBUG_libfirm */
55 /* returns the number of successors of the node: */
56 INLINE int get_irn_n_outs (ir_node *node) {
58 /* assert (node->out_valid); */
59 #endif /* defined DEBUG_libfirm */
60 return (int)(node->out[0]);
63 /* Access successor n */
64 INLINE ir_node *get_irn_out (ir_node *node, int pos) {
66 assert(pos >= 0 && pos < get_irn_n_outs(node));
68 /* assert (node->out_valid); */
69 #endif /* defined DEBUG_libfirm */
70 return node->out[pos+1];
73 INLINE void set_irn_out (ir_node *node, int pos, ir_node *out) {
75 assert(pos >= 0 && pos < get_irn_n_outs(node));
77 node->out_valid = 1; /* assume that this function is used correctly */
78 #endif /* defined DEBUG_libfirm */
79 node->out[pos+1] = out;
83 INLINE int get_Block_n_cfg_outs (ir_node *bl) {
84 int i, n_cfg_outs = 0;
85 assert(bl && (get_irn_op(bl) == op_Block));
87 assert (bl->out_valid);
88 #endif /* defined DEBUG_libfirm */
89 for (i = 0; i < (int)bl->out[0]; i++)
90 if ((get_irn_mode(bl->out[i+1]) == mode_X) &&
91 (get_irn_op(bl->out[i+1]) != op_End)) n_cfg_outs++;
96 INLINE ir_node *get_Block_cfg_out (ir_node *bl, int pos) {
98 assert(bl && (get_irn_op(bl) == op_Block));
100 assert (bl->out_valid);
101 #endif /* defined DEBUG_libfirm */
102 for (i = 0; i < (int)bl->out[0]; i++)
103 if ((get_irn_mode(bl->out[i+1]) == mode_X) &&
104 (get_irn_op(bl->out[i+1]) != op_End)) {
105 if (out_pos == pos) {
106 ir_node *cfop = bl->out[i+1];
107 return cfop->out[0+1];
115 void irg_out_walk_2(ir_node *node, irg_walk_func *pre,
116 irg_walk_func *post, void *env) {
121 assert(get_irn_visited(node) < get_irg_visited(current_ir_graph));
123 set_irn_visited(node, get_irg_visited(current_ir_graph));
125 if (pre) pre(node, env);
127 for (i = 0; i < get_irn_n_outs(node); i++) {
128 succ = get_irn_out(node, i);
129 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
130 irg_out_walk_2(succ, pre, post, env);
133 if (post) post(node, env);
138 void irg_out_walk(ir_node *node,
139 irg_walk_func *pre, irg_walk_func *post,
142 if (get_irg_outs_state(current_ir_graph) != outs_none) {
143 inc_irg_visited (current_ir_graph);
144 irg_out_walk_2(node, pre, post, env);
149 void irg_out_block_walk2(ir_node *bl,
150 irg_walk_func *pre, irg_walk_func *post,
154 if(get_Block_block_visited(bl) < get_irg_block_visited(current_ir_graph)) {
155 set_Block_block_visited(bl, get_irg_block_visited(current_ir_graph));
160 for(i = 0; i < get_Block_n_cfg_outs(bl); i++) {
161 /* find the corresponding predecessor block. */
162 ir_node *pred = get_Block_cfg_out(bl, i);
164 irg_out_block_walk2(pred, pre, post, env);
173 /* Walks only over Block nodes in the graph. Has it's own visited
174 flag, so that it can be interleaved with the other walker. */
175 void irg_out_block_walk(ir_node *node,
176 irg_walk_func *pre, irg_walk_func *post,
179 assert((get_irn_op(node) == op_Block) || (get_irn_mode(node) == mode_X));
181 inc_irg_block_visited(current_ir_graph);
183 if (get_irn_mode(node) == mode_X) node = node->out[1];
185 irg_out_block_walk2(node, pre, post, env);
191 /**********************************************************************/
192 /** Building and Removing the out datasturcture **/
194 /** The outs of a graph are allocated in a single, large array. **/
195 /** This allows to allocate and deallocate the memory for the outs **/
196 /** on demand. The large array is separated into many small ones **/
197 /** for each node. Only a single field to reference the out array **/
198 /** is stored in each node and a field referencing the large out **/
199 /** array in irgraph. The 0 field of each out array contains the **/
200 /** size of this array. This saves memory in the irnodes themselves.**/
201 /** The construction does two passes over the graph. The first pass **/
202 /** counts the overall number of outs and the outs of each node. It **/
203 /** stores the outs of each node in the out reference of the node. **/
204 /** Then the large array is allocated. The second iteration chops **/
205 /** the large array into smaller parts, sets the out edges and **/
206 /** recounts the out edges. **/
207 /** Removes Tuple nodes! **/
208 /**********************************************************************/
211 /* Returns the amount of out edges for not yet visited successors. */
212 static int count_outs(ir_node *n) {
213 int start, i, res, irn_arity;
216 set_irn_visited(n, get_irg_visited(current_ir_graph));
217 n->out = (ir_node **) 1; /* Space for array size. */
219 start = get_irn_op(n) == op_Block ? 0 : -1;
220 irn_arity = get_irn_arity(n);
221 res = irn_arity - start +1; /* --1 or --0; 1 for array size. */
222 for (i = start; i < irn_arity; i++) {
223 /* Optimize Tuples. They annoy if walking the cfg. */
224 succ = skip_Tuple(get_irn_n(n, i));
225 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);
236 static ir_node **set_out_edges(ir_node *n, ir_node **free) {
237 int n_outs, start, i, irn_arity;
240 set_irn_visited(n, get_irg_visited(current_ir_graph));
242 /* Allocate my array */
243 n_outs = (int) n->out;
247 #endif /* defined DEBUG_libfirm */
248 free = &free[n_outs];
249 /* We count the successors again, the space will be sufficient.
250 We use this counter to remember the position for the next back
252 n->out[0] = (ir_node *)0;
254 if (get_irn_op(n) == op_Block) start = 0; else start = -1;
255 irn_arity = get_irn_arity(n);
256 for (i = start; i < irn_arity; i++) {
257 succ = get_irn_n(n, i);
259 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
260 free = set_out_edges(succ, free);
261 /* Remember our back edge */
262 succ->out[get_irn_n_outs(succ)+1] = n;
263 succ->out[0] = (ir_node *) (get_irn_n_outs(succ) + 1);
268 /* We want that the out of ProjX from Start contains the next block at
269 position 1, the Start block at position 2. This is necessary for
270 the out block walker. */
271 static INLINE void fix_start_proj(ir_graph *irg) {
272 ir_node *proj = NULL;
273 ir_node *startbl = get_irg_start_block(irg);
276 if (get_Block_n_cfg_outs(startbl)) {
277 for (i = 0; i < get_irn_n_outs(startbl); i++)
278 if (get_irn_mode(get_irn_out(startbl, i)) == mode_X) {
279 proj = get_irn_out(startbl, i);
283 if (get_irn_out(proj, 0) == startbl) {
284 assert(get_irn_n_outs(proj) == 2);
285 set_irn_out(proj, 0, get_irn_out(proj, 1));
286 set_irn_out(proj, 1, startbl);
291 void compute_outs(ir_graph *irg) {
292 ir_graph *rem = current_ir_graph;
294 ir_node **end = NULL; /* Only for debugging */
296 current_ir_graph = irg;
298 /* Update graph state */
299 assert(get_irg_phase_state(current_ir_graph) != phase_building);
300 if (current_ir_graph->outs_state != outs_none) free_outs(current_ir_graph);
301 current_ir_graph->outs_state = outs_consistent;
303 /* This first iteration counts the overall number of out edges and the
304 number of out edges for each node. */
305 inc_irg_visited(irg);
306 n_out_edges = count_outs(get_irg_end(irg));
308 /* allocate memory for all out edges. */
309 irg->outs = (ir_node **) xmalloc (n_out_edges * sizeof(ir_node *));
311 irg->n_outs = n_out_edges;
312 #endif /* defined DEBUG_libfirm */
314 /* The second iteration splits the irg->outs array into smaller arrays
315 for each node and writes the back edges into this array. */
316 inc_irg_visited(irg);
317 end = set_out_edges(get_irg_end(irg), irg->outs);
320 /* Check how much memory we have used */
321 assert (end == (irg->outs + n_out_edges));
322 #endif /* defined DEBUG_libfirm */
324 /* We want that the out of ProjX from Start contains the next block at
325 position 1, the Start block at position 2. This is necessary for
326 the out block walker. */
329 current_ir_graph = rem;
335 /*------------------------------------------------------------*
336 * This computes the outedges for in interprocedural graph. *
337 * There is one quirk: *
338 * The number of the outedges for each node is saved in *
339 * the first member of the ir_node** array. Maybe we should *
340 * change this to make it more portable... *
341 *------------------------------------------------------------*/
344 /* ------------------------------------------
345 Inits the number of outedges for each node
347 ------------------------------------------ */
349 static void init_count(ir_node * node, void * env)
351 node->out = (ir_node **) 1; /* 1 for the array size */
355 /* -----------------------------------------------
356 Adjusts the out edge count for its predecessors
357 and adds the current arity to the overall count,
358 which is saved in "env"
359 ------------------------------------------------ */
361 static void node_arity_count(ir_node * node, void * env)
363 int *anz = (int *) env, arity, n_outs, i, start;
366 arity = get_irn_arity(node);
367 start = (is_Block(node)) ? 0 : -1;
369 n_outs = 1 + arity + (-start); // ((is_Block(node)) ? 0 : 1); // Why + 1??
372 for(i = start; i < arity; i++) {
373 succ = get_irn_n(node, i);
374 succ->out = (ir_node **)((int)succ->out + 1);
379 /* ----------------------------------------
380 Inits all nodes for setting the outedges
381 Returns the overall count of edges
382 ---------------------------------------- */
384 int count_ip_outs(void) {
388 cg_walk(init_count, node_arity_count, &res);
393 int dummy_count = 0, global_count; /* Only for debugging */
395 /* ---------------------------------------------
396 For each node: Sets the pointer to array
397 in which the outedges are written later.
398 The current array start is transported in env
399 --------------------------------------------- */
401 static void set_array_pointer(ir_node *node, void *env) {
404 ir_node ***free = (ir_node ***) env;
406 /* Allocate my array */
407 n_outs = (int) node -> out; /* We wrote the count here in count_ip_outs */
408 dummy_count += n_outs;
409 assert(dummy_count <= global_count && "More outedges than initially counted!");
411 *free = &((*free)[n_outs]);
412 /* We count the successors again, the space will be sufficient.
413 We use this counter to remember the position for the next back
415 node -> out[0] = (ir_node *) 0;
419 /* -------------------------------------------
420 Adds an outedge from the predecessor to the
422 ------------------------------------------- */
424 static void set_out_pointer(ir_node * node, void * env) {
425 int i, arity = get_irn_arity(node);
427 int start = (!is_Block(node)) ? -1 : 0;
429 for(i = start; i < arity; i++) {
430 succ = get_irn_n(node, i);
431 succ->out[get_irn_n_outs(succ)+1] = node;
432 succ->out[0] = (ir_node *) (get_irn_n_outs(succ) + 1);
437 /* -------------------------------
438 Sets the outedges for all nodes.
439 -------------------------------- */
441 void set_ip_outs(void)
443 ir_node **outedge_array = get_irp_ip_outedges();
444 cg_walk(set_array_pointer, set_out_pointer, (void *) &outedge_array);
449 /* --------------------------------------------------------
450 Counts the outedges, allocates memory to save the
451 outedges and fills this outedge array in interprocedural
453 -------------------------------------------------------- */
455 void compute_ip_outs(void) {
460 assert(get_irp_ip_view_state() == ip_view_valid &&
461 "Cannot construct outs for invalid ip view.");
463 if (irp->outs_state != outs_none) {
467 global_count = n_out_edges = count_ip_outs();
468 out_edges = (ir_node **) malloc (n_out_edges * sizeof(ir_node *));
469 set_irp_ip_outedges(out_edges);
473 void free_ip_outs(void)
475 ir_node **out_edges = get_irp_ip_outedges();
476 if (out_edges != NULL) {
478 set_irp_ip_outedges(NULL);
480 irp->outs_state = outs_none;
484 void free_outs(ir_graph *irg) {
486 /* current_ir_graph->outs_state = outs_none; */
487 irg->outs_state = outs_none;
491 memset(irg->outs, 0, irg->n_outs);
492 #endif /* defined DEBUG_libfirm */
497 #endif /* defined DEBUG_libfirm */
501 /* when debugging, *always* reset all nodes' outs! irg->outs might
502 have been lying to us */
503 irg_walk_graph (irg, reset_outs, NULL, NULL);
504 #endif /* defined DEBUG_libfirm */