OSDN Git Service

* tree-ssa-loop-niter.c (compute_estimated_nb_iterations): Fix
authorrakdver <rakdver@138bc75d-0d04-0410-961f-82ee72b054a4>
Sun, 25 Feb 2007 19:49:22 +0000 (19:49 +0000)
committerrakdver <rakdver@138bc75d-0d04-0410-961f-82ee72b054a4>
Sun, 25 Feb 2007 19:49:22 +0000 (19:49 +0000)
off-by-one error.
(array_at_struct_end_p): New function.
(idx_infer_loop_bounds): Use it.
(estimate_numbers_of_iterations_loop): Export.
* predict.c (predict_loops): Use estimated_loop_iterations_int.
Do not use PRED_LOOP_EXIT on exits predicted by # of iterations.
(tree_estimate_probability): Call record_loop_exits.
* tree-data-ref.c (get_number_of_iters_for_loop): Replaced by ...
(estimated_loop_iterations, estimated_loop_iterations_int,
estimated_loop_iterations_tree): New functions.
(analyze_siv_subscript_cst_affine,
compute_overlap_steps_for_affine_1_2,
analyze_subscript_affine_affine): Use estimated_loop_iterations_int.
(analyze_miv_subscript): Use estimated_loop_iterations_tree.
* predict.def (PRED_LOOP_ITERATIONS): Update comment.
(PRED_LOOP_ITERATIONS_GUESSED): New.
* cfgloop.c (record_loop_exits): Do nothing if there are no loops.
* cfgloop.h (estimate_numbers_of_iterations_loop,
estimated_loop_iterations_int): Declare.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@122316 138bc75d-0d04-0410-961f-82ee72b054a4

gcc/ChangeLog
gcc/cfgloop.c
gcc/cfgloop.h
gcc/predict.c
gcc/predict.def
gcc/tree-data-ref.c
gcc/tree-ssa-loop-niter.c

index 54d3ad5..e835441 100644 (file)
@@ -1,3 +1,26 @@
+2007-02-25  Zdenek Dvorak  <dvorakz@suse.cz>
+
+       * tree-ssa-loop-niter.c (compute_estimated_nb_iterations): Fix
+       off-by-one error.
+       (array_at_struct_end_p): New function.
+       (idx_infer_loop_bounds): Use it.
+       (estimate_numbers_of_iterations_loop): Export.
+       * predict.c (predict_loops): Use estimated_loop_iterations_int.
+       Do not use PRED_LOOP_EXIT on exits predicted by # of iterations.
+       (tree_estimate_probability): Call record_loop_exits.
+       * tree-data-ref.c (get_number_of_iters_for_loop): Replaced by ...
+       (estimated_loop_iterations, estimated_loop_iterations_int,
+       estimated_loop_iterations_tree): New functions.
+       (analyze_siv_subscript_cst_affine,
+       compute_overlap_steps_for_affine_1_2,
+       analyze_subscript_affine_affine): Use estimated_loop_iterations_int.
+       (analyze_miv_subscript): Use estimated_loop_iterations_tree.
+       * predict.def (PRED_LOOP_ITERATIONS): Update comment.
+       (PRED_LOOP_ITERATIONS_GUESSED): New.
+       * cfgloop.c (record_loop_exits): Do nothing if there are no loops.
+       * cfgloop.h (estimate_numbers_of_iterations_loop,
+       estimated_loop_iterations_int): Declare.
+
 2007-02-25  Mark Mitchell  <mark@codesourcery.com>
 
        * doc/extend.texi: Document optional priority argument to
index 62ee79c..12ce92c 100644 (file)
@@ -1038,6 +1038,9 @@ record_loop_exits (void)
   edge_iterator ei;
   edge e;
 
+  if (!current_loops)
+    return;
+
   if (current_loops->state & LOOPS_HAVE_RECORDED_EXITS)
     return;
   current_loops->state |= LOOPS_HAVE_RECORDED_EXITS;
