3 * File name: ir/ir/irgopt.c
4 * Purpose: Optimizations for a whole ir graph, i.e., a procedure.
5 * Author: Christian Schaefer, Goetz Lindenmaier
6 * Modified by: Sebastian Felis
9 * Copyright: (c) 1998-2003 Universität Karlsruhe
10 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
21 #include "irgraph_t.h"
33 #include "pdeq.h" /* Fuer code placement */
38 #include "irbackedge_t.h"
44 #include "iredges_t.h"
47 /* Defined in iropt.c */
48 pset *new_identities (void);
49 void del_identities (pset *value_table);
50 void add_identities (pset *value_table, ir_node *node);
52 /*------------------------------------------------------------------*/
53 /* apply optimizations of iropt to all nodes. */
54 /*------------------------------------------------------------------*/
56 static void init_link (ir_node *n, void *env) {
57 set_irn_link(n, NULL);
60 #if 0 /* Old version. Avoids Ids.
61 This is not necessary: we do a post walk, and get_irn_n
62 removes ids anyways. So it's much cheaper to call the
63 optimization less often and use the exchange() algorithm. */
65 optimize_in_place_wrapper (ir_node *n, void *env) {
67 ir_node *optimized, *old;
69 irn_arity = get_irn_arity(n);
70 for (i = 0; i < irn_arity; i++) {
71 /* get_irn_n skips Id nodes, so comparison old != optimized does not
72 show all optimizations. Therefore always set new predecessor. */
73 old = get_irn_intra_n(n, i);
74 optimized = optimize_in_place_2(old);
75 set_irn_n(n, i, optimized);
78 if (get_irn_op(n) == op_Block) {
79 optimized = optimize_in_place_2(n);
80 if (optimized != n) exchange (n, optimized);
85 optimize_in_place_wrapper (ir_node *n, void *env) {
86 ir_node *optimized = optimize_in_place_2(n);
87 if (optimized != n) exchange (n, optimized);
92 static INLINE void do_local_optimize(ir_node *n) {
93 /* Handle graph state */
94 assert(get_irg_phase_state(current_ir_graph) != phase_building);
96 if (get_opt_global_cse())
97 set_irg_pinned(current_ir_graph, op_pin_state_floats);
98 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
99 set_irg_outs_inconsistent(current_ir_graph);
100 set_irg_doms_inconsistent(current_ir_graph);
101 set_irg_loopinfo_inconsistent(current_ir_graph);
103 /* Clean the value_table in irg for the CSE. */
104 del_identities(current_ir_graph->value_table);
105 current_ir_graph->value_table = new_identities();
107 /* walk over the graph */
108 irg_walk(n, init_link, optimize_in_place_wrapper, NULL);
111 void local_optimize_node(ir_node *n) {
112 ir_graph *rem = current_ir_graph;
113 current_ir_graph = get_irn_irg(n);
115 do_local_optimize(n);
117 current_ir_graph = rem;
121 * Block-Walker: uses dominance depth to mark dead blocks.
123 static void kill_dead_blocks(ir_node *block, void *env)
125 if (get_Block_dom_depth(block) < 0)
126 set_Block_dead(block);
130 local_optimize_graph (ir_graph *irg) {
131 ir_graph *rem = current_ir_graph;
132 current_ir_graph = irg;
134 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
135 irg_block_walk_graph(irg, NULL, kill_dead_blocks, NULL);
137 do_local_optimize(irg->end);
139 current_ir_graph = rem;
143 /*------------------------------------------------------------------*/
144 /* Routines for dead node elimination / copying garbage collection */
145 /* of the obstack. */
146 /*------------------------------------------------------------------*/
149 * Remember the new node in the old node by using a field all nodes have.
151 #define set_new_node(oldn, newn) set_irn_link(oldn, newn)
154 * Get this new node, before the old node is forgotten.
156 #define get_new_node(oldn) get_irn_link(oldn)
159 * Check if a new node was set.
161 #define has_new_node(n) (get_new_node(n) != NULL)
164 * We use the block_visited flag to mark that we have computed the
165 * number of useful predecessors for this block.
166 * Further we encode the new arity in this flag in the old blocks.
167 * Remembering the arity is useful, as it saves a lot of pointer
168 * accesses. This function is called for all Phi and Block nodes
172 compute_new_arity(ir_node *b) {
173 int i, res, irn_arity;
176 irg_v = get_irg_block_visited(current_ir_graph);
177 block_v = get_Block_block_visited(b);
178 if (block_v >= irg_v) {
179 /* we computed the number of preds for this block and saved it in the
181 return block_v - irg_v;
183 /* compute the number of good predecessors */
184 res = irn_arity = get_irn_arity(b);
185 for (i = 0; i < irn_arity; i++)
186 if (get_irn_opcode(get_irn_n(b, i)) == iro_Bad) res--;
187 /* save it in the flag. */
188 set_Block_block_visited(b, irg_v + res);
194 * Copies the node to the new obstack. The Ins of the new node point to
195 * the predecessors on the old obstack. For block/phi nodes not all
196 * predecessors might be copied. n->link points to the new node.
197 * For Phi and Block nodes the function allocates in-arrays with an arity
198 * only for useful predecessors. The arity is determined by counting
199 * the non-bad predecessors of the block.
201 * @param n The node to be copied
202 * @param env if non-NULL, the node number attribute will be copied to the new node
204 * Note: Also used for loop unrolling.
206 static void copy_node(ir_node *n, void *env) {
209 ir_op *op = get_irn_op(n);
210 int copy_node_nr = env != NULL;
212 /* The end node looses it's flexible in array. This doesn't matter,
213 as dead node elimination builds End by hand, inlineing doesn't use
215 /* assert(op == op_End || ((_ARR_DESCR(n->in))->cookie != ARR_F_MAGIC)); */
218 /* node copied already */
220 } else if (op == op_Block) {
222 new_arity = compute_new_arity(n);
223 n->attr.block.graph_arr = NULL;
225 block = get_nodes_block(n);
227 new_arity = compute_new_arity(block);
229 new_arity = get_irn_arity(n);
232 nn = new_ir_node(get_irn_dbg_info(n),
239 /* Copy the attributes. These might point to additional data. If this
240 was allocated on the old obstack the pointers now are dangling. This
241 frees e.g. the memory of the graph_arr allocated in new_immBlock. */
242 copy_node_attr(n, nn);
243 new_backedge_info(nn);
247 /* for easier debugging, we want to copy the node numbers too */
248 nn->node_nr = n->node_nr;
256 * Copies new predecessors of old node to new node remembered in link.
257 * Spare the Bad predecessors of Phi and Block nodes.
260 copy_preds (ir_node *n, void *env) {
264 nn = get_new_node(n);
266 /* printf("\n old node: "); DDMSG2(n);
267 printf(" new node: "); DDMSG2(nn);
268 printf(" arities: old: %d, new: %d\n", get_irn_arity(n), get_irn_arity(nn)); */
271 /* Don't copy Bad nodes. */
273 irn_arity = get_irn_arity(n);
274 for (i = 0; i < irn_arity; i++)
275 if (! is_Bad(get_irn_n(n, i))) {
276 set_irn_n (nn, j, get_new_node(get_irn_n(n, i)));
277 /*if (is_backedge(n, i)) set_backedge(nn, j);*/
280 /* repair the block visited flag from above misuse. Repair it in both
281 graphs so that the old one can still be used. */
282 set_Block_block_visited(nn, 0);
283 set_Block_block_visited(n, 0);
284 /* Local optimization could not merge two subsequent blocks if
285 in array contained Bads. Now it's possible.
286 We don't call optimize_in_place as it requires
287 that the fields in ir_graph are set properly. */
288 if ((get_opt_control_flow_straightening()) &&
289 (get_Block_n_cfgpreds(nn) == 1) &&
290 (get_irn_op(get_Block_cfgpred(nn, 0)) == op_Jmp)) {
291 ir_node *old = get_nodes_block(get_Block_cfgpred(nn, 0));
293 /* Jmp jumps into the block it is in -- deal self cycle. */
294 assert(is_Bad(get_new_node(get_irg_bad(current_ir_graph))));
295 exchange(nn, get_new_node(get_irg_bad(current_ir_graph)));
300 } else if (get_irn_op(n) == op_Phi) {
301 /* Don't copy node if corresponding predecessor in block is Bad.
302 The Block itself should not be Bad. */
303 block = get_nodes_block(n);
304 set_irn_n (nn, -1, get_new_node(block));
306 irn_arity = get_irn_arity(n);
307 for (i = 0; i < irn_arity; i++)
308 if (! is_Bad(get_irn_n(block, i))) {
309 set_irn_n (nn, j, get_new_node(get_irn_n(n, i)));
310 /*if (is_backedge(n, i)) set_backedge(nn, j);*/
313 /* If the pre walker reached this Phi after the post walker visited the
314 block block_visited is > 0. */
315 set_Block_block_visited(get_nodes_block(n), 0);
316 /* Compacting the Phi's ins might generate Phis with only one
318 if (get_irn_arity(nn) == 1)
319 exchange(nn, get_irn_n(nn, 0));
321 irn_arity = get_irn_arity(n);
322 for (i = -1; i < irn_arity; i++)
323 set_irn_n (nn, i, get_new_node(get_irn_n(n, i)));
325 /* Now the new node is complete. We can add it to the hash table for CSE.
326 @@@ inlining aborts if we identify End. Why? */
327 if (get_irn_op(nn) != op_End)
328 add_identities (current_ir_graph->value_table, nn);
332 * Copies the graph recursively, compacts the keep-alives of the end node.
334 * @param irg the graph to be copied
335 * @param copy_node_nr If non-zero, the node number will be copied
337 static void copy_graph(ir_graph *irg, int copy_node_nr) {
338 ir_node *oe, *ne, *ob, *nb, *om, *nm; /* old end, new end, old bad, new bad, old NoMem, new NoMem */
339 ir_node *ka; /* keep alive */
342 oe = get_irg_end(irg);
343 /* copy the end node by hand, allocate dynamic in array! */
344 ne = new_ir_node(get_irn_dbg_info(oe),
351 /* Copy the attributes. Well, there might be some in the future... */
352 copy_node_attr(oe, ne);
353 set_new_node(oe, ne);
355 /* copy the Bad node */
356 ob = get_irg_bad(irg);
357 nb = new_ir_node(get_irn_dbg_info(ob),
364 set_new_node(ob, nb);
366 /* copy the NoMem node */
367 om = get_irg_no_mem(irg);
368 nm = new_ir_node(get_irn_dbg_info(om),
375 set_new_node(om, nm);
377 /* copy the live nodes */
378 irg_walk(get_nodes_block(oe), copy_node, copy_preds, INT_TO_PTR(copy_node_nr));
379 /* copy_preds for the end node ... */
380 set_nodes_block(ne, get_new_node(get_nodes_block(oe)));
382 /*- ... and now the keep alives. -*/
383 /* First pick the not marked block nodes and walk them. We must pick these
384 first as else we will oversee blocks reachable from Phis. */
385 irn_arity = get_irn_arity(oe);
386 for (i = 0; i < irn_arity; i++) {
387 ka = get_irn_intra_n(oe, i);
389 (get_irn_visited(ka) < get_irg_visited(irg))) {
390 /* We must keep the block alive and copy everything reachable */
391 set_irg_visited(irg, get_irg_visited(irg)-1);
392 irg_walk(ka, copy_node, copy_preds, INT_TO_PTR(copy_node_nr));
393 add_End_keepalive(ne, get_new_node(ka));
397 /* Now pick other nodes. Here we will keep all! */
398 irn_arity = get_irn_arity(oe);
399 for (i = 0; i < irn_arity; i++) {
400 ka = get_irn_intra_n(oe, i);
402 if (get_irn_visited(ka) < get_irg_visited(irg)) {
403 /* We didn't copy the node yet. */
404 set_irg_visited(irg, get_irg_visited(irg)-1);
405 irg_walk(ka, copy_node, copy_preds, INT_TO_PTR(copy_node_nr));
407 add_End_keepalive(ne, get_new_node(ka));
411 /* start block sometimes only reached after keep alives */
412 set_nodes_block(nb, get_new_node(get_nodes_block(ob)));
413 set_nodes_block(nm, get_new_node(get_nodes_block(om)));
417 * Copies the graph reachable from current_ir_graph->end to the obstack
418 * in current_ir_graph and fixes the environment.
419 * Then fixes the fields in current_ir_graph containing nodes of the
422 * @param copy_node_nr If non-zero, the node number will be copied
425 copy_graph_env (int copy_node_nr) {
426 ir_graph *irg = current_ir_graph;
427 ir_node *old_end, *n;
428 /* Not all nodes remembered in irg might be reachable
429 from the end node. Assure their link is set to NULL, so that
430 we can test whether new nodes have been computed. */
431 set_irn_link(get_irg_frame (irg), NULL);
432 set_irn_link(get_irg_globals (irg), NULL);
433 set_irn_link(get_irg_args (irg), NULL);
434 set_irn_link(get_irg_initial_mem(irg), NULL);
435 set_irn_link(get_irg_bad (irg), NULL);
436 set_irn_link(get_irg_no_mem (irg), NULL);
438 /* we use the block walk flag for removing Bads from Blocks ins. */
439 inc_irg_block_visited(irg);
442 copy_graph(irg, copy_node_nr);
444 /* fix the fields in irg */
445 old_end = get_irg_end(irg);
446 set_irg_end (irg, get_new_node(old_end));
447 set_irg_end_except (irg, get_irg_end(irg));
448 set_irg_end_reg (irg, get_irg_end(irg));
450 set_irg_end_block (irg, get_new_node(get_irg_end_block(irg)));
452 n = get_irg_frame(irg);
453 if (!has_new_node(n)) {
454 copy_node (n, INT_TO_PTR(copy_node_nr));
457 n = get_irg_globals(irg);
458 if (!has_new_node(n)) {
459 copy_node (n, INT_TO_PTR(copy_node_nr));
462 n = get_irg_initial_mem(irg);
463 if (!has_new_node(n)) {
464 copy_node (n, INT_TO_PTR(copy_node_nr));
467 n = get_irg_args(irg);
468 if (!has_new_node(n)) {
469 copy_node (n, INT_TO_PTR(copy_node_nr));
472 n = get_irg_bad(irg);
473 if (!has_new_node(n)) {
474 copy_node(n, INT_TO_PTR(copy_node_nr));
477 n = get_irg_no_mem(irg);
478 if (!has_new_node(n)) {
479 copy_node(n, INT_TO_PTR(copy_node_nr));
482 set_irg_start (irg, get_new_node(get_irg_start(irg)));
483 set_irg_start_block(irg, get_new_node(get_irg_start_block(irg)));
484 set_irg_frame (irg, get_new_node(get_irg_frame(irg)));
485 set_irg_globals (irg, get_new_node(get_irg_globals(irg)));
486 set_irg_initial_mem(irg, get_new_node(get_irg_initial_mem(irg)));
487 set_irg_args (irg, get_new_node(get_irg_args(irg)));
488 set_irg_bad (irg, get_new_node(get_irg_bad(irg)));
489 set_irg_no_mem (irg, get_new_node(get_irg_no_mem(irg)));
493 * Copies all reachable nodes to a new obstack. Removes bad inputs
494 * from block nodes and the corresponding inputs from Phi nodes.
495 * Merges single exit blocks with single entry blocks and removes
497 * Adds all new nodes to a new hash table for CSE. Does not
498 * perform CSE, so the hash table might contain common subexpressions.
501 dead_node_elimination(ir_graph *irg) {
503 int rem_ipview = get_interprocedural_view();
504 struct obstack *graveyard_obst = NULL;
505 struct obstack *rebirth_obst = NULL;
507 if (get_opt_optimize() && get_opt_dead_node_elimination()) {
508 assert(! edges_activated(irg) && "dead node elimination requieres disabled edges");
510 /* inform statistics that we started a dead-node elimination run */
511 hook_dead_node_elim(irg, 1);
513 /* Remember external state of current_ir_graph. */
514 rem = current_ir_graph;
515 current_ir_graph = irg;
516 set_interprocedural_view(0);
518 assert(get_irg_phase_state(current_ir_graph) != phase_building);
520 /* Handle graph state */
521 free_callee_info(current_ir_graph);
522 free_irg_outs(current_ir_graph);
525 /* @@@ so far we loose loops when copying */
526 free_loop_information(current_ir_graph);
528 set_irg_doms_inconsistent(irg);
530 /* A quiet place, where the old obstack can rest in peace,
531 until it will be cremated. */
532 graveyard_obst = irg->obst;
534 /* A new obstack, where the reachable nodes will be copied to. */
535 rebirth_obst = xmalloc (sizeof(*rebirth_obst));
536 current_ir_graph->obst = rebirth_obst;
537 obstack_init (current_ir_graph->obst);
539 /* We also need a new hash table for cse */
540 del_identities (irg->value_table);
541 irg->value_table = new_identities ();
543 /* Copy the graph from the old to the new obstack */
546 /* Free memory from old unoptimized obstack */
547 obstack_free(graveyard_obst, 0); /* First empty the obstack ... */
548 xfree (graveyard_obst); /* ... then free it. */
550 /* inform statistics that the run is over */
551 hook_dead_node_elim(irg, 0);
553 current_ir_graph = rem;
554 set_interprocedural_view(rem_ipview);
559 * Relink bad predecessors of a block and store the old in array to the
560 * link field. This function is called by relink_bad_predecessors().
561 * The array of link field starts with the block operand at position 0.
562 * If block has bad predecessors, create a new in array without bad preds.
563 * Otherwise let in array untouched.
565 static void relink_bad_block_predecessors(ir_node *n, void *env) {
566 ir_node **new_in, *irn;
567 int i, new_irn_n, old_irn_arity, new_irn_arity = 0;
569 /* if link field of block is NULL, look for bad predecessors otherwise
570 this is already done */
571 if (get_irn_op(n) == op_Block &&
572 get_irn_link(n) == NULL) {
574 /* save old predecessors in link field (position 0 is the block operand)*/
575 set_irn_link(n, get_irn_in(n));
577 /* count predecessors without bad nodes */
578 old_irn_arity = get_irn_arity(n);
579 for (i = 0; i < old_irn_arity; i++)
580 if (!is_Bad(get_irn_n(n, i))) new_irn_arity++;
582 /* arity changing: set new predecessors without bad nodes */
583 if (new_irn_arity < old_irn_arity) {
584 /* Get new predecessor array. We do not resize the array, as we must
585 keep the old one to update Phis. */
586 new_in = NEW_ARR_D (ir_node *, current_ir_graph->obst, (new_irn_arity+1));
588 /* set new predecessors in array */
591 for (i = 0; i < old_irn_arity; i++) {
592 irn = get_irn_n(n, i);
594 new_in[new_irn_n] = irn;
595 is_backedge(n, i) ? set_backedge(n, new_irn_n-1) : set_not_backedge(n, new_irn_n-1);
599 //ARR_SETLEN(int, n->attr.block.backedge, new_irn_arity);
600 ARR_SHRINKLEN(n->attr.block.backedge, new_irn_arity);
603 } /* ir node has bad predecessors */
605 } /* Block is not relinked */
609 * Relinks Bad predecessors from Blocks and Phis called by walker
610 * remove_bad_predecesors(). If n is a Block, call
611 * relink_bad_block_redecessors(). If n is a Phi-node, call also the relinking
612 * function of Phi's Block. If this block has bad predecessors, relink preds
615 static void relink_bad_predecessors(ir_node *n, void *env) {
616 ir_node *block, **old_in;
617 int i, old_irn_arity, new_irn_arity;
619 /* relink bad predecessors of a block */
620 if (get_irn_op(n) == op_Block)
621 relink_bad_block_predecessors(n, env);
623 /* If Phi node relink its block and its predecessors */
624 if (get_irn_op(n) == op_Phi) {
626 /* Relink predecessors of phi's block */
627 block = get_nodes_block(n);
628 if (get_irn_link(block) == NULL)
629 relink_bad_block_predecessors(block, env);
631 old_in = (ir_node **)get_irn_link(block); /* Of Phi's Block */
632 old_irn_arity = ARR_LEN(old_in);
634 /* Relink Phi predecessors if count of predecessors changed */
635 if (old_irn_arity != ARR_LEN(get_irn_in(block))) {
636 /* set new predecessors in array
637 n->in[0] remains the same block */
639 for(i = 1; i < old_irn_arity; i++)
640 if (!is_Bad((ir_node *)old_in[i])) {
641 n->in[new_irn_arity] = n->in[i];
642 is_backedge(n, i) ? set_backedge(n, new_irn_arity) : set_not_backedge(n, new_irn_arity);
646 ARR_SETLEN(ir_node *, n->in, new_irn_arity);
647 ARR_SETLEN(int, n->attr.phi_backedge, new_irn_arity);
650 } /* n is a Phi node */
654 * Removes Bad Bad predecessors from Blocks and the corresponding
655 * inputs to Phi nodes as in dead_node_elimination but without
657 * On walking up set the link field to NULL, on walking down call
658 * relink_bad_predecessors() (This function stores the old in array
659 * to the link field and sets a new in array if arity of predecessors
662 void remove_bad_predecessors(ir_graph *irg) {
663 irg_walk_graph(irg, init_link, relink_bad_predecessors, NULL);
667 /*--------------------------------------------------------------------*/
668 /* Functionality for inlining */
669 /*--------------------------------------------------------------------*/
672 * Copy node for inlineing. Updates attributes that change when
673 * inlineing but not for dead node elimination.
675 * Copies the node by calling copy_node() and then updates the entity if
676 * it's a local one. env must be a pointer of the frame type of the
677 * inlined procedure. The new entities must be in the link field of
681 copy_node_inline (ir_node *n, void *env) {
683 ir_type *frame_tp = (ir_type *)env;
686 if (get_irn_op(n) == op_Sel) {
687 new = get_new_node (n);
688 assert(get_irn_op(new) == op_Sel);
689 if (get_entity_owner(get_Sel_entity(n)) == frame_tp) {
690 set_Sel_entity(new, get_entity_link(get_Sel_entity(n)));
692 } else if (get_irn_op(n) == op_Block) {
693 new = get_new_node (n);
694 new->attr.block.irg = current_ir_graph;
698 static void find_addr(ir_node *node, void *env)
700 if (get_irn_opcode(node) == iro_Proj) {
701 if (get_Proj_proj(node) == pn_Start_P_value_arg_base)
707 * currently, we cannot inline two cases:
708 * - call with compound arguments
709 * - graphs that take the address of a parameter
711 * check these conditions here
713 static int can_inline(ir_node *call, ir_graph *called_graph)
715 ir_type *call_type = get_Call_type(call);
716 int params, ress, i, res;
717 assert(is_Method_type(call_type));
719 params = get_method_n_params(call_type);
720 ress = get_method_n_ress(call_type);
723 for (i = 0; i < params; ++i) {
724 ir_type *p_type = get_method_param_type(call_type, i);
726 if (is_compound_type(p_type))
731 for (i = 0; i < ress; ++i) {
732 ir_type *r_type = get_method_res_type(call_type, i);
734 if (is_compound_type(r_type))
739 irg_walk_graph(called_graph, find_addr, NULL, &res);
744 int inline_method(ir_node *call, ir_graph *called_graph) {
746 ir_node *post_call, *post_bl;
748 ir_node *end, *end_bl;
752 int arity, n_ret, n_exc, n_res, i, j, rem_opt, irn_arity;
754 ir_type *called_frame;
755 irg_inline_property prop = get_irg_inline_property(called_graph);
757 if ( (prop != irg_inline_forced) &&
758 (!get_opt_optimize() || !get_opt_inline() || (prop == irg_inline_forbidden))) return 0;
760 /* Do not inline variadic functions. */
761 if (get_method_variadicity(get_entity_type(get_irg_entity(called_graph))) == variadicity_variadic)
764 assert(get_method_n_params(get_entity_type(get_irg_entity(called_graph))) ==
765 get_method_n_params(get_Call_type(call)));
768 * currently, we cannot inline two cases:
769 * - call with compound arguments
770 * - graphs that take the address of a parameter
772 if (! can_inline(call, called_graph))
775 /* -- Turn off optimizations, this can cause problems when allocating new nodes. -- */
776 rem_opt = get_opt_optimize();
779 /* Handle graph state */
780 assert(get_irg_phase_state(current_ir_graph) != phase_building);
781 assert(get_irg_pinned(current_ir_graph) == op_pin_state_pinned);
782 assert(get_irg_pinned(called_graph) == op_pin_state_pinned);
783 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
784 set_irg_outs_inconsistent(current_ir_graph);
785 set_irg_loopinfo_inconsistent(current_ir_graph);
786 set_irg_callee_info_state(current_ir_graph, irg_callee_info_inconsistent);
788 /* -- Check preconditions -- */
789 assert(get_irn_op(call) == op_Call);
790 /* @@@ does not work for InterfaceIII.java after cgana
791 assert(get_Call_type(call) == get_entity_type(get_irg_entity(called_graph)));
792 assert(smaller_type(get_entity_type(get_irg_entity(called_graph)),
793 get_Call_type(call)));
795 assert(get_type_tpop(get_Call_type(call)) == type_method);
796 if (called_graph == current_ir_graph) {
797 set_optimize(rem_opt);
801 /* here we know we WILL inline, so inform the statistics */
802 hook_inline(call, called_graph);
804 /* -- Decide how to handle exception control flow: Is there a handler
805 for the Call node, or do we branch directly to End on an exception?
807 0 There is a handler.
809 2 Exception handling not represented in Firm. -- */
811 ir_node *proj, *Mproj = NULL, *Xproj = NULL;
812 for (proj = (ir_node *)get_irn_link(call); proj; proj = (ir_node *)get_irn_link(proj)) {
813 assert(get_irn_op(proj) == op_Proj);
814 if (get_Proj_proj(proj) == pn_Call_X_except) Xproj = proj;
815 if (get_Proj_proj(proj) == pn_Call_M_except) Mproj = proj;
817 if (Mproj) { assert(Xproj); exc_handling = 0; } /* Mproj */
818 else if (Xproj) { exc_handling = 1; } /* !Mproj && Xproj */
819 else { exc_handling = 2; } /* !Mproj && !Xproj */
824 the procedure and later replaces the Start node of the called graph.
825 Post_call is the old Call node and collects the results of the called
826 graph. Both will end up being a tuple. -- */
827 post_bl = get_nodes_block(call);
828 set_irg_current_block(current_ir_graph, post_bl);
829 /* XxMxPxP of Start + parameter of Call */
830 in[pn_Start_X_initial_exec] = new_Jmp();
831 in[pn_Start_M] = get_Call_mem(call);
832 in[pn_Start_P_frame_base] = get_irg_frame(current_ir_graph);
833 in[pn_Start_P_globals] = get_irg_globals(current_ir_graph);
834 in[pn_Start_T_args] = new_Tuple(get_Call_n_params(call), get_Call_param_arr(call));
835 /* in[pn_Start_P_value_arg_base] = ??? */
836 pre_call = new_Tuple(5, in);
840 The new block gets the ins of the old block, pre_call and all its
841 predecessors and all Phi nodes. -- */
842 part_block(pre_call);
844 /* -- Prepare state for dead node elimination -- */
845 /* Visited flags in calling irg must be >= flag in called irg.
846 Else walker and arity computation will not work. */
847 if (get_irg_visited(current_ir_graph) <= get_irg_visited(called_graph))
848 set_irg_visited(current_ir_graph, get_irg_visited(called_graph)+1);
849 if (get_irg_block_visited(current_ir_graph)< get_irg_block_visited(called_graph))
850 set_irg_block_visited(current_ir_graph, get_irg_block_visited(called_graph));
851 /* Set pre_call as new Start node in link field of the start node of
852 calling graph and pre_calls block as new block for the start block
854 Further mark these nodes so that they are not visited by the
856 set_irn_link(get_irg_start(called_graph), pre_call);
857 set_irn_visited(get_irg_start(called_graph), get_irg_visited(current_ir_graph));
858 set_irn_link(get_irg_start_block(called_graph), get_nodes_block(pre_call));
859 set_irn_visited(get_irg_start_block(called_graph), get_irg_visited(current_ir_graph));
860 set_irn_link(get_irg_bad(called_graph), get_irg_bad(current_ir_graph));
861 set_irn_visited(get_irg_bad(called_graph), get_irg_visited(current_ir_graph));
863 /* Initialize for compaction of in arrays */
864 inc_irg_block_visited(current_ir_graph);
866 /* -- Replicate local entities of the called_graph -- */
867 /* copy the entities. */
868 called_frame = get_irg_frame_type(called_graph);
869 for (i = 0; i < get_class_n_members(called_frame); i++) {
870 entity *new_ent, *old_ent;
871 old_ent = get_class_member(called_frame, i);
872 new_ent = copy_entity_own(old_ent, get_cur_frame_type());
873 set_entity_link(old_ent, new_ent);
876 /* visited is > than that of called graph. With this trick visited will
877 remain unchanged so that an outer walker, e.g., searching the call nodes
878 to inline, calling this inline will not visit the inlined nodes. */
879 set_irg_visited(current_ir_graph, get_irg_visited(current_ir_graph)-1);
881 /* -- Performing dead node elimination inlines the graph -- */
882 /* Copies the nodes to the obstack of current_ir_graph. Updates links to new
884 /* @@@ endless loops are not copied!! -- they should be, I think... */
885 irg_walk(get_irg_end(called_graph), copy_node_inline, copy_preds,
886 get_irg_frame_type(called_graph));
888 /* Repair called_graph */
889 set_irg_visited(called_graph, get_irg_visited(current_ir_graph));
890 set_irg_block_visited(called_graph, get_irg_block_visited(current_ir_graph));
891 set_Block_block_visited(get_irg_start_block(called_graph), 0);
893 /* -- Merge the end of the inlined procedure with the call site -- */
894 /* We will turn the old Call node into a Tuple with the following
897 0: Phi of all Memories of Return statements.
898 1: Jmp from new Block that merges the control flow from all exception
899 predecessors of the old end block.
900 2: Tuple of all arguments.
901 3: Phi of Exception memories.
902 In case the old Call directly branches to End on an exception we don't
903 need the block merging all exceptions nor the Phi of the exception
907 /* -- Precompute some values -- */
908 end_bl = get_new_node(get_irg_end_block(called_graph));
909 end = get_new_node(get_irg_end(called_graph));
910 arity = get_irn_arity(end_bl); /* arity = n_exc + n_ret */
911 n_res = get_method_n_ress(get_Call_type(call));
913 res_pred = xmalloc (n_res * sizeof(*res_pred));
914 cf_pred = xmalloc (arity * sizeof(*res_pred));
916 set_irg_current_block(current_ir_graph, post_bl); /* just to make sure */
918 /* -- archive keepalives -- */
919 irn_arity = get_irn_arity(end);
920 for (i = 0; i < irn_arity; i++)
921 add_End_keepalive(get_irg_end(current_ir_graph), get_irn_n(end, i));
923 /* The new end node will die. We need not free as the in array is on the obstack:
924 copy_node() only generated 'D' arrays. */
926 /* -- Replace Return nodes by Jump nodes. -- */
928 for (i = 0; i < arity; i++) {
930 ret = get_irn_n(end_bl, i);
931 if (get_irn_op(ret) == op_Return) {
932 cf_pred[n_ret] = new_r_Jmp(current_ir_graph, get_nodes_block(ret));
936 set_irn_in(post_bl, n_ret, cf_pred);
938 /* -- Build a Tuple for all results of the method.
939 Add Phi node if there was more than one Return. -- */
940 turn_into_tuple(post_call, 4);
941 /* First the Memory-Phi */
943 for (i = 0; i < arity; i++) {
944 ret = get_irn_n(end_bl, i);
945 if (get_irn_op(ret) == op_Return) {
946 cf_pred[n_ret] = get_Return_mem(ret);
950 phi = new_Phi(n_ret, cf_pred, mode_M);
951 set_Tuple_pred(call, pn_Call_M_regular, phi);
952 /* Conserve Phi-list for further inlinings -- but might be optimized */
953 if (get_nodes_block(phi) == post_bl) {
954 set_irn_link(phi, get_irn_link(post_bl));
955 set_irn_link(post_bl, phi);
957 /* Now the real results */
959 for (j = 0; j < n_res; j++) {
961 for (i = 0; i < arity; i++) {
962 ret = get_irn_n(end_bl, i);
963 if (get_irn_op(ret) == op_Return) {
964 cf_pred[n_ret] = get_Return_res(ret, j);
969 phi = new_Phi(n_ret, cf_pred, get_irn_mode(cf_pred[0]));
973 /* Conserve Phi-list for further inlinings -- but might be optimized */
974 if (get_nodes_block(phi) == post_bl) {
975 set_irn_link(phi, get_irn_link(post_bl));
976 set_irn_link(post_bl, phi);
979 set_Tuple_pred(call, pn_Call_T_result, new_Tuple(n_res, res_pred));
981 set_Tuple_pred(call, pn_Call_T_result, new_Bad());
983 /* Finally the exception control flow.
984 We have two (three) possible situations:
985 First if the Call branches to an exception handler: We need to add a Phi node to
986 collect the memory containing the exception objects. Further we need
987 to add another block to get a correct representation of this Phi. To
988 this block we add a Jmp that resolves into the X output of the Call
989 when the Call is turned into a tuple.
990 Second the Call branches to End, the exception is not handled. Just
991 add all inlined exception branches to the End node.
992 Third: there is no Exception edge at all. Handle as case two. */
993 if (exc_handling == 0) {
995 for (i = 0; i < arity; i++) {
997 ret = get_irn_n(end_bl, i);
998 if (is_fragile_op(skip_Proj(ret)) || (get_irn_op(skip_Proj(ret)) == op_Raise)) {
999 cf_pred[n_exc] = ret;
1004 new_Block(n_exc, cf_pred); /* watch it: current_block is changed! */
1005 set_Tuple_pred(call, pn_Call_X_except, new_Jmp());
1006 /* The Phi for the memories with the exception objects */
1008 for (i = 0; i < arity; i++) {
1010 ret = skip_Proj(get_irn_n(end_bl, i));
1011 if (get_irn_op(ret) == op_Call) {
1012 cf_pred[n_exc] = new_r_Proj(current_ir_graph, get_nodes_block(ret), ret, mode_M, 3);
1014 } else if (is_fragile_op(ret)) {
1015 /* We rely that all cfops have the memory output at the same position. */
1016 cf_pred[n_exc] = new_r_Proj(current_ir_graph, get_nodes_block(ret), ret, mode_M, 0);
1018 } else if (get_irn_op(ret) == op_Raise) {
1019 cf_pred[n_exc] = new_r_Proj(current_ir_graph, get_nodes_block(ret), ret, mode_M, 1);
1023 set_Tuple_pred(call, pn_Call_M_except, new_Phi(n_exc, cf_pred, mode_M));
1025 set_Tuple_pred(call, pn_Call_X_except, new_Bad());
1026 set_Tuple_pred(call, pn_Call_M_except, new_Bad());
1029 ir_node *main_end_bl;
1030 int main_end_bl_arity;
1031 ir_node **end_preds;
1033 /* assert(exc_handling == 1 || no exceptions. ) */
1035 for (i = 0; i < arity; i++) {
1036 ir_node *ret = get_irn_n(end_bl, i);
1038 if (is_fragile_op(skip_Proj(ret)) || (get_irn_op(skip_Proj(ret)) == op_Raise)) {
1039 cf_pred[n_exc] = ret;
1043 main_end_bl = get_irg_end_block(current_ir_graph);
1044 main_end_bl_arity = get_irn_arity(main_end_bl);
1045 end_preds = xmalloc ((n_exc + main_end_bl_arity) * sizeof(*end_preds));
1047 for (i = 0; i < main_end_bl_arity; ++i)
1048 end_preds[i] = get_irn_n(main_end_bl, i);
1049 for (i = 0; i < n_exc; ++i)
1050 end_preds[main_end_bl_arity + i] = cf_pred[i];
1051 set_irn_in(main_end_bl, n_exc + main_end_bl_arity, end_preds);
1052 set_Tuple_pred(call, pn_Call_X_except, new_Bad());
1053 set_Tuple_pred(call, pn_Call_M_except, new_Bad());
1059 #if 0 /* old. now better, correcter, faster implementation. */
1061 /* -- If the exception control flow from the inlined Call directly
1062 branched to the end block we now have the following control
1063 flow predecessor pattern: ProjX -> Tuple -> Jmp. We must
1064 remove the Jmp along with it's empty block and add Jmp's
1065 predecessors as predecessors of this end block. No problem if
1066 there is no exception, because then branches Bad to End which
1068 @@@ can't we know this beforehand: by getting the Proj(1) from
1069 the Call link list and checking whether it goes to Proj. */
1070 /* find the problematic predecessor of the end block. */
1071 end_bl = get_irg_end_block(current_ir_graph);
1072 for (i = 0; i < get_Block_n_cfgpreds(end_bl); i++) {
1073 cf_op = get_Block_cfgpred(end_bl, i);
1074 if (get_irn_op(cf_op) == op_Proj) {
1075 cf_op = get_Proj_pred(cf_op);
1076 if ((get_irn_op(cf_op) == op_Tuple) && (cf_op == call)) {
1077 /* There are unoptimized tuples from inlineing before when no exc */
1078 assert(get_Proj_proj(get_Block_cfgpred(end_bl, i)) == pn_Call_X_except);
1079 cf_op = get_Tuple_pred(cf_op, pn_Call_X_except);
1080 assert(get_irn_op(cf_op) == op_Jmp);
1086 if (i < get_Block_n_cfgpreds(end_bl)) {
1087 bl = get_nodes_block(cf_op);
1088 arity = get_Block_n_cfgpreds(end_bl) + get_Block_n_cfgpreds(bl) - 1;
1089 cf_pred = xmalloc (arity * sizeof(*cf_pred));
1090 for (j = 0; j < i; j++)
1091 cf_pred[j] = get_Block_cfgpred(end_bl, j);
1092 for (j = j; j < i + get_Block_n_cfgpreds(bl); j++)
1093 cf_pred[j] = get_Block_cfgpred(bl, j-i);
1094 for (j = j; j < arity; j++)
1095 cf_pred[j] = get_Block_cfgpred(end_bl, j-get_Block_n_cfgpreds(bl) +1);
1096 set_irn_in(end_bl, arity, cf_pred);
1098 /* Remove the exception pred from post-call Tuple. */
1099 set_Tuple_pred(call, pn_Call_X_except, new_Bad());
1104 /* -- Turn CSE back on. -- */
1105 set_optimize(rem_opt);
1110 /********************************************************************/
1111 /* Apply inlineing to small methods. */
1112 /********************************************************************/
1114 /* It makes no sense to inline too many calls in one procedure. Anyways,
1115 I didn't get a version with NEW_ARR_F to run. */
1116 #define MAX_INLINE 1024
1119 * environment for inlining small irgs
1121 typedef struct _inline_env_t {
1123 ir_node *calls[MAX_INLINE];
1127 * Returns the irg called from a Call node. If the irg is not
1128 * known, NULL is returned.
1130 static ir_graph *get_call_called_irg(ir_node *call) {
1132 ir_graph *called_irg = NULL;
1134 assert(get_irn_op(call) == op_Call);
1136 addr = get_Call_ptr(call);
1137 if ((get_irn_op(addr) == op_SymConst) && (get_SymConst_kind (addr) == symconst_addr_ent)) {
1138 called_irg = get_entity_irg(get_SymConst_entity(addr));
1144 static void collect_calls(ir_node *call, void *env) {
1147 if (get_irn_op(call) != op_Call) return;
1149 addr = get_Call_ptr(call);
1151 if (get_irn_op(addr) == op_SymConst) {
1152 if (get_SymConst_kind(addr) == symconst_addr_ent) {
1153 ir_graph *called_irg = get_entity_irg(get_SymConst_entity(addr));
1154 inline_env_t *ienv = (inline_env_t *)env;
1155 if (called_irg && ienv->pos < MAX_INLINE) {
1156 /* The Call node calls a locally defined method. Remember to inline. */
1157 ienv->calls[ienv->pos++] = call;
1164 * Inlines all small methods at call sites where the called address comes
1165 * from a Const node that references the entity representing the called
1167 * The size argument is a rough measure for the code size of the method:
1168 * Methods where the obstack containing the firm graph is smaller than
1171 void inline_small_irgs(ir_graph *irg, int size) {
1173 ir_graph *rem = current_ir_graph;
1174 inline_env_t env /* = {0, NULL}*/;
1176 if (!(get_opt_optimize() && get_opt_inline())) return;
1178 current_ir_graph = irg;
1179 /* Handle graph state */
1180 assert(get_irg_phase_state(current_ir_graph) != phase_building);
1181 free_callee_info(current_ir_graph);
1183 /* Find Call nodes to inline.
1184 (We can not inline during a walk of the graph, as inlineing the same
1185 method several times changes the visited flag of the walked graph:
1186 after the first inlineing visited of the callee equals visited of
1187 the caller. With the next inlineing both are increased.) */
1189 irg_walk(get_irg_end(irg), NULL, collect_calls, &env);
1191 if ((env.pos > 0) && (env.pos < MAX_INLINE)) {
1192 /* There are calls to inline */
1193 collect_phiprojs(irg);
1194 for (i = 0; i < env.pos; i++) {
1196 callee = get_entity_irg(get_SymConst_entity(get_Call_ptr(env.calls[i])));
1197 if (((_obstack_memory_used(callee->obst) - (int)obstack_room(callee->obst)) < size) ||
1198 (get_irg_inline_property(callee) == irg_inline_forced)) {
1199 inline_method(env.calls[i], callee);
1204 current_ir_graph = rem;
1208 * Environment for inlining irgs.
1211 int n_nodes; /**< Nodes in graph except Id, Tuple, Proj, Start, End */
1212 int n_nodes_orig; /**< for statistics */
1213 eset *call_nodes; /**< All call nodes in this graph */
1215 int n_call_nodes_orig; /**< for statistics */
1216 int n_callers; /**< Number of known graphs that call this graphs. */
1217 int n_callers_orig; /**< for statistics */
1221 * Allocate a new environment for inlining.
1223 static inline_irg_env *new_inline_irg_env(void) {
1224 inline_irg_env *env = xmalloc(sizeof(*env));
1225 env->n_nodes = -2; /* do not count count Start, End */
1226 env->n_nodes_orig = -2; /* do not count Start, End */
1227 env->call_nodes = eset_create();
1228 env->n_call_nodes = 0;
1229 env->n_call_nodes_orig = 0;
1231 env->n_callers_orig = 0;
1236 * destroy an environment for inlining.
1238 static void free_inline_irg_env(inline_irg_env *env) {
1239 eset_destroy(env->call_nodes);
1244 * post-walker: collect all calls in the inline-environment
1245 * of a graph and sum some statistics.
1247 static void collect_calls2(ir_node *call, void *env) {
1248 inline_irg_env *x = (inline_irg_env *)env;
1249 ir_op *op = get_irn_op(call);
1252 /* count meaningful nodes in irg */
1253 if (op != op_Proj && op != op_Tuple && op != op_Sync) {
1258 if (op != op_Call) return;
1260 /* collect all call nodes */
1261 eset_insert(x->call_nodes, call);
1263 x->n_call_nodes_orig++;
1265 /* count all static callers */
1266 callee = get_call_called_irg(call);
1268 inline_irg_env *callee_env = get_irg_link(callee);
1269 callee_env->n_callers++;
1270 callee_env->n_callers_orig++;
1275 * Returns TRUE if the number of callers in 0 in the irg's environment,
1276 * hence this irg is a leave.
1278 INLINE static int is_leave(ir_graph *irg) {
1279 return (((inline_irg_env *)get_irg_link(irg))->n_call_nodes == 0);
1283 * Returns TRUE if the number of callers is smaller size in the irg's environment.
1285 INLINE static int is_smaller(ir_graph *callee, int size) {
1286 return (((inline_irg_env *)get_irg_link(callee))->n_nodes < size);
1291 * Inlines small leave methods at call sites where the called address comes
1292 * from a Const node that references the entity representing the called
1294 * The size argument is a rough measure for the code size of the method:
1295 * Methods where the obstack containing the firm graph is smaller than
1298 void inline_leave_functions(int maxsize, int leavesize, int size) {
1299 inline_irg_env *env;
1300 int i, n_irgs = get_irp_n_irgs();
1301 ir_graph *rem = current_ir_graph;
1304 if (!(get_opt_optimize() && get_opt_inline())) return;
1306 /* extend all irgs by a temporary data structure for inlining. */
1307 for (i = 0; i < n_irgs; ++i)
1308 set_irg_link(get_irp_irg(i), new_inline_irg_env());
1310 /* Precompute information in temporary data structure. */
1311 for (i = 0; i < n_irgs; ++i) {
1312 current_ir_graph = get_irp_irg(i);
1313 assert(get_irg_phase_state(current_ir_graph) != phase_building);
1314 free_callee_info(current_ir_graph);
1316 irg_walk(get_irg_end(current_ir_graph), NULL, collect_calls2,
1317 get_irg_link(current_ir_graph));
1320 /* -- and now inline. -- */
1322 /* Inline leaves recursively -- we might construct new leaves. */
1323 while (did_inline) {
1326 for (i = 0; i < n_irgs; ++i) {
1328 int phiproj_computed = 0;
1330 current_ir_graph = get_irp_irg(i);
1331 env = (inline_irg_env *)get_irg_link(current_ir_graph);
1333 for (call = eset_first(env->call_nodes); call; call = eset_next(env->call_nodes)) {
1336 if (get_irn_op(call) == op_Tuple) continue; /* We already have inlined this call. */
1337 callee = get_call_called_irg(call);
1339 if (env->n_nodes > maxsize) continue; // break;
1341 if (callee && (is_leave(callee) && is_smaller(callee, leavesize))) {
1342 if (!phiproj_computed) {
1343 phiproj_computed = 1;
1344 collect_phiprojs(current_ir_graph);
1346 did_inline = inline_method(call, callee);
1349 /* Do some statistics */
1350 inline_irg_env *callee_env = (inline_irg_env *)get_irg_link(callee);
1351 env->n_call_nodes --;
1352 env->n_nodes += callee_env->n_nodes;
1353 callee_env->n_callers--;
1360 /* inline other small functions. */
1361 for (i = 0; i < n_irgs; ++i) {
1364 int phiproj_computed = 0;
1366 current_ir_graph = get_irp_irg(i);
1367 env = (inline_irg_env *)get_irg_link(current_ir_graph);
1369 /* we can not walk and change a set, nor remove from it.
1371 walkset = env->call_nodes;
1372 env->call_nodes = eset_create();
1373 for (call = eset_first(walkset); call; call = eset_next(walkset)) {
1376 if (get_irn_op(call) == op_Tuple) continue; /* We already inlined. */
1377 callee = get_call_called_irg(call);
1380 ((is_smaller(callee, size) && (env->n_nodes < maxsize)) || /* small function */
1381 (get_irg_inline_property(callee) == irg_inline_forced))) {
1382 if (!phiproj_computed) {
1383 phiproj_computed = 1;
1384 collect_phiprojs(current_ir_graph);
1386 if (inline_method(call, callee)) {
1387 inline_irg_env *callee_env = (inline_irg_env *)get_irg_link(callee);
1388 env->n_call_nodes--;
1389 eset_insert_all(env->call_nodes, callee_env->call_nodes); /* @@@ ??? This are the wrong nodes !? Not the copied ones. */
1390 env->n_call_nodes += callee_env->n_call_nodes;
1391 env->n_nodes += callee_env->n_nodes;
1392 callee_env->n_callers--;
1395 eset_insert(env->call_nodes, call);
1398 eset_destroy(walkset);
1401 for (i = 0; i < n_irgs; ++i) {
1402 current_ir_graph = get_irp_irg(i);
1404 env = (inline_irg_env *)get_irg_link(current_ir_graph);
1405 if ((env->n_call_nodes_orig != env->n_call_nodes) ||
1406 (env->n_callers_orig != env->n_callers))
1407 printf("Nodes:%3d ->%3d, calls:%3d ->%3d, callers:%3d ->%3d, -- %s\n",
1408 env->n_nodes_orig, env->n_nodes, env->n_call_nodes_orig, env->n_call_nodes,
1409 env->n_callers_orig, env->n_callers,
1410 get_entity_name(get_irg_entity(current_ir_graph)));
1412 free_inline_irg_env((inline_irg_env *)get_irg_link(current_ir_graph));
1415 current_ir_graph = rem;
1418 /*******************************************************************/
1419 /* Code Placement. Pins all floating nodes to a block where they */
1420 /* will be executed only if needed. */
1421 /*******************************************************************/
1424 * Returns non-zero, is a block is not reachable from Start.
1426 * @param block the block to test
1429 is_Block_unreachable(ir_node *block) {
1430 return is_Block_dead(block) || get_Block_dom_depth(block) < 0;
1434 * Find the earliest correct block for N. --- Place N into the
1435 * same Block as its dominance-deepest Input.
1437 * We have to avoid calls to get_nodes_block() here
1438 * because the graph is floating.
1440 * move_out_of_loops() expects that place_floats_early() have placed
1441 * all "living" nodes into a living block. That's why we must
1442 * move nodes in dead block with "live" successors into a valid
1444 * We move them just into the same block as it's successor (or
1445 * in case of a Phi into the effective use block). For Phi successors,
1446 * this may still be a dead block, but then there is no real use, as
1447 * the control flow will be dead later.
1450 place_floats_early(ir_node *n, pdeq *worklist)
1454 /* we must not run into an infinite loop */
1455 assert(irn_not_visited(n));
1456 mark_irn_visited(n);
1458 /* Place floating nodes. */
1459 if (get_irn_pinned(n) == op_pin_state_floats) {
1460 ir_node *curr_block = get_irn_n(n, -1);
1461 int in_dead_block = is_Block_unreachable(curr_block);
1463 ir_node *b = NULL; /* The block to place this node in */
1465 assert(get_irn_op(n) != op_Block);
1467 if ((get_irn_op(n) == op_Const) ||
1468 (get_irn_op(n) == op_SymConst) ||
1470 (get_irn_op(n) == op_Unknown)) {
1471 /* These nodes will not be placed by the loop below. */
1472 b = get_irg_start_block(current_ir_graph);
1476 /* find the block for this node. */
1477 irn_arity = get_irn_arity(n);
1478 for (i = 0; i < irn_arity; i++) {
1479 ir_node *pred = get_irn_n(n, i);
1480 ir_node *pred_block;
1482 if ((irn_not_visited(pred))
1483 && (get_irn_pinned(pred) == op_pin_state_floats)) {
1486 * If the current node is NOT in a dead block, but one of its
1487 * predecessors is, we must move the predecessor to a live block.
1488 * Such thing can happen, if global CSE chose a node from a dead block.
1489 * We move it simple to our block.
1490 * Note that neither Phi nor End nodes are floating, so we don't
1491 * need to handle them here.
1493 if (! in_dead_block) {
1494 if (get_irn_pinned(pred) == op_pin_state_floats &&
1495 is_Block_unreachable(get_irn_n(pred, -1)))
1496 set_nodes_block(pred, curr_block);
1498 place_floats_early(pred, worklist);
1502 * A node in the Bad block must stay in the bad block,
1503 * so don't compute a new block for it.
1508 /* Because all loops contain at least one op_pin_state_pinned node, now all
1509 our inputs are either op_pin_state_pinned or place_early() has already
1510 been finished on them. We do not have any unfinished inputs! */
1511 pred_block = get_irn_n(pred, -1);
1512 if ((!is_Block_dead(pred_block)) &&
1513 (get_Block_dom_depth(pred_block) > depth)) {
1515 depth = get_Block_dom_depth(pred_block);
1517 /* Avoid that the node is placed in the Start block */
1518 if ((depth == 1) && (get_Block_dom_depth(get_irn_n(n, -1)) > 1)) {
1519 b = get_Block_cfg_out(get_irg_start_block(current_ir_graph), 0);
1520 assert(b != get_irg_start_block(current_ir_graph));
1525 set_nodes_block(n, b);
1529 * Add predecessors of non floating nodes and non-floating predecessors
1530 * of floating nodes to worklist and fix their blocks if the are in dead block.
1532 irn_arity = get_irn_arity(n);
1534 if (get_irn_op(n) == op_End) {
1536 * Simplest case: End node. Predecessors are keep-alives,
1537 * no need to move out of dead block.
1539 for (i = -1; i < irn_arity; ++i) {
1540 ir_node *pred = get_irn_n(n, i);
1541 if (irn_not_visited(pred))
1542 pdeq_putr(worklist, pred);
1545 else if (is_Block(n)) {
1547 * Blocks: Predecessors are control flow, no need to move
1548 * them out of dead block.
1550 for (i = irn_arity - 1; i >= 0; --i) {
1551 ir_node *pred = get_irn_n(n, i);
1552 if (irn_not_visited(pred))
1553 pdeq_putr(worklist, pred);
1556 else if (is_Phi(n)) {
1558 ir_node *curr_block = get_irn_n(n, -1);
1559 int in_dead_block = is_Block_unreachable(curr_block);
1562 * Phi nodes: move nodes from dead blocks into the effective use
1563 * of the Phi-input if the Phi is not in a bad block.
1565 pred = get_irn_n(n, -1);
1566 if (irn_not_visited(pred))
1567 pdeq_putr(worklist, pred);
1569 for (i = irn_arity - 1; i >= 0; --i) {
1570 ir_node *pred = get_irn_n(n, i);
1572 if (irn_not_visited(pred)) {
1573 if (! in_dead_block &&
1574 get_irn_pinned(pred) == op_pin_state_floats &&
1575 is_Block_unreachable(get_irn_n(pred, -1))) {
1576 set_nodes_block(pred, get_Block_cfgpred_block(curr_block, i));
1578 pdeq_putr(worklist, pred);
1584 ir_node *curr_block = get_irn_n(n, -1);
1585 int in_dead_block = is_Block_unreachable(curr_block);
1588 * All other nodes: move nodes from dead blocks into the same block.
1590 pred = get_irn_n(n, -1);
1591 if (irn_not_visited(pred))
1592 pdeq_putr(worklist, pred);
1594 for (i = irn_arity - 1; i >= 0; --i) {
1595 ir_node *pred = get_irn_n(n, i);
1597 if (irn_not_visited(pred)) {
1598 if (! in_dead_block &&
1599 get_irn_pinned(pred) == op_pin_state_floats &&
1600 is_Block_unreachable(get_irn_n(pred, -1))) {
1601 set_nodes_block(pred, curr_block);
1603 pdeq_putr(worklist, pred);
1610 * Floating nodes form subgraphs that begin at nodes as Const, Load,
1611 * Start, Call and that end at op_pin_state_pinned nodes as Store, Call. Place_early
1612 * places all floating nodes reachable from its argument through floating
1613 * nodes and adds all beginnings at op_pin_state_pinned nodes to the worklist.
1615 static INLINE void place_early(pdeq *worklist) {
1617 inc_irg_visited(current_ir_graph);
1619 /* this inits the worklist */
1620 place_floats_early(get_irg_end(current_ir_graph), worklist);
1622 /* Work the content of the worklist. */
1623 while (!pdeq_empty(worklist)) {
1624 ir_node *n = pdeq_getl(worklist);
1625 if (irn_not_visited(n))
1626 place_floats_early(n, worklist);
1629 set_irg_outs_inconsistent(current_ir_graph);
1630 set_irg_pinned(current_ir_graph, op_pin_state_pinned);
1634 * Compute the deepest common ancestor of block and dca.
1636 static ir_node *calc_dca(ir_node *dca, ir_node *block)
1640 /* we do not want to place nodes in dead blocks */
1641 if (is_Block_dead(block))
1644 /* We found a first legal placement. */
1645 if (!dca) return block;
1647 /* Find a placement that is dominates both, dca and block. */
1648 while (get_Block_dom_depth(block) > get_Block_dom_depth(dca))
1649 block = get_Block_idom(block);
1651 while (get_Block_dom_depth(dca) > get_Block_dom_depth(block)) {
1652 dca = get_Block_idom(dca);
1655 while (block != dca)
1656 { block = get_Block_idom(block); dca = get_Block_idom(dca); }
1661 /** Deepest common dominance ancestor of DCA and CONSUMER of PRODUCER.
1662 * I.e., DCA is the block where we might place PRODUCER.
1663 * A data flow edge points from producer to consumer.
1666 consumer_dom_dca(ir_node *dca, ir_node *consumer, ir_node *producer)
1668 ir_node *block = NULL;
1670 /* Compute the latest block into which we can place a node so that it is
1672 if (get_irn_op(consumer) == op_Phi) {
1673 /* our consumer is a Phi-node, the effective use is in all those
1674 blocks through which the Phi-node reaches producer */
1676 ir_node *phi_block = get_nodes_block(consumer);
1677 irn_arity = get_irn_arity(consumer);
1679 for (i = 0; i < irn_arity; i++) {
1680 if (get_irn_n(consumer, i) == producer) {
1681 ir_node *new_block = get_nodes_block(get_Block_cfgpred(phi_block, i));
1683 if (! is_Block_unreachable(new_block))
1684 block = calc_dca(block, new_block);
1689 block = get_irn_n(producer, -1);
1692 assert(is_no_Block(consumer));
1693 block = get_nodes_block(consumer);
1696 /* Compute the deepest common ancestor of block and dca. */
1697 return calc_dca(dca, block);
1700 /* FIXME: the name clashes here with the function from ana/field_temperature.c
1702 static INLINE int get_irn_loop_depth(ir_node *n) {
1703 return get_loop_depth(get_irn_loop(n));
1707 * Move n to a block with less loop depth than it's current block. The
1708 * new block must be dominated by early.
1710 * @param n the node that should be moved
1711 * @param early the earliest block we can n move to
1714 move_out_of_loops (ir_node *n, ir_node *early)
1716 ir_node *best, *dca;
1720 /* Find the region deepest in the dominator tree dominating
1721 dca with the least loop nesting depth, but still dominated
1722 by our early placement. */
1723 dca = get_nodes_block(n);
1726 while (dca != early) {
1727 dca = get_Block_idom(dca);
1728 if (!dca || is_Bad(dca)) break; /* may be Bad if not reachable from Start */
1729 if (get_irn_loop_depth(dca) < get_irn_loop_depth(best)) {
1733 if (best != get_nodes_block(n)) {
1735 printf("Moving out of loop: "); DDMN(n);
1736 printf(" Outermost block: "); DDMN(early);
1737 printf(" Best block: "); DDMN(best);
1738 printf(" Innermost block: "); DDMN(get_nodes_block(n));
1740 set_nodes_block(n, best);
1745 * Find the latest legal block for N and place N into the
1746 * `optimal' Block between the latest and earliest legal block.
1747 * The `optimal' block is the dominance-deepest block of those
1748 * with the least loop-nesting-depth. This places N out of as many
1749 * loops as possible and then makes it as control dependent as
1753 place_floats_late(ir_node *n, pdeq *worklist)
1758 assert(irn_not_visited(n)); /* no multiple placement */
1760 mark_irn_visited(n);
1762 /* no need to place block nodes, control nodes are already placed. */
1763 if ((get_irn_op(n) != op_Block) &&
1765 (get_irn_mode(n) != mode_X)) {
1766 /* Remember the early_blk placement of this block to move it
1767 out of loop no further than the early_blk placement. */
1768 early_blk = get_irn_n(n, -1);
1771 * BEWARE: Here we also get code, that is live, but
1772 * was in a dead block. If the node is life, but because
1773 * of CSE in a dead block, we still might need it.
1776 /* Assure that our users are all placed, except the Phi-nodes.
1777 --- Each data flow cycle contains at least one Phi-node. We
1778 have to break the `user has to be placed before the
1779 producer' dependence cycle and the Phi-nodes are the
1780 place to do so, because we need to base our placement on the
1781 final region of our users, which is OK with Phi-nodes, as they
1782 are op_pin_state_pinned, and they never have to be placed after a
1783 producer of one of their inputs in the same block anyway. */
1784 for (i = get_irn_n_outs(n) - 1; i >= 0; --i) {
1785 ir_node *succ = get_irn_out(n, i);
1786 if (irn_not_visited(succ) && (get_irn_op(succ) != op_Phi))
1787 place_floats_late(succ, worklist);
1790 if (! is_Block_dead(early_blk)) {
1791 /* do only move things that where not dead */
1793 /* We have to determine the final block of this node... except for
1795 if ((get_irn_pinned(n) == op_pin_state_floats) &&
1796 (get_irn_op(n) != op_Const) &&
1797 (get_irn_op(n) != op_SymConst)) {
1798 ir_node *dca = NULL; /* deepest common ancestor in the
1799 dominator tree of all nodes'
1800 blocks depending on us; our final
1801 placement has to dominate DCA. */
1802 for (i = get_irn_n_outs(n) - 1; i >= 0; --i) {
1803 ir_node *succ = get_irn_out(n, i);
1806 if (get_irn_op(succ) == op_End) {
1808 * This consumer is the End node, a keep alive edge.
1809 * This is not a real consumer, so we ignore it
1814 /* ignore if succ is in dead code */
1815 succ_blk = get_irn_n(succ, -1);
1816 if (is_Block_unreachable(succ_blk))
1818 dca = consumer_dom_dca(dca, succ, n);
1821 set_nodes_block(n, dca);
1822 move_out_of_loops(n, early_blk);
1828 /* Add predecessors of all non-floating nodes on list. (Those of floating
1829 nodes are placed already and therefore are marked.) */
1830 for (i = 0; i < get_irn_n_outs(n); i++) {
1831 ir_node *succ = get_irn_out(n, i);
1832 if (irn_not_visited(get_irn_out(n, i))) {
1833 pdeq_putr(worklist, succ);
1838 static INLINE void place_late(pdeq *worklist) {
1840 inc_irg_visited(current_ir_graph);
1842 /* This fills the worklist initially. */
1843 place_floats_late(get_irg_start_block(current_ir_graph), worklist);
1845 /* And now empty the worklist again... */
1846 while (!pdeq_empty(worklist)) {
1847 ir_node *n = pdeq_getl(worklist);
1848 if (irn_not_visited(n))
1849 place_floats_late(n, worklist);
1853 void place_code(ir_graph *irg) {
1855 ir_graph *rem = current_ir_graph;
1857 current_ir_graph = irg;
1859 if (!(get_opt_optimize() && get_opt_global_cse())) return;
1861 /* Handle graph state */
1862 assert(get_irg_phase_state(irg) != phase_building);
1863 if (get_irg_dom_state(irg) != dom_consistent)
1866 if (1 || get_irg_loopinfo_state(irg) != loopinfo_consistent) {
1867 free_loop_information(irg);
1868 construct_backedges(irg);
1871 /* Place all floating nodes as early as possible. This guarantees
1872 a legal code placement. */
1873 worklist = new_pdeq();
1874 place_early(worklist);
1876 /* place_early() invalidates the outs, place_late needs them. */
1877 compute_irg_outs(irg);
1879 /* Now move the nodes down in the dominator tree. This reduces the
1880 unnecessary executions of the node. */
1881 place_late(worklist);
1883 set_irg_outs_inconsistent(current_ir_graph);
1884 set_irg_loopinfo_inconsistent(current_ir_graph);
1886 current_ir_graph = rem;
1890 * Called by walker of remove_critical_cf_edges().
1892 * Place an empty block to an edge between a blocks of multiple
1893 * predecessors and a block of multiple successors.
1896 * @param env Environment of walker. This field is unused and has
1899 static void walk_critical_cf_edges(ir_node *n, void *env) {
1901 ir_node *pre, *block, **in, *jmp;
1903 /* Block has multiple predecessors */
1904 if ((op_Block == get_irn_op(n)) &&
1905 (get_irn_arity(n) > 1)) {
1906 arity = get_irn_arity(n);
1908 if (n == get_irg_end_block(current_ir_graph))
1909 return; /* No use to add a block here. */
1911 for (i=0; i<arity; i++) {
1912 pre = get_irn_n(n, i);
1913 /* Predecessor has multiple successors. Insert new flow edge */
1914 if ((NULL != pre) &&
1915 (op_Proj == get_irn_op(pre)) &&
1916 op_Raise != get_irn_op(skip_Proj(pre))) {
1918 /* set predecessor array for new block */
1919 in = NEW_ARR_D (ir_node *, current_ir_graph->obst, 1);
1920 /* set predecessor of new block */
1922 block = new_Block(1, in);
1923 /* insert new jmp node to new block */
1924 set_cur_block(block);
1927 /* set successor of new block */
1928 set_irn_n(n, i, jmp);
1930 } /* predecessor has multiple successors */
1931 } /* for all predecessors */
1932 } /* n is a block */
1935 void remove_critical_cf_edges(ir_graph *irg) {
1936 if (get_opt_critical_edges())
1937 irg_walk_graph(irg, NULL, walk_critical_cf_edges, NULL);