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 */
36 /**********************************************************************/
37 /** Accessing the out datastructures **/
38 /**********************************************************************/
40 /* returns the number of successors of the node: */
41 INLINE int get_irn_n_outs (ir_node *node) {
42 return (int)(node->out[0]);
45 /* Access successor n */
46 INLINE ir_node *get_irn_out (ir_node *node, int pos) {
48 assert(pos >= 0 && pos < get_irn_n_outs(node));
49 return node->out[pos+1];
52 INLINE void set_irn_out (ir_node *node, int pos, ir_node *out) {
54 assert(pos >= 0 && pos < get_irn_n_outs(node));
55 node->out[pos+1] = out;
59 INLINE int get_Block_n_cfg_outs (ir_node *bl) {
60 int i, n_cfg_outs = 0;
61 assert(bl && (get_irn_op(bl) == op_Block));
62 for (i = 0; i < (int)bl->out[0]; i++)
63 if ((get_irn_mode(bl->out[i+1]) == mode_X) &&
64 (get_irn_op(bl->out[i+1]) != op_End)) n_cfg_outs++;
69 INLINE ir_node *get_Block_cfg_out (ir_node *bl, int pos) {
71 assert(bl && (get_irn_op(bl) == op_Block));
72 for (i = 0; i < (int)bl->out[0]; i++)
73 if ((get_irn_mode(bl->out[i+1]) == mode_X) &&
74 (get_irn_op(bl->out[i+1]) != op_End)) {
76 ir_node *cfop = bl->out[i+1];
77 return cfop->out[0+1];
85 void irg_out_walk_2(ir_node *node, irg_walk_func *pre,
86 irg_walk_func *post, void *env) {
91 assert(get_irn_visited(node) < get_irg_visited(current_ir_graph));
93 set_irn_visited(node, get_irg_visited(current_ir_graph));
95 if (pre) pre(node, env);
97 for (i = 0; i < get_irn_n_outs(node); i++) {
98 succ = get_irn_out(node, i);
99 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
100 irg_out_walk_2(succ, pre, post, env);
103 if (post) post(node, env);
108 void irg_out_walk(ir_node *node,
109 irg_walk_func *pre, irg_walk_func *post,
112 if (get_irg_outs_state(current_ir_graph) != no_outs) {
113 inc_irg_visited (current_ir_graph);
114 irg_out_walk_2(node, pre, post, env);
119 void irg_out_block_walk2(ir_node *bl,
120 irg_walk_func *pre, irg_walk_func *post,
124 assert(get_irn_opcode(bl) == iro_Block);
126 if(get_Block_block_visited(bl) < get_irg_block_visited(current_ir_graph)) {
127 set_Block_block_visited(bl, get_irg_block_visited(current_ir_graph));
132 for(i = 0; i < get_Block_n_cfg_outs(bl); i++) {
133 /* find the corresponding predecessor block. */
134 ir_node *pred = get_Block_cfg_out(bl, i);
135 assert(get_irn_opcode(pred) == iro_Block);
137 irg_out_block_walk2(pred, pre, post, env);
146 /* Walks only over Block nodes in the graph. Has it's own visited
147 flag, so that it can be interleaved with the other walker. */
148 void irg_out_block_walk(ir_node *node,
149 irg_walk_func *pre, irg_walk_func *post,
152 assert((get_irn_op(node) == op_Block) || (get_irn_mode(node) == mode_X));
154 inc_irg_block_visited(current_ir_graph);
156 if (get_irn_mode(node) == mode_X) node = node->out[1];
157 assert(get_irn_opcode(node) == iro_Block);
159 irg_out_block_walk2(node, pre, post, env);
165 /**********************************************************************/
166 /** Building and Removing the out datasturcture **/
168 /** The outs of a graph are allocated in a single, large array. **/
169 /** This allows to allocate and deallocate the memory for the outs **/
170 /** on demand. The large array is separated into many small ones **/
171 /** for each node. Only a single field to reference the out array **/
172 /** is stored in each node and a field referencing the large out **/
173 /** array in irgraph. The 0 field of each out array contains the **/
174 /** size of this array. This saves memory in the irnodes themselves.**/
175 /** The construction does two passes over the graph. The first pass **/
176 /** counts the overall number of outs and the outs of each node. It **/
177 /** stores the outs of each node in the out reference of the node. **/
178 /** Then the large array is allocated. The second iteration chops **/
179 /** the large array into smaller parts, sets the out edges and **/
180 /** recounts the out edges. **/
181 /**********************************************************************/
184 /* Returns the amount of out edges for not yet visited successors. */
185 static int count_outs(ir_node *n) {
186 int start, i, res, irn_arity;
189 set_irn_visited(n, get_irg_visited(current_ir_graph));
190 n->out = (ir_node **) 1; /* Space for array size. */
192 if ((get_irn_op(n) == op_Block)) start = 0; else start = -1;
193 irn_arity = get_irn_arity(n);
194 res = irn_arity - start +1; /* --1 or --0; 1 for array size. */
195 for (i = start; i < irn_arity; i++) {
196 /* Optimize Tuples. They annoy if walking the cfg. */
197 succ = skip_Tuple(get_irn_n(n, i));
198 set_irn_n(n, i, succ);
199 /* count outs for successors */
200 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
201 res += count_outs(succ);
203 succ->out = (ir_node **)( (int)succ->out +1);
208 static ir_node **set_out_edges(ir_node *n, ir_node **free) {
209 int n_outs, start, i, irn_arity;
212 set_irn_visited(n, get_irg_visited(current_ir_graph));
214 /* Allocate my array */
215 n_outs = (int) n->out;
217 free = &free[n_outs];
218 /* We count the successors again, the space will be sufficient.
219 We use this counter to remember the position for the next back
221 n->out[0] = (ir_node *)0;
223 if (get_irn_op(n) == op_Block) start = 0; else start = -1;
224 irn_arity = get_irn_arity(n);
225 for (i = start; i < irn_arity; i++) {
226 succ = get_irn_n(n, i);
228 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
229 free = set_out_edges(succ, free);
230 /* Remember our back edge */
231 succ->out[get_irn_n_outs(succ)+1] = n;
232 succ->out[0] = (ir_node *) (get_irn_n_outs(succ) + 1);
237 static INLINE void fix_start_proj(ir_graph *irg) {
238 ir_node *proj = NULL, *startbl;
240 if (get_Block_n_cfg_outs(get_irg_start_block(irg))) {
241 startbl = get_irg_start_block(irg);
242 for (i = 0; i < get_irn_n_outs(startbl); i++)
243 if (get_irn_mode(get_irn_out(startbl, i)) == mode_X)
244 proj = get_irn_out(startbl, i);
245 if (get_irn_out(proj, 0) == startbl) {
246 assert(get_irn_n_outs(proj) == 2);
247 set_irn_out(proj, 0, get_irn_out(proj, 1));
248 set_irn_out(proj, 1, startbl);
253 void compute_outs(ir_graph *irg) {
254 ir_graph *rem = current_ir_graph;
257 current_ir_graph = irg;
259 /* Update graph state */
260 assert(get_irg_phase_state(current_ir_graph) != phase_building);
261 current_ir_graph->outs_state = outs_consistent;
263 /* This first iteration counts the overall number of out edges and the
264 number of out edges for each node. */
265 inc_irg_visited(irg);
266 n_out_edges = count_outs(get_irg_end(irg));
268 /* allocate memory for all out edges. */
269 irg->outs = (ir_node **) malloc (n_out_edges * sizeof(ir_node *));
271 /* The second iteration splits the irg->outs array into smaller arrays
272 for each node and writes the back edges into this array. */
273 inc_irg_visited(irg);
274 set_out_edges(get_irg_end(irg), irg->outs);
276 /* We want that the out of ProjX from Start contains the next block at
277 position 1, the Start block at position 2. This is necessary for
278 the out block walker. */
281 current_ir_graph = rem;
285 void compute_ip_outs(ir_graph *irg) { /*irg_walk_func *pre, irg_walk_func *post, void *env) { */
287 ir_graph *rem = current_ir_graph;
288 int rem_view = interprocedural_view;
290 interprocedural_view = true;
292 inc_max_irg_visited();
293 /* Fix all irg_visited flags */
294 for (i = 0; i < get_irp_n_irgs(); i++)
295 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
297 /* Walk starting at unreachable procedures. Only these
298 * have End blocks visible in interprocedural view. */
299 for (i = 0; i < get_irp_n_irgs(); i++) {
301 current_ir_graph = get_irp_irg(i);
303 sb = get_irg_start_block(current_ir_graph);
305 if ((get_Block_n_cfgpreds(sb) > 1) ||
306 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
308 compute_outs(current_ir_graph); /*cg_walk_2(get_irg_end(current_ir_graph), pre, post, env);*/
311 /* Check whether we walked all procedures: there could be procedures
312 with cyclic calls but no call from the outside. */
313 for (i = 0; i < get_irp_n_irgs(); i++) {
315 current_ir_graph = get_irp_irg(i);
317 /* Test start block: if inner procedure end and end block are not
318 * visible and therefore not marked. */
319 sb = get_irg_start_block(current_ir_graph);
320 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) {
321 compute_outs(current_ir_graph); /*cg_walk_2(sb, pre, post, env); */
325 /* Walk all endless loops in inner procedures.
326 * We recognize an inner procedure if the End node is not visited. */
327 for (i = 0; i < get_irp_n_irgs(); i++) {
329 current_ir_graph = get_irp_irg(i);
330 e = get_irg_end(current_ir_graph);
331 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
332 /* Don't visit the End node. */
334 for (j = 0; j < get_End_n_keepalives(e); j++)
335 cg_walk_2(get_End_keepalive(e, j), pre, post, env);*/
336 compute_outs(current_ir_graph);
340 interprocedural_view = rem_view;
341 current_ir_graph = rem;
347 void free_outs(ir_graph *irg) {
349 /* Update graph state */
350 assert(get_irg_phase_state(current_ir_graph) != phase_building);
351 current_ir_graph->outs_state = no_outs;
353 if (irg->outs) free(irg->outs);