expand.c

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

/*
 * Revision Control Information
 *
 * $Source: /projects/mvsis/Repository/mvsis-1.3/src/sis/espresso/expand.c,v $
 * $Author: wjiang $
 * $Revision: 1.1.1.1 $
 * $Date: 2003/02/24 22:24:08 $
 *
 */
/*
    module: expand.c
    purpose: Perform the Espresso-II Expansion Step

    The idea is to take each nonprime cube of the on-set and expand it
    into a prime implicant such that we can cover as many other cubes
    of the on-set.  If no cube of the on-set can be covered, then we
    expand each cube into a large prime implicant by transforming the
    problem into a minimum covering problem which is solved by the
    heuristics of minimum_cover.

    These routines revolve around having a representation of the
    OFF-set.  (In contrast to the Espresso-II manuscript, we do NOT
    require an "unwrapped" version of the OFF-set).

    Some conventions on variable names:

	SUPER_CUBE is the supercube of all cubes which can be covered
	by an expansion of the cube being expanded

	OVEREXPANDED_CUBE is the cube which would result from expanding
	all parts which can expand individually of the cube being expanded

	RAISE is the current expansion of the current cube

	FREESET is the set of parts which haven't been raised or lowered yet.

	INIT_LOWER is a set of parts to be removed from the free parts before
	starting the expansion
*/

#include "espresso.h"

/*
    expand -- expand each nonprime cube of F into a prime implicant

    If nonsparse is true, only the non-sparse variables will be expanded;
    this is done by forcing all of the sparse variables out of the free set.
*/

pcover expand(F, R, nonsparse)
INOUT pcover F;
IN pcover R;
IN bool nonsparse;              /* expand non-sparse variables only */
{
    register pcube last, p;
    pcube RAISE, FREESET, INIT_LOWER, SUPER_CUBE, OVEREXPANDED_CUBE;
    int var, num_covered;
    bool change;

    /* Order the cubes according to "chewing-away from the edges" of mini */
    if (use_random_order)
	F = random_order(F);
    else
	F = mini_sort(F, ascend);

    /* Allocate memory for variables needed by expand1() */
    RAISE = new_cube();
    FREESET = new_cube();
    INIT_LOWER = new_cube();
    SUPER_CUBE = new_cube();
    OVEREXPANDED_CUBE = new_cube();

    /* Setup the initial lowering set (differs only for nonsparse) */
    if (nonsparse)
	for(var = 0; var < cube.num_vars; var++)
	    if (cube.sparse[var])
		(void) set_or(INIT_LOWER, INIT_LOWER, cube.var_mask[var]);

    /* Mark all cubes as not covered, and maybe essential */
    foreach_set(F, last, p) {
	RESET(p, COVERED);
	RESET(p, NONESSEN);
    }

    /* Try to expand each nonprime and noncovered cube */
    foreach_set(F, last, p) {
	/* do not expand if PRIME or if covered by previous expansion */
	if (! TESTP(p, PRIME) && ! TESTP(p, COVERED)) {

	    /* expand the cube p, result is RAISE */
	    expand1(R, F, RAISE, FREESET, OVEREXPANDED_CUBE, SUPER_CUBE,
		INIT_LOWER, &num_covered, p);
	    if (debug & EXPAND)
		(void) printf("EXPAND: %s (covered %d)\n", pc1(p), num_covered);
	    (void) set_copy(p, RAISE);
	    SET(p, PRIME);
	    RESET(p, COVERED);		/* not really necessary */

	    /* See if we generated an inessential prime */
	    if (num_covered == 0 && ! setp_equal(p, OVEREXPANDED_CUBE)) {
		SET(p, NONESSEN);
	    }
	}
    }

    /* Delete any cubes of F which became covered during the expansion */
    F->active_count = 0;
    change = FALSE;
    foreach_set(F, last, p) {
	if (TESTP(p, COVERED)) {
	    RESET(p, ACTIVE);
	    change = TRUE;
	} else {
	    SET(p, ACTIVE);
	    F->active_count++;
	}
    }
    if (change)
	F = sf_inactive(F);

    free_cube(RAISE);
    free_cube(FREESET);
    free_cube(INIT_LOWER);
    free_cube(SUPER_CUBE);
    free_cube(OVEREXPANDED_CUBE);
    return F;
}

