hack.c

主要进行大规模的电路综合

/*
 * Revision Control Information
 *
 * $Source: /projects/mvsis/Repository/mvsis-1.3/src/sis/espresso/hack.c,v $
 * $Author: wjiang $
 * $Revision: 1.1.1.1 $
 * $Date: 2003/02/24 22:24:08 $
 *
 */
#include "espresso.h"

map_dcset(PLA)
pPLA PLA;
{
    int var, i;
    pcover Tplus, Tminus, Tplusbar, Tminusbar;
    pcover newf, term1, term2, dcset, dcsetbar;
    pcube cplus, cminus, last, p;

    if (PLA->label == NIL(char *) || PLA->label[0] == NIL(char))
	return;

    /* try to find a binary variable named "DONT_CARE" */
    var = -1;
    for(i = 0; i < cube.num_binary_vars * 2; i++) {
	if (strncmp(PLA->label[i], "DONT_CARE", 9) == 0 ||
	  strncmp(PLA->label[i], "DONTCARE", 8) == 0 ||
	  strncmp(PLA->label[i], "dont_care", 9) == 0 ||
	  strncmp(PLA->label[i], "dontcare", 8) == 0) {
	    var = i/2;
	    break;
	}
    }
    if (var == -1) {
	return;
    }

    /* form the cofactor cubes for the don't-care variable */
    cplus = set_save(cube.fullset);
    cminus = set_save(cube.fullset);
    set_remove(cplus, var*2);
    set_remove(cminus, var*2 + 1);

    /* form the don't-care set */
    EXEC(simp_comp(cofactor(cube1list(PLA->F), cplus), &Tplus, &Tplusbar),
	"simpcomp+", Tplus);
    EXEC(simp_comp(cofactor(cube1list(PLA->F), cminus), &Tminus, &Tminusbar),
	"simpcomp-", Tminus);
    EXEC(term1 = cv_intersect(Tplus, Tminusbar), "term1    ", term1);
    EXEC(term2 = cv_intersect(Tminus, Tplusbar), "term2    ", term2);
    EXEC(dcset = sf_union(term1, term2), "union     ", dcset);
    EXEC(simp_comp(cube1list(dcset), &PLA->D, &dcsetbar), "simplify", PLA->D);
    EXEC(newf = cv_intersect(PLA->F, dcsetbar), "separate  ", PLA->F);
    free_cover(PLA->F);
    PLA->F = newf;
    free_cover(Tplus);
    free_cover(Tminus);
    free_cover(Tplusbar);
    free_cover(Tminusbar);
    free_cover(dcsetbar);

    /* remove any cubes dependent on the DONT_CARE variable */
    (void) sf_active(PLA->F);
    foreach_set(PLA->F, last, p) {
	if (! is_in_set(p, var*2) || ! is_in_set(p, var*2+1)) {
	    RESET(p, ACTIVE);
	}
    }
    PLA->F = sf_inactive(PLA->F);

    /* resize the cube and delete the don't-care variable */
    setdown_cube();
    for(i = 2*var+2; i < cube.size; i++) {
	PLA->label[i-2] = PLA->label[i];
    }
    for(i = var+1; i < cube.num_vars; i++) {
	cube.part_size[i-1] = cube.part_size[i];
    }
    cube.num_binary_vars--;
    cube.num_vars--;
    cube_setup();
    PLA->F = sf_delc(PLA->F, 2*var, 2*var+1);
    PLA->D = sf_delc(PLA->D, 2*var, 2*var+1);
}

