1 files changed, 254 insertions, 105 deletions

diff --git a/gcc/tree-ssa-forwprop.cc b/gcc/tree-ssa-forwprop.cc
index 75901ec..43b1c9d 100644
--- a/gcc/tree-ssa-forwprop.cc
+++ b/gcc/tree-ssa-forwprop.cc
@@ -1343,6 +1343,88 @@ optimize_memcpy_to_memset (gimple_stmt_iterator *gsip, tree dest, tree src, tree
     }
   return true;
 }
+/* Optimizes
+   a = c;
+   b = a;
+   into
+   a = c;
+   b = c;
+   GSIP is the second statement and SRC is the common
+   between the statements.
+*/
+static bool
+optimize_agr_copyprop (gimple_stmt_iterator *gsip)
+{
+  gimple *stmt = gsi_stmt (*gsip);
+  if (gimple_has_volatile_ops (stmt))
+    return false;
+
+  tree dest = gimple_assign_lhs (stmt);
+  tree src = gimple_assign_rhs1 (stmt);
+  /* If the statement is `src = src;` then ignore it. */
+  if (operand_equal_p (dest, src, 0))
+    return false;
+
+  tree vuse = gimple_vuse (stmt);
+  /* If the vuse is the default definition, then there is no store beforehand.  */
+  if (SSA_NAME_IS_DEFAULT_DEF (vuse))
+    return false;
+  gimple *defstmt = SSA_NAME_DEF_STMT (vuse);
+  if (!gimple_assign_load_p (defstmt)
+      || !gimple_store_p (defstmt))
+    return false;
+  if (gimple_has_volatile_ops (defstmt))
+    return false;
+
+  tree dest2 = gimple_assign_lhs (defstmt);
+  tree src2 = gimple_assign_rhs1 (defstmt);
+
+  /* If the original store is `src2 = src2;` skip over it. */
+  if (operand_equal_p (src2, dest2, 0))
+    return false;
+  if (!operand_equal_p (src, dest2, 0))
+    return false;
+
+
+  /* For 2 memory refences and using a temporary to do the copy,
+     don't remove the temporary as the 2 memory references might overlap.
+     Note t does not need to be decl as it could be field.
+     See PR 22237 for full details.
+     E.g.
+     t = *a;
+     *b = t;
+     Cannot be convert into
+     t = *a;
+     *b = *a;
+     Though the following is allowed to be done:
+     t = *a;
+     *a = t;
+     And convert it into:
+     t = *a;
+     *a = *a;
+  */
+  if (!operand_equal_p (src2, dest, 0)
+      && !DECL_P (dest) && !DECL_P (src2))
+    return false;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Simplified\n  ");
+      print_gimple_stmt (dump_file, stmt, 0, dump_flags);
+      fprintf (dump_file, "after previous\n  ");
+      print_gimple_stmt (dump_file, defstmt, 0, dump_flags);
+    }
+  gimple_assign_set_rhs_from_tree (gsip, unshare_expr (src2));
+  update_stmt (stmt);
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "into\n  ");
+      print_gimple_stmt (dump_file, stmt, 0, dump_flags);
+    }
+  statistics_counter_event (cfun, "copy prop for aggregate", 1);
+  return true;
+}
 
 /* *GSI_P is a GIMPLE_CALL to a builtin function.
    Optimize
@@ -2426,17 +2508,16 @@ simplify_rotate (gimple_stmt_iterator *gsi)
 }
 
 
-/* Check whether an array contains a valid ctz table.  */
+/* Check whether an array contains a valid table according to VALIDATE_FN.  */
+template<typename ValidateFn>
 static bool
