* Re: Insertng a call function
2005-07-29 14:52 ` Diego Novillo
@ 2005-07-29 15:06 ` drizzle drizzle
2005-07-29 15:21 ` Diego Novillo
0 siblings, 1 reply; 7+ messages in thread
From: drizzle drizzle @ 2005-07-29 15:06 UTC (permalink / raw)
To: Diego Novillo; +Cc: gcc
[-- Attachment #1: Type: text/plain, Size: 830 bytes --]
Here is the patch, an header file, the test case. The only thing I
need is be able to insert a function call inside
linear-loop-transform. The error message I get is
main.c:15: internal compiler error: in var_ann, at tree-flow-inline.h:36
thanks
On 7/29/05, Diego Novillo <dnovillo@redhat.com> wrote:
> On Fri, Jul 29, 2005 at 10:27:21AM -0400, drizzle drizzle wrote:
>
> > Could it be that it being done lower in the pass unlike insertions in
> > tree-profile, gomp - some ssa defintion information is missing. The
> > reason I have been led to think is because it fails
> > register_new_defintions. I would appreciate any suggestions.
> >
> Very many things could be wrong. You'll need to show us the
> exact patch you are testing, with a test case and the exact error
> message you are getting.
>
[-- Attachment #2: patch --]
[-- Type: application/octet-stream, Size: 202597 bytes --]
--- tree.h 2005-07-27 14:37:35.000000000 -0400
+++ tree.hmodified 2005-07-29 10:59:50.000000000 -0400
@@ -259,7 +259,7 @@
tree chain;
tree type;
union tree_ann_d *ann;
-
+ int refid;
ENUM_BITFIELD(tree_code) code : 8;
unsigned side_effects_flag : 1;
--- tree-loop-linear.c 2005-07-27 14:37:27.000000000 -0400
+++ tree-loop-linear.cmodified 2005-07-29 10:59:12.000000000 -0400
@@ -1,6 +1,6 @@
-/* Linear Loop transforms
+/* Data references and dependences detectors.
Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
- Contributed by Daniel Berlin <dberlin@dberlin.org>.
+ Contributed by Sebastian Pop <s.pop@laposte.net>
This file is part of GCC.
@@ -19,6 +19,60 @@
Software Foundation, 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA. */
+/* This pass walks a given loop structure searching for array
+ references. The information about the array accesses is recorded
+ in DATA_REFERENCE structures.
+
+ The basic test for determining the dependences is:
+ given two access functions chrec1 and chrec2 to a same array, and
+ x and y two vectors from the iteration domain, the same element of
+ the array is accessed twice at iterations x and y if and only if:
+ | chrec1 (x) == chrec2 (y).
+
+ The goals of this analysis are:
+
+ - to determine the independence: the relation between two
+ independent accesses is qualified with the chrec_known (this
+ information allows a loop parallelization),
+
+ - when two data references access the same data, to qualify the
+ dependence relation with classic dependence representations:
+
+ - distance vectors
+ - direction vectors
+ - loop carried level dependence
+ - polyhedron dependence
+ or with the chains of recurrences based representation,
+
+ - to define a knowledge base for storing the data dependence
+ information,
+
+ - to define an interface to access this data.
+
+
+ Definitions:
+
+ - subscript: given two array accesses a subscript is the tuple
+ composed of the access functions for a given dimension. Example:
+ Given A[f1][f2][f3] and B[g1][g2][g3], there are three subscripts:
+ (f1, g1), (f2, g2), (f3, g3).
+
+ - Diophantine equation: an equation whose coefficients and
+ solutions are integer constants, for example the equation
+ | 3*x + 2*y = 1
+ has an integer solution x = 1 and y = -1.
+
+ References:
+
+ - "Advanced Compilation for High Performance Computing" by Randy
+ Allen and Ken Kennedy.
+ http://citeseer.ist.psu.edu/goff91practical.html
+
+ - "Loop Transformations for Restructuring Compilers - The Foundations"
+ by Utpal Banerjee.
+
+
+*/
#include "config.h"
#include "system.h"
@@ -27,8 +81,8 @@
#include "errors.h"
#include "ggc.h"
#include "tree.h"
-#include "target.h"
+/* These RTL headers are needed for basic-block.h. */
#include "rtl.h"
#include "basic-block.h"
#include "diagnostic.h"
@@ -36,347 +90,3540 @@
#include "tree-dump.h"
#include "timevar.h"
#include "cfgloop.h"
-#include "expr.h"
-#include "optabs.h"
#include "tree-chrec.h"
#include "tree-data-ref.h"
#include "tree-scalar-evolution.h"
#include "tree-pass.h"
-#include "varray.h"
-#include "lambda.h"
-/* Linear loop transforms include any composition of interchange,
- scaling, skewing, and reversal. They are used to change the
- iteration order of loop nests in order to optimize data locality of
- traversals, or remove dependences that prevent
- parallelization/vectorization/etc.
-
- TODO: Determine reuse vectors/matrix and use it to determine optimal
- transform matrix for locality purposes.
- TODO: Completion of partial transforms. */
-
-/* Gather statistics for loop interchange. LOOP is the loop being
- considered. The first loop in the considered loop nest is
- FIRST_LOOP, and consequently, the index of the considered loop is
- obtained by LOOP->DEPTH - FIRST_LOOP->DEPTH
-
- Initializes:
- - DEPENDENCE_STEPS the sum of all the data dependence distances
- carried by loop LOOP,
-
- - NB_DEPS_NOT_CARRIED_BY_LOOP the number of dependence relations
- for which the loop LOOP is not carrying any dependence,
-
- - ACCESS_STRIDES the sum of all the strides in LOOP.
-
- Example: for the following loop,
-
- | loop_1 runs 1335 times
- | loop_2 runs 1335 times
- | A[{{0, +, 1}_1, +, 1335}_2]
- | B[{{0, +, 1}_1, +, 1335}_2]
- | endloop_2
- | A[{0, +, 1336}_1]
- | endloop_1
-
- gather_interchange_stats (in loop_1) will return
- DEPENDENCE_STEPS = 3002
- NB_DEPS_NOT_CARRIED_BY_LOOP = 5
- ACCESS_STRIDES = 10694
-
- gather_interchange_stats (in loop_2) will return
- DEPENDENCE_STEPS = 3000
- NB_DEPS_NOT_CARRIED_BY_LOOP = 7
- ACCESS_STRIDES = 8010
-*/
-static void
-gather_interchange_stats (varray_type dependence_relations,
- varray_type datarefs,
- struct loop *loop,
- struct loop *first_loop,
- unsigned int *dependence_steps,
- unsigned int *nb_deps_not_carried_by_loop,
- unsigned int *access_strides)
+// ADDED_SK
+
+
+#include "dynprof.h"
+int groupid=1;
+int refid=1;
+
+//extern int* iterations_estimate;
+//extern FILE* refFile;
+//extern FILE* refinfo;
+//extern int timestamp_flag;
+
+/* 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. */
+
+bool
+array_base_name_differ_p (struct data_reference *a,
+ struct data_reference *b,
+ bool *differ_p)
{
- unsigned int i;
+ tree base_a = DR_BASE_NAME (a);
+ tree base_b = DR_BASE_NAME (b);
+ tree ta, tb;
- *dependence_steps = 0;
- *nb_deps_not_carried_by_loop = 0;
- *access_strides = 0;
+ if (!base_a || !base_b)
+ return false;
- for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
+ ta = TREE_TYPE (base_a);
+ tb = TREE_TYPE (base_b);
+
+ /* 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)
{
- int dist;
- struct data_dependence_relation *ddr =
- (struct data_dependence_relation *)
- VARRAY_GENERIC_PTR (dependence_relations, i);
+ *differ_p = false;
+ return true;
+ }
- /* If we don't know anything about this dependence, or the distance
- vector is NULL, or there is no dependence, then there is no reuse of
- data. */
-
- if (DDR_DIST_VECT (ddr) == NULL
- || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know
- || DDR_ARE_DEPENDENT (ddr) == chrec_known)
- continue;
-
+ /* 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;
+ }
-
- dist = DDR_DIST_VECT (ddr)[loop->depth - first_loop->depth];
- if (dist == 0)
- (*nb_deps_not_carried_by_loop) += 1;
- else if (dist < 0)
- (*dependence_steps) += -dist;
- else
- (*dependence_steps) += dist;
+ /* 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;
+ }
+
+ /* 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 and an array access. */
+ if ((TREE_CODE (base_a) == VAR_DECL
+ && (TREE_CODE (base_b) == COMPONENT_REF
+ && TREE_CODE (TREE_OPERAND (base_b, 0)) == VAR_DECL))
+ || (TREE_CODE (base_b) == VAR_DECL
+ && (TREE_CODE (base_a) == COMPONENT_REF
+ && TREE_CODE (TREE_OPERAND (base_a, 0)) == VAR_DECL)))
+ {
+ *differ_p = true;
+ return true;
+ }
+
+ return false;
+}
+
+/* Returns true iff A divides B. */
+
+static inline bool
+tree_fold_divides_p (tree type,
+ tree a,
+ tree b)
+{
+ /* Determines whether (A == gcd (A, B)). */
+ return integer_zerop
+ (fold (build (MINUS_EXPR, type, a, tree_fold_gcd (a, b))));
+}
+
+/* Compute the greatest common denominator of two numbers using
+ Euclid's algorithm. */
+
+static int
+gcd (int a, int b)
+{
+
+ int x, y, z;
+
+ x = abs (a);
+ y = abs (b);
+
+ while (x>0)
+ {
+ z = y % x;
+ y = x;
+ x = z;
}
- /* Compute the access strides. */
+ return (y);
+}
+
+/* Returns true iff A divides B. */
+
+static inline bool
+int_divides_p (int a, int b)
+{
+ return ((b % a) == 0);
+}
+
+\f
+
+/* Dump into FILE all the data references from DATAREFS. */
+
+void
+dump_data_references (FILE *file,
+ varray_type datarefs)
+{
+ unsigned int i;
+
for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
+ dump_data_reference (file, VARRAY_GENERIC_PTR (datarefs, i));
+}
+
+/* Dump into FILE all the dependence relations from DDR. */
+
+void
+dump_data_dependence_relations (FILE *file,
+ varray_type ddr)
+{
+ unsigned int i;
+
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (ddr); i++)
+ dump_data_dependence_relation (file, VARRAY_GENERIC_PTR (ddr, i));
+}
+
+/* Dump function for a DATA_REFERENCE structure. */
+
+void
+dump_data_reference (FILE *outf,
+ struct data_reference *dr)
+{
+ unsigned int i;
+
+ fprintf (outf, "(Data Ref: \n stmt: ");
+ print_generic_stmt (outf, DR_STMT (dr), 0);
+ // fprintf(outf," Statement line number %d \n",dr->stmt->exp.common.refid);
+ fprintf (outf, " ref: ");
+ print_generic_stmt (outf, DR_REF (dr), 0);
+ fprintf (outf, " base_name: ");
+ print_generic_stmt (outf, DR_BASE_NAME (dr), 0);
+
+ for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
{
- unsigned int it;
- struct data_reference *dr = VARRAY_GENERIC_PTR (datarefs, i);
- tree stmt = DR_STMT (dr);
- struct loop *stmt_loop = loop_containing_stmt (stmt);
- struct loop *inner_loop = first_loop->inner;
-
- if (inner_loop != stmt_loop
- && !flow_loop_nested_p (inner_loop, stmt_loop))
- continue;
- for (it = 0; it < DR_NUM_DIMENSIONS (dr); it++)
- {
- tree chrec = DR_ACCESS_FN (dr, it);
- tree tstride = evolution_part_in_loop_num
- (chrec, loop->num);
-
- if (tstride == NULL_TREE
- || TREE_CODE (tstride) != INTEGER_CST)
- continue;
+ fprintf (outf, " Access function %d: ", i);
+ print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0);
+ }
+
+ fprintf (outf, ")\n");
+ // fprintf (outf, "the loop where this was found %d\n",dr->num);
+
+}
+
+/* Dump function for a SUBSCRIPT structure. */
+
+void
+dump_subscript (FILE *outf, struct subscript *subscript)
+{
+ tree chrec = SUB_CONFLICTS_IN_A (subscript);
+
+ fprintf (outf, "\n (subscript \n");
+ fprintf (outf, " iterations_that_access_an_element_twice_in_A: ");
+ print_generic_stmt (outf, chrec, 0);
+ if (chrec == chrec_known)
+ fprintf (outf, " (no dependence)\n");
+ else if (chrec_contains_undetermined (chrec))
+ fprintf (outf, " (don't know)\n");
+ else
+ {
+ tree last_iteration = SUB_LAST_CONFLICT (subscript);
+ fprintf (outf, " last_conflict: ");
+ print_generic_stmt (outf, last_iteration, 0);
+ }
- (*access_strides) += int_cst_value (tstride);
+ chrec = SUB_CONFLICTS_IN_B (subscript);
+ fprintf (outf, " iterations_that_access_an_element_twice_in_B: ");
+ print_generic_stmt (outf, chrec, 0);
+ if (chrec == chrec_known)
+ fprintf (outf, " (no dependence)\n");
+ else if (chrec_contains_undetermined (chrec))
+ fprintf (outf, " (don't know)\n");
+ else
+ {
+ tree last_iteration = SUB_LAST_CONFLICT (subscript);
+ fprintf (outf, " last_conflict: ");
+ print_generic_stmt (outf, last_iteration, 0);
+ }
+
+ fprintf (outf, " (Subscript distance: ");
+ print_generic_stmt (outf, SUB_DISTANCE (subscript), 0);
+ fprintf (outf, " )\n");
+ fprintf (outf, " )\n");
+}
+
+/* Dump function for a DATA_DEPENDENCE_RELATION structure. */
+
+void
+dump_data_dependence_relation (FILE *outf,
+ struct data_dependence_relation *ddr)
+{
+ struct data_reference *dra, *drb;
+
+ dra = DDR_A (ddr);
+ drb = DDR_B (ddr);
+ fprintf (outf, "(Data Dep: \n");
+ if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
+ fprintf (outf, " (don't know)\n");
+
+ else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
+ fprintf (outf, " (no dependence)\n");
+
+ else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
+ {
+ unsigned int i;
+ for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
+ {
+ fprintf (outf, " access_fn_A: ");
+ print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0);
+ fprintf (outf, " access_fn_B: ");
+ print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0);
+ dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
+ }
+ if (DDR_DIST_VECT (ddr))
+ {
+ fprintf (outf, " distance_vect: ");
+ print_lambda_vector (outf, DDR_DIST_VECT (ddr), DDR_SIZE_VECT (ddr));
+ }
+ if (DDR_DIR_VECT (ddr))
+ {
+ fprintf (outf, " direction_vect: ");
+ print_lambda_vector (outf, DDR_DIR_VECT (ddr), DDR_SIZE_VECT (ddr));
}
}
+
+ fprintf (outf, ")\n");
}
-/* Attempt to apply interchange transformations to TRANS to maximize the
- spatial and temporal locality of the loop.
- Returns the new transform matrix. The smaller the reuse vector
- distances in the inner loops, the fewer the cache misses.
- FIRST_LOOP is the loop->num of the first loop in the analyzed loop
- nest. */
-
-
-static lambda_trans_matrix
-try_interchange_loops (lambda_trans_matrix trans,
- unsigned int depth,
- varray_type dependence_relations,
- varray_type datarefs,
- struct loop *first_loop)
-{
- struct loop *loop_i;
- struct loop *loop_j;
- unsigned int dependence_steps_i, dependence_steps_j;
- unsigned int access_strides_i, access_strides_j;
- unsigned int nb_deps_not_carried_by_i, nb_deps_not_carried_by_j;
- struct data_dependence_relation *ddr;
-
- /* When there is an unknown relation in the dependence_relations, we
- know that it is no worth looking at this loop nest: give up. */
- ddr = (struct data_dependence_relation *)
- VARRAY_GENERIC_PTR (dependence_relations, 0);
- if (ddr == NULL || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
- return trans;
-
- /* LOOP_I is always the outer loop. */
- for (loop_j = first_loop->inner;
- loop_j;
- loop_j = loop_j->inner)
- for (loop_i = first_loop;
- loop_i->depth < loop_j->depth;
- loop_i = loop_i->inner)
- {
- gather_interchange_stats (dependence_relations, datarefs,
- loop_i, first_loop,
- &dependence_steps_i,
- &nb_deps_not_carried_by_i,
- &access_strides_i);
- gather_interchange_stats (dependence_relations, datarefs,
- loop_j, first_loop,
- &dependence_steps_j,
- &nb_deps_not_carried_by_j,
- &access_strides_j);
-
- /* Heuristics for loop interchange profitability:
- 1. (spatial locality) Inner loops should have smallest
- dependence steps.
- 2. (spatial locality) Inner loops should contain more
- dependence relations not carried by the loop.
+/* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */
- 3. (temporal locality) Inner loops should have smallest
- array access strides.
- */
- if (dependence_steps_i < dependence_steps_j
- || nb_deps_not_carried_by_i > nb_deps_not_carried_by_j
- || access_strides_i < access_strides_j)
- {
- lambda_matrix_row_exchange (LTM_MATRIX (trans),
- loop_i->depth - first_loop->depth,
- loop_j->depth - first_loop->depth);
- /* Validate the resulting matrix. When the transformation
- is not valid, reverse to the previous transformation. */
- if (!lambda_transform_legal_p (trans, depth, dependence_relations))
- lambda_matrix_row_exchange (LTM_MATRIX (trans),
- loop_i->depth - first_loop->depth,
- loop_j->depth - first_loop->depth);
- }
- }
+void
+dump_data_dependence_direction (FILE *file,
+ enum data_dependence_direction dir)
+{
+ switch (dir)
+ {
+ case dir_positive:
+ fprintf (file, "+");
+ break;
+
+ case dir_negative:
+ fprintf (file, "-");
+ break;
+
+ case dir_equal:
+ fprintf (file, "=");
+ break;
+
+ case dir_positive_or_negative:
+ fprintf (file, "+-");
+ break;
+
+ case dir_positive_or_equal:
+ fprintf (file, "+=");
+ break;
+
+ case dir_negative_or_equal:
+ fprintf (file, "-=");
+ break;
+
+ case dir_star:
+ fprintf (file, "*");
+ break;
+
+ default:
+ break;
+ }
+}
+
+/* Dumps the distance and direction vectors in FILE. DDRS contains
+ the dependence relations, and VECT_SIZE is the size of the
+ dependence vectors, or in other words the number of loops in the
+ considered nest. */
+
+void
+dump_dist_dir_vectors (FILE *file, varray_type ddrs)
+{
+ unsigned int i;
- return trans;
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++)
+ {
+ struct data_dependence_relation *ddr =
+ (struct data_dependence_relation *)
+ VARRAY_GENERIC_PTR (ddrs, i);
+ if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
+ && DDR_AFFINE_P (ddr))
+ {
+ fprintf (file, "DISTANCE_V (");
+ print_lambda_vector (file, DDR_DIST_VECT (ddr), DDR_SIZE_VECT (ddr));
+ fprintf (file, ")\n");
+ fprintf (file, "DIRECTION_V (");
+ print_lambda_vector (file, DDR_DIR_VECT (ddr), DDR_SIZE_VECT (ddr));
+ fprintf (file, ")\n");
+ }
+ }
+ fprintf (file, "\n\n");
}
-/* Perform a set of linear transforms on LOOPS. */
+/* Dumps the data dependence relations DDRS in FILE. */
-void
-linear_transform_loops (struct loops *loops)
+void
+dump_ddrs (FILE *file, varray_type ddrs)
{
unsigned int i;
+
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++)
+ {
+ struct data_dependence_relation *ddr =
+ (struct data_dependence_relation *)
+ VARRAY_GENERIC_PTR (ddrs, i);
+ dump_data_dependence_relation (file, ddr);
+ }
+ fprintf (file, "\n\n");
+}
+
+\f
+
+/* Compute the lowest iteration bound for LOOP. It is an
+ INTEGER_CST. */
+
+static void
+compute_estimated_nb_iterations (struct loop *loop)
+{
+ tree estimation;
+ struct nb_iter_bound *bound, *next;
- compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, NULL);
- for (i = 1; i < loops->num; i++)
+ for (bound = loop->bounds; bound; bound = next)
{
- unsigned int depth = 0;
- varray_type datarefs;
- varray_type dependence_relations;
- struct loop *loop_nest = loops->parray[i];
- struct loop *temp;
- VEC (tree) *oldivs = NULL;
- VEC (tree) *invariants = NULL;
- lambda_loopnest before, after;
- lambda_trans_matrix trans;
- bool problem = false;
- bool need_perfect_nest = false;
- /* If it's not a loop nest, we don't want it.
- We also don't handle sibling loops properly,
- which are loops of the following form:
- for (i = 0; i < 50; i++)
- {
- for (j = 0; j < 50; j++)
- {
- ...
- }
- for (j = 0; j < 50; j++)
- {
- ...
- }
- } */
- if (!loop_nest->inner)
+ next = bound->next;
+ estimation = bound->bound;
+
+ if (TREE_CODE (estimation) != INTEGER_CST)
continue;
- depth = 1;
- for (temp = loop_nest->inner; temp; temp = temp->inner)
+
+ if (loop->estimated_nb_iterations)
{
- flow_loop_scan (temp, LOOP_ALL);
- /* If we have a sibling loop or multiple exit edges, jump ship. */
- if (temp->next || temp->num_exits != 1)
- {
- problem = true;
- break;
- }
- depth ++;
+ /* Update only if estimation is smaller. */
+ if (tree_int_cst_lt (estimation, loop->estimated_nb_iterations))
+ loop->estimated_nb_iterations = estimation;
}
- if (problem)
- continue;
+ else
+ loop->estimated_nb_iterations = estimation;
+ }
+}
- /* Analyze data references and dependence relations using scev. */
-
- VARRAY_GENERIC_PTR_INIT (datarefs, 10, "datarefs");
- VARRAY_GENERIC_PTR_INIT (dependence_relations, 10,
- "dependence_relations");
-
+/* Estimate the number of iterations from the size of the data and the
+ access functions. */
+
+static void
+estimate_niter_from_size_of_data (struct loop *loop,
+ tree opnd0,
+ tree access_fn,
+ tree stmt)
+{
+ tree estimation;
+ tree array_size, data_size, element_size;
+ tree init, step;
+
+ init = initial_condition (access_fn);
+ step = evolution_part_in_loop_num (access_fn, loop->num);
+
+ array_size = TYPE_SIZE (TREE_TYPE (opnd0));
+ element_size = TYPE_SIZE (TREE_TYPE (TREE_TYPE (opnd0)));
+ if (array_size == NULL_TREE
+ || TREE_CODE (array_size) != INTEGER_CST
+ || TREE_CODE (element_size) != INTEGER_CST)
+ return;
+
+ data_size = fold (build2 (EXACT_DIV_EXPR, integer_type_node,
+ array_size, element_size));
+
+ if (init != NULL_TREE
+ && step != NULL_TREE
+ && TREE_CODE (init) == INTEGER_CST
+ && TREE_CODE (step) == INTEGER_CST)
+ {
+ estimation = fold (build2 (CEIL_DIV_EXPR, integer_type_node,
+ fold (build2 (MINUS_EXPR, integer_type_node,
+ data_size, init)), step));
+
+ record_estimate (loop, estimation, boolean_true_node, stmt);
+ }
+}
+
+/* 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,
+ varray_type *access_fns,
+ tree ref, tree stmt)
+{
+ tree opnd0, opnd1;
+ tree access_fn;
- compute_data_dependences_for_loop (depth, loop_nest,
- &datarefs, &dependence_relations);
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- unsigned int j;
- for (j = 0; j < VARRAY_ACTIVE_SIZE (dependence_relations); j++)
+ 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));
+
+ if (loop->estimated_nb_iterations == NULL_TREE)
+ estimate_niter_from_size_of_data (loop, opnd0, access_fn, stmt);
+
+ VARRAY_PUSH_TREE (*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. */
+
+struct data_reference *
+analyze_array (tree stmt, tree ref, bool is_read)
+{
+ struct data_reference *res;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "(analyze_array \n");
+ fprintf (dump_file, " (ref = ");
+ print_generic_stmt (dump_file, ref, 0);
+ fprintf (dump_file, ")\n");
+ }
+
+ res = xmalloc (sizeof (struct data_reference));
+
+ DR_STMT (res) = stmt;
+ DR_REF (res) = ref;
+ VARRAY_TREE_INIT (DR_ACCESS_FNS (res), 3, "access_fns");
+ DR_BASE_NAME (res) = analyze_array_indexes
+ (loop_containing_stmt (stmt), &(DR_ACCESS_FNS (res)), ref, stmt);
+ DR_IS_READ (res) = is_read;
+
+ 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. */
+
+struct data_reference *
+init_data_ref (tree stmt,
+ tree ref,
+ tree base,
+ tree access_fn,
+ bool is_read)
+{
+ struct data_reference *res;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "(init_data_ref \n");
+ fprintf (dump_file, " (ref = ");
+ print_generic_stmt (dump_file, ref, 0);
+ fprintf (dump_file, ")\n");
+ }
+
+ res = xmalloc (sizeof (struct data_reference));
+
+ DR_STMT (res) = stmt;
+ DR_REF (res) = ref;
+ VARRAY_TREE_INIT (DR_ACCESS_FNS (res), 5, "access_fns");
+ DR_BASE_NAME (res) = base;
+ VARRAY_PUSH_TREE (DR_ACCESS_FNS (res), access_fn);
+ DR_IS_READ (res) = is_read;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, ")\n");
+
+ return res;
+}
+
+\f
+
+/* Returns true when all the functions of a tree_vec CHREC are the
+ same. */
+
+static bool
+all_chrecs_equal_p (tree chrec)
+{
+ int j;
+
+ for (j = 0; j < TREE_VEC_LENGTH (chrec) - 1; j++)
+ {
+ tree chrec_j = TREE_VEC_ELT (chrec, j);
+ tree chrec_j_1 = TREE_VEC_ELT (chrec, j + 1);
+ if (!integer_zerop
+ (chrec_fold_minus
+ (integer_type_node, chrec_j, chrec_j_1)))
+ return false;
+ }
+ return true;
+}
+
+/* Determine for each subscript in the data dependence relation DDR
+ the distance. */
+
+static void
+compute_subscript_distance (struct data_dependence_relation *ddr)
+{
+ if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
+ {
+ unsigned int i;
+
+ for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
+ {
+ tree conflicts_a, conflicts_b, difference;
+ struct subscript *subscript;
+
+ subscript = DDR_SUBSCRIPT (ddr, i);
+ conflicts_a = SUB_CONFLICTS_IN_A (subscript);
+ conflicts_b = SUB_CONFLICTS_IN_B (subscript);
+
+ if (TREE_CODE (conflicts_a) == TREE_VEC)
{
- struct data_dependence_relation *ddr =
- (struct data_dependence_relation *)
- VARRAY_GENERIC_PTR (dependence_relations, j);
+ if (!all_chrecs_equal_p (conflicts_a))
+ {
+ SUB_DISTANCE (subscript) = chrec_dont_know;
+ return;
+ }
+ else
+ conflicts_a = TREE_VEC_ELT (conflicts_a, 0);
+ }
- if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
+ if (TREE_CODE (conflicts_b) == TREE_VEC)
+ {
+ if (!all_chrecs_equal_p (conflicts_b))
{
- fprintf (dump_file, "DISTANCE_V (");
- print_lambda_vector (dump_file, DDR_DIST_VECT (ddr),
- DDR_SIZE_VECT (ddr));
- fprintf (dump_file, ")\n");
- fprintf (dump_file, "DIRECTION_V (");
- print_lambda_vector (dump_file, DDR_DIR_VECT (ddr),
- DDR_SIZE_VECT (ddr));
- fprintf (dump_file, ")\n");
+ SUB_DISTANCE (subscript) = chrec_dont_know;
+ return;
}
+ else
+ conflicts_b = TREE_VEC_ELT (conflicts_b, 0);
}
- fprintf (dump_file, "\n\n");
- }
- /* Build the transformation matrix. */
- trans = lambda_trans_matrix_new (depth, depth);
- lambda_matrix_id (LTM_MATRIX (trans), depth);
- trans = try_interchange_loops (trans, depth, dependence_relations,
- datarefs, loop_nest);
+ difference = chrec_fold_minus
+ (integer_type_node, conflicts_b, conflicts_a);
+
+ if (evolution_function_is_constant_p (difference))
+ SUB_DISTANCE (subscript) = difference;
+
+ else
+ SUB_DISTANCE (subscript) = chrec_dont_know;
+ }
+ }
+}
- if (lambda_trans_matrix_id_p (trans))
- {
- if (dump_file)
- fprintf (dump_file, "Won't transform loop. Optimal transform is the identity transform\n");
- continue;
- }
+/* Initialize a ddr. */
- /* Check whether the transformation is legal. */
- if (!lambda_transform_legal_p (trans, depth, dependence_relations))
- {
- if (dump_file)
- fprintf (dump_file, "Can't transform loop, transform is illegal:\n");
- continue;
- }
- if (!perfect_nest_p (loop_nest))
- need_perfect_nest = true;
- before = gcc_loopnest_to_lambda_loopnest (loops,
- loop_nest, &oldivs,
- &invariants,
- need_perfect_nest);
- if (!before)
- continue;
-
- if (dump_file)
+struct data_dependence_relation *
+initialize_data_dependence_relation (struct data_reference *a,
+ struct data_reference *b)
+{
+ struct data_dependence_relation *res;
+ bool differ_p;
+
+ res = xmalloc (sizeof (struct data_dependence_relation));
+ DDR_A (res) = a;
+ DDR_B (res) = b;
+
+ if (a == NULL || b == NULL
+ || DR_BASE_NAME (a) == NULL_TREE
+ || DR_BASE_NAME (b) == NULL_TREE)
+ DDR_ARE_DEPENDENT (res) = chrec_dont_know;
+
+ /* When the dimensions of A and B differ, we directly initialize
+ the relation to "there is no dependence": chrec_known. */
+ else if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b)
+ || (array_base_name_differ_p (a, b, &differ_p) && differ_p))
+ DDR_ARE_DEPENDENT (res) = chrec_known;
+
+ else
+ {
+ unsigned int i;
+ DDR_AFFINE_P (res) = true;
+ DDR_ARE_DEPENDENT (res) = NULL_TREE;
+ DDR_SUBSCRIPTS_VECTOR_INIT (res, DR_NUM_DIMENSIONS (a));
+ DDR_SIZE_VECT (res) = 0;
+ DDR_DIST_VECT (res) = NULL;
+ DDR_DIR_VECT (res) = NULL;
+
+ for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
{
- fprintf (dump_file, "Before:\n");
- print_lambda_loopnest (dump_file, before, 'i');
+ struct subscript *subscript;
+
+ subscript = xmalloc (sizeof (struct subscript));
+ SUB_CONFLICTS_IN_A (subscript) = chrec_dont_know;
+ SUB_CONFLICTS_IN_B (subscript) = chrec_dont_know;
+ SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
+ SUB_DISTANCE (subscript) = chrec_dont_know;
+ VARRAY_PUSH_GENERIC_PTR (DDR_SUBSCRIPTS (res), subscript);
}
+ }
- after = lambda_loopnest_transform (before, trans);
- if (dump_file)
- {
- fprintf (dump_file, "After:\n");
- print_lambda_loopnest (dump_file, after, 'u');
- }
- lambda_loopnest_to_gcc_loopnest (loop_nest, oldivs, invariants,
- after, trans);
- if (dump_file)
- fprintf (dump_file, "Successfully transformed loop.\n");
- oldivs = NULL;
- invariants = NULL;
- free_dependence_relations (dependence_relations);
- free_data_refs (datarefs);
- }
- free_df ();
- scev_reset ();
- rewrite_into_ssa (false);
- rewrite_into_loop_closed_ssa ();
-#ifdef ENABLE_CHECKING
- verify_loop_closed_ssa ();
-#endif
+ return res;
+}
+
+/* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
+ description. */
+
+static inline void
+finalize_ddr_dependent (struct data_dependence_relation *ddr,
+ tree chrec)
+{
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "(dependence classified: ");
+ print_generic_expr (dump_file, chrec, 0);
+ fprintf (dump_file, ")\n");
+ }
+
+ DDR_ARE_DEPENDENT (ddr) = chrec;
+ varray_clear (DDR_SUBSCRIPTS (ddr));
+}
+
+/* The dependence relation DDR cannot be represented by a distance
+ vector. */
+
+static inline void
+non_affine_dependence_relation (struct data_dependence_relation *ddr)
+{
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
+
+ DDR_AFFINE_P (ddr) = false;
}
+
+\f
+
+/* This section contains the classic Banerjee tests. */
+
+/* Returns true iff CHREC_A and CHREC_B are not dependent on any index
+ variables, i.e., if the ZIV (Zero Index Variable) test is true. */
+
+static inline bool
+ziv_subscript_p (tree chrec_a,
+ tree chrec_b)
+{
+ return (evolution_function_is_constant_p (chrec_a)
+ && evolution_function_is_constant_p (chrec_b));
+}
+
+/* Returns true iff CHREC_A and CHREC_B are dependent on an index
+ variable, i.e., if the SIV (Single Index Variable) test is true. */
+
+static bool
+siv_subscript_p (tree chrec_a,
+ tree chrec_b)
+{
+ if ((evolution_function_is_constant_p (chrec_a)
+ && evolution_function_is_univariate_p (chrec_b))
+ || (evolution_function_is_constant_p (chrec_b)
+ && evolution_function_is_univariate_p (chrec_a)))
+ return true;
+
+ if (evolution_function_is_univariate_p (chrec_a)
+ && evolution_function_is_univariate_p (chrec_b))
+ {
+ switch (TREE_CODE (chrec_a))
+ {
+ case POLYNOMIAL_CHREC:
+ switch (TREE_CODE (chrec_b))
+ {
+ case POLYNOMIAL_CHREC:
+ if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
+ return false;
+
+ default:
+ return true;
+ }
+
+ default:
+ return true;
+ }
+ }
+
+ return false;
+}
+
+/* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
+ *OVERLAPS_B are initialized to the functions that describe the
+ relation between the elements accessed twice by CHREC_A and
+ CHREC_B. For k >= 0, the following property is verified:
+
+ CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
+
+static void
+analyze_ziv_subscript (tree chrec_a,
+ tree chrec_b,
+ tree *overlaps_a,
+ tree *overlaps_b,
+ tree *last_conflicts)
+{
+ tree difference;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "(analyze_ziv_subscript \n");
+
+ difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
+
+ switch (TREE_CODE (difference))
+ {
+ case INTEGER_CST:
+ if (integer_zerop (difference))
+ {
+ /* The difference is equal to zero: the accessed index
+ overlaps for each iteration in the loop. */
+ *overlaps_a = integer_zero_node;
+ *overlaps_b = integer_zero_node;
+ *last_conflicts = chrec_dont_know;
+ }
+ else
+ {
+ /* The accesses do not overlap. */
+ *overlaps_a = chrec_known;
+ *overlaps_b = chrec_known;
+ *last_conflicts = integer_zero_node;
+ }
+ break;
+
+ default:
+ /* We're not sure whether the indexes overlap. For the moment,
+ conservatively answer "don't know". */
+ *overlaps_a = chrec_dont_know;
+ *overlaps_b = chrec_dont_know;
+ *last_conflicts = chrec_dont_know;
+ break;
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, ")\n");
+}
+
+/* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
+ constant, and CHREC_B is an affine function. *OVERLAPS_A and
+ *OVERLAPS_B are initialized to the functions that describe the
+ relation between the elements accessed twice by CHREC_A and
+ CHREC_B. For k >= 0, the following property is verified:
+
+ CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
+
+static void
+analyze_siv_subscript_cst_affine (tree chrec_a,
+ tree chrec_b,
+ tree *overlaps_a,
+ tree *overlaps_b,
+ tree *last_conflicts)
+{
+ bool value0, value1, value2;
+ tree difference = chrec_fold_minus
+ (integer_type_node, CHREC_LEFT (chrec_b), chrec_a);
+
+ if (!chrec_is_positive (initial_condition (difference), &value0))
+ {
+ *overlaps_a = chrec_dont_know;
+ *overlaps_b = chrec_dont_know;
+ *last_conflicts = chrec_dont_know;
+ return;
+ }
+ else
+ {
+ if (value0 == false)
+ {
+ if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
+ {
+ *overlaps_a = chrec_dont_know;
+ *overlaps_b = chrec_dont_know;
+ *last_conflicts = chrec_dont_know;
+ return;
+ }
+ else
+ {
+ if (value1 == true)
+ {
+ /* Example:
+ chrec_a = 12
+ chrec_b = {10, +, 1}
+ */
+
+ if (tree_fold_divides_p
+ (integer_type_node, CHREC_RIGHT (chrec_b), difference))
+ {
+ *overlaps_a = integer_zero_node;
+ *overlaps_b = fold
+ (build (EXACT_DIV_EXPR, integer_type_node,
+ fold (build1 (ABS_EXPR, integer_type_node, difference)),
+ CHREC_RIGHT (chrec_b)));
+ *last_conflicts = integer_one_node;
+ return;
+ }
+
+ /* When the step does not divides the difference, there are
+ no overlaps. */
+ else
+ {
+ *overlaps_a = chrec_known;
+ *overlaps_b = chrec_known;
+ *last_conflicts = integer_zero_node;
+ return;
+ }
+ }
+
+ else
+ {
+ /* Example:
+ chrec_a = 12
+ chrec_b = {10, +, -1}
+
+ In this case, chrec_a will not overlap with chrec_b. */
+ *overlaps_a = chrec_known;
+ *overlaps_b = chrec_known;
+ *last_conflicts = integer_zero_node;
+ return;
+ }
+ }
+ }
+ else
+ {
+ if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
+ {
+ *overlaps_a = chrec_dont_know;
+ *overlaps_b = chrec_dont_know;
+ *last_conflicts = chrec_dont_know;
+ return;
+ }
+ else
+ {
+ if (value2 == false)
+ {
+ /* Example:
+ chrec_a = 3
+ chrec_b = {10, +, -1}
+ */
+ if (tree_fold_divides_p
+ (integer_type_node, CHREC_RIGHT (chrec_b), difference))
+ {
+ *overlaps_a = integer_zero_node;
+ *overlaps_b = fold
+ (build (EXACT_DIV_EXPR, integer_type_node, difference,
+ CHREC_RIGHT (chrec_b)));
+ *last_conflicts = integer_one_node;
+ return;
+ }
+
+ /* When the step does not divides the difference, there
+ are no overlaps. */
+ else
+ {
+ *overlaps_a = chrec_known;
+ *overlaps_b = chrec_known;
+ *last_conflicts = integer_zero_node;
+ return;
+ }
+ }
+ else
+ {
+ /* Example:
+ chrec_a = 3
+ chrec_b = {4, +, 1}
+
+ In this case, chrec_a will not overlap with chrec_b. */
+ *overlaps_a = chrec_known;
+ *overlaps_b = chrec_known;
+ *last_conflicts = integer_zero_node;
+ return;
+ }
+ }
+ }
+ }
+}
+
+/* Helper recursive function for initializing the matrix A. Returns
+ the initial value of CHREC. */
+
+static int
+initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
+{
+ gcc_assert (chrec);
+
+ if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
+ return int_cst_value (chrec);
+
+ A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
+ return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
+}
+
+#define FLOOR_DIV(x,y) ((x) / (y))
+
+/* Solves the special case of the Diophantine equation:
+ | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
+
+ Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
+ number of iterations that loops X and Y run. The overlaps will be
+ constructed as evolutions in dimension DIM. */
+
+static void
+compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
+ tree *overlaps_a, tree *overlaps_b,
+ tree *last_conflicts, int dim)
+{
+ if (((step_a > 0 && step_b > 0)
+ || (step_a < 0 && step_b < 0)))
+ {
+ int step_overlaps_a, step_overlaps_b;
+ int gcd_steps_a_b, last_conflict, tau2;
+
+ gcd_steps_a_b = gcd (step_a, step_b);
+ step_overlaps_a = step_b / gcd_steps_a_b;
+ step_overlaps_b = step_a / gcd_steps_a_b;
+
+ tau2 = FLOOR_DIV (niter, step_overlaps_a);
+ tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
+ last_conflict = tau2;
+
+ *overlaps_a = build_polynomial_chrec
+ (dim, integer_zero_node,
+ build_int_cst (NULL_TREE, step_overlaps_a));
+ *overlaps_b = build_polynomial_chrec
+ (dim, integer_zero_node,
+ build_int_cst (NULL_TREE, step_overlaps_b));
+ *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
+ }
+
+ else
+ {
+ *overlaps_a = integer_zero_node;
+ *overlaps_b = integer_zero_node;
+ *last_conflicts = integer_zero_node;
+ }
+}
+
+
+/* Solves the special case of a Diophantine equation where CHREC_A is
+ an affine bivariate function, and CHREC_B is an affine univariate
+ function. For example,
+
+ | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
+
+ has the following overlapping functions:
+
+ | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
+ | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
+ | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
+
+ FORNOW: This is a specialized implementation for a case occurring in
+ a common benchmark. Implement the general algorithm. */
+
+static void
+compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
+ tree *overlaps_a, tree *overlaps_b,
+ tree *last_conflicts)
+{
+ bool xz_p, yz_p, xyz_p;
+ int step_x, step_y, step_z;
+ int niter_x, niter_y, niter_z, niter;
+ tree numiter_x, numiter_y, numiter_z;
+ tree overlaps_a_xz, overlaps_b_xz, last_conflicts_xz;
+ tree overlaps_a_yz, overlaps_b_yz, last_conflicts_yz;
+ tree overlaps_a_xyz, overlaps_b_xyz, last_conflicts_xyz;
+
+ step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
+ step_y = int_cst_value (CHREC_RIGHT (chrec_a));
+ step_z = int_cst_value (CHREC_RIGHT (chrec_b));
+
+ numiter_x = number_of_iterations_in_loop
+ (current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]);
+ numiter_y = number_of_iterations_in_loop
+ (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
+ numiter_z = number_of_iterations_in_loop
+ (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
+
+ if (TREE_CODE (numiter_x) != INTEGER_CST)
+ numiter_x = current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]
+ ->estimated_nb_iterations;
+ if (TREE_CODE (numiter_y) != INTEGER_CST)
+ numiter_y = current_loops->parray[CHREC_VARIABLE (chrec_a)]
+ ->estimated_nb_iterations;
+ if (TREE_CODE (numiter_z) != INTEGER_CST)
+ numiter_z = current_loops->parray[CHREC_VARIABLE (chrec_b)]
+ ->estimated_nb_iterations;
+
+ if (numiter_x == NULL_TREE || numiter_y == NULL_TREE
+ || numiter_z == NULL_TREE)
+ {
+ *overlaps_a = chrec_dont_know;
+ *overlaps_b = chrec_dont_know;
+ *last_conflicts = chrec_dont_know;
+ return;
+ }
+
+ niter_x = int_cst_value (numiter_x);
+ niter_y = int_cst_value (numiter_y);
+ niter_z = int_cst_value (numiter_z);
+
+ niter = MIN (niter_x, niter_z);
+ compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
+ &overlaps_a_xz,
+ &overlaps_b_xz,
+ &last_conflicts_xz, 1);
+ niter = MIN (niter_y, niter_z);
+ compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
+ &overlaps_a_yz,
+ &overlaps_b_yz,
+ &last_conflicts_yz, 2);
+ niter = MIN (niter_x, niter_z);
+ niter = MIN (niter_y, niter);
+ compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
+ &overlaps_a_xyz,
+ &overlaps_b_xyz,
+ &last_conflicts_xyz, 3);
+
+ xz_p = !integer_zerop (last_conflicts_xz);
+ yz_p = !integer_zerop (last_conflicts_yz);
+ xyz_p = !integer_zerop (last_conflicts_xyz);
+
+ if (xz_p || yz_p || xyz_p)
+ {
+ *overlaps_a = make_tree_vec (2);
+ TREE_VEC_ELT (*overlaps_a, 0) = integer_zero_node;
+ TREE_VEC_ELT (*overlaps_a, 1) = integer_zero_node;
+ *overlaps_b = integer_zero_node;
+ if (xz_p)
+ {
+ TREE_VEC_ELT (*overlaps_a, 0) =
+ chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0),
+ overlaps_a_xz);
+ *overlaps_b =
+ chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xz);
+ *last_conflicts = last_conflicts_xz;
+ }
+ if (yz_p)
+ {
+ TREE_VEC_ELT (*overlaps_a, 1) =
+ chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1),
+ overlaps_a_yz);
+ *overlaps_b =
+ chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_yz);
+ *last_conflicts = last_conflicts_yz;
+ }
+ if (xyz_p)
+ {
+ TREE_VEC_ELT (*overlaps_a, 0) =
+ chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0),
+ overlaps_a_xyz);
+ TREE_VEC_ELT (*overlaps_a, 1) =
+ chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1),
+ overlaps_a_xyz);
+ *overlaps_b =
+ chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xyz);
+ *last_conflicts = last_conflicts_xyz;
+ }
+ }
+ else
+ {
+ *overlaps_a = integer_zero_node;
+ *overlaps_b = integer_zero_node;
+ *last_conflicts = integer_zero_node;
+ }
+}
+
+/* Determines the overlapping elements due to accesses CHREC_A and
+ CHREC_B, that are affine functions. This is a part of the
+ subscript analyzer. */
+
+static void
+analyze_subscript_affine_affine (tree chrec_a,
+ tree chrec_b,
+ tree *overlaps_a,
+ tree *overlaps_b,
+ tree *last_conflicts)
+{
+ unsigned nb_vars_a, nb_vars_b, dim;
+ int init_a, init_b, gamma, gcd_alpha_beta;
+ int tau1, tau2;
+ lambda_matrix A, U, S;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "(analyze_subscript_affine_affine \n");
+
+ /* For determining the initial intersection, we have to solve a
+ Diophantine equation. This is the most time consuming part.
+
+ For answering to the question: "Is there a dependence?" we have
+ to prove that there exists a solution to the Diophantine
+ equation, and that the solution is in the iteration domain,
+ i.e. the solution is positive or zero, and that the solution
+ happens before the upper bound loop.nb_iterations. Otherwise
+ there is no dependence. This function outputs a description of
+ the iterations that hold the intersections. */
+
+
+ nb_vars_a = nb_vars_in_chrec (chrec_a);
+ nb_vars_b = nb_vars_in_chrec (chrec_b);
+
+ dim = nb_vars_a + nb_vars_b;
+ U = lambda_matrix_new (dim, dim);
+ A = lambda_matrix_new (dim, 1);
+ S = lambda_matrix_new (dim, 1);
+
+ init_a = initialize_matrix_A (A, chrec_a, 0, 1);
+ init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1);
+ gamma = init_b - init_a;
+
+ /* Don't do all the hard work of solving the Diophantine equation
+ when we already know the solution: for example,
+ | {3, +, 1}_1
+ | {3, +, 4}_2
+ | gamma = 3 - 3 = 0.
+ Then the first overlap occurs during the first iterations:
+ | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
+ */
+ if (gamma == 0)
+ {
+ if (nb_vars_a == 1 && nb_vars_b == 1)
+ {
+ int step_a, step_b;
+ int niter, niter_a, niter_b;
+ tree numiter_a, numiter_b;
+
+ numiter_a = number_of_iterations_in_loop
+ (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
+ numiter_b = number_of_iterations_in_loop
+ (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
+
+ if (TREE_CODE (numiter_a) != INTEGER_CST)
+ numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)]
+ ->estimated_nb_iterations;
+ if (TREE_CODE (numiter_b) != INTEGER_CST)
+ numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
+ ->estimated_nb_iterations;
+ if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
+ {
+ *overlaps_a = chrec_dont_know;
+ *overlaps_b = chrec_dont_know;
+ *last_conflicts = chrec_dont_know;
+ return;
+ }
+
+ niter_a = int_cst_value (numiter_a);
+ niter_b = int_cst_value (numiter_b);
+ niter = MIN (niter_a, niter_b);
+
+ step_a = int_cst_value (CHREC_RIGHT (chrec_a));
+ step_b = int_cst_value (CHREC_RIGHT (chrec_b));
+
+ compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
+ overlaps_a, overlaps_b,
+ last_conflicts, 1);
+ }
+
+ else if (nb_vars_a == 2 && nb_vars_b == 1)
+ compute_overlap_steps_for_affine_1_2
+ (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
+
+ else if (nb_vars_a == 1 && nb_vars_b == 2)
+ compute_overlap_steps_for_affine_1_2
+ (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
+
+ else
+ {
+ *overlaps_a = chrec_dont_know;
+ *overlaps_b = chrec_dont_know;
+ *last_conflicts = chrec_dont_know;
+ }
+ return;
+ }
+
+ /* U.A = S */
+ lambda_matrix_right_hermite (A, dim, 1, S, U);
+
+ if (S[0][0] < 0)
+ {
+ S[0][0] *= -1;
+ lambda_matrix_row_negate (U, dim, 0);
+ }
+ gcd_alpha_beta = S[0][0];
+
+ /* The classic "gcd-test". */
+ if (!int_divides_p (gcd_alpha_beta, gamma))
+ {
+ /* The "gcd-test" has determined that there is no integer
+ solution, i.e. there is no dependence. */
+ *overlaps_a = chrec_known;
+ *overlaps_b = chrec_known;
+ *last_conflicts = integer_zero_node;
+ }
+
+ /* Both access functions are univariate. This includes SIV and MIV cases. */
+ else if (nb_vars_a == 1 && nb_vars_b == 1)
+ {
+ /* Both functions should have the same evolution sign. */
+ if (((A[0][0] > 0 && -A[1][0] > 0)
+ || (A[0][0] < 0 && -A[1][0] < 0)))
+ {
+ /* The solutions are given by:
+ |
+ | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
+ | [u21 u22] [y0]
+
+ For a given integer t. Using the following variables,
+
+ | i0 = u11 * gamma / gcd_alpha_beta
+ | j0 = u12 * gamma / gcd_alpha_beta
+ | i1 = u21
+ | j1 = u22
+
+ the solutions are:
+
+ | x0 = i0 + i1 * t,
+ | y0 = j0 + j1 * t. */
+
+ int i0, j0, i1, j1;
+
+ /* X0 and Y0 are the first iterations for which there is a
+ dependence. X0, Y0 are two solutions of the Diophantine
+ equation: chrec_a (X0) = chrec_b (Y0). */
+ int x0, y0;
+ int niter, niter_a, niter_b;
+ tree numiter_a, numiter_b;
+
+ numiter_a = number_of_iterations_in_loop
+ (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
+ numiter_b = number_of_iterations_in_loop
+ (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
+
+ if (TREE_CODE (numiter_a) != INTEGER_CST)
+ numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)]
+ ->estimated_nb_iterations;
+ if (TREE_CODE (numiter_b) != INTEGER_CST)
+ numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
+ ->estimated_nb_iterations;
+ if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
+ {
+ *overlaps_a = chrec_dont_know;
+ *overlaps_b = chrec_dont_know;
+ *last_conflicts = chrec_dont_know;
+ return;
+ }
+
+ niter_a = int_cst_value (numiter_a);
+ niter_b = int_cst_value (numiter_b);
+ niter = MIN (niter_a, niter_b);
+
+ i0 = U[0][0] * gamma / gcd_alpha_beta;
+ j0 = U[0][1] * gamma / gcd_alpha_beta;
+ i1 = U[1][0];
+ j1 = U[1][1];
+
+ if ((i1 == 0 && i0 < 0)
+ || (j1 == 0 && j0 < 0))
+ {
+ /* There is no solution.
+ FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
+ falls in here, but for the moment we don't look at the
+ upper bound of the iteration domain. */
+ *overlaps_a = chrec_known;
+ *overlaps_b = chrec_known;
+ *last_conflicts = integer_zero_node;
+ }
+
+ else
+ {
+ if (i1 > 0)
+ {
+ tau1 = CEIL (-i0, i1);
+ tau2 = FLOOR_DIV (niter - i0, i1);
+
+ if (j1 > 0)
+ {
+ int last_conflict, min_multiple;
+ tau1 = MAX (tau1, CEIL (-j0, j1));
+ tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1));
+
+ x0 = i1 * tau1 + i0;
+ y0 = j1 * tau1 + j0;
+
+ /* At this point (x0, y0) is one of the
+ solutions to the Diophantine equation. The
+ next step has to compute the smallest
+ positive solution: the first conflicts. */
+ min_multiple = MIN (x0 / i1, y0 / j1);
+ x0 -= i1 * min_multiple;
+ y0 -= j1 * min_multiple;
+
+ tau1 = (x0 - i0)/i1;
+ last_conflict = tau2 - tau1;
+
+ *overlaps_a = build_polynomial_chrec
+ (1,
+ build_int_cst (NULL_TREE, x0),
+ build_int_cst (NULL_TREE, i1));
+ *overlaps_b = build_polynomial_chrec
+ (1,
+ build_int_cst (NULL_TREE, y0),
+ build_int_cst (NULL_TREE, j1));
+ *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
+ }
+ else
+ {
+ /* FIXME: For the moment, the upper bound of the
+ iteration domain for j is not checked. */
+ *overlaps_a = chrec_dont_know;
+ *overlaps_b = chrec_dont_know;
+ *last_conflicts = chrec_dont_know;
+ }
+ }
+
+ else
+ {
+ /* FIXME: For the moment, the upper bound of the
+ iteration domain for i is not checked. */
+ *overlaps_a = chrec_dont_know;
+ *overlaps_b = chrec_dont_know;
+ *last_conflicts = chrec_dont_know;
+ }
+ }
+ }
+ else
+ {
+ *overlaps_a = chrec_dont_know;
+ *overlaps_b = chrec_dont_know;
+ *last_conflicts = chrec_dont_know;
+ }
+ }
+
+ else
+ {
+ *overlaps_a = chrec_dont_know;
+ *overlaps_b = chrec_dont_know;
+ *last_conflicts = chrec_dont_know;
+ }
+
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " (overlaps_a = ");
+ print_generic_expr (dump_file, *overlaps_a, 0);
+ fprintf (dump_file, ")\n (overlaps_b = ");
+ print_generic_expr (dump_file, *overlaps_b, 0);
+ fprintf (dump_file, ")\n");
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, ")\n");
+}
+
+/* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
+ *OVERLAPS_B are initialized to the functions that describe the
+ relation between the elements accessed twice by CHREC_A and
+ CHREC_B. For k >= 0, the following property is verified:
+
+ CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
+
+static void
+analyze_siv_subscript (tree chrec_a,
+ tree chrec_b,
+ tree *overlaps_a,
+ tree *overlaps_b,
+ tree *last_conflicts)
+{
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "(analyze_siv_subscript \n");
+
+ if (evolution_function_is_constant_p (chrec_a)
+ && evolution_function_is_affine_p (chrec_b))
+ analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
+ overlaps_a, overlaps_b, last_conflicts);
+
+ else if (evolution_function_is_affine_p (chrec_a)
+ && evolution_function_is_constant_p (chrec_b))
+ analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
+ overlaps_b, overlaps_a, last_conflicts);
+
+ else if (evolution_function_is_affine_p (chrec_a)
+ && evolution_function_is_affine_p (chrec_b))
+ analyze_subscript_affine_affine (chrec_a, chrec_b,
+ overlaps_a, overlaps_b, last_conflicts);
+ else
+ {
+ *overlaps_a = chrec_dont_know;
+ *overlaps_b = chrec_dont_know;
+ *last_conflicts = chrec_dont_know;
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, ")\n");
+}
+
+/* Return true when the evolution steps of an affine CHREC divide the
+ constant CST. */
+
+static bool
+chrec_steps_divide_constant_p (tree chrec,
+ tree cst)
+{
+ switch (TREE_CODE (chrec))
+ {
+ case POLYNOMIAL_CHREC:
+ return (tree_fold_divides_p (integer_type_node, CHREC_RIGHT (chrec), cst)
+ && chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst));
+
+ default:
+ /* On the initial condition, return true. */
+ return true;
+ }
+}
+
+/* Analyze a MIV (Multiple Index Variable) subscript. *OVERLAPS_A and
+ *OVERLAPS_B are initialized to the functions that describe the
+ relation between the elements accessed twice by CHREC_A and
+ CHREC_B. For k >= 0, the following property is verified:
+
+ CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
+
+static void
+analyze_miv_subscript (tree chrec_a,
+ tree chrec_b,
+ tree *overlaps_a,
+ tree *overlaps_b,
+ tree *last_conflicts)
+{
+ /* FIXME: This is a MIV subscript, not yet handled.
+ Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
+ (A[i] vs. A[j]).
+
+ In the SIV test we had to solve a Diophantine equation with two
+ variables. In the MIV case we have to solve a Diophantine
+ equation with 2*n variables (if the subscript uses n IVs).
+ */
+ tree difference;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "(analyze_miv_subscript \n");
+
+ difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
+
+ if (chrec_zerop (difference))
+ {
+ /* Access functions are the same: all the elements are accessed
+ in the same order. */
+ *overlaps_a = integer_zero_node;
+ *overlaps_b = integer_zero_node;
+ *last_conflicts = number_of_iterations_in_loop
+ (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
+ }
+
+ else if (evolution_function_is_constant_p (difference)
+ /* For the moment, the following is verified:
+ evolution_function_is_affine_multivariate_p (chrec_a) */
+ && !chrec_steps_divide_constant_p (chrec_a, difference))
+ {
+ /* testsuite/.../ssa-chrec-33.c
+ {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
+
+ The difference is 1, and the evolution steps are equal to 2,
+ consequently there are no overlapping elements. */
+ *overlaps_a = chrec_known;
+ *overlaps_b = chrec_known;
+ *last_conflicts = integer_zero_node;
+ }
+
+ else if (evolution_function_is_affine_multivariate_p (chrec_a)
+ && evolution_function_is_affine_multivariate_p (chrec_b))
+ {
+ /* testsuite/.../ssa-chrec-35.c
+ {0, +, 1}_2 vs. {0, +, 1}_3
+ the overlapping elements are respectively located at iterations:
+ {0, +, 1}_x and {0, +, 1}_x,
+ in other words, we have the equality:
+ {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
+
+ Other examples:
+ {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
+ {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
+
+ {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
+ {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
+ */
+ analyze_subscript_affine_affine (chrec_a, chrec_b,
+ overlaps_a, overlaps_b, last_conflicts);
+ }
+
+ else
+ {
+ /* When the analysis is too difficult, answer "don't know". */
+ *overlaps_a = chrec_dont_know;
+ *overlaps_b = chrec_dont_know;
+ *last_conflicts = chrec_dont_know;
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, ")\n");
+}
+
+/* Determines the iterations for which CHREC_A is equal to CHREC_B.
+ OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with
+ two functions that describe the iterations that contain conflicting
+ elements.
+
+ Remark: For an integer k >= 0, the following equality is true:
+
+ CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
+*/
+
+static void
+analyze_overlapping_iterations (tree chrec_a,
+ tree chrec_b,
+ tree *overlap_iterations_a,
+ tree *overlap_iterations_b,
+ tree *last_conflicts)
+{
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "(analyze_overlapping_iterations \n");
+ fprintf (dump_file, " (chrec_a = ");
+ print_generic_expr (dump_file, chrec_a, 0);
+ fprintf (dump_file, ")\n chrec_b = ");
+ print_generic_expr (dump_file, chrec_b, 0);
+ fprintf (dump_file, ")\n");
+ }
+
+ if (chrec_a == NULL_TREE
+ || chrec_b == NULL_TREE
+ || chrec_contains_undetermined (chrec_a)
+ || chrec_contains_undetermined (chrec_b)
+ || chrec_contains_symbols (chrec_a)
+ || chrec_contains_symbols (chrec_b))
+ {
+ *overlap_iterations_a = chrec_dont_know;
+ *overlap_iterations_b = chrec_dont_know;
+ }
+
+ else if (ziv_subscript_p (chrec_a, chrec_b))
+ analyze_ziv_subscript (chrec_a, chrec_b,
+ overlap_iterations_a, overlap_iterations_b,
+ last_conflicts);
+
+ else if (siv_subscript_p (chrec_a, chrec_b))
+ analyze_siv_subscript (chrec_a, chrec_b,
+ overlap_iterations_a, overlap_iterations_b,
+ last_conflicts);
+
+ else
+ analyze_miv_subscript (chrec_a, chrec_b,
+ overlap_iterations_a, overlap_iterations_b,
+ last_conflicts);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " (overlap_iterations_a = ");
+ print_generic_expr (dump_file, *overlap_iterations_a, 0);
+ fprintf (dump_file, ")\n (overlap_iterations_b = ");
+ print_generic_expr (dump_file, *overlap_iterations_b, 0);
+ fprintf (dump_file, ")\n");
+ }
+ /*
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (stdout, " (overlap_iterations_a = ");
+ print_generic_expr (stdout, *overlap_iterations_a, 0);
+ fprintf (stdout, ")\n (overlap_iterations_b = ");
+ print_generic_expr (stdout, *overlap_iterations_b, 0);
+ fprintf (stdout, ")\n");
+ }*/
+}
+
+\f
+
+/* This section contains the affine functions dependences detector. */
+
+/* Computes the conflicting iterations, and initialize DDR. */
+
+static void
+subscript_dependence_tester (struct data_dependence_relation *ddr)
+{
+ unsigned int i;
+ struct data_reference *dra = DDR_A (ddr);
+ struct data_reference *drb = DDR_B (ddr);
+ tree last_conflicts;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "(subscript_dependence_tester \n");
+
+ for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
+ {
+ tree overlaps_a, overlaps_b;
+ struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
+
+ analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
+ DR_ACCESS_FN (drb, i),
+ &overlaps_a, &overlaps_b,
+ &last_conflicts);
+
+ if (chrec_contains_undetermined (overlaps_a)
+ || chrec_contains_undetermined (overlaps_b))
+ {
+ finalize_ddr_dependent (ddr, chrec_dont_know);
+ break;
+ }
+
+ else if (overlaps_a == chrec_known
+ || overlaps_b == chrec_known)
+ {
+ finalize_ddr_dependent (ddr, chrec_known);
+ break;
+ }
+
+ else
+ {
+ SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
+ SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
+ SUB_LAST_CONFLICT (subscript) = last_conflicts;
+ }
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, ")\n");
+}
+
+/* Compute the classic per loop distance vector.
+
+ DDR is the data dependence relation to build a vector from.
+ NB_LOOPS is the total number of loops we are considering.
+ FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed
+ loop nest.
+ Return FALSE if the dependence relation is outside of the loop nest
+ starting at FIRST_LOOP_DEPTH.
+ Return TRUE otherwise. */
+
+static bool
+build_classic_dist_vector (struct data_dependence_relation *ddr,
+ int nb_loops, int first_loop_depth)
+{
+ unsigned i;
+ lambda_vector dist_v, init_v;
+
+ dist_v = lambda_vector_new (nb_loops);
+ init_v = lambda_vector_new (nb_loops);
+ lambda_vector_clear (dist_v, nb_loops);
+ lambda_vector_clear (init_v, nb_loops);
+
+ if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
+ return true;
+
+ for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
+ {
+ tree access_fn_a, access_fn_b;
+ struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
+
+ if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
+ {
+ non_affine_dependence_relation (ddr);
+ return true;
+ }
+
+ access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
+ access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i);
+
+ if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
+ && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
+ {
+ int dist, loop_nb, loop_depth;
+ int loop_nb_a = CHREC_VARIABLE (access_fn_a);
+ int loop_nb_b = CHREC_VARIABLE (access_fn_b);
+ struct loop *loop_a = current_loops->parray[loop_nb_a];
+ struct loop *loop_b = current_loops->parray[loop_nb_b];
+
+ /* If the loop for either variable is at a lower depth than
+ the first_loop's depth, then we can't possibly have a
+ dependency at this level of the loop. */
+
+ if (loop_a->depth < first_loop_depth
+ || loop_b->depth < first_loop_depth)
+ return false;
+
+ if (loop_nb_a != loop_nb_b
+ && !flow_loop_nested_p (loop_a, loop_b)
+ && !flow_loop_nested_p (loop_b, loop_a))
+ {
+ /* Example: when there are two consecutive loops,
+
+ | loop_1
+ | A[{0, +, 1}_1]
+ | endloop_1
+ | loop_2
+ | A[{0, +, 1}_2]
+ | endloop_2
+
+ the dependence relation cannot be captured by the
+ distance abstraction. */
+ non_affine_dependence_relation (ddr);
+ return true;
+ }
+
+ /* The dependence is carried by the outermost loop. Example:
+ | loop_1
+ | A[{4, +, 1}_1]
+ | loop_2
+ | A[{5, +, 1}_2]
+ | endloop_2
+ | endloop_1
+ In this case, the dependence is carried by loop_1. */
+ loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
+ loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth;
+
+ /* If the loop number is still greater than the number of
+ loops we've been asked to analyze, or negative,
+ something is borked. */
+ gcc_assert (loop_depth >= 0);
+ gcc_assert (loop_depth < nb_loops);
+ if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
+ {
+ non_affine_dependence_relation (ddr);
+ return true;
+ }
+
+ dist = int_cst_value (SUB_DISTANCE (subscript));
+
+ /* This is the subscript coupling test.
+ | loop i = 0, N, 1
+ | T[i+1][i] = ...
+ | ... = T[i][i]
+ | endloop
+ There is no dependence. */
+ if (init_v[loop_depth] != 0
+ && dist_v[loop_depth] != dist)
+ {
+ finalize_ddr_dependent (ddr, chrec_known);
+ return true;
+ }
+
+ dist_v[loop_depth] = dist;
+ init_v[loop_depth] = 1;
+ }
+ }
+
+ /* There is a distance of 1 on all the outer loops:
+
+ Example: there is a dependence of distance 1 on loop_1 for the array A.
+ | loop_1
+ | A[5] = ...
+ | endloop
+ */
+ {
+ struct loop *lca, *loop_a, *loop_b;
+ struct data_reference *a = DDR_A (ddr);
+ struct data_reference *b = DDR_B (ddr);
+ int lca_depth;
+ loop_a = loop_containing_stmt (DR_STMT (a));
+ loop_b = loop_containing_stmt (DR_STMT (b));
+
+ /* Get the common ancestor loop. */
+ lca = find_common_loop (loop_a, loop_b);
+
+ lca_depth = lca->depth;
+ lca_depth -= first_loop_depth;
+ gcc_assert (lca_depth >= 0);
+ gcc_assert (lca_depth < nb_loops);
+
+ /* For each outer loop where init_v is not set, the accesses are
+ in dependence of distance 1 in the loop. */
+ if (lca != loop_a
+ && lca != loop_b
+ && init_v[lca_depth] == 0)
+ dist_v[lca_depth] = 1;
+
+ lca = lca->outer;
+
+ if (lca)
+ {
+ lca_depth = lca->depth - first_loop_depth;
+ while (lca->depth != 0)
+ {
+ /* If we're considering just a sub-nest, then don't record
+ any information on the outer loops. */
+ if (lca_depth < 0)
+ break;
+
+ gcc_assert (lca_depth < nb_loops);
+
+ if (init_v[lca_depth] == 0)
+ dist_v[lca_depth] = 1;
+ lca = lca->outer;
+ lca_depth = lca->depth - first_loop_depth;
+
+ }
+ }
+ }
+
+ DDR_DIST_VECT (ddr) = dist_v;
+ DDR_SIZE_VECT (ddr) = nb_loops;
+ return true;
+}
+
+/* Compute the classic per loop direction vector.
+
+ DDR is the data dependence relation to build a vector from.
+ NB_LOOPS is the total number of loops we are considering.
+ FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed
+ loop nest.
+ Return FALSE if the dependence relation is outside of the loop nest
+ at FIRST_LOOP_DEPTH.
+ Return TRUE otherwise. */
+
+static bool
+build_classic_dir_vector (struct data_dependence_relation *ddr,
+ int nb_loops, int first_loop_depth)
+{
+ unsigned i;
+ lambda_vector dir_v, init_v;
+
+ dir_v = lambda_vector_new (nb_loops);
+ init_v = lambda_vector_new (nb_loops);
+ lambda_vector_clear (dir_v, nb_loops);
+ lambda_vector_clear (init_v, nb_loops);
+
+ if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
+ return true;
+
+ for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
+ {
+ tree access_fn_a, access_fn_b;
+ struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
+
+ if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
+ {
+ non_affine_dependence_relation (ddr);
+ return true;
+ }
+
+ access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
+ access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i);
+ if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
+ && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
+ {
+ int dist, loop_nb, loop_depth;
+ enum data_dependence_direction dir = dir_star;
+ int loop_nb_a = CHREC_VARIABLE (access_fn_a);
+ int loop_nb_b = CHREC_VARIABLE (access_fn_b);
+ struct loop *loop_a = current_loops->parray[loop_nb_a];
+ struct loop *loop_b = current_loops->parray[loop_nb_b];
+
+ /* If the loop for either variable is at a lower depth than
+ the first_loop's depth, then we can't possibly have a
+ dependency at this level of the loop. */
+
+ if (loop_a->depth < first_loop_depth
+ || loop_b->depth < first_loop_depth)
+ return false;
+
+ if (loop_nb_a != loop_nb_b
+ && !flow_loop_nested_p (loop_a, loop_b)
+ && !flow_loop_nested_p (loop_b, loop_a))
+ {
+ /* Example: when there are two consecutive loops,
+
+ | loop_1
+ | A[{0, +, 1}_1]
+ | endloop_1
+ | loop_2
+ | A[{0, +, 1}_2]
+ | endloop_2
+
+ the dependence relation cannot be captured by the
+ distance abstraction. */
+ non_affine_dependence_relation (ddr);
+ return true;
+ }
+
+ /* The dependence is carried by the outermost loop. Example:
+ | loop_1
+ | A[{4, +, 1}_1]
+ | loop_2
+ | A[{5, +, 1}_2]
+ | endloop_2
+ | endloop_1
+ In this case, the dependence is carried by loop_1. */
+ loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
+ loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth;
+
+ /* If the loop number is still greater than the number of
+ loops we've been asked to analyze, or negative,
+ something is borked. */
+ gcc_assert (loop_depth >= 0);
+ gcc_assert (loop_depth < nb_loops);
+
+ if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
+ {
+ non_affine_dependence_relation (ddr);
+ return true;
+ }
+
+ dist = int_cst_value (SUB_DISTANCE (subscript));
+
+ if (dist == 0)
+ dir = dir_equal;
+ else if (dist > 0)
+ dir = dir_positive;
+ else if (dist < 0)
+ dir = dir_negative;
+
+ /* This is the subscript coupling test.
+ | loop i = 0, N, 1
+ | T[i+1][i] = ...
+ | ... = T[i][i]
+ | endloop
+ There is no dependence. */
+ if (init_v[loop_depth] != 0
+ && dir != dir_star
+ && (enum data_dependence_direction) dir_v[loop_depth] != dir
+ && (enum data_dependence_direction) dir_v[loop_depth] != dir_star)
+ {
+ finalize_ddr_dependent (ddr, chrec_known);
+ return true;
+ }
+
+ dir_v[loop_depth] = dir;
+ init_v[loop_depth] = 1;
+ }
+ }
+
+ /* There is a distance of 1 on all the outer loops:
+
+ Example: there is a dependence of distance 1 on loop_1 for the array A.
+ | loop_1
+ | A[5] = ...
+ | endloop
+ */
+ {
+ struct loop *lca, *loop_a, *loop_b;
+ struct data_reference *a = DDR_A (ddr);
+ struct data_reference *b = DDR_B (ddr);
+ int lca_depth;
+ loop_a = loop_containing_stmt (DR_STMT (a));
+ loop_b = loop_containing_stmt (DR_STMT (b));
+
+ /* Get the common ancestor loop. */
+ lca = find_common_loop (loop_a, loop_b);
+ lca_depth = lca->depth - first_loop_depth;
+
+ gcc_assert (lca_depth >= 0);
+ gcc_assert (lca_depth < nb_loops);
+
+ /* For each outer loop where init_v is not set, the accesses are
+ in dependence of distance 1 in the loop. */
+ if (lca != loop_a
+ && lca != loop_b
+ && init_v[lca_depth] == 0)
+ dir_v[lca_depth] = dir_positive;
+
+ lca = lca->outer;
+ if (lca)
+ {
+ lca_depth = lca->depth - first_loop_depth;
+ while (lca->depth != 0)
+ {
+ /* If we're considering just a sub-nest, then don't record
+ any information on the outer loops. */
+ if (lca_depth < 0)
+ break;
+
+ gcc_assert (lca_depth < nb_loops);
+
+ if (init_v[lca_depth] == 0)
+ dir_v[lca_depth] = dir_positive;
+ lca = lca->outer;
+ lca_depth = lca->depth - first_loop_depth;
+
+ }
+ }
+ }
+
+ DDR_DIR_VECT (ddr) = dir_v;
+ DDR_SIZE_VECT (ddr) = nb_loops;
+ return true;
+}
+
+/* Returns true when all the access functions of A are affine or
+ constant. */
+
+static bool
+access_functions_are_affine_or_constant_p (struct data_reference *a)
+{
+ unsigned int i;
+ varray_type fns = DR_ACCESS_FNS (a);
+
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (fns); i++)
+ if (!evolution_function_is_constant_p (VARRAY_TREE (fns, i))
+ && !evolution_function_is_affine_multivariate_p (VARRAY_TREE (fns, i)))
+ return false;
+
+ return true;
+}
+
+/* This computes the affine dependence relation between A and B.
+ CHREC_KNOWN is used for representing the independence between two
+ accesses, while CHREC_DONT_KNOW is used for representing the unknown
+ relation.
+
+ Note that it is possible to stop the computation of the dependence
+ relation the first time we detect a CHREC_KNOWN element for a given
+ subscript. */
+
+void
+compute_affine_dependence (struct data_dependence_relation *ddr)
+{
+ struct data_reference *dra = DDR_A (ddr);
+ struct data_reference *drb = DDR_B (ddr);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "(compute_affine_dependence\n");
+ fprintf (dump_file, " (stmt_a = \n");
+ print_generic_expr (dump_file, DR_STMT (dra), 0);
+ fprintf (dump_file, ")\n (stmt_b = \n");
+ print_generic_expr (dump_file, DR_STMT (drb), 0);
+ fprintf (dump_file, ")\n");
+ }
+
+ /* Analyze only when the dependence relation is not yet known. */
+ if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
+ {
+ if (access_functions_are_affine_or_constant_p (dra)
+ && access_functions_are_affine_or_constant_p (drb))
+ subscript_dependence_tester (ddr);
+
+ /* As a last case, if the dependence cannot be determined, or if
+ the dependence is considered too difficult to determine, answer
+ "don't know". */
+ else
+ finalize_ddr_dependent (ddr, chrec_dont_know);
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, ")\n");
+}
+
+/* Compute a subset of the data dependence relation graph. Don't
+ compute read-read relations, and avoid the computation of the
+ opposite relation, i.e. when AB has been computed, don't compute BA.
+ DATAREFS contains a list of data references, and the result is set
+ in DEPENDENCE_RELATIONS. */
+
+static void
+compute_all_dependences (varray_type datarefs,
+ varray_type *dependence_relations)
+{
+ unsigned int i, j, N;
+
+ N = VARRAY_ACTIVE_SIZE (datarefs);
+
+ for (i = 0; i < N; i++)
+ for (j = i; j < N; j++)
+ {
+ struct data_reference *a, *b;
+ struct data_dependence_relation *ddr;
+
+ a = VARRAY_GENERIC_PTR (datarefs, i);
+ b = VARRAY_GENERIC_PTR (datarefs, j);
+ ddr = initialize_data_dependence_relation (a, b);
+
+ VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
+ compute_affine_dependence (ddr);
+ compute_subscript_distance (ddr);
+ }
+}
+
+/* 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, varray_type *datarefs)
+{
+ bool dont_know_node_not_inserted = true;
+ basic_block bb, *bbs;
+ unsigned int i;
+ block_stmt_iterator bsi;
+
+ bbs = get_loop_body (loop);
+
+ for (i = 0; i < loop->num_nodes; i++)
+ {
+ bb = bbs[i];
+
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ tree stmt = bsi_stmt (bsi);
+ stmt_ann_t ann = stmt_ann (stmt);
+
+ if (TREE_CODE (stmt) != MODIFY_EXPR)
+ continue;
+
+ if (!VUSE_OPS (ann)
+ && !V_MUST_DEF_OPS (ann)
+ && !V_MAY_DEF_OPS (ann))
+ continue;
+
+ /* In the GIMPLE representation, a modify expression
+ contains a single load or store to memory. */
+ if (TREE_CODE (TREE_OPERAND (stmt, 0)) == ARRAY_REF)
+ VARRAY_PUSH_GENERIC_PTR
+ (*datarefs, analyze_array (stmt, TREE_OPERAND (stmt, 0),
+ false));
+
+ else if (TREE_CODE (TREE_OPERAND (stmt, 1)) == ARRAY_REF)
+ VARRAY_PUSH_GENERIC_PTR
+ (*datarefs, analyze_array (stmt, TREE_OPERAND (stmt, 1),
+ true));
+ else
+ {
+ if (dont_know_node_not_inserted)
+ {
+ struct data_reference *res;
+ res = xmalloc (sizeof (struct data_reference));
+ DR_STMT (res) = NULL_TREE;
+ DR_REF (res) = NULL_TREE;
+ DR_ACCESS_FNS (res) = NULL;
+ DR_BASE_NAME (res) = NULL;
+ DR_IS_READ (res) = false;
+ VARRAY_PUSH_GENERIC_PTR (*datarefs, res);
+ dont_know_node_not_inserted = false;
+ }
+ }
+
+ /* When there are no defs in the loop, the loop is parallel. */
+ if (NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) > 0
+ || NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt)) > 0)
+ bb->loop_father->parallel_p = false;
+ }
+
+ if (bb->loop_father->estimated_nb_iterations == NULL_TREE)
+ compute_estimated_nb_iterations (bb->loop_father);
+ }
+
+ // dump_data_references(stdout,datarefs);
+
+ free (bbs);
+
+ return dont_know_node_not_inserted ? NULL_TREE : chrec_dont_know;
+}
+
+\f
+
+/* This section contains all the entry points. */
+
+/* Given a loop nest LOOP, the following vectors are returned:
+ *DATAREFS is initialized to all the array elements contained in this loop,
+ *DEPENDENCE_RELATIONS contains the relations between the data references. */
+
+void
+compute_data_dependences_for_loop (unsigned nb_loops,
+ struct loop *loop,
+ varray_type *datarefs,
+ varray_type *dependence_relations)
+{
+ unsigned int i;
+ varray_type allrelations;
+
+
+ /* If one of the data references is not computable, give up without
+ spending time to compute other dependences. */
+ if (find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
+ {
+ struct data_dependence_relation *ddr;
+
+ /* Insert a single relation into dependence_relations:
+ chrec_dont_know. */
+ ddr = initialize_data_dependence_relation (NULL, NULL);
+ VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
+ build_classic_dist_vector (ddr, nb_loops, loop->depth);
+ build_classic_dir_vector (ddr, nb_loops, loop->depth);
+ return;
+ }
+
+
+
+ VARRAY_GENERIC_PTR_INIT (allrelations, 1, "Data dependence relations");
+ compute_all_dependences (*datarefs, &allrelations);
+
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (allrelations); i++)
+ {
+ struct data_dependence_relation *ddr;
+ ddr = VARRAY_GENERIC_PTR (allrelations, i);
+ if (build_classic_dist_vector (ddr, nb_loops, loop->depth))
+ {
+ VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
+ build_classic_dir_vector (ddr, nb_loops, loop->depth);
+ }
+ }
+
+ // dump_data_references(stdout,datarefs);
+
+}
+
+
+/*PATCH
+
+void
+compute_data_dependences_for_loop_SK (unsigned nb_loops,
+ struct loop *loop,
+ varray_type *datarefs,
+ varray_type *dependence_relations)
+{
+ unsigned int i;
+ varray_type allrelations;
+ varray_type dummyrefs;
+ VARRAY_GENERIC_PTR_INIT (dummyrefs, 10, "dummyrefs");
+
+
+
+
+ VARRAY_GENERIC_PTR_INIT (allrelations, 1, "Data dependence relations");
+ compute_all_dependences (*datarefs, &allrelations);
+
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (allrelations); i++)
+ {
+ struct data_dependence_relation *ddr;
+ ddr = VARRAY_GENERIC_PTR (allrelations, i);
+ if (build_classic_dist_vector (ddr, nb_loops, loop->depth))
+ {
+ VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
+ build_classic_dir_vector (ddr, nb_loops, loop->depth);
+ }
+ }
+
+ // dump_data_references(stdout,datarefs);
+
+}
+
+*/
+/* PATCH
+void process_for_overlap(varray_type *dependence_relations)
+{
+ unsigned int j,i;
+ printf("Hello\n");
+ int temp_overlapa,temp_overlapb;
+
+ for (j = 0; j < VARRAY_ACTIVE_SIZE (*dependence_relations); j++)
+ {
+
+
+ struct data_dependence_relation *ddr =
+ (struct data_dependence_relation *)
+ VARRAY_GENERIC_PTR (*dependence_relations, j);
+
+ printf(" The references in question are %d %d\n",ddr->a->groupid,ddr->b->groupid);
+
+
+ if(DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
+ {
+ ddr->a->non_ug_overlap=1;
+ ddr->b->non_ug_overlap=1;
+
+
+ }
+
+// if ((DDR_ARE_DEPENDENT (ddr) == NULL_TREE) && (ddr->a->groupid != ddr->b->groupid))
+ if ((DDR_ARE_DEPENDENT (ddr) == NULL_TREE))
+ {
+
+ printf(" Null tree with %d %d \n", ddr->a->groupid,ddr->b->groupid);
+
+ if(ddr->a->groupid =ddr->b->groupid)
+
+ dump_data_reference(stdout,ddr->a);
+ printf("\n");
+ dump_data_reference(stdout,ddr->b);
+ printf("\n");
+ lambda_vector vector;
+ int vect_len=DDR_SIZE_VECT (ddr);
+ vector =DDR_DIST_VECT (ddr);
+ for (i = vect_len -1; i >= 0 ; i--)
+ {
+ printf(" the vector %d %d \n",i,vector[i]);
+ if(vector[i] < 0)//b is the source , a is sink
+ {
+ if((ddr->a->is_read == 0) && (ddr->b->is_read ==1))
+ {
+ temp_overlapa=0; // overlap can be ignored
+ temp_overlapb=0;
+
+
+ }
+ else
+ {
+ temp_overlapa=i+1;
+ temp_overlapb=i+1;
+ break;
+ }
+ }
+
+
+ else if(vector[i] > 0)
+ {
+ if((ddr->a->is_read == 1) && (ddr->b->is_read ==0))
+ {
+ temp_overlapa=0; // overlap can be ignored
+ temp_overlapb=0;
+
+
+ }
+ else
+ {
+ temp_overlapa=i+1;
+ temp_overlapb=i+1;
+ break;
+ }
+
+ }
+
+
+ // Verify - a 0 might indicate a loop independent dependence only if there are no loop carried dependences.
+
+
+ }
+
+ printf(" No loop carried dependence \n");
+ if(temp_overlapa ==0 )
+ {
+ if((ddr->a->is_read == 1) && (ddr->b->is_read ==0))
+ {
+ printf(" Overlap can be ignored \n");
+ temp_overlapa=0; // overlap can be ignored
+ temp_overlapb=0;
+
+
+ }
+
+
+ else
+ {
+ printf(" Overlap cant be ignored \n");
+ temp_overlapa=i+1;
+
+ temp_overlapb=i+1;
+ //printf(" the reference of b is %d %d\n",ddr->b->refid,ddr->b->overlap);
+ break;
+ }
+ }
+
+ if(temp_overlapa != 0)
+ {
+
+ if(ddr->a->groupid == ddr->b->groupid)
+ {
+ if(temp_overlapa < ddr->a->ug_overlap)
+ ddr->a->ug_overlap =temp_overlapa;
+
+ }
+ else
+ {
+ if(temp_overlapa < ddr->a->non_ug_overlap)
+ ddr->a->non_ug_overlap =temp_overlapa;
+
+
+
+ }
+
+ }
+ if(temp_overlapb != 0)
+ {
+
+ if(ddr->a->groupid == ddr->b->groupid)
+ {
+
+ if(temp_overlapb < ddr->b->ug_overlap)
+ ddr->b->ug_overlap =temp_overlapb;
+
+ }
+ else
+ {
+ if(temp_overlapb < ddr->b->non_ug_overlap)
+ ddr->b->non_ug_overlap =temp_overlapb;
+ }
+ }
+
+
+
+ fprintf (stdout, "DISTANCE_V (");
+ print_lambda_vector (stdout, DDR_DIST_VECT (ddr),
+ DDR_SIZE_VECT (ddr));
+ fprintf (stdout, ")\n");
+ fprintf (stdout, "DIRECTION_V (");
+ print_lambda_vector (stdout, DDR_DIR_VECT (ddr),
+ DDR_SIZE_VECT (ddr));
+ fprintf (stdout, ")\n");
+ }
+ }
+ fprintf (stdout, "\n\n");
+
+}
+
+
+
+
+void
+dump_updated_data_references (FILE *file,
+ varray_type datarefs)
+{
+ unsigned int i;
+
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
+ dump_updated_data_reference (file, VARRAY_GENERIC_PTR (datarefs, i));
+}
+
+void
+dump_updated_data_reference (FILE *outf,
+ struct data_reference *dr)
+{
+ unsigned int i;
+
+ fprintf (outf, "(Data Ref: \n stmt: ");
+ print_generic_stmt (outf, DR_STMT (dr), 0);
+ fprintf (outf, " ref: ");
+ print_generic_stmt (outf, DR_REF (dr), 0);
+ fprintf (outf, " base_name: ");
+ print_generic_stmt (outf, DR_BASE_NAME (dr), 0);
+
+ for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
+ {
+ fprintf (outf, " Access function %d: ", i);
+ print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0);
+
+ }
+ fprintf (outf, " Overlap information \n");
+ fprintf (outf, " Groupid %d reference %d Overlap %d %d\n",dr->groupid,dr->refid,dr->ug_overlap,dr->non_ug_overlap);
+
+ fprintf (outf, ")\n");
+}
+*/
+
+tree
+examine_data_references_in_loop (struct loop *loop, bblock_info** basic_block_list)
+//examine_data_references_in_loop (struct loop *loop, varray_type *datarefs)
+{
+ bool dont_know_node_not_inserted = true;
+ basic_block bb, *bbs;
+ unsigned int i;
+ block_stmt_iterator bsi;
+
+
+ bbs = get_loop_body (loop);
+ int index;
+
+
+ //varray_type myrefs;
+
+ printf(" Some info on this loop with id %d\n",loop->num);
+ printf(" No of blocks in this %d \n",loop->num_nodes);
+ printf(" The level of this loop %d \n",loop->level);
+ printf(" The Depth of this loop %d \n",loop->depth);
+ // printf(" The outer of this loop %d \n",loop->outer->num);
+ // printf(" The Depth of this loop %d \n",loop->depth);
+ //printf(" The index of loop latch %d \n",loop->latch->index);
+ // printf(" The header of loop %d \n",loop->header->index);
+// printf(" The first block in loop %d \n",loop->first->index);
+// printf(" The last block in loop %d \n",loop->last->index);
+
+// printf(" The starting basic block %d \n",loop->first->index);
+ // printf(" The last basic block %d \n",loop->last->index);
+
+ for (i = 0; i < loop->num_nodes; i++)
+ {
+
+
+
+ bb = bbs[i];
+ printf("Basic block %d with index %d with depth %d belonging to loop %d\n",i,bb->index,bb->loop_depth,bb->loop_father->num);
+// printf(" This basic belongs to %d with depth %d\n",bb->loop_father->num,loop->depth);
+ index=bb->index;
+
+
+ // if( basic_block_list[index]->depth > loop->depth)
+ {
+ printf(" Node %d already present \n",i);
+ // basic_block_list[index]->loop_num =loop->num;
+ // basic_block_list[index]->depth = loop->depth;
+ basic_block_list[i]->depth = bb->loop_depth;
+ basic_block_list[i]->num=bb->loop_father->num;
+
+
+
+ //printf(" Node %d already present done\n",i);
+
+ }
+
+// else
+ {
+
+ printf(" Collecting references \n");
+ // varray_clear(basic_block_list[i]->myrefs);
+
+ printf(" Traversing basic block lists \n");
+
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ tree stmt = bsi_stmt (bsi);
+ stmt_ann_t ann = stmt_ann (stmt);
+
+ if (TREE_CODE (stmt) != MODIFY_EXPR)
+ continue;
+
+ if (!VUSE_OPS (ann)
+ && !V_MUST_DEF_OPS (ann)
+ && !V_MAY_DEF_OPS (ann))
+ continue;
+
+ if (TREE_CODE (TREE_OPERAND (stmt, 0)) == ARRAY_REF)
+ {
+
+ VARRAY_PUSH_GENERIC_PTR
+ (basic_block_list[i]->myrefs, analyze_array (stmt, TREE_OPERAND (stmt, 0),
+ false));
+
+ }
+
+ else if (TREE_CODE (TREE_OPERAND (stmt, 1)) == ARRAY_REF)
+ VARRAY_PUSH_GENERIC_PTR
+ (basic_block_list[i]->myrefs, analyze_array (stmt, TREE_OPERAND (stmt, 1),
+ true));
+ else
+ {
+ if (dont_know_node_not_inserted)
+ {
+
+ printf(" Inside dont know node not inserted \n");
+ struct data_reference *res;
+ res = xmalloc (sizeof (struct data_reference));
+ DR_STMT (res) = NULL_TREE;
+ DR_REF (res) = NULL_TREE;
+ DR_ACCESS_FNS (res) = NULL;
+ DR_BASE_NAME (res) = NULL;
+ DR_IS_READ (res) = false;
+ VARRAY_PUSH_GENERIC_PTR (basic_block_list[i]->myrefs, res);
+ dont_know_node_not_inserted = false;
+ }
+ }
+
+
+ }
+ }
+
+ // printf(" Dumping data references \n");
+ //examine_data_references(*datarefs);
+
+ dump_data_references(stdout,basic_block_list[i]->myrefs);
+ // printf("\n");
+
+
+ }
+
+
+ free (bbs);
+
+ return dont_know_node_not_inserted ? NULL_TREE : chrec_dont_know;
+}
+
+tree
+insert_annotations (struct loop *loop)
+//examine_data_references_in_loop (struct loop *loop, varray_type *datarefs)
+{
+ bool dont_know_node_not_inserted = true;
+ basic_block bb, *bbs;
+ unsigned int i;
+ block_stmt_iterator bsi,new_bsi;
+ tree stmt,treenode;
+
+
+ bbs = get_loop_body (loop);
+ int index;
+ printf(" *********BEFORE****************************************\n");
+ bb = bbs[0];
+ bsi = bsi_start (bb);
+ stmt = bsi_stmt (bsi);
+ for (treenode = stmt; treenode; treenode = TREE_CHAIN(treenode))
+ print_generic_stmt(stdout,treenode,0);
+ printf(" *************************************************\n");
+
+
+ for (i = 0; i < loop->num_nodes; i++)
+ {
+
+
+
+ bb = bbs[i];
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ stmt = bsi_stmt (bsi);
+ if(stmt->exp.common.refid != 0)
+ {
+ stmt->exp.common.refid=0;
+ /*
+ printf(" The refid is %d ",stmt->exp.common.refid);
+ print_generic_stmt(stdout,stmt,0);
+
+ //tree new_tree=build_empty_stmt();
+ tree id = get_identifier ("foo");
+ // printf(" call node created \n");
+
+ tree t = build_function_type_list (void_type_node,integer_type_node,NULL_TREE);
+ // printf(" call node created \n");
+
+ // tree fntype=build_function_type(void_type_node,t);
+
+ tree fn_decl = build_decl (FUNCTION_DECL, id, t);
+ printf(" call node created \n");
+
+ DECL_EXTERNAL (fn_decl) = 1;
+ TREE_PUBLIC (fn_decl) = 1;
+ DECL_ARTIFICIAL (fn_decl) = 1;
+ TREE_NOTHROW (fn_decl) = 1;
+
+
+
+ tree res_decl = build_decl (RESULT_DECL, NULL_TREE, void_type_node);
+ DECL_ARTIFICIAL (res_decl) = 1;
+ DECL_IGNORED_P (res_decl) = 1;
+ DECL_RESULT (fn_decl) = res_decl;
+
+ TREE_STATIC (fn_decl) = 0;
+ TREE_USED (fn_decl) = 1;
+ DECL_ARTIFICIAL (fn_decl) = 1;
+ DECL_IGNORED_P (fn_decl) = 0;
+ TREE_PUBLIC (fn_decl) = 0;
+ DECL_UNINLINABLE (fn_decl) = 1;
+ DECL_EXTERNAL (fn_decl) = 0;
+ DECL_CONTEXT (fn_decl) = NULL_TREE;
+
+ tree fn_data_arg = build_decl (PARM_DECL, NULL_TREE, void_type_node);
+ DECL_ARGUMENTS (fn_decl) = fn_data_arg;
+
+ tree call = build_function_call_expr (fn_decl,build_tree_list(NULL_TREE,build_int_cst_wide(NULL,5,0)));
+ printf(" call node created \n");
+ */
+ tree fn, type;
+
+ type = build_function_type_list (void_type_node, void_type_node, NULL_TREE);
+ tree id = get_identifier ("foo");
+ tree fn_decl = build_decl (FUNCTION_DECL, id, type);
+ DECL_EXTERNAL (fn_decl) = 1;
+ TREE_PUBLIC (fn_decl) = 1;
+ DECL_ARTIFICIAL (fn_decl) = 1;
+ TREE_NOTHROW (fn_decl) = 1;
+
+ tree call=build_function_call_expr (fn_decl, NULL_TREE);
+
+
+
+
+
+ // TREE_SET_CODE(new_tree,CALL_EXPR);
+ bsi_insert_before(&bsi,call,BSI_CONTINUE_LINKING);
+ printf(" call node inserted \n");
+
+ print_generic_stmt(stdout,call,0);
+ printf("\n");
+ stmt->exp.common.refid=0;
+
+ }
+
+ }
+
+ }
+
+
+ printf(" ***************AFTER**********************************\n");
+ bb = bbs[0];
+ bsi = bsi_start (bb);
+ stmt = bsi_stmt (bsi);
+ for (treenode = stmt; treenode; treenode = TREE_CHAIN(treenode))
+ print_generic_stmt(stdout,treenode,0);
+ printf(" *************************************************\n");
+
+ free (bbs);
+
+ printf(" Finished inserting annnotation \n");
+
+ return dont_know_node_not_inserted ? NULL_TREE : chrec_dont_know;
+}
+
+int compute_UG_sets(varray_type datarefs)
+{
+
+ unsigned int i, j, N,ret,k;
+ struct data_reference *a, *b;
+
+
+
+ N = VARRAY_ACTIVE_SIZE (datarefs);
+
+ groupid=1;
+
+
+ /*for (i = 0; i < N; i++)
+ {
+
+
+ a = VARRAY_GENERIC_PTR (datarefs, i);
+ a->refid=0;
+ a->groupid=0;
+ a->overlap=0;
+
+ }*/
+
+
+
+
+ for (i = 0; i < N; i++)
+ {
+
+ printf("Comparing %d\n",i);
+ a = VARRAY_GENERIC_PTR (datarefs, i);
+//Pa a->refid=refid++;
+ /*
+ if(timestamp_flag)
+ {
+ fprintf(refFile,"#Promote %d ",a->refid);
+ fprintf(refFile," %d ",a->depth);
+ print_generic_stmt (refFile, DR_BASE_NAME (a), 0);
+ fprintf(refFile,"\n");
+
+ printf(" Assigned refid %d to ",a->refid);
+
+ print_generic_stmt (stdout,a->stmt, 0);
+ printf("\n");
+
+
+
+
+ }
+ */
+
+// a->stmt->exp.common.refid=a->refid;
+ a->stmt->exp.common.refid=refid++;
+
+
+ dump_data_reference(stdout,a);
+ /* PATCH
+ if(a->groupid !=0)
+ continue;
+ a->groupid = groupid ++;
+ */
+
+ for (j = 0; j < N; j++)
+ {
+
+ if(j==i)
+ continue;
+
+// struct data_dependence_relation *ddr;
+
+ b = VARRAY_GENERIC_PTR (datarefs, j);
+
+ printf("\n");
+ printf("with****************%d\n",j);
+ dump_data_reference(stdout,b);
+
+ tree base_a=DR_BASE_NAME(a);
+
+ tree base_b=DR_BASE_NAME(b);
+
+ if(base_a != base_b)
+ {
+ printf("Not equal \n");
+ continue;
+ }
+
+ if(DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS(b))
+ printf("Not equal \n");
+
+
+ else
+ {
+
+ for (k = 0; k < DR_NUM_DIMENSIONS (a); k++)
+ {
+ fprintf (stdout, " Comparing Access function %d: ", k);
+ print_generic_stmt (stdout, DR_ACCESS_FN (a, k), 0);
+ print_generic_stmt (stdout, DR_ACCESS_FN (b, k), 0);
+ printf("\n");
+ ret=1;
+
+ ret=simple_chrec_equal(DR_ACCESS_FN (a, k),DR_ACCESS_FN (b, k));
+ if(ret == -1)
+ break;
+
+ }
+ }
+ if(ret==-1)
+ printf("Not Equal");
+ else
+ {
+// b->groupid =a->groupid;
+ printf(" equal\n");
+ }
+ printf("\n********************\n");
+
+
+ }
+ }
+
+
+
+
+ return(1);
+
+
+}
+
+
+int
+simple_chrec_equal (tree t1, tree t2)
+{
+ enum tree_code code1, code2;
+ int cmp;
+ int i;
+ int ret;
+
+
+
+
+
+ code1 = TREE_CODE (t1);
+ code2 = TREE_CODE (t2);
+
+ printf(" Checking high level\n");
+
+ if(code1 != code2)
+ return(-1);
+
+
+
+ if(code1==POLYNOMIAL_CHREC)
+ {
+ printf(" Polynomial \n");
+ printf("Checking left tree\n");
+
+ tree tree_left_t1=CHREC_LEFT (t1);
+ tree tree_left_t2=CHREC_LEFT (t2);
+ code1=TREE_CODE(tree_left_t1);
+ code2=TREE_CODE(tree_left_t2);
+ if(code1 == code2)
+ {
+ if(code1== POLYNOMIAL_CHREC)
+ {
+ ret=simple_chrec_equal(tree_left_t1,tree_left_t2);
+ if(ret == -1)
+ return(ret);
+
+ }
+
+ }
+
+
+ else
+ return(-1);
+
+ printf(" Checking right tree \n");
+ tree tree_right_t1=CHREC_RIGHT(t1);
+ tree tree_right_t2=CHREC_RIGHT(t2);
+
+ code1=TREE_CODE(tree_right_t1);
+ code2=TREE_CODE(tree_right_t2);
+ if(code1 == code2)
+ {
+
+ /*if(TREE_CODE (tree_right_t2) == INTEGER_CST)
+ {
+ printf("low part %d \n", TREE_INT_CST_LOW(tree_right_t1));
+ printf(" high part%d \n", TREE_INT_CST_HIGH(tree_right_t1));
+ printf("low part-2 %d \n", TREE_INT_CST_LOW(tree_right_t2));
+ printf(" high part-2 %d \n", TREE_INT_CST_HIGH(tree_right_t2));
+
+ }
+ */
+
+ if(code1== POLYNOMIAL_CHREC)
+ {
+ ret=simple_chrec_equal(tree_right_t1,tree_right_t2);
+ if(ret == -1)
+ return(ret);
+
+ }
+
+
+ else if ( (TREE_CODE (tree_right_t1) == INTEGER_CST)
+ && ((TREE_INT_CST_LOW (tree_right_t1) != TREE_INT_CST_LOW (tree_right_t2))
+ || (TREE_INT_CST_HIGH (tree_right_t1) != TREE_INT_CST_HIGH (tree_right_t2))))
+ {
+ return(-1);
+ }
+
+ }
+
+
+ else
+ return(-1);
+
+
+ printf(" Checking index variable \n");
+
+ tree tree_var_t1=CHREC_VAR(t1);
+ tree tree_var_t2=CHREC_VAR(t2);
+ code1=TREE_CODE(tree_var_t1);
+ code2=TREE_CODE(tree_var_t2);
+ if(TREE_CODE (tree_var_t2) == INTEGER_CST)
+ {
+ printf("low part %d \n", TREE_INT_CST_LOW(tree_var_t1));
+ printf(" high part%d \n", TREE_INT_CST_HIGH(tree_var_t1));
+ printf("low part-2 %d \n", TREE_INT_CST_LOW(tree_var_t2));
+ printf(" high part-2 %d \n", TREE_INT_CST_HIGH(tree_var_t2));
+
+ }
+
+ if (TREE_CODE (tree_var_t1) == INTEGER_CST
+ && TREE_CODE (tree_var_t2) == INTEGER_CST
+ && TREE_INT_CST_LOW (tree_var_t1) == TREE_INT_CST_LOW (tree_var_t2)
+ && TREE_INT_CST_HIGH (tree_var_t1) == TREE_INT_CST_HIGH (tree_var_t2))
+ return(1);
+
+
+ else
+ {
+ printf(" Not equal \n");
+ return(-1);
+ }
+
+
+ }
+
+
+
+ }
+
+
+ /* PATCH
+ void compute_sizes(struct loop* loop, varray_type datarefs)
+ {
+ unsigned int i, j, N,ret,k;
+ struct data_reference *a, *b;
+ int subscript_spanned=0;
+ int temp_domain_size;
+ int subscript_spanned_at_current_depth;
+ int plane_flag=0; // Indicates of two dimensions are adjacent imen
+
+ int union_flag;
+ int size_of_element;
+
+ N = VARRAY_ACTIVE_SIZE (datarefs);
+
+ for (i = 0; i < N; i++)
+ {
+
+
+ a = VARRAY_GENERIC_PTR (datarefs, i);
+
+ printf(" Number of dimensions %d\n",DR_NUM_DIMENSIONS(a));
+ int* dimension_sizes;
+ dimension_sizes=(int*)xmalloc(sizeof(int)*DR_NUM_DIMENSIONS (a));
+ tree t= array_ref_element_size(DR_REF(a));
+
+ size_of_element= TREE_INT_CST_LOW(t);
+ a->size_of_element=size_of_element;
+
+
+ get_dimension_size(DR_BASE_NAME (a),DR_NUM_DIMENSIONS(a),dimension_sizes);
+
+ int depth=a->depth;
+
+ printf(" Reference found at depth %d \n",depth);
+
+
+ int* subscript;
+ subscript=(int*)xmalloc(sizeof(int)*DR_NUM_DIMENSIONS (a));
+ int* subscript_at_current_depth;
+ subscript_at_current_depth=(int*)xmalloc(sizeof(int)*DR_NUM_DIMENSIONS (a));
+
+
+
+ int size;
+ int domain_size=-1;
+
+ while(depth > 0)
+ {
+
+
+ subscript_spanned = 0;
+ subscript_spanned_at_current_depth=0;
+ plane_flag=0;
+
+ if(a->non_ug_overlap >= depth)
+ {
+ a->size[depth]=0;
+ depth --;
+ continue ;
+
+ }
+
+ union_flag=0;
+
+ if(a->ug_overlap >= depth)
+ {
+ union_flag=1; // indicates ug's overlap - so the size calculated is good enough for the whole ug set
+
+ }
+
+
+
+
+ for (k = 0; k < DR_NUM_DIMENSIONS (a); k++)
+ {
+
+ // for a loop depth, if there is an index variable affecting belonging to the same loop depth
+ // in the polynomial estimate size as size of that subscript // this is conservative else
+ // estimate size as 1
+ int ret=check_if_depth_occurs_in_subscript(k,depth,a);
+ if(ret ==1)
+ {
+ subscript_at_current_depth[k]=1;
+ printf(" Subscript %d being evaluated for depth %d set \n",k,depth);
+ subscript_spanned_at_current_depth ++;
+
+ // printf(" Subscript %d being evaluated for depth %d set \n",k,depth);
+ }
+ // else
+ // printf(" Subscript %d being evaluated for depth %d not set \n",k,depth);
+
+ }
+
+
+ for (k = 0; k < DR_NUM_DIMENSIONS (a); k++)
+ {
+ if(subscript[k] ==1)
+ subscript_spanned ++;
+ }
+
+ printf("subscript spanned %d current subscript_spanned %d \n",subscript_spanned,subscript_spanned_at_current_depth);
+
+ if(subscript_spanned_at_current_depth> 0)
+ {
+
+ if(subscript_spanned_at_current_depth == 2)
+ {
+ printf(" Special case diagonal \n");
+ printf(" The id of loop where this reference wasfound %d \n",a->num);
+ // diagonal // size of smallest dimension
+ domain_size=iterations_estimate[a->num]; // Induction variable estimate
+
+ }
+
+ else
+ {
+ domain_size=1;
+
+ for (k = 0; k < DR_NUM_DIMENSIONS (a); k++)
+ {
+ if(subscript_at_current_depth[k] ==1)
+ domain_size=dimension_sizes[k]*domain_size;
+ }
+
+ }
+ }
+
+ else
+ domain_size=1;
+
+
+ printf(" The size just from this level is %d \n",domain_size);
+
+ for (k = 0; k < DR_NUM_DIMENSIONS (a); k++)
+ {
+ if(subscript[k] ==1)
+ domain_size=dimension_sizes[k]*domain_size;
+ }
+ a->size[depth]=domain_size;
+
+ if(union_flag)
+ a->size[depth] - a->size[depth]*-1; // Consider the whole partition instead of individual reference
+
+
+ // Merge
+
+ for (k = 0; k < DR_NUM_DIMENSIONS (a); k++)
+ {
+ if(subscript_at_current_depth[k] ==1)
+ subscript[k] =1;
+
+ }
+
+ for (k = 0; k < DR_NUM_DIMENSIONS (a); k++)
+ {
+ subscript_at_current_depth[k] =0;
+
+ }
+
+
+ subscript_spanned_at_current_depth=0;
+ printf(" Size at depth %d found as %d \n",depth,domain_size);
+
+ depth --;
+ if(depth == 0)
+ break;
+
+ } // end of while
+
+
+
+
+ }
+
+ }
+
+
+ void dump_size_information(struct loop* loop, varray_type datarefs)
+ {
+
+ int N, i,j;
+
+
+
+ struct data_reference *a,*b;
+ int depth,level;
+
+
+ N = VARRAY_ACTIVE_SIZE (datarefs);
+
+
+
+
+
+
+
+ int varid=1;
+
+
+ for(level=loop->level;level > 0;level--)
+ {
+ depth=loop->level-level +1;
+
+ fprintf(refinfo,"#Depth %d \n",depth);
+ fprintf(refinfo,"\n");
+
+ for (i = 0; i < N; i++)
+ {
+
+ a = VARRAY_GENERIC_PTR (datarefs, i);
+ if(depth > a->depth)
+ continue;
+
+ if(a->size[depth] == 0)
+ continue;
+
+ fprintf(refinfo,"#Varid %d \n",varid++);
+ int count =1;
+
+ fprintf(refinfo,"#Members %d ",a->refid);
+
+
+ for (j = 0; j < N; j++)
+ {
+
+ if(j==i)
+ continue;
+
+ b = VARRAY_GENERIC_PTR (datarefs, j);
+
+ if(a->groupid != b->groupid)
+ continue;
+
+ if((depth < a->ug_overlap) || (depth < b->ug_overlap))
+ continue;
+
+
+ count++;
+ fprintf(refinfo,"%d ",b->refid);
+
+ b->size[depth]=0;
+
+
+
+ }
+
+ fprintf(refinfo,"\n");
+ fprintf(refinfo,"#Count %d \n",count);
+ fprintf(refinfo,"#Size %d \n",a->size[depth]*a->size_of_element);
+ fprintf(refinfo,"\n");
+ a->size[depth]=0;
+
+ }
+
+ }
+
+ }
+
+
+
+
+
+int check_if_depth_occurs_in_subscript(int k, int depth, struct data_reference* dr)
+
+ {
+
+
+ enum tree_code code1, code2;
+
+ code1 = TREE_CODE (DR_ACCESS_FN (dr, k));
+
+ printf(" Checking- high level\n");
+
+
+
+ if(code1==POLYNOMIAL_CHREC)
+ {
+
+
+ int index =get_loop_index(DR_ACCESS_FN(dr,k));
+ printf(" The index of subscript %d is %d and depth %d\n",k,index,depth);
+
+ if(index == depth)
+ return(1);
+
+ if(index < 1)
+ {
+
+ printf(" Non separable indices \n");
+
+ tree tree_left_t1=CHREC_LEFT (DR_ACCESS_FN (dr, k));
+ code1=TREE_CODE(tree_left_t1);
+ if(code1== POLYNOMIAL_CHREC)
+ {
+
+ if(check_if_depth_occurs_in_subscript(k,depth,tree_left_t1))
+ return(1);
+ else
+ return(-1);
+
+ }
+
+ }
+
+
+
+ }
+
+ return(-1);
+
+ }
+
+
+
+int get_loop_index(tree node)
+{
+
+ if(TREE_CODE (node) == POLYNOMIAL_CHREC)
+ {
+
+ return(TREE_INT_CST_LOW(CHREC_VAR (node)));
+
+
+ }
+ else
+ {
+ printf(" Node is not affine \n");
+ return(-1);
+
+ }
+
+
+
+ }
+
+
+int get_dimension_size(tree node,int k, int* dimension_sizes)
+{
+ tree tmp;
+ int i =0;
+
+
+ tmp = TREE_TYPE (node);
+ while (TREE_CODE (tmp) == ARRAY_TYPE)
+ {
+ int size = get_array_domain ( TYPE_DOMAIN (tmp));
+ tmp = TREE_TYPE (tmp);
+ dimension_sizes[k-i-1]=size;
+ printf("size is - %d \n",size);
+ i ++;
+ }
+
+
+
+}
+
+int get_array_domain(tree domain)
+{
+ if (domain)
+ {
+ tree min = TYPE_MIN_VALUE (domain);
+ tree max = TYPE_MAX_VALUE (domain);
+
+ if (min && max
+ && integer_zerop (min)
+ && host_integerp (max, 0))
+ {
+
+ return(TREE_INT_CST_LOW (max)+1);
+ }
+
+ }
+ return(0);
+}
+
+*/
+
+/* Entry point (for testing only). Analyze all the data references
+ and the dependence relations.
+
+ The data references are computed first.
+
+ A relation on these nodes is represented by a complete graph. Some
+ of the relations could be of no interest, thus the relations can be
+ computed on demand.
+
+ In the following function we compute all the relations. This is
+ just a first implementation that is here for:
+ - for showing how to ask for the dependence relations,
+ - for the debugging the whole dependence graph,
+ - for the dejagnu testcases and maintenance.
+
+ It is possible to ask only for a part of the graph, avoiding to
+ compute the whole dependence graph. The computed dependences are
+ stored in a knowledge base (KB) such that later queries don't
+ recompute the same information. The implementation of this KB is
+ transparent to the optimizer, and thus the KB can be changed with a
+ more efficient implementation, or the KB could be disabled. */
+
+void
+analyze_all_data_dependences (struct loops *loops)
+{
+ unsigned int i;
+ varray_type datarefs;
+ varray_type dependence_relations;
+ int nb_data_refs = 10;
+
+ VARRAY_GENERIC_PTR_INIT (datarefs, nb_data_refs, "datarefs");
+ VARRAY_GENERIC_PTR_INIT (dependence_relations,
+ nb_data_refs * nb_data_refs,
+ "dependence_relations");
+
+ /* Compute DDs on the whole function. */
+ compute_data_dependences_for_loop (loops->num, loops->parray[0],
+ &datarefs, &dependence_relations);
+
+
+ if (dump_file)
+ {
+ dump_data_dependence_relations (dump_file, dependence_relations);
+ fprintf (dump_file, "\n\n");
+
+ if (dump_flags & TDF_DETAILS)
+ dump_dist_dir_vectors (dump_file, dependence_relations);
+
+ if (dump_flags & TDF_STATS)
+ {
+ unsigned nb_top_relations = 0;
+ unsigned nb_bot_relations = 0;
+ unsigned nb_basename_differ = 0;
+ unsigned nb_chrec_relations = 0;
+
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
+ {
+ struct data_dependence_relation *ddr;
+ ddr = VARRAY_GENERIC_PTR (dependence_relations, i);
+
+ if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
+ nb_top_relations++;
+
+ else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
+ {
+ struct data_reference *a = DDR_A (ddr);
+ struct data_reference *b = DDR_B (ddr);
+ bool differ_p;
+
+ if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b)
+ || (array_base_name_differ_p (a, b, &differ_p) && differ_p))
+ nb_basename_differ++;
+ else
+ nb_bot_relations++;
+ }
+
+ else
+ nb_chrec_relations++;
+ }
+
+ gather_stats_on_scev_database ();
+ }
+ }
+
+ free_dependence_relations (dependence_relations);
+ free_data_refs (datarefs);
+}
+
+/* Free the memory used by a data dependence relation DDR. */
+
+void
+free_dependence_relation (struct data_dependence_relation *ddr)
+{
+ if (ddr == NULL)
+ return;
+
+ if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr))
+ varray_clear (DDR_SUBSCRIPTS (ddr));
+ free (ddr);
+}
+
+/* Free the memory used by the data dependence relations from
+ DEPENDENCE_RELATIONS. */
+
+void
+free_dependence_relations (varray_type dependence_relations)
+{
+ unsigned int i;
+ if (dependence_relations == NULL)
+ return;
+
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
+ free_dependence_relation (VARRAY_GENERIC_PTR (dependence_relations, i));
+ varray_clear (dependence_relations);
+}
+
+/* Free the memory used by the data references from DATAREFS. */
+
+void
+free_data_refs (varray_type datarefs)
+{
+ unsigned int i;
+
+ if (datarefs == NULL)
+ return;
+
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
+ {
+ struct data_reference *dr = (struct data_reference *)
+ VARRAY_GENERIC_PTR (datarefs, i);
+ if (dr)
+ {
+ if (DR_ACCESS_FNS (dr))
+ varray_clear (DR_ACCESS_FNS (dr));
+ free (dr);
+ }
+ }
+ varray_clear (datarefs);
+}
+
--- tree-data-ref.c 2005-07-27 14:37:23.000000000 -0400
+++ tree-data-ref.cmodified 2005-07-29 10:59:27.000000000 -0400
@@ -1,6 +1,6 @@
-/* Data references and dependences detectors.
+/* Linear Loop transforms
Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
- Contributed by Sebastian Pop <s.pop@laposte.net>
+ Contributed by Daniel Berlin <dberlin@dberlin.org>.
This file is part of GCC.
@@ -19,60 +19,6 @@
Software Foundation, 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA. */
-/* This pass walks a given loop structure searching for array
- references. The information about the array accesses is recorded
- in DATA_REFERENCE structures.
-
- The basic test for determining the dependences is:
- given two access functions chrec1 and chrec2 to a same array, and
- x and y two vectors from the iteration domain, the same element of
- the array is accessed twice at iterations x and y if and only if:
- | chrec1 (x) == chrec2 (y).
-
- The goals of this analysis are:
-
- - to determine the independence: the relation between two
- independent accesses is qualified with the chrec_known (this
- information allows a loop parallelization),
-
- - when two data references access the same data, to qualify the
- dependence relation with classic dependence representations:
-
- - distance vectors
- - direction vectors
- - loop carried level dependence
- - polyhedron dependence
- or with the chains of recurrences based representation,
-
- - to define a knowledge base for storing the data dependence
- information,
-
- - to define an interface to access this data.
-
-
- Definitions:
-
- - subscript: given two array accesses a subscript is the tuple
- composed of the access functions for a given dimension. Example:
- Given A[f1][f2][f3] and B[g1][g2][g3], there are three subscripts:
- (f1, g1), (f2, g2), (f3, g3).
-
- - Diophantine equation: an equation whose coefficients and
- solutions are integer constants, for example the equation
- | 3*x + 2*y = 1
- has an integer solution x = 1 and y = -1.
-
- References:
-
- - "Advanced Compilation for High Performance Computing" by Randy
- Allen and Ken Kennedy.
- http://citeseer.ist.psu.edu/goff91practical.html
-
- - "Loop Transformations for Restructuring Compilers - The Foundations"
- by Utpal Banerjee.
-
-
-*/
#include "config.h"
#include "system.h"
@@ -81,8 +27,8 @@
#include "errors.h"
#include "ggc.h"
#include "tree.h"
+#include "target.h"
-/* These RTL headers are needed for basic-block.h. */
#include "rtl.h"
#include "basic-block.h"
#include "diagnostic.h"
@@ -90,2386 +36,661 @@
#include "tree-dump.h"
#include "timevar.h"
#include "cfgloop.h"
+#include "expr.h"
+#include "optabs.h"
#include "tree-chrec.h"
#include "tree-data-ref.h"
#include "tree-scalar-evolution.h"
#include "tree-pass.h"
+#include "varray.h"
+#include "lambda.h"
-/* 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. */
-
-bool
-array_base_name_differ_p (struct data_reference *a,
- struct data_reference *b,
- bool *differ_p)
-{
- tree base_a = DR_BASE_NAME (a);
- tree base_b = DR_BASE_NAME (b);
- tree ta, tb;
-
- if (!base_a || !base_b)
- return false;
-
- ta = TREE_TYPE (base_a);
- tb = TREE_TYPE (base_b);
-
- /* 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;
- }
+// ADDED_SK
+#include "dynprof.h"
- /* 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;
- }
+//int* iterations_estimate;
+//extern int timestamp_flag;
- /* 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;
- }
+/* Linear loop transforms include any composition of interchange,
+ scaling, skewing, and reversal. They are used to change the
+ iteration order of loop nests in order to optimize data locality of
+ traversals, or remove dependences that prevent
+ parallelization/vectorization/etc.
+
+ TODO: Determine reuse vectors/matrix and use it to determine optimal
+ transform matrix for locality purposes.
+ TODO: Completion of partial transforms. */
+
+/* Gather statistics for loop interchange. LOOP is the loop being
+ considered. The first loop in the considered loop nest is
+ FIRST_LOOP, and consequently, the index of the considered loop is
+ obtained by LOOP->DEPTH - FIRST_LOOP->DEPTH
+
+ Initializes:
+ - DEPENDENCE_STEPS the sum of all the data dependence distances
+ carried by loop LOOP,
+
+ - NB_DEPS_NOT_CARRIED_BY_LOOP the number of dependence relations
+ for which the loop LOOP is not carrying any dependence,
+
+ - ACCESS_STRIDES the sum of all the strides in LOOP.
+
+ Example: for the following loop,
+
+ | loop_1 runs 1335 times
+ | loop_2 runs 1335 times
+ | A[{{0, +, 1}_1, +, 1335}_2]
+ | B[{{0, +, 1}_1, +, 1335}_2]
+ | endloop_2
+ | A[{0, +, 1336}_1]
+ | endloop_1
+
+ gather_interchange_stats (in loop_1) will return
+ DEPENDENCE_STEPS = 3002
+ NB_DEPS_NOT_CARRIED_BY_LOOP = 5
+ ACCESS_STRIDES = 10694
+
+ gather_interchange_stats (in loop_2) will return
+ DEPENDENCE_STEPS = 3000
+ NB_DEPS_NOT_CARRIED_BY_LOOP = 7
+ ACCESS_STRIDES = 8010
+*/
+static void
+gather_interchange_stats (varray_type dependence_relations,
+ varray_type datarefs,
+ struct loop *loop,
+ struct loop *first_loop,
+ unsigned int *dependence_steps,
+ unsigned int *nb_deps_not_carried_by_loop,
+ unsigned int *access_strides)
+{
+ unsigned int i;
- /* Determine if different bases. */
+ *dependence_steps = 0;
+ *nb_deps_not_carried_by_loop = 0;
+ *access_strides = 0;
- /* 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)
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
{
- *differ_p = true;
- return true;
- }
+ int dist;
+ struct data_dependence_relation *ddr =
+ (struct data_dependence_relation *)
+ VARRAY_GENERIC_PTR (dependence_relations, i);
- /* 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;
- }
+ /* If we don't know anything about this dependence, or the distance
+ vector is NULL, or there is no dependence, then there is no reuse of
+ data. */
+
+ if (DDR_DIST_VECT (ddr) == NULL
+ || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know
+ || DDR_ARE_DEPENDENT (ddr) == chrec_known)
+ continue;
+
- /* Compare a record/union access and an array access. */
- if ((TREE_CODE (base_a) == VAR_DECL
- && (TREE_CODE (base_b) == COMPONENT_REF
- && TREE_CODE (TREE_OPERAND (base_b, 0)) == VAR_DECL))
- || (TREE_CODE (base_b) == VAR_DECL
- && (TREE_CODE (base_a) == COMPONENT_REF
- && TREE_CODE (TREE_OPERAND (base_a, 0)) == VAR_DECL)))
- {
- *differ_p = true;
- return true;
+
+ dist = DDR_DIST_VECT (ddr)[loop->depth - first_loop->depth];
+ if (dist == 0)
+ (*nb_deps_not_carried_by_loop) += 1;
+ else if (dist < 0)
+ (*dependence_steps) += -dist;
+ else
+ (*dependence_steps) += dist;
}
- return false;
-}
-
-/* Returns true iff A divides B. */
-
-static inline bool
-tree_fold_divides_p (tree type,
- tree a,
- tree b)
-{
- /* Determines whether (A == gcd (A, B)). */
- return integer_zerop
- (fold (build (MINUS_EXPR, type, a, tree_fold_gcd (a, b))));
-}
-
-/* Compute the greatest common denominator of two numbers using
- Euclid's algorithm. */
-
-static int
-gcd (int a, int b)
-{
-
- int x, y, z;
-
- x = abs (a);
- y = abs (b);
-
- while (x>0)
+ /* Compute the access strides. */
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
{
- z = y % x;
- y = x;
- x = z;
+ unsigned int it;
+ struct data_reference *dr = VARRAY_GENERIC_PTR (datarefs, i);
+ tree stmt = DR_STMT (dr);
+ struct loop *stmt_loop = loop_containing_stmt (stmt);
+ struct loop *inner_loop = first_loop->inner;
+
+ if (inner_loop != stmt_loop
+ && !flow_loop_nested_p (inner_loop, stmt_loop))
+ continue;
+ for (it = 0; it < DR_NUM_DIMENSIONS (dr); it++)
+ {
+ tree chrec = DR_ACCESS_FN (dr, it);
+ tree tstride = evolution_part_in_loop_num
+ (chrec, loop->num);
+
+ if (tstride == NULL_TREE
+ || TREE_CODE (tstride) != INTEGER_CST)
+ continue;
+
+ (*access_strides) += int_cst_value (tstride);
+ }
}
-
- return (y);
}
-/* Returns true iff A divides B. */
+/* Attempt to apply interchange transformations to TRANS to maximize the
+ spatial and temporal locality of the loop.
+ Returns the new transform matrix. The smaller the reuse vector
+ distances in the inner loops, the fewer the cache misses.
+ FIRST_LOOP is the loop->num of the first loop in the analyzed loop
+ nest. */
+
+
+static lambda_trans_matrix
+try_interchange_loops (lambda_trans_matrix trans,
+ unsigned int depth,
+ varray_type dependence_relations,
+ varray_type datarefs,
+ struct loop *first_loop)
+{
+ struct loop *loop_i;
+ struct loop *loop_j;
+ unsigned int dependence_steps_i, dependence_steps_j;
+ unsigned int access_strides_i, access_strides_j;
+ unsigned int nb_deps_not_carried_by_i, nb_deps_not_carried_by_j;
+ struct data_dependence_relation *ddr;
+
+ /* When there is an unknown relation in the dependence_relations, we
+ know that it is no worth looking at this loop nest: give up. */
+ ddr = (struct data_dependence_relation *)
+ VARRAY_GENERIC_PTR (dependence_relations, 0);
+ if (ddr == NULL || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
+ return trans;
+
+ /* LOOP_I is always the outer loop. */
+ for (loop_j = first_loop->inner;
+ loop_j;
+ loop_j = loop_j->inner)
+ for (loop_i = first_loop;
+ loop_i->depth < loop_j->depth;
+ loop_i = loop_i->inner)
+ {
+ gather_interchange_stats (dependence_relations, datarefs,
+ loop_i, first_loop,
+ &dependence_steps_i,
+ &nb_deps_not_carried_by_i,
+ &access_strides_i);
+ gather_interchange_stats (dependence_relations, datarefs,
+ loop_j, first_loop,
+ &dependence_steps_j,
+ &nb_deps_not_carried_by_j,
+ &access_strides_j);
+
+ /* Heuristics for loop interchange profitability:
+
+ 1. (spatial locality) Inner loops should have smallest
+ dependence steps.
+
+ 2. (spatial locality) Inner loops should contain more
+ dependence relations not carried by the loop.
+
+ 3. (temporal locality) Inner loops should have smallest
+ array access strides.
+ */
+ if (dependence_steps_i < dependence_steps_j
+ || nb_deps_not_carried_by_i > nb_deps_not_carried_by_j
+ || access_strides_i < access_strides_j)
+ {
+ lambda_matrix_row_exchange (LTM_MATRIX (trans),
+ loop_i->depth - first_loop->depth,
+ loop_j->depth - first_loop->depth);
+ /* Validate the resulting matrix. When the transformation
+ is not valid, reverse to the previous transformation. */
+ if (!lambda_transform_legal_p (trans, depth, dependence_relations))
+ lambda_matrix_row_exchange (LTM_MATRIX (trans),
+ loop_i->depth - first_loop->depth,
+ loop_j->depth - first_loop->depth);
+ }
+ }
-static inline bool
-int_divides_p (int a, int b)
-{
- return ((b % a) == 0);
+ return trans;
}
-\f
-
-/* Dump into FILE all the data references from DATAREFS. */
-
-void
-dump_data_references (FILE *file,
- varray_type datarefs)
-{
- unsigned int i;
-
- for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
- dump_data_reference (file, VARRAY_GENERIC_PTR (datarefs, i));
-}
-/* Dump into FILE all the dependence relations from DDR. */
-void
-dump_data_dependence_relations (FILE *file,
- varray_type ddr)
+void find_data_references(struct loop *loop_nest, varray_type* datarefs)
{
- unsigned int i;
- for (i = 0; i < VARRAY_ACTIVE_SIZE (ddr); i++)
- dump_data_dependence_relation (file, VARRAY_GENERIC_PTR (ddr, i));
-}
-
-/* Dump function for a DATA_REFERENCE structure. */
-void
-dump_data_reference (FILE *outf,
- struct data_reference *dr)
-{
- unsigned int i;
+ // printf(" No of loops is %d \n",loops->num);
+ unsigned int i;
+ unsigned int j;
+ int N;
- fprintf (outf, "(Data Ref: \n stmt: ");
- print_generic_stmt (outf, DR_STMT (dr), 0);
- fprintf (outf, " ref: ");
- print_generic_stmt (outf, DR_REF (dr), 0);
- fprintf (outf, " base_name: ");
- print_generic_stmt (outf, DR_BASE_NAME (dr), 0);
-
- for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
- {
- fprintf (outf, " Access function %d: ", i);
- print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0);
- }
- fprintf (outf, ")\n");
-}
-
-/* Dump function for a SUBSCRIPT structure. */
+
+ struct data_reference *a, *b;
-void
-dump_subscript (FILE *outf, struct subscript *subscript)
-{
- tree chrec = SUB_CONFLICTS_IN_A (subscript);
- fprintf (outf, "\n (subscript \n");
- fprintf (outf, " iterations_that_access_an_element_twice_in_A: ");
- print_generic_stmt (outf, chrec, 0);
- if (chrec == chrec_known)
- fprintf (outf, " (no dependence)\n");
- else if (chrec_contains_undetermined (chrec))
- fprintf (outf, " (don't know)\n");
- else
- {
- tree last_iteration = SUB_LAST_CONFLICT (subscript);
- fprintf (outf, " last_conflict: ");
- print_generic_stmt (outf, last_iteration, 0);
+ bblock_info **basic_block_list;
+ // struct loop *loop_nest = loops->parray[0];
+ basic_block_list=(bblock_info**)xmalloc(sizeof(bblock_info*)*loop_nest->num_nodes);
+ // printf(" No of loops is %d basic_blocks %d\n",loops->num,loop_nest->num_nodes);
+ printf(" basic_blocks %d\n",loop_nest->num_nodes);
+
+ for(i=0; i < loop_nest->num_nodes;i++)
+ {
+ basic_block_list[i]=(bblock_info*)xmalloc(sizeof(bblock_info));
+
+ // basic_block_list[i]->depth =0;
+
}
-
- chrec = SUB_CONFLICTS_IN_B (subscript);
- fprintf (outf, " iterations_that_access_an_element_twice_in_B: ");
- print_generic_stmt (outf, chrec, 0);
- if (chrec == chrec_known)
- fprintf (outf, " (no dependence)\n");
- else if (chrec_contains_undetermined (chrec))
- fprintf (outf, " (don't know)\n");
- else
- {
- tree last_iteration = SUB_LAST_CONFLICT (subscript);
- fprintf (outf, " last_conflict: ");
- print_generic_stmt (outf, last_iteration, 0);
+ for(i=0; i < loop_nest->num_nodes;i++)
+ {
+ basic_block_list[i]->depth =0;
+ VARRAY_GENERIC_PTR_INIT (basic_block_list[i]->myrefs, 10, "myrefs");
}
- fprintf (outf, " (Subscript distance: ");
- print_generic_stmt (outf, SUB_DISTANCE (subscript), 0);
- fprintf (outf, " )\n");
- fprintf (outf, " )\n");
-}
-
-/* Dump function for a DATA_DEPENDENCE_RELATION structure. */
-
-void
-dump_data_dependence_relation (FILE *outf,
- struct data_dependence_relation *ddr)
-{
- struct data_reference *dra, *drb;
+
+
+ printf(" Some info on this loop with id %d\n",loop_nest->num);
+ printf(" No of blocks in this %d \n",loop_nest->num_nodes);
+ printf(" The level of this loop %d \n",loop_nest->level);
+ printf(" The Depth of this loop %d \n",loop_nest->depth);
+
+ unsigned int depth = 0;
+ examine_data_references_in_loop(loop_nest,basic_block_list);
+
+
+ VARRAY_GENERIC_PTR_INIT (*datarefs, 10, "datarefs");
+ // loop_nest = loops->parray[1];
+ // printf(" The Depth of this loop %d \n",loop_nest->depth);
- dra = DDR_A (ddr);
- drb = DDR_B (ddr);
- fprintf (outf, "(Data Dep: \n");
- if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
- fprintf (outf, " (don't know)\n");
-
- else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
- fprintf (outf, " (no dependence)\n");
-
- else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
- {
- unsigned int i;
- for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
- {
- fprintf (outf, " access_fn_A: ");
- print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0);
- fprintf (outf, " access_fn_B: ");
- print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0);
- dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
- }
- if (DDR_DIST_VECT (ddr))
- {
- fprintf (outf, " distance_vect: ");
- print_lambda_vector (outf, DDR_DIST_VECT (ddr), DDR_SIZE_VECT (ddr));
- }
- if (DDR_DIR_VECT (ddr))
- {
- fprintf (outf, " direction_vect: ");
- print_lambda_vector (outf, DDR_DIR_VECT (ddr), DDR_SIZE_VECT (ddr));
- }
- }
+
+ for(j=0; j < loop_nest->num_nodes;j++)
+ {
+
+
+ N = VARRAY_ACTIVE_SIZE (basic_block_list[j]->myrefs);
- fprintf (outf, ")\n");
-}
+ for (i = 0; i < N; i++)
+ {
+
+ printf(" Examining contents \n");
+
+
+ a = VARRAY_GENERIC_PTR (basic_block_list[j]->myrefs, i);
+ // a->refid=0;
+ // a->groupid=0;
+ // a->ug_overlap=0;
+ // a->non_ug_overlap=0;
+ // a->depth=basic_block_list[j]->depth;
+ // a->num=basic_block_list[j]->num;
+ // a->size=(int*)xmalloc(sizeof(int)*(a->depth+1));
+ dump_data_reference(stdout,a);
+ VARRAY_PUSH_GENERIC_PTR (*datarefs,a);
+
+ }
+
+ }
+
-/* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */
+
+
-void
-dump_data_dependence_direction (FILE *file,
- enum data_dependence_direction dir)
-{
- switch (dir)
- {
- case dir_positive:
- fprintf (file, "+");
- break;
-
- case dir_negative:
- fprintf (file, "-");
- break;
-
- case dir_equal:
- fprintf (file, "=");
- break;
-
- case dir_positive_or_negative:
- fprintf (file, "+-");
- break;
- case dir_positive_or_equal:
- fprintf (file, "+=");
- break;
+ // dumping data references per loop
- case dir_negative_or_equal:
- fprintf (file, "-=");
- break;
+ printf(" Finished looking at references \n");
+ // dump_data_references(stdout,datarefs);
- case dir_star:
- fprintf (file, "*");
- break;
-
- default:
- break;
- }
-}
-
-/* Dumps the distance and direction vectors in FILE. DDRS contains
- the dependence relations, and VECT_SIZE is the size of the
- dependence vectors, or in other words the number of loops in the
- considered nest. */
+ }
+
+
+/* Perform a set of linear transforms on LOOPS. */
-void
-dump_dist_dir_vectors (FILE *file, varray_type ddrs)
+void
+linear_transform_loops (struct loops *loops)
{
unsigned int i;
+
+ varray_type refsinloops;
+ struct loop *loop_nest;
+
+ compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, NULL);
+ analyze_all_data_dependences (loops);
- for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++)
- {
- struct data_dependence_relation *ddr =
- (struct data_dependence_relation *)
- VARRAY_GENERIC_PTR (ddrs, i);
- if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
- && DDR_AFFINE_P (ddr))
+ /*
+ if(timestamp_flag)
+ {
+
+ VARRAY_GENERIC_PTR_INIT (refsinloops, 10, "refsinloops");
+
+
+ printf(" Number of loops in this program is %d \n",loops->num);
+
+ estimate_numbers_of_iterations (loops);
+
+ iterations_estimate= (int*) xmalloc(sizeof(int)*(loops->num +1));
+
+ for (i = 1; i < loops->num; i++)
+ {
+ struct loop* l_nest = loops->parray[i];
+ printf(" Estimate for %d with depth %d ",i,l_nest->depth);
+
+ if(l_nest->estimated_nb_iterations != NULL)
{
- fprintf (file, "DISTANCE_V (");
- print_lambda_vector (file, DDR_DIST_VECT (ddr), DDR_SIZE_VECT (ddr));
- fprintf (file, ")\n");
- fprintf (file, "DIRECTION_V (");
- print_lambda_vector (file, DDR_DIR_VECT (ddr), DDR_SIZE_VECT (ddr));
- fprintf (file, ")\n");
- }
- }
- fprintf (file, "\n\n");
-}
-
-/* Dumps the data dependence relations DDRS in FILE. */
-
-void
-dump_ddrs (FILE *file, varray_type ddrs)
-{
- unsigned int i;
-
- for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++)
- {
- struct data_dependence_relation *ddr =
- (struct data_dependence_relation *)
- VARRAY_GENERIC_PTR (ddrs, i);
- dump_data_dependence_relation (file, ddr);
- }
- fprintf (file, "\n\n");
-}
-
-\f
+// && (TREE_CODE(l_nest->estimated_nb_iterations)== INTEGER_CST))
-/* Compute the lowest iteration bound for LOOP. It is an
- INTEGER_CST. */
+ printf("%d \n",TREE_INT_CST_LOW(l_nest->estimated_nb_iterations));
+ iterations_estimate[i]=TREE_INT_CST_LOW(l_nest->estimated_nb_iterations);
+ }
+ else
+ iterations_estimate[i]=-1;
+
+
+
+ }
+
+ }
+ */
-static void
-compute_estimated_nb_iterations (struct loop *loop)
-{
- tree estimation;
- struct nb_iter_bound *bound, *next;
+ // VARRAY_GENERIC_PTR_INIT (dependence_relations, 10,
+// "dependence_relations");
+
- for (bound = loop->bounds; bound; bound = next)
- {
- next = bound->next;
- estimation = bound->bound;
-
- if (TREE_CODE (estimation) != INTEGER_CST)
+ // compute_data_dependences_for_loop (depth, loop_nest,
+// &datarefs, &dependence_relations);
+
+
+
+ for (i = 1; i < loops->num; i++)
+ {
+ unsigned int depth = 0;
+ varray_type datarefs;
+ varray_type dependence_relations;
+ loop_nest = loops->parray[i];
+ struct loop *temp;
+ VEC (tree) *oldivs = NULL;
+ VEC (tree) *invariants = NULL;
+ lambda_loopnest before, after;
+ lambda_trans_matrix trans;
+ bool problem = false;
+ bool need_perfect_nest = false;
+ /* If it's not a loop nest, we don't want it.
+ We also don't handle sibling loops properly,
+ which are loops of the following form:
+ for (i = 0; i < 50; i++)
+ {
+ for (j = 0; j < 50; j++)
+ {
+ ...
+ }
+ for (j = 0; j < 50; j++)
+ {
+ ...
+ }
+ } */
+ if (!loop_nest->inner)
continue;
-
- if (loop->estimated_nb_iterations)
- {
- /* Update only if estimation is smaller. */
- if (tree_int_cst_lt (estimation, loop->estimated_nb_iterations))
- loop->estimated_nb_iterations = estimation;
+
+ printf(" Processing loop for %d \n",i);
+ depth = 1;
+ for (temp = loop_nest->inner; temp; temp = temp->inner)
+ {
+ flow_loop_scan (temp, LOOP_ALL);
+ /* If we have a sibling loop or multiple exit edges, jump ship. */
+ if (temp->next || temp->num_exits != 1)
+ {
+ problem = true;
+ break;
+ }
+ depth ++;
}
- else
- loop->estimated_nb_iterations = estimation;
- }
-}
-
-/* Estimate the number of iterations from the size of the data and the
- access functions. */
-
-static void
-estimate_niter_from_size_of_data (struct loop *loop,
- tree opnd0,
- tree access_fn,
- tree stmt)
-{
- tree estimation;
- tree array_size, data_size, element_size;
- tree init, step;
-
- init = initial_condition (access_fn);
- step = evolution_part_in_loop_num (access_fn, loop->num);
-
- array_size = TYPE_SIZE (TREE_TYPE (opnd0));
- element_size = TYPE_SIZE (TREE_TYPE (TREE_TYPE (opnd0)));
- if (array_size == NULL_TREE
- || TREE_CODE (array_size) != INTEGER_CST
- || TREE_CODE (element_size) != INTEGER_CST)
- return;
-
- data_size = fold (build2 (EXACT_DIV_EXPR, integer_type_node,
- array_size, element_size));
-
- if (init != NULL_TREE
- && step != NULL_TREE
- && TREE_CODE (init) == INTEGER_CST
- && TREE_CODE (step) == INTEGER_CST)
- {
- estimation = fold (build2 (CEIL_DIV_EXPR, integer_type_node,
- fold (build2 (MINUS_EXPR, integer_type_node,
- data_size, init)), step));
-
- record_estimate (loop, estimation, boolean_true_node, stmt);
- }
-}
-
-/* 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,
- varray_type *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));
+ if (problem)
+ continue;
- if (loop->estimated_nb_iterations == NULL_TREE)
- estimate_niter_from_size_of_data (loop, opnd0, access_fn, stmt);
-
- VARRAY_PUSH_TREE (*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;
-}
+ /* Analyze data references and dependence relations using scev. */
+
+
+ VARRAY_GENERIC_PTR_INIT (datarefs, 10, "datarefs");
+ VARRAY_GENERIC_PTR_INIT (dependence_relations, 10,
+ "dependence_relations");
+
+
+ printf(" Inside loop_nest->num %d %d\n",loop_nest->num,loop_nest->depth);
+
+ // compute_data_dependences_for_loop (depth, loop_nest, &datarefs, &dependence_relations);
+
+ // ADDED_SK
+
+ find_data_references(loop_nest,&refsinloops);
+ dump_data_references (stdout,refsinloops);
+
+ printf("*****************\n");
+ printf(" UG set information \n");
+ compute_UG_sets(refsinloops);
+
+/*
-/* 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. */
+ if(timestamp_flag)
+ {
+
+ //
+ find_data_references(loop_nest,&refsinloops);
+ dump_data_references (stdout,refsinloops);
-struct data_reference *
-analyze_array (tree stmt, tree ref, bool is_read)
-{
- struct data_reference *res;
+ printf("*****************\n");
+ printf(" UG set information \n");
+ compute_UG_sets(refsinloops);
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "(analyze_array \n");
- fprintf (dump_file, " (ref = ");
- print_generic_stmt (dump_file, ref, 0);
- fprintf (dump_file, ")\n");
- }
-
- res = xmalloc (sizeof (struct data_reference));
-
- DR_STMT (res) = stmt;
- DR_REF (res) = ref;
- VARRAY_TREE_INIT (DR_ACCESS_FNS (res), 3, "access_fns");
- DR_BASE_NAME (res) = analyze_array_indexes
- (loop_containing_stmt (stmt), &(DR_ACCESS_FNS (res)), ref, stmt);
- DR_IS_READ (res) = is_read;
-
- 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. */
+ printf("*****************\n");
+ printf("Data dependency information \n");
+
+ compute_data_dependences_for_loop_SK (depth, loop_nest,&refsinloops, &dependence_relations);
-struct data_reference *
-init_data_ref (tree stmt,
- tree ref,
- tree base,
- tree access_fn,
- bool is_read)
-{
- struct data_reference *res;
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "(init_data_ref \n");
- fprintf (dump_file, " (ref = ");
- print_generic_stmt (dump_file, ref, 0);
- fprintf (dump_file, ")\n");
- }
-
- res = xmalloc (sizeof (struct data_reference));
-
- DR_STMT (res) = stmt;
- DR_REF (res) = ref;
- VARRAY_TREE_INIT (DR_ACCESS_FNS (res), 5, "access_fns");
- DR_BASE_NAME (res) = base;
- VARRAY_PUSH_TREE (DR_ACCESS_FNS (res), access_fn);
- DR_IS_READ (res) = is_read;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, ")\n");
-
- return res;
-}
+ printf("*****************\n");
+ printf("Processing for overlap\n");
+ process_for_overlap(&dependence_relations);
+
+
-\f
+// dump_updated_data_references (stdout,refsinloops);
-/* Returns true when all the functions of a tree_vec CHREC are the
- same. */
+ printf("*****************\n");
+ printf(" Computing sizes \n");
+ compute_sizes(loop_nest,refsinloops);
+
+ printf("*****************\n");
+ printf(" Size information \n");
+ dump_size_information(loop_nest,refsinloops);
+ printf("*****************\n");
+ printf(" Inserting annotations \n");
-static bool
-all_chrecs_equal_p (tree chrec)
-{
- int j;
+ insert_annotations(loop_nest);
- for (j = 0; j < TREE_VEC_LENGTH (chrec) - 1; j++)
- {
- tree chrec_j = TREE_VEC_ELT (chrec, j);
- tree chrec_j_1 = TREE_VEC_ELT (chrec, j + 1);
- if (!integer_zerop
- (chrec_fold_minus
- (integer_type_node, chrec_j, chrec_j_1)))
- return false;
- }
- return true;
-}
+
+
+ }
+
+ */
-/* Determine for each subscript in the data dependence relation DDR
- the distance. */
+
+
+/* dump_file=stdout;
+ dump_flags=TDF_DETAILS;
-static void
-compute_subscript_distance (struct data_dependence_relation *ddr)
-{
- if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
- {
- unsigned int i;
-
- for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
- {
- tree conflicts_a, conflicts_b, difference;
- struct subscript *subscript;
-
- subscript = DDR_SUBSCRIPT (ddr, i);
- conflicts_a = SUB_CONFLICTS_IN_A (subscript);
- conflicts_b = SUB_CONFLICTS_IN_B (subscript);
- if (TREE_CODE (conflicts_a) == TREE_VEC)
- {
- if (!all_chrecs_equal_p (conflicts_a))
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ unsigned int j;
+ printf("Hello\n");
+ for (j = 0; j < VARRAY_ACTIVE_SIZE (dependence_relations); j++)
+ {
+ struct data_dependence_relation *ddr =
+ (struct data_dependence_relation *)
+ VARRAY_GENERIC_PTR (dependence_relations, j);
+ if(DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
+ {
+ ddr->a->overlap=1;
+ ddr->b->overlap=1;
+
+ }
+
+ if ((DDR_ARE_DEPENDENT (ddr) == NULL_TREE) )
{
- SUB_DISTANCE (subscript) = chrec_dont_know;
- return;
+ printf(" The references in question are %d %d\n",ddr->a->groupid,ddr->b->groupid);
+ dump_data_reference(dump_file,ddr->a);
+ printf("\n");
+ dump_data_reference(dump_file,ddr->b);
+ printf("\n");
+ // is -1 present
+
+ // if b is write and a is read
+ lambda_vector vector;
+ int vect_len=DDR_SIZE_VECT (ddr);
+ for (i = 0; i <vect_len; i++)
+ {
+ if(vector[i] == -1)//b is the source , a is sink
+ {
+ if((ddr->a->isread == 0) && (ddr->b->isread ==1))
+ {
+ ddr->a->overlap=0; // overlap can be ignored
+ ddr->b->overlap=0;
+
+
+ }
+ else
+ {
+ ddr->a->overlap=i+1;
+ ddr->b->overlap=i+1;
+ break;
+ }
+ }
+
+
+ else if(vector[i] == 1)
+ {
+ if((ddr->a->isread == 1) && (ddr->b->isread ==0))
+ {
+ ddr->a->overlap=0; // overlap can be ignored
+ ddr->b->overlap=0;
+
+
+ }
+ else
+ {
+ ddr->a->overlap=i+1;
+ ddr->b->overlap=i+1;
+ break;
+ }
+
+ }
+
+ }
+ fprintf (dump_file, "DISTANCE_V (");
+ print_lambda_vector (dump_file, DDR_DIST_VECT (ddr),
+ DDR_SIZE_VECT (ddr));
+ fprintf (dump_file, ")\n");
+ fprintf (dump_file, "DIRECTION_V (");
+ print_lambda_vector (dump_file, DDR_DIR_VECT (ddr),
+ DDR_SIZE_VECT (ddr));
+ fprintf (dump_file, ")\n");
}
- else
- conflicts_a = TREE_VEC_ELT (conflicts_a, 0);
}
-
- if (TREE_CODE (conflicts_b) == TREE_VEC)
- {
- if (!all_chrecs_equal_p (conflicts_b))
+ fprintf (dump_file, "\n\n");
+ }
+
+ /*
+
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ unsigned int j;
+ printf("Hello\n");
+ for (j = 0; j < VARRAY_ACTIVE_SIZE (dependence_relations); j++)
+ {
+ struct data_dependence_relation *ddr =
+ (struct data_dependence_relation *)
+ VARRAY_GENERIC_PTR (dependence_relations, j);
+
+ if ((DDR_ARE_DEPENDENT (ddr) == NULL_TREE) )
{
- SUB_DISTANCE (subscript) = chrec_dont_know;
- return;
+ printf(" The references in question are %d %d\n",ddr->a->groupid,ddr->b->groupid);
+ dump_data_reference(dump_file,ddr->a);
+
+
+ printf("\n");
+ dump_data_reference(dump_file,ddr->b);
+ printf("\n");
+
+
+ fprintf (dump_file, "DISTANCE_V (");
+ print_lambda_vector (dump_file, DDR_DIST_VECT (ddr),
+ DDR_SIZE_VECT (ddr));
+ fprintf (dump_file, ")\n");
+ fprintf (dump_file, "DIRECTION_V (");
+ print_lambda_vector (dump_file, DDR_DIR_VECT (ddr),
+ DDR_SIZE_VECT (ddr));
+ fprintf (dump_file, ")\n");
}
- else
- conflicts_b = TREE_VEC_ELT (conflicts_b, 0);
}
+ fprintf (dump_file, "\n\n");
+ }
+
+ dump_file=NULL;
+ dump_flags=0;
+
+ trans = lambda_trans_matrix_new (depth, depth);
+ lambda_matrix_id (LTM_MATRIX (trans), depth);
+
+ trans = try_interchange_loops (trans, depth, dependence_relations,
+ datarefs, loop_nest);
+
+ if (lambda_trans_matrix_id_p (trans))
+ {
+ if (dump_file)
+ fprintf (dump_file, "Won't transform loop. Optimal transform is the identity transform\n");
+ continue;
+ }
- difference = chrec_fold_minus
- (integer_type_node, conflicts_b, conflicts_a);
-
- if (evolution_function_is_constant_p (difference))
- SUB_DISTANCE (subscript) = difference;
-
- else
- SUB_DISTANCE (subscript) = chrec_dont_know;
- }
- }
-}
-
-/* Initialize a ddr. */
-
-struct data_dependence_relation *
-initialize_data_dependence_relation (struct data_reference *a,
- struct data_reference *b)
-{
- struct data_dependence_relation *res;
- bool differ_p;
-
- res = xmalloc (sizeof (struct data_dependence_relation));
- DDR_A (res) = a;
- DDR_B (res) = b;
-
- if (a == NULL || b == NULL
- || DR_BASE_NAME (a) == NULL_TREE
- || DR_BASE_NAME (b) == NULL_TREE)
- DDR_ARE_DEPENDENT (res) = chrec_dont_know;
-
- /* When the dimensions of A and B differ, we directly initialize
- the relation to "there is no dependence": chrec_known. */
- else if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b)
- || (array_base_name_differ_p (a, b, &differ_p) && differ_p))
- DDR_ARE_DEPENDENT (res) = chrec_known;
+
+ if (!lambda_transform_legal_p (trans, depth, dependence_relations))
+ {
+ if (dump_file)
+ fprintf (dump_file, "Can't transform loop, transform is illegal:\n");
+ continue;
+ }
+ if (!perfect_nest_p (loop_nest))
+ need_perfect_nest = true;
+ before = gcc_loopnest_to_lambda_loopnest (loops,
+ loop_nest, &oldivs,
+ &invariants,
+ need_perfect_nest);
+ if (!before)
+ continue;
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "Before:\n");
+ print_lambda_loopnest (dump_file, before, 'i');
+ }
- else
- {
- unsigned int i;
- DDR_AFFINE_P (res) = true;
- DDR_ARE_DEPENDENT (res) = NULL_TREE;
- DDR_SUBSCRIPTS_VECTOR_INIT (res, DR_NUM_DIMENSIONS (a));
- DDR_SIZE_VECT (res) = 0;
- DDR_DIST_VECT (res) = NULL;
- DDR_DIR_VECT (res) = NULL;
-
- for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
+ after = lambda_loopnest_transform (before, trans);
+ if (dump_file)
{
- struct subscript *subscript;
-
- subscript = xmalloc (sizeof (struct subscript));
- SUB_CONFLICTS_IN_A (subscript) = chrec_dont_know;
- SUB_CONFLICTS_IN_B (subscript) = chrec_dont_know;
- SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
- SUB_DISTANCE (subscript) = chrec_dont_know;
- VARRAY_PUSH_GENERIC_PTR (DDR_SUBSCRIPTS (res), subscript);
+ fprintf (dump_file, "After:\n");
+ print_lambda_loopnest (dump_file, after, 'u');
}
+ lambda_loopnest_to_gcc_loopnest (loop_nest, oldivs, invariants,
+ after, trans);
+ if (dump_file)
+ fprintf (dump_file, "Successfully transformed loop.\n");
+ oldivs = NULL;
+ invariants = NULL;
+ */
+ free_dependence_relations (dependence_relations);
+ free_data_refs (datarefs);
}
+
+ loop_nest = loops->parray[1];
+ insert_annotations(loop_nest);
- return res;
-}
-
-/* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
- description. */
-
-static inline void
-finalize_ddr_dependent (struct data_dependence_relation *ddr,
- tree chrec)
-{
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "(dependence classified: ");
- print_generic_expr (dump_file, chrec, 0);
- fprintf (dump_file, ")\n");
- }
-
- DDR_ARE_DEPENDENT (ddr) = chrec;
- varray_clear (DDR_SUBSCRIPTS (ddr));
+ free_df ();
+ scev_reset ();
+ rewrite_into_ssa (false);
+ rewrite_into_loop_closed_ssa ();
+#ifdef ENABLE_CHECKING
+ verify_loop_closed_ssa ();
+#endif
}
-
-/* The dependence relation DDR cannot be represented by a distance
- vector. */
-
-static inline void
-non_affine_dependence_relation (struct data_dependence_relation *ddr)
-{
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
-
- DDR_AFFINE_P (ddr) = false;
-}
-
-\f
-
-/* This section contains the classic Banerjee tests. */
-
-/* Returns true iff CHREC_A and CHREC_B are not dependent on any index
- variables, i.e., if the ZIV (Zero Index Variable) test is true. */
-
-static inline bool
-ziv_subscript_p (tree chrec_a,
- tree chrec_b)
-{
- return (evolution_function_is_constant_p (chrec_a)
- && evolution_function_is_constant_p (chrec_b));
-}
-
-/* Returns true iff CHREC_A and CHREC_B are dependent on an index
- variable, i.e., if the SIV (Single Index Variable) test is true. */
-
-static bool
-siv_subscript_p (tree chrec_a,
- tree chrec_b)
-{
- if ((evolution_function_is_constant_p (chrec_a)
- && evolution_function_is_univariate_p (chrec_b))
- || (evolution_function_is_constant_p (chrec_b)
- && evolution_function_is_univariate_p (chrec_a)))
- return true;
-
- if (evolution_function_is_univariate_p (chrec_a)
- && evolution_function_is_univariate_p (chrec_b))
- {
- switch (TREE_CODE (chrec_a))
- {
- case POLYNOMIAL_CHREC:
- switch (TREE_CODE (chrec_b))
- {
- case POLYNOMIAL_CHREC:
- if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
- return false;
-
- default:
- return true;
- }
-
- default:
- return true;
- }
- }
-
- return false;
-}
-
-/* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
- *OVERLAPS_B are initialized to the functions that describe the
- relation between the elements accessed twice by CHREC_A and
- CHREC_B. For k >= 0, the following property is verified:
-
- CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
-
-static void
-analyze_ziv_subscript (tree chrec_a,
- tree chrec_b,
- tree *overlaps_a,
- tree *overlaps_b,
- tree *last_conflicts)
-{
- tree difference;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "(analyze_ziv_subscript \n");
-
- difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
-
- switch (TREE_CODE (difference))
- {
- case INTEGER_CST:
- if (integer_zerop (difference))
- {
- /* The difference is equal to zero: the accessed index
- overlaps for each iteration in the loop. */
- *overlaps_a = integer_zero_node;
- *overlaps_b = integer_zero_node;
- *last_conflicts = chrec_dont_know;
- }
- else
- {
- /* The accesses do not overlap. */
- *overlaps_a = chrec_known;
- *overlaps_b = chrec_known;
- *last_conflicts = integer_zero_node;
- }
- break;
-
- default:
- /* We're not sure whether the indexes overlap. For the moment,
- conservatively answer "don't know". */
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
- *last_conflicts = chrec_dont_know;
- break;
- }
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, ")\n");
-}
-
-/* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
- constant, and CHREC_B is an affine function. *OVERLAPS_A and
- *OVERLAPS_B are initialized to the functions that describe the
- relation between the elements accessed twice by CHREC_A and
- CHREC_B. For k >= 0, the following property is verified:
-
- CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
-
-static void
-analyze_siv_subscript_cst_affine (tree chrec_a,
- tree chrec_b,
- tree *overlaps_a,
- tree *overlaps_b,
- tree *last_conflicts)
-{
- bool value0, value1, value2;
- tree difference = chrec_fold_minus
- (integer_type_node, CHREC_LEFT (chrec_b), chrec_a);
-
- if (!chrec_is_positive (initial_condition (difference), &value0))
- {
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
- *last_conflicts = chrec_dont_know;
- return;
- }
- else
- {
- if (value0 == false)
- {
- if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
- {
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
- *last_conflicts = chrec_dont_know;
- return;
- }
- else
- {
- if (value1 == true)
- {
- /* Example:
- chrec_a = 12
- chrec_b = {10, +, 1}
- */
-
- if (tree_fold_divides_p
- (integer_type_node, CHREC_RIGHT (chrec_b), difference))
- {
- *overlaps_a = integer_zero_node;
- *overlaps_b = fold
- (build (EXACT_DIV_EXPR, integer_type_node,
- fold (build1 (ABS_EXPR, integer_type_node, difference)),
- CHREC_RIGHT (chrec_b)));
- *last_conflicts = integer_one_node;
- return;
- }
-
- /* When the step does not divides the difference, there are
- no overlaps. */
- else
- {
- *overlaps_a = chrec_known;
- *overlaps_b = chrec_known;
- *last_conflicts = integer_zero_node;
- return;
- }
- }
-
- else
- {
- /* Example:
- chrec_a = 12
- chrec_b = {10, +, -1}
-
- In this case, chrec_a will not overlap with chrec_b. */
- *overlaps_a = chrec_known;
- *overlaps_b = chrec_known;
- *last_conflicts = integer_zero_node;
- return;
- }
- }
- }
- else
- {
- if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
- {
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
- *last_conflicts = chrec_dont_know;
- return;
- }
- else
- {
- if (value2 == false)
- {
- /* Example:
- chrec_a = 3
- chrec_b = {10, +, -1}
- */
- if (tree_fold_divides_p
- (integer_type_node, CHREC_RIGHT (chrec_b), difference))
- {
- *overlaps_a = integer_zero_node;
- *overlaps_b = fold
- (build (EXACT_DIV_EXPR, integer_type_node, difference,
- CHREC_RIGHT (chrec_b)));
- *last_conflicts = integer_one_node;
- return;
- }
-
- /* When the step does not divides the difference, there
- are no overlaps. */
- else
- {
- *overlaps_a = chrec_known;
- *overlaps_b = chrec_known;
- *last_conflicts = integer_zero_node;
- return;
- }
- }
- else
- {
- /* Example:
- chrec_a = 3
- chrec_b = {4, +, 1}
-
- In this case, chrec_a will not overlap with chrec_b. */
- *overlaps_a = chrec_known;
- *overlaps_b = chrec_known;
- *last_conflicts = integer_zero_node;
- return;
- }
- }
- }
- }
-}
-
-/* Helper recursive function for initializing the matrix A. Returns
- the initial value of CHREC. */
-
-static int
-initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
-{
- gcc_assert (chrec);
-
- if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
- return int_cst_value (chrec);
-
- A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
- return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
-}
-
-#define FLOOR_DIV(x,y) ((x) / (y))
-
-/* Solves the special case of the Diophantine equation:
- | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
-
- Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
- number of iterations that loops X and Y run. The overlaps will be
- constructed as evolutions in dimension DIM. */
-
-static void
-compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
- tree *overlaps_a, tree *overlaps_b,
- tree *last_conflicts, int dim)
-{
- if (((step_a > 0 && step_b > 0)
- || (step_a < 0 && step_b < 0)))
- {
- int step_overlaps_a, step_overlaps_b;
- int gcd_steps_a_b, last_conflict, tau2;
-
- gcd_steps_a_b = gcd (step_a, step_b);
- step_overlaps_a = step_b / gcd_steps_a_b;
- step_overlaps_b = step_a / gcd_steps_a_b;
-
- tau2 = FLOOR_DIV (niter, step_overlaps_a);
- tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
- last_conflict = tau2;
-
- *overlaps_a = build_polynomial_chrec
- (dim, integer_zero_node,
- build_int_cst (NULL_TREE, step_overlaps_a));
- *overlaps_b = build_polynomial_chrec
- (dim, integer_zero_node,
- build_int_cst (NULL_TREE, step_overlaps_b));
- *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
- }
-
- else
- {
- *overlaps_a = integer_zero_node;
- *overlaps_b = integer_zero_node;
- *last_conflicts = integer_zero_node;
- }
-}
-
-
-/* Solves the special case of a Diophantine equation where CHREC_A is
- an affine bivariate function, and CHREC_B is an affine univariate
- function. For example,
-
- | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
-
- has the following overlapping functions:
-
- | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
- | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
- | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
-
- FORNOW: This is a specialized implementation for a case occurring in
- a common benchmark. Implement the general algorithm. */
-
-static void
-compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
- tree *overlaps_a, tree *overlaps_b,
- tree *last_conflicts)
-{
- bool xz_p, yz_p, xyz_p;
- int step_x, step_y, step_z;
- int niter_x, niter_y, niter_z, niter;
- tree numiter_x, numiter_y, numiter_z;
- tree overlaps_a_xz, overlaps_b_xz, last_conflicts_xz;
- tree overlaps_a_yz, overlaps_b_yz, last_conflicts_yz;
- tree overlaps_a_xyz, overlaps_b_xyz, last_conflicts_xyz;
-
- step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
- step_y = int_cst_value (CHREC_RIGHT (chrec_a));
- step_z = int_cst_value (CHREC_RIGHT (chrec_b));
-
- numiter_x = number_of_iterations_in_loop
- (current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]);
- numiter_y = number_of_iterations_in_loop
- (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
- numiter_z = number_of_iterations_in_loop
- (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
-
- if (TREE_CODE (numiter_x) != INTEGER_CST)
- numiter_x = current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]
- ->estimated_nb_iterations;
- if (TREE_CODE (numiter_y) != INTEGER_CST)
- numiter_y = current_loops->parray[CHREC_VARIABLE (chrec_a)]
- ->estimated_nb_iterations;
- if (TREE_CODE (numiter_z) != INTEGER_CST)
- numiter_z = current_loops->parray[CHREC_VARIABLE (chrec_b)]
- ->estimated_nb_iterations;
-
- if (numiter_x == NULL_TREE || numiter_y == NULL_TREE
- || numiter_z == NULL_TREE)
- {
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
- *last_conflicts = chrec_dont_know;
- return;
- }
-
- niter_x = int_cst_value (numiter_x);
- niter_y = int_cst_value (numiter_y);
- niter_z = int_cst_value (numiter_z);
-
- niter = MIN (niter_x, niter_z);
- compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
- &overlaps_a_xz,
- &overlaps_b_xz,
- &last_conflicts_xz, 1);
- niter = MIN (niter_y, niter_z);
- compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
- &overlaps_a_yz,
- &overlaps_b_yz,
- &last_conflicts_yz, 2);
- niter = MIN (niter_x, niter_z);
- niter = MIN (niter_y, niter);
- compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
- &overlaps_a_xyz,
- &overlaps_b_xyz,
- &last_conflicts_xyz, 3);
-
- xz_p = !integer_zerop (last_conflicts_xz);
- yz_p = !integer_zerop (last_conflicts_yz);
- xyz_p = !integer_zerop (last_conflicts_xyz);
-
- if (xz_p || yz_p || xyz_p)
- {
- *overlaps_a = make_tree_vec (2);
- TREE_VEC_ELT (*overlaps_a, 0) = integer_zero_node;
- TREE_VEC_ELT (*overlaps_a, 1) = integer_zero_node;
- *overlaps_b = integer_zero_node;
- if (xz_p)
- {
- TREE_VEC_ELT (*overlaps_a, 0) =
- chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0),
- overlaps_a_xz);
- *overlaps_b =
- chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xz);
- *last_conflicts = last_conflicts_xz;
- }
- if (yz_p)
- {
- TREE_VEC_ELT (*overlaps_a, 1) =
- chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1),
- overlaps_a_yz);
- *overlaps_b =
- chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_yz);
- *last_conflicts = last_conflicts_yz;
- }
- if (xyz_p)
- {
- TREE_VEC_ELT (*overlaps_a, 0) =
- chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0),
- overlaps_a_xyz);
- TREE_VEC_ELT (*overlaps_a, 1) =
- chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1),
- overlaps_a_xyz);
- *overlaps_b =
- chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xyz);
- *last_conflicts = last_conflicts_xyz;
- }
- }
- else
- {
- *overlaps_a = integer_zero_node;
- *overlaps_b = integer_zero_node;
- *last_conflicts = integer_zero_node;
- }
-}
-
-/* Determines the overlapping elements due to accesses CHREC_A and
- CHREC_B, that are affine functions. This is a part of the
- subscript analyzer. */
-
-static void
-analyze_subscript_affine_affine (tree chrec_a,
- tree chrec_b,
- tree *overlaps_a,
- tree *overlaps_b,
- tree *last_conflicts)
-{
- unsigned nb_vars_a, nb_vars_b, dim;
- int init_a, init_b, gamma, gcd_alpha_beta;
- int tau1, tau2;
- lambda_matrix A, U, S;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "(analyze_subscript_affine_affine \n");
-
- /* For determining the initial intersection, we have to solve a
- Diophantine equation. This is the most time consuming part.
-
- For answering to the question: "Is there a dependence?" we have
- to prove that there exists a solution to the Diophantine
- equation, and that the solution is in the iteration domain,
- i.e. the solution is positive or zero, and that the solution
- happens before the upper bound loop.nb_iterations. Otherwise
- there is no dependence. This function outputs a description of
- the iterations that hold the intersections. */
-
-
- nb_vars_a = nb_vars_in_chrec (chrec_a);
- nb_vars_b = nb_vars_in_chrec (chrec_b);
-
- dim = nb_vars_a + nb_vars_b;
- U = lambda_matrix_new (dim, dim);
- A = lambda_matrix_new (dim, 1);
- S = lambda_matrix_new (dim, 1);
-
- init_a = initialize_matrix_A (A, chrec_a, 0, 1);
- init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1);
- gamma = init_b - init_a;
-
- /* Don't do all the hard work of solving the Diophantine equation
- when we already know the solution: for example,
- | {3, +, 1}_1
- | {3, +, 4}_2
- | gamma = 3 - 3 = 0.
- Then the first overlap occurs during the first iterations:
- | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
- */
- if (gamma == 0)
- {
- if (nb_vars_a == 1 && nb_vars_b == 1)
- {
- int step_a, step_b;
- int niter, niter_a, niter_b;
- tree numiter_a, numiter_b;
-
- numiter_a = number_of_iterations_in_loop
- (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
- numiter_b = number_of_iterations_in_loop
- (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
-
- if (TREE_CODE (numiter_a) != INTEGER_CST)
- numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)]
- ->estimated_nb_iterations;
- if (TREE_CODE (numiter_b) != INTEGER_CST)
- numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
- ->estimated_nb_iterations;
- if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
- {
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
- *last_conflicts = chrec_dont_know;
- return;
- }
-
- niter_a = int_cst_value (numiter_a);
- niter_b = int_cst_value (numiter_b);
- niter = MIN (niter_a, niter_b);
-
- step_a = int_cst_value (CHREC_RIGHT (chrec_a));
- step_b = int_cst_value (CHREC_RIGHT (chrec_b));
-
- compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
- overlaps_a, overlaps_b,
- last_conflicts, 1);
- }
-
- else if (nb_vars_a == 2 && nb_vars_b == 1)
- compute_overlap_steps_for_affine_1_2
- (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
-
- else if (nb_vars_a == 1 && nb_vars_b == 2)
- compute_overlap_steps_for_affine_1_2
- (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
-
- else
- {
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
- *last_conflicts = chrec_dont_know;
- }
- return;
- }
-
- /* U.A = S */
- lambda_matrix_right_hermite (A, dim, 1, S, U);
-
- if (S[0][0] < 0)
- {
- S[0][0] *= -1;
- lambda_matrix_row_negate (U, dim, 0);
- }
- gcd_alpha_beta = S[0][0];
-
- /* The classic "gcd-test". */
- if (!int_divides_p (gcd_alpha_beta, gamma))
- {
- /* The "gcd-test" has determined that there is no integer
- solution, i.e. there is no dependence. */
- *overlaps_a = chrec_known;
- *overlaps_b = chrec_known;
- *last_conflicts = integer_zero_node;
- }
-
- /* Both access functions are univariate. This includes SIV and MIV cases. */
- else if (nb_vars_a == 1 && nb_vars_b == 1)
- {
- /* Both functions should have the same evolution sign. */
- if (((A[0][0] > 0 && -A[1][0] > 0)
- || (A[0][0] < 0 && -A[1][0] < 0)))
- {
- /* The solutions are given by:
- |
- | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
- | [u21 u22] [y0]
-
- For a given integer t. Using the following variables,
-
- | i0 = u11 * gamma / gcd_alpha_beta
- | j0 = u12 * gamma / gcd_alpha_beta
- | i1 = u21
- | j1 = u22
-
- the solutions are:
-
- | x0 = i0 + i1 * t,
- | y0 = j0 + j1 * t. */
-
- int i0, j0, i1, j1;
-
- /* X0 and Y0 are the first iterations for which there is a
- dependence. X0, Y0 are two solutions of the Diophantine
- equation: chrec_a (X0) = chrec_b (Y0). */
- int x0, y0;
- int niter, niter_a, niter_b;
- tree numiter_a, numiter_b;
-
- numiter_a = number_of_iterations_in_loop
- (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
- numiter_b = number_of_iterations_in_loop
- (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
-
- if (TREE_CODE (numiter_a) != INTEGER_CST)
- numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)]
- ->estimated_nb_iterations;
- if (TREE_CODE (numiter_b) != INTEGER_CST)
- numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
- ->estimated_nb_iterations;
- if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
- {
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
- *last_conflicts = chrec_dont_know;
- return;
- }
-
- niter_a = int_cst_value (numiter_a);
- niter_b = int_cst_value (numiter_b);
- niter = MIN (niter_a, niter_b);
-
- i0 = U[0][0] * gamma / gcd_alpha_beta;
- j0 = U[0][1] * gamma / gcd_alpha_beta;
- i1 = U[1][0];
- j1 = U[1][1];
-
- if ((i1 == 0 && i0 < 0)
- || (j1 == 0 && j0 < 0))
- {
- /* There is no solution.
- FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
- falls in here, but for the moment we don't look at the
- upper bound of the iteration domain. */
- *overlaps_a = chrec_known;
- *overlaps_b = chrec_known;
- *last_conflicts = integer_zero_node;
- }
-
- else
- {
- if (i1 > 0)
- {
- tau1 = CEIL (-i0, i1);
- tau2 = FLOOR_DIV (niter - i0, i1);
-
- if (j1 > 0)
- {
- int last_conflict, min_multiple;
- tau1 = MAX (tau1, CEIL (-j0, j1));
- tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1));
-
- x0 = i1 * tau1 + i0;
- y0 = j1 * tau1 + j0;
-
- /* At this point (x0, y0) is one of the
- solutions to the Diophantine equation. The
- next step has to compute the smallest
- positive solution: the first conflicts. */
- min_multiple = MIN (x0 / i1, y0 / j1);
- x0 -= i1 * min_multiple;
- y0 -= j1 * min_multiple;
-
- tau1 = (x0 - i0)/i1;
- last_conflict = tau2 - tau1;
-
- *overlaps_a = build_polynomial_chrec
- (1,
- build_int_cst (NULL_TREE, x0),
- build_int_cst (NULL_TREE, i1));
- *overlaps_b = build_polynomial_chrec
- (1,
- build_int_cst (NULL_TREE, y0),
- build_int_cst (NULL_TREE, j1));
- *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
- }
- else
- {
- /* FIXME: For the moment, the upper bound of the
- iteration domain for j is not checked. */
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
- *last_conflicts = chrec_dont_know;
- }
- }
-
- else
- {
- /* FIXME: For the moment, the upper bound of the
- iteration domain for i is not checked. */
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
- *last_conflicts = chrec_dont_know;
- }
- }
- }
- else
- {
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
- *last_conflicts = chrec_dont_know;
- }
- }
-
- else
- {
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
- *last_conflicts = chrec_dont_know;
- }
-
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, " (overlaps_a = ");
- print_generic_expr (dump_file, *overlaps_a, 0);
- fprintf (dump_file, ")\n (overlaps_b = ");
- print_generic_expr (dump_file, *overlaps_b, 0);
- fprintf (dump_file, ")\n");
- }
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, ")\n");
-}
-
-/* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
- *OVERLAPS_B are initialized to the functions that describe the
- relation between the elements accessed twice by CHREC_A and
- CHREC_B. For k >= 0, the following property is verified:
-
- CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
-
-static void
-analyze_siv_subscript (tree chrec_a,
- tree chrec_b,
- tree *overlaps_a,
- tree *overlaps_b,
- tree *last_conflicts)
-{
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "(analyze_siv_subscript \n");
-
- if (evolution_function_is_constant_p (chrec_a)
- && evolution_function_is_affine_p (chrec_b))
- analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
- overlaps_a, overlaps_b, last_conflicts);
-
- else if (evolution_function_is_affine_p (chrec_a)
- && evolution_function_is_constant_p (chrec_b))
- analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
- overlaps_b, overlaps_a, last_conflicts);
-
- else if (evolution_function_is_affine_p (chrec_a)
- && evolution_function_is_affine_p (chrec_b))
- analyze_subscript_affine_affine (chrec_a, chrec_b,
- overlaps_a, overlaps_b, last_conflicts);
- else
- {
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
- *last_conflicts = chrec_dont_know;
- }
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, ")\n");
-}
-
-/* Return true when the evolution steps of an affine CHREC divide the
- constant CST. */
-
-static bool
-chrec_steps_divide_constant_p (tree chrec,
- tree cst)
-{
- switch (TREE_CODE (chrec))
- {
- case POLYNOMIAL_CHREC:
- return (tree_fold_divides_p (integer_type_node, CHREC_RIGHT (chrec), cst)
- && chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst));
-
- default:
- /* On the initial condition, return true. */
- return true;
- }
-}
-
-/* Analyze a MIV (Multiple Index Variable) subscript. *OVERLAPS_A and
- *OVERLAPS_B are initialized to the functions that describe the
- relation between the elements accessed twice by CHREC_A and
- CHREC_B. For k >= 0, the following property is verified:
-
- CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
-
-static void
-analyze_miv_subscript (tree chrec_a,
- tree chrec_b,
- tree *overlaps_a,
- tree *overlaps_b,
- tree *last_conflicts)
-{
- /* FIXME: This is a MIV subscript, not yet handled.
- Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
- (A[i] vs. A[j]).
-
- In the SIV test we had to solve a Diophantine equation with two
- variables. In the MIV case we have to solve a Diophantine
- equation with 2*n variables (if the subscript uses n IVs).
- */
- tree difference;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "(analyze_miv_subscript \n");
-
- difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
-
- if (chrec_zerop (difference))
- {
- /* Access functions are the same: all the elements are accessed
- in the same order. */
- *overlaps_a = integer_zero_node;
- *overlaps_b = integer_zero_node;
- *last_conflicts = number_of_iterations_in_loop
- (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
- }
-
- else if (evolution_function_is_constant_p (difference)
- /* For the moment, the following is verified:
- evolution_function_is_affine_multivariate_p (chrec_a) */
- && !chrec_steps_divide_constant_p (chrec_a, difference))
- {
- /* testsuite/.../ssa-chrec-33.c
- {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
-
- The difference is 1, and the evolution steps are equal to 2,
- consequently there are no overlapping elements. */
- *overlaps_a = chrec_known;
- *overlaps_b = chrec_known;
- *last_conflicts = integer_zero_node;
- }
-
- else if (evolution_function_is_affine_multivariate_p (chrec_a)
- && evolution_function_is_affine_multivariate_p (chrec_b))
- {
- /* testsuite/.../ssa-chrec-35.c
- {0, +, 1}_2 vs. {0, +, 1}_3
- the overlapping elements are respectively located at iterations:
- {0, +, 1}_x and {0, +, 1}_x,
- in other words, we have the equality:
- {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
-
- Other examples:
- {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
- {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
-
- {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
- {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
- */
- analyze_subscript_affine_affine (chrec_a, chrec_b,
- overlaps_a, overlaps_b, last_conflicts);
- }
-
- else
- {
- /* When the analysis is too difficult, answer "don't know". */
- *overlaps_a = chrec_dont_know;
- *overlaps_b = chrec_dont_know;
- *last_conflicts = chrec_dont_know;
- }
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, ")\n");
-}
-
-/* Determines the iterations for which CHREC_A is equal to CHREC_B.
- OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with
- two functions that describe the iterations that contain conflicting
- elements.
-
- Remark: For an integer k >= 0, the following equality is true:
-
- CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
-*/
-
-static void
-analyze_overlapping_iterations (tree chrec_a,
- tree chrec_b,
- tree *overlap_iterations_a,
- tree *overlap_iterations_b,
- tree *last_conflicts)
-{
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "(analyze_overlapping_iterations \n");
- fprintf (dump_file, " (chrec_a = ");
- print_generic_expr (dump_file, chrec_a, 0);
- fprintf (dump_file, ")\n chrec_b = ");
- print_generic_expr (dump_file, chrec_b, 0);
- fprintf (dump_file, ")\n");
- }
-
- if (chrec_a == NULL_TREE
- || chrec_b == NULL_TREE
- || chrec_contains_undetermined (chrec_a)
- || chrec_contains_undetermined (chrec_b)
- || chrec_contains_symbols (chrec_a)
- || chrec_contains_symbols (chrec_b))
- {
- *overlap_iterations_a = chrec_dont_know;
- *overlap_iterations_b = chrec_dont_know;
- }
-
- else if (ziv_subscript_p (chrec_a, chrec_b))
- analyze_ziv_subscript (chrec_a, chrec_b,
- overlap_iterations_a, overlap_iterations_b,
- last_conflicts);
-
- else if (siv_subscript_p (chrec_a, chrec_b))
- analyze_siv_subscript (chrec_a, chrec_b,
- overlap_iterations_a, overlap_iterations_b,
- last_conflicts);
-
- else
- analyze_miv_subscript (chrec_a, chrec_b,
- overlap_iterations_a, overlap_iterations_b,
- last_conflicts);
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, " (overlap_iterations_a = ");
- print_generic_expr (dump_file, *overlap_iterations_a, 0);
- fprintf (dump_file, ")\n (overlap_iterations_b = ");
- print_generic_expr (dump_file, *overlap_iterations_b, 0);
- fprintf (dump_file, ")\n");
- }
-}
-
-\f
-
-/* This section contains the affine functions dependences detector. */
-
-/* Computes the conflicting iterations, and initialize DDR. */
-
-static void
-subscript_dependence_tester (struct data_dependence_relation *ddr)
-{
- unsigned int i;
- struct data_reference *dra = DDR_A (ddr);
- struct data_reference *drb = DDR_B (ddr);
- tree last_conflicts;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "(subscript_dependence_tester \n");
-
- for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
- {
- tree overlaps_a, overlaps_b;
- struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
-
- analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
- DR_ACCESS_FN (drb, i),
- &overlaps_a, &overlaps_b,
- &last_conflicts);
-
- if (chrec_contains_undetermined (overlaps_a)
- || chrec_contains_undetermined (overlaps_b))
- {
- finalize_ddr_dependent (ddr, chrec_dont_know);
- break;
- }
-
- else if (overlaps_a == chrec_known
- || overlaps_b == chrec_known)
- {
- finalize_ddr_dependent (ddr, chrec_known);
- break;
- }
-
- else
- {
- SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
- SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
- SUB_LAST_CONFLICT (subscript) = last_conflicts;
- }
- }
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, ")\n");
-}
-
-/* Compute the classic per loop distance vector.
-
- DDR is the data dependence relation to build a vector from.
- NB_LOOPS is the total number of loops we are considering.
- FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed
- loop nest.
- Return FALSE if the dependence relation is outside of the loop nest
- starting at FIRST_LOOP_DEPTH.
- Return TRUE otherwise. */
-
-static bool
-build_classic_dist_vector (struct data_dependence_relation *ddr,
- int nb_loops, int first_loop_depth)
-{
- unsigned i;
- lambda_vector dist_v, init_v;
-
- dist_v = lambda_vector_new (nb_loops);
- init_v = lambda_vector_new (nb_loops);
- lambda_vector_clear (dist_v, nb_loops);
- lambda_vector_clear (init_v, nb_loops);
-
- if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
- return true;
-
- for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
- {
- tree access_fn_a, access_fn_b;
- struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
-
- if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
- {
- non_affine_dependence_relation (ddr);
- return true;
- }
-
- access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
- access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i);
-
- if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
- && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
- {
- int dist, loop_nb, loop_depth;
- int loop_nb_a = CHREC_VARIABLE (access_fn_a);
- int loop_nb_b = CHREC_VARIABLE (access_fn_b);
- struct loop *loop_a = current_loops->parray[loop_nb_a];
- struct loop *loop_b = current_loops->parray[loop_nb_b];
-
- /* If the loop for either variable is at a lower depth than
- the first_loop's depth, then we can't possibly have a
- dependency at this level of the loop. */
-
- if (loop_a->depth < first_loop_depth
- || loop_b->depth < first_loop_depth)
- return false;
-
- if (loop_nb_a != loop_nb_b
- && !flow_loop_nested_p (loop_a, loop_b)
- && !flow_loop_nested_p (loop_b, loop_a))
- {
- /* Example: when there are two consecutive loops,
-
- | loop_1
- | A[{0, +, 1}_1]
- | endloop_1
- | loop_2
- | A[{0, +, 1}_2]
- | endloop_2
-
- the dependence relation cannot be captured by the
- distance abstraction. */
- non_affine_dependence_relation (ddr);
- return true;
- }
-
- /* The dependence is carried by the outermost loop. Example:
- | loop_1
- | A[{4, +, 1}_1]
- | loop_2
- | A[{5, +, 1}_2]
- | endloop_2
- | endloop_1
- In this case, the dependence is carried by loop_1. */
- loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
- loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth;
-
- /* If the loop number is still greater than the number of
- loops we've been asked to analyze, or negative,
- something is borked. */
- gcc_assert (loop_depth >= 0);
- gcc_assert (loop_depth < nb_loops);
- if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
- {
- non_affine_dependence_relation (ddr);
- return true;
- }
-
- dist = int_cst_value (SUB_DISTANCE (subscript));
-
- /* This is the subscript coupling test.
- | loop i = 0, N, 1
- | T[i+1][i] = ...
- | ... = T[i][i]
- | endloop
- There is no dependence. */
- if (init_v[loop_depth] != 0
- && dist_v[loop_depth] != dist)
- {
- finalize_ddr_dependent (ddr, chrec_known);
- return true;
- }
-
- dist_v[loop_depth] = dist;
- init_v[loop_depth] = 1;
- }
- }
-
- /* There is a distance of 1 on all the outer loops:
-
- Example: there is a dependence of distance 1 on loop_1 for the array A.
- | loop_1
- | A[5] = ...
- | endloop
- */
- {
- struct loop *lca, *loop_a, *loop_b;
- struct data_reference *a = DDR_A (ddr);
- struct data_reference *b = DDR_B (ddr);
- int lca_depth;
- loop_a = loop_containing_stmt (DR_STMT (a));
- loop_b = loop_containing_stmt (DR_STMT (b));
-
- /* Get the common ancestor loop. */
- lca = find_common_loop (loop_a, loop_b);
-
- lca_depth = lca->depth;
- lca_depth -= first_loop_depth;
- gcc_assert (lca_depth >= 0);
- gcc_assert (lca_depth < nb_loops);
-
- /* For each outer loop where init_v is not set, the accesses are
- in dependence of distance 1 in the loop. */
- if (lca != loop_a
- && lca != loop_b
- && init_v[lca_depth] == 0)
- dist_v[lca_depth] = 1;
-
- lca = lca->outer;
-
- if (lca)
- {
- lca_depth = lca->depth - first_loop_depth;
- while (lca->depth != 0)
- {
- /* If we're considering just a sub-nest, then don't record
- any information on the outer loops. */
- if (lca_depth < 0)
- break;
-
- gcc_assert (lca_depth < nb_loops);
-
- if (init_v[lca_depth] == 0)
- dist_v[lca_depth] = 1;
- lca = lca->outer;
- lca_depth = lca->depth - first_loop_depth;
-
- }
- }
- }
-
- DDR_DIST_VECT (ddr) = dist_v;
- DDR_SIZE_VECT (ddr) = nb_loops;
- return true;
-}
-
-/* Compute the classic per loop direction vector.
-
- DDR is the data dependence relation to build a vector from.
- NB_LOOPS is the total number of loops we are considering.
- FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed
- loop nest.
- Return FALSE if the dependence relation is outside of the loop nest
- at FIRST_LOOP_DEPTH.
- Return TRUE otherwise. */
-
-static bool
-build_classic_dir_vector (struct data_dependence_relation *ddr,
- int nb_loops, int first_loop_depth)
-{
- unsigned i;
- lambda_vector dir_v, init_v;
-
- dir_v = lambda_vector_new (nb_loops);
- init_v = lambda_vector_new (nb_loops);
- lambda_vector_clear (dir_v, nb_loops);
- lambda_vector_clear (init_v, nb_loops);
-
- if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
- return true;
-
- for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
- {
- tree access_fn_a, access_fn_b;
- struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
-
- if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
- {
- non_affine_dependence_relation (ddr);
- return true;
- }
-
- access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
- access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i);
- if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
- && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
- {
- int dist, loop_nb, loop_depth;
- enum data_dependence_direction dir = dir_star;
- int loop_nb_a = CHREC_VARIABLE (access_fn_a);
- int loop_nb_b = CHREC_VARIABLE (access_fn_b);
- struct loop *loop_a = current_loops->parray[loop_nb_a];
- struct loop *loop_b = current_loops->parray[loop_nb_b];
-
- /* If the loop for either variable is at a lower depth than
- the first_loop's depth, then we can't possibly have a
- dependency at this level of the loop. */
-
- if (loop_a->depth < first_loop_depth
- || loop_b->depth < first_loop_depth)
- return false;
-
- if (loop_nb_a != loop_nb_b
- && !flow_loop_nested_p (loop_a, loop_b)
- && !flow_loop_nested_p (loop_b, loop_a))
- {
- /* Example: when there are two consecutive loops,
-
- | loop_1
- | A[{0, +, 1}_1]
- | endloop_1
- | loop_2
- | A[{0, +, 1}_2]
- | endloop_2
-
- the dependence relation cannot be captured by the
- distance abstraction. */
- non_affine_dependence_relation (ddr);
- return true;
- }
-
- /* The dependence is carried by the outermost loop. Example:
- | loop_1
- | A[{4, +, 1}_1]
- | loop_2
- | A[{5, +, 1}_2]
- | endloop_2
- | endloop_1
- In this case, the dependence is carried by loop_1. */
- loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
- loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth;
-
- /* If the loop number is still greater than the number of
- loops we've been asked to analyze, or negative,
- something is borked. */
- gcc_assert (loop_depth >= 0);
- gcc_assert (loop_depth < nb_loops);
-
- if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
- {
- non_affine_dependence_relation (ddr);
- return true;
- }
-
- dist = int_cst_value (SUB_DISTANCE (subscript));
-
- if (dist == 0)
- dir = dir_equal;
- else if (dist > 0)
- dir = dir_positive;
- else if (dist < 0)
- dir = dir_negative;
-
- /* This is the subscript coupling test.
- | loop i = 0, N, 1
- | T[i+1][i] = ...
- | ... = T[i][i]
- | endloop
- There is no dependence. */
- if (init_v[loop_depth] != 0
- && dir != dir_star
- && (enum data_dependence_direction) dir_v[loop_depth] != dir
- && (enum data_dependence_direction) dir_v[loop_depth] != dir_star)
- {
- finalize_ddr_dependent (ddr, chrec_known);
- return true;
- }
-
- dir_v[loop_depth] = dir;
- init_v[loop_depth] = 1;
- }
- }
-
- /* There is a distance of 1 on all the outer loops:
-
- Example: there is a dependence of distance 1 on loop_1 for the array A.
- | loop_1
- | A[5] = ...
- | endloop
- */
- {
- struct loop *lca, *loop_a, *loop_b;
- struct data_reference *a = DDR_A (ddr);
- struct data_reference *b = DDR_B (ddr);
- int lca_depth;
- loop_a = loop_containing_stmt (DR_STMT (a));
- loop_b = loop_containing_stmt (DR_STMT (b));
-
- /* Get the common ancestor loop. */
- lca = find_common_loop (loop_a, loop_b);
- lca_depth = lca->depth - first_loop_depth;
-
- gcc_assert (lca_depth >= 0);
- gcc_assert (lca_depth < nb_loops);
-
- /* For each outer loop where init_v is not set, the accesses are
- in dependence of distance 1 in the loop. */
- if (lca != loop_a
- && lca != loop_b
- && init_v[lca_depth] == 0)
- dir_v[lca_depth] = dir_positive;
-
- lca = lca->outer;
- if (lca)
- {
- lca_depth = lca->depth - first_loop_depth;
- while (lca->depth != 0)
- {
- /* If we're considering just a sub-nest, then don't record
- any information on the outer loops. */
- if (lca_depth < 0)
- break;
-
- gcc_assert (lca_depth < nb_loops);
-
- if (init_v[lca_depth] == 0)
- dir_v[lca_depth] = dir_positive;
- lca = lca->outer;
- lca_depth = lca->depth - first_loop_depth;
-
- }
- }
- }
-
- DDR_DIR_VECT (ddr) = dir_v;
- DDR_SIZE_VECT (ddr) = nb_loops;
- return true;
-}
-
-/* Returns true when all the access functions of A are affine or
- constant. */
-
-static bool
-access_functions_are_affine_or_constant_p (struct data_reference *a)
-{
- unsigned int i;
- varray_type fns = DR_ACCESS_FNS (a);
-
- for (i = 0; i < VARRAY_ACTIVE_SIZE (fns); i++)
- if (!evolution_function_is_constant_p (VARRAY_TREE (fns, i))
- && !evolution_function_is_affine_multivariate_p (VARRAY_TREE (fns, i)))
- return false;
-
- return true;
-}
-
-/* This computes the affine dependence relation between A and B.
- CHREC_KNOWN is used for representing the independence between two
- accesses, while CHREC_DONT_KNOW is used for representing the unknown
- relation.
-
- Note that it is possible to stop the computation of the dependence
- relation the first time we detect a CHREC_KNOWN element for a given
- subscript. */
-
-void
-compute_affine_dependence (struct data_dependence_relation *ddr)
-{
- struct data_reference *dra = DDR_A (ddr);
- struct data_reference *drb = DDR_B (ddr);
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "(compute_affine_dependence\n");
- fprintf (dump_file, " (stmt_a = \n");
- print_generic_expr (dump_file, DR_STMT (dra), 0);
- fprintf (dump_file, ")\n (stmt_b = \n");
- print_generic_expr (dump_file, DR_STMT (drb), 0);
- fprintf (dump_file, ")\n");
- }
-
- /* Analyze only when the dependence relation is not yet known. */
- if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
- {
- if (access_functions_are_affine_or_constant_p (dra)
- && access_functions_are_affine_or_constant_p (drb))
- subscript_dependence_tester (ddr);
-
- /* As a last case, if the dependence cannot be determined, or if
- the dependence is considered too difficult to determine, answer
- "don't know". */
- else
- finalize_ddr_dependent (ddr, chrec_dont_know);
- }
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, ")\n");
-}
-
-/* Compute a subset of the data dependence relation graph. Don't
- compute read-read relations, and avoid the computation of the
- opposite relation, i.e. when AB has been computed, don't compute BA.
- DATAREFS contains a list of data references, and the result is set
- in DEPENDENCE_RELATIONS. */
-
-static void
-compute_all_dependences (varray_type datarefs,
- varray_type *dependence_relations)
-{
- unsigned int i, j, N;
-
- N = VARRAY_ACTIVE_SIZE (datarefs);
-
- for (i = 0; i < N; i++)
- for (j = i; j < N; j++)
- {
- struct data_reference *a, *b;
- struct data_dependence_relation *ddr;
-
- a = VARRAY_GENERIC_PTR (datarefs, i);
- b = VARRAY_GENERIC_PTR (datarefs, j);
- ddr = initialize_data_dependence_relation (a, b);
-
- VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
- compute_affine_dependence (ddr);
- compute_subscript_distance (ddr);
- }
-}
-
-/* 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, varray_type *datarefs)
-{
- bool dont_know_node_not_inserted = true;
- basic_block bb, *bbs;
- unsigned int i;
- block_stmt_iterator bsi;
-
- bbs = get_loop_body (loop);
-
- for (i = 0; i < loop->num_nodes; i++)
- {
- bb = bbs[i];
-
- for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
- {
- tree stmt = bsi_stmt (bsi);
- stmt_ann_t ann = stmt_ann (stmt);
-
- if (TREE_CODE (stmt) != MODIFY_EXPR)
- continue;
-
- if (!VUSE_OPS (ann)
- && !V_MUST_DEF_OPS (ann)
- && !V_MAY_DEF_OPS (ann))
- continue;
-
- /* In the GIMPLE representation, a modify expression
- contains a single load or store to memory. */
- if (TREE_CODE (TREE_OPERAND (stmt, 0)) == ARRAY_REF)
- VARRAY_PUSH_GENERIC_PTR
- (*datarefs, analyze_array (stmt, TREE_OPERAND (stmt, 0),
- false));
-
- else if (TREE_CODE (TREE_OPERAND (stmt, 1)) == ARRAY_REF)
- VARRAY_PUSH_GENERIC_PTR
- (*datarefs, analyze_array (stmt, TREE_OPERAND (stmt, 1),
- true));
- else
- {
- if (dont_know_node_not_inserted)
- {
- struct data_reference *res;
- res = xmalloc (sizeof (struct data_reference));
- DR_STMT (res) = NULL_TREE;
- DR_REF (res) = NULL_TREE;
- DR_ACCESS_FNS (res) = NULL;
- DR_BASE_NAME (res) = NULL;
- DR_IS_READ (res) = false;
- VARRAY_PUSH_GENERIC_PTR (*datarefs, res);
- dont_know_node_not_inserted = false;
- }
- }
-
- /* When there are no defs in the loop, the loop is parallel. */
- if (NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) > 0
- || NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt)) > 0)
- bb->loop_father->parallel_p = false;
- }
-
- if (bb->loop_father->estimated_nb_iterations == NULL_TREE)
- compute_estimated_nb_iterations (bb->loop_father);
- }
-
- free (bbs);
-
- return dont_know_node_not_inserted ? NULL_TREE : chrec_dont_know;
-}
-
-\f
-
-/* This section contains all the entry points. */
-
-/* Given a loop nest LOOP, the following vectors are returned:
- *DATAREFS is initialized to all the array elements contained in this loop,
- *DEPENDENCE_RELATIONS contains the relations between the data references. */
-
-void
-compute_data_dependences_for_loop (unsigned nb_loops,
- struct loop *loop,
- varray_type *datarefs,
- varray_type *dependence_relations)
-{
- unsigned int i;
- varray_type allrelations;
-
- /* If one of the data references is not computable, give up without
- spending time to compute other dependences. */
- if (find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
- {
- struct data_dependence_relation *ddr;
-
- /* Insert a single relation into dependence_relations:
- chrec_dont_know. */
- ddr = initialize_data_dependence_relation (NULL, NULL);
- VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
- build_classic_dist_vector (ddr, nb_loops, loop->depth);
- build_classic_dir_vector (ddr, nb_loops, loop->depth);
- return;
- }
-
- VARRAY_GENERIC_PTR_INIT (allrelations, 1, "Data dependence relations");
- compute_all_dependences (*datarefs, &allrelations);
-
- for (i = 0; i < VARRAY_ACTIVE_SIZE (allrelations); i++)
- {
- struct data_dependence_relation *ddr;
- ddr = VARRAY_GENERIC_PTR (allrelations, i);
- if (build_classic_dist_vector (ddr, nb_loops, loop->depth))
- {
- VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
- build_classic_dir_vector (ddr, nb_loops, loop->depth);
- }
- }
-}
-
-/* Entry point (for testing only). Analyze all the data references
- and the dependence relations.
-
- The data references are computed first.
-
- A relation on these nodes is represented by a complete graph. Some
- of the relations could be of no interest, thus the relations can be
- computed on demand.
-
- In the following function we compute all the relations. This is
- just a first implementation that is here for:
- - for showing how to ask for the dependence relations,
- - for the debugging the whole dependence graph,
- - for the dejagnu testcases and maintenance.
-
- It is possible to ask only for a part of the graph, avoiding to
- compute the whole dependence graph. The computed dependences are
- stored in a knowledge base (KB) such that later queries don't
- recompute the same information. The implementation of this KB is
- transparent to the optimizer, and thus the KB can be changed with a
- more efficient implementation, or the KB could be disabled. */
-
-void
-analyze_all_data_dependences (struct loops *loops)
-{
- unsigned int i;
- varray_type datarefs;
- varray_type dependence_relations;
- int nb_data_refs = 10;
-
- VARRAY_GENERIC_PTR_INIT (datarefs, nb_data_refs, "datarefs");
- VARRAY_GENERIC_PTR_INIT (dependence_relations,
- nb_data_refs * nb_data_refs,
- "dependence_relations");
-
- /* Compute DDs on the whole function. */
- compute_data_dependences_for_loop (loops->num, loops->parray[0],
- &datarefs, &dependence_relations);
-
- if (dump_file)
- {
- dump_data_dependence_relations (dump_file, dependence_relations);
- fprintf (dump_file, "\n\n");
-
- if (dump_flags & TDF_DETAILS)
- dump_dist_dir_vectors (dump_file, dependence_relations);
-
- if (dump_flags & TDF_STATS)
- {
- unsigned nb_top_relations = 0;
- unsigned nb_bot_relations = 0;
- unsigned nb_basename_differ = 0;
- unsigned nb_chrec_relations = 0;
-
- for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
- {
- struct data_dependence_relation *ddr;
- ddr = VARRAY_GENERIC_PTR (dependence_relations, i);
-
- if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
- nb_top_relations++;
-
- else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
- {
- struct data_reference *a = DDR_A (ddr);
- struct data_reference *b = DDR_B (ddr);
- bool differ_p;
-
- if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b)
- || (array_base_name_differ_p (a, b, &differ_p) && differ_p))
- nb_basename_differ++;
- else
- nb_bot_relations++;
- }
-
- else
- nb_chrec_relations++;
- }
-
- gather_stats_on_scev_database ();
- }
- }
-
- free_dependence_relations (dependence_relations);
- free_data_refs (datarefs);
-}
-
-/* Free the memory used by a data dependence relation DDR. */
-
-void
-free_dependence_relation (struct data_dependence_relation *ddr)
-{
- if (ddr == NULL)
- return;
-
- if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr))
- varray_clear (DDR_SUBSCRIPTS (ddr));
- free (ddr);
-}
-
-/* Free the memory used by the data dependence relations from
- DEPENDENCE_RELATIONS. */
-
-void
-free_dependence_relations (varray_type dependence_relations)
-{
- unsigned int i;
- if (dependence_relations == NULL)
- return;
-
- for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
- free_dependence_relation (VARRAY_GENERIC_PTR (dependence_relations, i));
- varray_clear (dependence_relations);
-}
-
-/* Free the memory used by the data references from DATAREFS. */
-
-void
-free_data_refs (varray_type datarefs)
-{
- unsigned int i;
-
- if (datarefs == NULL)
- return;
-
- for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
- {
- struct data_reference *dr = (struct data_reference *)
- VARRAY_GENERIC_PTR (datarefs, i);
- if (dr)
- {
- if (DR_ACCESS_FNS (dr))
- varray_clear (DR_ACCESS_FNS (dr));
- free (dr);
- }
- }
- varray_clear (datarefs);
-}
-
[-- Attachment #3: dynprof.h --]
[-- Type: application/octet-stream, Size: 5374 bytes --]
/*
dynprof.h - Header file for dynamic profiling code
ADDED_AD : 02/12/2004: First version before cvs checkin. This is a more optimized, cleaner source file than
used previously. Functionality for dynamic profiling only contained here now.
*/
#include "memsimlib.h"
#include "varray.h"
typedef int myint;
#define ROWWISE 1
#define SCATTERGATHER 2
#define NONE 3
#define PROF_MAXLINE 256 /*max size of a line (string)*/
#define PROF_MEMCFGFILE "mem.cfg" /*name of the file used to store mem config info*/
#define STAMP_DUMP "out.stamp" /* name of file used to hold timestamp info */
#define PROF_MAXNREGS 64 /*max num of regs for compiler analysis*/
#define PROF_CALLGRAPHOUT "out.callgraph" //initial callgraph file
#define PROF_DPRGOUT "out.dprg" //initial callgraph file
#define PROF_GLOBALS "out.globals" //dumps out all global vars seen
struct basic_block_info{
varray_type myrefs;
int num;
int id;
int loop_level;
int depth;
int highest_depth;
};
typedef struct basic_block_info bblock_info;
struct partializing_info{
int dimension;
int type;
varray_type myrefs;
char base_array_name[10];
int no_of_dimensions;
int dimension_sizes;
int starting_offset;
int stride;
};
//structure used to store variable info
typedef struct {
char name[256]; //name of variable
int nread; //total number of reads
int nwrite; //total number of writes
int size; //size of the variable (in bytes)
int ispublic; //0 = var is static (not public), 1 = var is public
int index; //stores index of variable
//char type[256]; //stores type of variable(int,char,etc) maybe used later
//int sram; //shows if it should be allocated to sram
} profVars_t;
/****************************ADDED_SK****************************/
#define PROF_DEBUG "out.debug" //initial callgraph file
#define MAX_NODES 2
// Following define the type of Dprg nodes possible
#define B_BLOCK -1
// Following define the type of Dprg nodes possible
/*#define PROC 1
#define LOOP 2
#define VAR 3
#define LOOP_HEADER 4
#define IF_THEN 5
#define B_BLOCK 6
*/
#define INPUT_DPRG "dprg.input"
#define OUT_STACK "out.stack"
#define MAXNODES 100;
typedef struct{
char name[128];
int id;
int fileid;
int functionid;
int markerid;
int type;
int size;
int loop_index;
char scope[32];
int path_id;
int no_of_children;
int parent_bb;
int current_bb;
int end_bb;
int start_bb;
dll_t* childlist;
}dynprofNodeInfo_t;
typedef struct{
int id;
int type;
int read_weight;
int write_weight;
int invocations; // a running counter used for different purposes like invocations to a region, counter to the next use in history
int no_of_children;
int no_of_parents;
int no_of_paths;
int size;
int allocation_point; // is either 1/0 in the dprg for non variables nodes, undefined for variables nodes
//, but during allocation stores the offset in the history table for variable nodes.
// allca allocation[1]; // for a region stores allocation information at different time stamps contained in it.
//char parents[5][50];
// int* weight_of_path;
//t_stamp* time_stamps_for_edge;
char scope[32];
int allocation_choosen;
dll_t* child_list;
}dynprofAllocNode_t;
/***************************END_SK*****************************/
/******** Used to generate DYNAMIC profiling information ********/
/*Inserts the initialization function calls necessary for generating dynamic profiling information. */
int dynprofInsertMarkers(tree decl, rtx insns,int FileID,int FuncID);
/* Isnerts markers, according to slightly different loop semantics */
//int dynprofInsertDprgMarkers(tree decl, rtx insns,int FileID,int FuncID);
/* Inserts me style region markers */
int dynprofInsertRegionMarkers(tree decl, rtx insns,int FileID,int FuncID);
int dynprofInsertDprgMarkers(tree decl, rtx insns,int FileID,int FuncID,int markerid);
/*inserts hooks to avoid library call profiling */
int dynprofInsertProfCalls(tree decl, rtx insns);
int dynprofInsertProfCallsDprg(tree decl, rtx insns,int a, int b,int c);//this is the version for 2ndary ifthen call search
/*function used to initialize memory profiling */
int dynprofInit(char *basefilename);
/*clean up */
int dynprofDestroy(void);
//BELOW is for ad region profiling
/* Dumps callgraph and static dprg */
int dynprofDumpStaticInfo(tree decl, rtx insns,int fileid,int funcid,int FuncMark);
/* Dumps static dprg and inserts initial markers for loops and ifthen conditional blocks */
int dynprofDumpStaticGraph(tree decl, rtx insns);
int dynprofInsertChildNode(int type);
int dynprofPrintGraph(void);
int dynprofInsertIfThenStartAD(rtx tmprtx,int MarkerID, int Type);
int dynprofInsertIfThenEndAD(rtx tmprtx,int MarkerID, int Type);
int dynprofInsertLoopStartAD(rtx tmprtx,int MarkerID, int Type);
int dynprofInsertLoopEndAD(rtx tmprtx,int MarkerID, int Type);
int dynprofInsertLoopContAD(rtx tmprtx,int MarkerID, int Type);
int get_mem_exprAD(tree expr);
int FindVarAD(rtx rtxnode);
int dynprofDumpTree(tree decl);
//end ad region profiling
//Used to dump out callgraph for ilp profiling
int dynprofDumpStaticILP(tree decl, rtx insns);
int dynprofInsertSaveRegs(rtx tmprtx);
int dynprofInsertRestoreRegs(rtx tmprtx);
int dynprofCheckCALL(rtx rtxnode, char *funcname);
int dynprofClearList(dll_t *list);//cleanup code
[-- Attachment #4: main.c --]
[-- Type: application/octet-stream, Size: 641 bytes --]
#define A_ROW 10
#define A_COL 10
#define B_ROW 10
#define B_COL 10
int a_matrix[10][10];
//int b_matrix[10][10];
//int c_matrix[10][10];
void foo();
void a();
main()
{
int i,j,k;
int sum;
for (i = 0; i < A_ROW; i++) {
for (j = 0; j < B_COL; j++) {
sum = 0.0;
for (k = 0; k < B_ROW; ++k) {
//sum += a_matrix[i][k] * b_matrix[k][j];
a();
sum += a_matrix[i][k];
}
// c_matrix[i][j] = sum;
}
}
printf(" %d \n",sum);
}
/*
void foo()
{
printf("hello \n");
}
*/
^ permalink raw reply [flat|nested] 7+ messages in thread