This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [patch] Predictive commoning, updated


Hello,

> > I have run into some problems with
> > data reference analysis (and I do not see a simple clear solution;
> > either I can hack over them, or rewrite half of tree-data-ref.c;
> > slowly I am getting persuaded that the latter is a better choice).
> >
> 
> I'm curious what are the problems you're seeing, especially in case it's
> problems that should concern the vectorizer?

there are several problems with data reference analysis (object_analysis
& friends):

1) it is a bit messy; as usual, this developed historically.  We
   used to have a (somewhat simplistic) data reference analysis that
   handled just some special cases (sequence of ARRAY_REFs and at most one
   COMPONENT_REF, or something like that).  This was not sufficient for
   vectorizer, but instead of extending or replacing this analysis, we
   hacked in another one that is used when the first one does not apply.
   However, this second analysis delivers somewhat different results (it
   only analyses the behavior of the memory reference in the innermost
   loop, not any deeper loop nest); to make this work, some of the fields
   of struct data_reference are filled in by the first analysis, some by
   the second one, and one (access_fns) is shared magically, although it
   has slightly different semantics in each of the cases.

   The side effect of this was that although I wanted to use data
   reference analysis results in predictive commoning, it was close to
   impossible -- it is somewhat hard to work with analysis that delivers
   some of the results only part of the time and changes semantics of
   some of the results depending on the analysed object.

2) Semantics of some of the fields is not described well enough, e.g.
   deciphering what exactly does the alignment information stored in
   struct first_location_in_loop mean was real fun.  More importantly,
   it is not clear what DR_MEMTAG is supposed to mean -- sometimes, we
   initialize it from the tag of the base of the memory reference,
   sometimes from the initial value of the induction variable that
   is dereferenced; I could not find a setting for this value so that it
   is conservative enough that when we use it to set the virtual
   operands of newly created statements, they are correct; and at the
   same time, to be strong enough that when we use it in data dependence
   analysis to prove independence of accesses, it handles all current
   vectorizer testcases.
   
3) Both analyses are implemented in unnecessarily complex ways, ignoring
   existing helper functions.

Especially to fix 1), I did not see any other way but to rewrite things
from scratch, which the patch below does.

Data reference analysis (and correspondingly, struct data_reference)
is now separated into several parts:

-- dr_analyze_innermost analyses the behavior of the reference with
   respect to the innermost enclosing loop (which is what vectorizer
   uses).
-- dr_analyze_indices splits the reference into base object and a
   sequence of indices (which is what data dependence analysis uses).
-- dr_analyze_alias extracts alias information from the data
   reference (it is then used for setting up information for
   newly created references, and in data dependence analysis).

Some other changes to make things work had to be done:

-- adjustments to data dependence analysis, most importantly a new
   dr_may_alias_p function that replaces base_addr_differ_p
   and lots of case analysis (X_Y_differ_p for X and Y being any
   conceivable combination of array, ptr, decl, and record).

-- data dependence analysis gets confused when evolutions in the loops
   outside of the considered loop nest are included in the access_fns.
   This problem was present before (it causes PR31762 and its duplicates),
   but it was covered by the fact that most of the time we used the newer
   dr analysis introduced for vectorizer, that only considers the
   references with respect to the innermost enclosing loop.

   To fix this issue, we now do not instantiate the symbols that
   are defined outside of the analysed loop nest (which also fixes PR31762).

-- chrec_contains_undetermined considers NULL_TREE to be a special
   automatically generated chrec (also since we define
   chrec_not_analyzed_yet == NULL_TREE).  However, NULL_TREE is a valid
   argument of some of the tree nodes, so chrec_contains_undetermined
   would for example return true for &a[5] (which causes some of the
   analyses to stop consider such expressions and fail).  This issue was
   also present before, it only got uncovered by one of the vectorizer
   testcases with the changes in this patch.

-- updates of the alignment analysis in vectorizer; this causes us to
   detect that the initial address of the reference in the second loop
   of no-section-anchors-vect-69.c testcase is in fact aligned on 16
   bytes, so the outcome of the testcase needs to be changed.

I have bootstrapped & regtested the patch on i686, x86_64, ia64 and
ppc-linux, but the test coverage of data dependence analysis is fairly
low; I will definitely also run it through a bootstrap and cpu2000 build with
-ftree-vectorize and -ftree-loop-linear.

Zdenek

	* tree-scalar-evolution.c (resolve_mixers): Exported.
	* tree-scalar-evolution.h (resolve_mixers): Declare.
	* tree-chrec.c (chrec_contains_undetermined): Do not consider NULL_TREE
	to be a special chrec.
	* tree-chrec.h (automatically_generated_chrec_p): Ditto.
	* tree-data-ref.c (object_analysis, ptr_decl_may_alias_p,
	ptr_ptr_may_alias_p, may_alias_p, record_ptr_differ_p,
	record_record_differ_p, record_array_differ_p, array_ptr_differ_p,
	base_object_differ_p, base_addr_differ_p, analyze_array_indexes,
	init_array_ref, init_pointer_ref, analyze_indirect_ref,
	strip_conversion, analyze_offset_expr, address_analysis,
	object_analysis, analyze_offset): Removed.
	(dr_analyze_innermost, dr_analyze_indices, dr_analyze_alias,
	split_constant_offset, canonicalize_base_object_address,
	object_address_invariant_in_loop_p, disjoint_objects_p,
	dr_may_alias_p): New functions.
	(create_data_ref): Use dr_analyze_innermost, dr_analyze_indices
	and dr_analyze_alias.
	(initialize_data_dependence_relation): Use dr_may_alias_p
	and object_address_invariant_in_loop_p.
	(compute_self_dependence): Handle the case when DDR_ARE_DEPENDENT (ddr)
	is chrec_dont_know.
	(find_data_references_in_stmt): Restrict the analysis of data references
	to the given loop nest.
	(find_data_references_in_loop): Made static.  Pass loop nest to
	find_data_references_in_stmt.
	(compute_data_dependences_for_loop): Use DR_VOPS.
	(free_data_ref): Free DR_VOPS.
	* tree-data-ref.h (struct first_location_in_loop): Replaced by ...
	(struct innermost_loop_behavior): ... new.
	(struct base_object_info): Replaced by ...
	(struct indices): ... new.
	(struct dr_alias): New.
	(enum data_ref_type): Removed.
	(struct data_reference): Consist of struct innermost_loop_behavior,
	struct indices and struct dr_alias.
	(DR_SET_ACCESS_FNS, DR_FREE_ACCESS_FNS): Removed.
	(DR_MEMTAG): Renamed to ...
	(DR_SYMBOL_TAG): ... this.
	(find_data_references_in_loop): Declaration removed.
	* tree-vect-analyze.c (vect_compute_data_ref_alignment): Use DR_INIT
	instead of DR_OFFSET_MISALIGNMENT.  DR_ALIGNED_TO is never NULL.
	(vect_analyze_data_refs): Use DR_SYMBOL_TAG instead of DR_MEMTAG.
	* tree-vect-transform.c (vect_create_data_ref_ptr): Ditto.

	* gcc.dg/vect/no-section-anchors-vect-69.c: Fix outcome.

Index: tree-scalar-evolution.c
===================================================================
*** tree-scalar-evolution.c	(revision 124559)
--- tree-scalar-evolution.c	(working copy)
*************** Software Foundation, 51 Franklin Street,
*** 254,260 ****
  #include "params.h"
  
  static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
- static tree resolve_mixers (struct loop *, tree);
  
  /* The cached information about a ssa name VAR, claiming that inside LOOP,
     the value of VAR can be expressed as CHREC.  */
