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 */
38 /**********************************************************************/
39 /** Accessing the out datastructures **/
40 /**********************************************************************/
42 static void reset_outs (ir_node *node, void *unused)
50 /* returns the number of successors of the node: */
51 INLINE int get_irn_n_outs (ir_node *node) {
53 assert (node->out_valid);
55 return (int)(node->out[0]);
58 /* Access successor n */
59 INLINE ir_node *get_irn_out (ir_node *node, int pos) {
61 assert(pos >= 0 && pos < get_irn_n_outs(node));
63 assert (node->out_valid);
65 return node->out[pos+1];
68 INLINE void set_irn_out (ir_node *node, int pos, ir_node *out) {
70 assert(pos >= 0 && pos < get_irn_n_outs(node));
72 assert (node->out_valid);
74 node->out[pos+1] = out;
78 INLINE int get_Block_n_cfg_outs (ir_node *bl) {
79 int i, n_cfg_outs = 0;
80 assert(bl && (get_irn_op(bl) == op_Block));
82 assert (bl->out_valid);
84 for (i = 0; i < (int)bl->out[0]; i++)
85 if ((get_irn_mode(bl->out[i+1]) == mode_X) &&
86 (get_irn_op(bl->out[i+1]) != op_End)) n_cfg_outs++;
91 INLINE ir_node *get_Block_cfg_out (ir_node *bl, int pos) {
93 assert(bl && (get_irn_op(bl) == op_Block));
95 assert (bl->out_valid);
97 for (i = 0; i < (int)bl->out[0]; i++)
98 if ((get_irn_mode(bl->out[i+1]) == mode_X) &&
99 (get_irn_op(bl->out[i+1]) != op_End)) {
100 if (out_pos == pos) {
101 ir_node *cfop = bl->out[i+1];
102 return cfop->out[0+1];
110 void irg_out_walk_2(ir_node *node, irg_walk_func *pre,
111 irg_walk_func *post, void *env) {
116 assert(get_irn_visited(node) < get_irg_visited(current_ir_graph));
118 set_irn_visited(node, get_irg_visited(current_ir_graph));
120 if (pre) pre(node, env);
122 for (i = 0; i < get_irn_n_outs(node); i++) {
123 succ = get_irn_out(node, i);
124 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
125 irg_out_walk_2(succ, pre, post, env);
128 if (post) post(node, env);
133 void irg_out_walk(ir_node *node,
134 irg_walk_func *pre, irg_walk_func *post,
137 if (get_irg_outs_state(current_ir_graph) != no_outs) {
138 inc_irg_visited (current_ir_graph);
139 irg_out_walk_2(node, pre, post, env);
144 void irg_out_block_walk2(ir_node *bl,
145 irg_walk_func *pre, irg_walk_func *post,
149 if(get_Block_block_visited(bl) < get_irg_block_visited(current_ir_graph)) {
150 set_Block_block_visited(bl, get_irg_block_visited(current_ir_graph));
155 for(i = 0; i < get_Block_n_cfg_outs(bl); i++) {
156 /* find the corresponding predecessor block. */
157 ir_node *pred = get_Block_cfg_out(bl, i);
159 irg_out_block_walk2(pred, pre, post, env);
168 /* Walks only over Block nodes in the graph. Has it's own visited
169 flag, so that it can be interleaved with the other walker. */
170 void irg_out_block_walk(ir_node *node,
171 irg_walk_func *pre, irg_walk_func *post,
174 assert((get_irn_op(node) == op_Block) || (get_irn_mode(node) == mode_X));
176 inc_irg_block_visited(current_ir_graph);
178 if (get_irn_mode(node) == mode_X) node = node->out[1];
180 irg_out_block_walk2(node, pre, post, env);
186 /**********************************************************************/
187 /** Building and Removing the out datasturcture **/
189 /** The outs of a graph are allocated in a single, large array. **/
190 /** This allows to allocate and deallocate the memory for the outs **/
191 /** on demand. The large array is separated into many small ones **/
192 /** for each node. Only a single field to reference the out array **/
193 /** is stored in each node and a field referencing the large out **/
194 /** array in irgraph. The 0 field of each out array contains the **/
195 /** size of this array. This saves memory in the irnodes themselves.**/
196 /** The construction does two passes over the graph. The first pass **/
197 /** counts the overall number of outs and the outs of each node. It **/
198 /** stores the outs of each node in the out reference of the node. **/
199 /** Then the large array is allocated. The second iteration chops **/
200 /** the large array into smaller parts, sets the out edges and **/
201 /** recounts the out edges. **/
202 /** Removes Tuple nodes! **/
203 /**********************************************************************/
206 /* Returns the amount of out edges for not yet visited successors. */
207 static int count_outs(ir_node *n) {
208 int start, i, res, irn_arity;
211 set_irn_visited(n, get_irg_visited(current_ir_graph));
212 n->out = (ir_node **) 1; /* Space for array size. */
214 start = get_irn_op(n) == op_Block ? 0 : -1;
215 irn_arity = get_irn_arity(n);
216 res = irn_arity - start +1; /* --1 or --0; 1 for array size. */
217 for (i = start; i < irn_arity; i++) {
218 /* Optimize Tuples. They annoy if walking the cfg. */
219 succ = skip_Tuple(get_irn_n(n, i));
220 set_irn_n(n, i, succ);
221 /* count outs for successors */
222 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph)) {
223 res += count_outs(succ);
226 succ->out = (ir_node **)( (int)succ->out +1);
231 static ir_node **set_out_edges(ir_node *n, ir_node **free) {
232 int n_outs, start, i, irn_arity;
235 set_irn_visited(n, get_irg_visited(current_ir_graph));
237 /* Allocate my array */
238 n_outs = (int) n->out;
243 free = &free[n_outs];
244 /* We count the successors again, the space will be sufficient.
245 We use this counter to remember the position for the next back
247 n->out[0] = (ir_node *)0;
249 if (get_irn_op(n) == op_Block) start = 0; else start = -1;
250 irn_arity = get_irn_arity(n);
251 for (i = start; i < irn_arity; i++) {
252 succ = get_irn_n(n, i);
254 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
255 free = set_out_edges(succ, free);
256 /* Remember our back edge */
257 succ->out[get_irn_n_outs(succ)+1] = n;
258 succ->out[0] = (ir_node *) (get_irn_n_outs(succ) + 1);
263 static INLINE void fix_start_proj(ir_graph *irg) {
264 ir_node *proj = NULL, *startbl;
266 if (get_Block_n_cfg_outs(get_irg_start_block(irg))) {
267 startbl = get_irg_start_block(irg);
268 for (i = 0; i < get_irn_n_outs(startbl); i++)
269 if (get_irn_mode(get_irn_out(startbl, i)) == mode_X)
270 proj = get_irn_out(startbl, i);
271 if (get_irn_out(proj, 0) == startbl) {
272 assert(get_irn_n_outs(proj) == 2);
273 set_irn_out(proj, 0, get_irn_out(proj, 1));
274 set_irn_out(proj, 1, startbl);
279 void compute_outs(ir_graph *irg) {
280 ir_graph *rem = current_ir_graph;
282 ir_node **end = NULL;
284 current_ir_graph = irg;
286 /* Update graph state */
287 assert(get_irg_phase_state(current_ir_graph) != phase_building);
288 if (current_ir_graph->outs_state != no_outs) free_outs(current_ir_graph);
289 current_ir_graph->outs_state = outs_consistent;
291 /* This first iteration counts the overall number of out edges and the
292 number of out edges for each node. */
293 inc_irg_visited(irg);
294 n_out_edges = count_outs(get_irg_end(irg));
296 /* allocate memory for all out edges. */
297 irg->outs = (ir_node **) xmalloc (n_out_edges * sizeof(ir_node *));
298 irg->n_outs = n_out_edges;
300 /* The second iteration splits the irg->outs array into smaller arrays
301 for each node and writes the back edges into this array. */
302 inc_irg_visited(irg);
303 end = set_out_edges(get_irg_end(irg), irg->outs);
305 /* Check how much memory we have used */
306 assert (end == (irg->outs + n_out_edges));
308 /* We want that the out of ProjX from Start contains the next block at
309 position 1, the Start block at position 2. This is necessary for
310 the out block walker. */
313 current_ir_graph = rem;
319 /*------------------------------------------------------------*
320 * This computes the outedges for in interprocedural graph. *
321 * There is one quirk: *
322 * The number of the outedges for each node is saved in *
323 * the first member of the ir_node** array. Maybe we should *
324 * change this to make it more portable... *
325 *------------------------------------------------------------*/
328 /* ------------------------------------------
329 Inits the number of outedges for each node
331 ------------------------------------------ */
333 static void init_count(ir_node * node, void * env)
335 node->out = (ir_node **) 1; /* 1 for the array size */
339 /* -----------------------------------------------
340 Adjusts the out edge count for its predecessors
341 and adds the current arity to the overall count,
342 which is saved in "env"
343 ------------------------------------------------ */
345 static void node_arity_count(ir_node * node, void * env)
347 int *anz = (int *) env, arity, i, start;
350 arity = 1 + get_irn_arity(node)
351 + ((is_Block(node)) ? 0 : 1);
354 start = (is_Block(node)) ? 0 : -1;
355 for(i = start; i < get_irn_arity(node); i++) {
356 succ = 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 < get_irn_arity(node); i++) {
413 succ = get_irn_n(node, i);
414 succ->out[get_irn_n_outs(succ)+1] = node;
415 succ->out[0] = (ir_node *) (get_irn_n_outs(succ) + 1);
420 /* -------------------------------
421 Sets the outedges for all nodes.
422 -------------------------------- */
424 void set_ip_outs(void)
426 ir_node **outedge_array = get_irp_ip_outedges();
427 cg_walk(set_array_pointer, set_out_pointer, (void *) &outedge_array);
432 /* --------------------------------------------------------
433 Counts the outedges, allocates memory to save the
434 outedges and fills this outedge array in interprocedural
436 -------------------------------------------------------- */
438 void compute_ip_outs(void) {
443 assert(get_irp_ip_view_state() == ip_view_valid &&
444 "Cannot construct outs for invalid ip view.");
446 if (irp->outs_state != no_outs) free_ip_outs();
448 global_count = n_out_edges = count_ip_outs();
449 out_edges = (ir_node **) malloc (n_out_edges * sizeof(ir_node *));
450 set_irp_ip_outedges(out_edges);
454 void free_ip_outs(void)
456 ir_node **out_edges = get_irp_ip_outedges();
457 if (out_edges != NULL) {
459 set_irp_ip_outedges(NULL);
461 irp->outs_state = no_outs;
465 void free_outs(ir_graph *irg) {
467 /* current_ir_graph->outs_state = no_outs; */
468 irg->outs_state = no_outs;
471 memset(irg->outs, 0, irg->n_outs);
477 //irg_walk_graph (irg, reset_outs, NULL, NULL);