summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@tavianator.com>2023-07-29 14:44:26 -0400
committerTavian Barnes <tavianator@tavianator.com>2023-12-20 20:19:18 -0500
commitc60d93493f958cde1769a90058dac719ae1efa8c (patch)
tree009b2f8addb401b880e858c59e99ca2a89a2e36e
parent8f004e73238c5ee4be40c044827138eb5895ce88 (diff)
downloadbfs-c60d93493f958cde1769a90058dac719ae1efa8c.tar.xz
opt: Use more standard terminology for data flow domains
-rw-r--r--src/opt.c592
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;