named_lin_ineq.cc

c到DHL的转换工具

    lin_ineq involved = ineqs().filter_thru(elim,0);
    if (involved.m() > 0) {
	ineqs().do_filter_away(elim,0);
	if (debug_suifmath_project) {
	    fprintf(stderr,"for_project: filtering away, elim:\n");
	    elim.print(stderr);
	    fprintf(stderr,"uninvolved:\n");
	    ineqs().print(stderr);
	    fprintf(stderr,"involved:\n");
	    involved.print(stderr);
	}
	lin_ineq *projeq = 
	     fast_fourier_motzkin(involved, &elim, (use_alt_project > 1));
	if (debug_suifmath_project) {
	    fprintf(stderr,"after projection:\n");
	    projeq->print(stderr);
	}
	if (use_alt_project > 0) {
	    del_unit_stride_rows(*projeq, elim);
	    if (debug_suifmath_project) {
		fprintf(stderr,"after unit rows deleted:\n");
		projeq->print(stderr);
	    }
	    constraint noelim(n());
	    noelim = 1;
	    noelim -= elim;
	    noelim[0] = 0;
	    projeq->do_filter_thru(noelim,0);
	} else {
	    projeq->do_filter_away(elim,0);
	}
	if (debug_suifmath_project) {
	    fprintf(stderr,"after uninteresting rows deleted:\n");
	    projeq->print(stderr);
	}
	ineqs() &= *projeq;
	if (debug_suifmath_project) {
	    fprintf(stderr,"replacing uninvolved rows:\n");
	    ineqs().print(stderr);
	}
	delete projeq; projeq = 0;
	for (i=0; i<n(); i++) {
	    if (elim[i])
		names()[i].mark_aux();
	}
	if (debug_suifmath_project) {
	    fprintf(stderr,"before cleanup:\n");
	    print(stderr);
	}
    }
    
    ineqs().sort();
    ineqs().del_repetition();
    ineqs().del_loose();
    cleanup();
    return;
}

boolean named_lin_ineq::operator~() const
{
    return ~const_ineqs();
}

/***************************************************************************
 *                                                                         *
 ***************************************************************************/
void named_lin_ineq::print(FILE *fp) const
{
//    fprintf(fp, "       ");
//    for(int i=1; i<names().n(); i++) {
//        fprintf(fp, "%6s",
//                (names()[i].map())?names()[i].map()->name():"       ");
//        fprintf(fp, "%s", (names()[i].kind() == nte_loop)?".":" ");
//    }
//    for(; i<9; i++) fprintf(fp, "       ");
//    fprintf(fp, "%3d %s  <%X>\n", uid(), (is_killed()?"XXX":"   "),
//            get_home());

    fprintf(fp, "[%6d] ", unum);
    int i;
    for(i=1; i<const_names().n(); i++)
        fprintf(fp, "%7s",
                (const_names().e(i).string())?const_names().e(i).string():
                "<aux>");
    fprintf(fp, "     [ ");
    for(i=1; i<const_names().n(); i++) {
      char c = '.';
      switch(const_names().e(i).kind()) {
      case nte_none:       c = '?'; break;
      case nte_symconst:   c = 's'; break;
      case nte_cond:       c = 'c'; break;
      case nte_loop:       c = 'l'; break;
      case nte_dim:        c = 'd'; break;
      case nte_summary:    c = 'y'; break;
      case nte_aux:        c = 'a'; break;
      }
      fprintf(fp,"%c", c);
    }
    fprintf(fp, "]\n");
    const_ineqs().print(fp);
    fprintf(fp, "\n");
}

void named_lin_ineq::print_exp(print_exp_type type, FILE *fp) const
{
    if(type == pet_single) assert(const_ineqs().m() == 1);

    for(int x=0; x<const_ineqs().m(); x++) {
        switch(type) {
        case pet_system_nl:
            break;
        case pet_system:
            if(const_ineqs().m() > 1)
                fprintf(fp, "(");
            break;
        case pet_min:
        case pet_max:
            if((const_ineqs().m() > 1) && (x==0))
                fprintf(fp, "%s(", (type==pet_min)?"MIN":"MAX");
            break;
        default:
            break;
        }

        int pr = 0;
        integer_row R = const_ineqs().r(x);
        if(R[0]) {
            fprintf(fp, "%d ", R[0]);
            pr = 1;
        }

        for(int i=1; i<n(); i++)
            if(R[i]) {
                if(R[i] == 1) {
                    if(pr)
                        fprintf(fp, "+ ");
                } else if(R[i] == -1) {
                    if(pr)
                        fprintf(fp, "- ");
                    else
                        fprintf(fp, "-");
                } else if(R[i] > 0) {
                    if(pr)
                        fprintf(fp, "+ %d", R[i]);
                    else
                        fprintf(fp, "%d", R[i]);
                } else {
                    if(pr)
                        fprintf(fp, "- %d", -R[i]);
                    else
                        fprintf(fp, "%d", R[i]);
                }
                fprintf(fp, "%s ", const_names().e(i).string());
                pr = 1;
            }
        if(pr==0) fprintf(fp, "0 ");
        switch(type) {
        case pet_system:
            fprintf(fp, ">= 0");
            if(const_ineqs().m() > 1) fprintf(fp, ")");
            if(x < const_ineqs().m()-1)
                fprintf(fp, "&&");
            break;
        case pet_system_nl:
            fprintf(fp, ">= 0\n");
            break;
        case pet_min:
        case pet_max:
            if(x < const_ineqs().m()-1)
                fprintf(fp, ", ");
            if((const_ineqs().m() >1)&&(x == const_ineqs().m()-1))
                fprintf(fp, ")");
            break;
        default:
            break;
        }
    }
}


