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
13 #define DDMSG2(X) printf("%s(l.%i) %s%s: %ld\n", __FUNCTION__, __LINE__, \
14 id_to_str(get_irn_opident(X)), id_to_str(get_irn_modeident(X)), \
16 #define DDMSG5(X) printf("%s%s: %ld", \
17 id_to_str(get_irn_opident(X)), id_to_str(get_irn_modeident(X)), \
23 #include "irgraph_t.h" /* To access irg->outs field (which is private to this module)
24 without public access routine */
26 /**********************************************************************/
27 /** Accessing the out datastructures **/
28 /**********************************************************************/
30 /* returns the number of successors of the node: */
31 inline int get_irn_n_outs (ir_node *node) {
32 return (int)(node->out[0]);
35 /* Access successor n */
36 inline ir_node *get_irn_out (ir_node *node, int pos) {
38 assert(pos >= 0 && pos < get_irn_n_outs(node));
39 return node->out[pos+1];
42 inline void set_irn_out (ir_node *node, int pos, ir_node *out) {
44 assert(pos >= 0 && pos < get_irn_n_outs(node));
45 node->out[pos+1] = out;
48 void irg_out_walk_2(ir_node *node, void (pre)(ir_node*, void*),
49 void (post)(ir_node*, void*), void *env) {
53 //printf("++ in walker (%d outs) ", get_irn_n_outs(node)); DDMSG2(node);
56 assert(get_irn_visited(node) < get_irg_visited(current_ir_graph));
58 set_irn_visited(node, get_irg_visited(current_ir_graph));
60 if (pre) pre(node, env);
62 for (i = 0; i < get_irn_n_outs(node); i++) {
63 succ = get_irn_out(node, i);
64 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
65 irg_out_walk_2(succ, pre, post, env);
68 if (post) post(node, env);
70 //printf("++ done walking "); DDMSG2(node);
74 void irg_out_walk(ir_node *node,
75 void (pre)(ir_node*, void*), void (post)(ir_node*, void*),
78 if (get_irg_outs_state(current_ir_graph) != no_outs) {
79 inc_irg_visited (current_ir_graph);
80 irg_out_walk_2(node, pre, post, env);
85 /* Walks only over Block nodes in the graph. Has it's own visited
86 flag, so that it can be interleaved with the other walker. */
87 void irg_out_block_walk(ir_node *node,
88 void (pre)(ir_node*, void*), void (post)(ir_node*, void*),
92 /**********************************************************************/
93 /** Building and Removing the out datasturcture **/
95 /** The outs of a graph are allocated in a single, large array. **/
96 /** This allows to allocate and deallocate the memory for the outs **/
97 /** on demand. The large array is separated into many small ones **/
98 /** for each node. Only a single field to reference the out array **/
99 /** is stored in each node and a field referencing the large out **/
100 /** array in irgraph. The 0 field of each out array contains the **/
101 /** size of this array. This saves memory in the irnodes themselves.**/
102 /** The construction does two passes over the graph. The first pass **/
103 /** counts the overall number of outs and the outs of each node. It **/
104 /** stores the outs of each node in the out reference of the node. **/
105 /** Then the large array is allocated. The second iteration chops **/
106 /** the large array into smaller parts, sets the out edges and **/
107 /** recounts the out edges. **/
108 /**********************************************************************/
111 /* Returns the amount of out edges for not yet visited successors. */
112 int count_outs(ir_node *n) {
116 set_irn_visited(n, get_irg_visited(current_ir_graph));
117 n->out = (ir_node **) 1; /* Space for array size. */
119 if ((get_irn_op(n) == op_Block)) start = 0; else start = -1;
120 res = get_irn_arity(n) - start +1; /* --1 or --0; 1 for array size. */
121 for (i = start; i < get_irn_arity(n); i++) {
122 succ = get_irn_n(n, i);
123 /* count outs for successors */
124 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
125 res += count_outs(succ);
127 succ->out = (ir_node **)( (int)succ->out +1);
132 ir_node **set_out_edges(ir_node *n, ir_node **free) {
133 int n_outs, start, i;
136 set_irn_visited(n, get_irg_visited(current_ir_graph));
138 /* Allocate my array */
139 n_outs = (int) n->out;
141 free = &free[n_outs];
142 /* We count the successors again, the space will be sufficient.
143 We use this counter to remember the position for the next back
145 n->out[0] = (ir_node *)0;
147 if (get_irn_op(n) == op_Block) start = 0; else start = -1;
148 for (i = start; i < get_irn_arity(n); i++) {
149 succ = get_irn_n(n, i);
151 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
152 free = set_out_edges(succ, free);
153 /* Remember our back edge */
154 succ->out[get_irn_n_outs(succ)+1] = n;
155 succ->out[0] = (ir_node *) (get_irn_n_outs(succ) + 1);
160 void compute_outs(ir_graph *irg) {
161 ir_graph *rem = current_ir_graph;
164 current_ir_graph = irg;
166 /* Update graph state */
167 assert(get_irg_phase_state(current_ir_graph) != phase_building);
168 current_ir_graph->outs_state = outs_consistent;
170 /* This first iteration counts the overall number of out edges and the
171 number of out edges for each node. */
172 inc_irg_visited(irg);
173 n_out_edges = count_outs(get_irg_end(irg));
175 /* allocate memory for all out edges. */
176 irg->outs = (ir_node **) malloc (n_out_edges * sizeof(ir_node *));
178 /* The second iteration splits the irg->outs array into smaller arrays
179 for each node and writes the back edges into this array. */
180 inc_irg_visited(irg);
181 set_out_edges(get_irg_end(irg), irg->outs);
183 current_ir_graph = rem;
186 void free_outs(ir_graph *irg) {
188 /* Update graph state */
189 assert(get_irg_phase_state(current_ir_graph) != phase_building);
190 current_ir_graph->outs_state = no_outs;
192 if (irg->outs) free(irg->outs);