[PATCH 2/4 v3][PR 67328] Analyze some bit tests in VRP

[PATCH 2/4 v3][PR 67328] Analyze some bit tests in VRP

[Yuri Gribov]

[-- Attachment #1: Type: text/plain, Size: 80 bytes --]

This improve VRP handling for bitfield comparisons added by previous patch.

-I

[-- Attachment #2: 0002-Analyze-some-bit-tests-in-VRP.patch --]
[-- Type: application/octet-stream, Size: 3669 bytes --]

From f11d81a5f6cf1309e65c284072f5d5a164442082 Mon Sep 17 00:00:00 2001
From: Yury Gribov <tetra2005@gmail.com>
Date: Fri, 26 May 2017 07:56:47 +0100
Subject: [PATCH 2/4] Analyze some bit tests in VRP.

gcc/
2017-05-26  Yury Gribov  <tetra2005@gmail.com>

	* tree-vrp.c (is_masked_range_test): New function.
	(register_edge_assert_for): Determine ranges for
	some bit tests.
---
 gcc/tree-vrp.c | 95 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 95 insertions(+)

diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 716a7c2..71d23fb 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -5628,6 +5628,84 @@ register_edge_assert_for_1 (tree op, enum tree_code code,
     }
 }
 
+/* Check if comparison
+     NAME COND_OP INTEGER_CST
+   has a form of
+     (X & 11...100..0) COND_OP XX...X00...0
+   Such comparison can yield assertions like
+     X >= XX...X00...0
+     X <= XX...X11...1
+   in case of COND_OP being NE_EXPR or
+     X < XX...X00...0
+     X > XX...X11...1
+   in case of EQ_EXPR.  */
+
+static bool
+is_masked_range_test (tree name, tree valt, enum tree_code cond_code, bool is_else_edge,
+		      tree *new_name,
+		      tree *low, enum tree_code *low_code,
+		      tree *high, enum tree_code *high_code)
+{
+  gimple *def_stmt = SSA_NAME_DEF_STMT (name);
+
+  if (!is_gimple_assign (def_stmt)
+      || gimple_assign_rhs_code (def_stmt) != BIT_AND_EXPR)
+    return false;
+
+  tree maskt = gimple_assign_rhs2 (def_stmt);
+  if (TREE_CODE (maskt) != INTEGER_CST)
+    return false;
+
+  wide_int mask = maskt,
+    inv_mask = ~mask,
+    val = valt;  // Assume VALT is INTEGER_CST
+
+  if ((inv_mask & (inv_mask + 1)) != 0
+      || (val & mask) != val)
+    return false;
+
+  tree t = gimple_assign_rhs1 (def_stmt);
+  tree type = TREE_TYPE (t);
+
+//  bool is_range = (cond_code == EQ_EXPR) ^ is_else_edge;
+  bool is_range = cond_code == EQ_EXPR;
+
+  wide_int min = wi::min_value (type),
+    max = wi::max_value (type);
+
+  if (is_range)
+    {
+      *low_code = val == min ? (enum tree_code) 0 : GE_EXPR;
+      *high_code = val == max ? (enum tree_code) 0 : LE_EXPR;
+    }
+  else
+    {
+      /* We can still generate assertion if one of alternatives
+	 is known to always be false.  */
+      if (val == min)
+	{
+	  *low_code = (enum tree_code) 0;
+	  *high_code = GT_EXPR;
+	}
+      else if ((val | inv_mask) == max)
+	{
+	  *low_code = LT_EXPR;
+	  *high_code = (enum tree_code) 0;
+	}
+      else
+	return false;
+    }
+
+  *new_name = t;
+  *low = wide_int_to_tree (type, val);
+  *high = wide_int_to_tree (type, val | inv_mask);
+
+  if (wi::neg_p (val, TYPE_SIGN (type)))
+    std::swap (*low, *high);
+
+  return true;
+}
+
 /* Try to register an edge assertion for SSA name NAME on edge E for
    the condition COND contributing to the conditional jump pointed to by
    SI.  */
@@ -5700,6 +5778,23 @@ register_edge_assert_for (tree name, edge e,
 	  register_edge_assert_for_1 (op1, EQ_EXPR, e, asserts);
 	}
     }
+
+  /* Sometimes we can infer ranges from (NAME & MASK) == VALUE.  */
+  if ((comp_code == EQ_EXPR || comp_code == NE_EXPR)
+      && TREE_CODE (val) == INTEGER_CST)
+    {
+      enum tree_code low_code, high_code;
+      tree low, high;
+      if (is_masked_range_test (name, val, comp_code, is_else_edge, &name, &low, &low_code, &high, &high_code))
+	{
+	  if (low_code)
+	    register_edge_assert_for_2 (name, e, low_code, name,
+					low, /*invert*/false, asserts);
+	  if (high_code)
+	    register_edge_assert_for_2 (name, e, high_code, name,
+					high, /*invert*/false, asserts);
+	}
+    }
 }
 
 /* Finish found ASSERTS for E and register them at GSI.  */
-- 
2.7.4

Re: [PATCH 2/4 v3][PR 67328] Analyze some bit tests in VRP

[Richard Biener]

On Mon, 29 May 2017, Yuri Gribov wrote:

> This improve VRP handling for bitfield comparisons added by previous patch.
> 
> -I

+is_masked_range_test (tree name, tree valt, enum tree_code cond_code, 
bool is_else_edge,
+                     tree *new_name,

long line

+  wide_int mask = maskt,
+    inv_mask = ~mask,
+    val = valt;  // Assume VALT is INTEGER_CST

indent is off here, please use separate declarations:

  wide_int mask = maskt;
  wide_int inv_mask = ~mask;
...

+//  bool is_range = (cond_code == EQ_EXPR) ^ is_else_edge;
+  bool is_range = cond_code == EQ_EXPR;
+

do not leave dead code around.

+  if (is_range)
+    {
+      *low_code = val == min ? (enum tree_code) 0 : GE_EXPR;
+      *high_code = val == max ? (enum tree_code) 0 : LE_EXPR;
+    }

please use ERROR_MARK here instead of (enum tree_code) 0.

+       {
+         if (low_code)

and check with != ERROR_MARK here.

+      if (is_masked_range_test (name, val, comp_code, is_else_edge, 
&name, &low, &low_code, &high, &high_code))
+       {

long line again.

Otherwise looks ok.

Thanks,
Richard.