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.
23 # include "irnode_t.h"
24 # include "irgraph_t.h"
31 # include "pdeq.h" /* Fuer code placement */
34 # include "irbackedge_t.h"
36 /* Defined in iropt.c */
37 pset *new_identities (void);
38 void del_identities (pset *value_table);
39 void add_identities (pset *value_table, ir_node *node);
41 /********************************************************************/
42 /* apply optimizations of iropt to all nodes. */
43 /********************************************************************/
45 static void init_link (ir_node *n, void *env) {
46 set_irn_link(n, NULL);
50 optimize_in_place_wrapper (ir_node *n, void *env) {
52 ir_node *optimized, *old;
54 for (i = 0; i < get_irn_arity(n); i++) {
55 /* get?irn_n skips Id nodes, so comparison old != optimized does not
56 show all optimizations. Therefore always set new predecessor. */
57 old = get_irn_n(n, i);
58 optimized = optimize_in_place_2(old);
59 set_irn_n(n, i, optimized);
62 if (get_irn_op(n) == op_Block) {
63 optimized = optimize_in_place_2(n);
64 if (optimized != n) exchange (n, optimized);
69 local_optimize_graph (ir_graph *irg) {
70 ir_graph *rem = current_ir_graph;
71 current_ir_graph = irg;
73 /* Handle graph state */
74 assert(get_irg_phase_state(irg) != phase_building);
75 if (get_opt_global_cse())
76 set_irg_pinned(current_ir_graph, floats);
77 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
78 set_irg_outs_inconsistent(current_ir_graph);
79 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
80 set_irg_dom_inconsistent(current_ir_graph);
82 /* Clean the value_table in irg for the cse. */
83 del_identities(irg->value_table);
84 irg->value_table = new_identities();
86 /* walk over the graph */
87 irg_walk(irg->end, init_link, optimize_in_place_wrapper, NULL);
89 current_ir_graph = rem;
92 /********************************************************************/
93 /* Routines for dead node elimination / copying garbage collection */
95 /********************************************************************/
97 /* Remeber the new node in the old node by using a field all nodes have. */
99 set_new_node (ir_node *old, ir_node *new)
104 /* Get this new node, before the old node is forgotton.*/
105 static INLINE ir_node *
106 get_new_node (ir_node * n)
111 /* We use the block_visited flag to mark that we have computed the
112 number of useful predecessors for this block.
113 Further we encode the new arity in this flag in the old blocks.
114 Remembering the arity is useful, as it saves a lot of pointer
115 accesses. This function is called for all Phi and Block nodes
118 compute_new_arity(ir_node *b) {
122 irg_v = get_irg_block_visited(current_ir_graph);
123 block_v = get_Block_block_visited(b);
124 if (block_v >= irg_v) {
125 /* we computed the number of preds for this block and saved it in the
127 return block_v - irg_v;
129 /* compute the number of good predecessors */
130 res = get_irn_arity(b);
131 for (i = 0; i < get_irn_arity(b); i++)
132 if (get_irn_opcode(get_irn_n(b, i)) == iro_Bad) res--;
133 /* save it in the flag. */
134 set_Block_block_visited(b, irg_v + res);
139 static INLINE void new_backedge_info(ir_node *n) {
140 switch(get_irn_opcode(n)) {
142 n->attr.block.cg_backedge = NULL;
143 n->attr.block.backedge = new_backedge_arr(current_ir_graph->obst, get_irn_arity(n));
146 n->attr.phi_backedge = new_backedge_arr(current_ir_graph->obst, get_irn_arity(n));
149 n->attr.filter.backedge = new_backedge_arr(current_ir_graph->obst, get_irn_arity(n));
155 /* Copies the node to the new obstack. The Ins of the new node point to
156 the predecessors on the old obstack. For block/phi nodes not all
157 predecessors might be copied. n->link points to the new node.
158 For Phi and Block nodes the function allocates in-arrays with an arity
159 only for useful predecessors. The arity is determined by counting
160 the non-bad predecessors of the block. */
162 copy_node (ir_node *n, void *env) {
166 if (get_irn_opcode(n) == iro_Block) {
168 new_arity = compute_new_arity(n);
169 n->attr.block.graph_arr = NULL;
171 block = get_nodes_Block(n);
172 if (get_irn_opcode(n) == iro_Phi) {
173 new_arity = compute_new_arity(block);
175 new_arity = get_irn_arity(n);
178 nn = new_ir_node(get_irn_dbg_info(n),
185 /* Copy the attributes. These might point to additional data. If this
186 was allocated on the old obstack the pointers now are dangling. This
187 frees e.g. the memory of the graph_arr allocated in new_immBlock. */
189 new_backedge_info(nn);
192 /* printf("\n old node: "); DDMSG2(n);
193 printf(" new node: "); DDMSG2(nn); */
197 /* Copies new predecessors of old node to new node remembered in link.
198 Spare the Bad predecessors of Phi and Block nodes. */
200 copy_preds (ir_node *n, void *env) {
204 nn = get_new_node(n);
206 /* printf("\n old node: "); DDMSG2(n);
207 printf(" new node: "); DDMSG2(nn);
208 printf(" arities: old: %d, new: %d\n", get_irn_arity(n), get_irn_arity(nn)); */
210 if (get_irn_opcode(n) == iro_Block) {
211 /* Don't copy Bad nodes. */
213 for (i = 0; i < get_irn_arity(n); i++)
214 if (get_irn_opcode(get_irn_n(n, i)) != iro_Bad) {
215 set_irn_n (nn, j, get_new_node(get_irn_n(n, i)));
216 /*if (is_backedge(n, i)) set_backedge(nn, j);*/
219 /* repair the block visited flag from above misuse. Repair it in both
220 graphs so that the old one can still be used. */
221 set_Block_block_visited(nn, 0);
222 set_Block_block_visited(n, 0);
223 /* Local optimization could not merge two subsequent blocks if
224 in array contained Bads. Now it's possible.
225 We don't call optimize_in_place as it requires
226 that the fields in ir_graph are set properly. */
227 if ((get_opt_control_flow_straightening()) &&
228 (get_Block_n_cfgpreds(nn) == 1) &&
229 (get_irn_op(get_Block_cfgpred(nn, 0)) == op_Jmp))
230 exchange(nn, get_nodes_Block(get_Block_cfgpred(nn, 0)));
231 } else if (get_irn_opcode(n) == iro_Phi) {
232 /* Don't copy node if corresponding predecessor in block is Bad.
233 The Block itself should not be Bad. */
234 block = get_nodes_Block(n);
235 set_irn_n (nn, -1, get_new_node(block));
237 for (i = 0; i < get_irn_arity(n); i++)
238 if (get_irn_opcode(get_irn_n(block, i)) != iro_Bad) {
239 set_irn_n (nn, j, get_new_node(get_irn_n(n, i)));
240 /*if (is_backedge(n, i)) set_backedge(nn, j);*/
243 /* If the pre walker reached this Phi after the post walker visited the
244 block block_visited is > 0. */
245 set_Block_block_visited(get_nodes_Block(n), 0);
246 /* Compacting the Phi's ins might generate Phis with only one
248 if (get_irn_arity(n) == 1)
249 exchange(n, get_irn_n(n, 0));
251 for (i = -1; i < get_irn_arity(n); i++)
252 set_irn_n (nn, i, get_new_node(get_irn_n(n, i)));
254 /* Now the new node is complete. We can add it to the hash table for cse.
255 @@@ inlinening aborts if we identify End. Why? */
256 if(get_irn_op(nn) != op_End)
257 add_identities (current_ir_graph->value_table, nn);
260 /* Copies the graph recursively, compacts the keepalive of the end node. */
263 ir_node *oe, *ne; /* old end, new end */
264 ir_node *ka; /* keep alive */
267 oe = get_irg_end(current_ir_graph);
268 /* copy the end node by hand, allocate dynamic in array! */
269 ne = new_ir_node(get_irn_dbg_info(oe),
276 /* Copy the attributes. Well, there might be some in the future... */
278 set_new_node(oe, ne);
280 /* copy the live nodes */
281 irg_walk(get_nodes_Block(oe), copy_node, copy_preds, NULL);
282 /* copy_preds for the end node ... */
283 set_nodes_Block(ne, get_new_node(get_nodes_Block(oe)));
285 /** ... and now the keep alives. **/
286 /* First pick the not marked block nodes and walk them. We must pick these
287 first as else we will oversee blocks reachable from Phis. */
288 for (i = 0; i < get_irn_arity(oe); i++) {
289 ka = get_irn_n(oe, i);
290 if ((get_irn_op(ka) == op_Block) &&
291 (get_irn_visited(ka) < get_irg_visited(current_ir_graph))) {
292 /* We must keep the block alive and copy everything reachable */
293 set_irg_visited(current_ir_graph, get_irg_visited(current_ir_graph)-1);
294 irg_walk(ka, copy_node, copy_preds, NULL);
295 add_End_keepalive(ne, get_new_node(ka));
299 /* Now pick the Phis. Here we will keep all! */
300 for (i = 0; i < get_irn_arity(oe); i++) {
301 ka = get_irn_n(oe, i);
302 if ((get_irn_op(ka) == op_Phi)) {
303 if (get_irn_visited(ka) < get_irg_visited(current_ir_graph)) {
304 /* We didn't copy the Phi yet. */
305 set_irg_visited(current_ir_graph, get_irg_visited(current_ir_graph)-1);
306 irg_walk(ka, copy_node, copy_preds, NULL);
308 add_End_keepalive(ne, get_new_node(ka));
313 /* Copies the graph reachable from current_ir_graph->end to the obstack
314 in current_ir_graph and fixes the environment.
315 Then fixes the fields in current_ir_graph containing nodes of the
318 copy_graph_env (void) {
320 /* Not all nodes remembered in current_ir_graph might be reachable
321 from the end node. Assure their link is set to NULL, so that
322 we can test whether new nodes have been computed. */
323 set_irn_link(get_irg_frame (current_ir_graph), NULL);
324 set_irn_link(get_irg_globals(current_ir_graph), NULL);
325 set_irn_link(get_irg_args (current_ir_graph), NULL);
327 /* we use the block walk flag for removing Bads from Blocks ins. */
328 inc_irg_block_visited(current_ir_graph);
333 /* fix the fields in current_ir_graph */
334 old_end = get_irg_end(current_ir_graph);
335 set_irg_end (current_ir_graph, get_new_node(old_end));
337 set_irg_end_block (current_ir_graph, get_new_node(get_irg_end_block(current_ir_graph)));
338 if (get_irn_link(get_irg_frame(current_ir_graph)) == NULL) {
339 copy_node (get_irg_frame(current_ir_graph), NULL);
340 copy_preds(get_irg_frame(current_ir_graph), NULL);
342 if (get_irn_link(get_irg_globals(current_ir_graph)) == NULL) {
343 copy_node (get_irg_globals(current_ir_graph), NULL);
344 copy_preds(get_irg_globals(current_ir_graph), NULL);
346 if (get_irn_link(get_irg_args(current_ir_graph)) == NULL) {
347 copy_node (get_irg_args(current_ir_graph), NULL);
348 copy_preds(get_irg_args(current_ir_graph), NULL);
350 set_irg_start (current_ir_graph, get_new_node(get_irg_start(current_ir_graph)));
352 set_irg_start_block(current_ir_graph,
353 get_new_node(get_irg_start_block(current_ir_graph)));
354 set_irg_frame (current_ir_graph, get_new_node(get_irg_frame(current_ir_graph)));
355 set_irg_globals(current_ir_graph, get_new_node(get_irg_globals(current_ir_graph)));
356 set_irg_args (current_ir_graph, get_new_node(get_irg_args(current_ir_graph)));
357 if (get_irn_link(get_irg_bad(current_ir_graph)) == NULL) {
358 copy_node(get_irg_bad(current_ir_graph), NULL);
359 copy_preds(get_irg_bad(current_ir_graph), NULL);
361 set_irg_bad(current_ir_graph, get_new_node(get_irg_bad(current_ir_graph)));
362 /* GL removed: we need unknown with mode for analyses.
363 if (get_irn_link(get_irg_unknown(current_ir_graph)) == NULL) {
364 copy_node(get_irg_unknown(current_ir_graph), NULL);
365 copy_preds(get_irg_unknown(current_ir_graph), NULL);
367 set_irg_unknown(current_ir_graph, get_new_node(get_irg_unknown(current_ir_graph)));
371 /* Copies all reachable nodes to a new obstack. Removes bad inputs
372 from block nodes and the corresponding inputs from Phi nodes.
373 Merges single exit blocks with single entry blocks and removes
375 Adds all new nodes to a new hash table for cse. Does not
376 perform cse, so the hash table might contain common subexpressions. */
377 /* Amroq call this emigrate() */
379 dead_node_elimination(ir_graph *irg) {
381 struct obstack *graveyard_obst = NULL;
382 struct obstack *rebirth_obst = NULL;
384 /* Remember external state of current_ir_graph. */
385 rem = current_ir_graph;
386 current_ir_graph = irg;
388 /* Handle graph state */
389 assert(get_irg_phase_state(current_ir_graph) != phase_building);
390 free_outs(current_ir_graph);
392 /* @@@ so far we loose loops when copying */
393 set_irg_loop(current_ir_graph, NULL);
395 if (get_optimize() && get_opt_dead_node_elimination()) {
397 /* A quiet place, where the old obstack can rest in peace,
398 until it will be cremated. */
399 graveyard_obst = irg->obst;
401 /* A new obstack, where the reachable nodes will be copied to. */
402 rebirth_obst = (struct obstack *) xmalloc (sizeof (struct obstack));
403 current_ir_graph->obst = rebirth_obst;
404 obstack_init (current_ir_graph->obst);
406 /* We also need a new hash table for cse */
407 del_identities (irg->value_table);
408 irg->value_table = new_identities ();
410 /* Copy the graph from the old to the new obstack */
413 /* Free memory from old unoptimized obstack */
414 obstack_free(graveyard_obst, 0); /* First empty the obstack ... */
415 xfree (graveyard_obst); /* ... then free it. */
418 current_ir_graph = rem;
421 /* Relink bad predeseccors of a block and store the old in array to the
422 link field. This function is called by relink_bad_predecessors().
423 The array of link field starts with the block operand at position 0.
424 If block has bad predecessors, create a new in array without bad preds.
425 Otherwise let in array untouched. */
426 static void relink_bad_block_predecessors(ir_node *n, void *env) {
427 ir_node **new_in, *irn;
428 int i, new_irn_n, old_irn_arity, new_irn_arity = 0;
430 /* if link field of block is NULL, look for bad predecessors otherwise
431 this is allready done */
432 if (get_irn_op(n) == op_Block &&
433 get_irn_link(n) == NULL) {
435 /* save old predecessors in link field (position 0 is the block operand)*/
436 set_irn_link(n, (void *)get_irn_in(n));
438 /* count predecessors without bad nodes */
439 old_irn_arity = get_irn_arity(n);
440 for (i = 0; i < old_irn_arity; i++)
441 if (!is_Bad(get_irn_n(n, i))) new_irn_arity++;
443 /* arity changing: set new predecessors without bad nodes */
444 if (new_irn_arity < old_irn_arity) {
445 /* get new predecessor array without Block predecessor */
446 new_in = NEW_ARR_D (ir_node *, current_ir_graph->obst, (new_irn_arity+1));
448 /* set new predeseccors in array */
451 for (i = 1; i < old_irn_arity; i++) {
452 irn = get_irn_n(n, i);
453 if (!is_Bad(irn)) new_in[new_irn_n++] = irn;
456 } /* ir node has bad predecessors */
458 } /* Block is not relinked */
461 /* Relinks Bad predecesors from Bocks and Phis called by walker
462 remove_bad_predecesors(). If n is a Block, call
463 relink_bad_block_redecessors(). If n is a Phinode, call also the relinking
464 function of Phi's Block. If this block has bad predecessors, relink preds
466 static void relink_bad_predecessors(ir_node *n, void *env) {
467 ir_node *block, **old_in;
468 int i, old_irn_arity, new_irn_arity;
470 /* relink bad predeseccors of a block */
471 if (get_irn_op(n) == op_Block)
472 relink_bad_block_predecessors(n, env);
474 /* If Phi node relink its block and its predecessors */
475 if (get_irn_op(n) == op_Phi) {
477 /* Relink predeseccors of phi's block */
478 block = get_nodes_Block(n);
479 if (get_irn_link(block) == NULL)
480 relink_bad_block_predecessors(block, env);
482 old_in = (ir_node **)get_irn_link(block); /* Of Phi's Block */
483 old_irn_arity = ARR_LEN(old_in);
485 /* Relink Phi predeseccors if count of predeseccors changed */
486 if (old_irn_arity != ARR_LEN(get_irn_in(block))) {
487 /* set new predeseccors in array
488 n->in[0] remains the same block */
490 for(i = 1; i < old_irn_arity; i++)
491 if (!is_Bad((ir_node *)old_in[i])) n->in[new_irn_arity++] = n->in[i];
493 ARR_SETLEN(ir_node *, n->in, new_irn_arity);
496 } /* n is a Phi node */
499 /* Removes Bad Bad predecesors from Blocks and the corresponding
500 inputs to Phi nodes as in dead_node_elimination but without
502 On walking up set the link field to NULL, on walking down call
503 relink_bad_predecessors() (This function stores the old in array
504 to the link field and sets a new in array if arity of predecessors
506 void remove_bad_predecessors(ir_graph *irg) {
507 irg_walk_graph(irg, init_link, relink_bad_predecessors, NULL);
511 /**********************************************************************/
512 /* Funcionality for inlining */
513 /**********************************************************************/
515 /* Copy node for inlineing. Updates attributes that change when
516 * inlineing but not for dead node elimination.
518 * Copies the node by calling copy_node and then updates the entity if
519 * it's a local one. env must be a pointer of the frame type of the
520 * inlined procedure. The new entities must be in the link field of
523 copy_node_inline (ir_node *n, void *env) {
525 type *frame_tp = (type *)env;
528 if (get_irn_op(n) == op_Sel) {
529 new = get_new_node (n);
530 assert(get_irn_op(new) == op_Sel);
531 if (get_entity_owner(get_Sel_entity(n)) == frame_tp) {
532 set_Sel_entity(new, get_entity_link(get_Sel_entity(n)));
534 } else if (get_irn_op(n) == op_Block) {
535 new = get_new_node (n);
536 new->attr.block.irg = current_ir_graph;
541 void inline_method(ir_node *call, ir_graph *called_graph) {
543 ir_node *post_call, *post_bl;
545 ir_node *end, *end_bl;
549 ir_node *cf_op = NULL, *bl;
550 int arity, n_ret, n_exc, n_res, i, j, rem_opt;
553 if (!get_optimize() || !get_opt_inline()) return;
554 /* -- Turn off optimizations, this can cause problems when allocating new nodes. -- */
555 rem_opt = get_optimize();
558 /* Handle graph state */
559 assert(get_irg_phase_state(current_ir_graph) != phase_building);
560 assert(get_irg_pinned(current_ir_graph) == pinned);
561 assert(get_irg_pinned(called_graph) == pinned);
562 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
563 set_irg_outs_inconsistent(current_ir_graph);
565 /* -- Check preconditions -- */
566 assert(get_irn_op(call) == op_Call);
567 /* @@@ does not work for InterfaceIII.java after cgana
568 assert(get_Call_type(call) == get_entity_type(get_irg_ent(called_graph)));
569 assert(smaller_type(get_entity_type(get_irg_ent(called_graph)),
570 get_Call_type(call)));
572 assert(get_type_tpop(get_Call_type(call)) == type_method);
573 if (called_graph == current_ir_graph) {
574 set_optimize(rem_opt);
579 the procedure and later replaces the Start node of the called graph.
580 Post_call is the old Call node and collects the results of the called
581 graph. Both will end up being a tuple. -- */
582 post_bl = get_nodes_Block(call);
583 set_irg_current_block(current_ir_graph, post_bl);
584 /* XxMxPxP of Start + parameter of Call */
586 in[1] = get_Call_mem(call);
587 in[2] = get_irg_frame(current_ir_graph);
588 in[3] = get_irg_globals(current_ir_graph);
589 in[4] = new_Tuple (get_Call_n_params(call), get_Call_param_arr(call));
590 pre_call = new_Tuple(5, in);
594 The new block gets the ins of the old block, pre_call and all its
595 predecessors and all Phi nodes. -- */
596 part_block(pre_call);
598 /* -- Prepare state for dead node elimination -- */
599 /* Visited flags in calling irg must be >= flag in called irg.
600 Else walker and arity computation will not work. */
601 if (get_irg_visited(current_ir_graph) <= get_irg_visited(called_graph))
602 set_irg_visited(current_ir_graph, get_irg_visited(called_graph)+1);
603 if (get_irg_block_visited(current_ir_graph)< get_irg_block_visited(called_graph))
604 set_irg_block_visited(current_ir_graph, get_irg_block_visited(called_graph));
605 /* Set pre_call as new Start node in link field of the start node of
606 calling graph and pre_calls block as new block for the start block
608 Further mark these nodes so that they are not visited by the
610 set_irn_link(get_irg_start(called_graph), pre_call);
611 set_irn_visited(get_irg_start(called_graph),
612 get_irg_visited(current_ir_graph));
613 set_irn_link(get_irg_start_block(called_graph),
614 get_nodes_Block(pre_call));
615 set_irn_visited(get_irg_start_block(called_graph),
616 get_irg_visited(current_ir_graph));
618 /* Initialize for compaction of in arrays */
619 inc_irg_block_visited(current_ir_graph);
621 /* -- Replicate local entities of the called_graph -- */
622 /* copy the entities. */
623 called_frame = get_irg_frame_type(called_graph);
624 for (i = 0; i < get_class_n_members(called_frame); i++) {
625 entity *new_ent, *old_ent;
626 old_ent = get_class_member(called_frame, i);
627 new_ent = copy_entity_own(old_ent, get_cur_frame_type());
628 set_entity_link(old_ent, new_ent);
631 /* visited is > than that of called graph. With this trick visited will
632 remain unchanged so that an outer walker, e.g., searching the call nodes
633 to inline, calling this inline will not visit the inlined nodes. */
634 set_irg_visited(current_ir_graph, get_irg_visited(current_ir_graph)-1);
636 /* -- Performing dead node elimination inlines the graph -- */
637 /* Copies the nodes to the obstack of current_ir_graph. Updates links to new
639 /* @@@ endless loops are not copied!! -- they should be, I think... */
640 irg_walk(get_irg_end(called_graph), copy_node_inline, copy_preds,
641 get_irg_frame_type(called_graph));
643 /* Repair called_graph */
644 set_irg_visited(called_graph, get_irg_visited(current_ir_graph));
645 set_irg_block_visited(called_graph, get_irg_block_visited(current_ir_graph));
646 set_Block_block_visited(get_irg_start_block(called_graph), 0);
648 /* -- Merge the end of the inlined procedure with the call site -- */
649 /* We will turn the old Call node into a Tuple with the following
652 0: Phi of all Memories of Return statements.
653 1: Jmp from new Block that merges the control flow from all exception
654 predecessors of the old end block.
655 2: Tuple of all arguments.
656 3: Phi of Exception memories.
659 /* -- Precompute some values -- */
660 end_bl = get_new_node(get_irg_end_block(called_graph));
661 end = get_new_node(get_irg_end(called_graph));
662 arity = get_irn_arity(end_bl); /* arity = n_exc + n_ret */
663 n_res = get_method_n_ress(get_Call_type(call));
665 res_pred = (ir_node **) malloc (n_res * sizeof (ir_node *));
666 cf_pred = (ir_node **) malloc (arity * sizeof (ir_node *));
668 set_irg_current_block(current_ir_graph, post_bl); /* just to make sure */
670 /* -- archive keepalives -- */
671 for (i = 0; i < get_irn_arity(end); i++)
672 add_End_keepalive(get_irg_end(current_ir_graph), get_irn_n(end, i));
673 /* The new end node will die, but the in array is not on the obstack ... */
677 Return nodes by Jump nodes. -- */
679 for (i = 0; i < arity; i++) {
681 ret = get_irn_n(end_bl, i);
682 if (get_irn_op(ret) == op_Return) {
683 cf_pred[n_ret] = new_r_Jmp(current_ir_graph, get_nodes_Block(ret));
687 set_irn_in(post_bl, n_ret, cf_pred);
690 turned into a tuple. -- */
691 turn_into_tuple(post_call, 4);
692 /* First the Memory-Phi */
694 for (i = 0; i < arity; i++) {
695 ret = get_irn_n(end_bl, i);
696 if (get_irn_op(ret) == op_Return) {
697 cf_pred[n_ret] = get_Return_mem(ret);
701 phi = new_Phi(n_ret, cf_pred, mode_M);
702 set_Tuple_pred(call, 0, phi);
703 /* Conserve Phi-list for further inlinings -- but might be optimized */
704 if (get_nodes_Block(phi) == post_bl) {
705 set_irn_link(phi, get_irn_link(post_bl));
706 set_irn_link(post_bl, phi);
708 /* Now the real results */
710 for (j = 0; j < n_res; j++) {
712 for (i = 0; i < arity; i++) {
713 ret = get_irn_n(end_bl, i);
714 if (get_irn_op(ret) == op_Return) {
715 cf_pred[n_ret] = get_Return_res(ret, j);
719 phi = new_Phi(n_ret, cf_pred, get_irn_mode(cf_pred[0]));
721 /* Conserve Phi-list for further inlinings -- but might be optimized */
722 if (get_nodes_Block(phi) == post_bl) {
723 set_irn_link(phi, get_irn_link(post_bl));
724 set_irn_link(post_bl, phi);
727 set_Tuple_pred(call, 2, new_Tuple(n_res, res_pred));
729 set_Tuple_pred(call, 2, new_Bad());
731 /* Finally the exception control flow. We need to add a Phi node to
732 collect the memory containing the exception objects. Further we need
733 to add another block to get a correct representation of this Phi. To
734 this block we add a Jmp that resolves into the X output of the Call
735 when the Call is turned into a tuple. */
737 for (i = 0; i < arity; i++) {
739 ret = get_irn_n(end_bl, i);
740 if (is_fragile_op(skip_Proj(ret)) || (get_irn_op(skip_Proj(ret)) == op_Raise)) {
741 cf_pred[n_exc] = ret;
746 new_Block(n_exc, cf_pred); /* watch it: current_block is changed! */
747 set_Tuple_pred(call, 1, new_Jmp());
748 /* The Phi for the memories with the exception objects */
750 for (i = 0; i < arity; i++) {
752 ret = skip_Proj(get_irn_n(end_bl, i));
753 if (get_irn_op(ret) == op_Call) {
754 cf_pred[n_exc] = new_r_Proj(current_ir_graph, get_nodes_Block(ret), ret, mode_M, 3);
756 } else if (is_fragile_op(ret)) {
757 /* We rely that all cfops have the memory output at the same position. */
758 cf_pred[n_exc] = new_r_Proj(current_ir_graph, get_nodes_Block(ret), ret, mode_M, 0);
760 } else if (get_irn_op(ret) == op_Raise) {
761 cf_pred[n_exc] = new_r_Proj(current_ir_graph, get_nodes_Block(ret), ret, mode_M, 1);
765 set_Tuple_pred(call, 3, new_Phi(n_exc, cf_pred, mode_M));
767 set_Tuple_pred(call, 1, new_Bad());
768 set_Tuple_pred(call, 3, new_Bad());
774 /* -- If the exception control flow from the inlined Call directly
775 branched to the end block we now have the following control
776 flow predecessor pattern: ProjX -> Tuple -> Jmp. We must
777 remove the Jmp along with it's empty block and add Jmp's
778 predecessors as predecessors of this end block. No problem if
779 there is no exception, because then branches Bad to End which
781 /* find the problematic predecessor of the end block. */
782 end_bl = get_irg_end_block(current_ir_graph);
783 for (i = 0; i < get_Block_n_cfgpreds(end_bl); i++) {
784 cf_op = get_Block_cfgpred(end_bl, i);
785 if (get_irn_op(cf_op) == op_Proj) {
786 cf_op = get_Proj_pred(cf_op);
787 if ((get_irn_op(cf_op) == op_Tuple) && (cf_op == call)) {
788 // There are unoptimized tuples from inlineing before when no exc
789 assert(get_Proj_proj(get_Block_cfgpred(end_bl, i)) == pn_Call_X_except);
790 cf_op = get_Tuple_pred(cf_op, pn_Call_X_except);
791 assert(get_irn_op(cf_op) == op_Jmp);
797 if (i < get_Block_n_cfgpreds(end_bl)) {
798 bl = get_nodes_Block(cf_op);
799 arity = get_Block_n_cfgpreds(end_bl) + get_Block_n_cfgpreds(bl) - 1;
800 cf_pred = (ir_node **) malloc (arity * sizeof (ir_node *));
801 for (j = 0; j < i; j++)
802 cf_pred[j] = get_Block_cfgpred(end_bl, j);
803 for (j = j; j < i + get_Block_n_cfgpreds(bl); j++)
804 cf_pred[j] = get_Block_cfgpred(bl, j-i);
805 for (j = j; j < arity; j++)
806 cf_pred[j] = get_Block_cfgpred(end_bl, j-get_Block_n_cfgpreds(bl) +1);
807 set_irn_in(end_bl, arity, cf_pred);
809 // Remove the exception pred from post-call Tuple.
810 set_Tuple_pred(call, pn_Call_X_except, new_Bad());
814 /* -- Turn cse back on. -- */
815 set_optimize(rem_opt);
818 /********************************************************************/
819 /* Apply inlineing to small methods. */
820 /********************************************************************/
824 /* It makes no sense to inline too many calls in one procedure. Anyways,
825 I didn't get a version with NEW_ARR_F to run. */
826 #define MAX_INLINE 1024
828 static void collect_calls(ir_node *call, void *env) {
829 ir_node **calls = (ir_node **)env;
832 ir_graph *called_irg;
834 if (get_irn_op(call) != op_Call) return;
836 addr = get_Call_ptr(call);
837 if (get_irn_op(addr) == op_Const) {
838 /* Check whether the constant is the pointer to a compiled entity. */
839 tv = get_Const_tarval(addr);
840 if (tarval_to_entity(tv)) {
841 called_irg = get_entity_irg(tarval_to_entity(tv));
842 if (called_irg && pos < MAX_INLINE) {
843 /* The Call node calls a locally defined method. Remember to inline. */
851 /* Inlines all small methods at call sites where the called address comes
852 from a Const node that references the entity representing the called
854 The size argument is a rough measure for the code size of the method:
855 Methods where the obstack containing the firm graph is smaller than
857 void inline_small_irgs(ir_graph *irg, int size) {
859 ir_node *calls[MAX_INLINE];
860 ir_graph *rem = current_ir_graph;
862 if (!(get_optimize() && get_opt_inline())) return;
864 current_ir_graph = irg;
865 /* Handle graph state */
866 assert(get_irg_phase_state(current_ir_graph) != phase_building);
868 /* Find Call nodes to inline.
869 (We can not inline during a walk of the graph, as inlineing the same
870 method several times changes the visited flag of the walked graph:
871 after the first inlineing visited of the callee equals visited of
872 the caller. With the next inlineing both are increased.) */
874 irg_walk(get_irg_end(irg), NULL, collect_calls, (void *) calls);
876 if ((pos > 0) && (pos < MAX_INLINE)) {
877 /* There are calls to inline */
878 collect_phiprojs(irg);
879 for (i = 0; i < pos; i++) {
882 tv = get_Const_tarval(get_Call_ptr(calls[i]));
883 callee = get_entity_irg(tarval_to_entity(tv));
884 if ((_obstack_memory_used(callee->obst) - obstack_room(callee->obst)) < size) {
885 inline_method(calls[i], callee);
890 current_ir_graph = rem;
894 /********************************************************************/
895 /* Code Placement. Pinns all floating nodes to a block where they */
896 /* will be executed only if needed. */
897 /********************************************************************/
899 static pdeq *worklist; /* worklist of ir_node*s */
901 /* Find the earliest correct block for N. --- Place N into the
902 same Block as its dominance-deepest Input. */
904 place_floats_early (ir_node *n)
908 /* we must not run into an infinite loop */
909 assert (irn_not_visited(n));
912 /* Place floating nodes. */
913 if (get_op_pinned(get_irn_op(n)) == floats) {
915 ir_node *b = new_Bad(); /* The block to place this node in */
917 assert(get_irn_op(n) != op_Block);
919 if ((get_irn_op(n) == op_Const) ||
920 (get_irn_op(n) == op_SymConst) ||
922 (get_irn_op(n) == op_Unknown)) {
923 /* These nodes will not be placed by the loop below. */
924 b = get_irg_start_block(current_ir_graph);
928 /* find the block for this node. */
929 for (i = 0; i < get_irn_arity(n); i++) {
930 ir_node *dep = get_irn_n(n, i);
932 if ((irn_not_visited(dep)) &&
933 (get_op_pinned(get_irn_op(dep)) == floats)) {
934 place_floats_early (dep);
936 /* Because all loops contain at least one pinned node, now all
937 our inputs are either pinned or place_early has already
938 been finished on them. We do not have any unfinished inputs! */
939 dep_block = get_nodes_Block(dep);
940 if ((!is_Bad(dep_block)) &&
941 (get_Block_dom_depth(dep_block) > depth)) {
943 depth = get_Block_dom_depth(dep_block);
945 /* Avoid that the node is placed in the Start block */
946 if ((depth == 1) && (get_Block_dom_depth(get_nodes_Block(n)) > 1)) {
947 b = get_Block_cfg_out(get_irg_start_block(current_ir_graph), 0);
948 assert(b != get_irg_start_block(current_ir_graph));
952 set_nodes_Block(n, b);
955 /* Add predecessors of non floating nodes on worklist. */
956 start = (get_irn_op(n) == op_Block) ? 0 : -1;
957 for (i = start; i < get_irn_arity(n); i++) {
958 ir_node *pred = get_irn_n(n, i);
959 if (irn_not_visited(pred)) {
960 pdeq_putr (worklist, pred);
965 /* Floating nodes form subgraphs that begin at nodes as Const, Load,
966 Start, Call and end at pinned nodes as Store, Call. Place_early
967 places all floating nodes reachable from its argument through floating
968 nodes and adds all beginnings at pinned nodes to the worklist. */
969 static INLINE void place_early (void) {
971 inc_irg_visited(current_ir_graph);
973 /* this inits the worklist */
974 place_floats_early (get_irg_end(current_ir_graph));
976 /* Work the content of the worklist. */
977 while (!pdeq_empty (worklist)) {
978 ir_node *n = pdeq_getl (worklist);
979 if (irn_not_visited(n)) place_floats_early (n);
982 set_irg_outs_inconsistent(current_ir_graph);
983 current_ir_graph->pinned = pinned;
987 /* deepest common dominance ancestor of DCA and CONSUMER of PRODUCER */
989 consumer_dom_dca (ir_node *dca, ir_node *consumer, ir_node *producer)
991 ir_node *block = NULL;
993 /* Compute the latest block into which we can place a node so that it is
995 if (get_irn_op(consumer) == op_Phi) {
996 /* our comsumer is a Phi-node, the effective use is in all those
997 blocks through which the Phi-node reaches producer */
999 ir_node *phi_block = get_nodes_Block(consumer);
1000 for (i = 0; i < get_irn_arity(consumer); i++) {
1001 if (get_irn_n(consumer, i) == producer) {
1002 block = get_nodes_Block(get_Block_cfgpred(phi_block, i));
1006 assert(is_no_Block(consumer));
1007 block = get_nodes_Block(consumer);
1010 /* Compute the deepest common ancestor of block and dca. */
1012 if (!dca) return block;
1013 while (get_Block_dom_depth(block) > get_Block_dom_depth(dca))
1014 block = get_Block_idom(block);
1015 while (get_Block_dom_depth(dca) > get_Block_dom_depth(block))
1016 dca = get_Block_idom(dca);
1017 while (block != dca)
1018 { block = get_Block_idom(block); dca = get_Block_idom(dca); }
1023 static INLINE int get_irn_loop_depth(ir_node *n) {
1024 return get_loop_depth(get_irn_loop(n));
1027 /* Move n to a block with less loop depth than it's current block. The
1028 new block must be dominated by early. */
1030 move_out_of_loops (ir_node *n, ir_node *early)
1032 ir_node *best, *dca;
1036 /* Find the region deepest in the dominator tree dominating
1037 dca with the least loop nesting depth, but still dominated
1038 by our early placement. */
1039 dca = get_nodes_Block(n);
1041 while (dca != early) {
1042 dca = get_Block_idom(dca);
1043 if (!dca) break; /* should we put assert(dca)? */
1044 if (get_irn_loop_depth(dca) < get_irn_loop_depth(best)) {
1048 if (best != get_nodes_Block(n)) {
1050 printf("Moving out of loop: "); DDMN(n);
1051 printf(" Outermost block: "); DDMN(early);
1052 printf(" Best block: "); DDMN(best);
1053 printf(" Innermost block: "); DDMN(get_nodes_Block(n));
1055 set_nodes_Block(n, best);
1059 /* Find the latest legal block for N and place N into the
1060 `optimal' Block between the latest and earliest legal block.
1061 The `optimal' block is the dominance-deepest block of those
1062 with the least loop-nesting-depth. This places N out of as many
1063 loops as possible and then makes it as controldependant as
1066 place_floats_late (ir_node *n)
1071 assert (irn_not_visited(n)); /* no multiple placement */
1073 /* no need to place block nodes, control nodes are already placed. */
1074 if ((get_irn_op(n) != op_Block) &&
1076 (get_irn_mode(n) != mode_X)) {
1077 /* Remember the early palacement of this block to move it
1078 out of loop no further than the early placement. */
1079 early = get_nodes_Block(n);
1080 /* Assure that our users are all placed, except the Phi-nodes.
1081 --- Each dataflow cycle contains at least one Phi-node. We
1082 have to break the `user has to be placed before the
1083 producer' dependance cycle and the Phi-nodes are the
1084 place to do so, because we need to base our placement on the
1085 final region of our users, which is OK with Phi-nodes, as they
1086 are pinned, and they never have to be placed after a
1087 producer of one of their inputs in the same block anyway. */
1088 for (i = 0; i < get_irn_n_outs(n); i++) {
1089 ir_node *succ = get_irn_out(n, i);
1090 if (irn_not_visited(succ) && (get_irn_op(succ) != op_Phi))
1091 place_floats_late (succ);
1094 /* We have to determine the final block of this node... except for
1096 if ((get_op_pinned(get_irn_op(n)) == floats) &&
1097 (get_irn_op(n) != op_Const) &&
1098 (get_irn_op(n) != op_SymConst)) {
1099 ir_node *dca = NULL; /* deepest common ancestor in the
1100 dominator tree of all nodes'
1101 blocks depending on us; our final
1102 placement has to dominate DCA. */
1103 for (i = 0; i < get_irn_n_outs(n); i++) {
1104 dca = consumer_dom_dca (dca, get_irn_out(n, i), n);
1106 set_nodes_Block(n, dca);
1108 move_out_of_loops (n, early);
1112 mark_irn_visited(n);
1114 /* Add predecessors of all non-floating nodes on list. (Those of floating
1115 nodes are placeded already and therefore are marked.) */
1116 for (i = 0; i < get_irn_n_outs(n); i++) {
1117 if (irn_not_visited(get_irn_out(n, i))) {
1118 pdeq_putr (worklist, get_irn_out(n, i));
1123 static INLINE void place_late(void) {
1125 inc_irg_visited(current_ir_graph);
1127 /* This fills the worklist initially. */
1128 place_floats_late(get_irg_start_block(current_ir_graph));
1129 /* And now empty the worklist again... */
1130 while (!pdeq_empty (worklist)) {
1131 ir_node *n = pdeq_getl (worklist);
1132 if (irn_not_visited(n)) place_floats_late(n);
1136 void place_code(ir_graph *irg) {
1137 ir_graph *rem = current_ir_graph;
1138 current_ir_graph = irg;
1140 if (!(get_optimize() && get_opt_global_cse())) return;
1142 /* Handle graph state */
1143 assert(get_irg_phase_state(irg) != phase_building);
1144 if (get_irg_dom_state(irg) != dom_consistent)
1147 construct_backedges(irg);
1149 /* Place all floating nodes as early as possible. This guarantees
1150 a legal code placement. */
1151 worklist = new_pdeq ();
1154 /* place_early invalidates the outs, place_late needs them. */
1156 /* Now move the nodes down in the dominator tree. This reduces the
1157 unnecessary executions of the node. */
1160 set_irg_outs_inconsistent(current_ir_graph);
1161 del_pdeq (worklist);
1162 current_ir_graph = rem;
1167 /********************************************************************/
1168 /* Control flow optimization. */
1169 /* Removes Bad control flow predecessors and empty blocks. A block */
1170 /* is empty if it contains only a Jmp node. */
1171 /* Blocks can only be removed if they are not needed for the */
1172 /* semantics of Phi nodes. */
1173 /********************************************************************/
1175 /* Removes Tuples from Block control flow predecessors.
1176 Optimizes blocks with equivalent_node().
1177 Replaces n by Bad if n is unreachable control flow. */
1178 static void merge_blocks(ir_node *n, void *env) {
1180 set_irn_link(n, NULL);
1182 if (get_irn_op(n) == op_Block) {
1184 for (i = 0; i < get_Block_n_cfgpreds(n); i++)
1185 /* GL @@@ : is this possible? if (get_opt_normalize()) -- added, all tests go throug.
1186 A different order of optimizations might cause problems. */
1187 if (get_opt_normalize())
1188 set_Block_cfgpred(n, i, skip_Tuple(get_Block_cfgpred(n, i)));
1189 } else if (get_optimize() && (get_irn_mode(n) == mode_X)) {
1190 /* We will soon visit a block. Optimize it before visiting! */
1191 ir_node *b = get_nodes_Block(n);
1192 ir_node *new = equivalent_node(b);
1193 while (irn_not_visited(b) && (!is_Bad(new)) && (new != b)) {
1194 /* We would have to run gigo if new is bad, so we
1195 promote it directly below. */
1196 assert(((b == new) ||
1197 get_opt_control_flow_straightening() ||
1198 get_opt_control_flow_weak_simplification()) &&
1199 ("strange flag setting"));
1202 new = equivalent_node(b);
1204 /* GL @@@ get_opt_normalize hinzugefuegt, 5.5.2003 */
1205 if (is_Bad(new) && get_opt_normalize()) exchange (n, new_Bad());
1209 /* Collects all Phi nodes in link list of Block.
1210 Marks all blocks "block_visited" if they contain a node other
1212 static void collect_nodes(ir_node *n, void *env) {
1213 if (is_no_Block(n)) {
1214 ir_node *b = get_nodes_Block(n);
1216 if ((get_irn_op(n) == op_Phi)) {
1217 /* Collect Phi nodes to compact ins along with block's ins. */
1218 set_irn_link(n, get_irn_link(b));
1220 } else if (get_irn_op(n) != op_Jmp) { /* Check for non empty block. */
1221 mark_Block_block_visited(b);
1226 /* Returns true if pred is pred of block */
1227 static int is_pred_of(ir_node *pred, ir_node *b) {
1229 for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
1230 ir_node *b_pred = get_nodes_Block(get_Block_cfgpred(b, i));
1231 if (b_pred == pred) return 1;
1236 static int test_whether_dispensable(ir_node *b, int pos) {
1237 int i, j, n_preds = 1;
1238 int dispensable = 1;
1239 ir_node *cfop = get_Block_cfgpred(b, pos);
1240 ir_node *pred = get_nodes_Block(cfop);
1242 if (get_Block_block_visited(pred) + 1
1243 < get_irg_block_visited(current_ir_graph)) {
1244 if (!get_optimize() || !get_opt_control_flow_strong_simplification()) {
1245 /* Mark block so that is will not be removed. */
1246 set_Block_block_visited(pred, get_irg_block_visited(current_ir_graph)-1);
1249 /* Seems to be empty. */
1250 if (!get_irn_link(b)) {
1251 /* There are no Phi nodes ==> dispensable. */
1252 n_preds = get_Block_n_cfgpreds(pred);
1254 /* b's pred blocks and pred's pred blocks must be pairwise disjunct.
1255 Work preds < pos as if they were already removed. */
1256 for (i = 0; i < pos; i++) {
1257 ir_node *b_pred = get_nodes_Block(get_Block_cfgpred(b, i));
1258 if (get_Block_block_visited(b_pred) + 1
1259 < get_irg_block_visited(current_ir_graph)) {
1260 for (j = 0; j < get_Block_n_cfgpreds(b_pred); j++) {
1261 ir_node *b_pred_pred = get_nodes_Block(get_Block_cfgpred(b_pred, j));
1262 if (is_pred_of(b_pred_pred, pred)) dispensable = 0;
1265 if (is_pred_of(b_pred, pred)) dispensable = 0;
1268 for (i = pos +1; i < get_Block_n_cfgpreds(b); i++) {
1269 ir_node *b_pred = get_nodes_Block(get_Block_cfgpred(b, i));
1270 if (is_pred_of(b_pred, pred)) dispensable = 0;
1273 set_Block_block_visited(pred, get_irg_block_visited(current_ir_graph)-1);
1276 n_preds = get_Block_n_cfgpreds(pred);
1284 static void optimize_blocks(ir_node *b, void *env) {
1285 int i, j, k, max_preds, n_preds;
1286 ir_node *pred, *phi;
1289 /* Count the number of predecessor if this block is merged with pred blocks
1292 for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
1293 max_preds += test_whether_dispensable(b, i);
1295 in = (ir_node **) malloc(max_preds * sizeof(ir_node *));
1298 printf(" working on "); DDMN(b);
1299 for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
1300 pred = get_nodes_Block(get_Block_cfgpred(b, i));
1301 if (is_Bad(get_Block_cfgpred(b, i))) {
1302 printf(" removing Bad %i\n ", i);
1303 } else if (get_Block_block_visited(pred) +1
1304 < get_irg_block_visited(current_ir_graph)) {
1305 printf(" removing pred %i ", i); DDMN(pred);
1306 } else { printf(" Nothing to do for "); DDMN(pred); }
1308 * end Debug output **/
1310 /** Fix the Phi nodes **/
1311 phi = get_irn_link(b);
1313 assert(get_irn_op(phi) == op_Phi);
1314 /* Find the new predecessors for the Phi */
1316 for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
1317 pred = get_nodes_Block(get_Block_cfgpred(b, i));
1318 if (is_Bad(get_Block_cfgpred(b, i))) {
1320 } else if (get_Block_block_visited(pred) +1
1321 < get_irg_block_visited(current_ir_graph)) {
1322 /* It's an empty block and not yet visited. */
1323 ir_node *phi_pred = get_Phi_pred(phi, i);
1324 for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
1325 if (get_nodes_Block(phi_pred) == pred) {
1326 assert(get_irn_op(phi_pred) == op_Phi); /* Block is empty!! */
1327 in[n_preds] = get_Phi_pred(phi_pred, j);
1329 in[n_preds] = phi_pred;
1333 /* The Phi_pred node is replaced now if it is a Phi.
1334 In Schleifen kann offenbar der entfernte Phi Knoten legal verwendet werden.
1335 Daher muss der Phiknoten durch den neuen ersetzt werden.
1336 Weiter muss der alte Phiknoten entfernt werden (durch ersetzen oder
1337 durch einen Bad) damit er aus den keep_alive verschwinden kann.
1338 Man sollte also, falls keine Schleife vorliegt, exchange mit new_Bad
1340 if (get_nodes_Block(phi_pred) == pred) {
1341 /* remove the Phi as it might be kept alive. Further there
1342 might be other users. */
1343 exchange(phi_pred, phi); /* geht, ist aber doch semantisch falsch! Warum?? */
1346 in[n_preds] = get_Phi_pred(phi, i);
1351 set_irn_in(phi, n_preds, in);
1353 phi = get_irn_link(phi);
1357 This happens only if merge between loop backedge and single loop entry. **/
1358 for (k = 0; k < get_Block_n_cfgpreds(b); k++) {
1359 pred = get_nodes_Block(get_Block_cfgpred(b, k));
1360 if (get_Block_block_visited(pred) +1
1361 < get_irg_block_visited(current_ir_graph)) {
1362 phi = get_irn_link(pred);
1364 if (get_irn_op(phi) == op_Phi) {
1365 set_nodes_Block(phi, b);
1368 for (i = 0; i < k; i++) {
1369 pred = get_nodes_Block(get_Block_cfgpred(b, i));
1370 if (is_Bad(get_Block_cfgpred(b, i))) {
1372 } else if (get_Block_block_visited(pred) +1
1373 < get_irg_block_visited(current_ir_graph)) {
1374 /* It's an empty block and not yet visited. */
1375 for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
1376 /* @@@ Hier brauche ich Schleifeninformation!!! Kontrollflusskante
1377 muss Rueckwaertskante sein! (An allen vier in[n_preds] = phi
1378 Anweisungen.) Trotzdem tuts bisher!! */
1387 for (i = 0; i < get_Phi_n_preds(phi); i++) {
1388 in[n_preds] = get_Phi_pred(phi, i);
1391 for (i = k+1; i < get_Block_n_cfgpreds(b); i++) {
1392 pred = get_nodes_Block(get_Block_cfgpred(b, i));
1393 if (is_Bad(get_Block_cfgpred(b, i))) {
1395 } else if (get_Block_block_visited(pred) +1
1396 < get_irg_block_visited(current_ir_graph)) {
1397 /* It's an empty block and not yet visited. */
1398 for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
1407 set_irn_in(phi, n_preds, in);
1409 phi = get_irn_link(phi);
1414 /** Fix the block **/
1416 for (i = 0; i < get_Block_n_cfgpreds(b); i++) {
1417 pred = get_nodes_Block(get_Block_cfgpred(b, i));
1418 if (is_Bad(get_Block_cfgpred(b, i))) {
1420 } else if (get_Block_block_visited(pred) +1
1421 < get_irg_block_visited(current_ir_graph)) {
1422 /* It's an empty block and not yet visited. */
1423 assert(get_Block_n_cfgpreds(b) > 1);
1424 /* Else it should be optimized by equivalent_node. */
1425 for (j = 0; j < get_Block_n_cfgpreds(pred); j++) {
1426 in[n_preds] = get_Block_cfgpred(pred, j);
1429 /* Remove block as it might be kept alive. */
1430 exchange(pred, b/*new_Bad()*/);
1432 in[n_preds] = get_Block_cfgpred(b, i);
1436 set_irn_in(b, n_preds, in);
1440 void optimize_cf(ir_graph *irg) {
1443 ir_node *end = get_irg_end(irg);
1444 ir_graph *rem = current_ir_graph;
1445 current_ir_graph = irg;
1447 /* Handle graph state */
1448 assert(get_irg_phase_state(irg) != phase_building);
1449 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
1450 set_irg_outs_inconsistent(current_ir_graph);
1451 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
1452 set_irg_dom_inconsistent(current_ir_graph);
1454 /* Use block visited flag to mark non-empty blocks. */
1455 inc_irg_block_visited(irg);
1456 irg_walk(end, merge_blocks, collect_nodes, NULL);
1458 /* Optimize the standard code. */
1459 irg_block_walk(get_irg_end_block(irg), optimize_blocks, NULL, NULL);
1461 /* Walk all keep alives, optimize them if block, add to new in-array
1462 for end if useful. */
1463 in = NEW_ARR_F (ir_node *, 1);
1464 in[0] = get_nodes_Block(end);
1465 inc_irg_visited(current_ir_graph);
1466 for(i = 0; i < get_End_n_keepalives(end); i++) {
1467 ir_node *ka = get_End_keepalive(end, i);
1468 if (irn_not_visited(ka)) {
1469 if ((get_irn_op(ka) == op_Block) && Block_not_block_visited(ka)) {
1470 set_irg_block_visited(current_ir_graph, /* Don't walk all the way to Start. */
1471 get_irg_block_visited(current_ir_graph)-1);
1472 irg_block_walk(ka, optimize_blocks, NULL, NULL);
1473 mark_irn_visited(ka);
1474 ARR_APP1 (ir_node *, in, ka);
1475 } else if (get_irn_op(ka) == op_Phi) {
1476 mark_irn_visited(ka);
1477 ARR_APP1 (ir_node *, in, ka);
1481 /* DEL_ARR_F(end->in); GL @@@ tut nicht ! */
1484 current_ir_graph = rem;
1489 * Called by walker of remove_critical_cf_edges.
1491 * Place an empty block to an edge between a blocks of multiple
1492 * predecessors and a block of multiple sucessors.
1495 * @param env Envirnment of walker. This field is unused and has
1498 static void walk_critical_cf_edges(ir_node *n, void *env) {
1500 ir_node *pre, *block, **in, *jmp;
1502 /* Block has multiple predecessors */
1503 if ((op_Block == get_irn_op(n)) &&
1504 (get_irn_arity(n) > 1)) {
1505 arity = get_irn_arity(n);
1507 if (n == get_irg_end_block(current_ir_graph))
1508 return; // No use to add a block here.
1510 for (i=0; i<arity; i++) {
1511 pre = get_irn_n(n, i);
1512 /* Predecessor has multiple sucessors. Insert new flow edge */
1513 if ((NULL != pre) &&
1514 (op_Proj == get_irn_op(pre)) &&
1515 op_Raise != get_irn_op(skip_Proj(pre))) {
1517 /* set predecessor array for new block */
1518 in = NEW_ARR_D (ir_node *, current_ir_graph->obst, 1);
1519 /* set predecessor of new block */
1521 block = new_Block(1, in);
1522 /* insert new jmp node to new block */
1523 switch_block(block);
1526 /* set sucessor of new block */
1527 set_irn_n(n, i, jmp);
1529 } /* predecessor has multiple sucessors */
1530 } /* for all predecessors */
1531 } /* n is a block */
1534 void remove_critical_cf_edges(ir_graph *irg) {
1535 if (get_opt_critical_edges())
1536 irg_walk_graph(irg, NULL, walk_critical_cf_edges, NULL);