dvector.cc

c到DHL的转换工具

        }
    }
}




// check which loop variables are actually used by array statements
/* a variable is unused if it and its prime is not used either in the */
/* expression nor in a triangular loop */
// also check which write variables are used, assume a1 is the write 
void SetLoopUsed(int *loop_used,int minnest,int valid_dim, int *lb_valid, 
		 int *ub_valid, array_info_iter *a1i, array_info_iter *a2i, 
		 tn_list *al,integer_matrix *L, integer_matrix *U,int num_symb,
		 int *write_used) 
{
    access_vector *av1, *av2;
    int n=num_symb;
    
    int j;
    for (j=0; j<2*minnest; j++) loop_used[j+num_symb]=0;
    for (j=0; j<num_symb; j++) loop_used[j] = 1;
    for (j=0; j<minnest; j++) write_used[j] = 0;
    for (int i=0; i<valid_dim; i++) {
        av1 = a1i -> step();
        av2 = a2i -> step();
	assert(av1 && av2);
        tn_list_iter *loops = new tn_list_iter(al);
        for (j=2*(minnest-1); j>=0; j-=2) {
            if (av1->val(loops->step()) != 0) {
                loop_used[j+n]=1;
                write_used[j/2]=1;
            }
        }
        loops = new tn_list_iter(al);
        for (j=(2*minnest)-1; j>=0; j-=2) {
            if (av2->val(loops->step()) != 0) loop_used[j+n]=1;
        }
        delete loops;
    }
    
    // check unused ones in case they're used in triangular loops
    for (j=1; j<=2*minnest; j++) {
        if (!loop_used[j-1+n]) {
            int ltotal = 1;
            int utotal = 1;
            for (int i=1; i<=2*minnest; i++) {
                int lbounds = lb_valid[i+n];
		int k;
                for (k=ltotal; k<ltotal+lbounds; k++) {	
                    if (lb_valid[i+n] && (*L)[k][j+n]) {
                        loop_used[j-1+n] = 1;
                        write_used[(j-1)/2] = 1;
                    }
                } 
                ltotal += lbounds;
                
                int ubounds = ub_valid[i+n];
                for (k=utotal; k<utotal+ubounds; k++) {	
                    if (ub_valid[i+n] && (*U)[k][j+n]) {
                        loop_used[j-1+n] = 1;
                        write_used[(j-1)/2] = 1;
                    }
                } 
                utotal += ubounds;
            }
        }
    }
    
// check if pair of unused is used
    for (j=0; j<2*minnest; j+=2) {
        if (loop_used[j+n]) loop_used[j+1+n] =1;
        if (loop_used[j+1+n]) loop_used[j+n] =1;
    }
}



