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 */
35 /**********************************************************************/
36 /** Accessing the out datastructures **/
37 /**********************************************************************/
39 /* returns the number of successors of the node: */
40 INLINE int get_irn_n_outs (ir_node *node) {
41 return (int)(node->out[0]);
44 /* Access successor n */
45 INLINE ir_node *get_irn_out (ir_node *node, int pos) {
47 assert(pos >= 0 && pos < get_irn_n_outs(node));
48 return node->out[pos+1];
51 INLINE void set_irn_out (ir_node *node, int pos, ir_node *out) {
53 assert(pos >= 0 && pos < get_irn_n_outs(node));
54 node->out[pos+1] = out;
58 INLINE int get_Block_n_cfg_outs (ir_node *bl) {
59 int i, n_cfg_outs = 0;
60 assert(bl && (get_irn_op(bl) == op_Block));
61 for (i = 0; i < (int)bl->out[0]; i++)
62 if ((get_irn_mode(bl->out[i+1]) == mode_X) &&
63 (get_irn_op(bl->out[i+1]) != op_End)) n_cfg_outs++;
68 INLINE ir_node *get_Block_cfg_out (ir_node *bl, int pos) {
70 assert(bl && (get_irn_op(bl) == op_Block));
71 for (i = 0; i < (int)bl->out[0]; i++)
72 if ((get_irn_mode(bl->out[i+1]) == mode_X) &&
73 (get_irn_op(bl->out[i+1]) != op_End)) {
75 ir_node *cfop = bl->out[i+1];
76 return cfop->out[0+1];
84 void irg_out_walk_2(ir_node *node, irg_walk_func *pre,
85 irg_walk_func *post, void *env) {
90 assert(get_irn_visited(node) < get_irg_visited(current_ir_graph));
92 set_irn_visited(node, get_irg_visited(current_ir_graph));
94 if (pre) pre(node, env);
96 for (i = 0; i < get_irn_n_outs(node); i++) {
97 succ = get_irn_out(node, i);
98 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
99 irg_out_walk_2(succ, pre, post, env);
102 if (post) post(node, env);
107 void irg_out_walk(ir_node *node,
108 irg_walk_func *pre, irg_walk_func *post,
111 if (get_irg_outs_state(current_ir_graph) != no_outs) {
112 inc_irg_visited (current_ir_graph);
113 irg_out_walk_2(node, pre, post, env);
118 void irg_out_block_walk2(ir_node *bl,
119 irg_walk_func *pre, irg_walk_func *post,
123 assert(get_irn_opcode(bl) == iro_Block);
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);
134 assert(get_irn_opcode(pred) == iro_Block);
136 irg_out_block_walk2(pred, pre, post, env);
145 /* Walks only over Block nodes in the graph. Has it's own visited
146 flag, so that it can be interleaved with the other walker. */
147 void irg_out_block_walk(ir_node *node,
148 irg_walk_func *pre, irg_walk_func *post,
151 assert((get_irn_op(node) == op_Block) || (get_irn_mode(node) == mode_X));
153 inc_irg_block_visited(current_ir_graph);
155 if (get_irn_mode(node) == mode_X) node = node->out[1];
156 assert(get_irn_opcode(node) == iro_Block);
158 irg_out_block_walk2(node, pre, post, env);
164 /**********************************************************************/
165 /** Building and Removing the out datasturcture **/
167 /** The outs of a graph are allocated in a single, large array. **/
168 /** This allows to allocate and deallocate the memory for the outs **/
169 /** on demand. The large array is separated into many small ones **/
170 /** for each node. Only a single field to reference the out array **/
171 /** is stored in each node and a field referencing the large out **/
172 /** array in irgraph. The 0 field of each out array contains the **/
173 /** size of this array. This saves memory in the irnodes themselves.**/
174 /** The construction does two passes over the graph. The first pass **/
175 /** counts the overall number of outs and the outs of each node. It **/
176 /** stores the outs of each node in the out reference of the node. **/
177 /** Then the large array is allocated. The second iteration chops **/
178 /** the large array into smaller parts, sets the out edges and **/
179 /** recounts the out edges. **/
180 /**********************************************************************/
183 /* Returns the amount of out edges for not yet visited successors. */
184 static int count_outs(ir_node *n) {
188 set_irn_visited(n, get_irg_visited(current_ir_graph));
189 n->out = (ir_node **) 1; /* Space for array size. */
191 if ((get_irn_op(n) == op_Block)) start = 0; else start = -1;
192 res = get_irn_arity(n) - start +1; /* --1 or --0; 1 for array size. */
193 for (i = start; i < get_irn_arity(n); i++) {
194 /* Optimize Tuples. They annoy if walking the cfg. */
195 succ = skip_Tuple(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;
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 (get_irn_op(n) == op_Block) start = 0; else start = -1;
222 for (i = start; i < get_irn_arity(n); i++) {
223 succ = get_irn_n(n, i);
225 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
226 free = set_out_edges(succ, free);
227 /* Remember our back edge */
228 succ->out[get_irn_n_outs(succ)+1] = n;
229 succ->out[0] = (ir_node *) (get_irn_n_outs(succ) + 1);
234 static INLINE void fix_start_proj(ir_graph *irg) {
235 ir_node *proj = NULL, *startbl;
237 if (get_Block_n_cfg_outs(get_irg_start_block(irg))) {
238 startbl = get_irg_start_block(irg);
239 for (i = 0; i < get_irn_n_outs(startbl); i++)
240 if (get_irn_mode(get_irn_out(startbl, i)) == mode_X)
241 proj = get_irn_out(startbl, i);
242 if (get_irn_out(proj, 0) == startbl) {
243 assert(get_irn_n_outs(proj) == 2);
244 set_irn_out(proj, 0, get_irn_out(proj, 1));
245 set_irn_out(proj, 1, startbl);
250 void compute_outs(ir_graph *irg) {
251 ir_graph *rem = current_ir_graph;
254 current_ir_graph = irg;
256 /* Update graph state */
257 assert(get_irg_phase_state(current_ir_graph) != phase_building);
258 current_ir_graph->outs_state = outs_consistent;
260 /* This first iteration counts the overall number of out edges and the
261 number of out edges for each node. */
262 inc_irg_visited(irg);
263 n_out_edges = count_outs(get_irg_end(irg));
265 /* allocate memory for all out edges. */
266 irg->outs = (ir_node **) malloc (n_out_edges * sizeof(ir_node *));
268 /* The second iteration splits the irg->outs array into smaller arrays
269 for each node and writes the back edges into this array. */
270 inc_irg_visited(irg);
271 set_out_edges(get_irg_end(irg), irg->outs);
273 /* We want that the out of ProjX from Start contains the next block at
274 position 1, the Start block at position 2. This is necessary for
275 the out block walker. */
278 current_ir_graph = rem;
281 void free_outs(ir_graph *irg) {
283 /* Update graph state */
284 assert(get_irg_phase_state(current_ir_graph) != phase_building);
285 current_ir_graph->outs_state = no_outs;
287 if (irg->outs) free(irg->outs);