opt: Separate optimization from parsing

11 files changed, 859 insertions, 665 deletions

diff --git a/Makefile b/Makefile
index 62d72f2..0704d57 100644
--- a/Makefile
+++ b/Makefile
@@ -49,7 +49,7 @@ ALL_LDFLAGS = $(ALL_CFLAGS) $(LDFLAGS)
 
 all: bfs
 
-bfs: bftw.o color.o dstring.o eval.o exec.o main.o mtab.o parse.o printf.o typo.o util.o
+bfs: bftw.o color.o dstring.o eval.o exec.o main.o mtab.o opt.o parse.o printf.o typo.o util.o
 	$(CC) $(ALL_LDFLAGS) $^ -o $@
 
 release: CFLAGS := -O3 -flto $(WFLAGS) -DNDEBUG -g
diff --git a/bfs.h b/bfs.h
index 9c79449..909e76f 100644
--- a/bfs.h
+++ b/bfs.h
@@ -17,17 +17,6 @@
 #ifndef BFS_H
 #define BFS_H
 
-#include "color.h"
-#include "exec.h"
-#include "printf.h"
-#include "mtab.h"
-#include <regex.h>
-#include <stdbool.h>
-#include <stddef.h>
-#include <stdio.h>
-#include <sys/types.h>
-#include <time.h>
-
 #ifndef BFS_VERSION
 #	define BFS_VERSION "1.1.2"
 #endif
@@ -36,325 +25,4 @@
 #	define BFS_HOMEPAGE "https://github.com/tavianator/bfs"
 #endif
 
-/**
- * A command line expression.
- */
-struct expr;
-
-/**
- * Ephemeral state for evaluating an expression.
- */
-struct eval_state;
-
-/**
- * Expression evaluation function.
- *
- * @param expr
- *         The current expression.
- * @param state
- *         The current evaluation state.
- * @return
- *         The result of the test.
- */
-typedef bool eval_fn(const struct expr *expr, struct eval_state *state);
-
-/**
- * Various debugging flags.
- */
-enum debug_flags {
-	/** Print cost estimates. */
-	DEBUG_COST   = 1 << 0,
-	/** Print executed command details. */
-	DEBUG_EXEC   = 1 << 1,
-	/** Print optimization details. */
-	DEBUG_OPT    = 1 << 2,
-	/** Print rate information. */
-	DEBUG_RATES  = 1 << 3,
-	/** Trace the filesystem traversal. */
-	DEBUG_SEARCH = 1 << 4,
-	/** Trace all stat() calls. */
-	DEBUG_STAT   = 1 << 5,
-	/** Print the parse tree. */
-	DEBUG_TREE   = 1 << 6,
-};
-
-/**
- * A root path to explore.
- */
-struct root {
-	/** The root path itself. */
-	const char *path;
-	/** The next path in the list. */
-	struct root *next;
-};
-
-/**
- * The parsed command line.
- */
-struct cmdline {
-	/** The unparsed command line arguments. */
-	char **argv;
-
-	/** The list of root paths. */
-	struct root *roots;
-
-	/** Color data. */
-	struct colors *colors;
-	/** Colored stdout. */
-	CFILE *cout;
-	/** Colored stderr. */
-	CFILE *cerr;
-
-	/** Table of mounted file systems. */
-	struct bfs_mtab *mtab;
-
-	/** -mindepth option. */
-	int mindepth;
-	/** -maxdepth option. */
-	int maxdepth;
-
-	/** bftw() flags. */
-	enum bftw_flags flags;
-
-	/** Optimization level. */
-	int optlevel;
-	/** Debugging flags. */
-	enum debug_flags debug;
-	/** Whether to only handle paths with xargs-safe characters. */
-	bool xargs_safe;
-	/** Whether to ignore deletions that race with bfs. */
-	bool ignore_races;
-
-	/** The command line expression. */
-	struct expr *expr;
-
-	/** The number of open files used by the expression tree. */
-	int nopen_files;
-};
-
-/**
- * Possible types of numeric comparison.
- */
-enum cmp_flag {
-	/** Exactly n. */
-	CMP_EXACT,
-	/** Less than n. */
-	CMP_LESS,
-	/** Greater than n. */
-	CMP_GREATER,
-};
-
-/**
- * Possible types of mode comparison.
- */
-enum mode_cmp {
-	/** Mode is an exact match (MODE). */
-	MODE_EXACT,
-	/** Mode has all these bits (-MODE). */
-	MODE_ALL,
-	/** Mode has any of these bits (/MODE). */
-	MODE_ANY,
-};
-
-/**
- * Available struct stat time fields.
- */
-enum time_field {
-	/** Access time. */
-	ATIME,
-	/** Status change time. */
-	CTIME,
-	/** Modification time. */
-	MTIME,
-};
-
-/**
- * Possible time units.
- */
-enum time_unit {
-	/** Minutes. */
-	MINUTES,
-	/** Days. */
-	DAYS,
-};
-
-/**
- * Possible file size units.
- */
-enum size_unit {
-	/** 512-byte blocks. */
-	SIZE_BLOCKS,
-	/** Single bytes. */
-	SIZE_BYTES,
-	/** Two-byte words. */
-	SIZE_WORDS,
-	/** Kibibytes. */
-	SIZE_KB,
-	/** Mebibytes. */
-	SIZE_MB,
-	/** Gibibytes. */
-	SIZE_GB,
-	/** Tebibytes. */
-	SIZE_TB,
-	/** Pebibytes. */
-	SIZE_PB,
-};
-
-struct expr {
-	/** The function that evaluates this expression. */
-	eval_fn *eval;
-
-	/** The left hand side of the expression. */
-	struct expr *lhs;
-	/** The right hand side of the expression. */
-	struct expr *rhs;
-
-	/** Whether this expression has no side effects. */
-	bool pure;
-	/** Whether this expression always evaluates to true. */
-	bool always_true;
-	/** Whether this expression always evaluates to false. */
-	bool always_false;
-
-	/** Estimated cost. */
-	double cost;
-	/** Estimated probability of success. */
-	double probability;
-	/** Number of times this predicate was executed. */
-	size_t evaluations;
-	/** Number of times this predicate succeeded. */
-	size_t successes;
-	/** Total time spent running this predicate. */
-	struct timespec elapsed;
-
-	/** The number of command line arguments for this expression. */
-	size_t argc;
-	/** The command line arguments comprising this expression. */
-	char **argv;
-
-	/** The optional comparison flag. */
-	enum cmp_flag cmp_flag;
-
-	/** The mode comparison flag. */
-	enum mode_cmp mode_cmp;
-	/** Mode to use for files. */
-	mode_t file_mode;
-	/** Mode to use for directories (different due to X). */
-	mode_t dir_mode;
-
-	/** The optional reference time. */
-	struct timespec reftime;
-	/** The optional time field. */
-	enum time_field time_field;
-	/** The optional time unit. */
-	enum time_unit time_unit;
-
-	/** The optional size unit. */
-	enum size_unit size_unit;
-
-	/** Optional device number for a target file. */
-	dev_t dev;
-	/** Optional inode number for a target file. */
-	ino_t ino;
-
-	/** File to output to. */
-	CFILE *cfile;
-
-	/** Optional compiled regex. */
-	regex_t *regex;
-
-	/** Optional exec command. */
-	struct bfs_exec *execbuf;
-
-	/** Optional printf command. */
-	struct bfs_printf *printf;
-
-	/** Optional integer data for this expression. */
-	long long idata;
-
-	/** Optional string data for this expression. */
-	const char *sdata;
-};
-
-/**
- * @return Whether expr is known to always quit.
- */
-bool expr_never_returns(const struct expr *expr);
-
-/**
- * @return The result of the comparison for this expression.
- */
-bool expr_cmp(const struct expr *expr, long long n);
-
-/**
- * Parse the command line.
- */
-struct cmdline *parse_cmdline(int argc, char *argv[]);
-
-/**
- * Dump the parsed command line.
- */
-void dump_cmdline(const struct cmdline *cmdline, bool verbose);
-
-/**
- * Evaluate the command line.
- */
-int eval_cmdline(const struct cmdline *cmdline);
-
-/**
- * Free the parsed command line.
- */
-void free_cmdline(struct cmdline *cmdline);
-
-// Predicate evaluation functions
-bool eval_true(const struct expr *expr, struct eval_state *state);
-bool eval_false(const struct expr *expr, struct eval_state *state);
-
-bool eval_access(const struct expr *expr, struct eval_state *state);
-bool eval_perm(const struct expr *expr, struct eval_state *state);
-
-bool eval_acmtime(const struct expr *expr, struct eval_state *state);
-bool eval_acnewer(const struct expr *expr, struct eval_state *state);
-bool eval_used(const struct expr *expr, struct eval_state *state);
-
-bool eval_gid(const struct expr *expr, struct eval_state *state);
-bool eval_uid(const struct expr *expr, struct eval_state *state);
-bool eval_nogroup(const struct expr *expr, struct eval_state *state);
-bool eval_nouser(const struct expr *expr, struct eval_state *state);
-
-bool eval_depth(const struct expr *expr, struct eval_state *state);
-bool eval_empty(const struct expr *expr, struct eval_state *state);
-bool eval_fstype(const struct expr *expr, struct eval_state *state);
-bool eval_hidden(const struct expr *expr, struct eval_state *state);
-bool eval_inum(const struct expr *expr, struct eval_state *state);
-bool eval_links(const struct expr *expr, struct eval_state *state);
-bool eval_samefile(const struct expr *expr, struct eval_state *state);
-bool eval_size(const struct expr *expr, struct eval_state *state);
-bool eval_sparse(const struct expr *expr, struct eval_state *state);
-bool eval_type(const struct expr *expr, struct eval_state *state);
-bool eval_xtype(const struct expr *expr, struct eval_state *state);
-
-bool eval_lname(const struct expr *expr, struct eval_state *state);
-bool eval_name(const struct expr *expr, struct eval_state *state);
-bool eval_path(const struct expr *expr, struct eval_state *state);
-bool eval_regex(const struct expr *expr, struct eval_state *state);
-
-bool eval_delete(const struct expr *expr, struct eval_state *state);
-bool eval_exec(const struct expr *expr, struct eval_state *state);
-bool eval_exit(const struct expr *expr, struct eval_state *state);
-bool eval_nohidden(const struct expr *expr, struct eval_state *state);
-bool eval_fls(const struct expr *expr, struct eval_state *state);
-bool eval_fprint(const struct expr *expr, struct eval_state *state);
-bool eval_fprint0(const struct expr *expr, struct eval_state *state);
-bool eval_fprintf(const struct expr *expr, struct eval_state *state);
-bool eval_fprintx(const struct expr *expr, struct eval_state *state);
-bool eval_prune(const struct expr *expr, struct eval_state *state);
-bool eval_quit(const struct expr *expr, struct eval_state *state);
-
-// Operator evaluation functions
-bool eval_not(const struct expr *expr, struct eval_state *state);
-bool eval_and(const struct expr *expr, struct eval_state *state);
-bool eval_or(const struct expr *expr, struct eval_state *state);
-bool eval_comma(const struct expr *expr, struct eval_state *state);
-
 #endif // BFS_H
