Re-work optimization levels.

-O3 is the new default, for the future cost-based optimizer.  -O4
enables the surprising/aggressive optimizations that used to be under
-O3.  -Ofast is a synonym for -O4.

3 files changed, 55 insertions, 21 deletions

diff --git a/RELEASES.md b/RELEASES.md
index 2b55ff9..3d75210 100644
--- a/RELEASES.md
+++ b/RELEASES.md
@@ -9,21 +9,45 @@
 
 62/76 GNU find features supported.
 
+- Rework optimization levels
+  - `-O1` (logical simplification):
+    - Constant propagation (`! -false <==> -true`, `! -true <==> -false`)
+    - Double negation (`! ! X <==> X`)
+    - Conjunction elimination:
+      - `-true -a X <==> X`
+      - `X -a -true <==> X`
+    - Disjunctive syllogism:
+      - `-false -o X <==> X`
+      - `X -o -false <==> X`
+    - Short-circuiting:
+      - `-false -a X <==> -false`
+      - `-true -o X <==> -true`
+    - De Morgan's laws (**new**):
+      - `( ! X -a ! Y ) <==> ! ( X -o Y )`
+      - `( ! X -o ! Y ) <==> ! ( X -a Y )`
+      - `! ( X -a ! Y ) <==> ( ! X -o Y )`
+      - `! ( X -o ! Y ) <==> ( ! X -a Y )`
+      - `! ( ! X -a Y ) <==> ( X -o ! Y )`
+      - `! ( ! X -o Y ) <==> ( X -a ! Y )`
+    - Unused result (**new**): `! X , Y <==> X , Y`
+  - `-O2` (purity):
+    - (These optimizations take the purity of predicates into account, allowing side-effect-free tests like `-name` or `-type` to be moved or removed)
+    - `PURE -a -false <==> -false`
+    - `PURE -o -true <==> -true`
+    - `PURE , X <==> X`
+    - Top-level unused result (**new**): `X (-a|-o|,) PURE <==> X`
+  - `-O3` (cost-based, **default**):
+    - Re-order tests to reduce the expected cost (TODO)
+  - `-O4` (aggressive):
+    - (These are very aggressive optimizations that may have surprising effects on warning/error messages and runtime, but still should not affect the resulting output)
+    - Change top-level expressions with no actions to `-false` (**new**):
+      - For example, `bfs -O4 -true -o -print` becomes `-false`, because `-print` is unreachable
+    - Skip the entire traversal if the top-level expression is `-false`
+      - `bfs -O4 -false` (or anything that optimizes to `-false`) will exit immediately
+      - This may cause messages about non-existent files, symbolic link cycles, etc. to be skipped
+  - `-Ofast`:
+    - Always the highest level, currently the same as `-O4`
 - Color files with multiple hard links correctly
-- At `-O3`, replace command lines with no action with `-false`
-  - For example, `bfs -true -o -print` becomes `-false`, because `-print` is not reachable
-- Move optimizations that rely on the purity of a predicate to `-O2` (the new default)
-- Optimize using De Morgan's laws:
-  - `( ! X -a ! Y ) <==> ! ( X -o Y )`
-  - `( ! X -o ! Y ) <==> ! ( X -a Y )`
-  - `! ( X -a ! Y ) <==> ( ! X -o Y )`
-  - `! ( X -o ! Y ) <==> ( ! X -a Y )`
-  - `! ( ! X -a Y ) <==> ( X -o ! Y )`
-  - `! ( ! X -o Y ) <==> ( X -a ! Y )`
-- At `-O2`, remove top-level pure expressions
-  - For example, `bfs -print , -false` becomes `-print`, because the top-level return value is ignored
-- At `-O2`, remove negations from the left-hand side of the comma operator
-  - For example, `-not -print , -print` becomes `-print , -print`, because the return value of the LHS is ignored
 - Treat `-`, `)`, and `,` as paths when required to by POSIX
   - `)` and `,` are only supported before the expression begins
 - Implement `-D opt`
diff --git a/eval.c b/eval.c
index c3e29d2..44b1fa4 100644
--- a/eval.c
+++ b/eval.c
@@ -917,9 +917,9 @@ int eval_cmdline(const struct cmdline *cmdline) {
 		return 0;
 	}
 
-	if (cmdline->optlevel >= 3 && cmdline->expr->eval == eval_false) {
+	if (cmdline->optlevel >= 4 && cmdline->expr->eval == eval_false) {
 		if (cmdline->debug & DEBUG_OPT) {
-			fputs("-O3: skipping evaluation of top-level -false\n", stderr);
+			fputs("-O4: skipping evaluation of top-level -false\n", stderr);
 		}
 		return 0;
 	}
diff --git a/parse.c b/parse.c
index e9e1b52..c24592c 100644
--- a/parse.c
+++ b/parse.c
@@ -609,10 +609,20 @@ static struct expr *parse_debug(struct parser_state *state) {
  * Parse -On.
  */
 static struct expr *parse_optlevel(struct parser_state *state) {
-	if (!parse_int(state, state->argv[0] + 2, &state->cmdline->optlevel, IF_INT)) {
+	int *optlevel = &state->cmdline->optlevel;
+
+	if (strcmp(state->argv[0], "-Ofast") == 0) {
+		*optlevel = 4;
+	} else if (!parse_int(state, state->argv[0] + 2, optlevel, IF_INT)) {
 		return NULL;
 	}
 
+	if (*optlevel > 4) {
+		pretty_warning(state->cmdline->stderr_colors,
+		               "warning: %s is the same as -O4.\n\n",
+		               state->argv[0]);
+	}
+
 	return parse_nullary_flag(state);
 }
 
@@ -1777,8 +1787,8 @@ static struct expr *optimize_whole_expr(const struct parser_state *state, struct
 		}
 	}
 
-	if (optlevel >= 3 && expr->pure && expr != &expr_false) {
-		debug_opt(state, "-O3: top-level purity: %e <==> %e\n", expr, &expr_false);
+	if (optlevel >= 4 && expr->pure && expr != &expr_false) {
+		debug_opt(state, "-O4: top-level purity: %e <==> %e\n", expr, &expr_false);
 		free_expr(expr);
 		expr = &expr_false;
 	}
@@ -1798,7 +1808,7 @@ static void dump_cmdline(const struct cmdline *cmdline) {
 		fputs("-P ", stderr);
 	}
 
-	if (cmdline->optlevel != 2) {
+	if (cmdline->optlevel != 3) {
 		fprintf(stderr, "-O%d ", cmdline->optlevel);
 	}
 
@@ -1853,7 +1863,7 @@ struct cmdline *parse_cmdline(int argc, char *argv[]) {
 	cmdline->mindepth = 0;
 	cmdline->maxdepth = INT_MAX;
 	cmdline->flags = BFTW_RECOVER;
-	cmdline->optlevel = 2;
+	cmdline->optlevel = 3;
 	cmdline->debug = 0;
 	cmdline->expr = &expr_true;
 	cmdline->nopen_files = 0;