diff options
| -rw-r--r-- | opt.c | 81 | ||||
| -rwxr-xr-x | tests.sh | 12 | ||||
| -rw-r--r-- | tests/test_data_flow_and_swap.out | 12 | ||||
| -rw-r--r-- | tests/test_data_flow_or_swap.out | 12 |
4 files changed, 92 insertions, 25 deletions
@@ -355,17 +355,6 @@ static struct expr *optimize_and_expr(const struct opt_state *state, struct expr expr->cost = lhs->cost + lhs->probability*rhs->cost; expr->probability = lhs->probability*rhs->probability; - if (optlevel >= 3 && lhs->pure && rhs->pure) { - double swapped_cost = rhs->cost + rhs->probability*lhs->cost; - if (swapped_cost < expr->cost) { - debug_opt(state, "-O3: cost: %e", expr); - expr->lhs = rhs; - expr->rhs = lhs; - debug_opt(state, " <==> %e (~%g --> ~%g)\n", expr, expr->cost, swapped_cost); - expr->cost = swapped_cost; - } - } - return expr; } @@ -426,17 +415,6 @@ static struct expr *optimize_or_expr(const struct opt_state *state, struct expr expr->cost = lhs->cost + (1 - lhs->probability)*rhs->cost; expr->probability = lhs->probability + rhs->probability - lhs->probability*rhs->probability; - if (optlevel >= 3 && lhs->pure && rhs->pure) { - double swapped_cost = rhs->cost + (1 - rhs->probability)*lhs->cost; - if (swapped_cost < expr->cost) { - debug_opt(state, "-O3: cost: %e", expr); - expr->lhs = rhs; - expr->rhs = lhs; - debug_opt(state, " <==> %e (~%g --> ~%g)\n", expr, expr->cost, swapped_cost); - expr->cost = swapped_cost; - } - } - return expr; } @@ -619,6 +597,52 @@ done: return expr; } +/** Swap the children of a binary expression if it would reduce the cost. */ +static bool reorder_expr(const struct opt_state *state, struct expr *expr, double swapped_cost) { + if (swapped_cost < expr->cost) { + debug_opt(state, "-O3: cost: %e", expr); + struct expr *lhs = expr->lhs; + expr->lhs = expr->rhs; + expr->rhs = lhs; + debug_opt(state, " <==> %e (~%g --> ~%g)\n", expr, expr->cost, swapped_cost); + expr->cost = swapped_cost; + return true; + } else { + return false; + } +} + +/** + * Recursively reorder sub-expressions to reduce the overall cost. + * + * @param expr + * The expression to optimize. + * @return + * Whether any subexpression was reordered. + */ +static bool reorder_expr_recursive(const struct opt_state *state, struct expr *expr) { + bool ret = false; + struct expr *lhs = expr->lhs; + struct expr *rhs = expr->rhs; + + if (lhs) { + ret |= reorder_expr_recursive(state, lhs); + } + if (rhs) { + ret |= reorder_expr_recursive(state, rhs); + } + + if (expr->eval == eval_and || expr->eval == eval_or) { + if (lhs->pure && rhs->pure) { + double rhs_prob = expr->eval == eval_and ? rhs->probability : 1.0 - rhs->probability; + double swapped_cost = rhs->cost + rhs_prob*lhs->cost; + ret |= reorder_expr(state, expr, swapped_cost); + } + } + + return ret; +} + int optimize_cmdline(struct cmdline *cmdline) { struct opt_facts facts_when_impure; set_facts_impossible(&facts_when_impure); @@ -633,14 +657,23 @@ int optimize_cmdline(struct cmdline *cmdline) { .facts_when_impure = &facts_when_impure, }; + int optlevel = cmdline->optlevel; + cmdline->expr = optimize_expr_recursive(&state, cmdline->expr); if (!cmdline->expr) { return -1; } - cmdline->expr = ignore_result(&state, cmdline->expr); + if (optlevel >= 3 && reorder_expr_recursive(&state, cmdline->expr)) { + // Re-do optimizations to account for the new ordering + set_facts_impossible(&facts_when_impure); + cmdline->expr = optimize_expr_recursive(&state, cmdline->expr); + if (!cmdline->expr) { + return -1; + } + } - int optlevel = cmdline->optlevel; + cmdline->expr = ignore_result(&state, cmdline->expr); if (optlevel >= 2 && facts_when_impure.mindepth > cmdline->mindepth) { debug_opt(&state, "-O2: data flow: mindepth --> %d\n", facts_when_impure.mindepth); @@ -227,11 +227,14 @@ posix_tests=( test_a test_o test_deep + test_or_purity test_double_negation test_de_morgan_not test_de_morgan_and test_de_morgan_or test_data_flow_type + test_data_flow_and_swap + test_data_flow_or_swap ) bsd_tests=( @@ -410,7 +413,6 @@ gnu_tests=( test_comma test_precedence test_and_purity - test_or_purity test_not_reachability test_comma_reachability test_print_error @@ -1589,6 +1591,14 @@ function test_data_flow_type() { bfs_diff basic \! \( -type f -o \! -type f \) } +function test_data_flow_and_swap() { + bfs_diff basic \! -type f -a -type d +} + +function test_data_flow_or_swap() { + bfs_diff basic \! \( -type f -o -not -type d \) +} + function test_print_error() { if [ -e /dev/full ]; then ! invoke_bfs basic -maxdepth 0 >/dev/full 2>/dev/null diff --git a/tests/test_data_flow_and_swap.out b/tests/test_data_flow_and_swap.out new file mode 100644 index 0000000..1e72fd9 --- /dev/null +++ b/tests/test_data_flow_and_swap.out @@ -0,0 +1,12 @@ +basic +basic/c +basic/e +basic/g +basic/i +basic/j +basic/k +basic/l +basic/g/h +basic/k/foo +basic/l/foo +basic/l/foo/bar diff --git a/tests/test_data_flow_or_swap.out b/tests/test_data_flow_or_swap.out new file mode 100644 index 0000000..1e72fd9 --- /dev/null +++ b/tests/test_data_flow_or_swap.out @@ -0,0 +1,12 @@ +basic +basic/c +basic/e +basic/g +basic/i +basic/j +basic/k +basic/l +basic/g/h +basic/k/foo +basic/l/foo +basic/l/foo/bar |