opt: Apply data flow optimizations to more numeric ranges

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;