/*
    expand1 -- Expand a single cube against the OFF-set
*/
void expand1(BB, CC, RAISE, FREESET, OVEREXPANDED_CUBE, SUPER_CUBE,
		INIT_LOWER, num_covered, c)
pcover BB;			/* Blocking matrix (OFF-set) */
pcover CC;			/* Covering matrix (ON-set) */
pcube RAISE;			/* The current parts which have been raised */
pcube FREESET;			/* The current parts which are free */
pcube OVEREXPANDED_CUBE;	/* Overexpanded cube of c */
pcube SUPER_CUBE;		/* Supercube of all cubes of CC we cover */
pcube INIT_LOWER;		/* Parts to initially remove from FREESET */
int *num_covered;		/* Number of cubes of CC which are covered */
pcube c;			/* The cube to be expanded */
{
    int bestindex;

    if (debug & EXPAND1)
	(void) printf("\nEXPAND1:    \t%s\n", pc1(c));

    /* initialize BB and CC */
    SET(c, PRIME);		/* don't try to cover ourself */
    setup_BB_CC(BB, CC);

    /* initialize count of # cubes covered, and the supercube of them */
    *num_covered = 0;
    (void) set_copy(SUPER_CUBE, c);

    /* Initialize the lowering, raising and unassigned sets */
    (void) set_copy(RAISE, c);
    (void) set_diff(FREESET, cube.fullset, RAISE);

    /* If some parts are forced into lowering set, remove them */
    if (! setp_empty(INIT_LOWER)) {
	(void) set_diff(FREESET, FREESET, INIT_LOWER);
	elim_lowering(BB, CC, RAISE, FREESET);
    }

    /* Determine what can be raised, and return the over-expanded cube */
    essen_parts(BB, CC, RAISE, FREESET);
    (void) set_or(OVEREXPANDED_CUBE, RAISE, FREESET);

    /* While there are still cubes which can be covered, cover them ! */
    if (CC->active_count > 0) {
	select_feasible(BB, CC, RAISE, FREESET, SUPER_CUBE, num_covered);
    }

    /* While there are still cubes covered by the overexpanded cube ... */
    while (CC->active_count > 0) {
	bestindex = most_frequent(CC, FREESET);
	set_insert(RAISE, bestindex);
	set_remove(FREESET, bestindex);
	essen_parts(BB, CC, RAISE, FREESET);
    }

    /* Finally, when all else fails, choose the largest possible prime */
    /* We will loop only if we decide unravelling OFF-set is too expensive */
    while (BB->active_count > 0) {
	mincov(BB, RAISE, FREESET);
    }

    /* Raise any remaining free coordinates */
    (void) set_or(RAISE, RAISE, FREESET);
}

/*
    essen_parts -- determine which parts are forced into the lowering
    set to insure that the cube be orthognal to the OFF-set.

    If any cube of the OFF-set is distance 1 from the raising cube,
    then we must lower all parts of the conflicting variable.  (If the
    cube is distance 0, we detect this error here.)

    If there are essentially lowered parts, we can remove from consideration
    any cubes of the OFF-set which are more than distance 1 from the
    overexpanded cube of RAISE.
*/

void essen_parts(BB, CC, RAISE, FREESET)
pcover BB, CC;
pcube RAISE, FREESET;
{
    register pcube p, r = RAISE;
    pcube lastp, xlower = cube.temp[0];
    int dist;

    (void) set_copy(xlower, cube.emptyset);

    foreach_active_set(BB, lastp, p) {
#ifdef NO_INLINE
	if ((dist = cdist01(p, r)) > 1) goto exit_if;
#else
 {register int w,last;register unsigned int x;dist=0;if((last=cube.inword)!=-1)
{x=p[last]&r[last];if(x=~(x|x>>1)&cube.inmask)if((dist=count_ones(x))>1)goto
exit_if;for(w=1;w<last;w++){x=p[w]&r[w];if(x=~(x|x>>1)&DISJOINT)if(dist==1||(
dist+=count_ones(x))>1)goto exit_if;}}}{register int w,var,last;register pcube
mask;for(var=cube.num_binary_vars;var<cube.num_vars;var++){mask=cube.var_mask[
var];last=cube.last_word[var];for(w=cube.first_word[var];w<=last;w++)if(p[w]&r[
w]&mask[w])goto nextvar;if(++dist>1)goto exit_if;nextvar:;}}
#endif
	if (dist == 0) {
	    fatal("ON-set and OFF-set are not orthogonal");
	} else {
	    (void) force_lower(xlower, p, r);
	    BB->active_count--;
	    RESET(p, ACTIVE);
	}
exit_if: ;
    }

    if (! setp_empty(xlower)) {
	(void) set_diff(FREESET, FREESET, xlower);/* remove from free set */
	elim_lowering(BB, CC, RAISE, FREESET);
    }

    if (debug & EXPAND1)
	(void) printf("ESSEN_PARTS:\tRAISE=%s FREESET=%s\n", pc1(RAISE), pc2(FREESET));
}

