* @file
* @brief Control flow optimizations.
* @author Goetz Lindenmaier, Michael Beck, Sebastian Hack
- * @version $Id$
*
* Removes Bad control flow predecessors and empty blocks. A block is empty
* if it contains only a Jmp node. Blocks can only be removed if they are not
*/
static void collect_nodes(ir_node *n, void *ctx)
{
- ir_node ***switch_conds = (ir_node***)ctx;
-
+ (void) ctx;
if (is_Phi(n)) {
/* Collect Phi nodes to compact ins along with block's ins. */
ir_node *block = get_nodes_block(n);
add_Block_phi(block, n);
} else if (is_Block(n)) {
- if (has_Block_entity(n)) {
+ if (get_Block_entity(n) != NULL) {
/* block with a jump label attached cannot be removed. */
set_Block_removable(n, false);
}
ir_node *pred = get_Proj_pred(n);
set_irn_link(n, get_irn_link(pred));
set_irn_link(pred, n);
- } else if (is_Cond(n) && is_switch_Cond(n)) {
- /* found a switch-Cond, collect */
- ARR_APP1(ir_node*, *switch_conds, n);
}
}
}
return 1;
}
+/**
+ * This method merges blocks. A block is applicable to be merged, if it
+ * has only one predecessor with an unconditional jump to this block;
+ * and if this block does not contain any phis.
+ */
+static void merge_blocks(ir_node *b, void *env)
+{
+ (void) env;
+
+ if (get_Block_n_cfgpreds(b) == 1) {
+ ir_node* pred = get_Block_cfgpred(b, 0);
+ if (is_Jmp(pred)) {
+ ir_node* pred_block = get_nodes_block(pred);
+ if (get_Block_phis(b) == NULL) {
+ exchange(b, pred_block);
+ }
+ }
+ }
+}
+
/**
* This method removes empty blocks. A block is empty if it only contains Phi
* and Jmp nodes.
xfree(in);
}
-/**
- * Optimize table-switch Conds.
- *
- * @param cond the switch-Cond
- * @return true if the switch-Cond was optimized
- */
-static bool handle_switch_cond(ir_node *cond)
-{
- ir_node *sel = get_Cond_selector(cond);
- ir_node *proj1 = (ir_node*)get_irn_link(cond);
- ir_node *proj2 = (ir_node*)get_irn_link(proj1);
- ir_node *blk = get_nodes_block(cond);
-
- /* exactly 1 Proj on the Cond node: must be the defaultProj */
- if (proj2 == NULL) {
- ir_node *jmp = new_r_Jmp(blk);
- assert(get_Cond_default_proj(cond) == get_Proj_proj(proj1));
- /* convert it into a Jmp */
- exchange(proj1, jmp);
- return true;
- }
-
- /* handle Cond nodes with constant argument. In this case the localopt rules
- * should have killed all obviously impossible cases.
- * So the only case left to handle here is 1 defaultProj + 1 case
- * (this one case should be the one taken) */
- if (get_irn_link(proj2) == NULL) {
- ir_tarval *tv = value_of(sel);
-
- if (tv != tarval_bad) {
- /* we have a constant switch */
- long num = get_tarval_long(tv);
- long def_num = get_Cond_default_proj(cond);
- ir_graph *irg = get_irn_irg(cond);
- ir_node *bad = new_r_Bad(irg, mode_X);
-
- if (def_num == get_Proj_proj(proj1)) {
- /* first one is the defProj */
- if (num == get_Proj_proj(proj2)) {
- ir_node *jmp = new_r_Jmp(blk);
- exchange(proj2, jmp);
- exchange(proj1, bad);
- return true;
- }
- } else if (def_num == get_Proj_proj(proj2)) {
- /* second one is the defProj */
- if (num == get_Proj_proj(proj1)) {
- ir_node *jmp = new_r_Jmp(blk);
- exchange(proj1, jmp);
- exchange(proj2, bad);
- return true;
- }
- } else {
- /* neither: strange, Cond was not optimized so far */
- if (num == get_Proj_proj(proj1)) {
- ir_node *jmp = new_r_Jmp(blk);
- exchange(proj1, jmp);
- exchange(proj2, bad);
- return true;
- } else if (num == get_Proj_proj(proj2)) {
- ir_node *jmp = new_r_Jmp(blk);
- exchange(proj2, jmp);
- exchange(proj1, bad);
- return true;
- }
- }
- }
- }
- return false;
-}
-
/**
* Optimize boolean Conds, where true and false jump to the same block into a Jmp
* Block must contain no Phi nodes.
int n_preds = get_Block_n_cfgpreds(block);
for (i = 0; i < n_preds; ++i) {
- ir_node *jmp, *jmp_block, *pred, *pred_block;
+ ir_node *jmp, *jmp_block;
int n_jpreds = 0;
jmp = get_Block_cfgpred(block, i);
continue; /* this infinite loop cannot be optimized any further */
if (is_unknown_jump_target(&env->block_infos, jmp_block))
continue; /* unknown jump target must not be optimized */
- if (has_operations(&env->block_infos,jmp_block))
- continue; /* this block contains operations and cannot be skipped */
if (has_phis(&env->block_infos,jmp_block))
continue; /* this block contains Phis and is not skipped */
if (Block_block_visited(jmp_block)) {
* if block has no Phis.
*/
if (n_jpreds == 1) {
+ ir_node *pred = get_Block_cfgpred(jmp_block, 0);
+ ir_node *pred_block = get_nodes_block(pred);
+ if (has_operations(&env->block_infos,jmp_block)) {
+ if (get_irg_start_block(get_irn_irg(pred_block)) == pred_block)
+ continue; /* must not merge operations into start block */
+ if (!is_Jmp(pred))
+ continue; /* must not create partially dead code, especially when it is mode_M */
+ }
+
/* skip jmp block by rerouting its predecessor to block
*
* A A
* | |
* block block
*/
- pred = get_Block_cfgpred(jmp_block, 0);
exchange(jmp, pred);
/* cleanup: jmp_block might have a Keep edge! */
- pred_block = get_nodes_block(pred);
exchange(jmp_block, pred_block);
env->changed = true;
- } else if (! has_phis(&env->block_infos, block)) {
+ } else if ( !has_phis(&env->block_infos, block) &&
+ !has_operations(&env->block_infos,jmp_block))
+ {
/* all predecessors can skip the jmp block, so block gets some new
* predecessors
*
}
/* now append the new predecessors */
for (j = 0; j < n_jpreds; ++j) {
- pred = get_Block_cfgpred(jmp_block, j);
+ ir_node *pred = get_Block_cfgpred(jmp_block, j);
ins[n_preds+j] = pred;
}
set_irn_in(block, n_preds+n_jpreds, ins);
/* The switch Cond optimization might expose unreachable code, so we loop */
for (;;) {
- int length;
- ir_node **switch_conds = NULL;
bool changed = false;
assure_doms(irg);
* Finally it marks all blocks that do not contain useful
* computations, i.e., these blocks might be removed.
*/
- switch_conds = NEW_ARR_F(ir_node*, 0);
- irg_walk(end, clear_link_and_mark_blocks_removable, collect_nodes, &switch_conds);
-
- /* handle all collected switch-Conds */
- length = ARR_LEN(switch_conds);
- for (i = 0; i < length; ++i) {
- ir_node *cond = switch_conds[i];
- changed |= handle_switch_cond(cond);
- }
- DEL_ARR_F(switch_conds);
+ irg_walk(end, clear_link_and_mark_blocks_removable, collect_nodes, NULL);
if (!changed)
break;
* blocks, which it finds in a linked list computed before.
* */
assure_doms(irg);
- irg_block_walk_graph(irg, optimize_blocks, NULL, &env);
+ irg_block_walk_graph(irg, optimize_blocks, merge_blocks, &env);
new_end = optimize_in_place(end);
if (new_end != end) {