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) &&
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, void (pre)(ir_node*, void*),
68 void (post)(ir_node*, void*), void *env) {
72 //printf("++ in walker (%d outs) ", get_irn_n_outs(node)); DDMSG2(node);
75 assert(get_irn_visited(node) < get_irg_visited(current_ir_graph));
77 set_irn_visited(node, get_irg_visited(current_ir_graph));
79 if (pre) pre(node, env);
81 for (i = 0; i < get_irn_n_outs(node); i++) {
82 succ = get_irn_out(node, i);
83 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
84 irg_out_walk_2(succ, pre, post, env);
87 if (post) post(node, env);
89 //printf("++ done walking "); DDMSG2(node);
93 void irg_out_walk(ir_node *node,
94 void (pre)(ir_node*, void*), void (post)(ir_node*, void*),
97 if (get_irg_outs_state(current_ir_graph) != no_outs) {
98 inc_irg_visited (current_ir_graph);
99 irg_out_walk_2(node, pre, post, env);
104 void irg_out_block_walk2(ir_node *bl,
105 void (pre)(ir_node*, void*), void (post)(ir_node*, void*),
109 assert(get_irn_opcode(bl) == iro_Block);
111 if(get_Block_block_visited(bl) < get_irg_block_visited(current_ir_graph)) {
112 set_Block_block_visited(bl, get_irg_block_visited(current_ir_graph));
117 for(i = 0; i < get_Block_n_cfg_outs(bl); i++) {
118 /* find the corresponding predecessor block. */
119 ir_node *pred = get_Block_cfg_out(bl, i);
120 assert(get_irn_opcode(pred) == iro_Block);
122 irg_out_block_walk2(pred, pre, post, env);
131 /* Walks only over Block nodes in the graph. Has it's own visited
132 flag, so that it can be interleaved with the other walker. */
133 void irg_out_block_walk(ir_node *node,
134 void (pre)(ir_node*, void*), void (post)(ir_node*, void*),
137 assert((get_irn_op(node) == op_Block) || (get_irn_mode(node) == mode_X));
139 inc_irg_block_visited(current_ir_graph);
141 if (get_irn_mode(node) == mode_X) node = node->out[1];
142 assert(get_irn_opcode(node) == iro_Block);
144 irg_out_block_walk2(node, pre, post, env);
150 /**********************************************************************/
151 /** Building and Removing the out datasturcture **/
153 /** The outs of a graph are allocated in a single, large array. **/
154 /** This allows to allocate and deallocate the memory for the outs **/
155 /** on demand. The large array is separated into many small ones **/
156 /** for each node. Only a single field to reference the out array **/
157 /** is stored in each node and a field referencing the large out **/
158 /** array in irgraph. The 0 field of each out array contains the **/
159 /** size of this array. This saves memory in the irnodes themselves.**/
160 /** The construction does two passes over the graph. The first pass **/
161 /** counts the overall number of outs and the outs of each node. It **/
162 /** stores the outs of each node in the out reference of the node. **/
163 /** Then the large array is allocated. The second iteration chops **/
164 /** the large array into smaller parts, sets the out edges and **/
165 /** recounts the out edges. **/
166 /**********************************************************************/
169 /* Returns the amount of out edges for not yet visited successors. */
170 int count_outs(ir_node *n) {
174 set_irn_visited(n, get_irg_visited(current_ir_graph));
175 n->out = (ir_node **) 1; /* Space for array size. */
177 if ((get_irn_op(n) == op_Block)) start = 0; else start = -1;
178 res = get_irn_arity(n) - start +1; /* --1 or --0; 1 for array size. */
179 for (i = start; i < get_irn_arity(n); i++) {
180 /* Optimize Tuples. They annoy if walking the cfg. */
181 succ = skip_Tuple(get_irn_n(n, i));
182 set_irn_n(n, i, succ);
183 /* count outs for successors */
184 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
185 res += count_outs(succ);
187 succ->out = (ir_node **)( (int)succ->out +1);
192 ir_node **set_out_edges(ir_node *n, ir_node **free) {
193 int n_outs, start, i;
196 set_irn_visited(n, get_irg_visited(current_ir_graph));
198 /* Allocate my array */
199 n_outs = (int) n->out;
201 free = &free[n_outs];
202 /* We count the successors again, the space will be sufficient.
203 We use this counter to remember the position for the next back
205 n->out[0] = (ir_node *)0;
207 if (get_irn_op(n) == op_Block) start = 0; else start = -1;
208 for (i = start; i < get_irn_arity(n); i++) {
209 succ = get_irn_n(n, i);
211 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
212 free = set_out_edges(succ, free);
213 /* Remember our back edge */
214 succ->out[get_irn_n_outs(succ)+1] = n;
215 succ->out[0] = (ir_node *) (get_irn_n_outs(succ) + 1);
220 inline void fix_start_proj(ir_graph *irg) {
221 ir_node *proj = NULL, *startbl;
223 if (get_Block_n_cfg_outs(get_irg_start_block(irg))) {
224 startbl = get_irg_start_block(irg);
225 for (i = 0; i < get_irn_n_outs(startbl); i++)
226 if (get_irn_mode(get_irn_out(startbl, i)) == mode_X)
227 proj = get_irn_out(startbl, i);
228 if (get_irn_out(proj, 0) == startbl) {
229 assert(get_irn_n_outs(proj) == 2);
230 set_irn_out(proj, 0, get_irn_out(proj, 1));
231 set_irn_out(proj, 1, startbl);
236 void compute_outs(ir_graph *irg) {
237 ir_graph *rem = current_ir_graph;
240 current_ir_graph = irg;
242 /* Update graph state */
243 assert(get_irg_phase_state(current_ir_graph) != phase_building);
244 current_ir_graph->outs_state = outs_consistent;
246 /* This first iteration counts the overall number of out edges and the
247 number of out edges for each node. */
248 inc_irg_visited(irg);
249 n_out_edges = count_outs(get_irg_end(irg));
251 /* allocate memory for all out edges. */
252 irg->outs = (ir_node **) malloc (n_out_edges * sizeof(ir_node *));
254 /* The second iteration splits the irg->outs array into smaller arrays
255 for each node and writes the back edges into this array. */
256 inc_irg_visited(irg);
257 set_out_edges(get_irg_end(irg), irg->outs);
259 /* We want that the out of ProjX from Start contains the next block at
260 position 1, the Start block at position 2. This is necessary for
261 the out block walker. */
264 current_ir_graph = rem;
267 void free_outs(ir_graph *irg) {
269 /* Update graph state */
270 assert(get_irg_phase_state(current_ir_graph) != phase_building);
271 current_ir_graph->outs_state = no_outs;
273 if (irg->outs) free(irg->outs);