diff --git a/cmdline.h b/cmdline.h
new file mode 100644
index 0000000..a1dadc3
--- /dev/null
+++ b/cmdline.h
@@ -0,0 +1,123 @@
+/****************************************************************************
+ * bfs                                                                      *
+ * Copyright (C) 2015-2017 Tavian Barnes <tavianator@tavianator.com>        *
+ *                                                                          *
+ * Permission to use, copy, modify, and/or distribute this software for any *
+ * purpose with or without fee is hereby granted.                           *
+ *                                                                          *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES *
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF         *
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR  *
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES   *
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN    *
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF  *
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.           *
+ ****************************************************************************/
+
+#ifndef CMDLINE_H
+#define CMDLINE_H
+
+#include "color.h"
+
+/**
+ * Various debugging flags.
+ */
+enum debug_flags {
+	/** Print cost estimates. */
+	DEBUG_COST   = 1 << 0,
+	/** Print executed command details. */
+	DEBUG_EXEC   = 1 << 1,
+	/** Print optimization details. */
+	DEBUG_OPT    = 1 << 2,
+	/** Print rate information. */
+	DEBUG_RATES  = 1 << 3,
+	/** Trace the filesystem traversal. */
+	DEBUG_SEARCH = 1 << 4,
+	/** Trace all stat() calls. */
+	DEBUG_STAT   = 1 << 5,
+	/** Print the parse tree. */
+	DEBUG_TREE   = 1 << 6,
+};
+
+/**
+ * A root path to explore.
+ */
+struct root {
+	/** The root path itself. */
+	const char *path;
+	/** The next path in the list. */
+	struct root *next;
+};
+
+/**
+ * The parsed command line.
+ */
+struct cmdline {
+	/** The unparsed command line arguments. */
+	char **argv;
+
+	/** The list of root paths. */
+	struct root *roots;
+
+	/** Color data. */
+	struct colors *colors;
+	/** Colored stdout. */
+	CFILE *cout;
+	/** Colored stderr. */
+	CFILE *cerr;
+
+	/** Table of mounted file systems. */
+	struct bfs_mtab *mtab;
+
+	/** -mindepth option. */
+	int mindepth;
+	/** -maxdepth option. */
+	int maxdepth;
+
+	/** bftw() flags. */
+	enum bftw_flags flags;
+
+	/** Optimization level. */
+	int optlevel;
+	/** Debugging flags. */
+	enum debug_flags debug;
+	/** Whether to only handle paths with xargs-safe characters. */
+	bool xargs_safe;
+	/** Whether to ignore deletions that race with bfs. */
+	bool ignore_races;
+
+	/** The command line expression. */
+	struct expr *expr;
+
+	/** The number of open files used by the expression tree. */
+	int nopen_files;
+};
+
+/**
+ * Optimize the parsed command line.
+ *
+ * @return 0 if successful, -1 on error.
+ */
+int optimize_cmdline(struct cmdline *cmdline);
+
+/**
+ * Parse the command line.
+ */
+struct cmdline *parse_cmdline(int argc, char *argv[]);
+
+/**
+ * Dump the parsed command line.
+ */
+void dump_cmdline(const struct cmdline *cmdline, bool verbose);
+
+/**
+ * Evaluate the command line.
+ */
+int eval_cmdline(const struct cmdline *cmdline);
+
+/**
+ * Free the parsed command line.
+ */
+void free_cmdline(struct cmdline *cmdline);
+
+#endif // CMDLINE_H
diff --git a/eval.c b/eval.c
index 340e9eb..5196b57 100644
--- a/eval.c
+++ b/eval.c
@@ -14,11 +14,14 @@
  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.           *
  ****************************************************************************/
 
