opt: Use more standard terminology for data flow domains

1 files changed, 294 insertions, 298 deletions

diff --git a/src/opt.c b/src/opt.c
index ddcd1ab..a989670 100644
--- a/src/opt.c
+++ b/src/opt.c
@@ -6,14 +6,13 @@
  *
  * -O1: basic logical simplifications, like folding (-true -and -foo) to -foo.
  *
- * -O2: dead code elimination and data flow analysis.  struct opt_facts is used
+ * -O2: dead code elimination and data flow analysis.  struct df_domain is used
  * to record data flow facts that are true at various points of evaluation.
- * Specifically, struct opt_facts records the facts that must be true before an
- * expression is evaluated (state->facts), and those that must be true after the
- * expression is evaluated, given that it returns true (state->facts_when_true)
- * or false (state->facts_when_true).  Additionally, state->facts_when_impure
- * records the possible data flow facts before any expressions with side effects
- * are evaluated.
+ * Specifically, struct df_domain records the state before an expression is
+ * evaluated (opt->before), and after an expression returns true
+ * (opt->after_true) or false (opt->after_false).  Additionally, opt->impure
+ * records the possible state before any expression with side effects is
+ * evaluated.
  *
  * -O3: expression re-ordering to reduce expected cost.  In an expression like
  * (-foo -and -bar), if both -foo and -bar are pure (no side effects), they can
@@ -22,8 +21,8 @@
  * -bar is likely to return false.
  *
  * -O4/-Ofast: aggressive optimizations that may affect correctness in corner
- * cases.  The main effect is to use facts_when_impure to determine if any side-
- * effects are reachable at all, and skipping the traversal if not.
+ * cases.  The main effect is to use impure to determine if any side-effects are
+ * reachable at all, and skipping the traversal if not.
  */
 
 #include "opt.h"
@@ -47,15 +46,57 @@ static char *fake_or_arg = "-o";
 static char *fake_not_arg = "!";
 
 /**
+ * The data flow domain for predicates.
+ */
+enum df_pred {
+	/** The bottom state (unreachable). */
+	PRED_BOTTOM = 0,
+	/** The predicate is known to be false. */
+	PRED_FALSE = 1 << false,
+	/** The predicate is known to be true. */
+	PRED_TRUE = 1 << true,
+	/** The top state (unknown). */
+	PRED_TOP = PRED_FALSE | PRED_TRUE,
+};
+
+/** Make a predicate known. */
+static void constrain_pred(enum df_pred *pred, bool value) {
+	*pred &= 1 << value;
+}
+
+/** Compute the join (union) of two predicates. */
+static void pred_join(enum df_pred *dest, enum df_pred src) {
+	*dest |= src;
+}
+
+/**
  * A contrained integer range.
  */
