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 ((intern_get_irn_mode(bl->out[i+1]) == mode_X) &&
65 (intern_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 ((intern_get_irn_mode(bl->out[i+1]) == mode_X) &&
75 (intern_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 if(get_Block_block_visited(bl) < get_irg_block_visited(current_ir_graph)) {
126 set_Block_block_visited(bl, get_irg_block_visited(current_ir_graph));
131 for(i = 0; i < get_Block_n_cfg_outs(bl); i++) {
132 /* find the corresponding predecessor block. */
133 ir_node *pred = get_Block_cfg_out(bl, i);
135 irg_out_block_walk2(pred, pre, post, env);
144 /* Walks only over Block nodes in the graph. Has it's own visited
145 flag, so that it can be interleaved with the other walker. */
146 void irg_out_block_walk(ir_node *node,
147 irg_walk_func *pre, irg_walk_func *post,
150 assert((get_irn_op(node) == op_Block) || (intern_get_irn_mode(node) == mode_X));
152 inc_irg_block_visited(current_ir_graph);
154 if (intern_get_irn_mode(node) == mode_X) node = node->out[1];
156 irg_out_block_walk2(node, pre, post, env);
162 /**********************************************************************/
163 /** Building and Removing the out datasturcture **/
165 /** The outs of a graph are allocated in a single, large array. **/
166 /** This allows to allocate and deallocate the memory for the outs **/
167 /** on demand. The large array is separated into many small ones **/
168 /** for each node. Only a single field to reference the out array **/
169 /** is stored in each node and a field referencing the large out **/
170 /** array in irgraph. The 0 field of each out array contains the **/
171 /** size of this array. This saves memory in the irnodes themselves.**/
172 /** The construction does two passes over the graph. The first pass **/
173 /** counts the overall number of outs and the outs of each node. It **/
174 /** stores the outs of each node in the out reference of the node. **/
175 /** Then the large array is allocated. The second iteration chops **/
176 /** the large array into smaller parts, sets the out edges and **/
177 /** recounts the out edges. **/
178 /** Removes Tuple nodes! **/
179 /**********************************************************************/
182 /* Returns the amount of out edges for not yet visited successors. */
183 static int count_outs(ir_node *n) {
184 int start, i, res, irn_arity;
187 set_irn_visited(n, get_irg_visited(current_ir_graph));
188 n->out = (ir_node **) 1; /* Space for array size. */
190 if ((intern_get_irn_op(n) == op_Block)) start = 0; else start = -1;
191 irn_arity = intern_get_irn_arity(n);
192 res = irn_arity - start +1; /* --1 or --0; 1 for array size. */
193 for (i = start; i < irn_arity; i++) {
194 /* Optimize Tuples. They annoy if walking the cfg. */
195 succ = skip_Tuple(intern_get_irn_n(n, i));
196 set_irn_n(n, i, succ);
197 /* count outs for successors */
198 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
199 res += count_outs(succ);
201 succ->out = (ir_node **)( (int)succ->out +1);
206 static ir_node **set_out_edges(ir_node *n, ir_node **free) {
207 int n_outs, start, i, irn_arity;
210 set_irn_visited(n, get_irg_visited(current_ir_graph));
212 /* Allocate my array */
213 n_outs = (int) n->out;
215 free = &free[n_outs];
216 /* We count the successors again, the space will be sufficient.
217 We use this counter to remember the position for the next back
219 n->out[0] = (ir_node *)0;
221 if (intern_get_irn_op(n) == op_Block) start = 0; else start = -1;
222 irn_arity = intern_get_irn_arity(n);
223 for (i = start; i < irn_arity; i++) {
224 succ = intern_get_irn_n(n, i);
226 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
227 free = set_out_edges(succ, free);
228 /* Remember our back edge */
229 succ->out[get_irn_n_outs(succ)+1] = n;
230 succ->out[0] = (ir_node *) (get_irn_n_outs(succ) + 1);
235 static INLINE void fix_start_proj(ir_graph *irg) {
236 ir_node *proj = NULL, *startbl;
238 if (get_Block_n_cfg_outs(get_irg_start_block(irg))) {
239 startbl = get_irg_start_block(irg);
240 for (i = 0; i < get_irn_n_outs(startbl); i++)
241 if (intern_get_irn_mode(get_irn_out(startbl, i)) == mode_X)
242 proj = get_irn_out(startbl, i);
243 if (get_irn_out(proj, 0) == startbl) {
244 assert(get_irn_n_outs(proj) == 2);
245 set_irn_out(proj, 0, get_irn_out(proj, 1));
246 set_irn_out(proj, 1, startbl);
251 void compute_outs(ir_graph *irg) {
252 ir_graph *rem = current_ir_graph;
255 current_ir_graph = irg;
257 /* Update graph state */
258 assert(get_irg_phase_state(current_ir_graph) != phase_building);
259 if (current_ir_graph->outs_state != no_outs) free_outs(current_ir_graph);
260 current_ir_graph->outs_state = outs_consistent;
262 /* This first iteration counts the overall number of out edges and the
263 number of out edges for each node. */
264 inc_irg_visited(irg);
265 n_out_edges = count_outs(get_irg_end(irg));
267 /* allocate memory for all out edges. */
268 irg->outs = (ir_node **) malloc (n_out_edges * sizeof(ir_node *));
270 /* The second iteration splits the irg->outs array into smaller arrays
271 for each node and writes the back edges into this array. */
272 inc_irg_visited(irg);
273 set_out_edges(get_irg_end(irg), irg->outs);
275 /* We want that the out of ProjX from Start contains the next block at
276 position 1, the Start block at position 2. This is necessary for
277 the out block walker. */
280 current_ir_graph = rem;
286 /****************************************************************
287 ** This computes the outedges for in interprocedural graph. **
288 ** There is one quirk: **
289 ** The number of the outedges for each node is saved in **
290 ** the first member of the ir_node** array. Maybe we should **
291 ** change this to make it more portable... **
292 ****************************************************************/
295 /* ------------------------------------------
296 Inits the number of outedges for each node
298 ------------------------------------------ */
300 static void init_count(ir_node * node, void * env)
302 node->out = (ir_node **) 1; /* 1 for the array size */
306 /* -----------------------------------------------
307 Adjusts the out edge count for its predecessors
308 and adds the current arity to the overall count,
309 which is saved in "env"
310 ------------------------------------------------ */
312 static void node_arity_count(ir_node * node, void * env)
314 int *anz = (int *) env, arity, i, start;
317 arity = 1 + intern_get_irn_arity(node)
318 + ((is_Block(node)) ? 0 : 1);
321 start = (is_Block(node)) ? 0 : -1;
322 for(i = start; i < intern_get_irn_arity(node); i++)
324 succ = intern_get_irn_n(node, i);
325 succ->out = (ir_node **)((int)succ->out + 1);
330 /* ----------------------------------------
331 Inits all nodes for setting the outedges
332 Returns the overall count of edges
333 ---------------------------------------- */
335 int count_ip_outs(void) {
339 cg_walk(init_count, node_arity_count, &res);
344 int dummy_count = 0, global_count; /* Only for debugging */
346 /* ---------------------------------------------
347 For each node: Sets the pointer to array
348 in which the outedges are written later.
349 The current array start is transported in env
350 --------------------------------------------- */
352 static void set_array_pointer(ir_node *node, void *env) {
355 ir_node ***free = (ir_node ***) env;
357 /* Allocate my array */
358 n_outs = (int) node -> out; /* We wrote the count here in count_ip_outs */
359 dummy_count += n_outs;
360 assert(dummy_count <= global_count && "More outedges than initialliy counted!");
362 *free = &((*free)[n_outs]);
363 /* We count the successors again, the space will be sufficient.
364 We use this counter to remember the position for the next back
366 node -> out[0] = (ir_node *) 0;
370 /* -------------------------------------------
371 Adds an outedge from the predecessor to the
373 ------------------------------------------- */
375 static void set_out_pointer(ir_node * node, void * env) {
378 int start = (!is_Block(node)) ? -1 : 0;
380 for(i = start; i < intern_get_irn_arity(node); i++)
382 succ = intern_get_irn_n(node, i);
383 succ->out[get_irn_n_outs(succ)+1] = node;
384 succ->out[0] = (ir_node *) (get_irn_n_outs(succ) + 1);
389 /* -------------------------------
390 Sets the outedges for all nodes.
391 -------------------------------- */
393 void set_ip_outs(void)
395 ir_node **outedge_array = get_irp_ip_outedges();
396 cg_walk(set_array_pointer, set_out_pointer, (void *) &outedge_array);
401 /* --------------------------------------------------------
402 Counts the outedges, allocates memory to save the
403 outedges and fills this outedge array in interprocedural
405 -------------------------------------------------------- */
407 void compute_ip_outs(void) {
412 if (irp->outs_state != no_outs) free_ip_outs();
414 global_count = n_out_edges = count_ip_outs();
415 out_edges = (ir_node **) malloc (n_out_edges * sizeof(ir_node *));
416 set_irp_ip_outedges(out_edges);
420 void free_ip_outs(void)
422 ir_node **out_edges = get_irp_ip_outedges();
423 if (out_edges != NULL)
426 set_irp_ip_outedges(NULL);
428 irp->outs_state = no_outs;
432 void free_outs(ir_graph *irg) {
434 current_ir_graph->outs_state = no_outs;
436 if (irg->outs) free(irg->outs);