2009-04-17 Simon Baldwin <simonb@google.com>

[pf3gnuchains/gcc-fork.git] / gcc / tree-chrec.c

diff --git a/gcc/tree-chrec.c b/gcc/tree-chrec.c
index f36fc9b..82c1fbe 100644 (file)
--- a/gcc/tree-chrec.c
+++ b/gcc/tree-chrec.c
@@ -1,12 +1,13 @@
 /* Chains of recurrences.
 /* Chains of recurrences.

-   Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
+   Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
+   Free Software Foundation, Inc.

    Contributed by Sebastian Pop <pop@cri.ensmp.fr>
 
 This file is part of GCC.
 
 GCC is free software; you can redistribute it and/or modify it under
 the terms of the GNU General Public License as published by the Free
    Contributed by Sebastian Pop <pop@cri.ensmp.fr>
 
 This file is part of GCC.
 
 GCC is free software; you can redistribute it and/or modify it under
 the terms of the GNU General Public License as published by the Free

-Software Foundation; either version 2, or (at your option) any later
+Software Foundation; either version 3, or (at your option) any later

 version.
 
 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
 version.
 
 GCC is distributed in the hope that it will be useful, but WITHOUT ANY


@@ -15,9 +16,8 @@ FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 for more details.
 
 You should have received a copy of the GNU General Public License
 for more details.
 
 You should have received a copy of the GNU General Public License

-along with GCC; see the file COPYING.  If not, write to the Free
-Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
-02110-1301, USA.  */
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */

 
 /* This file implements operations on chains of recurrences.  Chains
    of recurrences are used for modeling evolution functions of scalar
 
 /* This file implements operations on chains of recurrences.  Chains
    of recurrences are used for modeling evolution functions of scalar


@@ -46,7 +46,7 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
 /* Determines whether CST is not a constant evolution.  */
 
 static inline bool
 /* Determines whether CST is not a constant evolution.  */
 
 static inline bool

-is_not_constant_evolution (tree cst)
+is_not_constant_evolution (const_tree cst)

 {
   return (TREE_CODE (cst) == POLYNOMIAL_CHREC);
 }
 {
   return (TREE_CODE (cst) == POLYNOMIAL_CHREC);
 }


@@ -99,21 +99,27 @@ chrec_fold_plus_poly_poly (enum tree_code code,
                           tree poly1)
 {
   tree left, right;
                           tree poly1)
 {
   tree left, right;

+  struct loop *loop0 = get_chrec_loop (poly0);
+  struct loop *loop1 = get_chrec_loop (poly1);
+  tree rtype = code == POINTER_PLUS_EXPR ? sizetype : type;

 
   gcc_assert (poly0);
   gcc_assert (poly1);
   gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
   gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
 
   gcc_assert (poly0);
   gcc_assert (poly1);
   gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
   gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);

-  gcc_assert (chrec_type (poly0) == chrec_type (poly1));
+  if (POINTER_TYPE_P (chrec_type (poly0)))
+    gcc_assert (chrec_type (poly1) == sizetype);
+  else
+    gcc_assert (chrec_type (poly0) == chrec_type (poly1));

   gcc_assert (type == chrec_type (poly0));
   
   /*
     {a, +, b}_1 + {c, +, d}_2  ->  {{a, +, b}_1 + c, +, d}_2,
     {a, +, b}_2 + {c, +, d}_1  ->  {{c, +, d}_1 + a, +, b}_2,
     {a, +, b}_x + {c, +, d}_x  ->  {a+c, +, b+d}_x.  */
   gcc_assert (type == chrec_type (poly0));
   
   /*
     {a, +, b}_1 + {c, +, d}_2  ->  {{a, +, b}_1 + c, +, d}_2,
     {a, +, b}_2 + {c, +, d}_1  ->  {{c, +, d}_1 + a, +, b}_2,
     {a, +, b}_x + {c, +, d}_x  ->  {a+c, +, b+d}_x.  */

-  if (CHREC_VARIABLE (poly0) < CHREC_VARIABLE (poly1))
+  if (flow_loop_nested_p (loop0, loop1))

     {
     {

-      if (code == PLUS_EXPR)
+      if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)

        return build_polynomial_chrec 
          (CHREC_VARIABLE (poly1), 
           chrec_fold_plus (type, poly0, CHREC_LEFT (poly1)),
        return build_polynomial_chrec 
          (CHREC_VARIABLE (poly1), 
           chrec_fold_plus (type, poly0, CHREC_LEFT (poly1)),


@@ -128,9 +134,9 @@ chrec_fold_plus_poly_poly (enum tree_code code,
                                : build_int_cst_type (type, -1)));
     }
   
                                : build_int_cst_type (type, -1)));
     }
   

-  if (CHREC_VARIABLE (poly0) > CHREC_VARIABLE (poly1))
+  if (flow_loop_nested_p (loop1, loop0))

     {
     {

-      if (code == PLUS_EXPR)
+      if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)

        return build_polynomial_chrec 
          (CHREC_VARIABLE (poly0), 
           chrec_fold_plus (type, CHREC_LEFT (poly0), poly1),
        return build_polynomial_chrec 
          (CHREC_VARIABLE (poly0), 
           chrec_fold_plus (type, CHREC_LEFT (poly0), poly1),


@@ -141,13 +147,17 @@ chrec_fold_plus_poly_poly (enum tree_code code,
           chrec_fold_minus (type, CHREC_LEFT (poly0), poly1),
           CHREC_RIGHT (poly0));
     }
           chrec_fold_minus (type, CHREC_LEFT (poly0), poly1),
           CHREC_RIGHT (poly0));
     }

