diff options
| -rw-r--r-- | opt.c | 287 |
1 files changed, 208 insertions, 79 deletions
@@ -27,45 +27,157 @@ static char *fake_and_arg = "-a"; static char *fake_or_arg = "-o"; /** + * A contrained integer range. + */ +struct range { + /** The (inclusive) minimum value. */ + long long min; + /** The (inclusive) maximum value. */ + long long max; +}; + +/** Compute the minimum of two values. */ +static long long min_value(long long a, long long b) { + if (a < b) { + return a; + } else { + return b; + } +} + +/** Compute the maximum of two values. */ +static long long max_value(long long a, long long b) { + if (a > b) { + return a; + } else { + return b; + } +} + +/** Constrain the minimum of a range. */ +static void constrain_min(struct 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) { + range->max = min_value(range->max, value); +} + +/** Remove a single value from a range. */ +static void range_remove(struct range *range, long long value) { + if (range->min == value) { + if (range->min == LLONG_MAX) { + range->max = LLONG_MIN; + } else { + ++range->min; + } + } + + if (range->max == value) { + if (range->max == LLONG_MIN) { + range->min = LLONG_MAX; + } else { + --range->max; + } + } +} + +/** 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_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; +} + +/** + * Types of ranges we track. + */ +enum range_type { + /** Search tree depth. */ + DEPTH_RANGE, + /** Group ID. */ + GID_RANGE, + /** Inode number. */ + INUM_RANGE, + /** Hard link count. */ + LINKS_RANGE, + /** File size. */ + SIZE_RANGE, + /** User ID. */ + UID_RANGE, + /** The number of range_types. */ + MAX_RANGE, +}; + +/** * Data flow facts about an evaluation point. */ struct opt_facts { - /** Minimum possible depth at this point. */ - int mindepth; - /** Maximum possible depth at this point. */ - int maxdepth; + /** The value ranges we track. */ + struct range ranges[MAX_RANGE]; - /** Bitmask of possible file types at this point. */ + /** Bitmask of possible file types. */ enum bftw_typeflag types; + /** Bitmask of possible link target types. */ + enum bftw_typeflag xtypes; }; -/** 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) { - if (lhs->mindepth < rhs->mindepth) { - result->mindepth = lhs->mindepth; - } else { - result->mindepth = rhs->mindepth; +/** Initialize some data flow facts. */ +static void facts_init(struct opt_facts *facts) { + for (int i = 0; i < MAX_RANGE; ++i) { + struct range *range = facts->ranges + i; + range->min = 0; // All ranges we currently track are non-negative + range->max = LLONG_MAX; } - if (lhs->maxdepth > rhs->maxdepth) { - result->maxdepth = lhs->maxdepth; - } else { - result->maxdepth = rhs->maxdepth; + 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 < MAX_RANGE; ++i) { + range_union(result->ranges + i, lhs->ranges + i, rhs->ranges + i); } result->types = lhs->types | rhs->types; + result->xtypes = lhs->xtypes | rhs->xtypes; } /** Determine whether a fact set is impossible. */ static bool facts_impossible(const struct opt_facts *facts) { - return facts->mindepth > facts->maxdepth || !facts->types; + for (int i = 0; i < MAX_RANGE; ++i) { + if (range_impossible(facts->ranges + i)) { + return true; + } + } + + if (!facts->types || !facts->xtypes) { + return true; + } + + return false; } /** Set some facts to be impossible. */ static void set_facts_impossible(struct opt_facts *facts) { - facts->mindepth = INT_MAX; - facts->maxdepth = -1; + for (int i = 0; i < MAX_RANGE; ++i) { + set_range_impossible(facts->ranges + i); + } + facts->types = 0; + facts->xtypes = 0; } /** @@ -110,6 +222,10 @@ static void debug_opt(const struct opt_state *state, const char *format, ...) { case 'g': cfprintf(cerr, "${ylw}%g${rs}", va_arg(args, double)); break; + + default: + assert(false); + break; } } else { fputc(*i, stderr); @@ -119,55 +235,6 @@ static void debug_opt(const struct opt_state *state, const char *format, ...) { va_end(args); } -/** Update the inferred mindepth. */ -static void update_mindepth(struct opt_facts *facts, long long mindepth) { - if (mindepth > facts->mindepth) { - if (mindepth > INT_MAX) { - facts->maxdepth = -1; - } else { - facts->mindepth = mindepth; - } - } -} - -/** Update the inferred maxdepth. */ -static void update_maxdepth(struct opt_facts *facts, long long maxdepth) { - if (maxdepth < facts->maxdepth) { - facts->maxdepth = maxdepth; - } -} - -/** Infer data flow facts about a -depth N expression. */ -static void infer_depth_facts(struct opt_state *state, const struct expr *expr) { - switch (expr->cmp_flag) { - case CMP_EXACT: - update_mindepth(&state->facts_when_true, expr->idata); - update_maxdepth(&state->facts_when_true, expr->idata); - break; - - case CMP_LESS: - update_maxdepth(&state->facts_when_true, expr->idata - 1); - update_mindepth(&state->facts_when_false, expr->idata); - break; - - case CMP_GREATER: - if (expr->idata == LLONG_MAX) { - // Avoid overflow - state->facts_when_true.maxdepth = -1; - } else { - update_mindepth(&state->facts_when_true, expr->idata + 1); - } - update_maxdepth(&state->facts_when_false, expr->idata); - break; - } -} - -/** Infer data flow facts about a -type expression. */ -static void infer_type_facts(struct opt_state *state, const struct expr *expr) { - state->facts_when_true.types &= expr->idata; - state->facts_when_false.types &= ~expr->idata; -} - /** Extract a child expression, freeing the outer expression. */ static struct expr *extract_child_expr(struct expr *expr, struct expr **child) { struct expr *ret = *child; @@ -525,14 +592,65 @@ fail: return NULL; } +/** Infer data flow facts about an icmp-style ([+-]N) expression */ +static void infer_icmp_facts(struct opt_state *state, const struct 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; + long long value = expr->idata; + + switch (expr->cmp_flag) { + case CMP_EXACT: + constrain_min(range_when_true, value); + constrain_max(range_when_true, value); + range_remove(range_when_false, value); + break; + + case CMP_LESS: + constrain_min(range_when_false, value); + constrain_max(range_when_true, value); + range_remove(range_when_true, value); + break; + + case CMP_GREATER: + constrain_max(range_when_false, value); + constrain_min(range_when_true, value); + range_remove(range_when_true, value); + break; + } +} + +/** Infer data flow facts about a -type expression. */ +static void infer_type_facts(struct opt_state *state, const struct expr *expr) { + state->facts_when_true.types &= expr->idata; + state->facts_when_false.types &= ~expr->idata; +} + +/** Infer data flow facts about an -xtype expression. */ +static void infer_xtype_facts(struct opt_state *state, const struct expr *expr) { + state->facts_when_true.xtypes &= expr->idata; + state->facts_when_false.xtypes &= ~expr->idata; +} + static struct expr *optimize_expr_recursive(struct opt_state *state, struct expr *expr) { state->facts_when_true = state->facts; state->facts_when_false = state->facts; if (expr->eval == eval_depth) { - infer_depth_facts(state, expr); + infer_icmp_facts(state, expr, DEPTH_RANGE); + } else if (expr->eval == eval_gid) { + infer_icmp_facts(state, expr, GID_RANGE); + } else if (expr->eval == eval_inum) { + infer_icmp_facts(state, expr, INUM_RANGE); + } else if (expr->eval == eval_links) { + infer_icmp_facts(state, expr, LINKS_RANGE); + } else if (expr->eval == eval_size) { + infer_icmp_facts(state, expr, SIZE_RANGE); } else if (expr->eval == eval_type) { infer_type_facts(state, expr); + } else if (expr->eval == eval_uid) { + infer_icmp_facts(state, expr, UID_RANGE); + } else if (expr->eval == eval_xtype) { + infer_xtype_facts(state, expr); } else if (expr->eval == eval_not) { expr = optimize_not_expr_recursive(state, expr); } else if (expr->eval == eval_and) { @@ -649,13 +767,13 @@ int optimize_cmdline(struct cmdline *cmdline) { struct opt_state state = { .cmdline = cmdline, - .facts = { - .mindepth = cmdline->mindepth, - .maxdepth = cmdline->maxdepth, - .types = ~0, - }, .facts_when_impure = &facts_when_impure, }; + facts_init(&state.facts); + + struct range *depth = state.facts.ranges + DEPTH_RANGE; + depth->min = cmdline->mindepth; + depth->max = cmdline->maxdepth; int optlevel = cmdline->optlevel; @@ -675,13 +793,24 @@ int optimize_cmdline(struct cmdline *cmdline) { cmdline->expr = ignore_result(&state, cmdline->expr); - if (optlevel >= 2 && facts_when_impure.mindepth > cmdline->mindepth) { - debug_opt(&state, "-O2: data flow: mindepth --> %d\n", facts_when_impure.mindepth); - cmdline->mindepth = facts_when_impure.mindepth; + 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; + + if (optlevel >= 2 && mindepth > cmdline->mindepth) { + if (mindepth > INT_MAX) { + mindepth = INT_MAX; + } + cmdline->mindepth = mindepth; + debug_opt(&state, "-O2: data flow: mindepth --> %d\n", cmdline->mindepth); } - if (optlevel >= 4 && facts_when_impure.maxdepth < cmdline->maxdepth) { - debug_opt(&state, "-O4: data flow: maxdepth --> %d\n", facts_when_impure.maxdepth); - cmdline->maxdepth = facts_when_impure.maxdepth; + + if (optlevel >= 4 && maxdepth < cmdline->maxdepth) { + if (maxdepth < INT_MIN) { + maxdepth = INT_MIN; + } + cmdline->maxdepth = maxdepth; + debug_opt(&state, "-O4: data flow: maxdepth --> %d\n", cmdline->maxdepth); } return 0; |