//
// use the tree_node_list and symbols to set a matrix of lower and upper bounds
// symbolic variables are placed first
//
void SetLU(tn_list *al, int DD, integer_matrix *L, integer_matrix *U, 
	    boolean *lb_valid,
	    boolean *ub_valid, access_list *symbols, int num_symb,
	    int flow=0)
{
    int is_good_symb(access_vector *,access_list *);
    int low_bounds = 0;
    int up_bounds = 0;
    // init lb_valid and ub_valid
    int i;
    for (i=0; i<=DD; i++) {
        lb_valid[i] = ub_valid[i] = 0;
    }
    
    // find out how many bounds there are
    tn_list_iter *loops = new tn_list_iter(al);
    for (i= DD; i>= 1+num_symb; i-=2) {	// for each loop
        tree_node *induct = loops->step();
        assert(induct->kind() == TREE_FOR);
        dep_for_annote * df = (dep_for_annote *)induct->peek_annote(k_dep_for_annote);
        assert(df);
        
        if (flow) assert(df->lb->count() <= 1);
        array_info_iter ai(df->lb);
        while (!ai.is_empty()) { // for each bound
            access_vector *lb = ai.step();
            if (is_good_symb(lb,symbols)) {
                low_bounds += 2;
                lb_valid[i]++;
                lb_valid[i-1]++;
                
            }
            
        }
        
        if (flow) assert(df->ub->count() <= 1);
        array_info_iter ai2(df->ub);
        while (!ai2.is_empty()) { // for each bound
            access_vector *ub = ai2.step();
            if (is_good_symb(ub,symbols)) {
                up_bounds += 2;
                ub_valid[i]++;
                ub_valid[i-1]++;
            }
        }
    }
    L->init(low_bounds+1,DD+1);
    U->init(up_bounds+1,DD+1);
    
    // set bounds of induction variables
    delete loops;
    loops = new tn_list_iter(al);
    int uconstr = up_bounds;
    int lconstr = low_bounds;
    for (i = DD; i>=1+num_symb; i-=2) {  // for each loop
        tree_node *induct = loops->step();
        dep_for_annote * df = (dep_for_annote *)induct->peek_annote(k_dep_for_annote);
        assert(df);
        
        array_info_iter ai(df->lb);
        int count = 0;
        
        while (!ai.is_empty()) {
            access_vector *lb = ai.step(); 
            if (is_good_symb(lb,symbols)) { 
                count ++;
                (*L)[lconstr][0] = lb->con;
                (*L)[lconstr-lb_valid[i]][0] = lb->con;
                tn_list_iter temp(al);
                temp.set(loops->glist_iter::peek());
		int j;
                for (j=i-2;j>=1+num_symb;j-=2) {  
                    // for each induct element
                    assert(!temp.is_empty());
                    tree_node *element = temp.step();
                    (*L)[lconstr][j] = 
                        (*L)[lconstr-lb_valid[i]][j-1]
                        = lb->val(element);
                }
                
                access_list_iter temp_symb(symbols);
                for (j=num_symb; j>=1; j--) {
                    assert(!temp_symb.is_empty());
                    access_list_e *e = temp_symb.step();
                    (*L)[lconstr][j] = 
                        (*L)[lconstr-lb_valid[i]][j] =
                        lb->conregs.val(e->var());
                }
                lconstr --;
            }
        }
        
        assert(count == lb_valid[i]);
        lconstr -= lb_valid[i];
        array_info_iter ai2(df->ub);
        count = 0;
        while (!ai2.is_empty()) {
            access_vector *ub = ai2.step(); 
            if (is_good_symb(ub,symbols)) { 
                count ++;
                (*U)[uconstr][0] = ub->con;
                (*U)[uconstr-ub_valid[i]][0] = ub->con;
                tn_list_iter temp(al);
                temp.set(loops->glist_iter::peek());
		int j;
                for (j=i-2;j>=1+num_symb;j-=2) {  
                    assert(!temp.is_empty());
                    tree_node *element = temp.step();
                    (*U)[uconstr][j] = 
                        (*U)[uconstr-ub_valid[i]][j-1]= 
                        ub->val(element);
                }
                
                access_list_iter temp_symb(symbols);
                for (j=num_symb; j>=1; j--) {
                    assert(!temp_symb.is_empty());
                    access_list_e *e = temp_symb.step();
                    (*U)[uconstr][j] =  
                        (*U)[uconstr-ub_valid[i]][j] =
                        ub->conregs.val(e->var());
                }
                uconstr -= 1;
            }
        }
        assert(count == ub_valid[i]);
        uconstr -= ub_valid[i];
    }
    delete loops;
}



// use the bit vector used to add unused components back into dvector
// if not flow any unused component is a star
void distance_vector::add_unused(boolean *used, int n)
{
    if (indep()) return;
    for (int i=0; i<n; i+=2) {
        if (!used[i]) {
	    distance d;
            assert(!used[i+1]);
            this->append(d);
        } else {
            this->append(this->pop()->d);
        }
    }
    
}

// use the bit vector used to add unused components back into dir_array
// any unused component is a star
void dir_list::add_unused(boolean *used, int n)
{
    assert(n%2==0);
    dir_list *temp = this;
    while (temp) {
        dir_array *dir = temp->data;
        distance *new_data = new distance[n/2];
        int i2=0;
        for (int i=0; i<n; i+=2) {
            if (!used[i]) {
                assert(!used[i+1]);
                new_data[i/2].set_direction(d_star);
            } else {
                new_data[i/2] = dir->data[i2];
                i2++;
            }
        }
        delete[] dir->data;
        dir->data = new_data;
        dir->size = n/2;
        
        temp = temp->next;
    }
}


		

// is this access vector good
// it's bad if memregs or conpaths or mod_this is not nil
inline int is_good_symb(access_vector *av1)
{
    return (!av1->too_messy && av1->memregs.is_empty() && 
            !av1->mod_this);
}

// same as above but can only refer to symbols on list
int is_good_symb(access_vector *av1,access_list *symbols)
{
    if (!is_good_symb(av1)) {
        return 0;
    }
    access_list *temp = new access_list;
    temp->unite(symbols,&av1->conregs);
    int answer = (temp->count() == symbols->count()); 
    delete temp;
    return answer;
}

