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;
249 #if 0 /* An old implementation */
251 /* To break the recursion of the graph walk if there are loops in
252 the graph we have to allocate new nodes for Phis and blocks
253 before descending. Here we use the old predecessors for the
254 new nodes. These are replaced by the proper predecessors in
256 It turned out that it is not sufficient to just break loops
257 for Phi and Block nodes, as the walker can hit visited but
258 not copied nodes at any point in the graph.
259 A simple fix would be allocating Id's for every node and then
260 exchanging them, but this will cause new dead nodes on the new
262 So now there is a different implementation more based on the
263 view on the graph as a graph than as a represented program. */
265 create_dummy (ir_node *n, void *env) {
268 /* Assure link is set to NULL so we can test whether there is a
269 new node by checking link.
270 set_irn_link(n, NULL); */
272 switch (get_irn_opcode(n)) {
274 set_new_node(n, new_ir_node(current_ir_graph, NULL, op_Block, mode_R,
275 get_irn_arity(n), get_irn_in(n)));
278 set_new_node(n, new_ir_node(current_ir_graph, NULL, op_Phi,
280 get_irn_arity(n), get_irn_in(n)));
283 } /* end switch (get_irn_opcode(n)) */
286 /* Create a copy of this node on a new obstack. */
288 copy_node2 (ir_node *n, void *env) {
298 a = get_binop_left(n);
299 b = get_binop_right(n);
300 } else if (is_unop(n)) {
304 switch (get_irn_opcode(n)) {
307 res = get_new_node(n);
309 for (i = 0; i < get_Block_n_cfgpreds(n); i++)
310 set_Block_cfgpred(res, i, get_new_node(get_Block_cfgpred(n, i)));
311 set_Block_matured(res, 1);
315 res = new_r_Start (current_ir_graph, get_new_node(get_nodes_Block(n)));
318 res = new_r_End (current_ir_graph, get_new_node(get_nodes_Block(n)));
319 current_ir_graph -> end = res;
320 current_ir_graph -> end_block = get_nodes_Block(res);
323 res = new_r_Jmp (current_ir_graph, get_new_node(get_nodes_Block(n)));
326 res = new_r_Cond (current_ir_graph, get_new_node(get_nodes_Block(n)),
327 get_new_node(get_Cond_selector(n)));
332 in = get_Return_res_arr(n);
333 for (i = 0; i < get_Return_n_res(n); i++)
334 set_Return_res(n, i, get_new_node(get_Return_res(n, i)));
335 res = new_r_Return (current_ir_graph,
336 get_new_node(get_nodes_Block(n)),
337 get_new_node(get_Return_mem(n)),
338 get_Return_n_res(n), in);
342 res = new_r_Raise (current_ir_graph,
343 get_new_node(get_nodes_Block(n)),
344 get_new_node(get_Raise_mem(n)),
345 get_new_node(get_Raise_exo_ptr(n)));
348 res = new_r_Const (current_ir_graph, get_new_node(get_nodes_Block(n)),
349 get_irn_mode(n), get_Const_tarval(n));
353 type_or_id_p value = NULL;
355 if ((get_SymConst_kind(n)==type_tag) || (get_SymConst_kind(n)==size))
358 value = (type_or_id_p) get_SymConst_type(n);
362 if (get_SymConst_kind(n)==linkage_ptr_info)
364 value = (type_or_id_p) get_SymConst_ptrinfo(n);
367 res = new_r_SymConst (current_ir_graph, get_new_node(get_nodes_Block(n)),
368 value, get_SymConst_kind (n));
373 ir_node **in = get_Sel_index_arr(n);
374 for (i = 0; i < get_Sel_n_index(n); i++)
375 set_Sel_index(n, i, get_new_node(get_Sel_index(n, i)));
376 res = new_r_Sel (current_ir_graph, get_new_node(get_nodes_Block(n)),
377 get_new_node(get_Sel_mem(n)),
378 get_new_node(get_Sel_ptr(n)), get_Sel_n_index(n),
379 in, get_Sel_entity(n));
385 in = get_Call_param_arr(n);
387 for (i = 0; i < get_Call_arity(n); i++)
388 set_Call_param(n, i, get_new_node(get_Call_param(n, i)));
389 res = new_r_Call (current_ir_graph,
390 get_new_node(get_nodes_Block(n)),
391 get_new_node(get_Call_mem(n)),
392 get_new_node(get_Call_ptr(n)),
393 get_Call_arity(n), in,
398 res = new_r_Add (current_ir_graph, get_new_node(get_nodes_Block(n)),
399 get_new_node(a), get_new_node(b), get_irn_mode(n));
403 res = new_r_Sub (current_ir_graph, get_new_node(get_nodes_Block(n)),
404 get_new_node(a), get_new_node(b), get_irn_mode(n));
408 res = new_r_Minus (current_ir_graph, get_new_node(get_nodes_Block(n)),
409 get_new_node(a), get_irn_mode(n));
412 res = new_r_Mul (current_ir_graph, get_new_node(get_nodes_Block(n)),
413 get_new_node(a), get_new_node(b), get_irn_mode(n));
416 res = new_r_Quot (current_ir_graph, get_new_node(get_nodes_Block(n)),
417 get_new_node(get_Quot_mem(n)), get_new_node(a),
421 res = new_r_DivMod (current_ir_graph, get_new_node(get_nodes_Block(n)),
422 get_new_node(get_DivMod_mem(n)), get_new_node(a),
426 res = new_r_Div (current_ir_graph, get_new_node(get_nodes_Block(n)),
427 get_new_node(get_Div_mem(n)), get_new_node(a),
431 res = new_r_Mod (current_ir_graph, get_new_node(get_nodes_Block(n)),
432 get_new_node(get_Mod_mem(n)), get_new_node(a),
436 res = new_r_Abs (current_ir_graph, get_new_node(get_nodes_Block(n)),
437 get_new_node(get_Abs_op(n)), get_irn_mode(n));
440 res = new_r_And (current_ir_graph, get_new_node(get_nodes_Block(n)),
441 get_new_node(a), get_new_node(b), get_irn_mode(n));
444 res = new_r_Or (current_ir_graph, get_new_node(get_nodes_Block(n)),
445 get_new_node(a), get_new_node(b), get_irn_mode(n));
448 res = new_r_Eor (current_ir_graph, get_new_node(get_nodes_Block(n)),
449 get_new_node(a), get_new_node(b), get_irn_mode(n));
452 res = new_r_Not (current_ir_graph, get_new_node(get_nodes_Block(n)),
453 get_new_node(get_Not_op(n)), get_irn_mode(n));
456 res = new_r_Cmp (current_ir_graph,
457 get_new_node(get_nodes_Block(n)),
458 get_new_node(get_Cmp_left(n)),
459 get_new_node(get_Cmp_right(n)));
462 res = new_r_Shl (current_ir_graph, get_new_node(get_nodes_Block(n)),
463 get_new_node(get_Shl_left(n)),
464 get_new_node(get_Shl_right(n)), get_irn_mode(n));
467 res = new_r_Shr (current_ir_graph, get_new_node(get_nodes_Block(n)),
468 get_new_node(get_Shr_left(n)),
469 get_new_node(get_Shr_right(n)), get_irn_mode(n));
472 res = new_r_Shrs (current_ir_graph, get_new_node(get_nodes_Block(n)),
473 get_new_node(get_Shrs_left(n)),
474 get_new_node(get_Shrs_right(n)), get_irn_mode(n));
477 res = new_r_Rot (current_ir_graph, get_new_node(get_nodes_Block(n)),
478 get_new_node(get_Rot_left(n)),
479 get_new_node(get_Rot_right(n)), get_irn_mode(n));
482 res = new_r_Conv (current_ir_graph, get_new_node(get_nodes_Block(n)),
483 get_new_node(get_Conv_op(n)),
488 res = get_new_node(n);
489 for (i = 0; i < get_Phi_n_preds(n); i++)
490 set_Phi_pred(res, i, get_new_node(get_Phi_pred(n, i)));
491 set_nodes_Block(res, get_new_node(get_nodes_Block(n)));
495 res = new_r_Load (current_ir_graph, get_new_node(get_nodes_Block(n)),
496 get_new_node(get_Load_mem(n)),
497 get_new_node(get_Load_ptr(n)));
500 res = new_r_Store (current_ir_graph, get_new_node(get_nodes_Block(n)),
501 get_new_node(get_Store_mem(n)),
502 get_new_node(get_Store_ptr(n)),
503 get_new_node(get_Store_value(n)));
506 res = new_r_Alloc (current_ir_graph, get_new_node(get_nodes_Block(n)),
507 get_new_node(get_Alloc_mem(n)),
508 get_new_node(get_Alloc_size(n)),
509 get_Alloc_type(n), get_Alloc_where(n));
513 res = new_r_Free (current_ir_graph, get_new_node(get_nodes_Block(n)),
514 get_new_node(get_Free_mem(n)),
515 get_new_node(get_Free_ptr(n)),
516 get_new_node(get_Free_size(n)), get_Free_type(n));
520 ir_node **in = get_Sync_preds_arr(n);
521 for (i = 0; i < get_Sync_n_preds(n); i++)
522 set_Sync_pred(n, i, get_new_node(get_Sync_pred(n, i)));
523 res = new_r_Sync (current_ir_graph, get_new_node(get_nodes_Block(n)),
524 get_Sync_n_preds(n), in);
528 res = new_r_Proj (current_ir_graph, get_new_node(get_nodes_Block(n)),
529 get_new_node(get_Proj_pred(n)), get_irn_mode(n),
535 ir_node **in = get_Tuple_preds_arr(n);
536 for (i = 0; i < get_Tuple_n_preds(n); i++)
537 set_Tuple_pred(n, i, get_new_node(get_Tuple_pred(n, i)));
538 res = new_r_Tuple (current_ir_graph, get_new_node(get_nodes_Block(n)),
539 get_Tuple_n_preds(n), in);
543 res = get_new_node(get_Id_pred(n));
549 /* @@@ Here we could call optimize()!! Not necessary, called in constructor anyways. */
550 set_new_node(n, res);
551 printf(" "); DDMSG2(res);
556 ir_node *old_node, *new_node, *projX;
557 ir_graph *irg = current_ir_graph;
560 printf("Before starting the DEAD NODE ELIMINATION !\n");
562 /* Copy nodes remembered in irg fields first.
563 The optimization contains tests against these fields, e.g., not
564 to optimize the start block away. Therefore these fields have to
566 Further setting these fields in copy_node would impose additional
567 tests for all nodes of a kind.
568 Predict the visited flag the walker will use! */
569 /* Copy the start Block node. Get the ProjX of the Start node, that is
570 predecessor of the start Block. We have to break the cycle and fix it
571 later. We use the old in array as placeholder. */
572 old_node = irg->start_block;
573 new_node = new_r_Block (current_ir_graph, get_Block_n_cfgpreds(old_node),
574 get_Block_cfgpred_arr(old_node));
575 /* new_r_Block calls no optimization --> save */
576 projX = get_Block_cfgpred(old_node, 0);
577 irg->start_block = new_node;
578 set_new_node (old_node, new_node);
579 set_irn_visited (old_node, get_irg_visited(current_ir_graph)+1);
580 /* Copy the Start node */
581 old_node = irg->start;
582 new_node = new_r_Start (current_ir_graph, irg->start_block);
583 irg->start = new_node;
584 set_new_node (old_node, new_node);
585 set_irn_visited (old_node, get_irg_visited(current_ir_graph)+1);
586 /* Copy the Bad node */
588 new_node = new_ir_node (irg, irg->start_block, op_Bad, mode_T, 0, NULL);
590 set_new_node (old_node, new_node);
591 set_irn_visited (old_node, get_irg_visited(current_ir_graph)+1);
592 /* Copy the Projs for the Start's results. */
594 new_node = new_r_Proj (irg, irg->start_block, irg->start, mode_X, pns_initial_exec);
595 set_Block_cfgpred(irg->start_block, 0, new_node);
596 set_new_node (old_node, new_node);
597 set_irn_visited (old_node, get_irg_visited(current_ir_graph)+1);
599 old_node = irg->frame;
600 new_node = new_r_Proj (irg, irg->start_block, irg->start, mode_p, pns_frame_base);
601 irg->frame = new_node;
602 set_new_node (old_node, new_node);
603 set_irn_visited (old_node, get_irg_visited(current_ir_graph)+1);
605 old_node = irg->globals;
606 new_node = new_r_Proj (irg, irg->start_block, irg->start, mode_p, pns_globals);
607 irg->globals = new_node;
608 set_new_node (old_node, new_node);
609 set_irn_visited (old_node, get_irg_visited(current_ir_graph)+1);
611 old_node = irg->args;
612 new_node = new_r_Proj (irg, irg->start_block, irg->start, mode_T, pns_args);
613 irg->args = new_node;
614 set_new_node (old_node, new_node);
615 set_irn_visited (old_node, get_irg_visited(current_ir_graph)+1);
617 /* Walks the graph once, and at the recursive way do the copy thing.
618 all reachable nodes will be copied to a new obstack. */
619 irg_walk(irg->end, create_dummy, copy_node2, NULL);
622 printf("After DEAD NODE ELIMINATION !\n");