19 #include "iredges_t.h"
24 #include "besched_t.h"
30 #define DBG_MODULE firm_dbg_register("firm.be.irgmod")
32 struct _dom_front_info_t {
37 * A wrapper for get_Block_idom.
38 * This function returns the block itself, if the block is the start
39 * block. Returning NULL would make any != comparison true which
40 * suggests, that the start block is dominated by some other node.
41 * @param bl The block.
42 * @return The immediate dominator of the block.
44 static INLINE ir_node *get_idom(ir_node *bl)
46 ir_node *idom = get_Block_idom(bl);
47 return idom == NULL ? bl : idom;
50 static void compute_df_local(ir_node *bl, void *data)
52 pmap *df_map = ((dom_front_info_t *) data)->df_map;
53 ir_node *idom = get_Block_idom(bl);
54 pset *df = pmap_get(df_map, bl);
58 * In the case that the immediate dominator is NULL, the
59 * block is the start block and its immediate dominator
60 * must be itself, else it is inserted into its own
67 * Create a new dom frot set for this node,
71 pmap_insert(df_map, bl, pset_new_ptr(16));
73 for(i = 0, n = get_irn_arity(bl); i < n; ++i) {
75 /* The predecessor block */
76 ir_node *pred = get_nodes_block(get_irn_n(bl, i));
78 /* The dominance frontier set of the predecessor. */
79 pset *df = pmap_get(df_map, pred);
81 df = pset_new_ptr(16);
82 pmap_insert(df_map, pred, df);
85 assert(df && "dom front set must have been created for this node");
87 if(pred != idom && bl)
88 pset_insert_ptr(df, bl);
92 static void compute_df_up(ir_node *bl, void *data)
94 pmap *df_map = ((dom_front_info_t *) data)->df_map;
97 for(y = get_Block_dominated_first(bl); y; y = get_Block_dominated_next(y)) {
99 pset *df = pmap_get(df_map, y);
101 for(w = pset_first(df); w; w = pset_next(df))
102 if(!block_dominates(bl, w) || bl == w)
103 pset_insert_ptr(df, w);
107 static void compute_df(ir_node *n, pmap *df_map)
110 const ir_edge_t *edge;
111 pset *df = pset_new_ptr_default();
113 /* Add local dominance frontiers */
114 foreach_block_succ(n, edge) {
115 ir_node *y = edge->src;
118 pset_insert_ptr(df, y);
122 * Go recursively down the dominance tree and add all blocks
123 * int the dominance frontiers of the children, which are not
124 * dominated by the given block.
126 for(c = get_Block_dominated_first(n); c; c = get_Block_dominated_next(c)) {
130 compute_df(c, df_map);
131 df_c = pmap_get(df_map, c);
133 for(w = pset_first(df_c); w; w = pset_next(df_c)) {
134 if(!block_dominates(n, w))
135 pset_insert_ptr(df, w);
139 pmap_insert(df_map, n, df);
143 dom_front_info_t *be_compute_dominance_frontiers(ir_graph *irg)
145 dom_front_info_t *info = malloc(sizeof(*info));
148 info->df_map = pmap_create();
149 compute_df(get_irg_start_block(irg), info->df_map);
153 * This must be called as a post walker, since the dom front sets
154 * of all predecessors must be created when a block is reached.
156 dom_tree_walk_irg(irg, NULL, compute_df_local, info);
157 dom_tree_walk_irg(irg, NULL, compute_df_up, info);
162 void be_free_dominance_frontiers(dom_front_info_t *info)
166 for(ent = pmap_first(info->df_map); ent; ent = pmap_next(info->df_map))
167 del_pset(ent->value);
169 pmap_destroy(info->df_map);
173 pset *be_get_dominance_frontier(dom_front_info_t *info, ir_node *block)
175 return pmap_get(info->df_map, block);
179 * Algorithm to place the Phi-Functions.
180 * @see Appel, Modern Compiler Implementation in Java, 2nd ed., p. 399ff
182 * This function takes an original node and a set of already placed
183 * copies of that node called @p copies. It places phi nodes at the
184 * iterated dominance frontiers of these copies and puts these phi nodes
185 * in the @p copies set, since they are another form of copies of the
188 * The rename phase (see below) is responsible for fixing up the usages
189 * of the original node.
191 * @param orig The original node.
192 * @param copies A set contianing nodes representing a copy of the
193 * original node. Each node must be inserted into the block's schedule.
194 * @param copy_blocks A set in which the blocks are recorded which
195 * contain a copy. This is just for efficiency in later phases (see
198 static void place_phi_functions(ir_node *orig, pset *copies,
199 pset *copy_blocks, dom_front_info_t *df_info)
202 ir_node *orig_block = get_nodes_block(orig);
203 ir_graph *irg = get_irn_irg(orig);
204 ir_mode *mode = get_irn_mode(orig);
205 pdeq *worklist = new_pdeq();
206 pset *phi_blocks = pset_new_ptr(8);
207 ir_node **ins = NULL;
209 firm_dbg_module_t *dbg = DBG_MODULE;
212 * Allocate an array for all blocks where the copies and the original
213 * value were defined.
215 int n_orig_blocks = pset_count(copy_blocks);
216 ir_node **orig_blocks = malloc(n_orig_blocks * sizeof(orig_blocks[0]));
219 * Fill the worklist queue and the rest of the orig blocks array.
221 for(it = pset_first(copy_blocks), i = 0; it; it = pset_next(copy_blocks)) {
222 ir_node *copy_block = it;
224 assert(block_dominates(orig_block, copy_block)
225 && "The block of the copy must be dominated by the block of the value");
227 pdeq_putr(worklist, copy_block);
228 orig_blocks[i++] = copy_block;
231 while(!pdeq_empty(worklist)) {
232 ir_node *bl = pdeq_getl(worklist);
234 pset *df = be_get_dominance_frontier(df_info, bl);
236 DBG((dbg, LEVEL_3, "dom front of %+F\n", bl));
237 for(y = pset_first(df); y; y = pset_next(df))
238 DBG((dbg, LEVEL_3, "\t%+F\n", y));
240 for(y = pset_first(df); y; y = pset_next(df)) {
241 int n_preds = get_irn_arity(y);
243 if(!pset_find_ptr(phi_blocks, y)) {
248 * Set the orig node as the only operand of the
251 ins = realloc(ins, n_preds * sizeof(ins[0]));
252 for(i = 0; i < n_preds; ++i)
255 /* Insert phi node */
256 phi = new_r_Phi(irg, y, n_preds, ins, mode);
257 DBG((dbg, LEVEL_2, " inserting phi %+F with %d args in block %+F\n",
261 * The phi node itself is also a copy of the original
262 * value. So put it in the copies set also, so that
263 * the rename phase can treat them right.
265 pset_insert_ptr(copies, phi);
266 pset_insert_ptr(copy_blocks, y);
269 * Insert the phi node into the schedule if it
270 * can occur there (PhiM's are not to put into a schedule.
272 if(to_appear_in_schedule(phi))
273 sched_add_before(sched_first(y), phi);
275 /* Insert the phi node in the phi blocks set. */
276 pset_insert_ptr(phi_blocks, y);
279 * If orig or a copy of it were not defined in y,
280 * add y to the worklist.
282 for(i = 0; i < n_orig_blocks; ++i)
283 if(orig_blocks[i] == y) {
289 pdeq_putr(worklist, y);
295 del_pset(phi_blocks);
305 * Find the copy of the given original node whose value is 'active'
308 * The usage is given as a node and a position. Initially, the given operand
309 * points to a node for which copies were introduced. We have to find
310 * the valid copy for this usage. This is done by travering the
311 * dominance tree upwards. If the usage is a phi function, we start
312 * traversing from the predecessor block which corresponds to the phi
315 * @param usage The node which uses the original node.
316 * @param pos The number of the argument which corresponds to the
318 * @param copy_blocks A set containing all basic block in which copies
319 * of the original node are located.
320 * @param copies A set containing all node which are copies from the
322 * @return The valid copy for usage.
324 static ir_node *search_def(ir_node *usage, int pos, pset *copies, pset *copy_blocks)
328 firm_dbg_module_t *dbg = DBG_MODULE;
329 firm_dbg_set_mask(dbg, -1);
331 curr_bl = get_nodes_block(usage);
334 DBG((dbg, LEVEL_1, "Searching valid def for use %+F at pos %d\n", usage, pos));
336 * If the usage is in a phi node, search the copy in the
337 * predecessor denoted by pos.
340 curr_bl = get_Block_cfgpred_block(curr_bl, pos);
341 start_irn = sched_last(curr_bl);
343 start_irn = sched_prev(usage);
347 * Traverse the dominance tree upwards from the
348 * predecessor block of the usage.
350 while(curr_bl != NULL) {
353 * If this block contains a copy, search the block
354 * instruction by instruction.
356 if(pset_find_ptr(copy_blocks, curr_bl)) {
359 /* Look at each instruction from last to first. */
360 for(irn = start_irn; !is_Block(irn); irn = sched_prev(irn)) {
362 /* Take the first copy we find. */
363 if(pset_find_ptr(copies, irn))
368 /* If were not done yet, look in the immediate dominator */
369 curr_bl = get_Block_idom(curr_bl);
371 start_irn = sched_last(curr_bl);
377 static void fix_usages(ir_node *orig, pset *copies, pset *copy_blocks)
381 const ir_edge_t *edge;
382 firm_dbg_module_t *dbg = DBG_MODULE;
389 /* Count the number of outs. */
390 foreach_out_edge(orig, edge)
394 * Put all outs into an array.
395 * This is neccessary, since the outs would be modified while
396 * interating on them what could bring the outs module in trouble.
398 outs = malloc(n_outs * sizeof(outs[0]));
399 foreach_out_edge(orig, edge) {
400 outs[i].irn = get_edge_src_irn(edge);
401 outs[i].pos = get_edge_src_pos(edge);
406 * Search the valid def for each out and set it.
408 for(i = 0; i < n_outs; ++i) {
410 ir_node *irn = outs[i].irn;
411 int pos = outs[i].pos;
413 def = search_def(irn, pos, copies, copy_blocks);
414 DBG((dbg, LEVEL_2, "\t%+F(%d) -> %+F\n", irn, pos, def));
417 set_irn_n(irn, pos, def);
424 * Remove phis which are not neccesary.
425 * During place_phi_functions() phi functions are put on the dominance
426 * frontiers blindly. However some of them will never be used (these
427 * have at least one predecessor which is NULL, see search_def() for
428 * this case). Since place_phi_functions() enters them into the
429 * schedule, we have to remove them from there.
431 * @param copies The set of all copies made (including the phi functions).
433 static void remove_odd_phis(pset *copies)
437 for(irn = pset_first(copies); irn; irn = pset_next(copies)) {
442 assert(sched_is_scheduled(irn) && "phi must be scheduled");
443 for(i = 0, n = get_irn_arity(irn); i < n && !illegal; ++i)
444 illegal = is_Bad(get_irn_n(irn, i));
452 void be_introduce_copies(dom_front_info_t *info, ir_node *orig, int n, ir_node *copy_nodes[])
454 pset *copies = pset_new_ptr(2 * n);
455 pset *copy_blocks = pset_new_ptr(2 * n);
456 int save_optimize = get_optimize();
457 int save_normalize = get_opt_normalize();
458 firm_dbg_module_t *dbg = DBG_MODULE;
461 firm_dbg_set_mask(dbg, -1);
462 DBG((dbg, LEVEL_1, "Introducing following copies of %+F\n", orig));
465 pset_insert_ptr(copies, orig);
466 pset_insert_ptr(copy_blocks, get_nodes_block(orig));
469 * All phis using the original value are also copies of it
470 * and must be present in the copies set.
472 for(i = 0; i < n; ++i) {
474 " %+F in block %+F\n", copy_nodes[i], get_nodes_block(copy_nodes[i])));
475 pset_insert_ptr(copies, copy_nodes[i]);
476 pset_insert_ptr(copy_blocks, get_nodes_block(copy_nodes[i]));
480 * Disable optimization so that the phi functions do not
484 set_opt_normalize(0);
487 * Place the phi functions and reroute the usages.
489 place_phi_functions(orig, copies, copy_blocks, info);
490 fix_usages(orig, copies, copy_blocks);
491 remove_odd_phis(copies);
493 /* reset the optimizations */
494 set_optimize(save_optimize);
495 set_opt_normalize(save_normalize);
498 del_pset(copy_blocks);