summaryrefslogtreecommitdiffhomepage
path: root/ir/opt
diff options
context:
space:
mode:
authorAndreas Fried <andreas.fried@kit.edu>2019-06-19 18:02:55 +0200
committerAndreas Fried <andreas.fried@kit.edu>2019-06-19 18:04:16 +0200
commitaf110c3424d1f33603916583091c02d76e2e27c6 (patch)
tree2f570919896ccf67a3d403a5691b3f7713201742 /ir/opt
parent6a311dc439f7c98a5dbb0dd6d31f4c42edc26ff8 (diff)
Place fewer Phis when constructing LCSSA form.better-lcssa
This implementation probably places the minimal amount of Phis for reducible control flow, but will miss SCCs. It uses the following rules: - If the block has one predecessor, pass along the predecessor's Phi. - If all predecessors are the same Phi or a self-loop, use the predecessor.
Diffstat (limited to 'ir/opt')
-rw-r--r--ir/opt/lcssa.c169
1 files changed, 138 insertions, 31 deletions
diff --git a/ir/opt/lcssa.c b/ir/opt/lcssa.c
index ad54f24..72f2fee 100644
--- a/ir/opt/lcssa.c
+++ b/ir/opt/lcssa.c
@@ -17,6 +17,23 @@
DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
+/* Returns true iff inner is nested inside outer.
+ * Also returns true if inner and outer are the same loop. */
+static bool is_loop_nested_inside(ir_loop const *inner, ir_loop const *const outer)
+{
+ unsigned inner_depth = get_loop_depth(inner);
+ unsigned outer_depth = get_loop_depth(outer);
+ if (outer_depth > inner_depth) {
+ return false;
+ }
+
+ for (unsigned i = inner_depth; i > outer_depth; i--) {
+ inner = get_loop_outer_loop(inner);
+ }
+
+ return inner == outer;
+}
+
/* Returns true if control flow has to exit a loop on the path from
* "from_block" to "to_block". */
static bool cf_has_loop_exit(ir_node const *const from_block, ir_node const *const to_block)
@@ -52,51 +69,138 @@ static bool cf_has_loop_exit(ir_node const *const from_block, ir_node const *con
// to_block is deeper in the loop or equally deep.
// Check if to_block's loop is an inner loop (or the same) of from_block's loop.
- for (unsigned i = to_depth; i > from_depth; i--) {
- to_loop = get_loop_outer_loop(to_loop);
- }
+ bool nested = is_loop_nested_inside(to_loop, from_loop);
+
// If loops are not equal, we have to leave from_loop before entering to_loop.
- DB((dbg, LEVEL_2, "checking nesting -> %s\n", from_loop != to_loop ? "true" : "false"));
- return from_loop != to_loop;
+ DB((dbg, LEVEL_2, "checking nesting -> %s\n", !nested ? "true" : "false"));
+ return !nested;
}
-static ir_node *insert_phis_recursive(ir_node *const pred, ir_node *const block)
+/* Returns true if control flow from pred_block to block is an exit of any loop containing target. */
+static bool is_nested_loop_exit(ir_node const *const block, ir_node const *const pred_block, ir_node const *const target)
{
- DB((dbg, LEVEL_2, "\tinsert_phis_recursive at %+F: ", block));
+ ir_loop const *const block_loop = get_irn_loop(block);
+ ir_loop const *const pred_loop = get_irn_loop(pred_block);
- if (block == get_nodes_block(pred)) {
- DB((dbg, LEVEL_2, "Target block found, return %+F\n", pred));
- return pred;
+ if (!block_loop || !pred_loop || block_loop == pred_loop) {
+ return false;
}
- ir_node *const link = get_irn_link(block);
- if (link) {
- DB((dbg, LEVEL_2, "Already visited, return %+F\n", link));
- return link;
- }
+ ir_node const *const target_block = get_nodes_block(target);
+ ir_loop const *const target_loop = get_irn_loop(target_block);
+ assert(target_loop && get_loop_depth(target_loop) > 0);
- int const arity = get_irn_arity(block);
- ir_node **const in = ALLOCAN(ir_node *, arity);
- for (int i = 0; i < arity; ++i) {
- in[i] = pred;
+ unsigned const block_depth = get_loop_depth(block_loop);
+ unsigned const pred_depth = get_loop_depth(pred_loop);
+
+ return is_loop_nested_inside(target_loop, pred_loop) &&
+ pred_depth > block_depth;
+}
+
+static ir_node *new_linked_Phi(ir_node *block, ir_mode *mode)
+{
+ ir_node *unknown = new_r_Unknown(get_irn_irg(block), mode);
+ unsigned arity = get_Block_n_cfgpreds(block);
+ ir_node *in[arity];
+
+ for (unsigned i = 0; i < arity; i++) {
+ in[i] = unknown;
}
- ir_mode *const mode = get_irn_mode(pred);
- int const opt = get_optimize();
+
+ int const opt = get_optimize();
set_optimize(0);
ir_node *const phi = new_r_Phi(block, arity, in, mode);
- DB((dbg, LEVEL_2, "Constructing new Phi %+F\n", phi));
set_optimize(opt);
+
set_irn_link(block, phi);
- for (int i = 0; i < arity; ++i) {
- ir_node *const pred_block = get_Block_cfgpred_block(block, i);
- ir_node *const pred_phi = insert_phis_recursive(pred, pred_block);
- DB((dbg, LEVEL_2, "\t\t%+F @ %+F: Predecessor %i is %+F\n", phi, block, i, pred_phi));
- set_irn_n(phi, i, pred_phi);
+ return phi;
+}
+
+static ir_node *insert_phis_recursive(ir_node *const target, ir_node *const block)
+{
+ DB((dbg, LEVEL_2, "\tinsert_phis_recursive at %+F: ", block));
+
+ ir_node *const link = get_irn_link(block);
+ if (link) {
+ DB((dbg, LEVEL_2, "Already visited, return %+F\n", link));
+ return link;
}
- DB((dbg, LEVEL_2, "\t%+F done, return %+F\n", block, phi));
- return phi;
+ ir_node *result;
+ unsigned const arity = get_irn_arity(block);
+ ir_mode *mode = get_irn_mode(target);
+
+ if (block == get_nodes_block(target)) {
+ DB((dbg, LEVEL_2, "Target block found, return %+F\n", target));
+ result = target;
+
+ } else if (arity == 1) {
+ ir_node *pred_block = get_Block_cfgpred_block(block, 0);
+
+ if (is_nested_loop_exit(block, pred_block, target)) {
+ ir_node *phi = new_linked_Phi(block, mode);
+ DB((dbg, LEVEL_2, "Loop exit, constructing %+F\n", phi));
+
+ ir_node *pred = insert_phis_recursive(target, pred_block);
+ set_irn_n(phi, 0, pred);
+ DB((dbg, LEVEL_2, "\tsetting pred of loop-exiting %+F to %+F\n", phi, pred));
+
+ result = phi;
+ } else {
+ DB((dbg, LEVEL_2, "One predecessor, pass-through\n"));
+ result = insert_phis_recursive(target, pred_block);
+ }
+
+ } else {
+ ir_node *phi = new_linked_Phi(block, mode);
+ DB((dbg, LEVEL_2, "Multiple preds, constructing tentative %+F\n", phi));
+
+ for (unsigned i = 0; i < arity; i++) {
+ ir_node *const pred_block = get_Block_cfgpred_block(block, i);
+ ir_node *const pred_phi = insert_phis_recursive(target, pred_block);
+ DB((dbg, LEVEL_2, "\t\t%+F @ %+F: Predecessor %i is %+F\n", phi, block, i, pred_phi));
+ set_irn_n(phi, i, pred_phi);
+ }
+
+#ifdef DEBUG_libfirm
+ DB((dbg, LEVEL_2, "\tChecking if %+F can be optimized away (preds are", phi));
+ for (unsigned i = 0; i < arity; i++) {
+ DB((dbg, LEVEL_2, " %+F", get_irn_n(phi, i)));
+ }
+ DB((dbg, LEVEL_2, "): "));
+#endif
+ bool phi_has_single_pred = true;
+ ir_node *single_pred = NULL;
+
+ for (unsigned i = 0; i < arity; i++) {
+ ir_node *pred = get_irn_n(phi, i);
+ if (pred == phi) {
+ // Self-loops can be ignored
+ // TODO This is only an approximation to SCCs
+ continue;
+ }
+ if (single_pred && pred != single_pred) {
+ phi_has_single_pred = false;
+ break;
+ }
+ single_pred = pred;
+ }
+
+ if (phi_has_single_pred) {
+ // single_pred dominates phi because it dominates every CF predecessor of block
+ // ==> We can use it as block's phi
+ DB((dbg, LEVEL_2, "Yes, replacing with %+F\n", single_pred));
+ result = single_pred;
+ } else {
+ DB((dbg, LEVEL_2, "No\n"));
+ result = phi;
+ }
+ }
+
+ set_irn_link(block, result);
+ DB((dbg, LEVEL_2, "\t%+F done, return %+F\n", block, result));
+ return result;
}
static void clear_link_recursive(ir_node *const block)
@@ -226,7 +330,8 @@ static void verify_lcssa(ir_graph *const irg)
void assure_lcssa(ir_graph *const irg)
{
FIRM_DBG_REGISTER(dbg, "firm.opt.lcssa");
- assure_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO | IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE);
+ assure_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO | IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE | IR_GRAPH_PROPERTY_NO_CRITICAL_EDGES);
+ dump_ir_graph(irg, "before-lcssa");
ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
irg_walk_graph(irg, firm_clear_link, NULL, NULL);
DB((dbg, LEVEL_1, "Begin LCSSA construction on %+F\n", irg));
@@ -234,6 +339,8 @@ void assure_lcssa(ir_graph *const irg)
DB((dbg, LEVEL_1, "LCSSA done on %+F\n", irg));
ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
DEBUG_ONLY(verify_lcssa(irg);)
+ confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_NONE);
+ dump_ir_graph(irg, "after-lcssa");
}
void assure_loop_lcssa(ir_graph *const irg, ir_loop *const loop)
@@ -245,5 +352,5 @@ void assure_loop_lcssa(ir_graph *const irg, ir_loop *const loop)
irg_walk_graph(irg, firm_clear_link, NULL, NULL);
insert_phis_for_loop(loop);
ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
- clear_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO | IR_GRAPH_PROPERTY_CONSISTENT_OUTS | IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE);
+ confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_NONE);
}