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 ir_node *src = get_edge_src_irn(edge);
380 /* ignore all users from ignore_uses or keep-alives (user is End node) */
381 if (! pset_find_ptr(ignore_uses, src) && ! is_End(src)) {
384 tmp.pos = get_edge_src_pos(edge);
385 obstack_grow(&obst, &tmp, sizeof(tmp));
390 outs = obstack_finish(&obst);
393 * Search the valid def for each out and set it.
395 for(i = 0; i < n_outs; ++i) {
396 ir_node *irn = outs[i].irn;
397 int pos = outs[i].pos;
398 ir_mode *mode = get_irn_mode(get_irn_n(irn, pos));
402 def = search_def(irn, pos, copies, copy_blocks, phis, phi_blocks, mode);
403 DBG((dbg, LEVEL_2, "\t%+F(%d) -> %+F\n", irn, pos, def));
406 ir_fprintf(stderr, "no definition found for %+F at position %d\nCopies: ", irn, pos);
407 for(irn = pset_first(copies); irn; irn = pset_next(copies)) {
408 ir_fprintf(stderr, "%+F ", irn);
410 ir_fprintf(stderr, "\n\n");
411 assert(def && "no definition found");
413 set_irn_n(irn, pos, def);
416 obstack_free(&obst, NULL);
421 * Remove phis which are not necessary.
422 * During place_phi_functions() phi functions are put on the dominance
423 * frontiers blindly. However some of them will never be used (these
424 * have at least one predecessor which is NULL, see search_def() for
425 * this case). Since place_phi_functions() enters them into the
426 * schedule, we have to remove them from there.
428 * @param copies The set of all copies made (including the phi functions).
430 static void remove_odd_phis(pset *copies, pset *unused_copies)
434 for(irn = pset_first(copies); irn; irn = pset_next(copies)) {
439 assert(sched_is_scheduled(irn) && "phi must be scheduled");
440 for(i = 0, n = get_irn_arity(irn); i < n && !illegal; ++i)
441 illegal = get_irn_n(irn, i) == NULL;
444 for(i = 0, n = get_irn_arity(irn); i < n; ++i)
445 set_irn_n(irn, i, new_Bad());
451 for(irn = pset_first(unused_copies); irn; irn = pset_next(unused_copies)) {
452 for(i = 0, n = get_irn_arity(irn); i < n; ++i)
453 set_irn_n(irn, i, new_Bad());
459 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)
461 pset *irns = pset_new_ptr(n);
464 for(i = 0; i < n; ++i)
465 pset_insert_ptr(irns, nodes[i]);
466 be_ssa_constr_set_phis_ignore(info, lv, irns, phis, ignore_uses);
470 void be_ssa_constr_ignore(be_dom_front_info_t *info, be_lv_t *lv, int n, ir_node *nodes[], pset *ignore_uses)
472 be_ssa_constr_phis_ignore(info, lv, n, nodes, NULL, ignore_uses);
475 void be_ssa_constr(be_dom_front_info_t *info, be_lv_t *lv, int n, ir_node *nodes[])
477 pset *empty_set = be_empty_set();
478 be_ssa_constr_ignore(info, lv, n, nodes, empty_set);
481 void be_ssa_constr_set_phis_ignore(be_dom_front_info_t *df, be_lv_t *lv, pset *nodes, pset *phis, pset *ignore_uses)
483 int n = pset_count(nodes);
484 pset *blocks = pset_new_ptr(n);
485 pset *phi_blocks = pset_new_ptr(n);
486 int save_optimize = get_optimize();
487 int save_normalize = get_opt_normalize();
488 int phis_set_created = 0;
489 FIRM_DBG_REGISTER(firm_dbg_module_t *dbg, DBG_MODULE);
493 /* We need to collect the phi functions to compute their liveness. */
495 phis_set_created = 1;
496 phis = pset_new_ptr_default();
499 DBG((dbg, LEVEL_1, "Introducing following copies for:\n"));
502 for(irn = pset_first(nodes); irn; irn = pset_next(nodes)) {
503 ir_node *bl = get_nodes_block(irn);
504 pset_insert_ptr(blocks, bl);
505 DBG((dbg, LEVEL_1, "\t%+F in %+F\n", irn, bl));
509 * Disable optimization so that the phi functions do not
513 set_opt_normalize(0);
516 * Place the phi functions and reroute the usages.
518 determine_phi_blocks(nodes, blocks, phi_blocks, df);
519 fix_usages(nodes, blocks, phi_blocks, phis, ignore_uses);
521 /* reset the optimizations */
522 set_optimize(save_optimize);
523 set_opt_normalize(save_normalize);
525 del_pset(phi_blocks);
528 /* Recompute the liveness (if wanted) of the original nodes, the copies and the inserted phis. */
531 foreach_pset(nodes, irn)
532 be_liveness_update(lv, irn);
534 foreach_pset(phis, irn)
535 be_liveness_introduce(lv, irn);
537 be_liveness_recompute(lv);
541 /* Free the phi set of we created it. */
547 void be_ssa_constr_set_phis(be_dom_front_info_t *df, be_lv_t *lv, pset *nodes, pset *phis)
549 pset *empty_set = be_empty_set();
550 be_ssa_constr_set_phis_ignore(df, lv, nodes, phis, empty_set);
553 void be_ssa_constr_set_ignore(be_dom_front_info_t *df, be_lv_t *lv, pset *nodes, pset *ignore_uses)
555 be_ssa_constr_set_phis_ignore(df, lv, nodes, NULL, ignore_uses);
558 void be_ssa_constr_set(be_dom_front_info_t *info, be_lv_t *lv, pset *nodes)
560 pset *empty_set = be_empty_set();
561 be_ssa_constr_set_ignore(info, lv, nodes, empty_set);
566 |_ _|_ __ ___ ___ _ __| |_ | _ \ ___ _ __ _ __ ___
567 | || '_ \/ __|/ _ \ '__| __| | |_) / _ \ '__| '_ ` _ \
568 | || | | \__ \ __/ | | |_ | __/ __/ | | | | | | |
569 |___|_| |_|___/\___|_| \__| |_| \___|_| |_| |_| |_|
573 ir_node *insert_Perm_after(const arch_env_t *arch_env,
575 const arch_register_class_t *cls,
576 be_dom_front_info_t *dom_front,
579 ir_node *bl = is_Block(pos) ? pos : get_nodes_block(pos);
580 ir_graph *irg = get_irn_irg(bl);
581 pset *live = pset_new_ptr_default();
582 FIRM_DBG_REGISTER(firm_dbg_module_t *dbg, "be.node");
584 ir_node *curr, *irn, *perm, **nodes;
587 DBG((dbg, LEVEL_1, "Insert Perm after: %+F\n", pos));
589 be_liveness_nodes_live_at(lv, arch_env, cls, pos, live);
591 n = pset_count(live);
598 nodes = xmalloc(n * sizeof(nodes[0]));
600 DBG((dbg, LEVEL_1, "live:\n"));
601 for(irn = pset_first(live), i = 0; irn; irn = pset_next(live), i++) {
602 DBG((dbg, LEVEL_1, "\t%+F\n", irn));
607 perm = be_new_Perm(cls, irg, bl, n, nodes);
608 sched_add_after(pos, perm);
612 for (i = 0; i < n; ++i) {
614 ir_node *perm_op = get_irn_n(perm, i);
615 const arch_register_t *reg = arch_get_irn_register(arch_env, perm_op);
617 ir_mode *mode = get_irn_mode(perm_op);
618 ir_node *proj = new_r_Proj(irg, bl, perm, mode, i);
619 arch_set_irn_register(arch_env, proj, reg);
621 sched_add_after(curr, proj);
627 be_ssa_constr(dom_front, lv, 2, copies);
633 struct _elr_closure_t {
635 const be_chordal_env_t *cenv;
638 static void elr_split_walker(ir_node *bl, void *data)
640 struct _elr_closure_t *c = data;
641 const be_chordal_env_t *cenv = c->cenv;
642 const arch_env_t *aenv = cenv->birg->main_env->arch_env;
643 be_lv_t *lv = cenv->birg->lv;
644 be_dom_front_info_t *dom_front = cenv->birg->dom_front;
648 be_insn_env_init(&ie, cenv->birg, cenv->cls, &c->obst);
650 for(insn = be_scan_insn(&ie, sched_first(bl)); !is_Block(insn->irn); insn = be_scan_insn(&ie, insn->next_insn)) {
651 ir_node *pred = sched_prev(insn->irn);
652 if(!is_Block(pred) && !is_Phi(insn->irn))
653 insert_Perm_after(aenv, lv, cenv->cls, dom_front, insn->irn);
657 void extreme_liverange_splitting(struct _be_chordal_env_t *cenv)
659 struct _elr_closure_t c;
660 be_lv_t *lv = cenv->birg->lv;
663 obstack_init(&c.obst);
664 be_liveness_recompute(lv);
665 irg_block_walk_graph(cenv->irg, elr_split_walker, NULL, &c);
666 be_liveness_recompute(lv);
667 obstack_free(&c.obst, NULL);
671 * Post-block-walker: Find blocks containing only one jump and
674 static void remove_empty_block(ir_node *block, void *data) {
675 const ir_edge_t *edge, *next;
678 ir_node *jump = NULL;
680 assert(is_Block(block));
682 if (get_Block_n_cfgpreds(block) != 1)
685 sched_foreach(block, node) {
689 /* we should never have 2 jumps in a block */
690 assert(0 && "We should never have 2 jumps in a block");
699 node = get_Block_cfgpred(block, 0);
700 foreach_out_edge_safe(jump, edge, next) {
701 ir_node *block = get_edge_src_irn(edge);
702 int pos = get_edge_src_pos(edge);
704 set_irn_n(block, pos, node);
707 set_Block_cfgpred(block, 0, new_Bad());
712 /* removes basic blocks that just contain a jump instruction */
713 int be_remove_empty_blocks(ir_graph *irg) {
716 irg_block_walk_graph(irg, remove_empty_block, NULL, &changed);
718 /* invalidate analysis info */
719 set_irg_doms_inconsistent(irg);
720 set_irg_extblk_inconsistent(irg);
721 set_irg_outs_inconsistent(irg);