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 {
36 static void compute_df_local(ir_node *bl, void *data)
38 pmap *df_map = ((dom_front_info_t *) data)->df_map;
39 ir_node *idom = get_Block_idom(bl);
40 pset *df = pmap_get(df_map, bl);
44 * In the case that the immediate dominator is NULL, the
45 * block is the start block and its immediate dominator
46 * must be itself, else it is inserted into its own
53 * Create a new dom frot set for this node,
57 pmap_insert(df_map, bl, pset_new_ptr(16));
59 for(i = 0, n = get_irn_arity(bl); i < n; ++i) {
61 /* The predecessor block */
62 ir_node *pred = get_nodes_block(get_irn_n(bl, i));
64 /* The dominance frontier set of the predecessor. */
65 pset *df = pmap_get(df_map, pred);
67 df = pset_new_ptr(16);
68 pmap_insert(df_map, pred, df);
71 assert(df && "dom front set must have been created for this node");
73 if(pred != idom && bl)
74 pset_insert_ptr(df, bl);
78 static void compute_df_up(ir_node *bl, void *data)
80 pmap *df_map = ((dom_front_info_t *) data)->df_map;
83 for(y = get_Block_dominated_first(bl); y; y = get_Block_dominated_next(y)) {
85 pset *df = pmap_get(df_map, y);
87 for(w = pset_first(df); w; w = pset_next(df))
88 if(!block_dominates(bl, w) || bl == w)
89 pset_insert_ptr(df, w);
93 dom_front_info_t *be_compute_dominance_frontiers(ir_graph *irg)
95 dom_front_info_t *info = malloc(sizeof(*info));
97 info->df_map = pmap_create();
100 * This must be called as a post walker, since the dom front sets
101 * of all predecessors must be created when a block is reached.
103 dom_tree_walk_irg(irg, NULL, compute_df_local, info);
104 dom_tree_walk_irg(irg, NULL, compute_df_up, info);
108 void be_free_dominance_frontiers(dom_front_info_t *info)
112 for(ent = pmap_first(info->df_map); ent; ent = pmap_next(info->df_map))
113 del_pset(ent->value);
115 pmap_destroy(info->df_map);
119 pset *be_get_dominance_frontier(dom_front_info_t *info, ir_node *block)
121 return pmap_get(info->df_map, block);
125 * Algorithm to place the Phi-Functions.
126 * @see Appel, Modern Compiler Implementation in Java, 2nd ed., p. 399ff
128 * This function takes an original node and a set of already placed
129 * copies of that node called @p copies. It places phi nodes at the
130 * iterated dominance frontiers of these copies and puts these phi nodes
131 * in the @p copies set, since they are another form of copies of the
134 * The rename phase (see below) is responsible for fixing up the usages
135 * of the original node.
137 * @param orig The original node.
138 * @param copies A set contianing nodes representing a copy of the
139 * original node. Each node must be inserted into the block's schedule.
140 * @param copy_blocks A set in which the blocks are recorded which
141 * contain a copy. This is just for efficiency in later phases (see
144 static void place_phi_functions(ir_node *orig, pset *copies,
145 pset *copy_blocks, dom_front_info_t *df_info)
148 ir_node *orig_block = get_nodes_block(orig);
149 ir_graph *irg = get_irn_irg(orig);
150 ir_mode *mode = get_irn_mode(orig);
151 pdeq *worklist = new_pdeq();
152 pset *phi_blocks = pset_new_ptr(8);
153 ir_node **ins = NULL;
155 firm_dbg_module_t *dbg = DBG_MODULE;
158 * Allocate an array for all blocks where the copies and the original
159 * value were defined.
161 int n_orig_blocks = pset_count(copy_blocks);
162 ir_node **orig_blocks = malloc(n_orig_blocks * sizeof(orig_blocks[0]));
165 * Fill the worklist queue and the rest of the orig blocks array.
167 for(it = pset_first(copies), i = 0; it; it = pset_next(copies)) {
168 ir_node *copy_block = get_nodes_block(it);
171 * Not true anymore, since phis can be copies of a value.
172 * Not all Phis are dominated by their args
174 if(!block_dominates(orig_block, copy_block)) {
175 assert(block_dominates(orig_block, copy_block)
176 && "The block of the copy must be dominated by the block of the value");
180 pdeq_putr(worklist, copy_block);
181 orig_blocks[i++] = copy_block;
184 while(!pdeq_empty(worklist)) {
185 ir_node *bl = pdeq_getl(worklist);
187 pset *df = be_get_dominance_frontier(df_info, bl);
189 DBG((dbg, LEVEL_3, "dom front of %+F\n", bl));
190 for(y = pset_first(df); y; y = pset_next(df))
191 DBG((dbg, LEVEL_3, "\t%+F\n", y));
193 for(y = pset_first(df); y; y = pset_next(df)) {
194 int n_preds = get_irn_arity(y);
196 if(!pset_find_ptr(phi_blocks, y)) {
201 * Set the orig node as the only operand of the
204 ins = realloc(ins, n_preds * sizeof(ins[0]));
205 for(i = 0; i < n_preds; ++i)
208 /* Insert phi node */
209 phi = new_r_Phi(irg, y, n_preds, ins, mode);
210 DBG((dbg, LEVEL_2, " inserting phi %+F with %d args in block %+F\n",
214 * The phi node itself is also a copy of the original
215 * value. So put it in the copies set also, so that
216 * the rename phase can treat them right.
218 pset_insert_ptr(copies, phi);
219 pset_insert_ptr(copy_blocks, y);
222 * Insert the phi node into the schedule if it
223 * can occur there (PhiM's are not to put into a schedule.
225 if(to_appear_in_schedule(phi))
226 sched_add_before(sched_first(y), phi);
228 /* Insert the phi node in the phi blocks set. */
229 pset_insert_ptr(phi_blocks, y);
232 * If orig or a copy of it were not defined in y,
233 * add y to the worklist.
235 for(i = 0; i < n_orig_blocks; ++i)
236 if(orig_blocks[i] == y) {
242 pdeq_putr(worklist, y);
248 del_pset(phi_blocks);
258 * Find the copy of the given original node whose value is 'active'
261 * The usage is given as a node and a position. Initially, the given operand
262 * points to a node for which copies were introduced. We have to find
263 * the valid copy for this usage. This is done by travering the
264 * dominance tree upwards. If the usage is a phi function, we start
265 * traversing from the predecessor block which corresponds to the phi
268 * @param usage The node which uses the original node.
269 * @param pos The number of the argument which corresponds to the
271 * @param copy_blocks A set containing all basic block in which copies
272 * of the original node are located.
273 * @param copies A set containing all node which are copies from the
275 * @return The valid copy for usage.
277 static ir_node *search_def(ir_node *usage, int pos, pset *copies, pset *copy_blocks)
281 firm_dbg_module_t *dbg = DBG_MODULE;
282 firm_dbg_set_mask(dbg, -1);
284 curr_bl = get_nodes_block(usage);
287 DBG((dbg, LEVEL_1, "Searching valid def for use %+F at pos %d\n", usage, pos));
289 * If the usage is in a phi node, search the copy in the
290 * predecessor denoted by pos.
293 curr_bl = get_Block_cfgpred_block(curr_bl, pos);
294 start_irn = sched_last(curr_bl);
296 start_irn = sched_prev(usage);
300 * Traverse the dominance tree upwards from the
301 * predecessor block of the usage.
303 while(curr_bl != NULL) {
306 * If this block contains a copy, search the block
307 * instruction by instruction.
309 if(pset_find_ptr(copy_blocks, curr_bl)) {
312 /* Look at each instruction from last to first. */
313 for(irn = start_irn; !is_Block(irn); irn = sched_prev(irn)) {
315 /* Take the first copy we find. */
317 DBG((dbg, LEVEL_1, "Is %F a copy?\n", irn));
318 if(pset_find_ptr(copies, irn))
323 /* If were not done yet, look in the immediate dominator */
324 curr_bl = get_Block_idom(curr_bl);
326 start_irn = sched_last(curr_bl);
329 assert(0 && "Did not find a valid def");
333 static void fix_usages(ir_node *orig, pset *copies, pset *copy_blocks)
337 const ir_edge_t *edge;
338 firm_dbg_module_t *dbg = DBG_MODULE;
345 /* Count the number of outs. */
346 foreach_out_edge(orig, edge)
350 * Put all outs into an array.
351 * This is neccessary, since the outs would be modified while
352 * interating on them what could bring the outs module in trouble.
354 DBG((dbg, LEVEL_2, " Users of %+F\n", orig));
355 outs = malloc(n_outs * sizeof(outs[0]));
356 foreach_out_edge(orig, edge) {
357 outs[i].irn = get_edge_src_irn(edge);
358 outs[i].pos = get_edge_src_pos(edge);
363 * Search the valid def for each out and set it.
365 for(i = 0; i < n_outs; ++i) {
367 ir_node *irn = outs[i].irn;
368 int pos = outs[i].pos;
370 DBG((dbg, LEVEL_2, " %+F(%d) -> ???\n", irn, pos));
371 def = search_def(irn, pos, copies, copy_blocks);
372 DBG((dbg, LEVEL_2, " %+F(%d) -> %+F\n", irn, pos, def));
375 set_irn_n(irn, pos, def);
381 struct phi_collect_info {
387 static void add_all_phis_walker(ir_node *irn, void *data)
391 struct phi_collect_info *info = data;
394 * Look at all operands of the phi. If one of them is the original
395 * node, insert the phi into the copies and copy_blocks set.
397 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
398 if(get_irn_n(irn, i) == info->orig) {
399 pset_insert_ptr(info->copies, irn);
400 pset_insert_ptr(info->copy_blocks, get_nodes_block(irn));
403 * If a phi is a copy insert all its args as copies too.
404 * Else setting the phi-args will fail in serach_def */
406 const ir_node *arg = get_irn_n(irn, o);
407 pset_insert_ptr(info->copies, arg);
408 pset_insert_ptr(info->copy_blocks, get_nodes_block(arg));
420 * Add all phis using a node to a set.
421 * @param orig The node the phis shall use.
422 * @param copies The set where the phis shall be put into.
423 * @param copy_blocks The set the blocks of the phis shall be put into.
425 static void add_all_phis_using(const ir_node *orig, pset *copies, pset *copy_blocks)
427 struct phi_collect_info info;
429 info.copies = copies;
430 info.copy_blocks = copy_blocks;
432 irg_walk_graph(get_irn_irg(orig), add_all_phis_walker, NULL, &info);
435 void be_introduce_copies(dom_front_info_t *info, ir_node *orig, int n, ir_node *copy_nodes[])
437 pset *copies = pset_new_ptr(2 * n);
438 pset *copy_blocks = pset_new_ptr(2 * n);
439 int save_optimize = get_optimize();
440 int save_normalize = get_opt_normalize();
441 firm_dbg_module_t *dbg = DBG_MODULE;
444 firm_dbg_set_mask(dbg, -1);
445 DBG((dbg, LEVEL_1, "Introducing following copies of %+F\n", orig));
448 pset_insert_ptr(copies, orig);
449 pset_insert_ptr(copy_blocks, get_nodes_block(orig));
452 * All phis using the original value are also copies of it
453 * and must be present in the copies set.
455 add_all_phis_using(orig, copies, copy_blocks);
457 for(i = 0; i < n; ++i) {
459 " %+F in block %+F\n", copy_nodes[i], get_nodes_block(copy_nodes[i])));
460 pset_insert_ptr(copies, copy_nodes[i]);
461 pset_insert_ptr(copy_blocks, get_nodes_block(copy_nodes[i]));
465 * Disable optimization so that the phi functions do not
469 set_opt_normalize(0);
472 * Place the phi functions and reroute the usages.
474 place_phi_functions(orig, copies, copy_blocks, info);
475 fix_usages(orig, copies, copy_blocks);
477 /* reset the optimizations */
478 set_optimize(save_optimize);
479 set_opt_normalize(save_normalize);
482 del_pset(copy_blocks);