OSDN Git Service

Fixes PR 18403 and meta PR 21861.
authorspop <spop@138bc75d-0d04-0410-961f-82ee72b054a4>
Tue, 7 Jun 2005 19:51:25 +0000 (19:51 +0000)
committerspop <spop@138bc75d-0d04-0410-961f-82ee72b054a4>
Tue, 7 Jun 2005 19:51:25 +0000 (19:51 +0000)
* Makefile.in (tree-chrec.o): Depend on CFGLOOP_H and TREE_FLOW_H.
* tree-chrec.c: Include cfgloop.h and tree-flow.h.
(evolution_function_is_invariant_rec_p,
evolution_function_is_invariant_p): New.
(chrec_convert): Use an extra parameter AT_STMT for refining the
information that is passed down to convert_step.  Integrate the
code that was in count_ev_in_wider_type.
* tree-chrec.h (count_ev_in_wider_type): Removed.
(chrec_convert): Modify its declaration.
(evolution_function_is_invariant_p): Declared.
(evolution_function_is_affine_p): Use evolution_function_is_invariant_p.
* tree-flow.h (can_count_iv_in_wider_type): Renamed convert_step.
(scev_probably_wraps_p): Declared.
* tree-scalar-evolution.c (count_ev_in_wider_type): Removed.
(follow_ssa_edge_in_rhs, interpret_rhs_modify_expr):
Use an extra parameter AT_STMT for refining the information that is
passed down to convert_step.
(follow_ssa_edge_inner_loop_phi, follow_ssa_edge,
analyze_scalar_evolution_1): Initialize AT_STMT with the current
analyzed statement.
(instantiate_parameters_1): Don't know yet how to initialize AT_STMT.
* tree-ssa-loop-ivopts.c (idx_find_step): Update the use of
can_count_iv_in_wider_type to use convert_step.
* tree-ssa-loop-niter.c (can_count_iv_in_wider_type_bound): Move
code that is independent of the loop over the known iteration
bounds to convert_step_widening, the rest is moved to
proved_non_wrapping_p.
(scev_probably_wraps_p): New.
(can_count_iv_in_wider_type): Renamed convert_step.
* tree-vrp.c (adjust_range_with_scev): Take an extra AT_STMT parameter.
Use scev_probably_wraps_p for computing init_is_max.
(vrp_visit_assignment): Pass the current analyzed statement to
adjust_range_with_scev.
(execute_vrp): Call estimate_numbers_of_iterations for refining the
information provided by scev analyzer.

testsuite:

* testsuite/gcc.dg/vect/vect-77.c: Remove xfail from lp64.
* testsuite/gcc.dg/vect/vect-78.c: Same.

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

gcc/ChangeLog
gcc/Makefile.in
gcc/testsuite/gcc.dg/vect/vect-77.c
gcc/testsuite/gcc.dg/vect/vect-78.c
gcc/tree-chrec.c
gcc/tree-chrec.h
gcc/tree-flow.h
gcc/tree-scalar-evolution.c
gcc/tree-ssa-loop-ivopts.c
gcc/tree-ssa-loop-niter.c
gcc/tree-vrp.c

index 8496165..e200023 100644 (file)
@@ -1,3 +1,42 @@
+2005-06-07  Sebastian Pop  <pop@cri.ensmp.fr>
+
+       PR 18403 and meta PR 21861.
+       * Makefile.in (tree-chrec.o): Depend on CFGLOOP_H and TREE_FLOW_H.
+       * tree-chrec.c: Include cfgloop.h and tree-flow.h.
+       (evolution_function_is_invariant_rec_p,
+       evolution_function_is_invariant_p): New.
+       (chrec_convert): Use an extra parameter AT_STMT for refining the
+       information that is passed down to convert_step.  Integrate the 
+       code that was in count_ev_in_wider_type.
+       * tree-chrec.h (count_ev_in_wider_type): Removed.
+       (chrec_convert): Modify its declaration.
+       (evolution_function_is_invariant_p): Declared.
+       (evolution_function_is_affine_p): Use evolution_function_is_invariant_p.
+       * tree-flow.h (can_count_iv_in_wider_type): Renamed convert_step.
+       (scev_probably_wraps_p): Declared.
+       * tree-scalar-evolution.c (count_ev_in_wider_type): Removed.
+       (follow_ssa_edge_in_rhs, interpret_rhs_modify_expr):
+       Use an extra parameter AT_STMT for refining the information that is
+       passed down to convert_step.
+       (follow_ssa_edge_inner_loop_phi, follow_ssa_edge,
+       analyze_scalar_evolution_1): Initialize AT_STMT with the current
+       analyzed statement.
+       (instantiate_parameters_1): Don't know yet how to initialize AT_STMT.
+       * tree-ssa-loop-ivopts.c (idx_find_step): Update the use of 
+       can_count_iv_in_wider_type to use convert_step.
+       * tree-ssa-loop-niter.c (can_count_iv_in_wider_type_bound): Move 
+       code that is independent of the loop over the known iteration
+       bounds to convert_step_widening, the rest is moved to
+       proved_non_wrapping_p.
+       (scev_probably_wraps_p): New.
+       (can_count_iv_in_wider_type): Renamed convert_step.
+       * tree-vrp.c (adjust_range_with_scev): Take an extra AT_STMT parameter.
+       Use scev_probably_wraps_p for computing init_is_max.
+       (vrp_visit_assignment): Pass the current analyzed statement to 
+       adjust_range_with_scev.
+       (execute_vrp): Call estimate_numbers_of_iterations for refining the 
+       information provided by scev analyzer.
+
 2005-06-07  Eric Christopher  <echristo@redhat.com>
 
        * config/mips/predicates.md (sleu_operand): Use