-struct range {
+struct df_range {
 	/** The (inclusive) minimum value. */
 	long long min;
 	/** The (inclusive) maximum value. */
 	long long max;
 };
 
+/** Initialize an empty range. */
+static void range_init_bottom(struct df_range *range) {
+	range->min = LLONG_MAX;
+	range->max = LLONG_MIN;
+}
+
+/** Check if a range is empty. */
+static bool range_is_bottom(const struct df_range *range) {
+	return range->min > range->max;
+}
+
+/** Initialize a full range. */
+static void range_init_top(struct df_range *range) {
+	// All ranges we currently track are non-negative
+	range->min = 0;
+	range->max = LLONG_MAX;
+}
+
 /** Compute the minimum of two values. */
 static long long min_value(long long a, long long b) {
 	if (a < b) {
@@ -75,17 +116,17 @@ static long long max_value(long long a, long long b) {
 }
 
 /** Constrain the minimum of a range. */
-static void constrain_min(struct range *range, long long value) {
+static void constrain_min(struct df_range *range, long long value) {
 	range->min = max_value(range->min, value);
 }
 
 /** Contrain the maximum of a range. */
-static void constrain_max(struct range *range, long long value) {
+static void constrain_max(struct df_range *range, long long value) {
 	range->max = min_value(range->max, value);
 }
 
 /** Remove a single value from a range. */
-static void range_remove(struct range *range, long long value) {
+static void range_remove(struct df_range *range, long long value) {
 	if (range->min == value) {
 		if (range->min == LLONG_MAX) {
 			range->max = LLONG_MIN;
@@ -104,20 +145,9 @@ static void range_remove(struct range *range, long long value) {
 }
 
 /** Compute the union of two ranges. */
-static void range_union(struct range *result, const struct range *lhs, const struct range *rhs) {
-	result->min = min_value(lhs->min, rhs->min);
-	result->max = max_value(lhs->max, rhs->max);
-}
-
-/** Check if a range contains no values. */
-static bool range_is_impossible(const struct range *range) {
-	return range->min > range->max;
-}
-
-/** Set a range to contain no values. */
-static void set_range_impossible(struct range *range) {
-	range->min = LLONG_MAX;
-	range->max = LLONG_MIN;
+static void range_join(struct df_range *dest, const struct df_range *src) {
+	dest->min = min_value(dest->min, src->min);
+	dest->max = max_value(dest->max, src->max);
 }
 
 /**
@@ -141,42 +171,6 @@ enum range_type {
 };
 
 /**
- * A possibly-known value of a predicate.
- */
-enum known_pred {
-	/** The state is impossible to reach. */
-	PRED_IMPOSSIBLE = -2,
-	/** The value of the predicate is not known. */
-	PRED_UNKNOWN = -1,
-	/** The predicate is known to be false. */
-	PRED_FALSE = false,
-	/** The predicate is known to be true. */
-	PRED_TRUE = true,
-};
-
-/** Make a predicate known. */
-static void constrain_pred(enum known_pred *pred, bool value) {
-	if (*pred == PRED_UNKNOWN) {
-		*pred = value;
-	} else if (*pred == !value) {
-		*pred = PRED_IMPOSSIBLE;
-	}
-}
-
-/** Compute the union of two known predicates. */
-static enum known_pred pred_union(enum known_pred lhs, enum known_pred rhs) {
-	if (lhs == PRED_IMPOSSIBLE) {
-		return rhs;
-	} else if (rhs == PRED_IMPOSSIBLE) {
-		return lhs;
-	} else if (lhs == rhs) {
-		return lhs;
-	} else {
-		return PRED_UNKNOWN;
-	}
-}
-
-/**
  * Types of predicates we track.
  */
 enum pred_type {
@@ -207,14 +201,14 @@ enum pred_type {
 };
 
 /**
- * Data flow facts about an evaluation point.
+ * The data flow analysis domain.
  */
-struct opt_facts {
-	/** The value ranges we track. */
-	struct range ranges[RANGE_TYPES];
-
+struct df_domain {
 	/** The predicates we track. */
-	enum known_pred preds[PRED_TYPES];
+	enum df_pred preds[PRED_TYPES];
+
+	/** The value ranges we track. */
+	struct df_range ranges[RANGE_TYPES];
 
 	/** Bitmask of possible file types. */
 	unsigned int types;
@@ -222,97 +216,101 @@ struct opt_facts {
 	unsigned int xtypes;
 };
 
-/** Initialize some data flow facts. */
-static void facts_init(struct opt_facts *facts) {
-	for (int i = 0; i < RANGE_TYPES; ++i) {
-		struct range *range = &facts->ranges[i];
-		range->min = 0; // All ranges we currently track are non-negative
-		range->max = LLONG_MAX;
-	}
-
+/** Set a data flow value to bottom. */
+static void df_init_bottom(struct df_domain *value) {
 	for (int i = 0; i < PRED_TYPES; ++i) {
-		facts->preds[i] = PRED_UNKNOWN;
+		value->preds[i] = PRED_BOTTOM;
 	}
 
-	facts->types = ~0;
-	facts->xtypes = ~0;
-}
-
-/** Compute the union of two fact sets. */
-static void facts_union(struct opt_facts *result, const struct opt_facts *lhs, const struct opt_facts *rhs) {
 	for (int i = 0; i < RANGE_TYPES; ++i) {
-		range_union(&result->ranges[i], &lhs->ranges[i], &rhs->ranges[i]);
+		range_init_bottom(&value->ranges[i]);
 	}
 
-	for (int i = 0; i < PRED_TYPES; ++i) {
-		result->preds[i] = pred_union(lhs->preds[i], rhs->preds[i]);
-	}
-
-	result->types = lhs->types | rhs->types;
-	result->xtypes = lhs->xtypes | rhs->xtypes;
+	value->types = 0;
+	value->xtypes = 0;
 }
 
 /** Determine whether a fact set is impossible. */
-static bool facts_are_impossible(const struct opt_facts *facts) {
+static bool df_is_bottom(const struct df_domain *value) {
 	for (int i = 0; i < RANGE_TYPES; ++i) {
-		if (range_is_impossible(&facts->ranges[i])) {
+		if (range_is_bottom(&value->ranges[i])) {
 			return true;
 		}
 	}
 
 	for (int i = 0; i < PRED_TYPES; ++i) {
-		if (facts->preds[i] == PRED_IMPOSSIBLE) {
+		if (value->preds[i] == PRED_BOTTOM) {
 			return true;
 		}
 	}
 
-	if (!facts->types || !facts->xtypes) {
+	if (!value->types || !value->xtypes) {
 		return true;
 	}
 
 	return false;
 }
 
-/** Set some facts to be impossible. */
-static void set_facts_impossible(struct opt_facts *facts) {
+/** Initialize some data flow value. */
+static void df_init_top(struct df_domain *value) {
+	for (int i = 0; i < PRED_TYPES; ++i) {
+		value->preds[i] = PRED_TOP;
+	}
+
 	for (int i = 0; i < RANGE_TYPES; ++i) {
-		set_range_impossible(&facts->ranges[i]);
+		range_init_top(&value->ranges[i]);
 	}
 
+	value->types = ~0;
+	value->xtypes = ~0;
+}
+
+/** Compute the union of two fact sets. */
+static void df_join(struct df_domain *dest, const struct df_domain *src) {
 	for (int i = 0; i < PRED_TYPES; ++i) {
-		facts->preds[i] = PRED_IMPOSSIBLE;
+		pred_join(&dest->preds[i], src->preds[i]);
 	}
 
-	facts->types = 0;
-	facts->xtypes = 0;
+	for (int i = 0; i < RANGE_TYPES; ++i) {
+		range_join(&dest->ranges[i], &src->ranges[i]);
+	}
+
+	dest->types |= src->types;
+	dest->xtypes |= src->xtypes;
 }
 
 /**
  * Optimizer state.
  */
-struct opt_state {
+struct bfs_opt {
 	/** The context we're optimizing. */
 	const struct bfs_ctx *ctx;
 
-	/** Data flow facts before this expression is evaluated. */
-	struct opt_facts facts;
-	/** Data flow facts after this expression returns true. */
-	struct opt_facts facts_when_true;
-	/** Data flow facts after this expression returns false. */
-	struct opt_facts facts_when_false;
-	/** Data flow facts before any side-effecting expressions are evaluated. */
-	struct opt_facts *facts_when_impure;
+	/** Data flow state before this expression is evaluated. */
+	struct df_domain before;
+	/** Data flow state after this expression returns true. */
+	struct df_domain after_true;
+	/** Data flow state after this expression returns false. */
+	struct df_domain after_false;
+	/** Data flow state before any side-effecting expressions are evaluated. */
+	struct df_domain *impure;
 };
 
+/** Constrain the value of a predicate. */
+static void opt_constrain_pred(struct bfs_opt *opt, enum pred_type type, bool value) {
+	constrain_pred(&opt->after_true.preds[type], value);
+	constrain_pred(&opt->after_false.preds[type], !value);
+}
+
 /** Log an optimization. */
 attr(printf(3, 4))
-static bool opt_debug(const struct opt_state *state, int level, const char *format, ...) {
-	bfs_assert(state->ctx->optlevel >= level);
+static bool opt_debug(const struct bfs_opt *opt, int level, const char *format, ...) {
+	bfs_assert(opt->ctx->optlevel >= level);
 
-	if (bfs_debug(state->ctx, DEBUG_OPT, "${cyn}-O%d${rs}: ", level)) {
+	if (bfs_debug(opt->ctx, DEBUG_OPT, "${cyn}-O%d${rs}: ", level)) {
 		va_list args;
 		va_start(args, format);
-		cvfprintf(state->ctx->cerr, format, args);
+		cvfprintf(opt->ctx->cerr, format, args);
 		va_end(args);
 		return true;
 	} else {
@@ -322,11 +320,11 @@ static bool opt_debug(const struct opt_state *state, int level, const char *form
 
 /** Warn about an expression. */
 attr(printf(3, 4))
-static void opt_warning(const struct opt_state *state, const struct bfs_expr *expr, const char *format, ...) {
-	if (bfs_expr_warning(state->ctx, expr)) {
+static void opt_warning(const struct bfs_opt *opt, const struct bfs_expr *expr, const char *format, ...) {
+	if (bfs_expr_warning(opt->ctx, expr)) {
 		va_list args;
 		va_start(args, format);
-		bfs_vwarning(state->ctx, format, args);
+		bfs_vwarning(opt->ctx, format, args);
 		va_end(args);
 	}
 }
@@ -365,15 +363,15 @@ static struct bfs_expr *negate_expr(struct bfs_expr *rhs, char **argv) {
 	return expr;
 }
 
-static struct bfs_expr *optimize_not_expr(const struct opt_state *state, struct bfs_expr *expr);
-static struct bfs_expr *optimize_and_expr(const struct opt_state *state, struct bfs_expr *expr);
-static struct bfs_expr *optimize_or_expr(const struct opt_state *state, struct bfs_expr *expr);
+static struct bfs_expr *optimize_not_expr(const struct bfs_opt *opt, struct bfs_expr *expr);
+static struct bfs_expr *optimize_and_expr(const struct bfs_opt *opt, struct bfs_expr *expr);
+static struct bfs_expr *optimize_or_expr(const struct bfs_opt *opt, struct bfs_expr *expr);
 
 /**
  * Apply De Morgan's laws.
  */
-static struct bfs_expr *de_morgan(const struct opt_state *state, struct bfs_expr *expr, char **argv) {
-	bool debug = opt_debug(state, 1, "De Morgan's laws: %pe ", expr);
+static struct bfs_expr *de_morgan(const struct bfs_opt *opt, struct bfs_expr *expr, char **argv) {
+	bool debug = opt_debug(opt, 1, "De Morgan's laws: %pe ", expr);
 
 	struct bfs_expr *parent = negate_expr(expr, argv);
 	if (!parent) {
@@ -403,14 +401,14 @@ static struct bfs_expr *de_morgan(const struct opt_state *state, struct bfs_expr
 	}
 
 	if (debug) {
-		cfprintf(state->ctx->cerr, "<==> %pe\n", parent);
+		cfprintf(opt->ctx->cerr, "<==> %pe\n", parent);
 	}
 
 	if (expr->lhs->eval_fn == eval_not) {
-		expr->lhs = optimize_not_expr(state, expr->lhs);
+		expr->lhs = optimize_not_expr(opt, expr->lhs);
 	}
 	if (expr->rhs->eval_fn == eval_not) {
-		expr->rhs = optimize_not_expr(state, expr->rhs);
+		expr->rhs = optimize_not_expr(opt, expr->rhs);
 	}
 	if (!expr->lhs || !expr->rhs) {
 		bfs_expr_free(parent);
@@ -418,9 +416,9 @@ static struct bfs_expr *de_morgan(const struct opt_state *state, struct bfs_expr
 	}
 
 	if (expr->eval_fn == eval_and) {
-		expr = optimize_and_expr(state, expr);
+		expr = optimize_and_expr(opt, expr);
 	} else {
-		expr = optimize_or_expr(state, expr);
+		expr = optimize_or_expr(opt, expr);
 	}
 	if (has_parent) {
 		parent->rhs = expr;
@@ -433,38 +431,38 @@ static struct bfs_expr *de_morgan(const struct opt_state *state, struct bfs_expr
 	}
 
 	if (has_parent) {
-		parent = optimize_not_expr(state, parent);
+		parent = optimize_not_expr(opt, parent);
 	}
 	return parent;
 }
 
 /** Optimize an expression recursively. */
-static struct bfs_expr *optimize_expr_recursive(struct opt_state *state, struct bfs_expr *expr);
+static struct bfs_expr *optimize_expr_recursive(struct bfs_opt *opt, struct bfs_expr *expr);
 
 /**
  * Optimize a negation.
  */
-static struct bfs_expr *optimize_not_expr(const struct opt_state *state, struct bfs_expr *expr) {
+static struct bfs_expr *optimize_not_expr(const struct bfs_opt *opt, struct bfs_expr *expr) {
 	bfs_assert(expr->eval_fn == eval_not);
 
 	struct bfs_expr *rhs = expr->rhs;
 
-	int optlevel = state->ctx->optlevel;
+	int optlevel = opt->ctx->optlevel;
 	if (optlevel >= 1) {
 		if (rhs->eval_fn == eval_true || rhs->eval_fn == eval_false) {
 			struct bfs_expr *ret = opt_const(rhs->eval_fn == eval_false);
-			opt_debug(state, 1, "constant propagation: %pe <==> %pe\n", expr, ret);
+			opt_debug(opt, 1, "constant propagation: %pe <==> %pe\n", expr, ret);
 			bfs_expr_free(expr);
 			return ret;
 		} else if (rhs->eval_fn == eval_not) {
-			opt_debug(state, 1, "double negation: %pe <==> %pe\n", expr, rhs->rhs);
+			opt_debug(opt, 1, "double negation: %pe <==> %pe\n", expr, rhs->rhs);
 			return extract_child_expr(expr, &rhs->rhs);
 		} else if (bfs_expr_never_returns(rhs)) {
-			opt_debug(state, 1, "reachability: %pe <==> %pe\n", expr, rhs);
+			opt_debug(opt, 1, "reachability: %pe <==> %pe\n", expr, rhs);
 			return extract_child_expr(expr, &expr->rhs);
 		} else if ((rhs->eval_fn == eval_and || rhs->eval_fn == eval_or)
 			   && (rhs->lhs->eval_fn == eval_not || rhs->rhs->eval_fn == eval_not)) {
-			return de_morgan(state, expr, expr->argv);
+			return de_morgan(opt, expr, expr->argv);
 		}
 	}
 
@@ -478,17 +476,17 @@ static struct bfs_expr *optimize_not_expr(const struct opt_state *state, struct
 }
 
 /** Optimize a negation recursively. */
-static struct bfs_expr *optimize_not_expr_recursive(struct opt_state *state, struct bfs_expr *expr) {
-	struct opt_state rhs_state = *state;
+static struct bfs_expr *optimize_not_expr_recursive(struct bfs_opt *opt, struct bfs_expr *expr) {
+	struct bfs_opt rhs_state = *opt;
 	expr->rhs = optimize_expr_recursive(&rhs_state, expr->rhs);
 	if (!expr->rhs) {
 		goto fail;
 	}
 
-	state->facts_when_true = rhs_state.facts_when_false;
-	state->facts_when_false = rhs_state.facts_when_true;
+	opt->after_true = rhs_state.after_false;
+	opt->after_false = rhs_state.after_true;
 
-	return optimize_not_expr(state, expr);
+	return optimize_not_expr(opt, expr);
 
 fail:
 	bfs_expr_free(expr);
@@ -496,27 +494,27 @@ fail:
 }
 
 /** Optimize a conjunction. */
-static struct bfs_expr *optimize_and_expr(const struct opt_state *state, struct bfs_expr *expr) {
+static struct bfs_expr *optimize_and_expr(const struct bfs_opt *opt, struct bfs_expr *expr) {
 	bfs_assert(expr->eval_fn == eval_and);
 
 	struct bfs_expr *lhs = expr->lhs;
 	struct bfs_expr *rhs = expr->rhs;
 
-	const struct bfs_ctx *ctx = state->ctx;
+	const struct bfs_ctx *ctx = opt->ctx;
 	int optlevel = ctx->optlevel;
 	if (optlevel >= 1) {
 		if (lhs->eval_fn == eval_true) {
-			opt_debug(state, 1, "conjunction elimination: %pe <==> %pe\n", expr, rhs);
+			opt_debug(opt, 1, "conjunction elimination: %pe <==> %pe\n", expr, rhs);
 			return extract_child_expr(expr, &expr->rhs);
 		} else if (rhs->eval_fn == eval_true) {
-			opt_debug(state, 1, "conjunction elimination: %pe <==> %pe\n", expr, lhs);
+			opt_debug(opt, 1, "conjunction elimination: %pe <==> %pe\n", expr, lhs);
 			return extract_child_expr(expr, &expr->lhs);
 		} else if (lhs->always_false) {
-			opt_debug(state, 1, "short-circuit: %pe <==> %pe\n", expr, lhs);
-			opt_warning(state, expr->rhs, "This expression is unreachable.\n\n");
+			opt_debug(opt, 1, "short-circuit: %pe <==> %pe\n", expr, lhs);
+			opt_warning(opt, expr->rhs, "This expression is unreachable.\n\n");
 			return extract_child_expr(expr, &expr->lhs);
 		} else if (lhs->always_true && rhs->eval_fn == eval_false) {
-			bool debug = opt_debug(state, 1, "strength reduction: %pe <==> ", expr);
+			bool debug = opt_debug(opt, 1, "strength reduction: %pe <==> ", expr);
 			struct bfs_expr *ret = extract_child_expr(expr, &expr->lhs);
 			ret = negate_expr(ret, &fake_not_arg);
 			if (debug && ret) {
@@ -524,11 +522,11 @@ static struct bfs_expr *optimize_and_expr(const struct opt_state *state, struct
 			}
 			return ret;
 		} else if (optlevel >= 2 && lhs->pure && rhs->eval_fn == eval_false) {
-			opt_debug(state, 2, "purity: %pe <==> %pe\n", expr, rhs);
-			opt_warning(state, expr->lhs, "The result of this expression is ignored.\n\n");
+			opt_debug(opt, 2, "purity: %pe <==> %pe\n", expr, rhs);
+			opt_warning(opt, expr->lhs, "The result of this expression is ignored.\n\n");
 			return extract_child_expr(expr, &expr->rhs);
 		} else if (lhs->eval_fn == eval_not && rhs->eval_fn == eval_not) {
-			return de_morgan(state, expr, expr->lhs->argv);
+			return de_morgan(opt, expr, expr->lhs->argv);
 		}
 	}
 
@@ -542,24 +540,25 @@ static struct bfs_expr *optimize_and_expr(const struct opt_state *state, struct
 }
 
 /** Optimize a conjunction recursively. */
-static struct bfs_expr *optimize_and_expr_recursive(struct opt_state *state, struct bfs_expr *expr) {
-	struct opt_state lhs_state = *state;
+static struct bfs_expr *optimize_and_expr_recursive(struct bfs_opt *opt, struct bfs_expr *expr) {
+	struct bfs_opt lhs_state = *opt;
 	expr->lhs = optimize_expr_recursive(&lhs_state, expr->lhs);
 	if (!expr->lhs) {
 		goto fail;
 	}
 
-	struct opt_state rhs_state = *state;
-	rhs_state.facts = lhs_state.facts_when_true;
+	struct bfs_opt rhs_state = *opt;
+	rhs_state.before = lhs_state.after_true;
 	expr->rhs = optimize_expr_recursive(&rhs_state, expr->rhs);
 	if (!expr->rhs) {
 		goto fail;
 	}
 
-	state->facts_when_true = rhs_state.facts_when_true;
-	facts_union(&state->facts_when_false, &lhs_state.facts_when_false, &rhs_state.facts_when_false);
+	opt->after_true = rhs_state.after_true;
+	opt->after_false = lhs_state.after_false;
+	df_join(&opt->after_false, &rhs_state.after_false);
 
-	return optimize_and_expr(state, expr);
+	return optimize_and_expr(opt, expr);
 
 fail:
 	bfs_expr_free(expr);
@@ -567,27 +566,27 @@ fail:
 }
 
 /** Optimize a disjunction. */
-static struct bfs_expr *optimize_or_expr(const struct opt_state *state, struct bfs_expr *expr) {
+static struct bfs_expr *optimize_or_expr(const struct bfs_opt *opt, struct bfs_expr *expr) {
 	bfs_assert(expr->eval_fn == eval_or);
 
 	struct bfs_expr *lhs = expr->lhs;
 	struct bfs_expr *rhs = expr->rhs;
 
-	const struct bfs_ctx *ctx = state->ctx;
+	const struct bfs_ctx *ctx = opt->ctx;
 	int optlevel = ctx->optlevel;
 	if (optlevel >= 1) {
 		if (lhs->always_true) {
-			opt_debug(state, 1, "short-circuit: %pe <==> %pe\n", expr, lhs);
-			opt_warning(state, expr->rhs, "This expression is unreachable.\n\n");
+			opt_debug(opt, 1, "short-circuit: %pe <==> %pe\n", expr, lhs);
+			opt_warning(opt, expr->rhs, "This expression is unreachable.\n\n");
 			return extract_child_expr(expr, &expr->lhs);
 		} else if (lhs->eval_fn == eval_false) {
-			opt_debug(state, 1, "disjunctive syllogism: %pe <==> %pe\n", expr, rhs);
+			opt_debug(opt, 1, "disjunctive syllogism: %pe <==> %pe\n", expr, rhs);
 			return extract_child_expr(expr, &expr->rhs);
 		} else if (rhs->eval_fn == eval_false) {
-			opt_debug(state, 1, "disjunctive syllogism: %pe <==> %pe\n", expr, lhs);
+			opt_debug(opt, 1, "disjunctive syllogism: %pe <==> %pe\n", expr, lhs);
 			return extract_child_expr(expr, &expr->lhs);
 		} else if (lhs->always_false && rhs->eval_fn == eval_true) {
-			bool debug = opt_debug(state, 1, "strength reduction: %pe <==> ", expr);
+			bool debug = opt_debug(opt, 1, "strength reduction: %pe <==> ", expr);
 			struct bfs_expr *ret = extract_child_expr(expr, &expr->lhs);
 			ret = negate_expr(ret, &fake_not_arg);
 			if (debug && ret) {
@@ -595,11 +594,11 @@ static struct bfs_expr *optimize_or_expr(const struct opt_state *state, struct b
 			}
 			return ret;
 		} else if (optlevel >= 2 && lhs->pure && rhs->eval_fn == eval_true) {
-			opt_debug(state, 2, "purity: %pe <==> %pe\n", expr, rhs);
-			opt_warning(state, expr->lhs, "The result of this expression is ignored.\n\n");
+			opt_debug(opt, 2, "purity: %pe <==> %pe\n", expr, rhs);
+			opt_warning(opt, expr->lhs, "The result of this expression is ignored.\n\n");
 			return extract_child_expr(expr, &expr->rhs);
 		} else if (lhs->eval_fn == eval_not && rhs->eval_fn == eval_not) {
-			return de_morgan(state, expr, expr->lhs->argv);
+			return de_morgan(opt, expr, expr->lhs->argv);
 		}
 	}
 
@@ -613,24 +612,25 @@ static struct bfs_expr *optimize_or_expr(const struct opt_state *state, struct b
 }
 
 /** Optimize a disjunction recursively. */
-static struct bfs_expr *optimize_or_expr_recursive(struct opt_state *state, struct bfs_expr *expr) {
-	struct opt_state lhs_state = *state;
+static struct bfs_expr *optimize_or_expr_recursive(struct bfs_opt *opt, struct bfs_expr *expr) {
+	struct bfs_opt lhs_state = *opt;
 	expr->lhs = optimize_expr_recursive(&lhs_state, expr->lhs);
 	if (!expr->lhs) {
 		goto fail;
 	}
 
-	struct opt_state rhs_state = *state;
-	rhs_state.facts = lhs_state.facts_when_false;
+	struct bfs_opt rhs_state = *opt;
+	rhs_state.before = lhs_state.after_false;
 	expr->rhs = optimize_expr_recursive(&rhs_state, expr->rhs);
 	if (!expr->rhs) {
 		goto fail;
 	}
 
-	facts_union(&state->facts_when_true, &lhs_state.facts_when_true, &rhs_state.facts_when_true);
-	state->facts_when_false = rhs_state.facts_when_false;
+	opt->after_false = rhs_state.after_false;
+	opt->after_true = lhs_state.after_true;
+	df_join(&opt->after_true, &rhs_state.after_true);
 
-	return optimize_or_expr(state, expr);
+	return optimize_or_expr(opt, expr);
 
 fail:
 	bfs_expr_free(expr);
@@ -638,20 +638,20 @@ fail:
 }
 
 /** Optimize an expression in an ignored-result context. */
-static struct bfs_expr *ignore_result(const struct opt_state *state, struct bfs_expr *expr) {
-	int optlevel = state->ctx->optlevel;
+static struct bfs_expr *ignore_result(const struct bfs_opt *opt, struct bfs_expr *expr) {
+	int optlevel = opt->ctx->optlevel;
 
 	if (optlevel >= 1) {
 		while (true) {
 			if (expr->eval_fn == eval_not) {
-				opt_debug(state, 1, "ignored result: %pe --> %pe\n", expr, expr->rhs);
-				opt_warning(state, expr, "The result of this expression is ignored.\n\n");
+				opt_debug(opt, 1, "ignored result: %pe --> %pe\n", expr, expr->rhs);
+				opt_warning(opt, expr, "The result of this expression is ignored.\n\n");
 				expr = extract_child_expr(expr, &expr->rhs);
 			} else if (optlevel >= 2
 			           && (expr->eval_fn == eval_and || expr->eval_fn == eval_or || expr->eval_fn == eval_comma)
 			           && expr->rhs->pure) {
-				opt_debug(state, 2, "ignored result: %pe --> %pe\n", expr, expr->lhs);
-				opt_warning(state, expr->rhs, "The result of this expression is ignored.\n\n");
+				opt_debug(opt, 2, "ignored result: %pe --> %pe\n", expr, expr->lhs);
+				opt_warning(opt, expr->rhs, "The result of this expression is ignored.\n\n");
 				expr = extract_child_expr(expr, &expr->lhs);
 			} else {
 				break;
@@ -660,8 +660,8 @@ static struct bfs_expr *ignore_result(const struct opt_state *state, struct bfs_
 
 		if (optlevel >= 2 && expr->pure && expr->eval_fn != eval_false) {
 			struct bfs_expr *ret = opt_const(false);
-			opt_debug(state, 2, "ignored result: %pe --> %pe\n", expr, ret);
-			opt_warning(state, expr, "The result of this expression is ignored.\n\n");
+			opt_debug(opt, 2, "ignored result: %pe --> %pe\n", expr, ret);
+			opt_warning(opt, expr, "The result of this expression is ignored.\n\n");
 			bfs_expr_free(expr);
 			return ret;
 		}
@@ -671,27 +671,27 @@ static struct bfs_expr *ignore_result(const struct opt_state *state, struct bfs_
 }
 
 /** Optimize a comma expression. */
-static struct bfs_expr *optimize_comma_expr(const struct opt_state *state, struct bfs_expr *expr) {
+static struct bfs_expr *optimize_comma_expr(const struct bfs_opt *opt, struct bfs_expr *expr) {
 	bfs_assert(expr->eval_fn == eval_comma);
 
 	struct bfs_expr *lhs = expr->lhs;
 	struct bfs_expr *rhs = expr->rhs;
 
-	int optlevel = state->ctx->optlevel;
+	int optlevel = opt->ctx->optlevel;
 	if (optlevel >= 1) {
-		lhs = expr->lhs = ignore_result(state, lhs);
+		lhs = expr->lhs = ignore_result(opt, lhs);
 
 		if (bfs_expr_never_returns(lhs)) {
-			opt_debug(state, 1, "reachability: %pe <==> %pe\n", expr, lhs);
-			opt_warning(state, expr->rhs, "This expression is unreachable.\n\n");
+			opt_debug(opt, 1, "reachability: %pe <==> %pe\n", expr, lhs);
+			opt_warning(opt, expr->rhs, "This expression is unreachable.\n\n");
 			return extract_child_expr(expr, &expr->lhs);
 		} else if ((lhs->always_true && rhs->eval_fn == eval_true)
 			   || (lhs->always_false && rhs->eval_fn == eval_false)) {
-			opt_debug(state, 1, "redundancy elimination: %pe <==> %pe\n", expr, lhs);
+			opt_debug(opt, 1, "redundancy elimination: %pe <==> %pe\n", expr, lhs);
 			return extract_child_expr(expr, &expr->lhs);
 		} else if (optlevel >= 2 && lhs->pure) {
-			opt_debug(state, 2, "purity: %pe <==> %pe\n", expr, rhs);
-			opt_warning(state, expr->lhs, "The result of this expression is ignored.\n\n");
+			opt_debug(opt, 2, "purity: %pe <==> %pe\n", expr, rhs);
+			opt_warning(opt, expr->lhs, "The result of this expression is ignored.\n\n");
 			return extract_child_expr(expr, &expr->rhs);
 		}
 	}
@@ -706,76 +706,72 @@ static struct bfs_expr *optimize_comma_expr(const struct opt_state *state, struc
 }
 
 /** Optimize a comma expression recursively. */
-static struct bfs_expr *optimize_comma_expr_recursive(struct opt_state *state, struct bfs_expr *expr) {
-	struct opt_state lhs_state = *state;
+static struct bfs_expr *optimize_comma_expr_recursive(struct bfs_opt *opt, struct bfs_expr *expr) {
+	struct bfs_opt lhs_state = *opt;
 	expr->lhs = optimize_expr_recursive(&lhs_state, expr->lhs);
 	if (!expr->lhs) {
 		goto fail;
 	}
 
-	struct opt_state rhs_state = *state;
-	facts_union(&rhs_state.facts, &lhs_state.facts_when_true, &lhs_state.facts_when_false);
+	struct bfs_opt rhs_state = *opt;
+	rhs_state.before = lhs_state.after_true;
+	df_join(&rhs_state.before, &lhs_state.after_false);
+
 	expr->rhs = optimize_expr_recursive(&rhs_state, expr->rhs);
 	if (!expr->rhs) {
 		goto fail;
 	}
 
-	return optimize_comma_expr(state, expr);
+	return optimize_comma_expr(opt, expr);
 
 fail:
 	bfs_expr_free(expr);
 	return NULL;
 }
 
-/** Infer data flow facts about a predicate. */
-static void infer_pred_facts(struct opt_state *state, enum pred_type pred) {
-	constrain_pred(&state->facts_when_true.preds[pred], true);
-	constrain_pred(&state->facts_when_false.preds[pred], false);
-}
-
-/** Infer data flow facts about an icmp-style ([+-]N) expression. */
-static void infer_icmp_facts(struct opt_state *state, const struct bfs_expr *expr, enum range_type type) {
-	struct range *range_when_true = &state->facts_when_true.ranges[type];
-	struct range *range_when_false = &state->facts_when_false.ranges[type];
+/** Optimize an icmp-style ([+-]N) expression. */
+static void optimize_icmp(struct bfs_opt *opt, const struct bfs_expr *expr, enum range_type type) {
+	struct df_range *true_range = &opt->after_true.ranges[type];
+	struct df_range *false_range = &opt->after_false.ranges[type];
 	long long value = expr->num;
 
 	switch (expr->int_cmp) {
 	case BFS_INT_EQUAL:
-		constrain_min(range_when_true, value);
-		constrain_max(range_when_true, value);
-		range_remove(range_when_false, value);
+		constrain_min(true_range, value);
+		constrain_max(true_range, value);
+		range_remove(false_range, value);
 		break;
 
 	case BFS_INT_LESS:
-		constrain_min(range_when_false, value);
-		constrain_max(range_when_true, value);
-		range_remove(range_when_true, value);
+		constrain_min(false_range, value);
+		constrain_max(true_range, value);
+		range_remove(true_range, value);
 		break;
 
 	case BFS_INT_GREATER:
-		constrain_max(range_when_false, value);
-		constrain_min(range_when_true, value);
-		range_remove(range_when_true, value);
+		constrain_max(false_range, value);
+		constrain_min(true_range, value);
+		range_remove(true_range, value);
 		break;
 	}
 }
 
 /** Optimize -{execut,read,writ}able. */
-static struct bfs_expr *optimize_access(struct opt_state *state, struct bfs_expr *expr) {
+static struct bfs_expr *optimize_access(struct bfs_opt *opt, struct bfs_expr *expr) {
 	expr->probability = 1.0;
 
 	if (expr->num & R_OK) {
-		infer_pred_facts(state, READABLE_PRED);
+		opt_constrain_pred(opt, READABLE_PRED, true);
 		expr->probability *= 0.99;
 	}
 
 	if (expr->num & W_OK) {
-		infer_pred_facts(state, WRITABLE_PRED);
+		opt_constrain_pred(opt, WRITABLE_PRED, true);
 		expr->probability *= 0.8;
 	}
 
 	if (expr->num & X_OK) {
-		infer_pred_facts(state, EXECUTABLE_PRED);
+		opt_constrain_pred(opt, EXECUTABLE_PRED, true);
 		expr->probability *= 0.2;
 	}
 
@@ -783,8 +779,8 @@ static struct bfs_expr *optimize_access(struct opt_state *state, struct bfs_expr
 }
 
 /** Optimize -empty. */
-static struct bfs_expr *optimize_empty(struct opt_state *state, struct bfs_expr *expr) {
-	if (state->ctx->optlevel >= 4) {
+static struct bfs_expr *optimize_empty(struct bfs_opt *opt, struct bfs_expr *expr) {
+	if (opt->ctx->optlevel >= 4) {
 		// Since -empty attempts to open and read directories, it may
 		// have side effects such as reporting permission errors, and
 		// thus shouldn't be re-ordered without aggressive optimizations
@@ -795,7 +791,7 @@ static struct bfs_expr *optimize_empty(struct opt_state *state, struct bfs_expr
 }
 
 /** Optimize -{exec,ok}{,dir}. */
-static struct bfs_expr *optimize_exec(struct opt_state *state, struct bfs_expr *expr) {
+static struct bfs_expr *optimize_exec(struct bfs_opt *opt, struct bfs_expr *expr) {
 	if (expr->exec->flags & BFS_EXEC_MULTI) {
 		expr->always_true = true;
 	} else {
@@ -806,7 +802,7 @@ static struct bfs_expr *optimize_exec(struct opt_state *state, struct bfs_expr *
 }
 
 /** Optimize -name/-lname/-path. */
-static struct bfs_expr *optimize_fnmatch(struct opt_state *state, struct bfs_expr *expr) {
+static struct bfs_expr *optimize_fnmatch(struct bfs_opt *opt, struct bfs_expr *expr) {
 	if (strchr(expr->argv[1], '*')) {
 		expr->probability = 0.5;
 	} else {
@@ -817,13 +813,13 @@ static struct bfs_expr *optimize_fnmatch(struct opt_state *state, struct bfs_exp
 }
 
 /** Optimize -gid. */
-static struct bfs_expr *optimize_gid(struct opt_state *state, struct bfs_expr *expr) {
-	struct range *range = &state->facts_when_true.ranges[GID_RANGE];
+static struct bfs_expr *optimize_gid(struct bfs_opt *opt, struct bfs_expr *expr) {
+	struct df_range *range = &opt->after_true.ranges[GID_RANGE];
 	if (range->min == range->max) {
 		gid_t gid = range->min;
-		bool nogroup = !bfs_getgrgid(state->ctx->groups, gid);
+		bool nogroup = !bfs_getgrgid(opt->ctx->groups, gid);
 		if (errno == 0) {
-			constrain_pred(&state->facts_when_true.preds[NOGROUP_PRED], nogroup);
+			opt_constrain_pred(opt, NOGROUP_PRED, nogroup);
 		}
 	}
 
@@ -831,8 +827,8 @@ static struct bfs_expr *optimize_gid(struct opt_state *state, struct bfs_expr *e
 }
 
 /** Optimize -inum. */
-static struct bfs_expr *optimize_inum(struct opt_state *state, struct bfs_expr *expr) {
-	struct range *range = &state->facts_when_true.ranges[INUM_RANGE];
+static struct bfs_expr *optimize_inum(struct bfs_opt *opt, struct bfs_expr *expr) {
+	struct df_range *range = &opt->after_true.ranges[INUM_RANGE];
 	if (range->min == range->max) {
 		expr->probability = 0.01;
 	} else {
@@ -843,8 +839,8 @@ static struct bfs_expr *optimize_inum(struct opt_state *state, struct bfs_expr *
 }
 
 /** Optimize -links. */
-static struct bfs_expr *optimize_links(struct opt_state *state, struct bfs_expr *expr) {
-	struct range *range = &state->facts_when_true.ranges[LINKS_RANGE];
+static struct bfs_expr *optimize_links(struct bfs_opt *opt, struct bfs_expr *expr) {
+	struct df_range *range = &opt->after_true.ranges[LINKS_RANGE];
 	if (1 >= range->min && 1 <= range->max) {
 		expr->probability = 0.99;
 	} else {
@@ -855,13 +851,13 @@ static struct bfs_expr *optimize_links(struct opt_state *state, struct bfs_expr
 }
 
 /** Optimize -uid. */
-static struct bfs_expr *optimize_uid(struct opt_state *state, struct bfs_expr *expr) {
-	struct range *range = &state->facts_when_true.ranges[UID_RANGE];
+static struct bfs_expr *optimize_uid(struct bfs_opt *opt, struct bfs_expr *expr) {
+	struct df_range *range = &opt->after_true.ranges[UID_RANGE];
 	if (range->min == range->max) {
 		uid_t uid = range->min;
-		bool nouser = !bfs_getpwuid(state->ctx->users, uid);
+		bool nouser = !bfs_getpwuid(opt->ctx->users, uid);
 		if (errno == 0) {
-			constrain_pred(&state->facts_when_true.preds[NOUSER_PRED], nouser);
+			opt_constrain_pred(opt, NOUSER_PRED, nouser);
 		}
 	}
 
@@ -869,16 +865,16 @@ static struct bfs_expr *optimize_uid(struct opt_state *state, struct bfs_expr *e
 }
 
 /** Optimize -samefile. */
-static struct bfs_expr *optimize_samefile(struct opt_state *state, struct bfs_expr *expr) {
-	struct range *range_when_true = &state->facts_when_true.ranges[INUM_RANGE];
-	constrain_min(range_when_true, expr->ino);
-	constrain_max(range_when_true, expr->ino);
+static struct bfs_expr *optimize_samefile(struct bfs_opt *opt, struct bfs_expr *expr) {
+	struct df_range *range = &opt->after_true.ranges[INUM_RANGE];
+	constrain_min(range, expr->ino);
+	constrain_max(range, expr->ino);
 	return expr;
 }
 
 /** Optimize -size. */
-static struct bfs_expr *optimize_size(struct opt_state *state, struct bfs_expr *expr) {
-	struct range *range = &state->facts_when_true.ranges[SIZE_RANGE];
+static struct bfs_expr *optimize_size(struct bfs_opt *opt, struct bfs_expr *expr) {
+	struct df_range *range = &opt->after_true.ranges[SIZE_RANGE];
 	if (range->min == range->max) {
 		expr->probability = 0.01;
 	} else {
@@ -923,9 +919,9 @@ static void estimate_type_probability(struct bfs_expr *expr) {
 }
 
 /** Optimize -type. */
-static struct bfs_expr *optimize_type(struct opt_state *state, struct bfs_expr *expr) {
-	state->facts_when_true.types &= expr->num;
-	state->facts_when_false.types &= ~expr->num;
+static struct bfs_expr *optimize_type(struct bfs_opt *opt, struct bfs_expr *expr) {
+	opt->after_true.types &= expr->num;
+	opt->after_false.types &= ~expr->num;
 
 	estimate_type_probability(expr);
 
@@ -933,16 +929,16 @@ static struct bfs_expr *optimize_type(struct opt_state *state, struct bfs_expr *
 }
 
 /** Optimize -xtype. */
-static struct bfs_expr *optimize_xtype(struct opt_state *state, struct bfs_expr *expr) {
-	if (state->ctx->optlevel >= 4) {
+static struct bfs_expr *optimize_xtype(struct bfs_opt *opt, struct bfs_expr *expr) {
+	if (opt->ctx->optlevel >= 4) {
 		// Since -xtype dereferences symbolic links, it may have side
 		// effects such as reporting permission errors, and thus
 		// shouldn't be re-ordered without aggressive optimizations
 		expr->pure = true;
 	}
 
-	state->facts_when_true.xtypes &= expr->num;
-	state->facts_when_false.xtypes &= ~expr->num;
+	opt->after_true.xtypes &= expr->num;
+	opt->after_false.xtypes &= ~expr->num;
 
 	estimate_type_probability(expr);
 
@@ -1115,7 +1111,7 @@ static const struct {
 };
 
 /** Signature for custom optimizer functions. */
-typedef struct bfs_expr *bfs_opt_fn(struct opt_state *state, struct bfs_expr *expr);
+typedef struct bfs_expr *bfs_opt_fn(struct bfs_opt *opt, struct bfs_expr *expr);
 
 /** Table of custom optimizer functions. */
 static const struct {
@@ -1150,7 +1146,7 @@ static const struct {
 /**
  * Look up the appropriate optimizer for an expression and call it.
  */
-static struct bfs_expr *optimize_expr_lookup(struct opt_state *state, struct bfs_expr *expr) {
+static struct bfs_expr *optimize_expr_lookup(struct bfs_opt *opt, struct bfs_expr *expr) {
 	for (size_t i = 0; i < countof(opt_pure); ++i) {
 		if (opt_pure[i] == expr->eval_fn) {
 			expr->pure = true;
@@ -1189,42 +1185,42 @@ static struct bfs_expr *optimize_expr_lookup(struct opt_state *state, struct bfs
 
 	for (size_t i = 0; i < countof(opt_preds); ++i) {
 		if (opt_preds[i].eval_fn == expr->eval_fn) {
-			infer_pred_facts(state, opt_preds[i].pred);
+			opt_constrain_pred(opt, opt_preds[i].pred, true);
 			break;
 		}
 	}
 
 	for (size_t i = 0; i < countof(opt_ranges); ++i) {
 		if (opt_ranges[i].eval_fn == expr->eval_fn) {
-			infer_icmp_facts(state, expr, opt_ranges[i].range);
+			optimize_icmp(opt, expr, opt_ranges[i].range);
 			break;
 		}
 	}
 
 	for (size_t i = 0; i < countof(opt_fns); ++i) {
 		if (opt_fns[i].eval_fn == expr->eval_fn) {
-			return opt_fns[i].opt_fn(state, expr);
+			return opt_fns[i].opt_fn(opt, expr);
 		}
 	}
 
 	return expr;
 }
 
-static struct bfs_expr *optimize_expr_recursive(struct opt_state *state, struct bfs_expr *expr) {
-	int optlevel = state->ctx->optlevel;
+static struct bfs_expr *optimize_expr_recursive(struct bfs_opt *opt, struct bfs_expr *expr) {
+	int optlevel = opt->ctx->optlevel;
 
-	state->facts_when_true = state->facts;
-	state->facts_when_false = state->facts;
+	opt->after_true = opt->before;
+	opt->after_false = opt->before;
 
-	if (optlevel >= 2 && facts_are_impossible(&state->facts)) {
+	if (optlevel >= 2 && df_is_bottom(&opt->before)) {
 		struct bfs_expr *ret = opt_const(false);
-		opt_debug(state, 2, "reachability: %pe --> %pe\n", expr, ret);
-		opt_warning(state, expr, "This expression is unreachable.\n\n");
+		opt_debug(opt, 2, "reachability: %pe --> %pe\n", expr, ret);
+		opt_warning(opt, expr, "This expression is unreachable.\n\n");
 		bfs_expr_free(expr);
 		return ret;
 	}
 
-	expr = optimize_expr_lookup(state, expr);
+	expr = optimize_expr_lookup(opt, expr);
 	if (!expr) {
 		return NULL;
 	}
@@ -1243,38 +1239,38 @@ static struct bfs_expr *optimize_expr_recursive(struct opt_state *state, struct
 			}
 		}
 	} else if (!expr->pure) {
-		facts_union(state->facts_when_impure, state->facts_when_impure, &state->facts);
+		df_join(opt->impure, &opt->before);
 	}
 
 	if (expr->always_true) {
 		expr->probability = 1.0;
-		set_facts_impossible(&state->facts_when_false);
+		df_init_bottom(&opt->after_false);
 	}
 	if (expr->always_false) {
 		expr->probability = 0.0;
-		set_facts_impossible(&state->facts_when_true);
+		df_init_bottom(&opt->after_true);
 	}
 
 	if (optlevel < 2 || expr->eval_fn == eval_true || expr->eval_fn == eval_false) {
 		return expr;
 	}
 
-	if (facts_are_impossible(&state->facts_when_true)) {
+	if (df_is_bottom(&opt->after_true)) {
 		if (expr->pure) {
 			struct bfs_expr *ret = opt_const(false);
-			opt_warning(state, expr, "This expression is always false.\n\n");
-			opt_debug(state, 2, "data flow: %pe --> %pe\n", expr, ret);
+			opt_warning(opt, expr, "This expression is always false.\n\n");
+			opt_debug(opt, 2, "data flow: %pe --> %pe\n", expr, ret);
 			bfs_expr_free(expr);
 			return ret;
 		} else {
 			expr->always_false = true;
 			expr->probability = 0.0;
 		}
-	} else if (facts_are_impossible(&state->facts_when_false)) {
+	} else if (df_is_bottom(&opt->after_false)) {
 		if (expr->pure) {
 			struct bfs_expr *ret = opt_const(true);
-			opt_debug(state, 2, "data flow: %pe --> %pe\n", expr, ret);
-			opt_warning(state, expr, "This expression is always true.\n\n");
+			opt_debug(opt, 2, "data flow: %pe --> %pe\n", expr, ret);
+			opt_warning(opt, expr, "This expression is always true.\n\n");
 			bfs_expr_free(expr);
 			return ret;
 		} else {
@@ -1287,14 +1283,14 @@ static struct bfs_expr *optimize_expr_recursive(struct opt_state *state, struct
 }
 
 /** Swap the children of a binary expression if it would reduce the cost. */
-static bool reorder_expr(const struct opt_state *state, struct bfs_expr *expr, float swapped_cost) {
+static bool reorder_expr(const struct bfs_opt *opt, struct bfs_expr *expr, float swapped_cost) {
 	if (swapped_cost < expr->cost) {
-		bool debug = opt_debug(state, 3, "cost: %pe <==> ", expr);
+		bool debug = opt_debug(opt, 3, "cost: %pe <==> ", expr);
 		struct bfs_expr *lhs = expr->lhs;
 		expr->lhs = expr->rhs;
 		expr->rhs = lhs;
 		if (debug) {
-			cfprintf(state->ctx->cerr, "%pe (~${ylw}%g${rs} --> ~${ylw}%g${rs})\n", expr, expr->cost, swapped_cost);
+			cfprintf(opt->ctx->cerr, "%pe (~${ylw}%g${rs} --> ~${ylw}%g${rs})\n", expr, expr->cost, swapped_cost);
 		}
 		expr->cost = swapped_cost;
 		return true;
@@ -1311,7 +1307,7 @@ static bool reorder_expr(const struct opt_state *state, struct bfs_expr *expr, f
  * @return
  *         Whether any subexpression was reordered.
  */
-static bool reorder_expr_recursive(const struct opt_state *state, struct bfs_expr *expr) {
+static bool reorder_expr_recursive(const struct bfs_opt *opt, struct bfs_expr *expr) {
 	if (!bfs_expr_is_parent(expr)) {
 		return false;
 	}
@@ -1321,17 +1317,17 @@ static bool reorder_expr_recursive(const struct opt_state *state, struct bfs_exp
 
 	bool ret = false;
 	if (lhs) {
-		ret |= reorder_expr_recursive(state, lhs);
+		ret |= reorder_expr_recursive(opt, lhs);
 	}
 	if (rhs) {
-		ret |= reorder_expr_recursive(state, rhs);
+		ret |= reorder_expr_recursive(opt, rhs);
 	}
 
 	if (expr->eval_fn == eval_and || expr->eval_fn == eval_or) {
 		if (lhs->pure && rhs->pure) {
 			float rhs_prob = expr->eval_fn == eval_and ? rhs->probability : 1.0 - rhs->probability;
 			float swapped_cost = rhs->cost + rhs_prob * lhs->cost;
-			ret |= reorder_expr(state, expr, swapped_cost);
+			ret |= reorder_expr(opt, expr, swapped_cost);
 		}
 	}
 
@@ -1341,18 +1337,18 @@ static bool reorder_expr_recursive(const struct opt_state *state, struct bfs_exp
 /**
  * Optimize a top-level expression.
  */
-static struct bfs_expr *optimize_expr(struct opt_state *state, struct bfs_expr *expr) {
-	struct opt_facts saved_impure = *state->facts_when_impure;
+static struct bfs_expr *optimize_expr(struct bfs_opt *opt, struct bfs_expr *expr) {
+	struct df_domain saved_impure = *opt->impure;
 
-	expr = optimize_expr_recursive(state, expr);
+	expr = optimize_expr_recursive(opt, expr);
 	if (!expr) {
 		return NULL;
 	}
 
-	if (state->ctx->optlevel >= 3 && reorder_expr_recursive(state, expr)) {
+	if (opt->ctx->optlevel >= 3 && reorder_expr_recursive(opt, expr)) {
 		// Re-do optimizations to account for the new ordering
-		*state->facts_when_impure = saved_impure;
-		expr = optimize_expr_recursive(state, expr);
+		*opt->impure = saved_impure;
+		expr = optimize_expr_recursive(opt, expr);
 		if (!expr) {
 			return NULL;
 		}
@@ -1364,41 +1360,41 @@ static struct bfs_expr *optimize_expr(struct opt_state *state, struct bfs_expr *
 int bfs_optimize(struct bfs_ctx *ctx) {
 	bfs_ctx_dump(ctx, DEBUG_OPT);
 
-	struct opt_facts facts_when_impure;
-	set_facts_impossible(&facts_when_impure);
+	struct df_domain impure;
+	df_init_bottom(&impure);
 
-	struct opt_state state = {
+	struct bfs_opt opt = {
 		.ctx = ctx,
-		.facts_when_impure = &facts_when_impure,
+		.impure = &impure,
 	};
-	facts_init(&state.facts);
+	df_init_top(&opt.before);
 
-	ctx->exclude = optimize_expr(&state, ctx->exclude);
+	ctx->exclude = optimize_expr(&opt, ctx->exclude);
 	if (!ctx->exclude) {
 		return -1;
 	}
 
 	// Only non-excluded files are evaluated
-	state.facts = state.facts_when_false;
+	opt.before = opt.after_false;
 
-	struct range *depth = &state.facts.ranges[DEPTH_RANGE];
+	struct df_range *depth = &opt.before.ranges[DEPTH_RANGE];
 	constrain_min(depth, ctx->mindepth);
 	constrain_max(depth, ctx->maxdepth);
 
-	ctx->expr = optimize_expr(&state, ctx->expr);
+	ctx->expr = optimize_expr(&opt, ctx->expr);
 	if (!ctx->expr) {
 		return -1;
 	}
 
-	ctx->expr = ignore_result(&state, ctx->expr);
+	ctx->expr = ignore_result(&opt, ctx->expr);
 
-	if (facts_are_impossible(&facts_when_impure)) {
+	if (df_is_bottom(&impure)) {
 		bfs_warning(ctx, "This command won't do anything.\n\n");
 	}
 
-	const struct range *depth_when_impure = &facts_when_impure.ranges[DEPTH_RANGE];
-	long long mindepth = depth_when_impure->min;
-	long long maxdepth = depth_when_impure->max;
+	const struct df_range *impure_depth = &impure.ranges[DEPTH_RANGE];
+	long long mindepth = impure_depth->min;
+	long long maxdepth = impure_depth->max;
 
 	int optlevel = ctx->optlevel;
 
@@ -1407,7 +1403,7 @@ int bfs_optimize(struct bfs_ctx *ctx) {
 			mindepth = INT_MAX;
 		}
 		ctx->mindepth = mindepth;
-		opt_debug(&state, 2, "data flow: mindepth --> %d\n", ctx->mindepth);
+		opt_debug(&opt, 2, "data flow: mindepth --> %d\n", ctx->mindepth);
 	}
 
 	if (optlevel >= 4 && maxdepth < ctx->maxdepth) {
@@ -1415,7 +1411,7 @@ int bfs_optimize(struct bfs_ctx *ctx) {
 			maxdepth = INT_MIN;
 		}
 		ctx->maxdepth = maxdepth;
-		opt_debug(&state, 4, "data flow: maxdepth --> %d\n", ctx->maxdepth);
+		opt_debug(&opt, 4, "data flow: maxdepth --> %d\n", ctx->maxdepth);
 	}
 
 	return 0;