-  
-  if (code == PLUS_EXPR)
+ 
+  /* This function should never be called for chrecs of loops that
+     do not belong to the same loop nest.  */
+  gcc_assert (loop0 == loop1);
+
+  if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)

     {
       left = chrec_fold_plus 
        (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
       right = chrec_fold_plus 
     {
       left = chrec_fold_plus 
        (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
       right = chrec_fold_plus 

-       (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
+       (rtype, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));

     }
   else
     {
     }
   else
     {


@@ -175,6 +185,8 @@ chrec_fold_multiply_poly_poly (tree type,
 {
   tree t0, t1, t2;
   int var;
 {
   tree t0, t1, t2;
   int var;

+  struct loop *loop0 = get_chrec_loop (poly0);
+  struct loop *loop1 = get_chrec_loop (poly1);

 
   gcc_assert (poly0);
   gcc_assert (poly1);
 
   gcc_assert (poly0);
   gcc_assert (poly1);


@@ -186,20 +198,22 @@ chrec_fold_multiply_poly_poly (tree type,
   /* {a, +, b}_1 * {c, +, d}_2  ->  {c*{a, +, b}_1, +, d}_2,
      {a, +, b}_2 * {c, +, d}_1  ->  {a*{c, +, d}_1, +, b}_2,
      {a, +, b}_x * {c, +, d}_x  ->  {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x.  */
   /* {a, +, b}_1 * {c, +, d}_2  ->  {c*{a, +, b}_1, +, d}_2,
      {a, +, b}_2 * {c, +, d}_1  ->  {a*{c, +, d}_1, +, b}_2,
      {a, +, b}_x * {c, +, d}_x  ->  {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x.  */

-  if (CHREC_VARIABLE (poly0) < CHREC_VARIABLE (poly1))
+  if (flow_loop_nested_p (loop0, loop1))

     /* poly0 is a constant wrt. poly1.  */
     return build_polynomial_chrec 
       (CHREC_VARIABLE (poly1), 
        chrec_fold_multiply (type, CHREC_LEFT (poly1), poly0),
        CHREC_RIGHT (poly1));
   
     /* poly0 is a constant wrt. poly1.  */
     return build_polynomial_chrec 
       (CHREC_VARIABLE (poly1), 
        chrec_fold_multiply (type, CHREC_LEFT (poly1), poly0),
        CHREC_RIGHT (poly1));
   

-  if (CHREC_VARIABLE (poly1) < CHREC_VARIABLE (poly0))
+  if (flow_loop_nested_p (loop1, loop0))

     /* poly1 is a constant wrt. poly0.  */
     return build_polynomial_chrec 
       (CHREC_VARIABLE (poly0), 
        chrec_fold_multiply (type, CHREC_LEFT (poly0), poly1),
        CHREC_RIGHT (poly0));
     /* poly1 is a constant wrt. poly0.  */
     return build_polynomial_chrec 
       (CHREC_VARIABLE (poly0), 
        chrec_fold_multiply (type, CHREC_LEFT (poly0), poly1),
        CHREC_RIGHT (poly0));

-  
+ 
+  gcc_assert (loop0 == loop1);
+

   /* poly0 and poly1 are two polynomials in the same variable,
      {a, +, b}_x * {c, +, d}_x  ->  {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x.  */
       
   /* poly0 and poly1 are two polynomials in the same variable,
      {a, +, b}_x * {c, +, d}_x  ->  {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x.  */
       


@@ -254,6 +268,8 @@ static tree
 chrec_fold_plus_1 (enum tree_code code, tree type, 
                   tree op0, tree op1)
 {
 chrec_fold_plus_1 (enum tree_code code, tree type, 
                   tree op0, tree op1)
 {

+  tree op1_type = code == POINTER_PLUS_EXPR ? sizetype : type;
+

   if (automatically_generated_chrec_p (op0)
       || automatically_generated_chrec_p (op1))
     return chrec_fold_automatically_generated_operands (op0, op1);
   if (automatically_generated_chrec_p (op0)
       || automatically_generated_chrec_p (op1))
     return chrec_fold_automatically_generated_operands (op0, op1);


@@ -267,7 +283,7 @@ chrec_fold_plus_1 (enum tree_code code, tree type,
          return chrec_fold_plus_poly_poly (code, type, op0, op1);
 
        default:
          return chrec_fold_plus_poly_poly (code, type, op0, op1);
 
        default:

-         if (code == PLUS_EXPR)
+         if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)

            return build_polynomial_chrec 
              (CHREC_VARIABLE (op0), 
               chrec_fold_plus (type, CHREC_LEFT (op0), op1),
            return build_polynomial_chrec 
              (CHREC_VARIABLE (op0), 
               chrec_fold_plus (type, CHREC_LEFT (op0), op1),


@@ -283,7 +299,7 @@ chrec_fold_plus_1 (enum tree_code code, tree type,
       switch (TREE_CODE (op1))
        {
        case POLYNOMIAL_CHREC:
       switch (TREE_CODE (op1))
        {
        case POLYNOMIAL_CHREC:

-         if (code == PLUS_EXPR)
+         if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)

            return build_polynomial_chrec 
              (CHREC_VARIABLE (op1), 
               chrec_fold_plus (type, op0, CHREC_LEFT (op1)),
            return build_polynomial_chrec 
              (CHREC_VARIABLE (op1), 
               chrec_fold_plus (type, op0, CHREC_LEFT (op1)),


@@ -307,7 +323,7 @@ chrec_fold_plus_1 (enum tree_code code, tree type,
            else if (size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
              return fold_build2 (code, type,
                                  fold_convert (type, op0),
            else if (size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
              return fold_build2 (code, type,
                                  fold_convert (type, op0),

-                                 fold_convert (type, op1));
+                                 fold_convert (op1_type, op1));

            else
              return chrec_dont_know;
          }
            else
              return chrec_dont_know;
          }


@@ -322,16 +338,22 @@ chrec_fold_plus (tree type,
                 tree op0,
                 tree op1)
 {
                 tree op0,
                 tree op1)
 {

+  enum tree_code code;

   if (automatically_generated_chrec_p (op0)
       || automatically_generated_chrec_p (op1))
     return chrec_fold_automatically_generated_operands (op0, op1);
 
   if (integer_zerop (op0))
   if (automatically_generated_chrec_p (op0)
       || automatically_generated_chrec_p (op1))
     return chrec_fold_automatically_generated_operands (op0, op1);
 
   if (integer_zerop (op0))

-    return op1;
+    return chrec_convert (type, op1, NULL);

   if (integer_zerop (op1))
   if (integer_zerop (op1))

-    return op0;
+    return chrec_convert (type, op0, NULL);
+
+  if (POINTER_TYPE_P (type))
+    code = POINTER_PLUS_EXPR;
+  else
+    code = PLUS_EXPR;

   
   

-  return chrec_fold_plus_1 (PLUS_EXPR, type, op0, op1);
+  return chrec_fold_plus_1 (code, type, op0, op1);

 }
 
 /* Fold the subtraction of two chrecs.  */
 }
 
 /* Fold the subtraction of two chrecs.  */


@@ -492,21 +514,22 @@ chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
 {
   tree arg0, arg1, binomial_n_k;
   tree type = TREE_TYPE (chrec);
 {
   tree arg0, arg1, binomial_n_k;
   tree type = TREE_TYPE (chrec);

+  struct loop *var_loop = get_loop (var);

 
   while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 
   while (TREE_CODE (chrec) == POLYNOMIAL_CHREC

-        && CHREC_VARIABLE (chrec) > var)
+        && flow_loop_nested_p (var_loop, get_chrec_loop (chrec)))

     chrec = CHREC_LEFT (chrec);
 
   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
       && CHREC_VARIABLE (chrec) == var)
     {
     chrec = CHREC_LEFT (chrec);
 
   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
       && CHREC_VARIABLE (chrec) == var)
     {

-      arg0 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1);
-      if (arg0 == chrec_dont_know)
+      arg1 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1);
+      if (arg1 == chrec_dont_know)

        return chrec_dont_know;
       binomial_n_k = tree_fold_binomial (type, n, k);
       if (!binomial_n_k)
        return chrec_dont_know;
        return chrec_dont_know;
       binomial_n_k = tree_fold_binomial (type, n, k);
       if (!binomial_n_k)
        return chrec_dont_know;

-      arg1 = fold_build2 (MULT_EXPR, type,
+      arg0 = fold_build2 (MULT_EXPR, type,

                          CHREC_LEFT (chrec), binomial_n_k);
       return chrec_fold_plus (type, arg0, arg1);
     }
                          CHREC_LEFT (chrec), binomial_n_k);
       return chrec_fold_plus (type, arg0, arg1);
     }


@@ -555,10 +578,9 @@ chrec_apply (unsigned var,
   if (evolution_function_is_affine_p (chrec))
     {
       /* "{a, +, b} (x)"  ->  "a + b*x".  */
   if (evolution_function_is_affine_p (chrec))
     {
       /* "{a, +, b} (x)"  ->  "a + b*x".  */

-      x = chrec_convert (type, x, NULL_TREE);
-      res = chrec_fold_multiply (type, CHREC_RIGHT (chrec), x);
-      if (!integer_zerop (CHREC_LEFT (chrec)))
-       res = chrec_fold_plus (type, CHREC_LEFT (chrec), res);
+      x = chrec_convert_rhs (type, x, NULL);
+      res = chrec_fold_multiply (TREE_TYPE (x), CHREC_RIGHT (chrec), x);
+      res = chrec_fold_plus (type, CHREC_LEFT (chrec), res);

     }
   
   else if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
     }
   
   else if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)


@@ -631,26 +653,32 @@ tree
 hide_evolution_in_other_loops_than_loop (tree chrec, 
                                         unsigned loop_num)
 {
 hide_evolution_in_other_loops_than_loop (tree chrec, 
                                         unsigned loop_num)
 {

+  struct loop *loop = get_loop (loop_num), *chloop;

   if (automatically_generated_chrec_p (chrec))
     return chrec;
   
   switch (TREE_CODE (chrec))
     {
     case POLYNOMIAL_CHREC:
   if (automatically_generated_chrec_p (chrec))
     return chrec;
   
   switch (TREE_CODE (chrec))
     {
     case POLYNOMIAL_CHREC:

-      if (CHREC_VARIABLE (chrec) == loop_num)
+      chloop = get_chrec_loop (chrec);
+
+      if (chloop == loop)

        return build_polynomial_chrec 
          (loop_num, 
           hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec), 
                                                    loop_num), 
           CHREC_RIGHT (chrec));
       
        return build_polynomial_chrec 
          (loop_num, 
           hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec), 
                                                    loop_num), 
           CHREC_RIGHT (chrec));
       

-      else if (CHREC_VARIABLE (chrec) < loop_num)
+      else if (flow_loop_nested_p (chloop, loop))

        /* There is no evolution in this loop.  */
        return initial_condition (chrec);
       
       else
        /* There is no evolution in this loop.  */
        return initial_condition (chrec);
       
       else

-       return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec), 
-                                                       loop_num);
+       {
+         gcc_assert (flow_loop_nested_p (loop, chloop));
+         return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec), 
+                                                         loop_num);
+       }

       
     default:
       return chrec;
       
     default:
       return chrec;


@@ -666,6 +694,7 @@ chrec_component_in_loop_num (tree chrec,
                             bool right)
 {
   tree component;
                             bool right)
 {
   tree component;

+  struct loop *loop = get_loop (loop_num), *chloop;

 
   if (automatically_generated_chrec_p (chrec))
     return chrec;
 
   if (automatically_generated_chrec_p (chrec))
     return chrec;


@@ -673,7 +702,9 @@ chrec_component_in_loop_num (tree chrec,
   switch (TREE_CODE (chrec))
     {
     case POLYNOMIAL_CHREC:
   switch (TREE_CODE (chrec))
     {
     case POLYNOMIAL_CHREC:

-      if (CHREC_VARIABLE (chrec) == loop_num)
+      chloop = get_chrec_loop (chrec);
+
+      if (chloop == loop)

        {
          if (right)
            component = CHREC_RIGHT (chrec);
        {
          if (right)
            component = CHREC_RIGHT (chrec);


@@ -693,14 +724,17 @@ chrec_component_in_loop_num (tree chrec,
               component);
        }
       
               component);
        }
       

-      else if (CHREC_VARIABLE (chrec) < loop_num)
+      else if (flow_loop_nested_p (chloop, loop))

        /* There is no evolution part in this loop.  */
        return NULL_TREE;
       
       else
        /* There is no evolution part in this loop.  */
        return NULL_TREE;
       
       else

-       return chrec_component_in_loop_num (CHREC_LEFT (chrec), 
-                                           loop_num, 
-                                           right);
+       {
+         gcc_assert (flow_loop_nested_p (loop, chloop));
+         return chrec_component_in_loop_num (CHREC_LEFT (chrec), 
+                                             loop_num, 
+                                             right);
+       }

       
      default:
       if (right)
       
      default:
       if (right)


@@ -742,10 +776,15 @@ reset_evolution_in_loop (unsigned loop_num,
                         tree chrec, 
                         tree new_evol)
 {
                         tree chrec, 
                         tree new_evol)
 {

-  gcc_assert (chrec_type (chrec) == chrec_type (new_evol));
+  struct loop *loop = get_loop (loop_num);
+
+  if (POINTER_TYPE_P (chrec_type (chrec)))
+    gcc_assert (sizetype == chrec_type (new_evol));
+  else
+    gcc_assert (chrec_type (chrec) == chrec_type (new_evol));

 
   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 
   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC

-      && CHREC_VARIABLE (chrec) > loop_num)
+      && flow_loop_nested_p (loop, get_chrec_loop (chrec)))

     {
       tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec),
                                           new_evol);
     {
       tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec),
                                           new_evol);


@@ -796,7 +835,7 @@ chrec_merge (tree chrec1,
 /* Helper function for is_multivariate_chrec.  */
 
 static bool 
 /* Helper function for is_multivariate_chrec.  */
 
 static bool 

-is_multivariate_chrec_rec (tree chrec, unsigned int rec_var)
+is_multivariate_chrec_rec (const_tree chrec, unsigned int rec_var)

 {
   if (chrec == NULL_TREE)
     return false;
 {
   if (chrec == NULL_TREE)
     return false;


@@ -816,7 +855,7 @@ is_multivariate_chrec_rec (tree chrec, unsigned int rec_var)
 /* Determine whether the given chrec is multivariate or not.  */
 
 bool 
 /* Determine whether the given chrec is multivariate or not.  */
 
 bool 

-is_multivariate_chrec (tree chrec)
+is_multivariate_chrec (const_tree chrec)

 {
   if (chrec == NULL_TREE)
     return false;
 {
   if (chrec == NULL_TREE)
     return false;


@@ -833,8 +872,10 @@ is_multivariate_chrec (tree chrec)
 /* Determines whether the chrec contains symbolic names or not.  */
 
 bool 
 /* Determines whether the chrec contains symbolic names or not.  */
 
 bool 

-chrec_contains_symbols (tree chrec)
+chrec_contains_symbols (const_tree chrec)

 {
 {

+  int i, n;
+

   if (chrec == NULL_TREE)
     return false;
   
   if (chrec == NULL_TREE)
     return false;
   


@@ -846,53 +887,32 @@ chrec_contains_symbols (tree chrec)
       || TREE_CODE (chrec) == RESULT_DECL
       || TREE_CODE (chrec) == FIELD_DECL)
     return true;
       || TREE_CODE (chrec) == RESULT_DECL
       || TREE_CODE (chrec) == FIELD_DECL)
     return true;

-  
-  switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
-    {
-    case 3:
-      if (chrec_contains_symbols (TREE_OPERAND (chrec, 2)))
-       return true;
-      
-    case 2:
-      if (chrec_contains_symbols (TREE_OPERAND (chrec, 1)))
-       return true;
-      
-    case 1:
-      if (chrec_contains_symbols (TREE_OPERAND (chrec, 0)))
-       return true;
-      
-    default:
-      return false;
-    }
+
+  n = TREE_OPERAND_LENGTH (chrec);
+  for (i = 0; i < n; i++)
+    if (chrec_contains_symbols (TREE_OPERAND (chrec, i)))
+      return true;
+  return false;

 }
 
 /* Determines whether the chrec contains undetermined coefficients.  */
 
 bool 
 }
 
 /* Determines whether the chrec contains undetermined coefficients.  */
 
 bool 

-chrec_contains_undetermined (tree chrec)
+chrec_contains_undetermined (const_tree chrec)

 {
 {

-  if (chrec == chrec_dont_know
-      || chrec == chrec_not_analyzed_yet
-      || chrec == NULL_TREE)
+  int i, n;
+
+  if (chrec == chrec_dont_know)

     return true;
     return true;

-  
-  switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
-    {
-    case 3:
-      if (chrec_contains_undetermined (TREE_OPERAND (chrec, 2)))
-       return true;
-      
-    case 2:
-      if (chrec_contains_undetermined (TREE_OPERAND (chrec, 1)))
-       return true;
-      
-    case 1:
-      if (chrec_contains_undetermined (TREE_OPERAND (chrec, 0)))
-       return true;
-      
-    default:
-      return false;
-    }
+
+  if (chrec == NULL_TREE)
+    return false;
+
+  n = TREE_OPERAND_LENGTH (chrec);
+  for (i = 0; i < n; i++)
+    if (chrec_contains_undetermined (TREE_OPERAND (chrec, i)))
+      return true;
+  return false;

 }
 
 /* Determines whether the tree EXPR contains chrecs, and increment
 }
 
 /* Determines whether the tree EXPR contains chrecs, and increment


@@ -900,8 +920,10 @@ chrec_contains_undetermined (tree chrec)
    the tree.  */
 
 bool
    the tree.  */
 
 bool

-tree_contains_chrecs (tree expr, int *size)
+tree_contains_chrecs (const_tree expr, int *size)

 {
 {

+  int i, n;
+

   if (expr == NULL_TREE)
     return false;
 
   if (expr == NULL_TREE)
     return false;
 


@@ -911,23 +933,11 @@ tree_contains_chrecs (tree expr, int *size)
   if (tree_is_chrec (expr))
     return true;
 
   if (tree_is_chrec (expr))
     return true;
 

-  switch (TREE_CODE_LENGTH (TREE_CODE (expr)))
-    {
-    case 3:
-      if (tree_contains_chrecs (TREE_OPERAND (expr, 2), size))
-       return true;
-      
-    case 2:
-      if (tree_contains_chrecs (TREE_OPERAND (expr, 1), size))
-       return true;
-      
-    case 1:
-      if (tree_contains_chrecs (TREE_OPERAND (expr, 0), size))
-       return true;
-      
-    default:
-      return false;
-    }
+  n = TREE_OPERAND_LENGTH (expr);
+  for (i = 0; i < n; i++)
+    if (tree_contains_chrecs (TREE_OPERAND (expr, i), size))
+      return true;
+  return false;

 }
 
 /* Recursive helper function.  */
 }
 
 /* Recursive helper function.  */


@@ -938,9 +948,9 @@ evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
   if (evolution_function_is_constant_p (chrec))
     return true;
 
   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))
+  if (TREE_CODE (chrec) == SSA_NAME
+      && (loopnum == 0
+         || expr_invariant_in_loop_p (get_loop (loopnum), chrec)))

     return true;
 
   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
     return true;
 
   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)


@@ -954,7 +964,7 @@ evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
       return true;
     }
 
       return true;
     }
 

-  switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
+  switch (TREE_OPERAND_LENGTH (chrec))

     {
     case 2:
       if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
     {
     case 2:
       if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),


@@ -979,20 +989,14 @@ evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
 bool
 evolution_function_is_invariant_p (tree chrec, int loopnum)
 {
 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;
+  return evolution_function_is_invariant_rec_p (chrec, loopnum);

 }
 
 /* Determine whether the given tree is an affine multivariate
    evolution.  */
 
 bool 
 }
 
 /* Determine whether the given tree is an affine multivariate
    evolution.  */
 
 bool 

-evolution_function_is_affine_multivariate_p (tree chrec)
+evolution_function_is_affine_multivariate_p (const_tree chrec, int loopnum)

 {
   if (chrec == NULL_TREE)
     return false;
 {
   if (chrec == NULL_TREE)
     return false;


@@ -1000,9 +1004,9 @@ evolution_function_is_affine_multivariate_p (tree chrec)
   switch (TREE_CODE (chrec))
     {
     case POLYNOMIAL_CHREC:
   switch (TREE_CODE (chrec))
     {
     case POLYNOMIAL_CHREC:

-      if (evolution_function_is_constant_p (CHREC_LEFT (chrec)))
+      if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), loopnum))

        {
        {

-         if (evolution_function_is_constant_p (CHREC_RIGHT (chrec)))
+         if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum))

            return true;
          else
            {
            return true;
          else
            {


@@ -1010,7 +1014,7 @@ evolution_function_is_affine_multivariate_p (tree chrec)
                  && CHREC_VARIABLE (CHREC_RIGHT (chrec)) 
                     != CHREC_VARIABLE (chrec)
                  && evolution_function_is_affine_multivariate_p 
                  && CHREC_VARIABLE (CHREC_RIGHT (chrec)) 
                     != CHREC_VARIABLE (chrec)
                  && evolution_function_is_affine_multivariate_p 

-                 (CHREC_RIGHT (chrec)))
+                 (CHREC_RIGHT (chrec), loopnum))

                return true;
              else
                return false;
                return true;
              else
                return false;


@@ -1018,11 +1022,11 @@ evolution_function_is_affine_multivariate_p (tree chrec)
        }
       else
        {
        }
       else
        {

-         if (evolution_function_is_constant_p (CHREC_RIGHT (chrec))
+         if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum)

              && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
              && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
              && evolution_function_is_affine_multivariate_p 
              && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
              && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
              && evolution_function_is_affine_multivariate_p 

-             (CHREC_LEFT (chrec)))
+             (CHREC_LEFT (chrec), loopnum))

            return true;
          else
            return false;
            return true;
          else
            return false;


@@ -1037,7 +1041,7 @@ evolution_function_is_affine_multivariate_p (tree chrec)
    variables.  */
 
 bool
    variables.  */
 
 bool

-evolution_function_is_univariate_p (tree chrec)
+evolution_function_is_univariate_p (const_tree chrec)

 {
   if (chrec == NULL_TREE)
     return true;
 {
   if (chrec == NULL_TREE)
     return true;


@@ -1100,7 +1104,7 @@ nb_vars_in_chrec (tree chrec)
    arithmetics, even though it is a scalar type.  */
 
 static bool
    arithmetics, even though it is a scalar type.  */
 
 static bool

-avoid_arithmetics_in_type_p (tree type)
+avoid_arithmetics_in_type_p (const_tree type)

 {
   /* Ada frontend uses subtypes -- an arithmetic cannot be directly performed
      in the subtype, but a base type must be used, and the result then can
 {
   /* Ada frontend uses subtypes -- an arithmetic cannot be directly performed
      in the subtype, but a base type must be used, and the result then can


@@ -1111,7 +1115,7 @@ avoid_arithmetics_in_type_p (tree type)
   return false;
 }
 
   return false;
 }
 

-static tree chrec_convert_1 (tree, tree, tree, bool);
+static tree chrec_convert_1 (tree, tree, gimple, bool);

 
 /* Converts BASE and STEP of affine scev to TYPE.  LOOP is the loop whose iv
    the scev corresponds to.  AT_STMT is the statement at that the scev is
 
 /* Converts BASE and STEP of affine scev to TYPE.  LOOP is the loop whose iv
    the scev corresponds to.  AT_STMT is the statement at that the scev is


@@ -1123,13 +1127,14 @@ static tree chrec_convert_1 (tree, tree, tree, bool);
 
 bool
 convert_affine_scev (struct loop *loop, tree type,
 
 bool
 convert_affine_scev (struct loop *loop, tree type,

-                    tree *base, tree *step, tree at_stmt,
+                    tree *base, tree *step, gimple at_stmt,

                     bool use_overflow_semantics)
 {
   tree ct = TREE_TYPE (*step);
   bool enforce_overflow_semantics;
   bool must_check_src_overflow, must_check_rslt_overflow;
   tree new_base, new_step;
                     bool use_overflow_semantics)
 {
   tree ct = TREE_TYPE (*step);
   bool enforce_overflow_semantics;
   bool must_check_src_overflow, must_check_rslt_overflow;
   tree new_base, new_step;

+  tree step_type = POINTER_TYPE_P (type) ? sizetype : type;

 
   /* If we cannot perform arithmetic in TYPE, avoid creating an scev.  */
   if (avoid_arithmetics_in_type_p (type))
 
   /* If we cannot perform arithmetic in TYPE, avoid creating an scev.  */
   if (avoid_arithmetics_in_type_p (type))


@@ -1162,7 +1167,10 @@ convert_affine_scev (struct loop *loop, tree type,
         -- must_check_src_overflow is true, and the range of TYPE is superset
            of the range of CT -- i.e., in all cases except if CT signed and
            TYPE unsigned.
         -- must_check_src_overflow is true, and the range of TYPE is superset
            of the range of CT -- i.e., in all cases except if CT signed and
            TYPE unsigned.

-         -- both CT and TYPE have the same precision and signedness.  */
+         -- both CT and TYPE have the same precision and signedness, and we
+           verify instead that the source does not overflow (this may be
+           easier than verifying it for the result, as we may use the
+           information about the semantics of overflow in CT).  */

       if (must_check_src_overflow)
        {
          if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))
       if (must_check_src_overflow)
        {
          if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))


@@ -1172,7 +1180,10 @@ convert_affine_scev (struct loop *loop, tree type,
        }
       else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
               && TYPE_PRECISION (ct) == TYPE_PRECISION (type))
        }
       else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
               && TYPE_PRECISION (ct) == TYPE_PRECISION (type))

-       must_check_rslt_overflow = false;
+       {
+         must_check_rslt_overflow = false;
+         must_check_src_overflow = true;
+       }

       else
        must_check_rslt_overflow = true;
     }
       else
        must_check_rslt_overflow = true;
     }


@@ -1193,10 +1204,10 @@ convert_affine_scev (struct loop *loop, tree type,
      [100, +, 255] with values 100, 355, ...; the sign-extension is 
      performed by default when CT is signed.  */
   new_step = *step;
      [100, +, 255] with values 100, 355, ...; the sign-extension is 
      performed by default when CT is signed.  */
   new_step = *step;

-  if (TYPE_PRECISION (type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
+  if (TYPE_PRECISION (step_type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))

     new_step = chrec_convert_1 (signed_type_for (ct), new_step, at_stmt,
                                use_overflow_semantics);
     new_step = chrec_convert_1 (signed_type_for (ct), new_step, at_stmt,
                                use_overflow_semantics);

-  new_step = chrec_convert_1 (type, new_step, at_stmt, use_overflow_semantics);
+  new_step = chrec_convert_1 (step_type, new_step, at_stmt, use_overflow_semantics);

 
   if (automatically_generated_chrec_p (new_base)
       || automatically_generated_chrec_p (new_step))
 
   if (automatically_generated_chrec_p (new_base)
       || automatically_generated_chrec_p (new_step))


@@ -1214,6 +1225,16 @@ convert_affine_scev (struct loop *loop, tree type,
 }
 \f
 
 }
 \f
 

+/* Convert CHREC for the right hand side of a CREC.
+   The increment for a pointer type is always sizetype.  */
+tree 
+chrec_convert_rhs (tree type, tree chrec, gimple at_stmt)
+{
+  if (POINTER_TYPE_P (type))
+   type = sizetype;
+  return chrec_convert (type, chrec, at_stmt);
+}
+

 /* 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
 /* 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


@@ -1239,7 +1260,7 @@ convert_affine_scev (struct loop *loop, tree type,
 */
 
 tree 
 */
 
 tree 

-chrec_convert (tree type, tree chrec, tree at_stmt)
+chrec_convert (tree type, tree chrec, gimple at_stmt)

 {
   return chrec_convert_1 (type, chrec, at_stmt, true);
 }
 {
   return chrec_convert_1 (type, chrec, at_stmt, true);
 }


@@ -1257,7 +1278,7 @@ chrec_convert (tree type, tree chrec, tree at_stmt)
    tests, but also to enforce that the result follows them.  */
 
 static tree 
    tests, but also to enforce that the result follows them.  */
 
 static tree 

-chrec_convert_1 (tree type, tree chrec, tree at_stmt,
+chrec_convert_1 (tree type, tree chrec, gimple at_stmt,

                 bool use_overflow_semantics)
 {
   tree ct, res;
                 bool use_overflow_semantics)
 {
   tree ct, res;


@@ -1274,7 +1295,7 @@ chrec_convert_1 (tree type, tree chrec, tree at_stmt,
   if (!evolution_function_is_affine_p (chrec))
     goto keep_cast;
 
   if (!evolution_function_is_affine_p (chrec))
     goto keep_cast;
 

-  loop = current_loops->parray[CHREC_VARIABLE (chrec)];
+  loop = get_chrec_loop (chrec);

   base = CHREC_LEFT (chrec);
   step = CHREC_RIGHT (chrec);
 
   base = CHREC_LEFT (chrec);
   step = CHREC_RIGHT (chrec);
 


@@ -1288,10 +1309,7 @@ keep_cast:
 
   /* Don't propagate overflows.  */
   if (CONSTANT_CLASS_P (res))
 
   /* Don't propagate overflows.  */
   if (CONSTANT_CLASS_P (res))

-    {
-      TREE_CONSTANT_OVERFLOW (res) = 0;
-      TREE_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
 
   /* 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


@@ -1314,7 +1332,7 @@ keep_cast:
 tree
 chrec_convert_aggressive (tree type, tree chrec)
 {
 tree
 chrec_convert_aggressive (tree type, tree chrec)
 {

-  tree inner_type, left, right, lc, rc;
+  tree inner_type, left, right, lc, rc, rtype;

 
   if (automatically_generated_chrec_p (chrec)
       || TREE_CODE (chrec) != POLYNOMIAL_CHREC)
 
   if (automatically_generated_chrec_p (chrec)
       || TREE_CODE (chrec) != POLYNOMIAL_CHREC)


@@ -1328,14 +1346,16 @@ chrec_convert_aggressive (tree type, tree chrec)
   if (avoid_arithmetics_in_type_p (type))
     return NULL_TREE;
 
   if (avoid_arithmetics_in_type_p (type))
     return NULL_TREE;
 

+  rtype = POINTER_TYPE_P (type) ? sizetype : type;
+

   left = CHREC_LEFT (chrec);
   right = CHREC_RIGHT (chrec);
   lc = chrec_convert_aggressive (type, left);
   if (!lc)
   left = CHREC_LEFT (chrec);
   right = CHREC_RIGHT (chrec);
   lc = chrec_convert_aggressive (type, left);
   if (!lc)

-    lc = chrec_convert (type, left, NULL_TREE);
-  rc = chrec_convert_aggressive (type, right);
+    lc = chrec_convert (type, left, NULL);
+  rc = chrec_convert_aggressive (rtype, right);

   if (!rc)
   if (!rc)

-    rc = chrec_convert (type, right, NULL_TREE);
+    rc = chrec_convert (rtype, right, NULL);

  
   return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
 }
  
   return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
 }


@@ -1343,8 +1363,7 @@ chrec_convert_aggressive (tree type, tree chrec)
 /* Returns true when CHREC0 == CHREC1.  */
 
 bool 
 /* Returns true when CHREC0 == CHREC1.  */
 
 bool 

-eq_evolutions_p (tree chrec0, 
-                tree chrec1)
+eq_evolutions_p (const_tree chrec0, const_tree chrec1)

 {
   if (chrec0 == NULL_TREE
       || chrec1 == NULL_TREE
 {
   if (chrec0 == NULL_TREE
       || chrec1 == NULL_TREE


@@ -1373,9 +1392,9 @@ eq_evolutions_p (tree chrec0,
    which of these cases happens.  */
 
 enum ev_direction
    which of these cases happens.  */
 
 enum ev_direction

-scev_direction (tree chrec)
+scev_direction (const_tree chrec)

 {
 {

-  tree step;
+  const_tree step;

 
   if (!evolution_function_is_affine_p (chrec))
     return EV_DIR_UNKNOWN;
 
   if (!evolution_function_is_affine_p (chrec))
     return EV_DIR_UNKNOWN;


@@ -1389,3 +1408,87 @@ scev_direction (tree chrec)
   else
     return EV_DIR_GROWS;
 }
   else
     return EV_DIR_GROWS;
 }

+
+/* Iterates over all the components of SCEV, and calls CBCK.  */
+
+void
+for_each_scev_op (tree *scev, bool (*cbck) (tree *, void *), void *data)
+{
+  switch (TREE_CODE_LENGTH (TREE_CODE (*scev)))
+    {
+    case 3:
+      for_each_scev_op (&TREE_OPERAND (*scev, 2), cbck, data);
+
+    case 2:
+      for_each_scev_op (&TREE_OPERAND (*scev, 1), cbck, data);
+      
+    case 1:
+      for_each_scev_op (&TREE_OPERAND (*scev, 0), cbck, data);
+
+    default:
+      cbck (scev, data);
+      break;
+    }
+}
+
+/* Returns true when the operation can be part of a linear
+   expression.  */
+
+static inline bool
+operator_is_linear (tree scev)
+{
+  switch (TREE_CODE (scev))
+    {
+    case INTEGER_CST:
+    case POLYNOMIAL_CHREC:
+    case PLUS_EXPR:
+    case POINTER_PLUS_EXPR:
+    case MULT_EXPR:
+    case MINUS_EXPR:
+    case NEGATE_EXPR:
+    case SSA_NAME:
+    case NON_LVALUE_EXPR:
+    CASE_CONVERT:
+      return true;
+
+    default:
+      return false;
+    }
+}
+
+/* Return true when SCEV is a linear expression.  Linear expressions
+   can contain additions, substractions and multiplications.
+   Multiplications are restricted to constant scaling: "cst * x".  */
+
+bool
+scev_is_linear_expression (tree scev)
+{
+  if (scev == NULL
+      || !operator_is_linear (scev))
+    return false;
+
+  if (TREE_CODE (scev) == MULT_EXPR)
+    return !(tree_contains_chrecs (TREE_OPERAND (scev, 0), NULL)
+            && tree_contains_chrecs (TREE_OPERAND (scev, 1), NULL));
+
+  switch (TREE_CODE_LENGTH (TREE_CODE (scev)))
+    {
+    case 3:
+      return scev_is_linear_expression (TREE_OPERAND (scev, 0))
+       && scev_is_linear_expression (TREE_OPERAND (scev, 1))
+       && scev_is_linear_expression (TREE_OPERAND (scev, 2));
+
+    case 2:
+      return scev_is_linear_expression (TREE_OPERAND (scev, 0))
+       && scev_is_linear_expression (TREE_OPERAND (scev, 1));
+      
+    case 1:
+      return scev_is_linear_expression (TREE_OPERAND (scev, 0));
+
+    case 0:
+      return true;
+
+    default:
+      return false;
+    }
+}