// eliminate dimensions which have anything but conregs and induct vars
// and where mod_this is not nil
// return the number of valid dims
int dvlist::elim_bad_symb(array_info *a1, array_info *a2)
{
    array_info_iter ai1(a1);	
    array_info_iter ai2(a2);	
    array_info newa1;
    array_info newa2;
    
    int valid_dim = 0;
    while (!ai1.is_empty() && !ai2.is_empty()) {
        access_vector *av1 = ai1.step();
        access_vector *av2 = ai2.step();
        
        if(is_good_symb(av1) && is_good_symb(av2)) {
            valid_dim++;
            newa1.append(new access_vector(av1));
            newa2.append(new access_vector(av2));
        }
    }
    a1->clear(); a1->glist::append(&newa1);
    a2->clear(); a2->glist::append(&newa2);
    newa1.clear(); newa2.clear();
    return valid_dim;
}

// return a list of all symbols used in the array_info
// only looks at conregs
access_list *dvlist::find_symb(array_info *a)
{
    access_list *al = new access_list();
    array_info_iter *ai = new array_info_iter(a);
    while (!ai->is_empty()) {
        access_vector *av = ai->step();
        al->unite(&av->conregs);
    }
    return al;
}

// return a list of all symbols used in either array_info
// disregard case where for the same dimension, both
// sybols have the same value (ie a[n] vrs a[n])
// only looks at conregs
access_list *dvlist::find_symbs(array_info *a1, array_info *a2)
{
    access_list *al = new access_list();
    array_info_iter ai1(a1);
    array_info_iter ai2(a2);
    while(!ai1.is_empty()) {
        assert(!ai2.is_empty());
        access_list *temp = unite_unequals(&ai1.step()->conregs,&ai2.step()->conregs);
                                           
        al->unite(temp);
        delete temp;
    }
    assert(ai2.is_empty());
    return al;
}



// return the union of two access_lists throwing out elements with the
// same value
access_list *unite_unequals(access_list *a1, access_list *a2)
{
    access_list *result = new access_list();
    
    access_list_iter ai(a1);
    while (!ai.is_empty()) {
        access_list_e *e = ai.step();
        access_list_e *e2 = a2->search(e->var());
        if (!e2 || (e2->val() != e->val())) {
            result->enter(e->var(),e->val());
        }
    }
    
    access_list_iter ai2(a2);
    while (!ai2.is_empty()) {
        access_list_e *e = ai2.step();
        access_list_e *e2 = a1->search(e->var());
        if (!e2 || (e2->val() != e->val())) {
            result->enter(e->var(),e->val());
        }
    }
    return result;
}

int distance_vector::operator==(distance_vector &d)
{
    distance_vector_iter ti(this),di(&d);
    while(!ti.is_empty() && !di.is_empty()) {
        if(ti.step()->d != di.step()->d)
            return 0;
    }
    return ti.is_empty() && di.is_empty();
}

static void insert_dvector(dvlist *l,distance_vector *d)
{
    // don't insert any duplicates ... pretty dumb
    dvlist_iter di(l);
    while(!di.is_empty()) {
        if(*di.step()->dv == *d) {
            delete d;
            return;
        }
    }
    l->append(new dvlist_e(d));
}

static void lexpos_decomp(dvlist *l, distance_vector *d,
			  boolean strict_pos=FALSE)
{
    assert(d->ind == 0);
    distance_vector_iter di(d);
    
    for(int i=1; !di.is_empty(); i++) {
        distance_vector_e *dd = di.step();
        switch(dd->d.dir()) {
        case d_lt:
            insert_dvector(l,d);
            return;
        case d_gt:
            delete d;
            return;
        case d_eq:
            break;
        case d_le:
        case d_star: {
            distance_vector *copy1 = new distance_vector(d);
            dd->d.set_direction(d_eq);
            distance ddd;
            ddd.set_direction(d_lt);
            copy1->set_entry(ddd,i);
            insert_dvector(l,copy1);
        }
            break;
        case d_ge:
            dd->d.set_direction(d_eq);
            break;
        case d_lg:
            dd->d.set_direction(d_lt);
            insert_dvector(l,d);
            return;
        default:
            assert(0);
        }
    }
    
    // if strictly lex. positive, DO NOT include loop independent dependences
    if (!strict_pos)
	insert_dvector(l,d); 
    else delete d; 
}

void dvlist::make_lexpos(boolean strict_pos)
{
    // make a list of dependence vectors all lexicographically positive.
    // actually, makes it lexpos or zero, unless strict_pos is set to TRUE.  
    // Those who wish can remove blatantly redundant entries from list.
    
    glist l;
    while(!is_empty())
        l.append(pop());
    
    while(!l.is_empty()) {
        dvlist_e *de = (dvlist_e *)l.pop();
        lexpos_decomp(this,de->dv,strict_pos);
        de->dv = 0;
        delete de;
    }
}