diff options
author | Tavian Barnes <tavianator@tavianator.com> | 2016-06-07 19:16:31 -0400 |
---|---|---|
committer | Tavian Barnes <tavianator@tavianator.com> | 2016-06-07 19:16:31 -0400 |
commit | f7ecc531ace37997e08f4c64503e428780f6a228 (patch) | |
tree | 2687585c0c205d7cb5a91fd64fb3cb3065262cf0 /parse.c | |
parent | 3f2c4850a6bc41813e344babe2956408755c338f (diff) | |
download | bfs-f7ecc531ace37997e08f4c64503e428780f6a228.tar.xz |
Optimize using De Morgan's laws.
Diffstat (limited to 'parse.c')
-rw-r--r-- | parse.c | 61 |
1 files changed, 61 insertions, 0 deletions
@@ -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); } } |