| /* |
| module: reduce.c |
| purpose: Perform the Espresso-II reduction step |
| |
| Reduction is a technique used to explore larger regions of the |
| optimization space. We replace each cube of F with a smaller |
| cube while still maintaining a cover of the same logic function. |
| */ |
| |
| #include "espresso.h" |
| |
| static bool toggle = TRUE; |
| |
| |
| /* |
| reduce -- replace each cube in F with its reduction |
| |
| The reduction of a cube is the smallest cube contained in the cube |
| which can replace the cube in the original cover without changing |
| the cover. This is equivalent to the super cube of all of the |
| essential points in the cube. This can be computed directly. |
| |
| The problem is that the order in which the cubes are reduced can |
| greatly affect the final result. We alternate between two ordering |
| strategies: |
| |
| (1) Order the cubes in ascending order of distance from the |
| largest cube breaking ties by ordering cubes of equal distance |
| in descending order of size (sort_reduce) |
| |
| (2) Order the cubes in descending order of the inner-product of |
| the cube and the column sums (mini_sort) |
| |
| The real workhorse of this section is the routine SCCC which is |
| used to find the Smallest Cube Containing the Complement of a cover. |
| Reduction as proposed by Espresso-II takes a cube and computes its |
| maximal reduction as the intersection between the cube and the |
| smallest cube containing the complement of (F u D - {c}) cofactored |
| against c. |
| |
| As usual, the unate-recursive paradigm is used to compute SCCC. |
| The SCCC of a unate cover is trivial to compute, and thus we perform |
| Shannon Cofactor expansion attempting to drive the cover to be unate |
| as fast as possible. |
| */ |
| |
| pcover reduce(F, D) |
| INOUT pcover F; |
| IN pcover D; |
| { |
| register pcube last, p, cunder, *FD; |
| |
| /* Order the cubes */ |
| if (use_random_order) |
| F = random_order(F); |
| else { |
| F = toggle ? sort_reduce(F) : mini_sort(F, descend); |
| toggle = ! toggle; |
| } |
| |
| /* Try to reduce each cube */ |
| FD = cube2list(F, D); |
| foreach_set(F, last, p) { |
| cunder = reduce_cube(FD, p); /* reduce the cube */ |
| if (setp_equal(cunder, p)) { /* see if it actually did */ |
| SET(p, ACTIVE); /* cube remains active */ |
| SET(p, PRIME); /* cube remains prime ? */ |
| } else { |
| if (debug & REDUCE) { |
| printf("REDUCE: %s to %s %s\n", |
| pc1(p), pc2(cunder), print_time(ptime())); |
| } |
| set_copy(p, cunder); /* save reduced version */ |
| RESET(p, PRIME); /* cube is no longer prime */ |
| if (setp_empty(cunder)) |
| RESET(p, ACTIVE); /* if null, kill the cube */ |
| else |
| SET(p, ACTIVE); /* cube is active */ |
| } |
| free_cube(cunder); |
| } |
| free_cubelist(FD); |
| |
| /* Delete any cubes of F which reduced to the empty cube */ |
| return sf_inactive(F); |
| } |
| |
| /* reduce_cube -- find the maximal reduction of a cube */ |
| pcube reduce_cube(FD, p) |
| IN pcube *FD, p; |
| { |
| pcube cunder; |
| |
| cunder = sccc(cofactor(FD, p)); |
| return set_and(cunder, cunder, p); |
| } |
| |
| |
| /* sccc -- find Smallest Cube Containing the Complement of a cover */ |
| pcube sccc(T) |
| INOUT pcube *T; /* T will be disposed of */ |
| { |
| pcube r; |
| register pcube cl, cr; |
| register int best; |
| static int sccc_level = 0; |
| |
| if (debug & REDUCE1) { |
| debug_print(T, "SCCC", sccc_level++); |
| } |
| |
| if (sccc_special_cases(T, &r) == MAYBE) { |
| cl = new_cube(); |
| cr = new_cube(); |
| best = binate_split_select(T, cl, cr, REDUCE1); |
| r = sccc_merge(sccc(scofactor(T, cl, best)), |
| sccc(scofactor(T, cr, best)), cl, cr); |
| free_cubelist(T); |
| } |
| |
| if (debug & REDUCE1) |
| printf("SCCC[%d]: result is %s\n", --sccc_level, pc1(r)); |
| return r; |
| } |
| |
| |
| pcube sccc_merge(left, right, cl, cr) |
| INOUT register pcube left, right; /* will be disposed of ... */ |
| INOUT register pcube cl, cr; /* will be disposed of ... */ |
| { |
| INLINEset_and(left, left, cl); |
| INLINEset_and(right, right, cr); |
| INLINEset_or(left, left, right); |
| free_cube(right); |
| free_cube(cl); |
| free_cube(cr); |
| return left; |
| } |
| |
| |
| /* |
| sccc_cube -- find the smallest cube containing the complement of a cube |
| |
| By DeMorgan's law and the fact that the smallest cube containing a |
| cover is the "or" of the positional cubes, it is simple to see that |
| the SCCC is the universe if the cube has more than two active |
| variables. If there is only a single active variable, then the |
| SCCC is merely the bitwise complement of the cube in that |
| variable. A last special case is no active variables, in which |
| case the SCCC is empty. |
| |
| This is "anded" with the incoming cube result. |
| */ |
| pcube sccc_cube(result, p) |
| register pcube result, p; |
| { |
| register pcube temp=cube.temp[0], mask; |
| int var; |
| |
| if ((var = cactive(p)) >= 0) { |
| mask = cube.var_mask[var]; |
| INLINEset_xor(temp, p, mask); |
| INLINEset_and(result, result, temp); |
| } |
| return result; |
| } |
| |
| /* |
| * sccc_special_cases -- check the special cases for sccc |
| */ |
| |
| bool sccc_special_cases(T, result) |
| INOUT pcube *T; /* will be disposed if answer is determined */ |
| OUT pcube *result; /* returned only if answer determined */ |
| { |
| register pcube *T1, p, temp = cube.temp[1], ceil, cof = T[0]; |
| pcube *A, *B; |
| |
| /* empty cover => complement is universe => SCCC is universe */ |
| if (T[2] == NULL) { |
| *result = set_save(cube.fullset); |
| free_cubelist(T); |
| return TRUE; |
| } |
| |
| /* row of 1's => complement is empty => SCCC is empty */ |
| for(T1 = T+2; (p = *T1++) != NULL; ) { |
| if (full_row(p, cof)) { |
| *result = new_cube(); |
| free_cubelist(T); |
| return TRUE; |
| } |
| } |
| |
| /* Collect column counts, determine unate variables, etc. */ |
| massive_count(T); |
| |
| /* If cover is unate (or single cube), apply simple rules to find SCCCU */ |
| if (cdata.vars_unate == cdata.vars_active || T[3] == NULL) { |
| *result = set_save(cube.fullset); |
| for(T1 = T+2; (p = *T1++) != NULL; ) { |
| (void) sccc_cube(*result, set_or(temp, p, cof)); |
| } |
| free_cubelist(T); |
| return TRUE; |
| } |
| |
| /* Check for column of 0's (which can be easily factored( */ |
| ceil = set_save(cof); |
| for(T1 = T+2; (p = *T1++) != NULL; ) { |
| INLINEset_or(ceil, ceil, p); |
| } |
| if (! setp_equal(ceil, cube.fullset)) { |
| *result = sccc_cube(set_save(cube.fullset), ceil); |
| if (setp_equal(*result, cube.fullset)) { |
| free_cube(ceil); |
| } else { |
| *result = sccc_merge(sccc(cofactor(T,ceil)), |
| set_save(cube.fullset), ceil, *result); |
| } |
| free_cubelist(T); |
| return TRUE; |
| } |
| free_cube(ceil); |
| |
| /* Single active column at this point => tautology => SCCC is empty */ |
| if (cdata.vars_active == 1) { |
| *result = new_cube(); |
| free_cubelist(T); |
| return TRUE; |
| } |
| |
| /* Check for components */ |
| if (cdata.var_zeros[cdata.best] < CUBELISTSIZE(T)/2) { |
| if (cubelist_partition(T, &A, &B, debug & REDUCE1) == 0) { |
| return MAYBE; |
| } else { |
| free_cubelist(T); |
| *result = sccc(A); |
| ceil = sccc(B); |
| (void) set_and(*result, *result, ceil); |
| set_free(ceil); |
| return TRUE; |
| } |
| } |
| |
| /* Not much we can do about it */ |
| return MAYBE; |
| } |