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);
91 local_optimize_graph (ir_graph *irg) {
92 ir_graph *rem = current_ir_graph;
93 current_ir_graph = irg;
95 /* Handle graph state */
96 assert(get_irg_phase_state(irg) != phase_building);
97 if (get_opt_global_cse())
98 set_irg_pinned(current_ir_graph, floats);
99 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
100 set_irg_outs_inconsistent(current_ir_graph);
101 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
102 set_irg_dom_inconsistent(current_ir_graph);
103 set_irg_loopinfo_inconsistent(current_ir_graph);
106 /* Clean the value_table in irg for the cse. */
107 del_identities(irg->value_table);
108 irg->value_table = new_identities();
110 /* walk over the graph */
111 irg_walk(irg->end, init_link, optimize_in_place_wrapper, NULL);
113 current_ir_graph = rem;
116 /*------------------------------------------------------------------*/
117 /* Routines for dead node elimination / copying garbage collection */
118 /* of the obstack. */
119 /*------------------------------------------------------------------*/
122 * Remember the new node in the old node by using a field all nodes have.
125 set_new_node (ir_node *old, ir_node *new)
131 * Get this new node, before the old node is forgotton.
133 static INLINE ir_node *
134 get_new_node (ir_node * n)
140 * We use the block_visited flag to mark that we have computed the
141 * number of useful predecessors for this block.
142 * Further we encode the new arity in this flag in the old blocks.
143 * Remembering the arity is useful, as it saves a lot of pointer
144 * accesses. This function is called for all Phi and Block nodes
148 compute_new_arity(ir_node *b) {
149 int i, res, irn_arity;
152 irg_v = get_irg_block_visited(current_ir_graph);
153 block_v = get_Block_block_visited(b);
154 if (block_v >= irg_v) {
155 /* we computed the number of preds for this block and saved it in the
157 return block_v - irg_v;
159 /* compute the number of good predecessors */
160 res = irn_arity = get_irn_arity(b);
161 for (i = 0; i < irn_arity; i++)
162 if (get_irn_opcode(get_irn_n(b, i)) == iro_Bad) res--;
163 /* save it in the flag. */
164 set_Block_block_visited(b, irg_v + res);
169 /* TODO: add an ir_op operation */
170 static INLINE void new_backedge_info(ir_node *n) {
171 switch(get_irn_opcode(n)) {
173 n->attr.block.cg_backedge = NULL;
174 n->attr.block.backedge = new_backedge_arr(current_ir_graph->obst, get_irn_arity(n));
177 n->attr.phi_backedge = new_backedge_arr(current_ir_graph->obst, get_irn_arity(n));
180 n->attr.filter.backedge = new_backedge_arr(current_ir_graph->obst, get_irn_arity(n));
187 * Copies the node to the new obstack. The Ins of the new node point to
188 * the predecessors on the old obstack. For block/phi nodes not all
189 * predecessors might be copied. n->link points to the new node.
190 * For Phi and Block nodes the function allocates in-arrays with an arity
191 * only for useful predecessors. The arity is determined by counting
192 * the non-bad predecessors of the block.
195 copy_node (ir_node *n, void *env) {
198 opcode op = get_irn_opcode(n);
199 /* The end node looses it's flexible in array. This doesn't matter,
200 as dead node elimination builds End by hand, inlineing doesn't use
202 /* assert(n->op == op_End || ((_ARR_DESCR(n->in))->cookie != ARR_F_MAGIC)); */
205 /* node copied already */
207 } else if (op == iro_Block) {
209 new_arity = compute_new_arity(n);
210 n->attr.block.graph_arr = NULL;
212 block = get_nodes_Block(n);
213 if (get_irn_opcode(n) == iro_Phi) {
214 new_arity = compute_new_arity(block);
216 new_arity = get_irn_arity(n);
219 nn = new_ir_node(get_irn_dbg_info(n),
226 /* Copy the attributes. These might point to additional data. If this
227 was allocated on the old obstack the pointers now are dangling. This
228 frees e.g. the memory of the graph_arr allocated in new_immBlock. */
230 new_backedge_info(nn);
233 /* printf("\n old node: "); DDMSG2(n);
234 printf(" new node: "); DDMSG2(nn); */
239 * Copies new predecessors of old node to new node remembered in link.
240 * Spare the Bad predecessors of Phi and Block nodes.
243 copy_preds (ir_node *n, void *env) {
247 nn = get_new_node(n);
249 /* printf("\n old node: "); DDMSG2(n);
250 printf(" new node: "); DDMSG2(nn);
251 printf(" arities: old: %d, new: %d\n", get_irn_arity(n), get_irn_arity(nn)); */
253 if (get_irn_opcode(n) == iro_Block) {
254 /* Don't copy Bad nodes. */
256 irn_arity = get_irn_arity(n);
257 for (i = 0; i < irn_arity; i++)
258 if (get_irn_opcode(get_irn_n(n, i)) != iro_Bad) {
259 set_irn_n (nn, j, get_new_node(get_irn_n(n, i)));
260 /*if (is_backedge(n, i)) set_backedge(nn, j);*/
263 /* repair the block visited flag from above misuse. Repair it in both
264 graphs so that the old one can still be used. */
265 set_Block_block_visited(nn, 0);
266 set_Block_block_visited(n, 0);
267 /* Local optimization could not merge two subsequent blocks if
268 in array contained Bads. Now it's possible.
269 We don't call optimize_in_place as it requires
270 that the fields in ir_graph are set properly. */
271 if ((get_opt_control_flow_straightening()) &&
272 (get_Block_n_cfgpreds(nn) == 1) &&
273 (get_irn_op(get_Block_cfgpred(nn, 0)) == op_Jmp)) {
274 ir_node *old = get_nodes_Block(get_Block_cfgpred(nn, 0));
276 /* Jmp jumps into the block it is in -- deal self cycle. */
277 assert(is_Bad(get_new_node(get_irg_bad(current_ir_graph))));
278 exchange(nn, get_new_node(get_irg_bad(current_ir_graph)));
283 } else if (get_irn_opcode(n) == iro_Phi) {
284 /* Don't copy node if corresponding predecessor in block is Bad.
285 The Block itself should not be Bad. */
286 block = get_nodes_Block(n);
287 set_irn_n (nn, -1, get_new_node(block));
289 irn_arity = get_irn_arity(n);
290 for (i = 0; i < irn_arity; i++)
291 if (get_irn_opcode(get_irn_n(block, i)) != iro_Bad) {
292 set_irn_n (nn, j, get_new_node(get_irn_n(n, i)));
293 /*if (is_backedge(n, i)) set_backedge(nn, j);*/
296 /* If the pre walker reached this Phi after the post walker visited the
297 block block_visited is > 0. */
298 set_Block_block_visited(get_nodes_Block(n), 0);
299 /* Compacting the Phi's ins might generate Phis with only one
301 if (get_irn_arity(n) == 1)
302 exchange(n, get_irn_n(n, 0));
304 irn_arity = get_irn_arity(n);
305 for (i = -1; i < irn_arity; i++)
306 set_irn_n (nn, i, get_new_node(get_irn_n(n, i)));
308 /* Now the new node is complete. We can add it to the hash table for cse.
309 @@@ inlinening aborts if we identify End. Why? */
310 if(get_irn_op(nn) != op_End)
311 add_identities (current_ir_graph->value_table, nn);
315 * Copies the graph recursively, compacts the keepalive of the end node.
319 ir_node *oe, *ne, *ob, *nb; /* old end, new end, old bad, new bad */
320 ir_node *ka; /* keep alive */
323 oe = get_irg_end(current_ir_graph);
324 /* copy the end node by hand, allocate dynamic in array! */
325 ne = new_ir_node(get_irn_dbg_info(oe),
332 /* Copy the attributes. Well, there might be some in the future... */
334 set_new_node(oe, ne);
336 ob = get_irg_bad(current_ir_graph);
337 nb = new_ir_node(get_irn_dbg_info(ob),
344 set_new_node(ob, nb);
346 /* copy the live nodes */
347 irg_walk(get_nodes_Block(oe), copy_node, copy_preds, NULL);
348 /* copy_preds for the end node ... */
349 set_nodes_Block(ne, get_new_node(get_nodes_Block(oe)));
350 set_nodes_Block(nb, get_new_node(get_nodes_Block(ob)));
352 /*- ... and now the keep alives. -*/
353 /* First pick the not marked block nodes and walk them. We must pick these
354 first as else we will oversee blocks reachable from Phis. */
355 irn_arity = get_irn_arity(oe);
356 for (i = 0; i < irn_arity; i++) {
357 ka = get_irn_intra_n(oe, i);
358 if ((get_irn_op(ka) == op_Block) &&
359 (get_irn_visited(ka) < get_irg_visited(current_ir_graph))) {
360 /* We must keep the block alive and copy everything reachable */
361 set_irg_visited(current_ir_graph, get_irg_visited(current_ir_graph)-1);
362 irg_walk(ka, copy_node, copy_preds, NULL);
363 add_End_keepalive(ne, get_new_node(ka));
367 /* Now pick the Phis. Here we will keep all! */
368 irn_arity = get_irn_arity(oe);
369 for (i = 0; i < irn_arity; i++) {
370 ka = get_irn_intra_n(oe, i);
371 if ((get_irn_op(ka) == op_Phi)) {
372 if (get_irn_visited(ka) < get_irg_visited(current_ir_graph)) {
373 /* We didn't copy the Phi yet. */
374 set_irg_visited(current_ir_graph, get_irg_visited(current_ir_graph)-1);
375 irg_walk(ka, copy_node, copy_preds, NULL);
377 add_End_keepalive(ne, get_new_node(ka));
383 * Copies the graph reachable from current_ir_graph->end to the obstack
384 * in current_ir_graph and fixes the environment.
385 * Then fixes the fields in current_ir_graph containing nodes of the
389 copy_graph_env (void) {
391 /* Not all nodes remembered in current_ir_graph might be reachable
392 from the end node. Assure their link is set to NULL, so that
393 we can test whether new nodes have been computed. */
394 set_irn_link(get_irg_frame (current_ir_graph), NULL);
395 set_irn_link(get_irg_globals (current_ir_graph), NULL);
396 set_irn_link(get_irg_args (current_ir_graph), NULL);
397 set_irn_link(get_irg_initial_mem(current_ir_graph), NULL);
399 /* we use the block walk flag for removing Bads from Blocks ins. */
400 inc_irg_block_visited(current_ir_graph);
405 /* fix the fields in current_ir_graph */
406 old_end = get_irg_end(current_ir_graph);
407 set_irg_end (current_ir_graph, get_new_node(old_end));
408 set_irg_end_except (current_ir_graph, get_irg_end(current_ir_graph));
409 set_irg_end_reg (current_ir_graph, get_irg_end(current_ir_graph));
411 set_irg_end_block (current_ir_graph, get_new_node(get_irg_end_block(current_ir_graph)));
412 if (get_irn_link(get_irg_frame(current_ir_graph)) == NULL) {
413 copy_node (get_irg_frame(current_ir_graph), NULL);
414 copy_preds(get_irg_frame(current_ir_graph), NULL);
416 if (get_irn_link(get_irg_globals(current_ir_graph)) == NULL) {
417 copy_node (get_irg_globals(current_ir_graph), NULL);
418 copy_preds(get_irg_globals(current_ir_graph), NULL);
420 if (get_irn_link(get_irg_initial_mem(current_ir_graph)) == NULL) {
421 copy_node (get_irg_initial_mem(current_ir_graph), NULL);
422 copy_preds(get_irg_initial_mem(current_ir_graph), NULL);
424 if (get_irn_link(get_irg_args(current_ir_graph)) == NULL) {
425 copy_node (get_irg_args(current_ir_graph), NULL);
426 copy_preds(get_irg_args(current_ir_graph), NULL);
428 set_irg_start (current_ir_graph, get_new_node(get_irg_start(current_ir_graph)));
430 set_irg_start_block(current_ir_graph,
431 get_new_node(get_irg_start_block(current_ir_graph)));
432 set_irg_frame (current_ir_graph, get_new_node(get_irg_frame(current_ir_graph)));
433 set_irg_globals (current_ir_graph, get_new_node(get_irg_globals(current_ir_graph)));
434 set_irg_initial_mem(current_ir_graph, get_new_node(get_irg_initial_mem(current_ir_graph)));
435 set_irg_args (current_ir_graph, get_new_node(get_irg_args(current_ir_graph)));
437 if (get_irn_link(get_irg_bad(current_ir_graph)) == NULL) {
438 copy_node(get_irg_bad(current_ir_graph), NULL);
439 copy_preds(get_irg_bad(current_ir_graph), NULL);
441 set_irg_bad(current_ir_graph, get_new_node(get_irg_bad(current_ir_graph)));
445 * Copies all reachable nodes to a new obstack. Removes bad inputs
446 * from block nodes and the corresponding inputs from Phi nodes.
447 * Merges single exit blocks with single entry blocks and removes
449 * Adds all new nodes to a new hash table for cse. Does not
450 * perform cse, so the hash table might contain common subexpressions.
453 dead_node_elimination(ir_graph *irg) {
455 int rem_ipview = interprocedural_view;
456 struct obstack *graveyard_obst = NULL;
457 struct obstack *rebirth_obst = NULL;
459 /* inform statistics that we started a dead-node elimination run */
460 stat_dead_node_elim_start(irg);
462 /* Remember external state of current_ir_graph. */
463 rem = current_ir_graph;
464 current_ir_graph = irg;
465 interprocedural_view = 0;
467 /* Handle graph state */
468 assert(get_irg_phase_state(current_ir_graph) != phase_building);
469 free_callee_info(current_ir_graph);
470 free_outs(current_ir_graph);
471 /* @@@ so far we loose loops when copying */
472 free_loop_information(current_ir_graph);
474 if (get_opt_optimize() && get_opt_dead_node_elimination()) {
476 /* A quiet place, where the old obstack can rest in peace,
477 until it will be cremated. */
478 graveyard_obst = irg->obst;
480 /* A new obstack, where the reachable nodes will be copied to. */
481 rebirth_obst = (struct obstack *) xmalloc (sizeof (struct obstack));
482 current_ir_graph->obst = rebirth_obst;
483 obstack_init (current_ir_graph->obst);
485 /* We also need a new hash table for cse */
486 del_identities (irg->value_table);
487 irg->value_table = new_identities ();
489 /* Copy the graph from the old to the new obstack */
492 /* Free memory from old unoptimized obstack */
493 obstack_free(graveyard_obst, 0); /* First empty the obstack ... */
494 xfree (graveyard_obst); /* ... then free it. */
497 /* inform statistics that the run is over */
498 stat_dead_node_elim_stop(irg);
500 current_ir_graph = rem;
501 interprocedural_view = rem_ipview;
505 * Relink bad predeseccors of a block and store the old in array to the
506 * link field. This function is called by relink_bad_predecessors().
507 * The array of link field starts with the block operand at position 0.
508 * If block has bad predecessors, create a new in array without bad preds.
509 * Otherwise let in array untouched.
511 static void relink_bad_block_predecessors(ir_node *n, void *env) {
512 ir_node **new_in, *irn;
513 int i, new_irn_n, old_irn_arity, new_irn_arity = 0;
515 /* if link field of block is NULL, look for bad predecessors otherwise
516 this is allready done */
517 if (get_irn_op(n) == op_Block &&
518 get_irn_link(n) == NULL) {
520 /* save old predecessors in link field (position 0 is the block operand)*/
521 set_irn_link(n, (void *)get_irn_in(n));
523 /* count predecessors without bad nodes */
524 old_irn_arity = get_irn_arity(n);
525 for (i = 0; i < old_irn_arity; i++)
526 if (!is_Bad(get_irn_n(n, i))) new_irn_arity++;
528 /* arity changing: set new predecessors without bad nodes */
529 if (new_irn_arity < old_irn_arity) {
530 /* get new predecessor array without Block predecessor */
531 new_in = NEW_ARR_D (ir_node *, current_ir_graph->obst, (new_irn_arity+1));
533 /* set new predeseccors in array */
536 for (i = 1; i < old_irn_arity; i++) {
537 irn = get_irn_n(n, i);
538 if (!is_Bad(irn)) new_in[new_irn_n++] = irn;
541 } /* ir node has bad predecessors */
543 } /* Block is not relinked */
547 * Relinks Bad predecesors from Bocks and Phis called by walker
548 * remove_bad_predecesors(). If n is a Block, call
549 * relink_bad_block_redecessors(). If n is a Phinode, call also the relinking
550 * function of Phi's Block. If this block has bad predecessors, relink preds
553 static void relink_bad_predecessors(ir_node *n, void *env) {
554 ir_node *block, **old_in;
555 int i, old_irn_arity, new_irn_arity;
557 /* relink bad predeseccors of a block */
558 if (get_irn_op(n) == op_Block)
559 relink_bad_block_predecessors(n, env);
561 /* If Phi node relink its block and its predecessors */
562 if (get_irn_op(n) == op_Phi) {
564 /* Relink predeseccors of phi's block */
565 block = get_nodes_Block(n);
566 if (get_irn_link(block) == NULL)
567 relink_bad_block_predecessors(block, env);
569 old_in = (ir_node **)get_irn_link(block); /* Of Phi's Block */
570 old_irn_arity = ARR_LEN(old_in);
572 /* Relink Phi predeseccors if count of predeseccors changed */
573 if (old_irn_arity != ARR_LEN(get_irn_in(block))) {
574 /* set new predeseccors in array
575 n->in[0] remains the same block */
577 for(i = 1; i < old_irn_arity; i++)
578 if (!is_Bad((ir_node *)old_in[i])) n->in[new_irn_arity++] = n->in[i];
580 ARR_SETLEN(ir_node *, n->in, new_irn_arity);
583 } /* n is a Phi node */
587 * Removes Bad Bad predecesors from Blocks and the corresponding
588 * inputs to Phi nodes as in dead_node_elimination but without
590 * On walking up set the link field to NULL, on walking down call
591 * relink_bad_predecessors() (This function stores the old in array
592 * to the link field and sets a new in array if arity of predecessors
595 void remove_bad_predecessors(ir_graph *irg) {
596 irg_walk_graph(irg, init_link, relink_bad_predecessors, NULL);
600 /*--------------------------------------------------------------------*/
601 /* Funcionality for inlining */
602 /*--------------------------------------------------------------------*/
605 * Copy node for inlineing. Updates attributes that change when
606 * inlineing but not for dead node elimination.
608 * Copies the node by calling copy_node and then updates the entity if
609 * it's a local one. env must be a pointer of the frame type of the
610 * inlined procedure. The new entities must be in the link field of
614 copy_node_inline (ir_node *n, void *env) {
616 type *frame_tp = (type *)env;
619 if (get_irn_op(n) == op_Sel) {
620 new = get_new_node (n);
621 assert(get_irn_op(new) == op_Sel);
622 if (get_entity_owner(get_Sel_entity(n)) == frame_tp) {
623 set_Sel_entity(new, get_entity_link(get_Sel_entity(n)));
625 } else if (get_irn_op(n) == op_Block) {
626 new = get_new_node (n);
627 new->attr.block.irg = current_ir_graph;
631 static void find_addr(ir_node *node, void *env)
633 if (get_irn_opcode(node) == iro_Proj) {
634 if (get_Proj_proj(node) == pn_Start_P_value_arg_base)
640 * currently, we cannot inline two cases:
641 * - call with compound arguments
642 * - graphs that take the address of a parameter
644 * check these condition here
646 static int can_inline(ir_node *call, ir_graph *called_graph)
648 type *call_type = get_Call_type(call);
649 int params, ress, i, res;
651 assert(is_method_type(call_type));
653 params = get_method_n_params(call_type);
654 ress = get_method_n_ress(call_type);
657 for (i = 0; i < params; ++i) {
658 type *p_type = get_method_param_type(call_type, i);
660 if (is_compound_type(p_type))
665 for (i = 0; i < ress; ++i) {
666 type *r_type = get_method_res_type(call_type, i);
668 if (is_compound_type(r_type))
673 irg_walk_graph(called_graph, find_addr, NULL, &res);
678 int inline_method(ir_node *call, ir_graph *called_graph) {
680 ir_node *post_call, *post_bl;
682 ir_node *end, *end_bl;
686 int arity, n_ret, n_exc, n_res, i, j, rem_opt, irn_arity;
689 irg_inline_property prop = get_irg_inline_property(called_graph);
691 if ( (prop != irg_inline_forced) && (!get_opt_optimize() || !get_opt_inline() ||
692 (prop == irg_inline_forbidden))) return 0;
696 * currently, we cannot inline two cases:
697 * - call with compound arguments
698 * - graphs that take the address of a parameter
700 if (! can_inline(call, called_graph))
703 /* -- Turn off optimizations, this can cause problems when allocating new nodes. -- */
704 rem_opt = get_opt_optimize();
707 /* Handle graph state */
708 assert(get_irg_phase_state(current_ir_graph) != phase_building);
709 assert(get_irg_pinned(current_ir_graph) == pinned);
710 assert(get_irg_pinned(called_graph) == pinned);
711 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
712 set_irg_outs_inconsistent(current_ir_graph);
713 set_irg_loopinfo_inconsistent(current_ir_graph);
715 /* -- Check preconditions -- */
716 assert(get_irn_op(call) == op_Call);
717 /* @@@ does not work for InterfaceIII.java after cgana
718 assert(get_Call_type(call) == get_entity_type(get_irg_ent(called_graph)));
719 assert(smaller_type(get_entity_type(get_irg_ent(called_graph)),
720 get_Call_type(call)));
722 assert(get_type_tpop(get_Call_type(call)) == type_method);
723 if (called_graph == current_ir_graph) {
724 set_optimize(rem_opt);
728 /* here we know we WILL inline, so inform the statistics */
729 stat_inline(call, called_graph);
731 /* -- Decide how to handle exception control flow: Is there a handler
732 for the Call node, or do we branch directly to End on an exception?
733 exc_handling: 0 There is a handler.
735 2 Exception handling not represented in Firm. -- */
737 ir_node *proj, *Mproj = NULL, *Xproj = NULL;
738 for (proj = (ir_node *)get_irn_link(call); proj; proj = (ir_node *)get_irn_link(proj)) {
739 assert(get_irn_op(proj) == op_Proj);
740 if (get_Proj_proj(proj) == pn_Call_X_except) Xproj = proj;
741 if (get_Proj_proj(proj) == pn_Call_M_except) Mproj = proj;
743 if (Mproj) { assert(Xproj); exc_handling = 0; } /* Mproj */
744 else if (Xproj) { exc_handling = 1; } /* !Mproj && Xproj */
745 else { exc_handling = 2; } /* !Mproj && !Xproj */
750 the procedure and later replaces the Start node of the called graph.
751 Post_call is the old Call node and collects the results of the called
752 graph. Both will end up being a tuple. -- */
753 post_bl = get_nodes_Block(call);
754 set_irg_current_block(current_ir_graph, post_bl);
755 /* XxMxPxP of Start + parameter of Call */
756 in[pn_Start_X_initial_exec] = new_Jmp();
757 in[pn_Start_M] = get_Call_mem(call);
758 in[pn_Start_P_frame_base] = get_irg_frame(current_ir_graph);
759 in[pn_Start_P_globals] = get_irg_globals(current_ir_graph);
760 in[pn_Start_T_args] = new_Tuple(get_Call_n_params(call), get_Call_param_arr(call));
761 /* in[pn_Start_P_value_arg_base] = ??? */
762 pre_call = new_Tuple(5, in);
766 The new block gets the ins of the old block, pre_call and all its
767 predecessors and all Phi nodes. -- */
768 part_block(pre_call);
770 /* -- Prepare state for dead node elimination -- */
771 /* Visited flags in calling irg must be >= flag in called irg.
772 Else walker and arity computation will not work. */
773 if (get_irg_visited(current_ir_graph) <= get_irg_visited(called_graph))
774 set_irg_visited(current_ir_graph, get_irg_visited(called_graph)+1);
775 if (get_irg_block_visited(current_ir_graph)< get_irg_block_visited(called_graph))
776 set_irg_block_visited(current_ir_graph, get_irg_block_visited(called_graph));
777 /* Set pre_call as new Start node in link field of the start node of
778 calling graph and pre_calls block as new block for the start block
780 Further mark these nodes so that they are not visited by the
782 set_irn_link(get_irg_start(called_graph), pre_call);
783 set_irn_visited(get_irg_start(called_graph), get_irg_visited(current_ir_graph));
784 set_irn_link(get_irg_start_block(called_graph), get_nodes_Block(pre_call));
785 set_irn_visited(get_irg_start_block(called_graph), get_irg_visited(current_ir_graph));
786 set_irn_link(get_irg_bad(called_graph), get_irg_bad(current_ir_graph));
787 set_irn_visited(get_irg_bad(called_graph), get_irg_visited(current_ir_graph));
789 /* Initialize for compaction of in arrays */
790 inc_irg_block_visited(current_ir_graph);
792 /* -- Replicate local entities of the called_graph -- */
793 /* copy the entities. */
794 called_frame = get_irg_frame_type(called_graph);
795 for (i = 0; i < get_class_n_members(called_frame); i++) {
796 entity *new_ent, *old_ent;
797 old_ent = get_class_member(called_frame, i);
798 new_ent = copy_entity_own(old_ent, get_cur_frame_type());
799 set_entity_link(old_ent, new_ent);
802 /* visited is > than that of called graph. With this trick visited will
803 remain unchanged so that an outer walker, e.g., searching the call nodes
804 to inline, calling this inline will not visit the inlined nodes. */
805 set_irg_visited(current_ir_graph, get_irg_visited(current_ir_graph)-1);
807 /* -- Performing dead node elimination inlines the graph -- */
808 /* Copies the nodes to the obstack of current_ir_graph. Updates links to new
810 /* @@@ endless loops are not copied!! -- they should be, I think... */
811 irg_walk(get_irg_end(called_graph), copy_node_inline, copy_preds,
812 get_irg_frame_type(called_graph));
814 /* Repair called_graph */
815 set_irg_visited(called_graph, get_irg_visited(current_ir_graph));
816 set_irg_block_visited(called_graph, get_irg_block_visited(current_ir_graph));
817 set_Block_block_visited(get_irg_start_block(called_graph), 0);
819 /* -- Merge the end of the inlined procedure with the call site -- */
820 /* We will turn the old Call node into a Tuple with the following
823 0: Phi of all Memories of Return statements.
824 1: Jmp from new Block that merges the control flow from all exception
825 predecessors of the old end block.
826 2: Tuple of all arguments.
827 3: Phi of Exception memories.
828 In case the old Call directly branches to End on an exception we don't
829 need the block merging all exceptions nor the Phi of the exception
833 /* -- Precompute some values -- */
834 end_bl = get_new_node(get_irg_end_block(called_graph));
835 end = get_new_node(get_irg_end(called_graph));
836 arity = get_irn_arity(end_bl); /* arity = n_exc + n_ret */
837 n_res = get_method_n_ress(get_Call_type(call));
839 res_pred = (ir_node **) malloc (n_res * sizeof (ir_node *));
840 cf_pred = (ir_node **) malloc (arity * sizeof (ir_node *));
842 set_irg_current_block(current_ir_graph, post_bl); /* just to make sure */
844 /* -- archive keepalives -- */
845 irn_arity = get_irn_arity(end);
846 for (i = 0; i < irn_arity; i++)
847 add_End_keepalive(get_irg_end(current_ir_graph), get_irn_n(end, i));
849 /* The new end node will die. We need not free as the in array is on the obstack:
850 copy_node only generated 'D' arrays. */
852 /* -- Replace Return nodes by Jump nodes. -- */
854 for (i = 0; i < arity; i++) {
856 ret = get_irn_n(end_bl, i);
857 if (get_irn_op(ret) == op_Return) {
858 cf_pred[n_ret] = new_r_Jmp(current_ir_graph, get_nodes_Block(ret));
862 set_irn_in(post_bl, n_ret, cf_pred);
864 /* -- Build a Tuple for all results of the method.
865 Add Phi node if there was more than one Return. -- */
866 turn_into_tuple(post_call, 4);
867 /* First the Memory-Phi */
869 for (i = 0; i < arity; i++) {
870 ret = get_irn_n(end_bl, i);
871 if (get_irn_op(ret) == op_Return) {
872 cf_pred[n_ret] = get_Return_mem(ret);
876 phi = new_Phi(n_ret, cf_pred, mode_M);
877 set_Tuple_pred(call, pn_Call_M_regular, phi);
878 /* Conserve Phi-list for further inlinings -- but might be optimized */
879 if (get_nodes_Block(phi) == post_bl) {
880 set_irn_link(phi, get_irn_link(post_bl));
881 set_irn_link(post_bl, phi);
883 /* Now the real results */
885 for (j = 0; j < n_res; j++) {
887 for (i = 0; i < arity; i++) {
888 ret = get_irn_n(end_bl, i);
889 if (get_irn_op(ret) == op_Return) {
890 cf_pred[n_ret] = get_Return_res(ret, j);
895 phi = new_Phi(n_ret, cf_pred, get_irn_mode(cf_pred[0]));
899 /* Conserve Phi-list for further inlinings -- but might be optimized */
900 if (get_nodes_Block(phi) == post_bl) {
901 set_irn_link(phi, get_irn_link(post_bl));
902 set_irn_link(post_bl, phi);
905 set_Tuple_pred(call, pn_Call_T_result, new_Tuple(n_res, res_pred));
907 set_Tuple_pred(call, pn_Call_T_result, new_Bad());
909 /* Finally the exception control flow.
910 We have two (three) possible situations:
911 First if the Call branches to an exception handler: We need to add a Phi node to
912 collect the memory containing the exception objects. Further we need
913 to add another block to get a correct representation of this Phi. To
914 this block we add a Jmp that resolves into the X output of the Call
915 when the Call is turned into a tuple.
916 Second the Call branches to End, the exception is not handled. Just
917 add all inlined exception branches to the End node.
918 Third: there is no Exception edge at all. Handle as case two. */
919 if (exc_handling == 0) {
921 for (i = 0; i < arity; i++) {
923 ret = get_irn_n(end_bl, i);
924 if (is_fragile_op(skip_Proj(ret)) || (get_irn_op(skip_Proj(ret)) == op_Raise)) {
925 cf_pred[n_exc] = ret;
930 new_Block(n_exc, cf_pred); /* watch it: current_block is changed! */
931 set_Tuple_pred(call, pn_Call_X_except, new_Jmp());
932 /* The Phi for the memories with the exception objects */
934 for (i = 0; i < arity; i++) {
936 ret = skip_Proj(get_irn_n(end_bl, i));
937 if (get_irn_op(ret) == op_Call) {
938 cf_pred[n_exc] = new_r_Proj(current_ir_graph, get_nodes_Block(ret), ret, mode_M, 3);
940 } else if (is_fragile_op(ret)) {
941 /* We rely that all cfops have the memory output at the same position. */
942 cf_pred[n_exc] = new_r_Proj(current_ir_graph, get_nodes_Block(ret), ret, mode_M, 0);
944 } else if (get_irn_op(ret) == op_Raise) {
945 cf_pred[n_exc] = new_r_Proj(current_ir_graph, get_nodes_Block(ret), ret, mode_M, 1);
949 set_Tuple_pred(call, pn_Call_M_except, new_Phi(n_exc, cf_pred, mode_M));
951 set_Tuple_pred(call, pn_Call_X_except, new_Bad());
952 set_Tuple_pred(call, pn_Call_M_except, new_Bad());
955 ir_node *main_end_bl;
956 int main_end_bl_arity;
959 /* assert(exc_handling == 1 || no exceptions. ) */
961 for (i = 0; i < arity; i++) {
962 ir_node *ret = get_irn_n(end_bl, i);
964 if (is_fragile_op(skip_Proj(ret)) || (get_irn_op(skip_Proj(ret)) == op_Raise)) {
965 cf_pred[n_exc] = ret;
969 main_end_bl = get_irg_end_block(current_ir_graph);
970 main_end_bl_arity = get_irn_arity(main_end_bl);
971 end_preds = (ir_node **) malloc ((n_exc + main_end_bl_arity) * sizeof (ir_node *));
973 for (i = 0; i < main_end_bl_arity; ++i)
974 end_preds[i] = get_irn_n(main_end_bl, i);
975 for (i = 0; i < n_exc; ++i)
976 end_preds[main_end_bl_arity + i] = cf_pred[i];
977 set_irn_in(main_end_bl, n_exc + main_end_bl_arity, end_preds);
978 set_Tuple_pred(call, pn_Call_X_except, new_Bad());
979 set_Tuple_pred(call, pn_Call_M_except, new_Bad());
985 #if 0 /* old. now better, correcter, faster implementation. */
987 /* -- If the exception control flow from the inlined Call directly
988 branched to the end block we now have the following control
989 flow predecessor pattern: ProjX -> Tuple -> Jmp. We must
990 remove the Jmp along with it's empty block and add Jmp's
991 predecessors as predecessors of this end block. No problem if
992 there is no exception, because then branches Bad to End which
994 @@@ can't we know this beforehand: by getting the Proj(1) from
995 the Call link list and checking whether it goes to Proj. */
996 /* find the problematic predecessor of the end block. */
997 end_bl = get_irg_end_block(current_ir_graph);
998 for (i = 0; i < get_Block_n_cfgpreds(end_bl); i++) {
999 cf_op = get_Block_cfgpred(end_bl, i);
1000 if (get_irn_op(cf_op) == op_Proj) {
1001 cf_op = get_Proj_pred(cf_op);
1002 if ((get_irn_op(cf_op) == op_Tuple) && (cf_op == call)) {
1003 /* There are unoptimized tuples from inlineing before when no exc */
1004 assert(get_Proj_proj(get_Block_cfgpred(end_bl, i)) == pn_Call_X_except);
1005 cf_op = get_Tuple_pred(cf_op, pn_Call_X_except);
1006 assert(get_irn_op(cf_op) == op_Jmp);
1012 if (i < get_Block_n_cfgpreds(end_bl)) {
1013 bl = get_nodes_Block(cf_op);
1014 arity = get_Block_n_cfgpreds(end_bl) + get_Block_n_cfgpreds(bl) - 1;
1015 cf_pred = (ir_node **) malloc (arity * sizeof (ir_node *));
1016 for (j = 0; j < i; j++)
1017 cf_pred[j] = get_Block_cfgpred(end_bl, j);
1018 for (j = j; j < i + get_Block_n_cfgpreds(bl); j++)
1019 cf_pred[j] = get_Block_cfgpred(bl, j-i);
1020 for (j = j; j < arity; j++)
1021 cf_pred[j] = get_Block_cfgpred(end_bl, j-get_Block_n_cfgpreds(bl) +1);
1022 set_irn_in(end_bl, arity, cf_pred);
1024 /* Remove the exception pred from post-call Tuple. */
1025 set_Tuple_pred(call, pn_Call_X_except, new_Bad());
1030 /* -- Turn cse back on. -- */
1031 set_optimize(rem_opt);
1036 /********************************************************************/
1037 /* Apply inlineing to small methods. */
1038 /********************************************************************/
1040 /* It makes no sense to inline too many calls in one procedure. Anyways,
1041 I didn't get a version with NEW_ARR_F to run. */
1042 #define MAX_INLINE 1024
1045 * environment for inlining small irgs
1047 typedef struct _inline_env_t {
1049 ir_node *calls[MAX_INLINE];
1053 * Returns the irg called from a Call node. If the irg is not
1054 * known, NULL is returned.
1056 static ir_graph *get_call_called_irg(ir_node *call) {
1059 ir_graph *called_irg = NULL;
1061 assert(get_irn_op(call) == op_Call);
1063 addr = get_Call_ptr(call);
1064 if (get_irn_op(addr) == op_Const) {
1065 /* Check whether the constant is the pointer to a compiled entity. */
1066 tv = get_Const_tarval(addr);
1067 if (tarval_to_entity(tv))
1068 called_irg = get_entity_irg(tarval_to_entity(tv));
1073 static void collect_calls(ir_node *call, void *env) {
1074 inline_env_t *ienv = env;
1077 ir_graph *called_irg;
1079 if (get_irn_op(call) != op_Call) return;
1081 addr = get_Call_ptr(call);
1082 if (get_irn_op(addr) == op_Const) {
1083 /* Check whether the constant is the pointer to a compiled entity. */
1084 tv = get_Const_tarval(addr);
1085 if (tarval_to_entity(tv)) {
1086 called_irg = get_entity_irg(tarval_to_entity(tv));
1087 if (called_irg && ienv->pos < MAX_INLINE) {
1088 /* The Call node calls a locally defined method. Remember to inline. */
1089 ienv->calls[ienv->pos++] = call;
1096 * Inlines all small methods at call sites where the called address comes
1097 * from a Const node that references the entity representing the called
1099 * The size argument is a rough measure for the code size of the method:
1100 * Methods where the obstack containing the firm graph is smaller than
1103 void inline_small_irgs(ir_graph *irg, int size) {
1105 ir_graph *rem = current_ir_graph;
1108 if (!(get_opt_optimize() && get_opt_inline())) return;
1110 current_ir_graph = irg;
1111 /* Handle graph state */
1112 assert(get_irg_phase_state(current_ir_graph) != phase_building);
1113 free_callee_info(current_ir_graph);
1115 /* Find Call nodes to inline.
1116 (We can not inline during a walk of the graph, as inlineing the same
1117 method several times changes the visited flag of the walked graph:
1118 after the first inlineing visited of the callee equals visited of
1119 the caller. With the next inlineing both are increased.) */
1121 irg_walk(get_irg_end(irg), NULL, collect_calls, &env);
1123 if ((env.pos > 0) && (env.pos < MAX_INLINE)) {
1124 /* There are calls to inline */
1125 collect_phiprojs(irg);
1126 for (i = 0; i < env.pos; i++) {
1129 tv = get_Const_tarval(get_Call_ptr(env.calls[i]));
1130 callee = get_entity_irg(tarval_to_entity(tv));
1131 if (((_obstack_memory_used(callee->obst) - obstack_room(callee->obst)) < size) ||
1132 (get_irg_inline_property(callee) == irg_inline_forced)) {
1133 inline_method(env.calls[i], callee);
1138 current_ir_graph = rem;
1142 * Environment for inlining irgs.
1145 int n_nodes; /**< Nodes in graph except Id, Tuple, Proj, Start, End */
1146 int n_nodes_orig; /**< for statistics */
1147 eset *call_nodes; /**< All call nodes in this graph */
1149 int n_call_nodes_orig; /**< for statistics */
1150 int n_callers; /**< Number of known graphs that call this graphs. */
1151 int n_callers_orig; /**< for statistics */
1154 static inline_irg_env *new_inline_irg_env(void) {
1155 inline_irg_env *env = malloc(sizeof(inline_irg_env));
1156 env->n_nodes = -2; /* uncount Start, End */
1157 env->n_nodes_orig = -2; /* uncount Start, End */
1158 env->call_nodes = eset_create();
1159 env->n_call_nodes = 0;
1160 env->n_call_nodes_orig = 0;
1162 env->n_callers_orig = 0;
1166 static void free_inline_irg_env(inline_irg_env *env) {
1167 eset_destroy(env->call_nodes);
1171 static void collect_calls2(ir_node *call, void *env) {
1172 inline_irg_env *x = (inline_irg_env *)env;
1173 ir_op *op = get_irn_op(call);
1176 /* count nodes in irg */
1177 if (op != op_Proj && op != op_Tuple && op != op_Sync) {
1182 if (op != op_Call) return;
1184 /* collect all call nodes */
1185 eset_insert(x->call_nodes, (void *)call);
1187 x->n_call_nodes_orig++;
1189 /* count all static callers */
1190 callee = get_call_called_irg(call);
1192 ((inline_irg_env *)get_irg_link(callee))->n_callers++;
1193 ((inline_irg_env *)get_irg_link(callee))->n_callers_orig++;
1197 INLINE static int is_leave(ir_graph *irg) {
1198 return (((inline_irg_env *)get_irg_link(irg))->n_call_nodes == 0);
1201 INLINE static int is_smaller(ir_graph *callee, int size) {
1202 return (((inline_irg_env *)get_irg_link(callee))->n_nodes < size);
1207 * Inlines small leave methods at call sites where the called address comes
1208 * from a Const node that references the entity representing the called
1210 * The size argument is a rough measure for the code size of the method:
1211 * Methods where the obstack containing the firm graph is smaller than
1214 void inline_leave_functions(int maxsize, int leavesize, int size) {
1215 inline_irg_env *env;
1216 int i, n_irgs = get_irp_n_irgs();
1217 ir_graph *rem = current_ir_graph;
1220 if (!(get_opt_optimize() && get_opt_inline())) return;
1222 /* extend all irgs by a temporary data structure for inlineing. */
1223 for (i = 0; i < n_irgs; ++i)
1224 set_irg_link(get_irp_irg(i), new_inline_irg_env());
1226 /* Precompute information in temporary data structure. */
1227 for (i = 0; i < n_irgs; ++i) {
1228 current_ir_graph = get_irp_irg(i);
1229 assert(get_irg_phase_state(current_ir_graph) != phase_building);
1230 free_callee_info(current_ir_graph);
1232 irg_walk(get_irg_end(current_ir_graph), NULL, collect_calls2,
1233 get_irg_link(current_ir_graph));
1237 Inline leaves recursively -- we might construct new leaves. */
1238 /* int itercnt = 1; */
1239 while (did_inline) {
1240 /* printf("iteration %d\n", itercnt++); */
1242 for (i = 0; i < n_irgs; ++i) {
1245 int phiproj_computed = 0;
1247 current_ir_graph = get_irp_irg(i);
1248 env = (inline_irg_env *)get_irg_link(current_ir_graph);
1250 /* we can not walk and change a set, nor remove from it.
1252 walkset = env->call_nodes;
1253 env->call_nodes = eset_create();
1254 for (call = eset_first(walkset); call; call = eset_next(walkset)) {
1255 inline_irg_env *callee_env;
1256 ir_graph *callee = get_call_called_irg(call);
1258 if (env->n_nodes > maxsize) break;
1260 ((is_leave(callee) && is_smaller(callee, leavesize)) ||
1261 (get_irg_inline_property(callee) == irg_inline_forced))) {
1262 if (!phiproj_computed) {
1263 phiproj_computed = 1;
1264 collect_phiprojs(current_ir_graph);
1266 callee_env = (inline_irg_env *)get_irg_link(callee);
1267 /* printf(" %s: Inlineing %s.\n", get_entity_name(get_irg_entity(current_ir_graph)), */
1268 /* get_entity_name(get_irg_entity(callee))); */
1269 if (inline_method(call, callee)) {
1271 env->n_call_nodes--;
1272 eset_insert_all(env->call_nodes, callee_env->call_nodes);
1273 env->n_call_nodes += callee_env->n_call_nodes;
1274 env->n_nodes += callee_env->n_nodes;
1275 callee_env->n_callers--;
1278 eset_insert(env->call_nodes, call);
1281 eset_destroy(walkset);
1285 /* printf("Non leaves\n"); */
1286 /* inline other small functions. */
1287 for (i = 0; i < n_irgs; ++i) {
1290 int phiproj_computed = 0;
1292 current_ir_graph = get_irp_irg(i);
1293 env = (inline_irg_env *)get_irg_link(current_ir_graph);
1295 /* we can not walk and change a set, nor remove from it.
1297 walkset = env->call_nodes;
1298 env->call_nodes = eset_create();
1299 for (call = eset_first(walkset); call; call = eset_next(walkset)) {
1300 inline_irg_env *callee_env;
1301 ir_graph *callee = get_call_called_irg(call);
1303 if (env->n_nodes > maxsize) break;
1304 if (callee && is_smaller(callee, size)) {
1305 if (!phiproj_computed) {
1306 phiproj_computed = 1;
1307 collect_phiprojs(current_ir_graph);
1309 callee_env = (inline_irg_env *)get_irg_link(callee);
1310 /* printf(" %s: Inlineing %s.\n", get_entity_name(get_irg_entity(current_ir_graph)), */
1311 /* get_entity_name(get_irg_entity(callee))); */
1312 if (inline_method(call, callee)) {
1314 env->n_call_nodes--;
1315 eset_insert_all(env->call_nodes, callee_env->call_nodes);
1316 env->n_call_nodes += callee_env->n_call_nodes;
1317 env->n_nodes += callee_env->n_nodes;
1318 callee_env->n_callers--;
1321 eset_insert(env->call_nodes, call);
1324 eset_destroy(walkset);
1327 for (i = 0; i < n_irgs; ++i) {
1328 current_ir_graph = get_irp_irg(i);
1330 env = (inline_irg_env *)get_irg_link(current_ir_graph);
1331 if ((env->n_call_nodes_orig != env->n_call_nodes) ||
1332 (env->n_callers_orig != env->n_callers))
1333 printf("Nodes:%3d ->%3d, calls:%3d ->%3d, callers:%3d ->%3d, -- %s\n",
1334 env->n_nodes_orig, env->n_nodes, env->n_call_nodes_orig, env->n_call_nodes,
1335 env->n_callers_orig, env->n_callers,
1336 get_entity_name(get_irg_entity(current_ir_graph)));
1338 free_inline_irg_env((inline_irg_env *)get_irg_link(current_ir_graph));
1341 current_ir_graph = rem;
1344 /*******************************************************************/
1345 /* Code Placement. Pins all floating nodes to a block where they */
1346 /* will be executed only if needed. */
1347 /*******************************************************************/
1350 * Find the earliest correct block for N. --- Place N into the
1351 * same Block as its dominance-deepest Input.
1354 place_floats_early(ir_node *n, pdeq *worklist)
1356 int i, start, irn_arity;
1358 /* we must not run into an infinite loop */
1359 assert (irn_not_visited(n));
1360 mark_irn_visited(n);
1362 /* Place floating nodes. */
1363 if (get_op_pinned(get_irn_op(n)) == floats) {
1365 ir_node *b = new_Bad(); /* The block to place this node in */
1366 int bad_recursion = is_Bad(get_nodes_block(n));
1368 assert(get_irn_op(n) != op_Block);
1370 if ((get_irn_op(n) == op_Const) ||
1371 (get_irn_op(n) == op_SymConst) ||
1373 (get_irn_op(n) == op_Unknown)) {
1374 /* These nodes will not be placed by the loop below. */
1375 b = get_irg_start_block(current_ir_graph);
1379 /* find the block for this node. */
1380 irn_arity = get_irn_arity(n);
1381 for (i = 0; i < irn_arity; i++) {
1382 ir_node *dep = get_irn_n(n, i);
1385 if ((irn_not_visited(dep))
1386 && (get_op_pinned(get_irn_op(dep)) == floats)) {
1387 place_floats_early(dep, worklist);
1391 * A node in the Bad block must stay in the bad block,
1392 * so don't compute a new block for it.
1397 /* Because all loops contain at least one pinned node, now all
1398 our inputs are either pinned or place_early has already
1399 been finished on them. We do not have any unfinished inputs! */
1400 dep_block = get_nodes_Block(dep);
1401 if ((!is_Bad(dep_block)) &&
1402 (get_Block_dom_depth(dep_block) > depth)) {
1404 depth = get_Block_dom_depth(dep_block);
1406 /* Avoid that the node is placed in the Start block */
1407 if ((depth == 1) && (get_Block_dom_depth(get_nodes_Block(n)) > 1)) {
1408 b = get_Block_cfg_out(get_irg_start_block(current_ir_graph), 0);
1409 assert(b != get_irg_start_block(current_ir_graph));
1413 set_nodes_Block(n, b);
1416 /* Add predecessors of non floating nodes on worklist. */
1417 start = (get_irn_op(n) == op_Block) ? 0 : -1;
1418 irn_arity = get_irn_arity(n);
1419 for (i = start; i < irn_arity; i++) {
1420 ir_node *pred = get_irn_n(n, i);
1421 if (irn_not_visited(pred)) {
1422 pdeq_putr (worklist, pred);
1428 * Floating nodes form subgraphs that begin at nodes as Const, Load,
1429 * Start, Call and that end at pinned nodes as Store, Call. Place_early
1430 * places all floating nodes reachable from its argument through floating
1431 * nodes and adds all beginnings at pinned nodes to the worklist.
1433 static INLINE void place_early(pdeq* worklist) {
1435 inc_irg_visited(current_ir_graph);
1437 /* this inits the worklist */
1438 place_floats_early(get_irg_end(current_ir_graph), worklist);
1440 /* Work the content of the worklist. */
1441 while (!pdeq_empty (worklist)) {
1442 ir_node *n = pdeq_getl (worklist);
1443 if (irn_not_visited(n)) place_floats_early(n, worklist);
1446 set_irg_outs_inconsistent(current_ir_graph);
1447 current_ir_graph->pinned = pinned;
1451 /** deepest common dominance ancestor of DCA and CONSUMER of PRODUCER. */
1453 consumer_dom_dca (ir_node *dca, ir_node *consumer, ir_node *producer)
1455 ir_node *block = NULL;
1457 /* Compute the latest block into which we can place a node so that it is
1459 if (get_irn_op(consumer) == op_Phi) {
1460 /* our consumer is a Phi-node, the effective use is in all those
1461 blocks through which the Phi-node reaches producer */
1463 ir_node *phi_block = get_nodes_Block(consumer);
1464 irn_arity = get_irn_arity(consumer);
1465 for (i = 0; i < irn_arity; i++) {
1466 if (get_irn_n(consumer, i) == producer) {
1467 block = get_nodes_Block(get_Block_cfgpred(phi_block, i));
1471 assert(is_no_Block(consumer));
1472 block = get_nodes_Block(consumer);
1475 /* Compute the deepest common ancestor of block and dca. */
1477 if (!dca) return block;
1478 while (get_Block_dom_depth(block) > get_Block_dom_depth(dca))
1479 block = get_Block_idom(block);
1480 while (get_Block_dom_depth(dca) > get_Block_dom_depth(block))
1481 dca = get_Block_idom(dca);
1482 while (block != dca)
1483 { block = get_Block_idom(block); dca = get_Block_idom(dca); }
1488 static INLINE int get_irn_loop_depth(ir_node *n) {
1489 return get_loop_depth(get_irn_loop(n));
1493 * Move n to a block with less loop depth than it's current block. The
1494 * new block must be dominated by early.
1497 move_out_of_loops (ir_node *n, ir_node *early)
1499 ir_node *best, *dca;
1503 /* Find the region deepest in the dominator tree dominating
1504 dca with the least loop nesting depth, but still dominated
1505 by our early placement. */
1506 dca = get_nodes_Block(n);
1508 while (dca != early) {
1509 dca = get_Block_idom(dca);
1510 if (!dca) break; /* should we put assert(dca)? */
1511 if (get_irn_loop_depth(dca) < get_irn_loop_depth(best)) {
1515 if (best != get_nodes_Block(n)) {
1517 printf("Moving out of loop: "); DDMN(n);
1518 printf(" Outermost block: "); DDMN(early);
1519 printf(" Best block: "); DDMN(best);
1520 printf(" Innermost block: "); DDMN(get_nodes_Block(n));
1522 set_nodes_Block(n, best);
1527 * Find the latest legal block for N and place N into the
1528 * `optimal' Block between the latest and earliest legal block.
1529 * The `optimal' block is the dominance-deepest block of those
1530 * with the least loop-nesting-depth. This places N out of as many
1531 * loops as possible and then makes it as control dependant as
1535 place_floats_late(ir_node *n, pdeq *worklist)
1540 assert (irn_not_visited(n)); /* no multiple placement */
1542 /* no need to place block nodes, control nodes are already placed. */
1543 if ((get_irn_op(n) != op_Block) &&
1545 (get_irn_mode(n) != mode_X)) {
1546 /* Remember the early placement of this block to move it
1547 out of loop no further than the early placement. */
1548 early = get_nodes_Block(n);
1549 /* Assure that our users are all placed, except the Phi-nodes.
1550 --- Each data flow cycle contains at least one Phi-node. We
1551 have to break the `user has to be placed before the
1552 producer' dependence cycle and the Phi-nodes are the
1553 place to do so, because we need to base our placement on the
1554 final region of our users, which is OK with Phi-nodes, as they
1555 are pinned, and they never have to be placed after a
1556 producer of one of their inputs in the same block anyway. */
1557 for (i = 0; i < get_irn_n_outs(n); i++) {
1558 ir_node *succ = get_irn_out(n, i);
1559 if (irn_not_visited(succ) && (get_irn_op(succ) != op_Phi))
1560 place_floats_late(succ, worklist);
1563 /* We have to determine the final block of this node... except for
1565 if ((get_op_pinned(get_irn_op(n)) == floats) &&
1566 (get_irn_op(n) != op_Const) &&
1567 (get_irn_op(n) != op_SymConst)) {
1568 ir_node *dca = NULL; /* deepest common ancestor in the
1569 dominator tree of all nodes'
1570 blocks depending on us; our final
1571 placement has to dominate DCA. */
1572 for (i = 0; i < get_irn_n_outs(n); i++) {
1573 dca = consumer_dom_dca (dca, get_irn_out(n, i), n);
1575 set_nodes_Block(n, dca);
1577 move_out_of_loops (n, early);
1581 mark_irn_visited(n);
1583 /* Add predecessors of all non-floating nodes on list. (Those of floating
1584 nodes are placeded already and therefore are marked.) */
1585 for (i = 0; i < get_irn_n_outs(n); i++) {
1586 if (irn_not_visited(get_irn_out(n, i))) {
1587 pdeq_putr (worklist, get_irn_out(n, i));
1592 static INLINE void place_late(pdeq* worklist) {
1594 inc_irg_visited(current_ir_graph);
1596 /* This fills the worklist initially. */
1597 place_floats_late(get_irg_start_block(current_ir_graph), worklist);
1598 /* And now empty the worklist again... */
1599 while (!pdeq_empty (worklist)) {
1600 ir_node *n = pdeq_getl (worklist);
1601 if (irn_not_visited(n)) place_floats_late(n, worklist);
1605 void place_code(ir_graph *irg) {
1607 ir_graph *rem = current_ir_graph;
1609 current_ir_graph = irg;
1611 if (!(get_opt_optimize() && get_opt_global_cse())) return;
1613 /* Handle graph state */
1614 assert(get_irg_phase_state(irg) != phase_building);
1615 if (get_irg_dom_state(irg) != dom_consistent)
1618 if (1 || get_irg_loopinfo_state(irg) != loopinfo_consistent) {
1619 free_loop_information(irg);
1620 construct_backedges(irg);
1623 /* Place all floating nodes as early as possible. This guarantees
1624 a legal code placement. */
1625 worklist = new_pdeq();
1626 place_early(worklist);
1628 /* place_early invalidates the outs, place_late needs them. */
1630 /* Now move the nodes down in the dominator tree. This reduces the
1631 unnecessary executions of the node. */
1632 place_late(worklist);
1634 set_irg_outs_inconsistent(current_ir_graph);
1635 set_irg_loopinfo_inconsistent(current_ir_graph);
1637 current_ir_graph = rem;
1642 /********************************************************************/
1643 /* Control flow optimization. */
1644 /* Removes Bad control flow predecessors and empty blocks. A block */
1645 /* is empty if it contains only a Jmp node. */
1646 /* Blocks can only be removed if they are not needed for the */
1647 /* semantics of Phi nodes. */
1648 /********************************************************************/
1651 * Removes Tuples from Block control flow predecessors.
1652 * Optimizes blocks with equivalent_node().
1653 * Replaces n by Bad if n is unreachable control flow.
1655 static void merge_blocks(ir_node *n, void *env) {
1657 set_irn_link(n, NULL);
1659 if (get_irn_op(n) == op_Block) {
1661 for (i = 0; i < get_Block_n_cfgpreds(n); i++)
1662 /* GL @@@ : is this possible? if (get_opt_normalize()) -- added, all tests go through.
1663 A different order of optimizations might cause problems. */
1664 if (get_opt_normalize())
1665 set_Block_cfgpred(n, i, skip_Tuple(get_Block_cfgpred(n, i)));
1666 } else if (get_opt_optimize() && (get_irn_mode(n) == mode_X)) {
1667 /* We will soon visit a block. Optimize it before visiting! */
1668 ir_node *b = get_nodes_Block(n);
1669 ir_node *new_node = equivalent_node(b);
1670 while (irn_not_visited(b) && (!is_Bad(new_node)) && (new_node != b)) {
1671 /* We would have to run gigo if new is bad, so we
1672 promote it directly below. */
1673 assert(((b == new_node) ||
1674 get_opt_control_flow_straightening() ||
1675 get_opt_control_flow_weak_simplification()) &&
1676 ("strange flag setting"));
1677 exchange (b, new_node);
1679 new_node = equivalent_node(b);
1681 if (is_Bad(new_node) && get_opt_normalize()) exchange(n, new_Bad());
1686 * Collects all Phi nodes in link list of Block.
1687 * Marks all blocks "block_visited" if they contain a node other
1690 static void collect_nodes(ir_node *n, void *env) {
1691 if (is_no_Block(n)) {
1692 ir_node *b = get_nodes_Block(n);
1694 if ((get_irn_op(n) == op_Phi)) {
1695 /* Collect Phi nodes to compact ins along with block's ins. */
1696 set_irn_link(n, get_irn_link(b));
1698 } else if ((get_irn_op(n) != op_Jmp) && !is_Bad(b)) { /* Check for non empty block. */
1699 mark_Block_block_visited(b);
1704 /** Returns true if pred is predecessor of block. */
1705 static int is_pred_of(ir_node *pred, ir_node *b) {
1707 for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
1708 ir_node *b_pred = get_nodes_Block(get_Block_cfgpred(b, i));
1709 if (b_pred == pred) return 1;
1714 static int test_whether_dispensable(ir_node *b, int pos) {
1715 int i, j, n_preds = 1;
1716 int dispensable = 1;
1717 ir_node *cfop = get_Block_cfgpred(b, pos);
1718 ir_node *pred = get_nodes_Block(cfop);
1720 if (get_Block_block_visited(pred) + 1
1721 < get_irg_block_visited(current_ir_graph)) {
1722 if (!get_opt_optimize() || !get_opt_control_flow_strong_simplification()) {
1723 /* Mark block so that is will not be removed. */
1724 set_Block_block_visited(pred, get_irg_block_visited(current_ir_graph)-1);
1727 /* Seems to be empty. */
1728 if (!get_irn_link(b)) {
1729 /* There are no Phi nodes ==> dispensable. */
1730 n_preds = get_Block_n_cfgpreds(pred);
1732 /* b's pred blocks and pred's pred blocks must be pairwise disjunct.
1733 Work preds < pos as if they were already removed. */
1734 for (i = 0; i < pos; i++) {
1735 ir_node *b_pred = get_nodes_Block(get_Block_cfgpred(b, i));
1736 if (get_Block_block_visited(b_pred) + 1
1737 < get_irg_block_visited(current_ir_graph)) {
1738 for (j = 0; j < get_Block_n_cfgpreds(b_pred); j++) {
1739 ir_node *b_pred_pred = get_nodes_Block(get_Block_cfgpred(b_pred, j));
1740 if (is_pred_of(b_pred_pred, pred)) dispensable = 0;
1743 if (is_pred_of(b_pred, pred)) dispensable = 0;
1746 for (i = pos +1; i < get_Block_n_cfgpreds(b); i++) {
1747 ir_node *b_pred = get_nodes_Block(get_Block_cfgpred(b, i));
1748 if (is_pred_of(b_pred, pred)) dispensable = 0;
1751 set_Block_block_visited(pred, get_irg_block_visited(current_ir_graph)-1);
1754 n_preds = get_Block_n_cfgpreds(pred);
1762 static void optimize_blocks(ir_node *b, void *env) {
1763 int i, j, k, max_preds, n_preds;
1764 ir_node *pred, *phi;
1767 /* Count the number of predecessor if this block is merged with pred blocks
1770 for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
1771 max_preds += test_whether_dispensable(b, i);
1773 in = (ir_node **) malloc(max_preds * sizeof(ir_node *));
1776 printf(" working on "); DDMN(b);
1777 for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
1778 pred = get_nodes_Block(get_Block_cfgpred(b, i));
1779 if (is_Bad(get_Block_cfgpred(b, i))) {
1780 printf(" removing Bad %i\n ", i);
1781 } else if (get_Block_block_visited(pred) +1
1782 < get_irg_block_visited(current_ir_graph)) {
1783 printf(" removing pred %i ", i); DDMN(pred);
1784 } else { printf(" Nothing to do for "); DDMN(pred); }
1786 * end Debug output -*/
1788 /*- Fix the Phi nodes -*/
1789 phi = get_irn_link(b);
1791 assert(get_irn_op(phi) == op_Phi);
1792 /* Find the new predecessors for the Phi */
1794 for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
1795 pred = get_nodes_Block(get_Block_cfgpred(b, i));
1796 if (is_Bad(get_Block_cfgpred(b, i))) {
1798 } else if (get_Block_block_visited(pred) +1
1799 < get_irg_block_visited(current_ir_graph)) {
1800 /* It's an empty block and not yet visited. */
1801 ir_node *phi_pred = get_Phi_pred(phi, i);
1802 for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
1803 if (get_nodes_Block(phi_pred) == pred) {
1804 assert(get_irn_op(phi_pred) == op_Phi); /* Block is empty!! */
1805 in[n_preds] = get_Phi_pred(phi_pred, j);
1807 in[n_preds] = phi_pred;
1811 /* The Phi_pred node is replaced now if it is a Phi.
1812 In Schleifen kann offenbar der entfernte Phi Knoten legal verwendet werden.
1813 Daher muss der Phiknoten durch den neuen ersetzt werden.
1814 Weiter muss der alte Phiknoten entfernt werden (durch ersetzen oder
1815 durch einen Bad) damit er aus den keep_alive verschwinden kann.
1816 Man sollte also, falls keine Schleife vorliegt, exchange mit new_Bad
1818 if (get_nodes_Block(phi_pred) == pred) {
1819 /* remove the Phi as it might be kept alive. Further there
1820 might be other users. */
1821 exchange(phi_pred, phi); /* geht, ist aber doch semantisch falsch! Warum?? */
1824 in[n_preds] = get_Phi_pred(phi, i);
1829 set_irn_in(phi, n_preds, in);
1831 phi = get_irn_link(phi);
1835 This happens only if merge between loop backedge and single loop entry. -*/
1836 for (k = 0; k < get_Block_n_cfgpreds(b); k++) {
1837 pred = get_nodes_Block(get_Block_cfgpred(b, k));
1838 if (get_Block_block_visited(pred)+1 < get_irg_block_visited(current_ir_graph)) {
1839 phi = get_irn_link(pred);
1841 if (get_irn_op(phi) == op_Phi) {
1842 set_nodes_Block(phi, b);
1845 for (i = 0; i < k; i++) {
1846 pred = get_nodes_Block(get_Block_cfgpred(b, i));
1847 if (is_Bad(get_Block_cfgpred(b, i))) {
1849 } else if (get_Block_block_visited(pred) +1
1850 < get_irg_block_visited(current_ir_graph)) {
1851 /* It's an empty block and not yet visited. */
1852 for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
1853 /* @@@ Hier brauche ich Schleifeninformation!!! Kontrollflusskante
1854 muss Rueckwaertskante sein! (An allen vier in[n_preds] = phi
1855 Anweisungen.) Trotzdem tuts bisher!! */
1864 for (i = 0; i < get_Phi_n_preds(phi); i++) {
1865 in[n_preds] = get_Phi_pred(phi, i);
1868 for (i = k+1; i < get_Block_n_cfgpreds(b); i++) {
1869 pred = get_nodes_Block(get_Block_cfgpred(b, i));
1870 if (is_Bad(get_Block_cfgpred(b, i))) {
1872 } else if (get_Block_block_visited(pred) +1
1873 < get_irg_block_visited(current_ir_graph)) {
1874 /* It's an empty block and not yet visited. */
1875 for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
1884 set_irn_in(phi, n_preds, in);
1886 phi = get_irn_link(phi);
1891 /*- Fix the block -*/
1893 for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
1894 pred = get_nodes_Block(get_Block_cfgpred(b, i));
1895 if (is_Bad(get_Block_cfgpred(b, i))) {
1897 } else if (get_Block_block_visited(pred) +1
1898 < get_irg_block_visited(current_ir_graph)) {
1899 /* It's an empty block and not yet visited. */
1900 assert(get_Block_n_cfgpreds(b) > 1);
1901 /* Else it should be optimized by equivalent_node. */
1902 for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
1903 in[n_preds] = get_Block_cfgpred(pred, j);
1906 /* Remove block as it might be kept alive. */
1907 exchange(pred, b/*new_Bad()*/);
1909 in[n_preds] = get_Block_cfgpred(b, i);
1913 set_irn_in(b, n_preds, in);
1917 void optimize_cf(ir_graph *irg) {
1920 ir_node *end = get_irg_end(irg);
1921 ir_graph *rem = current_ir_graph;
1922 current_ir_graph = irg;
1924 /* Handle graph state */
1925 assert(get_irg_phase_state(irg) != phase_building);
1926 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
1927 set_irg_outs_inconsistent(current_ir_graph);
1928 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
1929 set_irg_dom_inconsistent(current_ir_graph);
1931 /* Use block visited flag to mark non-empty blocks. */
1932 inc_irg_block_visited(irg);
1933 irg_walk(end, merge_blocks, collect_nodes, NULL);
1935 /* Optimize the standard code. */
1936 irg_block_walk(get_irg_end_block(irg), optimize_blocks, NULL, NULL);
1938 /* Walk all keep alives, optimize them if block, add to new in-array
1939 for end if useful. */
1940 in = NEW_ARR_F (ir_node *, 1);
1941 in[0] = get_nodes_Block(end);
1942 inc_irg_visited(current_ir_graph);
1943 for(i = 0; i < get_End_n_keepalives(end); i++) {
1944 ir_node *ka = get_End_keepalive(end, i);
1945 if (irn_not_visited(ka)) {
1946 if ((get_irn_op(ka) == op_Block) && Block_not_block_visited(ka)) {
1947 set_irg_block_visited(current_ir_graph, /* Don't walk all the way to Start. */
1948 get_irg_block_visited(current_ir_graph)-1);
1949 irg_block_walk(ka, optimize_blocks, NULL, NULL);
1950 mark_irn_visited(ka);
1951 ARR_APP1 (ir_node *, in, ka);
1952 } else if (get_irn_op(ka) == op_Phi) {
1953 mark_irn_visited(ka);
1954 ARR_APP1 (ir_node *, in, ka);
1958 /* DEL_ARR_F(end->in); GL @@@ tut nicht ! */
1961 current_ir_graph = rem;
1966 * Called by walker of remove_critical_cf_edges().
1968 * Place an empty block to an edge between a blocks of multiple
1969 * predecessors and a block of multiple successors.
1972 * @param env Environment of walker. This field is unused and has
1975 static void walk_critical_cf_edges(ir_node *n, void *env) {
1977 ir_node *pre, *block, **in, *jmp;
1979 /* Block has multiple predecessors */
1980 if ((op_Block == get_irn_op(n)) &&
1981 (get_irn_arity(n) > 1)) {
1982 arity = get_irn_arity(n);
1984 if (n == get_irg_end_block(current_ir_graph))
1985 return; /* No use to add a block here. */
1987 for (i=0; i<arity; i++) {
1988 pre = get_irn_n(n, i);
1989 /* Predecessor has multiple successors. Insert new flow edge */
1990 if ((NULL != pre) &&
1991 (op_Proj == get_irn_op(pre)) &&
1992 op_Raise != get_irn_op(skip_Proj(pre))) {
1994 /* set predecessor array for new block */
1995 in = NEW_ARR_D (ir_node *, current_ir_graph->obst, 1);
1996 /* set predecessor of new block */
1998 block = new_Block(1, in);
1999 /* insert new jmp node to new block */
2000 switch_block(block);
2003 /* set successor of new block */
2004 set_irn_n(n, i, jmp);
2006 } /* predecessor has multiple successors */
2007 } /* for all predecessors */
2008 } /* n is a block */
2011 void remove_critical_cf_edges(ir_graph *irg) {
2012 if (get_opt_critical_edges())
2013 irg_walk_graph(irg, NULL, walk_critical_cf_edges, NULL);