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"
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 /** Clear the outs of a node */
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 int get_irn_n_outs (ir_node *node) {
58 assert(node && node->kind == k_ir_node);
60 /* assert (node->out_valid); */
61 #endif /* defined DEBUG_libfirm */
62 return (int)(node->out[0]);
65 /* Access successor n */
66 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 void set_irn_out (ir_node *node, int pos, ir_node *out) {
76 assert(pos >= 0 && pos < get_irn_n_outs(node));
78 node->out_valid = 1; /* assume that this function is used correctly */
79 #endif /* defined DEBUG_libfirm */
80 node->out[pos+1] = out;
84 int get_Block_n_cfg_outs(ir_node *bl) {
85 int i, n_cfg_outs = 0;
86 assert(bl && is_Block(bl));
88 assert (bl->out_valid);
89 #endif /* defined DEBUG_libfirm */
90 for (i = 1; i <= (int)bl->out[0]; i++)
91 if ((get_irn_mode(bl->out[i]) == mode_X) &&
92 (get_irn_op(bl->out[i]) != op_End))
98 ir_node *get_Block_cfg_out(ir_node *bl, int pos) {
100 assert(bl && (get_irn_op(bl) == op_Block));
102 assert (bl->out_valid);
103 #endif /* defined DEBUG_libfirm */
104 for (i = 1; i <= (int)bl->out[0]; i++)
105 if ((get_irn_mode(bl->out[i]) == mode_X) &&
106 (get_irn_op(bl->out[i]) != op_End)) {
107 if (out_pos == pos) {
108 ir_node *cfop = bl->out[i];
116 static 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) != outs_none) {
144 inc_irg_visited (current_ir_graph);
145 irg_out_walk_2(node, pre, post, env);
150 static 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 n->out = (ir_node **) 1; /* Space for array size. */
219 start = is_Block(n) ? 0 : -1;
220 irn_arity = get_irn_arity(n);
221 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 ir_node *pred = skip_Tuple(get_irn_n(n, i));
226 set_irn_n(n, i, pred);
228 /* count outs for successors */
229 if (irn_not_visited(pred))
230 res += _count_outs(pred);
233 pred->out = (ir_node **)( (int)pred->out + 1);
239 /** Returns the amount of out edges for not yet visited successors.
240 * This version handles some special nodes like irg_frame etc.
242 static int count_outs(ir_graph *irg) {
246 inc_irg_visited(irg);
247 res = _count_outs(get_irg_end(irg));
249 /* now handle special nodes */
250 n = get_irg_frame(irg);
251 if (irn_not_visited(n)) {
252 n->out = (ir_node **)1;
260 * Enter memory for the outs to a node.
262 * @param n current node
263 * @param free current free address in the chunk allocated for the outs
265 * @return The next free address
267 static ir_node **_set_out_edges(ir_node *n, ir_node **free) {
268 int n_outs, start, i, irn_arity;
271 set_irn_visited(n, get_irg_visited(current_ir_graph));
273 /* Allocate my array */
274 n_outs = (int) n->out;
278 #endif /* defined DEBUG_libfirm */
280 /* We count the successors again, the space will be sufficient.
281 We use this counter to remember the position for the next back
283 n->out[0] = (ir_node *)0;
285 start = is_Block(n) ? 0 : -1;
286 irn_arity = get_irn_arity(n);
288 for (i = start; i < irn_arity; i++) {
289 pred = get_irn_n(n, i);
291 if (get_irn_visited(pred) < get_irg_visited(current_ir_graph))
292 free = _set_out_edges(pred, free);
293 /* Remember our back edge */
294 pred->out[get_irn_n_outs(pred)+1] = n;
295 pred->out[0] = (ir_node *) (get_irn_n_outs(pred) + 1);
301 * Enter memory for the outs to a node. Handles special nodes
303 * @param irg the graph
304 * @param free current free address in the chunk allocated for the outs
306 * @return The next free address
308 static ir_node **set_out_edges(ir_graph *irg, ir_node **free) {
312 inc_irg_visited(irg);
313 free = _set_out_edges(get_irg_end(irg), free);
315 n = get_irg_frame(irg);
316 if (get_irn_visited(n) < get_irg_visited(current_ir_graph)) {
317 n_outs = (int)n->out;
321 #endif /* defined DEBUG_libfirm */
329 /* We want that the out of ProjX from Start contains the next block at
330 position 1, the Start block at position 2. This is necessary for
331 the out block walker. */
332 static INLINE void fix_start_proj(ir_graph *irg) {
333 ir_node *proj = NULL;
334 ir_node *startbl = get_irg_start_block(irg);
337 if (get_Block_n_cfg_outs(startbl)) {
338 for (i = 0; i < get_irn_n_outs(startbl); i++)
339 if (get_irn_mode(get_irn_out(startbl, i)) == mode_X) {
340 proj = get_irn_out(startbl, i);
344 if (get_irn_out(proj, 0) == startbl) {
345 assert(get_irn_n_outs(proj) == 2);
346 set_irn_out(proj, 0, get_irn_out(proj, 1));
347 set_irn_out(proj, 1, startbl);
352 /* compute the outs for a given graph */
353 void compute_irg_outs(ir_graph *irg) {
354 ir_graph *rem = current_ir_graph;
356 ir_node **end = NULL; /* Only for debugging */
358 current_ir_graph = irg;
360 /* Update graph state */
361 assert(get_irg_phase_state(current_ir_graph) != phase_building);
363 if (current_ir_graph->outs_state != outs_none)
364 free_irg_outs(current_ir_graph);
365 current_ir_graph->outs_state = outs_consistent;
367 /* This first iteration counts the overall number of out edges and the
368 number of out edges for each node. */
369 n_out_edges = count_outs(irg);
371 /* allocate memory for all out edges. */
372 irg->outs = xcalloc(n_out_edges, sizeof(irg->outs[0]));
374 irg->n_outs = n_out_edges;
375 #endif /* defined DEBUG_libfirm */
377 /* The second iteration splits the irg->outs array into smaller arrays
378 for each node and writes the back edges into this array. */
379 end = set_out_edges(irg, irg->outs);
381 /* Check how much memory we have used */
382 assert (end == (irg->outs + n_out_edges));
384 /* We want that the out of ProjX from Start contains the next block at
385 position 1, the Start block at position 2. This is necessary for
386 the out block walker. */
389 current_ir_graph = rem;
392 void compute_irp_outs(void) {
393 int i, n_irgs = get_irp_n_irgs();
394 for (i = 0; i < n_irgs; ++i)
395 compute_irg_outs(get_irp_irg(i));
397 void free_irp_outs(void) {
398 int i, n_irgs = get_irp_n_irgs();
399 for (i = 0; i < n_irgs; ++i)
400 free_irg_outs(get_irp_irg(i));
404 /*------------------------------------------------------------*
405 * This computes the outedges for in interprocedural graph. *
406 * There is one quirk: *
407 * The number of the outedges for each node is saved in *
408 * the first member of the ir_node** array. Maybe we should *
409 * change this to make it more portable... *
410 *------------------------------------------------------------*/
414 * Inits the number of outedges for each node
417 static void init_count(ir_node * node, void *env) {
418 node->out = (ir_node **) 1; /* 1 for the array size */
423 * Adjusts the out edge count for its predecessors
424 * and adds the current arity to the overall count,
425 * which is saved in "env"
427 static void node_arity_count(ir_node * node, void * env)
429 int *anz = (int *) env, arity, n_outs, i, start;
432 arity = get_irn_arity(node);
433 start = (is_Block(node)) ? 0 : -1;
435 n_outs = 1 + arity + (-start); // ((is_Block(node)) ? 0 : 1); // Why + 1??
438 for(i = start; i < arity; i++) {
439 succ = get_irn_n(node, i);
440 succ->out = (ir_node **)((int)succ->out + 1);
446 * Inits all nodes for setting the outedges
447 * Returns the overall count of edges
449 int count_ip_outs(void) {
453 cg_walk(init_count, node_arity_count, &res);
458 static int dummy_count = 0, global_count; /* Only for debugging */
461 * For each node: Sets the pointer to array
462 * in which the outedges are written later.
463 * The current array start is transported in env
465 static void set_array_pointer(ir_node *node, void *env) {
468 ir_node ***free = (ir_node ***) env;
470 /* Allocate my array */
471 n_outs = (int) node -> out; /* We wrote the count here in count_ip_outs */
472 dummy_count += n_outs;
473 assert(dummy_count <= global_count && "More outedges than initially counted!");
475 *free = &((*free)[n_outs]);
476 /* We count the successors again, the space will be sufficient.
477 We use this counter to remember the position for the next back
479 node -> out[0] = (ir_node *) 0;
484 * Adds an outedge from the predecessor to the
487 static void set_out_pointer(ir_node * node, void * env) {
488 int i, arity = get_irn_arity(node);
490 int start = (!is_Block(node)) ? -1 : 0;
492 for(i = start; i < arity; i++) {
493 succ = get_irn_n(node, i);
494 succ->out[get_irn_n_outs(succ)+1] = node;
495 succ->out[0] = (ir_node *) (get_irn_n_outs(succ) + 1);
501 * Sets the outedges for all nodes.
503 void set_ip_outs(void)
505 ir_node **outedge_array = get_irp_ip_outedges();
506 cg_walk(set_array_pointer, set_out_pointer, (void *) &outedge_array);
512 * Counts the outedges, allocates memory to save the
513 * outedges and fills this outedge array in interprocedural
516 void compute_ip_outs(void) {
521 assert(get_irp_ip_view_state() == ip_view_valid &&
522 "Cannot construct outs for invalid ip view.");
524 if (irp->outs_state != outs_none) {
528 global_count = n_out_edges = count_ip_outs();
529 out_edges = xcalloc(n_out_edges, sizeof(out_edges[0]));
530 set_irp_ip_outedges(out_edges);
534 void free_ip_outs(void)
536 ir_node **out_edges = get_irp_ip_outedges();
537 if (out_edges != NULL) {
539 set_irp_ip_outedges(NULL);
541 irp->outs_state = outs_none;
545 void free_irg_outs(ir_graph *irg) {
547 /* current_ir_graph->outs_state = outs_none; */
548 irg->outs_state = outs_none;
552 memset(irg->outs, 0, irg->n_outs);
553 #endif /* defined DEBUG_libfirm */
558 #endif /* defined DEBUG_libfirm */
562 /* when debugging, *always* reset all nodes' outs! irg->outs might
563 have been lying to us */
564 irg_walk_graph (irg, reset_outs, NULL, NULL);
565 #endif /* defined DEBUG_libfirm */