3 * @brief SSA construction for a set of nodes
4 * @author Sebastian Hack, Daniel Grund, Matthias Braun, Christian Wuerdig
7 * Copyright: (c) Universitaet Karlsruhe
8 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
10 * The problem: Given a value and a set of "copies" that are known to
11 * represent the same abstract value, rewire all usages of the original value
12 * to their closest copy while introducing phis as necessary.
14 * Algorithm: Mark all blocks in the iterated dominance frontiers of the value
15 * and it's copies. Link the copies ordered by dominance to the blocks. The
16 * we search for each use all all definitions in the current block, if none is
17 * found, then we search one in the immediate dominator. If we are in a block
18 * of the dominance frontier, create a phi and search do the same search for
25 #include "bessaconstr.h"
27 #include "besched_t.h"
38 #include "iredges_t.h"
40 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
43 * Calculates the iterated dominance frontier of a set of blocks. Marks the
44 * blocks as visited. Sets the link fields of the blocks in the dominance
45 * frontier to the block itself.
48 void mark_iterated_dominance_frontiers(const be_dom_front_info_t *domfronts,
51 DBG((dbg, LEVEL_3, "Dominance Frontier:"));
52 while(!pdeq_empty(worklist)) {
54 ir_node *block = waitq_get(worklist);
55 ir_node **domfront = be_get_dominance_frontier(domfronts, block);
56 int domfront_len = ARR_LEN(domfront);
58 for (i = 0; i < domfront_len; ++i) {
59 ir_node *y = domfront[i];
60 if(Block_block_visited(y))
64 set_irn_link(y, NULL);
65 waitq_put(worklist, y);
67 DBG((dbg, LEVEL_3, " %+F", y));
68 mark_Block_block_visited(y);
71 DBG((dbg, LEVEL_3, "\n"));
75 ir_node *search_def_end_of_block(be_ssa_construction_env_t *env,
79 ir_node *create_phi(be_ssa_construction_env_t *env, ir_node *block,
82 int i, n_preds = get_Block_n_cfgpreds(block);
83 ir_graph *irg = get_irn_irg(block);
85 ir_node **ins = alloca(n_preds * sizeof(ins[0]));
89 for(i = 0; i < n_preds; ++i) {
90 ins[i] = new_r_Unknown(irg, env->mode);
92 phi = new_r_Phi(irg, block, n_preds, ins, env->mode);
93 if(env->new_phis != NULL) {
94 ARR_APP1(ir_node*, env->new_phis, phi);
97 if(env->mode != mode_M) {
98 sched_add_after(block, phi);
101 DBG((dbg, LEVEL_2, "\tcreating phi %+F in %+F\n", phi, block));
102 set_irn_link(link_with, phi);
103 mark_irn_visited(block);
105 for(i = 0; i < n_preds; ++i) {
106 ir_node *pred_block = get_Block_cfgpred_block(block, i);
107 ir_node *pred_def = search_def_end_of_block(env, pred_block);
109 set_irn_n(phi, i, pred_def);
116 ir_node *get_def_at_idom(be_ssa_construction_env_t *env, ir_node *block)
118 ir_node *dom = get_Block_idom(block);
119 ir_node *def = search_def_end_of_block(env, dom);
125 ir_node *search_def_end_of_block(be_ssa_construction_env_t *env, ir_node *block)
127 if(irn_visited(block)) {
128 assert(get_irn_link(block) != NULL);
129 return get_irn_link(block);
130 } else if(Block_block_visited(block)) {
131 return create_phi(env, block, block);
133 ir_node *def = get_def_at_idom(env, block);
134 mark_irn_visited(block);
135 set_irn_link(block, def);
142 ir_node *search_def(be_ssa_construction_env_t *env, ir_node *at)
144 ir_node *block = get_nodes_block(at);
148 DBG((dbg, LEVEL_3, "\t...searching def at %+F\n", at));
150 /* no defs in the current block we can do the normal searching */
151 if(!irn_visited(block) && !Block_block_visited(block)) {
152 DBG((dbg, LEVEL_3, "\t...continue at idom\n"));
153 return get_def_at_idom(env, block);
156 /* there are defs in the current block, walk the linked list to find
157 the one immediately dominating us
160 def = get_irn_link(node);
162 if(!value_dominates(at, def)) {
163 DBG((dbg, LEVEL_3, "\t...found dominating def %+F\n", def));
168 def = get_irn_link(node);
171 /* block in dominance frontier? create a phi then */
172 if(Block_block_visited(block)) {
173 DBG((dbg, LEVEL_3, "\t...create phi at block %+F\n", block));
174 assert(!is_Phi(node));
175 return create_phi(env, block, node);
179 DBG((dbg, LEVEL_3, "\t...continue at idom (after checking block)\n"));
180 return get_def_at_idom(env, block);
184 * Adds a definition into the link field of the block. The definitions are
185 * sorted by dominance. A non-visited block means no definition has been
189 void introduce_def_at_block(ir_node *block, ir_node *def)
191 if(irn_visited(block)) {
192 ir_node *node = block;
193 ir_node *current_def;
196 current_def = get_irn_link(node);
197 if(current_def == def) {
198 /* already in block */
201 if(current_def == NULL)
203 if(value_dominates(current_def, def))
208 set_irn_link(node, def);
209 set_irn_link(def, current_def);
211 set_irn_link(block, def);
212 set_irn_link(def, NULL);
213 mark_irn_visited(block);
217 void be_ssa_construction_init(be_ssa_construction_env_t *env, be_irg_t *birg)
219 ir_graph *irg = be_get_birg_irg(birg);
220 memset(env, 0, sizeof(env[0]));
222 be_assure_dom_front(birg);
225 env->domfronts = be_get_birg_dom_front(birg);
226 env->new_phis = NEW_ARR_F(ir_node*, 0);
227 env->worklist = new_waitq();
229 set_using_visited(irg);
230 set_using_block_visited(irg);
231 set_using_irn_link(irg);
233 /* we use the visited flag to indicate blocks in the dominance frontier
234 * and blocks that already have the relevant value at the end calculated */
235 inc_irg_visited(irg);
236 /* We use the block visited flag to indicate blocks in the dominance
237 * froniter of some values (and this potentially needing phis) */
238 inc_irg_block_visited(irg);
241 void be_ssa_construction_destroy(be_ssa_construction_env_t *env)
243 del_waitq(env->worklist);
244 DEL_ARR_F(env->new_phis);
246 clear_using_visited(env->irg);
247 clear_using_block_visited(env->irg);
248 clear_using_irn_link(env->irg);
251 void be_ssa_construction_add_copy(be_ssa_construction_env_t *env,
256 assert(env->iterated_domfront_calculated == 0);
258 if(env->mode == NULL) {
259 env->mode = get_irn_mode(copy);
261 assert(env->mode == get_irn_mode(copy));
264 block = get_nodes_block(copy);
266 if(!irn_visited(block)) {
267 waitq_put(env->worklist, block);
269 introduce_def_at_block(block, copy);
272 void be_ssa_construction_add_copies(be_ssa_construction_env_t *env,
273 ir_node **copies, size_t copies_len)
277 assert(env->iterated_domfront_calculated == 0);
279 if(env->mode == NULL) {
280 env->mode = get_irn_mode(copies[0]);
283 for(i = 0; i < copies_len; ++i) {
284 ir_node *copy = copies[i];
285 ir_node *block = get_nodes_block(copy);
287 assert(env->mode == get_irn_mode(copy));
288 if(!irn_visited(block)) {
289 waitq_put(env->worklist, block);
291 introduce_def_at_block(block, copy);
295 void be_ssa_construction_set_ignore_uses(be_ssa_construction_env_t *env,
296 const ir_nodeset_t *ignore_uses)
298 env->ignore_uses = ignore_uses;
301 ir_node **be_ssa_construction_get_new_phis(be_ssa_construction_env_t *env)
303 return env->new_phis;
306 void be_ssa_construction_fix_users(be_ssa_construction_env_t *env,
309 const ir_edge_t *edge, *next;
311 if(!env->iterated_domfront_calculated) {
312 mark_iterated_dominance_frontiers(env->domfronts, env->worklist);
313 env->iterated_domfront_calculated = 1;
317 * Search the valid def for each use and set it.
319 foreach_out_edge_safe(value, edge, next) {
320 ir_node *use = get_edge_src_irn(edge);
322 int pos = get_edge_src_pos(edge);
325 if(env->ignore_uses != NULL &&
326 ir_nodeset_contains(env->ignore_uses, use))
330 ir_node *block = get_nodes_block(use);
331 ir_node *predblock = get_Block_cfgpred_block(block, pos);
332 at = sched_last(predblock);
335 def = search_def(env, at);
338 panic("no definition found for %+F at position %d\n", use, pos);
341 DBG((dbg, LEVEL_2, "\t%+F(%d) -> %+F\n", use, pos, def));
342 set_irn_n(use, pos, def);
346 void be_ssa_construction_fix_users_array(be_ssa_construction_env_t *env,
347 ir_node **nodes, size_t nodes_len)
351 for(i = 0; i < nodes_len; ++i) {
352 ir_node *node = nodes[i];
353 be_ssa_construction_fix_users(env, node);
357 void be_ssa_construction_update_liveness_phis(be_ssa_construction_env_t *env,
362 n = ARR_LEN(env->new_phis);
363 for(i = 0; i < n; ++i) {
364 ir_node *phi = env->new_phis[i];
365 be_liveness_introduce(lv, phi);
370 ir_node **be_ssa_construction(const be_dom_front_info_t *domfronts, be_lv_t *lv,
371 ir_node *value, int copies_len, ir_node **copies,
372 const ir_nodeset_t *ignore_uses, int need_new_phis)
374 ir_graph *irg = get_irn_irg(value);
375 const ir_edge_t *edge, *next;
379 be_ssa_construction_env_t env;
381 /* We need to collect the phi functions to compute their liveness. */
382 if(lv != NULL || need_new_phis) {
383 env.new_phis = NEW_ARR_F(ir_node*, 0);
387 env.mode = get_irn_mode(value);
389 set_using_visited(irg);
390 set_using_block_visited(irg);
391 set_using_irn_link(irg);
393 /* we use the visited flag to indicate blocks in the dominance frontier
394 * and blocks that already have the relevant value at the end calculated */
395 inc_irg_visited(irg);
396 /* We use the block visited flag to indicate blocks in the dominance
397 * froniter of some values (and this potentially needing phis) */
398 inc_irg_block_visited(irg);
400 DBG((dbg, LEVEL_1, "Introducing following copies for: %+F\n", value));
401 /* compute iterated dominance frontiers and create lists in the block link
402 * fields that sort usages by dominance. Blocks in the dominance frontier
403 * are marked by links back to the block. */
404 worklist = new_waitq();
406 block = get_nodes_block(value);
407 /* we sometimes replace virtual values by real ones, in this case we do
408 not want to insert them into the def list (they're not scheduled
409 and can't be used anyway) */
410 if(sched_is_scheduled(value)) {
411 introduce_def_at_block(block, value);
413 waitq_put(worklist, block);
415 for(i = 0; i < copies_len; ++i) {
416 ir_node *copy = copies[i];
417 block = get_nodes_block(copy);
419 if(!irn_visited(block)) {
420 waitq_put(worklist, block);
422 introduce_def_at_block(block, copy);
423 DBG((dbg, LEVEL_1, "\t%+F in %+F\n", copy, block));
426 mark_iterated_dominance_frontiers(domfronts, worklist);
429 DBG((dbg, LEVEL_2, "New Definitions:\n"));
431 * Search the valid def for each use and set it.
433 foreach_out_edge_safe(value, edge, next) {
434 ir_node *use = get_edge_src_irn(edge);
436 int pos = get_edge_src_pos(edge);
438 if(ignore_uses != NULL && ir_nodeset_contains(ignore_uses, use))
442 ir_node *block = get_nodes_block(use);
443 ir_node *predblock = get_Block_cfgpred_block(block, pos);
444 at = sched_last(predblock);
447 ir_node *def = search_def(&env, at);
450 panic("no definition found for %+F at position %d\n", use, pos);
453 DBG((dbg, LEVEL_2, "\t%+F(%d) -> %+F\n", use, pos, def));
454 set_irn_n(use, pos, def);
457 /* Recompute the liveness of the original nodes, the copies and the
462 be_liveness_update(lv, value);
463 for(i = 0; i < copies_len; ++i) {
464 ir_node *copy = copies[i];
465 be_liveness_update(lv, copy);
468 n = ARR_LEN(env.new_phis);
469 for(i = 0; i < n; ++i) {
470 ir_node *phi = env.new_phis[i];
471 be_liveness_introduce(lv, phi);
475 clear_using_visited(irg);
476 clear_using_block_visited(irg);
477 clear_using_irn_link(irg);
479 if(!need_new_phis && env.new_phis != NULL) {
480 DEL_ARR_F(env.new_phis);
487 void be_init_ssaconstr(void)
489 FIRM_DBG_REGISTER(dbg, "firm.be.ssaconstr");
492 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_ssaconstr);