opt: Re-run optimizations after reordering expressions

This catches new data flow inferences that can be made after swapping
the children of an expression.

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