ros.c

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

/*
 * Revision Control Information
 *
 * $Source: /projects/mvsis/Repository/mvsis-1.3/src/sis/minimize/ros.c,v $
 * $Author: wjiang $
 * $Revision: 1.2 $
 * $Date: 2003/05/04 22:04:42 $
 *
 */
/******************************************************************************
 * This module has been written by Abdul A. Malik                             *
 * Please forward all feedback, comments, bugs etc to:                        *
 *                                                                            *
 * ABDUL A. MALIK                                                             *
 * [e-mail]                                                      *
 *                                                                            *
 * Department of Electrical Engineering and Computer Sciences                 *
 * University of California at Berkeley                                       *
 * Berkeley, CA 94704.                                                        *
 *                                                                            *
 * Telephone: [phone]                                                  *
 ******************************************************************************/

/*
 * This file contains routines to find the overexpanded cube and blocking
 * matrix (reduced offset) in the dynamic mode. The dynamic mode is
 * characterized by the fact that the unate tree subtree is not stored 
 * for the cofactor passed to one of these routines. To get to unate cofactors
 * of the subtree, all the necessary cofactors will have to be evaluated.
 */

#include "espresso.h"
#define extern
#include "ros.h"
#undef extern

static bool is_taut;
static bool d1_active;

/*
 * Get the blocking matrix (Reduced Off Set) for p.
 */

void
get_ROS1(p, overexpanded_cube, pNode)
pcube p, overexpanded_cube;
pnc_node pNode;

{
    pcover BB;
    long t;
    pcube temp;

    if (trace)
	t = ptime();

    temp = new_cube();
    (void) set_or(temp, p, cube.mv_mask);
    Num_act_vars = cube.size - set_ord(temp);
    Num_act_vars += cube.num_vars - cube.num_binary_vars;

    BB = setupBB(p, overexpanded_cube, pNode, 1);
    ROS = sf_contain(BB);
    free_cube(temp);

    if (trace) {
	Max_ROS_size = MAX(Max_ROS_size, ROS->count);
	ROS_count++;
	ROS_time += ptime() - t;
    }
}

/*
 * Get reduced offset for the ith cube in F, combine it with as many other
 * cubes as possible.
 */

pcover
get_ROS(i, F, Fold)
int i;
pcover F, Fold;

{

    int max_ones, last, j;
    pcube old_cube, overexpanded_cube;

    if (find_correct_ROS(GETSET(F, i))) {
	return (ROS);
    }

    ROS_cube = new_cube();
    old_cube = new_cube();
    overexpanded_cube = new_cube();

    max_ones = cube.size - ROS_zeros;
    last = F->count - 1;

    if (Fold == (pcover) NULL)
	Fold = F;

    /* Form the ROS_cube by multiplying all the cubes in F beginning with
       ith cube until ROS_cube has more ones then max_ones. Form the super-
       cube of the corresponding old cubes in old_cube */
    (void) set_copy(ROS_cube, GETSET(F, i));
    (void) set_copy(old_cube, GETSET(Fold, i));
    for(j=i+1; j<=last; j++) {
	if (set_ord(ROS_cube) > max_ones) {
	    (void) set_and(ROS_cube, ROS_cube, GETSET(F, j));
	    (void) set_or(old_cube, old_cube, GETSET(Fold, j));
	} else {
	    break;
	}
    }

    /* The overexpanded cube of ROS_cube must contain the old_cube;
       therefore, if old_cube is fullset so is overexpanded_cube. If
       overexpanded_cube equals GETSET(F,i) or GETSET(Fold, i) then
       the overexpanded_cube is itself a prime and ROS is simply
       complement of overexpanded_cube */

    if (!setp_equal(old_cube, cube.fullset)) {
	get_OC(ROS_cube, overexpanded_cube, old_cube);
	if (setp_equal(overexpanded_cube, GETSET(F, i))
	   || (setp_equal(overexpanded_cube, GETSET(Fold, i)))) {
	    ROS = nc_compl_cube(overexpanded_cube);
	    store_ROS();
        free_cube(old_cube);           /* added by wjiang (5/4/03) */
        free_cube(overexpanded_cube);  /* to avoid memory leaks    */
	    return(ROS);
	}
    } else {
	(void) set_copy(overexpanded_cube, cube.fullset);
    }

    get_ROS1(ROS_cube, overexpanded_cube, root);

    if (!setp_equal(overexpanded_cube, cube.fullset))
	ROS = sf_append(ROS, nc_compl_cube(overexpanded_cube));

    store_ROS();

    free_cube(old_cube);
    free_cube(overexpanded_cube);

    return(ROS);

}

