summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@tavianator.com>2016-06-07 19:16:31 -0400
committerTavian Barnes <tavianator@tavianator.com>2016-06-07 19:16:31 -0400
commit21bd2698e78605917024c99b579f6daae3fb7003 (patch)
tree8b36e65fc9aaea8fd9eb0e6066e96a1d0e2dc703
parentcbb7cc9bf6d49ba922010f77c06cbea23f8e39de (diff)
downloadbfs-21bd2698e78605917024c99b579f6daae3fb7003.tar.xz
Implement -D opt.
-rw-r--r--bfs.h6
-rw-r--r--eval.c3
-rw-r--r--parse.c108
3 files changed, 88 insertions, 29 deletions
diff --git a/bfs.h b/bfs.h
index 13865fe..f6f120d 100644
--- a/bfs.h
+++ b/bfs.h
@@ -52,10 +52,12 @@ typedef bool eval_fn(const struct expr *expr, struct eval_state *state);
* Various debugging flags.
*/
enum debugflags {
+ /** Print optimization details. */
+ DEBUG_OPT = 1 << 0,
/** Trace all stat() calls. */
- DEBUG_STAT = 1 << 0,
+ DEBUG_STAT = 1 << 1,
/** Print the parse tree. */
- DEBUG_TREE = 1 << 1,
+ DEBUG_TREE = 1 << 2,
};
/**
diff --git a/eval.c b/eval.c
index 9ac0c6a..828a33f 100644
--- a/eval.c
+++ b/eval.c
@@ -908,6 +908,9 @@ int eval_cmdline(const struct cmdline *cmdline) {
}
if (cmdline->optlevel >= 3 && cmdline->expr->eval == eval_false) {
+ if (cmdline->debug & DEBUG_OPT) {
+ fputs("-O3: skipping evaluation of top-level -false\n", stderr);
+ }
return 0;
}
diff --git a/parse.c b/parse.c
index 4f86647..cb90e9b 100644
--- a/parse.c
+++ b/parse.c
@@ -17,6 +17,7 @@
#include <grp.h>
#include <limits.h>
#include <pwd.h>
+#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
@@ -113,6 +114,32 @@ static struct expr *new_binary_expr(eval_fn *eval, struct expr *lhs, struct expr
}
/**
+ * Dump the parsed expression tree, for debugging.
+ */
+static void dump_expr(const struct expr *expr) {
+ fputs("(", stderr);
+
+ for (size_t i = 0; i < expr->argc; ++i) {
+ if (i > 0) {
+ fputs(" ", stderr);
+ }
+ fputs(expr->argv[i], stderr);
+ }
+
+ if (expr->lhs) {
+ fputs(" ", stderr);
+ dump_expr(expr->lhs);
+ }
+
+ if (expr->rhs) {
+ fputs(" ", stderr);
+ dump_expr(expr->rhs);
+ }
+
+ fputs(")", stderr);
+}
+
+/**
* Free the parsed command line.
*/
void free_cmdline(struct cmdline *cmdline) {
@@ -168,6 +195,40 @@ struct parser_state {
};
/**
+ * Log an optimization.
+ */
+static void debug_opt(const struct parser_state *state, const char *format, ...) {
+ if (!(state->cmdline->debug & DEBUG_OPT)) {
+ return;
+ }
+
+ va_list args;
+ va_start(args, format);
+
+ for (const char *i = format; *i != '\0'; ++i) {
+ if (*i == '%') {
+ switch (*++i) {
+ case '%':
+ fputc('%', stderr);
+ break;
+
+ case 's':
+ fputs(va_arg(args, const char *), stderr);
+ break;
+
+ case 'e':
+ dump_expr(va_arg(args, const struct expr *));
+ break;
+ }
+ } else {
+ fputc(*i, stderr);
+ }
+ }
+
+ va_end(args);
+}
+
+/**
* Invoke stat() on an argument.
*/
static int stat_arg(const struct parser_state *state, struct expr *expr, struct stat *sb) {
@@ -447,11 +508,14 @@ static struct expr *parse_debug(struct parser_state *state) {
printf("Supported debug flags:\n\n");
printf(" help: This message.\n");
+ printf(" opt: Print optimization details.\n");
printf(" stat: Trace all stat() calls.\n");
printf(" tree: Print the parse tree.\n");
state->just_info = true;
return NULL;
+ } else if (strcmp(flag, "opt") == 0) {
+ cmdline->debug |= DEBUG_OPT;
} else if (strcmp(flag, "stat") == 0) {
cmdline->debug |= DEBUG_STAT;
} else if (strcmp(flag, "tree") == 0) {
@@ -1258,11 +1322,14 @@ static struct expr *parse_literal(struct parser_state *state) {
static struct expr *new_not_expr(const struct parser_state *state, struct expr *rhs, char **argv) {
if (state->cmdline->optlevel >= 1) {
if (rhs == &expr_true) {
+ debug_opt(state, "-O1: constant propagation: (%s %e) <==> %e\n", argv[0], rhs, &expr_false);
return &expr_false;
} else if (rhs == &expr_false) {
+ debug_opt(state, "-O1: constant propagation: (%s %e) <==> %e\n", argv[0], rhs, &expr_true);
return &expr_true;
} else if (rhs->eval == eval_not) {
struct expr *expr = rhs->rhs;
+ debug_opt(state, "-O1: double negation: (%s %e) <==> %e\n", argv[0], rhs, expr);
rhs->rhs = NULL;
free_expr(rhs);
return expr;
@@ -1320,13 +1387,17 @@ static struct expr *parse_factor(struct parser_state *state) {
static struct expr *new_and_expr(const struct parser_state *state, struct expr *lhs, struct expr *rhs, char **argv) {
if (state->cmdline->optlevel >= 1) {
if (lhs == &expr_true) {
+ debug_opt(state, "-O1: conjunction elimination: (%s %e %e) <==> %e\n", argv[0], lhs, rhs, rhs);
return rhs;
} else if (lhs == &expr_false) {
+ debug_opt(state, "-O1: short-circuit: (%s %e %e) <==> %e\n", argv[0], lhs, rhs, lhs);
free_expr(rhs);
return lhs;
} else if (rhs == &expr_true) {
+ debug_opt(state, "-O1: conjunction elimination: (%s %e %e) <==> %e\n", argv[0], lhs, rhs, lhs);
return lhs;
} else if (rhs == &expr_false && lhs->pure) {
+ debug_opt(state, "-O1: purity: (%s %e %e) <==> %e\n", argv[0], lhs, rhs, rhs);
free_expr(lhs);
return rhs;
}
@@ -1380,14 +1451,18 @@ static struct expr *parse_term(struct parser_state *state) {
static struct expr *new_or_expr(const struct parser_state *state, struct expr *lhs, struct expr *rhs, char **argv) {
if (state->cmdline->optlevel >= 1) {
if (lhs == &expr_true) {
+ debug_opt(state, "-O1: short-circuit: (%s %e %e) <==> %e\n", argv[0], lhs, rhs, lhs);
free_expr(rhs);
return lhs;
} else if (lhs == &expr_false) {
+ debug_opt(state, "-O1: disjunctive syllogism: (%s %e %e) <==> %e\n", argv[0], lhs, rhs, rhs);
return rhs;
} else if (rhs == &expr_true && lhs->pure) {
+ debug_opt(state, "-O1: purity: (%s %e %e) <==> %e\n", argv[0], lhs, rhs, rhs);
free_expr(lhs);
return rhs;
} else if (rhs == &expr_false) {
+ debug_opt(state, "-O1: disjunctive syllogism: (%s %e %e) <==> %e\n", argv[0], lhs, rhs, lhs);
return lhs;
}
}
@@ -1434,6 +1509,7 @@ static struct expr *parse_clause(struct parser_state *state) {
static struct expr *new_comma_expr(const struct parser_state *state, struct expr *lhs, struct expr *rhs, char **argv) {
if (state->cmdline->optlevel >= 1) {
if (lhs->pure) {
+ debug_opt(state, "-O1: purity: (%s %e %e) <==> %e\n", argv[0], lhs, rhs, rhs);
free_expr(lhs);
return rhs;
}
@@ -1475,32 +1551,6 @@ static struct expr *parse_expr(struct parser_state *state) {
}
/**
- * Dump the parsed expression tree, for debugging.
- */
-static void dump_expr(const struct expr *expr) {
- fputs("(", stderr);
-
- for (size_t i = 0; i < expr->argc; ++i) {
- if (i > 0) {
- fputs(" ", stderr);
- }
- fputs(expr->argv[i], stderr);
- }
-
- if (expr->lhs) {
- fputs(" ", stderr);
- dump_expr(expr->lhs);
- }
-
- if (expr->rhs) {
- fputs(" ", stderr);
- dump_expr(expr->rhs);
- }
-
- fputs(")", stderr);
-}
-
-/**
* Dump the parsed form of the command line, for debugging.
*/
static void dump_cmdline(const struct cmdline *cmdline) {
@@ -1516,6 +1566,9 @@ static void dump_cmdline(const struct cmdline *cmdline) {
fprintf(stderr, "-O%d ", cmdline->optlevel);
}
+ if (cmdline->debug & DEBUG_OPT) {
+ fputs("-D opt ", stderr);
+ }
if (cmdline->debug & DEBUG_STAT) {
fputs("-D stat ", stderr);
}
@@ -1616,7 +1669,8 @@ struct cmdline *parse_cmdline(int argc, char *argv[]) {
}
}
- if (cmdline->optlevel >= 3 && cmdline->expr->pure) {
+ if (cmdline->optlevel >= 3 && cmdline->expr->pure && cmdline->expr != &expr_false) {
+ debug_opt(&state, "-O3: top-level purity: %e <==> %e\n", cmdline->expr, &expr_false);
free_expr(cmdline->expr);
cmdline->expr = &expr_false;
}