2 * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Optimizations for a whole ir graph, i.e., a procedure.
23 * @author Christian Schaefer, Goetz Lindenmaier, Sebastian Felis,
34 #include "irgraph_t.h"
47 #include "pdeq.h" /* Fuer code placement */
52 #include "irbackedge_t.h"
59 #include "iredges_t.h"
62 /*------------------------------------------------------------------*/
63 /* apply optimizations of iropt to all nodes. */
64 /*------------------------------------------------------------------*/
67 * A wrapper around optimize_inplace_2() to be called from a walker.
69 static void optimize_in_place_wrapper (ir_node *n, void *env) {
70 ir_node *optimized = optimize_in_place_2(n);
71 if (optimized != n) exchange (n, optimized);
75 * Do local optimizations for a node.
77 * @param n the IR-node where to start. Typically the End node
80 * @note current_ir_graph must be set
82 static INLINE void do_local_optimize(ir_node *n) {
83 /* Handle graph state */
84 assert(get_irg_phase_state(current_ir_graph) != phase_building);
86 if (get_opt_global_cse())
87 set_irg_pinned(current_ir_graph, op_pin_state_floats);
88 set_irg_outs_inconsistent(current_ir_graph);
89 set_irg_doms_inconsistent(current_ir_graph);
90 set_irg_loopinfo_inconsistent(current_ir_graph);
92 /* Clean the value_table in irg for the CSE. */
93 del_identities(current_ir_graph->value_table);
94 current_ir_graph->value_table = new_identities();
96 /* walk over the graph */
97 irg_walk(n, firm_clear_link, optimize_in_place_wrapper, NULL);
100 /* Applies local optimizations (see iropt.h) to all nodes reachable from node n */
101 void local_optimize_node(ir_node *n) {
102 ir_graph *rem = current_ir_graph;
103 current_ir_graph = get_irn_irg(n);
105 do_local_optimize(n);
107 current_ir_graph = rem;
111 * Block-Walker: uses dominance depth to mark dead blocks.
113 static void kill_dead_blocks(ir_node *block, void *env) {
114 if (get_Block_dom_depth(block) < 0) {
116 * Note that the new dominance code correctly handles
117 * the End block, i.e. it is always reachable from Start
119 set_Block_dead(block);
123 /* Applies local optimizations (see iropt.h) to all nodes reachable from node n. */
124 void local_optimize_graph(ir_graph *irg) {
125 ir_graph *rem = current_ir_graph;
126 current_ir_graph = irg;
128 if (get_irg_dom_state(irg) == dom_consistent)
129 irg_block_walk_graph(irg, NULL, kill_dead_blocks, NULL);
131 do_local_optimize(get_irg_end(irg));
133 current_ir_graph = rem;
137 * Enqueue all users of a node to a wait queue.
138 * Handles mode_T nodes.
140 static void enqueue_users(ir_node *n, pdeq *waitq) {
141 const ir_edge_t *edge;
143 foreach_out_edge(n, edge) {
144 ir_node *succ = get_edge_src_irn(edge);
146 if (get_irn_link(succ) != waitq) {
147 pdeq_putr(waitq, succ);
148 set_irn_link(succ, waitq);
150 if (get_irn_mode(succ) == mode_T) {
151 /* A mode_T node has Proj's. Because most optimizations
152 run on the Proj's we have to enqueue them also. */
153 enqueue_users(succ, waitq);
159 * Data flow optimization walker.
160 * Optimizes all nodes and enqueue it's users
163 static void opt_walker(ir_node *n, void *env) {
167 optimized = optimize_in_place_2(n);
168 set_irn_link(optimized, NULL);
170 if (optimized != n) {
171 enqueue_users(n, waitq);
172 exchange(n, optimized);
176 /* Applies local optimizations to all nodes in the graph until fixpoint. */
177 void optimize_graph_df(ir_graph *irg) {
178 pdeq *waitq = new_pdeq();
179 int state = edges_activated(irg);
180 ir_graph *rem = current_ir_graph;
182 current_ir_graph = irg;
187 if (get_opt_global_cse())
188 set_irg_pinned(current_ir_graph, op_pin_state_floats);
190 /* Clean the value_table in irg for the CSE. */
191 del_identities(irg->value_table);
192 irg->value_table = new_identities();
194 if (get_irg_dom_state(irg) == dom_consistent)
195 irg_block_walk_graph(irg, NULL, kill_dead_blocks, NULL);
197 /* invalidate info */
198 set_irg_outs_inconsistent(irg);
199 set_irg_doms_inconsistent(irg);
200 set_irg_loopinfo_inconsistent(irg);
202 set_using_irn_link(irg);
204 /* walk over the graph */
205 irg_walk_graph(irg, NULL, opt_walker, waitq);
207 /* finish the wait queue */
208 while (! pdeq_empty(waitq)) {
209 ir_node *n = pdeq_getl(waitq);
211 opt_walker(n, waitq);
216 clear_using_irn_link(irg);
219 edges_deactivate(irg);
221 current_ir_graph = rem;
225 /*------------------------------------------------------------------*/
226 /* Routines for dead node elimination / copying garbage collection */
227 /* of the obstack. */
228 /*------------------------------------------------------------------*/
231 * Remember the new node in the old node by using a field all nodes have.
233 #define set_new_node(oldn, newn) set_irn_link(oldn, newn)
236 * Get this new node, before the old node is forgotten.
238 #define get_new_node(oldn) get_irn_link(oldn)
241 * Check if a new node was set.
243 #define has_new_node(n) (get_new_node(n) != NULL)
246 * We use the block_visited flag to mark that we have computed the
247 * number of useful predecessors for this block.
248 * Further we encode the new arity in this flag in the old blocks.
249 * Remembering the arity is useful, as it saves a lot of pointer
250 * accesses. This function is called for all Phi and Block nodes
254 compute_new_arity(ir_node *b) {
255 int i, res, irn_arity;
258 irg_v = get_irg_block_visited(current_ir_graph);
259 block_v = get_Block_block_visited(b);
260 if (block_v >= irg_v) {
261 /* we computed the number of preds for this block and saved it in the
263 return block_v - irg_v;
265 /* compute the number of good predecessors */
266 res = irn_arity = get_irn_arity(b);
267 for (i = 0; i < irn_arity; i++)
268 if (get_irn_opcode(get_irn_n(b, i)) == iro_Bad) res--;
269 /* save it in the flag. */
270 set_Block_block_visited(b, irg_v + res);
276 * Copies the node to the new obstack. The Ins of the new node point to
277 * the predecessors on the old obstack. For block/phi nodes not all
278 * predecessors might be copied. n->link points to the new node.
279 * For Phi and Block nodes the function allocates in-arrays with an arity
280 * only for useful predecessors. The arity is determined by counting
281 * the non-bad predecessors of the block.
283 * @param n The node to be copied
284 * @param env if non-NULL, the node number attribute will be copied to the new node
286 * Note: Also used for loop unrolling.
288 static void copy_node(ir_node *n, void *env) {
291 ir_op *op = get_irn_op(n);
293 /* The end node looses it's flexible in array. This doesn't matter,
294 as dead node elimination builds End by hand, inlineing doesn't use
296 /* assert(op == op_End || ((_ARR_DESCR(n->in))->cookie != ARR_F_MAGIC)); */
299 /* node copied already */
301 } else if (op == op_Block) {
303 new_arity = compute_new_arity(n);
304 n->attr.block.graph_arr = NULL;
306 block = get_nodes_block(n);
308 new_arity = compute_new_arity(block);
310 new_arity = get_irn_arity(n);
313 nn = new_ir_node(get_irn_dbg_info(n),
320 /* Copy the attributes. These might point to additional data. If this
321 was allocated on the old obstack the pointers now are dangling. This
322 frees e.g. the memory of the graph_arr allocated in new_immBlock. */
323 copy_node_attr(n, nn);
327 int copy_node_nr = env != NULL;
329 /* for easier debugging, we want to copy the node numbers too */
330 nn->node_nr = n->node_nr;
336 hook_dead_node_elim_subst(current_ir_graph, n, nn);
340 * Copies new predecessors of old node to new node remembered in link.
341 * Spare the Bad predecessors of Phi and Block nodes.
344 copy_preds(ir_node *n, void *env) {
348 nn = get_new_node(n);
351 /* Don't copy Bad nodes. */
353 irn_arity = get_irn_arity(n);
354 for (i = 0; i < irn_arity; i++) {
355 if (! is_Bad(get_irn_n(n, i))) {
356 set_irn_n (nn, j, get_new_node(get_irn_n(n, i)));
357 /*if (is_backedge(n, i)) set_backedge(nn, j);*/
361 /* repair the block visited flag from above misuse. Repair it in both
362 graphs so that the old one can still be used. */
363 set_Block_block_visited(nn, 0);
364 set_Block_block_visited(n, 0);
365 /* Local optimization could not merge two subsequent blocks if
366 in array contained Bads. Now it's possible.
367 We don't call optimize_in_place as it requires
368 that the fields in ir_graph are set properly. */
369 if ((get_opt_control_flow_straightening()) &&
370 (get_Block_n_cfgpreds(nn) == 1) &&
371 (get_irn_op(get_Block_cfgpred(nn, 0)) == op_Jmp)) {
372 ir_node *old = get_nodes_block(get_Block_cfgpred(nn, 0));
374 /* Jmp jumps into the block it is in -- deal self cycle. */
375 assert(is_Bad(get_new_node(get_irg_bad(current_ir_graph))));
376 exchange(nn, get_new_node(get_irg_bad(current_ir_graph)));
381 } else if (get_irn_op(n) == op_Phi) {
382 /* Don't copy node if corresponding predecessor in block is Bad.
383 The Block itself should not be Bad. */
384 block = get_nodes_block(n);
385 set_irn_n(nn, -1, get_new_node(block));
387 irn_arity = get_irn_arity(n);
388 for (i = 0; i < irn_arity; i++) {
389 if (! is_Bad(get_irn_n(block, i))) {
390 set_irn_n(nn, j, get_new_node(get_irn_n(n, i)));
391 /*if (is_backedge(n, i)) set_backedge(nn, j);*/
395 /* If the pre walker reached this Phi after the post walker visited the
396 block block_visited is > 0. */
397 set_Block_block_visited(get_nodes_block(n), 0);
398 /* Compacting the Phi's ins might generate Phis with only one
400 if (get_irn_arity(nn) == 1)
401 exchange(nn, get_irn_n(nn, 0));
403 irn_arity = get_irn_arity(n);
404 for (i = -1; i < irn_arity; i++)
405 set_irn_n (nn, i, get_new_node(get_irn_n(n, i)));
407 /* Now the new node is complete. We can add it to the hash table for CSE.
408 @@@ inlining aborts if we identify End. Why? */
409 if (get_irn_op(nn) != op_End)
410 add_identities(current_ir_graph->value_table, nn);
414 * Copies the graph recursively, compacts the keep-alives of the end node.
416 * @param irg the graph to be copied
417 * @param copy_node_nr If non-zero, the node number will be copied
419 static void copy_graph(ir_graph *irg, int copy_node_nr) {
420 ir_node *oe, *ne, *ob, *nb, *om, *nm; /* old end, new end, old bad, new bad, old NoMem, new NoMem */
421 ir_node *ka; /* keep alive */
425 /* Some nodes must be copied by hand, sigh */
426 vfl = get_irg_visited(irg);
427 set_irg_visited(irg, vfl + 1);
429 oe = get_irg_end(irg);
430 mark_irn_visited(oe);
431 /* copy the end node by hand, allocate dynamic in array! */
432 ne = new_ir_node(get_irn_dbg_info(oe),
439 /* Copy the attributes. Well, there might be some in the future... */
440 copy_node_attr(oe, ne);
441 set_new_node(oe, ne);
443 /* copy the Bad node */
444 ob = get_irg_bad(irg);
445 mark_irn_visited(ob);
446 nb = new_ir_node(get_irn_dbg_info(ob),
453 copy_node_attr(ob, nb);
454 set_new_node(ob, nb);
456 /* copy the NoMem node */
457 om = get_irg_no_mem(irg);
458 mark_irn_visited(om);
459 nm = new_ir_node(get_irn_dbg_info(om),
466 copy_node_attr(om, nm);
467 set_new_node(om, nm);
469 /* copy the live nodes */
470 set_irg_visited(irg, vfl);
471 irg_walk(get_nodes_block(oe), copy_node, copy_preds, INT_TO_PTR(copy_node_nr));
473 /* Note: from yet, the visited flag of the graph is equal to vfl + 1 */
475 /* visit the anchors as well */
476 for (i = anchor_max - 1; i >= 0; --i) {
477 ir_node *n = irg->anchors[i];
479 if (n && (get_irn_visited(n) <= vfl)) {
480 set_irg_visited(irg, vfl);
481 irg_walk(n, copy_node, copy_preds, INT_TO_PTR(copy_node_nr));
485 /* copy_preds for the end node ... */
486 set_nodes_block(ne, get_new_node(get_nodes_block(oe)));
488 /*- ... and now the keep alives. -*/
489 /* First pick the not marked block nodes and walk them. We must pick these
490 first as else we will oversee blocks reachable from Phis. */
491 irn_arity = get_End_n_keepalives(oe);
492 for (i = 0; i < irn_arity; i++) {
493 ka = get_End_keepalive(oe, i);
495 if (get_irn_visited(ka) <= vfl) {
496 /* We must keep the block alive and copy everything reachable */
497 set_irg_visited(irg, vfl);
498 irg_walk(ka, copy_node, copy_preds, INT_TO_PTR(copy_node_nr));
500 add_End_keepalive(ne, get_new_node(ka));
504 /* Now pick other nodes. Here we will keep all! */
505 irn_arity = get_End_n_keepalives(oe);
506 for (i = 0; i < irn_arity; i++) {
507 ka = get_End_keepalive(oe, i);
509 if (get_irn_visited(ka) <= vfl) {
510 /* We didn't copy the node yet. */
511 set_irg_visited(irg, vfl);
512 irg_walk(ka, copy_node, copy_preds, INT_TO_PTR(copy_node_nr));
514 add_End_keepalive(ne, get_new_node(ka));
518 /* start block sometimes only reached after keep alives */
519 set_nodes_block(nb, get_new_node(get_nodes_block(ob)));
520 set_nodes_block(nm, get_new_node(get_nodes_block(om)));
524 * Copies the graph reachable from current_ir_graph->end to the obstack
525 * in current_ir_graph and fixes the environment.
526 * Then fixes the fields in current_ir_graph containing nodes of the
529 * @param copy_node_nr If non-zero, the node number will be copied
532 copy_graph_env(int copy_node_nr) {
533 ir_graph *irg = current_ir_graph;
534 ir_node *old_end, *n;
537 /* remove end_except and end_reg nodes */
538 old_end = get_irg_end(irg);
539 set_irg_end_except (irg, old_end);
540 set_irg_end_reg (irg, old_end);
542 /* Not all nodes remembered in irg might be reachable
543 from the end node. Assure their link is set to NULL, so that
544 we can test whether new nodes have been computed. */
545 for (i = anchor_max - 1; i >= 0; --i) {
547 set_new_node(irg->anchors[i], NULL);
549 /* we use the block walk flag for removing Bads from Blocks ins. */
550 inc_irg_block_visited(irg);
553 copy_graph(irg, copy_node_nr);
555 /* fix the fields in irg */
556 old_end = get_irg_end(irg);
557 for (i = anchor_max - 1; i >= 0; --i) {
560 irg->anchors[i] = get_new_node(n);
566 * Copies all reachable nodes to a new obstack. Removes bad inputs
567 * from block nodes and the corresponding inputs from Phi nodes.
568 * Merges single exit blocks with single entry blocks and removes
570 * Adds all new nodes to a new hash table for CSE. Does not
571 * perform CSE, so the hash table might contain common subexpressions.
574 dead_node_elimination(ir_graph *irg) {
575 if (get_opt_optimize() && get_opt_dead_node_elimination()) {
577 int rem_ipview = get_interprocedural_view();
578 struct obstack *graveyard_obst = NULL;
579 struct obstack *rebirth_obst = NULL;
580 assert(! edges_activated(irg) && "dead node elimination requires disabled edges");
582 /* inform statistics that we started a dead-node elimination run */
583 hook_dead_node_elim(irg, 1);
585 /* Remember external state of current_ir_graph. */
586 rem = current_ir_graph;
587 current_ir_graph = irg;
588 set_interprocedural_view(0);
590 assert(get_irg_phase_state(irg) != phase_building);
592 /* Handle graph state */
593 free_callee_info(irg);
597 /* @@@ so far we loose loops when copying */
598 free_loop_information(irg);
600 set_irg_doms_inconsistent(irg);
602 /* A quiet place, where the old obstack can rest in peace,
603 until it will be cremated. */
604 graveyard_obst = irg->obst;
606 /* A new obstack, where the reachable nodes will be copied to. */
607 rebirth_obst = xmalloc(sizeof(*rebirth_obst));
608 irg->obst = rebirth_obst;
609 obstack_init(irg->obst);
610 irg->last_node_idx = 0;
612 /* We also need a new value table for CSE */
613 del_identities(irg->value_table);
614 irg->value_table = new_identities();
616 /* Copy the graph from the old to the new obstack */
617 copy_graph_env(/*copy_node_nr=*/1);
619 /* Free memory from old unoptimized obstack */
620 obstack_free(graveyard_obst, 0); /* First empty the obstack ... */
621 xfree (graveyard_obst); /* ... then free it. */
623 /* inform statistics that the run is over */
624 hook_dead_node_elim(irg, 0);
626 current_ir_graph = rem;
627 set_interprocedural_view(rem_ipview);
632 * Relink bad predecessors of a block and store the old in array to the
633 * link field. This function is called by relink_bad_predecessors().
634 * The array of link field starts with the block operand at position 0.
635 * If block has bad predecessors, create a new in array without bad preds.
636 * Otherwise let in array untouched.
638 static void relink_bad_block_predecessors(ir_node *n, void *env) {
639 ir_node **new_in, *irn;
640 int i, new_irn_n, old_irn_arity, new_irn_arity = 0;
642 /* if link field of block is NULL, look for bad predecessors otherwise
643 this is already done */
644 if (get_irn_op(n) == op_Block &&
645 get_irn_link(n) == NULL) {
647 /* save old predecessors in link field (position 0 is the block operand)*/
648 set_irn_link(n, get_irn_in(n));
650 /* count predecessors without bad nodes */
651 old_irn_arity = get_irn_arity(n);
652 for (i = 0; i < old_irn_arity; i++)
653 if (!is_Bad(get_irn_n(n, i))) new_irn_arity++;
655 /* arity changing: set new predecessors without bad nodes */
656 if (new_irn_arity < old_irn_arity) {
657 /* Get new predecessor array. We do not resize the array, as we must
658 keep the old one to update Phis. */
659 new_in = NEW_ARR_D (ir_node *, current_ir_graph->obst, (new_irn_arity+1));
661 /* set new predecessors in array */
664 for (i = 0; i < old_irn_arity; i++) {
665 irn = get_irn_n(n, i);
667 new_in[new_irn_n] = irn;
668 is_backedge(n, i) ? set_backedge(n, new_irn_n-1) : set_not_backedge(n, new_irn_n-1);
672 /* ARR_SETLEN(int, n->attr.block.backedge, new_irn_arity); */
673 ARR_SHRINKLEN(n->attr.block.backedge, new_irn_arity);
675 } /* ir node has bad predecessors */
676 } /* Block is not relinked */
680 * Relinks Bad predecessors from Blocks and Phis called by walker
681 * remove_bad_predecesors(). If n is a Block, call
682 * relink_bad_block_redecessors(). If n is a Phi-node, call also the relinking
683 * function of Phi's Block. If this block has bad predecessors, relink preds
686 static void relink_bad_predecessors(ir_node *n, void *env) {
687 ir_node *block, **old_in;
688 int i, old_irn_arity, new_irn_arity;
690 /* relink bad predecessors of a block */
691 if (get_irn_op(n) == op_Block)
692 relink_bad_block_predecessors(n, env);
694 /* If Phi node relink its block and its predecessors */
695 if (get_irn_op(n) == op_Phi) {
697 /* Relink predecessors of phi's block */
698 block = get_nodes_block(n);
699 if (get_irn_link(block) == NULL)
700 relink_bad_block_predecessors(block, env);
702 old_in = (ir_node **)get_irn_link(block); /* Of Phi's Block */
703 old_irn_arity = ARR_LEN(old_in);
705 /* Relink Phi predecessors if count of predecessors changed */
706 if (old_irn_arity != ARR_LEN(get_irn_in(block))) {
707 /* set new predecessors in array
708 n->in[0] remains the same block */
710 for(i = 1; i < old_irn_arity; i++)
711 if (!is_Bad((ir_node *)old_in[i])) {
712 n->in[new_irn_arity] = n->in[i];
713 is_backedge(n, i) ? set_backedge(n, new_irn_arity) : set_not_backedge(n, new_irn_arity);
717 ARR_SETLEN(ir_node *, n->in, new_irn_arity);
718 ARR_SETLEN(int, n->attr.phi_backedge, new_irn_arity);
720 } /* n is a Phi node */
724 * Removes Bad Bad predecessors from Blocks and the corresponding
725 * inputs to Phi nodes as in dead_node_elimination but without
727 * On walking up set the link field to NULL, on walking down call
728 * relink_bad_predecessors() (This function stores the old in array
729 * to the link field and sets a new in array if arity of predecessors
732 void remove_bad_predecessors(ir_graph *irg) {
733 irg_walk_graph(irg, firm_clear_link, relink_bad_predecessors, NULL);
740 __)|_| | \_/ | \_/(/_ |_/\__|__
742 The following stuff implements a facility that automatically patches
743 registered ir_node pointers to the new node when a dead node elimination occurs.
746 struct _survive_dce_t {
750 hook_entry_t dead_node_elim;
751 hook_entry_t dead_node_elim_subst;
754 typedef struct _survive_dce_list_t {
755 struct _survive_dce_list_t *next;
757 } survive_dce_list_t;
759 static void dead_node_hook(void *context, ir_graph *irg, int start) {
760 survive_dce_t *sd = context;
762 /* Create a new map before the dead node elimination is performed. */
764 sd->new_places = pmap_create_ex(pmap_count(sd->places));
766 /* Patch back all nodes if dead node elimination is over and something is to be done. */
767 pmap_destroy(sd->places);
768 sd->places = sd->new_places;
769 sd->new_places = NULL;
774 * Hook called when dead node elimination replaces old by nw.
776 static void dead_node_subst_hook(void *context, ir_graph *irg, ir_node *old, ir_node *nw) {
777 survive_dce_t *sd = context;
778 survive_dce_list_t *list = pmap_get(sd->places, old);
780 /* If the node is to be patched back, write the new address to all registered locations. */
782 survive_dce_list_t *p;
784 for (p = list; p; p = p->next)
787 pmap_insert(sd->new_places, nw, list);
792 * Make a new Survive DCE environment.
794 survive_dce_t *new_survive_dce(void) {
795 survive_dce_t *res = xmalloc(sizeof(res[0]));
796 obstack_init(&res->obst);
797 res->places = pmap_create();
798 res->new_places = NULL;
800 res->dead_node_elim.hook._hook_dead_node_elim = dead_node_hook;
801 res->dead_node_elim.context = res;
802 res->dead_node_elim.next = NULL;
804 res->dead_node_elim_subst.hook._hook_dead_node_elim_subst = dead_node_subst_hook;
805 res->dead_node_elim_subst.context = res;
806 res->dead_node_elim_subst.next = NULL;
808 #ifndef FIRM_ENABLE_HOOKS
809 assert(0 && "need hooks enabled");
812 register_hook(hook_dead_node_elim, &res->dead_node_elim);
813 register_hook(hook_dead_node_elim_subst, &res->dead_node_elim_subst);
818 * Free a Survive DCE environment.
820 void free_survive_dce(survive_dce_t *sd) {
821 obstack_free(&sd->obst, NULL);
822 pmap_destroy(sd->places);
823 unregister_hook(hook_dead_node_elim, &sd->dead_node_elim);
824 unregister_hook(hook_dead_node_elim_subst, &sd->dead_node_elim_subst);
829 * Register a node pointer to be patched upon DCE.
830 * When DCE occurs, the node pointer specified by @p place will be
831 * patched to the new address of the node it is pointing to.
833 * @param sd The Survive DCE environment.
834 * @param place The address of the node pointer.
836 void survive_dce_register_irn(survive_dce_t *sd, ir_node **place) {
837 if (*place != NULL) {
838 ir_node *irn = *place;
839 survive_dce_list_t *curr = pmap_get(sd->places, irn);
840 survive_dce_list_t *nw = obstack_alloc(&sd->obst, sizeof(nw[0]));
845 pmap_insert(sd->places, irn, nw);
849 /*--------------------------------------------------------------------*/
850 /* Functionality for inlining */
851 /*--------------------------------------------------------------------*/
854 * Copy node for inlineing. Updates attributes that change when
855 * inlineing but not for dead node elimination.
857 * Copies the node by calling copy_node() and then updates the entity if
858 * it's a local one. env must be a pointer of the frame type of the
859 * inlined procedure. The new entities must be in the link field of
863 copy_node_inline(ir_node *n, void *env) {
865 ir_type *frame_tp = (ir_type *)env;
868 if (get_irn_op(n) == op_Sel) {
869 nn = get_new_node (n);
871 if (get_entity_owner(get_Sel_entity(n)) == frame_tp) {
872 set_Sel_entity(nn, get_entity_link(get_Sel_entity(n)));
874 } else if (get_irn_op(n) == op_Block) {
875 nn = get_new_node (n);
876 nn->attr.block.irg = current_ir_graph;
881 * Walker: checks if P_value_arg_base is used.
883 static void find_addr(ir_node *node, void *env) {
884 int *allow_inline = env;
885 if (is_Proj(node) && get_irn_op(get_Proj_pred(node)) == op_Start) {
886 if (get_Proj_proj(node) == pn_Start_P_value_arg_base)
892 * Check if we can inline a given call.
893 * Currently, we cannot inline two cases:
894 * - call with compound arguments
895 * - graphs that take the address of a parameter
897 * check these conditions here
899 static int can_inline(ir_node *call, ir_graph *called_graph) {
900 ir_type *call_type = get_Call_type(call);
901 int params, ress, i, res;
902 assert(is_Method_type(call_type));
904 params = get_method_n_params(call_type);
905 ress = get_method_n_ress(call_type);
907 /* check parameters for compound arguments */
908 for (i = 0; i < params; ++i) {
909 ir_type *p_type = get_method_param_type(call_type, i);
911 if (is_compound_type(p_type))
915 /* check results for compound arguments */
916 for (i = 0; i < ress; ++i) {
917 ir_type *r_type = get_method_res_type(call_type, i);
919 if (is_compound_type(r_type))
924 irg_walk_graph(called_graph, find_addr, NULL, &res);
929 /* Inlines a method at the given call site. */
930 int inline_method(ir_node *call, ir_graph *called_graph) {
932 ir_node *post_call, *post_bl;
933 ir_node *in[pn_Start_max];
934 ir_node *end, *end_bl;
938 int arity, n_ret, n_exc, n_res, i, j, rem_opt, irn_arity;
940 ir_type *called_frame;
941 irg_inline_property prop = get_irg_inline_property(called_graph);
943 if ( (prop < irg_inline_forced) &&
944 (!get_opt_optimize() || !get_opt_inline() || (prop == irg_inline_forbidden))) return 0;
946 /* Do not inline variadic functions. */
947 if (get_method_variadicity(get_entity_type(get_irg_entity(called_graph))) == variadicity_variadic)
950 assert(get_method_n_params(get_entity_type(get_irg_entity(called_graph))) ==
951 get_method_n_params(get_Call_type(call)));
954 * currently, we cannot inline two cases:
955 * - call with compound arguments
956 * - graphs that take the address of a parameter
958 if (! can_inline(call, called_graph))
961 /* -- Turn off optimizations, this can cause problems when allocating new nodes. -- */
962 rem_opt = get_opt_optimize();
965 /* Handle graph state */
966 assert(get_irg_phase_state(current_ir_graph) != phase_building);
967 assert(get_irg_pinned(current_ir_graph) == op_pin_state_pinned);
968 assert(get_irg_pinned(called_graph) == op_pin_state_pinned);
969 set_irg_outs_inconsistent(current_ir_graph);
970 set_irg_extblk_inconsistent(current_ir_graph);
971 set_irg_doms_inconsistent(current_ir_graph);
972 set_irg_loopinfo_inconsistent(current_ir_graph);
973 set_irg_callee_info_state(current_ir_graph, irg_callee_info_inconsistent);
975 /* -- Check preconditions -- */
976 assert(is_Call(call));
977 /* @@@ does not work for InterfaceIII.java after cgana
978 assert(get_Call_type(call) == get_entity_type(get_irg_entity(called_graph)));
979 assert(smaller_type(get_entity_type(get_irg_entity(called_graph)),
980 get_Call_type(call)));
982 if (called_graph == current_ir_graph) {
983 set_optimize(rem_opt);
987 /* here we know we WILL inline, so inform the statistics */
988 hook_inline(call, called_graph);
990 /* -- Decide how to handle exception control flow: Is there a handler
991 for the Call node, or do we branch directly to End on an exception?
993 0 There is a handler.
995 2 Exception handling not represented in Firm. -- */
997 ir_node *proj, *Mproj = NULL, *Xproj = NULL;
998 for (proj = get_irn_link(call); proj; proj = get_irn_link(proj)) {
999 assert(is_Proj(proj));
1000 if (get_Proj_proj(proj) == pn_Call_X_except) Xproj = proj;
1001 if (get_Proj_proj(proj) == pn_Call_M_except) Mproj = proj;
1003 if (Mproj) { assert(Xproj); exc_handling = 0; } /* Mproj */
1004 else if (Xproj) { exc_handling = 1; } /* !Mproj && Xproj */
1005 else { exc_handling = 2; } /* !Mproj && !Xproj */
1009 the procedure and later replaces the Start node of the called graph.
1010 Post_call is the old Call node and collects the results of the called
1011 graph. Both will end up being a tuple. -- */
1012 post_bl = get_nodes_block(call);
1013 set_irg_current_block(current_ir_graph, post_bl);
1014 /* XxMxPxPxPxT of Start + parameter of Call */
1015 in[pn_Start_X_initial_exec] = new_Jmp();
1016 in[pn_Start_M] = get_Call_mem(call);
1017 in[pn_Start_P_frame_base] = get_irg_frame(current_ir_graph);
1018 in[pn_Start_P_globals] = get_irg_globals(current_ir_graph);
1019 in[pn_Start_P_tls] = get_irg_tls(current_ir_graph);
1020 in[pn_Start_T_args] = new_Tuple(get_Call_n_params(call), get_Call_param_arr(call));
1021 /* in[pn_Start_P_value_arg_base] = ??? */
1022 assert(pn_Start_P_value_arg_base == pn_Start_max - 1 && "pn_Start_P_value_arg_base not supported, fix");
1023 pre_call = new_Tuple(pn_Start_max - 1, in);
1027 The new block gets the ins of the old block, pre_call and all its
1028 predecessors and all Phi nodes. -- */
1029 part_block(pre_call);
1031 /* -- Prepare state for dead node elimination -- */
1032 /* Visited flags in calling irg must be >= flag in called irg.
1033 Else walker and arity computation will not work. */
1034 if (get_irg_visited(current_ir_graph) <= get_irg_visited(called_graph))
1035 set_irg_visited(current_ir_graph, get_irg_visited(called_graph)+1);
1036 if (get_irg_block_visited(current_ir_graph)< get_irg_block_visited(called_graph))
1037 set_irg_block_visited(current_ir_graph, get_irg_block_visited(called_graph));
1038 /* Set pre_call as new Start node in link field of the start node of
1039 calling graph and pre_calls block as new block for the start block
1041 Further mark these nodes so that they are not visited by the
1043 set_irn_link(get_irg_start(called_graph), pre_call);
1044 set_irn_visited(get_irg_start(called_graph), get_irg_visited(current_ir_graph));
1045 set_irn_link(get_irg_start_block(called_graph), get_nodes_block(pre_call));
1046 set_irn_visited(get_irg_start_block(called_graph), get_irg_visited(current_ir_graph));
1047 set_irn_link(get_irg_bad(called_graph), get_irg_bad(current_ir_graph));
1048 set_irn_visited(get_irg_bad(called_graph), get_irg_visited(current_ir_graph));
1050 /* Initialize for compaction of in arrays */
1051 inc_irg_block_visited(current_ir_graph);
1053 /* -- Replicate local entities of the called_graph -- */
1054 /* copy the entities. */
1055 called_frame = get_irg_frame_type(called_graph);
1056 for (i = 0; i < get_class_n_members(called_frame); i++) {
1057 ir_entity *new_ent, *old_ent;
1058 old_ent = get_class_member(called_frame, i);
1059 new_ent = copy_entity_own(old_ent, get_cur_frame_type());
1060 set_entity_link(old_ent, new_ent);
1063 /* visited is > than that of called graph. With this trick visited will
1064 remain unchanged so that an outer walker, e.g., searching the call nodes
1065 to inline, calling this inline will not visit the inlined nodes. */
1066 set_irg_visited(current_ir_graph, get_irg_visited(current_ir_graph)-1);
1068 /* -- Performing dead node elimination inlines the graph -- */
1069 /* Copies the nodes to the obstack of current_ir_graph. Updates links to new
1071 /* @@@ endless loops are not copied!! -- they should be, I think... */
1072 irg_walk(get_irg_end(called_graph), copy_node_inline, copy_preds,
1073 get_irg_frame_type(called_graph));
1075 /* Repair called_graph */
1076 set_irg_visited(called_graph, get_irg_visited(current_ir_graph));
1077 set_irg_block_visited(called_graph, get_irg_block_visited(current_ir_graph));
1078 set_Block_block_visited(get_irg_start_block(called_graph), 0);
1080 /* -- Merge the end of the inlined procedure with the call site -- */
1081 /* We will turn the old Call node into a Tuple with the following
1084 0: Phi of all Memories of Return statements.
1085 1: Jmp from new Block that merges the control flow from all exception
1086 predecessors of the old end block.
1087 2: Tuple of all arguments.
1088 3: Phi of Exception memories.
1089 In case the old Call directly branches to End on an exception we don't
1090 need the block merging all exceptions nor the Phi of the exception
1094 /* -- Precompute some values -- */
1095 end_bl = get_new_node(get_irg_end_block(called_graph));
1096 end = get_new_node(get_irg_end(called_graph));
1097 arity = get_irn_arity(end_bl); /* arity = n_exc + n_ret */
1098 n_res = get_method_n_ress(get_Call_type(call));
1100 res_pred = xmalloc (n_res * sizeof(*res_pred));
1101 cf_pred = xmalloc (arity * sizeof(*res_pred));
1103 set_irg_current_block(current_ir_graph, post_bl); /* just to make sure */
1105 /* -- archive keepalives -- */
1106 irn_arity = get_irn_arity(end);
1107 for (i = 0; i < irn_arity; i++)
1108 add_End_keepalive(get_irg_end(current_ir_graph), get_irn_n(end, i));
1110 /* The new end node will die. We need not free as the in array is on the obstack:
1111 copy_node() only generated 'D' arrays. */
1113 /* -- Replace Return nodes by Jump nodes. -- */
1115 for (i = 0; i < arity; i++) {
1117 ret = get_irn_n(end_bl, i);
1118 if (is_Return(ret)) {
1119 cf_pred[n_ret] = new_r_Jmp(current_ir_graph, get_nodes_block(ret));
1123 set_irn_in(post_bl, n_ret, cf_pred);
1125 /* -- Build a Tuple for all results of the method.
1126 Add Phi node if there was more than one Return. -- */
1127 turn_into_tuple(post_call, 4);
1128 /* First the Memory-Phi */
1130 for (i = 0; i < arity; i++) {
1131 ret = get_irn_n(end_bl, i);
1132 if (is_Return(ret)) {
1133 cf_pred[n_ret] = get_Return_mem(ret);
1137 phi = new_Phi(n_ret, cf_pred, mode_M);
1138 set_Tuple_pred(call, pn_Call_M_regular, phi);
1139 /* Conserve Phi-list for further inlinings -- but might be optimized */
1140 if (get_nodes_block(phi) == post_bl) {
1141 set_irn_link(phi, get_irn_link(post_bl));
1142 set_irn_link(post_bl, phi);
1144 /* Now the real results */
1146 for (j = 0; j < n_res; j++) {
1148 for (i = 0; i < arity; i++) {
1149 ret = get_irn_n(end_bl, i);
1150 if (get_irn_op(ret) == op_Return) {
1151 cf_pred[n_ret] = get_Return_res(ret, j);
1156 phi = new_Phi(n_ret, cf_pred, get_irn_mode(cf_pred[0]));
1160 /* Conserve Phi-list for further inlinings -- but might be optimized */
1161 if (get_nodes_block(phi) == post_bl) {
1162 set_irn_link(phi, get_irn_link(post_bl));
1163 set_irn_link(post_bl, phi);
1166 set_Tuple_pred(call, pn_Call_T_result, new_Tuple(n_res, res_pred));
1168 set_Tuple_pred(call, pn_Call_T_result, new_Bad());
1170 /* Finally the exception control flow.
1171 We have two (three) possible situations:
1172 First if the Call branches to an exception handler: We need to add a Phi node to
1173 collect the memory containing the exception objects. Further we need
1174 to add another block to get a correct representation of this Phi. To
1175 this block we add a Jmp that resolves into the X output of the Call
1176 when the Call is turned into a tuple.
1177 Second the Call branches to End, the exception is not handled. Just
1178 add all inlined exception branches to the End node.
1179 Third: there is no Exception edge at all. Handle as case two. */
1180 if (exc_handling == 0) {
1182 for (i = 0; i < arity; i++) {
1184 ret = get_irn_n(end_bl, i);
1185 if (is_fragile_op(skip_Proj(ret)) || (get_irn_op(skip_Proj(ret)) == op_Raise)) {
1186 cf_pred[n_exc] = ret;
1191 new_Block(n_exc, cf_pred); /* watch it: current_block is changed! */
1192 set_Tuple_pred(call, pn_Call_X_except, new_Jmp());
1193 /* The Phi for the memories with the exception objects */
1195 for (i = 0; i < arity; i++) {
1197 ret = skip_Proj(get_irn_n(end_bl, i));
1199 cf_pred[n_exc] = new_r_Proj(current_ir_graph, get_nodes_block(ret), ret, mode_M, 3);
1201 } else if (is_fragile_op(ret)) {
1202 /* We rely that all cfops have the memory output at the same position. */
1203 cf_pred[n_exc] = new_r_Proj(current_ir_graph, get_nodes_block(ret), ret, mode_M, 0);
1205 } else if (get_irn_op(ret) == op_Raise) {
1206 cf_pred[n_exc] = new_r_Proj(current_ir_graph, get_nodes_block(ret), ret, mode_M, 1);
1210 set_Tuple_pred(call, pn_Call_M_except, new_Phi(n_exc, cf_pred, mode_M));
1212 set_Tuple_pred(call, pn_Call_X_except, new_Bad());
1213 set_Tuple_pred(call, pn_Call_M_except, new_Bad());
1216 ir_node *main_end_bl;
1217 int main_end_bl_arity;
1218 ir_node **end_preds;
1220 /* assert(exc_handling == 1 || no exceptions. ) */
1222 for (i = 0; i < arity; i++) {
1223 ir_node *ret = get_irn_n(end_bl, i);
1225 if (is_fragile_op(skip_Proj(ret)) || (get_irn_op(skip_Proj(ret)) == op_Raise)) {
1226 cf_pred[n_exc] = ret;
1230 main_end_bl = get_irg_end_block(current_ir_graph);
1231 main_end_bl_arity = get_irn_arity(main_end_bl);
1232 end_preds = xmalloc ((n_exc + main_end_bl_arity) * sizeof(*end_preds));
1234 for (i = 0; i < main_end_bl_arity; ++i)
1235 end_preds[i] = get_irn_n(main_end_bl, i);
1236 for (i = 0; i < n_exc; ++i)
1237 end_preds[main_end_bl_arity + i] = cf_pred[i];
1238 set_irn_in(main_end_bl, n_exc + main_end_bl_arity, end_preds);
1239 set_Tuple_pred(call, pn_Call_X_except, new_Bad());
1240 set_Tuple_pred(call, pn_Call_M_except, new_Bad());
1246 /* -- Turn CSE back on. -- */
1247 set_optimize(rem_opt);
1252 /********************************************************************/
1253 /* Apply inlineing to small methods. */
1254 /********************************************************************/
1256 /** Represents a possible inlinable call in a graph. */
1257 typedef struct _call_entry call_entry;
1258 struct _call_entry {
1259 ir_node *call; /**< the Call */
1260 ir_graph *callee; /**< the callee called here */
1261 call_entry *next; /**< for linking the next one */
1265 * environment for inlining small irgs
1267 typedef struct _inline_env_t {
1268 struct obstack obst; /**< an obstack where call_entries are allocated on. */
1269 call_entry *head; /**< the head of the call entry list */
1270 call_entry *tail; /**< the tail of the call entry list */
1274 * Returns the irg called from a Call node. If the irg is not
1275 * known, NULL is returned.
1277 static ir_graph *get_call_called_irg(ir_node *call) {
1279 ir_graph *called_irg = NULL;
1281 addr = get_Call_ptr(call);
1282 if (is_SymConst(addr) && get_SymConst_kind(addr) == symconst_addr_ent) {
1283 called_irg = get_entity_irg(get_SymConst_entity(addr));
1290 * Walker: Collect all calls to known graphs inside a graph.
1292 static void collect_calls(ir_node *call, void *env) {
1293 if (is_Call(call)) {
1294 ir_graph *called_irg = get_call_called_irg(call);
1296 /* The Call node calls a locally defined method. Remember to inline. */
1297 inline_env_t *ienv = env;
1298 call_entry *entry = obstack_alloc(&ienv->obst, sizeof(*entry));
1300 entry->callee = called_irg;
1303 if (ienv->tail == NULL)
1306 ienv->tail->next = entry;
1313 * Inlines all small methods at call sites where the called address comes
1314 * from a Const node that references the entity representing the called
1316 * The size argument is a rough measure for the code size of the method:
1317 * Methods where the obstack containing the firm graph is smaller than
1320 void inline_small_irgs(ir_graph *irg, int size) {
1321 ir_graph *rem = current_ir_graph;
1324 DEBUG_ONLY(firm_dbg_module_t *dbg;)
1326 if (!(get_opt_optimize() && get_opt_inline())) return;
1328 FIRM_DBG_REGISTER(dbg, "firm.opt.inline");
1330 current_ir_graph = irg;
1331 /* Handle graph state */
1332 assert(get_irg_phase_state(irg) != phase_building);
1333 free_callee_info(irg);
1335 /* Find Call nodes to inline.
1336 (We can not inline during a walk of the graph, as inlineing the same
1337 method several times changes the visited flag of the walked graph:
1338 after the first inlineing visited of the callee equals visited of
1339 the caller. With the next inlineing both are increased.) */
1340 obstack_init(&env.obst);
1341 env.head = env.tail = NULL;
1342 irg_walk_graph(irg, NULL, collect_calls, &env);
1344 if (env.head != NULL) {
1345 /* There are calls to inline */
1346 collect_phiprojs(irg);
1347 for (entry = env.head; entry != NULL; entry = entry->next) {
1348 ir_graph *callee = entry->callee;
1349 if (((_obstack_memory_used(callee->obst) - (int)obstack_room(callee->obst)) < size) ||
1350 (get_irg_inline_property(callee) >= irg_inline_forced)) {
1351 inline_method(entry->call, callee);
1355 obstack_free(&env.obst, NULL);
1356 current_ir_graph = rem;
1360 * Environment for inlining irgs.
1363 int n_nodes; /**< Number of nodes in graph except Id, Tuple, Proj, Start, End. */
1364 int n_nodes_orig; /**< for statistics */
1365 call_entry *call_head; /**< The head of the list of all call nodes in this graph. */
1366 call_entry *call_tail; /**< The tail of the list of all call nodes in this graph .*/
1367 int n_call_nodes; /**< Number of Call nodes in the graph. */
1368 int n_call_nodes_orig; /**< for statistics */
1369 int n_callers; /**< Number of known graphs that call this graphs. */
1370 int n_callers_orig; /**< for statistics */
1371 int got_inline; /**< Set, if at leat one call inside this graph was inlined. */
1375 * Allocate a new environment for inlining.
1377 static inline_irg_env *alloc_inline_irg_env(struct obstack *obst) {
1378 inline_irg_env *env = obstack_alloc(obst, sizeof(*env));
1379 env->n_nodes = -2; /* do not count count Start, End */
1380 env->n_nodes_orig = -2; /* do not count Start, End */
1381 env->call_head = NULL;
1382 env->call_tail = NULL;
1383 env->n_call_nodes = 0;
1384 env->n_call_nodes_orig = 0;
1386 env->n_callers_orig = 0;
1387 env->got_inline = 0;
1391 typedef struct walker_env {
1392 struct obstack *obst; /**< the obstack for allocations. */
1393 inline_irg_env *x; /**< the inline environment */
1394 int ignore_runtime; /**< the ignore runtime flag */
1398 * post-walker: collect all calls in the inline-environment
1399 * of a graph and sum some statistics.
1401 static void collect_calls2(ir_node *call, void *ctx) {
1403 inline_irg_env *x = env->x;
1404 ir_op *op = get_irn_op(call);
1408 /* count meaningful nodes in irg */
1409 if (op != op_Proj && op != op_Tuple && op != op_Sync) {
1414 if (op != op_Call) return;
1416 /* check, if it's a runtime call */
1417 if (env->ignore_runtime) {
1418 ir_node *symc = get_Call_ptr(call);
1420 if (is_SymConst(symc) && get_SymConst_kind(symc) == symconst_addr_ent) {
1421 ir_entity *ent = get_SymConst_entity(symc);
1423 if (get_entity_additional_properties(ent) & mtp_property_runtime)
1428 /* collect all call nodes */
1430 ++x->n_call_nodes_orig;
1432 callee = get_call_called_irg(call);
1434 inline_irg_env *callee_env = get_irg_link(callee);
1435 /* count all static callers */
1436 ++callee_env->n_callers;
1437 ++callee_env->n_callers_orig;
1439 /* link it in the list of possible inlinable entries */
1440 entry = obstack_alloc(env->obst, sizeof(*entry));
1442 entry->callee = callee;
1444 if (x->call_tail == NULL)
1445 x->call_head = entry;
1447 x->call_tail->next = entry;
1448 x->call_tail = entry;
1453 * Returns TRUE if the number of callers in 0 in the irg's environment,
1454 * hence this irg is a leave.
1456 INLINE static int is_leave(ir_graph *irg) {
1457 inline_irg_env *env = get_irg_link(irg);
1458 return env->n_call_nodes == 0;
1462 * Returns TRUE if the number of callers is smaller size in the irg's environment.
1464 INLINE static int is_smaller(ir_graph *callee, int size) {
1465 inline_irg_env *env = get_irg_link(callee);
1466 return env->n_nodes < size;
1470 * Append the nodes of the list src to the nodes of the list in environment dst.
1472 static void append_call_list(struct obstack *obst, inline_irg_env *dst, call_entry *src) {
1473 call_entry *entry, *nentry;
1475 /* Note that the src list points to Call nodes in the inlined graph, but
1476 we need Call nodes in our graph. Luckily the inliner leaves this information
1477 in the link field. */
1478 for (entry = src; entry != NULL; entry = entry->next) {
1479 nentry = obstack_alloc(obst, sizeof(*nentry));
1480 nentry->call = get_irn_link(entry->call);
1481 nentry->callee = entry->callee;
1482 nentry->next = NULL;
1483 dst->call_tail->next = nentry;
1484 dst->call_tail = nentry;
1489 * Inlines small leave methods at call sites where the called address comes
1490 * from a Const node that references the entity representing the called
1492 * The size argument is a rough measure for the code size of the method:
1493 * Methods where the obstack containing the firm graph is smaller than
1496 void inline_leave_functions(int maxsize, int leavesize, int size, int ignore_runtime) {
1497 inline_irg_env *env;
1503 call_entry *entry, *tail;
1504 const call_entry *centry;
1505 struct obstack obst;
1506 DEBUG_ONLY(firm_dbg_module_t *dbg;)
1508 if (!(get_opt_optimize() && get_opt_inline())) return;
1510 FIRM_DBG_REGISTER(dbg, "firm.opt.inline");
1511 rem = current_ir_graph;
1512 obstack_init(&obst);
1514 /* extend all irgs by a temporary data structure for inlining. */
1515 n_irgs = get_irp_n_irgs();
1516 for (i = 0; i < n_irgs; ++i)
1517 set_irg_link(get_irp_irg(i), alloc_inline_irg_env(&obst));
1519 /* Precompute information in temporary data structure. */
1521 wenv.ignore_runtime = ignore_runtime;
1522 for (i = 0; i < n_irgs; ++i) {
1523 ir_graph *irg = get_irp_irg(i);
1525 assert(get_irg_phase_state(irg) != phase_building);
1526 free_callee_info(irg);
1528 wenv.x = get_irg_link(irg);
1529 irg_walk_graph(irg, NULL, collect_calls2, &wenv);
1532 /* -- and now inline. -- */
1534 /* Inline leaves recursively -- we might construct new leaves. */
1538 for (i = 0; i < n_irgs; ++i) {
1540 int phiproj_computed = 0;
1542 current_ir_graph = get_irp_irg(i);
1543 env = (inline_irg_env *)get_irg_link(current_ir_graph);
1546 for (entry = env->call_head; entry != NULL; entry = entry->next) {
1549 if (env->n_nodes > maxsize) break;
1552 callee = entry->callee;
1554 if (is_leave(callee) && is_smaller(callee, leavesize)) {
1555 if (!phiproj_computed) {
1556 phiproj_computed = 1;
1557 collect_phiprojs(current_ir_graph);
1559 did_inline = inline_method(call, callee);
1562 /* Do some statistics */
1563 inline_irg_env *callee_env = (inline_irg_env *)get_irg_link(callee);
1565 env->got_inline = 1;
1566 --env->n_call_nodes;
1567 env->n_nodes += callee_env->n_nodes;
1568 --callee_env->n_callers;
1570 /* remove this call from the list */
1572 tail->next = entry->next;
1574 env->call_head = entry->next;
1580 env->call_tail = tail;
1582 } while (did_inline);
1584 /* inline other small functions. */
1585 for (i = 0; i < n_irgs; ++i) {
1587 int phiproj_computed = 0;
1589 current_ir_graph = get_irp_irg(i);
1590 env = (inline_irg_env *)get_irg_link(current_ir_graph);
1592 /* note that the list of possible calls is updated during the process */
1594 for (entry = env->call_head; entry != NULL; entry = entry->next) {
1598 callee = entry->callee;
1600 if (((is_smaller(callee, size) && (env->n_nodes < maxsize)) || /* small function */
1601 (get_irg_inline_property(callee) >= irg_inline_forced))) {
1602 if (!phiproj_computed) {
1603 phiproj_computed = 1;
1604 collect_phiprojs(current_ir_graph);
1606 if (inline_method(call, callee)) {
1607 inline_irg_env *callee_env = (inline_irg_env *)get_irg_link(callee);
1609 /* callee was inline. Append it's call list. */
1610 env->got_inline = 1;
1611 --env->n_call_nodes;
1612 append_call_list(&obst, env, callee_env->call_head);
1613 env->n_call_nodes += callee_env->n_call_nodes;
1614 env->n_nodes += callee_env->n_nodes;
1615 --callee_env->n_callers;
1617 /* after we have inlined callee, all called methods inside callee
1618 are now called once more */
1619 for (centry = callee_env->call_head; centry != NULL; centry = centry->next) {
1620 inline_irg_env *penv = get_irg_link(centry->callee);
1624 /* remove this call from the list */
1626 tail->next = entry->next;
1628 env->call_head = entry->next;
1634 env->call_tail = tail;
1637 for (i = 0; i < n_irgs; ++i) {
1638 irg = get_irp_irg(i);
1639 env = (inline_irg_env *)get_irg_link(irg);
1641 if (env->got_inline) {
1642 /* this irg got calls inlined */
1643 set_irg_outs_inconsistent(irg);
1644 set_irg_doms_inconsistent(irg);
1646 optimize_graph_df(irg);
1649 if (env->got_inline || (env->n_callers_orig != env->n_callers))
1650 DB((dbg, SET_LEVEL_1, "Nodes:%3d ->%3d, calls:%3d ->%3d, callers:%3d ->%3d, -- %s\n",
1651 env->n_nodes_orig, env->n_nodes, env->n_call_nodes_orig, env->n_call_nodes,
1652 env->n_callers_orig, env->n_callers,
1653 get_entity_name(get_irg_entity(irg))));
1656 obstack_free(&obst, NULL);
1657 current_ir_graph = rem;
1660 /*******************************************************************/
1661 /* Code Placement. Pins all floating nodes to a block where they */
1662 /* will be executed only if needed. */
1663 /*******************************************************************/
1666 * Returns non-zero, is a block is not reachable from Start.
1668 * @param block the block to test
1671 is_Block_unreachable(ir_node *block) {
1672 return is_Block_dead(block) || get_Block_dom_depth(block) < 0;
1676 * Find the earliest correct block for node n. --- Place n into the
1677 * same Block as its dominance-deepest Input.
1679 * We have to avoid calls to get_nodes_block() here
1680 * because the graph is floating.
1682 * move_out_of_loops() expects that place_floats_early() have placed
1683 * all "living" nodes into a living block. That's why we must
1684 * move nodes in dead block with "live" successors into a valid
1686 * We move them just into the same block as it's successor (or
1687 * in case of a Phi into the effective use block). For Phi successors,
1688 * this may still be a dead block, but then there is no real use, as
1689 * the control flow will be dead later.
1691 * @param n the node to be placed
1692 * @param worklist a worklist, predecessors of non-floating nodes are placed here
1695 place_floats_early(ir_node *n, waitq *worklist) {
1698 /* we must not run into an infinite loop */
1699 assert(irn_not_visited(n));
1700 mark_irn_visited(n);
1702 /* Place floating nodes. */
1703 if (get_irn_pinned(n) == op_pin_state_floats) {
1704 ir_node *curr_block = get_irn_n(n, -1);
1705 int in_dead_block = is_Block_unreachable(curr_block);
1707 ir_node *b = NULL; /* The block to place this node in */
1709 assert(is_no_Block(n));
1711 if (is_irn_start_block_placed(n)) {
1712 /* These nodes will not be placed by the loop below. */
1713 b = get_irg_start_block(current_ir_graph);
1717 /* find the block for this node. */
1718 irn_arity = get_irn_arity(n);
1719 for (i = 0; i < irn_arity; i++) {
1720 ir_node *pred = get_irn_n(n, i);
1721 ir_node *pred_block;
1723 if ((irn_not_visited(pred))
1724 && (get_irn_pinned(pred) == op_pin_state_floats)) {
1727 * If the current node is NOT in a dead block, but one of its
1728 * predecessors is, we must move the predecessor to a live block.
1729 * Such thing can happen, if global CSE chose a node from a dead block.
1730 * We move it simply to our block.
1731 * Note that neither Phi nor End nodes are floating, so we don't
1732 * need to handle them here.
1734 if (! in_dead_block) {
1735 if (get_irn_pinned(pred) == op_pin_state_floats &&
1736 is_Block_unreachable(get_irn_n(pred, -1)))
1737 set_nodes_block(pred, curr_block);
1739 place_floats_early(pred, worklist);
1743 * A node in the Bad block must stay in the bad block,
1744 * so don't compute a new block for it.
1749 /* Because all loops contain at least one op_pin_state_pinned node, now all
1750 our inputs are either op_pin_state_pinned or place_early() has already
1751 been finished on them. We do not have any unfinished inputs! */
1752 pred_block = get_irn_n(pred, -1);
1753 if ((!is_Block_dead(pred_block)) &&
1754 (get_Block_dom_depth(pred_block) > depth)) {
1756 depth = get_Block_dom_depth(pred_block);
1758 /* Avoid that the node is placed in the Start block */
1759 if ((depth == 1) && (get_Block_dom_depth(get_irn_n(n, -1)) > 1)
1760 && get_irg_phase_state(current_ir_graph) != phase_backend) {
1761 b = get_Block_cfg_out(get_irg_start_block(current_ir_graph), 0);
1762 assert(b != get_irg_start_block(current_ir_graph));
1767 set_nodes_block(n, b);
1771 * Add predecessors of non floating nodes and non-floating predecessors
1772 * of floating nodes to worklist and fix their blocks if the are in dead block.
1774 irn_arity = get_irn_arity(n);
1776 if (get_irn_op(n) == op_End) {
1778 * Simplest case: End node. Predecessors are keep-alives,
1779 * no need to move out of dead block.
1781 for (i = -1; i < irn_arity; ++i) {
1782 ir_node *pred = get_irn_n(n, i);
1783 if (irn_not_visited(pred))
1784 waitq_put(worklist, pred);
1786 } else if (is_Block(n)) {
1788 * Blocks: Predecessors are control flow, no need to move
1789 * them out of dead block.
1791 for (i = irn_arity - 1; i >= 0; --i) {
1792 ir_node *pred = get_irn_n(n, i);
1793 if (irn_not_visited(pred))
1794 waitq_put(worklist, pred);
1796 } else if (is_Phi(n)) {
1798 ir_node *curr_block = get_irn_n(n, -1);
1799 int in_dead_block = is_Block_unreachable(curr_block);
1802 * Phi nodes: move nodes from dead blocks into the effective use
1803 * of the Phi-input if the Phi is not in a bad block.
1805 pred = get_irn_n(n, -1);
1806 if (irn_not_visited(pred))
1807 waitq_put(worklist, pred);
1809 for (i = irn_arity - 1; i >= 0; --i) {
1810 ir_node *pred = get_irn_n(n, i);
1812 if (irn_not_visited(pred)) {
1813 if (! in_dead_block &&
1814 get_irn_pinned(pred) == op_pin_state_floats &&
1815 is_Block_unreachable(get_irn_n(pred, -1))) {
1816 set_nodes_block(pred, get_Block_cfgpred_block(curr_block, i));
1818 waitq_put(worklist, pred);
1823 ir_node *curr_block = get_irn_n(n, -1);
1824 int in_dead_block = is_Block_unreachable(curr_block);
1827 * All other nodes: move nodes from dead blocks into the same block.
1829 pred = get_irn_n(n, -1);
1830 if (irn_not_visited(pred))
1831 waitq_put(worklist, pred);
1833 for (i = irn_arity - 1; i >= 0; --i) {
1834 ir_node *pred = get_irn_n(n, i);
1836 if (irn_not_visited(pred)) {
1837 if (! in_dead_block &&
1838 get_irn_pinned(pred) == op_pin_state_floats &&
1839 is_Block_unreachable(get_irn_n(pred, -1))) {
1840 set_nodes_block(pred, curr_block);
1842 waitq_put(worklist, pred);
1849 * Floating nodes form subgraphs that begin at nodes as Const, Load,
1850 * Start, Call and that end at op_pin_state_pinned nodes as Store, Call. Place_early
1851 * places all floating nodes reachable from its argument through floating
1852 * nodes and adds all beginnings at op_pin_state_pinned nodes to the worklist.
1854 * @param worklist a worklist, used for the algorithm, empty on in/output
1856 static void place_early(waitq *worklist) {
1858 inc_irg_visited(current_ir_graph);
1860 /* this inits the worklist */
1861 place_floats_early(get_irg_end(current_ir_graph), worklist);
1863 /* Work the content of the worklist. */
1864 while (!waitq_empty(worklist)) {
1865 ir_node *n = waitq_get(worklist);
1866 if (irn_not_visited(n))
1867 place_floats_early(n, worklist);
1870 set_irg_outs_inconsistent(current_ir_graph);
1871 set_irg_pinned(current_ir_graph, op_pin_state_pinned);
1875 * Compute the deepest common ancestor of block and dca.
1877 static ir_node *calc_dca(ir_node *dca, ir_node *block) {
1880 /* we do not want to place nodes in dead blocks */
1881 if (is_Block_dead(block))
1884 /* We found a first legal placement. */
1885 if (!dca) return block;
1887 /* Find a placement that is dominates both, dca and block. */
1888 while (get_Block_dom_depth(block) > get_Block_dom_depth(dca))
1889 block = get_Block_idom(block);
1891 while (get_Block_dom_depth(dca) > get_Block_dom_depth(block)) {
1892 dca = get_Block_idom(dca);
1895 while (block != dca) {
1896 block = get_Block_idom(block); dca = get_Block_idom(dca);
1902 /** Deepest common dominance ancestor of DCA and CONSUMER of PRODUCER.
1903 * I.e., DCA is the block where we might place PRODUCER.
1904 * A data flow edge points from producer to consumer.
1907 consumer_dom_dca(ir_node *dca, ir_node *consumer, ir_node *producer) {
1908 ir_node *block = NULL;
1910 /* Compute the latest block into which we can place a node so that it is
1912 if (get_irn_op(consumer) == op_Phi) {
1913 /* our consumer is a Phi-node, the effective use is in all those
1914 blocks through which the Phi-node reaches producer */
1916 ir_node *phi_block = get_nodes_block(consumer);
1917 irn_arity = get_irn_arity(consumer);
1919 for (i = 0; i < irn_arity; i++) {
1920 if (get_irn_n(consumer, i) == producer) {
1921 ir_node *new_block = get_nodes_block(get_Block_cfgpred(phi_block, i));
1923 if (! is_Block_unreachable(new_block))
1924 block = calc_dca(block, new_block);
1929 block = get_irn_n(producer, -1);
1931 assert(is_no_Block(consumer));
1932 block = get_nodes_block(consumer);
1935 /* Compute the deepest common ancestor of block and dca. */
1936 return calc_dca(dca, block);
1939 /* FIXME: the name clashes here with the function from ana/field_temperature.c
1941 static INLINE int get_irn_loop_depth(ir_node *n) {
1942 return get_loop_depth(get_irn_loop(n));
1946 * Move n to a block with less loop depth than it's current block. The
1947 * new block must be dominated by early.
1949 * @param n the node that should be moved
1950 * @param early the earliest block we can n move to
1952 static void move_out_of_loops(ir_node *n, ir_node *early) {
1953 ir_node *best, *dca;
1957 /* Find the region deepest in the dominator tree dominating
1958 dca with the least loop nesting depth, but still dominated
1959 by our early placement. */
1960 dca = get_nodes_block(n);
1963 while (dca != early) {
1964 dca = get_Block_idom(dca);
1965 if (!dca || is_Bad(dca)) break; /* may be Bad if not reachable from Start */
1966 if (get_irn_loop_depth(dca) < get_irn_loop_depth(best)) {
1970 if (best != get_nodes_block(n)) {
1972 printf("Moving out of loop: "); DDMN(n);
1973 printf(" Outermost block: "); DDMN(early);
1974 printf(" Best block: "); DDMN(best);
1975 printf(" Innermost block: "); DDMN(get_nodes_block(n));
1977 set_nodes_block(n, best);
1982 * Find the latest legal block for N and place N into the
1983 * `optimal' Block between the latest and earliest legal block.
1984 * The `optimal' block is the dominance-deepest block of those
1985 * with the least loop-nesting-depth. This places N out of as many
1986 * loops as possible and then makes it as control dependent as
1989 * @param n the node to be placed
1990 * @param worklist a worklist, all successors of non-floating nodes are
1993 static void place_floats_late(ir_node *n, pdeq *worklist) {
1997 assert(irn_not_visited(n)); /* no multiple placement */
1999 mark_irn_visited(n);
2001 /* no need to place block nodes, control nodes are already placed. */
2002 if ((get_irn_op(n) != op_Block) &&
2004 (get_irn_mode(n) != mode_X)) {
2005 /* Remember the early_blk placement of this block to move it
2006 out of loop no further than the early_blk placement. */
2007 early_blk = get_irn_n(n, -1);
2010 * BEWARE: Here we also get code, that is live, but
2011 * was in a dead block. If the node is life, but because
2012 * of CSE in a dead block, we still might need it.
2015 /* Assure that our users are all placed, except the Phi-nodes.
2016 --- Each data flow cycle contains at least one Phi-node. We
2017 have to break the `user has to be placed before the
2018 producer' dependence cycle and the Phi-nodes are the
2019 place to do so, because we need to base our placement on the
2020 final region of our users, which is OK with Phi-nodes, as they
2021 are op_pin_state_pinned, and they never have to be placed after a
2022 producer of one of their inputs in the same block anyway. */
2023 for (i = get_irn_n_outs(n) - 1; i >= 0; --i) {
2024 ir_node *succ = get_irn_out(n, i);
2025 if (irn_not_visited(succ) && (get_irn_op(succ) != op_Phi))
2026 place_floats_late(succ, worklist);
2029 if (! is_Block_dead(early_blk)) {
2030 /* do only move things that where not dead */
2031 ir_op *op = get_irn_op(n);
2033 /* We have to determine the final block of this node... except for
2034 constants and Projs */
2035 if ((get_irn_pinned(n) == op_pin_state_floats) &&
2037 (op != op_SymConst) &&
2040 ir_node *dca = NULL; /* deepest common ancestor in the
2041 dominator tree of all nodes'
2042 blocks depending on us; our final
2043 placement has to dominate DCA. */
2044 for (i = get_irn_n_outs(n) - 1; i >= 0; --i) {
2045 ir_node *succ = get_irn_out(n, i);
2048 if (get_irn_op(succ) == op_End) {
2050 * This consumer is the End node, a keep alive edge.
2051 * This is not a real consumer, so we ignore it
2056 /* ignore if succ is in dead code */
2057 succ_blk = get_irn_n(succ, -1);
2058 if (is_Block_unreachable(succ_blk))
2060 dca = consumer_dom_dca(dca, succ, n);
2063 set_nodes_block(n, dca);
2064 move_out_of_loops(n, early_blk);
2070 /* Add successors of all non-floating nodes on list. (Those of floating
2071 nodes are placed already and therefore are marked.) */
2072 for (i = 0; i < get_irn_n_outs(n); i++) {
2073 ir_node *succ = get_irn_out(n, i);
2074 if (irn_not_visited(get_irn_out(n, i))) {
2075 pdeq_putr(worklist, succ);
2081 * Place floating nodes on the given worklist as late as possible using
2082 * the dominance tree.
2084 * @param worklist the worklist containing the nodes to place
2086 static void place_late(waitq *worklist) {
2088 inc_irg_visited(current_ir_graph);
2090 /* This fills the worklist initially. */
2091 place_floats_late(get_irg_start_block(current_ir_graph), worklist);
2093 /* And now empty the worklist again... */
2094 while (!waitq_empty(worklist)) {
2095 ir_node *n = waitq_get(worklist);
2096 if (irn_not_visited(n))
2097 place_floats_late(n, worklist);
2101 /* Code Placement. */
2102 void place_code(ir_graph *irg) {
2104 ir_graph *rem = current_ir_graph;
2106 current_ir_graph = irg;
2108 /* Handle graph state */
2109 assert(get_irg_phase_state(irg) != phase_building);
2112 if (1 || get_irg_loopinfo_state(irg) != loopinfo_consistent) {
2113 free_loop_information(irg);
2114 construct_backedges(irg);
2117 /* Place all floating nodes as early as possible. This guarantees
2118 a legal code placement. */
2119 worklist = new_waitq();
2120 place_early(worklist);
2122 /* place_early() invalidates the outs, place_late needs them. */
2123 compute_irg_outs(irg);
2125 /* Now move the nodes down in the dominator tree. This reduces the
2126 unnecessary executions of the node. */
2127 place_late(worklist);
2129 set_irg_outs_inconsistent(current_ir_graph);
2130 set_irg_loopinfo_inconsistent(current_ir_graph);
2131 del_waitq(worklist);
2132 current_ir_graph = rem;
2136 * Called by walker of remove_critical_cf_edges().
2138 * Place an empty block to an edge between a blocks of multiple
2139 * predecessors and a block of multiple successors.
2142 * @param env Environment of walker. The changed field.
2144 static void walk_critical_cf_edges(ir_node *n, void *env) {
2146 ir_node *pre, *block, *jmp;
2148 ir_graph *irg = get_irn_irg(n);
2150 /* Block has multiple predecessors */
2151 arity = get_irn_arity(n);
2153 if (n == get_irg_end_block(irg))
2154 return; /* No use to add a block here. */
2156 for (i = 0; i < arity; ++i) {
2159 pre = get_irn_n(n, i);
2160 cfop = get_irn_op(skip_Proj(pre));
2161 /* Predecessor has multiple successors. Insert new control flow edge but
2162 ignore exception edges. */
2163 if (! is_op_fragile(cfop) && is_op_forking(cfop)) {
2164 /* set predecessor of new block */
2165 block = new_r_Block(irg, 1, &pre);
2166 /* insert new jmp node to new block */
2167 jmp = new_r_Jmp(irg, block);
2168 /* set successor of new block */
2169 set_irn_n(n, i, jmp);
2171 } /* predecessor has multiple successors */
2172 } /* for all predecessors */
2173 } /* n is a multi-entry block */
2176 void remove_critical_cf_edges(ir_graph *irg) {
2179 irg_block_walk_graph(irg, NULL, walk_critical_cf_edges, &changed);
2181 /* control flow changed */
2182 set_irg_outs_inconsistent(irg);
2183 set_irg_extblk_inconsistent(irg);
2184 set_irg_doms_inconsistent(irg);
2185 set_irg_loopinfo_inconsistent(irg);