dvector.cc

c到DHL的转换工具

/* file "dvector.cc" */

/*  Copyright (c) 1994 Stanford University

    All rights reserved.

    This software is provided under the terms described in
    the "suif_copyright.h" include file. */

#include <suif_copyright.h>

//dvector.c
#define _MODULE_ "libdependence.a"
#pragma implementation "dvector.h"

#include <stdio.h>
#include <suif1.h>
#include <builder.h>
#include <suifmath.h>
#include "dependence.h"

//
// dvector.c
//
// routines to create a distance vector
// taking as input two array instructions
//

// a1 and a2 are two memory references which have the same base array
// --- possibly NULL or unknown
// if a1 and a2 are array accesses, generate the access vectors using
//	gcd
// if they are not, try to determine if they are independent, if not
//	dependence vector is (*)

//
// interface the access vectors to the gcd program and find
// the distance vector
//
int Gcd(coeff, coeff **);
//overload int is_good_symb(access_vector *av1,access_list *symbols);
access_list *unite_unequals(access_list *a1, access_list *a2);
//overload int inline is_good_symb(access_vector *av1);


dvlist::dvlist(array_info *a1, array_info *a2, 
         int minnest, int valid_dim, tn_list * al, int lexpos, int flow)
{
    dv_calc(a1,a2,minnest,valid_dim,al,flow);
    if(lexpos) make_lexpos();
}

distance_vector::distance_vector(array_info *a1, array_info *a2, 
	int minnest, int valid_dim, tn_list * al,int flow)
{
    dvlist *dvl=new dvlist(a1,a2,minnest,valid_dim,al,flow);
    dvl->collapse(this);
    delete dvl;
}

static int dim_is_ok(access_vector *a,tn_list *al)
{
    if(a->too_messy)
        return 0;
    alist_iter ai(&a->elts);
    while(!ai.is_empty()) {
        alist_e *ae = ai.step();
        if((int)ae->info != 0 && !al->lookup((tree_node *)ae->key))
            return 0;
    }
    return 1;
}

static int wierd_constant_fields_same(access_vector *av1,access_vector *av2)
{
    av_compare_info ans(av1,av2);
    return ans.same_paths() && ans.same_conregs() && ans.same_memregs();
}


void dvlist::clear()
{
    dvlist_iter iter(this);
    while(!iter.is_empty()) {
	dvlist_e * de = iter.step();
	if(de->dv) delete de->dv;
	remove(iter.cur_elem());
	delete de;
    }
    glist::clear();
}






dvlist::dvlist(array_info *a1, array_info *a2, tn_list *al,int lexpos, int flow)
{
    int valid_dim = 0;
    array_info *ai1 = new array_info;
    array_info *ai2 = new array_info;
    array_info_iter aii1(a1);
    array_info_iter aii2(a2);
    while(!aii1.is_empty()) {
        assert(!aii2.is_empty());
        access_vector *av1 = aii1.step();
        access_vector *av2 = aii2.step();
        if(dim_is_ok(av1,al) && dim_is_ok(av2,al)) {
//		   wierd_constant_fields_same(av1,av2)) {
            valid_dim++;
            ai1 -> append(new access_vector(av1));
            ai2 -> append(new access_vector(av2));
        }
    }
    dv_calc(ai1,ai2,al->count(),valid_dim,al,flow);
    if(lexpos) make_lexpos();
    delete ai1;
    delete ai2;
    
}


distance_vector::distance_vector(array_info *a1,array_info *a2,
			tn_list *al,int flow)
{
    int valid_dim = 0;
    array_info *ai1 = new array_info;
    array_info *ai2 = new array_info;
    array_info_iter aii1(a1);
    array_info_iter aii2(a2);
    while(!aii1.is_empty()) {
        assert(!aii2.is_empty());
        access_vector *av1 = aii1.step();
        access_vector *av2 = aii2.step();
        if(dim_is_ok(av1,al) && dim_is_ok(av2,al) &&
           wierd_constant_fields_same(av1,av2)) {
            valid_dim++;
            ai1 -> append(new access_vector(av1));
            ai2 -> append(new access_vector(av2));
        }
    }
    dvlist *dvl=new dvlist(ai1,ai2,al->count(),valid_dim,al,flow);
    dvl->collapse(this);
    delete ai1; delete ai2;
}

