summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--opt.c287
1 files changed, 208 insertions, 79 deletions
diff --git a/opt.c b/opt.c
index 2ded162..b3abf37 100644
--- a/opt.c
+++ b/opt.c
@@ -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;