[patch] Externalize data-ref analysis - part 1

[Ira Rosen <IRAR at il dot ibm dot com>]

This is the first part - of generalization/externalization data-ref
analysis from the vectorizer.
The patch also adds a support for INDIRECT_REFS, improves data-refs bases
comparison for data-dependence tests,
and fixes PR21218 and PR19049. This is a merge from autovect branch.
Testcases are attached (to the second part of the patch).

In this part of the patch functions that are responsible for extraction of
base address, offset, step, misalignment and aliasing info for data-ref are
moved from tree-vect-analyze.c to tree-data-ref.c, along with a new API
create_data_ref. The function find_data_references_in_loop now calls
create_data_ref to find the data-refs, i.e., the general data-ref analysis
now uses the analysis originally developed for the vectorizer.
The above fields (base address, etc.) are moved from stmt_vec_info
structure to data_reference structure.

Data references analysis (including data dependence tests) was originally
developed for ARRAY_REFs. In order to handle INDIRECT_REFs this analysis
must be adapted. A DR representation is now divided in two parts:

(1) Information about BASE_OBJECT and access_fns used to represent
evolution relative to BASE_OBJECT. This was the original meaning of the DR
access_fns, when the data-reference analysis was written, with the original
intention to support arrays. For example, for a reference 'a.b[i][j]', the
BASE_OBJECT is 'a.b' and the access_fns is a list of access-functions, one
for each array subscript: '{i_init, + i_step}_1, {j_init, +, j_step}_2'.

(2) Information about first location accessed by DR in the loop and
access_fn used to represent evolution relative to this location. This was
introduced when we added support for pointers. Pointer accesses are
represented as a one-dimensional access that starts from the first location
accessed in the loop. Usually we don't know which object a pointer is
referring to, or can't prove that the access is confined to the boundaries
of a certain object. We don't use the access_fn this way for arrays (for
which we have BASE_OBJECT), but we do use the access_fn this way for
pointers - for example:
      for i
         for j
          *((int *)p + i + j) = a[i][j];
       The access function of the pointer access is {0, + 4B}_2 relative to
'p + i'.
      The access functions of the array are '{i_init, + i_step}_1 and
{j_init, +, j_step}_2' relative to 'a'.

We can compare two DRs only if at least one of these two representations
has all its fields filled for both DRs. One important thing to note though,
is that even though we can always fill in all the "first-location" fields,
that doesn't always help us to compare two references, because the
data-dependence engine handles only constant and affine access functions.

So we either need to extend the data-dependence tests engine to compare
non-constant access-fns, or, try to represent pointers the same way arrays
are represented (e.g. - access_fn for each "dimension", etc). This is not
trivial to do (with Daniel's patch it would at least be easier for pointer
accesses that look like ARRAY_REFs to begin with).

Our current strategy for data dependence tests is as follows:
if (both a and b are represented as arrays)
      compare a.base_object and b.base_object
            if equal, apply dependence tests
            (use access functions based on base_objects)
else if (both a and b are represented as pointers)
      compare a.first_location and b.first_location
            if equal, apply dependence tests
            (use access functions based on first location)
else if (a and b are represented differently)
      only try to prove that the bases are surely different


Bootstrapped and tested on ppc-darwin (several vectorizer tests fail
without the second part of the patch).

O.K. for mainline?

Thanks,
Ira

ChangeLog entry:
      * tree-data-ref.c (array_base_name_differ_p): Make static. Use a
correct
      field name.
      (base_addr_differ_p): Moved from tree-vect-analyze.c.
      (dump_data_reference): Use a correct field name.
      (analyze_array): Make static. Initialize new data-ref fields.
      (analyze_indirect_ref): New function.
      (init_data_ref): Initialize new data-ref fields.
      (strip_conversion): Moved from tree-vect-analyze.c.
      (analyze_offset_expr, get_ptr_offset, address_analysis,
object_analysis):
      Likewise.
      (analyze_offset): New function.
      (create_data_ref): Likewise.
      (initialize_data_dependence_relation): Call base_addr_differ_p.
