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, Michael Beck
9 * Copyright: (c) 1998-2006 Universität Karlsruhe
10 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
19 #include "irgraph_t.h"
32 #include "pdeq.h" /* Fuer code placement */
37 #include "irbackedge_t.h"
44 #include "iredges_t.h"
47 /*------------------------------------------------------------------*/
48 /* apply optimizations of iropt to all nodes. */
49 /*------------------------------------------------------------------*/
52 * A wrapper around optimize_inplace_2() to be called from a walker.
54 static void optimize_in_place_wrapper (ir_node *n, void *env) {
55 ir_node *optimized = optimize_in_place_2(n);
56 if (optimized != n) exchange (n, optimized);
60 * Do local optimizations for a node.
62 * @param n the IR-node where to start. Typically the End node
65 * @note current_ir_graph must be set
67 static INLINE void do_local_optimize(ir_node *n) {
68 /* Handle graph state */
69 assert(get_irg_phase_state(current_ir_graph) != phase_building);
71 if (get_opt_global_cse())
72 set_irg_pinned(current_ir_graph, op_pin_state_floats);
73 set_irg_outs_inconsistent(current_ir_graph);
74 set_irg_doms_inconsistent(current_ir_graph);
75 set_irg_loopinfo_inconsistent(current_ir_graph);
77 /* Clean the value_table in irg for the CSE. */
78 del_identities(current_ir_graph->value_table);
79 current_ir_graph->value_table = new_identities();
81 /* walk over the graph */
82 irg_walk(n, firm_clear_link, optimize_in_place_wrapper, NULL);
85 /* Applies local optimizations (see iropt.h) to all nodes reachable from node n */
86 void local_optimize_node(ir_node *n) {
87 ir_graph *rem = current_ir_graph;
88 current_ir_graph = get_irn_irg(n);
92 current_ir_graph = rem;
96 * Block-Walker: uses dominance depth to mark dead blocks.
98 static void kill_dead_blocks(ir_node *block, void *env)
100 if (get_Block_dom_depth(block) < 0) {
102 * Note that the new dominance code correctly handles
103 * the End block, i.e. it is always reachable from Start
105 set_Block_dead(block);
109 /* Applies local optimizations (see iropt.h) to all nodes reachable from node n. */
110 void local_optimize_graph(ir_graph *irg) {
111 ir_graph *rem = current_ir_graph;
112 current_ir_graph = irg;
114 if (get_irg_dom_state(irg) == dom_consistent)
115 irg_block_walk_graph(irg, NULL, kill_dead_blocks, NULL);
117 do_local_optimize(get_irg_end(irg));
119 current_ir_graph = rem;
123 * Enqueue all users of a node to a wait queue.
124 * Handles mode_T nodes.
126 static void enqueue_users(ir_node *n, pdeq *waitq) {
127 const ir_edge_t *edge;
129 foreach_out_edge(n, edge) {
130 ir_node *succ = get_edge_src_irn(edge);
132 if (get_irn_link(succ) != waitq) {
133 pdeq_putr(waitq, succ);
134 set_irn_link(succ, waitq);
136 if (get_irn_mode(succ) == mode_T) {
137 /* A mode_T node has Proj's. Because most optimizations
138 run on the Proj's we have to enqueue them also. */
139 enqueue_users(succ, waitq);
145 * Data flow optimization walker.
146 * Optimizes all nodes and enqueue it's users
149 static void opt_walker(ir_node *n, void *env) {
153 optimized = optimize_in_place_2(n);
154 set_irn_link(optimized, NULL);
156 if (optimized != n) {
157 enqueue_users(n, waitq);
158 exchange(n, optimized);
162 /* Applies local optimizations to all nodes in the graph until fixpoint. */
163 void optimize_graph_df(ir_graph *irg) {
164 pdeq *waitq = new_pdeq();
165 int state = edges_activated(irg);
166 ir_graph *rem = current_ir_graph;
168 current_ir_graph = irg;
173 if (get_opt_global_cse())
174 set_irg_pinned(current_ir_graph, op_pin_state_floats);
176 /* Clean the value_table in irg for the CSE. */
177 del_identities(irg->value_table);
178 irg->value_table = new_identities();
180 if (get_irg_dom_state(irg) == dom_consistent)
181 irg_block_walk_graph(irg, NULL, kill_dead_blocks, NULL);
183 /* invalidate info */
184 set_irg_outs_inconsistent(irg);
185 set_irg_doms_inconsistent(irg);
186 set_irg_loopinfo_inconsistent(irg);
188 /* walk over the graph */
189 irg_walk_graph(irg, NULL, opt_walker, waitq);
191 /* finish the wait queue */
192 while (! pdeq_empty(waitq)) {
193 ir_node *n = pdeq_getl(waitq);
195 opt_walker(n, waitq);
201 edges_deactivate(irg);
203 current_ir_graph = rem;
207 /*------------------------------------------------------------------*/
208 /* Routines for dead node elimination / copying garbage collection */
209 /* of the obstack. */
210 /*------------------------------------------------------------------*/
213 * Remember the new node in the old node by using a field all nodes have.
215 #define set_new_node(oldn, newn) set_irn_link(oldn, newn)
218 * Get this new node, before the old node is forgotten.
220 #define get_new_node(oldn) get_irn_link(oldn)
223 * Check if a new node was set.
225 #define has_new_node(n) (get_new_node(n) != NULL)
228 * We use the block_visited flag to mark that we have computed the
229 * number of useful predecessors for this block.
230 * Further we encode the new arity in this flag in the old blocks.
231 * Remembering the arity is useful, as it saves a lot of pointer
232 * accesses. This function is called for all Phi and Block nodes
236 compute_new_arity(ir_node *b) {
237 int i, res, irn_arity;
240 irg_v = get_irg_block_visited(current_ir_graph);
241 block_v = get_Block_block_visited(b);
242 if (block_v >= irg_v) {
243 /* we computed the number of preds for this block and saved it in the
245 return block_v - irg_v;
247 /* compute the number of good predecessors */
248 res = irn_arity = get_irn_arity(b);
249 for (i = 0; i < irn_arity; i++)
250 if (get_irn_opcode(get_irn_n(b, i)) == iro_Bad) res--;
251 /* save it in the flag. */
252 set_Block_block_visited(b, irg_v + res);
258 * Copies the node to the new obstack. The Ins of the new node point to
259 * the predecessors on the old obstack. For block/phi nodes not all
260 * predecessors might be copied. n->link points to the new node.
261 * For Phi and Block nodes the function allocates in-arrays with an arity
262 * only for useful predecessors. The arity is determined by counting
263 * the non-bad predecessors of the block.
265 * @param n The node to be copied
266 * @param env if non-NULL, the node number attribute will be copied to the new node
268 * Note: Also used for loop unrolling.
270 static void copy_node(ir_node *n, void *env) {
273 ir_op *op = get_irn_op(n);
275 /* The end node looses it's flexible in array. This doesn't matter,
276 as dead node elimination builds End by hand, inlineing doesn't use
278 /* assert(op == op_End || ((_ARR_DESCR(n->in))->cookie != ARR_F_MAGIC)); */
281 /* node copied already */
283 } else if (op == op_Block) {
285 new_arity = compute_new_arity(n);
286 n->attr.block.graph_arr = NULL;
288 block = get_nodes_block(n);
290 new_arity = compute_new_arity(block);
292 new_arity = get_irn_arity(n);
295 nn = new_ir_node(get_irn_dbg_info(n),
302 /* Copy the attributes. These might point to additional data. If this
303 was allocated on the old obstack the pointers now are dangling. This
304 frees e.g. the memory of the graph_arr allocated in new_immBlock. */
305 copy_node_attr(n, nn);
309 int copy_node_nr = env != NULL;
311 /* for easier debugging, we want to copy the node numbers too */
312 nn->node_nr = n->node_nr;
318 hook_dead_node_elim_subst(current_ir_graph, n, nn);
322 * Copies new predecessors of old node to new node remembered in link.
323 * Spare the Bad predecessors of Phi and Block nodes.
326 copy_preds(ir_node *n, void *env) {
330 nn = get_new_node(n);
332 /* printf("\n old node: "); DDMSG2(n);
333 printf(" new node: "); DDMSG2(nn);
334 printf(" arities: old: %d, new: %d\n", get_irn_arity(n), get_irn_arity(nn)); */
337 /* Don't copy Bad nodes. */
339 irn_arity = get_irn_arity(n);
340 for (i = 0; i < irn_arity; i++)
341 if (! is_Bad(get_irn_n(n, i))) {
342 set_irn_n (nn, j, get_new_node(get_irn_n(n, i)));
343 /*if (is_backedge(n, i)) set_backedge(nn, j);*/
346 /* repair the block visited flag from above misuse. Repair it in both
347 graphs so that the old one can still be used. */
348 set_Block_block_visited(nn, 0);
349 set_Block_block_visited(n, 0);
350 /* Local optimization could not merge two subsequent blocks if
351 in array contained Bads. Now it's possible.
352 We don't call optimize_in_place as it requires
353 that the fields in ir_graph are set properly. */
354 if ((get_opt_control_flow_straightening()) &&
355 (get_Block_n_cfgpreds(nn) == 1) &&
356 (get_irn_op(get_Block_cfgpred(nn, 0)) == op_Jmp)) {
357 ir_node *old = get_nodes_block(get_Block_cfgpred(nn, 0));
359 /* Jmp jumps into the block it is in -- deal self cycle. */
360 assert(is_Bad(get_new_node(get_irg_bad(current_ir_graph))));
361 exchange(nn, get_new_node(get_irg_bad(current_ir_graph)));
366 } else if (get_irn_op(n) == op_Phi) {
367 /* Don't copy node if corresponding predecessor in block is Bad.
368 The Block itself should not be Bad. */
369 block = get_nodes_block(n);
370 set_irn_n(nn, -1, get_new_node(block));
372 irn_arity = get_irn_arity(n);
373 for (i = 0; i < irn_arity; i++)
374 if (! is_Bad(get_irn_n(block, i))) {
375 set_irn_n(nn, j, get_new_node(get_irn_n(n, i)));
376 /*if (is_backedge(n, i)) set_backedge(nn, j);*/
379 /* If the pre walker reached this Phi after the post walker visited the
380 block block_visited is > 0. */
381 set_Block_block_visited(get_nodes_block(n), 0);
382 /* Compacting the Phi's ins might generate Phis with only one
384 if (get_irn_arity(nn) == 1)
385 exchange(nn, get_irn_n(nn, 0));
387 irn_arity = get_irn_arity(n);
388 for (i = -1; i < irn_arity; i++)
389 set_irn_n (nn, i, get_new_node(get_irn_n(n, i)));
391 /* Now the new node is complete. We can add it to the hash table for CSE.
392 @@@ inlining aborts if we identify End. Why? */
393 if (get_irn_op(nn) != op_End)
394 add_identities(current_ir_graph->value_table, nn);
398 * Copies the graph recursively, compacts the keep-alives of the end node.
400 * @param irg the graph to be copied
401 * @param copy_node_nr If non-zero, the node number will be copied
403 static void copy_graph(ir_graph *irg, int copy_node_nr) {
404 ir_node *oe, *ne, *ob, *nb, *om, *nm; /* old end, new end, old bad, new bad, old NoMem, new NoMem */
405 ir_node *ka; /* keep alive */
409 /* Some nodes must be copied by hand, sigh */
410 vfl = get_irg_visited(irg);
411 set_irg_visited(irg, vfl + 1);
413 oe = get_irg_end(irg);
414 mark_irn_visited(oe);
415 /* copy the end node by hand, allocate dynamic in array! */
416 ne = new_ir_node(get_irn_dbg_info(oe),
423 /* Copy the attributes. Well, there might be some in the future... */
424 copy_node_attr(oe, ne);
425 set_new_node(oe, ne);
427 /* copy the Bad node */
428 ob = get_irg_bad(irg);
429 mark_irn_visited(ob);
430 nb = new_ir_node(get_irn_dbg_info(ob),
437 copy_node_attr(ob, nb);
438 set_new_node(ob, nb);
440 /* copy the NoMem node */
441 om = get_irg_no_mem(irg);
442 mark_irn_visited(om);
443 nm = new_ir_node(get_irn_dbg_info(om),
450 copy_node_attr(om, nm);
451 set_new_node(om, nm);
453 /* copy the live nodes */
454 set_irg_visited(irg, vfl);
455 irg_walk(get_nodes_block(oe), copy_node, copy_preds, INT_TO_PTR(copy_node_nr));
457 /* Note: from yet, the visited flag of the graph is equal to vfl + 1 */
459 /* visit the anchors as well */
460 for (i = anchor_max - 1; i >= 0; --i) {
461 ir_node *n = irg->anchors[i];
463 if (n && (get_irn_visited(n) <= vfl)) {
464 set_irg_visited(irg, vfl);
465 irg_walk(n, copy_node, copy_preds, INT_TO_PTR(copy_node_nr));
469 /* copy_preds for the end node ... */
470 set_nodes_block(ne, get_new_node(get_nodes_block(oe)));
472 /*- ... and now the keep alives. -*/
473 /* First pick the not marked block nodes and walk them. We must pick these
474 first as else we will oversee blocks reachable from Phis. */
475 irn_arity = get_End_n_keepalives(oe);
476 for (i = 0; i < irn_arity; i++) {
477 ka = get_End_keepalive(oe, i);
479 if (get_irn_visited(ka) <= vfl) {
480 /* We must keep the block alive and copy everything reachable */
481 set_irg_visited(irg, vfl);
482 irg_walk(ka, copy_node, copy_preds, INT_TO_PTR(copy_node_nr));
484 add_End_keepalive(ne, get_new_node(ka));
488 /* Now pick other nodes. Here we will keep all! */
489 irn_arity = get_End_n_keepalives(oe);
490 for (i = 0; i < irn_arity; i++) {
491 ka = get_End_keepalive(oe, i);
493 if (get_irn_visited(ka) <= vfl) {
494 /* We didn't copy the node yet. */
495 set_irg_visited(irg, vfl);
496 irg_walk(ka, copy_node, copy_preds, INT_TO_PTR(copy_node_nr));
498 add_End_keepalive(ne, get_new_node(ka));
502 /* start block sometimes only reached after keep alives */
503 set_nodes_block(nb, get_new_node(get_nodes_block(ob)));
504 set_nodes_block(nm, get_new_node(get_nodes_block(om)));
508 * Copies the graph reachable from current_ir_graph->end to the obstack
509 * in current_ir_graph and fixes the environment.
510 * Then fixes the fields in current_ir_graph containing nodes of the
513 * @param copy_node_nr If non-zero, the node number will be copied
516 copy_graph_env(int copy_node_nr) {
517 ir_graph *irg = current_ir_graph;
518 ir_node *old_end, *n;
521 /* remove end_except and end_reg nodes */
522 old_end = get_irg_end(irg);
523 set_irg_end_except (irg, old_end);
524 set_irg_end_reg (irg, old_end);
526 /* Not all nodes remembered in irg might be reachable
527 from the end node. Assure their link is set to NULL, so that
528 we can test whether new nodes have been computed. */
529 for (i = anchor_max - 1; i >= 0; --i) {
531 set_new_node(irg->anchors[i], NULL);
533 /* we use the block walk flag for removing Bads from Blocks ins. */
534 inc_irg_block_visited(irg);
537 copy_graph(irg, copy_node_nr);
539 /* fix the fields in irg */
540 old_end = get_irg_end(irg);
541 for (i = anchor_max - 1; i >= 0; --i) {
544 irg->anchors[i] = get_new_node(n);
550 * Copies all reachable nodes to a new obstack. Removes bad inputs
551 * from block nodes and the corresponding inputs from Phi nodes.
552 * Merges single exit blocks with single entry blocks and removes
554 * Adds all new nodes to a new hash table for CSE. Does not
555 * perform CSE, so the hash table might contain common subexpressions.
558 dead_node_elimination(ir_graph *irg) {
559 if (get_opt_optimize() && get_opt_dead_node_elimination()) {
561 int rem_ipview = get_interprocedural_view();
562 struct obstack *graveyard_obst = NULL;
563 struct obstack *rebirth_obst = NULL;
564 assert(! edges_activated(irg) && "dead node elimination requires disabled edges");
566 /* inform statistics that we started a dead-node elimination run */
567 hook_dead_node_elim(irg, 1);
569 /* Remember external state of current_ir_graph. */
570 rem = current_ir_graph;
571 current_ir_graph = irg;
572 set_interprocedural_view(0);
574 assert(get_irg_phase_state(irg) != phase_building);
576 /* Handle graph state */
577 free_callee_info(irg);
581 /* @@@ so far we loose loops when copying */
582 free_loop_information(irg);
584 set_irg_doms_inconsistent(irg);
586 /* A quiet place, where the old obstack can rest in peace,
587 until it will be cremated. */
588 graveyard_obst = irg->obst;
590 /* A new obstack, where the reachable nodes will be copied to. */
591 rebirth_obst = xmalloc(sizeof(*rebirth_obst));
592 irg->obst = rebirth_obst;
593 obstack_init(irg->obst);
594 irg->last_node_idx = 0;
596 /* We also need a new value table for CSE */
597 del_identities(irg->value_table);
598 irg->value_table = new_identities();
600 /* Copy the graph from the old to the new obstack */
601 copy_graph_env(/*copy_node_nr=*/1);
603 /* Free memory from old unoptimized obstack */
604 obstack_free(graveyard_obst, 0); /* First empty the obstack ... */
605 xfree (graveyard_obst); /* ... then free it. */
607 /* inform statistics that the run is over */
608 hook_dead_node_elim(irg, 0);
610 current_ir_graph = rem;
611 set_interprocedural_view(rem_ipview);
616 * Relink bad predecessors of a block and store the old in array to the
617 * link field. This function is called by relink_bad_predecessors().
618 * The array of link field starts with the block operand at position 0.
619 * If block has bad predecessors, create a new in array without bad preds.
620 * Otherwise let in array untouched.
622 static void relink_bad_block_predecessors(ir_node *n, void *env) {
623 ir_node **new_in, *irn;
624 int i, new_irn_n, old_irn_arity, new_irn_arity = 0;
626 /* if link field of block is NULL, look for bad predecessors otherwise
627 this is already done */
628 if (get_irn_op(n) == op_Block &&
629 get_irn_link(n) == NULL) {
631 /* save old predecessors in link field (position 0 is the block operand)*/
632 set_irn_link(n, get_irn_in(n));
634 /* count predecessors without bad nodes */
635 old_irn_arity = get_irn_arity(n);
636 for (i = 0; i < old_irn_arity; i++)
637 if (!is_Bad(get_irn_n(n, i))) new_irn_arity++;
639 /* arity changing: set new predecessors without bad nodes */
640 if (new_irn_arity < old_irn_arity) {
641 /* Get new predecessor array. We do not resize the array, as we must
642 keep the old one to update Phis. */
643 new_in = NEW_ARR_D (ir_node *, current_ir_graph->obst, (new_irn_arity+1));
645 /* set new predecessors in array */
648 for (i = 0; i < old_irn_arity; i++) {
649 irn = get_irn_n(n, i);
651 new_in[new_irn_n] = irn;
652 is_backedge(n, i) ? set_backedge(n, new_irn_n-1) : set_not_backedge(n, new_irn_n-1);
656 //ARR_SETLEN(int, n->attr.block.backedge, new_irn_arity);
657 ARR_SHRINKLEN(n->attr.block.backedge, new_irn_arity);
660 } /* ir node has bad predecessors */
662 } /* Block is not relinked */
666 * Relinks Bad predecessors from Blocks and Phis called by walker
667 * remove_bad_predecesors(). If n is a Block, call
668 * relink_bad_block_redecessors(). If n is a Phi-node, call also the relinking
669 * function of Phi's Block. If this block has bad predecessors, relink preds
672 static void relink_bad_predecessors(ir_node *n, void *env) {
673 ir_node *block, **old_in;
674 int i, old_irn_arity, new_irn_arity;
676 /* relink bad predecessors of a block */
677 if (get_irn_op(n) == op_Block)
678 relink_bad_block_predecessors(n, env);
680 /* If Phi node relink its block and its predecessors */
681 if (get_irn_op(n) == op_Phi) {
683 /* Relink predecessors of phi's block */
684 block = get_nodes_block(n);
685 if (get_irn_link(block) == NULL)
686 relink_bad_block_predecessors(block, env);
688 old_in = (ir_node **)get_irn_link(block); /* Of Phi's Block */
689 old_irn_arity = ARR_LEN(old_in);
691 /* Relink Phi predecessors if count of predecessors changed */
692 if (old_irn_arity != ARR_LEN(get_irn_in(block))) {
693 /* set new predecessors in array
694 n->in[0] remains the same block */
696 for(i = 1; i < old_irn_arity; i++)
697 if (!is_Bad((ir_node *)old_in[i])) {
698 n->in[new_irn_arity] = n->in[i];
699 is_backedge(n, i) ? set_backedge(n, new_irn_arity) : set_not_backedge(n, new_irn_arity);
703 ARR_SETLEN(ir_node *, n->in, new_irn_arity);
704 ARR_SETLEN(int, n->attr.phi_backedge, new_irn_arity);
707 } /* n is a Phi node */
711 * Removes Bad Bad predecessors from Blocks and the corresponding
712 * inputs to Phi nodes as in dead_node_elimination but without
714 * On walking up set the link field to NULL, on walking down call
715 * relink_bad_predecessors() (This function stores the old in array
716 * to the link field and sets a new in array if arity of predecessors
719 void remove_bad_predecessors(ir_graph *irg) {
720 irg_walk_graph(irg, firm_clear_link, relink_bad_predecessors, NULL);
727 __)|_| | \_/ | \_/(/_ |_/\__|__
729 The following stuff implements a facility that automatically patches
730 registered ir_node pointers to the new node when a dead node elimination occurs.
733 struct _survive_dce_t {
737 hook_entry_t dead_node_elim;
738 hook_entry_t dead_node_elim_subst;
741 typedef struct _survive_dce_list_t {
742 struct _survive_dce_list_t *next;
744 } survive_dce_list_t;
746 static void dead_node_hook(void *context, ir_graph *irg, int start)
748 survive_dce_t *sd = context;
750 /* Create a new map before the dead node elimination is performed. */
752 sd->new_places = pmap_create_ex(pmap_count(sd->places));
755 /* Patch back all nodes if dead node elimination is over and something is to be done. */
757 pmap_destroy(sd->places);
758 sd->places = sd->new_places;
759 sd->new_places = NULL;
764 * Hook called when dead node elimination replaces old by nw.
766 static void dead_node_subst_hook(void *context, ir_graph *irg, ir_node *old, ir_node *nw)
768 survive_dce_t *sd = context;
769 survive_dce_list_t *list = pmap_get(sd->places, old);
771 /* If the node is to be patched back, write the new address to all registered locations. */
773 survive_dce_list_t *p;
775 for(p = list; p; p = p->next)
778 pmap_insert(sd->new_places, nw, list);
783 * Make a new Survive DCE environment.
785 survive_dce_t *new_survive_dce(void)
787 survive_dce_t *res = xmalloc(sizeof(res[0]));
788 obstack_init(&res->obst);
789 res->places = pmap_create();
790 res->new_places = NULL;
792 res->dead_node_elim.hook._hook_dead_node_elim = dead_node_hook;
793 res->dead_node_elim.context = res;
794 res->dead_node_elim.next = NULL;
796 res->dead_node_elim_subst.hook._hook_dead_node_elim_subst = dead_node_subst_hook;
797 res->dead_node_elim_subst.context = res;
798 res->dead_node_elim_subst.next = NULL;
800 #ifndef FIRM_ENABLE_HOOKS
801 assert(0 && "need hooks enabled");
804 register_hook(hook_dead_node_elim, &res->dead_node_elim);
805 register_hook(hook_dead_node_elim_subst, &res->dead_node_elim_subst);
810 * Free a Survive DCE environment.
812 void free_survive_dce(survive_dce_t *sd)
814 obstack_free(&sd->obst, NULL);
815 pmap_destroy(sd->places);
816 unregister_hook(hook_dead_node_elim, &sd->dead_node_elim);
817 unregister_hook(hook_dead_node_elim_subst, &sd->dead_node_elim_subst);
822 * Register a node pointer to be patched upon DCE.
823 * When DCE occurs, the node pointer specified by @p place will be
824 * patched to the new address of the node it is pointing to.
826 * @param sd The Survive DCE environment.
827 * @param place The address of the node pointer.
829 void survive_dce_register_irn(survive_dce_t *sd, ir_node **place)
832 ir_node *irn = *place;
833 survive_dce_list_t *curr = pmap_get(sd->places, irn);
834 survive_dce_list_t *nw = obstack_alloc(&sd->obst, sizeof(nw[0]));
839 pmap_insert(sd->places, irn, nw);
843 /*--------------------------------------------------------------------*/
844 /* Functionality for inlining */
845 /*--------------------------------------------------------------------*/
848 * Copy node for inlineing. Updates attributes that change when
849 * inlineing but not for dead node elimination.
851 * Copies the node by calling copy_node() and then updates the entity if
852 * it's a local one. env must be a pointer of the frame type of the
853 * inlined procedure. The new entities must be in the link field of
857 copy_node_inline (ir_node *n, void *env) {
859 ir_type *frame_tp = (ir_type *)env;
862 if (get_irn_op(n) == op_Sel) {
863 nn = get_new_node (n);
865 if (get_entity_owner(get_Sel_entity(n)) == frame_tp) {
866 set_Sel_entity(nn, get_entity_link(get_Sel_entity(n)));
868 } else if (get_irn_op(n) == op_Block) {
869 nn = get_new_node (n);
870 nn->attr.block.irg = current_ir_graph;
875 * Walker: checks if P_value_arg_base is used.
877 static void find_addr(ir_node *node, void *env) {
878 int *allow_inline = env;
879 if (is_Proj(node) && get_irn_op(get_Proj_pred(node)) == op_Start) {
880 if (get_Proj_proj(node) == pn_Start_P_value_arg_base)
886 * currently, we cannot inline two cases:
887 * - call with compound arguments
888 * - graphs that take the address of a parameter
890 * check these conditions here
892 static int can_inline(ir_node *call, ir_graph *called_graph)
894 ir_type *call_type = get_Call_type(call);
895 int params, ress, i, res;
896 assert(is_Method_type(call_type));
898 params = get_method_n_params(call_type);
899 ress = get_method_n_ress(call_type);
901 /* check parameters for compound arguments */
902 for (i = 0; i < params; ++i) {
903 ir_type *p_type = get_method_param_type(call_type, i);
905 if (is_compound_type(p_type))
909 /* check results for compound arguments */
910 for (i = 0; i < ress; ++i) {
911 ir_type *r_type = get_method_res_type(call_type, i);
913 if (is_compound_type(r_type))
918 irg_walk_graph(called_graph, find_addr, NULL, &res);
923 /* Inlines a method at the given call site. */
924 int inline_method(ir_node *call, ir_graph *called_graph) {
926 ir_node *post_call, *post_bl;
927 ir_node *in[pn_Start_max];
928 ir_node *end, *end_bl;
932 int arity, n_ret, n_exc, n_res, i, j, rem_opt, irn_arity;
934 ir_type *called_frame;
935 irg_inline_property prop = get_irg_inline_property(called_graph);
937 if ( (prop < irg_inline_forced) &&
938 (!get_opt_optimize() || !get_opt_inline() || (prop == irg_inline_forbidden))) return 0;
940 /* Do not inline variadic functions. */
941 if (get_method_variadicity(get_entity_type(get_irg_entity(called_graph))) == variadicity_variadic)
944 assert(get_method_n_params(get_entity_type(get_irg_entity(called_graph))) ==
945 get_method_n_params(get_Call_type(call)));
948 * currently, we cannot inline two cases:
949 * - call with compound arguments
950 * - graphs that take the address of a parameter
952 if (! can_inline(call, called_graph))
955 /* -- Turn off optimizations, this can cause problems when allocating new nodes. -- */
956 rem_opt = get_opt_optimize();
959 /* Handle graph state */
960 assert(get_irg_phase_state(current_ir_graph) != phase_building);
961 assert(get_irg_pinned(current_ir_graph) == op_pin_state_pinned);
962 assert(get_irg_pinned(called_graph) == op_pin_state_pinned);
963 set_irg_outs_inconsistent(current_ir_graph);
964 set_irg_extblk_inconsistent(current_ir_graph);
965 set_irg_doms_inconsistent(current_ir_graph);
966 set_irg_loopinfo_inconsistent(current_ir_graph);
967 set_irg_callee_info_state(current_ir_graph, irg_callee_info_inconsistent);
969 /* -- Check preconditions -- */
970 assert(is_Call(call));
971 /* @@@ does not work for InterfaceIII.java after cgana
972 assert(get_Call_type(call) == get_entity_type(get_irg_entity(called_graph)));
973 assert(smaller_type(get_entity_type(get_irg_entity(called_graph)),
974 get_Call_type(call)));
976 if (called_graph == current_ir_graph) {
977 set_optimize(rem_opt);
981 /* here we know we WILL inline, so inform the statistics */
982 hook_inline(call, called_graph);
984 /* -- Decide how to handle exception control flow: Is there a handler
985 for the Call node, or do we branch directly to End on an exception?
987 0 There is a handler.
989 2 Exception handling not represented in Firm. -- */
991 ir_node *proj, *Mproj = NULL, *Xproj = NULL;
992 for (proj = get_irn_link(call); proj; proj = get_irn_link(proj)) {
993 assert(is_Proj(proj));
994 if (get_Proj_proj(proj) == pn_Call_X_except) Xproj = proj;
995 if (get_Proj_proj(proj) == pn_Call_M_except) Mproj = proj;
997 if (Mproj) { assert(Xproj); exc_handling = 0; } /* Mproj */
998 else if (Xproj) { exc_handling = 1; } /* !Mproj && Xproj */
999 else { exc_handling = 2; } /* !Mproj && !Xproj */
1004 the procedure and later replaces the Start node of the called graph.
1005 Post_call is the old Call node and collects the results of the called
1006 graph. Both will end up being a tuple. -- */
1007 post_bl = get_nodes_block(call);
1008 set_irg_current_block(current_ir_graph, post_bl);
1009 /* XxMxPxPxPxT of Start + parameter of Call */
1010 in[pn_Start_X_initial_exec] = new_Jmp();
1011 in[pn_Start_M] = get_Call_mem(call);
1012 in[pn_Start_P_frame_base] = get_irg_frame(current_ir_graph);
1013 in[pn_Start_P_globals] = get_irg_globals(current_ir_graph);
1014 in[pn_Start_P_tls] = get_irg_tls(current_ir_graph);
1015 in[pn_Start_T_args] = new_Tuple(get_Call_n_params(call), get_Call_param_arr(call));
1016 /* in[pn_Start_P_value_arg_base] = ??? */
1017 assert(pn_Start_P_value_arg_base == pn_Start_max - 1 && "pn_Start_P_value_arg_base not supported, fix");
1018 pre_call = new_Tuple(pn_Start_max - 1, in);
1022 The new block gets the ins of the old block, pre_call and all its
1023 predecessors and all Phi nodes. -- */
1024 part_block(pre_call);
1026 /* -- Prepare state for dead node elimination -- */
1027 /* Visited flags in calling irg must be >= flag in called irg.
1028 Else walker and arity computation will not work. */
1029 if (get_irg_visited(current_ir_graph) <= get_irg_visited(called_graph))
1030 set_irg_visited(current_ir_graph, get_irg_visited(called_graph)+1);
1031 if (get_irg_block_visited(current_ir_graph)< get_irg_block_visited(called_graph))
1032 set_irg_block_visited(current_ir_graph, get_irg_block_visited(called_graph));
1033 /* Set pre_call as new Start node in link field of the start node of
1034 calling graph and pre_calls block as new block for the start block
1036 Further mark these nodes so that they are not visited by the
1038 set_irn_link(get_irg_start(called_graph), pre_call);
1039 set_irn_visited(get_irg_start(called_graph), get_irg_visited(current_ir_graph));
1040 set_irn_link(get_irg_start_block(called_graph), get_nodes_block(pre_call));
1041 set_irn_visited(get_irg_start_block(called_graph), get_irg_visited(current_ir_graph));
1042 set_irn_link(get_irg_bad(called_graph), get_irg_bad(current_ir_graph));
1043 set_irn_visited(get_irg_bad(called_graph), get_irg_visited(current_ir_graph));
1045 /* Initialize for compaction of in arrays */
1046 inc_irg_block_visited(current_ir_graph);
1048 /* -- Replicate local entities of the called_graph -- */
1049 /* copy the entities. */
1050 called_frame = get_irg_frame_type(called_graph);
1051 for (i = 0; i < get_class_n_members(called_frame); i++) {
1052 ir_entity *new_ent, *old_ent;
1053 old_ent = get_class_member(called_frame, i);
1054 new_ent = copy_entity_own(old_ent, get_cur_frame_type());
1055 set_entity_link(old_ent, new_ent);
1058 /* visited is > than that of called graph. With this trick visited will
1059 remain unchanged so that an outer walker, e.g., searching the call nodes
1060 to inline, calling this inline will not visit the inlined nodes. */
1061 set_irg_visited(current_ir_graph, get_irg_visited(current_ir_graph)-1);
1063 /* -- Performing dead node elimination inlines the graph -- */
1064 /* Copies the nodes to the obstack of current_ir_graph. Updates links to new
1066 /* @@@ endless loops are not copied!! -- they should be, I think... */
1067 irg_walk(get_irg_end(called_graph), copy_node_inline, copy_preds,
1068 get_irg_frame_type(called_graph));
1070 /* Repair called_graph */
1071 set_irg_visited(called_graph, get_irg_visited(current_ir_graph));
1072 set_irg_block_visited(called_graph, get_irg_block_visited(current_ir_graph));
1073 set_Block_block_visited(get_irg_start_block(called_graph), 0);
1075 /* -- Merge the end of the inlined procedure with the call site -- */
1076 /* We will turn the old Call node into a Tuple with the following
1079 0: Phi of all Memories of Return statements.
1080 1: Jmp from new Block that merges the control flow from all exception
1081 predecessors of the old end block.
1082 2: Tuple of all arguments.
1083 3: Phi of Exception memories.
1084 In case the old Call directly branches to End on an exception we don't
1085 need the block merging all exceptions nor the Phi of the exception
1089 /* -- Precompute some values -- */
1090 end_bl = get_new_node(get_irg_end_block(called_graph));
1091 end = get_new_node(get_irg_end(called_graph));
1092 arity = get_irn_arity(end_bl); /* arity = n_exc + n_ret */
1093 n_res = get_method_n_ress(get_Call_type(call));
1095 res_pred = xmalloc (n_res * sizeof(*res_pred));
1096 cf_pred = xmalloc (arity * sizeof(*res_pred));
1098 set_irg_current_block(current_ir_graph, post_bl); /* just to make sure */
1100 /* -- archive keepalives -- */
1101 irn_arity = get_irn_arity(end);
1102 for (i = 0; i < irn_arity; i++)
1103 add_End_keepalive(get_irg_end(current_ir_graph), get_irn_n(end, i));
1105 /* The new end node will die. We need not free as the in array is on the obstack:
1106 copy_node() only generated 'D' arrays. */
1108 /* -- Replace Return nodes by Jump nodes. -- */
1110 for (i = 0; i < arity; i++) {
1112 ret = get_irn_n(end_bl, i);
1113 if (is_Return(ret)) {
1114 cf_pred[n_ret] = new_r_Jmp(current_ir_graph, get_nodes_block(ret));
1118 set_irn_in(post_bl, n_ret, cf_pred);
1120 /* -- Build a Tuple for all results of the method.
1121 Add Phi node if there was more than one Return. -- */
1122 turn_into_tuple(post_call, 4);
1123 /* First the Memory-Phi */
1125 for (i = 0; i < arity; i++) {
1126 ret = get_irn_n(end_bl, i);
1127 if (is_Return(ret)) {
1128 cf_pred[n_ret] = get_Return_mem(ret);
1132 phi = new_Phi(n_ret, cf_pred, mode_M);
1133 set_Tuple_pred(call, pn_Call_M_regular, phi);
1134 /* Conserve Phi-list for further inlinings -- but might be optimized */
1135 if (get_nodes_block(phi) == post_bl) {
1136 set_irn_link(phi, get_irn_link(post_bl));
1137 set_irn_link(post_bl, phi);
1139 /* Now the real results */
1141 for (j = 0; j < n_res; j++) {
1143 for (i = 0; i < arity; i++) {
1144 ret = get_irn_n(end_bl, i);
1145 if (get_irn_op(ret) == op_Return) {
1146 cf_pred[n_ret] = get_Return_res(ret, j);
1151 phi = new_Phi(n_ret, cf_pred, get_irn_mode(cf_pred[0]));
1155 /* Conserve Phi-list for further inlinings -- but might be optimized */
1156 if (get_nodes_block(phi) == post_bl) {
1157 set_irn_link(phi, get_irn_link(post_bl));
1158 set_irn_link(post_bl, phi);
1161 set_Tuple_pred(call, pn_Call_T_result, new_Tuple(n_res, res_pred));
1163 set_Tuple_pred(call, pn_Call_T_result, new_Bad());
1165 /* Finally the exception control flow.
1166 We have two (three) possible situations:
1167 First if the Call branches to an exception handler: We need to add a Phi node to
1168 collect the memory containing the exception objects. Further we need
1169 to add another block to get a correct representation of this Phi. To
1170 this block we add a Jmp that resolves into the X output of the Call
1171 when the Call is turned into a tuple.
1172 Second the Call branches to End, the exception is not handled. Just
1173 add all inlined exception branches to the End node.
1174 Third: there is no Exception edge at all. Handle as case two. */
1175 if (exc_handling == 0) {
1177 for (i = 0; i < arity; i++) {
1179 ret = get_irn_n(end_bl, i);
1180 if (is_fragile_op(skip_Proj(ret)) || (get_irn_op(skip_Proj(ret)) == op_Raise)) {
1181 cf_pred[n_exc] = ret;
1186 new_Block(n_exc, cf_pred); /* watch it: current_block is changed! */
1187 set_Tuple_pred(call, pn_Call_X_except, new_Jmp());
1188 /* The Phi for the memories with the exception objects */
1190 for (i = 0; i < arity; i++) {
1192 ret = skip_Proj(get_irn_n(end_bl, i));
1194 cf_pred[n_exc] = new_r_Proj(current_ir_graph, get_nodes_block(ret), ret, mode_M, 3);
1196 } else if (is_fragile_op(ret)) {
1197 /* We rely that all cfops have the memory output at the same position. */
1198 cf_pred[n_exc] = new_r_Proj(current_ir_graph, get_nodes_block(ret), ret, mode_M, 0);
1200 } else if (get_irn_op(ret) == op_Raise) {
1201 cf_pred[n_exc] = new_r_Proj(current_ir_graph, get_nodes_block(ret), ret, mode_M, 1);
1205 set_Tuple_pred(call, pn_Call_M_except, new_Phi(n_exc, cf_pred, mode_M));
1207 set_Tuple_pred(call, pn_Call_X_except, new_Bad());
1208 set_Tuple_pred(call, pn_Call_M_except, new_Bad());
1211 ir_node *main_end_bl;
1212 int main_end_bl_arity;
1213 ir_node **end_preds;
1215 /* assert(exc_handling == 1 || no exceptions. ) */
1217 for (i = 0; i < arity; i++) {
1218 ir_node *ret = get_irn_n(end_bl, i);
1220 if (is_fragile_op(skip_Proj(ret)) || (get_irn_op(skip_Proj(ret)) == op_Raise)) {
1221 cf_pred[n_exc] = ret;
1225 main_end_bl = get_irg_end_block(current_ir_graph);
1226 main_end_bl_arity = get_irn_arity(main_end_bl);
1227 end_preds = xmalloc ((n_exc + main_end_bl_arity) * sizeof(*end_preds));
1229 for (i = 0; i < main_end_bl_arity; ++i)
1230 end_preds[i] = get_irn_n(main_end_bl, i);
1231 for (i = 0; i < n_exc; ++i)
1232 end_preds[main_end_bl_arity + i] = cf_pred[i];
1233 set_irn_in(main_end_bl, n_exc + main_end_bl_arity, end_preds);
1234 set_Tuple_pred(call, pn_Call_X_except, new_Bad());
1235 set_Tuple_pred(call, pn_Call_M_except, new_Bad());
1241 /* -- Turn CSE back on. -- */
1242 set_optimize(rem_opt);
1247 /********************************************************************/
1248 /* Apply inlineing to small methods. */
1249 /********************************************************************/
1251 /** Represents a possible inlinable call in a graph. */
1252 typedef struct _call_entry call_entry;
1253 struct _call_entry {
1254 ir_node *call; /**< the Call */
1255 ir_graph *callee; /**< the callee called here */
1256 call_entry *next; /**< for linking the next one */
1260 * environment for inlining small irgs
1262 typedef struct _inline_env_t {
1263 struct obstack obst; /**< an obstack where call_entries are allocated on. */
1264 call_entry *head; /**< the head of the call entry list */
1265 call_entry *tail; /**< the tail of the call entry list */
1269 * Returns the irg called from a Call node. If the irg is not
1270 * known, NULL is returned.
1272 static ir_graph *get_call_called_irg(ir_node *call) {
1274 ir_graph *called_irg = NULL;
1276 addr = get_Call_ptr(call);
1277 if (is_SymConst(addr) && get_SymConst_kind(addr) == symconst_addr_ent) {
1278 called_irg = get_entity_irg(get_SymConst_entity(addr));
1285 * Walker: Collect all calls to known graphs inside a graph.
1287 static void collect_calls(ir_node *call, void *env) {
1288 if (is_Call(call)) {
1289 ir_graph *called_irg = get_call_called_irg(call);
1291 /* The Call node calls a locally defined method. Remember to inline. */
1292 inline_env_t *ienv = env;
1293 call_entry *entry = obstack_alloc(&ienv->obst, sizeof(*entry));
1295 entry->callee = called_irg;
1298 if (ienv->tail == NULL)
1301 ienv->tail->next = entry;
1308 * Inlines all small methods at call sites where the called address comes
1309 * from a Const node that references the entity representing the called
1311 * The size argument is a rough measure for the code size of the method:
1312 * Methods where the obstack containing the firm graph is smaller than
1315 void inline_small_irgs(ir_graph *irg, int size) {
1316 ir_graph *rem = current_ir_graph;
1319 DEBUG_ONLY(firm_dbg_module_t *dbg;)
1321 if (!(get_opt_optimize() && get_opt_inline())) return;
1323 FIRM_DBG_REGISTER(dbg, "firm.opt.inline");
1325 current_ir_graph = irg;
1326 /* Handle graph state */
1327 assert(get_irg_phase_state(irg) != phase_building);
1328 free_callee_info(irg);
1330 /* Find Call nodes to inline.
1331 (We can not inline during a walk of the graph, as inlineing the same
1332 method several times changes the visited flag of the walked graph:
1333 after the first inlineing visited of the callee equals visited of
1334 the caller. With the next inlineing both are increased.) */
1335 obstack_init(&env.obst);
1336 env.head = env.tail = NULL;
1337 irg_walk_graph(irg, NULL, collect_calls, &env);
1339 if (env.head != NULL) {
1340 /* There are calls to inline */
1341 collect_phiprojs(irg);
1342 for (entry = env.head; entry != NULL; entry = entry->next) {
1343 ir_graph *callee = entry->callee;
1344 if (((_obstack_memory_used(callee->obst) - (int)obstack_room(callee->obst)) < size) ||
1345 (get_irg_inline_property(callee) >= irg_inline_forced)) {
1346 inline_method(entry->call, callee);
1350 obstack_free(&env.obst, NULL);
1351 current_ir_graph = rem;
1355 * Environment for inlining irgs.
1358 int n_nodes; /**< Number of nodes in graph except Id, Tuple, Proj, Start, End. */
1359 int n_nodes_orig; /**< for statistics */
1360 call_entry *call_head; /**< The head of the list of all call nodes in this graph. */
1361 call_entry *call_tail; /**< The tail of the list of all call nodes in this graph .*/
1362 int n_call_nodes; /**< Number of Call nodes in the graph. */
1363 int n_call_nodes_orig; /**< for statistics */
1364 int n_callers; /**< Number of known graphs that call this graphs. */
1365 int n_callers_orig; /**< for statistics */
1366 int got_inline; /**< Set, if at leat one call inside this graph was inlined. */
1370 * Allocate a new environment for inlining.
1372 static inline_irg_env *alloc_inline_irg_env(struct obstack *obst) {
1373 inline_irg_env *env = obstack_alloc(obst, sizeof(*env));
1374 env->n_nodes = -2; /* do not count count Start, End */
1375 env->n_nodes_orig = -2; /* do not count Start, End */
1376 env->call_head = NULL;
1377 env->call_tail = NULL;
1378 env->n_call_nodes = 0;
1379 env->n_call_nodes_orig = 0;
1381 env->n_callers_orig = 0;
1382 env->got_inline = 0;
1386 typedef struct walker_env {
1387 struct obstack *obst; /**< the obstack for allocations. */
1388 inline_irg_env *x; /**< the inline environment */
1389 int ignore_runtime; /**< the ignore runtime flag */
1393 * post-walker: collect all calls in the inline-environment
1394 * of a graph and sum some statistics.
1396 static void collect_calls2(ir_node *call, void *ctx) {
1398 inline_irg_env *x = env->x;
1399 ir_op *op = get_irn_op(call);
1403 /* count meaningful nodes in irg */
1404 if (op != op_Proj && op != op_Tuple && op != op_Sync) {
1409 if (op != op_Call) return;
1411 /* check, if it's a runtime call */
1412 if (env->ignore_runtime) {
1413 ir_node *symc = get_Call_ptr(call);
1415 if (is_SymConst(symc) && get_SymConst_kind(symc) == symconst_addr_ent) {
1416 ir_entity *ent = get_SymConst_entity(symc);
1418 if (get_entity_additional_properties(ent) & mtp_property_runtime)
1423 /* collect all call nodes */
1425 ++x->n_call_nodes_orig;
1427 callee = get_call_called_irg(call);
1429 inline_irg_env *callee_env = get_irg_link(callee);
1430 /* count all static callers */
1431 ++callee_env->n_callers;
1432 ++callee_env->n_callers_orig;
1434 /* link it in the list of possible inlinable entries */
1435 entry = obstack_alloc(env->obst, sizeof(*entry));
1437 entry->callee = callee;
1439 if (x->call_tail == NULL)
1440 x->call_head = entry;
1442 x->call_tail->next = entry;
1443 x->call_tail = entry;
1448 * Returns TRUE if the number of callers in 0 in the irg's environment,
1449 * hence this irg is a leave.
1451 INLINE static int is_leave(ir_graph *irg) {
1452 inline_irg_env *env = get_irg_link(irg);
1453 return env->n_call_nodes == 0;
1457 * Returns TRUE if the number of callers is smaller size in the irg's environment.
1459 INLINE static int is_smaller(ir_graph *callee, int size) {
1460 inline_irg_env *env = get_irg_link(callee);
1461 return env->n_nodes < size;
1465 * Append the nodes of the list src to the nodes of the list in environment dst.
1467 static void append_call_list(struct obstack *obst, inline_irg_env *dst, call_entry *src) {
1468 call_entry *entry, *nentry;
1470 /* Note that the src list points to Call nodes in the inlined graph, but
1471 we need Call nodes in our graph. Luckily the inliner leaves this information
1472 in the link field. */
1473 for (entry = src; entry != NULL; entry = entry->next) {
1474 nentry = obstack_alloc(obst, sizeof(*nentry));
1475 nentry->call = get_irn_link(entry->call);
1476 nentry->callee = entry->callee;
1477 nentry->next = NULL;
1478 dst->call_tail->next = nentry;
1479 dst->call_tail = nentry;
1484 * Inlines small leave methods at call sites where the called address comes
1485 * from a Const node that references the entity representing the called
1487 * The size argument is a rough measure for the code size of the method:
1488 * Methods where the obstack containing the firm graph is smaller than
1491 void inline_leave_functions(int maxsize, int leavesize, int size, int ignore_runtime) {
1492 inline_irg_env *env;
1498 call_entry *entry, *tail;
1499 const call_entry *centry;
1500 struct obstack obst;
1501 DEBUG_ONLY(firm_dbg_module_t *dbg;)
1503 if (!(get_opt_optimize() && get_opt_inline())) return;
1505 FIRM_DBG_REGISTER(dbg, "firm.opt.inline");
1506 rem = current_ir_graph;
1507 obstack_init(&obst);
1509 /* extend all irgs by a temporary data structure for inlining. */
1510 n_irgs = get_irp_n_irgs();
1511 for (i = 0; i < n_irgs; ++i)
1512 set_irg_link(get_irp_irg(i), alloc_inline_irg_env(&obst));
1514 /* Precompute information in temporary data structure. */
1516 wenv.ignore_runtime = ignore_runtime;
1517 for (i = 0; i < n_irgs; ++i) {
1518 ir_graph *irg = get_irp_irg(i);
1520 assert(get_irg_phase_state(irg) != phase_building);
1521 free_callee_info(irg);
1523 wenv.x = get_irg_link(irg);
1524 irg_walk_graph(irg, NULL, collect_calls2, &wenv);
1527 /* -- and now inline. -- */
1529 /* Inline leaves recursively -- we might construct new leaves. */
1533 for (i = 0; i < n_irgs; ++i) {
1535 int phiproj_computed = 0;
1537 current_ir_graph = get_irp_irg(i);
1538 env = (inline_irg_env *)get_irg_link(current_ir_graph);
1541 for (entry = env->call_head; entry != NULL; entry = entry->next) {
1544 if (env->n_nodes > maxsize) break;
1547 callee = entry->callee;
1549 if (is_leave(callee) && is_smaller(callee, leavesize)) {
1550 if (!phiproj_computed) {
1551 phiproj_computed = 1;
1552 collect_phiprojs(current_ir_graph);
1554 did_inline = inline_method(call, callee);
1557 /* Do some statistics */
1558 inline_irg_env *callee_env = (inline_irg_env *)get_irg_link(callee);
1560 env->got_inline = 1;
1561 --env->n_call_nodes;
1562 env->n_nodes += callee_env->n_nodes;
1563 --callee_env->n_callers;
1565 /* remove this call from the list */
1567 tail->next = entry->next;
1569 env->call_head = entry->next;
1575 env->call_tail = tail;
1577 } while (did_inline);
1579 /* inline other small functions. */
1580 for (i = 0; i < n_irgs; ++i) {
1582 int phiproj_computed = 0;
1584 current_ir_graph = get_irp_irg(i);
1585 env = (inline_irg_env *)get_irg_link(current_ir_graph);
1587 /* note that the list of possible calls is updated during the process */
1589 for (entry = env->call_head; entry != NULL; entry = entry->next) {
1593 callee = entry->callee;
1595 if (((is_smaller(callee, size) && (env->n_nodes < maxsize)) || /* small function */
1596 (get_irg_inline_property(callee) >= irg_inline_forced))) {
1597 if (!phiproj_computed) {
1598 phiproj_computed = 1;
1599 collect_phiprojs(current_ir_graph);
1601 if (inline_method(call, callee)) {
1602 inline_irg_env *callee_env = (inline_irg_env *)get_irg_link(callee);
1604 /* callee was inline. Append it's call list. */
1605 env->got_inline = 1;
1606 --env->n_call_nodes;
1607 append_call_list(&obst, env, callee_env->call_head);
1608 env->n_call_nodes += callee_env->n_call_nodes;
1609 env->n_nodes += callee_env->n_nodes;
1610 --callee_env->n_callers;
1612 /* after we have inlined callee, all called methods inside callee
1613 are now called once more */
1614 for (centry = callee_env->call_head; centry != NULL; centry = centry->next) {
1615 inline_irg_env *penv = get_irg_link(centry->callee);
1619 /* remove this call from the list */
1621 tail->next = entry->next;
1623 env->call_head = entry->next;
1629 env->call_tail = tail;
1632 for (i = 0; i < n_irgs; ++i) {
1633 irg = get_irp_irg(i);
1634 env = (inline_irg_env *)get_irg_link(irg);
1636 if (env->got_inline) {
1637 /* this irg got calls inlined */
1638 set_irg_outs_inconsistent(irg);
1639 set_irg_doms_inconsistent(irg);
1641 optimize_graph_df(irg);
1644 if (env->got_inline || (env->n_callers_orig != env->n_callers))
1645 DB((dbg, SET_LEVEL_1, "Nodes:%3d ->%3d, calls:%3d ->%3d, callers:%3d ->%3d, -- %s\n",
1646 env->n_nodes_orig, env->n_nodes, env->n_call_nodes_orig, env->n_call_nodes,
1647 env->n_callers_orig, env->n_callers,
1648 get_entity_name(get_irg_entity(irg))));
1651 obstack_free(&obst, NULL);
1652 current_ir_graph = rem;
1655 /*******************************************************************/
1656 /* Code Placement. Pins all floating nodes to a block where they */
1657 /* will be executed only if needed. */
1658 /*******************************************************************/
1661 * Returns non-zero, is a block is not reachable from Start.
1663 * @param block the block to test
1666 is_Block_unreachable(ir_node *block) {
1667 return is_Block_dead(block) || get_Block_dom_depth(block) < 0;
1671 * Find the earliest correct block for N. --- Place N into the
1672 * same Block as its dominance-deepest Input.
1674 * We have to avoid calls to get_nodes_block() here
1675 * because the graph is floating.
1677 * move_out_of_loops() expects that place_floats_early() have placed
1678 * all "living" nodes into a living block. That's why we must
1679 * move nodes in dead block with "live" successors into a valid
1681 * We move them just into the same block as it's successor (or
1682 * in case of a Phi into the effective use block). For Phi successors,
1683 * this may still be a dead block, but then there is no real use, as
1684 * the control flow will be dead later.
1687 place_floats_early(ir_node *n, waitq *worklist)
1691 /* we must not run into an infinite loop */
1692 assert(irn_not_visited(n));
1693 mark_irn_visited(n);
1695 /* Place floating nodes. */
1696 if (get_irn_pinned(n) == op_pin_state_floats) {
1697 ir_node *curr_block = get_irn_n(n, -1);
1698 int in_dead_block = is_Block_unreachable(curr_block);
1700 ir_node *b = NULL; /* The block to place this node in */
1702 assert(is_no_Block(n));
1704 if (is_irn_start_block_placed(n)) {
1705 /* These nodes will not be placed by the loop below. */
1706 b = get_irg_start_block(current_ir_graph);
1710 /* find the block for this node. */
1711 irn_arity = get_irn_arity(n);
1712 for (i = 0; i < irn_arity; i++) {
1713 ir_node *pred = get_irn_n(n, i);
1714 ir_node *pred_block;
1716 if ((irn_not_visited(pred))
1717 && (get_irn_pinned(pred) == op_pin_state_floats)) {
1720 * If the current node is NOT in a dead block, but one of its
1721 * predecessors is, we must move the predecessor to a live block.
1722 * Such thing can happen, if global CSE chose a node from a dead block.
1723 * We move it simply to our block.
1724 * Note that neither Phi nor End nodes are floating, so we don't
1725 * need to handle them here.
1727 if (! in_dead_block) {
1728 if (get_irn_pinned(pred) == op_pin_state_floats &&
1729 is_Block_unreachable(get_irn_n(pred, -1)))
1730 set_nodes_block(pred, curr_block);
1732 place_floats_early(pred, worklist);
1736 * A node in the Bad block must stay in the bad block,
1737 * so don't compute a new block for it.
1742 /* Because all loops contain at least one op_pin_state_pinned node, now all
1743 our inputs are either op_pin_state_pinned or place_early() has already
1744 been finished on them. We do not have any unfinished inputs! */
1745 pred_block = get_irn_n(pred, -1);
1746 if ((!is_Block_dead(pred_block)) &&
1747 (get_Block_dom_depth(pred_block) > depth)) {
1749 depth = get_Block_dom_depth(pred_block);
1751 /* Avoid that the node is placed in the Start block */
1752 if ((depth == 1) && (get_Block_dom_depth(get_irn_n(n, -1)) > 1)) {
1753 b = get_Block_cfg_out(get_irg_start_block(current_ir_graph), 0);
1754 assert(b != get_irg_start_block(current_ir_graph));
1759 set_nodes_block(n, b);
1763 * Add predecessors of non floating nodes and non-floating predecessors
1764 * of floating nodes to worklist and fix their blocks if the are in dead block.
1766 irn_arity = get_irn_arity(n);
1768 if (get_irn_op(n) == op_End) {
1770 * Simplest case: End node. Predecessors are keep-alives,
1771 * no need to move out of dead block.
1773 for (i = -1; i < irn_arity; ++i) {
1774 ir_node *pred = get_irn_n(n, i);
1775 if (irn_not_visited(pred))
1776 waitq_put(worklist, pred);
1779 else if (is_Block(n)) {
1781 * Blocks: Predecessors are control flow, no need to move
1782 * them out of dead block.
1784 for (i = irn_arity - 1; i >= 0; --i) {
1785 ir_node *pred = get_irn_n(n, i);
1786 if (irn_not_visited(pred))
1787 waitq_put(worklist, pred);
1790 else if (is_Phi(n)) {
1792 ir_node *curr_block = get_irn_n(n, -1);
1793 int in_dead_block = is_Block_unreachable(curr_block);
1796 * Phi nodes: move nodes from dead blocks into the effective use
1797 * of the Phi-input if the Phi is not in a bad block.
1799 pred = get_irn_n(n, -1);
1800 if (irn_not_visited(pred))
1801 waitq_put(worklist, pred);
1803 for (i = irn_arity - 1; i >= 0; --i) {
1804 ir_node *pred = get_irn_n(n, i);
1806 if (irn_not_visited(pred)) {
1807 if (! in_dead_block &&
1808 get_irn_pinned(pred) == op_pin_state_floats &&
1809 is_Block_unreachable(get_irn_n(pred, -1))) {
1810 set_nodes_block(pred, get_Block_cfgpred_block(curr_block, i));
1812 waitq_put(worklist, pred);
1818 ir_node *curr_block = get_irn_n(n, -1);
1819 int in_dead_block = is_Block_unreachable(curr_block);
1822 * All other nodes: move nodes from dead blocks into the same block.
1824 pred = get_irn_n(n, -1);
1825 if (irn_not_visited(pred))
1826 waitq_put(worklist, pred);
1828 for (i = irn_arity - 1; i >= 0; --i) {
1829 ir_node *pred = get_irn_n(n, i);
1831 if (irn_not_visited(pred)) {
1832 if (! in_dead_block &&
1833 get_irn_pinned(pred) == op_pin_state_floats &&
1834 is_Block_unreachable(get_irn_n(pred, -1))) {
1835 set_nodes_block(pred, curr_block);
1837 waitq_put(worklist, pred);
1844 * Floating nodes form subgraphs that begin at nodes as Const, Load,
1845 * Start, Call and that end at op_pin_state_pinned nodes as Store, Call. Place_early
1846 * places all floating nodes reachable from its argument through floating
1847 * nodes and adds all beginnings at op_pin_state_pinned nodes to the worklist.
1849 static INLINE void place_early(waitq *worklist) {
1851 inc_irg_visited(current_ir_graph);
1853 /* this inits the worklist */
1854 place_floats_early(get_irg_end(current_ir_graph), worklist);
1856 /* Work the content of the worklist. */
1857 while (!waitq_empty(worklist)) {
1858 ir_node *n = waitq_get(worklist);
1859 if (irn_not_visited(n))
1860 place_floats_early(n, worklist);
1863 set_irg_outs_inconsistent(current_ir_graph);
1864 set_irg_pinned(current_ir_graph, op_pin_state_pinned);
1868 * Compute the deepest common ancestor of block and dca.
1870 static ir_node *calc_dca(ir_node *dca, ir_node *block)
1874 /* we do not want to place nodes in dead blocks */
1875 if (is_Block_dead(block))
1878 /* We found a first legal placement. */
1879 if (!dca) return block;
1881 /* Find a placement that is dominates both, dca and block. */
1882 while (get_Block_dom_depth(block) > get_Block_dom_depth(dca))
1883 block = get_Block_idom(block);
1885 while (get_Block_dom_depth(dca) > get_Block_dom_depth(block)) {
1886 dca = get_Block_idom(dca);
1889 while (block != dca)
1890 { block = get_Block_idom(block); dca = get_Block_idom(dca); }
1895 /** Deepest common dominance ancestor of DCA and CONSUMER of PRODUCER.
1896 * I.e., DCA is the block where we might place PRODUCER.
1897 * A data flow edge points from producer to consumer.
1900 consumer_dom_dca(ir_node *dca, ir_node *consumer, ir_node *producer)
1902 ir_node *block = NULL;
1904 /* Compute the latest block into which we can place a node so that it is
1906 if (get_irn_op(consumer) == op_Phi) {
1907 /* our consumer is a Phi-node, the effective use is in all those
1908 blocks through which the Phi-node reaches producer */
1910 ir_node *phi_block = get_nodes_block(consumer);
1911 irn_arity = get_irn_arity(consumer);
1913 for (i = 0; i < irn_arity; i++) {
1914 if (get_irn_n(consumer, i) == producer) {
1915 ir_node *new_block = get_nodes_block(get_Block_cfgpred(phi_block, i));
1917 if (! is_Block_unreachable(new_block))
1918 block = calc_dca(block, new_block);
1923 block = get_irn_n(producer, -1);
1926 assert(is_no_Block(consumer));
1927 block = get_nodes_block(consumer);
1930 /* Compute the deepest common ancestor of block and dca. */
1931 return calc_dca(dca, block);
1934 /* FIXME: the name clashes here with the function from ana/field_temperature.c
1936 static INLINE int get_irn_loop_depth(ir_node *n) {
1937 return get_loop_depth(get_irn_loop(n));
1941 * Move n to a block with less loop depth than it's current block. The
1942 * new block must be dominated by early.
1944 * @param n the node that should be moved
1945 * @param early the earliest block we can n move to
1947 static void move_out_of_loops(ir_node *n, ir_node *early)
1949 ir_node *best, *dca;
1953 /* Find the region deepest in the dominator tree dominating
1954 dca with the least loop nesting depth, but still dominated
1955 by our early placement. */
1956 dca = get_nodes_block(n);
1959 while (dca != early) {
1960 dca = get_Block_idom(dca);
1961 if (!dca || is_Bad(dca)) break; /* may be Bad if not reachable from Start */
1962 if (get_irn_loop_depth(dca) < get_irn_loop_depth(best)) {
1966 if (best != get_nodes_block(n)) {
1968 printf("Moving out of loop: "); DDMN(n);
1969 printf(" Outermost block: "); DDMN(early);
1970 printf(" Best block: "); DDMN(best);
1971 printf(" Innermost block: "); DDMN(get_nodes_block(n));
1973 set_nodes_block(n, best);
1978 * Find the latest legal block for N and place N into the
1979 * `optimal' Block between the latest and earliest legal block.
1980 * The `optimal' block is the dominance-deepest block of those
1981 * with the least loop-nesting-depth. This places N out of as many
1982 * loops as possible and then makes it as control dependent as
1985 static void place_floats_late(ir_node *n, pdeq *worklist)
1990 assert(irn_not_visited(n)); /* no multiple placement */
1992 mark_irn_visited(n);
1994 /* no need to place block nodes, control nodes are already placed. */
1995 if ((get_irn_op(n) != op_Block) &&
1997 (get_irn_mode(n) != mode_X)) {
1998 /* Remember the early_blk placement of this block to move it
1999 out of loop no further than the early_blk placement. */
2000 early_blk = get_irn_n(n, -1);
2003 * BEWARE: Here we also get code, that is live, but
2004 * was in a dead block. If the node is life, but because
2005 * of CSE in a dead block, we still might need it.
2008 /* Assure that our users are all placed, except the Phi-nodes.
2009 --- Each data flow cycle contains at least one Phi-node. We
2010 have to break the `user has to be placed before the
2011 producer' dependence cycle and the Phi-nodes are the
2012 place to do so, because we need to base our placement on the
2013 final region of our users, which is OK with Phi-nodes, as they
2014 are op_pin_state_pinned, and they never have to be placed after a
2015 producer of one of their inputs in the same block anyway. */
2016 for (i = get_irn_n_outs(n) - 1; i >= 0; --i) {
2017 ir_node *succ = get_irn_out(n, i);
2018 if (irn_not_visited(succ) && (get_irn_op(succ) != op_Phi))
2019 place_floats_late(succ, worklist);
2022 if (! is_Block_dead(early_blk)) {
2023 /* do only move things that where not dead */
2024 ir_op *op = get_irn_op(n);
2026 /* We have to determine the final block of this node... except for
2027 constants and Projs */
2028 if ((get_irn_pinned(n) == op_pin_state_floats) &&
2030 (op != op_SymConst) &&
2033 ir_node *dca = NULL; /* deepest common ancestor in the
2034 dominator tree of all nodes'
2035 blocks depending on us; our final
2036 placement has to dominate DCA. */
2037 for (i = get_irn_n_outs(n) - 1; i >= 0; --i) {
2038 ir_node *succ = get_irn_out(n, i);
2041 if (get_irn_op(succ) == op_End) {
2043 * This consumer is the End node, a keep alive edge.
2044 * This is not a real consumer, so we ignore it
2049 /* ignore if succ is in dead code */
2050 succ_blk = get_irn_n(succ, -1);
2051 if (is_Block_unreachable(succ_blk))
2053 dca = consumer_dom_dca(dca, succ, n);
2056 set_nodes_block(n, dca);
2057 move_out_of_loops(n, early_blk);
2063 /* Add predecessors of all non-floating nodes on list. (Those of floating
2064 nodes are placed already and therefore are marked.) */
2065 for (i = 0; i < get_irn_n_outs(n); i++) {
2066 ir_node *succ = get_irn_out(n, i);
2067 if (irn_not_visited(get_irn_out(n, i))) {
2068 pdeq_putr(worklist, succ);
2073 static INLINE void place_late(waitq *worklist) {
2075 inc_irg_visited(current_ir_graph);
2077 /* This fills the worklist initially. */
2078 place_floats_late(get_irg_start_block(current_ir_graph), worklist);
2080 /* And now empty the worklist again... */
2081 while (!waitq_empty(worklist)) {
2082 ir_node *n = waitq_get(worklist);
2083 if (irn_not_visited(n))
2084 place_floats_late(n, worklist);
2088 void place_code(ir_graph *irg) {
2090 ir_graph *rem = current_ir_graph;
2092 current_ir_graph = irg;
2094 if (!(get_opt_optimize() && get_opt_global_cse())) return;
2096 /* Handle graph state */
2097 assert(get_irg_phase_state(irg) != phase_building);
2100 if (1 || get_irg_loopinfo_state(irg) != loopinfo_consistent) {
2101 free_loop_information(irg);
2102 construct_backedges(irg);
2105 /* Place all floating nodes as early as possible. This guarantees
2106 a legal code placement. */
2107 worklist = new_waitq();
2108 place_early(worklist);
2110 /* place_early() invalidates the outs, place_late needs them. */
2111 compute_irg_outs(irg);
2113 /* Now move the nodes down in the dominator tree. This reduces the
2114 unnecessary executions of the node. */
2115 place_late(worklist);
2117 set_irg_outs_inconsistent(current_ir_graph);
2118 set_irg_loopinfo_inconsistent(current_ir_graph);
2119 del_waitq(worklist);
2120 current_ir_graph = rem;
2124 * Called by walker of remove_critical_cf_edges().
2126 * Place an empty block to an edge between a blocks of multiple
2127 * predecessors and a block of multiple successors.
2130 * @param env Environment of walker. The changed field.
2132 static void walk_critical_cf_edges(ir_node *n, void *env) {
2134 ir_node *pre, *block, *jmp;
2136 ir_graph *irg = get_irn_irg(n);
2138 /* Block has multiple predecessors */
2139 arity = get_irn_arity(n);
2141 if (n == get_irg_end_block(irg))
2142 return; /* No use to add a block here. */
2144 for (i = 0; i < arity; ++i) {
2147 pre = get_irn_n(n, i);
2148 cfop = get_irn_op(skip_Proj(pre));
2149 /* Predecessor has multiple successors. Insert new control flow edge but
2150 ignore exception edges. */
2151 if (! is_op_fragile(cfop) && is_op_forking(cfop)) {
2152 /* set predecessor of new block */
2153 block = new_r_Block(irg, 1, &pre);
2154 /* insert new jmp node to new block */
2155 jmp = new_r_Jmp(irg, block);
2156 /* set successor of new block */
2157 set_irn_n(n, i, jmp);
2159 } /* predecessor has multiple successors */
2160 } /* for all predecessors */
2161 } /* n is a multi-entry block */
2164 void remove_critical_cf_edges(ir_graph *irg) {
2167 irg_block_walk_graph(irg, NULL, walk_critical_cf_edges, &changed);
2169 /* control flow changed */
2170 set_irg_outs_inconsistent(irg);
2171 set_irg_extblk_inconsistent(irg);
2172 set_irg_doms_inconsistent(irg);
2173 set_irg_loopinfo_inconsistent(irg);