-check_ctz_array (tree ctor, unsigned HOST_WIDE_INT mulc,
-		 HOST_WIDE_INT &zero_val, unsigned shift, unsigned bits)
+check_table_array (tree ctor, HOST_WIDE_INT &zero_val, unsigned bits,
+		  ValidateFn validate_fn)
 {
   tree elt, idx;
-  unsigned HOST_WIDE_INT i, mask, raw_idx = 0;
+  unsigned HOST_WIDE_INT i, raw_idx = 0;
   unsigned matched = 0;
 
-  mask = ((HOST_WIDE_INT_1U << (bits - shift)) - 1) << shift;
-
   zero_val = 0;
 
   FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), i, idx, elt)
@@ -2476,7 +2557,7 @@ check_ctz_array (tree ctor, unsigned HOST_WIDE_INT mulc,
 	  matched++;
 	}
 
-      if (val >= 0 && val < bits && (((mulc << val) & mask) >> shift) == index)
+      if (val >= 0 && val < bits && validate_fn (val, index))
 	matched++;
 
       if (matched > bits)
@@ -2486,48 +2567,86 @@ check_ctz_array (tree ctor, unsigned HOST_WIDE_INT mulc,
   return false;
 }
 
-/* Check whether a string contains a valid ctz table.  */
+/* Check whether a string contains a valid table according to VALIDATE_FN.  */
+template<typename ValidateFn>
 static bool
-check_ctz_string (tree string, unsigned HOST_WIDE_INT mulc,
-		  HOST_WIDE_INT &zero_val, unsigned shift, unsigned bits)
+check_table_string (tree string, HOST_WIDE_INT &zero_val,unsigned bits,
+		    ValidateFn validate_fn)
 {
   unsigned HOST_WIDE_INT len = TREE_STRING_LENGTH (string);
-  unsigned HOST_WIDE_INT mask;
   unsigned matched = 0;
   const unsigned char *p = (const unsigned char *) TREE_STRING_POINTER (string);
 
   if (len < bits || len > bits * 2)
     return false;
 
-  mask = ((HOST_WIDE_INT_1U << (bits - shift)) - 1) << shift;
-
   zero_val = p[0];
 
   for (unsigned i = 0; i < len; i++)
-    if (p[i] < bits && (((mulc << p[i]) & mask) >> shift) == i)
+    if (p[i] < bits && validate_fn (p[i], i))
       matched++;
 
   return matched == bits;
 }
 
-/* Recognize count trailing zeroes idiom.
+/* Check whether CTOR contains a valid table according to VALIDATE_FN.  */
+template<typename ValidateFn>
+static bool
+check_table (tree ctor, tree type, HOST_WIDE_INT &zero_val, unsigned bits,
+	     ValidateFn validate_fn)
+{
+  if (TREE_CODE (ctor) == CONSTRUCTOR)
+    return check_table_array (ctor, zero_val, bits, validate_fn);
+  else if (TREE_CODE (ctor) == STRING_CST
+	   && TYPE_PRECISION (type) == CHAR_TYPE_SIZE)
+    return check_table_string (ctor, zero_val, bits, validate_fn);
+  return false;
+}
+
+/* Match.pd function to match the ctz expression.  */
+extern bool gimple_ctz_table_index (tree, tree *, tree (*)(tree));
+extern bool gimple_clz_table_index (tree, tree *, tree (*)(tree));
+
+/* Recognize count leading and trailing zeroes idioms.
    The canonical form is array[((x & -x) * C) >> SHIFT] where C is a magic
    constant which when multiplied by a power of 2 creates a unique value
    in the top 5 or 6 bits.  This is then indexed into a table which maps it
    to the number of trailing zeroes.  Array[0] is returned so the caller can
    emit an appropriate sequence depending on whether ctz (0) is defined on
    the target.  */
+
 static bool
