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.
10 # include "irnode_t.h"
16 /********************************************************************/
17 /* apply optimizations of iropt to all nodes. */
20 optimize_in_place_wrapper (ir_node *n, void *env) {
24 /* optimize all sons after recursion, i.e., the sons' sons are
26 for (i = -1; i < get_irn_arity(n); i++) {
27 optimized = optimize_in_place(get_irn_n(n, i));
28 set_irn_n(n, i, optimized);
33 local_optimize_graph (ir_graph *irg) {
34 ir_graph *rem = current_ir_graph;
35 current_ir_graph = irg;
37 /* walk over the graph */
38 irg_walk(irg->end, NULL, optimize_in_place_wrapper, NULL);
40 current_ir_graph = rem;
43 /********************************************************************/
44 /* Routines for dead node elimination / copying garbage collection */
47 /* Remeber the new node in the old node by using a field all nodes have. */
49 set_new_node (ir_node *old, ir_node *new)
54 /* Get this new node, before the old node is forgotton.*/
56 get_new_node (ir_node * n)
61 /* Copies the node to the new obstack. In's point to the predecessors
62 on the old obstack. n->link points to the new node. */
64 copy_node (ir_node *n, void *env) {
67 if (get_irn_opcode(n) == iro_Block) {
70 block = get_nodes_Block(n);
72 nn = new_ir_node(current_ir_graph,
82 /* Copies new predecessors of old node to new node remembered in link. */
84 copy_preds (ir_node *n, void *env) {
89 if (get_irn_opcode(n) == iro_Block) start = 0; else start = -1;
90 for (i = start; i < get_irn_arity(n); i++)
91 set_irn_n (nn, i, get_new_node(get_irn_n(n, i)));
94 /* To break the recursion of the graph walk if there are loops in
95 the graph we have to allocate new nodes for Phis and blocks
96 before descending. Here we use the old predecessors for the
97 new nodes. These are replaced by the proper predecessors in
99 It turned out that it is not sufficient to just break loops
100 for Phi and Block nodes, as the walker can hit visited but
101 not copied nodes at any point in the graph.
102 A simple fix would be allocating Id's for every node and then
103 exchanging them, but this will cause new dead nodes on the new
105 So now there is a different implementation more based on the
106 view on the graph as a graph than as a represented program. */
108 create_dummy (ir_node *n, void *env) {
111 /* Assure link is set to NULL so we can test whether there is a
112 new node by checking link.
113 set_irn_link(n, NULL); */
115 switch (get_irn_opcode(n)) {
117 set_new_node(n, new_ir_node(current_ir_graph, NULL, op_Block, mode_R,
118 get_irn_arity(n), get_irn_in(n)));
121 set_new_node(n, new_ir_node(current_ir_graph, NULL, op_Phi,
123 get_irn_arity(n), get_irn_in(n)));
126 } /* end switch (get_irn_opcode(n)) */
129 /* Create a copy of this node on a new obstack. */
131 copy_node2 (ir_node *n, void *env) {
141 a = get_binop_left(n);
142 b = get_binop_right(n);
143 } else if (is_unop(n)) {
147 switch (get_irn_opcode(n)) {
150 res = get_new_node(n);
152 for (i = 0; i < get_Block_n_cfgpreds(n); i++)
153 set_Block_cfgpred(res, i, get_new_node(get_Block_cfgpred(n, i)));
154 set_Block_matured(res, 1);
158 res = new_r_Start (current_ir_graph, get_new_node(get_nodes_Block(n)));
161 res = new_r_End (current_ir_graph, get_new_node(get_nodes_Block(n)));
162 current_ir_graph -> end = res;
163 current_ir_graph -> end_block = get_nodes_Block(res);
166 res = new_r_Jmp (current_ir_graph, get_new_node(get_nodes_Block(n)));
169 res = new_r_Cond (current_ir_graph, get_new_node(get_nodes_Block(n)),
170 get_new_node(get_Cond_selector(n)));
175 in = get_Return_res_arr(n);
176 for (i = 0; i < get_Return_n_res(n); i++)
177 set_Return_res(n, i, get_new_node(get_Return_res(n, i)));
178 res = new_r_Return (current_ir_graph,
179 get_new_node(get_nodes_Block(n)),
180 get_new_node(get_Return_mem(n)),
181 get_Return_n_res(n), in);
185 res = new_r_Raise (current_ir_graph,
186 get_new_node(get_nodes_Block(n)),
187 get_new_node(get_Raise_mem(n)),
188 get_new_node(get_Raise_exo_ptr(n)));
191 res = new_r_Const (current_ir_graph, get_new_node(get_nodes_Block(n)),
192 get_irn_mode(n), get_Const_tarval(n));
196 type_or_id_p value = NULL;
198 if ((get_SymConst_kind(n)==type_tag) || (get_SymConst_kind(n)==size))
201 value = (type_or_id_p) get_SymConst_type(n);
205 if (get_SymConst_kind(n)==linkage_ptr_info)
207 value = (type_or_id_p) get_SymConst_ptrinfo(n);
210 res = new_r_SymConst (current_ir_graph, get_new_node(get_nodes_Block(n)),
211 value, get_SymConst_kind (n));
216 ir_node **in = get_Sel_index_arr(n);
217 for (i = 0; i < get_Sel_n_index(n); i++)
218 set_Sel_index(n, i, get_new_node(get_Sel_index(n, i)));
219 res = new_r_Sel (current_ir_graph, get_new_node(get_nodes_Block(n)),
220 get_new_node(get_Sel_mem(n)),
221 get_new_node(get_Sel_ptr(n)), get_Sel_n_index(n),
222 in, get_Sel_entity(n));
228 in = get_Call_param_arr(n);
230 for (i = 0; i < get_Call_arity(n); i++)
231 set_Call_param(n, i, get_new_node(get_Call_param(n, i)));
232 res = new_r_Call (current_ir_graph,
233 get_new_node(get_nodes_Block(n)),
234 get_new_node(get_Call_mem(n)),
235 get_new_node(get_Call_ptr(n)),
236 get_Call_arity(n), in,
241 res = new_r_Add (current_ir_graph, get_new_node(get_nodes_Block(n)),
242 get_new_node(a), get_new_node(b), get_irn_mode(n));
246 res = new_r_Sub (current_ir_graph, get_new_node(get_nodes_Block(n)),
247 get_new_node(a), get_new_node(b), get_irn_mode(n));
251 res = new_r_Minus (current_ir_graph, get_new_node(get_nodes_Block(n)),
252 get_new_node(a), get_irn_mode(n));
255 res = new_r_Mul (current_ir_graph, get_new_node(get_nodes_Block(n)),
256 get_new_node(a), get_new_node(b), get_irn_mode(n));
259 res = new_r_Quot (current_ir_graph, get_new_node(get_nodes_Block(n)),
260 get_new_node(get_Quot_mem(n)), get_new_node(a),
264 res = new_r_DivMod (current_ir_graph, get_new_node(get_nodes_Block(n)),
265 get_new_node(get_DivMod_mem(n)), get_new_node(a),
269 res = new_r_Div (current_ir_graph, get_new_node(get_nodes_Block(n)),
270 get_new_node(get_Div_mem(n)), get_new_node(a),
274 res = new_r_Mod (current_ir_graph, get_new_node(get_nodes_Block(n)),
275 get_new_node(get_Mod_mem(n)), get_new_node(a),
279 res = new_r_Abs (current_ir_graph, get_new_node(get_nodes_Block(n)),
280 get_new_node(get_Abs_op(n)), get_irn_mode(n));
283 res = new_r_And (current_ir_graph, get_new_node(get_nodes_Block(n)),
284 get_new_node(a), get_new_node(b), get_irn_mode(n));
287 res = new_r_Or (current_ir_graph, get_new_node(get_nodes_Block(n)),
288 get_new_node(a), get_new_node(b), get_irn_mode(n));
291 res = new_r_Eor (current_ir_graph, get_new_node(get_nodes_Block(n)),
292 get_new_node(a), get_new_node(b), get_irn_mode(n));
295 res = new_r_Not (current_ir_graph, get_new_node(get_nodes_Block(n)),
296 get_new_node(get_Not_op(n)), get_irn_mode(n));
299 res = new_r_Cmp (current_ir_graph,
300 get_new_node(get_nodes_Block(n)),
301 get_new_node(get_Cmp_left(n)),
302 get_new_node(get_Cmp_right(n)));
305 res = new_r_Shl (current_ir_graph, get_new_node(get_nodes_Block(n)),
306 get_new_node(get_Shl_left(n)),
307 get_new_node(get_Shl_right(n)), get_irn_mode(n));
310 res = new_r_Shr (current_ir_graph, get_new_node(get_nodes_Block(n)),
311 get_new_node(get_Shr_left(n)),
312 get_new_node(get_Shr_right(n)), get_irn_mode(n));
315 res = new_r_Shrs (current_ir_graph, get_new_node(get_nodes_Block(n)),
316 get_new_node(get_Shrs_left(n)),
317 get_new_node(get_Shrs_right(n)), get_irn_mode(n));
320 res = new_r_Rot (current_ir_graph, get_new_node(get_nodes_Block(n)),
321 get_new_node(get_Rot_left(n)),
322 get_new_node(get_Rot_right(n)), get_irn_mode(n));
325 res = new_r_Conv (current_ir_graph, get_new_node(get_nodes_Block(n)),
326 get_new_node(get_Conv_op(n)),
331 res = get_new_node(n);
332 for (i = 0; i < get_Phi_n_preds(n); i++)
333 set_Phi_pred(res, i, get_new_node(get_Phi_pred(n, i)));
334 set_nodes_Block(res, get_new_node(get_nodes_Block(n)));
338 res = new_r_Load (current_ir_graph, get_new_node(get_nodes_Block(n)),
339 get_new_node(get_Load_mem(n)),
340 get_new_node(get_Load_ptr(n)));
343 res = new_r_Store (current_ir_graph, get_new_node(get_nodes_Block(n)),
344 get_new_node(get_Store_mem(n)),
345 get_new_node(get_Store_ptr(n)),
346 get_new_node(get_Store_value(n)));
349 res = new_r_Alloc (current_ir_graph, get_new_node(get_nodes_Block(n)),
350 get_new_node(get_Alloc_mem(n)),
351 get_new_node(get_Alloc_size(n)),
352 get_Alloc_type(n), get_Alloc_where(n));
356 res = new_r_Free (current_ir_graph, get_new_node(get_nodes_Block(n)),
357 get_new_node(get_Free_mem(n)),
358 get_new_node(get_Free_ptr(n)),
359 get_new_node(get_Free_size(n)), get_Free_type(n));
363 ir_node **in = get_Sync_preds_arr(n);
364 for (i = 0; i < get_Sync_n_preds(n); i++)
365 set_Sync_pred(n, i, get_new_node(get_Sync_pred(n, i)));
366 res = new_r_Sync (current_ir_graph, get_new_node(get_nodes_Block(n)),
367 get_Sync_n_preds(n), in);
371 res = new_r_Proj (current_ir_graph, get_new_node(get_nodes_Block(n)),
372 get_new_node(get_Proj_pred(n)), get_irn_mode(n),
378 ir_node **in = get_Tuple_preds_arr(n);
379 for (i = 0; i < get_Tuple_n_preds(n); i++)
380 set_Tuple_pred(n, i, get_new_node(get_Tuple_pred(n, i)));
381 res = new_r_Tuple (current_ir_graph, get_new_node(get_nodes_Block(n)),
382 get_Tuple_n_preds(n), in);
386 res = get_new_node(get_Id_pred(n));
392 /* @@@ Here we could call optimize()!! Not necessary, called in constructor anyways. */
393 set_new_node(n, res);
394 printf(" "); DDMSG2(res);
397 /* Copies the graph reachable from current_ir_graph->end to the obstack
399 Then fixes the fields in current_ir_graph containing nodes of the
403 /* Not all nodes remembered in current_ir_graph might be reachable
404 from the end node. Assure their link is set to NULL so that
405 we can test whether new nodes have been computed. */
406 set_irn_link(get_irg_frame (current_ir_graph), NULL);
407 set_irn_link(get_irg_globals(current_ir_graph), NULL);
408 set_irn_link(get_irg_args (current_ir_graph), NULL);
411 irg_walk(get_irg_end(current_ir_graph), copy_node, copy_preds, NULL);
413 /* fix the fields in current_ir_graph */
414 set_irg_end (current_ir_graph, get_new_node(get_irg_end(current_ir_graph)));
415 set_irg_end_block (current_ir_graph, get_new_node(get_irg_end_block(current_ir_graph)));
416 if (get_irn_link(get_irg_frame(current_ir_graph)) == NULL)
417 irg_walk(get_irg_frame(current_ir_graph), copy_node, copy_preds, NULL);
418 if (get_irn_link(get_irg_globals(current_ir_graph)) == NULL)
419 irg_walk(get_irg_globals(current_ir_graph), copy_node, copy_preds, NULL);
420 if (get_irn_link(get_irg_args(current_ir_graph)) == NULL)
421 irg_walk(get_irg_args(current_ir_graph), copy_node, copy_preds, NULL);
422 set_irg_start (current_ir_graph, get_new_node(get_irg_start(current_ir_graph)));
423 set_irg_start_block(current_ir_graph,
424 get_new_node(get_irg_start_block(current_ir_graph)));
425 set_irg_frame (current_ir_graph, get_new_node(get_irg_frame(current_ir_graph)));
426 set_irg_globals(current_ir_graph, get_new_node(get_irg_globals(current_ir_graph)));
427 set_irg_args (current_ir_graph, get_new_node(get_irg_args(current_ir_graph)));
428 if (get_irn_link(get_irg_bad(current_ir_graph)) == NULL) {
429 copy_node(get_irg_bad(current_ir_graph), NULL);
430 copy_preds(get_irg_bad(current_ir_graph), NULL);
432 set_irg_bad(current_ir_graph, get_new_node(get_irg_bad(current_ir_graph)));
437 ir_node *old_node, *new_node, *projX;
438 ir_graph *irg = current_ir_graph;
441 printf("Before starting the DEAD NODE ELIMINATION !\n");
443 /* Copy nodes remembered in irg fields first.
444 The optimization contains tests against these fields, e.g., not
445 to optimize the start block away. Therefore these fields have to
447 Further setting these fields in copy_node would impose additional
448 tests for all nodes of a kind.
449 Predict the visited flag the walker will use! */
450 /* Copy the start Block node. Get the ProjX of the Start node, that is
451 predecessor of the start Block. We have to break the cycle and fix it
452 later. We use the old in array as placeholder. */
453 old_node = irg->start_block;
454 new_node = new_r_Block (current_ir_graph, get_Block_n_cfgpreds(old_node),
455 get_Block_cfgpred_arr(old_node));
456 /* new_r_Block calls no optimization --> save */
457 projX = get_Block_cfgpred(old_node, 0);
458 irg->start_block = new_node;
459 set_new_node (old_node, new_node);
460 set_irn_visited (old_node, get_irg_visited(current_ir_graph)+1);
461 /* Copy the Start node */
462 old_node = irg->start;
463 new_node = new_r_Start (current_ir_graph, irg->start_block);
464 irg->start = new_node;
465 set_new_node (old_node, new_node);
466 set_irn_visited (old_node, get_irg_visited(current_ir_graph)+1);
467 /* Copy the Bad node */
469 new_node = new_ir_node (irg, irg->start_block, op_Bad, mode_T, 0, NULL);
471 set_new_node (old_node, new_node);
472 set_irn_visited (old_node, get_irg_visited(current_ir_graph)+1);
473 /* Copy the Projs for the Start's results. */
475 new_node = new_r_Proj (irg, irg->start_block, irg->start, mode_X, pns_initial_exec);
476 set_Block_cfgpred(irg->start_block, 0, new_node);
477 set_new_node (old_node, new_node);
478 set_irn_visited (old_node, get_irg_visited(current_ir_graph)+1);
480 old_node = irg->frame;
481 new_node = new_r_Proj (irg, irg->start_block, irg->start, mode_p, pns_frame_base);
482 irg->frame = new_node;
483 set_new_node (old_node, new_node);
484 set_irn_visited (old_node, get_irg_visited(current_ir_graph)+1);
486 old_node = irg->globals;
487 new_node = new_r_Proj (irg, irg->start_block, irg->start, mode_p, pns_globals);
488 irg->globals = new_node;
489 set_new_node (old_node, new_node);
490 set_irn_visited (old_node, get_irg_visited(current_ir_graph)+1);
492 old_node = irg->args;
493 new_node = new_r_Proj (irg, irg->start_block, irg->start, mode_T, pns_args);
494 irg->args = new_node;
495 set_new_node (old_node, new_node);
496 set_irn_visited (old_node, get_irg_visited(current_ir_graph)+1);
498 /* Walks the graph once, and at the recursive way do the copy thing.
499 all reachable nodes will be copied to a new obstack. */
500 irg_walk(irg->end, create_dummy, copy_node2, NULL);
503 printf("After DEAD NODE ELIMINATION !\n");
506 /* Amroq call this emigrate() */
508 dead_node_elimination(ir_graph *irg) {
510 struct obstack *graveyard_obst = NULL;
511 struct obstack *rebirth_obst = NULL;
513 /* Remember external state of current_ir_graph. */
514 rem = current_ir_graph;
515 current_ir_graph = irg;
517 if (get_optimize() && get_opt_dead_node_elimination()) {
519 /* A quiet place, where the old obstack can rest in peace,
520 until it will be cremated. */
521 graveyard_obst = irg->obst;
523 /* A new obstack, where the reachable nodes will be copied to. */
524 rebirth_obst = (struct obstack *) xmalloc (sizeof (struct obstack));
525 current_ir_graph->obst = rebirth_obst;
526 obstack_init (current_ir_graph->obst);
528 /* Copy the graph from the old to the new obstack */
531 /* Free memory from old unoptimized obstack */
532 // obstack_free(graveyard_obst, 0); /* First empty the obstack ... */
533 //xfree (graveyard_obst); /* ... then free it. */
536 current_ir_graph = rem;