index 09eef08..c6cd722 100644 (file)
@@ -265,6 +265,9 @@ extern bool just_once_each_iteration_p (const struct loop *, basic_block);
 extern unsigned expected_loop_iterations (const struct loop *);
 extern rtx doloop_condition_get (rtx);
 
+void estimate_numbers_of_iterations_loop (struct loop *);
+HOST_WIDE_INT estimated_loop_iterations_int (struct loop *, bool);
+
 /* Loop manipulation.  */
 extern bool can_duplicate_loop_p (struct loop *loop);
 
index df5d310..0e86c52 100644 (file)
@@ -650,6 +650,10 @@ predict_loops (void)
       for (j = 0; VEC_iterate (edge, exits, j, ex); j++)
        {
          tree niter = NULL;
+         HOST_WIDE_INT nitercst;
+         int max = PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS);
+         int probability;
+         enum br_predictor predictor;
 
          if (number_of_iterations_exit (loop, ex, &niter_desc, false))
            niter = niter_desc.niter;
@@ -658,20 +662,31 @@ predict_loops (void)
 
          if (TREE_CODE (niter) == INTEGER_CST)
            {
-             int probability;
-             int max = PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS);
              if (host_integerp (niter, 1)
                  && compare_tree_int (niter, max-1) == -1)
-               {
-                 HOST_WIDE_INT nitercst = tree_low_cst (niter, 1) + 1;
-                 probability = ((REG_BR_PROB_BASE + nitercst / 2)
-                                / nitercst);
-               }
+               nitercst = tree_low_cst (niter, 1) + 1;
              else
-               probability = ((REG_BR_PROB_BASE + max / 2) / max);
+               nitercst = max;
+             predictor = PRED_LOOP_ITERATIONS;
+           }
+         /* If we have just one exit and we can derive some information about
+            the number of iterations of the loop from the statements inside
+            the loop, use it to predict this exit.  */
+         else if (n_exits == 1)
+           {
+             nitercst = estimated_loop_iterations_int (loop, false);
+             if (nitercst < 0)
+               continue;
+             if (nitercst > max)
+               nitercst = max;
 
-             predict_edge (ex, PRED_LOOP_ITERATIONS, probability);
+             predictor = PRED_LOOP_ITERATIONS_GUESSED;
            }
+         else
+           continue;
+
+         probability = ((REG_BR_PROB_BASE + nitercst / 2) / nitercst);
+         predict_edge (ex, predictor, probability);
        }
       VEC_free (edge, heap, exits);
 
@@ -706,7 +721,11 @@ predict_loops (void)
 
          /* Loop exit heuristics - predict an edge exiting the loop if the
             conditional has no loop header successors as not taken.  */
