* doc/invoke.texi (C++ Dialect Options): Update -fabi-version=6

[pf3gnuchains/gcc-fork.git] / gcc / tree-data-ref.c

diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index 9e5df7d..a0d86ec 100644 (file)
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -1,5 +1,5 @@
 /* Data references and dependences detectors.
 /* Data references and dependences detectors.

-   Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
+   Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011

    Free Software Foundation, Inc.
    Contributed by Sebastian Pop <pop@cri.ensmp.fr>
 
    Free Software Foundation, Inc.
    Contributed by Sebastian Pop <pop@cri.ensmp.fr>
 


@@ -84,6 +84,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-scalar-evolution.h"
 #include "tree-pass.h"
 #include "langhooks.h"
 #include "tree-scalar-evolution.h"
 #include "tree-pass.h"
 #include "langhooks.h"

+#include "tree-affine.h"

 
 static struct datadep_stats
 {
 
 static struct datadep_stats
 {


@@ -123,7 +124,7 @@ tree_fold_divides_p (const_tree a, const_tree b)
 {
   gcc_assert (TREE_CODE (a) == INTEGER_CST);
   gcc_assert (TREE_CODE (b) == INTEGER_CST);
 {
   gcc_assert (TREE_CODE (a) == INTEGER_CST);
   gcc_assert (TREE_CODE (b) == INTEGER_CST);

-  return integer_zerop (int_const_binop (TRUNC_MOD_EXPR, b, a, 0));
+  return integer_zerop (int_const_binop (TRUNC_MOD_EXPR, b, a));

 }
 
 /* Returns true iff A divides B.  */
 }
 
 /* Returns true iff A divides B.  */


@@ -588,9 +589,6 @@ split_constant_offset_1 (tree type, tree op0, enum tree_code code, tree op1,
        int punsignedp, pvolatilep;
 
        op0 = TREE_OPERAND (op0, 0);
        int punsignedp, pvolatilep;
 
        op0 = TREE_OPERAND (op0, 0);

-       if (!handled_component_p (op0))
-         return false;
-

        base = get_inner_reference (op0, &pbitsize, &pbitpos, &poffset,
                                    &pmode, &punsignedp, &pvolatilep, false);
 
        base = get_inner_reference (op0, &pbitsize, &pbitpos, &poffset,
                                    &pmode, &punsignedp, &pvolatilep, false);
 


@@ -604,8 +602,7 @@ split_constant_offset_1 (tree type, tree op0, enum tree_code code, tree op1,
            split_constant_offset (poffset, &poffset, &off1);
            off0 = size_binop (PLUS_EXPR, off0, off1);
            if (POINTER_TYPE_P (TREE_TYPE (base)))
            split_constant_offset (poffset, &poffset, &off1);
            off0 = size_binop (PLUS_EXPR, off0, off1);
            if (POINTER_TYPE_P (TREE_TYPE (base)))

-             base = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (base),
-                                 base, fold_convert (sizetype, poffset));
+             base = fold_build_pointer_plus (base, poffset);

            else
              base = fold_build2 (PLUS_EXPR, TREE_TYPE (base), base,
                                  fold_convert (TREE_TYPE (base), poffset));
            else
              base = fold_build2 (PLUS_EXPR, TREE_TYPE (base), base,
                                  fold_convert (TREE_TYPE (base), poffset));


@@ -686,7 +683,8 @@ split_constant_offset (tree exp, tree *var, tree *off)
   *off = ssize_int (0);
   STRIP_NOPS (exp);
 
   *off = ssize_int (0);
   STRIP_NOPS (exp);
 

-  if (automatically_generated_chrec_p (exp))
+  if (tree_is_chrec (exp)
+      || get_gimple_rhs_class (TREE_CODE (exp)) == GIMPLE_TERNARY_RHS)

     return;
 
   otype = TREE_TYPE (exp);
     return;
 
   otype = TREE_TYPE (exp);


@@ -721,11 +719,11 @@ canonicalize_base_object_address (tree addr)
 }
 
 /* Analyzes the behavior of the memory reference DR in the innermost loop or
 }
 
 /* Analyzes the behavior of the memory reference DR in the innermost loop or

-   basic block that contains it. Returns true if analysis succeed or false
+   basic block that contains it.  Returns true if analysis succeed or false

    otherwise.  */
 
 bool
    otherwise.  */
 
 bool

-dr_analyze_innermost (struct data_reference *dr)
+dr_analyze_innermost (struct data_reference *dr, struct loop *nest)

 {
   gimple stmt = DR_STMT (dr);
   struct loop *loop = loop_containing_stmt (stmt);
 {
   gimple stmt = DR_STMT (dr);
   struct loop *loop = loop_containing_stmt (stmt);


@@ -768,14 +766,25 @@ dr_analyze_innermost (struct data_reference *dr)
     }
   else
     base = build_fold_addr_expr (base);
     }
   else
     base = build_fold_addr_expr (base);