index b9f0f1e..9e8bbe0 100644 (file)
@@ -1873,7 +1873,7 @@ tree-browser.o : tree-browser.c tree-browser.def $(CONFIG_H) $(SYSTEM_H) \
    $(TM_H) coretypes.h
 tree-chrec.o: tree-chrec.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
    $(GGC_H) $(TREE_H) tree-chrec.h tree-pass.h $(PARAMS_H) \
-   $(DIAGNOSTIC_H) $(VARRAY_H)
+   $(DIAGNOSTIC_H) $(VARRAY_H) $(CFGLOOP_H) $(TREE_FLOW_H)
 tree-scalar-evolution.o: tree-scalar-evolution.c $(CONFIG_H) $(SYSTEM_H) \
    coretypes.h $(TM_H) $(GGC_H) $(TREE_H) $(RTL_H) \
    $(BASIC_BLOCK_H) $(DIAGNOSTIC_H) $(TREE_FLOW_H) $(TREE_DUMP_H) \
index 14da163..8557b29 100644 (file)
@@ -39,7 +39,7 @@ int main (void)
   return 0;
 }
 
-/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" { xfail { lp64 || vect_no_align } } } } */
-/* { dg-final { scan-tree-dump-times "Vectorizing an unaligned access" 1 "vect" { xfail { lp64 || vect_no_align } } } } */
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" { xfail { vect_no_align } } } } */
+/* { dg-final { scan-tree-dump-times "Vectorizing an unaligned access" 1 "vect" { xfail { vect_no_align } } } } */
 /* { dg-final { scan-tree-dump-times "Alignment of access forced using peeling" 0 "vect" } } */
 /* { dg-final { cleanup-tree-dump "vect" } } */
index e22efca..a059f30 100644 (file)
@@ -40,7 +40,7 @@ int main (void)
   return 0;
 }
 
-/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" { xfail { lp64 || vect_no_align } } } } */
-/* { dg-final { scan-tree-dump-times "Vectorizing an unaligned access" 1 "vect" { xfail { lp64 || vect_no_align } } } } */
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" { xfail { vect_no_align } } } } */
+/* { dg-final { scan-tree-dump-times "Vectorizing an unaligned access" 1 "vect" { xfail { vect_no_align } } } } */
 /* { dg-final { scan-tree-dump-times "Alignment of access forced using peeling" 0 "vect" } } */
 /* { dg-final { cleanup-tree-dump "vect" } } */
index 1a7e8c8..ee17150 100644 (file)
@@ -32,6 +32,8 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
 #include "tree.h"
 #include "diagnostic.h"
 #include "varray.h"
+#include "cfgloop.h"
+#include "tree-flow.h"
 #include "tree-chrec.h"
 #include "tree-pass.h"
 #include "params.h"
@@ -909,6 +911,57 @@ tree_contains_chrecs (tree expr, int *size)
     }
 }
 
+/* Recursive helper function.  */
+
+static bool
+evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
+{
+  if (evolution_function_is_constant_p (chrec))
+    return true;
+
+  if (TREE_CODE (chrec) == SSA_NAME 
+      && expr_invariant_in_loop_p (current_loops->parray[loopnum],
+                                  chrec))
+    return true;
+
+  if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
+      && CHREC_VARIABLE (chrec) == (unsigned) loopnum)
+    return false;
+
+  switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
+    {
+    case 2:
+      if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
+                                                 loopnum))
+       return false;
+      
+    case 1:
+      if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0),
+                                                 loopnum))
+       return false;
+      return true;
+
+    default:
+      return false;
+    }
+
+  return false;
+}
+
+/* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
+
+bool
+evolution_function_is_invariant_p (tree chrec, int loopnum)
+{
+  if (evolution_function_is_constant_p (chrec))
+    return true;
+  
+  if (current_loops != NULL)
+    return evolution_function_is_invariant_rec_p (chrec, loopnum);
+
+  return false;
+}
+
 /* Determine whether the given tree is an affine multivariate
    evolution.  */
 
@@ -1019,11 +1072,17 @@ nb_vars_in_chrec (tree chrec)
 
 \f
 
-/* Convert CHREC to TYPE.  The following is rule is always true:
-   TREE_TYPE (chrec) == TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE
-   (CHREC_RIGHT (chrec)).  An example of what could happen when adding
-   two chrecs and the type of the CHREC_RIGHT is different than
-   CHREC_LEFT is:
+/* Convert CHREC to TYPE.  When the analyzer knows the context in
+   which the CHREC is built, it sets AT_STMT to the statement that
+   contains the definition of the analyzed variable, otherwise the
+   conversion is less accurate: the information is used for
+   determining a more accurate estimation of the number of iterations.
+   By default AT_STMT could be safely set to NULL_TREE.
+
+   The following rule is always true: TREE_TYPE (chrec) ==
+   TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
+   An example of what could happen when adding two chrecs and the type
+   of the CHREC_RIGHT is different than CHREC_LEFT is:
    
    {(uint) 0, +, (uchar) 10} +
    {(uint) 0, +, (uchar) 250}
@@ -1038,11 +1097,10 @@ nb_vars_in_chrec (tree chrec)
 */
 
 tree 