Compare
      dimensions for ARRAY_REFs only.
      (build_classic_dist_vector): Make static.
      (access_functions_are_affine_or_constant_p): Call macro to get the
      address of access functions.
      (compute_all_dependences): Add new parameter
      compute_self_and_read_read_dependences. Compute self and read-read
      dependences if it is true.
      (find_data_references_in_loop): Add new parameter alignment. Call
      create_data_ref. Initialize new data-ref fields.
      (compute_data_dependences_for_loop): Add new parameters alignment
      and compute_self_and_read_read_dependences. Remove parameter
nb_loops,
      compute nb_loops. Call find_data_references_in_loop,
      compute_all_dependences, build_classic_dist_vector and
      build_classic_dir_vector with correct parameters.
      (analyze_all_data_dependences): Call
compute_data_dependences_for_loop with
      correct parameters. Compare dimensions for ARRAY_REFs only.
      (free_data_refs): Call macro to free access functions.
      * tree-data-ref.h (struct first_location_in_loop): New structure.
Move
      fields from stmt_vinfo.
      (struct base_object_info): New structure.
      (struct data_reference): Move fields to base_object_info. Add fields
      first_location and object_info for above structures. Move fields from
      stmt_info: memtag, ptr_info, subvars, base_aligned, misalignment.
      Add macros to access the new fields.
      Update functions declarations.
      * tree-loop-linear.c (linear_transform_loops): Call
      compute_data_dependences_for_loop with correct parameters.
      * tree-ssa-loop-niter.c (estimate_numbers_of_iterations_loop): Call
      find_data_references_in_loop with correct parameters.
      * tree-vect-analyze.c (vect_get_ptr_offset): Remove.
      (vect_analyze_offset_expr, vect_base_addr_differ_p): Likewise.
      (vect_analyze_data_ref_dependence): Get ddr. Remove call to
      vect_base_addr_differ_p, compute_subscript_distance and
      build_classic_dist_vector. Add printings. Check absolute value of
      distance.
      (vect_analyze_data_ref_dependences): Go through ddrs instead of
data-refs.
      (vect_compute_data_ref_alignment): Get the fields of data-ref instead
of
      stmt. Remove conversion to bytes. Add printing.
      (vect_compute_data_refs_alignment): Go through loads and stores in
one loop.
      (vect_enhance_data_refs_alignment, vect_analyze_data_refs_alignment,
      vect_analyze_data_ref_access): Likewise.
      (vect_analyze_pointer_ref_access): Remove.
      (vect_address_analysis, vect_object_analysis): Likewise.
      (vect_analyze_data_refs): Call compute_data_dependences_for_loop to
find
      and analyze data-refs in the loop.
      * tree-vect-transform.c (vect_create_addr_base_for_vector_ref): Get
the
      fields of data-ref instead of stmt. Add init to the offset from the
base.
      (vect_create_data_ref_ptr): Get the fields of data-ref instead of
stmt.
      (vect_update_init_of_dr): Likewise.
      (vect_update_inits_of_drs): Go through loads and stores in one loop.
      * tree-vectorizer.c (new_stmt_vec_info): Remove initialization of
removed
      fields.
      (new_loop_vec_info): Initialize new fields.
      (destroy_loop_vec_info): Free new fields.
      (vect_strip_conversion): Remove.
      * tree-vectorizer.h (enum verbosity_levels): Add new verbosity level.
      (struct _loop_vec_info): Unify data_ref_writes and data_ref_reads
into
      datarefs. Add new field ddrs.
      Add macros for the new fields access.
      (struct _stmt_vec_info): Remove: base_address, initial_offset, step,
      base_aligned_p, misalignment, memtag, ptr_info and subvars.
      Remove their macros.

Patch (part 1):

(See attached file: dr.patch1)

Attachment: dr.patch1
Description: Binary data