summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--expr.h2
-rw-r--r--opt.c136
-rw-r--r--parse.c5
3 files changed, 115 insertions, 28 deletions
diff --git a/expr.h b/expr.h
index b825ca1..1f1ece6 100644
--- a/expr.h
+++ b/expr.h
@@ -110,6 +110,8 @@ struct bfs_expr {
bool always_true;
/** Whether this expression always evaluates to false. */
bool always_false;
+ /** Whether this expression doesn't appear on the command line. */
+ bool synthetic;
/** Estimated cost. */
float cost;
diff --git a/opt.c b/opt.c
index 886c49a..f46436a 100644
--- a/opt.c
+++ b/opt.c
@@ -51,7 +51,9 @@
#include <limits.h>
#include <stdarg.h>
#include <stdbool.h>
+#include <stdint.h>
#include <stdio.h>
+#include <string.h>
#include <unistd.h>
static char *fake_and_arg = "-a";
@@ -318,7 +320,7 @@ struct opt_state {
/** Log an optimization. */
BFS_FORMATTER(3, 4)
-static bool debug_opt(const struct opt_state *state, int level, const char *format, ...) {
+static bool opt_debug(const struct opt_state *state, int level, const char *format, ...) {
assert(state->ctx->optlevel >= level);
if (bfs_debug(state->ctx, DEBUG_OPT, "${cyn}-O%d${rs}: ", level)) {
@@ -332,6 +334,78 @@ static bool debug_opt(const struct opt_state *state, int level, const char *form
}
}
+/** Warn about an expression. */
+static void opt_vwarning(const struct opt_state *state, const struct bfs_expr *expr, const char *format, va_list args) {
+ if (bfs_expr_has_children(expr)) {
+ if (expr->lhs) {
+ va_list copy;
+ va_copy(copy, args);
+ opt_vwarning(state, expr->lhs, format, copy);
+ va_end(copy);
+ }
+
+ if (expr->rhs) {
+ opt_vwarning(state, expr->rhs, format, args);
+ }
+
+ return;
+ }
+
+ if (expr->synthetic) {
+ return;
+ }
+
+ const struct bfs_ctx *ctx = state->ctx;
+ if (!bfs_warning_prefix(ctx)) {
+ return;
+ }
+
+ size_t offset = 0;
+ size_t start = SIZE_MAX, end = SIZE_MAX;
+ for (size_t i = 0; ctx->argv[i]; ++i) {
+ if (i > 0) {
+ cfprintf(ctx->cerr, " ");
+ offset += 1;
+ }
+
+ if (expr->argv == &ctx->argv[i]) {
+ start = offset;
+ }
+
+ cfprintf(ctx->cerr, "%s", ctx->argv[i]);
+ offset += strlen(ctx->argv[i]);
+
+ if (&expr->argv[expr->argc - 1] == &ctx->argv[i]) {
+ end = offset;
+ }
+ }
+ cfprintf(ctx->cerr, "\n");
+
+ assert(start <= offset);
+ assert(end <= offset);
+
+ bfs_warning_prefix(ctx);
+ for (size_t i = 0; i < end; ++i) {
+ if (i < start) {
+ fputc(' ', stderr);
+ } else {
+ fputc('~', stderr);
+ }
+ }
+ fputc('\n', stderr);
+
+ bfs_vwarning(ctx, format, args);
+}
+
+/** Warn about an expression. */
+BFS_FORMATTER(3, 4)
+static void opt_warning(const struct opt_state *state, const struct bfs_expr *expr, const char *format, ...) {
+ va_list args;
+ va_start(args, format);
+ opt_vwarning(state, expr, format, args);
+ va_end(args);
+}
+
/** Extract a child expression, freeing the outer expression. */
static struct bfs_expr *extract_child_expr(struct bfs_expr *expr, struct bfs_expr **child) {
struct bfs_expr *ret = *child;
@@ -367,7 +441,7 @@ static struct bfs_expr *optimize_or_expr(const struct opt_state *state, struct b
* Apply De Morgan's laws.
*/
static struct bfs_expr *de_morgan(const struct opt_state *state, struct bfs_expr *expr, char **argv) {
- bool debug = debug_opt(state, 1, "De Morgan's laws: %pe ", expr);
+ bool debug = opt_debug(state, 1, "De Morgan's laws: %pe ", expr);
struct bfs_expr *parent = negate_expr(expr, argv);
if (!parent) {
@@ -446,18 +520,18 @@ static struct bfs_expr *optimize_not_expr(const struct opt_state *state, struct
int optlevel = state->ctx->optlevel;
if (optlevel >= 1) {
if (rhs == &bfs_true) {
- debug_opt(state, 1, "constant propagation: %pe <==> %pe\n", expr, &bfs_false);
+ opt_debug(state, 1, "constant propagation: %pe <==> %pe\n", expr, &bfs_false);
bfs_expr_free(expr);
return &bfs_false;
} else if (rhs == &bfs_false) {
- debug_opt(state, 1, "constant propagation: %pe <==> %pe\n", expr, &bfs_true);
+ opt_debug(state, 1, "constant propagation: %pe <==> %pe\n", expr, &bfs_true);
bfs_expr_free(expr);
return &bfs_true;
} else if (rhs->eval_fn == eval_not) {
- debug_opt(state, 1, "double negation: %pe <==> %pe\n", expr, rhs->rhs);
+ opt_debug(state, 1, "double negation: %pe <==> %pe\n", expr, rhs->rhs);
return extract_child_expr(expr, &rhs->rhs);
} else if (bfs_expr_never_returns(rhs)) {
- debug_opt(state, 1, "reachability: %pe <==> %pe\n", expr, rhs);
+ opt_debug(state, 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)) {
@@ -503,16 +577,16 @@ static struct bfs_expr *optimize_and_expr(const struct opt_state *state, struct
int optlevel = ctx->optlevel;
if (optlevel >= 1) {
if (lhs == &bfs_true) {
- debug_opt(state, 1, "conjunction elimination: %pe <==> %pe\n", expr, rhs);
+ opt_debug(state, 1, "conjunction elimination: %pe <==> %pe\n", expr, rhs);
return extract_child_expr(expr, &expr->rhs);
} else if (rhs == &bfs_true) {
- debug_opt(state, 1, "conjunction elimination: %pe <==> %pe\n", expr, lhs);
+ opt_debug(state, 1, "conjunction elimination: %pe <==> %pe\n", expr, lhs);
return extract_child_expr(expr, &expr->lhs);
} else if (lhs->always_false) {
- debug_opt(state, 1, "short-circuit: %pe <==> %pe\n", expr, lhs);
+ opt_debug(state, 1, "short-circuit: %pe <==> %pe\n", expr, lhs);
return extract_child_expr(expr, &expr->lhs);
} else if (lhs->always_true && rhs == &bfs_false) {
- bool debug = debug_opt(state, 1, "strength reduction: %pe <==> ", expr);
+ bool debug = opt_debug(state, 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) {
@@ -520,7 +594,7 @@ static struct bfs_expr *optimize_and_expr(const struct opt_state *state, struct
}
return ret;
} else if (optlevel >= 2 && lhs->pure && rhs == &bfs_false) {
- debug_opt(state, 2, "purity: %pe <==> %pe\n", expr, rhs);
+ opt_debug(state, 2, "purity: %pe <==> %pe\n", expr, rhs);
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);
@@ -572,16 +646,16 @@ static struct bfs_expr *optimize_or_expr(const struct opt_state *state, struct b
int optlevel = ctx->optlevel;
if (optlevel >= 1) {
if (lhs->always_true) {
- debug_opt(state, 1, "short-circuit: %pe <==> %pe\n", expr, lhs);
+ opt_debug(state, 1, "short-circuit: %pe <==> %pe\n", expr, lhs);
return extract_child_expr(expr, &expr->lhs);
} else if (lhs == &bfs_false) {
- debug_opt(state, 1, "disjunctive syllogism: %pe <==> %pe\n", expr, rhs);
+ opt_debug(state, 1, "disjunctive syllogism: %pe <==> %pe\n", expr, rhs);
return extract_child_expr(expr, &expr->rhs);
} else if (rhs == &bfs_false) {
- debug_opt(state, 1, "disjunctive syllogism: %pe <==> %pe\n", expr, lhs);
+ opt_debug(state, 1, "disjunctive syllogism: %pe <==> %pe\n", expr, lhs);
return extract_child_expr(expr, &expr->lhs);
} else if (lhs->always_false && rhs == &bfs_true) {
- bool debug = debug_opt(state, 1, "strength reduction: %pe <==> ", expr);
+ bool debug = opt_debug(state, 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) {
@@ -589,7 +663,7 @@ static struct bfs_expr *optimize_or_expr(const struct opt_state *state, struct b
}
return ret;
} else if (optlevel >= 2 && lhs->pure && rhs == &bfs_true) {
- debug_opt(state, 2, "purity: %pe <==> %pe\n", expr, rhs);
+ opt_debug(state, 2, "purity: %pe <==> %pe\n", expr, rhs);
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);
@@ -637,12 +711,13 @@ static struct bfs_expr *ignore_result(const struct opt_state *state, struct bfs_
if (optlevel >= 1) {
while (true) {
if (expr->eval_fn == eval_not) {
- debug_opt(state, 1, "ignored result: %pe --> %pe\n", expr, expr->rhs);
+ opt_debug(state, 1, "ignored result: %pe --> %pe\n", expr, expr->rhs);
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) {
- debug_opt(state, 2, "ignored result: %pe --> %pe\n", expr, expr->lhs);
+ 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");
expr = extract_child_expr(expr, &expr->lhs);
} else {
break;
@@ -650,7 +725,8 @@ static struct bfs_expr *ignore_result(const struct opt_state *state, struct bfs_
}
if (optlevel >= 2 && expr->pure && expr != &bfs_false) {
- debug_opt(state, 2, "ignored result: %pe --> %pe\n", expr, &bfs_false);
+ opt_debug(state, 2, "ignored result: %pe --> %pe\n", expr, &bfs_false);
+ opt_warning(state, expr, "The result of this expression is ignored.\n\n");
bfs_expr_free(expr);
expr = &bfs_false;
}
@@ -671,14 +747,15 @@ static struct bfs_expr *optimize_comma_expr(const struct opt_state *state, struc
lhs = expr->lhs = ignore_result(state, lhs);
if (bfs_expr_never_returns(lhs)) {
- debug_opt(state, 1, "reachability: %pe <==> %pe\n", expr, lhs);
+ opt_debug(state, 1, "reachability: %pe <==> %pe\n", expr, lhs);
+ opt_warning(state, expr->rhs, "This expression is unreachable.\n\n");
return extract_child_expr(expr, &expr->lhs);
} else if ((lhs->always_true && rhs == &bfs_true)
|| (lhs->always_false && rhs == &bfs_false)) {
- debug_opt(state, 1, "redundancy elimination: %pe <==> %pe\n", expr, lhs);
+ opt_debug(state, 1, "redundancy elimination: %pe <==> %pe\n", expr, lhs);
return extract_child_expr(expr, &expr->lhs);
} else if (optlevel >= 2 && lhs->pure) {
- debug_opt(state, 2, "purity: %pe <==> %pe\n", expr, rhs);
+ opt_debug(state, 2, "purity: %pe <==> %pe\n", expr, rhs);
return extract_child_expr(expr, &expr->rhs);
}
}
@@ -812,7 +889,8 @@ static struct bfs_expr *optimize_expr_recursive(struct opt_state *state, struct
state->facts_when_false = state->facts;
if (optlevel >= 2 && facts_are_impossible(&state->facts)) {
- debug_opt(state, 2, "reachability: %pe --> %pe\n", expr, &bfs_false);
+ opt_debug(state, 2, "reachability: %pe --> %pe\n", expr, &bfs_false);
+ opt_warning(state, expr, "This expression is unreachable.\n\n");
bfs_expr_free(expr);
expr = &bfs_false;
goto done;
@@ -900,7 +978,8 @@ static struct bfs_expr *optimize_expr_recursive(struct opt_state *state, struct
if (facts_are_impossible(&state->facts_when_true)) {
if (expr->pure) {
- debug_opt(state, 2, "data flow: %pe --> %pe\n", expr, &bfs_false);
+ opt_debug(state, 2, "data flow: %pe --> %pe\n", expr, &bfs_false);
+ opt_warning(state, expr, "This expression is always false.\n\n");
bfs_expr_free(expr);
expr = &bfs_false;
} else {
@@ -909,7 +988,8 @@ static struct bfs_expr *optimize_expr_recursive(struct opt_state *state, struct
}
} else if (facts_are_impossible(&state->facts_when_false)) {
if (expr->pure) {
- debug_opt(state, 2, "data flow: %pe --> %pe\n", expr, &bfs_true);
+ opt_debug(state, 2, "data flow: %pe --> %pe\n", expr, &bfs_true);
+ opt_warning(state, expr, "This expression is always true.\n\n");
bfs_expr_free(expr);
expr = &bfs_true;
} else {
@@ -925,7 +1005,7 @@ done:
/** 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, double swapped_cost) {
if (swapped_cost < expr->cost) {
- bool debug = debug_opt(state, 3, "cost: %pe <==> ", expr);
+ bool debug = opt_debug(state, 3, "cost: %pe <==> ", expr);
struct bfs_expr *lhs = expr->lhs;
expr->lhs = expr->rhs;
expr->rhs = lhs;
@@ -1043,7 +1123,7 @@ int bfs_optimize(struct bfs_ctx *ctx) {
mindepth = INT_MAX;
}
ctx->mindepth = mindepth;
- debug_opt(&state, 2, "data flow: mindepth --> %d\n", ctx->mindepth);
+ opt_debug(&state, 2, "data flow: mindepth --> %d\n", ctx->mindepth);
}
if (optlevel >= 4 && maxdepth < ctx->maxdepth) {
@@ -1051,7 +1131,7 @@ int bfs_optimize(struct bfs_ctx *ctx) {
maxdepth = INT_MIN;
}
ctx->maxdepth = maxdepth;
- debug_opt(&state, 4, "data flow: maxdepth --> %d\n", ctx->maxdepth);
+ opt_debug(&state, 4, "data flow: maxdepth --> %d\n", ctx->maxdepth);
}
return 0;
diff --git a/parse.c b/parse.c
index 0019987..87d73e3 100644
--- a/parse.c
+++ b/parse.c
@@ -79,6 +79,7 @@ struct bfs_expr bfs_true = {
.argv = &fake_true_arg,
.pure = true,
.always_true = true,
+ .synthetic = true,
.cost = FAST_COST,
.probability = 1.0,
};
@@ -89,6 +90,7 @@ struct bfs_expr bfs_false = {
.argv = &fake_false_arg,
.pure = true,
.always_false = true,
+ .synthetic = true,
.cost = FAST_COST,
.probability = 0.0,
};
@@ -127,6 +129,7 @@ struct bfs_expr *bfs_expr_new(bfs_eval_fn *eval_fn, size_t argc, char **argv) {
expr->pure = false;
expr->always_true = false;
expr->always_false = false;
+ expr->synthetic = false;
expr->cost = FAST_COST;
expr->probability = 0.5;
expr->evaluations = 0;
@@ -1860,6 +1863,7 @@ static struct bfs_expr *parse_nohidden(struct parser_state *state, int arg1, int
hidden->probability = 0.01;
hidden->pure = true;
+ hidden->synthetic = true;
struct bfs_ctx *ctx = state->ctx;
ctx->exclude = new_binary_expr(eval_or, ctx->exclude, hidden, &fake_or_arg);
@@ -3484,6 +3488,7 @@ static struct bfs_expr *parse_whole_expr(struct parser_state *state) {
goto fail;
}
init_print_expr(state, print);
+ print->synthetic = true;
expr = new_binary_expr(eval_and, expr, print, &fake_and_arg);
if (!expr) {
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-02 08:13:06 +0000