Go to the previous section.

Detailed Description

fill_in_access(tree_proc * tp): annotates code in the given tree_proc with dep_instr_annote and dep_for_annote. These annotations store information needed by the dependence analyzer. fill_in_access must be run before any calls to DependenceTest.

enum deptest_result {dt_none, dt_ok, dt_indep, dt_no_common_nest, dt_too_messy}: When DependenceTest is called with a deptest_result pointer, the pointer will be assigned one of these five values. dt_none indicates that no dependence test was run. dt_ok means that the two array accesses are data dependent, and the corresponding dependence vectors are returned by DependenceTest. Returning dt_indep conveys that the two array accesses are independent, and returning dt_no_common_nest indicates the accesses have no common enclosing loop. Lastly, dt_too_messy suggests that the array access function was too messy, thus beyond the scope of the dependence analyzer.

dvlist * DependenceTest(in_array *w, in_array *r, int lexpos, deptest_result * res): Function DependenceTest tests whether the two array accesses (*w & *r) are data dependent. In particular, it tests whether *w is data dependent on *r. If *w is indeed dependent on *r, dt_ok would be assigned to *res. Otherwise, *res would be given a value other than dt_ok. See above for other deptest_result values. When the two accesses are data dependent, DependenceTest returns a list of dependence vectors. If lexpos is set, the list of dependence vectors would only contain lexicographically positive dependence vectors.

dvlist * DependenceTest(in_array *w, in_array *r, deptest_result * res): Calling this function is equivalent to calling DependenceTest(in_array *w, in_array *r, int lexpos, deptest_result * res) with lexpos = 1.

dvlist * DependenceTest(in_array *w, in_array *r, int lexpos): Calling this function is the same as calling DependenceTest(in_array *w, in_array *r, int lexpos, deptest_result * res) except no deptest_result is returned through the deptest_result pointer.

dvlist * DependenceTest(in_array *w, in_array *r): Calling this function is equivalent to calling DependenceTest(in_array *w, in_array *r, int lexpos) with lexpos = 1.

void print_array_access(in_array * in, FILE * fs = stdout): print the array access *in to file *fs.

class dvlist
    int indep();
    dvlist_e *pop();
    void print(FILE *);

A dvlist is used to store a list of dependence vectors. Method indep returns TRUE only if the corresponding array accesses are independent. Method pop returns the first element of the list of dependence vectors as a dvlist_e. Lastly, the print method is provided for class dvlist for outputing the list to a file.

class dvlist_iter
	dvlist_iter(dvlist *dv);
	dvlist_e *step();
	int is_empty()

A dvlist_iter is an iterator for class dvlist. Once an iterator is created for a specific dvlist *dv (using dvlist_iter(dv)), the methods step, next, is_empty, etc. can be used to look at the elements of the list (also see documentation for glist_iter in the SUIF Library Reference Manual).

class dvlist_e
    distance_vector * dv;

Each element of a dvlist is a dvlist_e, and a dvlist_e simply contains a dependence vector represented by the class distance_vector.

class distance_vector
    distance_vector_e *pop()
    indep();
    void print(FILE *);
    is_empty()
    int is_zero();			/* is the vector 0? */
    int is_pos();			/* is first entry positive? */
    int is_neg();			/*                negative? */
    int is_star();			/*                star? */ 
    int level();			/* what is the level of this dep? */
    int size();			/* how big is the dvector? */
    distance *thresh(int level);     /* what is the threshold? must be # */
    void negate();			/* negate all of the distances */
    int first_not_eq();		/* level of the first non-= or * */
    /*   if all =, returns 0 */
    int operator==(distance_vector &); /* if two vectors identical */
    int operator!=(distance_vector &d);

A dependence vector is represented by class distance_vector which is a list of distance_vector_e. The length of the vector can be obtained by calling the method size. The elements of the list can be extracted from the list using the pop method, and the is_empty method tests whether all the elements have been removed. Of course, one can also instantiate an iterator for looking at the list. Some other useful methods are: indep returns TRUE if the corresponding array accesses are independent, level returns the dependence level, first_not_eq returns the level of the first non-zero component, negate simply reverses the sign of all the components, and print outputs the dependence vector to a file. Operators == and != are provided for comparing dependence vectors, and methods is_zero, is_pos, is_neg, is_star respectively test whether the distance_vector is a zero vector, a lexicographically positive vector, a lexicographically negative vector, or a vector with the star direction as its first entry.

class distance_vector_e
    distance d;
    int is_zero();
};

Each element of a distance_vector is a distance_vector_e, and a distance_vector_e contains a distance, a component of a dependence vector. A method is_zero is provided to test whether the distance is zero.

enum direction {d_lt=1,d_gt=2,d_eq=4,d_le=5,d_ge=6,d_lg=3,d_star=7};

Each component of a dependence vector can be summarized by one of seven directions. d_lt represents <, d_gt represents >, d_eq represents =, d_le represents <=, d_ge represents >=, d_lg represents <> and d_star represents *.

class distance 
    int is_const();
    int dist();
    direction dir();
    int is_star();
    int has_eq();
    void print(FILE *);
    int is_zero();
    void negate();			/* negate the distance */
    int operator ==(distance &d)
    int operator !=(distance &d)

Each component of a dependence vector (represented by class distance_vector) is a distance. An object of type distance contains a direction, and can be obtained by calling the method dir. In addition, if a numeric value is known, the object also stores the integer value. If an object of type distance contains an integer value, a call to is_const would return TRUE and a call to method dist would return the integer value. Similarly, methods is_zero and is_star test whether an object is respectively the direction d_eq and the direction d_star. Method has_eq returns TRUE if the object contains a direction including d_eq, i.e. d_eq, d_le, d_ge and d_star. Furthermore, a few helpful mthods are provided for class distance. For example, operators == and != are provided to compare objects of type distance. The method negate is provided to negate a distance and method print to output the distance to a file.

Go to the previous section.