summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--opt.c81
-rwxr-xr-xtests.sh12
-rw-r--r--tests/test_data_flow_and_swap.out12
-rw-r--r--tests/test_data_flow_or_swap.out12
4 files changed, 92 insertions, 25 deletions
diff --git a/opt.c b/opt.c
index a7ebbe2..6875e92 100644
--- a/opt.c
+++ b/opt.c
@@ -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);
diff --git a/tests.sh b/tests.sh
index 8532d10..1ad1568 100755
--- a/tests.sh
+++ b/tests.sh
@@ -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