-#include "bfs.h"
+#include "eval.h"
 #include "bftw.h"
+#include "cmdline.h"
 #include "color.h"
 #include "dstring.h"
+#include "exec.h"
 #include "mtab.h"
+#include "printf.h"
 #include "util.h"
 #include <assert.h>
 #include <dirent.h>
diff --git a/eval.h b/eval.h
new file mode 100644
index 0000000..356f332
--- /dev/null
+++ b/eval.h
@@ -0,0 +1,73 @@
+/****************************************************************************
+ * bfs                                                                      *
+ * Copyright (C) 2015-2017 Tavian Barnes <tavianator@tavianator.com>        *
+ *                                                                          *
+ * Permission to use, copy, modify, and/or distribute this software for any *
+ * purpose with or without fee is hereby granted.                           *
+ *                                                                          *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES *
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF         *
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR  *
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES   *
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN    *
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF  *
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.           *
+ ****************************************************************************/
+
+#ifndef EVAL_H
+#define EVAL_H
+
+#include "expr.h"
+
+// Predicate evaluation functions
+bool eval_true(const struct expr *expr, struct eval_state *state);
+bool eval_false(const struct expr *expr, struct eval_state *state);
+
+bool eval_access(const struct expr *expr, struct eval_state *state);
+bool eval_perm(const struct expr *expr, struct eval_state *state);
+
+bool eval_acmtime(const struct expr *expr, struct eval_state *state);
+bool eval_acnewer(const struct expr *expr, struct eval_state *state);
+bool eval_used(const struct expr *expr, struct eval_state *state);
+
+bool eval_gid(const struct expr *expr, struct eval_state *state);
+bool eval_uid(const struct expr *expr, struct eval_state *state);
+bool eval_nogroup(const struct expr *expr, struct eval_state *state);
+bool eval_nouser(const struct expr *expr, struct eval_state *state);
+
+bool eval_depth(const struct expr *expr, struct eval_state *state);
+bool eval_empty(const struct expr *expr, struct eval_state *state);
+bool eval_fstype(const struct expr *expr, struct eval_state *state);
+bool eval_hidden(const struct expr *expr, struct eval_state *state);
+bool eval_inum(const struct expr *expr, struct eval_state *state);
+bool eval_links(const struct expr *expr, struct eval_state *state);
+bool eval_samefile(const struct expr *expr, struct eval_state *state);
+bool eval_size(const struct expr *expr, struct eval_state *state);
+bool eval_sparse(const struct expr *expr, struct eval_state *state);
+bool eval_type(const struct expr *expr, struct eval_state *state);
+bool eval_xtype(const struct expr *expr, struct eval_state *state);
+
+bool eval_lname(const struct expr *expr, struct eval_state *state);
+bool eval_name(const struct expr *expr, struct eval_state *state);
+bool eval_path(const struct expr *expr, struct eval_state *state);
+bool eval_regex(const struct expr *expr, struct eval_state *state);
+
+bool eval_delete(const struct expr *expr, struct eval_state *state);
+bool eval_exec(const struct expr *expr, struct eval_state *state);
+bool eval_exit(const struct expr *expr, struct eval_state *state);
+bool eval_nohidden(const struct expr *expr, struct eval_state *state);
+bool eval_fls(const struct expr *expr, struct eval_state *state);
+bool eval_fprint(const struct expr *expr, struct eval_state *state);
+bool eval_fprint0(const struct expr *expr, struct eval_state *state);
+bool eval_fprintf(const struct expr *expr, struct eval_state *state);
+bool eval_fprintx(const struct expr *expr, struct eval_state *state);
+bool eval_prune(const struct expr *expr, struct eval_state *state);
+bool eval_quit(const struct expr *expr, struct eval_state *state);
+
+// Operator evaluation functions
+bool eval_not(const struct expr *expr, struct eval_state *state);
+bool eval_and(const struct expr *expr, struct eval_state *state);
+bool eval_or(const struct expr *expr, struct eval_state *state);
+bool eval_comma(const struct expr *expr, struct eval_state *state);
+
+#endif // EVAL_H
diff --git a/exec.c b/exec.c
index 42deccf..4b34ab6 100644
--- a/exec.c
+++ b/exec.c
@@ -15,8 +15,8 @@
  ****************************************************************************/
 
 #include "exec.h"
-#include "bfs.h"
 #include "bftw.h"
+#include "cmdline.h"
 #include "color.h"
 #include "dstring.h"
 #include "util.h"