-optimize_count_trailing_zeroes (tree array_ref, tree x, tree mulc,
-				tree tshift, HOST_WIDE_INT &zero_val)
+simplify_count_zeroes (gimple_stmt_iterator *gsi)
 {
-  tree type = TREE_TYPE (array_ref);
-  tree array = TREE_OPERAND (array_ref, 0);
+  gimple *stmt = gsi_stmt (*gsi);
+  tree array_ref = gimple_assign_rhs1 (stmt);
+  tree res_ops[3];
 
-  gcc_assert (TREE_CODE (mulc) == INTEGER_CST);
-  gcc_assert (TREE_CODE (tshift) == INTEGER_CST);
+  gcc_checking_assert (TREE_CODE (array_ref) == ARRAY_REF);
 
-  tree input_type = TREE_TYPE (x);
+  internal_fn fn = IFN_LAST;
+  /* For CTZ we recognize ((x & -x) * C) >> SHIFT where the array data
+     represents the number of trailing zeros.  */
+  if (gimple_ctz_table_index (TREE_OPERAND (array_ref, 1), &res_ops[0], NULL))
+    fn = IFN_CTZ;
+  /* For CLZ we recognize
+       x |= x >> 1;
+       x |= x >> 2;
+       x |= x >> 4;
+       x |= x >> 8;
+       x |= x >> 16;
+       (x * C) >> SHIFT
+     where 31 minus the array data represents the number of leading zeros.  */
+  else if (gimple_clz_table_index (TREE_OPERAND (array_ref, 1), &res_ops[0],
+				   NULL))
+    fn = IFN_CLZ;
+  else
+    return false;
+
+  HOST_WIDE_INT zero_val;
+  tree type = TREE_TYPE (array_ref);
+  tree array = TREE_OPERAND (array_ref, 0);
+  tree input_type = TREE_TYPE (res_ops[0]);
   unsigned input_bits = tree_to_shwi (TYPE_SIZE (input_type));
 
   /* Check the array element type is not wider than 32 bits and the input is
@@ -2537,7 +2656,7 @@ optimize_count_trailing_zeroes (tree array_ref, tree x, tree mulc,
   if (input_bits != 32 && input_bits != 64)
     return false;
 
-  if (!direct_internal_fn_supported_p (IFN_CTZ, input_type, OPTIMIZE_FOR_BOTH))
+  if (!direct_internal_fn_supported_p (fn, input_type, OPTIMIZE_FOR_BOTH))
     return false;
 
   /* Check the lower bound of the array is zero.  */
@@ -2545,102 +2664,127 @@ optimize_count_trailing_zeroes (tree array_ref, tree x, tree mulc,
   if (!low || !integer_zerop (low))
     return false;
 
-  unsigned shiftval = tree_to_shwi (tshift);
-
   /* Check the shift extracts the top 5..7 bits.  */
+  unsigned shiftval = tree_to_shwi (res_ops[2]);
   if (shiftval < input_bits - 7 || shiftval > input_bits - 5)
     return false;
 
   tree ctor = ctor_for_folding (array);
   if (!ctor)
     return false;
-
-  unsigned HOST_WIDE_INT val = tree_to_uhwi (mulc);
-
-  if (TREE_CODE (ctor) == CONSTRUCTOR)
-    return check_ctz_array (ctor, val, zero_val, shiftval, input_bits);
-
-  if (TREE_CODE (ctor) == STRING_CST
-      && TYPE_PRECISION (type) == CHAR_TYPE_SIZE)
-    return check_ctz_string (ctor, val, zero_val, shiftval, input_bits);
-
-  return false;
-}
-
-/* Match.pd function to match the ctz expression.  */
-extern bool gimple_ctz_table_index (tree, tree *, tree (*)(tree));
-
-static bool
-simplify_count_trailing_zeroes (gimple_stmt_iterator *gsi)
-{
-  gimple *stmt = gsi_stmt (*gsi);
-  tree array_ref = gimple_assign_rhs1 (stmt);
-  tree res_ops[3];
-  HOST_WIDE_INT zero_val;
-
-  gcc_checking_assert (TREE_CODE (array_ref) == ARRAY_REF);
-
-  if (!gimple_ctz_table_index (TREE_OPERAND (array_ref, 1), &res_ops[0], NULL))
-    return false;
-
-  if (optimize_count_trailing_zeroes (array_ref, res_ops[0],
-				      res_ops[1], res_ops[2], zero_val))
+  unsigned HOST_WIDE_INT mulval = tree_to_uhwi (res_ops[1]);
+  if (fn == IFN_CTZ)
     {
-      tree type = TREE_TYPE (res_ops[0]);
-      HOST_WIDE_INT ctz_val = 0;
-      HOST_WIDE_INT type_size = tree_to_shwi (TYPE_SIZE (type));
-      bool zero_ok
-	= CTZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (type), ctz_val) == 2;
-      int nargs = 2;
-
-      /* If the input value can't be zero, don't special case ctz (0).  */
-      if (tree_expr_nonzero_p (res_ops[0]))
+      auto checkfn = [&](unsigned data, unsigned i) -> bool
 	{
-	  zero_ok = true;
-	  zero_val = 0;
-	  ctz_val = 0;
-	  nargs = 1;
-	}
-
-      /* Skip if there is no value defined at zero, or if we can't easily
-	 return the correct value for zero.  */
-      if (!zero_ok)
+	  unsigned HOST_WIDE_INT mask
+	    = ((HOST_WIDE_INT_1U << (input_bits - shiftval)) - 1) << shiftval;
+	  return (((mulval << data) & mask) >> shiftval) == i;
+	};
+      if (!check_table (ctor, type, zero_val, input_bits, checkfn))
 	return false;
-      if (zero_val != ctz_val && !(zero_val == 0 && ctz_val == type_size))
-	return false;
-
-      gimple_seq seq = NULL;
-      gimple *g;
-      gcall *call
-	= gimple_build_call_internal (IFN_CTZ, nargs, res_ops[0],
-				      nargs == 1 ? NULL_TREE
-				      : build_int_cst (integer_type_node,
-						       ctz_val));
-      gimple_set_location (call, gimple_location (stmt));
-      gimple_set_lhs (call, make_ssa_name (integer_type_node));
-      gimple_seq_add_stmt (&seq, call);
-
-      tree prev_lhs = gimple_call_lhs (call);
-
-      /* Emit ctz (x) & 31 if ctz (0) is 32 but we need to return 0.  */
-      if (zero_val == 0 && ctz_val == type_size)
+    }
+  else if (fn == IFN_CLZ)
+    {
+      auto checkfn = [&](unsigned data, unsigned i) -> bool
 	{
-	  g = gimple_build_assign (make_ssa_name (integer_type_node),
-				   BIT_AND_EXPR, prev_lhs,
-				   build_int_cst (integer_type_node,
-						  type_size - 1));
-	  gimple_set_location (g, gimple_location (stmt));
-	  gimple_seq_add_stmt (&seq, g);
-	  prev_lhs = gimple_assign_lhs (g);
-	}
+	  unsigned HOST_WIDE_INT mask
+	    = ((HOST_WIDE_INT_1U << (input_bits - shiftval)) - 1) << shiftval;
+	  return (((((HOST_WIDE_INT_1U << (data + 1)) - 1) * mulval) & mask)
+		  >> shiftval) == i;
+	};
+    if (!check_table (ctor, type, zero_val, input_bits, checkfn))
+      return false;
+    }
 