/*
 * Initialize parameters used by ROS related subroutines.
 * Most of these variables are declared in minimize.h
 */

void
init_ROS(F, D, maxLevel, nLevel, rosZeros)
pcover F;
pcover D;
int maxLevel;
int nLevel;
int rosZeros;

{

    pcube *T;
    long t;

    ROS = (pcover) NULL;/* Reduced Offset itself */
    ROS_count = 0;	/* Number of computations of ROS */
    ROS_time = 0;	/* Aggregate time for computation of ROS */

    ROS_cube = cube.fullset;
			/* Cube for which current ROS was computed */

    Max_ROS_size = 0;	/* Maximum size of ROS computed at any time */

    ROS_zeros = rosZeros;
			/* Maximum number of zeros allowed in ROS_cube.
			   This controls the maximum size of ROS returned. */

    ROS_max_store = 2 * (F->count);
			/* Don't store more than ROS_max_store ROSs */
    
    if (F->count != 0)
	ROS_max_size_store = (int) (ROS_MEM_SIZE/ROS_max_store);
			/* Don't store any ROS that has size more than this */
    
    N_ROS = 0;		/* Number of ROSs stored so far */

    /* Allocate memory to ROS_array */
    ROS_array = ALLOC(ros_holder_t, ROS_max_store);

    /* Initialize variables to collect statistics about OC */
    OC_count = 0;
    OC_time = 0;

    /* Assigne memory to temporary cubes. */
    nc_setup_tmp_cubes(33);

    /* Generate unate cofactors of T = (F U D) to use latter for computing
       reduced off sets */
    Tree_cover = sf_save(F);
    Tree_cover = sf_append(Tree_cover, sf_save(D));
    T = cube1list(Tree_cover);

    /* Max_level is the maximum depth of the static cofactoring tree.
       N_level is the number of levels after which some special filtering is
       done. */
    Max_level = maxLevel;
    N_level = nLevel;

    /* Generate the cofactoring tree */
    root = ALLOC(nc_node_t, 1);
    if (trace) {
	t = ptime();
    }

    nc_generate_cof_tree(root, T, 1);

    if (trace) {
	t = ptime() - t;
	(void) printf("# COFACTOR TREE\tTime was %s, level=%d\n",
					    print_time(t), maxLevel);
    }

}

/*
 * find_correct_ROS -- Find a ROS that is usable to expand p.
 * If such a ROS is found, set ROS to it and ROS_cube to its cube.
 * return TRUE, otherwise return FALSE.
 */

bool
find_correct_ROS(p)
pcube p;

{

    int i;
    pros_holder pros_h;

    /* Check to see if the current ROS is usable. If so don't
       have to do anything */
    if (setp_implies(ROS_cube, p))
	return(TRUE);

    for (i=0; i<N_ROS; i++) {
	pros_h = ROS_array+i;
	if (setp_implies(pros_h->ros_cube, p)) {
	    ROS = pros_h->ros;
	    ROS_cube = pros_h->ros_cube;
	    (pros_h->count)++;
	    return (TRUE);
	}
    }

    return(FALSE);

}