+

   if (in_loop)
     {
       if (!simple_iv (loop, loop_containing_stmt (stmt), base, &base_iv,
                       false))
         {
   if (in_loop)
     {
       if (!simple_iv (loop, loop_containing_stmt (stmt), base, &base_iv,
                       false))
         {

-          if (dump_file && (dump_flags & TDF_DETAILS))
-           fprintf (dump_file, "failed: evolution of base is not affine.\n");
-          return false;
+          if (nest)
+            {
+              if (dump_file && (dump_flags & TDF_DETAILS))
+                fprintf (dump_file, "failed: evolution of base is not"
+                                    " affine.\n");
+              return false;
+            }
+          else
+            {
+              base_iv.base = base;
+              base_iv.step = ssize_int (0);
+              base_iv.no_overflow = true;
+            }

         }
     }
   else
         }
     }
   else


@@ -800,10 +809,18 @@ dr_analyze_innermost (struct data_reference *dr)
       else if (!simple_iv (loop, loop_containing_stmt (stmt),
                            poffset, &offset_iv, false))
         {
       else if (!simple_iv (loop, loop_containing_stmt (stmt),
                            poffset, &offset_iv, false))
         {

-          if (dump_file && (dump_flags & TDF_DETAILS))
-            fprintf (dump_file, "failed: evolution of offset is not"
-                                " affine.\n");
-          return false;
+          if (nest)
+            {
+              if (dump_file && (dump_flags & TDF_DETAILS))
+                fprintf (dump_file, "failed: evolution of offset is not"
+                                    " affine.\n");
+              return false;
+            }
+          else
+            {
+              offset_iv.base = poffset;
+              offset_iv.step = ssize_int (0);
+            }

         }
     }
 
         }
     }
 


@@ -838,66 +855,93 @@ static void
 dr_analyze_indices (struct data_reference *dr, loop_p nest, loop_p loop)
 {
   VEC (tree, heap) *access_fns = NULL;
 dr_analyze_indices (struct data_reference *dr, loop_p nest, loop_p loop)
 {
   VEC (tree, heap) *access_fns = NULL;

-  tree ref = unshare_expr (DR_REF (dr)), aref = ref, op;
-  tree base, off, access_fn = NULL_TREE;
-  basic_block before_loop = NULL;
+  tree ref, *aref, op;
+  tree base, off, access_fn;
+  basic_block before_loop;
+
+  /* If analyzing a basic-block there are no indices to analyze
+     and thus no access functions.  */
+  if (!nest)
+    {
+      DR_BASE_OBJECT (dr) = DR_REF (dr);
+      DR_ACCESS_FNS (dr) = NULL;
+      return;
+    }
+
+  ref = unshare_expr (DR_REF (dr));
+  before_loop = block_before_loop (nest);

 
 

-  if (nest)
-    before_loop = block_before_loop (nest);
+  /* REALPART_EXPR and IMAGPART_EXPR can be handled like accesses
+     into a two element array with a constant index.  The base is
+     then just the immediate underlying object.  */
+  if (TREE_CODE (ref) == REALPART_EXPR)
+    {
+      ref = TREE_OPERAND (ref, 0);
+      VEC_safe_push (tree, heap, access_fns, integer_zero_node);
+    }
+  else if (TREE_CODE (ref) == IMAGPART_EXPR)
+    {
+      ref = TREE_OPERAND (ref, 0);
+      VEC_safe_push (tree, heap, access_fns, integer_one_node);
+    }

 
 

-  while (handled_component_p (aref))
+  /* Analyze access functions of dimensions we know to be independent.  */
+  aref = &ref;
+  while (handled_component_p (*aref))

     {
     {

-      if (TREE_CODE (aref) == ARRAY_REF)
+      if (TREE_CODE (*aref) == ARRAY_REF)

        {
        {

-         op = TREE_OPERAND (aref, 1);
-         if (nest)
+         op = TREE_OPERAND (*aref, 1);
+         access_fn = analyze_scalar_evolution (loop, op);
+         access_fn = instantiate_scev (before_loop, loop, access_fn);
+         VEC_safe_push (tree, heap, access_fns, access_fn);
+         /* For ARRAY_REFs the base is the reference with the index replaced
+            by zero if we can not strip it as the outermost component.  */
+         if (*aref == ref)

            {
            {

-             access_fn = analyze_scalar_evolution (loop, op);
-             access_fn = instantiate_scev (before_loop, loop, access_fn);
-             VEC_safe_push (tree, heap, access_fns, access_fn);
+             *aref = TREE_OPERAND (*aref, 0);
+             continue;

            }
            }

-
-         TREE_OPERAND (aref, 1) = build_int_cst (TREE_TYPE (op), 0);
+         else
+           TREE_OPERAND (*aref, 1) = build_int_cst (TREE_TYPE (op), 0);

        }
 
        }
 

-      aref = TREE_OPERAND (aref, 0);
+      aref = &TREE_OPERAND (*aref, 0);

     }
 
     }
 

-  if (nest
-      && (INDIRECT_REF_P (aref)
-         || TREE_CODE (aref) == MEM_REF))
+  /* If the address operand of a MEM_REF base has an evolution in the
+     analyzed nest, add it as an additional independent access-function.  */
+  if (TREE_CODE (*aref) == MEM_REF)

     {
     {

-      op = TREE_OPERAND (aref, 0);
+      op = TREE_OPERAND (*aref, 0);

       access_fn = analyze_scalar_evolution (loop, op);
       access_fn = instantiate_scev (before_loop, loop, access_fn);
       access_fn = analyze_scalar_evolution (loop, op);
       access_fn = instantiate_scev (before_loop, loop, access_fn);

-      base = initial_condition (access_fn);
-      split_constant_offset (base, &base, &off);
-      if (TREE_CODE (aref) == MEM_REF)
-       off = size_binop (PLUS_EXPR, off,
-                         fold_convert (ssizetype, TREE_OPERAND (aref, 1)));
-      access_fn = chrec_replace_initial_condition (access_fn,
-                       fold_convert (TREE_TYPE (base), off));
-
-      TREE_OPERAND (aref, 0) = base;
-      VEC_safe_push (tree, heap, access_fns, access_fn);
+      if (TREE_CODE (access_fn) == POLYNOMIAL_CHREC)
+       {
+         tree orig_type;
+         base = initial_condition (access_fn);
+         orig_type = TREE_TYPE (base);
+         STRIP_USELESS_TYPE_CONVERSION (base);
+         split_constant_offset (base, &base, &off);
+         /* Fold the MEM_REF offset into the evolutions initial
+            value to make more bases comparable.  */
+         if (!integer_zerop (TREE_OPERAND (*aref, 1)))
+           {
+             off = size_binop (PLUS_EXPR, off,
+                               fold_convert (ssizetype,
+                                             TREE_OPERAND (*aref, 1)));
+             TREE_OPERAND (*aref, 1)
+               = build_int_cst (TREE_TYPE (TREE_OPERAND (*aref, 1)), 0);
+           }
+         access_fn = chrec_replace_initial_condition
+             (access_fn, fold_convert (orig_type, off));
+         *aref = fold_build2_loc (EXPR_LOCATION (*aref),
+                                  MEM_REF, TREE_TYPE (*aref),
+                                  base, TREE_OPERAND (*aref, 1));
+         VEC_safe_push (tree, heap, access_fns, access_fn);
+       }

     }
 
     }
 

-  if (TREE_CODE (aref) == MEM_REF)
-    TREE_OPERAND (aref, 1)
-      = build_int_cst (TREE_TYPE (TREE_OPERAND (aref, 1)), 0);
-
-  if (TREE_CODE (ref) == MEM_REF
-      && TREE_CODE (TREE_OPERAND (ref, 0)) == ADDR_EXPR
-      && integer_zerop (TREE_OPERAND (ref, 1)))
-    ref = TREE_OPERAND (TREE_OPERAND (ref, 0), 0);
-
-  /* For canonicalization purposes we'd like to strip all outermost
-     zero-offset component-refs.
-     ???  For now simply handle zero-index array-refs.  */
-  while (TREE_CODE (ref) == ARRAY_REF
-        && integer_zerop (TREE_OPERAND (ref, 1)))
-    ref = TREE_OPERAND (ref, 0);
-

   DR_BASE_OBJECT (dr) = ref;
   DR_ACCESS_FNS (dr) = access_fns;
 }
   DR_BASE_OBJECT (dr) = ref;
   DR_ACCESS_FNS (dr) = access_fns;
 }