instruction * named_lin_ineq::mk_bounds() const
{
    block bnf(0);
    constraint filter(n());
    filter = 0;
    int i;
    for(i=1; i<n(); i++)
        if(const_names().e(i).kind() == nte_aux)
            filter[i] = 1;
    lin_ineq Laux    = const_ineqs().filter_thru(filter, -1);
            // only A - aux >= 0
    lin_ineq Lbounds = const_ineqs().filter_away(filter, 0);

    boolean first = TRUE;

    for(i=0; i<Lbounds.m(); i++) {
        block stmt(Lbounds[i][0]);
        for(int j=1; j<n(); j++)
            if(const_names().e(j).kind() != nte_aux) {
                int val = Lbounds[i][j];
                block sym((var_sym *)const_names().e(j).name().symbol());
                if(val == 1)
                    stmt.set(stmt + sym);
                else if(val == -1)
                    stmt.set(stmt - sym);
                else if(val != 0)
                    stmt.set(stmt + block(val)*sym);
            }
        if(first) {
            bnf.set(stmt >= block(0));
            first = FALSE;
        } else
            bnf.set(bnf & (stmt >= block(0)));
    }

    for(i=0; i<Laux.m(); i++) {
        block stmt(Laux[i][0]);
        int done = FALSE;
        for(int j=1; (j<n())&&(!done); j++) {
            int val = Laux[i][j];
            if(const_names().e(j).kind() != nte_aux) {
                block sym((var_sym *)const_names().e(j).name().symbol());
                if(val == 1)
                    stmt.set(stmt + sym);
                else if(val == -1)
                    stmt.set(stmt - sym);
                else if(val != 0)
                    stmt.set(stmt + block(val)*sym);
            } else if(val) {
                done = TRUE;
                if(first) {
                    bnf.set((stmt % block(-val)) == block(0));
                    first = FALSE;
                } else
                    bnf.set(bnf & ((stmt % block(-val)) == block(0)));
            }
        }
    }

    base_symtab * bs = const_names().get_symtab();
//    bnf.print();
    instruction * ins = bs ? bnf.make_instruction((block_symtab *)bs) : 0;
    return ins;
}


instruction * named_lin_ineq::create_expression(const immed & v,
                                                boolean is_ub,
                                                block_symtab * sym) const
{
    assert(const_ineqs().m() > 0);
    int pos = find(v);
    assert(pos > 0);

    if(!sym)
        sym = (block_symtab *)const_names().get_symtab();
    if(!sym)
	return 0;

    constraint filter(n());
    filter = 0;
    filter[pos] = 1;
    lin_ineq L = const_ineqs().filter_thru(filter, (is_ub)?-1:1);
    if(!is_ub) L *= -1;

    block exp;
    for(int i=0; i<L.m(); i++) {
        block curr(L[i][0]);
        int val = -1*L[i][pos];
        L[i][pos] = 0;
        for(int j=1; j<n(); j++)
            if(const_names().e(j).name().is_symbol() ||
               const_names().e(j).name().is_string()) {
                block var((var_sym *)const_names().e(j).name().symbol());
                if(L[i][j] == 1)
                    curr.set(curr + var);
                else if(L[i][j] == -1)
                    curr.set(curr - var);
                else if(L[i][j] != 0)
                    curr.set(curr + block(L[i][j])*var);
            }
        if(val != 1)
            curr.set(block::op(curr,
                               (is_ub)?bop_divfloor:bop_divceil,
                               block(val)));
        if(i==0)
            exp.set(curr);
        else
            exp.set(block::op(exp, (is_ub)?bop_min:bop_max, curr));
    }
    instruction * ret = exp.make_instruction(sym);
    return ret;
}



/***************************************************************************
 *                                                                         *
 ***************************************************************************/