--- 254,259 ----
*************** instantiate_parameters (struct loop *loo
*** 2408,2414 ****
     care about causing overflows, as long as they do not affect value
     of an expression.  */
  
! static tree
  resolve_mixers (struct loop *loop, tree chrec)
  {
    htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
--- 2407,2413 ----
     care about causing overflows, as long as they do not affect value
     of an expression.  */
  
! tree
  resolve_mixers (struct loop *loop, tree chrec)
  {
    htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
Index: tree-scalar-evolution.h
===================================================================
*** tree-scalar-evolution.h	(revision 124559)
--- tree-scalar-evolution.h	(working copy)
*************** extern void scev_reset (void);
*** 31,36 ****
--- 31,37 ----
  extern void scev_finalize (void);
  extern tree analyze_scalar_evolution (struct loop *, tree);
  extern tree instantiate_parameters (struct loop *, tree);
+ extern tree resolve_mixers (struct loop *, tree);
  extern void gather_stats_on_scev_database (void);
  extern void scev_analysis (void);
  unsigned int scev_const_prop (void);
Index: tree-chrec.c
===================================================================
*** tree-chrec.c	(revision 124559)
--- tree-chrec.c	(working copy)
*************** chrec_contains_undetermined (tree chrec)
*** 888,898 ****
  {
    int i, n;
  
!   if (chrec == chrec_dont_know
!       || chrec == chrec_not_analyzed_yet
!       || chrec == NULL_TREE)
      return true;
  
    n = TREE_OPERAND_LENGTH (chrec);
    for (i = 0; i < n; i++)
      if (chrec_contains_undetermined (TREE_OPERAND (chrec, i)))
--- 888,899 ----
  {
    int i, n;
  
!   if (chrec == chrec_dont_know)
      return true;
  
+   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)))
Index: tree-chrec.h
===================================================================
*** tree-chrec.h	(revision 124559)
--- tree-chrec.h	(working copy)
*************** extern GTY(()) tree chrec_known;
*** 36,43 ****
  static inline bool
  automatically_generated_chrec_p (tree chrec)
  {
!   return (chrec == chrec_not_analyzed_yet 
! 	  || chrec == chrec_dont_know
  	  || chrec == chrec_known);
  }
  
--- 36,42 ----
  static inline bool
  automatically_generated_chrec_p (tree chrec)
  {
!   return (chrec == chrec_dont_know
  	  || chrec == chrec_known);
  }
  
Index: testsuite/gcc.dg/vect/no-section-anchors-vect-69.c
===================================================================
*** testsuite/gcc.dg/vect/no-section-anchors-vect-69.c	(revision 124559)
--- testsuite/gcc.dg/vect/no-section-anchors-vect-69.c	(working copy)
*************** int main1 ()
*** 50,56 ****
          abort ();
      }
  
!   /* 2. aligned on 8-bytes */
    for (i = 3; i < N-1; i++)
      {
        tmp1[2].a.n[1][2][i] = 6;
--- 50,56 ----
          abort ();
      }
  
!   /* 2. aligned */
    for (i = 3; i < N-1; i++)
      {
        tmp1[2].a.n[1][2][i] = 6;
*************** int main1 ()
*** 63,69 ****
          abort ();
      }
  
!   /* 3. aligned on 16-bytes */
    for (i = 0; i < N; i++)
      {
        for (j = 0; j < N; j++)
--- 63,69 ----
          abort ();
      }
  
!   /* 3. aligned */
    for (i = 0; i < N; i++)
      {
        for (j = 0; j < N; j++)
*************** int main (void)
*** 113,120 ****
  
  /* { dg-final { scan-tree-dump-times "vectorized 4 loops" 1 "vect" } } */
  /* { dg-final { scan-tree-dump-times "Vectorizing an unaligned access" 0 "vect" } } */
! /* Loops 1,2,4 are unaligned on targets that require 16-byte alignment.
!    Loops 1,4 are unaligned on targets that require 8-byte alignment (ia64). */
! /* { dg-final { scan-tree-dump-times "Alignment of access forced using peeling" 3 "vect" { xfail ia64-*-* } } } */
! /* { dg-final { scan-tree-dump-times "Alignment of access forced using peeling" 2 "vect" { target ia64-*-* } } } */
  /* { dg-final { cleanup-tree-dump "vect" } } */
--- 113,117 ----
  
  /* { dg-final { scan-tree-dump-times "vectorized 4 loops" 1 "vect" } } */
  /* { dg-final { scan-tree-dump-times "Vectorizing an unaligned access" 0 "vect" } } */
! /* { dg-final { scan-tree-dump-times "Alignment of access forced using peeling" 2 "vect" } } */
  /* { dg-final { cleanup-tree-dump "vect" } } */
Index: tree-data-ref.c
===================================================================
*** tree-data-ref.c	(revision 124559)
--- tree-data-ref.c	(working copy)
*************** static struct datadep_stats
*** 122,584 ****
    int num_miv_unimplemented;
  } dependence_stats;
  
- static tree object_analysis (tree, tree, bool, struct data_reference **, 
- 			     tree *, tree *, tree *, tree *, tree *,
- 			     struct ptr_info_def **, subvar_t *);
  static bool subscript_dependence_tester_1 (struct data_dependence_relation *,
  					   struct data_reference *,
  					   struct data_reference *);
- 
- /* Determine if PTR and DECL may alias, the result is put in ALIASED.
-    Return FALSE if there is no symbol memory tag for PTR.  */
- 
- static bool
- ptr_decl_may_alias_p (tree ptr, tree decl, 
- 		      struct data_reference *ptr_dr, 
- 		      bool *aliased)
- {
-   tree tag = NULL_TREE;
-   struct ptr_info_def *pi = DR_PTR_INFO (ptr_dr);  
- 
-   gcc_assert (TREE_CODE (ptr) == SSA_NAME && DECL_P (decl));
- 
-   if (pi)
-     tag = pi->name_mem_tag;
-   if (!tag)
-     tag = symbol_mem_tag (SSA_NAME_VAR (ptr));
-   if (!tag)
-     tag = DR_MEMTAG (ptr_dr);
-   if (!tag)
-     return false;
-    
-   *aliased = is_aliased_with (tag, decl);      
-   return true;
- }
- 
- 
- /* Determine if two pointers may alias, the result is put in ALIASED.
-    Return FALSE if there is no symbol memory tag for one of the pointers.  */
- 
- static bool
- ptr_ptr_may_alias_p (tree ptr_a, tree ptr_b, 
- 		     struct data_reference *dra, 
- 		     struct data_reference *drb, 
- 		     bool *aliased)
- {  
-   tree tag_a = NULL_TREE, tag_b = NULL_TREE;
-   struct ptr_info_def *pi_a = DR_PTR_INFO (dra);  
-   struct ptr_info_def *pi_b = DR_PTR_INFO (drb);  
-   bitmap bal1, bal2;
- 
-   if (pi_a && pi_a->name_mem_tag && pi_b && pi_b->name_mem_tag)
-     {
-       tag_a = pi_a->name_mem_tag;
-       tag_b = pi_b->name_mem_tag;
-     }
-   else
-     {
-       tag_a = symbol_mem_tag (SSA_NAME_VAR (ptr_a));
-       if (!tag_a)
- 	tag_a = DR_MEMTAG (dra);
-       if (!tag_a)
- 	return false;
-       
-       tag_b = symbol_mem_tag (SSA_NAME_VAR (ptr_b));
-       if (!tag_b)
- 	tag_b = DR_MEMTAG (drb);
-       if (!tag_b)
- 	return false;
-     }
-   bal1 = BITMAP_ALLOC (NULL);
-   bitmap_set_bit (bal1, DECL_UID (tag_a));
-   if (MTAG_P (tag_a) && MTAG_ALIASES (tag_a))
-     bitmap_ior_into (bal1, MTAG_ALIASES (tag_a));
- 
-   bal2 = BITMAP_ALLOC (NULL);
-   bitmap_set_bit (bal2, DECL_UID (tag_b));
-   if (MTAG_P (tag_b) && MTAG_ALIASES (tag_b))
-     bitmap_ior_into (bal2, MTAG_ALIASES (tag_b));
-   *aliased = bitmap_intersect_p (bal1, bal2);
- 
-   BITMAP_FREE (bal1);
-   BITMAP_FREE (bal2);
-   return true;
- }
- 
- 
- /* Determine if BASE_A and BASE_B may alias, the result is put in ALIASED.
-    Return FALSE if there is no symbol memory tag for one of the symbols.  */
- 
- static bool
- may_alias_p (tree base_a, tree base_b,
- 	     struct data_reference *dra,
- 	     struct data_reference *drb,
- 	     bool *aliased)
- {
-   if (TREE_CODE (base_a) == ADDR_EXPR || TREE_CODE (base_b) == ADDR_EXPR)
-     {
-       if (TREE_CODE (base_a) == ADDR_EXPR && TREE_CODE (base_b) == ADDR_EXPR)
- 	{
- 	 *aliased = (TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0));
- 	 return true;
- 	}
-       if (TREE_CODE (base_a) == ADDR_EXPR)
- 	return ptr_decl_may_alias_p (base_b, TREE_OPERAND (base_a, 0), drb, 
- 				     aliased);
-       else
- 	return ptr_decl_may_alias_p (base_a, TREE_OPERAND (base_b, 0), dra, 
- 				     aliased);
-     }
- 
-   return ptr_ptr_may_alias_p (base_a, base_b, dra, drb, aliased);
- }
- 
- 
- /* Determine if a pointer (BASE_A) and a record/union access (BASE_B)
-    are not aliased. Return TRUE if they differ.  */
- static bool
- record_ptr_differ_p (struct data_reference *dra,
- 		     struct data_reference *drb)
- {
-   bool aliased;
-   tree base_a = DR_BASE_OBJECT (dra);
-   tree base_b = DR_BASE_OBJECT (drb);
- 
-   if (TREE_CODE (base_b) != COMPONENT_REF)
-     return false;
- 
-   /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs.
-      For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b.  
-      Probably will be unnecessary with struct alias analysis.  */
-   while (TREE_CODE (base_b) == COMPONENT_REF)
-      base_b = TREE_OPERAND (base_b, 0);
-   /* Compare a record/union access (b.c[i] or p->c[i]) and a pointer
-      ((*q)[i]).  */
-   if (TREE_CODE (base_a) == INDIRECT_REF
-       && ((TREE_CODE (base_b) == VAR_DECL
- 	   && (ptr_decl_may_alias_p (TREE_OPERAND (base_a, 0), base_b, dra, 
- 				     &aliased)
- 	       && !aliased))
- 	  || (TREE_CODE (base_b) == INDIRECT_REF
- 	      && (ptr_ptr_may_alias_p (TREE_OPERAND (base_a, 0), 
- 				       TREE_OPERAND (base_b, 0), dra, drb, 
- 				       &aliased)
- 		  && !aliased))))
-     return true;
-   else
-     return false;
- }
- 
- /* Determine if two record/union accesses are aliased. Return TRUE if they 
-    differ.  */
- static bool
- record_record_differ_p (struct data_reference *dra,
- 			struct data_reference *drb)
- {
-   bool aliased;
-   tree base_a = DR_BASE_OBJECT (dra);
-   tree base_b = DR_BASE_OBJECT (drb);
- 
-   if (TREE_CODE (base_b) != COMPONENT_REF 
-       || TREE_CODE (base_a) != COMPONENT_REF)
-     return false;
- 
-   /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs.
-      For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b.  
-      Probably will be unnecessary with struct alias analysis.  */
-   while (TREE_CODE (base_b) == COMPONENT_REF)
-     base_b = TREE_OPERAND (base_b, 0);
-   while (TREE_CODE (base_a) == COMPONENT_REF)
-     base_a = TREE_OPERAND (base_a, 0);
- 
-   if (TREE_CODE (base_a) == INDIRECT_REF
-       && TREE_CODE (base_b) == INDIRECT_REF
-       && ptr_ptr_may_alias_p (TREE_OPERAND (base_a, 0), 
- 			      TREE_OPERAND (base_b, 0), 
- 			      dra, drb, &aliased)
-       && !aliased)
-     return true;
-   else
-     return false;
- }
-     
- /* Determine if an array access (BASE_A) and a record/union access (BASE_B)
-    are not aliased. Return TRUE if they differ.  */
- static bool
- record_array_differ_p (struct data_reference *dra,
- 		       struct data_reference *drb)
- {  
-   bool aliased;
-   tree base_a = DR_BASE_OBJECT (dra);
-   tree base_b = DR_BASE_OBJECT (drb);
- 
-   if (TREE_CODE (base_b) != COMPONENT_REF)
-     return false;
- 
-   /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs.
-      For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b.  
-      Probably will be unnecessary with struct alias analysis.  */
-   while (TREE_CODE (base_b) == COMPONENT_REF)
-      base_b = TREE_OPERAND (base_b, 0);
- 
-   /* Compare a record/union access (b.c[i] or p->c[i]) and an array access 
-      (a[i]). In case of p->c[i] use alias analysis to verify that p is not
-      pointing to a.  */
-   if (TREE_CODE (base_a) == VAR_DECL
-       && (TREE_CODE (base_b) == VAR_DECL
- 	  || (TREE_CODE (base_b) == INDIRECT_REF
- 	      && (ptr_decl_may_alias_p (TREE_OPERAND (base_b, 0), base_a, drb, 
- 					&aliased)
- 		  && !aliased))))
-     return true;
-   else
-     return false;
- }
- 
- 
- /* Determine if an array access (BASE_A) and a pointer (BASE_B)
-    are not aliased. Return TRUE if they differ.  */
- static bool
- array_ptr_differ_p (tree base_a, tree base_b, 	     
- 		    struct data_reference *drb)
- {  
-   bool aliased;
- 
-   /* In case one of the bases is a pointer (a[i] and (*p)[i]), we check with the
-      help of alias analysis that p is not pointing to a.  */
-   if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == INDIRECT_REF 
-       && (ptr_decl_may_alias_p (TREE_OPERAND (base_b, 0), base_a, drb, &aliased)
- 	  && !aliased))
-     return true;
-   else
-     return false;
- }
- 
- 
- /* This is the simplest data dependence test: determines whether the
-    data references A and B access the same array/region.  Returns
-    false when the property is not computable at compile time.
-    Otherwise return true, and DIFFER_P will record the result. This
-    utility will not be necessary when alias_sets_conflict_p will be
-    less conservative.  */
- 
- static bool
- base_object_differ_p (struct data_reference *a,
- 		      struct data_reference *b,
- 		      bool *differ_p)
- {
-   tree base_a = DR_BASE_OBJECT (a);
-   tree base_b = DR_BASE_OBJECT (b);
-   bool aliased;
- 
-   if (!base_a || !base_b)
-     return false;
- 
-   /* Determine if same base.  Example: for the array accesses
-      a[i], b[i] or pointer accesses *a, *b, bases are a, b.  */
-   if (base_a == base_b)
-     {
-       *differ_p = false;
-       return true;
-     }
- 
-   /* For pointer based accesses, (*p)[i], (*q)[j], the bases are (*p)
-      and (*q)  */
-   if (TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == INDIRECT_REF
-       && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0))
-     {
-       *differ_p = false;
-       return true;
-     }
- 
-   /* Record/union based accesses - s.a[i], t.b[j]. bases are s.a,t.b.  */ 
-   if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF
-       && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0)
-       && TREE_OPERAND (base_a, 1) == TREE_OPERAND (base_b, 1))
-     {
-       *differ_p = false;
-       return true;
-     }
- 
- 
-   /* Determine if different bases.  */
- 
-   /* At this point we know that base_a != base_b.  However, pointer
-      accesses of the form x=(*p) and y=(*q), whose bases are p and q,
-      may still be pointing to the same base. In SSAed GIMPLE p and q will
-      be SSA_NAMES in this case.  Therefore, here we check if they are
-      really two different declarations.  */
-   if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == VAR_DECL)
-     {
-       *differ_p = true;
-       return true;
-     }
- 
-   /* In case one of the bases is a pointer (a[i] and (*p)[i]), we check with the
-      help of alias analysis that p is not pointing to a.  */
-   if (array_ptr_differ_p (base_a, base_b, b) 
-       || array_ptr_differ_p (base_b, base_a, a))
-     {
-       *differ_p = true;
-       return true;
-     }
- 
-   /* If the bases are pointers ((*q)[i] and (*p)[i]), we check with the
-      help of alias analysis they don't point to the same bases.  */
-   if (TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == INDIRECT_REF 
-       && (may_alias_p (TREE_OPERAND (base_a, 0), TREE_OPERAND (base_b, 0), a, b, 
- 		       &aliased)
- 	  && !aliased))
-     {
-       *differ_p = true;
-       return true;
-     }
- 
-   /* Compare two record/union bases s.a and t.b: s != t or (a != b and
-      s and t are not unions).  */
-   if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF
-       && ((TREE_CODE (TREE_OPERAND (base_a, 0)) == VAR_DECL
-            && TREE_CODE (TREE_OPERAND (base_b, 0)) == VAR_DECL
-            && TREE_OPERAND (base_a, 0) != TREE_OPERAND (base_b, 0))
-           || (TREE_CODE (TREE_TYPE (TREE_OPERAND (base_a, 0))) == RECORD_TYPE 
-               && TREE_CODE (TREE_TYPE (TREE_OPERAND (base_b, 0))) == RECORD_TYPE
-               && TREE_OPERAND (base_a, 1) != TREE_OPERAND (base_b, 1))))
-     {
-       *differ_p = true;
-       return true;
-     }
- 
-   /* Compare a record/union access (b.c[i] or p->c[i]) and a pointer
-      ((*q)[i]).  */
-   if (record_ptr_differ_p (a, b) || record_ptr_differ_p (b, a))
-     {
-       *differ_p = true;
-       return true;
-     }
- 
-   /* Compare a record/union access (b.c[i] or p->c[i]) and an array access 
-      (a[i]). In case of p->c[i] use alias analysis to verify that p is not
-      pointing to a.  */
-   if (record_array_differ_p (a, b) || record_array_differ_p (b, a))
-     {
-       *differ_p = true;
-       return true;
-     }
- 
-   /* Compare two record/union accesses (b.c[i] or p->c[i]).  */
-   if (record_record_differ_p (a, b))
-     {
-       *differ_p = true;
-       return true;
-     }
- 
-   return false;
- }
- 
- /* Function base_addr_differ_p.
- 
-    This is the simplest data dependence test: determines whether the
-    data references DRA and DRB access the same array/region.  Returns
-    false when the property is not computable at compile time.
-    Otherwise return true, and DIFFER_P will record the result.
- 
-    The algorithm:   
-    1. if (both DRA and DRB are represented as arrays)
-           compare DRA.BASE_OBJECT and DRB.BASE_OBJECT
-    2. else if (both DRA and DRB are represented as pointers)
-           try to prove that DRA.FIRST_LOCATION == DRB.FIRST_LOCATION
-    3. else if (DRA and DRB are represented differently or 2. fails)
-           only try to prove that the bases are surely different
- */
- 
- static bool
- base_addr_differ_p (struct data_reference *dra,
- 		    struct data_reference *drb,
- 		    bool *differ_p)
- {
-   tree addr_a = DR_BASE_ADDRESS (dra);
-   tree addr_b = DR_BASE_ADDRESS (drb);
-   tree type_a, type_b;
-   tree decl_a, decl_b;
-   bool aliased;
- 
-   if (!addr_a || !addr_b)
-     return false;
- 
-   type_a = TREE_TYPE (addr_a);
-   type_b = TREE_TYPE (addr_b);
- 
-   gcc_assert (POINTER_TYPE_P (type_a) &&  POINTER_TYPE_P (type_b));
- 
-   /* 1. if (both DRA and DRB are represented as arrays)
-             compare DRA.BASE_OBJECT and DRB.BASE_OBJECT.  */
-   if (DR_TYPE (dra) == ARRAY_REF_TYPE && DR_TYPE (drb) == ARRAY_REF_TYPE)
-     return base_object_differ_p (dra, drb, differ_p);
- 
-   /* 2. else if (both DRA and DRB are represented as pointers)
- 	    try to prove that DRA.FIRST_LOCATION == DRB.FIRST_LOCATION.  */
-   /* If base addresses are the same, we check the offsets, since the access of 
-      the data-ref is described by {base addr + offset} and its access function,
-      i.e., in order to decide whether the bases of data-refs are the same we 
-      compare both base addresses and offsets.  */
-   if (DR_TYPE (dra) == POINTER_REF_TYPE && DR_TYPE (drb) == POINTER_REF_TYPE
-       && (addr_a == addr_b 
- 	  || (TREE_CODE (addr_a) == ADDR_EXPR && TREE_CODE (addr_b) == ADDR_EXPR
- 	      && TREE_OPERAND (addr_a, 0) == TREE_OPERAND (addr_b, 0))))
-     {
-       /* Compare offsets.  */
-       tree offset_a = DR_OFFSET (dra); 
-       tree offset_b = DR_OFFSET (drb);
-       
-       STRIP_NOPS (offset_a);
-       STRIP_NOPS (offset_b);
- 
-       /* FORNOW: we only compare offsets that are MULT_EXPR, i.e., we don't handle
- 	 PLUS_EXPR.  */
-       if (offset_a == offset_b
- 	  || (TREE_CODE (offset_a) == MULT_EXPR 
- 	      && TREE_CODE (offset_b) == MULT_EXPR
- 	      && TREE_OPERAND (offset_a, 0) == TREE_OPERAND (offset_b, 0)
- 	      && TREE_OPERAND (offset_a, 1) == TREE_OPERAND (offset_b, 1)))
- 	{
- 	  *differ_p = false;
- 	  return true;
- 	}
-     }
- 
-   /*  3. else if (DRA and DRB are represented differently or 2. fails) 
-               only try to prove that the bases are surely different.  */
- 
-   /* Apply alias analysis.  */
-   if (may_alias_p (addr_a, addr_b, dra, drb, &aliased) && !aliased)
-     {
-       *differ_p = true;
-       return true;
-     }
-   
-   /* An instruction writing through a restricted pointer is "independent" of any 
-      instruction reading or writing through a different restricted pointer, 
-      in the same block/scope.  */
-   else if (TYPE_RESTRICT (type_a)
- 	   &&  TYPE_RESTRICT (type_b) 
- 	   && (!DR_IS_READ (drb) || !DR_IS_READ (dra))
- 	   && TREE_CODE (DR_BASE_ADDRESS (dra)) == SSA_NAME
- 	   && (decl_a = SSA_NAME_VAR (DR_BASE_ADDRESS (dra)))
- 	   && TREE_CODE (decl_a) == PARM_DECL
- 	   && TREE_CODE (DECL_CONTEXT (decl_a)) == FUNCTION_DECL
- 	   && TREE_CODE (DR_BASE_ADDRESS (drb)) == SSA_NAME
- 	   && (decl_b = SSA_NAME_VAR (DR_BASE_ADDRESS (drb)))
- 	   && TREE_CODE (decl_b) == PARM_DECL
- 	   && TREE_CODE (DECL_CONTEXT (decl_b)) == FUNCTION_DECL
- 	   && DECL_CONTEXT (decl_a) == DECL_CONTEXT (decl_b)) 
-     {
-       *differ_p = true;
-       return true;
-     }
- 
-   return false;
- }
- 
  /* Returns true iff A divides B.  */
  
  static inline bool 