@@ -919,21 +963,6 @@ dr_analyze_alias (struct data_reference *dr)
     }
 }
 
     }
 }
 

-/* Returns true if the address of DR is invariant.  */
-
-static bool
-dr_address_invariant_p (struct data_reference *dr)
-{
-  unsigned i;
-  tree idx;
-
-  FOR_EACH_VEC_ELT (tree, DR_ACCESS_FNS (dr), i, idx)
-    if (tree_contains_chrecs (idx, NULL))
-      return false;
-
-  return true;
-}
-

 /* Frees data reference DR.  */
 
 void
 /* Frees data reference DR.  */
 
 void


@@ -967,12 +996,13 @@ create_data_ref (loop_p nest, loop_p loop, tree memref, gimple stmt,
   DR_REF (dr) = memref;
   DR_IS_READ (dr) = is_read;
 
   DR_REF (dr) = memref;
   DR_IS_READ (dr) = is_read;
 

-  dr_analyze_innermost (dr);
+  dr_analyze_innermost (dr, nest);

   dr_analyze_indices (dr, nest, loop);
   dr_analyze_alias (dr);
 
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
   dr_analyze_indices (dr, nest, loop);
   dr_analyze_alias (dr);
 
   if (dump_file && (dump_flags & TDF_DETAILS))
     {

+      unsigned i;

       fprintf (dump_file, "\tbase_address: ");
       print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM);
       fprintf (dump_file, "\n\toffset from base address: ");
       fprintf (dump_file, "\tbase_address: ");
       print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM);
       fprintf (dump_file, "\n\toffset from base address: ");