-chrec_convert (tree type, 
-              tree chrec)
+chrec_convert (tree type, tree chrec, tree at_stmt)
 {
-  tree ct;
-  
+  tree ct, res;
+
   if (automatically_generated_chrec_p (chrec))
     return chrec;
   
@@ -1050,43 +1108,44 @@ chrec_convert (tree type,
   if (ct == type)
     return chrec;
 
-  if (TYPE_PRECISION (ct) < TYPE_PRECISION (type))
-    return count_ev_in_wider_type (type, chrec);
-
-  switch (TREE_CODE (chrec))
+  if (evolution_function_is_affine_p (chrec))
     {
-    case POLYNOMIAL_CHREC:
+      tree step = convert_step (current_loops->parray[CHREC_VARIABLE (chrec)],
+                               type, CHREC_LEFT (chrec), CHREC_RIGHT (chrec),
+                               at_stmt);
+      if (!step)
+       return fold_convert (type, chrec);
+
       return build_polynomial_chrec (CHREC_VARIABLE (chrec),
-                                    chrec_convert (type,
-                                                   CHREC_LEFT (chrec)),
-                                    chrec_convert (type,
-                                                   CHREC_RIGHT (chrec)));
+                                    chrec_convert (type, CHREC_LEFT (chrec),
+                                                   at_stmt),
+                                    step);
+    }
 
-    default:
-      {
-       tree res = fold_convert (type, chrec);
+  if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
+    return chrec_dont_know;
 
-       /* Don't propagate overflows.  */
-       if (CONSTANT_CLASS_P (res))
-         {
-           TREE_CONSTANT_OVERFLOW (res) = 0;
-           TREE_OVERFLOW (res) = 0;
-         }
+  res = fold_convert (type, chrec);
 
-       /* But reject constants that don't fit in their type after conversion.
-          This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
-          natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
-          and can cause problems later when computing niters of loops.  Note
-          that we don't do the check before converting because we don't want
-          to reject conversions of negative chrecs to unsigned types.  */
-       if (TREE_CODE (res) == INTEGER_CST
-           && TREE_CODE (type) == INTEGER_TYPE
-           && !int_fits_type_p (res, type))
-         res = chrec_dont_know;
-
-       return res;
-      }
+  /* Don't propagate overflows.  */
+  if (CONSTANT_CLASS_P (res))
+    {
+      TREE_CONSTANT_OVERFLOW (res) = 0;
+      TREE_OVERFLOW (res) = 0;
     }
+
+  /* But reject constants that don't fit in their type after conversion.
+     This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
+     natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
+     and can cause problems later when computing niters of loops.  Note
+     that we don't do the check before converting because we don't want
+     to reject conversions of negative chrecs to unsigned types.  */
+  if (TREE_CODE (res) == INTEGER_CST
+      && TREE_CODE (type) == INTEGER_TYPE
+      && !int_fits_type_p (res, type))
+    res = chrec_dont_know;
+
+  return res;
 }
 
 /* Returns the type of the chrec.  */
index d101c9b..723c891 100644 (file)
@@ -67,8 +67,7 @@ tree_is_chrec (tree expr)
 extern tree chrec_fold_plus (tree, tree, tree);
 extern tree chrec_fold_minus (tree, tree, tree);
 extern tree chrec_fold_multiply (tree, tree, tree);
-extern tree chrec_convert (tree, tree);
-extern tree count_ev_in_wider_type (tree, tree);
+extern tree chrec_convert (tree, tree, tree);
 extern tree chrec_type (tree);
 
 /* Operations.  */
@@ -146,6 +145,7 @@ evolution_function_is_constant_p (tree chrec)
     }
 }
 
+extern bool evolution_function_is_invariant_p (tree, int);
 /* Determine whether the given tree is an affine evolution function or not.  */
 
 static inline bool 
@@ -157,8 +157,10 @@ evolution_function_is_affine_p (tree chrec)
   switch (TREE_CODE (chrec))
     {
     case POLYNOMIAL_CHREC:
-      if (evolution_function_is_constant_p (CHREC_LEFT (chrec))
-         && evolution_function_is_constant_p (CHREC_RIGHT (chrec)))
+      if (evolution_function_is_invariant_p (CHREC_LEFT (chrec), 
+                                            CHREC_VARIABLE (chrec))
+         && evolution_function_is_invariant_p (CHREC_RIGHT (chrec),
+                                               CHREC_VARIABLE (chrec)))
        return true;
       else
        return false;
index 7d7dc00..d318019 100644 (file)
@@ -658,7 +658,8 @@ tree find_loop_niter (struct loop *, edge *);
 tree loop_niter_by_eval (struct loop *, edge);
 tree find_loop_niter_by_eval (struct loop *, edge *);
 void estimate_numbers_of_iterations (struct loops *);
-tree can_count_iv_in_wider_type (struct loop *, tree, tree, tree, tree);
+bool scev_probably_wraps_p (tree, tree, tree, tree, struct loop *, bool *);
+tree convert_step (struct loop *, tree, tree, tree, tree);
 void free_numbers_of_iterations_estimates (struct loops *);
 void rewrite_into_loop_closed_ssa (bitmap, unsigned);
 void verify_loop_closed_ssa (void);
index 2753186..49806b2 100644 (file)
@@ -349,33 +349,6 @@ find_var_scev_info (tree var)
   return &res->chrec;
 }
 
