named_sc_op.cc

c到DHL的转换工具

// This may look like C code, but it is really -*- C++ -*-

// This may look like C code, but it is really -*- C++ -*-

// This may look like C code, but it is really -*- C++ -*-

/* file "named_sc_op.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>

#define _MODULE_ "libsuifmath.a"

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

#define DO_CHECK



/***************************************************************************
 *************************************************************************** 
 ****   Column Operations                                               ****
 ***************************************************************************
 ***************************************************************************/

void named_symcoeff_ineq::swap_col(int i, int j)
{
    name_table_entry tmp(cols()[i]);
    cols()[i].init(cols()[j]);
    cols()[j].init(tmp);

    if (m() > 0) {
        for (int c=0; c<p(); c++)
            L[c] = L[c].swap_col(i, j);
    }
#ifdef DO_CHECK
    check();
#endif
}

void named_symcoeff_ineq::add_col(immed im, int i)
{
    name_table_entry * nte = new name_table_entry(im);
    add_col(*nte, i);
}

void named_symcoeff_ineq::add_col(const name_table_entry & nte, int i)
{
    
    int xn = n();    
    assert((i>=0)||(i<=xn));
    
    if(m() == 0) {
	for(int x=0; x<p(); x++)
	    (*this)[x].init(0, xn+1);	
    } else {
	nim_op O;
	int x;
	if(i == n())
	    for(x=0; x<p(); x++)
		(*this)[x].init(Compose(1, 2,
		    O.NIM((*this)[x]),
		    O.NIM((*this)[x].m(), 1)));
	else 
	    for(x=0; x<p(); x++)
		(*this)[x].init(Compose(1, 3,
		    O.NIM((*this)[x].resize(0, (*this)[x].m(),
			0, i)),
		    O.NIM((*this)[x].m(), 1),
		    O.NIM((*this)[x].resize(0, (*this)[x].m(),
			i, (*this)[x].n()))));
    }
    
    
    cols().insert(nte, i);
#ifdef DO_CHECK
    check();
#endif
}

void named_symcoeff_ineq::del_col(int i, int j)
{
    integer_row r(n());
    r = 0;
    for(int x=i; x<=j; x++) r[x] = 1;
    del_col(r);
#ifdef DO_CHECK
    check();
#endif
}

void named_symcoeff_ineq::del_col(integer_row & row)
{
    assert(row.n() == n());
    assert(row[0]==0);
    
    int nc = 1;
    int i;
    for(i=1; i<n(); i++)
        if(row[i]==0) nc++;
    
    name_table newcol(nc);
    int curr = 1;
    for(i=1; i<n(); i++)
        if(row[i]==0)
            newcol[curr++] = cols()[i];
    
    
    int oldn = n();
    int oldm = m();
    lin_ineq * oldL = L;
    L = NULL;
    cols().init(newcol);
    initL(oldm);
    
    for(int ip=0; ip<p(); ip++)
        for(int im=0; im<m(); im++) {
            int curr = 0;
            for(int in=0; in<oldn; in++)
                if(row[in]==0)
                    (*this)[ip][im][curr++] = oldL[ip][im][in];
        }
    
    delete[] oldL;
#ifdef DO_CHECK
    check();
#endif
}



/***************************************************************************
 ***************************************************************************
 ****   Plain Operations                                                ****
 ***************************************************************************
 ***************************************************************************/

void named_symcoeff_ineq::add_pln(immed sym, int i)
{
    name_table_entry * nte = new name_table_entry(sym);
    add_pln(*nte, i);
}

void named_symcoeff_ineq::add_pln(name_table_entry & nte, int i)
{
    int oldm = m();
    lin_ineq * oldL = L;
    L = NULL;
    planes().insert(nte, i);
    initL(oldm);
    
    int ip;
    for(ip=0; ip<i; ip++)
        (*this)[ip] = oldL[ip];
    
    for(ip=i+1; ip<p(); ip++)
        (*this)[ip] = oldL[ip-1];
    delete[] oldL;
#ifdef DO_CHECK
    check();
#endif
}

void named_symcoeff_ineq::del_pln(int /* i */, int /* j */)
{
    assert(0);
}