--- 122,130 ----
*************** dump_dist_dir_vectors (FILE *file, VEC (
*** 913,2063 ****
  	    fprintf (file, "DISTANCE_V (");
  	    print_lambda_vector (file, v, DDR_NB_LOOPS (ddr));
  	    fprintf (file, ")\n");
! 	  }
! 
! 	for (j = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), j, v); j++)
! 	  {
! 	    fprintf (file, "DIRECTION_V (");
! 	    print_direction_vector (file, v, DDR_NB_LOOPS (ddr));
! 	    fprintf (file, ")\n");
! 	  }
!       }
! 
!   fprintf (file, "\n\n");
! }
! 
! /* Dumps the data dependence relations DDRS in FILE.  */
! 
! void 
! dump_ddrs (FILE *file, VEC (ddr_p, heap) *ddrs)
! {
!   unsigned int i;
!   struct data_dependence_relation *ddr;
! 
!   for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
!     dump_data_dependence_relation (file, ddr);
! 
!   fprintf (file, "\n\n");
! }
! 
! 
! 
! /* Given an ARRAY_REF node REF, records its access functions.
!    Example: given A[i][3], record in ACCESS_FNS the opnd1 function,
!    i.e. the constant "3", then recursively call the function on opnd0,
!    i.e. the ARRAY_REF "A[i]".  
!    The function returns the base name: "A".  */
! 
! static tree
! analyze_array_indexes (struct loop *loop,
! 		       VEC(tree,heap) **access_fns, 
! 		       tree ref, tree stmt)
! {
!   tree opnd0, opnd1;
!   tree access_fn;
! 
!   opnd0 = TREE_OPERAND (ref, 0);
!   opnd1 = TREE_OPERAND (ref, 1);
! 
!   /* The detection of the evolution function for this data access is
!      postponed until the dependence test.  This lazy strategy avoids
!      the computation of access functions that are of no interest for
!      the optimizers.  */
!   access_fn = instantiate_parameters
!     (loop, analyze_scalar_evolution (loop, opnd1));
! 
!   VEC_safe_push (tree, heap, *access_fns, access_fn);
!   
!   /* Recursively record other array access functions.  */
!   if (TREE_CODE (opnd0) == ARRAY_REF)
!     return analyze_array_indexes (loop, access_fns, opnd0, stmt);
! 
!   /* Return the base name of the data access.  */
!   else
!     return opnd0;
! }
! 
! /* For a data reference REF contained in the statement STMT, initialize
!    a DATA_REFERENCE structure, and return it.  IS_READ flag has to be
!    set to true when REF is in the right hand side of an
!    assignment.  */
! 
! static struct data_reference *
! init_array_ref (tree stmt, tree ref, bool is_read)
! {
!   struct loop *loop = loop_containing_stmt (stmt);
!   VEC(tree,heap) *acc_fns = VEC_alloc (tree, heap, 3);
!   struct data_reference *res = XNEW (struct data_reference);;
! 
!   if (dump_file && (dump_flags & TDF_DETAILS))
!     {
!       fprintf (dump_file, "(init_array_ref \n");
!       fprintf (dump_file, "  (ref = ");
!       print_generic_stmt (dump_file, ref, 0);
!       fprintf (dump_file, ")\n");
!     }
! 
!   DR_STMT (res) = stmt;
!   DR_REF (res) = ref;
!   DR_BASE_OBJECT (res) = analyze_array_indexes (loop, &acc_fns, ref, stmt);
!   DR_TYPE (res) = ARRAY_REF_TYPE;
!   DR_SET_ACCESS_FNS (res, acc_fns);
!   DR_IS_READ (res) = is_read;
!   DR_BASE_ADDRESS (res) = NULL_TREE;
!   DR_OFFSET (res) = NULL_TREE;
!   DR_INIT (res) = NULL_TREE;
!   DR_STEP (res) = NULL_TREE;
!   DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
!   DR_MEMTAG (res) = NULL_TREE;
!   DR_PTR_INFO (res) = NULL;
! 
!   if (dump_file && (dump_flags & TDF_DETAILS))
!     fprintf (dump_file, ")\n");
! 
!   return res;
! }
! 
! /* For a data reference REF contained in the statement STMT, initialize
!    a DATA_REFERENCE structure, and return it.  */
! 
! static struct data_reference *
! init_pointer_ref (tree stmt, tree ref, tree access_fn, bool is_read,
! 		  tree base_address, tree step, struct ptr_info_def *ptr_info)
! {
!   struct data_reference *res = XNEW (struct data_reference);
!   VEC(tree,heap) *acc_fns = VEC_alloc (tree, heap, 3);
! 
!   if (dump_file && (dump_flags & TDF_DETAILS))
!     {
!       fprintf (dump_file, "(init_pointer_ref \n");
!       fprintf (dump_file, "  (ref = ");
!       print_generic_stmt (dump_file, ref, 0);
!       fprintf (dump_file, ")\n");
!     }
! 
!   DR_STMT (res) = stmt;
!   DR_REF (res) = ref;
!   DR_BASE_OBJECT (res) = NULL_TREE;
!   DR_TYPE (res) = POINTER_REF_TYPE;
!   DR_SET_ACCESS_FNS (res, acc_fns);
!   VEC_quick_push (tree, DR_ACCESS_FNS (res), access_fn);
!   DR_IS_READ (res) = is_read;
!   DR_BASE_ADDRESS (res) = base_address;
!   DR_OFFSET (res) = NULL_TREE;
!   DR_INIT (res) = NULL_TREE;
!   DR_STEP (res) = step;
!   DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
!   DR_MEMTAG (res) = NULL_TREE;
!   DR_PTR_INFO (res) = ptr_info;
! 
!   if (dump_file && (dump_flags & TDF_DETAILS))
!     fprintf (dump_file, ")\n");
! 
!   return res;
! }
! 
! /* Analyze an indirect memory reference, REF, that comes from STMT.
!    IS_READ is true if this is an indirect load, and false if it is
!    an indirect store.
!    Return a new data reference structure representing the indirect_ref, or
!    NULL if we cannot describe the access function.  */
! 
! static struct data_reference *
! analyze_indirect_ref (tree stmt, tree ref, bool is_read)
! {
!   struct loop *loop = loop_containing_stmt (stmt);
!   tree ptr_ref = TREE_OPERAND (ref, 0);
!   tree access_fn = analyze_scalar_evolution (loop, ptr_ref);
!   tree init = initial_condition_in_loop_num (access_fn, loop->num);
!   tree base_address = NULL_TREE, evolution, step = NULL_TREE;
!   struct ptr_info_def *ptr_info = NULL;
! 
!   if (TREE_CODE (ptr_ref) == SSA_NAME)
!     ptr_info = SSA_NAME_PTR_INFO (ptr_ref);
! 
!   STRIP_NOPS (init);
!   if (access_fn == chrec_dont_know || !init || init == chrec_dont_know)
!     {
!       if (dump_file && (dump_flags & TDF_DETAILS))
! 	{
! 	  fprintf (dump_file, "\nBad access function of ptr: ");
! 	  print_generic_expr (dump_file, ref, TDF_SLIM);
! 	  fprintf (dump_file, "\n");
! 	}
!       return NULL;
!     }
! 
!   if (dump_file && (dump_flags & TDF_DETAILS))
!     {
!       fprintf (dump_file, "\nAccess function of ptr: ");
!       print_generic_expr (dump_file, access_fn, TDF_SLIM);
!       fprintf (dump_file, "\n");
!     }
! 
!   if (!expr_invariant_in_loop_p (loop, init))
!     {
!       if (dump_file && (dump_flags & TDF_DETAILS))
! 	fprintf (dump_file, "\ninitial condition is not loop invariant.\n");	
!     }
!   else
!     {
!       base_address = init;
!       evolution = evolution_part_in_loop_num (access_fn, loop->num);
!       if (evolution != chrec_dont_know)
! 	{       
! 	  if (!evolution)
! 	    step = ssize_int (0);
! 	  else  
! 	    {
! 	      if (TREE_CODE (evolution) == INTEGER_CST)
! 		step = fold_convert (ssizetype, evolution);
! 	      else
! 		if (dump_file && (dump_flags & TDF_DETAILS))
! 		  fprintf (dump_file, "\nnon constant step for ptr access.\n");	
! 	    }
! 	}
!       else
! 	if (dump_file && (dump_flags & TDF_DETAILS))
! 	  fprintf (dump_file, "\nunknown evolution of ptr.\n");	
!     }
!   return init_pointer_ref (stmt, ref, access_fn, is_read, base_address, 
! 			   step, ptr_info);
! }
! 
! /* Function strip_conversions
! 
!    Strip conversions that don't narrow the mode.  */
! 
! static tree 
! strip_conversion (tree expr)
! {
!   tree to, ti, oprnd0;
!   
!   while (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR)
!     {
!       to = TREE_TYPE (expr);
!       oprnd0 = TREE_OPERAND (expr, 0);
!       ti = TREE_TYPE (oprnd0);
!  
!       if (!INTEGRAL_TYPE_P (to) || !INTEGRAL_TYPE_P (ti))
! 	return NULL_TREE;
!       if (GET_MODE_SIZE (TYPE_MODE (to)) < GET_MODE_SIZE (TYPE_MODE (ti)))
! 	return NULL_TREE;
!       
!       expr = oprnd0;
!     }
!   return expr; 
! }
! 
! 
! /* Function analyze_offset_expr
! 
!    Given an offset expression EXPR received from get_inner_reference, analyze
!    it and create an expression for INITIAL_OFFSET by substituting the variables 
!    of EXPR with initial_condition of the corresponding access_fn in the loop. 
!    E.g., 
!       for i
!          for (j = 3; j < N; j++)
!             a[j].b[i][j] = 0;
! 	 
!    For a[j].b[i][j], EXPR will be 'i * C_i + j * C_j + C'. 'i' cannot be 
!    substituted, since its access_fn in the inner loop is i. 'j' will be 
!    substituted with 3. An INITIAL_OFFSET will be 'i * C_i + C`', where
!    C` =  3 * C_j + C.
! 
!    Compute MISALIGN (the misalignment of the data reference initial access from
!    its base). Misalignment can be calculated only if all the variables can be 
!    substituted with constants, otherwise, we record maximum possible alignment
!    in ALIGNED_TO. In the above example, since 'i' cannot be substituted, MISALIGN 
!    will be NULL_TREE, and the biggest divider of C_i (a power of 2) will be 
!    recorded in ALIGNED_TO.
! 
!    STEP is an evolution of the data reference in this loop in bytes.
!    In the above example, STEP is C_j.
! 
!    Return FALSE, if the analysis fails, e.g., there is no access_fn for a 
!    variable. In this case, all the outputs (INITIAL_OFFSET, MISALIGN, ALIGNED_TO
!    and STEP) are NULL_TREEs. Otherwise, return TRUE.
! 
! */
! 
! static bool
! analyze_offset_expr (tree expr, 
! 		     struct loop *loop, 
! 		     tree *initial_offset,
! 		     tree *misalign,
! 		     tree *aligned_to,
! 		     tree *step)
! {
!   tree oprnd0;
!   tree oprnd1;
!   tree left_offset = ssize_int (0);
!   tree right_offset = ssize_int (0);
!   tree left_misalign = ssize_int (0);
!   tree right_misalign = ssize_int (0);
!   tree left_step = ssize_int (0);
!   tree right_step = ssize_int (0);
!   enum tree_code code;
!   tree init, evolution;
!   tree left_aligned_to = NULL_TREE, right_aligned_to = NULL_TREE;
! 
!   *step = NULL_TREE;
!   *misalign = NULL_TREE;
!   *aligned_to = NULL_TREE;  
!   *initial_offset = NULL_TREE;
! 
!   /* Strip conversions that don't narrow the mode.  */
!   expr = strip_conversion (expr);
!   if (!expr)
!     return false;
! 
!   /* Stop conditions:
!      1. Constant.  */
!   if (TREE_CODE (expr) == INTEGER_CST)
!     {
!       *initial_offset = fold_convert (ssizetype, expr);
!       *misalign = fold_convert (ssizetype, expr);      
!       *step = ssize_int (0);
!       return true;
!     }
! 
!   /* 2. Variable. Try to substitute with initial_condition of the corresponding
!      access_fn in the current loop.  */
!   if (SSA_VAR_P (expr))
!     {
!       tree access_fn = analyze_scalar_evolution (loop, expr);
! 
!       if (access_fn == chrec_dont_know)
! 	/* No access_fn.  */
! 	return false;
! 
!       init = initial_condition_in_loop_num (access_fn, loop->num);
!       if (!expr_invariant_in_loop_p (loop, init))
! 	/* Not enough information: may be not loop invariant.  
! 	   E.g., for a[b[i]], we get a[D], where D=b[i]. EXPR is D, its 
! 	   initial_condition is D, but it depends on i - loop's induction
! 	   variable.  */	  
! 	return false;
! 
!       evolution = evolution_part_in_loop_num (access_fn, loop->num);
!       if (evolution && TREE_CODE (evolution) != INTEGER_CST)
! 	/* Evolution is not constant.  */
! 	return false;
! 
!       if (TREE_CODE (init) == INTEGER_CST)
! 	*misalign = fold_convert (ssizetype, init);
!       else
! 	/* Not constant, misalignment cannot be calculated.  */
! 	*misalign = NULL_TREE;
! 
!       *initial_offset = fold_convert (ssizetype, init); 
! 
!       *step = evolution ? fold_convert (ssizetype, evolution) : ssize_int (0);
!       return true;      
!     }
! 
!   /* Recursive computation.  */
!   if (!BINARY_CLASS_P (expr))
!     {
!       /* We expect to get binary expressions (PLUS/MINUS and MULT).  */
!       if (dump_file && (dump_flags & TDF_DETAILS))
!         {
! 	  fprintf (dump_file, "\nNot binary expression ");
!           print_generic_expr (dump_file, expr, TDF_SLIM);
! 	  fprintf (dump_file, "\n");
! 	}
!       return false;
!     }
!   oprnd0 = TREE_OPERAND (expr, 0);
!   oprnd1 = TREE_OPERAND (expr, 1);
! 
!   if (!analyze_offset_expr (oprnd0, loop, &left_offset, &left_misalign, 
! 			    &left_aligned_to, &left_step)
!       || !analyze_offset_expr (oprnd1, loop, &right_offset, &right_misalign, 
! 			       &right_aligned_to, &right_step))
!     return false;
! 
!   /* The type of the operation: plus, minus or mult.  */
!   code = TREE_CODE (expr);
!   switch (code)
!     {
!     case MULT_EXPR:
!       if (TREE_CODE (right_offset) != INTEGER_CST)
! 	/* RIGHT_OFFSET can be not constant. For example, for arrays of variable 
! 	   sized types. 
! 	   FORNOW: We don't support such cases.  */
! 	return false;
! 
!       /* Strip conversions that don't narrow the mode.  */
!       left_offset = strip_conversion (left_offset);      
!       if (!left_offset)
! 	return false;      
!       /* Misalignment computation.  */
!       if (SSA_VAR_P (left_offset))
! 	{
! 	  /* If the left side contains variables that can't be substituted with 
! 	     constants, the misalignment is unknown. However, if the right side 
! 	     is a multiple of some alignment, we know that the expression is
! 	     aligned to it. Therefore, we record such maximum possible value.
! 	   */
! 	  *misalign = NULL_TREE;
! 	  *aligned_to = ssize_int (highest_pow2_factor (right_offset));
! 	}
!       else 
! 	{
! 	  /* The left operand was successfully substituted with constant.  */	  
! 	  if (left_misalign)
! 	    {
! 	      /* In case of EXPR '(i * C1 + j) * C2', LEFT_MISALIGN is 
! 		 NULL_TREE.  */
! 	      *misalign  = size_binop (code, left_misalign, right_misalign);
! 	      if (left_aligned_to && right_aligned_to)
! 		*aligned_to = size_binop (MIN_EXPR, left_aligned_to, 
! 					  right_aligned_to);
! 	      else 
! 		*aligned_to = left_aligned_to ? 
! 		  left_aligned_to : right_aligned_to;
! 	    }
! 	  else
! 	    *misalign = NULL_TREE; 
! 	}
! 
!       /* Step calculation.  */
!       /* Multiply the step by the right operand.  */
!       *step  = size_binop (MULT_EXPR, left_step, right_offset);
!       break;
!    
!     case PLUS_EXPR:
!     case MINUS_EXPR:
!       /* Combine the recursive calculations for step and misalignment.  */
!       *step = size_binop (code, left_step, right_step);
! 
!       /* Unknown alignment.  */
!       if ((!left_misalign && !left_aligned_to)
! 	  || (!right_misalign && !right_aligned_to))
! 	{
! 	  *misalign = NULL_TREE;
! 	  *aligned_to = NULL_TREE;
! 	  break;
! 	}
! 
!       if (left_misalign && right_misalign)
! 	*misalign = size_binop (code, left_misalign, right_misalign);
!       else
! 	*misalign = left_misalign ? left_misalign : right_misalign;
! 
!       if (left_aligned_to && right_aligned_to)
! 	*aligned_to = size_binop (MIN_EXPR, left_aligned_to, right_aligned_to);
!       else 
! 	*aligned_to = left_aligned_to ? left_aligned_to : right_aligned_to;
! 
!       break;
! 
!     default:
!       gcc_unreachable ();
!     }
! 
!   /* Compute offset.  */
!   *initial_offset = fold_convert (ssizetype, 
! 				  fold_build2 (code, TREE_TYPE (left_offset), 
! 					       left_offset, 
! 					       right_offset));
!   return true;
! }
! 
! /* Function address_analysis
! 
!    Return the BASE of the address expression EXPR.
!    Also compute the OFFSET from BASE, MISALIGN and STEP.
! 
!    Input:
!    EXPR - the address expression that is being analyzed
!    STMT - the statement that contains EXPR or its original memory reference
!    IS_READ - TRUE if STMT reads from EXPR, FALSE if writes to EXPR
!    DR - data_reference struct for the original memory reference
! 
!    Output:
!    BASE (returned value) - the base of the data reference EXPR.
!    INITIAL_OFFSET - initial offset of EXPR from BASE (an expression)
!    MISALIGN - offset of EXPR from BASE in bytes (a constant) or NULL_TREE if the
!               computation is impossible 
!    ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be 
!                 calculated (doesn't depend on variables)
!    STEP - evolution of EXPR in the loop
!  
!    If something unexpected is encountered (an unsupported form of data-ref),
!    then NULL_TREE is returned.  
!  */
! 
! static tree
! address_analysis (tree expr, tree stmt, bool is_read, struct data_reference *dr, 
! 		  tree *offset, tree *misalign, tree *aligned_to, tree *step)
! {
!   tree oprnd0, oprnd1, base_address, offset_expr, base_addr0, base_addr1;
!   tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
!   tree dummy, address_aligned_to = NULL_TREE;
!   struct ptr_info_def *dummy1;
!   subvar_t dummy2;
! 
!   switch (TREE_CODE (expr))
!     {
!     case PLUS_EXPR:
!     case MINUS_EXPR:
!       /* EXPR is of form {base +/- offset} (or {offset +/- base}).  */
!       oprnd0 = TREE_OPERAND (expr, 0);
!       oprnd1 = TREE_OPERAND (expr, 1);
! 
!       STRIP_NOPS (oprnd0);
!       STRIP_NOPS (oprnd1);
!       
!       /* Recursively try to find the base of the address contained in EXPR.
! 	 For offset, the returned base will be NULL.  */
!       base_addr0 = address_analysis (oprnd0, stmt, is_read, dr, &address_offset, 
! 				     &address_misalign, &address_aligned_to, 
! 				     step);
! 
!       base_addr1 = address_analysis (oprnd1, stmt, is_read,  dr, &address_offset, 
! 				     &address_misalign, &address_aligned_to, 
! 				     step);
! 
!       /* We support cases where only one of the operands contains an 
! 	 address.  */
!       if ((base_addr0 && base_addr1) || (!base_addr0 && !base_addr1))
! 	{
! 	  if (dump_file && (dump_flags & TDF_DETAILS))
! 	    {
! 	      fprintf (dump_file, 
! 		    "\neither more than one address or no addresses in expr ");
! 	      print_generic_expr (dump_file, expr, TDF_SLIM);
! 	      fprintf (dump_file, "\n");
! 	    }	
! 	  return NULL_TREE;
! 	}
! 
!       /* To revert STRIP_NOPS.  */
!       oprnd0 = TREE_OPERAND (expr, 0);
!       oprnd1 = TREE_OPERAND (expr, 1);
!       
!       offset_expr = base_addr0 ? 
! 	fold_convert (ssizetype, oprnd1) : fold_convert (ssizetype, oprnd0);
! 
!       /* EXPR is of form {base +/- offset} (or {offset +/- base}). If offset is 
! 	 a number, we can add it to the misalignment value calculated for base,
! 	 otherwise, misalignment is NULL.  */
!       if (TREE_CODE (offset_expr) == INTEGER_CST && address_misalign)
! 	{
! 	  *misalign = size_binop (TREE_CODE (expr), address_misalign, 
! 				  offset_expr);
! 	  *aligned_to = address_aligned_to;
! 	}
!       else
! 	{
! 	  *misalign = NULL_TREE;
! 	  *aligned_to = NULL_TREE;
! 	}
! 
!       /* Combine offset (from EXPR {base + offset}) with the offset calculated
! 	 for base.  */
!       *offset = size_binop (TREE_CODE (expr), address_offset, offset_expr);
!       return base_addr0 ? base_addr0 : base_addr1;
! 
!     case ADDR_EXPR:
!       base_address = object_analysis (TREE_OPERAND (expr, 0), stmt, is_read, 
! 				      &dr, offset, misalign, aligned_to, step, 
! 				      &dummy, &dummy1, &dummy2);
!       return base_address;
! 
!     case SSA_NAME:
!       if (!POINTER_TYPE_P (TREE_TYPE (expr)))
! 	{
! 	  if (dump_file && (dump_flags & TDF_DETAILS))
! 	    {
! 	      fprintf (dump_file, "\nnot pointer SSA_NAME ");
! 	      print_generic_expr (dump_file, expr, TDF_SLIM);
! 	      fprintf (dump_file, "\n");
! 	    }	
! 	  return NULL_TREE;
! 	}
!       *aligned_to = ssize_int (TYPE_ALIGN_UNIT (TREE_TYPE (TREE_TYPE (expr))));
!       *misalign = ssize_int (0);
!       *offset = ssize_int (0);
!       *step = ssize_int (0);
!       return expr;
!       
!     default:
!       return NULL_TREE;
!     }
! }
! 
! 
! /* Function object_analysis
! 
!    Create a data-reference structure DR for MEMREF.
!    Return the BASE of the data reference MEMREF if the analysis is possible.
!    Also compute the INITIAL_OFFSET from BASE, MISALIGN and STEP.
!    E.g., for EXPR a.b[i] + 4B, BASE is a, and OFFSET is the overall offset  
!    'a.b[i] + 4B' from a (can be an expression), MISALIGN is an OFFSET 
!    instantiated with initial_conditions of access_functions of variables, 
!    and STEP is the evolution of the DR_REF in this loop.
!    
!    Function get_inner_reference is used for the above in case of ARRAY_REF and
!    COMPONENT_REF.
! 
!    The structure of the function is as follows:
!    Part 1:
!    Case 1. For handled_component_p refs 
!           1.1 build data-reference structure for MEMREF
!           1.2 call get_inner_reference
!             1.2.1 analyze offset expr received from get_inner_reference
!           (fall through with BASE)
!    Case 2. For declarations 
!           2.1 set MEMTAG
!    Case 3. For INDIRECT_REFs 
!           3.1 build data-reference structure for MEMREF
! 	  3.2 analyze evolution and initial condition of MEMREF
! 	  3.3 set data-reference structure for MEMREF
!           3.4 call address_analysis to analyze INIT of the access function
! 	  3.5 extract memory tag
! 
!    Part 2:
!    Combine the results of object and address analysis to calculate 
!    INITIAL_OFFSET, STEP and misalignment info.   
! 
!    Input:
!    MEMREF - the memory reference that is being analyzed
!    STMT - the statement that contains MEMREF
!    IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
!    
!    Output:
!    BASE_ADDRESS (returned value) - the base address of the data reference MEMREF
!                                    E.g, if MEMREF is a.b[k].c[i][j] the returned
! 			           base is &a.
!    DR - data_reference struct for MEMREF
!    INITIAL_OFFSET - initial offset of MEMREF from BASE (an expression)
!    MISALIGN - offset of MEMREF from BASE in bytes (a constant) modulo alignment of 
!               ALIGNMENT or NULL_TREE if the computation is impossible
!    ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be 
!                 calculated (doesn't depend on variables)
!    STEP - evolution of the DR_REF in the loop
!    MEMTAG - memory tag for aliasing purposes
!    PTR_INFO - NULL or points-to aliasing info from a pointer SSA_NAME
!    SUBVARS - Sub-variables of the variable
! 
!    If the analysis of MEMREF evolution in the loop fails, NULL_TREE is returned, 
!    but DR can be created anyway.
!    
! */
!  
! static tree
! object_analysis (tree memref, tree stmt, bool is_read, 
! 		 struct data_reference **dr, tree *offset, tree *misalign, 
! 		 tree *aligned_to, tree *step, tree *memtag,
! 		 struct ptr_info_def **ptr_info, subvar_t *subvars)
! {
!   tree base = NULL_TREE, base_address = NULL_TREE;
!   tree object_offset = ssize_int (0), object_misalign = ssize_int (0);
!   tree object_step = ssize_int (0), address_step = ssize_int (0);
!   tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
!   HOST_WIDE_INT pbitsize, pbitpos;
!   tree poffset, bit_pos_in_bytes;
!   enum machine_mode pmode;
!   int punsignedp, pvolatilep;
!   tree ptr_step = ssize_int (0), ptr_init = NULL_TREE;
!   struct loop *loop = loop_containing_stmt (stmt);
!   struct data_reference *ptr_dr = NULL;
!   tree object_aligned_to = NULL_TREE, address_aligned_to = NULL_TREE;
!   tree comp_ref = NULL_TREE;
! 
!  *ptr_info = NULL;
! 
!   /* Part 1:  */
!   /* Case 1. handled_component_p refs.  */
!   if (handled_component_p (memref))
!     {
!       /* 1.1 build data-reference structure for MEMREF.  */
!       if (!(*dr))
! 	{ 
! 	  if (TREE_CODE (memref) == ARRAY_REF)
! 	    *dr = init_array_ref (stmt, memref, is_read);	  
! 	  else if (TREE_CODE (memref) == COMPONENT_REF)
! 	    comp_ref = memref;
! 	  else  
! 	    {
! 	      if (dump_file && (dump_flags & TDF_DETAILS))
! 		{
! 		  fprintf (dump_file, "\ndata-ref of unsupported type ");
! 		  print_generic_expr (dump_file, memref, TDF_SLIM);
! 		  fprintf (dump_file, "\n");
! 		}
! 	      return NULL_TREE;
! 	    }
! 	}
! 
!       /* 1.2 call get_inner_reference.  */
!       /* Find the base and the offset from it.  */
!       base = get_inner_reference (memref, &pbitsize, &pbitpos, &poffset,
! 				  &pmode, &punsignedp, &pvolatilep, false);
!       if (!base)
! 	{
! 	  if (dump_file && (dump_flags & TDF_DETAILS))
! 	    {
! 	      fprintf (dump_file, "\nfailed to get inner ref for ");
! 	      print_generic_expr (dump_file, memref, TDF_SLIM);
! 	      fprintf (dump_file, "\n");
! 	    }	  
! 	  return NULL_TREE;
! 	}
! 
!       /* 1.2.1 analyze offset expr received from get_inner_reference.  */
!       if (poffset 
! 	  && !analyze_offset_expr (poffset, loop, &object_offset, 
! 				   &object_misalign, &object_aligned_to,
! 				   &object_step))
! 	{
! 	  if (dump_file && (dump_flags & TDF_DETAILS))
! 	    {
! 	      fprintf (dump_file, "\nfailed to compute offset or step for ");
! 	      print_generic_expr (dump_file, memref, TDF_SLIM);
! 	      fprintf (dump_file, "\n");
! 	    }
! 	  return NULL_TREE;
! 	}
! 
!       /* Add bit position to OFFSET and MISALIGN.  */
! 
!       bit_pos_in_bytes = ssize_int (pbitpos/BITS_PER_UNIT);
!       /* Check that there is no remainder in bits.  */
!       if (pbitpos%BITS_PER_UNIT)
! 	{
! 	  if (dump_file && (dump_flags & TDF_DETAILS))
! 	    fprintf (dump_file, "\nbit offset alignment.\n");
! 	  return NULL_TREE;
! 	}
!       object_offset = size_binop (PLUS_EXPR, bit_pos_in_bytes, object_offset);     
!       if (object_misalign) 
! 	object_misalign = size_binop (PLUS_EXPR, object_misalign, 
! 				      bit_pos_in_bytes); 
!       
!       memref = base; /* To continue analysis of BASE.  */
!       /* fall through  */
!     }
!   
!   /*  Part 1: Case 2. Declarations.  */ 
!   if (DECL_P (memref))
!     {
!       /* We expect to get a decl only if we already have a DR, or with 
! 	 COMPONENT_REFs of type 'a[i].b'.  */
!       if (!(*dr))
! 	{
! 	  if (comp_ref && TREE_CODE (TREE_OPERAND (comp_ref, 0)) == ARRAY_REF)
! 	    {
! 	      *dr = init_array_ref (stmt, TREE_OPERAND (comp_ref, 0), is_read);	      	      
! 	      if (DR_NUM_DIMENSIONS (*dr) != 1)
! 		{
! 		  if (dump_file && (dump_flags & TDF_DETAILS))
! 		    {
! 		      fprintf (dump_file, "\n multidimensional component ref ");
! 		      print_generic_expr (dump_file, comp_ref, TDF_SLIM);
! 		      fprintf (dump_file, "\n");
! 		    }
! 		  return NULL_TREE;
! 		}
! 	    }
! 	  else 
! 	    {
! 	      if (dump_file && (dump_flags & TDF_DETAILS))
! 		{
! 		  fprintf (dump_file, "\nunhandled decl ");
! 		  print_generic_expr (dump_file, memref, TDF_SLIM);
! 		  fprintf (dump_file, "\n");
! 		}
! 	      return NULL_TREE;
! 	    }
! 	}
! 
!       /* TODO: if during the analysis of INDIRECT_REF we get to an object, put 
! 	 the object in BASE_OBJECT field if we can prove that this is O.K., 
! 	 i.e., the data-ref access is bounded by the bounds of the BASE_OBJECT.
! 	 (e.g., if the object is an array base 'a', where 'a[N]', we must prove
! 	 that every access with 'p' (the original INDIRECT_REF based on '&a')
! 	 in the loop is within the array boundaries - from a[0] to a[N-1]).
! 	 Otherwise, our alias analysis can be incorrect.
! 	 Even if an access function based on BASE_OBJECT can't be build, update
! 	 BASE_OBJECT field to enable us to prove that two data-refs are 
! 	 different (without access function, distance analysis is impossible).
!       */
!      if (SSA_VAR_P (memref) && var_can_have_subvars (memref))	
! 	*subvars = get_subvars_for_var (memref);
!       base_address = build_fold_addr_expr (memref);
!       /* 2.1 set MEMTAG.  */
!       *memtag = memref;
!     }
! 
!   /* Part 1:  Case 3. INDIRECT_REFs.  */
!   else if (TREE_CODE (memref) == INDIRECT_REF)
!     {
!       tree ptr_ref = TREE_OPERAND (memref, 0);
!       if (TREE_CODE (ptr_ref) == SSA_NAME)
!         *ptr_info = SSA_NAME_PTR_INFO (ptr_ref);
! 
!       /* 3.1 build data-reference structure for MEMREF.  */
!       ptr_dr = analyze_indirect_ref (stmt, memref, is_read);
!       if (!ptr_dr)
! 	{
! 	  if (dump_file && (dump_flags & TDF_DETAILS))
! 	    {
! 	      fprintf (dump_file, "\nfailed to create dr for ");
! 	      print_generic_expr (dump_file, memref, TDF_SLIM);
! 	      fprintf (dump_file, "\n");
! 	    }	
! 	  return NULL_TREE;      
! 	}
! 
!       /* 3.2 analyze evolution and initial condition of MEMREF.  */
!       ptr_step = DR_STEP (ptr_dr);
!       ptr_init = DR_BASE_ADDRESS (ptr_dr);
!       if (!ptr_init || !ptr_step || !POINTER_TYPE_P (TREE_TYPE (ptr_init)))
! 	{
! 	  *dr = (*dr) ? *dr : ptr_dr;
! 	  if (dump_file && (dump_flags & TDF_DETAILS))
! 	    {
! 	      fprintf (dump_file, "\nbad pointer access ");
! 	      print_generic_expr (dump_file, memref, TDF_SLIM);
! 	      fprintf (dump_file, "\n");
! 	    }
! 	  return NULL_TREE;
! 	}
! 
!       if (integer_zerop (ptr_step) && !(*dr))
! 	{
! 	  if (dump_file && (dump_flags & TDF_DETAILS)) 
! 	    fprintf (dump_file, "\nptr is loop invariant.\n");	
! 	  *dr = ptr_dr;
! 	  return NULL_TREE;
! 	
! 	  /* If there exists DR for MEMREF, we are analyzing the base of
! 	     handled component (PTR_INIT), which not necessary has evolution in 
! 	     the loop.  */
! 	}
!       object_step = size_binop (PLUS_EXPR, object_step, ptr_step);
! 
!       /* 3.3 set data-reference structure for MEMREF.  */
!       if (!*dr)
!         *dr = ptr_dr;
! 
!       /* 3.4 call address_analysis to analyze INIT of the access 
! 	 function.  */
!       base_address = address_analysis (ptr_init, stmt, is_read, *dr, 
! 				       &address_offset, &address_misalign, 
! 				       &address_aligned_to, &address_step);
!       if (!base_address)
! 	{
! 	  if (dump_file && (dump_flags & TDF_DETAILS))
! 	    {
! 	      fprintf (dump_file, "\nfailed to analyze address ");
! 	      print_generic_expr (dump_file, ptr_init, TDF_SLIM);
! 	      fprintf (dump_file, "\n");
! 	    }
! 	  return NULL_TREE;
! 	}
  
!       /* 3.5 extract memory tag.  */
!       switch (TREE_CODE (base_address))
! 	{
! 	case SSA_NAME:
! 	  *memtag = symbol_mem_tag (SSA_NAME_VAR (base_address));
! 	  if (!(*memtag) && TREE_CODE (TREE_OPERAND (memref, 0)) == SSA_NAME)
! 	    *memtag = symbol_mem_tag (SSA_NAME_VAR (TREE_OPERAND (memref, 0)));
! 	  break;
! 	case ADDR_EXPR:
! 	  *memtag = TREE_OPERAND (base_address, 0);
! 	  break;
! 	default:
! 	  if (dump_file && (dump_flags & TDF_DETAILS))
! 	    {
! 	      fprintf (dump_file, "\nno memtag for "); 
! 	      print_generic_expr (dump_file, memref, TDF_SLIM);
! 	      fprintf (dump_file, "\n");
! 	    }
! 	  *memtag = NULL_TREE;
! 	  break;
! 	}
!     }      
!     
!   if (!base_address)
!     {
!       /* MEMREF cannot be analyzed.  */
!       if (dump_file && (dump_flags & TDF_DETAILS))
! 	{
! 	  fprintf (dump_file, "\ndata-ref of unsupported type ");
! 	  print_generic_expr (dump_file, memref, TDF_SLIM);
! 	  fprintf (dump_file, "\n");
! 	}
!       return NULL_TREE;
!     }
  
!   if (comp_ref)
!     DR_REF (*dr) = comp_ref;
  
!   if (SSA_VAR_P (*memtag) && var_can_have_subvars (*memtag))
!     *subvars = get_subvars_for_var (*memtag);
! 	
!   /* Part 2: Combine the results of object and address analysis to calculate 
!      INITIAL_OFFSET, STEP and misalignment info.  */
!   *offset = size_binop (PLUS_EXPR, object_offset, address_offset);
  
!   if ((!object_misalign && !object_aligned_to)
!       || (!address_misalign && !address_aligned_to))
!     {
!       *misalign = NULL_TREE;
!       *aligned_to = NULL_TREE;
!     }  
!   else 
!     {
!       if (object_misalign && address_misalign)
! 	*misalign = size_binop (PLUS_EXPR, object_misalign, address_misalign);
!       else
! 	*misalign = object_misalign ? object_misalign : address_misalign;
!       if (object_aligned_to && address_aligned_to)
! 	*aligned_to = size_binop (MIN_EXPR, object_aligned_to, 
! 				  address_aligned_to);
!       else
! 	*aligned_to = object_aligned_to ? 
! 	  object_aligned_to : address_aligned_to; 
!     }
!   *step = size_binop (PLUS_EXPR, object_step, address_step); 
  
!   return base_address;
  }
  
