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 /********************************************************************/
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 *value = NULL;
198 if ((get_SymConst_kind(n)==type_tag) || (get_SymConst_kind(n)==size))
201 value = (type_or_id *) get_SymConst_type(n);
205 if (get_SymConst_kind(n)==linkage_ptr_info)
207 value = (type_or_id *) 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
404 /* Not all nodes remembered in current_ir_graph might be reachable
405 from the end node. Assure their link is set to NULL so that
406 we can test whether new nodes have been computed. */
407 set_irn_link(get_irg_frame (current_ir_graph), NULL);
408 set_irn_link(get_irg_globals(current_ir_graph), NULL);
409 set_irn_link(get_irg_args (current_ir_graph), NULL);
412 irg_walk(get_irg_end(current_ir_graph), copy_node, copy_preds, NULL);
414 /* fix the fields in current_ir_graph */
415 set_irg_end (current_ir_graph, get_new_node(get_irg_end(current_ir_graph)));
416 set_irg_end_block (current_ir_graph, get_new_node(get_irg_end_block(current_ir_graph)));
417 if (get_irn_link(get_irg_frame(current_ir_graph)) == NULL)
418 irg_walk(get_irg_frame(current_ir_graph), copy_node, copy_preds, NULL);
419 if (get_irn_link(get_irg_globals(current_ir_graph)) == NULL)
420 irg_walk(get_irg_globals(current_ir_graph), copy_node, copy_preds, NULL);
421 if (get_irn_link(get_irg_args(current_ir_graph)) == NULL)
422 irg_walk(get_irg_args(current_ir_graph), copy_node, copy_preds, NULL);
423 set_irg_start (current_ir_graph, get_new_node(get_irg_start(current_ir_graph)));
424 set_irg_start_block(current_ir_graph,
425 get_new_node(get_irg_start_block(current_ir_graph)));
426 set_irg_frame (current_ir_graph, get_new_node(get_irg_frame(current_ir_graph)));
427 set_irg_globals(current_ir_graph, get_new_node(get_irg_globals(current_ir_graph)));
428 set_irg_args (current_ir_graph, get_new_node(get_irg_args(current_ir_graph)));
429 if (get_irn_link(get_irg_bad(current_ir_graph)) == NULL) {
430 copy_node(get_irg_bad(current_ir_graph), NULL);
431 copy_preds(get_irg_bad(current_ir_graph), NULL);
433 set_irg_bad(current_ir_graph, get_new_node(get_irg_bad(current_ir_graph)));
440 ir_node *old_node, *new_node, *projX;
441 ir_graph *irg = current_ir_graph;
444 printf("Before starting the DEAD NODE ELIMINATION !\n");
446 /* Copy nodes remembered in irg fields first.
447 The optimization contains tests against these fields, e.g., not
448 to optimize the start block away. Therefore these fields have to
450 Further setting these fields in copy_node would impose additional
451 tests for all nodes of a kind.
452 Predict the visited flag the walker will use! */
453 /* Copy the start Block node. Get the ProjX of the Start node, that is
454 predecessor of the start Block. We have to break the cycle and fix it
455 later. We use the old in array as placeholder. */
456 old_node = irg->start_block;
457 new_node = new_r_Block (current_ir_graph, get_Block_n_cfgpreds(old_node),
458 get_Block_cfgpred_arr(old_node));
459 /* new_r_Block calls no optimization --> save */
460 projX = get_Block_cfgpred(old_node, 0);
461 irg->start_block = new_node;
462 set_new_node (old_node, new_node);
463 set_irn_visited (old_node, get_irg_visited(current_ir_graph)+1);
464 /* Copy the Start node */
465 old_node = irg->start;
466 new_node = new_r_Start (current_ir_graph, irg->start_block);
467 irg->start = new_node;
468 set_new_node (old_node, new_node);
469 set_irn_visited (old_node, get_irg_visited(current_ir_graph)+1);
470 /* Copy the Bad node */
472 new_node = new_ir_node (irg, irg->start_block, op_Bad, mode_T, 0, NULL);
474 set_new_node (old_node, new_node);
475 set_irn_visited (old_node, get_irg_visited(current_ir_graph)+1);
476 /* Copy the Projs for the Start's results. */
478 new_node = new_r_Proj (irg, irg->start_block, irg->start, mode_X, pns_initial_exec);
479 set_Block_cfgpred(irg->start_block, 0, new_node);
480 set_new_node (old_node, new_node);
481 set_irn_visited (old_node, get_irg_visited(current_ir_graph)+1);
483 old_node = irg->frame;
484 new_node = new_r_Proj (irg, irg->start_block, irg->start, mode_p, pns_frame_base);
485 irg->frame = new_node;
486 set_new_node (old_node, new_node);
487 set_irn_visited (old_node, get_irg_visited(current_ir_graph)+1);
489 old_node = irg->globals;
490 new_node = new_r_Proj (irg, irg->start_block, irg->start, mode_p, pns_globals);
491 irg->globals = new_node;
492 set_new_node (old_node, new_node);
493 set_irn_visited (old_node, get_irg_visited(current_ir_graph)+1);
495 old_node = irg->args;
496 new_node = new_r_Proj (irg, irg->start_block, irg->start, mode_T, pns_args);
497 irg->args = new_node;
498 set_new_node (old_node, new_node);
499 set_irn_visited (old_node, get_irg_visited(current_ir_graph)+1);
501 /* Walks the graph once, and at the recursive way do the copy thing.
502 all reachable nodes will be copied to a new obstack. */
503 irg_walk(irg->end, create_dummy, copy_node2, NULL);
506 printf("After DEAD NODE ELIMINATION !\n");
509 /* Amroq call this emigrate() */
511 dead_node_elimination(ir_graph *irg) {
513 struct obstack *graveyard_obst = NULL;
514 struct obstack *rebirth_obst = NULL;
516 /* Remember external state of current_ir_graph. */
517 rem = current_ir_graph;
518 current_ir_graph = irg;
520 if (get_optimize() && get_opt_dead_node_elimination()) {
522 /* A quiet place, where the old obstack can rest in peace,
523 until it will be cremated. */
524 graveyard_obst = irg->obst;
526 /* A new obstack, where the reachable nodes will be copied to. */
527 rebirth_obst = (struct obstack *) xmalloc (sizeof (struct obstack));
528 current_ir_graph->obst = rebirth_obst;
529 obstack_init (current_ir_graph->obst);
531 /* Copy the graph from the old to the new obstack */
534 /* Free memory from old unoptimized obstack */
535 // obstack_free(graveyard_obst, 0); /* First empty the obstack ... */
536 //xfree (graveyard_obst); /* ... then free it. */
539 current_ir_graph = rem;