1 /* Copyright (C) 1998 - 2000 by Universitaet Karlsruhe
2 ** All rights reserved.
4 ** Author: Christian Schaefer
6 ** Optimizations for a whole ir graph, i.e., a procedure.
12 # include "irnode_t.h"
13 # include "irgraph_t.h"
20 /********************************************************************/
21 /* apply optimizations of iropt to all nodes. */
22 /********************************************************************/
25 optimize_in_place_wrapper (ir_node *n, void *env) {
29 /* optimize all sons after recursion, i.e., the sons' sons are
31 for (i = -1; i < get_irn_arity(n); i++) {
32 optimized = optimize_in_place(get_irn_n(n, i));
33 set_irn_n(n, i, optimized);
38 local_optimize_graph (ir_graph *irg) {
39 ir_graph *rem = current_ir_graph;
40 current_ir_graph = irg;
42 /* walk over the graph */
43 irg_walk(irg->end, NULL, optimize_in_place_wrapper, NULL);
45 current_ir_graph = rem;
48 /********************************************************************/
49 /* Routines for dead node elimination / copying garbage collection */
51 /********************************************************************/
53 /* Remeber the new node in the old node by using a field all nodes have. */
55 set_new_node (ir_node *old, ir_node *new)
60 /* Get this new node, before the old node is forgotton.*/
62 get_new_node (ir_node * n)
68 /* We use the block_visited flag to mark that we have computed the
69 number of useful predecessors for this block.
70 Further we encode the new arity in this flag. Remembering the arity is
71 useful, as it saves a lot of pointer accesses. This function is called
72 for all Phi and Block nodes in a Block. */
74 compute_new_arity(ir_node *b) {
78 irg_v = get_irg_block_visited(current_ir_graph);
79 block_v = get_Block_block_visited(b);
80 if (block_v >= irg_v) {
81 /* we computed the number of preds for this block and saved it in the
83 return block_v - irg_v;
85 /* compute the number of good predecessors */
86 res = get_irn_arity(b);
87 for (i = 0; i < get_irn_arity(b); i++)
88 if (get_irn_opcode(get_irn_n(b, i)) == iro_Bad) res--;
89 /* save it in the flag. */
90 set_Block_block_visited(b, irg_v + res);
95 /* Copies the node to the new obstack. The Ins of the new node point to
96 the predecessors on the old obstack. n->link points to the new node.
97 For Phi and Block nodes the function allocate in arrays with an arity
98 only for useful predecessors. The arity is determined by counting
99 the non-bad predecessors of the block. */
101 copy_node (ir_node *n, void *env) {
105 if (get_irn_opcode(n) == iro_Block) {
107 new_arity = compute_new_arity(n);
109 block = get_nodes_Block(n);
110 if (get_irn_opcode(n) == iro_Phi) {
111 new_arity = compute_new_arity(block);
113 new_arity = get_irn_arity(n);
116 nn = new_ir_node(current_ir_graph,
126 /* Copies new predecessors of old node to new node remembered in link.
127 Spare the Bad predecessors of Phi and Block nodes. */
129 copy_preds (ir_node *n, void *env) {
130 ir_node *nn, *block/*, *on*/;
133 nn = get_new_node(n);
135 if (get_irn_opcode(n) == iro_Block) {
136 /* Don't copy Bad nodes. */
138 for (i = 0; i < get_irn_arity(n); i++)
139 if (get_irn_opcode(get_irn_n(n, i)) != iro_Bad) {
140 set_irn_n (nn, j, get_new_node(get_irn_n(n, i)));
143 /* repair the block visited flag from above misuse */
144 set_Block_block_visited(nn, 0);
145 /* Local optimization could not merge two subsequent blocks if
146 in array contained Bads. Now it's possible. *
147 on = optimize_in_place(nn);
148 if (nn != on) exchange(nn, on);*/
149 } else if (get_irn_opcode(n) == iro_Phi) {
150 /* Don't copy node if corresponding predecessor in block is Bad.
151 The Block itself should not be Bad. */
152 block = get_nodes_Block(n);
153 set_irn_n (nn, -1, get_new_node(block));
155 for (i = 0; i < get_irn_arity(n); i++)
156 if (get_irn_opcode(get_irn_n(block, i)) != iro_Bad) {
157 set_irn_n (nn, j, get_new_node(get_irn_n(n, i)));
160 /* Compacting the Phi's ins might generate Phis with only one
162 if (get_irn_arity(n) == 1)
163 exchange(n, get_irn_n(n, 0)); */
165 for (i = -1; i < get_irn_arity(n); i++)
166 set_irn_n (nn, i, get_new_node(get_irn_n(n, i)));
170 /* Copies the graph reachable from current_ir_graph->end to the obstack
172 Then fixes the fields in current_ir_graph containing nodes of the
176 /* Not all nodes remembered in current_ir_graph might be reachable
177 from the end node. Assure their link is set to NULL so that
178 we can test whether new nodes have been computed. */
179 set_irn_link(get_irg_frame (current_ir_graph), NULL);
180 set_irn_link(get_irg_globals(current_ir_graph), NULL);
181 set_irn_link(get_irg_args (current_ir_graph), NULL);
183 /* we use the block walk flag for removing Bads from Blocks ins. */
184 inc_irg_block_visited(current_ir_graph);
187 irg_walk(get_irg_end(current_ir_graph), copy_node, copy_preds, NULL);
189 /* fix the fields in current_ir_graph */
190 set_irg_end (current_ir_graph, get_new_node(get_irg_end(current_ir_graph)));
191 set_irg_end_block (current_ir_graph, get_new_node(get_irg_end_block(current_ir_graph)));
192 if (get_irn_link(get_irg_frame(current_ir_graph)) == NULL)
193 irg_walk(get_irg_frame(current_ir_graph), copy_node, copy_preds, NULL);
194 if (get_irn_link(get_irg_globals(current_ir_graph)) == NULL)
195 irg_walk(get_irg_globals(current_ir_graph), copy_node, copy_preds, NULL);
196 if (get_irn_link(get_irg_args(current_ir_graph)) == NULL)
197 irg_walk(get_irg_args(current_ir_graph), copy_node, copy_preds, NULL);
198 set_irg_start (current_ir_graph, get_new_node(get_irg_start(current_ir_graph)));
199 set_irg_start_block(current_ir_graph,
200 get_new_node(get_irg_start_block(current_ir_graph)));
201 set_irg_frame (current_ir_graph, get_new_node(get_irg_frame(current_ir_graph)));
202 set_irg_globals(current_ir_graph, get_new_node(get_irg_globals(current_ir_graph)));
203 set_irg_args (current_ir_graph, get_new_node(get_irg_args(current_ir_graph)));
204 if (get_irn_link(get_irg_bad(current_ir_graph)) == NULL) {
205 copy_node(get_irg_bad(current_ir_graph), NULL);
206 copy_preds(get_irg_bad(current_ir_graph), NULL);
208 set_irg_bad(current_ir_graph, get_new_node(get_irg_bad(current_ir_graph)));
212 /* Amroq call this emigrate() */
214 dead_node_elimination(ir_graph *irg) {
216 struct obstack *graveyard_obst = NULL;
217 struct obstack *rebirth_obst = NULL;
219 /* Remember external state of current_ir_graph. */
220 rem = current_ir_graph;
221 current_ir_graph = irg;
223 if (get_optimize() && get_opt_dead_node_elimination()) {
225 /* A quiet place, where the old obstack can rest in peace,
226 until it will be cremated. */
227 graveyard_obst = irg->obst;
229 /* A new obstack, where the reachable nodes will be copied to. */
230 rebirth_obst = (struct obstack *) xmalloc (sizeof (struct obstack));
231 current_ir_graph->obst = rebirth_obst;
232 obstack_init (current_ir_graph->obst);
234 /* Copy the graph from the old to the new obstack */
237 /* Free memory from old unoptimized obstack */
238 obstack_free(graveyard_obst, 0); /* First empty the obstack ... */
239 xfree (graveyard_obst); /* ... then free it. */
242 current_ir_graph = rem;