[PATCH PR45098, 7/10] Nowrap limits iterations

[Tom de Vries <vries at codesourcery dot com>]

On 05/17/2011 09:20 AM, Tom de Vries wrote:
> On 05/17/2011 09:10 AM, Tom de Vries wrote:
>> Hi Zdenek,
>>
>> I have a patch set for for PR45098.
>>
>> 01_object-size-target.patch
>> 02_pr45098-rtx-cost-set.patch
>> 03_pr45098-computation-cost.patch
>> 04_pr45098-iv-init-cost.patch
>> 05_pr45098-bound-cost.patch
>> 06_pr45098-bound-cost.test.patch
>> 07_pr45098-nowrap-limits-iterations.patch
>> 08_pr45098-nowrap-limits-iterations.test.patch
>> 09_pr45098-shift-add-cost.patch
>> 10_pr45098-shift-add-cost.test.patch
>>
>> I will sent out the patches individually.
>>
> 
> OK for trunk?
> 
> Thanks,
> - Tom

Resubmitting with comment.

This patch attemps to estimate the number of iterations of the loop based on
nonwrapping arithmetic in the loop body.

2011-05-05  Tom de Vries  <tom@codesourcery.com>

	PR target/45098
	* tree-ssa-loop-ivopts.c (struct ivopts_data): Add fields
	max_iterations_p and max_iterations.
	(is_nonwrap_use, max_loop_iterations, set_max_iterations): New function.
	(may_eliminate_iv): Use max_iterations_p and max_iterations.
	(tree_ssa_iv_optimize_loop): Use set_max_iterations.

Index: gcc/tree-ssa-loop-ivopts.c
===================================================================
--- gcc/tree-ssa-loop-ivopts.c (revision 173355)
+++ gcc/tree-ssa-loop-ivopts.c (working copy)
@@ -291,6 +291,12 @@ struct ivopts_data
 
   /* Whether the loop body includes any function calls.  */
   bool body_includes_call;
+
+  /* Whether max_iterations is valid.  */
+  bool max_iterations_p;
+
+  /* Maximum number of iterations of current_loop.  */
+  double_int max_iterations;
 };
 
 /* An assignment of iv candidates to uses.  */
@@ -4319,6 +4325,108 @@ iv_elimination_compare (struct ivopts_da
   return (exit->flags & EDGE_TRUE_VALUE ? EQ_EXPR : NE_EXPR);
 }
 
+/* Determine if USE contains non-wrapping arithmetic.  */
+
+static bool
+is_nonwrap_use (struct ivopts_data *data, struct iv_use *use)
+{
+  gimple stmt = use->stmt;
+  tree var, ptr, ptr_type;
+
+  if (!is_gimple_assign (stmt))
+    return false;
+
+  switch (gimple_assign_rhs_code (stmt))
+    {
+    case POINTER_PLUS_EXPR:
+      ptr = gimple_assign_rhs1 (stmt);
+      ptr_type = TREE_TYPE (ptr);
+      var = gimple_assign_rhs2 (stmt);
+      if (!expr_invariant_in_loop_p (data->current_loop, ptr))
+        return false;
+      break;
+    case ARRAY_REF:
+      ptr = TREE_OPERAND ((gimple_assign_rhs1 (stmt)), 0);
+      ptr_type = build_pointer_type (TREE_TYPE (gimple_assign_rhs1 (stmt)));
+      var = TREE_OPERAND ((gimple_assign_rhs1 (stmt)), 1);
+      break;
+    default:
+      return false;
+    }
+
+  if (!nowrap_type_p (ptr_type))
+    return false;
+
+  if (TYPE_PRECISION (ptr_type) != TYPE_PRECISION (TREE_TYPE (var)))
+    return false;
+
+  return true;
+}
+
+/* Attempt to infer maximum number of loop iterations of DATA->current_loop
+   from uses in loop containing non-wrapping arithmetic.  If successful,
+   return true, and return maximum iterations in MAX_NITER.  */
+
+static bool
+max_loop_iterations (struct ivopts_data *data, double_int *max_niter)
+{
+  struct iv_use *use;
+  struct iv *iv;
+  bool found = false;
+  double_int period;
+  gimple stmt;
+  unsigned i;
+
+  for (i = 0; i < n_iv_uses (data); i++)
+    {
+      use = iv_use (data, i);
+
+      stmt = use->stmt;
+      if (!just_once_each_iteration_p (data->current_loop, gimple_bb (stmt)))
+	continue;
+
+      if (!is_nonwrap_use (data, use))
+        continue;
+
+      iv = use->iv;
+      if (iv->step == NULL_TREE || TREE_CODE (iv->step) != INTEGER_CST)
+	continue;
+      period = tree_to_double_int (iv_period (iv));
+
+      if (found)
+        *max_niter = double_int_umin (*max_niter, period);
+      else
+        {
+          found = true;
+          *max_niter = period;
+        }
+    }
+
+  return found;
+}
+
+/* Initializes DATA->max_iterations and DATA->max_iterations_p.  */
+
+static void
+set_max_iterations (struct ivopts_data *data)
+{
+  double_int max_niter, max_niter2;
+  bool estimate1, estimate2;
+
+  data->max_iterations_p = false;
+  estimate1 = estimated_loop_iterations (data->current_loop, true, &max_niter);
+  estimate2 = max_loop_iterations (data, &max_niter2);
+  if (!(estimate1 || estimate2))
+    return;
+  if (estimate1 && estimate2)
+    data->max_iterations = double_int_umin (max_niter, max_niter2);
+  else if (estimate1)
+    data->max_iterations = max_niter;
+  else
+    data->max_iterations = max_niter2;
+  data->max_iterations_p = true;
+}
+
 /* Check whether it is possible to express the condition in USE by comparison
    of candidate CAND.  If so, store the value compared with to BOUND.  */
 
@@ -4391,10 +4499,10 @@ may_eliminate_iv (struct ivopts_data *da
           /* See if we can take advantage of infered loop bound information.  */
           if (loop_only_exit_p (loop, exit))
             {
-              if (!estimated_loop_iterations (loop, true, &max_niter))
+              if (!data->max_iterations_p)
                 return false;
               /* The loop bound is already adjusted by adding 1.  */
-              if (double_int_ucmp (max_niter, period_value) > 0)
+              if (double_int_ucmp (data->max_iterations, period_value) > 0)
                 return false;
             }
           else
@@ -6390,6 +6498,8 @@ tree_ssa_iv_optimize_loop (struct ivopts
   /* Finds candidates for the induction variables (item 2).  */
   find_iv_candidates (data);
 
+  set_max_iterations (data);
+
   /* Calculates the costs (item 3, part 1).  */
   determine_iv_costs (data);
   determine_use_iv_costs (data);