20 #include "iredges_t.h"
25 #include "besched_t.h"
31 #define DBG_MODULE firm_dbg_register("firm.be.irgmod")
32 #define DBG_LEVEL 0 //SET_LEVEL_4
34 struct _dom_front_info_t {
39 * A wrapper for get_Block_idom.
40 * This function returns the block itself, if the block is the start
41 * block. Returning NULL would make any != comparison true which
42 * suggests, that the start block is dominated by some other node.
43 * @param bl The block.
44 * @return The immediate dominator of the block.
46 static INLINE ir_node *get_idom(ir_node *bl)
48 ir_node *idom = get_Block_idom(bl);
49 return idom == NULL ? bl : idom;
52 static void compute_df_local(ir_node *bl, void *data)
54 pmap *df_map = ((dom_front_info_t *) data)->df_map;
55 ir_node *idom = get_Block_idom(bl);
56 pset *df = pmap_get(df_map, bl);
60 * In the case that the immediate dominator is NULL, the
61 * block is the start block and its immediate dominator
62 * must be itself, else it is inserted into its own
69 * Create a new dom frot set for this node,
73 pmap_insert(df_map, bl, pset_new_ptr(16));
75 for(i = 0, n = get_irn_arity(bl); i < n; ++i) {
77 /* The predecessor block */
78 ir_node *pred = get_nodes_block(get_irn_n(bl, i));
80 /* The dominance frontier set of the predecessor. */
81 pset *df = pmap_get(df_map, pred);
83 df = pset_new_ptr(16);
84 pmap_insert(df_map, pred, df);
87 assert(df && "dom front set must have been created for this node");
89 if(pred != idom && bl)
90 pset_insert_ptr(df, bl);
94 static void compute_df_up(ir_node *bl, void *data)
96 pmap *df_map = ((dom_front_info_t *) data)->df_map;
99 for(y = get_Block_dominated_first(bl); y; y = get_Block_dominated_next(y)) {
101 pset *df = pmap_get(df_map, y);
103 for(w = pset_first(df); w; w = pset_next(df))
104 if(!block_dominates(bl, w) || bl == w)
105 pset_insert_ptr(df, w);
109 static void compute_df(ir_node *n, pmap *df_map)
112 const ir_edge_t *edge;
113 pset *df = pset_new_ptr_default();
115 /* Add local dominance frontiers */
116 foreach_block_succ(n, edge) {
117 ir_node *y = edge->src;
120 pset_insert_ptr(df, y);
124 * Go recursively down the dominance tree and add all blocks
125 * int the dominance frontiers of the children, which are not
126 * dominated by the given block.
128 for(c = get_Block_dominated_first(n); c; c = get_Block_dominated_next(c)) {
132 compute_df(c, df_map);
133 df_c = pmap_get(df_map, c);
135 for(w = pset_first(df_c); w; w = pset_next(df_c)) {
136 if(!block_dominates(n, w))
137 pset_insert_ptr(df, w);
141 pmap_insert(df_map, n, df);
145 dom_front_info_t *be_compute_dominance_frontiers(ir_graph *irg)
147 dom_front_info_t *info = malloc(sizeof(*info));
150 info->df_map = pmap_create();
151 compute_df(get_irg_start_block(irg), info->df_map);
155 * This must be called as a post walker, since the dom front sets
156 * of all predecessors must be created when a block is reached.
158 dom_tree_walk_irg(irg, NULL, compute_df_local, info);
159 dom_tree_walk_irg(irg, NULL, compute_df_up, info);
164 void be_free_dominance_frontiers(dom_front_info_t *info)
168 for(ent = pmap_first(info->df_map); ent; ent = pmap_next(info->df_map))
169 del_pset(ent->value);
171 pmap_destroy(info->df_map);
175 pset *be_get_dominance_frontier(dom_front_info_t *info, ir_node *block)
177 return pmap_get(info->df_map, block);
181 * Algorithm to place the Phi-Functions.
182 * @see Appel, Modern Compiler Implementation in Java, 2nd ed., p. 399ff
184 * This function takes an original node and a set of already placed
185 * copies of that node called @p copies. It places phi nodes at the
186 * iterated dominance frontiers of these copies and puts these phi nodes
187 * in the @p copies set, since they are another form of copies of the
190 * The rename phase (see below) is responsible for fixing up the usages
191 * of the original node.
193 * @param orig The original node.
194 * @param copies A set contianing nodes representing a copy of the
195 * original node. Each node must be inserted into the block's schedule.
196 * @param copy_blocks A set in which the blocks are recorded which
197 * contain a copy. This is just for efficiency in later phases (see
200 static void place_phi_functions(ir_node *orig, pset *copies,
201 pset *copy_blocks, dom_front_info_t *df_info)
204 ir_node *orig_block = get_nodes_block(orig);
205 ir_graph *irg = get_irn_irg(orig);
206 ir_mode *mode = get_irn_mode(orig);
207 pdeq *worklist = new_pdeq();
208 pset *phi_blocks = pset_new_ptr(8);
209 ir_node **ins = NULL;
211 firm_dbg_module_t *dbg = DBG_MODULE;
214 * Allocate an array for all blocks where the copies and the original
215 * value were defined.
217 int n_orig_blocks = pset_count(copy_blocks);
218 ir_node **orig_blocks = malloc(n_orig_blocks * sizeof(orig_blocks[0]));
221 * Fill the worklist queue and the rest of the orig blocks array.
223 for(it = pset_first(copy_blocks), i = 0; it; it = pset_next(copy_blocks)) {
224 ir_node *copy_block = it;
226 assert(block_dominates(orig_block, copy_block)
227 && "The block of the copy must be dominated by the block of the value");
229 pdeq_putr(worklist, copy_block);
230 orig_blocks[i++] = copy_block;
233 while(!pdeq_empty(worklist)) {
234 ir_node *bl = pdeq_getl(worklist);
236 pset *df = be_get_dominance_frontier(df_info, bl);
238 DBG((dbg, LEVEL_3, "dom front of %+F\n", bl));
239 for(y = pset_first(df); y; y = pset_next(df))
240 DBG((dbg, LEVEL_3, "\t%+F\n", y));
242 for(y = pset_first(df); y; y = pset_next(df)) {
243 int n_preds = get_irn_arity(y);
245 if(!pset_find_ptr(phi_blocks, y)) {
250 * Set the orig node as the only operand of the
253 ins = realloc(ins, n_preds * sizeof(ins[0]));
254 for(i = 0; i < n_preds; ++i)
257 /* Insert phi node */
258 phi = new_r_Phi(irg, y, n_preds, ins, mode);
259 DBG((dbg, LEVEL_2, " inserting phi %+F with %d args in block %+F\n",
263 * The phi node itself is also a copy of the original
264 * value. So put it in the copies set also, so that
265 * the rename phase can treat them right.
267 pset_insert_ptr(copies, phi);
268 pset_insert_ptr(copy_blocks, y);
271 * Insert the phi node into the schedule if it
272 * can occur there (PhiM's are not to put into a schedule.
274 if(to_appear_in_schedule(phi))
275 sched_add_before(sched_first(y), phi);
277 /* Insert the phi node in the phi blocks set. */
278 pset_insert_ptr(phi_blocks, y);
281 * If orig or a copy of it were not defined in y,
282 * add y to the worklist.
284 for(i = 0; i < n_orig_blocks; ++i)
285 if(orig_blocks[i] == y) {
291 pdeq_putr(worklist, y);
297 del_pset(phi_blocks);
307 * Find the copy of the given original node whose value is 'active'
310 * The usage is given as a node and a position. Initially, the given operand
311 * points to a node for which copies were introduced. We have to find
312 * the valid copy for this usage. This is done by travering the
313 * dominance tree upwards. If the usage is a phi function, we start
314 * traversing from the predecessor block which corresponds to the phi
317 * @param usage The node which uses the original node.
318 * @param pos The number of the argument which corresponds to the
320 * @param copy_blocks A set containing all basic block in which copies
321 * of the original node are located.
322 * @param copies A set containing all node which are copies from the
324 * @return The valid copy for usage.
326 static ir_node *search_def(ir_node *usage, int pos, pset *copies, pset *copy_blocks)
330 firm_dbg_module_t *dbg = DBG_MODULE;
331 firm_dbg_set_mask(dbg, DBG_LEVEL);
333 curr_bl = get_nodes_block(usage);
336 DBG((dbg, LEVEL_1, "Searching valid def for use %+F at pos %d\n", usage, pos));
338 * If the usage is in a phi node, search the copy in the
339 * predecessor denoted by pos.
342 curr_bl = get_Block_cfgpred_block(curr_bl, pos);
343 start_irn = sched_last(curr_bl);
345 start_irn = sched_prev(usage);
349 * Traverse the dominance tree upwards from the
350 * predecessor block of the usage.
352 while(curr_bl != NULL) {
355 * If this block contains a copy, search the block
356 * instruction by instruction.
358 if(pset_find_ptr(copy_blocks, curr_bl)) {
361 /* Look at each instruction from last to first. */
362 for(irn = start_irn; !is_Block(irn); irn = sched_prev(irn)) {
364 /* Take the first copy we find. */
365 if(pset_find_ptr(copies, irn))
370 /* If were not done yet, look in the immediate dominator */
371 curr_bl = get_Block_idom(curr_bl);
373 start_irn = sched_last(curr_bl);
379 static void fix_usages(ir_node *orig, pset *copies, pset *copy_blocks)
383 const ir_edge_t *edge;
384 firm_dbg_module_t *dbg = DBG_MODULE;
391 /* Count the number of outs. */
392 foreach_out_edge(orig, edge)
396 * Put all outs into an array.
397 * This is neccessary, since the outs would be modified while
398 * interating on them what could bring the outs module in trouble.
400 outs = malloc(n_outs * sizeof(outs[0]));
401 foreach_out_edge(orig, edge) {
402 outs[i].irn = get_edge_src_irn(edge);
403 outs[i].pos = get_edge_src_pos(edge);
408 * Search the valid def for each out and set it.
410 for(i = 0; i < n_outs; ++i) {
412 ir_node *irn = outs[i].irn;
413 int pos = outs[i].pos;
415 def = search_def(irn, pos, copies, copy_blocks);
416 DBG((dbg, LEVEL_2, "\t%+F(%d) -> %+F\n", irn, pos, def));
419 set_irn_n(irn, pos, def);
426 * Remove phis which are not neccesary.
427 * During place_phi_functions() phi functions are put on the dominance
428 * frontiers blindly. However some of them will never be used (these
429 * have at least one predecessor which is NULL, see search_def() for
430 * this case). Since place_phi_functions() enters them into the
431 * schedule, we have to remove them from there.
433 * @param copies The set of all copies made (including the phi functions).
435 static void remove_odd_phis(pset *copies)
439 for(irn = pset_first(copies); irn; irn = pset_next(copies)) {
444 assert(sched_is_scheduled(irn) && "phi must be scheduled");
445 for(i = 0, n = get_irn_arity(irn); i < n && !illegal; ++i)
446 illegal = is_Bad(get_irn_n(irn, i));
454 void be_introduce_copies(dom_front_info_t *info, ir_node *orig, int n, ir_node *copy_nodes[])
456 pset *copies = pset_new_ptr(2 * n);
457 pset *copy_blocks = pset_new_ptr(2 * n);
458 int save_optimize = get_optimize();
459 int save_normalize = get_opt_normalize();
460 firm_dbg_module_t *dbg = DBG_MODULE;
463 firm_dbg_set_mask(dbg, DBG_LEVEL);
464 DBG((dbg, LEVEL_1, "Introducing following copies of %+F\n", orig));
467 pset_insert_ptr(copies, orig);
468 pset_insert_ptr(copy_blocks, get_nodes_block(orig));
471 * All phis using the original value are also copies of it
472 * and must be present in the copies set.
474 for(i = 0; i < n; ++i) {
476 " %+F in block %+F\n", copy_nodes[i], get_nodes_block(copy_nodes[i])));
477 pset_insert_ptr(copies, copy_nodes[i]);
478 pset_insert_ptr(copy_blocks, get_nodes_block(copy_nodes[i]));
482 * Disable optimization so that the phi functions do not
486 set_opt_normalize(0);
489 * Place the phi functions and reroute the usages.
491 place_phi_functions(orig, copies, copy_blocks, info);
492 fix_usages(orig, copies, copy_blocks);
493 remove_odd_phis(copies);
495 /* reset the optimizations */
496 set_optimize(save_optimize);
497 set_opt_normalize(save_normalize);
500 del_pset(copy_blocks);