void named_symcoeff_ineq::del_pln(integer_row & row)
{
    assert(row.n() == p());
    assert(row[0]==0);

    int np = 1;
    int i;
    for(i=1; i<p(); i++)
        if(row[i]==0) np++;

    name_table newpln(np);
    int curr = 1;
    for(i=1; i<p(); i++)
        if(row[i]==0)
            newpln[curr++] = planes()[i];
    
    
    int oldm = m();
    int oldp = p();
    lin_ineq * oldL = L;
    L = NULL;
    planes().init(newpln);
    initL(oldm);
    curr = 0;
    for(int ip=0; ip<oldp; ip++) 
        if(row[ip]==0)
            (*this)[curr++].init(oldL[ip]);

    delete[] oldL;
#ifdef DO_CHECK
    check();
#endif
}



/***************************************************************************
 ***************************************************************************
 ****   Inequality Operations                                           ****
 ***************************************************************************
 ***************************************************************************/

void named_symcoeff_ineq::add_ineq(int i)
{
    nim_op O;
    int x;
    if(m() == 0) {
        assert((i==0)||(i==1));
        for(x=0; x<p(); x++)
            (*this)[x].init(1, n());
    } else if(i == 0)
        for(x=0; x<p(); x++)
            (*this)[x].init(Compose(2, 1,
		O.NIM(1, (*this).n()),
		O.NIM((*this)[x])));
    else if(i == m())
        for(x=0; x<p(); x++)
            (*this)[x].init(Compose(2, 1,
		O.NIM((*this)[x]),
		O.NIM(1, (*this)[x].n())));
    else 
        for(x=0; x<p(); x++)
            (*this)[x].init(Compose(3, 1,
		O.NIM((*this)[x].resize(0, i,
		    0, (*this)[x].n())),
		O.NIM(1, (*this)[x].n()),
		O.NIM((*this)[x].resize(i, (*this)[x].m(),
		    0, (*this)[x].n()))));
#ifdef DO_CHECK
    check();
#endif
}

void named_symcoeff_ineq::del_ineq(int i, int j)
{
    integer_row r(m());
    r = 0;
    for(int x=i; x<=j; x++) r[x] = 1;
    del_ineq(r);
}

void named_symcoeff_ineq::del_ineq(integer_row & row)
{
    assert(row.n() == m());
    
    int nm = 0;
    for(int i=0; i<m(); i++)
        if(row[i]==0) nm++;
    
    
    lin_ineq * oldL = L;
    L = NULL;
    initL(nm);
    
    int curr = 0;
    for(int im=0; im<m(); im++) 
        if(row[im]==0) {
            for(int ip=0; ip<p(); ip++)
                for(int in=0; in<n(); in++)
                    (*this)[ip][curr][in] = oldL[ip][im][in];
            curr++;
        }
    
    delete[] oldL;
#ifdef DO_CHECK
    check();
#endif
}


/***************************************************************************
 * Assignment                                                              *
 ***************************************************************************/
named_symcoeff_ineq & 
named_symcoeff_ineq::operator=(const named_symcoeff_ineq & c)
{
    if(this == &c) return *this;
    init(c);
    return *this;
}


/***************************************************************************
 * Projection                                                              *
 ***************************************************************************/
void named_symcoeff_ineq::project_away(immed im)
{
    named_sc_fm FM(this);
    int x = cols().find(im);
    assert(x>0);
    FM.fm_bounds(x,x+1);
    init(FM.internal_get());
#ifdef DO_CHECK
    check();
#endif
}

void named_symcoeff_ineq::project_away(name_table &)
{
    assert(0);
}

// ret(??, m, ??) += ex@(ip, 0, in) * ret@(sp, m, sn)
static instruction * do_substitute(instruction * in, var_sym * sym, instruction * expr, base_symtab * st, boolean first_in = TRUE)
{
    assert(in);
    if(first_in) in = in->clone(st);

    if(in->opcode() == io_ldc)
	if(((in_ldc *)in)->value() == immed(sym)) 
	    return expr->clone(st);

    for(unsigned i=0; i < in->num_srcs(); i++) {
	operand op(in->src_op(i));
	if(op.is_symbol()) {
	    if(op.symbol() == sym) 
		in->set_src_op(i, operand(expr->clone(st)));
	} else if(op.is_instr()) {
	    instruction * cout = do_substitute(op.instr(), sym, expr, st, FALSE);
	    if(cout != op.instr())
		in->set_src_op(i, operand(cout));
	}
    }

    return in;
}


/**************************************************************************
 * a simple substitution method                                           *
 * This is a cheap alternative to expensive Fourier-Motzkin               *
 * substitution expression given in expr is of the form                   *
 * var >= sub_expr and var <= sub_expr or                                 *
 * sub_expr >= 0                                                          *
 * BUGBUG: This implementation is a gros hack.  Trying to do the          *
 * substitution involves dealing with too many cases. Since convertion    *
 * of expression trees to named_symcoefff_ineq already is doing most of   *
 * the cases, I am using that for now.  But this is ugly and inefficient  *
 * and should be rewritten.                                               *
 **************************************************************************/