-      g = gimple_build_assign (gimple_assign_lhs (stmt), NOP_EXPR, prev_lhs);
+  HOST_WIDE_INT ctz_val = -1;
+  bool zero_ok;
+  if (fn == IFN_CTZ)
+    {
+      ctz_val = 0;
+      zero_ok = CTZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (input_type),
+					   ctz_val) == 2;
+    }
+  else if (fn == IFN_CLZ)
+    {
+      ctz_val = 32;
+      zero_ok = CLZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (input_type),
+					   ctz_val) == 2;
+      zero_val = input_bits - 1 - zero_val;
+    }
+  int nargs = 2;
+
+  /* If the input value can't be zero, don't special case ctz (0).  */
+  range_query *q = get_range_query (cfun);
+  if (q == get_global_range_query ())
+    q = enable_ranger (cfun);
+  int_range_max vr;
+  if (q->range_of_expr (vr, res_ops[0], stmt)
+      && !range_includes_zero_p (vr))
+    {
+      zero_ok = true;
+      zero_val = 0;
+      ctz_val = 0;
+      nargs = 1;
+    }
+
+  gimple_seq seq = NULL;
+  gimple *g;
+  gcall *call = gimple_build_call_internal (fn, nargs, res_ops[0],
+					    nargs == 1 ? NULL_TREE
+					    : build_int_cst (integer_type_node,
+							     ctz_val));
+  gimple_set_location (call, gimple_location (stmt));
+  gimple_set_lhs (call, make_ssa_name (integer_type_node));
+  gimple_seq_add_stmt (&seq, call);
+
+  tree prev_lhs = gimple_call_lhs (call);
+  if (fn == IFN_CLZ)
+    {
+      g = gimple_build_assign (make_ssa_name (integer_type_node),
+			       MINUS_EXPR,
+			       build_int_cst (integer_type_node,
+					      input_bits - 1),
+			       prev_lhs);
+      gimple_set_location (g, gimple_location (stmt));
       gimple_seq_add_stmt (&seq, g);
-      gsi_replace_with_seq (gsi, seq, true);
-      return true;
+      prev_lhs = gimple_assign_lhs (g);
     }
 