@@ -986,11 +1016,58 @@ create_data_ref (loop_p nest, loop_p loop, tree memref, gimple stmt,
       fprintf (dump_file, "\n\tbase_object: ");
       print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
       fprintf (dump_file, "\n");
       fprintf (dump_file, "\n\tbase_object: ");
       print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
       fprintf (dump_file, "\n");

+      for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
+       {
+         fprintf (dump_file, "\tAccess function %d: ", i);
+         print_generic_stmt (dump_file, DR_ACCESS_FN (dr, i), TDF_SLIM);
+       }

     }
 
   return dr;
 }
 
     }
 
   return dr;
 }
 

+/* Check if OFFSET1 and OFFSET2 (DR_OFFSETs of some data-refs) are identical
+   expressions.  */
+static bool
+dr_equal_offsets_p1 (tree offset1, tree offset2)
+{
+  bool res;
+
+  STRIP_NOPS (offset1);
+  STRIP_NOPS (offset2);
+
+  if (offset1 == offset2)
+    return true;
+
+  if (TREE_CODE (offset1) != TREE_CODE (offset2)
+      || (!BINARY_CLASS_P (offset1) && !UNARY_CLASS_P (offset1)))
+    return false;
+
+  res = dr_equal_offsets_p1 (TREE_OPERAND (offset1, 0),
+                             TREE_OPERAND (offset2, 0));
+
+  if (!res || !BINARY_CLASS_P (offset1))
+    return res;
+
+  res = dr_equal_offsets_p1 (TREE_OPERAND (offset1, 1),
+                             TREE_OPERAND (offset2, 1));
+
+  return res;
+}
+
+/* Check if DRA and DRB have equal offsets.  */
+bool
+dr_equal_offsets_p (struct data_reference *dra,
+                    struct data_reference *drb)
+{
+  tree offset1, offset2;
+
+  offset1 = DR_OFFSET (dra);
+  offset2 = DR_OFFSET (drb);
+
+  return dr_equal_offsets_p1 (offset1, offset2);
+}
+

 /* Returns true if FNA == FNB.  */
 
 static bool
 /* Returns true if FNA == FNB.  */
 
 static bool


@@ -1240,14 +1317,33 @@ object_address_invariant_in_loop_p (const struct loop *loop, const_tree obj)
 }
 
 /* Returns false if we can prove that data references A and B do not alias,
 }
 
 /* Returns false if we can prove that data references A and B do not alias,

-   true otherwise.  */
+   true otherwise.  If LOOP_NEST is false no cross-iteration aliases are
+   considered.  */

 
 bool
 
 bool

-dr_may_alias_p (const struct data_reference *a, const struct data_reference *b)
+dr_may_alias_p (const struct data_reference *a, const struct data_reference *b,
+               bool loop_nest)

 {
   tree addr_a = DR_BASE_OBJECT (a);
   tree addr_b = DR_BASE_OBJECT (b);
 
 {
   tree addr_a = DR_BASE_OBJECT (a);
   tree addr_b = DR_BASE_OBJECT (b);
 

+  /* If we are not processing a loop nest but scalar code we
+     do not need to care about possible cross-iteration dependences
+     and thus can process the full original reference.  Do so,
+     similar to how loop invariant motion applies extra offset-based
+     disambiguation.  */
+  if (!loop_nest)
+    {
+      aff_tree off1, off2;
+      double_int size1, size2;
+      get_inner_reference_aff (DR_REF (a), &off1, &size1);
+      get_inner_reference_aff (DR_REF (b), &off2, &size2);
+      aff_combination_scale (&off1, double_int_minus_one);
+      aff_combination_add (&off2, &off1);
+      if (aff_comb_cannot_overlap_p (&off2, size1, size2))
+       return false;
+    }
+

   if (DR_IS_WRITE (a) && DR_IS_WRITE (b))
     return refs_output_dependent_p (addr_a, addr_b);
   else if (DR_IS_READ (a) && DR_IS_WRITE (b))
   if (DR_IS_WRITE (a) && DR_IS_WRITE (b))
     return refs_output_dependent_p (addr_a, addr_b);
   else if (DR_IS_READ (a) && DR_IS_WRITE (b))


@@ -1255,13 +1351,11 @@ dr_may_alias_p (const struct data_reference *a, const struct data_reference *b)
   return refs_may_alias_p (addr_a, addr_b);
 }
 
   return refs_may_alias_p (addr_a, addr_b);
 }
 

-static void compute_self_dependence (struct data_dependence_relation *);
-

 /* Initialize a data dependence relation between data accesses A and
    B.  NB_LOOPS is the number of loops surrounding the references: the
    size of the classic distance/direction vectors.  */
 
 /* Initialize a data dependence relation between data accesses A and
    B.  NB_LOOPS is the number of loops surrounding the references: the
    size of the classic distance/direction vectors.  */
 

-static struct data_dependence_relation *
+struct data_dependence_relation *

 initialize_data_dependence_relation (struct data_reference *a,
                                     struct data_reference *b,
                                     VEC (loop_p, heap) *loop_nest)
 initialize_data_dependence_relation (struct data_reference *a,
                                     struct data_reference *b,
                                     VEC (loop_p, heap) *loop_nest)


