-
-
-/**
- * A convenience function for _find_conds.
- * It sets some parameters needed for recursion to appropriate start
- * values. Always use this function.
- *
- * @param irn The node to start looking for Conds from. This might
- * be the phi node we are investigating.
- * @param conds The set to record the found Conds in.
- */
-static INLINE void find_conds(ir_node *irn, cond_info_t *ci)
-{
- int i, n;
- unsigned long visited_nr;
- ir_node *block = get_nodes_block(irn);
- ir_node *dom = get_Block_idom(block);
-
- for(i = 0, n = get_irn_arity(block); i < n; ++i) {
- ir_node *pred = get_irn_n(block, i);
-
- inc_irg_block_visited(current_ir_graph);
- visited_nr = get_irg_block_visited(current_ir_graph);
- set_Block_block_visited(block, visited_nr);
-
- DBG((dbg, LEVEL_2, "find conds at pred %d (%n) and idom %n\n", i, pred, dom));
- _find_conds(pred, visited_nr, dom, NULL, i, 0, ci);
- }
-}
-
-/**
- * Make the mux for a given cond.
- *
- * @param phi The phi node which shall be replaced by a mux.
- * @param dom The block where the muxes shall be placed.
- * @param cond The cond information.
- * @param info The options for createing Mux nodes.
- * @return The mux node made for this cond.
- */
-static ir_node *make_mux_on_demand(ir_node *phi, ir_node *dom, cond_t *cond,
- const opt_if_conv_info_t *info, ir_node **mux, bitset_t *positions,
- int *muxes_made, long visited_nr)
-{
- int i, can_move[2];
- ir_node *projb = get_Cond_selector(cond->cond);
- ir_node *bl = get_nodes_block(cond->cond);
- ir_node *operands[2];
- int set[2];
-
- cond->visited_nr = visited_nr;
- DBG((dbg, LEVEL_2, "%n\n", cond->cond));
- for(i = 0; i < 2; ++i) {
- cond_t *masked_by = cond->cases[i].masked_by;
- int pos = cond->cases[i].pos;
-
- operands[i] = NULL;
- set[i] = -1;
-
- /*
- * If this Cond branch is masked by another cond, make the mux
- * for that Cond first, since the Mux for this cond takes
- * it as an operand.
- */
- if(masked_by) {
- assert(pos < 0);
- DBG((dbg, LEVEL_2, "\tmasked by: %n\n", masked_by->cond));
- if(masked_by->visited_nr < visited_nr)
- operands[i] = make_mux_on_demand(phi, dom, masked_by, info, mux, positions, muxes_made, visited_nr);
- }
-
- /*
- * If this cond branch is not masked by another cond, take
- * the corresponding phi operand as an operand to the mux.
- */
- else if(pos >= 0) {
- operands[i] = get_irn_n(phi, pos);
- set[i] = pos;
- }
- }
-
- /*
- * Move the operands to the dominator block if the cond
- * made sense. Some Conds found are not suitable for making a mux
- * out of them, since one of their branches cannot be reached from
- * the phi block. In that case we do not make a mux and return NULL.
- */
- if(operands[0] && operands[1]) {
- if (operands[0] == operands[1]) {
- /* there is no gain in using mux in this case, as
- it will be optimized away. We will NOT move the
- content of the blocks either
- */
- for (i = 0; i < 2; ++i)
- if(set[i] >= 0)
- bitset_set(positions, set[i]);
-
- *mux = operands[0];
- return *mux;
- }
-
- can_move[0] = can_move_to(operands[0], bl, info);
- can_move[1] = can_move_to(operands[1], bl, info);
-
- if (can_move[0] == SUCCESS && can_move[1] == SUCCESS) {
- if (info->allow_mux(projb, operands[0], operands[1])) {
- move_to(operands[0], bl);
- move_to(operands[1], bl);
-
- /* Make the mux. */
- *mux = new_r_Mux(current_ir_graph, bl, projb,
- operands[0], operands[1], get_irn_mode(operands[0]));
-
- *muxes_made += 1;
-
- DBG((dbg, LEVEL_2, "\t%n(%n, %n, %n)[%d, %d]\n",
- *mux, projb, operands[0], operands[1], set[0], set[1]));
-
- for(i = 0; i < 2; ++i)
- if(set[i] >= 0) {
- bitset_set(positions, set[i]);
-
- /* we have done one */
- hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_SUCCESS);
- }
- }
- else {
- hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_DENIED);
- }
- }
- else {
- if(can_move[0] != SUCCESS)
- hook_if_conversion(current_ir_graph, phi, set[0], NULL, can_move[0]);
- if(can_move[1] != SUCCESS)
- hook_if_conversion(current_ir_graph, phi, set[1], NULL, can_move[1]);
- }
- }
- else {
- if(operands[0])
- hook_if_conversion(current_ir_graph, phi, set[0], NULL, IF_RESULT_BAD_CF);
- if(operands[1])
- hook_if_conversion(current_ir_graph, phi, set[1], NULL, IF_RESULT_BAD_CF);
- }
-
- return *mux;
-}
-
-typedef struct _phi_info_t {
- struct list_head list;
- cond_info_t *cond_info;
- ir_node *irn;
-} phi_info_t;
-
-
-/**
- * Examine a phi node if it can be replaced by some muxes.
- * @param irn A phi node.
- * @param info Parameters for the if conversion algorithm.
- */
-static int check_out_phi(phi_info_t *phi_info, const opt_if_conv_info_t *info)
-{
- ir_node *irn = phi_info->irn;
- ir_node *block, *nw;
- cond_info_t *cond_info = phi_info->cond_info;
- cond_t *cond;
- int i, arity;
- int muxes_made = 0;
- bitset_t *positions;
-
- block = get_nodes_block(irn);
- arity = get_irn_arity(irn);
- positions = bitset_alloca(arity);
-
- assert(is_Phi(irn));
- assert(get_irn_arity(irn) == get_irn_arity(block));
- assert(arity > 0);
-
- DBG((dbg, LEVEL_2, "phi candidate: %n\n", irn));
-
- list_for_each_entry(cond_t, cond, &cond_info->roots, list) {
- ir_node *cidom = block;
- ir_node *mux = NULL;
- cond_t *p, *head = NULL;
- long pos;
-
- bitset_clear_all(positions);
-
- DBG((dbg, LEVEL_2, "\tcond root: %n\n", cond->cond));
- /*
- * Link all conds which are in the subtree of
- * the current cond in the list together.
- */
- walk_conds(cond, link_conds, NULL, &head);
-
- cidom = block;
- for(p = head; p; p = p->link) {
- for(i = 0; i < 2; ++i) {
- int pos = p->cases[i].pos;
- if(pos != -1)
- cidom = common_idom(cidom, get_nodes_block(get_irn_n(block, pos)));
- }
- }
-
- DBG((dbg, LEVEL_2, "\tcommon idom: %n\n", cidom));
- make_mux_on_demand(irn, cidom, cond, info, &mux, positions, &muxes_made, ++cond_visited_nr);
-
- if(mux) {
- bitset_foreach(positions, pos)
- set_irn_n(irn, (int) pos, mux);
- }
- }
-
- /*
- * optimize the phi away. This can anable further runs of this
- * function. Look at _can_move. phis cannot be moved there.
- */
- nw = optimize_in_place_2(irn);
- if(nw != irn)
- exchange(irn, nw);
-
- return muxes_made;
-}
-
-typedef struct _cond_walk_info_t {
- struct obstack *obst;
- struct list_head cond_info_head;
- struct list_head phi_head;
-} cond_walk_info_t;
-
-
-static void annotate_cond_info_pre(ir_node *irn, void *data)
-{
- set_irn_link(irn, NULL);
-}
-
-static void annotate_cond_info_post(ir_node *irn, void *data)
-{
- cond_walk_info_t *cwi = data;
-
- /*
- * Check, if the node is a phi
- * we then compute a set of conds which are reachable from this
- * phi's block up to its dominator.
- * The set is attached to the blocks link field.
- */
- if(is_Phi(irn) && mode_is_datab(get_irn_mode(irn))) {
- ir_node *block = get_nodes_block(irn);
-
- cond_info_t *ci = get_irn_link(block);
-
- /* If the set is not yet computed, do it now. */
- if(!ci) {
- ci = obstack_alloc(cwi->obst, sizeof(*ci));
- ci->cond_set = new_set(cond_cmp, log2_ceil(get_irn_arity(block)));
- ci->first_phi = irn;
-
- INIT_LIST_HEAD(&ci->roots);
- INIT_LIST_HEAD(&ci->list);
-
- /*
- * Add this cond info to the list of all cond infos
- * in this graph. This is just done to xfree the
- * set easier afterwards (we save an irg_walk_graph).
- */
- list_add(&cwi->cond_info_head, &ci->list);
-
- DBG((dbg, LEVEL_2, "searching conds at %n\n", irn));
-
- /*
- * Fill the set with conds we find on the way from
- * the block to its dominator.
- */
- find_conds(irn, ci);
-
- /*
- * If there where no suitable conds, delete the set
- * immediately and reset the set pointer to NULL
- */
- if(set_count(ci->cond_set) == 0) {
- del_set(ci->cond_set);
- list_del(&ci->list);
- obstack_free(cwi->obst, ci);
- ci = NULL;
- }
- }
-
- else
- DBG((dbg, LEVEL_2, "conds already computed for %n (look at %n)\n", irn, ci->first_phi));
-
- set_irn_link(block, ci);
-
- if(ci) {
- phi_info_t *pi = obstack_alloc(cwi->obst, sizeof(*pi));
- pi->irn = irn;
- pi->cond_info = ci;
- INIT_LIST_HEAD(&pi->list);
- list_add(&pi->list, &cwi->phi_head);
- }
-
- }
-}
-
-static void dump_conds(cond_t *cond, void *env)
-{
- int i;
- FILE *f = env;
-
- ir_fprintf(f, "node:{title:\"n%p\" label:\"%n(%d, %d)\n%n\"}\n",
- cond, cond->cond, cond->cases[0].pos, cond->cases[1].pos,
- get_nodes_block(cond->cond));
-
- for(i = 0; i < 2; ++i)
- if(cond->cases[i].masked_by)
- ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\" label:\"%d\"}\n",
- cond, cond->cases[i].masked_by, i);
-}
-
-static void vcg_dump_conds(ir_graph *irg, cond_walk_info_t *cwi)
-{
- char buf[512];
- FILE *f;
-
- snprintf(buf, sizeof(buf), "%s-conds.vcg", get_entity_name(get_irg_entity(irg)));
-
- if((f = fopen(buf, "wt")) != NULL) {
- cond_info_t *ci;
- phi_info_t *phi;
- cond_t *cond;
-
- ir_fprintf(f, "graph:{\ndisplay_edge_labels:yes\n");
- list_for_each_entry(cond_info_t, ci, &cwi->cond_info_head, list) {
- ir_fprintf(f, "node:{title:\"n%p\" label:\"cond info\"}\n", ci);
- list_for_each_entry(cond_t, cond, &ci->roots, list) {
- walk_conds(cond, NULL, dump_conds, f);
- ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", ci, cond);
- }
- }
-
- list_for_each_entry(phi_info_t, phi, &cwi->phi_head, list) {
- ir_fprintf(f, "node:{title:\"n%p\" label:\"%n\n%n\"}\n",
- phi->irn, phi->irn, get_nodes_block(phi->irn));
- ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", phi->irn, phi->cond_info);
- }
- fprintf(f, "}\n");
- }
-}
-
-void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
-{
- int muxes_made = 0;
- struct obstack obst;
- phi_info_t *phi_info;
- cond_info_t *cond_info;
- cond_walk_info_t cwi;
-
- opt_if_conv_info_t p;
-
- if(!get_opt_if_conversion())
- return;
-
- /* get the parameters */
- if (params)
- memcpy(&p, params, sizeof(p));
- else
- memcpy(&p, &default_info, sizeof(p));
-
- if (! p.allow_mux)
- p.allow_mux = default_info.allow_mux;
-
- obstack_init(&obst);
-
- cwi.obst = &obst;
- INIT_LIST_HEAD(&cwi.cond_info_head);
- INIT_LIST_HEAD(&cwi.phi_head);
-
- /* Init the debug stuff. */
- FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
-#if 0
- firm_dbg_set_mask(dbg, LEVEL_1|LEVEL_2|LEVEL_3);
-#endif
-
- /* if-conversion works better with normalized returns */
- normalize_one_return(irg);
-
- /* Ensure, that the dominators are computed. */
- assure_doms(irg);
-
- DBG((dbg, LEVEL_1, "if conversion for irg %s(%p)\n",
- get_entity_name(get_irg_entity(irg)), irg));
-
- /*
- * Collect information about the conds pu the phis on an obstack.
- * It is important that phi nodes which are 'higher' (with a
- * lower dfs pre order) are in front of the obstack. Since they are
- * possibly turned in to muxes this can enable the optimization
- * of 'lower' ones.
- */
- irg_walk_graph(irg, annotate_cond_info_pre, annotate_cond_info_post, &cwi);
-
-#if 0
- vcg_dump_conds(irg, &cwi);
-#endif
-
- /* Process each suitable phi found. */
- list_for_each_entry(phi_info_t, phi_info, &cwi.phi_head, list) {
- DBG((dbg, LEVEL_2, "phi node %n\n", phi_info->irn));
- muxes_made += check_out_phi(phi_info, &p);
- }
-
- list_for_each_entry(cond_info_t, cond_info, &cwi.cond_info_head, list) {
- del_set(cond_info->cond_set);
- }
-
- DBG((dbg, LEVEL_1, "muxes made: %d\n", muxes_made));
-
- obstack_free(&obst, NULL);
-
- dump_ir_block_graph(irg, "_ifconv_hack");
-}
-
-#endif