/*
 * store_ROS -- store current ROS in ROS_array.
 */

void
store_ROS()

{

    pros_holder pros_h;
    int count, min, i;

    /* If the size of ROS is larger than the maximum size allowed for
       storage then don't store */
    if (ROS->count > ROS_max_size_store)
	return;

    if (N_ROS < ROS_max_store) {
	pros_h = ROS_array + N_ROS;
	N_ROS++;
    } else { /* Find a ros with the least count */
	min = 0;
	count = ROS_array[0].count;
	for (i=1; i<N_ROS; i++) {
	    if (ROS_array[i].count < count) {
		min = i;
		count = ROS_array[i].count;
	    }
	}
	pros_h = ROS_array + min;
	sf_free(pros_h->ros);
	free_cube(pros_h->ros_cube);
    }

    pros_h->ros = ROS;
    pros_h->ros_cube = ROS_cube;
    pros_h->count = 1;

}

/*
 * Free all the stuff in ROS_array.
 */

void
close_ROS()

{

    int i;
    pros_holder pros_h;

    /* Print stat about ROS and OC in this run */
    if (trace) {
        (void) printf("# OVEREXPANDED CUBES\tTime was %s, count=%d\n",
            print_time(OC_time), OC_count);
        (void) printf("# REDUCED OFFSETS\tTime was %s, count=%d, maximum size=%d\n",
            print_time(ROS_time), ROS_count, Max_ROS_size);
    }

    /* Free the memory used in the unate tree */
    nc_free_unate_tree(root);
    sf_free(Tree_cover);

    /* Free temporary cubes */
    nc_free_tmp_cubes(33);

    /* First free all ros and ros_cubes in the array */
    for (i=0; i<N_ROS; i++) {
       pros_h = ROS_array + i;
       sf_free(pros_h->ros);
       free_cube(pros_h->ros_cube);
    }

    /* Finally free the array */
    FREE(ROS_array);

}

/*
 * Find the overexpanded cube of cube p.
 *
 * This subroutine is used when the entire unate tree is stored
 * rather than only the leafs.
 */

void
find_overexpanded_cube_dyn(p, overexpanded_cube, T, dist_cube, dist, var, level)
pcube p;			/* Node to be expanded */
pcube overexpanded_cube;	/* overexpanded cube so far */
pcube *T;		/* The current cubelist */
pcube dist_cube;	/* Node where distance changed from 0 to 1 */
int dist;		/* Distance so far between cofactoring cube and p */
int var;		/* Conflicting variable */
int level;		/* Level in the unate tree */

{
    pcube cl, cr;
    pcube *Tl, *Tr;
    int best;

    if (find_oc_dyn_special_cases(p, overexpanded_cube, T,
					    dist_cube, dist, var, level)) {
    return;
    }
    else {

	cl = new_cube();
	cr = new_cube();

	best = binate_split_select(T, cl, cr, COMPL);

	if (best < cube.num_binary_vars) {
	    nc_bin_cof(T, &Tl, &Tr, cl, cr, best);
	}

	else {
	    Tl = scofactor(T, cl, best);
	    nc_cof_contain(Tl);
	    Tr = scofactor(T, cr, best);
	    nc_cof_contain(Tr);
	}

	if (dist == 0) {

	    /* Process the left subtree */
	    if (cdist0v(cl, p, best))
		find_overexpanded_cube_dyn(p, overexpanded_cube,
					    Tl, (pcube)NULL, 0, 0, level+1);
	    else if (cdist0v(cl, overexpanded_cube, best)) {
		d1_active = TRUE;
		find_overexpanded_cube_dyn(p, overexpanded_cube,
					    Tl, cr, 1, best, level+1);
	    }

	    /* Process the right subtree */
	    if (cdist0v(cr, p, best))
		find_overexpanded_cube_dyn(p, overexpanded_cube,
					    Tr, (pcube)NULL, 0, 0, level+1);
	    else if (cdist0v(cr, overexpanded_cube, best)) {
		d1_active = TRUE;
		find_overexpanded_cube_dyn(p, overexpanded_cube,
					    Tr, cl, 1, best, level+1);
	    }

	}

	else {  /* dist == 1 */

	    if (var == best) { /* Split is on the conflicting variable */
		find_overexpanded_cube_dyn(p, overexpanded_cube,
					    Tl, dist_cube, 1, var, level+1);
		find_overexpanded_cube_dyn(p, overexpanded_cube,
					    Tr, dist_cube, 1, var, level+1);
	    }

	    else {
		if (cdist0v(cl, p, best))
		    find_overexpanded_cube_dyn(p, overexpanded_cube,
					    Tl, dist_cube, 1, var, level+1);
		if (cdist0v(cr, p, best) && (d1_active))
		    find_overexpanded_cube_dyn(p, overexpanded_cube,
					    Tr, dist_cube, 1, var, level+1);
	    }
	}

	/* Free left and right cubelists and partition cubes */
	free_cubelist(Tl);
	free_cubelist(Tr);
	free_cube(cl);
	free_cube(cr);

    }

}