@@ -1285,23 +1379,39 @@ initialize_data_dependence_relation (struct data_reference *a,
     }
 
   /* If the data references do not alias, then they are independent.  */
     }
 
   /* If the data references do not alias, then they are independent.  */

-  if (!dr_may_alias_p (a, b))
+  if (!dr_may_alias_p (a, b, loop_nest != NULL))

     {
       DDR_ARE_DEPENDENT (res) = chrec_known;
       return res;
     }
 
     {
       DDR_ARE_DEPENDENT (res) = chrec_known;
       return res;
     }
 

-  /* When the references are exactly the same, don't spend time doing
-     the data dependence tests, just initialize the ddr and return.  */
+  /* The case where the references are exactly the same.  */

   if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
     {
   if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
     {

+     if (loop_nest
+        && !object_address_invariant_in_loop_p (VEC_index (loop_p, loop_nest, 0),
+                                                       DR_BASE_OBJECT (a)))
+      {
+        DDR_ARE_DEPENDENT (res) = chrec_dont_know;
+        return res;
+      }

       DDR_AFFINE_P (res) = true;
       DDR_ARE_DEPENDENT (res) = NULL_TREE;
       DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
       DDR_LOOP_NEST (res) = loop_nest;
       DDR_INNER_LOOP (res) = 0;
       DDR_SELF_REFERENCE (res) = true;
       DDR_AFFINE_P (res) = true;
       DDR_ARE_DEPENDENT (res) = NULL_TREE;
       DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
       DDR_LOOP_NEST (res) = loop_nest;
       DDR_INNER_LOOP (res) = 0;
       DDR_SELF_REFERENCE (res) = true;

-      compute_self_dependence (res);
+      for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
+       {
+         struct subscript *subscript;
+
+         subscript = XNEW (struct subscript);
+         SUB_CONFLICTS_IN_A (subscript) = conflict_fn_not_known ();
+         SUB_CONFLICTS_IN_B (subscript) = conflict_fn_not_known ();
+         SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
+         SUB_DISTANCE (subscript) = chrec_dont_know;
+         VEC_safe_push (subscript_p, heap, DDR_SUBSCRIPTS (res), subscript);
+       }

       return res;
     }
 
       return res;
     }
 


@@ -1579,73 +1689,23 @@ analyze_ziv_subscript (tree chrec_a,
     fprintf (dump_file, ")\n");
 }
 
     fprintf (dump_file, ")\n");
 }
 

-/* 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.  */
-
-bool
-estimated_loop_iterations (struct loop *loop, bool conservative,
-                          double_int *nit)
-{
-  estimate_numbers_of_iterations_loop (loop, true);
-  if (conservative)
-    {
-      if (!loop->any_upper_bound)
-       return false;
-
-      *nit = loop->nb_iterations_upper_bound;
-    }
-  else
-    {
-      if (!loop->any_estimate)
-       return false;
-
-      *nit = loop->nb_iterations_estimate;
-    }
-
-  return true;
-}
-
-/* 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,
+/* Similar to max_stmt_executions_int, but returns the bound as a tree,

    and only if it fits to the int type.  If this is not the case, or the
    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
+   bound  on the number of iterations of LOOP could not be derived, returns

    chrec_dont_know.  */
 
 static tree
    chrec_dont_know.  */
 
 static tree

-estimated_loop_iterations_tree (struct loop *loop, bool conservative)
+max_stmt_executions_tree (struct loop *loop)

 {
   double_int nit;
 {
   double_int nit;

-  tree type;

 
 

-  if (!estimated_loop_iterations (loop, conservative, &nit))
+  if (!max_stmt_executions (loop, true, &nit))

     return chrec_dont_know;
 
     return chrec_dont_know;
 

-  type = lang_hooks.types.type_for_size (INT_TYPE_SIZE, true);
-  if (!double_int_fits_to_tree_p (type, nit))
+  if (!double_int_fits_to_tree_p (unsigned_type_node, nit))

     return chrec_dont_know;
 
     return chrec_dont_know;
 

-  return double_int_to_tree (type, nit);
+  return double_int_to_tree (unsigned_type_node, nit);

 }
 
 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
 }
 
 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a