boolean named_lin_ineq::is_aligned(const named_lin_ineq & A,
                                   const named_lin_ineq & B)
{
    const name_table & na = A.const_names();
    const name_table & nb = B.const_names();

    return name_table::is_aligned(na, nb);
}


/***************************************************************************
 *                                                                         *
 ***************************************************************************/
void named_lin_ineq::align(const name_table & ant)
{
    if(name_table::is_aligned(ant, names())) return;

    named_lin_ineq tmp(this);
    integer_row rmap(n());
    rmap[0] = 0;
    int i;
    for(i=1; i<n(); i++) {
        assert_msg(names()[i].kind() != nte_aux,
                   ("Handling aux. vars. is not implemented"));
        int x = ant.find(names()[i]);
        assert_msg(x > 0, ("The variable %s is not in align name table",
                           names()[i].string()));
        rmap[i] = x;
    }

    names().init(ant);
    ineqs().init(m(), ant.n());

    for(i=0; i<m(); i++)
        for(int j=0; j<tmp.n(); j++)
            ineqs()[i][rmap[j]] = tmp.ineqs()[i][j];
}


/***************************************************************************
 *                                                                         *
 ***************************************************************************/
void named_lin_ineq::align_with(named_lin_ineq & B)
{
    named_lin_ineq & A = *this;
    if(is_aligned(A,B)) return;

    A.cleanup();
    B.cleanup();

    name_table & na = A.names();
    name_table & nb = B.names();

    // indexes to the new list
    integer_row ca(na.n());
    integer_row cb(nb.n());

    name_table * newnt = name_table::align_tables(na, nb, ca, cb);

    A.nt.init(newnt);
    B.nt.init(newnt);

    // Readjust the inequalities to match the new name table
    lin_ineq leqa(A.lq.m(), newnt->n());
    int i;
    for(i=0; i<A.lq.m(); i++)
        for(int j1=0; j1<A.lq.n(); j1++)
            leqa[i][ca[j1]] = A.lq[i][j1];
    A.lq.init(leqa);

    lin_ineq leqb(B.lq.m(), newnt->n());
    for(i=0; i<B.lq.m(); i++)
        for(int j2=0; j2<B.lq.n(); j2++)
            leqb[i][cb[j2]] = B.lq[i][j2];
    B.lq.init(leqb);

    delete newnt;
}

// reorders the table so element kind ordering matches historical ordering;
// if ca, then sets ca so that new[*ca[i]] = old[i];
void named_lin_ineq::do_reorder_table(integer_row *retca)
{
    integer_row ca(n());
    boolean changed = nt.do_reorder_table(ca);

    if (changed) {
	integer_row tmp(n());
	for (int j=0; j<m(); j++) {
	    constraint &rowj = lq[j];
	    tmp[0] = rowj[0];
	    for (int i=1; i<n(); i++)
		tmp[ca[i]] = rowj[i];
	    rowj.init(tmp);
	}
    }
    if (retca) retca->init(ca);
}


/***************************************************************************
 *                                                                         *
 ***************************************************************************/
named_lin_ineq * named_lin_ineq::merge_named_lin_ineqs(
        const named_lin_ineq & A, const named_lin_ineq & B)
{
    named_lin_ineq * nA = new named_lin_ineq(A);
    named_lin_ineq * nB = new named_lin_ineq(B);
    align_named_lin_ineqs(*nA, *nB);

    (*nA) &= nB->ineqs();

    delete nB;
    return nA;
}





/* ##################################################
   #####   other routines for debugging only    #####
   ################################################## */

/***************************************************************************
 *                                                                         *
 ***************************************************************************/
void name_table_entry::print(FILE * fp) const
{
//     fprintf(fp, "(");
//     switch(kind()) {
//     case nte_none:
//         fprintf(fp, "n ");
//         break;
//     case nte_symconst:
//         fprintf(fp, "s ");
//         break;
//     case nte_cond:
//         fprintf(fp, "c ");
//         break;
//     case nte_loop:
//         fprintf(fp, "l ");
//         break;
//     default:
//         fprintf(fp, "? ");
//         break;
//     }
//     if(name)
//         name->print();
//     else
//         fprintf(fp, "?");
//     fprintf(fp, " ");
//     if(old_name) old_name->print();
//     fprintf(fp, ")");
    fprintf(fp, "%s ", (string())?string():"?");
}


void name_table::print(FILE * fp) const
{
    for(int i=1; i<n(); i++) e(i).print(fp);
    fprintf(fp, "\n");
}


void name_table::print_symtabs(FILE * fp) const
{
    fprintf(fp, "     ");
    for(int i=1; i<n(); i++) {
      if(e(i).is_var) 
	fprintf(fp, "%7s", e(i).vsname.v->parent()->name());
    }
    fprintf(fp, "\n");
}