! /* Function analyze_offset.
!    
!    Extract INVARIANT and CONSTANT parts from OFFSET. 
  
! */
! static bool 
! analyze_offset (tree offset, tree *invariant, tree *constant)
  {
!   tree op0, op1, constant_0, constant_1, invariant_0, invariant_1;
!   enum tree_code code = TREE_CODE (offset);
  
!   *invariant = NULL_TREE;
!   *constant = NULL_TREE;
  
!   /* Not PLUS/MINUS expression - recursion stop condition.  */
!   if (code != PLUS_EXPR && code != MINUS_EXPR)
      {
!       if (TREE_CODE (offset) == INTEGER_CST)
! 	*constant = offset;
!       else
! 	*invariant = offset;
!       return true;
!     }
  
!   op0 = TREE_OPERAND (offset, 0);
!   op1 = TREE_OPERAND (offset, 1);
  
!   /* Recursive call with the operands.  */
!   if (!analyze_offset (op0, &invariant_0, &constant_0)
!       || !analyze_offset (op1, &invariant_1, &constant_1))
!     return false;
  
!   /* Combine the results. Add negation to the subtrahend in case of 
!      subtraction.  */
!   if (constant_0 && constant_1)
!     return false;
!   *constant = constant_0 ? constant_0 : constant_1;
!   if (code == MINUS_EXPR && constant_1)
!     *constant = fold_build1 (NEGATE_EXPR, TREE_TYPE (*constant), *constant);
! 
!   if (invariant_0 && invariant_1)
!     *invariant = 
!       fold_build2 (code, TREE_TYPE (invariant_0), invariant_0, invariant_1);
!   else
!     {
!       *invariant = invariant_0 ? invariant_0 : invariant_1;
!       if (code == MINUS_EXPR && invariant_1)
!         *invariant = 
!            fold_build1 (NEGATE_EXPR, TREE_TYPE (*invariant), *invariant);
      }
!   return true;
  }
  