-  return false;
+  if (zero_ok && zero_val == ctz_val)
+    ;
+  /* Emit ctz (x) & 31 if ctz (0) is 32 but we need to return 0.  */
+  else if (zero_ok && zero_val == 0 && ctz_val == input_bits)
+    {
+      g = gimple_build_assign (make_ssa_name (integer_type_node),
+			       BIT_AND_EXPR, prev_lhs,
+			       build_int_cst (integer_type_node,
+					      input_bits - 1));
+      gimple_set_location (g, gimple_location (stmt));
+      gimple_seq_add_stmt (&seq, g);
+      prev_lhs = gimple_assign_lhs (g);
+    }
+  /* As fallback emit a conditional move.  */
+  else
+    {
+      g = gimple_build_assign (make_ssa_name (boolean_type_node), EQ_EXPR,
+			       res_ops[0], build_zero_cst (input_type));
+      gimple_set_location (g, gimple_location (stmt));
+      gimple_seq_add_stmt (&seq, g);
+      tree cond = gimple_assign_lhs (g);
+      g = gimple_build_assign (make_ssa_name (integer_type_node),
+			       COND_EXPR, cond,
+			       build_int_cst (integer_type_node, zero_val),
+			       prev_lhs);
+      gimple_set_location (g, gimple_location (stmt));
+      gimple_seq_add_stmt (&seq, g);
+      prev_lhs = gimple_assign_lhs (g);
+    }
+
+  g = gimple_build_assign (gimple_assign_lhs (stmt), NOP_EXPR, prev_lhs);
+  gimple_seq_add_stmt (&seq, g);
+  gsi_replace_with_seq (gsi, seq, true);
+  return true;
 }
 
 
@@ -4724,6 +4868,11 @@ pass_forwprop::execute (function *fun)
 			    changed = true;
 			    break;
 			  }
+			if (optimize_agr_copyprop (&gsi))
+			  {
+			    changed = true;
+			    break;
+			  }
 		      }
 
 		    if (TREE_CODE_CLASS (code) == tcc_comparison)
@@ -4750,7 +4899,7 @@ pass_forwprop::execute (function *fun)
 			     && TREE_CODE (TREE_TYPE (rhs1)) == VECTOR_TYPE)
 		      changed |= simplify_vector_constructor (&gsi);
 		    else if (code == ARRAY_REF)
-		      changed |= simplify_count_trailing_zeroes (&gsi);
+		      changed |= simplify_count_zeroes (&gsi);
 		    break;
 		  }