-         if (!header_found)
+         if (!header_found
+             /* If we already used more reliable loop exit predictors, do not
+                bother with PRED_LOOP_EXIT.  */
+             && !predicted_by_p (bb, PRED_LOOP_ITERATIONS_GUESSED)
+             && !predicted_by_p (bb, PRED_LOOP_ITERATIONS))
            {
              /* For loop with many exits we don't want to predict all exits
                 with the pretty large probability, because if all exits are
@@ -1258,6 +1277,7 @@ tree_estimate_probability (void)
   tree_bb_level_predictions ();
 
   mark_irreducible_loops ();
+  record_loop_exits ();
   if (current_loops)
     predict_loops ();
 
index 997f4d2..22474b3 100644 (file)
@@ -52,9 +52,9 @@ DEF_PREDICTOR (PRED_NO_PREDICTION, "no prediction", PROB_ALWAYS, 0)
 DEF_PREDICTOR (PRED_UNCONDITIONAL, "unconditional jump", PROB_ALWAYS,
               PRED_FLAG_FIRST_MATCH)
 
-/* Use number of loop iterations determined by loop unroller to set
-   probability.  We don't want to use Dempster-Shaffer theory here,
-   as the predictions is exact.  */
+/* Use number of loop iterations determined by # of iterations
+   analysis to set probability.  We don't want to use Dempster-Shaffer
+   theory here, as the predictions is exact.  */
 DEF_PREDICTOR (PRED_LOOP_ITERATIONS, "loop iterations", PROB_ALWAYS,
               PRED_FLAG_FIRST_MATCH)
 
@@ -62,6 +62,10 @@ DEF_PREDICTOR (PRED_LOOP_ITERATIONS, "loop iterations", PROB_ALWAYS,
 DEF_PREDICTOR (PRED_BUILTIN_EXPECT, "__builtin_expect", PROB_VERY_LIKELY,
               PRED_FLAG_FIRST_MATCH)
 
+/* Use number of loop iterations guessed by the contents of the loop.  */
+DEF_PREDICTOR (PRED_LOOP_ITERATIONS_GUESSED, "guessed loop iterations",
+              PROB_ALWAYS, PRED_FLAG_FIRST_MATCH)
+
 /* Branch containing goto is probably not taken.  */
 DEF_PREDICTOR (PRED_CONTINUE, "continue", HITRATE (56), 0)
 
index 2f57c4f..b6750ee 100644 (file)
@@ -2543,29 +2543,85 @@ analyze_ziv_subscript (tree chrec_a,
     fprintf (dump_file, ")\n");
 }
 
-/* Get the real or estimated number of iterations for LOOPNUM, whichever is
-   available. Return the number of iterations as a tree, or NULL_TREE if
-   we don't know.  */
+/* Sets NIT to the estimated number of executions of the statements in
+   LOOP.  If CONSERVATIVE is true, we must be sure that NIT is at least as
+   large as the number of iterations.  If we have no reliable estimate,
+   the function returns false, otherwise returns true.  */
 
-static tree
-get_number_of_iters_for_loop (int loopnum)
+static bool
+estimated_loop_iterations (struct loop *loop, bool conservative,
+                          double_int *nit)
 {
-  struct loop *loop = get_loop (loopnum);
   tree numiter = number_of_exit_cond_executions (loop);
 
+  /* If we have an exact value, use it.  */
   if (TREE_CODE (numiter) == INTEGER_CST)
-    return numiter;
+    {
+      *nit = tree_to_double_int (numiter);
+      return true;
+    }
 
+  /* If we have a measured profile and we do not ask for a conservative bound,
+     use it.  */
+  if (!conservative && loop->header->count != 0)
+    {
+      *nit = uhwi_to_double_int (expected_loop_iterations (loop) + 1);
+      return true;
+    }
+
+  /* Finally, try using a reliable estimate on number of iterations according
+     to the size of the accessed data, if available.  */
+  estimate_numbers_of_iterations_loop (loop);
   if (loop->estimate_state == EST_AVAILABLE)
     {
-      tree type = lang_hooks.types.type_for_size (INT_TYPE_SIZE, true);
-      if (double_int_fits_to_tree_p (type, loop->estimated_nb_iterations))
-       return double_int_to_tree (type, loop->estimated_nb_iterations);
+      *nit = loop->estimated_nb_iterations;
+      return true;
     }
 
-  return NULL_TREE;
+  return false;
+}
+
+/* Similar to estimated_loop_iterations, but returns the estimate only
+   if it fits to HOST_WIDE_INT.  If this is not the case, or the estimate
+   on the number of iterations of LOOP could not be derived, returns -1.  */
+
+HOST_WIDE_INT
+estimated_loop_iterations_int (struct loop *loop, bool conservative)
+{
+  double_int nit;
+  HOST_WIDE_INT hwi_nit;
+
+  if (!estimated_loop_iterations (loop, conservative, &nit))
+    return -1;
+
+  if (!double_int_fits_in_shwi_p (nit))
+    return -1;
+  hwi_nit = double_int_to_shwi (nit);
+
+  return hwi_nit < 0 ? -1 : hwi_nit;
 }
     
+/* Similar to estimated_loop_iterations, but returns the estimate as a tree,
+   and only if it fits to the int type.  If this is not the case, or the
+   estimate on the number of iterations of LOOP could not be derived, returns
+   chrec_dont_know.  */
+
+static tree
+estimated_loop_iterations_tree (struct loop *loop, bool conservative)
+{
+  double_int nit;
+  tree type;
+
+  if (!estimated_loop_iterations (loop, conservative, &nit))
+    return chrec_dont_know;
+
+  type = lang_hooks.types.type_for_size (INT_TYPE_SIZE, true);
+  if (!double_int_fits_to_tree_p (type, nit))
+    return chrec_dont_know;
+
+  return double_int_to_tree (type, nit);
+}
+
 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
    constant, and CHREC_B is an affine function.  *OVERLAPS_A and
    *OVERLAPS_B are initialized to the functions that describe the
@@ -2626,8 +2682,8 @@ analyze_siv_subscript_cst_affine (tree chrec_a,
                  
                  if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
                    {
-                     tree numiter;
-                     int loopnum = CHREC_VARIABLE (chrec_b);
+                     HOST_WIDE_INT numiter;
+                     struct loop *loop = get_chrec_loop (chrec_b);
 
                      *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
                      tmp = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
@@ -2641,11 +2697,10 @@ analyze_siv_subscript_cst_affine (tree chrec_a,
 
                      /* Perform weak-zero siv test to see if overlap is
                         outside the loop bounds.  */
-                     numiter = get_number_of_iters_for_loop (loopnum);
+                     numiter = estimated_loop_iterations_int (loop, true);
 
-                     if (numiter != NULL_TREE
-                         && TREE_CODE (tmp) == INTEGER_CST
-                         && tree_int_cst_lt (numiter, tmp))
+                     if (numiter >= 0
+                         && compare_tree_int (tmp, numiter) > 0)
                        {
                          free_conflict_function (*overlaps_a);
                          free_conflict_function (*overlaps_b);
@@ -2709,8 +2764,8 @@ analyze_siv_subscript_cst_affine (tree chrec_a,
                  */
                  if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
                    {
-                     tree numiter;
-                     int loopnum = CHREC_VARIABLE (chrec_b);
+                     HOST_WIDE_INT numiter;
+                     struct loop *loop = get_chrec_loop (chrec_b);
 
                      *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
                      tmp = fold_build2 (EXACT_DIV_EXPR,
@@ -2721,11 +2776,10 @@ analyze_siv_subscript_cst_affine (tree chrec_a,
 
                      /* Perform weak-zero siv test to see if overlap is
                         outside the loop bounds.  */
-                     numiter = get_number_of_iters_for_loop (loopnum);
+                     numiter = estimated_loop_iterations_int (loop, true);
 
-                     if (numiter != NULL_TREE
-                         && TREE_CODE (tmp) == INTEGER_CST
-                         && tree_int_cst_lt (numiter, tmp))
+                     if (numiter >= 0
+                         && compare_tree_int (tmp, numiter) > 0)
                        {
                          free_conflict_function (*overlaps_a);
                          free_conflict_function (*overlaps_b);
@@ -2852,8 +2906,7 @@ compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
 {
   bool xz_p, yz_p, xyz_p;
   int step_x, step_y, step_z;
-  int niter_x, niter_y, niter_z, niter;
-  tree numiter_x, numiter_y, numiter_z;
+  HOST_WIDE_INT niter_x, niter_y, niter_z, niter;
   affine_fn overlaps_a_xz, overlaps_b_xz;
   affine_fn overlaps_a_yz, overlaps_b_yz;
   affine_fn overlaps_a_xyz, overlaps_b_xyz;
@@ -2864,12 +2917,12 @@ compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
   step_y = int_cst_value (CHREC_RIGHT (chrec_a));
   step_z = int_cst_value (CHREC_RIGHT (chrec_b));
 
-  numiter_x = get_number_of_iters_for_loop (CHREC_VARIABLE (CHREC_LEFT (chrec_a)));
-  numiter_y = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
-  numiter_z = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b));
+  niter_x = estimated_loop_iterations_int
+               (get_chrec_loop (CHREC_LEFT (chrec_a)), true);
+  niter_y = estimated_loop_iterations_int (get_chrec_loop (chrec_a), true);
+  niter_z = estimated_loop_iterations_int (get_chrec_loop (chrec_b), true);
   
-  if (numiter_x == NULL_TREE || numiter_y == NULL_TREE 
-      || numiter_z == NULL_TREE)
+  if (niter_x < 0 || niter_y < 0 || niter_z < 0)
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
        fprintf (dump_file, "overlap steps test failed: no iteration counts.\n");
@@ -2880,10 +2933,6 @@ compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
       return;
     }
 
-  niter_x = int_cst_value (numiter_x);
-  niter_y = int_cst_value (numiter_y);
-  niter_z = int_cst_value (numiter_z);
-
   niter = MIN (niter_x, niter_z);
   compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
                                           &overlaps_a_xz,
@@ -3029,13 +3078,14 @@ analyze_subscript_affine_affine (tree chrec_a,
       if (nb_vars_a == 1 && nb_vars_b == 1)
        {
          int step_a, step_b;
-         int niter, niter_a, niter_b;
-         tree numiter_a, numiter_b;
+         HOST_WIDE_INT niter, niter_a, niter_b;
          affine_fn ova, ovb;
 
-         numiter_a = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
-         numiter_b = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b));
-         if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
+         niter_a = estimated_loop_iterations_int
+                       (get_chrec_loop (chrec_a), true);
+         niter_b = estimated_loop_iterations_int
+                       (get_chrec_loop (chrec_b), true);
+         if (niter_a < 0 || niter_b < 0)
            {
              if (dump_file && (dump_flags & TDF_DETAILS))
                fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
@@ -3045,8 +3095,6 @@ analyze_subscript_affine_affine (tree chrec_a,
              goto end_analyze_subs_aa;
            }
 
-         niter_a = int_cst_value (numiter_a);
-         niter_b = int_cst_value (numiter_b);
          niter = MIN (niter_a, niter_b);
 
          step_a = int_cst_value (CHREC_RIGHT (chrec_a));
@@ -3140,12 +3188,13 @@ analyze_subscript_affine_affine (tree chrec_a,
             equation: chrec_a (X0) = chrec_b (Y0).  */
          int x0, y0;
          int niter, niter_a, niter_b;
-         tree numiter_a, numiter_b;
 
-         numiter_a = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
-         numiter_b = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b));
+         niter_a = estimated_loop_iterations_int
+                       (get_chrec_loop (chrec_a), true);
+         niter_b = estimated_loop_iterations_int
+                       (get_chrec_loop (chrec_b), true);
 
-         if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
+         if (niter_a < 0 || niter_b < 0)
            {
              if (dump_file && (dump_flags & TDF_DETAILS))
                fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
@@ -3155,8 +3204,6 @@ analyze_subscript_affine_affine (tree chrec_a,
              goto end_analyze_subs_aa;
            }
 
-         niter_a = int_cst_value (numiter_a);
-         niter_b = int_cst_value (numiter_b);
          niter = MIN (niter_a, niter_b);
 
          i0 = U[0][0] * gamma / gcd_alpha_beta;
@@ -3481,7 +3528,8 @@ analyze_miv_subscript (tree chrec_a,
         in the same order.  */
       *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
       *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
-      *last_conflicts = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
+      *last_conflicts = estimated_loop_iterations_tree
+                               (get_chrec_loop (chrec_a), true);
       dependence_stats.num_miv_dependent++;
     }
   
index 56ef2e9..018e9a8 100644 (file)
@@ -1752,6 +1752,8 @@ static void
 compute_estimated_nb_iterations (struct loop *loop)
 {
   struct nb_iter_bound *bound;
+  double_int bnd_val, delta;
+  edge exit;
  
   gcc_assert (loop->estimate_state == EST_NOT_AVAILABLE);
 
@@ -1760,17 +1762,79 @@ compute_estimated_nb_iterations (struct loop *loop)
       if (!bound->realistic)
        continue;
 
+      bnd_val = bound->bound;
+      /* If bound->stmt is an exit, then every statement in the loop is
+        executed at most BND_VAL + 1 times.  If it is not an exit, then
+        some of the statements before it could be executed BND_VAL + 2
+        times, if an exit of LOOP is before stmt.  */
+      exit = single_exit (loop);
+
+      if (bound->is_exit
+         || (exit != NULL
+             && dominated_by_p (CDI_DOMINATORS,
+                                exit->src, bb_for_stmt (bound->stmt))))
+       delta = double_int_one;
+      else
+       delta = double_int_two;
+      bnd_val = double_int_add (bnd_val, delta);
+
+      /* If an overflow occured, ignore the result.  */
+      if (double_int_ucmp (bnd_val, delta) < 0)
+       continue;
+
       /* Update only when there is no previous estimation, or when the current
         estimation is smaller.  */
       if (loop->estimate_state == EST_NOT_AVAILABLE
-         || double_int_ucmp (bound->bound, loop->estimated_nb_iterations) < 0)
+         || double_int_ucmp (bnd_val, loop->estimated_nb_iterations) < 0)
        {
          loop->estimate_state = EST_AVAILABLE;
-         loop->estimated_nb_iterations = bound->bound;
+         loop->estimated_nb_iterations = bnd_val;
        }
     }
 }
 
+/* Returns true if REF is a reference to an array at the end of a dynamically
+   allocated structure.  If this is the case, the array may be allocated larger
+   than its upper bound implies.  */
+
+static bool
+array_at_struct_end_p (tree ref)
+{
+  tree base = get_base_address (ref);
+  tree parent, field;
+
+  /* Unless the reference is through a pointer, the size of the array matches
+     its declaration.  */
+  if (!base || !INDIRECT_REF_P (base))
+    return false;
+  
+  for (;handled_component_p (ref); ref = parent)
+    {
+      parent = TREE_OPERAND (ref, 0);
+
+      if (TREE_CODE (ref) == COMPONENT_REF)
+       {
+         /* All fields of a union are at its end.  */
+         if (TREE_CODE (TREE_TYPE (parent)) == UNION_TYPE)
+           continue;
+
+         /* Unless the field is at the end of the struct, we are done.  */
+         field = TREE_OPERAND (ref, 1);
+         if (TREE_CHAIN (field))
+           return false;
+       }
+
+      /* The other options are ARRAY_REF, ARRAY_RANGE_REF, VIEW_CONVERT_EXPR.
+        In all these cases, we might be accessing the last element, and
+        although in practice this will probably never happen, it is legal for
+        the indices of this last element to exceed the bounds of the array.
+        Therefore, continue checking.  */
+    }
+
+  gcc_assert (INDIRECT_REF_P (ref));
+  return true;
+}
+
 /* Determine information about number of iterations a LOOP from the index
    IDX of a data reference accessed in STMT.  Callback for for_each_index.  */
 
@@ -1789,7 +1853,8 @@ idx_infer_loop_bounds (tree base, tree *idx, void *dta)
   bool sign;
   struct loop *loop = data->loop;
 
-  if (TREE_CODE (base) != ARRAY_REF)
+  if (TREE_CODE (base) != ARRAY_REF
+      || array_at_struct_end_p (base))
     return true;
 
   ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, *idx));
@@ -1974,7 +2039,7 @@ infer_loop_bounds_from_undefined (struct loop *loop)
 
 /* Records estimates on numbers of iterations of LOOP.  */
 
-static void
+void
 estimate_numbers_of_iterations_loop (struct loop *loop)
 {
   VEC (edge, heap) *exits;