! /* Free the memory used by the data reference DR.  */
  
! static void
! free_data_ref (data_reference_p dr)
  {
!   DR_FREE_ACCESS_FNS (dr);
!   free (dr);
! }
  
! /* Function create_data_ref.
!    
!    Create a data-reference structure for MEMREF. Set its DR_BASE_ADDRESS,
!    DR_OFFSET, DR_INIT, DR_STEP, DR_OFFSET_MISALIGNMENT, DR_ALIGNED_TO,
!    DR_MEMTAG, and DR_POINTSTO_INFO fields. 
! 
!    Input:
!    MEMREF - the memory reference that is being analyzed
!    STMT - the statement that contains MEMREF
!    IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
  
!    Output:
!    DR (returned value) - data_reference struct for MEMREF
! */
  
! static struct data_reference *
! create_data_ref (tree memref, tree stmt, bool is_read)
  {
!   struct data_reference *dr = NULL;
!   tree base_address, offset, step, misalign, memtag;
    struct loop *loop = loop_containing_stmt (stmt);
!   tree invariant = NULL_TREE, constant = NULL_TREE;
!   tree type_size, init_cond;
!   struct ptr_info_def *ptr_info;
!   subvar_t subvars = NULL;
!   tree aligned_to, type = NULL_TREE, orig_offset;
  
!   if (!memref)
!     return NULL;
  
!   base_address = object_analysis (memref, stmt, is_read, &dr, &offset, 
! 				  &misalign, &aligned_to, &step, &memtag, 
! 				  &ptr_info, &subvars);
!   if (!dr || !base_address)
      {
        if (dump_file && (dump_flags & TDF_DETAILS))
! 	{
! 	  fprintf (dump_file, "\ncreate_data_ref: failed to create a dr for ");
! 	  print_generic_expr (dump_file, memref, TDF_SLIM);
! 	  fprintf (dump_file, "\n");
! 	}
!       return NULL;
      }
  
!   DR_BASE_ADDRESS (dr) = base_address;
!   DR_OFFSET (dr) = offset;
!   DR_INIT (dr) = ssize_int (0);
!   DR_STEP (dr) = step;
!   DR_OFFSET_MISALIGNMENT (dr) = misalign;
!   DR_ALIGNED_TO (dr) = aligned_to;
!   DR_MEMTAG (dr) = memtag;
!   DR_PTR_INFO (dr) = ptr_info;
!   DR_SUBVARS (dr) = subvars;
!   
!   type_size = fold_convert (ssizetype, TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr))));
! 
!   /* Extract CONSTANT and INVARIANT from OFFSET.  */
!   /* Remove cast from OFFSET and restore it for INVARIANT part.  */
!   orig_offset = offset;
!   STRIP_NOPS (offset);
!   if (offset != orig_offset)
!     type = TREE_TYPE (orig_offset);
!   if (!analyze_offset (offset, &invariant, &constant))
      {
        if (dump_file && (dump_flags & TDF_DETAILS))
!         {
!           fprintf (dump_file, "\ncreate_data_ref: failed to analyze dr's");
!           fprintf (dump_file, " offset for ");
!           print_generic_expr (dump_file, memref, TDF_SLIM);
!           fprintf (dump_file, "\n");
!         }
!       return NULL;
      }
!   if (type && invariant)
!     invariant = fold_convert (type, invariant);
! 
!   /* Put CONSTANT part of OFFSET in DR_INIT and INVARIANT in DR_OFFSET field
!      of DR.  */
!   if (constant)
!     {
!       DR_INIT (dr) = fold_convert (ssizetype, constant);
!       init_cond = fold_build2 (TRUNC_DIV_EXPR, TREE_TYPE (constant), 
! 			       constant, type_size);
      }
-   else
-     DR_INIT (dr) = init_cond = ssize_int (0);
  
!   if (invariant)
!     DR_OFFSET (dr) = invariant;
!   else
!     DR_OFFSET (dr) = ssize_int (0);
  
