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.
16 # include "irnode_t.h"
17 # include "irgraph_t.h"
25 pset *new_identities (void);
26 void del_identities (pset *value_table);
27 void add_identity (pset *value_table, ir_node *node);
30 /* To fill the hash table */
32 add_identity (pset *value_table, ir_node *n) {
33 /* identify_remember (value_table, n);*/
36 /********************************************************************/
37 /* apply optimizations of iropt to all nodes. */
38 /********************************************************************/
41 optimize_in_place_wrapper (ir_node *n, void *env) {
45 /* optimize all sons after recursion, i.e., the sons' sons are
47 for (i = -1; i < get_irn_arity(n); i++) {
48 optimized = optimize_in_place(get_irn_n(n, i));
49 set_irn_n(n, i, optimized);
54 local_optimize_graph (ir_graph *irg) {
55 ir_graph *rem = current_ir_graph;
56 current_ir_graph = irg;
58 /* Should we clean the value_table in irg for the cse? Better do so... */
59 del_identities(irg->value_table);
60 irg->value_table = new_identities();
62 /* walk over the graph */
63 irg_walk(irg->end, NULL, optimize_in_place_wrapper, NULL);
65 current_ir_graph = rem;
68 /********************************************************************/
69 /* Routines for dead node elimination / copying garbage collection */
71 /********************************************************************/
73 /* Remeber the new node in the old node by using a field all nodes have. */
75 set_new_node (ir_node *old, ir_node *new)
80 /* Get this new node, before the old node is forgotton.*/
82 get_new_node (ir_node * n)
88 /* We use the block_visited flag to mark that we have computed the
89 number of useful predecessors for this block.
90 Further we encode the new arity in this flag in the old blocks.
91 Remembering the arity is useful, as it saves a lot of pointer
92 accesses. This function is called for all Phi and Block nodes
95 compute_new_arity(ir_node *b) {
99 irg_v = get_irg_block_visited(current_ir_graph);
100 block_v = get_Block_block_visited(b);
101 if (block_v >= irg_v) {
102 /* we computed the number of preds for this block and saved it in the
104 return block_v - irg_v;
106 /* compute the number of good predecessors */
107 res = get_irn_arity(b);
108 for (i = 0; i < get_irn_arity(b); i++)
109 if (get_irn_opcode(get_irn_n(b, i)) == iro_Bad) res--;
110 /* save it in the flag. */
111 set_Block_block_visited(b, irg_v + res);
116 /* Copies the node to the new obstack. The Ins of the new node point to
117 the predecessors on the old obstack. n->link points to the new node.
118 For Phi and Block nodes the function allocates in-arrays with an arity
119 only for useful predecessors. The arity is determined by counting
120 the non-bad predecessors of the block. */
122 copy_node (ir_node *n, void *env) {
126 if (get_irn_opcode(n) == iro_Block) {
128 new_arity = compute_new_arity(n);
130 block = get_nodes_Block(n);
131 if (get_irn_opcode(n) == iro_Phi) {
132 new_arity = compute_new_arity(block);
134 new_arity = get_irn_arity(n);
137 nn = new_ir_node(current_ir_graph,
143 /* Copy the attributes. These might point to additional data. If this
144 was allocated on the old obstack the pointers now are dangling. This
145 frees e.g. the memory of the graph_arr allocated in new_immBlock. */
150 /* Copies new predecessors of old node to new node remembered in link.
151 Spare the Bad predecessors of Phi and Block nodes. */
153 copy_preds (ir_node *n, void *env) {
154 ir_node *nn, *block, *on;
157 nn = get_new_node(n);
159 if (get_irn_opcode(n) == iro_Block) {
160 /* Don't copy Bad nodes. */
162 for (i = 0; i < get_irn_arity(n); i++)
163 if (get_irn_opcode(get_irn_n(n, i)) != iro_Bad) {
164 set_irn_n (nn, j, get_new_node(get_irn_n(n, i)));
167 /* repair the block visited flag from above misuse */
168 set_Block_block_visited(nn, 0);
169 /* Local optimization could not merge two subsequent blocks if
170 in array contained Bads. Now it's possible, but don't do it for
172 /* GL: this is inefficient!!
173 if (n != current_ir_graph->end_block) on = optimize_in_place(nn);
175 if (nn != on) exchange(nn, on);
177 if (n != current_ir_graph->end_block) {
178 on = optimize_in_place(nn);
180 if (get_irn_op(on) == op_Bad)
181 /* if on is Bad it is the old Bad node. */
182 on = get_new_node(on);
184 nn = on; /* For cse ... */
187 } else if (get_irn_opcode(n) == iro_Phi) {
188 /* Don't copy node if corresponding predecessor in block is Bad.
189 The Block itself should not be Bad. */
190 block = get_nodes_Block(n);
191 set_irn_n (nn, -1, get_new_node(block));
193 for (i = 0; i < get_irn_arity(n); i++)
194 if (get_irn_opcode(get_irn_n(block, i)) != iro_Bad) {
195 set_irn_n (nn, j, get_new_node(get_irn_n(n, i)));
198 /* Compacting the Phi's ins might generate Phis with only one
200 if (get_irn_arity(n) == 1)
201 exchange(n, get_irn_n(n, 0));
203 for (i = -1; i < get_irn_arity(n); i++)
204 set_irn_n (nn, i, get_new_node(get_irn_n(n, i)));
206 /* Now the new node is complete. We can add it to the hash table for cse. */
207 add_identity (current_ir_graph->value_table, nn);
210 /* Copies the graph reachable from current_ir_graph->end to the obstack
212 Then fixes the fields in current_ir_graph containing nodes of the
219 /* Not all nodes remembered in current_ir_graph might be reachable
220 from the end node. Assure their link is set to NULL, so that
221 we can test whether new nodes have been computed. */
222 set_irn_link(get_irg_frame (current_ir_graph), NULL);
223 set_irn_link(get_irg_globals(current_ir_graph), NULL);
224 set_irn_link(get_irg_args (current_ir_graph), NULL);
226 /* we use the block walk flag for removing Bads from Blocks ins. */
227 inc_irg_block_visited(current_ir_graph);
230 irg_walk(get_irg_end(current_ir_graph), copy_node, copy_preds, NULL);
232 /* fix the fields in current_ir_graph */
233 set_irg_end (current_ir_graph, get_new_node(get_irg_end(current_ir_graph)));
234 set_irg_end_block (current_ir_graph, get_new_node(get_irg_end_block(current_ir_graph)));
235 if (get_irn_link(get_irg_frame(current_ir_graph)) == NULL) {
236 copy_node (get_irg_frame(current_ir_graph), NULL);
237 copy_preds(get_irg_frame(current_ir_graph), NULL);
239 if (get_irn_link(get_irg_globals(current_ir_graph)) == NULL) {
240 copy_node (get_irg_globals(current_ir_graph), NULL);
241 copy_preds(get_irg_globals(current_ir_graph), NULL);
243 if (get_irn_link(get_irg_args(current_ir_graph)) == NULL) {
244 copy_node (get_irg_args(current_ir_graph), NULL);
245 copy_preds(get_irg_args(current_ir_graph), NULL);
247 set_irg_start (current_ir_graph, get_new_node(get_irg_start(current_ir_graph)));
249 set_irg_start_block(current_ir_graph,
250 get_new_node(get_irg_start_block(current_ir_graph)));
251 set_irg_frame (current_ir_graph, get_new_node(get_irg_frame(current_ir_graph)));
252 set_irg_globals(current_ir_graph, get_new_node(get_irg_globals(current_ir_graph)));
253 set_irg_args (current_ir_graph, get_new_node(get_irg_args(current_ir_graph)));
254 if (get_irn_link(get_irg_bad(current_ir_graph)) == NULL) {
255 copy_node(get_irg_bad(current_ir_graph), NULL);
256 copy_preds(get_irg_bad(current_ir_graph), NULL);
258 set_irg_bad(current_ir_graph, get_new_node(get_irg_bad(current_ir_graph)));
261 /* Copies all reachable nodes to a new obstack. Removes bad inputs
262 from block nodes and the corresponding inputs from Phi nodes.
263 Merges single exit blocks with single entry blocks and removes
265 Adds all new nodes to a new hash table for cse. Does not
266 perform cse, so the hash table might contain common subexpressions. */
267 /* Amroq call this emigrate() */
269 dead_node_elimination(ir_graph *irg) {
271 struct obstack *graveyard_obst = NULL;
272 struct obstack *rebirth_obst = NULL;
274 /* Remember external state of current_ir_graph. */
275 rem = current_ir_graph;
276 current_ir_graph = irg;
278 if (get_optimize() && get_opt_dead_node_elimination()) {
280 /* A quiet place, where the old obstack can rest in peace,
281 until it will be cremated. */
282 graveyard_obst = irg->obst;
284 /* A new obstack, where the reachable nodes will be copied to. */
285 rebirth_obst = (struct obstack *) xmalloc (sizeof (struct obstack));
286 current_ir_graph->obst = rebirth_obst;
287 obstack_init (current_ir_graph->obst);
289 /* We also need a new hash table for cse */
290 del_identities (irg->value_table);
291 irg->value_table = new_identities ();
293 /* Copy the graph from the old to the new obstack */
296 /* Free memory from old unoptimized obstack */
297 obstack_free(graveyard_obst, 0); /* First empty the obstack ... */
298 xfree (graveyard_obst); /* ... then free it. */
301 current_ir_graph = rem;