void dvlist::dv_calc(array_info *a1, array_info *a2, 
			int minnest, int valid_dim, tn_list * al,int flow)
{ 
//=    printf("a1:"); a1->print();
//=    printf("\na2:"); a2->print();
//=    printf("\nminnest=%d, valid_dim=%d, flow=%d\n", minnest, valid_dim, flow);
/*    assert(al);
    tn_list_iter titer(al);
    printf("[");
    while(!titer.is_empty()) {
        tree_node * tn = titer.step();
        assert(tn->is_for());
        printf("%s ", ((tree_for*)tn)->index());
    }
    printf("]\n"); */

    array_info_iter * a1i, *a2i;
    access_vector * av1, * av2;
    tn_list_iter * loops;
    tn_list_iter * loops2;
    dependency_test *dt=new dependency_test(); 
    set_dep();  // initialization
    int DD = 2*minnest;
    int *write_used = new int[minnest]; // which loops are used by
    // the write, assume a1 is 
    // the write
    
    valid_dim = elim_bad_symb(a1, a2); // dims with bad symbols
    if (!valid_dim && flow) {
        dir_array *da = new dir_array(minnest);
        int *is_used = new int[2*minnest];
        for (int i=0; i<minnest; i++) {
            da->data[i].set_direction(d_star);
            is_used[2*i] = 0;
            is_used[2*i+1] = 0;
        }
        dir_list *dl = new dir_list(da);
        dl->flow_reduce(is_used);
        dir_array *da2;
        while ((da2=dl->pop())) {
            distance_vector *dv2 = new distance_vector();
            for (int s=0; s<da2->size; s++) {
                distance dis=da2->data[s];
                dv2->append(dis);
            }
            push(new dvlist_e(dv2));
        }
        return;
    }
    
    
    access_list *symbols = find_symbs(a1,a2);
    int num_symb = symbols->count();
    DD += num_symb;
/*	
  printf("\nThe two references are \n");
  a1->print(stdout); printf("\n");
  a2->print(stdout); printf("\n");
  */
// find the bounds from al and shove into L and U
    integer_matrix *L = new integer_matrix();
    integer_matrix *U = new integer_matrix();
    boolean *lb_valid = new boolean[DD+1];  // does this bound exist
    boolean *ub_valid = new boolean[DD+1];
    void SetLU(tn_list *, int, integer_matrix *, integer_matrix * ,boolean * ,
               boolean *,access_list *,int,int flow=0);
    SetLU(al,DD,L,U,lb_valid,ub_valid,symbols,num_symb,flow);
    
// throw out constant dimensions
    a1i = new array_info_iter(a1);
    a2i = new array_info_iter(a2);
    
    int has_const_dim = 0;
    // throw out constant dimensions
    array_info *newa1 = new array_info();
    array_info *newa2 = new array_info();
    while(!a1i->is_empty()) {
        assert(!a2i->is_empty());
        av1=a1i->step();
        av2=a2i->step();
        av_compare_info avc(av1,av2);
        // will subracting the two will create a constant
        if (av1->elts.is_empty() && av2->elts.is_empty() &&
            avc.same_conregs() && avc.same_memregs() && 
            avc.same_paths()) {
            if (av1->con != av2->con) {
                if (minnest > 0) dt->const_test++;
                set_indep();
                //printf("It's independent \n");
                return;
            }
            has_const_dim = 1;
            valid_dim--;
        } else {
            newa1->append(av1);
            newa2->append(av2);
        }
    }
    delete a1i; delete a2i;
    a1->clear(); a2->clear();
    
    // degenerate case
    if (valid_dim == 0) {  // set all elements to star 
        if (has_const_dim && (minnest >0)) dt->const_test++;
        distance_vector *dv = new distance_vector();
        for (int i=0; i<minnest; i++) {    
            distance *d = new distance();
            distance_vector_e *temp = new distance_vector_e(*d);
            dv->push(temp);
        }
        push(new dvlist_e(dv));
//=        printf("The result is1 \n"); this->print(stdout); printf("\n");
        return;
    }
    
    a1i = new array_info_iter(newa1);
    a2i = new array_info_iter(newa2);
    
// check which induction variables are actually used and get a count
    int *loop_used = new int[2*minnest+num_symb];
    void SetLoopUsed(int *,int ,int,int *, int *, array_info_iter *,
                     array_info_iter*,tn_list *,integer_matrix *,
                     integer_matrix*,int,int *);
    SetLoopUsed(loop_used,minnest,valid_dim,lb_valid,ub_valid,
                a1i,a2i,al,L,U,num_symb,write_used);
    int loop1_num = 0;
    int loop2_num = 0;
    int i;
    for (i=2*(minnest-1); i>=0; i-=2) {
        if (loop_used[i+num_symb]) loop1_num++;
    }
    for (i=2*minnest-1; i>=0; i-=2) {
        if (loop_used[i+num_symb]) loop2_num++;
    }
    int num_used = loop1_num + loop2_num;	
    
    // throw out unused variables from write_used
    assert(num_used%2 == 0);
    int i2=0;
    for (i=0; i<num_used/2; i++) {
        if (loop_used[2*i+num_symb] || loop_used[2*i+num_symb+1]) {
            write_used[i2++] = write_used[i];
        }
    }
//=    printf("L:\n");L->print();
//=    printf("U:\n");U->print();
//=    for(int x=0; x<DD+1; x++)
//=        printf("(%d %d)", lb_valid[x], ub_valid[x]);
// put equations into a coeff A
    coeff A;
    coeff *X=new coeff;
    int total_vars = 2*minnest+num_symb;
    X->vars = new int[total_vars*total_vars];
    X->constant = new int[total_vars];
    A.n = num_used+num_symb;
    A.m = valid_dim;
    A.vars = new int[A.n*A.m];
    A.constant = new int[valid_dim];
    
/* now set the A matrix, eliminating unused variables */
    a1i = new array_info_iter(newa1);
    a2i = new array_info_iter(newa2);
    for (i=0; i<valid_dim; i++) {
        av1 = a1i -> step();
        av2 = a2i -> step();
	assert(av1 && av2);
        loops = new tn_list_iter(al);
        loops2 = new tn_list_iter(al);
        int k=2*minnest-1;
	int j;
        for (j=num_used-1; j>=0; j--) {
            int j2 = j+num_symb;
            while(!loop_used[k+num_symb]) {
                if ((k %2) ==0) av1->val(loops->step());
                else av2->val(loops2->step());
                k--;
            }
            if ((k % 2) == 0)  {
                A.vars[j2*valid_dim+i] = av1->val(loops -> step());
            } else {
                A.vars[j2*valid_dim+i] = -av2->val(loops2 -> step());
            }
            k--;
//=            printf("%d %d %d---\n", i, j, k); A.print();
        }
        delete loops; delete loops2;
        A.constant[i] = av1->con - av2->con;
        
        // add in symbolic components
        access_list_iter temp_symb(symbols);
        for (j=num_symb-1; j>=0; j--) {
            assert(!temp_symb.is_empty());
            access_list_e *e = temp_symb.step();
            A.vars[j*valid_dim+i] = av1->conregs.val(e->var())-
                av2->conregs.val(e->var());
//=            printf("%d %d ---\n", i, j); A.print();
        }
    }
    
    //eliminate unused variables for L and U
    int olddd = DD;
    DD = num_used+num_symb;
    int numlow = 0; // number of lower bounds
    int numup = 0;
    for (i=1; i<=olddd; i++) {
        if (loop_used[i-1]) {
            numlow += lb_valid[i];
            numup += ub_valid[i];
        }
    }
    integer_matrix *L2 = new integer_matrix();
    integer_matrix *U2 = new integer_matrix();
    L2->init(num_symb+numlow+1,DD+1);
    U2->init(num_symb+numup+1,DD+1);
    int oldlow,oldup,newlow,newup;
//=    printf("L:\n");L->print();
//=    printf("U:\n");U->print();
    oldlow = oldup = newlow = newup = 1;
    i2 = 1;
    for (i=1; i<=olddd; i++) {
        if (loop_used[i-1]) {
            lb_valid[i2] = lb_valid[i]; ub_valid[i2] = ub_valid[i];
	    int a;
            for (a=1; a<= lb_valid[i]; a++, oldlow++, newlow++) {
                (*L2)[newlow][0] = (*L)[oldlow][0]; 
                int j2=1;
		int j;
                for (j=1; j<i; j++) {
                    if (loop_used[j-1]) {
                        (*L2)[newlow][j2] = (*L)[oldlow][j];
                        j2++;
                    }
                }
            }
            for (a=1; a<= ub_valid[i]; a++, oldup++, newup++) {
                (*U2)[newup][0] = (*U)[oldup][0]; 
                int j2=1;
		int j;
                for (j=1; j<i; j++) {
                    if (loop_used[j-1]) {
                        (*U2)[newup][j2] = (*U)[oldup][j];
                        j2++;
                    }
                }
            }
            i2++;
        } else {	
            oldlow += lb_valid[i];
            oldup += ub_valid[i];
        }
    }
    delete L; delete U;
    L = L2; U = U2;
//=    printf("L:\n");L->print();
//=    printf("U:\n");U->print();
//=    A.print();
    
    // check degenerate cases
    if (minnest == 0) { // if all constants equal then set to star
        // else set to independent
        for (i=0; i<valid_dim; i++) {
            if (A.constant[i] != 0) {
                set_indep();
                break;
            } 
        }
	// do Gcd
    } else if (Gcd(A,&X)) {
        distance_vector *dv = new distance_vector();
        for (i=num_used/2-1; i >= 0; i--) { // once for each d_vec dim
            int i2 = 2*i+num_symb;
            int done = FALSE;
            distance *d = NULL;
            for (int j=0; j<X->n && !done; j++) {
                if (X->vars[j*X->m+i2] != 
                    X->vars[j*X->m+i2+1]) {
// non constant distance vector
                    d = new distance(); // star
                    done = TRUE;
                }
            }
            
            if (!done) {
                int c=X->constant[i2+1]-X->constant[i2];
                d = new distance(-c);
            }
            distance_vector_e *temp = new distance_vector_e(*d);
            dv->push(temp);
        }
        
        if (dt->exact()) {
// convert from coefficient structure to integer_matrix needed by exact
            integer_matrix S;
            S.init(DD+1,DD+1);
            for (int l=0; l<X->m; l++) {
                assert(l+1 < (DD+1));
                S[l+1][0] = X->constant[l];
                for (int m=0; m<X->n; m++) {
                    assert((m+1) < (DD+1));
                    S[l+1][m+1]=X->vars[m*X->m + l];
                }
            }
// convert direction vector to dir_array needed by exact
            dir_array *da = new dir_array(num_used/2);
            boolean *const_dist = new boolean[num_used/2];
            distance_vector_iter di(dv);
            for (i=0; i<num_used/2; i++) {
                distance d;
                d = di.step()->d;
                da->data[i].set_direction(d.dir());
                const_dist[i] = d.is_const();
            }
            
            exact *ex = new exact(&S,DD,da,const_dist,L,U,
                                  lb_valid,ub_valid,num_symb,flow,write_used);
            if (ex->is_indep()) {