!   /* Change the access function for INIDIRECT_REFs, according to 
!      DR_BASE_ADDRESS.  Analyze OFFSET calculated in object_analysis. OFFSET is 
!      an expression that can contain loop invariant expressions and constants.
!      We put the constant part in the initial condition of the access function
!      (for data dependence tests), and in DR_INIT of the data-ref. The loop
!      invariant part is put in DR_OFFSET. 
!      The evolution part of the access function is STEP calculated in
!      object_analysis divided by the size of data type.
!   */
!   if (!DR_BASE_OBJECT (dr)
!       || (TREE_CODE (memref) == COMPONENT_REF && DR_NUM_DIMENSIONS (dr) == 1))
!     {
!       tree access_fn;
!       tree new_step;
  
!       /* Update access function.  */
!       access_fn = DR_ACCESS_FN (dr, 0);
!       if (automatically_generated_chrec_p (access_fn))
  	{
! 	  free_data_ref (dr);
! 	  return NULL;
  	}
  
!       new_step = size_binop (TRUNC_DIV_EXPR,  
! 			     fold_convert (ssizetype, step), type_size);
  
!       init_cond = chrec_convert (chrec_type (access_fn), init_cond, stmt);
!       new_step = chrec_convert (chrec_type (access_fn), new_step, stmt);
!       if (automatically_generated_chrec_p (init_cond)
! 	  || automatically_generated_chrec_p (new_step))
  	{
! 	  free_data_ref (dr);
! 	  return NULL;
  	}
!       access_fn = chrec_replace_initial_condition (access_fn, init_cond);
!       access_fn = reset_evolution_in_loop (loop->num, access_fn, new_step);
  
!       VEC_replace (tree, DR_ACCESS_FNS (dr), 0, access_fn);
      }
  
    if (dump_file && (dump_flags & TDF_DETAILS))
      {
!       struct ptr_info_def *pi = DR_PTR_INFO (dr);
! 
!       fprintf (dump_file, "\nCreated dr for ");
        print_generic_expr (dump_file, memref, TDF_SLIM);
!       fprintf (dump_file, "\n\tbase_address: ");
        print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM);
        fprintf (dump_file, "\n\toffset from base address: ");
        print_generic_expr (dump_file, DR_OFFSET (dr), TDF_SLIM);
        fprintf (dump_file, "\n\tconstant offset from base address: ");
        print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM);
-       fprintf (dump_file, "\n\tbase_object: ");
-       print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
        fprintf (dump_file, "\n\tstep: ");
        print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM);
!       fprintf (dump_file, "B\n\tmisalignment from base: ");
!       print_generic_expr (dump_file, DR_OFFSET_MISALIGNMENT (dr), TDF_SLIM);
!       if (DR_OFFSET_MISALIGNMENT (dr))
! 	fprintf (dump_file, "B");
!       if (DR_ALIGNED_TO (dr))
! 	{
! 	  fprintf (dump_file, "\n\taligned to: ");
! 	  print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM);
! 	}
!       fprintf (dump_file, "\n\tmemtag: ");
!       print_generic_expr (dump_file, DR_MEMTAG (dr), TDF_SLIM);
        fprintf (dump_file, "\n");
-       if (pi && pi->name_mem_tag)
-         {
-           fprintf (dump_file, "\n\tnametag: ");
-           print_generic_expr (dump_file, pi->name_mem_tag, TDF_SLIM);
-           fprintf (dump_file, "\n");
-         }
      }  
    return dr;  
  }
--- 459,782 ----
  	    fprintf (file, "DISTANCE_V (");
  	    print_lambda_vector (file, v, DDR_NB_LOOPS (ddr));
  	    fprintf (file, ")\n");
! 	  }
  
! 	for (j = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), j, v); j++)
! 	  {
! 	    fprintf (file, "DIRECTION_V (");
! 	    print_direction_vector (file, v, DDR_NB_LOOPS (ddr));
! 	    fprintf (file, ")\n");
! 	  }
!       }
  
!   fprintf (file, "\n\n");
! }
  
! /* Dumps the data dependence relations DDRS in FILE.  */
  
! void 
! dump_ddrs (FILE *file, VEC (ddr_p, heap) *ddrs)
! {
!   unsigned int i;
!   struct data_dependence_relation *ddr;
! 
!   for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
!     dump_data_dependence_relation (file, ddr);
  
!   fprintf (file, "\n\n");
  }
  
! /* Expresses EXP as VAR + OFF, where off is a constant.  The type of OFF
!    will be ssizetype.  */
  
! static void
! split_constant_offset (tree exp, tree *var, tree *off)
  {
!   tree type = TREE_TYPE (exp), otype;
!   tree var0, var1;
!   tree off0, off1;
  
!   *var = exp;
!   STRIP_NOPS (exp);
!   otype = TREE_TYPE (exp);
  
!   switch (TREE_CODE (exp))
      {
!     case INTEGER_CST:
!       *var = build_int_cst (type, 0);
!       *off = fold_convert (ssizetype, exp);
!       return;
  
!     case PLUS_EXPR:
!     case MINUS_EXPR:
!       split_constant_offset (TREE_OPERAND (exp, 0), &var0, &off0);
!       split_constant_offset (TREE_OPERAND (exp, 1), &var1, &off1);
!       *var = fold_convert (type, fold_build2 (TREE_CODE (exp), otype, 
! 					      var0, var1));
!       *off = size_binop (TREE_CODE (exp), off0, off1);
!       return;
  
!     case MULT_EXPR:
!       off1 = TREE_OPERAND (exp, 1);
!       if (TREE_CODE (off1) != INTEGER_CST)
! 	break;
! 
!       split_constant_offset (TREE_OPERAND (exp, 0), &var0, &off0);
!       *var = fold_convert (type, fold_build2 (MULT_EXPR, otype,
! 					      var0, off1));
!       *off = size_binop (MULT_EXPR, off0, fold_convert (ssizetype, off1));
!       return;
  
!     case ADDR_EXPR:
!       {
! 	tree op, base, poffset;
! 	HOST_WIDE_INT pbitsize, pbitpos;
! 	enum machine_mode pmode;
! 	int punsignedp, pvolatilep;
! 
! 	op = TREE_OPERAND (exp, 0);
! 	if (!handled_component_p (op))
! 	  break;
! 
! 	base = get_inner_reference (op, &pbitsize, &pbitpos, &poffset,
! 				    &pmode, &punsignedp, &pvolatilep, false);
! 
! 	if (pbitpos % BITS_PER_UNIT != 0)
! 	  break;
! 	base = build_fold_addr_expr (base);
! 	off0 = ssize_int (pbitpos / BITS_PER_UNIT);
! 
! 	if (poffset)
! 	  {
! 	    split_constant_offset (poffset, &poffset, &off1);
! 	    off0 = size_binop (PLUS_EXPR, off0, off1);
! 	    base = fold_build2 (PLUS_EXPR, TREE_TYPE (base),
! 				base,
! 				fold_convert (TREE_TYPE (base), poffset));
! 	  }
! 
! 	*var = fold_convert (type, base);
! 	*off = off0;
! 	return;
!       }
! 
!     default:
!       break;
      }
! 
!   *off = ssize_int (0);
  }
  
! /* Returns the address ADDR of an object in a canonical shape (without nop
!    casts, and with type of pointer to the object).  */
  
! static tree
! canonicalize_base_object_address (tree addr)
  {
!   STRIP_NOPS (addr);
  
!   if (TREE_CODE (addr) != ADDR_EXPR)
!     return addr;
  
!   return build_fold_addr_expr (TREE_OPERAND (addr, 0));
! }
  
! /* Analyzes the behavior of the memory reference DR in the innermost loop that
!    contains it.  */
! 
! static void
! dr_analyze_innermost (struct data_reference *dr)
  {
!   tree stmt = DR_STMT (dr);
    struct loop *loop = loop_containing_stmt (stmt);
!   tree ref = DR_REF (dr);
!   HOST_WIDE_INT pbitsize, pbitpos;
!   tree base, poffset;
!   enum machine_mode pmode;
!   int punsignedp, pvolatilep;
!   affine_iv base_iv, offset_iv;
!   tree init, dinit, step;
  
!   if (dump_file && (dump_flags & TDF_DETAILS))
!     fprintf (dump_file, "analyze_innermost: ");
  
!   base = get_inner_reference (ref, &pbitsize, &pbitpos, &poffset,
! 			      &pmode, &punsignedp, &pvolatilep, false);
!   gcc_assert (base != NULL_TREE);
! 
!   if (pbitpos % BITS_PER_UNIT != 0)
      {
        if (dump_file && (dump_flags & TDF_DETAILS))
! 	fprintf (dump_file, "failed: bit offset alignment.\n");
!       return;
      }
  
!   base = build_fold_addr_expr (base);
!   if (!simple_iv (loop, stmt, base, &base_iv, false))
      {
        if (dump_file && (dump_flags & TDF_DETAILS))
! 	fprintf (dump_file, "failed: evolution of base is not affine.\n");
!       return;
      }
!   if (!poffset)
!     {
!       offset_iv.base = ssize_int (0);
!       offset_iv.step = ssize_int (0);
!     }
!   else if (!simple_iv (loop, stmt, poffset, &offset_iv, false))
!     {
!       if (dump_file && (dump_flags & TDF_DETAILS))
! 	fprintf (dump_file, "failed: evolution of offset is not affine.\n");
!       return;
      }
  
!   init = ssize_int (pbitpos / BITS_PER_UNIT);
!   split_constant_offset (base_iv.base, &base_iv.base, &dinit);
!   init =  size_binop (PLUS_EXPR, init, dinit);
!   split_constant_offset (offset_iv.base, &offset_iv.base, &dinit);
!   init =  size_binop (PLUS_EXPR, init, dinit);
! 
!   step = size_binop (PLUS_EXPR,
! 		     fold_convert (ssizetype, base_iv.step),
! 		     fold_convert (ssizetype, offset_iv.step));
  
!   DR_BASE_ADDRESS (dr) = canonicalize_base_object_address (base_iv.base);
  
!   DR_OFFSET (dr) = fold_convert (ssizetype, offset_iv.base);
!   DR_INIT (dr) = init;
!   DR_STEP (dr) = step;
! 
!   DR_ALIGNED_TO (dr) = size_int (highest_pow2_factor (offset_iv.base));
! 
!   if (dump_file && (dump_flags & TDF_DETAILS))
!     fprintf (dump_file, "success.\n");
! }
! 
! /* Determines the base object and the list of indices of memory reference
!    DR, analysed in loop nest NEST.  */
! 
! static void
! dr_analyze_indices (struct data_reference *dr, struct loop *nest)
! {
!   tree stmt = DR_STMT (dr);
!   struct loop *loop = loop_containing_stmt (stmt);
!   VEC (tree, heap) *access_fns = NULL;
!   tree ref = unshare_expr (DR_REF (dr)), aref = ref, op;
!   tree base, off, access_fn;
! 
!   while (handled_component_p (aref))
!     {
!       if (TREE_CODE (aref) == ARRAY_REF)
  	{
! 	  op = TREE_OPERAND (aref, 1);
! 	  access_fn = analyze_scalar_evolution (loop, op);
! 	  access_fn = resolve_mixers (nest, access_fn);
! 	  VEC_safe_push (tree, heap, access_fns, access_fn);
! 
! 	  TREE_OPERAND (aref, 1) = build_int_cst (TREE_TYPE (op), 0);
  	}
+       
+       aref = TREE_OPERAND (aref, 0);
+     }
+ 
+   if (INDIRECT_REF_P (aref))
+     {
+       op = TREE_OPERAND (aref, 0);
+       access_fn = analyze_scalar_evolution (loop, op);
+       access_fn = resolve_mixers (nest, access_fn);
+       base = initial_condition (access_fn);
+       split_constant_offset (base, &base, &off);
+       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);
+     }
+ 
+   DR_BASE_OBJECT (dr) = ref;
+   DR_ACCESS_FNS (dr) = access_fns;
+ }
+ 
+ /* Extracts the alias analysis information from the memory reference DR.  */
  
! static void
! dr_analyze_alias (struct data_reference *dr)
! {
!   tree stmt = DR_STMT (dr);
!   tree ref = DR_REF (dr);
!   tree base = get_base_address (ref), addr, smt = NULL_TREE;
!   ssa_op_iter it;
!   tree op;
!   bitmap vops;
  
!   if (DECL_P (base))
!     smt = base;
!   else if (INDIRECT_REF_P (base))
!     {
!       addr = TREE_OPERAND (base, 0);
!       if (TREE_CODE (addr) == SSA_NAME)
  	{
! 	  smt = symbol_mem_tag (SSA_NAME_VAR (addr));
! 	  DR_PTR_INFO (dr) = SSA_NAME_PTR_INFO (addr);
  	}
!     }
  
!   DR_SYMBOL_TAG (dr) = smt;
!   if (var_can_have_subvars (smt))
!     DR_SUBVARS (dr) = get_subvars_for_var (smt);
! 
!   vops = BITMAP_ALLOC (NULL);
!   FOR_EACH_SSA_TREE_OPERAND (op, stmt, it, SSA_OP_VIRTUAL_USES)
!     {
!       bitmap_set_bit (vops, DECL_UID (SSA_NAME_VAR (op)));
      }
  
+   DR_VOPS (dr) = vops;
+ }
+ 
+ /* Analyzes memory reference MEMREF accessed in STMT.  The reference
+    is read if IS_READ is true, write otherwise.  Returns the
+    data_reference description of MEMREF.  NEST is the outermost loop of the
+    loop nest in that the reference should be analysed.  */
+ 
+ static struct data_reference *
+ create_data_ref (struct loop *nest, tree memref, tree stmt, bool is_read)
+ {
+   struct data_reference *dr;
+ 
    if (dump_file && (dump_flags & TDF_DETAILS))
      {
!       fprintf (dump_file, "Creating dr for ");
        print_generic_expr (dump_file, memref, TDF_SLIM);
!       fprintf (dump_file, "\n");
!     }
! 
!   dr = XCNEW (struct data_reference);
!   DR_STMT (dr) = stmt;
!   DR_REF (dr) = memref;
!   DR_IS_READ (dr) = is_read;
! 
!   dr_analyze_innermost (dr);
!   dr_analyze_indices (dr, nest);
!   dr_analyze_alias (dr);
! 
!   if (dump_file && (dump_flags & TDF_DETAILS))
!     {
!       fprintf (dump_file, "\tbase_address: ");
        print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM);
        fprintf (dump_file, "\n\toffset from base address: ");
        print_generic_expr (dump_file, DR_OFFSET (dr), TDF_SLIM);
        fprintf (dump_file, "\n\tconstant offset from base address: ");
        print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM);
        fprintf (dump_file, "\n\tstep: ");
        print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM);
