1 files changed, 90 insertions, 3 deletions

diff --git a/gcc/tree-ssa-loop-niter.cc b/gcc/tree-ssa-loop-niter.cc
index 6e13086..cc76383 100644
--- a/gcc/tree-ssa-loop-niter.cc
+++ b/gcc/tree-ssa-loop-niter.cc
@@ -2321,6 +2321,48 @@ is_rshift_by_1 (gassign *stmt)
   return false;
 }
 
+/* Helper for number_of_iterations_cltz that uses ranger to determine
+   if SRC's range, shifted left (when LEFT_SHIFT is true) or right
+   by NUM_IGNORED_BITS, is guaranteed to be != 0 on LOOP's preheader
+   edge.
+   Return true if so or false otherwise.  */
+
+static bool
+shifted_range_nonzero_p (loop_p loop, tree src,
+			 bool left_shift, int num_ignored_bits)
+{
+  int_range_max r (TREE_TYPE (src));
+  gcc_assert (num_ignored_bits >= 0);
+
+  if (get_range_query (cfun)->range_on_edge
+      (r, loop_preheader_edge (loop), src)
+      && !r.varying_p ()
+      && !r.undefined_p ())
+    {
+      if (num_ignored_bits)
+	{
+	  range_op_handler op (left_shift ? LSHIFT_EXPR : RSHIFT_EXPR);
+	  int_range_max shifted_range (TREE_TYPE (src));
+	  wide_int shift_count = wi::shwi (num_ignored_bits,
+					   TYPE_PRECISION (TREE_TYPE
+							   (src)));
+	  int_range_max shift_amount
+	    (TREE_TYPE (src), shift_count, shift_count);
+
+	  if (op.fold_range (shifted_range, TREE_TYPE (src), r,
+			     shift_amount))
+	    r = shifted_range;
+	}
+
+      /* If the range does not contain zero we are good.  */
+      if (!range_includes_zero_p (r))
+	return true;
+    }
+
+  return false;
+}
+
+
 /* See comment below for number_of_iterations_bitcount.
    For c[lt]z, we have:
 
@@ -2438,6 +2480,9 @@ number_of_iterations_cltz (loop_p loop, edge exit,
   tree src = gimple_phi_arg_def (phi, loop_preheader_edge (loop)->dest_idx);
   int src_precision = TYPE_PRECISION (TREE_TYPE (src));
 
+  /* Save the original SSA name before preprocessing for ranger queries.  */
+  tree unshifted_src = src;
+
   /* Apply any needed preprocessing to src.  */
   int num_ignored_bits;
   if (left_shift)
@@ -2463,10 +2508,52 @@ number_of_iterations_cltz (loop_p loop, edge exit,
 
   expr = fold_convert (unsigned_type_node, expr);
 
-  tree assumptions = fold_build2 (NE_EXPR, boolean_type_node, src,
-				  build_zero_cst (TREE_TYPE (src)));
+  /* If the copy-header (ch) pass peeled one iteration we're shifting
+     SRC by preprocessing it above.
+
+     A loop like
+      if (bits)
+	{
+	  while (!(bits & 1))
+	    {
+	      bits >>= 1;
+	      cnt += 1;
+	    }
+	  return cnt;
+	}
+     ch (roughly) transforms into:
+      if (bits)
+	{
+	  if (!(bits & 1)
+	    {
+	      do
+		{
+		  bits >>= 1;
+		  cnt += 1;
+		} while (!(bits & 1));
+	    }
+	   else
+	     cnt = 1;
+	  return cnt;
+	}
+
+     Then, our preprocessed SRC (that is used for c[tl]z computation)
+     will be bits >> 1, and the assumption is bits >> 1 != 0.  */
+
+  tree assumptions;
+  if (shifted_range_nonzero_p (loop, unshifted_src,
+			       left_shift, num_ignored_bits))
+    assumptions = boolean_true_node;
+  else
+    {
+      /* If ranger couldn't prove the assumption, try
+	 simplify_using_initial_conditions.  */
+      assumptions = fold_build2 (NE_EXPR, boolean_type_node, src,
+				 build_zero_cst (TREE_TYPE (src)));
+      assumptions = simplify_using_initial_conditions (loop, assumptions);
+    }
 
-  niter->assumptions = simplify_using_initial_conditions (loop, assumptions);
+  niter->assumptions = assumptions;
   niter->may_be_zero = boolean_false_node;
   niter->niter = simplify_using_initial_conditions (loop, expr);