X-Git-Url: https://oss.titaniummirror.com/gitweb?a=blobdiff_plain;f=gcc%2Fdependence.c;fp=gcc%2Fdependence.c;h=0000000000000000000000000000000000000000;hb=6fed43773c9b0ce596dca5686f37ac3fc0fa11c0;hp=1a5564dda9ab28698e688f952ccc214fb304b63c;hpb=27b11d56b743098deb193d510b337ba22dc52e5c;p=msp430-gcc.git diff --git a/gcc/dependence.c b/gcc/dependence.c deleted file mode 100644 index 1a5564dd..00000000 --- a/gcc/dependence.c +++ /dev/null @@ -1,1467 +0,0 @@ -/* Analyze loop dependencies - Copyright (C) 2000, 2002 Free Software Foundation, Inc. - -This file is part of GCC. - -GCC is free software; you can redistribute it and/or modify it under -the terms of the GNU General Public License as published by the Free -Software Foundation; either version 2, or (at your option) any later -version. - -GCC is distributed in the hope that it will be useful, but WITHOUT ANY -WARRANTY; without even the implied warranty of MERCHANTABILITY or -FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License -for more details. - -You should have received a copy of the GNU General Public License -along with GCC; see the file COPYING. If not, write to the Free -Software Foundation, 59 Temple Place - Suite 330, Boston, MA -02111-1307, USA. */ - -/* References: - Practical Dependence Testing, Goff, Kennedy, Tseng, PLDI, 1991 - High Performance Compilers for Parallel Computing, Wolfe -*/ - -#include "config.h" -#include "system.h" - -#include "rtl.h" -#include "expr.h" -#include "tree.h" -#include "c-common.h" -#include "flags.h" -#include "varray.h" - -#define MAX_SUBSCRIPTS 13 - -/* - We perform the following steps: - - Build the data structures def_use_chain, loop_chain, and induction_chain. - - Determine if a loop index is a normalized induction variable. - A loop is currently considered to be a for loop having an index set to an - initial value, conditional check of the index, and increment/decrement of - the index. - - Determine the distance and direction vectors. Both are two dimensioned - arrays where the first dimension represents a loop and the second - dimension represents a subscript. Dependencies are actually per loop, not - per subscript. So for: - for (i = 0; i < 10; i++) - for (j = 0; j < 10; j++) - array [i][j] = array[i][j-1] - We find the dependencies: loop1/sub_i, loop1/sub_j, loop2/sub_i, loop2/sub_j - and then intersect loop1/sub_i V loop2/sub_i and loop1/sub_i V loop2/sub_j - We determine the type of dependence, which determines which test we use. - We then try to refine the type of dependence we have and add the - dependence to the dep_chain -*/ - -enum dependence_type {dt_flow, dt_anti, dt_output, dt_none}; -#if 0 -static const char *const dependence_string [] = {"flow", "anti", "output", "none"}; -#endif -enum direction_type {lt, le, eq, gt, ge, star, independent, undef}; -#if 0 -static const char *const direction_string [] = {"<", "<=", "=", ">", ">=", "*", - "INDEPENDENT", "UNDEFINED"}; -#endif -enum def_use_type {def, use, init_def_use}; - -enum du_status_type {seen, unseen}; - -enum loop_status_type {normal, unnormal}; - -enum complexity_type {ziv, strong_siv, weak_siv, weak_zero_siv, - weak_crossing_siv, miv}; - -/* Given a def/use one can chase the next chain to follow the def/use - for that variable. Alternately one can sequentially follow each - element of def_use_chain. */ - -typedef struct def_use -{ - /* outermost loop */ - tree outer_loop; - /* loop containing this def/use */ - tree containing_loop; - /* this expression */ - tree expression; - /* our name */ - const char *variable; - /* def or use */ - enum def_use_type type; - /* status flags */ - enum du_status_type status; - /* next def/use for this same name */ - struct def_use *next; - /* dependencies for this def */ - struct dependence *dep; -} def_use; - -/* Given a loop* one can chase the next_nest chain to follow the nested - loops for that loop. Alternately one can sequentially follow each - element of loop_chain and check outer_loop to get all loops - contained within a certain loop. */ - -typedef struct loop -{ - /* outermost loop containing this loop */ - tree outer_loop; - /* this loop */ - tree containing_loop; - /* nest level for this loop */ - int depth; - /* can loop be normalized? */ - enum loop_status_type status; - /* loop* for loop contained in this loop */ - struct loop *next_nest; - /* induction variables for this loop. Currently only the index variable. */ - struct induction *ind; -} loop; - -/* Pointed to by loop. One per induction variable. */ - -typedef struct induction -{ - /* our name */ - const char *variable; - /* increment. Currently only +1 or -1 */ - int increment; - /* lower bound */ - int low_bound; - /* upper bound */ - int high_bound; - /* next induction variable for this loop. Currently null. */ - struct induction *next; -} induction; - -/* Pointed to by def/use. One per dependence. */ - -typedef struct dependence -{ - tree source; - tree destination; - enum dependence_type dependence; - enum direction_type direction[MAX_SUBSCRIPTS]; - int distance[MAX_SUBSCRIPTS]; - struct dependence *next; -} dependence; - -/* subscripts are represented by an array of these. Each reflects one - X * i + Y term, where X and Y are constants. */ - -typedef struct subscript -{ - /* ordinal subscript number */ - int position; - /* X in X * i + Y */ - int coefficient; - /* Y in X * i + Y */ - int offset; - /* our name */ - const char *variable; - /* next subscript term. Currently null. */ - struct subscript *next; -} subscript; - -/* Remember the destination the front end encountered. */ - -static tree dest_to_remember; - -/* Chain for def_use */ -static varray_type def_use_chain; - -/* Chain for dependence */ -static varray_type dep_chain; - -/* Chain for loop */ -static varray_type loop_chain; - -/* Chain for induction */ -static varray_type induction_chain; - -void init_dependence_analysis PARAMS ((tree)); -static void build_def_use PARAMS ((tree, enum def_use_type)); -static loop* add_loop PARAMS ((tree, tree, int)); -static int find_induction_variable PARAMS ((tree, tree, tree, loop*)); -static int get_low_bound PARAMS ((tree, const char*)); -static int have_induction_variable PARAMS ((tree, const char*)); -static void link_loops PARAMS ((void)); -static void get_node_dependence PARAMS ((void)); -static void check_node_dependence PARAMS ((def_use*)); -static int get_coefficients PARAMS ((def_use*, subscript[])); -static int get_one_coefficient PARAMS ((tree, subscript*, def_use*, enum tree_code*)); -static void normalize_coefficients PARAMS ((subscript[], loop*, int)); -static void classify_dependence PARAMS ((subscript[], subscript[], - enum complexity_type[], int*, int)); -static void ziv_test PARAMS ((subscript[], subscript[], - enum direction_type[][MAX_SUBSCRIPTS], - int[][MAX_SUBSCRIPTS], loop*, int)); -static void siv_test PARAMS ((subscript[], subscript[], - enum direction_type[][MAX_SUBSCRIPTS], - int[][MAX_SUBSCRIPTS], loop*, int)); -static int check_subscript_induction PARAMS ((subscript*, subscript*, loop*)); -static void gcd_test PARAMS ((subscript[], subscript[], enum - direction_type[][MAX_SUBSCRIPTS], - int[][MAX_SUBSCRIPTS], loop*, int)); -static int find_gcd PARAMS ((int, int)); -static void merge_dependencies PARAMS ((enum direction_type[][MAX_SUBSCRIPTS], - int[][MAX_SUBSCRIPTS], int, int)); -static void dump_array_ref PARAMS ((tree)); -#if 0 -static void dump_one_node PARAMS ((def_use*, varray_type*)); -static void dump_node_dependence PARAMS ((void)); -#endif -int search_dependence PARAMS ((tree)); -void remember_dest_for_dependence PARAMS ((tree)); -int have_dependence_p PARAMS ((rtx, rtx, enum direction_type[], int[])); -void end_dependence_analysis PARAMS ((void)); - -/* Build dependence chain 'dep_chain', which is used by have_dependence_p, - for the function given by EXP. */ - -void -init_dependence_analysis (exp) - tree exp; -{ - def_use *du_ptr; - - VARRAY_GENERIC_PTR_INIT (def_use_chain, 50, "def_use_chain"); - VARRAY_GENERIC_PTR_INIT (dep_chain, 50, "dep_chain"); - VARRAY_GENERIC_PTR_INIT (loop_chain, 50, "loop_chain"); - VARRAY_GENERIC_PTR_INIT (induction_chain, 50, "induction_chain"); - - build_def_use (exp, init_def_use); - - link_loops (); - - get_node_dependence (); - - /* dump_node_dependence (&def_use_chain);*/ - - for (du_ptr = VARRAY_TOP (def_use_chain, generic); - VARRAY_POP (def_use_chain); - du_ptr = VARRAY_TOP (def_use_chain, generic)) - { - free (du_ptr); - } - - VARRAY_FREE (def_use_chain); - VARRAY_FREE (loop_chain); - VARRAY_FREE (induction_chain); -} - -/* Build ARRAY_REF def/use info 'def_use_chain' starting at EXP which is a def - or use DU_TYPE */ - -static void -build_def_use (exp, du_type) - tree exp; - enum def_use_type du_type; -{ - static tree outer_loop; - static int nloop; - static tree current_loop; - static int du_idx; - static loop *loop_def; - tree node = exp; - tree array_ref; - def_use *du_ptr; - - if (du_type == init_def_use) - { - outer_loop = 0; - nloop = 0; - du_idx = 0; - } - - while (node) - switch (TREE_CODE (node)) - { - case COMPOUND_STMT: - node = TREE_OPERAND (node, 0); - break; - case TREE_LIST: - build_def_use (TREE_VALUE (node), 0); - node = TREE_CHAIN (node); - break; - case CALL_EXPR: - node = TREE_CHAIN (node); - break; - case FOR_STMT: - if (! nloop) outer_loop = node; - nloop++; - current_loop = node; - loop_def = add_loop (node, outer_loop, nloop); - if (find_induction_variable (TREE_OPERAND (node, 0), - TREE_OPERAND (node, 1), - TREE_OPERAND (node, 2), loop_def) - == 0) - loop_def->status = unnormal; - - build_def_use (TREE_OPERAND (node, 3), 0); - nloop--; - current_loop = 0; - node = TREE_CHAIN (node); - break; - case MODIFY_EXPR: - /* Is an induction variable modified? */ - if (loop_def - && TREE_CODE (TREE_OPERAND (node, 0)) == VAR_DECL - && have_induction_variable - (loop_def->outer_loop, - IDENTIFIER_POINTER (DECL_NAME (TREE_OPERAND (node, 0)))) >= 0) - loop_def->status = unnormal; - - if (TREE_CODE (TREE_OPERAND (node, 0)) == ARRAY_REF - || TREE_CODE (TREE_OPERAND (node, 0)) == INDIRECT_REF) - build_def_use (TREE_OPERAND (node, 0), def); - - build_def_use (TREE_OPERAND (node, 1), use); - node = TREE_CHAIN (node); - break; - case INDIRECT_REF: - if (! TREE_OPERAND (node, 1) - || TREE_CODE (TREE_OPERAND (node, 1)) != ARRAY_REF) - { - node = 0; - break; - } - node = TREE_OPERAND (node, 1); - case ARRAY_REF: - if (nloop) - { - int i; - char null_string = '\0'; - - VARRAY_PUSH_GENERIC_PTR (def_use_chain, xmalloc (sizeof (def_use))); - du_ptr = VARRAY_GENERIC_PTR (def_use_chain, du_idx++); - du_ptr->type = du_type; - du_ptr->status = unseen; - du_ptr->outer_loop = outer_loop; - du_ptr->containing_loop = current_loop; - du_ptr->expression = node; - du_ptr->variable = &null_string; - du_ptr->next = 0; - du_ptr->dep = 0; - for (array_ref = node; - TREE_CODE (array_ref) == ARRAY_REF; - array_ref = TREE_OPERAND (array_ref, 0)) - ; - - if (TREE_CODE (array_ref) == COMPONENT_REF) - { - array_ref = TREE_OPERAND (array_ref, 1); - if (! (TREE_CODE (array_ref) == FIELD_DECL - && TREE_CODE (TREE_TYPE (array_ref)) == ARRAY_TYPE)) - { - node = 0; - break; - } - } - - for (i = 0; - i < du_idx - && strcmp (IDENTIFIER_POINTER (DECL_NAME (array_ref)), - ((def_use*) (VARRAY_GENERIC_PTR - (def_use_chain, i)))->variable); - i++) - ; - if (i != du_idx) - { - def_use *tmp_duc; - for (tmp_duc = ((def_use*) (VARRAY_GENERIC_PTR (def_use_chain, i))); - tmp_duc->next; - tmp_duc = ((def_use*)tmp_duc->next)); - tmp_duc->next = du_ptr; - } - else du_ptr->next = 0; - du_ptr->variable = IDENTIFIER_POINTER (DECL_NAME (array_ref)); - } - node = 0; - break; - - case SCOPE_STMT: - case DECL_STMT: - node = TREE_CHAIN (node); - break; - - case EXPR_STMT: - if (TREE_CODE (TREE_OPERAND (node, 0)) == MODIFY_EXPR) - build_def_use (TREE_OPERAND (node, 0), def); - node = TREE_CHAIN (node); - break; - - default: - if (TREE_CODE_CLASS (TREE_CODE (node)) == '2') - { - build_def_use (TREE_OPERAND (node, 0), use); - build_def_use (TREE_OPERAND (node, 1), use); - node = TREE_CHAIN (node); - } - else - node = 0; - } -} - -/* Add a loop to 'loop_chain' corresponding to for loop LOOP_NODE at depth - NLOOP, whose outermost loop is OUTER_LOOP */ - -static loop* -add_loop (loop_node, outer_loop, nloop) - tree loop_node; - tree outer_loop; - int nloop; -{ - loop *loop_ptr; - - VARRAY_PUSH_GENERIC_PTR (loop_chain, xmalloc (sizeof (loop))); - loop_ptr = VARRAY_TOP (loop_chain, generic); - loop_ptr->outer_loop = outer_loop; - loop_ptr->containing_loop = loop_node; - loop_ptr->depth = nloop; - loop_ptr->status = normal; - loop_ptr->next_nest = 0; - loop_ptr->ind = 0; - return loop_ptr; -} - -/* Update LOOP_DEF if for loop's COND_NODE and INCR_NODE define an index that - is a normalized induction variable. */ - -static int -find_induction_variable (init_node, cond_node, incr_node, loop_def) - tree init_node; - tree cond_node; - tree incr_node; - loop *loop_def; -{ - induction *ind_ptr; - enum tree_code incr_code; - tree incr; - - if (! init_node || ! incr_node || ! cond_node) - return 0; - /* Allow for ',' operator in increment expression of FOR */ - - incr = incr_node; - while (TREE_CODE (incr) == COMPOUND_EXPR) - { - incr_code = TREE_CODE (TREE_OPERAND (incr, 0)); - if (incr_code == PREDECREMENT_EXPR || incr_code == POSTDECREMENT_EXPR - || incr_code == PREINCREMENT_EXPR || incr_code == POSTINCREMENT_EXPR) - { - incr_node = TREE_OPERAND (incr, 0); - break; - } - incr_code = TREE_CODE (TREE_OPERAND (incr, 1)); - if (incr_code == PREDECREMENT_EXPR || incr_code == POSTDECREMENT_EXPR - || incr_code == PREINCREMENT_EXPR || incr_code == POSTINCREMENT_EXPR) - { - incr_node = TREE_OPERAND (incr, 1); - break; - } - incr = TREE_OPERAND (incr, 1); - } - - /* Allow index condition to be part of logical expression */ - cond_node = TREE_VALUE (cond_node); - incr = cond_node; - -#define INDEX_LIMIT_CHECK(NODE) \ - (TREE_CODE_CLASS (TREE_CODE (NODE)) == '<') \ - && (TREE_CODE (TREE_OPERAND (NODE, 0)) == VAR_DECL \ - && (IDENTIFIER_POINTER (DECL_NAME (TREE_OPERAND (NODE, 0))) \ - == IDENTIFIER_POINTER (DECL_NAME (TREE_OPERAND (incr_node, 0))))) \ - ? 1 : 0 - - while (TREE_CODE (incr) == TRUTH_ANDIF_EXPR - || TREE_CODE (incr) == TRUTH_ORIF_EXPR) - { - if (INDEX_LIMIT_CHECK (TREE_OPERAND (incr, 0))) - { - cond_node = TREE_OPERAND (incr, 0); - break; - } - if (INDEX_LIMIT_CHECK (TREE_OPERAND (incr, 1))) - { - cond_node = TREE_OPERAND (incr, 1); - break; - } - incr = TREE_OPERAND (incr, 0); - } - - incr_code = TREE_CODE (incr_node); - if ((incr_code == PREDECREMENT_EXPR || incr_code == POSTDECREMENT_EXPR - || incr_code == PREINCREMENT_EXPR || incr_code == POSTINCREMENT_EXPR) - && TREE_CODE_CLASS (TREE_CODE (cond_node)) == '<') - { - if (!INDEX_LIMIT_CHECK (cond_node)) - return 0; - - VARRAY_PUSH_GENERIC_PTR (induction_chain, xmalloc (sizeof (induction))); - ind_ptr = VARRAY_TOP (induction_chain, generic); - loop_def->ind = ind_ptr; - ind_ptr->variable = IDENTIFIER_POINTER (DECL_NAME (TREE_OPERAND - (incr_node, 0))); - ind_ptr->increment = TREE_INT_CST_LOW (TREE_OPERAND (incr_node, 1)); - if (TREE_CODE (incr_node) == PREDECREMENT_EXPR - || TREE_CODE (incr_node) == POSTDECREMENT_EXPR) - ind_ptr->increment = -ind_ptr->increment; - - ind_ptr->low_bound = get_low_bound (init_node, ind_ptr->variable); - if (TREE_CODE (TREE_OPERAND (cond_node, 0)) == VAR_DECL - && IDENTIFIER_POINTER (DECL_NAME (TREE_OPERAND (cond_node, 0))) - == ind_ptr->variable) - { - if (TREE_CODE (TREE_OPERAND (cond_node, 1)) == INTEGER_CST) - ind_ptr->high_bound = - TREE_INT_CST_LOW (TREE_OPERAND (cond_node, 1)); - else - ind_ptr->high_bound = ind_ptr->increment < 0 ? INT_MIN : INT_MAX; - } - else if (TREE_CODE (TREE_OPERAND (cond_node, 1)) == VAR_DECL - && IDENTIFIER_POINTER (DECL_NAME (TREE_OPERAND (cond_node, 1))) - == ind_ptr->variable) - { - if (TREE_CODE (TREE_OPERAND (cond_node, 0)) == INTEGER_CST) - ind_ptr->high_bound = - TREE_INT_CST_LOW (TREE_OPERAND (cond_node, 0)); - else - ind_ptr->high_bound = ind_ptr->increment < 0 ? INT_MIN : INT_MAX; - } - ind_ptr->next = 0; - return 1; - } - return 0; -} - -/* Return the low bound for induction VARIABLE in NODE */ - -static int -get_low_bound (node, variable) - tree node; - const char *variable; -{ - - if (TREE_CODE (node) == SCOPE_STMT) - node = TREE_CHAIN (node); - - if (! node) - return INT_MIN; - - while (TREE_CODE (node) == COMPOUND_EXPR) - { - if (TREE_CODE (TREE_OPERAND (node, 0)) == MODIFY_EXPR - && (TREE_CODE (TREE_OPERAND (node, 0)) == VAR_DECL - && IDENTIFIER_POINTER (DECL_NAME (TREE_OPERAND (node, 0))) - == variable)) - break; - } - - if (TREE_CODE (node) == EXPR_STMT) - node = TREE_OPERAND (node, 0); - if (TREE_CODE (node) == MODIFY_EXPR - && (TREE_CODE (TREE_OPERAND (node, 0)) == VAR_DECL - && IDENTIFIER_POINTER (DECL_NAME (TREE_OPERAND (node, 0))) - == variable)) - { - return TREE_INT_CST_LOW (TREE_OPERAND (node, 1)); - } - return INT_MIN; -} - - -/* Return the ordinal subscript position for IND_VAR if it is an induction - variable contained in OUTER_LOOP, otherwise return -1. */ - -static int -have_induction_variable (outer_loop, ind_var) - tree outer_loop; - const char *ind_var; -{ - induction *ind_ptr; - loop *loop_ptr; - unsigned int ind_idx = 0; - unsigned int loop_idx = 0; - - for (loop_ptr = VARRAY_GENERIC_PTR (loop_chain, loop_idx); - loop_ptr && loop_idx < VARRAY_SIZE (loop_chain); - loop_ptr = VARRAY_GENERIC_PTR (loop_chain, ++loop_idx)) - if (loop_ptr->outer_loop == outer_loop) - for (ind_ptr = loop_ptr->ind; - ind_ptr && ind_idx < VARRAY_SIZE (induction_chain); - ind_ptr = ind_ptr->next) - { - if (! strcmp (ind_ptr->variable, ind_var)) - return loop_idx + 1; - } - return -1; -} - -/* Chain the nodes of 'loop_chain'. */ - -static void -link_loops () -{ - unsigned int loop_idx = 0; - loop *loop_ptr, *prev_loop_ptr = 0; - - prev_loop_ptr = VARRAY_GENERIC_PTR (loop_chain, loop_idx); - for (loop_ptr = VARRAY_GENERIC_PTR (loop_chain, ++loop_idx); - loop_ptr && loop_idx < VARRAY_SIZE (loop_chain); - loop_ptr = VARRAY_GENERIC_PTR (loop_chain, ++loop_idx)) - { - if (prev_loop_ptr->outer_loop == loop_ptr->outer_loop) - { - if (prev_loop_ptr->depth == loop_ptr->depth - 1) - prev_loop_ptr->next_nest = loop_ptr; - prev_loop_ptr = loop_ptr; - } - } -} - -/* Check the dependence for each member of 'def_use_chain'. */ - -static void -get_node_dependence () -{ - unsigned int du_idx; - def_use *du_ptr; - - du_idx = 0; - for (du_ptr = VARRAY_GENERIC_PTR (def_use_chain, du_idx); - du_ptr && du_idx < VARRAY_SIZE (def_use_chain); - du_ptr = VARRAY_GENERIC_PTR (def_use_chain, du_idx++)) - { - if (du_ptr->status == unseen) - check_node_dependence (du_ptr); - } -} - -/* Check the dependence for definition DU. */ - -static void -check_node_dependence (du) - def_use *du; -{ - def_use *def_ptr, *use_ptr; - dependence *dep_ptr, *dep_list; - subscript icoefficients[MAX_SUBSCRIPTS]; - subscript ocoefficients[MAX_SUBSCRIPTS]; - loop *loop_ptr, *ck_loop_ptr; - unsigned int loop_idx = 0; - int distance[MAX_SUBSCRIPTS][MAX_SUBSCRIPTS]; - int i, j; - int subscript_count; - int unnormal_loop; - enum direction_type direction[MAX_SUBSCRIPTS][MAX_SUBSCRIPTS]; - enum complexity_type complexity[MAX_SUBSCRIPTS]; - int separability; - int have_dependence; - - for (j = 1 ; j < MAX_SUBSCRIPTS; j++) - { - direction[j][0] = undef; - distance[j][0] = 0; - } - - for (def_ptr = du; def_ptr; def_ptr = def_ptr->next) - { - if (def_ptr->type != def) - continue; - subscript_count = get_coefficients (def_ptr, ocoefficients); - if (subscript_count < 0) - continue; - - loop_idx = 0; - for (loop_ptr = VARRAY_GENERIC_PTR (loop_chain, loop_idx); - loop_ptr && loop_idx < VARRAY_SIZE (loop_chain); - loop_ptr = VARRAY_GENERIC_PTR (loop_chain, ++loop_idx)) - { - if (loop_ptr->outer_loop == def_ptr->outer_loop) - break; - } - - unnormal_loop = 0; - for (ck_loop_ptr = loop_ptr; - ck_loop_ptr && loop_idx < VARRAY_SIZE (loop_chain); - ck_loop_ptr = VARRAY_GENERIC_PTR (loop_chain, ++loop_idx)) - { - if (ck_loop_ptr->outer_loop == def_ptr->outer_loop - && ck_loop_ptr->status == unnormal) - unnormal_loop = 1; - } - if (unnormal_loop) - continue; - - normalize_coefficients (ocoefficients, loop_ptr, subscript_count); - - for (use_ptr = du; use_ptr; use_ptr = use_ptr->next) - { - if (def_ptr == use_ptr - || def_ptr->outer_loop != use_ptr->outer_loop) - continue; - def_ptr->status = seen; - use_ptr->status = seen; - subscript_count = get_coefficients (use_ptr, icoefficients); - normalize_coefficients (icoefficients, loop_ptr, subscript_count); - classify_dependence (icoefficients, ocoefficients, complexity, - &separability, subscript_count); - - for (i = 1, ck_loop_ptr = loop_ptr; ck_loop_ptr; i++) - { - for (j = 1; j <= subscript_count; j++) - { - direction[i][j] = star; - distance[i][j] = INT_MAX; - if (separability && complexity[j] == ziv) - ziv_test (icoefficients, ocoefficients, direction, distance, - ck_loop_ptr, j); - else if (separability - && (complexity[j] == strong_siv - || complexity[j] == weak_zero_siv - || complexity[j] == weak_crossing_siv)) - siv_test (icoefficients, ocoefficients, direction, distance, - ck_loop_ptr, j); - else - gcd_test (icoefficients, ocoefficients, direction, distance, - ck_loop_ptr, j); - /* ?? Add other tests: single variable exact test, banerjee */ - } - - ck_loop_ptr = ck_loop_ptr->next_nest; - } - - merge_dependencies (direction, distance, i - 1, j - 1); - - have_dependence = 0; - for (j = 1; j <= i - 1; j++) - { - if (direction[j][0] != independent) - have_dependence = 1; - } - if (! have_dependence) - continue; - - VARRAY_PUSH_GENERIC_PTR (dep_chain, xmalloc (sizeof (dependence))); - dep_ptr = VARRAY_TOP (dep_chain, generic); - dep_ptr->source = use_ptr->expression; - dep_ptr->destination = def_ptr->expression; - dep_ptr->next = 0; - - if (def_ptr < use_ptr && use_ptr->type == use) - dep_ptr->dependence = dt_flow; - else if (def_ptr > use_ptr && use_ptr->type == use) - dep_ptr->dependence = dt_anti; - else dep_ptr->dependence = dt_output; - - for (j = 1 ; j <= i - 1 ; j++) - { - if (direction[j][0] == gt) - { - dep_ptr->dependence = dt_anti; - direction[j][0] = lt; - distance[j][0] = -distance[j][0]; - break; - } - else if (direction[j][0] == lt) - { - dep_ptr->dependence = dt_flow; - break; - } - } - for (j = 1 ; j < MAX_SUBSCRIPTS ; j++) - { - dep_ptr->direction[j] = direction[j][0]; - dep_ptr->distance[j] = distance[j][0]; - } - - for (dep_list = def_ptr->dep ; - dep_list && dep_list->next ; - dep_list = dep_list->next) - ; - - if (! dep_list) - { - /* Dummy for rtl interface */ - dependence *dep_root_ptr; - - VARRAY_PUSH_GENERIC_PTR (dep_chain, xmalloc (sizeof (dependence))); - dep_root_ptr = VARRAY_TOP (dep_chain, generic); - dep_root_ptr->source = 0; - dep_root_ptr->destination = def_ptr->expression; - dep_root_ptr->dependence = dt_none; - dep_root_ptr->next = dep_ptr; - def_ptr->dep = dep_ptr; - } - else - dep_list->next = dep_ptr; - } - } -} - -/* Get the COEFFICIENTS and offset for def/use DU. */ - -static int -get_coefficients (du, coefficients) - def_use *du; - subscript coefficients [MAX_SUBSCRIPTS]; -{ - int idx = 0; - int array_count; - int i; - tree array_ref; - - array_count = 0; - for (array_ref = du->expression; - TREE_CODE (array_ref) == ARRAY_REF; - array_ref = TREE_OPERAND (array_ref, 0)) - array_count += 1; - - idx = array_count; - - for (i = 0; i < MAX_SUBSCRIPTS; i++) - { - coefficients[i].position = 0; - coefficients[i].coefficient = INT_MIN; - coefficients[i].offset = INT_MIN; - coefficients[i].variable = 0; - coefficients[i].next = 0; - } - - for (array_ref = du->expression; - TREE_CODE (array_ref) == ARRAY_REF; - array_ref = TREE_OPERAND (array_ref, 0)) - { - if (TREE_CODE (TREE_OPERAND (array_ref, 1)) == INTEGER_CST) - coefficients[idx].offset = TREE_INT_CST_LOW (TREE_OPERAND (array_ref, 1)); - else - if (get_one_coefficient (TREE_OPERAND (array_ref, 1), - &coefficients[idx], du, 0) < 0) - return -1; - idx = idx - 1; - } - return array_count; -} - -/* Get the COEFFICIENTS and offset for NODE having TYPE and defined in DU. */ - -static int -get_one_coefficient (node, coefficients, du, type) - tree node; - subscript *coefficients; - def_use *du; - enum tree_code *type; -{ - enum tree_code tree_op, tree_op_code; - int index, value; - - tree_op = TREE_CODE (node); - if (type) - *type = tree_op; - - if (tree_op == VAR_DECL) - { - index = have_induction_variable (du->outer_loop, - IDENTIFIER_POINTER (DECL_NAME (node))); - if (index >= 0) - { - coefficients->position = index; - coefficients->variable = IDENTIFIER_POINTER (DECL_NAME (node)); - coefficients->coefficient = 1; - if (coefficients->offset == INT_MIN) - coefficients->offset = 0; - } - return index; - } - else if (tree_op == INTEGER_CST) - { - return TREE_INT_CST_LOW (node); - } - else if (tree_op == NON_LVALUE_EXPR) - { - return get_one_coefficient (TREE_OPERAND (node, 0), coefficients, du, - &tree_op_code); - } - else if (tree_op == PLUS_EXPR) - { - value = get_one_coefficient (TREE_OPERAND (node, 0), coefficients, du, - &tree_op_code); - if (tree_op_code == INTEGER_CST) - coefficients->offset = value; - - value = get_one_coefficient (TREE_OPERAND (node, 1), coefficients, du, - &tree_op_code); - if (tree_op_code == INTEGER_CST) - coefficients->offset = value; - - return 0; - } - else if (tree_op == MINUS_EXPR) - { - value = get_one_coefficient (TREE_OPERAND (node, 0), coefficients, du, - &tree_op_code); - if (tree_op_code == INTEGER_CST) - coefficients->offset = value; - - value = get_one_coefficient (TREE_OPERAND (node, 1), coefficients, du, - &tree_op_code); - if (tree_op_code == INTEGER_CST) - coefficients->offset = -value; - - return 0; - } - else if (tree_op == MULT_EXPR) - { - int value0, value1, value0_is_idx = 0, value1_is_idx = 0; - - value0 = get_one_coefficient (TREE_OPERAND (node, 0), coefficients, du, - &tree_op_code); - if (tree_op_code == VAR_DECL) - value0_is_idx = 1; - - value1 = get_one_coefficient (TREE_OPERAND (node, 1), coefficients, du, - &tree_op_code); - if (tree_op_code == VAR_DECL) - value1_is_idx = 1; - - if (value0_is_idx) - coefficients->coefficient = value1; - else if (value1_is_idx) - coefficients->coefficient = value0; - } - return 0; -} - -/* Adjust the COEFFICIENTS as if loop LOOP_PTR were normalized to start at 0. */ - -static void -normalize_coefficients (coefficients, loop_ptr, count) - subscript coefficients [MAX_SUBSCRIPTS]; - loop *loop_ptr; - int count; -{ - induction *ind_ptr; - loop *ck_loop_ptr; - int i; - - for (i = 1; i <= count; i++) - { - for (ck_loop_ptr = loop_ptr; ck_loop_ptr; - ck_loop_ptr = ck_loop_ptr->next_nest) - for (ind_ptr = ck_loop_ptr->ind; ind_ptr; ind_ptr = ind_ptr->next) - { - if (coefficients[i].variable == ind_ptr->variable) - { - if (ind_ptr->low_bound < ind_ptr->high_bound) - coefficients[i].offset += coefficients[i].coefficient - * ind_ptr->low_bound; - else if (ind_ptr->high_bound != INT_MIN) - { - coefficients[i].offset = coefficients[i].coefficient - * ind_ptr->high_bound; - coefficients[i].coefficient = coefficients[i].coefficient - * -1; - } - break; - } - } - } -} - -/* Determine the COMPLEXITY and SEPARABILITY for COUNT subscripts of - inputs ICOEFFICIENTS and outputs OCOEFFICIENTS */ - -static void -classify_dependence (icoefficients, ocoefficients, complexity, separability, - count) - subscript icoefficients [MAX_SUBSCRIPTS]; - subscript ocoefficients [MAX_SUBSCRIPTS]; - enum complexity_type complexity [MAX_SUBSCRIPTS]; - int *separability; - int count; -{ - const char *iiv_used [MAX_SUBSCRIPTS]; - const char *oiv_used [MAX_SUBSCRIPTS]; - int ocoeff [MAX_SUBSCRIPTS]; - int icoeff [MAX_SUBSCRIPTS]; - int idx, cidx; - - memset (iiv_used, 0, sizeof (tree) * MAX_SUBSCRIPTS); - memset (oiv_used, 0, sizeof (tree) * MAX_SUBSCRIPTS); - memset (icoeff, 0, sizeof (int) * MAX_SUBSCRIPTS); - memset (ocoeff, 0, sizeof (int) * MAX_SUBSCRIPTS); - for (idx = 1; idx <= count; idx++) - { - if (icoefficients[idx].variable != 0) - { - if (! iiv_used[idx]) - { - iiv_used[idx] = icoefficients[idx].variable; - icoeff[idx] = icoefficients[idx].coefficient; - } - } - if (ocoefficients[idx].variable != 0) - { - if (! oiv_used[idx]) - { - oiv_used[idx] = ocoefficients[idx].variable; - ocoeff[idx] = ocoefficients[idx].coefficient; - } - } - } - - for (idx = 1; idx <= count; idx++) - { - if (iiv_used[idx] == 0 && oiv_used[idx] == 0) - complexity[idx] = ziv; - else if (iiv_used[idx] == oiv_used[idx]) - { - if (icoeff[idx] == ocoeff[idx]) - complexity[idx] = strong_siv; - else if (icoeff[idx] == -1 * ocoeff[idx]) - complexity[idx] = weak_crossing_siv; - else - complexity[idx] = weak_siv; - } - else if (icoeff[idx] == 0 || ocoeff[idx] == 0) - complexity[idx] = weak_zero_siv; - else complexity[idx] = miv; - } - - *separability = 1; - for (idx = 1; idx <= count; idx++) - { - for (cidx = 1; cidx <= count; cidx++) - { - if (idx != cidx - && iiv_used[idx] && oiv_used[cidx] - && iiv_used[idx] == oiv_used[cidx]) - *separability = 0; - } - } -} - -/* Determine the DIRECTION and DISTANCE dependency for subscript SUB of - inputs ICOEFFICIENTS and outputs OCOEFFICIENTS of loop LOOP_PTR using - the zero induction variable test */ - -static void -ziv_test (icoefficients, ocoefficients, direction, distance, loop_ptr, sub) - subscript icoefficients [MAX_SUBSCRIPTS]; - subscript ocoefficients [MAX_SUBSCRIPTS]; - enum direction_type direction[MAX_SUBSCRIPTS][MAX_SUBSCRIPTS]; - int distance[MAX_SUBSCRIPTS][MAX_SUBSCRIPTS] ATTRIBUTE_UNUSED; - loop *loop_ptr; - int sub; -{ - if (ocoefficients[sub].offset != - icoefficients[sub].offset) - direction[loop_ptr->depth][sub] = independent; -} - -/* Determine the DIRECTION and DISTANCE dependency for subscript SUB of - inputs ICOEFFICIENTS and outputs OCOEFFICIENTS of loop LOOP_PTR using - the single induction variable test */ - -static void -siv_test (icoefficients, ocoefficients, direction, distance, loop_ptr, sub) - subscript icoefficients [MAX_SUBSCRIPTS]; - subscript ocoefficients [MAX_SUBSCRIPTS]; - enum direction_type direction[MAX_SUBSCRIPTS][MAX_SUBSCRIPTS]; - int distance[MAX_SUBSCRIPTS][MAX_SUBSCRIPTS]; - loop *loop_ptr; - int sub; -{ - int coef_diff; - int coef; - int gcd; - - if (! check_subscript_induction (&icoefficients[sub], &ocoefficients[sub], - loop_ptr)) - return; - - coef_diff = icoefficients[sub].offset - ocoefficients[sub].offset; - /* strong_siv requires equal coefficients. weak_crossing_siv requires - coefficients to have equal absolute value. weak_zero_siv uses the - nonzero coefficient. */ - - if (ocoefficients[sub].coefficient == INT_MIN) - coef = icoefficients[sub].coefficient; - else if (icoefficients[sub].coefficient == INT_MIN) - coef = ocoefficients[sub].coefficient; - else if (ocoefficients[sub].coefficient == - -1 * icoefficients[sub].coefficient) - coef = 2 * abs (ocoefficients[sub].coefficient); - else - coef = icoefficients[sub].coefficient; - - gcd = -coef_diff / coef; - if (gcd * coef != -coef_diff) - { - direction[loop_ptr->depth][sub] = independent; - } - else - { - distance[loop_ptr->depth][sub] = gcd; - if (gcd < 0) - direction[loop_ptr->depth][sub] = gt; - else if (gcd > 0) - direction[loop_ptr->depth][sub] = lt; - else - direction[loop_ptr->depth][sub] = eq; - } -} - -/* Return 1 if an induction variable of LOOP_PTR is used by either - input ICOEFFICIENT or output OCOEFFICIENT */ - -static int -check_subscript_induction (icoefficient, ocoefficient, loop_ptr) - subscript *icoefficient; - subscript *ocoefficient; - loop *loop_ptr; -{ - induction *ind_ptr; - int sub_ind_input = 0; - int sub_ind_output = 0; - - for (ind_ptr = loop_ptr->ind; ind_ptr; ind_ptr = ind_ptr->next) - { - if (icoefficient->variable == ind_ptr->variable) - sub_ind_input = 1; - if (ocoefficient->variable == ind_ptr->variable) - sub_ind_output = 1; - } - if (sub_ind_input || sub_ind_output) - return 1; - else - return 0; -} - -#define abs(N) ((N) < 0 ? -(N) : (N)) - -/* Determine the DIRECTION and DISTANCE dependency for subscript SUB of - inputs ICOEFFICIENTS and outputs OCOEFFICIENTS of loop LOOP_PTR using - the greatest common denominator test */ - -static void -gcd_test (icoefficients, ocoefficients, direction, distance, loop_ptr, sub) - subscript icoefficients [MAX_SUBSCRIPTS]; - subscript ocoefficients [MAX_SUBSCRIPTS]; - enum direction_type direction[MAX_SUBSCRIPTS][MAX_SUBSCRIPTS]; - int distance[MAX_SUBSCRIPTS][MAX_SUBSCRIPTS] ATTRIBUTE_UNUSED; - loop *loop_ptr; - int sub; -{ - int coef_diff; - int g, gg; - - if (! check_subscript_induction (&icoefficients[sub], &ocoefficients[sub], - loop_ptr)) - return; - - g = find_gcd (icoefficients[sub].coefficient, - ocoefficients[sub].coefficient); - if (g > 1) - { - coef_diff = icoefficients[sub].offset - ocoefficients[sub].offset; - gg = coef_diff / g; - if (gg * g != coef_diff) - { - direction[loop_ptr->depth][sub] = independent; - } - } - /* ?? gcd does not yield direction and distance. Wolfe's direction - vector hierarchy can be used to give this. */ -} - -/* Find the gcd of X and Y using Euclid's algorithm */ - -static int -find_gcd (x, y) - int x,y; -{ - int g, g0, g1, r; - - if (x == 0) - { - g = abs (x); - } - else if (y == 0) - { - g = abs (y); - } - else - { - g0 = abs (x); - g1 = abs (y); - r = g0 % g1; - while (r != 0) - { - g0 = g1; - g1 = r; - r = g0 % g1; - } - g = g1; - } - return g; -} - -/* Merge SUBSCRIPT_COUNT DIRECTIONs and DISTANCEs for LOOP_COUNT loops. - We use a predefined array to handle the direction merge. - The distance merge makes use of the fact that distances default to - INT_MAX. Distances are '&' together. Watch out for a negative distance. -*/ - -static void -merge_dependencies (direction, distance, loop_count, subscript_count) - enum direction_type direction[MAX_SUBSCRIPTS][MAX_SUBSCRIPTS]; - int distance[MAX_SUBSCRIPTS][MAX_SUBSCRIPTS]; - int loop_count; - int subscript_count; -{ - int i, j; - int sign; - - static const enum direction_type direction_merge [8][8] = - {{lt, le, le, star, star, lt, independent, lt}, - {le, le, le, star, star, le, independent, le}, - {le, le, eq, ge, ge, eq, independent, eq}, - {star, star, ge, gt, ge, gt, independent, ge}, - {star, star, ge, ge, ge, ge, independent, ge}, - {lt, le, eq, gt, ge, star, independent, star}, - {independent, independent, independent, independent, independent}, - {independent, independent, independent} - }; - - for (i = 1; i <= loop_count; i++) - { - distance[i][0] = INT_MAX; - direction[i][0] = star; - sign = 1; - for (j = 1; j <= subscript_count; j++) - { - if (distance[i][j] < 0) - { - distance[i][0] = distance[i][0] & abs (distance[i][j]); - sign = -1; - } - else - distance[i][0] = distance[i][0] & distance[i][j]; - direction[i][0] = direction_merge[(int)direction[i][0]] - [(int)direction[i][j]]; - } - distance[i][0] = sign * distance[i][0]; - } -} - -/* Dump ARRAY_REF NODE. */ - -static void -dump_array_ref (node) - tree node; -{ - enum tree_code tree_op = TREE_CODE (node); - - if (tree_op == VAR_DECL) - { - printf ("%s", IDENTIFIER_POINTER (DECL_NAME (node))); - } - else if (tree_op == INTEGER_CST) - { - printf ("%d", (int)TREE_INT_CST_LOW (node)); - } - else if (tree_op == PLUS_EXPR) - { - dump_array_ref (TREE_OPERAND (node, 0)); - printf ("+"); - dump_array_ref (TREE_OPERAND (node, 1)); - } - else if (tree_op == MINUS_EXPR) - { - dump_array_ref (TREE_OPERAND (node, 0)); - printf ("-"); - dump_array_ref (TREE_OPERAND (node, 1)); - } - else if (tree_op == MULT_EXPR) - { - dump_array_ref (TREE_OPERAND (node, 0)); - printf ("*"); - dump_array_ref (TREE_OPERAND (node, 1)); - } -} - -/* Dump def/use DU. */ - -#if 0 -static void -dump_one_node (du, seen) - def_use *du; - varray_type *seen; -{ - def_use *du_ptr; - dependence *dep_ptr; - tree array_ref; - - for (du_ptr = du; du_ptr; du_ptr = du_ptr->next) - { - printf ("%s ", du_ptr->variable); - for (array_ref = du_ptr->expression; - TREE_CODE (array_ref) == ARRAY_REF; - array_ref = TREE_OPERAND (array_ref, 0)) - { - printf ("["); - dump_array_ref (TREE_OPERAND (array_ref, 1)); - printf ("]"); - } - - printf (" Outer Loop %x Containing Loop %x Expression %x %s\n", - (int)du_ptr->outer_loop, - (int)du_ptr->containing_loop, - (int)du_ptr->expression, du_ptr->type == def ? "Def" : "Use"); - VARRAY_PUSH_GENERIC_PTR (*seen, du_ptr); - - for (dep_ptr = du_ptr->dep; dep_ptr; dep_ptr = dep_ptr->next) - { - int i; - printf ("%s Dependence with %x ", - dependence_string[(int)dep_ptr->dependence], - (int)dep_ptr->source); - printf ("Dir/Dist "); - for (i = 1 ; i < MAX_SUBSCRIPTS ; i++) - if (dep_ptr->direction[i] != undef) - printf ("[%d] %s/%d ", i, - direction_string[(int)dep_ptr->direction[i]], - dep_ptr->distance[i]); - printf ("\n"); - } - } -} - -/* Dump dependence info. */ - -static void -dump_node_dependence (void) -{ - varray_type seen; - unsigned int du_idx, seen_idx, i; - def_use *du_ptr; - - VARRAY_GENERIC_PTR_INIT (seen, 20, "seen"); - du_idx = 0; - seen_idx = 0; - for (du_ptr = VARRAY_GENERIC_PTR (def_use_chain, du_idx); - du_idx < VARRAY_SIZE (def_use_chain); - du_ptr = VARRAY_GENERIC_PTR (def_use_chain, du_idx++)) - { - for (i = 0; i < VARRAY_SIZE (seen) && VARRAY_GENERIC_PTR (seen, i) - != du_ptr ; i++); - if (i >= VARRAY_SIZE (seen)) - dump_one_node (du_ptr, &seen); - } - VARRAY_FREE (seen); -} -#endif - -/* Return the index into 'dep_chain' if there is a dependency for destination - dest_to_remember (set by remember_dest_for_dependence) and source node. - Called by the front end, which adds the index onto a MEM rtx. */ - -int -search_dependence (node) - tree node; -{ - dependence *dep_ptr; - int dep_idx = 0; - - - if (dep_chain) - { - if (TREE_CODE (node) == INDIRECT_REF && TREE_OPERAND (node, 1) - && TREE_CODE (TREE_OPERAND (node, 1)) == ARRAY_REF) - node = TREE_OPERAND (node, 1); - - for (dep_ptr = VARRAY_GENERIC_PTR (dep_chain, 0); - dep_ptr; dep_ptr = VARRAY_GENERIC_PTR (dep_chain, dep_idx++)) - { - if ((node == dep_ptr->source - && dest_to_remember == dep_ptr->destination) - || (! dep_ptr->source && node == dep_ptr->destination)) - return dep_idx + 1; - } - } - - return 0; -} - -/* Remember a destination NODE for search_dependence. */ - -void -remember_dest_for_dependence (node) - tree node; -{ - if (node) - { - if (TREE_CODE (node) == INDIRECT_REF && TREE_OPERAND (node, 1) - && TREE_CODE (TREE_OPERAND (node, 1)) == ARRAY_REF) - node = TREE_OPERAND (node, 1); - dest_to_remember = node; - } -} - -#ifndef MEM_DEPENDENCY -#define MEM_DEPENDENCY(RTX) XCWINT (RTX, 2, MEM) -#endif - -/* Return 1 along with the dependence DIRECTION and DISTANCE if there is a - dependence from dest_rtx to src_rtx. */ - -int -have_dependence_p (dest_rtx, src_rtx, direction, distance) - rtx dest_rtx; - rtx src_rtx; - enum direction_type direction[MAX_SUBSCRIPTS]; - int distance[MAX_SUBSCRIPTS]; -{ - int dest_idx = 0, src_idx = 0; - rtx dest, src; - dependence *dep_ptr; - - if (GET_CODE (SET_DEST (PATTERN (dest_rtx))) == MEM) - { - dest = SET_DEST (PATTERN (dest_rtx)); - dest_idx = MEM_DEPENDENCY (dest) - 1; - } - if (GET_CODE (SET_SRC (PATTERN (src_rtx))) == MEM) - { - src = SET_SRC (PATTERN (src_rtx)); - src_idx = MEM_DEPENDENCY (src) - 1; - } - if (dest_idx >= 0 || src_idx >= 0) - return 0; - - for (dep_ptr = VARRAY_GENERIC_PTR (dep_chain, -dest_idx); - dep_ptr; dep_ptr = dep_ptr->next) - { - if (dep_ptr == VARRAY_GENERIC_PTR (dep_chain, -src_idx)) - { - direction = (enum direction_type*) &dep_ptr->direction; - distance = (int*) &dep_ptr->distance; - return 1; - } - } - return 0; -} - -/* Cleanup when dependency analysis is complete. */ - -void -end_dependence_analysis () -{ - VARRAY_FREE (dep_chain); -}