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_MODULE "firm.be.irgmod"
58 #define DBG_LEVEL SET_LEVEL_0
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();
175 FIRM_DBG_REGISTER(firm_dbg_module_t *dbg, DBG_MODULE);
178 * Fill the worklist queue and the rest of the orig blocks array.
180 for (bl = pset_first(copy_blocks); bl; bl = pset_next(copy_blocks)) {
181 waitq_put(worklist, bl);
184 while (!pdeq_empty(worklist)) {
185 ir_node *bl = waitq_get(worklist);
186 ir_node **df = be_get_dominance_frontier(df_info, bl);
191 DBG((dbg, LEVEL_3, "dom front of %+F\n", bl));
193 for (i = ARR_LEN(df) - 1; i >= 0; --i)
194 DBG((dbg, LEVEL_3, "\t%+F\n", df[i]))
197 for (i = ARR_LEN(df) - 1; i >= 0; --i) {
199 if (!pset_find_ptr(phi_blocks, y)) {
200 pset_insert_ptr(phi_blocks, y);
203 * Clear the link field of a possible phi block, since
204 * the possibly created phi will be stored there. See,
207 set_irn_link(y, NULL);
209 if(!pset_find_ptr(copy_blocks, y))
210 waitq_put(worklist, y);
225 / ___|___ _ __ ___| |_ _ __ _ _ ___| |_(_) ___ _ __
226 | | / _ \| '_ \/ __| __| '__| | | |/ __| __| |/ _ \| '_ \
227 | |__| (_) | | | \__ \ |_| | | |_| | (__| |_| | (_) | | | |
228 \____\___/|_| |_|___/\__|_| \__,_|\___|\__|_|\___/|_| |_|
233 * Find the copy of the given original node whose value is 'active'
236 * The usage is given as a node and a position. Initially, the given operand
237 * points to a node for which copies were introduced. We have to find
238 * the valid copy for this usage. This is done by traversing the
239 * dominance tree upwards. If the usage is a phi function, we start
240 * traversing from the predecessor block which corresponds to the phi
243 * @param usage The node which uses the original node.
244 * @param pos The position of the argument which corresponds to the original node.
245 * @param copies A set containing all node which are copies from the original node.
246 * @param copy_blocks A set containing all basic block in which copies of the original node are located.
247 * @param phis A set where all created phis are recorded.
248 * @param phi_blocks A set of all blocks where Phis shall be inserted (iterated dominance frontier).
249 * @param mode The mode for the Phi if one has to be created.
250 * @return The valid copy for usage.
252 static ir_node *search_def(ir_node *usage, int pos, pset *copies, pset *copy_blocks, pset *phis, pset *phi_blocks, ir_mode *mode)
256 FIRM_DBG_REGISTER(firm_dbg_module_t *dbg, DBG_MODULE);
258 curr_bl = get_nodes_block(usage);
260 DBG((dbg, LEVEL_1, "Searching valid def for use %+F at pos %d\n", usage, pos));
262 * If the usage is in a phi node, search the copy in the
263 * predecessor denoted by pos.
266 curr_bl = get_Block_cfgpred_block(curr_bl, pos);
267 start_irn = sched_last(curr_bl);
269 start_irn = sched_prev(usage);
273 * Traverse the dominance tree upwards from the
274 * predecessor block of the usage.
276 while(curr_bl != NULL) {
280 * If this block contains a copy, search the block
281 * instruction by instruction. If nothing is found
282 * search for a not scheduled PhiM.
284 if(pset_find_ptr(copy_blocks, curr_bl)) {
287 /* Look at each instruction from last to first. */
288 sched_foreach_reverse_from(start_irn, irn) {
290 /* Take the first copy we find. */
291 if(pset_find_ptr(copies, irn))
295 for(phim = pset_first(copies); phim; phim = pset_next(copies)) {
296 if(!is_Phi(phim) || !(get_irn_mode(phim) == mode_M))
299 if(get_nodes_block(phim) == curr_bl) {
306 if(pset_find_ptr(phi_blocks, curr_bl)) {
307 ir_node *phi = get_irn_link(curr_bl);
310 int i, n_preds = get_irn_arity(curr_bl);
311 ir_graph *irg = get_irn_irg(curr_bl);
312 ir_node **ins = alloca(n_preds * sizeof(ins[0]));
314 for(i = 0; i < n_preds; ++i)
315 ins[i] = new_r_Bad(irg);
317 phi = new_r_Phi(irg, curr_bl, n_preds, ins, mode);
318 DBG((dbg, LEVEL_2, "\tcreating phi %+F in %+F\n", phi, curr_bl));
320 set_irn_link(curr_bl, phi);
322 sched_add_after(curr_bl, phi);
324 for(i = 0; i < n_preds; ++i) {
325 ir_node *arg = search_def(phi, i, copies, copy_blocks, phis, phi_blocks, mode);
329 ir_fprintf(stderr, "no definition found for %+F at position %d\nCopies: ", phi, i);
330 for(irn = pset_first(copies); irn; irn = pset_next(copies)) {
331 ir_fprintf(stderr, "%+F ", irn);
333 ir_fprintf(stderr, "\n\n");
334 assert(arg && "no definition found");
336 DBG((dbg, LEVEL_2, "\t\t%+F(%d) -> %+F\n", phi, i, arg));
337 set_irn_n(phi, i, arg);
341 pset_insert_ptr(phis, phi);
347 /* If were not done yet, look in the immediate dominator */
348 curr_bl = get_Block_idom(curr_bl);
350 start_irn = sched_last(curr_bl);
356 static void fix_usages(pset *copies, pset *copy_blocks, pset *phi_blocks, pset *phis, pset *ignore_uses)
367 FIRM_DBG_REGISTER(firm_dbg_module_t *dbg, DBG_MODULE);
372 * Put all outs into an array.
373 * This is necessary, since the outs would be modified while
374 * iterating on them what could bring the outs module in trouble.
376 for (irn = pset_first(copies); irn; irn = pset_next(copies)) {
377 const ir_edge_t *edge;
378 foreach_out_edge(irn, edge) {
379 if (!pset_find_ptr(ignore_uses, get_edge_src_irn(edge))) {
381 tmp.irn = get_edge_src_irn(edge);
382 tmp.pos = get_edge_src_pos(edge);
383 obstack_grow(&obst, &tmp, sizeof(tmp));
388 outs = obstack_finish(&obst);
391 * Search the valid def for each out and set it.
393 for(i = 0; i < n_outs; ++i) {
394 ir_node *irn = outs[i].irn;
395 int pos = outs[i].pos;
396 ir_mode *mode = get_irn_mode(get_irn_n(irn, pos));
400 def = search_def(irn, pos, copies, copy_blocks, phis, phi_blocks, mode);
401 DBG((dbg, LEVEL_2, "\t%+F(%d) -> %+F\n", irn, pos, def));
404 ir_fprintf(stderr, "no definition found for %+F at position %d\nCopies: ", irn, pos);
405 for(irn = pset_first(copies); irn; irn = pset_next(copies)) {
406 ir_fprintf(stderr, "%+F ", irn);
408 ir_fprintf(stderr, "\n\n");
409 assert(def && "no definition found");
411 set_irn_n(irn, pos, def);
414 obstack_free(&obst, NULL);
419 * Remove phis which are not necessary.
420 * During place_phi_functions() phi functions are put on the dominance
421 * frontiers blindly. However some of them will never be used (these
422 * have at least one predecessor which is NULL, see search_def() for
423 * this case). Since place_phi_functions() enters them into the
424 * schedule, we have to remove them from there.
426 * @param copies The set of all copies made (including the phi functions).
428 static void remove_odd_phis(pset *copies, pset *unused_copies)
432 for(irn = pset_first(copies); irn; irn = pset_next(copies)) {
437 assert(sched_is_scheduled(irn) && "phi must be scheduled");
438 for(i = 0, n = get_irn_arity(irn); i < n && !illegal; ++i)
439 illegal = get_irn_n(irn, i) == NULL;
442 for(i = 0, n = get_irn_arity(irn); i < n; ++i)
443 set_irn_n(irn, i, new_Bad());
449 for(irn = pset_first(unused_copies); irn; irn = pset_next(unused_copies)) {
450 for(i = 0, n = get_irn_arity(irn); i < n; ++i)
451 set_irn_n(irn, i, new_Bad());
457 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)
459 pset *irns = pset_new_ptr(n);
462 for(i = 0; i < n; ++i)
463 pset_insert_ptr(irns, nodes[i]);
464 be_ssa_constr_set_phis_ignore(info, lv, irns, phis, ignore_uses);
468 void be_ssa_constr_ignore(be_dom_front_info_t *info, be_lv_t *lv, int n, ir_node *nodes[], pset *ignore_uses)
470 be_ssa_constr_phis_ignore(info, lv, n, nodes, NULL, ignore_uses);
473 void be_ssa_constr(be_dom_front_info_t *info, be_lv_t *lv, int n, ir_node *nodes[])
475 pset *empty_set = be_empty_set();
476 be_ssa_constr_ignore(info, lv, n, nodes, empty_set);
479 void be_ssa_constr_set_phis_ignore(be_dom_front_info_t *df, be_lv_t *lv, pset *nodes, pset *phis, pset *ignore_uses)
481 int n = pset_count(nodes);
482 pset *blocks = pset_new_ptr(n);
483 pset *phi_blocks = pset_new_ptr(n);
484 int save_optimize = get_optimize();
485 int save_normalize = get_opt_normalize();
486 int phis_set_created = 0;
487 FIRM_DBG_REGISTER(firm_dbg_module_t *dbg, DBG_MODULE);
491 /* We need to collect the phi functions to compute their liveness. */
493 phis_set_created = 1;
494 phis = pset_new_ptr_default();
497 DBG((dbg, LEVEL_1, "Introducing following copies for:\n"));
500 for(irn = pset_first(nodes); irn; irn = pset_next(nodes)) {
501 ir_node *bl = get_nodes_block(irn);
502 pset_insert_ptr(blocks, bl);
503 DBG((dbg, LEVEL_1, "\t%+F in %+F\n", irn, bl));
507 * Disable optimization so that the phi functions do not
511 set_opt_normalize(0);
514 * Place the phi functions and reroute the usages.
516 determine_phi_blocks(nodes, blocks, phi_blocks, df);
517 fix_usages(nodes, blocks, phi_blocks, phis, ignore_uses);
519 /* reset the optimizations */
520 set_optimize(save_optimize);
521 set_opt_normalize(save_normalize);
523 del_pset(phi_blocks);
526 /* Recompute the liveness (if wanted) of the original nodes, the copies and the inserted phis. */
529 foreach_pset(nodes, irn)
530 be_liveness_update(lv, irn);
532 foreach_pset(phis, irn)
533 be_liveness_introduce(lv, irn);
535 be_liveness_recompute(lv);
539 /* Free the phi set of we created it. */
545 void be_ssa_constr_set_phis(be_dom_front_info_t *df, be_lv_t *lv, pset *nodes, pset *phis)
547 pset *empty_set = be_empty_set();
548 be_ssa_constr_set_phis_ignore(df, lv, nodes, phis, empty_set);
551 void be_ssa_constr_set_ignore(be_dom_front_info_t *df, be_lv_t *lv, pset *nodes, pset *ignore_uses)
553 be_ssa_constr_set_phis_ignore(df, lv, nodes, NULL, ignore_uses);
556 void be_ssa_constr_set(be_dom_front_info_t *info, be_lv_t *lv, pset *nodes)
558 pset *empty_set = be_empty_set();
559 be_ssa_constr_set_ignore(info, lv, nodes, empty_set);
564 |_ _|_ __ ___ ___ _ __| |_ | _ \ ___ _ __ _ __ ___
565 | || '_ \/ __|/ _ \ '__| __| | |_) / _ \ '__| '_ ` _ \
566 | || | | \__ \ __/ | | |_ | __/ __/ | | | | | | |
567 |___|_| |_|___/\___|_| \__| |_| \___|_| |_| |_| |_|
571 ir_node *insert_Perm_after(const arch_env_t *arch_env,
573 const arch_register_class_t *cls,
574 be_dom_front_info_t *dom_front,
577 ir_node *bl = is_Block(pos) ? pos : get_nodes_block(pos);
578 ir_graph *irg = get_irn_irg(bl);
579 pset *live = pset_new_ptr_default();
580 FIRM_DBG_REGISTER(firm_dbg_module_t *dbg, "be.node");
582 ir_node *curr, *irn, *perm, **nodes;
585 DBG((dbg, LEVEL_1, "Insert Perm after: %+F\n", pos));
587 be_liveness_nodes_live_at(lv, arch_env, cls, pos, live);
589 n = pset_count(live);
596 nodes = xmalloc(n * sizeof(nodes[0]));
598 DBG((dbg, LEVEL_1, "live:\n"));
599 for(irn = pset_first(live), i = 0; irn; irn = pset_next(live), i++) {
600 DBG((dbg, LEVEL_1, "\t%+F\n", irn));
605 perm = be_new_Perm(cls, irg, bl, n, nodes);
606 sched_add_after(pos, perm);
610 for (i = 0; i < n; ++i) {
612 ir_node *perm_op = get_irn_n(perm, i);
613 const arch_register_t *reg = arch_get_irn_register(arch_env, perm_op);
615 ir_mode *mode = get_irn_mode(perm_op);
616 ir_node *proj = new_r_Proj(irg, bl, perm, mode, i);
617 arch_set_irn_register(arch_env, proj, reg);
619 sched_add_after(curr, proj);
625 be_ssa_constr(dom_front, lv, 2, copies);
631 struct _elr_closure_t {
633 const be_chordal_env_t *cenv;
636 static void elr_split_walker(ir_node *bl, void *data)
638 struct _elr_closure_t *c = data;
639 const be_chordal_env_t *cenv = c->cenv;
640 const arch_env_t *aenv = cenv->birg->main_env->arch_env;
641 be_lv_t *lv = cenv->birg->lv;
642 be_dom_front_info_t *dom_front = cenv->birg->dom_front;
646 be_insn_env_init(&ie, cenv->birg, cenv->cls, &c->obst);
648 for(insn = be_scan_insn(&ie, sched_first(bl)); !is_Block(insn->irn); insn = be_scan_insn(&ie, insn->next_insn)) {
649 ir_node *pred = sched_prev(insn->irn);
650 if(!is_Block(pred) && !is_Phi(insn->irn))
651 insert_Perm_after(aenv, lv, cenv->cls, dom_front, insn->irn);
655 void extreme_liverange_splitting(struct _be_chordal_env_t *cenv)
657 struct _elr_closure_t c;
658 be_lv_t *lv = cenv->birg->lv;
661 obstack_init(&c.obst);
662 be_liveness_recompute(lv);
663 irg_block_walk_graph(cenv->irg, elr_split_walker, NULL, &c);
664 be_liveness_recompute(lv);
665 obstack_free(&c.obst, NULL);
669 * Post-block-walker: Find blocks containing only one jump and
672 static void remove_empty_block(ir_node *block, void *data) {
673 const ir_edge_t *edge, *next;
676 ir_node *jump = NULL;
678 assert(is_Block(block));
680 if (get_Block_n_cfgpreds(block) != 1)
683 sched_foreach(block, node) {
687 /* we should never have 2 jumps in a block */
688 assert(0 && "We should never have 2 jumps in a block");
697 node = get_Block_cfgpred(block, 0);
698 foreach_out_edge_safe(jump, edge, next) {
699 ir_node *block = get_edge_src_irn(edge);
700 int pos = get_edge_src_pos(edge);
702 set_irn_n(block, pos, node);
705 set_Block_cfgpred(block, 0, new_Bad());
710 /* removes basic blocks that just contain a jump instruction */
711 int be_remove_empty_blocks(ir_graph *irg) {
714 irg_block_walk_graph(irg, remove_empty_block, NULL, &changed);
716 /* invalidate analysis info */
717 set_irg_doms_inconsistent(irg);
718 set_irg_extblk_inconsistent(irg);
719 set_irg_outs_inconsistent(irg);
724 typedef struct _be_dead_out_env_t {
727 DEBUG_ONLY(firm_dbg_module_t *dbg);
731 * Check if @p node has dead users, i.e. they are reachable only via outedges from @p node.
732 * Set all ins of those users to BAD.
734 static void kill_dead_out(ir_node *node, be_dead_out_env_t *env) {
735 ir_graph *irg = env->irg;
736 const ir_edge_t *edge, *tmp_edge;
738 if (irn_visited(node))
740 mark_irn_visited(node);
742 /* check all out edges */
743 foreach_out_edge_safe(node, edge, tmp_edge) {
744 ir_node *src = get_edge_src_irn(edge);
746 if (! bitset_is_set(env->reachable, get_irn_idx(src))) {
747 /* BEWARE: do not kill anchors or TLS */
748 if (src != get_irg_globals(irg) && src != get_irg_tls(irg)) {
749 DBG((env->dbg, LEVEL_1, "killing %+F, only reachable from %+F\n", src, node));
756 if (! is_Block(src)) {
757 kill_dead_out(src, env);
762 static void set_reachable(ir_node *node, void *data) {
763 bitset_t *reachable = data;
764 bitset_set(reachable, get_irn_idx(node));
768 * Set input of all nodes only reachable via out edges to BAD.
770 void be_kill_dead_nodes(ir_graph *irg) {
771 be_dead_out_env_t env;
774 env.reachable = bitset_alloca(get_irg_last_idx(irg));
775 FIRM_DBG_REGISTER(env.dbg, "firm.be.killdead");
777 /* collect all reachable nodes */
778 irg_walk_in_or_dep_graph(irg, set_reachable, NULL, env.reachable);
780 /* this is a forward walk (start -> end) */
781 inc_irg_visited(irg);
782 kill_dead_out(get_irg_start(irg), &env);