1 /* Copyright (C) 2002 by Universitaet Karlsruhe
2 ** All rights reserved.
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)
57 ir_node *cfop = bl->out[i+1];
58 return cfop->out[0+1];
65 void irg_out_walk_2(ir_node *node, void (pre)(ir_node*, void*),
66 void (post)(ir_node*, void*), void *env) {
70 //printf("++ in walker (%d outs) ", get_irn_n_outs(node)); DDMSG2(node);
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);
87 //printf("++ done walking "); DDMSG2(node);
91 void irg_out_walk(ir_node *node,
92 void (pre)(ir_node*, void*), void (post)(ir_node*, void*),
95 if (get_irg_outs_state(current_ir_graph) != no_outs) {
96 inc_irg_visited (current_ir_graph);
97 irg_out_walk_2(node, pre, post, env);
102 void irg_out_block_walk2(ir_node *bl,
103 void (pre)(ir_node*, void*), void (post)(ir_node*, void*),
107 assert(get_irn_opcode(bl) == iro_Block);
109 if(get_Block_block_visited(bl) < get_irg_block_visited(current_ir_graph)) {
110 set_Block_block_visited(bl, get_irg_block_visited(current_ir_graph));
115 for(i = 0; i < get_Block_n_cfg_outs(bl); i++) {
116 /* find the corresponding predecessor block. */
117 ir_node *pred = get_Block_cfg_out(bl, i);
118 assert(get_irn_opcode(pred) == iro_Block);
120 irg_out_block_walk2(pred, pre, post, env);
129 /* Walks only over Block nodes in the graph. Has it's own visited
130 flag, so that it can be interleaved with the other walker. */
131 void irg_out_block_walk(ir_node *node,
132 void (pre)(ir_node*, void*), void (post)(ir_node*, void*),
135 assert((get_irn_op(node) == op_Block) || (get_irn_mode(node) == mode_X));
137 inc_irg_block_visited(current_ir_graph);
139 if (get_irn_mode(node) == mode_X) node = node->out[1];
140 assert(get_irn_opcode(node) == iro_Block);
142 irg_out_block_walk2(node, pre, post, env);
148 /**********************************************************************/
149 /** Building and Removing the out datasturcture **/
151 /** The outs of a graph are allocated in a single, large array. **/
152 /** This allows to allocate and deallocate the memory for the outs **/
153 /** on demand. The large array is separated into many small ones **/
154 /** for each node. Only a single field to reference the out array **/
155 /** is stored in each node and a field referencing the large out **/
156 /** array in irgraph. The 0 field of each out array contains the **/
157 /** size of this array. This saves memory in the irnodes themselves.**/
158 /** The construction does two passes over the graph. The first pass **/
159 /** counts the overall number of outs and the outs of each node. It **/
160 /** stores the outs of each node in the out reference of the node. **/
161 /** Then the large array is allocated. The second iteration chops **/
162 /** the large array into smaller parts, sets the out edges and **/
163 /** recounts the out edges. **/
164 /**********************************************************************/
167 /* Returns the amount of out edges for not yet visited successors. */
168 int count_outs(ir_node *n) {
172 set_irn_visited(n, get_irg_visited(current_ir_graph));
173 n->out = (ir_node **) 1; /* Space for array size. */
175 if ((get_irn_op(n) == op_Block)) start = 0; else start = -1;
176 res = get_irn_arity(n) - start +1; /* --1 or --0; 1 for array size. */
177 for (i = start; i < get_irn_arity(n); i++) {
178 /* Optimize Tuples. They annoy if walking the cfg. */
179 succ = skip_Tuple(get_irn_n(n, i));
180 set_irn_n(n, i, succ);
181 /* count outs for successors */
182 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
183 res += count_outs(succ);
185 succ->out = (ir_node **)( (int)succ->out +1);
190 ir_node **set_out_edges(ir_node *n, ir_node **free) {
191 int n_outs, start, i;
194 set_irn_visited(n, get_irg_visited(current_ir_graph));
196 /* Allocate my array */
197 n_outs = (int) n->out;
199 free = &free[n_outs];
200 /* We count the successors again, the space will be sufficient.
201 We use this counter to remember the position for the next back
203 n->out[0] = (ir_node *)0;
205 if (get_irn_op(n) == op_Block) start = 0; else start = -1;
206 for (i = start; i < get_irn_arity(n); i++) {
207 succ = get_irn_n(n, i);
209 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
210 free = set_out_edges(succ, free);
211 /* Remember our back edge */
212 succ->out[get_irn_n_outs(succ)+1] = n;
213 succ->out[0] = (ir_node *) (get_irn_n_outs(succ) + 1);
218 inline void fix_start_proj(ir_graph *irg) {
219 ir_node *proj, *startbl;
221 if (get_Block_n_cfg_outs(get_irg_start_block(irg))) {
222 startbl = get_irg_start_block(irg);
223 for (i = 0; i < get_irn_n_outs(startbl); i++)
224 if (get_irn_mode(get_irn_out(startbl, i)) == mode_X)
225 proj = get_irn_out(startbl, i);
226 if (get_irn_out(proj, 0) == startbl) {
227 assert(get_irn_n_outs(proj) == 2);
228 set_irn_out(proj, 0, get_irn_out(proj, 1));
229 set_irn_out(proj, 1, startbl);
234 void compute_outs(ir_graph *irg) {
235 ir_graph *rem = current_ir_graph;
238 current_ir_graph = irg;
240 /* Update graph state */
241 assert(get_irg_phase_state(current_ir_graph) != phase_building);
242 current_ir_graph->outs_state = outs_consistent;
244 /* This first iteration counts the overall number of out edges and the
245 number of out edges for each node. */
246 inc_irg_visited(irg);
247 n_out_edges = count_outs(get_irg_end(irg));
249 /* allocate memory for all out edges. */
250 irg->outs = (ir_node **) malloc (n_out_edges * sizeof(ir_node *));
252 /* The second iteration splits the irg->outs array into smaller arrays
253 for each node and writes the back edges into this array. */
254 inc_irg_visited(irg);
255 set_out_edges(get_irg_end(irg), irg->outs);
257 /* We want that the out of ProjX from Start contains the next block at
258 position 1, the Start block at position 2. This is necessary for
259 the out block walker. */
262 current_ir_graph = rem;
265 void free_outs(ir_graph *irg) {
267 /* Update graph state */
268 assert(get_irg_phase_state(current_ir_graph) != phase_building);
269 current_ir_graph->outs_state = no_outs;
271 if (irg->outs) free(irg->outs);