map_output_symbolic(PLA)
pPLA PLA;
{
    pset_family newF, newD;
    pset compress;
    symbolic_t *p1;
    symbolic_list_t *p2;
    int i, bit, tot_size, base, old_size;

    /* Remove the DC-set from the ON-set (is this necessary ??) */
    if (PLA->D->count > 0) {
	sf_free(PLA->F);
	PLA->F = complement(cube2list(PLA->D, PLA->R));
    }

    /* tot_size = width added for all symbolic variables */
    tot_size = 0;
    for(p1=PLA->symbolic_output; p1!=NIL(symbolic_t); p1=p1->next) {
	for(p2=p1->symbolic_list; p2!=NIL(symbolic_list_t); p2=p2->next) {
	    if (p2->pos<0 || p2->pos>=cube.part_size[cube.output]) {
		fatal("symbolic-output index out of range");
/*	    } else if (p2->variable != cube.output) {
		fatal("symbolic-output label must be an output");*/
	    }
	}
	tot_size += 1 << p1->symbolic_list_length;
    }

    /* adjust the indices to skip over new outputs */
    for(p1=PLA->symbolic_output; p1!=NIL(symbolic_t); p1=p1->next) {
	for(p2=p1->symbolic_list; p2!=NIL(symbolic_list_t); p2=p2->next) {
	    p2->pos += tot_size;
	}
    }

    /* resize the cube structure -- add enough for the one-hot outputs */
    old_size = cube.size;
    cube.part_size[cube.output] += tot_size;
    setdown_cube();
    cube_setup();

    /* insert space in the output part for the one-hot output */
    base = cube.first_part[cube.output];
    PLA->F = sf_addcol(PLA->F, base, tot_size);
    PLA->D = sf_addcol(PLA->D, base, tot_size);
    PLA->R = sf_addcol(PLA->R, base, tot_size);

    /* do the real work */
    for(p1=PLA->symbolic_output; p1!=NIL(symbolic_t); p1=p1->next) {
	newF = new_cover(100);
	newD = new_cover(100);
	find_inputs(NIL(set_family_t), PLA, p1->symbolic_list, base, 0,
			    &newF, &newD);
/*
 *  Not sure what this means
	find_dc_inputs(PLA, p1->symbolic_list,
			    base, 1 << p1->symbolic_list_length, &newF, &newD);
 */
	free_cover(PLA->F);
	PLA->F = newF;
/*
 *  retain OLD DC-set -- but we've lost the don't-care arc information
 *  (it defaults to branch to the zero state)
	free_cover(PLA->D);
	PLA->D = newD;
 */
	free_cover(newD);
	base += 1 << p1->symbolic_list_length;
    }

    /* delete the old outputs, and resize the cube */
    compress = set_full(newF->sf_size);
    for(p1=PLA->symbolic_output; p1!=NIL(symbolic_t); p1=p1->next) {
	for(p2=p1->symbolic_list; p2!=NIL(symbolic_list_t); p2=p2->next) {
	    bit = cube.first_part[cube.output] + p2->pos;
	    set_remove(compress, bit);
	}
    }
    cube.part_size[cube.output] -= newF->sf_size - set_ord(compress);
    setdown_cube();
    cube_setup();
    PLA->F = sf_compress(PLA->F, compress);
    PLA->D = sf_compress(PLA->D, compress);
    if (cube.size != PLA->F->sf_size) fatal("error");

    /* Quick minimization */
    PLA->F = sf_contain(PLA->F);
    PLA->D = sf_contain(PLA->D);
    for(i = 0; i < cube.num_vars; i++) {
	PLA->F = d1merge(PLA->F, i);
	PLA->D = d1merge(PLA->D, i);
    }
    PLA->F = sf_contain(PLA->F);
    PLA->D = sf_contain(PLA->D);

    free_cover(PLA->R);
    PLA->R = new_cover(0);

    symbolic_hack_labels(PLA, PLA->symbolic_output,
			    compress, cube.size, old_size, tot_size);
    set_free(compress);
}


