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 /* returns the number of successors of the node: */
42 INLINE int get_irn_n_outs (ir_node *node) {
43 return (int)(node->out[0]);
46 /* Access successor n */
47 INLINE ir_node *get_irn_out (ir_node *node, int pos) {
49 assert(pos >= 0 && pos < get_irn_n_outs(node));
50 return node->out[pos+1];
53 INLINE void set_irn_out (ir_node *node, int pos, ir_node *out) {
55 assert(pos >= 0 && pos < get_irn_n_outs(node));
56 node->out[pos+1] = out;
60 INLINE int get_Block_n_cfg_outs (ir_node *bl) {
61 int i, n_cfg_outs = 0;
62 assert(bl && (get_irn_op(bl) == op_Block));
63 for (i = 0; i < (int)bl->out[0]; i++)
64 if ((get_irn_mode(bl->out[i+1]) == mode_X) &&
65 (get_irn_op(bl->out[i+1]) != op_End)) n_cfg_outs++;
70 INLINE ir_node *get_Block_cfg_out (ir_node *bl, int pos) {
72 assert(bl && (get_irn_op(bl) == op_Block));
73 for (i = 0; i < (int)bl->out[0]; i++)
74 if ((get_irn_mode(bl->out[i+1]) == mode_X) &&
75 (get_irn_op(bl->out[i+1]) != op_End)) {
77 ir_node *cfop = bl->out[i+1];
78 return cfop->out[0+1];
86 void irg_out_walk_2(ir_node *node, irg_walk_func *pre,
87 irg_walk_func *post, void *env) {
92 assert(get_irn_visited(node) < get_irg_visited(current_ir_graph));
94 set_irn_visited(node, get_irg_visited(current_ir_graph));
96 if (pre) pre(node, env);
98 for (i = 0; i < get_irn_n_outs(node); i++) {
99 succ = get_irn_out(node, i);
100 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
101 irg_out_walk_2(succ, pre, post, env);
104 if (post) post(node, env);
109 void irg_out_walk(ir_node *node,
110 irg_walk_func *pre, irg_walk_func *post,
113 if (get_irg_outs_state(current_ir_graph) != no_outs) {
114 inc_irg_visited (current_ir_graph);
115 irg_out_walk_2(node, pre, post, env);
120 void irg_out_block_walk2(ir_node *bl,
121 irg_walk_func *pre, irg_walk_func *post,
125 assert(get_irn_opcode(bl) == iro_Block);
127 if(get_Block_block_visited(bl) < get_irg_block_visited(current_ir_graph)) {
128 set_Block_block_visited(bl, get_irg_block_visited(current_ir_graph));
133 for(i = 0; i < get_Block_n_cfg_outs(bl); i++) {
134 /* find the corresponding predecessor block. */
135 ir_node *pred = get_Block_cfg_out(bl, i);
136 assert(get_irn_opcode(pred) == iro_Block);
138 irg_out_block_walk2(pred, pre, post, env);
147 /* Walks only over Block nodes in the graph. Has it's own visited
148 flag, so that it can be interleaved with the other walker. */
149 void irg_out_block_walk(ir_node *node,
150 irg_walk_func *pre, irg_walk_func *post,
153 assert((get_irn_op(node) == op_Block) || (get_irn_mode(node) == mode_X));
155 inc_irg_block_visited(current_ir_graph);
157 if (get_irn_mode(node) == mode_X) node = node->out[1];
158 assert(get_irn_opcode(node) == iro_Block);
160 irg_out_block_walk2(node, pre, post, env);
166 /**********************************************************************/
167 /** Building and Removing the out datasturcture **/
169 /** The outs of a graph are allocated in a single, large array. **/
170 /** This allows to allocate and deallocate the memory for the outs **/
171 /** on demand. The large array is separated into many small ones **/
172 /** for each node. Only a single field to reference the out array **/
173 /** is stored in each node and a field referencing the large out **/
174 /** array in irgraph. The 0 field of each out array contains the **/
175 /** size of this array. This saves memory in the irnodes themselves.**/
176 /** The construction does two passes over the graph. The first pass **/
177 /** counts the overall number of outs and the outs of each node. It **/
178 /** stores the outs of each node in the out reference of the node. **/
179 /** Then the large array is allocated. The second iteration chops **/
180 /** the large array into smaller parts, sets the out edges and **/
181 /** recounts the out edges. **/
182 /** Removes Tuple nodes! **/
183 /**********************************************************************/
186 /* Returns the amount of out edges for not yet visited successors. */
187 static int count_outs(ir_node *n) {
188 int start, i, res, irn_arity;
191 set_irn_visited(n, get_irg_visited(current_ir_graph));
192 n->out = (ir_node **) 1; /* Space for array size. */
194 if ((get_irn_op(n) == op_Block)) start = 0; else start = -1;
195 irn_arity = get_irn_arity(n);
196 res = irn_arity - start +1; /* --1 or --0; 1 for array size. */
197 for (i = start; i < irn_arity; i++) {
198 /* Optimize Tuples. They annoy if walking the cfg. */
199 succ = skip_Tuple(get_irn_n(n, i));
200 set_irn_n(n, i, succ);
201 /* count outs for successors */
202 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
203 res += count_outs(succ);
205 succ->out = (ir_node **)( (int)succ->out +1);
210 static ir_node **set_out_edges(ir_node *n, ir_node **free) {
211 int n_outs, start, i, irn_arity;
214 set_irn_visited(n, get_irg_visited(current_ir_graph));
216 /* Allocate my array */
217 n_outs = (int) n->out;
219 free = &free[n_outs];
220 /* We count the successors again, the space will be sufficient.
221 We use this counter to remember the position for the next back
223 n->out[0] = (ir_node *)0;
225 if (get_irn_op(n) == op_Block) start = 0; else start = -1;
226 irn_arity = get_irn_arity(n);
227 for (i = start; i < irn_arity; i++) {
228 succ = get_irn_n(n, i);
230 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
231 free = set_out_edges(succ, free);
232 /* Remember our back edge */
233 succ->out[get_irn_n_outs(succ)+1] = n;
234 succ->out[0] = (ir_node *) (get_irn_n_outs(succ) + 1);
239 static INLINE void fix_start_proj(ir_graph *irg) {
240 ir_node *proj = NULL, *startbl;
242 if (get_Block_n_cfg_outs(get_irg_start_block(irg))) {
243 startbl = get_irg_start_block(irg);
244 for (i = 0; i < get_irn_n_outs(startbl); i++)
245 if (get_irn_mode(get_irn_out(startbl, i)) == mode_X)
246 proj = get_irn_out(startbl, i);
247 if (get_irn_out(proj, 0) == startbl) {
248 assert(get_irn_n_outs(proj) == 2);
249 set_irn_out(proj, 0, get_irn_out(proj, 1));
250 set_irn_out(proj, 1, startbl);
255 void compute_outs(ir_graph *irg) {
256 ir_graph *rem = current_ir_graph;
259 current_ir_graph = irg;
261 /* Update graph state */
262 assert(get_irg_phase_state(current_ir_graph) != phase_building);
263 current_ir_graph->outs_state = outs_consistent;
265 /* This first iteration counts the overall number of out edges and the
266 number of out edges for each node. */
267 inc_irg_visited(irg);
268 n_out_edges = count_outs(get_irg_end(irg));
270 /* allocate memory for all out edges. */
271 irg->outs = (ir_node **) malloc (n_out_edges * sizeof(ir_node *));
273 /* The second iteration splits the irg->outs array into smaller arrays
274 for each node and writes the back edges into this array. */
275 inc_irg_visited(irg);
276 set_out_edges(get_irg_end(irg), irg->outs);
278 /* We want that the out of ProjX from Start contains the next block at
279 position 1, the Start block at position 2. This is necessary for
280 the out block walker. */
283 current_ir_graph = rem;
289 /****************************************************************
290 ** This computes the outedges for in interprocedural graph. **
291 ** There is one quirk: **
292 ** The number of the outedges for each node is saved in **
293 ** the first member of the ir_node** array. Maybe we should **
294 ** change this to make it more portable... **
295 ****************************************************************/
298 /* ------------------------------------------
299 Inits the number of outedges for each node
301 ------------------------------------------ */
303 static void init_count(ir_node * node, void * env)
305 node->out = (ir_node **) 1; /* 1 for the array size */
309 /* -----------------------------------------------
310 Adjusts the out edge count for its predecessors
311 and adds the current arity to the overall count,
312 which is saved in "env"
313 ------------------------------------------------ */
315 static void node_arity_count(ir_node * node, void * env)
317 int *anz = (int *) env, arity, i, start;
320 arity = 1 + get_irn_arity(node)
321 + ((is_Block(node)) ? 0 : 1);
324 start = (is_Block(node)) ? 0 : -1;
325 for(i = start; i < get_irn_arity(node); i++)
327 succ = get_irn_n(node, i);
328 succ->out = (ir_node **)((int)succ->out + 1);
333 /* ----------------------------------------
334 Inits all nodes for setting the outedges
335 Returns the overall count of edges
336 ---------------------------------------- */
338 int count_ip_outs(void) {
342 cg_walk(init_count, node_arity_count, &res);
347 int dummy_count = 0, global_count; /* Only for debugging */
349 /* ---------------------------------------------
350 For each node: Sets the pointer to array
351 in which the outedges are written later.
352 The current array start is transported in env
353 --------------------------------------------- */
355 static void set_array_pointer(ir_node *node, void *env) {
358 ir_node ***free = (ir_node ***) env;
360 /* Allocate my array */
361 n_outs = (int) node -> out; /* We wrote the count here in count_ip_outs */
362 dummy_count += n_outs;
363 assert(dummy_count <= global_count && "More outedges than initialliy counted!");
365 *free = &((*free)[n_outs]);
366 /* We count the successors again, the space will be sufficient.
367 We use this counter to remember the position for the next back
369 node -> out[0] = (ir_node *) 0;
373 /* -------------------------------------------
374 Adds an outedge from the predecessor to the
376 ------------------------------------------- */
378 static void set_out_pointer(ir_node * node, void * env) {
381 int start = (!is_Block(node)) ? -1 : 0;
383 for(i = start; i < get_irn_arity(node); i++)
385 succ = get_irn_n(node, i);
386 succ->out[get_irn_n_outs(succ)+1] = node;
387 succ->out[0] = (ir_node *) (get_irn_n_outs(succ) + 1);
392 /* -------------------------------
393 Sets the outedges for all nodes.
394 -------------------------------- */
396 void set_ip_outs(void)
398 ir_node **outedge_array = get_irp_ip_outedges();
399 cg_walk(set_array_pointer, set_out_pointer, (void *) &outedge_array);
404 /* --------------------------------------------------------
405 Counts the outedges, allocates memory to save the
406 outedges and fills this outedge array in interprocedural
408 -------------------------------------------------------- */
410 void ascompute_ip_outs(void) {
415 global_count = n_out_edges = count_ip_outs();
416 out_edges = (ir_node **) malloc (n_out_edges * sizeof(ir_node *));
417 set_irp_ip_outedges(out_edges);
421 void free_ip_outs(void)
423 ir_node **out_edges = get_irp_ip_outedges();
424 if(out_edges != NULL)
427 set_irp_ip_outedges(NULL);
432 void free_outs(ir_graph *irg) {
434 current_ir_graph->outs_state = no_outs;
436 if (irg->outs) free(irg->outs);