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
32 #include "irgraph_t.h" /* To access irg->outs field (which is private to this module)
33 without public access routine */
37 /**********************************************************************/
38 /** Accessing the out datastructures **/
39 /**********************************************************************/
41 static void reset_outs (ir_node *node, void *unused)
49 /* returns the number of successors of the node: */
50 INLINE int get_irn_n_outs (ir_node *node) {
52 assert (node->out_valid);
54 return (int)(node->out[0]);
57 /* Access successor n */
58 INLINE ir_node *get_irn_out (ir_node *node, int pos) {
60 assert(pos >= 0 && pos < get_irn_n_outs(node));
62 assert (node->out_valid);
64 return node->out[pos+1];
67 INLINE void set_irn_out (ir_node *node, int pos, ir_node *out) {
69 assert(pos >= 0 && pos < get_irn_n_outs(node));
71 assert (node->out_valid);
73 node->out[pos+1] = out;
77 INLINE int get_Block_n_cfg_outs (ir_node *bl) {
78 int i, n_cfg_outs = 0;
79 assert(bl && (get_irn_op(bl) == op_Block));
81 assert (bl->out_valid);
83 for (i = 0; i < (int)bl->out[0]; i++)
84 if ((intern_get_irn_mode(bl->out[i+1]) == mode_X) &&
85 (intern_get_irn_op(bl->out[i+1]) != op_End)) n_cfg_outs++;
90 INLINE ir_node *get_Block_cfg_out (ir_node *bl, int pos) {
92 assert(bl && (get_irn_op(bl) == op_Block));
94 assert (bl->out_valid);
96 for (i = 0; i < (int)bl->out[0]; i++)
97 if ((intern_get_irn_mode(bl->out[i+1]) == mode_X) &&
98 (intern_get_irn_op(bl->out[i+1]) != op_End)) {
100 ir_node *cfop = bl->out[i+1];
101 return cfop->out[0+1];
109 void irg_out_walk_2(ir_node *node, irg_walk_func *pre,
110 irg_walk_func *post, void *env) {
115 assert(get_irn_visited(node) < get_irg_visited(current_ir_graph));
117 set_irn_visited(node, get_irg_visited(current_ir_graph));
119 if (pre) pre(node, env);
121 for (i = 0; i < get_irn_n_outs(node); i++) {
122 succ = get_irn_out(node, i);
123 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
124 irg_out_walk_2(succ, pre, post, env);
127 if (post) post(node, env);
132 void irg_out_walk(ir_node *node,
133 irg_walk_func *pre, irg_walk_func *post,
136 if (get_irg_outs_state(current_ir_graph) != no_outs) {
137 inc_irg_visited (current_ir_graph);
138 irg_out_walk_2(node, pre, post, env);
143 void irg_out_block_walk2(ir_node *bl,
144 irg_walk_func *pre, irg_walk_func *post,
148 if(get_Block_block_visited(bl) < get_irg_block_visited(current_ir_graph)) {
149 set_Block_block_visited(bl, get_irg_block_visited(current_ir_graph));
154 for(i = 0; i < get_Block_n_cfg_outs(bl); i++) {
155 /* find the corresponding predecessor block. */
156 ir_node *pred = get_Block_cfg_out(bl, i);
158 irg_out_block_walk2(pred, pre, post, env);
167 /* Walks only over Block nodes in the graph. Has it's own visited
168 flag, so that it can be interleaved with the other walker. */
169 void irg_out_block_walk(ir_node *node,
170 irg_walk_func *pre, irg_walk_func *post,
173 assert((get_irn_op(node) == op_Block) || (intern_get_irn_mode(node) == mode_X));
175 inc_irg_block_visited(current_ir_graph);
177 if (intern_get_irn_mode(node) == mode_X) node = node->out[1];
179 irg_out_block_walk2(node, pre, post, env);
185 /**********************************************************************/
186 /** Building and Removing the out datasturcture **/
188 /** The outs of a graph are allocated in a single, large array. **/
189 /** This allows to allocate and deallocate the memory for the outs **/
190 /** on demand. The large array is separated into many small ones **/
191 /** for each node. Only a single field to reference the out array **/
192 /** is stored in each node and a field referencing the large out **/
193 /** array in irgraph. The 0 field of each out array contains the **/
194 /** size of this array. This saves memory in the irnodes themselves.**/
195 /** The construction does two passes over the graph. The first pass **/
196 /** counts the overall number of outs and the outs of each node. It **/
197 /** stores the outs of each node in the out reference of the node. **/
198 /** Then the large array is allocated. The second iteration chops **/
199 /** the large array into smaller parts, sets the out edges and **/
200 /** recounts the out edges. **/
201 /** Removes Tuple nodes! **/
202 /**********************************************************************/
205 /* Returns the amount of out edges for not yet visited successors. */
206 static int count_outs(ir_node *n) {
207 int start, i, res, irn_arity;
210 set_irn_visited(n, get_irg_visited(current_ir_graph));
211 n->out = (ir_node **) 1; /* Space for array size. */
213 if ((intern_get_irn_op(n) == op_Block)) start = 0; else start = -1;
214 irn_arity = intern_get_irn_arity(n);
215 res = irn_arity - start +1; /* --1 or --0; 1 for array size. */
216 for (i = start; i < irn_arity; i++) {
217 /* Optimize Tuples. They annoy if walking the cfg. */
218 succ = skip_Tuple(intern_get_irn_n(n, i));
219 set_irn_n(n, i, succ);
220 /* count outs for successors */
221 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph)) {
222 res += count_outs(succ);
225 succ->out = (ir_node **)( (int)succ->out +1);
230 static ir_node **set_out_edges(ir_node *n, ir_node **free) {
231 int n_outs, start, i, irn_arity;
234 set_irn_visited(n, get_irg_visited(current_ir_graph));
236 /* Allocate my array */
237 n_outs = (int) n->out;
242 free = &free[n_outs];
243 /* We count the successors again, the space will be sufficient.
244 We use this counter to remember the position for the next back
246 n->out[0] = (ir_node *)0;
248 if (intern_get_irn_op(n) == op_Block) start = 0; else start = -1;
249 irn_arity = intern_get_irn_arity(n);
250 for (i = start; i < irn_arity; i++) {
251 succ = intern_get_irn_n(n, i);
253 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
254 free = set_out_edges(succ, free);
255 /* Remember our back edge */
256 succ->out[get_irn_n_outs(succ)+1] = n;
257 succ->out[0] = (ir_node *) (get_irn_n_outs(succ) + 1);
262 static INLINE void fix_start_proj(ir_graph *irg) {
263 ir_node *proj = NULL, *startbl;
265 if (get_Block_n_cfg_outs(get_irg_start_block(irg))) {
266 startbl = get_irg_start_block(irg);
267 for (i = 0; i < get_irn_n_outs(startbl); i++)
268 if (intern_get_irn_mode(get_irn_out(startbl, i)) == mode_X)
269 proj = get_irn_out(startbl, i);
270 if (get_irn_out(proj, 0) == startbl) {
271 assert(get_irn_n_outs(proj) == 2);
272 set_irn_out(proj, 0, get_irn_out(proj, 1));
273 set_irn_out(proj, 1, startbl);
278 void compute_outs(ir_graph *irg) {
279 ir_graph *rem = current_ir_graph;
283 current_ir_graph = irg;
285 /* Update graph state */
286 assert(get_irg_phase_state(current_ir_graph) != phase_building);
287 if (current_ir_graph->outs_state != no_outs) free_outs(current_ir_graph);
288 current_ir_graph->outs_state = outs_consistent;
290 /* This first iteration counts the overall number of out edges and the
291 number of out edges for each node. */
292 inc_irg_visited(irg);
293 n_out_edges = count_outs(get_irg_end(irg));
295 /* allocate memory for all out edges. */
296 irg->outs = (ir_node **) xmalloc (n_out_edges * sizeof(ir_node *));
297 irg->n_outs = n_out_edges;
299 /* The second iteration splits the irg->outs array into smaller arrays
300 for each node and writes the back edges into this array. */
301 inc_irg_visited(irg);
302 end = set_out_edges(get_irg_end(irg), irg->outs);
304 /* Check how much memory we have used */
305 assert (end == (irg->outs + n_out_edges));
307 /* We want that the out of ProjX from Start contains the next block at
308 position 1, the Start block at position 2. This is necessary for
309 the out block walker. */
312 current_ir_graph = rem;
318 /****************************************************************
319 ** This computes the outedges for in interprocedural graph. **
320 ** There is one quirk: **
321 ** The number of the outedges for each node is saved in **
322 ** the first member of the ir_node** array. Maybe we should **
323 ** change this to make it more portable... **
324 ****************************************************************/
327 /* ------------------------------------------
328 Inits the number of outedges for each node
330 ------------------------------------------ */
332 static void init_count(ir_node * node, void * env)
334 node->out = (ir_node **) 1; /* 1 for the array size */
338 /* -----------------------------------------------
339 Adjusts the out edge count for its predecessors
340 and adds the current arity to the overall count,
341 which is saved in "env"
342 ------------------------------------------------ */
344 static void node_arity_count(ir_node * node, void * env)
346 int *anz = (int *) env, arity, i, start;
349 arity = 1 + intern_get_irn_arity(node)
350 + ((is_Block(node)) ? 0 : 1);
353 start = (is_Block(node)) ? 0 : -1;
354 for(i = start; i < intern_get_irn_arity(node); i++)
356 succ = intern_get_irn_n(node, i);
357 succ->out = (ir_node **)((int)succ->out + 1);
362 /* ----------------------------------------
363 Inits all nodes for setting the outedges
364 Returns the overall count of edges
365 ---------------------------------------- */
367 int count_ip_outs(void) {
371 cg_walk(init_count, node_arity_count, &res);
376 int dummy_count = 0, global_count; /* Only for debugging */
378 /* ---------------------------------------------
379 For each node: Sets the pointer to array
380 in which the outedges are written later.
381 The current array start is transported in env
382 --------------------------------------------- */
384 static void set_array_pointer(ir_node *node, void *env) {
387 ir_node ***free = (ir_node ***) env;
389 /* Allocate my array */
390 n_outs = (int) node -> out; /* We wrote the count here in count_ip_outs */
391 dummy_count += n_outs;
392 assert(dummy_count <= global_count && "More outedges than initially counted!");
394 *free = &((*free)[n_outs]);
395 /* We count the successors again, the space will be sufficient.
396 We use this counter to remember the position for the next back
398 node -> out[0] = (ir_node *) 0;
402 /* -------------------------------------------
403 Adds an outedge from the predecessor to the
405 ------------------------------------------- */
407 static void set_out_pointer(ir_node * node, void * env) {
410 int start = (!is_Block(node)) ? -1 : 0;
412 for(i = start; i < intern_get_irn_arity(node); i++)
414 succ = intern_get_irn_n(node, i);
415 succ->out[get_irn_n_outs(succ)+1] = node;
416 succ->out[0] = (ir_node *) (get_irn_n_outs(succ) + 1);
421 /* -------------------------------
422 Sets the outedges for all nodes.
423 -------------------------------- */
425 void set_ip_outs(void)
427 ir_node **outedge_array = get_irp_ip_outedges();
428 cg_walk(set_array_pointer, set_out_pointer, (void *) &outedge_array);
433 /* --------------------------------------------------------
434 Counts the outedges, allocates memory to save the
435 outedges and fills this outedge array in interprocedural
437 -------------------------------------------------------- */
439 void compute_ip_outs(void) {
444 assert(get_irp_ip_view_state() == ip_view_valid &&
445 "Cannot construct outs for invalid ip view.");
447 if (irp->outs_state != no_outs) free_ip_outs();
449 global_count = n_out_edges = count_ip_outs();
450 out_edges = (ir_node **) malloc (n_out_edges * sizeof(ir_node *));
451 set_irp_ip_outedges(out_edges);
455 void free_ip_outs(void)
457 ir_node **out_edges = get_irp_ip_outedges();
458 if (out_edges != NULL)
461 set_irp_ip_outedges(NULL);
463 irp->outs_state = no_outs;
467 void free_outs(ir_graph *irg) {
469 /* current_ir_graph->outs_state = no_outs; */
470 irg->outs_state = no_outs;
473 bzero (irg->outs, irg->n_outs);
479 irg_walk (get_irg_end_block (irg), reset_outs, NULL, NULL);