* @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
#include "irdump.h"
#include "irverify.h"
#include "iredges.h"
-#include "opt_manage.h"
#include "array_t.h"
*/
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.
static bool get_block_flag(const ir_nodehashmap_t *infos, const ir_node *block,
int flag)
{
- return PTR_TO_INT(ir_nodehashmap_get(infos, block)) & flag;
+ return PTR_TO_INT(ir_nodehashmap_get(void, infos, block)) & flag;
}
static void set_block_flag(ir_nodehashmap_t *infos, ir_node *block,
block_flags_t flag)
{
- int data = PTR_TO_INT(ir_nodehashmap_get(infos, block));
+ int data = PTR_TO_INT(ir_nodehashmap_get(void, infos, block));
data |= flag;
ir_nodehashmap_insert(infos, block, INT_TO_PTR(data));
}
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);
irg_block_walk_graph(irg, NULL, optimize_ifs, &env);
if (env.changed) {
- clear_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_DOMINANCE);
+ confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_NONE);
/* clear block info, because it must be recomputed */
irg_block_walk_graph(irg, clear_block_info, NULL, &env.block_infos);
/* Removing blocks and Conds might enable more optimizations */
continue;
} else {
+ confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_ALL);
break;
}
}
}
/* Optimizations of the control flow that also require changes of Phi nodes. */
-static ir_graph_state_t do_cfopt(ir_graph *irg)
+void optimize_cf(ir_graph *irg)
{
int i, j, n;
ir_node **in = NULL;
env.changed = false;
env.phis_moved = false;
- assert(get_irg_phase_state(irg) != phase_building);
-
/* if the graph is not pinned, we cannot determine empty blocks */
assert(get_irg_pinned(irg) != op_pin_state_floats &&
"Control flow optimization need a pinned graph");
- edges_deactivate(irg);
+ assure_irg_properties(irg, IR_GRAPH_PROPERTY_NO_UNREACHABLE_CODE);
/* First the "simple" optimizations, which do not touch Phis */
cfgopt_ignoring_phis(irg);
ir_reserve_resources(irg, IR_RESOURCE_BLOCK_MARK | IR_RESOURCE_IRN_LINK
| IR_RESOURCE_PHI_LIST);
- /* 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);
-
- /*
- * This pass collects all Phi nodes in a link list in the block
- * nodes. Further it performs simple control flow optimizations.
- * 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);
-
- if (!changed)
- break;
-
- clear_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_DOMINANCE
- | IR_GRAPH_STATE_VALID_EXTENDED_BLOCKS
- | IR_GRAPH_STATE_CONSISTENT_ENTITY_USAGE);
- }
+ /*
+ * This pass collects all Phi nodes in a link list in the block
+ * nodes. Further it performs simple control flow optimizations.
+ * Finally it marks all blocks that do not contain useful
+ * computations, i.e., these blocks might be removed.
+ */
+ irg_walk(end, clear_link_and_mark_blocks_removable, collect_nodes, NULL);
/* assert due to collect_nodes:
* 1. removable blocks are now marked as such
*/
/* Optimize the standard code.
- * It walks only over block nodes and adapts these and the Phi nodes in these
- * blocks, which it finds in a linked list computed before.
- * */
- assure_doms(irg);
- irg_block_walk_graph(irg, optimize_blocks, NULL, &env);
+ * It walks only over block nodes and adapts these and the Phi nodes in
+ * these blocks, which it finds in a linked list computed before.
+ */
+ assure_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE);
+ irg_block_walk_graph(irg, optimize_blocks, merge_blocks, &env);
new_end = optimize_in_place(end);
if (new_end != end) {
}
}
- return 0;
-}
-
-static optdesc_t opt_cf = {
- "control-flow",
- IR_GRAPH_STATE_NO_UNREACHABLE_CODE,
- do_cfopt,
-};
-
-void optimize_cf(ir_graph *irg)
-{
- perform_irg_optimization(irg, &opt_cf);
+ confirm_irg_properties(irg,
+ env.changed ? IR_GRAPH_PROPERTIES_NONE : IR_GRAPH_PROPERTIES_ALL);
}
/* Creates an ir_graph pass for optimize_cf. */
projects / libfirm / blobdiff