diff mbox

[ovs-dev,4/4] expr: Better simplify some special cases of expressions.

Message ID 1475811039-31662-4-git-send-email-blp@ovn.org
State Accepted
Headers show

Commit Message

Ben Pfaff Oct. 7, 2016, 3:30 a.m. UTC 
It's pretty unlikely that a human would write expressions like these, but
they can come up in machine-generated expressions and it seems best to
simplify them in an efficient way.

Signed-off-by: Ben Pfaff <blp@ovn.org>
---
 ovn/lib/expr.c | 41 ++++++++++++++++++++++++++++++++++-------
 tests/ovn.at   | 12 ++++++++++++
 2 files changed, 46 insertions(+), 7 deletions(-)

Comments

Andy Zhou Oct. 10, 2016, 11:52 p.m. UTC | #1 
On Thu, Oct 6, 2016 at 8:30 PM, Ben Pfaff <blp@ovn.org> wrote:

> It's pretty unlikely that a human would write expressions like these, but
> they can come up in machine-generated expressions and it seems best to
> simplify them in an efficient way.
>
> Signed-off-by: Ben Pfaff <blp@ovn.org>
>
Acked-by: Andy Zhou <azhou@ovn.org>
Ben Pfaff Oct. 11, 2016, 3:39 p.m. UTC | #2 
On Mon, Oct 10, 2016 at 04:52:07PM -0700, Andy Zhou wrote:
> On Thu, Oct 6, 2016 at 8:30 PM, Ben Pfaff <blp@ovn.org> wrote:
> 
> > It's pretty unlikely that a human would write expressions like these, but
> > they can come up in machine-generated expressions and it seems best to
> > simplify them in an efficient way.
> >
> > Signed-off-by: Ben Pfaff <blp@ovn.org>
> >
> Acked-by: Andy Zhou <azhou@ovn.org>

Thanks for the reviews!  I applied these to master and I'm planning to
apply the first three to branch-2.6 in a minute.
diff mbox

Patch

diff --git a/ovn/lib/expr.c b/ovn/lib/expr.c
index a197474..5399985 100644
--- a/ovn/lib/expr.c
+++ b/ovn/lib/expr.c
@@ -297,6 +297,10 @@  expr_fix(struct expr *expr)
 
 /* Formatting. */
 
+/* Searches bits [0,width) in 'sv' for a contiguous sequence of 1-bits.  If one
+ * such sequence exists, stores the index of the first 1-bit into '*startp' and
+ * the number of 1-bits into '*n_bitsp'.  Stores 0 into both variables if no
+ * such sequence, or more than one, exists. */
 static void
 find_bitwise_range(const union mf_subvalue *sv, int width,
                    int *startp, int *n_bitsp)
@@ -1729,18 +1733,41 @@  expr_simplify_relational(struct expr *expr)
     ovs_assert(n_bits > 0);
     end = start + n_bits;
 
-    struct expr *new;
-    if (expr->cmp.relop == EXPR_R_LE || expr->cmp.relop == EXPR_R_GE) {
+    /* Handle some special cases.
+     *
+     * These optimize to just "true":
+     *
+     *    tcp.dst >= 0
+     *    tcp.dst <= 65535
+     *
+     * These are easier to understand, and equivalent, when treated as if
+     * > or < were !=:
+     *
+     *    tcp.dst > 0
+     *    tcp.dst < 65535
+     */
+    bool lt = expr->cmp.relop == EXPR_R_LT || expr->cmp.relop == EXPR_R_LE;
+    bool eq = expr->cmp.relop == EXPR_R_LE || expr->cmp.relop == EXPR_R_GE;
+    if (bitwise_scan(value, sizeof *value, !lt, start, end) == end) {
+        if (eq) {
+            expr_destroy(expr);
+            return expr_create_boolean(true);
+        } else {
+            return expr_simplify_ne(expr);
+        }
+    }
+
+    /* Reduce "tcp.dst >= 1234" to "tcp.dst == 1234 || tcp.dst > 1234",
+     * and similarly for "tcp.dst <= 1234". */
+    struct expr *new = NULL;
+    if (eq) {
         new = xmemdup(expr, sizeof *expr);
         new->cmp.relop = EXPR_R_EQ;
-    } else {
-        new = NULL;
     }
 
-    bool b = expr->cmp.relop == EXPR_R_LT || expr->cmp.relop == EXPR_R_LE;
-    for (int z = bitwise_scan(value, sizeof *value, b, start, end);
+    for (int z = bitwise_scan(value, sizeof *value, lt, start, end);
          z < end;
-         z = bitwise_scan(value, sizeof *value, b, z + 1, end)) {
+         z = bitwise_scan(value, sizeof *value, lt, z + 1, end)) {
         struct expr *e;
 
         e = xmemdup(expr, sizeof *expr);
diff --git a/tests/ovn.at b/tests/ovn.at
index be85004..5f3f4df 100644
--- a/tests/ovn.at
+++ b/tests/ovn.at
@@ -433,6 +433,18 @@  AT_CHECK([simplify 'eth.dst == 0/0'], [0], [1
 ])
 AT_CHECK([simplify 'eth.dst != 0/0'], [0], [0
 ])
+AT_CHECK([simplify 'tcp.dst >= 0'], [0],
+    [ip.proto == 0x6 && (eth.type == 0x800 || eth.type == 0x86dd)
+])
+AT_CHECK([simplify 'tcp.dst <= 65535'], [0],
+    [ip.proto == 0x6 && (eth.type == 0x800 || eth.type == 0x86dd)
+])
+AT_CHECK([simplify 'tcp.dst > 0'], [0],
+    [[(tcp.dst[0] || tcp.dst[1] || tcp.dst[2] || tcp.dst[3] || tcp.dst[4] || tcp.dst[5] || tcp.dst[6] || tcp.dst[7] || tcp.dst[8] || tcp.dst[9] || tcp.dst[10] || tcp.dst[11] || tcp.dst[12] || tcp.dst[13] || tcp.dst[14] || tcp.dst[15]) && ip.proto == 0x6 && (eth.type == 0x800 || eth.type == 0x86dd)
+]])
+AT_CHECK([simplify 'tcp.dst < 65535'], [0],
+    [[(!tcp.dst[0] || !tcp.dst[1] || !tcp.dst[2] || !tcp.dst[3] || !tcp.dst[4] || !tcp.dst[5] || !tcp.dst[6] || !tcp.dst[7] || !tcp.dst[8] || !tcp.dst[9] || !tcp.dst[10] || !tcp.dst[11] || !tcp.dst[12] || !tcp.dst[13] || !tcp.dst[14] || !tcp.dst[15]) && ip.proto == 0x6 && (eth.type == 0x800 || eth.type == 0x86dd)
+]])
 AT_CLEANUP
 
 AT_SETUP([ovn -- 4-term numeric expression normalization])