diff --git a/expr.h b/expr.h
new file mode 100644
index 0000000..0eba0da
--- /dev/null
+++ b/expr.h
@@ -0,0 +1,225 @@
+/****************************************************************************
+ * bfs                                                                      *
+ * Copyright (C) 2015-2017 Tavian Barnes <tavianator@tavianator.com>        *
+ *                                                                          *
+ * Permission to use, copy, modify, and/or distribute this software for any *
+ * purpose with or without fee is hereby granted.                           *
+ *                                                                          *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES *
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF         *
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR  *
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES   *
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN    *
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF  *
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.           *
+ ****************************************************************************/
+
+#ifndef EXPR_H
+#define EXPR_H
+
+#include "color.h"
+#include "exec.h"
+#include "printf.h"
+#include <regex.h>
+#include <stdbool.h>
+#include <stddef.h>
+#include <sys/types.h>
+#include <time.h>
+
+/**
+ * A command line expression.
+ */
+struct expr;
+
+/**
+ * Ephemeral state for evaluating an expression.
+ */
+struct eval_state;
+
+/**
+ * Expression evaluation function.
+ *
+ * @param expr
+ *         The current expression.
+ * @param state
+ *         The current evaluation state.
+ * @return
+ *         The result of the test.
+ */
+typedef bool eval_fn(const struct expr *expr, struct eval_state *state);
+
+/**
+ * Possible types of numeric comparison.
+ */
+enum cmp_flag {
+	/** Exactly n. */
+	CMP_EXACT,
+	/** Less than n. */
+	CMP_LESS,
+	/** Greater than n. */
+	CMP_GREATER,
+};
+
+/**
+ * Possible types of mode comparison.
+ */
+enum mode_cmp {
+	/** Mode is an exact match (MODE). */
+	MODE_EXACT,
+	/** Mode has all these bits (-MODE). */
+	MODE_ALL,
+	/** Mode has any of these bits (/MODE). */
+	MODE_ANY,
+};
+
+/**
+ * Available struct stat time fields.
+ */
+enum time_field {
+	/** Access time. */
+	ATIME,
+	/** Status change time. */
+	CTIME,
+	/** Modification time. */
+	MTIME,
+};
+
+/**
+ * Possible time units.
+ */
+enum time_unit {
+	/** Minutes. */
+	MINUTES,
+	/** Days. */
+	DAYS,
+};
+
+/**
+ * Possible file size units.
+ */
+enum size_unit {
+	/** 512-byte blocks. */
+	SIZE_BLOCKS,
+	/** Single bytes. */
+	SIZE_BYTES,
+	/** Two-byte words. */
+	SIZE_WORDS,
+	/** Kibibytes. */
+	SIZE_KB,
+	/** Mebibytes. */
+	SIZE_MB,
+	/** Gibibytes. */
+	SIZE_GB,
+	/** Tebibytes. */
+	SIZE_TB,
+	/** Pebibytes. */
+	SIZE_PB,
+};
+
+struct expr {
+	/** The function that evaluates this expression. */
+	eval_fn *eval;
+
+	/** The left hand side of the expression. */
+	struct expr *lhs;
+	/** The right hand side of the expression. */
+	struct expr *rhs;
+
+	/** Whether this expression has no side effects. */
+	bool pure;
+	/** Whether this expression always evaluates to true. */
+	bool always_true;
+	/** Whether this expression always evaluates to false. */
+	bool always_false;
+
+	/** Estimated cost. */
+	double cost;
+	/** Estimated probability of success. */
+	double probability;
+	/** Number of times this predicate was executed. */
+	size_t evaluations;
+	/** Number of times this predicate succeeded. */
+	size_t successes;
+	/** Total time spent running this predicate. */
+	struct timespec elapsed;
+
+	/** The number of command line arguments for this expression. */
+	size_t argc;
+	/** The command line arguments comprising this expression. */
+	char **argv;
+
+	/** The optional comparison flag. */
+	enum cmp_flag cmp_flag;
+
+	/** The mode comparison flag. */
+	enum mode_cmp mode_cmp;
+	/** Mode to use for files. */
+	mode_t file_mode;
+	/** Mode to use for directories (different due to X). */
+	mode_t dir_mode;
+
+	/** The optional reference time. */
+	struct timespec reftime;
+	/** The optional time field. */
+	enum time_field time_field;
+	/** The optional time unit. */
+	enum time_unit time_unit;
+
+	/** The optional size unit. */
+	enum size_unit size_unit;
+
+	/** Optional device number for a target file. */
+	dev_t dev;
+	/** Optional inode number for a target file. */
+	ino_t ino;
+
+	/** File to output to. */
+	CFILE *cfile;
+
+	/** Optional compiled regex. */
+	regex_t *regex;
+
+	/** Optional exec command. */
+	struct bfs_exec *execbuf;
+
+	/** Optional printf command. */
+	struct bfs_printf *printf;
+
+	/** Optional integer data for this expression. */
+	long long idata;
+
+	/** Optional string data for this expression. */
+	const char *sdata;
+};
+
+/** Singleton true expression instance. */
+extern struct expr expr_true;
+/** Singleton false expression instance. */
+extern struct expr expr_false;
+
+/**
+ * Create a new expression.
+ */
+struct expr *new_expr(eval_fn *eval, size_t argc, char **argv);
+
+/**
+ * @return Whether expr is known to always quit.
+ */
+bool expr_never_returns(const struct expr *expr);
+
+/**
+ * @return The result of the comparison for this expression.
+ */
+bool expr_cmp(const struct expr *expr, long long n);
+
+/**
+ * Dump a parsed expression.
+ */
+void dump_expr(CFILE *cfile, const struct expr *expr, bool verbose);
+
+/**
+ * Free an expression tree.
+ */
+void free_expr(struct expr *expr);
+
+#endif // EXPR_H
diff --git a/main.c b/main.c
index b5b9a99..9e8fdbf 100644
--- a/main.c
+++ b/main.c
@@ -14,7 +14,7 @@
  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.           *
  ****************************************************************************/
 
-#include "bfs.h"
+#include "cmdline.h"
 #include "util.h"
 #include <errno.h>
 #include <fcntl.h>
