[Patch match.pd] Fold (A / (1 << B)) to (A >> B)

For the testcase in the patch:

  unsigned long
  f2 (unsigned long a, int b)
  {
    unsigned long x = 1UL << b;
    return a / x;
  }

We currently generate an unsigned division and a left shift, where
we could instead generate a right shift.

gcc/

2017-06-21  James Greenhalgh  <james.greenhalgh@arm.com>

	* match.pd (A / (1 << B) -> A >> B): New.
	* generic-match-head.c: Include optabs-tree.h.
	* gimple-match-head.c: Likewise.
	* optabs-tree.h (target_supports_op_p): New.
	* optabs-tree.c (target_supports_op_p): New.

gcc/testsuite/

2017-06-21  James Greenhalgh  <james.greenhalgh@arm.com>

	* gcc.dg/tree-ssa/forwprop-37.c: New.

From-SVN: r249502

8 files changed, 68 insertions, 0 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index c056ae4..9b150a4 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,11 @@
+2017-06-22  James Greenhalgh  <james.greenhalgh@arm.com>
+
+	* match.pd (A / (1 << B) -> A >> B): New.
+	* generic-match-head.c: Include optabs-tree.h.
+	* gimple-match-head.c: Likewise.
+	* optabs-tree.h (target_supports_op_p): New.
+	* optabs-tree.c (target_supports_op_p): New.
+
 2017-06-22  Rainer Orth  <ro@CeBiTec.Uni-Bielefeld.DE>
 
 	* configure.ac (gcc_cv_ld_static_dynamic): Also check stderr for
diff --git a/gcc/generic-match-head.c b/gcc/generic-match-head.c
index 0c0d182..4504401 100644
--- a/gcc/generic-match-head.c
+++ b/gcc/generic-match-head.c
@@ -33,6 +33,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "builtins.h"
 #include "case-cfn-macros.h"
 #include "gimplify.h"
+#include "optabs-tree.h"
 
 
 /* Routine to determine if the types T1 and T2 are effectively
diff --git a/gcc/gimple-match-head.c b/gcc/gimple-match-head.c
index e7e9839..5f6aa273 100644
--- a/gcc/gimple-match-head.c
+++ b/gcc/gimple-match-head.c
@@ -39,6 +39,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "internal-fn.h"
 #include "case-cfn-macros.h"
 #include "gimplify.h"
+#include "optabs-tree.h"
 
 
 /* Forward declarations of the private auto-generated matchers.
diff --git a/gcc/match.pd b/gcc/match.pd
index 7bd2676..a4cae11 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -161,6 +161,18 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
     (op @0 integer_onep)
     (non_lvalue @0)))
 
+/* (A / (1 << B)) -> (A >> B).
+   Only for unsigned A.  For signed A, this would not preserve rounding
+   toward zero.
+   For example: (-1 / ( 1 << B)) !=  -1 >> B.  */
+(simplify
+ (trunc_div @0 (lshift integer_onep@1 @2))
+ (if ((TYPE_UNSIGNED (type) || tree_expr_nonnegative_p (@0))
+      && (!VECTOR_TYPE_P (type)
+	  || target_supports_op_p (type, RSHIFT_EXPR, optab_vector)
+	  || target_supports_op_p (type, RSHIFT_EXPR, optab_scalar)))
+  (rshift @0 @2)))
+
 /* Preserve explicit divisions by 0: the C++ front-end wants to detect
    undefined behavior in constexpr evaluation, and assuming that the division
    traps enables better optimizations than these anyway.  */
diff --git a/gcc/optabs-tree.c b/gcc/optabs-tree.c
index 4bb54ba..c183b14 100644
--- a/gcc/optabs-tree.c
+++ b/gcc/optabs-tree.c
@@ -376,3 +376,18 @@ init_tree_optimization_optabs (tree optnode)
       ggc_free (tmp_optabs);
     }
 }
+
+/* Return TRUE if the target has support for vector right shift of an
+   operand of type TYPE.  If OT_TYPE is OPTAB_DEFAULT, check for existence
+   of a shift by either a scalar or a vector.  Otherwise, check only
+   for a shift that matches OT_TYPE.  */
+
+bool
+target_supports_op_p (tree type, enum tree_code code,
+		      enum optab_subtype ot_subtype)
+{
+  optab ot = optab_for_tree_code (code, type, ot_subtype);
+  return (ot != unknown_optab
+	  && optab_handler (ot, TYPE_MODE (type)) != CODE_FOR_nothing);
+}
+
diff --git a/gcc/optabs-tree.h b/gcc/optabs-tree.h
index d0b27e0..52e842b 100644
--- a/gcc/optabs-tree.h
+++ b/gcc/optabs-tree.h
@@ -41,5 +41,7 @@ bool supportable_convert_operation (enum tree_code, tree, tree, tree *,
 bool expand_vec_cmp_expr_p (tree, tree, enum tree_code);
 bool expand_vec_cond_expr_p (tree, tree, enum tree_code);
 void init_tree_optimization_optabs (tree);
+bool target_supports_op_p (tree, enum tree_code,
+			   enum optab_subtype = optab_default);
 
 #endif
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 050e37d..497c4b8 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,7 @@
+2017-06-22  James Greenhalgh  <james.greenhalgh@arm.com>
+
+	* gcc.dg/tree-ssa/forwprop-37.c: New.
+
 2017-06-22  Richard Biener  <rguenther@suse.de>
 
 	* gcc.dg/vect/pr65947-14.c: Fix missing brace.
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/forwprop-37.c b/gcc/testsuite/gcc.dg/tree-ssa/forwprop-37.c
new file mode 100644
index 0000000..dec826c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/forwprop-37.c
@@ -0,0 +1,25 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-forwprop1-raw" } */
+
+unsigned int
+f1 (unsigned int a, unsigned int b)
+{
+  unsigned int x = 1U << b;
+  return a / x;
+}
+
+unsigned long
+f2 (unsigned long a, int b)
+{
+  unsigned long x = 1UL << b;
+  return a / x;
+}
+
+unsigned long long
+f3 (unsigned long long a, int b)
+{
+  unsigned long long x = 1ULL << b;
+  return a / x;
+}
+
+/* { dg-final { scan-tree-dump-not "trunc_div_expr" "forwprop1" } } */