!       fprintf (dump_file, "\n\taligned to: ");
!       print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM);
!       fprintf (dump_file, "\n\tbase_object: ");
!       print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
!       fprintf (dump_file, "\n\tsymbol tag: ");
!       print_generic_expr (dump_file, DR_SYMBOL_TAG (dr), TDF_SLIM);
        fprintf (dump_file, "\n");
      }  
    return dr;  
  }
*************** conflict_fn_no_dependence (void)
*** 2259,2264 ****
--- 978,1157 ----
    return fn;
  }
  
+ /* Returns true if the address of OBJ is invariant in LOOP.  */
+ 
+ static bool
+ object_address_invariant_in_loop_p (struct loop *loop, tree obj)
+ {
+   while (handled_component_p (obj))
+     {
+       if (TREE_CODE (obj) == ARRAY_REF)
+ 	{
+ 	  /* Index of the ARRAY_REF was zeroed in analyze_indices, thus we only
+ 	     need to check the stride and the lower bound of the reference.  */
+ 	  if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 2),
+ 						      loop->num)
+ 	      || chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 3),
+ 							 loop->num))
+ 	    return false;
+ 	}
+       else if (TREE_CODE (obj) == COMPONENT_REF)
+ 	{
+ 	  if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 2),
+ 						      loop->num))
+ 	    return false;
+ 	}
+       obj = TREE_OPERAND (obj, 0);
+     }
+ 
+   if (!INDIRECT_REF_P (obj))
+     return true;
+ 
+   return !chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 0),
+ 						  loop->num);
+ }
+ 
+ /* Returns true if A and B are accesses to different objects, or to different
+    fields of the same object.  */
+ 
+ static bool
+ disjoint_objects_p (tree a, tree b)
+ {
+   tree base_a, base_b;
+   VEC (tree, heap) *comp_a = NULL, *comp_b = NULL;
+   bool ret;
+ 
+   base_a = get_base_address (a);
+   base_b = get_base_address (b);
+ 
+   if (DECL_P (base_a)
+       && DECL_P (base_b)
+       && base_a != base_b)
+     return true;
+ 
+   if (!operand_equal_p (base_a, base_b, 0))
+     return false;
+ 
+   /* Compare the component references of A and B.  We must start from the inner
+      ones, so record them to the vector first.  */
+   while (handled_component_p (a))
+     {
+       VEC_safe_push (tree, heap, comp_a, a);
+       a = TREE_OPERAND (a, 0);
+     }
+   while (handled_component_p (b))
+     {
+       VEC_safe_push (tree, heap, comp_b, b);
+       b = TREE_OPERAND (b, 0);
+     }
+ 
+   ret = false;
+   while (1)
+     {
+       if (VEC_length (tree, comp_a) == 0
+ 	  || VEC_length (tree, comp_b) == 0)
+ 	break;
+ 
+       a = VEC_pop (tree, comp_a);
+       b = VEC_pop (tree, comp_b);
+ 
+       /* Real and imaginary part of a variable do not alias.  */
+       if ((TREE_CODE (a) == REALPART_EXPR
+ 	   && TREE_CODE (b) == IMAGPART_EXPR)
+ 	  || (TREE_CODE (a) == IMAGPART_EXPR
+ 	      && TREE_CODE (b) == REALPART_EXPR))
+ 	{
+ 	  ret = true;
+ 	  break;
+ 	}
+ 
+       if (TREE_CODE (a) != TREE_CODE (b))
+ 	break;
+ 
+       /* Nothing to do for ARRAY_REFs, as the indices of array_refs in
+ 	 DR_BASE_OBJECT are always zero.  */
+       if (TREE_CODE (a) == ARRAY_REF)
+ 	continue;
+       else if (TREE_CODE (a) == COMPONENT_REF)
+ 	{
+ 	  if (operand_equal_p (TREE_OPERAND (a, 1), TREE_OPERAND (b, 1), 0))
+ 	    continue;
+ 
+ 	  /* Different fields of unions may overlap.  */
+ 	  base_a = TREE_OPERAND (a, 0);
+ 	  if (TREE_CODE (TREE_TYPE (base_a)) == UNION_TYPE)
+ 	    break;
+ 
+ 	  /* Different fields of structures cannot.  */
+ 	  ret = true;
+ 	  break;
+ 	}
+       else
+ 	break;
+     }
+ 
+   VEC_free (tree, heap, comp_a);
+   VEC_free (tree, heap, comp_b);
+ 
+   return ret;
+ }
+ 
+ /* Returns false if we can prove that data references A and B do not alias,
+    true otherwise.  */
+ 
+ static bool
+ dr_may_alias_p (struct data_reference *a, struct data_reference *b)
+ {
+   tree addr_a = DR_BASE_ADDRESS (a);
+   tree addr_b = DR_BASE_ADDRESS (b);
+   tree type_a, type_b;
+   tree decl_a = NULL_TREE, decl_b = NULL_TREE;
+ 
+   /* If the sets of virtual operands are disjoint, the memory references do not
+      alias.  */
+   if (!bitmap_intersect_p (DR_VOPS (a), DR_VOPS (b)))
+     return false;
+ 
+   /* If the accessed objects are disjoint, the memory references do not
+      alias.  */
+   if (disjoint_objects_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b)))
+     return false;
+ 
+   if (!addr_a || !addr_b)
+     return true;
+ 
+   /* If the references are based on different static objects, they cannot alias
+      (PTA should be able to disambiguate such accesses, but often it fails to,
+      since currently we cannot distinguish between pointer and offset in pointer
+      arithmetics).  */
+   if (TREE_CODE (addr_a) == ADDR_EXPR
+       && TREE_CODE (addr_b) == ADDR_EXPR)
+     return TREE_OPERAND (addr_a, 0) == TREE_OPERAND (addr_b, 0);
+ 
+   /* An instruction writing through a restricted pointer is "independent" of any 
+      instruction reading or writing through a different restricted pointer, 
+      in the same block/scope.  */
+ 
+   type_a = TREE_TYPE (addr_a);
+   type_b = TREE_TYPE (addr_b);
+   gcc_assert (POINTER_TYPE_P (type_a) && POINTER_TYPE_P (type_b));
+ 
+   if (TREE_CODE (addr_a) == SSA_NAME)
+     decl_a = SSA_NAME_VAR (addr_a);
+   if (TREE_CODE (addr_b) == SSA_NAME)
+     decl_b = SSA_NAME_VAR (addr_b);
+ 
+   if (TYPE_RESTRICT (type_a) && TYPE_RESTRICT (type_b) 
+       && (!DR_IS_READ (a) || !DR_IS_READ (b))
+       && decl_a && TREE_CODE (decl_a) == PARM_DECL
+       && decl_b && TREE_CODE (decl_b) == PARM_DECL
+       && TREE_CODE (DECL_CONTEXT (decl_a)) == FUNCTION_DECL
+       && DECL_CONTEXT (decl_a) == DECL_CONTEXT (decl_b))
+     return false;
+ 
+   return true;
+ }
+ 
  /* 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_data_dependence_relation (str
*** 2269,2275 ****
   				     VEC (loop_p, heap) *loop_nest)
  {
    struct data_dependence_relation *res;
-   bool differ_p, known_dependence;
    unsigned int i;
    
    res = XNEW (struct data_dependence_relation);
--- 1162,1167 ----
*************** initialize_data_dependence_relation (str
*** 2283,2316 ****
        return res;
      }   
  
!   /* When A and B are arrays and their dimensions differ, we directly
!      initialize the relation to "there is no dependence": chrec_known.  */
!   if (DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b)
!       && DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
      {
!       DDR_ARE_DEPENDENT (res) = chrec_known;
        return res;
      }
  
!   if (DR_BASE_ADDRESS (a) && DR_BASE_ADDRESS (b))
!     known_dependence = base_addr_differ_p (a, b, &differ_p);
!   else 
!     known_dependence = base_object_differ_p (a, b, &differ_p);
! 
!   if (!known_dependence)
      {
-       /* Can't determine whether the data-refs access the same memory 
- 	 region.  */
        DDR_ARE_DEPENDENT (res) = chrec_dont_know;    
        return res;
      }
  
!   if (differ_p)
      {
!       DDR_ARE_DEPENDENT (res) = chrec_known;    
        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));
--- 1175,1207 ----
        return res;
      }   
  
!   /* If the data references do not alias, then they are independent.  */
!   if (!dr_may_alias_p (a, b))
      {
!       DDR_ARE_DEPENDENT (res) = chrec_known;    
        return res;
      }
  
!   /* If the references do not access the same object, we do not know
!      whether they alias or not.  */
!   if (!operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0))
      {
        DDR_ARE_DEPENDENT (res) = chrec_dont_know;    
        return res;
      }
  
!   /* If the base of the object is not invariant in the loop nest, we cannot
!      analyse it.  TODO -- in fact, it would suffice to record that there may
!      be arbitrary depencences in the loops where the base object varies.  */
!   if (!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;
      }
! 
!   gcc_assert (DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b));
! 
    DDR_AFFINE_P (res) = true;
    DDR_ARE_DEPENDENT (res) = NULL_TREE;
    DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
