| /* |
| module: sparse.c |
| |
| make_sparse is a last-step cleanup to reduce the total number |
| of literals in the cover. |
| |
| This is done by reducing the "sparse" variables (using a modified |
| version of irredundant rather than reduce), followed by expanding |
| the "dense" variables (using modified version of expand). |
| */ |
| |
| #include "espresso.h" |
| |
| pcover make_sparse(F, D, R) |
| pcover F, D, R; |
| { |
| cost_t cost, best_cost; |
| |
| cover_cost(F, &best_cost); |
| |
| do { |
| EXECUTE(F = mv_reduce(F, D), MV_REDUCE_TIME, F, cost); |
| if (cost.total == best_cost.total) |
| break; |
| copy_cost(&cost, &best_cost); |
| |
| EXECUTE(F = expand(F, R, TRUE), RAISE_IN_TIME, F, cost); |
| if (cost.total == best_cost.total) |
| break; |
| copy_cost(&cost, &best_cost); |
| } while (force_irredundant); |
| |
| return F; |
| } |
| |
| /* |
| mv_reduce -- perform an "optimal" reduction of the variables which |
| we desire to be sparse |
| |
| This could be done using "reduce" and then saving just the desired |
| part of the reduction. Instead, this version uses IRRED to find |
| which cubes of an output are redundant. Note that this gets around |
| the cube-ordering problem. |
| |
| In normal use, it is expected that the cover is irredundant and |
| hence no cubes will be reduced to the empty cube (however, this is |
| checked for and such cubes will be deleted) |
| */ |
| |
| pcover |
| mv_reduce(F, D) |
| pcover F, D; |
| { |
| register int i, var; |
| register pcube p, p1, last; |
| int index; |
| pcover F1, D1; |
| pcube *F_cube_table; |
| |
| /* loop for each multiple-valued variable */ |
| for(var = 0; var < cube.num_vars; var++) { |
| |
| if (cube.sparse[var]) { |
| |
| /* loop for each part of the variable */ |
| for(i = cube.first_part[var]; i <= cube.last_part[var]; i++) { |
| |
| /* remember mapping of F1 cubes back to F cubes */ |
| F_cube_table = ALLOC(pcube, F->count); |
| |
| /* 'cofactor' against part #i of variable #var */ |
| F1 = new_cover(F->count); |
| foreach_set(F, last, p) { |
| if (is_in_set(p, i)) { |
| F_cube_table[F1->count] = p; |
| p1 = GETSET(F1, F1->count++); |
| (void) set_diff(p1, p, cube.var_mask[var]); |
| set_insert(p1, i); |
| } |
| } |
| |
| /* 'cofactor' against part #i of variable #var */ |
| /* not really necessary -- just more efficient ? */ |
| D1 = new_cover(D->count); |
| foreach_set(D, last, p) { |
| if (is_in_set(p, i)) { |
| p1 = GETSET(D1, D1->count++); |
| (void) set_diff(p1, p, cube.var_mask[var]); |
| set_insert(p1, i); |
| } |
| } |
| |
| mark_irredundant(F1, D1); |
| |
| /* now remove part i from cubes which are redundant */ |
| index = 0; |
| foreach_set(F1, last, p1) { |
| if (! TESTP(p1, ACTIVE)) { |
| p = F_cube_table[index]; |
| |
| /* don't reduce a variable which is full |
| * (unless it is the output variable) |
| */ |
| if (var == cube.num_vars-1 || |
| ! setp_implies(cube.var_mask[var], p)) { |
| set_remove(p, i); |
| } |
| RESET(p, PRIME); |
| } |
| index++; |
| } |
| |
| free_cover(F1); |
| free_cover(D1); |
| FREE(F_cube_table); |
| } |
| } |
| } |
| |
| /* Check if any cubes disappeared */ |
| (void) sf_active(F); |
| for(var = 0; var < cube.num_vars; var++) { |
| if (cube.sparse[var]) { |
| foreach_active_set(F, last, p) { |
| if (setp_disjoint(p, cube.var_mask[var])) { |
| RESET(p, ACTIVE); |
| F->active_count--; |
| } |
| } |
| } |
| } |
| |
| if (F->count != F->active_count) { |
| F = sf_inactive(F); |
| } |
| return F; |
| } |