@@ -1721,7 +1781,7 @@ analyze_siv_subscript_cst_affine (tree chrec_a,
 
                      /* Perform weak-zero siv test to see if overlap is
                         outside the loop bounds.  */
 
                      /* Perform weak-zero siv test to see if overlap is
                         outside the loop bounds.  */

-                     numiter = estimated_loop_iterations_int (loop, false);
+                     numiter = max_stmt_executions_int (loop, true);

 
                      if (numiter >= 0
                          && compare_tree_int (tmp, numiter) > 0)
 
                      if (numiter >= 0
                          && compare_tree_int (tmp, numiter) > 0)


@@ -1799,7 +1859,7 @@ analyze_siv_subscript_cst_affine (tree chrec_a,
 
                      /* Perform weak-zero siv test to see if overlap is
                         outside the loop bounds.  */
 
                      /* Perform weak-zero siv test to see if overlap is
                         outside the loop bounds.  */

-                     numiter = estimated_loop_iterations_int (loop, false);
+                     numiter = max_stmt_executions_int (loop, true);

 
                      if (numiter >= 0
                          && compare_tree_int (tmp, numiter) > 0)
 
                      if (numiter >= 0
                          && compare_tree_int (tmp, numiter) > 0)


@@ -1980,10 +2040,9 @@ compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
   step_z = int_cst_value (CHREC_RIGHT (chrec_b));
 
   niter_x =
   step_z = int_cst_value (CHREC_RIGHT (chrec_b));
 
   niter_x =

-    estimated_loop_iterations_int (get_chrec_loop (CHREC_LEFT (chrec_a)),
-                                  false);
-  niter_y = estimated_loop_iterations_int (get_chrec_loop (chrec_a), false);
-  niter_z = estimated_loop_iterations_int (get_chrec_loop (chrec_b), false);
+    max_stmt_executions_int (get_chrec_loop (CHREC_LEFT (chrec_a)), true);
+  niter_y = max_stmt_executions_int (get_chrec_loop (chrec_a), true);
+  niter_z = max_stmt_executions_int (get_chrec_loop (chrec_b), true);

 
   if (niter_x < 0 || niter_y < 0 || niter_z < 0)
     {
 
   if (niter_x < 0 || niter_y < 0 || niter_z < 0)
     {


@@ -2308,10 +2367,8 @@ analyze_subscript_affine_affine (tree chrec_a,
          HOST_WIDE_INT niter, niter_a, niter_b;
          affine_fn ova, ovb;
 
          HOST_WIDE_INT niter, niter_a, niter_b;
          affine_fn ova, ovb;
 

-         niter_a = estimated_loop_iterations_int (get_chrec_loop (chrec_a),
-                                                  false);
-         niter_b = estimated_loop_iterations_int (get_chrec_loop (chrec_b),
-                                                  false);
+         niter_a = max_stmt_executions_int (get_chrec_loop (chrec_a), true);
+         niter_b = max_stmt_executions_int (get_chrec_loop (chrec_b), true);

          niter = MIN (niter_a, niter_b);
          step_a = int_cst_value (CHREC_RIGHT (chrec_a));
          step_b = int_cst_value (CHREC_RIGHT (chrec_b));
          niter = MIN (niter_a, niter_b);
          step_a = int_cst_value (CHREC_RIGHT (chrec_a));
          step_b = int_cst_value (CHREC_RIGHT (chrec_b));


@@ -2418,10 +2475,10 @@ analyze_subscript_affine_affine (tree chrec_a,
 
          if (i1 > 0 && j1 > 0)
            {
 
          if (i1 > 0 && j1 > 0)
            {

-             HOST_WIDE_INT niter_a = estimated_loop_iterations_int
-               (get_chrec_loop (chrec_a), false);
-             HOST_WIDE_INT niter_b = estimated_loop_iterations_int
-               (get_chrec_loop (chrec_b), false);
+             HOST_WIDE_INT niter_a = max_stmt_executions_int
+               (get_chrec_loop (chrec_a), true);
+             HOST_WIDE_INT niter_b = max_stmt_executions_int
+               (get_chrec_loop (chrec_b), true);

              HOST_WIDE_INT niter = MIN (niter_a, niter_b);
 
              /* (X0, Y0) is a solution of the Diophantine equation:
              HOST_WIDE_INT niter = MIN (niter_a, niter_b);
 
              /* (X0, Y0) is a solution of the Diophantine equation:


@@ -2681,14 +2738,6 @@ analyze_miv_subscript (tree chrec_a,
                       tree *last_conflicts,
                       struct loop *loop_nest)
 {
                       tree *last_conflicts,
                       struct loop *loop_nest)
 {

-  /* FIXME:  This is a MIV subscript, not yet handled.
-     Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
-     (A[i] vs. A[j]).
-
-     In the SIV test we had to solve a Diophantine equation with two
-     variables.  In the MIV case we have to solve a Diophantine
-     equation with 2*n variables (if the subscript uses n IVs).
-  */

   tree type, difference;
 
   dependence_stats.num_miv++;
   tree type, difference;
 
   dependence_stats.num_miv++;


@@ -2706,8 +2755,7 @@ 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));
         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 = estimated_loop_iterations_tree
-                               (get_chrec_loop (chrec_a), true);
+      *last_conflicts = max_stmt_executions_tree (get_chrec_loop (chrec_a));

       dependence_stats.num_miv_dependent++;
     }
 
       dependence_stats.num_miv_dependent++;
     }
 


@@ -2960,29 +3008,19 @@ build_classic_dist_vector_1 (struct data_dependence_relation *ddr,
          && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
        {
          int dist, index;
          && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
        {
          int dist, index;

-         int index_a = index_in_loop_nest (CHREC_VARIABLE (access_fn_a),
-                                           DDR_LOOP_NEST (ddr));
-         int index_b = index_in_loop_nest (CHREC_VARIABLE (access_fn_b),
-                                           DDR_LOOP_NEST (ddr));
-
-         /* The dependence is carried by the outermost loop.  Example:
-            | loop_1
-            |   A[{4, +, 1}_1]
-            |   loop_2
-            |     A[{5, +, 1}_2]
-            |   endloop_2
-            | endloop_1
-            In this case, the dependence is carried by loop_1.  */
-         index = index_a < index_b ? index_a : index_b;
-         *index_carry = MIN (index, *index_carry);
+         int var_a = CHREC_VARIABLE (access_fn_a);
+         int var_b = CHREC_VARIABLE (access_fn_b);

 
 

-         if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
+         if (var_a != var_b
+             || chrec_contains_undetermined (SUB_DISTANCE (subscript)))

            {
              non_affine_dependence_relation (ddr);
              return false;
            }
 
          dist = int_cst_value (SUB_DISTANCE (subscript));
            {
              non_affine_dependence_relation (ddr);
              return false;
            }
 
          dist = int_cst_value (SUB_DISTANCE (subscript));

+         index = index_in_loop_nest (var_a, DDR_LOOP_NEST (ddr));
+         *index_carry = MIN (index, *index_carry);

 
          /* This is the subscript coupling test.  If we have already
             recorded a distance for this loop (a distance coming from
 
          /* This is the subscript coupling test.  If we have already
             recorded a distance for this loop (a distance coming from


@@ -3730,7 +3768,7 @@ init_omega_for_ddr_1 (struct data_reference *dra, struct data_reference *drb,
   for (i = 0; i <= DDR_INNER_LOOP (ddr)
         && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
     {
   for (i = 0; i <= DDR_INNER_LOOP (ddr)
         && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
     {

-      HOST_WIDE_INT nbi = estimated_loop_iterations_int (loopi, false);
+      HOST_WIDE_INT nbi = max_stmt_executions_int (loopi, true);

 
       /* 0 <= loop_x */
       ineq = omega_add_zero_geq (pb, omega_black);
 
       /* 0 <= loop_x */
       ineq = omega_add_zero_geq (pb, omega_black);


@@ -4018,8 +4056,7 @@ compute_affine_dependence (struct data_dependence_relation *ddr,
     }
 
   /* Analyze only when the dependence relation is not yet known.  */
     }
 
   /* Analyze only when the dependence relation is not yet known.  */

-  if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
-      && !DDR_SELF_REFERENCE (ddr))
+  if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)

     {
       dependence_stats.num_dependence_tests++;
 
     {
       dependence_stats.num_dependence_tests++;
 


@@ -4094,39 +4131,6 @@ compute_affine_dependence (struct data_dependence_relation *ddr,
     fprintf (dump_file, ")\n");
 }
 
     fprintf (dump_file, ")\n");
 }
 

-/* This computes the dependence relation for the same data
-   reference into DDR.  */
-
-static void
-compute_self_dependence (struct data_dependence_relation *ddr)
-{
-  unsigned int i;
-  struct subscript *subscript;
-
-  if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
-    return;
-
-  for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
-       i++)
-    {
-      if (SUB_CONFLICTS_IN_A (subscript))
-       free_conflict_function (SUB_CONFLICTS_IN_A (subscript));
-      if (SUB_CONFLICTS_IN_B (subscript))
-       free_conflict_function (SUB_CONFLICTS_IN_B (subscript));
-
-      /* The accessed index overlaps for each iteration.  */
-      SUB_CONFLICTS_IN_A (subscript)
-       = conflict_fn (1, affine_fn_cst (integer_zero_node));
-      SUB_CONFLICTS_IN_B (subscript)
-       = conflict_fn (1, affine_fn_cst (integer_zero_node));
-      SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
-    }
-
-  /* The distance vector is the zero vector.  */
-  save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
-  save_dir_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
-}
-

 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
    the data references in DATAREFS, in the LOOP_NEST.  When
    COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
    the data references in DATAREFS, in the LOOP_NEST.  When
    COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self


@@ -4157,7 +4161,8 @@ compute_all_dependences (VEC (data_reference_p, heap) *datarefs,
       {
        ddr = initialize_data_dependence_relation (a, a, loop_nest);
        VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
       {
        ddr = initialize_data_dependence_relation (a, a, loop_nest);
        VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);

-       compute_self_dependence (ddr);
+        if (loop_nest)
+         compute_affine_dependence (ddr, VEC_index (loop_p, loop_nest, 0));

       }
 }
 
       }
 }
 


@@ -4201,33 +4206,37 @@ get_references_in_stmt (gimple stmt, VEC (data_ref_loc, heap) **references)
          ref->pos = op1;
          ref->is_read = true;
        }
          ref->pos = op1;
          ref->is_read = true;
        }

