2 * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief SSA construction for a set of nodes
23 * @author Sebastian Hack, Daniel Grund, Matthias Braun, Christian Wuerdig
26 * Copyright: (c) Universitaet Karlsruhe
27 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
29 * The problem: Given a value and a set of "copies" that are known to
30 * represent the same abstract value, rewire all usages of the original value
31 * to their closest copy while introducing phis as necessary.
33 * Algorithm: Mark all blocks in the iterated dominance frontiers of the value
34 * and it's copies. Link the copies ordered by dominance to the blocks. The
35 * we search for each use all all definitions in the current block, if none is
36 * found, then we search one in the immediate dominator. If we are in a block
37 * of the dominance frontier, create a phi and search do the same search for
44 #include "bessaconstr.h"
46 #include "besched_t.h"
57 #include "iredges_t.h"
59 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
62 * Calculates the iterated dominance frontier of a set of blocks. Marks the
63 * blocks as visited. Sets the link fields of the blocks in the dominance
64 * frontier to the block itself.
67 void mark_iterated_dominance_frontiers(const be_dom_front_info_t *domfronts,
70 DBG((dbg, LEVEL_3, "Dominance Frontier:"));
71 while(!pdeq_empty(worklist)) {
73 ir_node *block = waitq_get(worklist);
74 ir_node **domfront = be_get_dominance_frontier(domfronts, block);
75 int domfront_len = ARR_LEN(domfront);
77 for (i = 0; i < domfront_len; ++i) {
78 ir_node *y = domfront[i];
79 if(Block_block_visited(y))
83 set_irn_link(y, NULL);
84 waitq_put(worklist, y);
86 DBG((dbg, LEVEL_3, " %+F", y));
87 mark_Block_block_visited(y);
90 DBG((dbg, LEVEL_3, "\n"));
94 ir_node *search_def_end_of_block(be_ssa_construction_env_t *env,
98 ir_node *create_phi(be_ssa_construction_env_t *env, ir_node *block,
101 int i, n_preds = get_Block_n_cfgpreds(block);
102 ir_graph *irg = get_irn_irg(block);
104 ir_node **ins = alloca(n_preds * sizeof(ins[0]));
108 for(i = 0; i < n_preds; ++i) {
109 ins[i] = new_r_Unknown(irg, env->mode);
111 phi = new_r_Phi(irg, block, n_preds, ins, env->mode);
112 if(env->new_phis != NULL) {
113 ARR_APP1(ir_node*, env->new_phis, phi);
116 if(env->mode != mode_M) {
117 sched_add_after(block, phi);
120 DBG((dbg, LEVEL_2, "\tcreating phi %+F in %+F\n", phi, block));
121 set_irn_link(link_with, phi);
122 mark_irn_visited(block);
124 for(i = 0; i < n_preds; ++i) {
125 ir_node *pred_block = get_Block_cfgpred_block(block, i);
126 ir_node *pred_def = search_def_end_of_block(env, pred_block);
128 set_irn_n(phi, i, pred_def);
135 ir_node *get_def_at_idom(be_ssa_construction_env_t *env, ir_node *block)
137 ir_node *dom = get_Block_idom(block);
138 ir_node *def = search_def_end_of_block(env, dom);
144 ir_node *search_def_end_of_block(be_ssa_construction_env_t *env, ir_node *block)
146 if(irn_visited(block)) {
147 assert(get_irn_link(block) != NULL);
148 return get_irn_link(block);
149 } else if(Block_block_visited(block)) {
150 return create_phi(env, block, block);
152 ir_node *def = get_def_at_idom(env, block);
153 mark_irn_visited(block);
154 set_irn_link(block, def);
161 ir_node *search_def(be_ssa_construction_env_t *env, ir_node *at)
163 ir_node *block = get_nodes_block(at);
167 DBG((dbg, LEVEL_3, "\t...searching def at %+F\n", at));
169 /* no defs in the current block we can do the normal searching */
170 if(!irn_visited(block) && !Block_block_visited(block)) {
171 DBG((dbg, LEVEL_3, "\t...continue at idom\n"));
172 return get_def_at_idom(env, block);
175 /* there are defs in the current block, walk the linked list to find
176 the one immediately dominating us
179 def = get_irn_link(node);
181 if(!value_dominates(at, def)) {
182 DBG((dbg, LEVEL_3, "\t...found dominating def %+F\n", def));
187 def = get_irn_link(node);
190 /* block in dominance frontier? create a phi then */
191 if(Block_block_visited(block)) {
192 DBG((dbg, LEVEL_3, "\t...create phi at block %+F\n", block));
193 assert(!is_Phi(node));
194 return create_phi(env, block, node);
198 DBG((dbg, LEVEL_3, "\t...continue at idom (after checking block)\n"));
199 return get_def_at_idom(env, block);
203 * Adds a definition into the link field of the block. The definitions are
204 * sorted by dominance. A non-visited block means no definition has been
208 void introduce_def_at_block(ir_node *block, ir_node *def)
210 if(irn_visited(block)) {
211 ir_node *node = block;
212 ir_node *current_def;
215 current_def = get_irn_link(node);
216 if(current_def == def) {
217 /* already in block */
220 if(current_def == NULL)
222 if(value_dominates(current_def, def))
227 set_irn_link(node, def);
228 set_irn_link(def, current_def);
230 set_irn_link(block, def);
231 set_irn_link(def, NULL);
232 mark_irn_visited(block);
236 void be_ssa_construction_init(be_ssa_construction_env_t *env, be_irg_t *birg)
238 ir_graph *irg = be_get_birg_irg(birg);
239 memset(env, 0, sizeof(env[0]));
241 be_assure_dom_front(birg);
244 env->domfronts = be_get_birg_dom_front(birg);
245 env->new_phis = NEW_ARR_F(ir_node*, 0);
246 env->worklist = new_waitq();
248 set_using_visited(irg);
249 set_using_block_visited(irg);
250 set_using_irn_link(irg);
252 /* we use the visited flag to indicate blocks in the dominance frontier
253 * and blocks that already have the relevant value at the end calculated */
254 inc_irg_visited(irg);
255 /* We use the block visited flag to indicate blocks in the dominance
256 * froniter of some values (and this potentially needing phis) */
257 inc_irg_block_visited(irg);
260 void be_ssa_construction_destroy(be_ssa_construction_env_t *env)
262 del_waitq(env->worklist);
263 DEL_ARR_F(env->new_phis);
265 clear_using_visited(env->irg);
266 clear_using_block_visited(env->irg);
267 clear_using_irn_link(env->irg);
270 void be_ssa_construction_add_copy(be_ssa_construction_env_t *env,
275 assert(env->iterated_domfront_calculated == 0);
277 if(env->mode == NULL) {
278 env->mode = get_irn_mode(copy);
280 assert(env->mode == get_irn_mode(copy));
283 block = get_nodes_block(copy);
285 if(!irn_visited(block)) {
286 waitq_put(env->worklist, block);
288 introduce_def_at_block(block, copy);
291 void be_ssa_construction_add_copies(be_ssa_construction_env_t *env,
292 ir_node **copies, size_t copies_len)
296 assert(env->iterated_domfront_calculated == 0);
298 if(env->mode == NULL) {
299 env->mode = get_irn_mode(copies[0]);
302 for(i = 0; i < copies_len; ++i) {
303 ir_node *copy = copies[i];
304 ir_node *block = get_nodes_block(copy);
306 assert(env->mode == get_irn_mode(copy));
307 if(!irn_visited(block)) {
308 waitq_put(env->worklist, block);
310 introduce_def_at_block(block, copy);
314 void be_ssa_construction_set_ignore_uses(be_ssa_construction_env_t *env,
315 const ir_nodeset_t *ignore_uses)
317 env->ignore_uses = ignore_uses;
320 ir_node **be_ssa_construction_get_new_phis(be_ssa_construction_env_t *env)
322 return env->new_phis;
325 void be_ssa_construction_fix_users(be_ssa_construction_env_t *env,
328 const ir_edge_t *edge, *next;
330 if(!env->iterated_domfront_calculated) {
331 mark_iterated_dominance_frontiers(env->domfronts, env->worklist);
332 env->iterated_domfront_calculated = 1;
336 * Search the valid def for each use and set it.
338 foreach_out_edge_safe(value, edge, next) {
339 ir_node *use = get_edge_src_irn(edge);
341 int pos = get_edge_src_pos(edge);
344 if(env->ignore_uses != NULL &&
345 ir_nodeset_contains(env->ignore_uses, use))
349 ir_node *block = get_nodes_block(use);
350 ir_node *predblock = get_Block_cfgpred_block(block, pos);
351 at = sched_last(predblock);
354 def = search_def(env, at);
357 panic("no definition found for %+F at position %d\n", use, pos);
360 DBG((dbg, LEVEL_2, "\t%+F(%d) -> %+F\n", use, pos, def));
361 set_irn_n(use, pos, def);
365 void be_ssa_construction_fix_users_array(be_ssa_construction_env_t *env,
366 ir_node **nodes, size_t nodes_len)
370 for(i = 0; i < nodes_len; ++i) {
371 ir_node *node = nodes[i];
372 be_ssa_construction_fix_users(env, node);
376 void be_ssa_construction_update_liveness_phis(be_ssa_construction_env_t *env,
381 n = ARR_LEN(env->new_phis);
382 for(i = 0; i < n; ++i) {
383 ir_node *phi = env->new_phis[i];
384 be_liveness_introduce(lv, phi);
389 ir_node **be_ssa_construction(const be_dom_front_info_t *domfronts, be_lv_t *lv,
390 ir_node *value, int copies_len, ir_node **copies,
391 const ir_nodeset_t *ignore_uses, int need_new_phis)
393 ir_graph *irg = get_irn_irg(value);
394 const ir_edge_t *edge, *next;
398 be_ssa_construction_env_t env;
400 /* We need to collect the phi functions to compute their liveness. */
401 if(lv != NULL || need_new_phis) {
402 env.new_phis = NEW_ARR_F(ir_node*, 0);
406 env.mode = get_irn_mode(value);
408 set_using_visited(irg);
409 set_using_block_visited(irg);
410 set_using_irn_link(irg);
412 /* we use the visited flag to indicate blocks in the dominance frontier
413 * and blocks that already have the relevant value at the end calculated */
414 inc_irg_visited(irg);
415 /* We use the block visited flag to indicate blocks in the dominance
416 * froniter of some values (and this potentially needing phis) */
417 inc_irg_block_visited(irg);
419 DBG((dbg, LEVEL_1, "Introducing following copies for: %+F\n", value));
420 /* compute iterated dominance frontiers and create lists in the block link
421 * fields that sort usages by dominance. Blocks in the dominance frontier
422 * are marked by links back to the block. */
423 worklist = new_waitq();
425 block = get_nodes_block(value);
426 /* we sometimes replace virtual values by real ones, in this case we do
427 not want to insert them into the def list (they're not scheduled
428 and can't be used anyway) */
429 if(sched_is_scheduled(value)) {
430 introduce_def_at_block(block, value);
432 waitq_put(worklist, block);
434 for(i = 0; i < copies_len; ++i) {
435 ir_node *copy = copies[i];
436 block = get_nodes_block(copy);
438 if(!irn_visited(block)) {
439 waitq_put(worklist, block);
441 introduce_def_at_block(block, copy);
442 DBG((dbg, LEVEL_1, "\t%+F in %+F\n", copy, block));
445 mark_iterated_dominance_frontiers(domfronts, worklist);
448 DBG((dbg, LEVEL_2, "New Definitions:\n"));
450 * Search the valid def for each use and set it.
452 foreach_out_edge_safe(value, edge, next) {
453 ir_node *use = get_edge_src_irn(edge);
455 int pos = get_edge_src_pos(edge);
457 if(ignore_uses != NULL && ir_nodeset_contains(ignore_uses, use))
461 ir_node *block = get_nodes_block(use);
462 ir_node *predblock = get_Block_cfgpred_block(block, pos);
463 at = sched_last(predblock);
466 ir_node *def = search_def(&env, at);
469 panic("no definition found for %+F at position %d\n", use, pos);
472 DBG((dbg, LEVEL_2, "\t%+F(%d) -> %+F\n", use, pos, def));
473 set_irn_n(use, pos, def);
476 /* Recompute the liveness of the original nodes, the copies and the
481 be_liveness_update(lv, value);
482 for(i = 0; i < copies_len; ++i) {
483 ir_node *copy = copies[i];
484 be_liveness_update(lv, copy);
487 n = ARR_LEN(env.new_phis);
488 for(i = 0; i < n; ++i) {
489 ir_node *phi = env.new_phis[i];
490 be_liveness_introduce(lv, phi);
494 clear_using_visited(irg);
495 clear_using_block_visited(irg);
496 clear_using_irn_link(irg);
498 if(!need_new_phis && env.new_phis != NULL) {
499 DEL_ARR_F(env.new_phis);
506 void be_init_ssaconstr(void)
508 FIRM_DBG_REGISTER(dbg, "firm.be.ssaconstr");
511 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_ssaconstr);