diff --git a/opt.c b/opt.c
new file mode 100644
index 0000000..8074172
--- /dev/null
+++ b/opt.c
@@ -0,0 +1,410 @@
+/****************************************************************************
+ * bfs                                                                      *
+ * Copyright (C) 2017 Tavian Barnes <tavianator@tavianator.com>             *
+ *                                                                          *
+ * Permission to use, copy, modify, and/or distribute this software for any *
+ * purpose with or without fee is hereby granted.                           *
+ *                                                                          *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES *
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF         *
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR  *
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES   *
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN    *
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF  *
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.           *
+ ****************************************************************************/
+
+#include "cmdline.h"
+#include "color.h"
+#include "eval.h"
+#include "expr.h"
+#include <assert.h>
+#include <stdarg.h>
+#include <stdio.h>
+
+static char *fake_and_arg = "-a";
+static char *fake_or_arg = "-o";
+
+/**
+ * Log an optimization.
+ */
+static void debug_opt(const struct cmdline *cmdline, const char *format, ...) {
+	if (!(cmdline->debug & DEBUG_OPT)) {
+		return;
+	}
+
+	CFILE *cerr = cmdline->cerr;
+
+	va_list args;
+	va_start(args, format);
+
+	for (const char *i = format; *i != '\0'; ++i) {
+		if (*i == '%') {
+			switch (*++i) {
+			case 'e':
+				dump_expr(cerr, va_arg(args, const struct expr *), false);
+				break;
+
+			case 'g':
+				cfprintf(cerr, "%{ylw}%g%{rs}", va_arg(args, double));
+				break;
+			}
+		} else {
+			fputc(*i, stderr);
+		}
+	}
+
+	va_end(args);
+}
+
+/**
+ * Extract a child expression, freeing the outer expression.
+ */
+static struct expr *extract_child_expr(struct expr *expr, struct expr **child) {
+	struct expr *ret = *child;
+	*child = NULL;
+	free_expr(expr);
+	return ret;
+}
+
+/**
+ * Negate an expression.
+ */
+static struct expr *negate_expr(struct expr *rhs, char **argv) {
+	if (rhs->eval == eval_not) {
+		return extract_child_expr(rhs, &rhs->rhs);
+	}
+
+	struct expr *expr = new_expr(eval_not, 1, argv);
+	if (!expr) {
+		free_expr(rhs);
+		return NULL;
+	}
+
+	expr->rhs = rhs;
+	return expr;
+}
+
+static struct expr *optimize_not_expr(const struct cmdline *cmdline, struct expr *expr);
+static struct expr *optimize_and_expr(const struct cmdline *cmdline, struct expr *expr);
+static struct expr *optimize_or_expr(const struct cmdline *cmdline, struct expr *expr);
+
+/**
+ * Apply De Morgan's laws.
+ */
+static struct expr *de_morgan(const struct cmdline *cmdline, struct expr *expr, char **argv) {
+	debug_opt(cmdline, "-O1: De Morgan's laws: %e ", expr);
+
+	struct expr *parent = negate_expr(expr, argv);
+	if (!parent) {
+		return NULL;
+	}
+
+	bool has_parent = true;
+	if (parent->eval != eval_not) {
+		expr = parent;
+		has_parent = false;
+	}
+
+	if (expr->eval == eval_and) {
+		expr->eval = eval_or;
+		expr->argv = &fake_or_arg;
+	} else {
+		assert(expr->eval == eval_or);
+		expr->eval = eval_and;
+		expr->argv = &fake_and_arg;
+	}
+
+	expr->lhs = negate_expr(expr->lhs, argv);
+	expr->rhs = negate_expr(expr->rhs, argv);
+	if (!expr->lhs || !expr->rhs) {
+		free_expr(parent);
+		return NULL;
+	}
+
+	debug_opt(cmdline, "<==> %e\n", parent);
+
+	if (expr->lhs->eval == eval_not) {
+		expr->lhs = optimize_not_expr(cmdline, expr->lhs);
+	}
+	if (expr->rhs->eval == eval_not) {
+		expr->rhs = optimize_not_expr(cmdline, expr->rhs);
+	}
+	if (!expr->lhs || !expr->rhs) {
+		free_expr(parent);
+		return NULL;
+	}
+
+	if (expr->eval == eval_and) {
+		expr = optimize_and_expr(cmdline, expr);
+	} else {
+		expr = optimize_or_expr(cmdline, expr);
+	}
+	if (!expr) {
+		if (has_parent) {
+			parent->rhs = NULL;
+			free_expr(parent);
+		}
+		return NULL;
+	}
+
+	if (has_parent) {
+		parent = optimize_not_expr(cmdline, parent);
+	}
+	return parent;
+}
+
+/**
+ * Optimize a negation.
+ */
+static struct expr *optimize_not_expr(const struct cmdline *cmdline, struct expr *expr) {
+	assert(expr->eval == eval_not && !expr->lhs && expr->rhs);
+
+	struct expr *rhs = expr->rhs;
+
+	int optlevel = cmdline->optlevel;
+	if (optlevel >= 1) {
+		if (rhs == &expr_true) {
+			debug_opt(cmdline, "-O1: constant propagation: %e <==> %e\n", expr, &expr_false);
+			free_expr(expr);
+			return &expr_false;
+		} else if (rhs == &expr_false) {
+			debug_opt(cmdline, "-O1: constant propagation: %e <==> %e\n", expr, &expr_true);
+			free_expr(expr);
+			return &expr_true;
+		} else if (rhs->eval == eval_not) {
+			debug_opt(cmdline, "-O1: double negation: %e <==> %e\n", expr, rhs->rhs);
+			return extract_child_expr(expr, &rhs->rhs);
+		} else if (expr_never_returns(rhs)) {
+			debug_opt(cmdline, "-O1: reachability: %e <==> %e\n", expr, rhs);
+			return extract_child_expr(expr, &expr->rhs);
+		} else if ((rhs->eval == eval_and || rhs->eval == eval_or)
+			   && (rhs->lhs->eval == eval_not || rhs->rhs->eval == eval_not)) {
+			return de_morgan(cmdline, expr, expr->argv);
+		}
+	}
+
+	expr->pure = rhs->pure;
+	expr->always_true = rhs->always_false;
+	expr->always_false = rhs->always_true;
+	expr->cost = rhs->cost;
+	expr->probability = 1.0 - rhs->probability;
+
+	return expr;
+}
+
+/**
+ * Optimize a conjunction.
+ */
+static struct expr *optimize_and_expr(const struct cmdline *cmdline, struct expr *expr) {
+	assert(expr->eval == eval_and && expr->lhs && expr->rhs);
+
+	struct expr *lhs = expr->lhs;
+	struct expr *rhs = expr->rhs;
+
+	int optlevel = cmdline->optlevel;
+	if (optlevel >= 1) {
+		if (lhs == &expr_true) {
+			debug_opt(cmdline, "-O1: conjunction elimination: %e <==> %e\n", expr, rhs);
+			return extract_child_expr(expr, &expr->rhs);
+		} else if (rhs == &expr_true) {
+			debug_opt(cmdline, "-O1: conjunction elimination: %e <==> %e\n", expr, lhs);
+			return extract_child_expr(expr, &expr->lhs);
+		} else if (lhs->always_false) {
+			debug_opt(cmdline, "-O1: short-circuit: %e <==> %e\n", expr, lhs);
+			return extract_child_expr(expr, &expr->lhs);
+		} else if (optlevel >= 2 && lhs->pure && rhs == &expr_false) {
+			debug_opt(cmdline, "-O2: purity: %e <==> %e\n", expr, rhs);
+			return extract_child_expr(expr, &expr->rhs);
+		} else if (lhs->eval == eval_not && rhs->eval == eval_not) {
+			return de_morgan(cmdline, expr, expr->lhs->argv);
+		}
+	}
+
+	expr->pure = lhs->pure && rhs->pure;
+	expr->always_true = lhs->always_true && rhs->always_true;
+	expr->always_false = lhs->always_false || rhs->always_false;
+	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(cmdline, "-O3: cost: %e", expr);
+			expr->lhs = rhs;
+			expr->rhs = lhs;
+			debug_opt(cmdline, " <==> %e (~%g --> ~%g)\n", expr, expr->cost, swapped_cost);
+			expr->cost = swapped_cost;
+		}
+	}
+
+	return expr;
+}
+
+/**
+ * Optimize a disjunction.
+ */
+static struct expr *optimize_or_expr(const struct cmdline *cmdline, struct expr *expr) {
+	assert(expr->eval == eval_or && expr->lhs && expr->rhs);
+
+	struct expr *lhs = expr->lhs;
+	struct expr *rhs = expr->rhs;
+
+	int optlevel = cmdline->optlevel;
+	if (optlevel >= 1) {
+		if (lhs->always_true) {
+			debug_opt(cmdline, "-O1: short-circuit: %e <==> %e\n", expr, lhs);
+			return extract_child_expr(expr, &expr->lhs);
+		} else if (lhs == &expr_false) {
+			debug_opt(cmdline, "-O1: disjunctive syllogism: %e <==> %e\n", expr, rhs);
+			return extract_child_expr(expr, &expr->rhs);
+		} else if (rhs == &expr_false) {
+			debug_opt(cmdline, "-O1: disjunctive syllogism: %e <==> %e\n", expr, lhs);
+			return extract_child_expr(expr, &expr->lhs);
+		} else if (optlevel >= 2 && lhs->pure && rhs == &expr_true) {
+			debug_opt(cmdline, "-O2: purity: %e <==> %e\n", expr, rhs);
+			return extract_child_expr(expr, &expr->rhs);
+		} else if (lhs->eval == eval_not && rhs->eval == eval_not) {
+			return de_morgan(cmdline, expr, expr->lhs->argv);
+		}
+	}
+
+	expr->pure = lhs->pure && rhs->pure;
+	expr->always_true = lhs->always_true || rhs->always_true;
+	expr->always_false = lhs->always_false && rhs->always_false;
+	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(cmdline, "-O3: cost: %e", expr);
+			expr->lhs = rhs;
+			expr->rhs = lhs;
+			debug_opt(cmdline, " <==> %e (~%g --> ~%g)\n", expr, expr->cost, swapped_cost);
+			expr->cost = swapped_cost;
+		}
+	}
+
+	return expr;
+}
+
+/**
+ * Optimize an expression in an ignored-result context.
+ */
+static struct expr *ignore_result(const struct cmdline *cmdline, struct expr *expr) {
+	int optlevel = cmdline->optlevel;
+
+	if (optlevel >= 1) {
+		while (true) {
+			if (expr->eval == eval_not) {
+				debug_opt(cmdline, "-O1: ignored result: %e --> %e\n", expr, expr->rhs);
+				expr = extract_child_expr(expr, &expr->rhs);
+			} else if (optlevel >= 2
+			           && (expr->eval == eval_and || expr->eval == eval_or || expr->eval == eval_comma)
+			           && expr->rhs->pure) {
+				debug_opt(cmdline, "-O2: ignored result: %e --> %e\n", expr, expr->lhs);
+				expr = extract_child_expr(expr, &expr->lhs);
+			} else {
+				break;
+			}
+		}
+	}
+
+	return expr;
+}
+
+/**
+ * Optimize a comma expression.
+ */
+static struct expr *optimize_comma_expr(const struct cmdline *cmdline, struct expr *expr) {
+	struct expr *lhs = expr->lhs;
+	struct expr *rhs = expr->rhs;
+
+	int optlevel = cmdline->optlevel;
+	if (optlevel >= 1) {
+		lhs = expr->lhs = ignore_result(cmdline, lhs);
+
+		if (expr_never_returns(lhs)) {
+			debug_opt(cmdline, "-O1: reachability: %e <==> %e\n", expr, lhs);
+			return extract_child_expr(expr, &expr->lhs);
+		}
+
+		if (optlevel >= 2 && lhs->pure) {
+			debug_opt(cmdline, "-O2: purity: %e <==> %e\n", expr, rhs);
+			return extract_child_expr(expr, &expr->rhs);
+		}
+	}
+
+	expr->pure = lhs->pure && rhs->pure;
+	expr->always_true = expr_never_returns(lhs) || rhs->always_true;
+	expr->always_false = expr_never_returns(lhs) || rhs->always_false;
+	expr->cost = lhs->cost + rhs->cost;
+	expr->probability = rhs->probability;
+
+	return expr;
+}
+
+/**
+ * Optimize an expression.
+ */
+static struct expr *optimize_expr(const struct cmdline *cmdline, struct expr *expr) {
+	if (expr->lhs) {
+		expr->lhs = optimize_expr(cmdline, expr->lhs);
+		if (!expr->lhs) {
+			goto fail;
+		}
+	}
+
+	if (expr->rhs) {
+		expr->rhs = optimize_expr(cmdline, expr->rhs);
+		if (!expr->rhs) {
+			goto fail;
+		}
+	}
+
+	if (expr->eval == eval_not) {
+		return optimize_not_expr(cmdline, expr);
+	} else if (expr->eval == eval_and) {
+		return optimize_and_expr(cmdline, expr);
+	} else if (expr->eval == eval_or) {
+		return optimize_or_expr(cmdline, expr);
+	} else if (expr->eval == eval_comma) {
+		return optimize_comma_expr(cmdline, expr);
+	} else {
+		return expr;
+	}
+
+fail:
+	free_expr(expr);
+	return NULL;
+}
+
+/**
+ * Apply top-level optimizations.
+ */
+static struct expr *optimize_whole_expr(const struct cmdline *cmdline, struct expr *expr) {
+	expr = optimize_expr(cmdline, expr);
+	if (!expr) {
+		return NULL;
+	}
+
+	expr = ignore_result(cmdline, expr);
+
+	if (cmdline->optlevel >= 4 && expr->pure && expr != &expr_false) {
+		debug_opt(cmdline, "-O4: top-level purity: %e --> %e\n", expr, &expr_false);
+		free_expr(expr);
+		expr = &expr_false;
+	}
+
+	return expr;
+}
+
+int optimize_cmdline(struct cmdline *cmdline) {
+	cmdline->expr = optimize_whole_expr(cmdline, cmdline->expr);
+	if (cmdline->expr) {
+		return 0;
+	} else {
+		return -1;
+	}
+}
diff --git a/parse.c b/parse.c
index f6cde7a..2e77b10 100644
--- a/parse.c
+++ b/parse.c
@@ -15,8 +15,12 @@
  ****************************************************************************/
 
 #include "bfs.h"
