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
commitf7ecc531ace37997e08f4c64503e428780f6a228 (patch)
tree2687585c0c205d7cb5a91fd64fb3cb3065262cf0
parent3f2c4850a6bc41813e344babe2956408755c338f (diff)
downloadbfs-f7ecc531ace37997e08f4c64503e428780f6a228.tar.xz
Optimize using De Morgan's laws.
-rw-r--r--parse.c61
1 files changed, 61 insertions, 0 deletions
diff --git a/parse.c b/parse.c
index a94a668..2c02c83 100644
--- a/parse.c
+++ b/parse.c
@@ -29,6 +29,7 @@
// Strings printed by -D tree for "fake" expressions
static char *fake_and_arg = "-a";
static char *fake_false_arg = "-false";
+static char *fake_or_arg = "-o";
static char *fake_print_arg = "-print";
static char *fake_true_arg = "-true";
@@ -1316,6 +1317,9 @@ static struct expr *parse_literal(struct parser_state *state) {
return NULL;
}
+static struct expr *new_and_expr(const struct parser_state *state, struct expr *lhs, struct expr *rhs, char **argv);
+static struct expr *new_or_expr(const struct parser_state *state, struct expr *lhs, struct expr *rhs, char **argv);
+
/**
* Create a "not" expression.
*/
@@ -1333,6 +1337,31 @@ static struct expr *new_not_expr(const struct parser_state *state, struct expr *
rhs->rhs = NULL;
free_expr(rhs);
return expr;
+ } else if ((rhs->eval == eval_and || rhs->eval == eval_or)
+ && (rhs->lhs->eval == eval_not || rhs->rhs->eval == eval_not)) {
+ bool other_and = rhs->eval == eval_or;
+ char **other_arg = other_and ? &fake_and_arg : &fake_or_arg;
+
+ debug_opt(state, "-O1: De Morgan's laws: (%s %e) <==> (%s (%s %e) (%s %e))\n",
+ argv[0], rhs,
+ *other_arg, argv[0], rhs->lhs, argv[0], rhs->rhs);
+
+ struct expr *other_lhs = new_not_expr(state, rhs->lhs, argv);
+ struct expr *other_rhs = new_not_expr(state, rhs->rhs, argv);
+ rhs->rhs = NULL;
+ rhs->lhs = NULL;
+ free_expr(rhs);
+ if (!other_lhs || !other_rhs) {
+ free_expr(other_rhs);
+ free_expr(other_lhs);
+ return NULL;
+ }
+
+ if (other_and) {
+ return new_and_expr(state, other_lhs, other_rhs, other_arg);
+ } else {
+ return new_or_expr(state, other_lhs, other_rhs, other_arg);
+ }
}
}
@@ -1404,6 +1433,22 @@ static struct expr *new_and_expr(const struct parser_state *state, struct expr *
debug_opt(state, "-O2: purity: (%s %e %e) <==> %e\n", argv[0], lhs, rhs, rhs);
free_expr(lhs);
return rhs;
+ } else if (lhs->eval == eval_not && rhs->eval == eval_not) {
+ char **not_arg = lhs->argv;
+ debug_opt(state, "-O1: De Morgan's laws: (%s %e %e) <==> (%s (%s %e %e))\n",
+ argv[0], lhs, rhs,
+ *not_arg, fake_or_arg, lhs->rhs, rhs->rhs);
+
+ struct expr *or_expr = new_or_expr(state, lhs->rhs, rhs->rhs, &fake_or_arg);
+ rhs->rhs = NULL;
+ lhs->rhs = NULL;
+ free_expr(rhs);
+ free_expr(lhs);
+ if (!or_expr) {
+ return NULL;
+ }
+
+ return new_not_expr(state, or_expr, not_arg);
}
}
@@ -1470,6 +1515,22 @@ static struct expr *new_or_expr(const struct parser_state *state, struct expr *l
} else if (rhs == &expr_false) {
debug_opt(state, "-O1: disjunctive syllogism: (%s %e %e) <==> %e\n", argv[0], lhs, rhs, lhs);
return lhs;
+ } else if (lhs->eval == eval_not && rhs->eval == eval_not) {
+ char **not_arg = lhs->argv;
+ debug_opt(state, "-O1: De Morgan's laws: (%s %e %e) <==> (%s (%s %e %e))\n",
+ argv[0], lhs, rhs,
+ *not_arg, fake_and_arg, lhs->rhs, rhs->rhs);
+
+ struct expr *and_expr = new_and_expr(state, lhs->rhs, rhs->rhs, &fake_and_arg);
+ rhs->rhs = NULL;
+ lhs->rhs = NULL;
+ free_expr(rhs);
+ free_expr(lhs);
+ if (!and_expr) {
+ return NULL;
+ }
+
+ return new_not_expr(state, and_expr, not_arg);
}
}