-/* Tries to express CHREC in wider type TYPE.  */
-
-tree
-count_ev_in_wider_type (tree type, tree chrec)
-{
-  tree base, step;
-  struct loop *loop;
-
-  if (!evolution_function_is_affine_p (chrec))
-    return fold_convert (type, chrec);
-
-  base = CHREC_LEFT (chrec);
-  step = CHREC_RIGHT (chrec);
-  loop = current_loops->parray[CHREC_VARIABLE (chrec)];
-
-  /* TODO -- if we knew the statement at that the conversion occurs,
-     we could pass it to can_count_iv_in_wider_type and get a better
-     result.  */
-  step = can_count_iv_in_wider_type (loop, type, base, step, NULL_TREE);
-  if (!step)
-    return fold_convert (type, chrec);
-  base = chrec_convert (type, base);
-
-  return build_polynomial_chrec (CHREC_VARIABLE (chrec),
-                                base, step);
-}
-
 /* Return true when CHREC contains symbolic names defined in
    LOOP_NB.  */
 
@@ -1052,6 +1025,7 @@ static bool follow_ssa_edge (struct loop *loop, tree, tree, tree *);
 
 static bool
 follow_ssa_edge_in_rhs (struct loop *loop,
+                       tree at_stmt,
                        tree rhs, 
                        tree halting_phi, 
                        tree *evolution_of_loop)
@@ -1071,9 +1045,10 @@ follow_ssa_edge_in_rhs (struct loop *loop,
     {
     case NOP_EXPR:
       /* This assignment is under the form "a_1 = (cast) rhs.  */
-      res = follow_ssa_edge_in_rhs (loop, TREE_OPERAND (rhs, 0), halting_phi, 
-                                   evolution_of_loop);
-      *evolution_of_loop = chrec_convert (TREE_TYPE (rhs), *evolution_of_loop);
+      res = follow_ssa_edge_in_rhs (loop, at_stmt, TREE_OPERAND (rhs, 0),
+                                   halting_phi, evolution_of_loop);
+      *evolution_of_loop = chrec_convert (TREE_TYPE (rhs),
+                                         *evolution_of_loop, at_stmt);
       break;
 
     case INTEGER_CST:
@@ -1107,7 +1082,7 @@ follow_ssa_edge_in_rhs (struct loop *loop,
              if (res)
                *evolution_of_loop = add_to_evolution 
                  (loop->num, 
-                  chrec_convert (type_rhs, *evolution_of_loop), 
+                  chrec_convert (type_rhs, *evolution_of_loop, at_stmt), 
                   PLUS_EXPR, rhs1);
              
              else
@@ -1119,7 +1094,7 @@ follow_ssa_edge_in_rhs (struct loop *loop,
                  if (res)
                    *evolution_of_loop = add_to_evolution 
                      (loop->num, 
-                      chrec_convert (type_rhs, *evolution_of_loop), 
+                      chrec_convert (type_rhs, *evolution_of_loop, at_stmt), 
                       PLUS_EXPR, rhs0);
                }
            }
@@ -1133,7 +1108,8 @@ follow_ssa_edge_in_rhs (struct loop *loop,
                 evolution_of_loop);
              if (res)
                *evolution_of_loop = add_to_evolution 
-                 (loop->num, chrec_convert (type_rhs, *evolution_of_loop), 
+                 (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
+                                            at_stmt),
                   PLUS_EXPR, rhs1);
            }
        }
@@ -1147,7 +1123,8 @@ follow_ssa_edge_in_rhs (struct loop *loop,
             evolution_of_loop);
          if (res)
            *evolution_of_loop = add_to_evolution 
-             (loop->num, chrec_convert (type_rhs, *evolution_of_loop), 
+             (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
+                                        at_stmt),
               PLUS_EXPR, rhs0);
        }
 
@@ -1174,7 +1151,8 @@ follow_ssa_edge_in_rhs (struct loop *loop,
                                 evolution_of_loop);
          if (res)
            *evolution_of_loop = add_to_evolution 
-                   (loop->num, chrec_convert (type_rhs, *evolution_of_loop), 
+                   (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
+                                              at_stmt),
                     MINUS_EXPR, rhs1);
        }
       else
@@ -1391,7 +1369,8 @@ follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
          /* Follow the edges that exit the inner loop.  */
          bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
          if (!flow_bb_inside_loop_p (loop, bb))
-           res = res || follow_ssa_edge_in_rhs (outer_loop, arg, halting_phi,
+           res = res || follow_ssa_edge_in_rhs (outer_loop, loop_phi_node,
+                                                arg, halting_phi,
                                                 evolution_of_loop);
        }
 
@@ -1404,7 +1383,7 @@ follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
 
   /* Otherwise, compute the overall effect of the inner loop.  */
   ev = compute_overall_effect_of_inner_loop (loop, ev);
-  return follow_ssa_edge_in_rhs (outer_loop, ev, halting_phi,
+  return follow_ssa_edge_in_rhs (outer_loop, loop_phi_node, ev, halting_phi,
                                 evolution_of_loop);
 }
 
