From c60d93493f958cde1769a90058dac719ae1efa8c Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Sat, 29 Jul 2023 14:44:26 -0400 Subject: opt: Use more standard terminology for data flow domains --- src/opt.c | 592 +++++++++++++++++++++++++++++++------------------------------- 1 file changed, 294 insertions(+), 298 deletions(-) (limited to 'src/opt.c') 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" @@ -46,16 +45,58 @@ static char *fake_and_arg = "-a"; 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); } /** @@ -140,42 +170,6 @@ enum range_type { RANGE_TYPES, }; -/** - * 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. */ @@ -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; -- cgit v1.2.3