1 /* Copyright (C) 2002 by Universitaet Karlsruhe
4 * Authors: Goetz Lindenmaier
6 * irouts.c --- Compute out edges for ir nodes (also called def-use
15 #include "irgraph_t.h" /* To access irg->outs field (which is private to this module)
16 without public access routine */
18 /**********************************************************************/
19 /** Accessing the out datastructures **/
20 /**********************************************************************/
22 /* returns the number of successors of the node: */
23 INLINE int get_irn_n_outs (ir_node *node) {
24 return (int)(node->out[0]);
27 /* Access successor n */
28 INLINE ir_node *get_irn_out (ir_node *node, int pos) {
30 assert(pos >= 0 && pos < get_irn_n_outs(node));
31 return node->out[pos+1];
34 INLINE void set_irn_out (ir_node *node, int pos, ir_node *out) {
36 assert(pos >= 0 && pos < get_irn_n_outs(node));
37 node->out[pos+1] = out;
41 INLINE int get_Block_n_cfg_outs (ir_node *bl) {
42 int i, n_cfg_outs = 0;
43 assert(bl && (get_irn_op(bl) == op_Block));
44 for (i = 0; i < (int)bl->out[0]; i++)
45 if ((get_irn_mode(bl->out[i+1]) == mode_X) &&
46 (get_irn_op(bl->out[i+1]) != op_End)) n_cfg_outs++;
51 INLINE ir_node *get_Block_cfg_out (ir_node *bl, int pos) {
53 assert(bl && (get_irn_op(bl) == op_Block));
54 for (i = 0; i < (int)bl->out[0]; i++)
55 if ((get_irn_mode(bl->out[i+1]) == mode_X) &&
56 (get_irn_op(bl->out[i+1]) != op_End)) {
58 ir_node *cfop = bl->out[i+1];
59 return cfop->out[0+1];
67 void irg_out_walk_2(ir_node *node, irg_walk_func *pre,
68 irg_walk_func *post, void *env) {
73 assert(get_irn_visited(node) < get_irg_visited(current_ir_graph));
75 set_irn_visited(node, get_irg_visited(current_ir_graph));
77 if (pre) pre(node, env);
79 for (i = 0; i < get_irn_n_outs(node); i++) {
80 succ = get_irn_out(node, i);
81 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
82 irg_out_walk_2(succ, pre, post, env);
85 if (post) post(node, env);
90 void irg_out_walk(ir_node *node,
91 irg_walk_func *pre, irg_walk_func *post,
94 if (get_irg_outs_state(current_ir_graph) != no_outs) {
95 inc_irg_visited (current_ir_graph);
96 irg_out_walk_2(node, pre, post, env);
101 void irg_out_block_walk2(ir_node *bl,
102 irg_walk_func *pre, irg_walk_func *post,
106 assert(get_irn_opcode(bl) == iro_Block);
108 if(get_Block_block_visited(bl) < get_irg_block_visited(current_ir_graph)) {
109 set_Block_block_visited(bl, get_irg_block_visited(current_ir_graph));
114 for(i = 0; i < get_Block_n_cfg_outs(bl); i++) {
115 /* find the corresponding predecessor block. */
116 ir_node *pred = get_Block_cfg_out(bl, i);
117 assert(get_irn_opcode(pred) == iro_Block);
119 irg_out_block_walk2(pred, pre, post, env);
128 /* Walks only over Block nodes in the graph. Has it's own visited
129 flag, so that it can be interleaved with the other walker. */
130 void irg_out_block_walk(ir_node *node,
131 irg_walk_func *pre, irg_walk_func *post,
134 assert((get_irn_op(node) == op_Block) || (get_irn_mode(node) == mode_X));
136 inc_irg_block_visited(current_ir_graph);
138 if (get_irn_mode(node) == mode_X) node = node->out[1];
139 assert(get_irn_opcode(node) == iro_Block);
141 irg_out_block_walk2(node, pre, post, env);
147 /**********************************************************************/
148 /** Building and Removing the out datasturcture **/
150 /** The outs of a graph are allocated in a single, large array. **/
151 /** This allows to allocate and deallocate the memory for the outs **/
152 /** on demand. The large array is separated into many small ones **/
153 /** for each node. Only a single field to reference the out array **/
154 /** is stored in each node and a field referencing the large out **/
155 /** array in irgraph. The 0 field of each out array contains the **/
156 /** size of this array. This saves memory in the irnodes themselves.**/
157 /** The construction does two passes over the graph. The first pass **/
158 /** counts the overall number of outs and the outs of each node. It **/
159 /** stores the outs of each node in the out reference of the node. **/
160 /** Then the large array is allocated. The second iteration chops **/
161 /** the large array into smaller parts, sets the out edges and **/
162 /** recounts the out edges. **/
163 /**********************************************************************/
166 /* Returns the amount of out edges for not yet visited successors. */
167 static int count_outs(ir_node *n) {
171 set_irn_visited(n, get_irg_visited(current_ir_graph));
172 n->out = (ir_node **) 1; /* Space for array size. */
174 if ((get_irn_op(n) == op_Block)) start = 0; else start = -1;
175 res = get_irn_arity(n) - start +1; /* --1 or --0; 1 for array size. */
176 for (i = start; i < get_irn_arity(n); i++) {
177 /* Optimize Tuples. They annoy if walking the cfg. */
178 succ = skip_Tuple(get_irn_n(n, i));
179 set_irn_n(n, i, succ);
180 /* count outs for successors */
181 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
182 res += count_outs(succ);
184 succ->out = (ir_node **)( (int)succ->out +1);
189 static ir_node **set_out_edges(ir_node *n, ir_node **free) {
190 int n_outs, start, i;
193 set_irn_visited(n, get_irg_visited(current_ir_graph));
195 /* Allocate my array */
196 n_outs = (int) n->out;
198 free = &free[n_outs];
199 /* We count the successors again, the space will be sufficient.
200 We use this counter to remember the position for the next back
202 n->out[0] = (ir_node *)0;
204 if (get_irn_op(n) == op_Block) start = 0; else start = -1;
205 for (i = start; i < get_irn_arity(n); i++) {
206 succ = get_irn_n(n, i);
208 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
209 free = set_out_edges(succ, free);
210 /* Remember our back edge */
211 succ->out[get_irn_n_outs(succ)+1] = n;
212 succ->out[0] = (ir_node *) (get_irn_n_outs(succ) + 1);
217 static INLINE void fix_start_proj(ir_graph *irg) {
218 ir_node *proj = NULL, *startbl;
220 if (get_Block_n_cfg_outs(get_irg_start_block(irg))) {
221 startbl = get_irg_start_block(irg);
222 for (i = 0; i < get_irn_n_outs(startbl); i++)
223 if (get_irn_mode(get_irn_out(startbl, i)) == mode_X)
224 proj = get_irn_out(startbl, i);
225 if (get_irn_out(proj, 0) == startbl) {
226 assert(get_irn_n_outs(proj) == 2);
227 set_irn_out(proj, 0, get_irn_out(proj, 1));
228 set_irn_out(proj, 1, startbl);
233 void compute_outs(ir_graph *irg) {
234 ir_graph *rem = current_ir_graph;
237 current_ir_graph = irg;
239 /* Update graph state */
240 assert(get_irg_phase_state(current_ir_graph) != phase_building);
241 current_ir_graph->outs_state = outs_consistent;
243 /* This first iteration counts the overall number of out edges and the
244 number of out edges for each node. */
245 inc_irg_visited(irg);
246 n_out_edges = count_outs(get_irg_end(irg));
248 /* allocate memory for all out edges. */
249 irg->outs = (ir_node **) malloc (n_out_edges * sizeof(ir_node *));
251 /* The second iteration splits the irg->outs array into smaller arrays
252 for each node and writes the back edges into this array. */
253 inc_irg_visited(irg);
254 set_out_edges(get_irg_end(irg), irg->outs);
256 /* We want that the out of ProjX from Start contains the next block at
257 position 1, the Start block at position 2. This is necessary for
258 the out block walker. */
261 current_ir_graph = rem;
264 void free_outs(ir_graph *irg) {
266 /* Update graph state */
267 assert(get_irg_phase_state(current_ir_graph) != phase_building);
268 current_ir_graph->outs_state = no_outs;
270 if (irg->outs) free(irg->outs);