2 * This file contains the following IRG modifications for be routines:
3 * - backend dominance information
4 * - SSA construction for a set of nodes
5 * - insertion of Perm nodes
6 * - empty block elimination
7 * - a simple dead node elimination (set inputs of unreachable nodes to BAD)
9 * Author: Sebastian Hack, Daniel Grund, Matthias Braun, Christian Wuerdig
11 * Copyright: (c) Universitaet Karlsruhe
12 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
41 #include "iredges_t.h"
43 #include "irprintf_t.h"
47 #include "bechordal_t.h"
49 #include "besched_t.h"
57 #define DBG_LEVEL SET_LEVEL_0
58 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
62 | _ \ ___ _ __ ___ (_)_ __ __ _ _ __ ___ ___
63 | | | |/ _ \| '_ ` _ \| | '_ \ / _` | '_ \ / __/ _ \
64 | |_| | (_) | | | | | | | | | | (_| | | | | (_| __/
65 |____/ \___/|_| |_| |_|_|_| |_|\__,_|_| |_|\___\___|
66 | ___| __ ___ _ __ | |_(_) ___ _ __ ___
67 | |_ | '__/ _ \| '_ \| __| |/ _ \ '__/ __|
68 | _|| | | (_) | | | | |_| | __/ | \__ \
69 |_| |_| \___/|_| |_|\__|_|\___|_| |___/
74 * The dominance frontier for a graph.
76 struct _be_dom_front_info_t {
77 pmap *df_map; /**< A map, mapping every block to a list of its dominance frontier blocks. */
78 struct obstack obst; /**< An obstack holding all the frontier data. */
82 * A wrapper for get_Block_idom.
83 * This function returns the block itself, if the block is the start
84 * block. Returning NULL would make any != comparison true which
85 * suggests, that the start block is dominated by some other node.
86 * @param bl The block.
87 * @return The immediate dominator of the block.
89 static INLINE ir_node *get_idom(ir_node *bl)
91 ir_node *idom = get_Block_idom(bl);
92 return idom == NULL ? bl : idom;
96 * Compute the dominance frontier for a given block.
98 * @param blk the block where the calculation starts
100 * @return the list of all blocks in the dominance frontier of blk
102 static ir_node **compute_df(ir_node *blk, be_dom_front_info_t *info)
105 const ir_edge_t *edge;
106 ir_node **df_list = NEW_ARR_F(ir_node *, 0);
110 /* Add local dominance frontiers */
111 foreach_block_succ(blk, edge) {
112 ir_node *y = edge->src;
114 if (get_idom(y) != blk) {
115 ARR_APP1(ir_node *, df_list, y);
120 * Go recursively down the dominance tree and add all blocks
121 * into the dominance frontiers of the children, which are not
122 * dominated by the given block.
124 for (c = get_Block_dominated_first(blk); c; c = get_Block_dominated_next(c)) {
126 ir_node **df_c_list = compute_df(c, info);
128 for (i = ARR_LEN(df_c_list) - 1; i >= 0; --i) {
129 ir_node *w = df_c_list[i];
130 if (get_idom(w) != blk)
131 ARR_APP1(ir_node *, df_list, w);
135 /* now copy the flexible array to the obstack */
136 len = ARR_LEN(df_list);
137 df = NEW_ARR_D(ir_node *, &info->obst, len);
138 memcpy(df, df_list, len * sizeof(df[0]));
141 pmap_insert(info->df_map, blk, df);
145 be_dom_front_info_t *be_compute_dominance_frontiers(ir_graph *irg)
147 be_dom_front_info_t *info = xmalloc(sizeof(*info));
150 obstack_init(&info->obst);
151 info->df_map = pmap_create();
153 (void)compute_df(get_irg_start_block(irg), info);
158 void be_free_dominance_frontiers(be_dom_front_info_t *info)
160 obstack_free(&info->obst, NULL);
161 pmap_destroy(info->df_map);
165 /* Get the dominance frontier of a block. */
166 ir_node **be_get_dominance_frontier(be_dom_front_info_t *info, ir_node *block)
168 return pmap_get(info->df_map, block);
171 static void determine_phi_blocks(pset *copies, pset *copy_blocks, pset *phi_blocks, be_dom_front_info_t *df_info)
174 waitq *worklist = new_waitq();
177 * Fill the worklist queue and the rest of the orig blocks array.
179 for (bl = pset_first(copy_blocks); bl; bl = pset_next(copy_blocks)) {
180 waitq_put(worklist, bl);
183 while (!pdeq_empty(worklist)) {
184 ir_node *bl = waitq_get(worklist);
185 ir_node **df = be_get_dominance_frontier(df_info, bl);
190 DBG((dbg, LEVEL_3, "dom front of %+F\n", bl));
192 for (i = ARR_LEN(df) - 1; i >= 0; --i)
193 DBG((dbg, LEVEL_3, "\t%+F\n", df[i]))
196 for (i = ARR_LEN(df) - 1; i >= 0; --i) {
198 if (!pset_find_ptr(phi_blocks, y)) {
199 pset_insert_ptr(phi_blocks, y);
202 * Clear the link field of a possible phi block, since
203 * the possibly created phi will be stored there. See,
206 set_irn_link(y, NULL);
208 if(!pset_find_ptr(copy_blocks, y))
209 waitq_put(worklist, y);
224 / ___|___ _ __ ___| |_ _ __ _ _ ___| |_(_) ___ _ __
225 | | / _ \| '_ \/ __| __| '__| | | |/ __| __| |/ _ \| '_ \
226 | |__| (_) | | | \__ \ |_| | | |_| | (__| |_| | (_) | | | |
227 \____\___/|_| |_|___/\__|_| \__,_|\___|\__|_|\___/|_| |_|
232 * Find the copy of the given original node whose value is 'active'
235 * The usage is given as a node and a position. Initially, the given operand
236 * points to a node for which copies were introduced. We have to find
237 * the valid copy for this usage. This is done by traversing the
238 * dominance tree upwards. If the usage is a phi function, we start
239 * traversing from the predecessor block which corresponds to the phi
242 * @param usage The node which uses the original node.
243 * @param pos The position of the argument which corresponds to the original node.
244 * @param copies A set containing all node which are copies from the original node.
245 * @param copy_blocks A set containing all basic block in which copies of the original node are located.
246 * @param phis A set where all created phis are recorded.
247 * @param phi_blocks A set of all blocks where Phis shall be inserted (iterated dominance frontier).
248 * @param mode The mode for the Phi if one has to be created.
249 * @return The valid copy for usage.
251 static ir_node *search_def(ir_node *usage, int pos, pset *copies, pset *copy_blocks, pset *phis, pset *phi_blocks, ir_mode *mode)
256 curr_bl = get_nodes_block(usage);
258 DBG((dbg, LEVEL_1, "Searching valid def for use %+F at pos %d\n", usage, pos));
260 * If the usage is in a phi node, search the copy in the
261 * predecessor denoted by pos.
264 curr_bl = get_Block_cfgpred_block(curr_bl, pos);
265 start_irn = sched_last(curr_bl);
267 start_irn = sched_prev(usage);
271 * Traverse the dominance tree upwards from the
272 * predecessor block of the usage.
274 while(curr_bl != NULL) {
278 * If this block contains a copy, search the block
279 * instruction by instruction. If nothing is found
280 * search for a not scheduled PhiM.
282 if(pset_find_ptr(copy_blocks, curr_bl)) {
285 /* Look at each instruction from last to first. */
286 sched_foreach_reverse_from(start_irn, irn) {
288 /* Take the first copy we find. */
289 if(pset_find_ptr(copies, irn))
293 for(phim = pset_first(copies); phim; phim = pset_next(copies)) {
294 if(!is_Phi(phim) || !(get_irn_mode(phim) == mode_M))
297 if(get_nodes_block(phim) == curr_bl) {
304 if(pset_find_ptr(phi_blocks, curr_bl)) {
305 ir_node *phi = get_irn_link(curr_bl);
308 int i, n_preds = get_irn_arity(curr_bl);
309 ir_graph *irg = get_irn_irg(curr_bl);
310 ir_node **ins = alloca(n_preds * sizeof(ins[0]));
312 for(i = 0; i < n_preds; ++i)
313 ins[i] = new_r_Bad(irg);
315 phi = new_r_Phi(irg, curr_bl, n_preds, ins, mode);
316 DBG((dbg, LEVEL_2, "\tcreating phi %+F in %+F\n", phi, curr_bl));
318 set_irn_link(curr_bl, phi);
320 sched_add_after(curr_bl, phi);
322 for(i = 0; i < n_preds; ++i) {
323 ir_node *arg = search_def(phi, i, copies, copy_blocks, phis, phi_blocks, mode);
327 ir_fprintf(stderr, "no definition found for %+F at position %d\nCopies: ", phi, i);
328 for(irn = pset_first(copies); irn; irn = pset_next(copies)) {
329 ir_fprintf(stderr, "%+F ", irn);
331 ir_fprintf(stderr, "\n\n");
332 assert(arg && "no definition found");
334 DBG((dbg, LEVEL_2, "\t\t%+F(%d) -> %+F\n", phi, i, arg));
335 set_irn_n(phi, i, arg);
339 pset_insert_ptr(phis, phi);
345 /* If were not done yet, look in the immediate dominator */
346 curr_bl = get_Block_idom(curr_bl);
348 start_irn = sched_last(curr_bl);
354 static void fix_usages(pset *copies, pset *copy_blocks, pset *phi_blocks, pset *phis, pset *ignore_uses)
368 * Put all outs into an array.
369 * This is necessary, since the outs would be modified while
370 * iterating on them what could bring the outs module in trouble.
372 for (irn = pset_first(copies); irn; irn = pset_next(copies)) {
373 const ir_edge_t *edge;
374 foreach_out_edge(irn, edge) {
375 ir_node *src = get_edge_src_irn(edge);
376 /* ignore all users from ignore_uses or keep-alives (user is End node) */
377 if (! pset_find_ptr(ignore_uses, src) && ! is_End(src)) {
380 tmp.pos = get_edge_src_pos(edge);
381 obstack_grow(&obst, &tmp, sizeof(tmp));
386 outs = obstack_finish(&obst);
389 * Search the valid def for each out and set it.
391 for(i = 0; i < n_outs; ++i) {
392 ir_node *irn = outs[i].irn;
393 int pos = outs[i].pos;
394 ir_mode *mode = get_irn_mode(get_irn_n(irn, pos));
398 def = search_def(irn, pos, copies, copy_blocks, phis, phi_blocks, mode);
399 DBG((dbg, LEVEL_2, "\t%+F(%d) -> %+F\n", irn, pos, def));
402 ir_fprintf(stderr, "no definition found for %+F at position %d\nCopies: ", irn, pos);
403 for(irn = pset_first(copies); irn; irn = pset_next(copies)) {
404 ir_fprintf(stderr, "%+F ", irn);
406 ir_fprintf(stderr, "\n\n");
407 assert(def && "no definition found");
409 set_irn_n(irn, pos, def);
412 obstack_free(&obst, NULL);
417 * Remove phis which are not necessary.
418 * During place_phi_functions() phi functions are put on the dominance
419 * frontiers blindly. However some of them will never be used (these
420 * have at least one predecessor which is NULL, see search_def() for
421 * this case). Since place_phi_functions() enters them into the
422 * schedule, we have to remove them from there.
424 * @param copies The set of all copies made (including the phi functions).
426 static void remove_odd_phis(pset *copies, pset *unused_copies)
430 for(irn = pset_first(copies); irn; irn = pset_next(copies)) {
435 assert(sched_is_scheduled(irn) && "phi must be scheduled");
436 for(i = 0, n = get_irn_arity(irn); i < n && !illegal; ++i)
437 illegal = get_irn_n(irn, i) == NULL;
440 for(i = 0, n = get_irn_arity(irn); i < n; ++i)
441 set_irn_n(irn, i, new_Bad());
447 for(irn = pset_first(unused_copies); irn; irn = pset_next(unused_copies)) {
448 for(i = 0, n = get_irn_arity(irn); i < n; ++i)
449 set_irn_n(irn, i, new_Bad());
455 void be_ssa_constr_phis_ignore(be_dom_front_info_t *info, be_lv_t *lv, int n, ir_node *nodes[], pset *phis, pset *ignore_uses)
457 pset *irns = pset_new_ptr(n);
460 for(i = 0; i < n; ++i)
461 pset_insert_ptr(irns, nodes[i]);
462 be_ssa_constr_set_phis_ignore(info, lv, irns, phis, ignore_uses);
466 void be_ssa_constr_ignore(be_dom_front_info_t *info, be_lv_t *lv, int n, ir_node *nodes[], pset *ignore_uses)
468 be_ssa_constr_phis_ignore(info, lv, n, nodes, NULL, ignore_uses);
471 void be_ssa_constr(be_dom_front_info_t *info, be_lv_t *lv, int n, ir_node *nodes[])
473 pset *empty_set = be_empty_set();
474 be_ssa_constr_ignore(info, lv, n, nodes, empty_set);
477 void be_ssa_constr_set_phis_ignore(be_dom_front_info_t *df, be_lv_t *lv, pset *nodes, pset *phis, pset *ignore_uses)
479 int n = pset_count(nodes);
480 pset *blocks = pset_new_ptr(n);
481 pset *phi_blocks = pset_new_ptr(n);
482 int save_optimize = get_optimize();
483 int save_normalize = get_opt_normalize();
484 int phis_set_created = 0;
488 /* We need to collect the phi functions to compute their liveness. */
490 phis_set_created = 1;
491 phis = pset_new_ptr_default();
494 DBG((dbg, LEVEL_1, "Introducing following copies for:\n"));
497 for(irn = pset_first(nodes); irn; irn = pset_next(nodes)) {
498 ir_node *bl = get_nodes_block(irn);
499 pset_insert_ptr(blocks, bl);
500 DBG((dbg, LEVEL_1, "\t%+F in %+F\n", irn, bl));
504 * Disable optimization so that the phi functions do not
508 set_opt_normalize(0);
511 * Place the phi functions and reroute the usages.
513 determine_phi_blocks(nodes, blocks, phi_blocks, df);
514 fix_usages(nodes, blocks, phi_blocks, phis, ignore_uses);
516 /* reset the optimizations */
517 set_optimize(save_optimize);
518 set_opt_normalize(save_normalize);
520 del_pset(phi_blocks);
523 /* Recompute the liveness (if wanted) of the original nodes, the copies and the inserted phis. */
526 foreach_pset(nodes, irn)
527 be_liveness_update(lv, irn);
529 foreach_pset(phis, irn)
530 be_liveness_introduce(lv, irn);
532 be_liveness_recompute(lv);
536 /* Free the phi set of we created it. */
542 void be_ssa_constr_set_phis(be_dom_front_info_t *df, be_lv_t *lv, pset *nodes, pset *phis)
544 pset *empty_set = be_empty_set();
545 be_ssa_constr_set_phis_ignore(df, lv, nodes, phis, empty_set);
548 void be_ssa_constr_set_ignore(be_dom_front_info_t *df, be_lv_t *lv, pset *nodes, pset *ignore_uses)
550 be_ssa_constr_set_phis_ignore(df, lv, nodes, NULL, ignore_uses);
553 void be_ssa_constr_set(be_dom_front_info_t *info, be_lv_t *lv, pset *nodes)
555 pset *empty_set = be_empty_set();
556 be_ssa_constr_set_ignore(info, lv, nodes, empty_set);
561 |_ _|_ __ ___ ___ _ __| |_ | _ \ ___ _ __ _ __ ___
562 | || '_ \/ __|/ _ \ '__| __| | |_) / _ \ '__| '_ ` _ \
563 | || | | \__ \ __/ | | |_ | __/ __/ | | | | | | |
564 |___|_| |_|___/\___|_| \__| |_| \___|_| |_| |_| |_|
568 ir_node *insert_Perm_after(const arch_env_t *arch_env,
570 const arch_register_class_t *cls,
571 be_dom_front_info_t *dom_front,
574 ir_node *bl = is_Block(pos) ? pos : get_nodes_block(pos);
575 ir_graph *irg = get_irn_irg(bl);
576 pset *live = pset_new_ptr_default();
578 ir_node *curr, *irn, *perm, **nodes;
581 DBG((dbg, LEVEL_1, "Insert Perm after: %+F\n", pos));
583 be_liveness_nodes_live_at(lv, arch_env, cls, pos, live);
585 n = pset_count(live);
592 nodes = xmalloc(n * sizeof(nodes[0]));
594 DBG((dbg, LEVEL_1, "live:\n"));
595 for(irn = pset_first(live), i = 0; irn; irn = pset_next(live), i++) {
596 DBG((dbg, LEVEL_1, "\t%+F\n", irn));
601 perm = be_new_Perm(cls, irg, bl, n, nodes);
602 sched_add_after(pos, perm);
606 for (i = 0; i < n; ++i) {
608 ir_node *perm_op = get_irn_n(perm, i);
609 const arch_register_t *reg = arch_get_irn_register(arch_env, perm_op);
611 ir_mode *mode = get_irn_mode(perm_op);
612 ir_node *proj = new_r_Proj(irg, bl, perm, mode, i);
613 arch_set_irn_register(arch_env, proj, reg);
615 sched_add_after(curr, proj);
621 be_ssa_constr(dom_front, lv, 2, copies);
627 struct _elr_closure_t {
629 const be_chordal_env_t *cenv;
632 static void elr_split_walker(ir_node *bl, void *data)
634 struct _elr_closure_t *c = data;
635 const be_chordal_env_t *cenv = c->cenv;
636 const arch_env_t *aenv = cenv->birg->main_env->arch_env;
637 be_lv_t *lv = cenv->birg->lv;
638 be_dom_front_info_t *dom_front = cenv->birg->dom_front;
642 be_insn_env_init(&ie, cenv->birg, cenv->cls, &c->obst);
644 for(insn = be_scan_insn(&ie, sched_first(bl)); !is_Block(insn->irn); insn = be_scan_insn(&ie, insn->next_insn)) {
645 ir_node *pred = sched_prev(insn->irn);
646 if(!is_Block(pred) && !is_Phi(insn->irn))
647 insert_Perm_after(aenv, lv, cenv->cls, dom_front, insn->irn);
651 void extreme_liverange_splitting(struct _be_chordal_env_t *cenv)
653 struct _elr_closure_t c;
654 be_lv_t *lv = cenv->birg->lv;
657 obstack_init(&c.obst);
658 be_liveness_recompute(lv);
659 irg_block_walk_graph(cenv->irg, elr_split_walker, NULL, &c);
660 be_liveness_recompute(lv);
661 obstack_free(&c.obst, NULL);
665 * Post-block-walker: Find blocks containing only one jump and
668 static void remove_empty_block(ir_node *block, void *data) {
669 const ir_edge_t *edge, *next;
672 ir_node *jump = NULL;
674 assert(is_Block(block));
676 if (get_Block_n_cfgpreds(block) != 1)
679 sched_foreach(block, node) {
683 /* we should never have 2 jumps in a block */
684 assert(0 && "We should never have 2 jumps in a block");
693 node = get_Block_cfgpred(block, 0);
694 foreach_out_edge_safe(jump, edge, next) {
695 ir_node *block = get_edge_src_irn(edge);
696 int pos = get_edge_src_pos(edge);
698 set_irn_n(block, pos, node);
701 set_Block_cfgpred(block, 0, new_Bad());
706 /* removes basic blocks that just contain a jump instruction */
707 int be_remove_empty_blocks(ir_graph *irg) {
710 irg_block_walk_graph(irg, remove_empty_block, NULL, &changed);
712 /* invalidate analysis info */
713 set_irg_doms_inconsistent(irg);
714 set_irg_extblk_inconsistent(irg);
715 set_irg_outs_inconsistent(irg);
720 void be_init_irgmod(void)
722 FIRM_DBG_REGISTER(dbg, "firm.be.irgmod");
725 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_irgmod);