4 * This file contains the following IRG modifications for be routines:
5 * - backend dominance information
6 * - SSA construction for a set of nodes
7 * - insertion of Perm nodes
8 * - empty block elimination
9 * - a simple dead node elimination (set inputs of unreachable nodes to BAD)
11 * @author Sebastian Hack, Daniel Grund, Matthias Braun, Christian Wuerdig
14 * Copyright: (c) Universitaet Karlsruhe
15 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
44 #include "iredges_t.h"
45 #include "irgraph_t.h"
47 #include "irprintf_t.h"
51 #include "bechordal_t.h"
53 #include "besched_t.h"
61 DEBUG_ONLY(static firm_dbg_module_t *dbgssa = NULL;)
62 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
71 / ___|___ _ __ ___| |_ _ __ _ _ ___| |_(_) ___ _ __
72 | | / _ \| '_ \/ __| __| '__| | | |/ __| __| |/ _ \| '_ \
73 | |__| (_) | | | \__ \ |_| | | |_| | (__| |_| | (_) | | | |
74 \____\___/|_| |_|___/\__|_| \__,_|\___|\__|_|\___/|_| |_|
78 /* The problem: Given a value and a set of "copies" that are known to represent
79 * the same abstract value, rewire all usages of the original value to their
80 * closest copy while introducing phis as necessary.
82 * Algorithm: Mark all blocks in the iterated dominance frontiers of the value
83 * and it's copies. Link the copies ordered by dominance to the blocks.
84 * The we search for each use all all definitions in the current block, if none
85 * is found, then we search one in the immediate dominator. If we are in a block
86 * of the dominance frontier, create a phi and search do the same search for the
91 * Calculates the iterated dominance frontier of a set of blocks. Marks the
92 * blocks as visited. Sets the link fields of the blocks in the dominance
93 * frontier to the block itself.
96 void mark_iterated_dominance_frontiers(const be_dom_front_info_t *domfronts,
99 DBG((dbgssa, LEVEL_3, "Dominance Frontier:"));
100 while(!pdeq_empty(worklist)) {
102 ir_node *block = waitq_get(worklist);
103 ir_node **domfront = be_get_dominance_frontier(domfronts, block);
104 int domfront_len = ARR_LEN(domfront);
106 for (i = 0; i < domfront_len; ++i) {
107 ir_node *y = domfront[i];
108 if(Block_block_visited(y))
111 if(!irn_visited(y)) {
112 set_irn_link(y, NULL);
113 waitq_put(worklist, y);
115 DBG((dbgssa, LEVEL_3, " %+F", y));
116 mark_Block_block_visited(y);
119 DBG((dbgssa, LEVEL_3, "\n"));
122 typedef struct ssa_constr_env_t {
123 ir_node **new_phis; /**< ARR_F of newly created phis or NULL */
124 ir_mode *mode; /**< mode of the value */
128 ir_node *search_def_end_of_block(ssa_constr_env_t *env, ir_node *block);
131 ir_node *create_phi(ssa_constr_env_t *env, ir_node *block, ir_node *link_with)
133 int i, n_preds = get_Block_n_cfgpreds(block);
134 ir_graph *irg = get_irn_irg(block);
136 ir_node **ins = alloca(n_preds * sizeof(ins[0]));
140 for(i = 0; i < n_preds; ++i) {
141 ins[i] = new_r_Unknown(irg, env->mode);
143 phi = new_r_Phi(irg, block, n_preds, ins, env->mode);
144 if(env->new_phis != NULL) {
145 ARR_APP1(ir_node*, env->new_phis, phi);
148 if(env->mode != mode_M) {
149 sched_add_after(block, phi);
152 DBG((dbgssa, LEVEL_2, "\tcreating phi %+F in %+F\n", phi, block));
153 set_irn_link(link_with, phi);
154 mark_irn_visited(block);
156 for(i = 0; i < n_preds; ++i) {
157 ir_node *pred_block = get_Block_cfgpred_block(block, i);
158 ir_node *pred_def = search_def_end_of_block(env, pred_block);
160 set_irn_n(phi, i, pred_def);
167 ir_node *get_def_at_idom(ssa_constr_env_t *env, ir_node *block)
169 ir_node *dom = get_Block_idom(block);
170 ir_node *def = search_def_end_of_block(env, dom);
176 ir_node *search_def_end_of_block(ssa_constr_env_t *env, ir_node *block)
178 if(irn_visited(block)) {
179 assert(get_irn_link(block) != NULL);
180 return get_irn_link(block);
181 } else if(Block_block_visited(block)) {
182 return create_phi(env, block, block);
184 ir_node *def = get_def_at_idom(env, block);
186 mark_irn_visited(block);
187 set_irn_link(block, def);
195 ir_node *search_def(ssa_constr_env_t *env, ir_node *at)
197 ir_node *block = get_nodes_block(at);
201 DBG((dbgssa, LEVEL_3, "\t...searching def at %+F\n", at));
203 /* no defs in the current block we can do the normal searching */
204 if(!irn_visited(block) && !Block_block_visited(block)) {
205 DBG((dbgssa, LEVEL_3, "\t...continue at idom\n"));
206 return get_def_at_idom(env, block);
209 /* there are defs in the current block, walk the linked list to find
210 the one immediately dominating us
213 def = get_irn_link(node);
216 assert(get_nodes_block(def) == block);
217 if(!value_dominates_intrablock(at, def)) {
218 DBG((dbgssa, LEVEL_3, "\t...found dominating def %+F\n", def));
222 if(!value_dominates(at, def)) {
223 DBG((dbgssa, LEVEL_3, "\t...found dominating def %+F\n", def));
228 def = get_irn_link(node);
231 /* block in dominance frontier? create a phi then */
232 if(Block_block_visited(block)) {
233 DBG((dbgssa, LEVEL_3, "\t...create phi at block %+F\n", block));
234 assert(!is_Phi(node));
235 return create_phi(env, block, node);
239 DBG((dbgssa, LEVEL_3, "\t...continue at idom (after checking block)\n"));
240 return get_def_at_idom(env, block);
244 * Adds a definition into the link field of the block. The definitions are
245 * sorted by dominance. A non-visited block means no definition has been
249 void introduce_def_at_block(ir_node *block, ir_node *def)
251 if(irn_visited(block)) {
252 ir_node *node = block;
253 ir_node *current_def;
256 current_def = get_irn_link(node);
257 if(current_def == def) {
258 /* already in block */
261 if(current_def == NULL)
263 if(value_dominates(current_def, def))
268 set_irn_link(node, def);
269 set_irn_link(def, current_def);
271 set_irn_link(block, def);
272 set_irn_link(def, NULL);
273 mark_irn_visited(block);
277 ir_node **be_ssa_construction(const be_dom_front_info_t *domfronts, be_lv_t *lv,
278 ir_node *value, int copies_len, ir_node **copies,
279 const ir_nodeset_t *ignore_uses, int need_new_phis)
281 ir_graph *irg = get_irn_irg(value);
282 const ir_edge_t *edge, *next;
286 ssa_constr_env_t env;
288 /* We need to collect the phi functions to compute their liveness. */
289 if(lv != NULL || need_new_phis) {
290 env.new_phis = NEW_ARR_F(ir_node*, 0);
294 env.mode = get_irn_mode(value);
296 set_using_visited(irg);
297 set_using_block_visited(irg);
298 set_using_irn_link(irg);
300 /* we use the visited flag to indicate blocks in the dominance frontier
301 * and blocks that already have the relevant value at the end calculated */
302 inc_irg_visited(irg);
303 /* We use the block visited flag to indicate blocks in the dominance
304 * froniter of some values (and this potentially needing phis) */
305 inc_irg_block_visited(irg);
307 DBG((dbgssa, LEVEL_1, "Introducing following copies for: %+F\n", value));
308 /* compute iterated dominance frontiers and create lists in the block link
309 * fields that sort usages by dominance. Blocks in the dominance frontier
310 * are marked by links back to the block. */
311 worklist = new_waitq();
313 block = get_nodes_block(value);
314 introduce_def_at_block(block, value);
315 waitq_put(worklist, block);
317 for(i = 0; i < copies_len; ++i) {
318 ir_node *copy = copies[i];
319 block = get_nodes_block(copy);
321 if(!irn_visited(block)) {
322 waitq_put(worklist, block);
324 introduce_def_at_block(block, copy);
325 DBG((dbgssa, LEVEL_1, "\t%+F in %+F\n", copy, block));
328 mark_iterated_dominance_frontiers(domfronts, worklist);
331 DBG((dbgssa, LEVEL_2, "New Definitions:\n"));
333 * Search the valid def for each use and set it.
335 foreach_out_edge_safe(value, edge, next) {
336 ir_node *use = get_edge_src_irn(edge);
338 int pos = get_edge_src_pos(edge);
340 if(ignore_uses != NULL && ir_nodeset_contains(ignore_uses, use))
344 ir_node *block = get_nodes_block(use);
345 ir_node *predblock = get_Block_cfgpred_block(block, pos);
346 at = sched_last(predblock);
349 ir_node *def = search_def(&env, at);
352 panic("no definition found for %+F at position %d\n", use, pos);
355 DBG((dbgssa, LEVEL_2, "\t%+F(%d) -> %+F\n", use, pos, def));
356 set_irn_n(use, pos, def);
359 /* Recompute the liveness of the original nodes, the copies and the
364 be_liveness_update(lv, value);
365 for(i = 0; i < copies_len; ++i) {
366 ir_node *copy = copies[i];
367 be_liveness_update(lv, copy);
370 n = ARR_LEN(env.new_phis);
371 for(i = 0; i < n; ++i) {
372 ir_node *phi = env.new_phis[i];
373 be_liveness_introduce(lv, phi);
377 clear_using_visited(irg);
378 clear_using_block_visited(irg);
379 clear_using_irn_link(irg);
381 if(!need_new_phis && env.new_phis != NULL) {
382 DEL_ARR_F(env.new_phis);
388 void be_ssa_constr_set_ignore(const be_dom_front_info_t *domfronts, be_lv_t *lv,
389 pset *nodes, pset *ignores)
392 const ir_edge_t *edge, *next;
397 ssa_constr_env_t env;
399 foreach_pset(nodes, value) {
403 irg = get_irn_irg(value);
405 /* We need to collect the phi functions to compute their liveness. */
407 env.new_phis = NEW_ARR_F(ir_node*, 0);
410 set_using_visited(irg);
411 set_using_block_visited(irg);
412 set_using_irn_link(irg);
414 /* we use the visited flag to indicate blocks in the dominance frontier
415 * and blocks that already have the relevant value at the end calculated */
416 inc_irg_visited(irg);
417 /* We use the block visited flag to indicate blocks in the dominance
418 * froniter of some values (and this potentially needing phis) */
419 inc_irg_block_visited(irg);
421 DBG((dbgssa, LEVEL_1, "Introducing following copies for:\n"));
423 /* compute iterated dominance frontiers and create lists in the block link
424 * fields that sort usages by dominance. Blocks in the dominance frontier
425 * are marked by links back to the block. */
426 worklist = new_waitq();
428 foreach_pset(nodes, value) {
429 block = get_nodes_block(value);
430 env.mode = get_irn_mode(value);
432 if(!irn_visited(block)) {
433 waitq_put(worklist, block);
435 introduce_def_at_block(block, value);
436 DBG((dbgssa, LEVEL_1, "\t%+F in %+F\n", value, block));
439 mark_iterated_dominance_frontiers(domfronts, worklist);
443 * Search the valid def for each use and set it.
445 foreach_pset(nodes, value) {
446 foreach_out_edge_safe(value, edge, next) {
447 ir_node *use = get_edge_src_irn(edge);
449 int pos = get_edge_src_pos(edge);
451 if(ignores != NULL && pset_find_ptr(ignores, use))
455 ir_node *block = get_nodes_block(use);
456 ir_node *predblock = get_Block_cfgpred_block(block, pos);
457 at = sched_last(predblock);
460 ir_node *def = search_def(&env, at);
463 panic("no definition found for %+F input %d\n", use, pos);
466 DBG((dbgssa, LEVEL_2, "\t%+F(%d) -> %+F\n", use, pos, def));
467 set_irn_n(use, pos, def);
471 /* Recompute the liveness of the original nodes, the copies and the
476 foreach_pset(nodes, value) {
477 be_liveness_update(lv, value);
480 n = ARR_LEN(env.new_phis);
481 for(i = 0; i < n; ++i) {
482 ir_node *phi = env.new_phis[i];
483 be_liveness_introduce(lv, phi);
485 DEL_ARR_F(env.new_phis);
488 clear_using_visited(irg);
489 clear_using_block_visited(irg);
490 clear_using_irn_link(irg);
495 |_ _|_ __ ___ ___ _ __| |_ | _ \ ___ _ __ _ __ ___
496 | || '_ \/ __|/ _ \ '__| __| | |_) / _ \ '__| '_ ` _ \
497 | || | | \__ \ __/ | | |_ | __/ __/ | | | | | | |
498 |___|_| |_|___/\___|_| \__| |_| \___|_| |_| |_| |_|
502 ir_node *insert_Perm_after(const arch_env_t *arch_env,
504 const arch_register_class_t *cls,
505 be_dom_front_info_t *dom_front,
508 ir_node *bl = is_Block(pos) ? pos : get_nodes_block(pos);
509 ir_graph *irg = get_irn_irg(bl);
510 pset *live = pset_new_ptr_default();
512 ir_node *curr, *irn, *perm, **nodes;
515 DBG((dbg, LEVEL_1, "Insert Perm after: %+F\n", pos));
517 be_liveness_nodes_live_at(lv, arch_env, cls, pos, live);
519 n = pset_count(live);
526 nodes = xmalloc(n * sizeof(nodes[0]));
528 DBG((dbg, LEVEL_1, "live:\n"));
529 for(irn = pset_first(live), i = 0; irn; irn = pset_next(live), i++) {
530 DBG((dbg, LEVEL_1, "\t%+F\n", irn));
535 perm = be_new_Perm(cls, irg, bl, n, nodes);
536 sched_add_after(pos, perm);
540 for (i = 0; i < n; ++i) {
542 ir_node *perm_op = get_irn_n(perm, i);
543 const arch_register_t *reg = arch_get_irn_register(arch_env, perm_op);
545 ir_mode *mode = get_irn_mode(perm_op);
546 ir_node *proj = new_r_Proj(irg, bl, perm, mode, i);
547 arch_set_irn_register(arch_env, proj, reg);
549 sched_add_after(curr, proj);
554 be_ssa_construction(dom_front, lv, perm_op, 1, copies, NULL, 0);
561 * Post-block-walker: Find blocks containing only one jump and
564 static void remove_empty_block(ir_node *block, void *data) {
565 const ir_edge_t *edge, *next;
568 ir_node *jump = NULL;
570 assert(is_Block(block));
572 if (get_Block_n_cfgpreds(block) != 1)
575 sched_foreach(block, node) {
579 /* we should never have 2 jumps in a block */
580 panic("We should never have 2 jumps in a block");
588 node = get_Block_cfgpred(block, 0);
589 foreach_out_edge_safe(jump, edge, next) {
590 ir_node *block = get_edge_src_irn(edge);
591 int pos = get_edge_src_pos(edge);
593 set_irn_n(block, pos, node);
596 set_Block_cfgpred(block, 0, new_Bad());
601 /* removes basic blocks that just contain a jump instruction */
602 int be_remove_empty_blocks(ir_graph *irg) {
605 irg_block_walk_graph(irg, remove_empty_block, NULL, &changed);
607 /* invalidate analysis info */
608 set_irg_doms_inconsistent(irg);
609 set_irg_extblk_inconsistent(irg);
610 set_irg_outs_inconsistent(irg);
615 void be_init_irgmod(void)
617 FIRM_DBG_REGISTER(dbgssa, "firm.be.ssaconstr");
618 FIRM_DBG_REGISTER(dbg, "firm.be.irgmod");
621 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_irgmod);