/*
 * Special cases for finding overexpanded cube.
 */
bool
find_oc_dyn_special_cases(p, overexpanded_cube, T, dist_cube, dist, var, level)
pcube p;		/* Node to be expanded */
pcube overexpanded_cube;/* overexpanded cube so far */
pcube T[];		/* The current cubelist */
pcube dist_cube;	/* Node where distance changed from 0 to 1 */
int dist;		/* Distance so far between cofactoring cube and p */
int var;		/* Conflicting variable */
int level;		/* Level in the unate tree */

{
    pcube temp;
    int k, last_word;
    pcube mask; 

    if (dist == 0) {

	/* If all the variables in T are either already lowered in
	   the overexpanded cube or not present in p then there is no
	   point in processing any cofactors of T */

	temp = set_diff(new_cube(), overexpanded_cube, T[0]);
	if (setp_implies(temp, p)) {
	    free_cube(temp);
	    return(TRUE);
	}
	free_cube(temp);

    }

    /* Remove unnecessary cubes from the cofactor. These are the cubes
    that don't contain p in their unate variables. */

    if (!(level % N_level)) {
	nc_rem_unnec_cubes(p, T);
    }

    /* Avoid massive count if there is no cube or only one cube in the cover */
    if ((T[2] == NULL) || (T[3] == NULL))
	cdata.vars_unate = cdata.vars_active = 1;

    else massive_count(T);

    /* Check for unate cover */
    if (cdata.vars_active == cdata.vars_unate) { /* T is unate */

	temp = new_cube();

	if (dist == 0) {
	    nc_or_unnec(p, T, temp);
	    (void) set_and(overexpanded_cube, overexpanded_cube, temp);
	}

	else { /* dist == 1 */

	    if (var < cube.num_binary_vars) {  
		/* Conflicting variable is binary variable */
		if (!nc_is_nec(p, T)) {
		    d1_active = FALSE;
		    (void) set_and(overexpanded_cube, overexpanded_cube, dist_cube);
		}
	    }

	    else { 
		/* Conflicting variable is an mv.
		Lower essential parts in overexpanded cube */
		nc_or_unnec(p, T, temp);
		last_word = cube.last_word[var];
		mask = cube.var_mask[var];
		for (k=cube.first_word[var]; k<=last_word; k++)
		    overexpanded_cube[k] &= temp[k] | ~mask[k];
	    }

	}

	free_cube(temp);

	return(TRUE);
    
    }

    return(FALSE);

}

/*
 * Generate the blocking matrix for cube p.
 *
 * This routine is similar to setupBB except that it is
 * used when blocking matrix is comupted dynamically for a subtree.
 *
 */

pcover
setupBB_dyn(p, overexpanded_cube, T, level)