-
-      if (DECL_P (*op0)
-         || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0)))
-       {
-         ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
-         ref->pos = op0;
-         ref->is_read = false;
-       }

     }
   else if (stmt_code == GIMPLE_CALL)
     {
     }
   else if (stmt_code == GIMPLE_CALL)
     {

-      unsigned i, n = gimple_call_num_args (stmt);
+      unsigned i, n;

 
 

+      op0 = gimple_call_lhs_ptr (stmt);
+      n = gimple_call_num_args (stmt);

       for (i = 0; i < n; i++)
        {
       for (i = 0; i < n; i++)
        {

-         op0 = gimple_call_arg_ptr (stmt, i);
+         op1 = gimple_call_arg_ptr (stmt, i);

 
 

-         if (DECL_P (*op0)
-             || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0)))
+         if (DECL_P (*op1)
+             || (REFERENCE_CLASS_P (*op1) && get_base_address (*op1)))

            {
              ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
            {
              ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);

-             ref->pos = op0;
+             ref->pos = op1;

              ref->is_read = true;
            }
        }
     }
              ref->is_read = true;
            }
        }
     }

+  else
+    return clobbers_memory;

 
 

+  if (*op0
+      && (DECL_P (*op0)
+         || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0))))
+    {
+      ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
+      ref->pos = op0;
+      ref->is_read = false;
+    }

   return clobbers_memory;
 }
 
   return clobbers_memory;
 }
 