@@ -1456,7 +1435,7 @@ follow_ssa_edge (struct loop *loop,
       return false;
 
     case MODIFY_EXPR:
-      return follow_ssa_edge_in_rhs (loop,
+      return follow_ssa_edge_in_rhs (loop, def,
                                     TREE_OPERAND (def, 1), 
                                     halting_phi, 
                                     evolution_of_loop);
@@ -1665,14 +1644,14 @@ interpret_condition_phi (struct loop *loop, tree condition_phi)
    analyze the effect of an inner loop: see interpret_loop_phi.  */
 
 static tree
-interpret_rhs_modify_expr (struct loop *loop,
+interpret_rhs_modify_expr (struct loop *loop, tree at_stmt,
                           tree opnd1, tree type)
 {
   tree res, opnd10, opnd11, chrec10, chrec11;
-  
+
   if (is_gimple_min_invariant (opnd1))
-    return chrec_convert (type, opnd1);
-  
+    return chrec_convert (type, opnd1, at_stmt);
+
   switch (TREE_CODE (opnd1))
     {
     case PLUS_EXPR:
@@ -1680,8 +1659,8 @@ interpret_rhs_modify_expr (struct loop *loop,
       opnd11 = TREE_OPERAND (opnd1, 1);
       chrec10 = analyze_scalar_evolution (loop, opnd10);
       chrec11 = analyze_scalar_evolution (loop, opnd11);
-      chrec10 = chrec_convert (type, chrec10);
-      chrec11 = chrec_convert (type, chrec11);
+      chrec10 = chrec_convert (type, chrec10, at_stmt);
+      chrec11 = chrec_convert (type, chrec11, at_stmt);
       res = chrec_fold_plus (type, chrec10, chrec11);
       break;
       
@@ -1690,15 +1669,15 @@ interpret_rhs_modify_expr (struct loop *loop,
       opnd11 = TREE_OPERAND (opnd1, 1);
       chrec10 = analyze_scalar_evolution (loop, opnd10);
       chrec11 = analyze_scalar_evolution (loop, opnd11);
-      chrec10 = chrec_convert (type, chrec10);
-      chrec11 = chrec_convert (type, chrec11);
+      chrec10 = chrec_convert (type, chrec10, at_stmt);
+      chrec11 = chrec_convert (type, chrec11, at_stmt);
       res = chrec_fold_minus (type, chrec10, chrec11);
       break;
 
     case NEGATE_EXPR:
       opnd10 = TREE_OPERAND (opnd1, 0);
       chrec10 = analyze_scalar_evolution (loop, opnd10);
-      chrec10 = chrec_convert (type, chrec10);
+      chrec10 = chrec_convert (type, chrec10, at_stmt);
       res = chrec_fold_minus (type, build_int_cst (type, 0), chrec10);
       break;
 
@@ -1707,25 +1686,27 @@ interpret_rhs_modify_expr (struct loop *loop,
       opnd11 = TREE_OPERAND (opnd1, 1);
       chrec10 = analyze_scalar_evolution (loop, opnd10);
       chrec11 = analyze_scalar_evolution (loop, opnd11);
-      chrec10 = chrec_convert (type, chrec10);
-      chrec11 = chrec_convert (type, chrec11);
+      chrec10 = chrec_convert (type, chrec10, at_stmt);
+      chrec11 = chrec_convert (type, chrec11, at_stmt);
       res = chrec_fold_multiply (type, chrec10, chrec11);
       break;
       
     case SSA_NAME:
-      res = chrec_convert (type, analyze_scalar_evolution (loop, opnd1));
+      res = chrec_convert (type, analyze_scalar_evolution (loop, opnd1),
+                          at_stmt);
       break;
 
     case ASSERT_EXPR:
       opnd10 = ASSERT_EXPR_VAR (opnd1);
-      res = chrec_convert (type, analyze_scalar_evolution (loop, opnd10));
+      res = chrec_convert (type, analyze_scalar_evolution (loop, opnd10),
+                          at_stmt);
       break;
       
     case NOP_EXPR:
     case CONVERT_EXPR:
       opnd10 = TREE_OPERAND (opnd1, 0);
       chrec10 = analyze_scalar_evolution (loop, opnd10);
-      res = chrec_convert (type, chrec10);
+      res = chrec_convert (type, chrec10, at_stmt);
       break;
       
     default:
@@ -1775,7 +1756,7 @@ analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res)
     return chrec_dont_know;
 
   if (TREE_CODE (var) != SSA_NAME)
-    return interpret_rhs_modify_expr (loop, var, type);
+    return interpret_rhs_modify_expr (loop, NULL_TREE, var, type);
 
   def = SSA_NAME_DEF_STMT (var);
   bb = bb_for_stmt (def);
@@ -1809,7 +1790,7 @@ analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res)
   switch (TREE_CODE (def))
     {
     case MODIFY_EXPR:
-      res = interpret_rhs_modify_expr (loop, TREE_OPERAND (def, 1), type);
+      res = interpret_rhs_modify_expr (loop, def, TREE_OPERAND (def, 1), type);
       break;
 
     case PHI_NODE:
@@ -2093,7 +2074,7 @@ instantiate_parameters_1 (struct loop *loop, tree chrec,
       if (op0 == TREE_OPERAND (chrec, 0))
        return chrec;
 
-      return chrec_convert (TREE_TYPE (chrec), op0);
+      return chrec_convert (TREE_TYPE (chrec), op0, NULL_TREE);
 
     case SCEV_NOT_KNOWN:
       return chrec_dont_know;
index 716d113..ed10722 100644 (file)
@@ -1442,11 +1442,8 @@ idx_find_step (tree base, tree *idx, void *data)
     /* The step for pointer arithmetics already is 1 byte.  */
     step = build_int_cst (sizetype, 1);
 
-  if (TYPE_PRECISION (TREE_TYPE (iv->base)) < TYPE_PRECISION (sizetype))
-    iv_step = can_count_iv_in_wider_type (dta->ivopts_data->current_loop,
-                                         sizetype, iv->base, iv->step, dta->stmt);
-  else
-    iv_step = fold_convert (sizetype, iv->step);
+  iv_step = convert_step (dta->ivopts_data->current_loop,
+                         sizetype, iv->base, iv->step, dta->stmt);
 
   if (!iv_step)
     {
index 78f14e9..40f8e45 100644 (file)
@@ -1445,13 +1445,18 @@ stmt_dominates_stmt_p (tree s1, tree s2)
   return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
 }
 
-/* Checks whether it is correct to count the induction variable BASE + STEP * I
-   at AT_STMT in wider TYPE, using the fact that statement OF is executed at
-   most BOUND times in the loop.  If it is possible, return the value of step
-   of the induction variable in the TYPE, otherwise return NULL_TREE.
+/* Return true when it is possible to prove that the induction
+   variable does not wrap: vary outside the type specified bounds.
+   Checks whether BOUND < VALID_NITER that means in the context of iv
+   conversion that all the iterations in the loop are safe: not
+   producing wraps.
+
+   The statement NITER_BOUND->AT_STMT is executed at most
+   NITER_BOUND->BOUND times in the loop.
    
-   ADDITIONAL is the additional condition recorded for operands of the bound.
-   This is useful in the following case, created by loop header copying:
+   NITER_BOUND->ADDITIONAL is the additional condition recorded for
+   operands of the bound.  This is useful in the following case,
+   created by loop header copying:
 
    i = 0;
    if (n > 0)
@@ -1465,108 +1470,211 @@ stmt_dominates_stmt_p (tree s1, tree s2)
    assumption "n > 0" says us that the value of the number of iterations is at
    most MAX_TYPE - 1 (without this assumption, it might overflow).  */
 
-static tree
-can_count_iv_in_wider_type_bound (tree type, tree base, tree step,
-                                 tree at_stmt,
-                                 tree bound,
-                                 tree additional,
-                                 tree of)
+static bool
+proved_non_wrapping_p (tree at_stmt,
+                      struct nb_iter_bound *niter_bound, 
+                      tree new_type,
+                      tree valid_niter)
 {
-  tree inner_type = TREE_TYPE (base), b, bplusstep, new_step, new_step_abs;
-  tree valid_niter, extreme, unsigned_type, delta, bound_type;
   tree cond;
+  tree bound = niter_bound->bound;
+
+  if (TYPE_PRECISION (new_type) > TYPE_PRECISION (TREE_TYPE (bound)))
+    bound = fold_convert (unsigned_type_for (new_type), bound);
+  else
+    valid_niter = fold_convert (TREE_TYPE (bound), valid_niter);
+
+  /* After the statement niter_bound->at_stmt we know that anything is
+     executed at most BOUND times.  */
+  if (at_stmt && stmt_dominates_stmt_p (niter_bound->at_stmt, at_stmt))
+    cond = fold_build2 (GE_EXPR, boolean_type_node, valid_niter, bound);
+
+  /* Before the statement niter_bound->at_stmt we know that anything
+     is executed at most BOUND + 1 times.  */
+  else
+    cond = fold_build2 (GT_EXPR, boolean_type_node, valid_niter, bound);
+
+  if (nonzero_p (cond))
+    return true;
+
+  /* Try taking additional conditions into account.  */
+  cond = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
+                     invert_truthvalue (niter_bound->additional),
+                     cond);
+
+  if (nonzero_p (cond))
+    return true;
 
-  b = fold_convert (type, base);
-  bplusstep = fold_convert (type,
-                           fold_build2 (PLUS_EXPR, inner_type, base, step));
-  new_step = fold_build2 (MINUS_EXPR, type, bplusstep, b);
-  if (TREE_CODE (new_step) != INTEGER_CST)
+  return false;
+}
+
+/* Checks whether it is correct to count the induction variable BASE +
+   STEP * I at AT_STMT in a wider type NEW_TYPE, using the bounds on
+   numbers of iterations of a LOOP.  If it is possible, return the
+   value of step of the induction variable in the NEW_TYPE, otherwise
+   return NULL_TREE.  */
+
+static tree
+convert_step_widening (struct loop *loop, tree new_type, tree base, tree step,
+                      tree at_stmt)
+{
+  struct nb_iter_bound *bound;
+  tree base_in_new_type, base_plus_step_in_new_type, step_in_new_type;
+  tree delta, step_abs;
+  tree unsigned_type, valid_niter;
+
+  /* Compute the new step.  For example, {(uchar) 100, +, (uchar) 240}
+     is converted to {(uint) 100, +, (uint) 0xfffffff0} in order to
+     keep the values of the induction variable unchanged: 100, 84, 68,
+     ...
+
+     Another example is: (uint) {(uchar)100, +, (uchar)3} is converted
+     to {(uint)100, +, (uint)3}.  
+
+     Before returning the new step, verify that the number of
+     iterations is less than DELTA / STEP_ABS (i.e. in the previous
+     example (256 - 100) / 3) such that the iv does not wrap (in which
+     case the operations are too difficult to be represented and
+     handled: the values of the iv should be taken modulo 256 in the
+     wider type; this is not implemented).  */
+  base_in_new_type = fold_convert (new_type, base);
+  base_plus_step_in_new_type = 
+    fold_convert (new_type,
+                 fold_build2 (PLUS_EXPR, TREE_TYPE (base), base, step));
+  step_in_new_type = fold_build2 (MINUS_EXPR, new_type,
+                                 base_plus_step_in_new_type,
+                                 base_in_new_type);
+
+  if (TREE_CODE (step_in_new_type) != INTEGER_CST)
     return NULL_TREE;
 
-  switch (compare_trees (bplusstep, b))
+  switch (compare_trees (base_plus_step_in_new_type, base_in_new_type))
     {
     case -1:
-      extreme = upper_bound_in_type (type, inner_type);
-      delta = fold_build2 (MINUS_EXPR, type, extreme, b);
-      new_step_abs = new_step;
-      break;
+      {
+       tree extreme = upper_bound_in_type (new_type, TREE_TYPE (base));
+       delta = fold_build2 (MINUS_EXPR, new_type, extreme,
+                            base_in_new_type);
+       step_abs = step_in_new_type;
+       break;
+      }
 
     case 1:
-      extreme = lower_bound_in_type (type, inner_type);
-      new_step_abs = fold_build1 (NEGATE_EXPR, type, new_step);
-      delta = fold_build2 (MINUS_EXPR, type, b, extreme);
-      break;
+      {
+       tree extreme = lower_bound_in_type (new_type, TREE_TYPE (base));
+       delta = fold_build2 (MINUS_EXPR, new_type, base_in_new_type,
+                            extreme);
+       step_abs = fold_build1 (NEGATE_EXPR, new_type, step_in_new_type);
+       break;
+      }
 
     case 0:
-      return new_step;
+      return step_in_new_type;
 
     default:
       return NULL_TREE;
     }
 
-  unsigned_type = unsigned_type_for (type);
+  unsigned_type = unsigned_type_for (new_type);
   delta = fold_convert (unsigned_type, delta);
-  new_step_abs = fold_convert (unsigned_type, new_step_abs);
+  step_abs = fold_convert (unsigned_type, step_abs);
   valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type,
-                            delta, new_step_abs);
+                            delta, step_abs);
 
-  bound_type = TREE_TYPE (bound);
-  if (TYPE_PRECISION (type) > TYPE_PRECISION (bound_type))
-    bound = fold_convert (unsigned_type, bound);
-  else
-    valid_niter = fold_convert (bound_type, valid_niter);
-    
-  if (at_stmt && stmt_dominates_stmt_p (of, at_stmt))
-    {
-      /* After the statement OF we know that anything is executed at most
-        BOUND times.  */
-      cond = fold_build2 (GE_EXPR, boolean_type_node, valid_niter, bound);
-    }
-  else
+  for (bound = loop->bounds; bound; bound = bound->next)
+    if (proved_non_wrapping_p (at_stmt, bound, new_type, valid_niter))
+      return step_in_new_type;
+
+  /* Fail when the loop has no bound estimations, or when no bound can
+     be used for verifying the conversion.  */
+  return NULL_TREE;
+}
+
+/* Return false only when the induction variable BASE + STEP * I is
+   known to not overflow: i.e. when the number of iterations is small
+   enough with respect to the step and initial condition in order to
+   keep the evolution confined in TYPEs bounds.  Return true when the
+   iv is known to overflow or when the property is not computable.
+
+   Initialize INIT_IS_MAX to true when the evolution goes from
+   INIT_IS_MAX to LOWER_BOUND_IN_TYPE, false in the contrary case, not
+   defined when the function returns true.  */
+
+bool
+scev_probably_wraps_p (tree type, tree base, tree step, 
+                      tree at_stmt, struct loop *loop,
+                      bool *init_is_max)
+{
+  struct nb_iter_bound *bound;
+  tree delta, step_abs;
+  tree unsigned_type, valid_niter;
+  tree base_plus_step = fold_build2 (PLUS_EXPR, type, base, step);
+
+  switch (compare_trees (base_plus_step, base))
     {
-      /* Before the statement OF we know that anything is executed at most
-        BOUND + 1 times.  */
-      cond = fold_build2 (GT_EXPR, boolean_type_node, valid_niter, bound);
+    case -1:
+      {
+       tree extreme = upper_bound_in_type (type, TREE_TYPE (base));
+       delta = fold_build2 (MINUS_EXPR, type, extreme, base);
+       step_abs = step;
+       *init_is_max = false;
+       break;
+      }
+
+    case 1:
+      {
+       tree extreme = lower_bound_in_type (type, TREE_TYPE (base));
+       delta = fold_build2 (MINUS_EXPR, type, base, extreme);
+       step_abs = fold_build1 (NEGATE_EXPR, type, step);
+       *init_is_max = true;
+       break;
+      }
+
+    case 0:
+      /* This means step is equal to 0.  This should not happen.  It
+        could happen in convert step, but not here.  Safely answer
+        don't know as in the default case.  */
+
+    default:
+      return true;
     }
 
-  if (nonzero_p (cond))
-    return new_step;
+  /* After having set INIT_IS_MAX, we can return false: when not using
+     wrapping arithmetic, signed types don't wrap.  */
+  if (!flag_wrapv && !TYPE_UNSIGNED (type))
+    return false;
 
-  /* Try taking additional conditions into account.  */
-  cond = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
-                     invert_truthvalue (additional),
-                     cond);
-  if (nonzero_p (cond))
-    return new_step;
+  unsigned_type = unsigned_type_for (type);
+  delta = fold_convert (unsigned_type, delta);
+  step_abs = fold_convert (unsigned_type, step_abs);
+  valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
 
-  return NULL_TREE;
+  for (bound = loop->bounds; bound; bound = bound->next)
+    if (proved_non_wrapping_p (at_stmt, bound, type, valid_niter))
+      return false;
+
+  /* At this point we still don't have a proof that the iv does not
+     overflow: give up.  */
+  return true;
 }
 
-/* Checks whether it is correct to count the induction variable BASE + STEP * I
-   at AT_STMT in wider TYPE, using the bounds on numbers of iterations of a
-   LOOP.  If it is possible, return the value of step of the induction variable
-   in the TYPE, otherwise return NULL_TREE.  */
+/* Return the conversion to NEW_TYPE of the STEP of an induction
+   variable BASE + STEP * I at AT_STMT.  */
 
 tree
-can_count_iv_in_wider_type (struct loop *loop, tree type, tree base, tree step,
-                           tree at_stmt)
+convert_step (struct loop *loop, tree new_type, tree base, tree step,
+             tree at_stmt)
 {
-  struct nb_iter_bound *bound;
-  tree new_step;
+  tree base_type = TREE_TYPE (base);
 
-  for (bound = loop->bounds; bound; bound = bound->next)
-    {
-      new_step = can_count_iv_in_wider_type_bound (type, base, step,
-                                                  at_stmt,
-                                                  bound->bound,
-                                                  bound->additional,
-                                                  bound->at_stmt);
-
-      if (new_step)
-       return new_step;
-    }
+  /* When not using wrapping arithmetic, signed types don't wrap.  */
+  if (!flag_wrapv && !TYPE_UNSIGNED (base_type))
+    return fold_convert (new_type, step);
 
-  return NULL_TREE;
+  if (TYPE_PRECISION (new_type) > TYPE_PRECISION (base_type))
+    return convert_step_widening (loop, new_type, base, step, at_stmt);
+
+  return fold_convert (new_type, step);
 }
 
 /* Frees the information on upper bounds on numbers of iterations of LOOP.  */
index 373e8d9..b42da82 100644 (file)
@@ -1427,13 +1427,13 @@ extract_range_from_expr (value_range_t *vr, tree expr)
     set_value_range_to_varying (vr);
 }
 
-
-/* Given a range VR, a loop L and a variable VAR, determine whether it
+/* Given a range VR, a LOOP and a variable VAR, determine whether it
    would be profitable to adjust VR using scalar evolution information
    for VAR.  If so, update VR with the new limits.  */
 
 static void
-adjust_range_with_scev (value_range_t *vr, struct loop *l, tree var)
+adjust_range_with_scev (value_range_t *vr, struct loop *loop, tree stmt,
+                       tree var)
 {
   tree init, step, chrec;
   bool init_is_max;
@@ -1443,7 +1443,7 @@ adjust_range_with_scev (value_range_t *vr, struct loop *l, tree var)
   if (vr->type == VR_ANTI_RANGE)
     return;
 
-  chrec = analyze_scalar_evolution (l, var);
+  chrec = analyze_scalar_evolution (loop, var);
   if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
     return;
 
@@ -1455,22 +1455,12 @@ adjust_range_with_scev (value_range_t *vr, struct loop *l, tree var)
   if (!is_gimple_min_invariant (step))
     return;
 
-  /* FIXME.  When dealing with unsigned types,
-     analyze_scalar_evolution sets STEP to very large unsigned values
-     when the evolution goes backwards.  This confuses this analysis
-     because we think that INIT is the smallest value that the range
-     can take, instead of the largest.  Ignore these chrecs for now.  */
-  if (INTEGRAL_TYPE_P (TREE_TYPE (step)) && TYPE_UNSIGNED (TREE_TYPE (step)))
-    return;
-
-  /* Do not adjust ranges when using wrapping arithmetic.  */
-  if (flag_wrapv)
+  /* Do not adjust ranges when chrec may wrap.  */
+  if (scev_probably_wraps_p (chrec_type (chrec), init, step, stmt,
+                            cfg_loops->parray[CHREC_VARIABLE (chrec)],
+                            &init_is_max))
     return;
 
-  /* If STEP is negative, then INIT is the maximum value the range
-     will take.  Otherwise, INIT is the minimum value.  */
-  init_is_max = (tree_int_cst_sgn (step) < 0);
-
   if (!POINTER_TYPE_P (TREE_TYPE (init))
       && (vr->type == VR_VARYING || vr->type == VR_UNDEFINED))
     {
@@ -2772,7 +2762,7 @@ vrp_visit_assignment (tree stmt, tree *output_p)
         else about the range of LHS by examining scalar evolution
         information.  */
       if (cfg_loops && (l = loop_containing_stmt (stmt)))
-       adjust_range_with_scev (&new_vr, l, lhs);
+       adjust_range_with_scev (&new_vr, l, stmt, lhs);
 
       if (update_value_range (lhs, &new_vr))
        {
@@ -3519,7 +3509,10 @@ execute_vrp (void)
 
   cfg_loops = loop_optimizer_init (NULL);
   if (cfg_loops)
-    scev_initialize (cfg_loops);
+    {
+      scev_initialize (cfg_loops);
+      estimate_numbers_of_iterations (cfg_loops);
+    }
 
   vrp_initialize ();
   ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node);