19 #include "iredges_t.h"
24 #include "besched_t.h"
30 #define DBG_MODULE firm_dbg_register("firm.be.irgmod")
33 struct _dom_front_info_t {
38 * A wrapper for get_Block_idom.
39 * This function returns the block itself, if the block is the start
40 * block. Returning NULL would make any != comparison true which
41 * suggests, that the start block is dominated by some other node.
42 * @param bl The block.
43 * @return The immediate dominator of the block.
45 static INLINE ir_node *get_idom(ir_node *bl)
47 ir_node *idom = get_Block_idom(bl);
48 return idom == NULL ? bl : idom;
51 static void compute_df_local(ir_node *bl, void *data)
53 pmap *df_map = ((dom_front_info_t *) data)->df_map;
54 ir_node *idom = get_Block_idom(bl);
55 pset *df = pmap_get(df_map, bl);
59 * In the case that the immediate dominator is NULL, the
60 * block is the start block and its immediate dominator
61 * must be itself, else it is inserted into its own
68 * Create a new dom frot set for this node,
72 pmap_insert(df_map, bl, pset_new_ptr(16));
74 for(i = 0, n = get_irn_arity(bl); i < n; ++i) {
76 /* The predecessor block */
77 ir_node *pred = get_nodes_block(get_irn_n(bl, i));
79 /* The dominance frontier set of the predecessor. */
80 pset *df = pmap_get(df_map, pred);
82 df = pset_new_ptr(16);
83 pmap_insert(df_map, pred, df);
86 assert(df && "dom front set must have been created for this node");
88 if(pred != idom && bl)
89 pset_insert_ptr(df, bl);
93 static void compute_df_up(ir_node *bl, void *data)
95 pmap *df_map = ((dom_front_info_t *) data)->df_map;
98 for(y = get_Block_dominated_first(bl); y; y = get_Block_dominated_next(y)) {
100 pset *df = pmap_get(df_map, y);
102 for(w = pset_first(df); w; w = pset_next(df))
103 if(!block_dominates(bl, w) || bl == w)
104 pset_insert_ptr(df, w);
108 static void compute_df(ir_node *n, pmap *df_map)
111 const ir_edge_t *edge;
112 pset *df = pset_new_ptr_default();
114 /* Add local dominance frontiers */
115 foreach_block_succ(n, edge) {
116 ir_node *y = edge->src;
119 pset_insert_ptr(df, y);
123 * Go recursively down the dominance tree and add all blocks
124 * int the dominance frontiers of the children, which are not
125 * dominated by the given block.
127 for(c = get_Block_dominated_first(n); c; c = get_Block_dominated_next(c)) {
131 compute_df(c, df_map);
132 df_c = pmap_get(df_map, c);
134 for(w = pset_first(df_c); w; w = pset_next(df_c)) {
135 if(!block_dominates(n, w))
136 pset_insert_ptr(df, w);
140 pmap_insert(df_map, n, df);
144 dom_front_info_t *be_compute_dominance_frontiers(ir_graph *irg)
146 dom_front_info_t *info = malloc(sizeof(*info));
149 info->df_map = pmap_create();
150 compute_df(get_irg_start_block(irg), info->df_map);
154 * This must be called as a post walker, since the dom front sets
155 * of all predecessors must be created when a block is reached.
157 dom_tree_walk_irg(irg, NULL, compute_df_local, info);
158 dom_tree_walk_irg(irg, NULL, compute_df_up, info);
163 void be_free_dominance_frontiers(dom_front_info_t *info)
167 for(ent = pmap_first(info->df_map); ent; ent = pmap_next(info->df_map))
168 del_pset(ent->value);
170 pmap_destroy(info->df_map);
174 pset *be_get_dominance_frontier(dom_front_info_t *info, ir_node *block)
176 return pmap_get(info->df_map, block);
180 * Algorithm to place the Phi-Functions.
181 * @see Appel, Modern Compiler Implementation in Java, 2nd ed., p. 399ff
183 * This function takes an original node and a set of already placed
184 * copies of that node called @p copies. It places phi nodes at the
185 * iterated dominance frontiers of these copies and puts these phi nodes
186 * in the @p copies set, since they are another form of copies of the
189 * The rename phase (see below) is responsible for fixing up the usages
190 * of the original node.
192 * @param orig The original node.
193 * @param copies A set contianing nodes representing a copy of the
194 * original node. Each node must be inserted into the block's schedule.
195 * @param copy_blocks A set in which the blocks are recorded which
196 * contain a copy. This is just for efficiency in later phases (see
199 static void place_phi_functions(ir_node *orig, pset *copies,
200 pset *copy_blocks, dom_front_info_t *df_info)
203 ir_node *orig_block = get_nodes_block(orig);
204 ir_graph *irg = get_irn_irg(orig);
205 ir_mode *mode = get_irn_mode(orig);
206 pdeq *worklist = new_pdeq();
207 pset *phi_blocks = pset_new_ptr(8);
208 ir_node **ins = NULL;
210 firm_dbg_module_t *dbg = DBG_MODULE;
213 * Allocate an array for all blocks where the copies and the original
214 * value were defined.
216 int n_orig_blocks = pset_count(copy_blocks);
217 ir_node **orig_blocks = malloc(n_orig_blocks * sizeof(orig_blocks[0]));
220 * Fill the worklist queue and the rest of the orig blocks array.
222 for(it = pset_first(copy_blocks), i = 0; it; it = pset_next(copy_blocks)) {
223 ir_node *copy_block = it;
225 assert(block_dominates(orig_block, copy_block)
226 && "The block of the copy must be dominated by the block of the value");
228 pdeq_putr(worklist, copy_block);
229 orig_blocks[i++] = copy_block;
232 while(!pdeq_empty(worklist)) {
233 ir_node *bl = pdeq_getl(worklist);
235 pset *df = be_get_dominance_frontier(df_info, bl);
237 DBG((dbg, LEVEL_3, "dom front of %+F\n", bl));
238 for(y = pset_first(df); y; y = pset_next(df))
239 DBG((dbg, LEVEL_3, "\t%+F\n", y));
241 for(y = pset_first(df); y; y = pset_next(df)) {
242 int n_preds = get_irn_arity(y);
244 if(!pset_find_ptr(phi_blocks, y)) {
249 * Set the orig node as the only operand of the
252 ins = realloc(ins, n_preds * sizeof(ins[0]));
253 for(i = 0; i < n_preds; ++i)
256 /* Insert phi node */
257 phi = new_r_Phi(irg, y, n_preds, ins, mode);
258 DBG((dbg, LEVEL_2, " inserting phi %+F with %d args in block %+F\n",
262 * The phi node itself is also a copy of the original
263 * value. So put it in the copies set also, so that
264 * the rename phase can treat them right.
266 pset_insert_ptr(copies, phi);
267 pset_insert_ptr(copy_blocks, y);
270 * Insert the phi node into the schedule if it
271 * can occur there (PhiM's are not to put into a schedule.
273 if(to_appear_in_schedule(phi))
274 sched_add_before(sched_first(y), phi);
276 /* Insert the phi node in the phi blocks set. */
277 pset_insert_ptr(phi_blocks, y);
280 * If orig or a copy of it were not defined in y,
281 * add y to the worklist.
283 for(i = 0; i < n_orig_blocks; ++i)
284 if(orig_blocks[i] == y) {
290 pdeq_putr(worklist, y);
296 del_pset(phi_blocks);
306 * Find the copy of the given original node whose value is 'active'
309 * The usage is given as a node and a position. Initially, the given operand
310 * points to a node for which copies were introduced. We have to find
311 * the valid copy for this usage. This is done by travering the
312 * dominance tree upwards. If the usage is a phi function, we start
313 * traversing from the predecessor block which corresponds to the phi
316 * @param usage The node which uses the original node.
317 * @param pos The number of the argument which corresponds to the
319 * @param copy_blocks A set containing all basic block in which copies
320 * of the original node are located.
321 * @param copies A set containing all node which are copies from the
323 * @return The valid copy for usage.
325 static ir_node *search_def(ir_node *usage, int pos, pset *copies, pset *copy_blocks)
329 firm_dbg_module_t *dbg = DBG_MODULE;
330 firm_dbg_set_mask(dbg, DBG_LEVEL);
332 curr_bl = get_nodes_block(usage);
335 DBG((dbg, LEVEL_1, "Searching valid def for use %+F at pos %d\n", usage, pos));
337 * If the usage is in a phi node, search the copy in the
338 * predecessor denoted by pos.
341 curr_bl = get_Block_cfgpred_block(curr_bl, pos);
342 start_irn = sched_last(curr_bl);
344 start_irn = sched_prev(usage);
348 * Traverse the dominance tree upwards from the
349 * predecessor block of the usage.
351 while(curr_bl != NULL) {
354 * If this block contains a copy, search the block
355 * instruction by instruction.
357 if(pset_find_ptr(copy_blocks, curr_bl)) {
360 /* Look at each instruction from last to first. */
361 for(irn = start_irn; !is_Block(irn); irn = sched_prev(irn)) {
363 /* Take the first copy we find. */
364 if(pset_find_ptr(copies, irn))
369 /* If were not done yet, look in the immediate dominator */
370 curr_bl = get_Block_idom(curr_bl);
372 start_irn = sched_last(curr_bl);
378 static void fix_usages(ir_node *orig, pset *copies, pset *copy_blocks)
382 const ir_edge_t *edge;
383 firm_dbg_module_t *dbg = DBG_MODULE;
390 /* Count the number of outs. */
391 foreach_out_edge(orig, edge)
395 * Put all outs into an array.
396 * This is neccessary, since the outs would be modified while
397 * interating on them what could bring the outs module in trouble.
399 outs = malloc(n_outs * sizeof(outs[0]));
400 foreach_out_edge(orig, edge) {
401 outs[i].irn = get_edge_src_irn(edge);
402 outs[i].pos = get_edge_src_pos(edge);
407 * Search the valid def for each out and set it.
409 for(i = 0; i < n_outs; ++i) {
411 ir_node *irn = outs[i].irn;
412 int pos = outs[i].pos;
414 def = search_def(irn, pos, copies, copy_blocks);
415 DBG((dbg, LEVEL_2, "\t%+F(%d) -> %+F\n", irn, pos, def));
418 set_irn_n(irn, pos, def);
425 * Remove phis which are not neccesary.
426 * During place_phi_functions() phi functions are put on the dominance
427 * frontiers blindly. However some of them will never be used (these
428 * have at least one predecessor which is NULL, see search_def() for
429 * this case). Since place_phi_functions() enters them into the
430 * schedule, we have to remove them from there.
432 * @param copies The set of all copies made (including the phi functions).
434 static void remove_odd_phis(pset *copies)
438 for(irn = pset_first(copies); irn; irn = pset_next(copies)) {
443 assert(sched_is_scheduled(irn) && "phi must be scheduled");
444 for(i = 0, n = get_irn_arity(irn); i < n && !illegal; ++i)
445 illegal = is_Bad(get_irn_n(irn, i));
453 void be_introduce_copies(dom_front_info_t *info, ir_node *orig, int n, ir_node *copy_nodes[])
455 pset *copies = pset_new_ptr(2 * n);
456 pset *copy_blocks = pset_new_ptr(2 * n);
457 int save_optimize = get_optimize();
458 int save_normalize = get_opt_normalize();
459 firm_dbg_module_t *dbg = DBG_MODULE;
462 firm_dbg_set_mask(dbg, DBG_LEVEL);
463 DBG((dbg, LEVEL_1, "Introducing following copies of %+F\n", orig));
466 pset_insert_ptr(copies, orig);
467 pset_insert_ptr(copy_blocks, get_nodes_block(orig));
470 * All phis using the original value are also copies of it
471 * and must be present in the copies set.
473 for(i = 0; i < n; ++i) {
475 " %+F in block %+F\n", copy_nodes[i], get_nodes_block(copy_nodes[i])));
476 pset_insert_ptr(copies, copy_nodes[i]);
477 pset_insert_ptr(copy_blocks, get_nodes_block(copy_nodes[i]));
481 * Disable optimization so that the phi functions do not
485 set_opt_normalize(0);
488 * Place the phi functions and reroute the usages.
490 place_phi_functions(orig, copies, copy_blocks, info);
491 fix_usages(orig, copies, copy_blocks);
492 remove_odd_phis(copies);
494 /* reset the optimizations */
495 set_optimize(save_optimize);
496 set_opt_normalize(save_normalize);
499 del_pset(copy_blocks);