*************** compute_self_dependence (struct data_dep
*** 4895,4900 ****
--- 3786,3794 ----
    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++)
      {
*************** get_references_in_stmt (tree stmt, VEC (
*** 5013,5022 ****
  }
  
  /* Stores the data references in STMT to DATAREFS.  If there is an unanalyzable
!    reference, returns false, otherwise returns true.  */
  
  static bool
! find_data_references_in_stmt (tree stmt,
  			      VEC (data_reference_p, heap) **datarefs)
  {
    unsigned i;
--- 3907,3917 ----
  }
  
  /* Stores the data references in STMT to DATAREFS.  If there is an unanalyzable
!    reference, returns false, otherwise returns true.  NEST is the outermost
!    loop of the loop nest in that the references should be analysed.  */
  
  static bool
! find_data_references_in_stmt (struct loop *nest, tree stmt,
  			      VEC (data_reference_p, heap) **datarefs)
  {
    unsigned i;
*************** find_data_references_in_stmt (tree stmt,
*** 5033,5039 ****
  
    for (i = 0; VEC_iterate (data_ref_loc, references, i, ref); i++)
      {
!       dr = create_data_ref (*ref->pos, stmt, ref->is_read);
        if (dr)
  	VEC_safe_push (data_reference_p, heap, *datarefs, dr);
        else
--- 3928,3934 ----
  
    for (i = 0; VEC_iterate (data_ref_loc, references, i, ref); i++)
      {
!       dr = create_data_ref (nest, *ref->pos, stmt, ref->is_read);
        if (dr)
  	VEC_safe_push (data_reference_p, heap, *datarefs, dr);
        else
*************** find_data_references_in_stmt (tree stmt,
*** 5049,5059 ****
  /* Search the data references in LOOP, and record the information into
     DATAREFS.  Returns chrec_dont_know when failing to analyze a
     difficult case, returns NULL_TREE otherwise.
!    
     TODO: This function should be made smarter so that it can handle address
     arithmetic as if they were array accesses, etc.  */
  
! tree 
  find_data_references_in_loop (struct loop *loop,
  			      VEC (data_reference_p, heap) **datarefs)
  {
--- 3944,3954 ----
  /* Search the data references in LOOP, and record the information into
     DATAREFS.  Returns chrec_dont_know when failing to analyze a
     difficult case, returns NULL_TREE otherwise.
! 
     TODO: This function should be made smarter so that it can handle address
     arithmetic as if they were array accesses, etc.  */
  
! static tree 
  find_data_references_in_loop (struct loop *loop,
  			      VEC (data_reference_p, heap) **datarefs)
  {
*************** find_data_references_in_loop (struct loo
*** 5071,5094 ****
  	{
  	  tree stmt = bsi_stmt (bsi);
  
! 	  if (!find_data_references_in_stmt (stmt, datarefs))
  	    {
  	      struct data_reference *res;
! 	      res = XNEW (struct data_reference);
! 	      DR_STMT (res) = NULL_TREE;
! 	      DR_REF (res) = NULL_TREE;
! 	      DR_BASE_OBJECT (res) = NULL;
! 	      DR_TYPE (res) = ARRAY_REF_TYPE;
! 	      DR_SET_ACCESS_FNS (res, NULL);
! 	      DR_BASE_OBJECT (res) = NULL;
! 	      DR_IS_READ (res) = false;
! 	      DR_BASE_ADDRESS (res) = NULL_TREE;
! 	      DR_OFFSET (res) = NULL_TREE;
! 	      DR_INIT (res) = NULL_TREE;
! 	      DR_STEP (res) = NULL_TREE;
! 	      DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
! 	      DR_MEMTAG (res) = NULL_TREE;
! 	      DR_PTR_INFO (res) = NULL;
  	      VEC_safe_push (data_reference_p, heap, *datarefs, res);
  
  	      free (bbs);
--- 3966,3975 ----
  	{
  	  tree stmt = bsi_stmt (bsi);
  
! 	  if (!find_data_references_in_stmt (loop, stmt, datarefs))
  	    {
  	      struct data_reference *res;
! 	      res = XCNEW (struct data_reference);
  	      VEC_safe_push (data_reference_p, heap, *datarefs, res);
  
  	      free (bbs);
*************** compute_data_dependences_for_loop (struc
*** 5155,5161 ****
  				   VEC (data_reference_p, heap) **datarefs,
  				   VEC (ddr_p, heap) **dependence_relations)
  {
-   struct loop *loop_nest = loop;
    VEC (loop_p, heap) *vloops = VEC_alloc (loop_p, heap, 3);
  
    memset (&dependence_stats, 0, sizeof (dependence_stats));
--- 4036,4041 ----
*************** compute_data_dependences_for_loop (struc
*** 5163,5170 ****
    /* If the loop nest is not well formed, or one of the data references 
       is not computable, give up without spending time to compute other
       dependences.  */
!   if (!loop_nest
!       || !find_loop_nest (loop_nest, &vloops)
        || find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
      {
        struct data_dependence_relation *ddr;
--- 4043,4050 ----
    /* If the loop nest is not well formed, or one of the data references 
       is not computable, give up without spending time to compute other
       dependences.  */
!   if (!loop
!       || !find_loop_nest (loop, &vloops)
        || find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
      {
        struct data_dependence_relation *ddr;
*************** analyze_all_data_dependences (struct loo
*** 5287,5298 ****
  		{
  		  struct data_reference *a = DDR_A (ddr);
  		  struct data_reference *b = DDR_B (ddr);
! 		  bool differ_p;	
! 	      
! 		  if ((DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b)
! 		       && DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
! 		      || (base_object_differ_p (a, b, &differ_p) 
! 			  && differ_p))
  		    nb_basename_differ++;
  		  else
  		    nb_bot_relations++;
--- 4167,4174 ----
  		{
  		  struct data_reference *a = DDR_A (ddr);
  		  struct data_reference *b = DDR_B (ddr);
! 
! 		  if (!bitmap_intersect_p (DR_VOPS (a), DR_VOPS (b)))
  		    nb_basename_differ++;
  		  else
  		    nb_bot_relations++;
*************** free_dependence_relations (VEC (ddr_p, h
*** 5364,5369 ****
--- 4240,4255 ----
    VEC_free (ddr_p, heap, dependence_relations);
  }
  
+ /* Frees data reference DR.  */
+ 
+ static void
+ free_data_ref (data_reference_p dr)
+ {
+   BITMAP_FREE (DR_VOPS (dr));
+   VEC_free (tree, heap, DR_ACCESS_FNS (dr));
+   free (dr);
+ }
+ 
  /* Free the memory used by the data references from DATAREFS.  */
  
  void
Index: tree-data-ref.h
===================================================================
*** tree-data-ref.h	(revision 124559)
--- tree-data-ref.h	(working copy)
*************** Software Foundation, 51 Franklin Street,
*** 26,73 ****
  #include "omega.h"
  
  /*
!   The first location accessed by data-ref in the loop is the address of data-ref's 
!   base (BASE_ADDRESS) plus the initial offset from the base. We divide the initial offset 
!   into two parts: loop invariant offset (OFFSET) and constant offset (INIT). 
!   STEP is the stride of data-ref in the loop in bytes.
  
                         Example 1                      Example 2
!       data-ref         a[j].b[i][j]                   a + x + 16B (a is int*)
        
!   First location info:
!       base_address     &a                             a
!       offset           j_0*D_j + i_0*D_i              x
!       init             C_b + C_a                      16
        step             D_j                            4
-       access_fn        NULL                           {16, +, 1}
- 
-   Base object info:
-       base_object      a                              NULL
-       access_fn        <access_fns of indexes of b>   NULL
  
    */
! struct first_location_in_loop
  {
    tree base_address;
    tree offset;
    tree init;
    tree step;
!   /* Access function related to first location in the loop.  */
!   VEC(tree,heap) *access_fns;
  };
  
! struct base_object_info
  {
    /* The object.  */
    tree base_object;
    
!   /* A list of chrecs.  Access functions related to BASE_OBJECT.  */
    VEC(tree,heap) *access_fns;
  };
  
! enum data_ref_type {
!   ARRAY_REF_TYPE,
!   POINTER_REF_TYPE
  };
  
  struct data_reference
--- 26,98 ----
  #include "omega.h"
  
  /*
!   innermost_loop_behavior describes the evolution of the address of the memory
!   reference in the innermost enclosing loop.  The address is expressed as
!   BASE + STEP * # of iteration, and base is further decomposed as the base
!   pointer (BASE_ADDRESS),  loop invariant offset (OFFSET) and
!   constant offset (INIT).  Examples, in loop nest 
!   
!   for (i = 0; i < 100; i++)
!     for (j = 3; j < 100; j++)
  
                         Example 1                      Example 2
!       data-ref         a[j].b[i][j]                   *(p + x + 16B + 4B * j)
        
!   innermost_loop_behavior
!       base_address     &a                             p
!       offset           i * D_i			      x
!       init             3 * D_j + offsetof (b)         28
        step             D_j                            4
  
    */
! struct innermost_loop_behavior
  {
    tree base_address;
    tree offset;
    tree init;
    tree step;
! 
!   /* Alignment information.  ALIGNED_TO is set to the largest power of two
!      that divides OFFSET.  */
!   tree aligned_to;
  };
  
! /* Describes the evolutions of indices of the memory reference.  The indices
!    are indices of the ARRAY_REFs and the operands of INDIRECT_REFs.
!    For ARRAY_REFs, BASE_OBJECT is the reference with zeroed indices
!    (note that this reference does not have to be valid, if zero does not
!    belong to the range of the array; hence it is not recommended to use
!    BASE_OBJECT in any code generation).  For INDIRECT_REFs, the address is
!    set to the loop-invariant part of the address of the object, except for
!    the constant offset.  For the examples above,
! 
!    base_object:        a[0].b[0][0]                   *(p + x + 4B * j_0)
!    indices:            {j_0, +, 1}_2                  {16, +, 4}_2
! 		       {i_0, +, 1}_1
! 		       {j_0, +, 1}_2
! */
! 
! struct indices
  {
    /* The object.  */
    tree base_object;
    
!   /* A list of chrecs.  Access functions of the indices.  */
    VEC(tree,heap) *access_fns;
  };
  
! struct dr_alias
! {
!   /* The alias information that should be used for new pointers to this
!      location.  SYMBOL_TAG is either a DECL or a SYMBOL_MEMORY_TAG.  */
!   tree symbol_tag;
!   subvar_t subvars;
!   struct ptr_info_def *ptr_info;
! 
!   /* The set of virtual operands corresponding to this memory reference,
!      serving as a description of the alias information for the memory
!      reference.  This could be eliminated if we had alias oracle.  */
!   bitmap vops;
  };
  
  struct data_reference
*************** struct data_reference
*** 75,81 ****
    /* A pointer to the statement that contains this DR.  */
    tree stmt;
    
!   /* A pointer to the ARRAY_REF node.  */
    tree ref;
  
    /* Auxiliary info specific to a pass.  */
--- 100,106 ----
    /* A pointer to the statement that contains this DR.  */
    tree stmt;
    
!   /* A pointer to the memory reference.  */
    tree ref;
  
    /* Auxiliary info specific to a pass.  */
*************** struct data_reference
*** 84,141 ****
    /* True when the data reference is in RHS of a stmt.  */
    bool is_read;
  
!   /* First location accessed by the data-ref in the loop.  */
!   struct first_location_in_loop first_location;
  
!   /* Base object related info.  */
!   struct base_object_info object_info;
  
!   /* Aliasing information.  This field represents the symbol that
!      should be aliased by a pointer holding the address of this data
!      reference.  If the original data reference was a pointer
!      dereference, then this field contains the memory tag that should
!      be used by the new vector-pointer.  */
!   tree memtag;
!   struct ptr_info_def *ptr_info;
!   subvar_t subvars;
! 
!   /* Alignment information.  
!      MISALIGNMENT is the offset of the data-reference from its base in bytes.
!      ALIGNED_TO is the maximum data-ref's alignment.  
! 
!      Example 1, 
!        for i
!           for (j = 3; j < N; j++)
!             a[j].b[i][j] = 0;
! 	 
!      For a[j].b[i][j], the offset from base (calculated in get_inner_reference() 
!      will be 'i * C_i + j * C_j + C'. 
!      We try to substitute the variables of the offset expression
!      with initial_condition of the corresponding access_fn in the loop.
!      'i' cannot be substituted, since its access_fn in the inner loop is i. 'j' 
!      will be substituted with 3. 
! 
!      Example 2
!         for (j = 3; j < N; j++)
!           a[j].b[5][j] = 0; 
! 
!      Here the offset expression (j * C_j + C) will not contain variables after
!      substitution of j=3 (3*C_j + C).
! 
!      Misalignment can be calculated only if all the variables can be 
!      substituted with constants, otherwise, we record maximum possible alignment
!      in ALIGNED_TO. In Example 1, since 'i' cannot be substituted, 
!      MISALIGNMENT will be NULL_TREE, and the biggest divider of C_i (a power of 
!      2) will be recorded in ALIGNED_TO.
! 
!      In Example 2, MISALIGNMENT will be the value of 3*C_j + C in bytes, and 
!      ALIGNED_TO will be NULL_TREE.
!   */
!   tree misalignment;
!   tree aligned_to;
! 
!   /* The type of the data-ref.  */
!   enum data_ref_type type;
  };
  
  typedef struct data_reference *data_reference_p;
--- 109,122 ----
    /* True when the data reference is in RHS of a stmt.  */
    bool is_read;
  
!   /* Behavior of the memory reference in the innermost loop.  */
!   struct innermost_loop_behavior innermost;
  
!   /* Decomposition to indices for alias analysis.  */
!   struct indices indices;
  
!   /* Alias information for the data reference.  */
!   struct dr_alias alias;
  };
  
  typedef struct data_reference *data_reference_p;
*************** DEF_VEC_ALLOC_P (data_reference_p, heap)
*** 144,180 ****
  
  #define DR_STMT(DR)                (DR)->stmt
  #define DR_REF(DR)                 (DR)->ref
! #define DR_BASE_OBJECT(DR)         (DR)->object_info.base_object
! #define DR_TYPE(DR)                (DR)->type
! #define DR_ACCESS_FNS(DR)\
!   (DR_TYPE(DR) == ARRAY_REF_TYPE ?  \
!    (DR)->object_info.access_fns : (DR)->first_location.access_fns)
  #define DR_ACCESS_FN(DR, I)        VEC_index (tree, DR_ACCESS_FNS (DR), I)
  #define DR_NUM_DIMENSIONS(DR)      VEC_length (tree, DR_ACCESS_FNS (DR))  
  #define DR_IS_READ(DR)             (DR)->is_read
! #define DR_BASE_ADDRESS(DR)        (DR)->first_location.base_address
! #define DR_OFFSET(DR)              (DR)->first_location.offset
! #define DR_INIT(DR)                (DR)->first_location.init
! #define DR_STEP(DR)                (DR)->first_location.step
! #define DR_MEMTAG(DR)              (DR)->memtag
! #define DR_ALIGNED_TO(DR)          (DR)->aligned_to
! #define DR_OFFSET_MISALIGNMENT(DR) (DR)->misalignment
! #define DR_PTR_INFO(DR)            (DR)->ptr_info
! #define DR_SUBVARS(DR)             (DR)->subvars
! #define DR_SET_ACCESS_FNS(DR, ACC_FNS)         \
! {                                              \
!   if (DR_TYPE(DR) == ARRAY_REF_TYPE)           \
!     (DR)->object_info.access_fns = ACC_FNS;    \
!   else                                         \
!     (DR)->first_location.access_fns = ACC_FNS; \
! }
! #define DR_FREE_ACCESS_FNS(DR)                              \
! {                                                           \
!   if (DR_TYPE(DR) == ARRAY_REF_TYPE)                        \
!     VEC_free (tree, heap, (DR)->object_info.access_fns);    \
!   else                                                      \
!     VEC_free (tree, heap, (DR)->first_location.access_fns); \
! }
  
  enum data_dependence_direction {
    dir_positive, 
--- 125,144 ----
  
  #define DR_STMT(DR)                (DR)->stmt
  #define DR_REF(DR)                 (DR)->ref
! #define DR_BASE_OBJECT(DR)         (DR)->indices.base_object
! #define DR_ACCESS_FNS(DR)	   (DR)->indices.access_fns
  #define DR_ACCESS_FN(DR, I)        VEC_index (tree, DR_ACCESS_FNS (DR), I)
  #define DR_NUM_DIMENSIONS(DR)      VEC_length (tree, DR_ACCESS_FNS (DR))  
  #define DR_IS_READ(DR)             (DR)->is_read
! #define DR_BASE_ADDRESS(DR)        (DR)->innermost.base_address
! #define DR_OFFSET(DR)              (DR)->innermost.offset
! #define DR_INIT(DR)                (DR)->innermost.init
! #define DR_STEP(DR)                (DR)->innermost.step
! #define DR_SYMBOL_TAG(DR)          (DR)->alias.symbol_tag
! #define DR_PTR_INFO(DR)            (DR)->alias.ptr_info
! #define DR_SUBVARS(DR)             (DR)->alias.subvars
! #define DR_VOPS(DR)		   (DR)->alias.vops
! #define DR_ALIGNED_TO(DR)          (DR)->innermost.aligned_to
  
  enum data_dependence_direction {
    dir_positive, 
*************** DEF_VEC_O (data_ref_loc);
*** 335,342 ****
  DEF_VEC_ALLOC_O (data_ref_loc, heap);
  
  bool get_references_in_stmt (tree, VEC (data_ref_loc, heap) **);
- extern tree find_data_references_in_loop (struct loop *,
- 					  VEC (data_reference_p, heap) **);
  extern void compute_data_dependences_for_loop (struct loop *, bool,
  					       VEC (data_reference_p, heap) **,
  					       VEC (ddr_p, heap) **);
--- 299,304 ----
Index: tree-vect-analyze.c
===================================================================
*** tree-vect-analyze.c	(revision 124559)
--- tree-vect-analyze.c	(working copy)
*************** vect_compute_data_ref_alignment (struct 
*** 1130,1144 ****
    /* Initialize misalignment to unknown.  */
    DR_MISALIGNMENT (dr) = -1;
  
!   misalign = DR_OFFSET_MISALIGNMENT (dr);
    aligned_to = DR_ALIGNED_TO (dr);
    base_addr = DR_BASE_ADDRESS (dr);
    base = build_fold_indirect_ref (base_addr);
    vectype = STMT_VINFO_VECTYPE (stmt_info);
    alignment = ssize_int (TYPE_ALIGN (vectype)/BITS_PER_UNIT);
  
!   if ((aligned_to && tree_int_cst_compare (aligned_to, alignment) < 0)
!       || !misalign)
      {
        if (vect_print_dump_info (REPORT_DETAILS))
  	{
--- 1130,1143 ----
    /* Initialize misalignment to unknown.  */
    DR_MISALIGNMENT (dr) = -1;
  
!   misalign = DR_INIT (dr);
    aligned_to = DR_ALIGNED_TO (dr);
    base_addr = DR_BASE_ADDRESS (dr);
    base = build_fold_indirect_ref (base_addr);
    vectype = STMT_VINFO_VECTYPE (stmt_info);
    alignment = ssize_int (TYPE_ALIGN (vectype)/BITS_PER_UNIT);
  
!   if (tree_int_cst_compare (aligned_to, alignment) < 0)
      {
        if (vect_print_dump_info (REPORT_DETAILS))
  	{
*************** vect_analyze_data_refs (loop_vec_info lo
*** 2044,2050 ****
              }
            return false;
          }
!       if (!DR_MEMTAG (dr))
          {
            if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
              {
--- 2043,2049 ----
              }
            return false;
          }
!       if (!DR_SYMBOL_TAG (dr))
          {
            if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
              {
Index: tree-vect-transform.c
===================================================================
*** tree-vect-transform.c	(revision 124559)
--- tree-vect-transform.c	(working copy)
*************** vect_create_data_ref_ptr (tree stmt,
*** 298,304 ****
    /** (2) Add aliasing information to the new vector-pointer:
            (The points-to info (DR_PTR_INFO) may be defined later.)  **/
    
!   tag = DR_MEMTAG (dr);
    gcc_assert (tag);
  
    /* If tag is a variable (and NOT_A_TAG) than a new symbol memory
--- 298,304 ----
    /** (2) Add aliasing information to the new vector-pointer:
            (The points-to info (DR_PTR_INFO) may be defined later.)  **/
    
!   tag = DR_SYMBOL_TAG (dr);
    gcc_assert (tag);
  
    /* If tag is a variable (and NOT_A_TAG) than a new symbol memory


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]