@@ -4256,19 +4265,6 @@ find_data_references_in_stmt (struct loop *nest, gimple stmt,
       dr = create_data_ref (nest, loop_containing_stmt (stmt),
                            *ref->pos, stmt, ref->is_read);
       gcc_assert (dr != NULL);
       dr = create_data_ref (nest, loop_containing_stmt (stmt),
                            *ref->pos, stmt, ref->is_read);
       gcc_assert (dr != NULL);

-
-      /* FIXME -- data dependence analysis does not work correctly for objects
-         with invariant addresses in loop nests.  Let us fail here until the
-        problem is fixed.  */
-      if (dr_address_invariant_p (dr) && nest)
-       {
-         free_data_ref (dr);
-         if (dump_file && (dump_flags & TDF_DETAILS))
-           fprintf (dump_file, "\tFAILED as dr address is invariant\n");
-         ret = false;
-         break;
-       }
-

       VEC_safe_push (data_reference_p, heap, *datarefs, dr);
     }
   VEC_free (data_ref_loc, heap, references);
       VEC_safe_push (data_reference_p, heap, *datarefs, dr);
     }
   VEC_free (data_ref_loc, heap, references);


@@ -4312,7 +4308,7 @@ graphite_find_data_references_in_stmt (loop_p nest, loop_p loop, gimple stmt,
    DATAREFS.  Returns chrec_dont_know when failing to analyze a
    difficult case, returns NULL_TREE otherwise.  */
 
    DATAREFS.  Returns chrec_dont_know when failing to analyze a
    difficult case, returns NULL_TREE otherwise.  */
 

-static tree
+tree

 find_data_references_in_bb (struct loop *loop, basic_block bb,
                             VEC (data_reference_p, heap) **datarefs)
 {
 find_data_references_in_bb (struct loop *loop, basic_block bb,
                             VEC (data_reference_p, heap) **datarefs)
 {


@@ -4993,7 +4989,7 @@ stmts_from_loop (struct loop *loop, VEC (gimple, heap) **stmts)
       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
        {
          stmt = gsi_stmt (bsi);
       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
        {
          stmt = gsi_stmt (bsi);

-         if (gimple_code (stmt) != GIMPLE_LABEL)
+         if (gimple_code (stmt) != GIMPLE_LABEL && !is_gimple_debug (stmt))

            VEC_safe_push (gimple, heap, *stmts, stmt);
        }
     }
            VEC_safe_push (gimple, heap, *stmts, stmt);
        }
     }


@@ -5103,11 +5099,9 @@ free_rdg (struct graph *rdg)
       struct graph_edge *e;
 
       for (e = v->succ; e; e = e->succ_next)
       struct graph_edge *e;
 
       for (e = v->succ; e; e = e->succ_next)

-       if (e->data)
-         free (e->data);
+       free (e->data);

 
 

-      if (v->data)
-       free (v->data);
+      free (v->data);

     }
 
   htab_delete (rdg->indices);
     }
 
   htab_delete (rdg->indices);


@@ -5161,7 +5155,7 @@ stmt_with_adjacent_zero_store_dr_p (gimple stmt)
   DR_STMT (dr) = stmt;
   DR_REF (dr) = op0;
 
   DR_STMT (dr) = stmt;
   DR_REF (dr) = op0;
 

-  res = dr_analyze_innermost (dr)
+  res = dr_analyze_innermost (dr, loop_containing_stmt (stmt))

     && stride_of_unit_type_p (DR_STEP (dr), TREE_TYPE (op0));
 
   free_data_ref (dr);
     && stride_of_unit_type_p (DR_STEP (dr), TREE_TYPE (op0));
 
   free_data_ref (dr);


@@ -5201,7 +5195,7 @@ ref_base_address (gimple stmt, data_ref_loc *ref)
 
   DR_STMT (dr) = stmt;
   DR_REF (dr) = *ref->pos;
 
   DR_STMT (dr) = stmt;
   DR_REF (dr) = *ref->pos;

-  dr_analyze_innermost (dr);
+  dr_analyze_innermost (dr, loop_containing_stmt (stmt));

   base_address = DR_BASE_ADDRESS (dr);
 
   if (!base_address)
   base_address = DR_BASE_ADDRESS (dr);
 
   if (!base_address)