named_symcoeff_ineq * named_symcoeff_ineq::substitute(immed var, named_symcoeff_ineq & expr)
{
    assert(var.is_symbol());
    assert(var.symbol()->is_var());
    
    int cpos = cols().find(var);
    int ppos = planes().find(var);
    if((cpos <= 0)&&(ppos <= 0))
	return new named_symcoeff_ineq(this);
    assert((cpos <= 0)||(ppos <= 0));

    named_symcoeff_ineq myex;
    if(expr.m() == 1) {
	assert_msg(expr.cols().find(var) == -1, ("Variable cannot be a part of the sub_expr in this form"));
	assert_msg(expr.planes().find(var) == -1, ("Variable cannot be a part of the sub_expr in this form"));
	myex = expr;
    } else {
	int pos = expr.cols().find(var);
	assert_msg(pos > 0, ("variable is not in the expression"));
	int ip;
	for(ip=0; ip<expr.p(); ip++)
	    for(int im=0; im<expr.n(); im++)
		assert_msg(expr[ip][0][im] + expr[ip][1][im] == 0, ("expr is not a equality given by two inequalities"));
	assert_msg(ABS(expr[0][0][pos]) == 1, ("Expr is not v = sub_expr, but %d*v = sub_expr", ABS(expr[0][0][pos])));
	for(ip=1; ip<expr.p(); ip++)
	    assert_msg(expr[ip][0][pos] == 0, ("Expr is not v = sub_expr, but %s*v = sub_expr", expr.planes()[ip].string()));

	lin_ineq * l;
	if(expr[0][0][pos] > 0)
	    l = expr.get_m(1);
	else 
	    l = expr.get_m(0);
	myex.init(expr.p(), 1, expr.n());
	myex.cols().init(expr.cols());
	myex.planes().init(expr.planes());
	myex.set_m(0, l);
	delete l;
	
	myex.del_col(pos);
    }

    base_symtab * bt = NULL;
    bt = cols().get_symtab(bt);
    bt = planes().get_symtab(bt);
    bt = myex.cols().get_symtab(bt);
    bt = myex.planes().get_symtab(bt);

    instruction * inex = myex.create_expression();
    named_symcoeff_ineq ret;
    for(int i=0; i<m(); i++) {
	named_symcoeff_ineq curr;
	curr.init(p(), 1, n());
	curr.cols().init(cols());
	curr.planes().init(planes());
	lin_ineq * t = get_m(i);
	curr.set_m(i, t);
	delete t;
	
	instruction * incurr = curr.create_expression();
	instruction * insub = do_substitute(incurr, (var_sym *)var.symbol(), inex, bt);

	named_symcoeff_ineq * rep = convert_exp(insub);
	if(rep == NULL)
	    return NULL;
	
	ret || *rep;
	assert(rep->m() == 1);
	t = rep->get_m(0);
	ret.add_ineq(0);
	ret.set_m(0, t);
	delete t;
	delete rep;
	delete incurr;
    }

    return new named_symcoeff_ineq(ret);
}



void named_symcoeff_ineq::move_col2plane(name_table_entry & nte, boolean * too_messy)
{
    int c = cols().find(nte);
    assert_msg(c > 0, ("not a constant or variable"));
    
    assert_msg(planes().find(nte) == -1, 
	("Error same variable in both"
	 " plane and column"));

    int xm;
    int xp;
    for(xp=1; xp<p(); xp++)
        for(xm=0; xm<m(); xm++) {
            if((*this)[xp][xm][c]) {
                if(too_messy) {
                    (*too_messy)++;
                    return;
                } else
                    assert_msg(0, ("Will become too messy because of (%d,%d,%d)", 
			xp, xm, c));
            }
        }
    
    int ap = p();
    int am = m();
    int an = n();
    lin_ineq * AL = L;
    L = NULL;
    planes().insert(cols()[c], ap);
    initL(am);
    for(xp=0; xp<ap; xp++)
        for(xm=0; xm<am; xm++)
            for(int xn=0; xn<an; xn++)
                (*this)[xp][xm][xn] = AL[xp][xm][xn];
    
    delete[] AL;
    
    for(xm=0; xm<am; xm++)
        (*this)[ap][xm][0] = (*this)[0][xm][c];