find_inputs(A, PLA, list, base, value, newF, newD)
pcover A;
pPLA PLA;
symbolic_list_t *list;
int base, value;
pcover *newF, *newD;
{
    pcover S, S1;
    register pset last, p;

    /*
     *  A represents th 'input' values for which the outputs assume
     *  the integer value 'value
     */
    if (list == NIL(symbolic_list_t)) {
	/*
	 *  Simulate these inputs against the on-set; then, insert into the
	 *  new on-set a 1 in the proper position
	 */
	S = cv_intersect(A, PLA->F);
	foreach_set(S, last, p) {
	    set_insert(p, base + value);
	}
	*newF = sf_append(*newF, S);

	/*
	 *  'simulate' these inputs against the don't-care set
	S = cv_intersect(A, PLA->D);
	*newD = sf_append(*newD, S);
	 */

    } else {
	/* intersect and recur with the OFF-set */
	S = cof_output(PLA->R, cube.first_part[cube.output] + list->pos);
	if (A != NIL(set_family_t)) {
	    S1 = cv_intersect(A, S);
	    free_cover(S);
	    S = S1;
	}
	find_inputs(S, PLA, list->next, base, value*2, newF, newD);
	free_cover(S);

	/* intersect and recur with the ON-set */
	S = cof_output(PLA->F, cube.first_part[cube.output] + list->pos);
	if (A != NIL(set_family_t)) {
	    S1 = cv_intersect(A, S);
	    free_cover(S);
	    S = S1;
	}
	find_inputs(S, PLA, list->next, base, value*2 + 1, newF, newD);
	free_cover(S);
    }
}


#if 0
find_dc_inputs(PLA, list, base, maxval, newF, newD)
pPLA PLA;
symbolic_list_t *list;
int base, maxval;
pcover *newF, *newD;
{
    pcover A, S, S1;
    symbolic_list_t *p2;
    register pset p, last;
    register int i;

    /* painfully find the points for which the symbolic output is dc */
    A = NIL(set_family_t);
    for(p2=list; p2!=NIL(symbolic_list_t); p2=p2->next) {
	S = cof_output(PLA->D, cube.first_part[cube.output] + p2->pos);
	if (A == NIL(set_family_t)) {
	    A = S;
	} else {
	    S1 = cv_intersect(A, S);
	    free_cover(S);
	    free_cover(A);
	    A = S1;
	}
    }

    S = cv_intersect(A, PLA->F);
    *newF = sf_append(*newF, S);

    S = cv_intersect(A, PLA->D);
    foreach_set(S, last, p) {
	for(i = base; i < base + maxval; i++) {
	    set_insert(p, i);
	}
    }
    *newD = sf_append(*newD, S);
    free_cover(A);
}
#endif

map_symbolic(PLA)
pPLA PLA;
{
    symbolic_t *p1;
    symbolic_list_t *p2;
    int var, base, num_vars, num_binary_vars, *new_part_size;
    int new_size, size_added, num_deleted_vars, num_added_vars, newvar;
    pset compress;

    /* Verify legal values are in the symbolic lists */
    for(p1 = PLA->symbolic; p1 != NIL(symbolic_t); p1 = p1->next) {
	for(p2=p1->symbolic_list; p2!=NIL(symbolic_list_t); p2=p2->next) {
	    if (p2->variable  < 0 || p2->variable >= cube.num_binary_vars) {
		fatal(".symbolic requires binary variables");
	    }
	}
    }

    /*
     *  size_added = width added for all symbolic variables
     *  num_deleted_vars = # binary variables to be deleted
     *  num_added_vars = # new mv variables
     *  compress = a cube which will be used to compress the set families
     */
    size_added = 0;
    num_added_vars = 0;
    for(p1 = PLA->symbolic; p1 != NIL(symbolic_t); p1 = p1->next) {
	size_added += 1 << p1->symbolic_list_length;
	num_added_vars++;
    }
    compress = set_full(PLA->F->sf_size + size_added);
    for(p1 = PLA->symbolic; p1 != NIL(symbolic_t); p1 = p1->next) {
	for(p2=p1->symbolic_list; p2!=NIL(symbolic_list_t); p2=p2->next) {
	    set_remove(compress, p2->variable*2);
	    set_remove(compress, p2->variable*2+1);
	}
    }