3 * File name: ir/ir/irgopt.c
4 * Purpose: Optimizations for a whole ir graph, i.e., a procedure.
5 * Author: Christian Schaefer, Goetz Lindenmaier
6 * Modified by: Sebastian Felis
9 * Copyright: (c) 1998-2003 Universität Karlsruhe
10 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
22 #include "irgraph_t.h"
34 #include "pdeq.h" /* Fuer code placement */
38 #include "irbackedge_t.h"
44 /* Defined in iropt.c */
45 pset *new_identities (void);
46 void del_identities (pset *value_table);
47 void add_identities (pset *value_table, ir_node *node);
49 /*------------------------------------------------------------------*/
50 /* apply optimizations of iropt to all nodes. */
51 /*------------------------------------------------------------------*/
53 static void init_link (ir_node *n, void *env) {
54 set_irn_link(n, NULL);
57 #if 0 /* Old version. Avoids Ids.
58 This is not necessary: we do a postwalk, and get_irn_n
59 removes ids anyways. So it's much cheaper to call the
60 optimization less often and use the exchange() algorithm. */
62 optimize_in_place_wrapper (ir_node *n, void *env) {
64 ir_node *optimized, *old;
66 irn_arity = get_irn_arity(n);
67 for (i = 0; i < irn_arity; i++) {
68 /* get_irn_n skips Id nodes, so comparison old != optimized does not
69 show all optimizations. Therefore always set new predecessor. */
70 old = get_irn_intra_n(n, i);
71 optimized = optimize_in_place_2(old);
72 set_irn_n(n, i, optimized);
75 if (get_irn_op(n) == op_Block) {
76 optimized = optimize_in_place_2(n);
77 if (optimized != n) exchange (n, optimized);
82 optimize_in_place_wrapper (ir_node *n, void *env) {
83 ir_node *optimized = optimize_in_place_2(n);
84 if (optimized != n) exchange (n, optimized);
89 static INLINE void do_local_optimize(ir_node *n) {
90 /* Handle graph state */
91 assert(get_irg_phase_state(current_ir_graph) != phase_building);
92 if (get_opt_global_cse())
93 set_irg_pinned(current_ir_graph, op_pin_state_floats);
94 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
95 set_irg_outs_inconsistent(current_ir_graph);
96 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
97 set_irg_dom_inconsistent(current_ir_graph);
98 set_irg_loopinfo_inconsistent(current_ir_graph);
101 /* Clean the value_table in irg for the cse. */
102 del_identities(current_ir_graph->value_table);
103 current_ir_graph->value_table = new_identities();
105 /* walk over the graph */
106 irg_walk(n, init_link, optimize_in_place_wrapper, NULL);
109 void local_optimize_node(ir_node *n) {
110 ir_graph *rem = current_ir_graph;
111 current_ir_graph = get_irn_irg(n);
113 do_local_optimize(n);
115 current_ir_graph = rem;
120 local_optimize_graph (ir_graph *irg) {
121 ir_graph *rem = current_ir_graph;
122 current_ir_graph = irg;
124 do_local_optimize(irg->end);
126 current_ir_graph = rem;
130 /*------------------------------------------------------------------*/
131 /* Routines for dead node elimination / copying garbage collection */
132 /* of the obstack. */
133 /*------------------------------------------------------------------*/
136 * Remember the new node in the old node by using a field all nodes have.
139 set_new_node (ir_node *old, ir_node *new)
145 * Get this new node, before the old node is forgotton.
147 static INLINE ir_node *
148 get_new_node (ir_node * n)
154 * We use the block_visited flag to mark that we have computed the
155 * number of useful predecessors for this block.
156 * Further we encode the new arity in this flag in the old blocks.
157 * Remembering the arity is useful, as it saves a lot of pointer
158 * accesses. This function is called for all Phi and Block nodes
162 compute_new_arity(ir_node *b) {
163 int i, res, irn_arity;
166 irg_v = get_irg_block_visited(current_ir_graph);
167 block_v = get_Block_block_visited(b);
168 if (block_v >= irg_v) {
169 /* we computed the number of preds for this block and saved it in the
171 return block_v - irg_v;
173 /* compute the number of good predecessors */
174 res = irn_arity = get_irn_arity(b);
175 for (i = 0; i < irn_arity; i++)
176 if (get_irn_opcode(get_irn_n(b, i)) == iro_Bad) res--;
177 /* save it in the flag. */
178 set_Block_block_visited(b, irg_v + res);
183 /* TODO: add an ir_op operation */
184 static INLINE void new_backedge_info(ir_node *n) {
185 switch(get_irn_opcode(n)) {
187 n->attr.block.cg_backedge = NULL;
188 n->attr.block.backedge = new_backedge_arr(current_ir_graph->obst, get_irn_arity(n));
191 n->attr.phi_backedge = new_backedge_arr(current_ir_graph->obst, get_irn_arity(n));
194 n->attr.filter.backedge = new_backedge_arr(current_ir_graph->obst, get_irn_arity(n));
201 * Copies the node to the new obstack. The Ins of the new node point to
202 * the predecessors on the old obstack. For block/phi nodes not all
203 * predecessors might be copied. n->link points to the new node.
204 * For Phi and Block nodes the function allocates in-arrays with an arity
205 * only for useful predecessors. The arity is determined by counting
206 * the non-bad predecessors of the block.
208 * @param n The node to be copied
209 * @param env if non-NULL, the node number attribute will be copied to the new node
212 copy_node (ir_node *n, void *env) {
215 opcode op = get_irn_opcode(n);
216 int copy_node_nr = env != NULL;
218 /* The end node looses it's flexible in array. This doesn't matter,
219 as dead node elimination builds End by hand, inlineing doesn't use
221 /* assert(n->op == op_End || ((_ARR_DESCR(n->in))->cookie != ARR_F_MAGIC)); */
224 /* node copied already */
226 } else if (op == iro_Block) {
228 new_arity = compute_new_arity(n);
229 n->attr.block.graph_arr = NULL;
231 block = get_nodes_block(n);
232 if (get_irn_opcode(n) == iro_Phi) {
233 new_arity = compute_new_arity(block);
235 new_arity = get_irn_arity(n);
238 nn = new_ir_node(get_irn_dbg_info(n),
245 /* Copy the attributes. These might point to additional data. If this
246 was allocated on the old obstack the pointers now are dangling. This
247 frees e.g. the memory of the graph_arr allocated in new_immBlock. */
249 new_backedge_info(nn);
254 /* for easier debugging, we want to copy the node numbers too */
255 nn->node_nr = n->node_nr;
259 /* printf("\n old node: "); DDMSG2(n);
260 printf(" new node: "); DDMSG2(nn); */
265 * Copies new predecessors of old node to new node remembered in link.
266 * Spare the Bad predecessors of Phi and Block nodes.
269 copy_preds (ir_node *n, void *env) {
273 nn = get_new_node(n);
275 /* printf("\n old node: "); DDMSG2(n);
276 printf(" new node: "); DDMSG2(nn);
277 printf(" arities: old: %d, new: %d\n", get_irn_arity(n), get_irn_arity(nn)); */
279 if (get_irn_opcode(n) == iro_Block) {
280 /* Don't copy Bad nodes. */
282 irn_arity = get_irn_arity(n);
283 for (i = 0; i < irn_arity; i++)
284 if (get_irn_opcode(get_irn_n(n, i)) != iro_Bad) {
285 set_irn_n (nn, j, get_new_node(get_irn_n(n, i)));
286 /*if (is_backedge(n, i)) set_backedge(nn, j);*/
289 /* repair the block visited flag from above misuse. Repair it in both
290 graphs so that the old one can still be used. */
291 set_Block_block_visited(nn, 0);
292 set_Block_block_visited(n, 0);
293 /* Local optimization could not merge two subsequent blocks if
294 in array contained Bads. Now it's possible.
295 We don't call optimize_in_place as it requires
296 that the fields in ir_graph are set properly. */
297 if ((get_opt_control_flow_straightening()) &&
298 (get_Block_n_cfgpreds(nn) == 1) &&
299 (get_irn_op(get_Block_cfgpred(nn, 0)) == op_Jmp)) {
300 ir_node *old = get_nodes_block(get_Block_cfgpred(nn, 0));
302 /* Jmp jumps into the block it is in -- deal self cycle. */
303 assert(is_Bad(get_new_node(get_irg_bad(current_ir_graph))));
304 exchange(nn, get_new_node(get_irg_bad(current_ir_graph)));
309 } else if (get_irn_opcode(n) == iro_Phi) {
310 /* Don't copy node if corresponding predecessor in block is Bad.
311 The Block itself should not be Bad. */
312 block = get_nodes_block(n);
313 set_irn_n (nn, -1, get_new_node(block));
315 irn_arity = get_irn_arity(n);
316 for (i = 0; i < irn_arity; i++)
317 if (get_irn_opcode(get_irn_n(block, i)) != iro_Bad) {
318 set_irn_n (nn, j, get_new_node(get_irn_n(n, i)));
319 /*if (is_backedge(n, i)) set_backedge(nn, j);*/
322 /* If the pre walker reached this Phi after the post walker visited the
323 block block_visited is > 0. */
324 set_Block_block_visited(get_nodes_block(n), 0);
325 /* Compacting the Phi's ins might generate Phis with only one
327 if (get_irn_arity(n) == 1)
328 exchange(n, get_irn_n(n, 0));
330 irn_arity = get_irn_arity(n);
331 for (i = -1; i < irn_arity; i++)
332 set_irn_n (nn, i, get_new_node(get_irn_n(n, i)));
334 /* Now the new node is complete. We can add it to the hash table for cse.
335 @@@ inlinening aborts if we identify End. Why? */
336 if(get_irn_op(nn) != op_End)
337 add_identities (current_ir_graph->value_table, nn);
341 * Copies the graph recursively, compacts the keepalive of the end node.
343 * @param copy_node_nr If non-zero, the node number will be copied
346 copy_graph (int copy_node_nr) {
347 ir_node *oe, *ne, *ob, *nb; /* old end, new end, old bad, new bad */
348 ir_node *ka; /* keep alive */
351 oe = get_irg_end(current_ir_graph);
352 /* copy the end node by hand, allocate dynamic in array! */
353 ne = new_ir_node(get_irn_dbg_info(oe),
360 /* Copy the attributes. Well, there might be some in the future... */
362 set_new_node(oe, ne);
364 ob = get_irg_bad(current_ir_graph);
365 nb = new_ir_node(get_irn_dbg_info(ob),
372 set_new_node(ob, nb);
374 /* copy the live nodes */
375 irg_walk(get_nodes_block(oe), copy_node, copy_preds, (void *)copy_node_nr);
376 /* copy_preds for the end node ... */
377 set_nodes_block(ne, get_new_node(get_nodes_block(oe)));
379 /*- ... and now the keep alives. -*/
380 /* First pick the not marked block nodes and walk them. We must pick these
381 first as else we will oversee blocks reachable from Phis. */
382 irn_arity = get_irn_arity(oe);
383 for (i = 0; i < irn_arity; i++) {
384 ka = get_irn_intra_n(oe, i);
385 if ((get_irn_op(ka) == op_Block) &&
386 (get_irn_visited(ka) < get_irg_visited(current_ir_graph))) {
387 /* We must keep the block alive and copy everything reachable */
388 set_irg_visited(current_ir_graph, get_irg_visited(current_ir_graph)-1);
389 irg_walk(ka, copy_node, copy_preds, (void *)copy_node_nr);
390 add_End_keepalive(ne, get_new_node(ka));
394 /* Now pick the Phis. Here we will keep all! */
395 irn_arity = get_irn_arity(oe);
396 for (i = 0; i < irn_arity; i++) {
397 ka = get_irn_intra_n(oe, i);
398 if ((get_irn_op(ka) == op_Phi)) {
399 if (get_irn_visited(ka) < get_irg_visited(current_ir_graph)) {
400 /* We didn't copy the Phi yet. */
401 set_irg_visited(current_ir_graph, get_irg_visited(current_ir_graph)-1);
402 irg_walk(ka, copy_node, copy_preds, (void *)copy_node_nr);
404 add_End_keepalive(ne, get_new_node(ka));
408 /* start block somtimes only reached after keep alives */
409 set_nodes_block(nb, get_new_node(get_nodes_block(ob)));
413 * Copies the graph reachable from current_ir_graph->end to the obstack
414 * in current_ir_graph and fixes the environment.
415 * Then fixes the fields in current_ir_graph containing nodes of the
418 * @param copy_node_nr If non-zero, the node number will be copied
421 copy_graph_env (int copy_node_nr) {
423 /* Not all nodes remembered in current_ir_graph might be reachable
424 from the end node. Assure their link is set to NULL, so that
425 we can test whether new nodes have been computed. */
426 set_irn_link(get_irg_frame (current_ir_graph), NULL);
427 set_irn_link(get_irg_globals (current_ir_graph), NULL);
428 set_irn_link(get_irg_args (current_ir_graph), NULL);
429 set_irn_link(get_irg_initial_mem(current_ir_graph), NULL);
431 /* we use the block walk flag for removing Bads from Blocks ins. */
432 inc_irg_block_visited(current_ir_graph);
435 copy_graph(copy_node_nr);
437 /* fix the fields in current_ir_graph */
438 old_end = get_irg_end(current_ir_graph);
439 set_irg_end (current_ir_graph, get_new_node(old_end));
440 set_irg_end_except (current_ir_graph, get_irg_end(current_ir_graph));
441 set_irg_end_reg (current_ir_graph, get_irg_end(current_ir_graph));
443 set_irg_end_block (current_ir_graph, get_new_node(get_irg_end_block(current_ir_graph)));
444 if (get_irn_link(get_irg_frame(current_ir_graph)) == NULL) {
445 copy_node (get_irg_frame(current_ir_graph), (void *)copy_node_nr);
446 copy_preds(get_irg_frame(current_ir_graph), NULL);
448 if (get_irn_link(get_irg_globals(current_ir_graph)) == NULL) {
449 copy_node (get_irg_globals(current_ir_graph), (void *)copy_node_nr);
450 copy_preds(get_irg_globals(current_ir_graph), NULL);
452 if (get_irn_link(get_irg_initial_mem(current_ir_graph)) == NULL) {
453 copy_node (get_irg_initial_mem(current_ir_graph), (void *)copy_node_nr);
454 copy_preds(get_irg_initial_mem(current_ir_graph), NULL);
456 if (get_irn_link(get_irg_args(current_ir_graph)) == NULL) {
457 copy_node (get_irg_args(current_ir_graph), (void *)copy_node_nr);
458 copy_preds(get_irg_args(current_ir_graph), NULL);
460 set_irg_start (current_ir_graph, get_new_node(get_irg_start(current_ir_graph)));
462 set_irg_start_block(current_ir_graph,
463 get_new_node(get_irg_start_block(current_ir_graph)));
464 set_irg_frame (current_ir_graph, get_new_node(get_irg_frame(current_ir_graph)));
465 set_irg_globals (current_ir_graph, get_new_node(get_irg_globals(current_ir_graph)));
466 set_irg_initial_mem(current_ir_graph, get_new_node(get_irg_initial_mem(current_ir_graph)));
467 set_irg_args (current_ir_graph, get_new_node(get_irg_args(current_ir_graph)));
469 if (get_irn_link(get_irg_bad(current_ir_graph)) == NULL) {
470 copy_node(get_irg_bad(current_ir_graph), (void *)copy_node_nr);
471 copy_preds(get_irg_bad(current_ir_graph), NULL);
473 set_irg_bad(current_ir_graph, get_new_node(get_irg_bad(current_ir_graph)));
477 * Copies all reachable nodes to a new obstack. Removes bad inputs
478 * from block nodes and the corresponding inputs from Phi nodes.
479 * Merges single exit blocks with single entry blocks and removes
481 * Adds all new nodes to a new hash table for cse. Does not
482 * perform cse, so the hash table might contain common subexpressions.
485 dead_node_elimination(ir_graph *irg) {
487 int rem_ipview = interprocedural_view;
488 struct obstack *graveyard_obst = NULL;
489 struct obstack *rebirth_obst = NULL;
491 /* inform statistics that we started a dead-node elimination run */
492 stat_dead_node_elim_start(irg);
494 /* Remember external state of current_ir_graph. */
495 rem = current_ir_graph;
496 current_ir_graph = irg;
497 interprocedural_view = 0;
499 /* Handle graph state */
500 assert(get_irg_phase_state(current_ir_graph) != phase_building);
501 free_callee_info(current_ir_graph);
502 free_outs(current_ir_graph);
503 /* @@@ so far we loose loops when copying */
504 free_loop_information(current_ir_graph);
506 if (get_opt_optimize() && get_opt_dead_node_elimination()) {
508 /* A quiet place, where the old obstack can rest in peace,
509 until it will be cremated. */
510 graveyard_obst = irg->obst;
512 /* A new obstack, where the reachable nodes will be copied to. */
513 rebirth_obst = (struct obstack *) xmalloc (sizeof (struct obstack));
514 current_ir_graph->obst = rebirth_obst;
515 obstack_init (current_ir_graph->obst);
517 /* We also need a new hash table for cse */
518 del_identities (irg->value_table);
519 irg->value_table = new_identities ();
521 /* Copy the graph from the old to the new obstack */
524 /* Free memory from old unoptimized obstack */
525 obstack_free(graveyard_obst, 0); /* First empty the obstack ... */
526 xfree (graveyard_obst); /* ... then free it. */
529 /* inform statistics that the run is over */
530 stat_dead_node_elim_stop(irg);
532 current_ir_graph = rem;
533 interprocedural_view = rem_ipview;
537 * Relink bad predeseccors of a block and store the old in array to the
538 * link field. This function is called by relink_bad_predecessors().
539 * The array of link field starts with the block operand at position 0.
540 * If block has bad predecessors, create a new in array without bad preds.
541 * Otherwise let in array untouched.
543 static void relink_bad_block_predecessors(ir_node *n, void *env) {
544 ir_node **new_in, *irn;
545 int i, new_irn_n, old_irn_arity, new_irn_arity = 0;
547 /* if link field of block is NULL, look for bad predecessors otherwise
548 this is allready done */
549 if (get_irn_op(n) == op_Block &&
550 get_irn_link(n) == NULL) {
552 /* save old predecessors in link field (position 0 is the block operand)*/
553 set_irn_link(n, (void *)get_irn_in(n));
555 /* count predecessors without bad nodes */
556 old_irn_arity = get_irn_arity(n);
557 for (i = 0; i < old_irn_arity; i++)
558 if (!is_Bad(get_irn_n(n, i))) new_irn_arity++;
560 /* arity changing: set new predecessors without bad nodes */
561 if (new_irn_arity < old_irn_arity) {
562 /* get new predecessor array without Block predecessor */
563 new_in = NEW_ARR_D (ir_node *, current_ir_graph->obst, (new_irn_arity+1));
565 /* set new predeseccors in array */
568 for (i = 1; i < old_irn_arity; i++) {
569 irn = get_irn_n(n, i);
570 if (!is_Bad(irn)) new_in[new_irn_n++] = irn;
573 } /* ir node has bad predecessors */
575 } /* Block is not relinked */
579 * Relinks Bad predecesors from Bocks and Phis called by walker
580 * remove_bad_predecesors(). If n is a Block, call
581 * relink_bad_block_redecessors(). If n is a Phinode, call also the relinking
582 * function of Phi's Block. If this block has bad predecessors, relink preds
585 static void relink_bad_predecessors(ir_node *n, void *env) {
586 ir_node *block, **old_in;
587 int i, old_irn_arity, new_irn_arity;
589 /* relink bad predeseccors of a block */
590 if (get_irn_op(n) == op_Block)
591 relink_bad_block_predecessors(n, env);
593 /* If Phi node relink its block and its predecessors */
594 if (get_irn_op(n) == op_Phi) {
596 /* Relink predeseccors of phi's block */
597 block = get_nodes_block(n);
598 if (get_irn_link(block) == NULL)
599 relink_bad_block_predecessors(block, env);
601 old_in = (ir_node **)get_irn_link(block); /* Of Phi's Block */
602 old_irn_arity = ARR_LEN(old_in);
604 /* Relink Phi predeseccors if count of predeseccors changed */
605 if (old_irn_arity != ARR_LEN(get_irn_in(block))) {
606 /* set new predeseccors in array
607 n->in[0] remains the same block */
609 for(i = 1; i < old_irn_arity; i++)
610 if (!is_Bad((ir_node *)old_in[i])) n->in[new_irn_arity++] = n->in[i];
612 ARR_SETLEN(ir_node *, n->in, new_irn_arity);
615 } /* n is a Phi node */
619 * Removes Bad Bad predecesors from Blocks and the corresponding
620 * inputs to Phi nodes as in dead_node_elimination but without
622 * On walking up set the link field to NULL, on walking down call
623 * relink_bad_predecessors() (This function stores the old in array
624 * to the link field and sets a new in array if arity of predecessors
627 void remove_bad_predecessors(ir_graph *irg) {
628 irg_walk_graph(irg, init_link, relink_bad_predecessors, NULL);
632 /*--------------------------------------------------------------------*/
633 /* Funcionality for inlining */
634 /*--------------------------------------------------------------------*/
637 * Copy node for inlineing. Updates attributes that change when
638 * inlineing but not for dead node elimination.
640 * Copies the node by calling copy_node and then updates the entity if
641 * it's a local one. env must be a pointer of the frame type of the
642 * inlined procedure. The new entities must be in the link field of
646 copy_node_inline (ir_node *n, void *env) {
648 type *frame_tp = (type *)env;
651 if (get_irn_op(n) == op_Sel) {
652 new = get_new_node (n);
653 assert(get_irn_op(new) == op_Sel);
654 if (get_entity_owner(get_Sel_entity(n)) == frame_tp) {
655 set_Sel_entity(new, get_entity_link(get_Sel_entity(n)));
657 } else if (get_irn_op(n) == op_Block) {
658 new = get_new_node (n);
659 new->attr.block.irg = current_ir_graph;
663 static void find_addr(ir_node *node, void *env)
665 if (get_irn_opcode(node) == iro_Proj) {
666 if (get_Proj_proj(node) == pn_Start_P_value_arg_base)
672 * currently, we cannot inline two cases:
673 * - call with compound arguments
674 * - graphs that take the address of a parameter
676 * check these conditions here
678 static int can_inline(ir_node *call, ir_graph *called_graph)
680 type *call_type = get_Call_type(call);
681 int params, ress, i, res;
682 assert(is_method_type(call_type));
684 params = get_method_n_params(call_type);
685 ress = get_method_n_ress(call_type);
688 for (i = 0; i < params; ++i) {
689 type *p_type = get_method_param_type(call_type, i);
691 if (is_compound_type(p_type))
696 for (i = 0; i < ress; ++i) {
697 type *r_type = get_method_res_type(call_type, i);
699 if (is_compound_type(r_type))
704 irg_walk_graph(called_graph, find_addr, NULL, &res);
709 int inline_method(ir_node *call, ir_graph *called_graph) {
711 ir_node *post_call, *post_bl;
713 ir_node *end, *end_bl;
717 int arity, n_ret, n_exc, n_res, i, j, rem_opt, irn_arity;
720 irg_inline_property prop = get_irg_inline_property(called_graph);
722 if ( (prop != irg_inline_forced) &&
723 (!get_opt_optimize() || !get_opt_inline() || (prop == irg_inline_forbidden))) return 0;
725 /* Do not inline variadic functions. */
726 if (get_method_variadicity(get_entity_type(get_irg_entity(called_graph))) == variadicity_variadic)
729 assert(get_method_n_params(get_entity_type(get_irg_entity(called_graph))) ==
730 get_method_n_params(get_Call_type(call)));
733 * currently, we cannot inline two cases:
734 * - call with compound arguments
735 * - graphs that take the address of a parameter
737 if (! can_inline(call, called_graph))
740 /* -- Turn off optimizations, this can cause problems when allocating new nodes. -- */
741 rem_opt = get_opt_optimize();
744 /* Handle graph state */
745 assert(get_irg_phase_state(current_ir_graph) != phase_building);
746 assert(get_irg_pinned(current_ir_graph) == op_pin_state_pinned);
747 assert(get_irg_pinned(called_graph) == op_pin_state_pinned);
748 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
749 set_irg_outs_inconsistent(current_ir_graph);
750 set_irg_loopinfo_inconsistent(current_ir_graph);
752 /* -- Check preconditions -- */
753 assert(get_irn_op(call) == op_Call);
754 /* @@@ does not work for InterfaceIII.java after cgana
755 assert(get_Call_type(call) == get_entity_type(get_irg_entity(called_graph)));
756 assert(smaller_type(get_entity_type(get_irg_entity(called_graph)),
757 get_Call_type(call)));
759 assert(get_type_tpop(get_Call_type(call)) == type_method);
760 if (called_graph == current_ir_graph) {
761 set_optimize(rem_opt);
765 /* here we know we WILL inline, so inform the statistics */
766 stat_inline(call, called_graph);
768 /* -- Decide how to handle exception control flow: Is there a handler
769 for the Call node, or do we branch directly to End on an exception?
771 0 There is a handler.
773 2 Exception handling not represented in Firm. -- */
775 ir_node *proj, *Mproj = NULL, *Xproj = NULL;
776 for (proj = (ir_node *)get_irn_link(call); proj; proj = (ir_node *)get_irn_link(proj)) {
777 assert(get_irn_op(proj) == op_Proj);
778 if (get_Proj_proj(proj) == pn_Call_X_except) Xproj = proj;
779 if (get_Proj_proj(proj) == pn_Call_M_except) Mproj = proj;
781 if (Mproj) { assert(Xproj); exc_handling = 0; } /* Mproj */
782 else if (Xproj) { exc_handling = 1; } /* !Mproj && Xproj */
783 else { exc_handling = 2; } /* !Mproj && !Xproj */
788 the procedure and later replaces the Start node of the called graph.
789 Post_call is the old Call node and collects the results of the called
790 graph. Both will end up being a tuple. -- */
791 post_bl = get_nodes_block(call);
792 set_irg_current_block(current_ir_graph, post_bl);
793 /* XxMxPxP of Start + parameter of Call */
794 in[pn_Start_X_initial_exec] = new_Jmp();
795 in[pn_Start_M] = get_Call_mem(call);
796 in[pn_Start_P_frame_base] = get_irg_frame(current_ir_graph);
797 in[pn_Start_P_globals] = get_irg_globals(current_ir_graph);
798 in[pn_Start_T_args] = new_Tuple(get_Call_n_params(call), get_Call_param_arr(call));
799 /* in[pn_Start_P_value_arg_base] = ??? */
800 pre_call = new_Tuple(5, in);
804 The new block gets the ins of the old block, pre_call and all its
805 predecessors and all Phi nodes. -- */
806 part_block(pre_call);
808 /* -- Prepare state for dead node elimination -- */
809 /* Visited flags in calling irg must be >= flag in called irg.
810 Else walker and arity computation will not work. */
811 if (get_irg_visited(current_ir_graph) <= get_irg_visited(called_graph))
812 set_irg_visited(current_ir_graph, get_irg_visited(called_graph)+1);
813 if (get_irg_block_visited(current_ir_graph)< get_irg_block_visited(called_graph))
814 set_irg_block_visited(current_ir_graph, get_irg_block_visited(called_graph));
815 /* Set pre_call as new Start node in link field of the start node of
816 calling graph and pre_calls block as new block for the start block
818 Further mark these nodes so that they are not visited by the
820 set_irn_link(get_irg_start(called_graph), pre_call);
821 set_irn_visited(get_irg_start(called_graph), get_irg_visited(current_ir_graph));
822 set_irn_link(get_irg_start_block(called_graph), get_nodes_block(pre_call));
823 set_irn_visited(get_irg_start_block(called_graph), get_irg_visited(current_ir_graph));
824 set_irn_link(get_irg_bad(called_graph), get_irg_bad(current_ir_graph));
825 set_irn_visited(get_irg_bad(called_graph), get_irg_visited(current_ir_graph));
827 /* Initialize for compaction of in arrays */
828 inc_irg_block_visited(current_ir_graph);
830 /* -- Replicate local entities of the called_graph -- */
831 /* copy the entities. */
832 called_frame = get_irg_frame_type(called_graph);
833 for (i = 0; i < get_class_n_members(called_frame); i++) {
834 entity *new_ent, *old_ent;
835 old_ent = get_class_member(called_frame, i);
836 new_ent = copy_entity_own(old_ent, get_cur_frame_type());
837 set_entity_link(old_ent, new_ent);
840 /* visited is > than that of called graph. With this trick visited will
841 remain unchanged so that an outer walker, e.g., searching the call nodes
842 to inline, calling this inline will not visit the inlined nodes. */
843 set_irg_visited(current_ir_graph, get_irg_visited(current_ir_graph)-1);
845 /* -- Performing dead node elimination inlines the graph -- */
846 /* Copies the nodes to the obstack of current_ir_graph. Updates links to new
848 /* @@@ endless loops are not copied!! -- they should be, I think... */
849 irg_walk(get_irg_end(called_graph), copy_node_inline, copy_preds,
850 get_irg_frame_type(called_graph));
852 /* Repair called_graph */
853 set_irg_visited(called_graph, get_irg_visited(current_ir_graph));
854 set_irg_block_visited(called_graph, get_irg_block_visited(current_ir_graph));
855 set_Block_block_visited(get_irg_start_block(called_graph), 0);
857 /* -- Merge the end of the inlined procedure with the call site -- */
858 /* We will turn the old Call node into a Tuple with the following
861 0: Phi of all Memories of Return statements.
862 1: Jmp from new Block that merges the control flow from all exception
863 predecessors of the old end block.
864 2: Tuple of all arguments.
865 3: Phi of Exception memories.
866 In case the old Call directly branches to End on an exception we don't
867 need the block merging all exceptions nor the Phi of the exception
871 /* -- Precompute some values -- */
872 end_bl = get_new_node(get_irg_end_block(called_graph));
873 end = get_new_node(get_irg_end(called_graph));
874 arity = get_irn_arity(end_bl); /* arity = n_exc + n_ret */
875 n_res = get_method_n_ress(get_Call_type(call));
877 res_pred = (ir_node **) malloc (n_res * sizeof (ir_node *));
878 cf_pred = (ir_node **) malloc (arity * sizeof (ir_node *));
880 set_irg_current_block(current_ir_graph, post_bl); /* just to make sure */
882 /* -- archive keepalives -- */
883 irn_arity = get_irn_arity(end);
884 for (i = 0; i < irn_arity; i++)
885 add_End_keepalive(get_irg_end(current_ir_graph), get_irn_n(end, i));
887 /* The new end node will die. We need not free as the in array is on the obstack:
888 copy_node only generated 'D' arrays. */
890 /* -- Replace Return nodes by Jump nodes. -- */
892 for (i = 0; i < arity; i++) {
894 ret = get_irn_n(end_bl, i);
895 if (get_irn_op(ret) == op_Return) {
896 cf_pred[n_ret] = new_r_Jmp(current_ir_graph, get_nodes_block(ret));
900 set_irn_in(post_bl, n_ret, cf_pred);
902 /* -- Build a Tuple for all results of the method.
903 Add Phi node if there was more than one Return. -- */
904 turn_into_tuple(post_call, 4);
905 /* First the Memory-Phi */
907 for (i = 0; i < arity; i++) {
908 ret = get_irn_n(end_bl, i);
909 if (get_irn_op(ret) == op_Return) {
910 cf_pred[n_ret] = get_Return_mem(ret);
914 phi = new_Phi(n_ret, cf_pred, mode_M);
915 set_Tuple_pred(call, pn_Call_M_regular, phi);
916 /* Conserve Phi-list for further inlinings -- but might be optimized */
917 if (get_nodes_block(phi) == post_bl) {
918 set_irn_link(phi, get_irn_link(post_bl));
919 set_irn_link(post_bl, phi);
921 /* Now the real results */
923 for (j = 0; j < n_res; j++) {
925 for (i = 0; i < arity; i++) {
926 ret = get_irn_n(end_bl, i);
927 if (get_irn_op(ret) == op_Return) {
928 cf_pred[n_ret] = get_Return_res(ret, j);
933 phi = new_Phi(n_ret, cf_pred, get_irn_mode(cf_pred[0]));
937 /* Conserve Phi-list for further inlinings -- but might be optimized */
938 if (get_nodes_block(phi) == post_bl) {
939 set_irn_link(phi, get_irn_link(post_bl));
940 set_irn_link(post_bl, phi);
943 set_Tuple_pred(call, pn_Call_T_result, new_Tuple(n_res, res_pred));
945 set_Tuple_pred(call, pn_Call_T_result, new_Bad());
947 /* Finally the exception control flow.
948 We have two (three) possible situations:
949 First if the Call branches to an exception handler: We need to add a Phi node to
950 collect the memory containing the exception objects. Further we need
951 to add another block to get a correct representation of this Phi. To
952 this block we add a Jmp that resolves into the X output of the Call
953 when the Call is turned into a tuple.
954 Second the Call branches to End, the exception is not handled. Just
955 add all inlined exception branches to the End node.
956 Third: there is no Exception edge at all. Handle as case two. */
957 if (exc_handling == 0) {
959 for (i = 0; i < arity; i++) {
961 ret = get_irn_n(end_bl, i);
962 if (is_fragile_op(skip_Proj(ret)) || (get_irn_op(skip_Proj(ret)) == op_Raise)) {
963 cf_pred[n_exc] = ret;
968 new_Block(n_exc, cf_pred); /* watch it: current_block is changed! */
969 set_Tuple_pred(call, pn_Call_X_except, new_Jmp());
970 /* The Phi for the memories with the exception objects */
972 for (i = 0; i < arity; i++) {
974 ret = skip_Proj(get_irn_n(end_bl, i));
975 if (get_irn_op(ret) == op_Call) {
976 cf_pred[n_exc] = new_r_Proj(current_ir_graph, get_nodes_block(ret), ret, mode_M, 3);
978 } else if (is_fragile_op(ret)) {
979 /* We rely that all cfops have the memory output at the same position. */
980 cf_pred[n_exc] = new_r_Proj(current_ir_graph, get_nodes_block(ret), ret, mode_M, 0);
982 } else if (get_irn_op(ret) == op_Raise) {
983 cf_pred[n_exc] = new_r_Proj(current_ir_graph, get_nodes_block(ret), ret, mode_M, 1);
987 set_Tuple_pred(call, pn_Call_M_except, new_Phi(n_exc, cf_pred, mode_M));
989 set_Tuple_pred(call, pn_Call_X_except, new_Bad());
990 set_Tuple_pred(call, pn_Call_M_except, new_Bad());
993 ir_node *main_end_bl;
994 int main_end_bl_arity;
997 /* assert(exc_handling == 1 || no exceptions. ) */
999 for (i = 0; i < arity; i++) {
1000 ir_node *ret = get_irn_n(end_bl, i);
1002 if (is_fragile_op(skip_Proj(ret)) || (get_irn_op(skip_Proj(ret)) == op_Raise)) {
1003 cf_pred[n_exc] = ret;
1007 main_end_bl = get_irg_end_block(current_ir_graph);
1008 main_end_bl_arity = get_irn_arity(main_end_bl);
1009 end_preds = (ir_node **) malloc ((n_exc + main_end_bl_arity) * sizeof (ir_node *));
1011 for (i = 0; i < main_end_bl_arity; ++i)
1012 end_preds[i] = get_irn_n(main_end_bl, i);
1013 for (i = 0; i < n_exc; ++i)
1014 end_preds[main_end_bl_arity + i] = cf_pred[i];
1015 set_irn_in(main_end_bl, n_exc + main_end_bl_arity, end_preds);
1016 set_Tuple_pred(call, pn_Call_X_except, new_Bad());
1017 set_Tuple_pred(call, pn_Call_M_except, new_Bad());
1023 #if 0 /* old. now better, correcter, faster implementation. */
1025 /* -- If the exception control flow from the inlined Call directly
1026 branched to the end block we now have the following control
1027 flow predecessor pattern: ProjX -> Tuple -> Jmp. We must
1028 remove the Jmp along with it's empty block and add Jmp's
1029 predecessors as predecessors of this end block. No problem if
1030 there is no exception, because then branches Bad to End which
1032 @@@ can't we know this beforehand: by getting the Proj(1) from
1033 the Call link list and checking whether it goes to Proj. */
1034 /* find the problematic predecessor of the end block. */
1035 end_bl = get_irg_end_block(current_ir_graph);
1036 for (i = 0; i < get_Block_n_cfgpreds(end_bl); i++) {
1037 cf_op = get_Block_cfgpred(end_bl, i);
1038 if (get_irn_op(cf_op) == op_Proj) {
1039 cf_op = get_Proj_pred(cf_op);
1040 if ((get_irn_op(cf_op) == op_Tuple) && (cf_op == call)) {
1041 /* There are unoptimized tuples from inlineing before when no exc */
1042 assert(get_Proj_proj(get_Block_cfgpred(end_bl, i)) == pn_Call_X_except);
1043 cf_op = get_Tuple_pred(cf_op, pn_Call_X_except);
1044 assert(get_irn_op(cf_op) == op_Jmp);
1050 if (i < get_Block_n_cfgpreds(end_bl)) {
1051 bl = get_nodes_block(cf_op);
1052 arity = get_Block_n_cfgpreds(end_bl) + get_Block_n_cfgpreds(bl) - 1;
1053 cf_pred = (ir_node **) malloc (arity * sizeof (ir_node *));
1054 for (j = 0; j < i; j++)
1055 cf_pred[j] = get_Block_cfgpred(end_bl, j);
1056 for (j = j; j < i + get_Block_n_cfgpreds(bl); j++)
1057 cf_pred[j] = get_Block_cfgpred(bl, j-i);
1058 for (j = j; j < arity; j++)
1059 cf_pred[j] = get_Block_cfgpred(end_bl, j-get_Block_n_cfgpreds(bl) +1);
1060 set_irn_in(end_bl, arity, cf_pred);
1062 /* Remove the exception pred from post-call Tuple. */
1063 set_Tuple_pred(call, pn_Call_X_except, new_Bad());
1068 /* -- Turn cse back on. -- */
1069 set_optimize(rem_opt);
1074 /********************************************************************/
1075 /* Apply inlineing to small methods. */
1076 /********************************************************************/
1078 /* It makes no sense to inline too many calls in one procedure. Anyways,
1079 I didn't get a version with NEW_ARR_F to run. */
1080 #define MAX_INLINE 1024
1083 * environment for inlining small irgs
1085 typedef struct _inline_env_t {
1087 ir_node *calls[MAX_INLINE];
1091 * Returns the irg called from a Call node. If the irg is not
1092 * known, NULL is returned.
1094 static ir_graph *get_call_called_irg(ir_node *call) {
1096 ir_graph *called_irg = NULL;
1098 assert(get_irn_op(call) == op_Call);
1100 addr = get_Call_ptr(call);
1101 if ((get_irn_op(addr) == op_SymConst) && (get_SymConst_kind (addr) == symconst_addr_ent)) {
1102 called_irg = get_entity_irg(get_SymConst_entity(addr));
1108 static void collect_calls(ir_node *call, void *env) {
1111 if (get_irn_op(call) != op_Call) return;
1113 addr = get_Call_ptr(call);
1115 if (get_irn_op(addr) == op_SymConst) {
1116 if (get_SymConst_kind(addr) == symconst_addr_ent) {
1117 ir_graph *called_irg = get_entity_irg(get_SymConst_entity(addr));
1118 inline_env_t *ienv = (inline_env_t *)env;
1119 if (called_irg && ienv->pos < MAX_INLINE) {
1120 /* The Call node calls a locally defined method. Remember to inline. */
1121 ienv->calls[ienv->pos++] = call;
1128 * Inlines all small methods at call sites where the called address comes
1129 * from a Const node that references the entity representing the called
1131 * The size argument is a rough measure for the code size of the method:
1132 * Methods where the obstack containing the firm graph is smaller than
1135 void inline_small_irgs(ir_graph *irg, int size) {
1137 ir_graph *rem = current_ir_graph;
1138 inline_env_t env /* = {0, NULL}*/;
1140 if (!(get_opt_optimize() && get_opt_inline())) return;
1142 current_ir_graph = irg;
1143 /* Handle graph state */
1144 assert(get_irg_phase_state(current_ir_graph) != phase_building);
1145 free_callee_info(current_ir_graph);
1147 /* Find Call nodes to inline.
1148 (We can not inline during a walk of the graph, as inlineing the same
1149 method several times changes the visited flag of the walked graph:
1150 after the first inlineing visited of the callee equals visited of
1151 the caller. With the next inlineing both are increased.) */
1153 irg_walk(get_irg_end(irg), NULL, collect_calls, &env);
1155 if ((env.pos > 0) && (env.pos < MAX_INLINE)) {
1156 /* There are calls to inline */
1157 collect_phiprojs(irg);
1158 for (i = 0; i < env.pos; i++) {
1160 callee = get_entity_irg(get_SymConst_entity(get_Call_ptr(env.calls[i])));
1161 if (((_obstack_memory_used(callee->obst) - obstack_room(callee->obst)) < size) ||
1162 (get_irg_inline_property(callee) == irg_inline_forced)) {
1163 inline_method(env.calls[i], callee);
1168 current_ir_graph = rem;
1172 * Environment for inlining irgs.
1175 int n_nodes; /**< Nodes in graph except Id, Tuple, Proj, Start, End */
1176 int n_nodes_orig; /**< for statistics */
1177 eset *call_nodes; /**< All call nodes in this graph */
1179 int n_call_nodes_orig; /**< for statistics */
1180 int n_callers; /**< Number of known graphs that call this graphs. */
1181 int n_callers_orig; /**< for statistics */
1184 static inline_irg_env *new_inline_irg_env(void) {
1185 inline_irg_env *env = malloc(sizeof(inline_irg_env));
1186 env->n_nodes = -2; /* uncount Start, End */
1187 env->n_nodes_orig = -2; /* uncount Start, End */
1188 env->call_nodes = eset_create();
1189 env->n_call_nodes = 0;
1190 env->n_call_nodes_orig = 0;
1192 env->n_callers_orig = 0;
1196 static void free_inline_irg_env(inline_irg_env *env) {
1197 eset_destroy(env->call_nodes);
1201 static void collect_calls2(ir_node *call, void *env) {
1202 inline_irg_env *x = (inline_irg_env *)env;
1203 ir_op *op = get_irn_op(call);
1206 /* count nodes in irg */
1207 if (op != op_Proj && op != op_Tuple && op != op_Sync) {
1212 if (op != op_Call) return;
1214 /* collect all call nodes */
1215 eset_insert(x->call_nodes, (void *)call);
1217 x->n_call_nodes_orig++;
1219 /* count all static callers */
1220 callee = get_call_called_irg(call);
1222 ((inline_irg_env *)get_irg_link(callee))->n_callers++;
1223 ((inline_irg_env *)get_irg_link(callee))->n_callers_orig++;
1227 INLINE static int is_leave(ir_graph *irg) {
1228 return (((inline_irg_env *)get_irg_link(irg))->n_call_nodes == 0);
1231 INLINE static int is_smaller(ir_graph *callee, int size) {
1232 return (((inline_irg_env *)get_irg_link(callee))->n_nodes < size);
1237 * Inlines small leave methods at call sites where the called address comes
1238 * from a Const node that references the entity representing the called
1240 * The size argument is a rough measure for the code size of the method:
1241 * Methods where the obstack containing the firm graph is smaller than
1244 void inline_leave_functions(int maxsize, int leavesize, int size) {
1245 inline_irg_env *env;
1246 int i, n_irgs = get_irp_n_irgs();
1247 ir_graph *rem = current_ir_graph;
1250 if (!(get_opt_optimize() && get_opt_inline())) return;
1252 /* extend all irgs by a temporary data structure for inlineing. */
1253 for (i = 0; i < n_irgs; ++i)
1254 set_irg_link(get_irp_irg(i), new_inline_irg_env());
1256 /* Precompute information in temporary data structure. */
1257 for (i = 0; i < n_irgs; ++i) {
1258 current_ir_graph = get_irp_irg(i);
1259 assert(get_irg_phase_state(current_ir_graph) != phase_building);
1260 free_callee_info(current_ir_graph);
1262 irg_walk(get_irg_end(current_ir_graph), NULL, collect_calls2,
1263 get_irg_link(current_ir_graph));
1266 /* -- and now inline. -- */
1268 /* Inline leaves recursively -- we might construct new leaves. */
1269 while (did_inline) {
1272 for (i = 0; i < n_irgs; ++i) {
1274 int phiproj_computed = 0;
1276 current_ir_graph = get_irp_irg(i);
1277 env = (inline_irg_env *)get_irg_link(current_ir_graph);
1279 for (call = eset_first(env->call_nodes); call; call = eset_next(env->call_nodes)) {
1280 if (get_irn_op(call) == op_Tuple) continue; /* We already inlined. */
1281 ir_graph *callee = get_call_called_irg(call);
1283 if (env->n_nodes > maxsize) continue; // break;
1285 if (callee && (is_leave(callee) && is_smaller(callee, leavesize))) {
1286 if (!phiproj_computed) {
1287 phiproj_computed = 1;
1288 collect_phiprojs(current_ir_graph);
1290 did_inline = inline_method(call, callee);
1293 /* Do some statistics */
1294 inline_irg_env *callee_env = (inline_irg_env *)get_irg_link(callee);
1295 env->n_call_nodes --;
1296 env->n_nodes += callee_env->n_nodes;
1297 callee_env->n_callers--;
1304 /* inline other small functions. */
1305 for (i = 0; i < n_irgs; ++i) {
1308 int phiproj_computed = 0;
1310 current_ir_graph = get_irp_irg(i);
1311 env = (inline_irg_env *)get_irg_link(current_ir_graph);
1313 /* we can not walk and change a set, nor remove from it.
1315 walkset = env->call_nodes;
1316 env->call_nodes = eset_create();
1317 for (call = eset_first(walkset); call; call = eset_next(walkset)) {
1318 if (get_irn_op(call) == op_Tuple) continue; /* We already inlined. */
1319 ir_graph *callee = get_call_called_irg(call);
1322 ((is_smaller(callee, size) && (env->n_nodes < maxsize)) || /* small function */
1323 (get_irg_inline_property(callee) == irg_inline_forced))) {
1324 if (!phiproj_computed) {
1325 phiproj_computed = 1;
1326 collect_phiprojs(current_ir_graph);
1328 if (inline_method(call, callee)) {
1329 inline_irg_env *callee_env = (inline_irg_env *)get_irg_link(callee);
1330 env->n_call_nodes--;
1331 eset_insert_all(env->call_nodes, callee_env->call_nodes); /* @@@ ??? This are the wrong nodes !? Not the copied ones. */
1332 env->n_call_nodes += callee_env->n_call_nodes;
1333 env->n_nodes += callee_env->n_nodes;
1334 callee_env->n_callers--;
1337 eset_insert(env->call_nodes, call);
1340 eset_destroy(walkset);
1343 for (i = 0; i < n_irgs; ++i) {
1344 current_ir_graph = get_irp_irg(i);
1346 env = (inline_irg_env *)get_irg_link(current_ir_graph);
1347 if ((env->n_call_nodes_orig != env->n_call_nodes) ||
1348 (env->n_callers_orig != env->n_callers))
1349 printf("Nodes:%3d ->%3d, calls:%3d ->%3d, callers:%3d ->%3d, -- %s\n",
1350 env->n_nodes_orig, env->n_nodes, env->n_call_nodes_orig, env->n_call_nodes,
1351 env->n_callers_orig, env->n_callers,
1352 get_entity_name(get_irg_entity(current_ir_graph)));
1354 free_inline_irg_env((inline_irg_env *)get_irg_link(current_ir_graph));
1357 current_ir_graph = rem;
1360 /*******************************************************************/
1361 /* Code Placement. Pins all floating nodes to a block where they */
1362 /* will be executed only if needed. */
1363 /*******************************************************************/
1366 * Find the earliest correct block for N. --- Place N into the
1367 * same Block as its dominance-deepest Input.
1370 place_floats_early(ir_node *n, pdeq *worklist)
1372 int i, start, irn_arity;
1374 /* we must not run into an infinite loop */
1375 assert (irn_not_visited(n));
1376 mark_irn_visited(n);
1378 /* Place floating nodes. */
1379 if (get_op_pinned(get_irn_op(n)) == op_pin_state_floats) {
1381 ir_node *b = new_Bad(); /* The block to place this node in */
1382 int bad_recursion = is_Bad(get_nodes_block(n));
1384 assert(get_irn_op(n) != op_Block);
1386 if ((get_irn_op(n) == op_Const) ||
1387 (get_irn_op(n) == op_SymConst) ||
1389 (get_irn_op(n) == op_Unknown)) {
1390 /* These nodes will not be placed by the loop below. */
1391 b = get_irg_start_block(current_ir_graph);
1395 /* find the block for this node. */
1396 irn_arity = get_irn_arity(n);
1397 for (i = 0; i < irn_arity; i++) {
1398 ir_node *dep = get_irn_n(n, i);
1401 if ((irn_not_visited(dep))
1402 && (get_op_pinned(get_irn_op(dep)) == op_pin_state_floats)) {
1403 place_floats_early(dep, worklist);
1407 * A node in the Bad block must stay in the bad block,
1408 * so don't compute a new block for it.
1413 /* Because all loops contain at least one op_pin_state_pinned node, now all
1414 our inputs are either op_pin_state_pinned or place_early has already
1415 been finished on them. We do not have any unfinished inputs! */
1416 dep_block = get_nodes_block(dep);
1417 if ((!is_Bad(dep_block)) &&
1418 (get_Block_dom_depth(dep_block) > depth)) {
1420 depth = get_Block_dom_depth(dep_block);
1422 /* Avoid that the node is placed in the Start block */
1423 if ((depth == 1) && (get_Block_dom_depth(get_nodes_block(n)) > 1)) {
1424 b = get_Block_cfg_out(get_irg_start_block(current_ir_graph), 0);
1425 assert(b != get_irg_start_block(current_ir_graph));
1429 set_nodes_block(n, b);
1432 /* Add predecessors of non floating nodes on worklist. */
1433 start = (get_irn_op(n) == op_Block) ? 0 : -1;
1434 irn_arity = get_irn_arity(n);
1435 for (i = start; i < irn_arity; i++) {
1436 ir_node *pred = get_irn_n(n, i);
1437 if (irn_not_visited(pred)) {
1438 pdeq_putr (worklist, pred);
1444 * Floating nodes form subgraphs that begin at nodes as Const, Load,
1445 * Start, Call and that end at op_pin_state_pinned nodes as Store, Call. Place_early
1446 * places all floating nodes reachable from its argument through floating
1447 * nodes and adds all beginnings at op_pin_state_pinned nodes to the worklist.
1449 static INLINE void place_early(pdeq *worklist) {
1451 inc_irg_visited(current_ir_graph);
1453 /* this inits the worklist */
1454 place_floats_early(get_irg_end(current_ir_graph), worklist);
1456 /* Work the content of the worklist. */
1457 while (!pdeq_empty (worklist)) {
1458 ir_node *n = pdeq_getl (worklist);
1459 if (irn_not_visited(n)) place_floats_early(n, worklist);
1462 set_irg_outs_inconsistent(current_ir_graph);
1463 current_ir_graph->op_pin_state_pinned = op_pin_state_pinned;
1467 /** Deepest common dominance ancestor of DCA and CONSUMER of PRODUCER.
1468 * I.e., DCA is the block where we might place PRODUCER.
1469 * A data flow edge points from producer to consumer.
1472 consumer_dom_dca (ir_node *dca, ir_node *consumer, ir_node *producer)
1474 ir_node *block = NULL;
1476 /* Compute the latest block into which we can place a node so that it is
1478 if (get_irn_op(consumer) == op_Phi) {
1479 /* our consumer is a Phi-node, the effective use is in all those
1480 blocks through which the Phi-node reaches producer */
1482 ir_node *phi_block = get_nodes_block(consumer);
1483 irn_arity = get_irn_arity(consumer);
1485 for (i = 0; i < irn_arity; i++) {
1486 if (get_irn_n(consumer, i) == producer) {
1487 block = get_nodes_block(get_Block_cfgpred(phi_block, i));
1491 assert(is_no_Block(consumer));
1492 block = get_nodes_block(consumer);
1495 /* Compute the deepest common ancestor of block and dca. */
1497 if (!dca) return block;
1498 while (get_Block_dom_depth(block) > get_Block_dom_depth(dca))
1499 block = get_Block_idom(block);
1500 while (get_Block_dom_depth(dca) > get_Block_dom_depth(block)) {
1501 dca = get_Block_idom(dca);
1503 while (block != dca)
1504 { block = get_Block_idom(block); dca = get_Block_idom(dca); }
1509 static INLINE int get_irn_loop_depth(ir_node *n) {
1510 return get_loop_depth(get_irn_loop(n));
1514 * Move n to a block with less loop depth than it's current block. The
1515 * new block must be dominated by early.
1518 move_out_of_loops (ir_node *n, ir_node *early)
1520 ir_node *best, *dca;
1524 /* Find the region deepest in the dominator tree dominating
1525 dca with the least loop nesting depth, but still dominated
1526 by our early placement. */
1527 dca = get_nodes_block(n);
1529 while (dca != early) {
1530 dca = get_Block_idom(dca);
1531 if (!dca || is_Bad(dca)) break; /* may be Bad if not reachable from Start */
1532 if (get_irn_loop_depth(dca) < get_irn_loop_depth(best)) {
1536 if (best != get_nodes_block(n)) {
1538 printf("Moving out of loop: "); DDMN(n);
1539 printf(" Outermost block: "); DDMN(early);
1540 printf(" Best block: "); DDMN(best);
1541 printf(" Innermost block: "); DDMN(get_nodes_block(n));
1543 set_nodes_block(n, best);
1548 * Find the latest legal block for N and place N into the
1549 * `optimal' Block between the latest and earliest legal block.
1550 * The `optimal' block is the dominance-deepest block of those
1551 * with the least loop-nesting-depth. This places N out of as many
1552 * loops as possible and then makes it as control dependant as
1556 place_floats_late(ir_node *n, pdeq *worklist)
1561 assert (irn_not_visited(n)); /* no multiple placement */
1563 mark_irn_visited(n);
1565 /* no need to place block nodes, control nodes are already placed. */
1566 if ((get_irn_op(n) != op_Block) &&
1568 (get_irn_mode(n) != mode_X)) {
1569 /* Remember the early placement of this block to move it
1570 out of loop no further than the early placement. */
1571 early = get_nodes_block(n);
1573 /* Do not move code not reachable from Start. For
1574 * these we could not compute dominator information. */
1575 if (is_Bad(early) || get_Block_dom_depth(early) == -1)
1578 /* Assure that our users are all placed, except the Phi-nodes.
1579 --- Each data flow cycle contains at least one Phi-node. We
1580 have to break the `user has to be placed before the
1581 producer' dependence cycle and the Phi-nodes are the
1582 place to do so, because we need to base our placement on the
1583 final region of our users, which is OK with Phi-nodes, as they
1584 are op_pin_state_pinned, and they never have to be placed after a
1585 producer of one of their inputs in the same block anyway. */
1586 for (i = 0; i < get_irn_n_outs(n); i++) {
1587 ir_node *succ = get_irn_out(n, i);
1588 if (irn_not_visited(succ) && (get_irn_op(succ) != op_Phi))
1589 place_floats_late(succ, worklist);
1592 /* We have to determine the final block of this node... except for
1594 if ((get_op_pinned(get_irn_op(n)) == op_pin_state_floats) &&
1595 (get_irn_op(n) != op_Const) &&
1596 (get_irn_op(n) != op_SymConst)) {
1597 ir_node *dca = NULL; /* deepest common ancestor in the
1598 dominator tree of all nodes'
1599 blocks depending on us; our final
1600 placement has to dominate DCA. */
1601 for (i = 0; i < get_irn_n_outs(n); i++) {
1602 ir_node *out = get_irn_out(n, i);
1603 /* ignore if out is in dead code */
1604 ir_node *outbl = get_nodes_block(out);
1605 if (is_Bad(outbl) || get_Block_dom_depth(outbl) == -1)
1607 dca = consumer_dom_dca (dca, out, n);
1610 set_nodes_block(n, dca);
1612 move_out_of_loops (n, early);
1614 /* else all outs are in dead code */
1618 /* Add predecessors of all non-floating nodes on list. (Those of floating
1619 nodes are placeded already and therefore are marked.) */
1620 for (i = 0; i < get_irn_n_outs(n); i++) {
1621 if (irn_not_visited(get_irn_out(n, i))) {
1622 pdeq_putr (worklist, get_irn_out(n, i));
1627 static INLINE void place_late(pdeq *worklist) {
1629 inc_irg_visited(current_ir_graph);
1631 /* This fills the worklist initially. */
1632 place_floats_late(get_irg_start_block(current_ir_graph), worklist);
1634 /* And now empty the worklist again... */
1635 while (!pdeq_empty (worklist)) {
1636 ir_node *n = pdeq_getl (worklist);
1637 if (irn_not_visited(n)) place_floats_late(n, worklist);
1641 void place_code(ir_graph *irg) {
1643 ir_graph *rem = current_ir_graph;
1645 current_ir_graph = irg;
1647 if (!(get_opt_optimize() && get_opt_global_cse())) return;
1649 /* Handle graph state */
1650 assert(get_irg_phase_state(irg) != phase_building);
1651 if (get_irg_dom_state(irg) != dom_consistent)
1654 if (1 || get_irg_loopinfo_state(irg) != loopinfo_consistent) {
1655 free_loop_information(irg);
1656 construct_backedges(irg);
1659 /* Place all floating nodes as early as possible. This guarantees
1660 a legal code placement. */
1661 worklist = new_pdeq();
1662 place_early(worklist);
1664 /* place_early invalidates the outs, place_late needs them. */
1666 /* Now move the nodes down in the dominator tree. This reduces the
1667 unnecessary executions of the node. */
1668 place_late(worklist);
1670 set_irg_outs_inconsistent(current_ir_graph);
1671 set_irg_loopinfo_inconsistent(current_ir_graph);
1673 current_ir_graph = rem;
1677 * Called by walker of remove_critical_cf_edges().
1679 * Place an empty block to an edge between a blocks of multiple
1680 * predecessors and a block of multiple successors.
1683 * @param env Environment of walker. This field is unused and has
1686 static void walk_critical_cf_edges(ir_node *n, void *env) {
1688 ir_node *pre, *block, **in, *jmp;
1690 /* Block has multiple predecessors */
1691 if ((op_Block == get_irn_op(n)) &&
1692 (get_irn_arity(n) > 1)) {
1693 arity = get_irn_arity(n);
1695 if (n == get_irg_end_block(current_ir_graph))
1696 return; /* No use to add a block here. */
1698 for (i=0; i<arity; i++) {
1699 pre = get_irn_n(n, i);
1700 /* Predecessor has multiple successors. Insert new flow edge */
1701 if ((NULL != pre) &&
1702 (op_Proj == get_irn_op(pre)) &&
1703 op_Raise != get_irn_op(skip_Proj(pre))) {
1705 /* set predecessor array for new block */
1706 in = NEW_ARR_D (ir_node *, current_ir_graph->obst, 1);
1707 /* set predecessor of new block */
1709 block = new_Block(1, in);
1710 /* insert new jmp node to new block */
1711 set_cur_block(block);
1714 /* set successor of new block */
1715 set_irn_n(n, i, jmp);
1717 } /* predecessor has multiple successors */
1718 } /* for all predecessors */
1719 } /* n is a block */
1722 void remove_critical_cf_edges(ir_graph *irg) {
1723 if (get_opt_critical_edges())
1724 irg_walk_graph(irg, NULL, walk_critical_cf_edges, NULL);