+#include "cmdline.h"
 #include "dstring.h"
+#include "eval.h"
 #include "exec.h"
+#include "expr.h"
+#include "mtab.h"
 #include "printf.h"
 #include "typo.h"
 #include "util.h"
@@ -41,7 +45,6 @@
 // Strings printed by -D tree for "fake" expressions
 static char *fake_and_arg = "-a";
 static char *fake_false_arg = "-false";
-static char *fake_or_arg = "-o";
 static char *fake_print_arg = "-print";
 static char *fake_true_arg = "-true";
 
@@ -50,10 +53,7 @@ static char *fake_true_arg = "-true";
 #define STAT_COST   1000.0
 #define PRINT_COST 20000.0
 
-/**
- * Singleton true expression instance.
- */
-static struct expr expr_true = {
+struct expr expr_true = {
 	.eval = eval_true,
 	.lhs = NULL,
 	.rhs = NULL,
@@ -65,10 +65,7 @@ static struct expr expr_true = {
 	.argv = &fake_true_arg,
 };
 
-/**
- * Singleton false expression instance.
- */
-static struct expr expr_false = {
+struct expr expr_false = {
 	.eval = eval_false,
 	.lhs = NULL,
 	.rhs = NULL,
@@ -83,7 +80,7 @@ static struct expr expr_false = {
 /**
  * Free an expression.
  */
-static void free_expr(struct expr *expr) {
+void free_expr(struct expr *expr) {
 	if (expr && expr != &expr_true && expr != &expr_false) {
 		if (expr->cfile && expr->cfile->close) {
 			if (cfclose(expr->cfile) != 0) {
@@ -105,11 +102,8 @@ static void free_expr(struct expr *expr) {
 	}
 }
 
-/**
- * Create a new expression.
- */
-static struct expr *new_expr(eval_fn *eval, size_t argc, char **argv) {
-	struct expr *expr = malloc(sizeof(struct expr));
+struct expr *new_expr(eval_fn *eval, size_t argc, char **argv) {
+	struct expr *expr = malloc(sizeof(*expr));
 	if (!expr) {
 		perror("malloc()");
 		return NULL;
@@ -192,7 +186,7 @@ static void expr_set_never_returns(struct expr *expr) {
 /**
  * Dump the parsed expression tree, for debugging.
  */
-static void dump_expr(CFILE *cfile, const struct expr *expr, bool verbose) {
+void dump_expr(CFILE *cfile, const struct expr *expr, bool verbose) {
 	fputs("(", cfile->file);
 
 	if (expr->lhs || expr->rhs) {
@@ -320,46 +314,6 @@ enum token_type {
 };
 
 /**
- * Log an optimization.
- */
-static void debug_opt(const struct parser_state *state, const char *format, ...) {
-	if (!(state->cmdline->debug & DEBUG_OPT)) {
-		return;
-	}
-
-	CFILE *cerr = state->cmdline->cerr;
-
-	va_list args;
-	va_start(args, format);
-
-	for (const char *i = format; *i != '\0'; ++i) {
-		if (*i == '%') {
-			switch (*++i) {
-			case '%':
-				fputc('%', stderr);
-				break;
-
-			case 'e':
-				dump_expr(cerr, va_arg(args, const struct expr *), false);
-				break;
-
-			case 'g':
-				cfprintf(cerr, "%{ylw}%g%{rs}", va_arg(args, double));
-				break;
-
-			case 's':
-				cfprintf(cerr, "%{red}%s%{rs}", va_arg(args, const char *));
-				break;
-			}
-		} else {
-			fputc(*i, stderr);
-		}
-	}
-
-	va_end(args);
-}
-
-/**
  * Fill in a "-print"-type expression.
  */
 static void init_print_expr(struct parser_state *state, struct expr *expr) {
@@ -2578,76 +2532,6 @@ unexpected:
 	return NULL;
 }
 
-static struct expr *new_and_expr(const struct parser_state *state, struct expr *lhs, struct expr *rhs, char **argv);
-static struct expr *new_or_expr(const struct parser_state *state, struct expr *lhs, struct expr *rhs, char **argv);
-
-/**
- * Extract a child expression, freeing the outer expression.
- */
-static struct expr *extract_child_expr(struct expr *expr, struct expr **child) {
-	struct expr *ret = *child;
-	*child = NULL;
-	free_expr(expr);
-	return ret;
-}
-
-/**
- * Create a "not" expression.
- */
-static struct expr *new_not_expr(const struct parser_state *state, struct expr *rhs, char **argv) {
-	int optlevel = state->cmdline->optlevel;
-	if (optlevel >= 1) {
-		if (rhs == &expr_true) {
-			debug_opt(state, "-O1: constant propagation: (%s %e) <==> %e\n", argv[0], rhs, &expr_false);
-			return &expr_false;
-		} else if (rhs == &expr_false) {
-			debug_opt(state, "-O1: constant propagation: (%s %e) <==> %e\n", argv[0], rhs, &expr_true);
-			return &expr_true;
-		} else if (expr_never_returns(rhs)) {
-			debug_opt(state, "-O1: reachability: (%s %e) <==> %e\n", argv[0], rhs, rhs);
-			return rhs;
-		} else if (rhs->eval == eval_not) {
-			debug_opt(state, "-O1: double negation: (%s %e) <==> %e\n", argv[0], rhs, rhs->rhs);
-			return extract_child_expr(rhs, &rhs->rhs);
-		} else if ((rhs->eval == eval_and || rhs->eval == eval_or)
-			   && (rhs->lhs->eval == eval_not || rhs->rhs->eval == eval_not)) {
-			bool other_and = rhs->eval == eval_or;
-			char **other_arg = other_and ? &fake_and_arg : &fake_or_arg;
-
-			debug_opt(state, "-O1: De Morgan's laws: (%s %e) <==> (%s (%s %e) (%s %e))\n",
-				  argv[0], rhs,
-				  *other_arg, argv[0], rhs->lhs, argv[0], rhs->rhs);
-
-			struct expr *other_lhs = new_not_expr(state, rhs->lhs, argv);
-			struct expr *other_rhs = new_not_expr(state, rhs->rhs, argv);
-			rhs->rhs = NULL;
-			rhs->lhs = NULL;
-			free_expr(rhs);
-			if (!other_lhs || !other_rhs) {
-				free_expr(other_rhs);
-				free_expr(other_lhs);
-				return NULL;
-			}
-
-			if (other_and) {
-				return new_and_expr(state, other_lhs, other_rhs, other_arg);
-			} else {
-				return new_or_expr(state, other_lhs, other_rhs, other_arg);
-			}
-		}
-	}
-
-	struct expr *expr = new_unary_expr(eval_not, rhs, argv);
-	if (expr) {
-		expr->pure = rhs->pure;
-		expr->always_true = rhs->always_false;
-		expr->always_false = rhs->always_true;
-		expr->cost = rhs->cost;
-		expr->probability = 1.0 - rhs->probability;
-	}
-	return expr;
-}
-
 /**
  * FACTOR : "(" EXPR ")"
  *        | "!" FACTOR | "-not" FACTOR
@@ -2696,76 +2580,13 @@ static struct expr *parse_factor(struct parser_state *state) {
 			return NULL;
 		}
 
-		return new_not_expr(state, factor, argv);
+		return new_unary_expr(eval_not, factor, argv);
 	} else {
 		return parse_literal(state);
 	}
 }
 
 /**
- * Create an "and" expression.
- */
-static struct expr *new_and_expr(const struct parser_state *state, struct expr *lhs, struct expr *rhs, char **argv) {
-	int optlevel = state->cmdline->optlevel;
-	if (optlevel >= 1) {
-		if (lhs == &expr_true) {
-			debug_opt(state, "-O1: conjunction elimination: (%s %e %e) <==> %e\n", argv[0], lhs, rhs, rhs);
-			return rhs;
-		} else if (rhs == &expr_true) {
-			debug_opt(state, "-O1: conjunction elimination: (%s %e %e) <==> %e\n", argv[0], lhs, rhs, lhs);
-			return lhs;
-		} else if (lhs->always_false) {
-			debug_opt(state, "-O1: short-circuit: (%s %e %e) <==> %e\n", argv[0], lhs, rhs, lhs);
-			free_expr(rhs);
-			return lhs;
-		} else if (optlevel >= 2 && lhs->pure && rhs == &expr_false) {
-			debug_opt(state, "-O2: purity: (%s %e %e) <==> %e\n", argv[0], lhs, rhs, rhs);
-			free_expr(lhs);
-			return rhs;
-		} else if (lhs->eval == eval_not && rhs->eval == eval_not) {
-			char **not_arg = lhs->argv;
-			debug_opt(state, "-O1: De Morgan's laws: (%s %e %e) <==> (%s (%s %e %e))\n",
-			          argv[0], lhs, rhs,
-				  *not_arg, fake_or_arg, lhs->rhs, rhs->rhs);
-
-			lhs = extract_child_expr(lhs, &lhs->rhs);
-			rhs = extract_child_expr(rhs, &rhs->rhs);
-
-			struct expr *or_expr = new_or_expr(state, lhs, rhs, &fake_or_arg);
-			if (!or_expr) {
-				return NULL;
-			}
-
-			return new_not_expr(state, or_expr, not_arg);
-		}
-	}
-
-	struct expr *expr = new_binary_expr(eval_and, lhs, rhs, argv);
-	if (!expr) {
-		return NULL;
-	}
-
-	expr->pure = lhs->pure && rhs->pure;
-	expr->always_true = lhs->always_true && rhs->always_true;
-	expr->always_false = lhs->always_false || rhs->always_false;
-	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 <==> (%s %e %e) (~%g --> ~%g)\n",
-			          expr, argv[0], rhs, lhs, expr->cost, swapped_cost);
-			expr->cost = swapped_cost;
-			expr->lhs = rhs;
-			expr->rhs = lhs;
-		}
-	}
-
-	return expr;
-}
-
-/**
  * TERM : FACTOR
  *      | TERM FACTOR
  *      | TERM "-a" FACTOR
@@ -2803,77 +2624,13 @@ static struct expr *parse_term(struct parser_state *state) {
 			return NULL;
 		}
 
-		term = new_and_expr(state, lhs, rhs, argv);
+		term = new_binary_expr(eval_and, lhs, rhs, argv);
 	}
 
 	return term;
 }
 
 /**
- * Create an "or" expression.
- */
-static struct expr *new_or_expr(const struct parser_state *state, struct expr *lhs, struct expr *rhs, char **argv) {
-	int optlevel = state->cmdline->optlevel;
-	if (optlevel >= 1) {
-		if (lhs->always_true) {
-			debug_opt(state, "-O1: short-circuit: (%s %e %e) <==> %e\n", argv[0], lhs, rhs, lhs);
-			free_expr(rhs);
-			return lhs;
-		} else if (lhs == &expr_false) {
-			debug_opt(state, "-O1: disjunctive syllogism: (%s %e %e) <==> %e\n", argv[0], lhs, rhs, rhs);
-			return rhs;
-		} else if (rhs == &expr_false) {
-			debug_opt(state, "-O1: disjunctive syllogism: (%s %e %e) <==> %e\n", argv[0], lhs, rhs, lhs);
-			return lhs;
-		} else if (optlevel >= 2 && lhs->pure && rhs == &expr_true) {
-			debug_opt(state, "-O2: purity: (%s %e %e) <==> %e\n", argv[0], lhs, rhs, rhs);
-			free_expr(lhs);
-			return rhs;
-		} else if (lhs->eval == eval_not && rhs->eval == eval_not) {
-			char **not_arg = lhs->argv;
-			debug_opt(state, "-O1: De Morgan's laws: (%s %e %e) <==> (%s (%s %e %e))\n",
-			          argv[0], lhs, rhs,
-				  *not_arg, fake_and_arg, lhs->rhs, rhs->rhs);
-
-			lhs = extract_child_expr(lhs, &lhs->rhs);
-			rhs = extract_child_expr(rhs, &rhs->rhs);
-
-			struct expr *and_expr = new_and_expr(state, lhs, rhs, &fake_and_arg);
-			if (!and_expr) {
-				return NULL;
-			}
-
-			return new_not_expr(state, and_expr, not_arg);
-		}
-	}
-
-	struct expr *expr = new_binary_expr(eval_or, lhs, rhs, argv);
-	if (!expr) {
-		return NULL;
-	}
-
-	expr->pure = lhs->pure && rhs->pure;
-	expr->always_true = lhs->always_true || rhs->always_true;
-	expr->always_false = lhs->always_false && rhs->always_false;
-	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 <==> (%s %e %e) (~%g --> ~%g)\n",
-			          expr, argv[0], rhs, lhs, expr->cost, swapped_cost);
-			expr->cost = swapped_cost;
-			expr->lhs = rhs;
-			expr->rhs = lhs;
-		}
-
-	}
-
-	return expr;
-}
-
-/**
  * CLAUSE : TERM
  *        | CLAUSE "-o" TERM
  *        | CLAUSE "-or" TERM
@@ -2905,50 +2662,13 @@ static struct expr *parse_clause(struct parser_state *state) {
 			return NULL;
 		}
 
-		clause = new_or_expr(state, lhs, rhs, argv);
+		clause = new_binary_expr(eval_or, lhs, rhs, argv);
 	}
 
 	return clause;
 }
 
 /**
- * Create a "comma" expression.
- */
-static struct expr *new_comma_expr(const struct parser_state *state, struct expr *lhs, struct expr *rhs, char **argv) {
-	int optlevel = state->cmdline->optlevel;
-	if (optlevel >= 1) {
-		if (lhs->eval == eval_not) {
-			debug_opt(state, "-O1: ignored result: (%s %e %e) <==> (%s %e %e)\n",
-			          argv[0], lhs, rhs,
-				  argv[0], lhs->rhs, rhs);
-			lhs = extract_child_expr(lhs, &lhs->rhs);
-		}
-
-		if (expr_never_returns(lhs)) {
-			debug_opt(state, "-O1: reachability: (%s %e %e) <==> %e\n", argv[0], lhs, rhs, lhs);
-			free_expr(rhs);
-			return lhs;
-		}
-
-		if (optlevel >= 2 && lhs->pure) {
-			debug_opt(state, "-O2: purity: (%s %e %e) <==> %e\n", argv[0], lhs, rhs, rhs);
-			free_expr(lhs);
-			return rhs;
-		}
-	}
-
-	struct expr *expr = new_binary_expr(eval_comma, lhs, rhs, argv);
-	if (expr) {
-		expr->pure = lhs->pure && rhs->pure;
-		expr->always_true = expr_never_returns(lhs) || rhs->always_true;
-		expr->always_false = expr_never_returns(lhs) || rhs->always_false;
-		expr->cost = lhs->cost + rhs->cost;
-		expr->probability = rhs->probability;
-	}
-	return expr;
-}
-
-/**
  * EXPR : CLAUSE
  *      | EXPR "," CLAUSE
  */
@@ -2979,38 +2699,7 @@ static struct expr *parse_expr(struct parser_state *state) {
 			return NULL;
 		}
 
-		expr = new_comma_expr(state, lhs, rhs, argv);
-	}
-
-	return expr;
-}
-
-/**
- * Apply top-level optimizations.
- */
-static struct expr *optimize_whole_expr(const struct parser_state *state, struct expr *expr) {
-	int optlevel = state->cmdline->optlevel;
-
-	if (optlevel >= 1) {
-		while (true) {
-			if (expr->eval == eval_not) {
-				debug_opt(state, "-O1: ignored result: %e --> %e\n", expr, expr->rhs);
-				expr = extract_child_expr(expr, &expr->rhs);
-			} else if (optlevel >= 2
-			           && (expr->eval == eval_and || expr->eval == eval_or || expr->eval == eval_comma)
-			           && expr->rhs->pure) {
-				debug_opt(state, "-O2: ignored result: %e --> %e\n", expr, expr->lhs);
-				expr = extract_child_expr(expr, &expr->lhs);
-			} else {
-				break;
-			}
-		}
-	}
-
-	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;
+		expr = new_binary_expr(eval_comma, lhs, rhs, argv);
 	}
 
 	return expr;
@@ -3046,14 +2735,12 @@ static struct expr *parse_whole_expr(struct parser_state *state) {
 		}
 		init_print_expr(state, print);
 
-		expr = new_and_expr(state, expr, print, &fake_and_arg);
+		expr = new_binary_expr(eval_and, expr, print, &fake_and_arg);
 		if (!expr) {
 			goto fail;
 		}
 	}
 
-	expr = optimize_whole_expr(state, expr);
-
 	if (state->warn && state->depth_arg && state->prune_arg) {
 		cfprintf(cerr, "%{wr}warning: %s does not work in the presence of %s.%{rs}\n", state->prune_arg, state->depth_arg);
 
@@ -3252,6 +2939,10 @@ struct cmdline *parse_cmdline(int argc, char *argv[]) {
 		}
 	}
 
+	if (optimize_cmdline(cmdline) != 0) {
+		goto fail;
+	}
+
 	if (!cmdline->roots) {
 		if (parse_root(&state, ".") != 0) {
 			goto fail;
diff --git a/printf.c b/printf.c
index da3f851..3c32108 100644
--- a/printf.c
+++ b/printf.c
@@ -15,9 +15,10 @@
  ****************************************************************************/
 
 #include "printf.h"
-#include "bfs.h"
+#include "cmdline.h"
 #include "color.h"
 #include "dstring.h"
+#include "expr.h"
 #include "mtab.h"
 #include "util.h"
 #include <assert.h>