/*
    essen_raising -- determine which parts may always be added to
    the raising set without restricting further expansions

    General rule: if some part is not blocked by any cube of BB, then
    this part can always be raised.
*/

void essen_raising(BB, RAISE, FREESET)
register pcover BB;
pcube RAISE, FREESET;
{
    register pcube last, p, xraise = cube.temp[0];

    /* Form union of all cubes of BB, and then take complement wrt FREESET */
    (void) set_copy(xraise, cube.emptyset);
    foreach_active_set(BB, last, p)
	INLINEset_or(xraise, xraise, p);
    (void) set_diff(xraise, FREESET, xraise);

    (void) set_or(RAISE, RAISE, xraise);         /* add to raising set */
    (void) set_diff(FREESET, FREESET, xraise);       /* remove from free set */

    if (debug & EXPAND1)
	(void) printf("ESSEN_RAISING:\tRAISE=%s FREESET=%s\n",
	    pc1(RAISE), pc2(FREESET));
}

/*
    elim_lowering -- after removing parts from FREESET, we can reduce the
    size of both BB and CC.

    We mark as inactive any cube of BB which does not intersect the
    overexpanded cube (i.e., RAISE + FREESET).  Likewise, we remove
    from CC any cube which is not covered by the overexpanded cube.
*/

void elim_lowering(BB, CC, RAISE, FREESET)
pcover BB, CC;
pcube RAISE, FREESET;
{
    register pcube p, r = set_or(cube.temp[0], RAISE, FREESET);
    pcube last;

    /*
     *  Remove sets of BB which are orthogonal to future expansions
     */
    foreach_active_set(BB, last, p) {
#ifdef NO_INLINE
	if (! cdist0(p, r))
#else
 {register int w,lastw;register unsigned int x;if((lastw=cube.inword)!=-1){x=p[
lastw]&r[lastw];if(~(x|x>>1)&cube.inmask)goto false;for(w=1;w<lastw;w++){x=p[w]
&r[w];if(~(x|x>>1)&DISJOINT)goto false;}}}{register int w,var,lastw;register
pcube mask;for(var=cube.num_binary_vars;var<cube.num_vars;var++){mask=cube.
var_mask[var];lastw=cube.last_word[var];for(w=cube.first_word[var];w<=lastw;w++)
if(p[w]&r[w]&mask[w])goto nextvar;goto false;nextvar:;}}continue;false:
#endif
	    BB->active_count--, RESET(p, ACTIVE);
    }


    /*
     *  Remove sets of CC which cannot be covered by future expansions
     */
    if (CC != (pcover) NULL) {
	foreach_active_set(CC, last, p) {
#ifdef NO_INLINE
	    if (! setp_implies(p, r))
#else
	    INLINEsetp_implies(p, r, /* when false => */ goto false1);
	    /* when true => go to end of loop */ continue;
	    false1:
#endif
		CC->active_count--, RESET(p, ACTIVE);
	}
    }
}

/*
    most_frequent -- When all else fails, select a reasonable part to raise
    The active cubes of CC are the cubes which are covered by the
    overexpanded cube of the original cube (however, we know that none
    of them can actually be covered by a feasible expansion of the
    original cube).  We resort to the MINI strategy of selecting to
    raise the part which will cover the same part in the most cubes of CC.
*/
int most_frequent(CC, FREESET)
pcover CC;
pcube FREESET;
{
    register int i, best_part, best_count, *count;
    register pset p, last;

    /* Count occurences of each variable */
    count = ALLOC(int, cube.size);
    for(i = 0; i < cube.size; i++)
	count[i] = 0;