| #include "citten.h" | |
| #include "internal.hpp" | |
| namespace CaDiCaL { | |
| /*------------------------------------------------------------------------*/ | |
| // Implements a variant of bounded variable elimination as originally | |
| // described in our SAT'05 paper introducing 'SATeLite'. This is an | |
| // inprocessing version, i.e., it is interleaved with search and triggers | |
| // subsumption and strengthening, blocked and covered clause elimination | |
| // during elimination rounds. It focuses only those variables which | |
| // occurred in removed irredundant clauses since the last time an | |
| // elimination round was run. By bounding the maximum resolvent size we can | |
| // run each elimination round until completion. See the code of 'elim' for | |
| // how elimination rounds are interleaved with blocked clause elimination | |
| // and subsumption (which in turn also calls vivification and transitive | |
| // reduction of the binary implication graph). | |
| /*------------------------------------------------------------------------*/ | |
| inline double Internal::compute_elim_score (unsigned alit) { | |
| assert (1 <= alit), assert (alit <= (unsigned) max_var); | |
| const int not_lit = -(int) alit; | |
| const double pos = noccs (alit); | |
| const double neg = noccs (-not_lit); | |
| if (!pos) | |
| return -neg; | |
| if (!neg) | |
| return -pos; | |
| double sum = 0, prod = 0; | |
| if (opts.elimsum) | |
| sum = opts.elimsum * (pos + neg); | |
| if (opts.elimprod) | |
| prod = opts.elimprod * (pos * neg); | |
| return prod + sum; | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| bool elim_more::operator() (unsigned a, unsigned b) { | |
| const auto s = internal->compute_elim_score (a); | |
| const auto t = internal->compute_elim_score (b); | |
| if (s > t) | |
| return true; | |
| if (s < t) | |
| return false; | |
| return a > b; | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| // Note that the new fast subsumption algorithm implemented in 'subsume' | |
| // does not distinguish between irredundant and redundant clauses and is | |
| // also run during search to strengthen and remove 'sticky' redundant | |
| // clauses but also irredundant ones. So beside learned units during search | |
| // or as consequence of other preprocessors, these subsumption rounds during | |
| // search can remove (irredundant) clauses (and literals), which in turn | |
| // might make new bounded variable elimination possible. This is tested | |
| // in the 'bool ineliminating ()' guard. | |
| bool Internal::ineliminating () { | |
| if (!opts.elim) | |
| return false; | |
| if (!preprocessing && !opts.inprocessing) | |
| return false; | |
| if (preprocessing) | |
| assert (lim.preprocessing); | |
| // Respect (increasing) conflict limit. | |
| // | |
| if (lim.elim >= stats.conflicts) | |
| return false; | |
| // Wait until there are new units or new removed variables | |
| // (in removed or shrunken irredundant clauses and thus marked). | |
| // | |
| if (last.elim.fixed < stats.vars_all_fixed) | |
| return true; | |
| if (last.elim.marked < stats.mark_elim) | |
| return true; | |
| // VERBOSE (3, "elim not scheduled due to fixpoint"); | |
| return false; | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| // Update the global elimination schedule after adding or removing a clause. | |
| void Internal::elim_update_added_clause (Eliminator &eliminator, | |
| Clause *c) { | |
| assert (!c->redundant); | |
| ElimSchedule &schedule = eliminator.schedule; | |
| ++eliminator.ticks; | |
| for (const auto &lit : *c) { | |
| if (!active (lit)) | |
| continue; | |
| occs (lit).push_back (c); | |
| if (frozen (lit)) | |
| continue; | |
| noccs (lit)++; | |
| const int idx = abs (lit); | |
| if (schedule.contains (idx)) | |
| schedule.update (idx); | |
| } | |
| } | |
| void Internal::elim_update_removed_lit (Eliminator &eliminator, int lit) { | |
| if (!active (lit)) | |
| return; | |
| if (frozen (lit)) | |
| return; | |
| if (!opts.elimfactor && flags (lit).factored) | |
| return; | |
| uint64_t &score = noccs (lit); | |
| assert (score > 0); | |
| score--; | |
| const int idx = abs (lit); | |
| ElimSchedule &schedule = eliminator.schedule; | |
| if (schedule.contains (idx)) | |
| schedule.update (idx); | |
| else { | |
| LOG ("rescheduling %d for elimination after removing clause", idx); | |
| schedule.push_back (idx); | |
| } | |
| } | |
| void Internal::elim_update_removed_clause (Eliminator &eliminator, | |
| Clause *c, int except) { | |
| assert (!c->redundant); | |
| ++eliminator.ticks; | |
| for (const auto &lit : *c) { | |
| if (lit == except) | |
| continue; | |
| assert (lit != -except); | |
| elim_update_removed_lit (eliminator, lit); | |
| } | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| // Since we do not have watches we have to do our own unit propagation | |
| // during elimination as soon we find a unit clause. This finds new units | |
| // and also marks clauses satisfied by those units as garbage immediately. | |
| void Internal::elim_propagate (Eliminator &eliminator, int root) { | |
| assert (val (root) > 0); | |
| vector<int> work; | |
| size_t i = 0; | |
| work.push_back (root); | |
| while (i < work.size ()) { | |
| int lit = work[i++]; | |
| LOG ("elimination propagation of %d", lit); | |
| assert (val (lit) > 0); | |
| const Occs &ns = occs (-lit); | |
| eliminator.ticks += 1 + cache_lines (ns.size (), sizeof (ns.begin ())); | |
| for (const auto &c : ns) { | |
| if (c->garbage) | |
| continue; | |
| int unit = 0, satisfied = 0; | |
| ++eliminator.ticks; | |
| for (const auto &other : *c) { | |
| const signed char tmp = val (other); | |
| if (tmp < 0) | |
| continue; | |
| if (tmp > 0) { | |
| satisfied = other; | |
| break; | |
| } | |
| if (unit) | |
| unit = INT_MIN; | |
| else | |
| unit = other; | |
| } | |
| if (satisfied) { | |
| LOG (c, "elimination propagation of %d finds %d satisfied", lit, | |
| satisfied); | |
| elim_update_removed_clause (eliminator, c, satisfied); | |
| mark_garbage (c); | |
| } else if (!unit) { | |
| LOG ("empty clause during elimination propagation of %d", lit); | |
| // need to set conflict = c for lrat | |
| conflict = c; | |
| learn_empty_clause (); | |
| conflict = 0; | |
| break; | |
| } else if (unit != INT_MIN) { | |
| LOG ("new unit %d during elimination propagation of %d", unit, lit); | |
| build_chain_for_units (unit, c, 0); | |
| assign_unit (unit); | |
| work.push_back (unit); | |
| } | |
| } | |
| if (unsat) | |
| break; | |
| const Occs &ps = occs (lit); | |
| eliminator.ticks += 1 + cache_lines (ps.size (), sizeof (ps.begin ())); | |
| for (const auto &c : ps) { | |
| if (c->garbage) | |
| continue; | |
| LOG (c, "elimination propagation of %d produces satisfied", lit); | |
| elim_update_removed_clause (eliminator, c, lit); | |
| mark_garbage (c); | |
| } | |
| } | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| // On-the-fly self-subsuming resolution during variable elimination is due | |
| // to HyoJung Han, Fabio Somenzi, SAT'09. Basically while resolving two | |
| // clauses we test the resolvent to be smaller than one of the antecedents. | |
| // If this is the case the pivot can be removed from the antecedent | |
| // on-the-fly and the resolution can be skipped during elimination. | |
| void Internal::elim_on_the_fly_self_subsumption (Eliminator &eliminator, | |
| Clause *c, int pivot) { | |
| LOG (c, "pivot %d on-the-fly self-subsuming resolution", pivot); | |
| stats.eliminate_otf_str++; | |
| stats.strengthened++; | |
| assert (clause.empty ()); | |
| ++eliminator.ticks; | |
| for (const auto &lit : *c) { | |
| if (lit == pivot) | |
| continue; | |
| const signed char tmp = val (lit); | |
| assert (tmp <= 0); | |
| if (tmp < 0) | |
| continue; | |
| clause.push_back (lit); | |
| } | |
| Clause *r = new_resolved_irredundant_clause (); | |
| elim_update_added_clause (eliminator, r); | |
| clause.clear (); | |
| lrat_chain.clear (); | |
| elim_update_removed_clause (eliminator, c, pivot); | |
| mark_garbage (c); | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| // Resolve two clauses on the pivot literal 'pivot', which is assumed to | |
| // occur in opposite phases in 'c' and 'd'. The actual resolvent is stored | |
| // in the temporary global 'clause' if it is not redundant. It is | |
| // considered redundant if one of the clauses is already marked as garbage | |
| // it is root level satisfied, the resolvent is empty, a unit, or produces a | |
| // self-subsuming resolution, which results in the pivot to be removed from | |
| // at least one of the antecedents. | |
| // Note that current root level assignments are taken into account, i.e., by | |
| // removing root level falsified literals. The function returns true if the | |
| // resolvent is not redundant and for instance has to be taken into account | |
| // during bounded variable elimination. | |
| // Detected units are immediately assigned and in case the last argument is | |
| // true also propagated eagerly in a elimination specific propagation | |
| // routine, which not only finds units but also updates the schedule. | |
| // When this function is called during computation of the number of | |
| // non-trivial (or non-satisfied) resolvents we can eagerly propagate units. | |
| // But during actually adding the resolvents this results in problems as we | |
| // found one rare test case '../test/trace/reg0056.trace' (out of billions), | |
| // where the pivot itself was assigned during such a propagation while | |
| // adding resolvents and lead to pushing a clause to the reconstruction | |
| // stack that later flipped the value of the pivot (while all other literals | |
| // in that clause were unit implied too). Not pushing the pivot clauses to | |
| // the reconstruction stack produced a wrong model too. Our fix is to only | |
| // eagerly propagate during computation of the number of resolvents and | |
| // otherwise delay propagation until the end of elimination (which is less | |
| // precise regarding scheduling but very rarely happens). | |
| bool Internal::resolve_clauses (Eliminator &eliminator, Clause *c, | |
| int pivot, Clause *d, | |
| const bool propagate_eagerly, | |
| const bool keep_chain) { | |
| assert (!c->redundant); | |
| assert (!d->redundant); | |
| eliminator.ticks += 2; // access of the 2 clauses | |
| stats.eliminate_resolved++; | |
| if (c->garbage || d->garbage) | |
| return false; | |
| if (c->size > d->size) { | |
| pivot = -pivot; | |
| swap (c, d); | |
| } | |
| assert (!level); | |
| assert (clause.empty ()); | |
| int satisfied = 0; // Contains this satisfying literal. | |
| int tautological = 0; // Clashing literal if tautological. | |
| int s = 0; // Actual literals from 'c'. | |
| int t = 0; // Actual literals from 'd'. | |
| // First determine whether the first antecedent is satisfied, add its | |
| // literals to 'clause' and mark them (except for 'pivot'). | |
| // | |
| for (const auto &lit : *c) { | |
| if (lit == pivot) { | |
| s++; | |
| continue; | |
| } | |
| assert (lit != -pivot); | |
| const signed char tmp = val (lit); | |
| if (tmp > 0) { | |
| satisfied = lit; | |
| break; | |
| } else if (tmp < 0) { | |
| if (!lrat) | |
| continue; | |
| Flags &f = flags (lit); | |
| if (f.seen) | |
| continue; | |
| analyzed.push_back (lit); | |
| f.seen = true; | |
| int64_t id = unit_id (-lit); | |
| lrat_chain.push_back (id); | |
| continue; | |
| } else | |
| mark (lit), clause.push_back (lit), s++; | |
| } | |
| if (satisfied) { | |
| LOG (c, "satisfied by %d antecedent", satisfied); | |
| elim_update_removed_clause (eliminator, c, satisfied); | |
| mark_garbage (c); | |
| clause.clear (); | |
| lrat_chain.clear (); | |
| clear_analyzed_literals (); | |
| unmark (c); | |
| return false; | |
| } | |
| // Then determine whether the second antecedent is satisfied, add its | |
| // literal to 'clause' and check whether a clashing literal is found, such | |
| // that the resolvent would be tautological. | |
| // | |
| for (const auto &lit : *d) { | |
| if (lit == -pivot) { | |
| t++; | |
| continue; | |
| } | |
| assert (lit != pivot); | |
| signed char tmp = val (lit); | |
| if (tmp > 0) { | |
| satisfied = lit; | |
| break; | |
| } else if (tmp < 0) { | |
| if (!lrat) | |
| continue; | |
| Flags &f = flags (lit); | |
| if (f.seen) | |
| continue; | |
| analyzed.push_back (lit); | |
| f.seen = true; | |
| int64_t id = unit_id (-lit); | |
| lrat_chain.push_back (id); | |
| continue; | |
| } else if ((tmp = marked (lit)) < 0) { | |
| tautological = lit; | |
| break; | |
| } else if (!tmp) | |
| clause.push_back (lit), t++; | |
| else | |
| assert (tmp > 0), t++; | |
| } | |
| clear_analyzed_literals (); | |
| unmark (c); | |
| const int64_t size = clause.size (); | |
| if (lrat) { | |
| lrat_chain.push_back (d->id); | |
| lrat_chain.push_back (c->id); | |
| } | |
| if (satisfied) { | |
| LOG (d, "satisfied by %d antecedent", satisfied); | |
| elim_update_removed_clause (eliminator, d, satisfied); | |
| mark_garbage (d); | |
| clause.clear (); | |
| lrat_chain.clear (); | |
| return false; | |
| } | |
| LOG (c, "first antecedent"); | |
| LOG (d, "second antecedent"); | |
| if (tautological) { | |
| clause.clear (); | |
| LOG ("resolvent tautological on %d", tautological); | |
| lrat_chain.clear (); | |
| return false; | |
| } | |
| if (!size) { | |
| clause.clear (); | |
| LOG ("empty resolvent"); | |
| learn_empty_clause (); // already clears lrat_chain. | |
| return false; | |
| } | |
| if (size == 1) { | |
| int unit = clause[0]; | |
| LOG ("unit resolvent %d", unit); | |
| clause.clear (); | |
| assign_unit (unit); // already clears lrat_chain. | |
| if (propagate_eagerly) | |
| elim_propagate (eliminator, unit); | |
| return false; | |
| } | |
| LOG (clause, "resolvent"); | |
| assert (!lrat || !lrat_chain.empty ()); | |
| // Double self-subsuming resolution. The clauses 'c' and 'd' are | |
| // identical except for the pivot which occurs in different phase. The | |
| // resolvent subsumes both antecedents. | |
| if (s > size && t > size) { | |
| assert (s == size + 1); | |
| assert (t == size + 1); | |
| clause.clear (); | |
| // LRAT is c + d (+ eventual units) | |
| elim_on_the_fly_self_subsumption (eliminator, c, pivot); | |
| LOG (d, "double pivot %d on-the-fly self-subsuming resolution", -pivot); | |
| stats.eliminate_otf_sub++; | |
| stats.subsumed++; | |
| elim_update_removed_clause (eliminator, d, -pivot); | |
| mark_garbage (d); | |
| return false; | |
| } | |
| // Single self-subsuming resolution: The pivot can be removed from 'c', | |
| // which is implemented by adding a clause which is the same as 'c' but | |
| // with 'pivot' removed and then marking 'c' as garbage. | |
| if (s > size) { | |
| assert (s == size + 1); | |
| clause.clear (); | |
| // LRAT is c + d (+ eventual units) | |
| elim_on_the_fly_self_subsumption (eliminator, c, pivot); | |
| return false; | |
| } | |
| // Same single self-subsuming resolution situation, but only for 'd'. | |
| if (t > size) { | |
| assert (t == size + 1); | |
| clause.clear (); | |
| // LRAT is c + d (+ eventual units) -> same. | |
| elim_on_the_fly_self_subsumption (eliminator, d, -pivot); | |
| return false; | |
| } | |
| if (!keep_chain) | |
| lrat_chain.clear (); | |
| return true; | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| // Check whether the number of non-tautological resolvents on 'pivot' is | |
| // smaller or equal to the number of clauses with 'pivot' or '-pivot'. This | |
| // is the main criteria of bounded variable elimination. As a side effect | |
| // it flushes garbage clauses with that variable, sorts its occurrence lists | |
| // (smallest clauses first) and also negates pivot if it has more positive | |
| // than negative occurrences. | |
| bool Internal::elim_resolvents_are_bounded (Eliminator &eliminator, | |
| int pivot) { | |
| const bool substitute = !eliminator.gates.empty (); | |
| const bool resolve_gates = eliminator.definition_unit; | |
| if (substitute) | |
| LOG ("trying to substitute %d", pivot); | |
| stats.eliminate_tried++; | |
| assert (!unsat); | |
| assert (active (pivot)); | |
| const Occs &ps = occs (pivot); | |
| const Occs &ns = occs (-pivot); | |
| const int64_t pos = ps.size (); | |
| const int64_t neg = ns.size (); | |
| if (!pos || !neg) | |
| return lim.elimbound >= 0; | |
| const int64_t bound = pos + neg + lim.elimbound; | |
| LOG ("checking number resolvents on %d bounded by " | |
| "%" PRId64 " = %" PRId64 " + %" PRId64 " + %" PRId64, | |
| pivot, bound, pos, neg, lim.elimbound); | |
| // Try all resolutions between a positive occurrence (outer loop) of | |
| // 'pivot' and a negative occurrence of 'pivot' (inner loop) as long the | |
| // bound on non-tautological resolvents is not hit and the size of the | |
| // generated resolvents does not exceed the resolvent clause size limit. | |
| int64_t resolvents = 0; // Non-tautological resolvents. | |
| // loose assumption: stays in cache | |
| eliminator.ticks += 1 + cache_lines (ps.size (), sizeof (ps.begin ())); | |
| eliminator.ticks += 1 + cache_lines (ns.size (), sizeof (ns.begin ())); | |
| for (const auto &c : ps) { | |
| ++eliminator.ticks; | |
| assert (!c->redundant); | |
| if (c->garbage) | |
| continue; | |
| if (c->size > opts.elimclslim) | |
| return false; | |
| for (const auto &d : ns) { | |
| ++eliminator.ticks; | |
| assert (!d->redundant); | |
| if (d->garbage) | |
| continue; | |
| if (!resolve_gates && substitute && c->gate == d->gate) | |
| continue; | |
| if (d->size > opts.elimclslim) | |
| return false; | |
| stats.eliminate_tried_res++; | |
| if (resolve_clauses (eliminator, c, pivot, d, true, false)) { | |
| resolvents++; | |
| int size = clause.size (); | |
| clause.clear (); | |
| LOG ("now at least %" PRId64 | |
| " non-tautological resolvents on pivot %d", | |
| resolvents, pivot); | |
| if (size > opts.elimclslim) { | |
| LOG ("resolvent size %d too big after %" PRId64 | |
| " resolvents on %d", | |
| size, resolvents, pivot); | |
| return false; | |
| } | |
| if (resolvents > bound) { | |
| LOG ("too many non-tautological resolvents on %d", pivot); | |
| return false; | |
| } | |
| } else if (unsat) | |
| return false; | |
| else if (val (pivot)) | |
| return false; | |
| } | |
| } | |
| LOG ("need %" PRId64 " <= %" PRId64 " non-tautological resolvents", | |
| resolvents, bound); | |
| return true; | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| // Add all resolvents on 'pivot' and connect them. | |
| inline void Internal::elim_add_resolvents (Eliminator &eliminator, | |
| int pivot) { | |
| const bool substitute = !eliminator.gates.empty (); | |
| const bool resolve_gates = eliminator.definition_unit; | |
| stats.eliminated++; | |
| if (substitute) { | |
| LOG ("substituting pivot %d by resolving with %zd gate clauses", pivot, | |
| eliminator.gates.size ()); | |
| stats.eliminate_substituted++; | |
| } | |
| switch (eliminator.gatetype) { | |
| case EQUI: | |
| stats.eliminated_equivalent++; | |
| break; | |
| case AND: | |
| stats.eliminated_and++; | |
| break; | |
| case ITE: | |
| stats.eliminated_ite++; | |
| break; | |
| case XOR: | |
| stats.eliminated_xor++; | |
| break; | |
| case DEF: | |
| stats.eliminated_defs++; | |
| break; | |
| case NO: | |
| break; | |
| } | |
| LOG ("adding all resolvents on %d", pivot); | |
| assert (!val (pivot)); | |
| assert (!flags (pivot).eliminated ()); | |
| const Occs &ps = occs (pivot); | |
| const Occs &ns = occs (-pivot); | |
| eliminator.ticks += 1 + cache_lines (ps.size (), sizeof (ps.begin ())); | |
| eliminator.ticks += 1 + cache_lines (ns.size (), sizeof (ns.begin ())); | |
| #ifdef LOGGING | |
| int64_t resolvents = 0; | |
| #endif | |
| for (auto &c : ps) { | |
| ++eliminator.ticks; | |
| if (unsat) | |
| break; | |
| if (c->garbage) | |
| continue; | |
| for (auto &d : ns) { | |
| if (unsat) | |
| break; | |
| if (d->garbage) | |
| continue; | |
| if (!resolve_gates && substitute && c->gate == d->gate) | |
| continue; | |
| if (!resolve_clauses (eliminator, c, pivot, d, false, true)) | |
| continue; | |
| assert (!lrat || !lrat_chain.empty ()); | |
| Clause *r = new_resolved_irredundant_clause (); | |
| elim_update_added_clause (eliminator, r); | |
| eliminator.enqueue (r); | |
| lrat_chain.clear (); | |
| clause.clear (); | |
| #ifdef LOGGING | |
| resolvents++; | |
| #endif | |
| } | |
| } | |
| LOG ("added %" PRId64 " resolvents to eliminate %d", resolvents, pivot); | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| // Remove clauses with 'pivot' and '-pivot' by marking them as garbage and | |
| // push them on the extension stack. | |
| void Internal::mark_eliminated_clauses_as_garbage ( | |
| Eliminator &eliminator, int pivot, bool &deleted_binary_clause) { | |
| assert (!unsat); | |
| LOG ("marking irredundant clauses with %d as garbage", pivot); | |
| const int64_t substitute = eliminator.gates.size (); | |
| if (substitute) | |
| LOG ("pushing %" PRId64 " gate clauses on extension stack", substitute); | |
| #ifndef NDEBUG | |
| int64_t pushed = 0; | |
| #endif | |
| Occs &ps = occs (pivot); | |
| eliminator.ticks += 1 + cache_lines (ps.size (), sizeof (ps.begin ())); | |
| for (const auto &c : ps) { | |
| ++eliminator.ticks; | |
| if (c->garbage) | |
| continue; | |
| assert (!c->redundant); | |
| if (!substitute || c->gate) { | |
| if (proof) | |
| proof->weaken_minus (c); | |
| if (c->size == 2) | |
| deleted_binary_clause = true; | |
| external->push_clause_on_extension (pivot, c); | |
| #ifndef NDEBUG | |
| pushed++; | |
| #endif | |
| } | |
| mark_garbage (c); | |
| elim_update_removed_clause (eliminator, c, pivot); | |
| } | |
| erase_occs (ps); | |
| LOG ("marking irredundant clauses with %d as garbage", -pivot); | |
| Occs &ns = occs (-pivot); | |
| eliminator.ticks += 1 + cache_lines (ns.size (), sizeof (ns.begin ())); | |
| for (const auto &d : ns) { | |
| ++eliminator.ticks; | |
| if (d->garbage) | |
| continue; | |
| assert (!d->redundant); | |
| if (!substitute || d->gate) { | |
| if (proof) | |
| proof->weaken_minus (d); | |
| if (d->size == 2) | |
| deleted_binary_clause = true; | |
| external->push_clause_on_extension (-pivot, d); | |
| #ifndef NDEBUG | |
| pushed++; | |
| #endif | |
| } | |
| mark_garbage (d); | |
| elim_update_removed_clause (eliminator, d, -pivot); | |
| } | |
| erase_occs (ns); | |
| if (substitute) | |
| assert (pushed <= substitute); | |
| // Unfortunately, we can not use the trick by Niklas Soerensson anymore, | |
| // which avoids saving all clauses on the extension stack. This would | |
| // break our new incremental 'restore' logic. | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| // Try to eliminate 'pivot' by bounded variable elimination. | |
| void Internal::try_to_eliminate_variable (Eliminator &eliminator, int pivot, | |
| bool &deleted_binary_clause) { | |
| if (!active (pivot)) | |
| return; | |
| assert (!frozen (pivot)); | |
| // First flush garbage clauses. | |
| // | |
| int64_t pos = flush_occs (pivot); | |
| int64_t neg = flush_occs (-pivot); | |
| if (pos > neg) { | |
| pivot = -pivot; | |
| swap (pos, neg); | |
| } | |
| LOG ("pivot %d occurs positively %" PRId64 | |
| " times and negatively %" PRId64 " times", | |
| pivot, pos, neg); | |
| assert (!eliminator.schedule.contains (abs (pivot))); | |
| assert (pos <= neg); | |
| if (pos && neg > opts.elimocclim) { | |
| LOG ("too many occurrences thus not eliminated %d", pivot); | |
| assert (!eliminator.schedule.contains (abs (pivot))); | |
| return; | |
| } | |
| LOG ("trying to eliminate %d", pivot); | |
| assert (!flags (pivot).eliminated ()); | |
| // Sort occurrence lists, such that shorter clauses come first. | |
| Occs &ps = occs (pivot); | |
| stable_sort (ps.begin (), ps.end (), clause_smaller_size ()); | |
| Occs &ns = occs (-pivot); | |
| stable_sort (ns.begin (), ns.end (), clause_smaller_size ()); | |
| // loose approximation of ticks for sorting | |
| eliminator.ticks += 1 + cache_lines (ps.size (), sizeof (ps.begin ())); | |
| eliminator.ticks += 1 + cache_lines (ns.size (), sizeof (ns.begin ())); | |
| if (pos) | |
| find_gate_clauses (eliminator, pivot); | |
| if (!unsat && !val (pivot)) { | |
| if (elim_resolvents_are_bounded (eliminator, pivot)) { | |
| LOG ("number of resolvents on %d are bounded", pivot); | |
| elim_add_resolvents (eliminator, pivot); | |
| if (!unsat) | |
| mark_eliminated_clauses_as_garbage (eliminator, pivot, | |
| deleted_binary_clause); | |
| if (active (pivot)) | |
| mark_eliminated (pivot); | |
| } else { | |
| LOG ("too many resolvents on %d so not eliminated", pivot); | |
| } | |
| } | |
| unmark_gate_clauses (eliminator); | |
| elim_backward_clauses (eliminator); | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| void Internal::mark_redundant_clauses_with_eliminated_variables_as_garbage ( | |
| int64_t &ticks) { | |
| ticks += 1 + cache_lines (clauses.size (), sizeof (clauses.begin ())); | |
| for (const auto &c : clauses) { | |
| ++ticks; | |
| if (c->garbage || !c->redundant) | |
| continue; | |
| bool clean = true; | |
| for (const auto &lit : *c) { | |
| Flags &f = flags (lit); | |
| if (f.eliminated ()) { | |
| clean = false; | |
| break; | |
| } | |
| if (f.pure ()) { | |
| clean = false; | |
| break; | |
| } | |
| } | |
| if (!clean) | |
| mark_garbage (c); | |
| } | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| // This function performs one round of bounded variable elimination and | |
| // returns the number of eliminated variables. The additional result | |
| // 'completed' is true if this elimination round ran to completion (all | |
| // variables have been tried). Otherwise it was asynchronously terminated | |
| // or the resolution limit was hit. | |
| int Internal::elim_round (bool &completed, bool &deleted_binary_clause) { | |
| assert (opts.elim); | |
| assert (!unsat); | |
| MODE_SCOPE_SIMPLIFY (ELIM); | |
| PROFILE_SCOPE_SIMPLIFY (elim); | |
| stats.eliminations++; | |
| int64_t marked_before = last.elim.marked; | |
| last.elim.marked = stats.mark_elim; | |
| assert (!level); | |
| int64_t resolution_limit; | |
| if (opts.elimlimited) { | |
| int64_t delta = stats.propagations_search; | |
| delta *= 1e-3 * opts.elimeffort; | |
| if (delta < opts.elimmineff) | |
| delta = opts.elimmineff; | |
| if (delta > opts.elimmaxeff) | |
| delta = opts.elimmaxeff; | |
| delta = max (delta, (int64_t) 2l * active ()); | |
| PHASE ("elim-round", stats.eliminations, | |
| "limit of %" PRId64 " resolutions", delta); | |
| resolution_limit = stats.eliminate_resolved + delta; | |
| } else { | |
| PHASE ("elim-round", stats.eliminations, "resolutions unlimited"); | |
| resolution_limit = LONG_MAX; | |
| } | |
| init_noccs (); | |
| // First compute the number of occurrences of each literal and at the same | |
| // time mark satisfied clauses and update 'elim' flags of variables in | |
| // clauses with root level assigned literals (both false and true). | |
| // | |
| for (const auto &c : clauses) { | |
| if (c->garbage || c->redundant) | |
| continue; | |
| bool satisfied = false, falsified = false; | |
| for (const auto &lit : *c) { | |
| const signed char tmp = val (lit); | |
| if (tmp > 0) | |
| satisfied = true; | |
| else if (tmp < 0) | |
| falsified = true; | |
| else | |
| assert (active (lit)); | |
| } | |
| if (satisfied) | |
| mark_garbage (c); // forces more precise counts | |
| else { | |
| for (const auto &lit : *c) { | |
| if (!active (lit)) | |
| continue; | |
| if (falsified) | |
| mark_elim (lit); // simulate unit propagation | |
| noccs (lit)++; | |
| } | |
| } | |
| } | |
| init_occs (); | |
| Eliminator eliminator (this); | |
| ElimSchedule &schedule = eliminator.schedule; | |
| assert (schedule.empty ()); | |
| // Now find elimination candidates which occurred in clauses removed since | |
| // the last time we ran bounded variable elimination, which in turned | |
| // triggered their 'elim' bit to be set. | |
| // | |
| for (auto idx : vars) { | |
| if (!active (idx)) | |
| continue; | |
| if (frozen (idx)) | |
| continue; | |
| if (!flags (idx).elim) | |
| continue; | |
| if (!opts.elimfactor && flags (idx).factored) | |
| continue; | |
| LOG ("scheduling %d for elimination initially", idx); | |
| schedule.push_back (idx); | |
| } | |
| schedule.shrink (); | |
| #ifndef QUIET | |
| int64_t scheduled = schedule.size (); | |
| #endif | |
| PHASE ("elim-round", stats.eliminations, | |
| "scheduled %" PRId64 " variables %.0f%% for elimination", | |
| scheduled, percent (scheduled, active ())); | |
| // Connect irredundant clauses. | |
| for (const auto &c : clauses) { | |
| if (terminated_asynchronously ()) | |
| break; | |
| if (!c->garbage && !c->redundant) | |
| for (const auto &lit : *c) | |
| if (active (lit)) | |
| occs (lit).push_back (c); | |
| } | |
| #ifndef QUIET | |
| const int64_t old_resolutions = stats.eliminate_resolved; | |
| #endif | |
| const int old_eliminated = stats.vars_all_elim; | |
| const int old_fixed = stats.vars_all_fixed; | |
| // Limit on garbage literals during variable elimination. If the | |
| // limit is hit a garbage collection is performed. During | |
| // investigation we found that the current limit is never reached | |
| // during mobical, hence we introduced the `elimaggressiveGC` | |
| // option. However, this is not a useful option for users, hence we | |
| // made it debug only. | |
| // | |
| const int64_t garbage_limit = (2 * stats.irredundant_literals / 3) | |
| #ifndef NDEBUG | |
| + (opts.elimaggressiveGC ? 0 : 1 << 20); | |
| #else | |
| + (1 << 20); | |
| #endif | |
| // Main loops tries to eliminate variables according to the schedule. The | |
| // schedule is updated dynamically and variables are potentially | |
| // rescheduled to be tried again if they occur in a removed clause. | |
| // | |
| #ifndef QUIET | |
| int64_t tried = 0; | |
| #endif | |
| while (!unsat && !terminated_asynchronously () && | |
| stats.eliminate_resolved <= resolution_limit && | |
| !schedule.empty ()) { | |
| int idx = schedule.front (); | |
| schedule.pop_front (); | |
| flags (idx).elim = false; | |
| try_to_eliminate_variable (eliminator, idx, deleted_binary_clause); | |
| #ifndef QUIET | |
| tried++; | |
| #endif | |
| if (stats.garbage_literals <= garbage_limit) | |
| continue; | |
| mark_redundant_clauses_with_eliminated_variables_as_garbage ( | |
| eliminator.ticks); | |
| garbage_collection (); | |
| } | |
| // If the schedule is empty all variables have been tried (even | |
| // rescheduled ones). Otherwise asynchronous termination happened or we | |
| // ran into the resolution limit (or derived unsatisfiability). | |
| // | |
| completed = !schedule.size (); | |
| if (!completed) | |
| last.elim.marked = marked_before; | |
| PHASE ("elim-round", stats.eliminations, | |
| "tried to eliminate %" PRId64 " variables %.0f%% (%zd remain)", | |
| tried, percent (tried, scheduled), schedule.size ()); | |
| schedule.erase (); | |
| // Collect potential literal clause instantiation pairs, which needs full | |
| // occurrence lists and thus we have it here before resetting them. | |
| // | |
| Instantiator instantiator; | |
| if (!unsat && !terminated_asynchronously () && opts.instantiate) | |
| collect_instantiation_candidates (instantiator); | |
| reset_occs (); | |
| reset_noccs (); | |
| // Mark all redundant clauses with eliminated variables as garbage. | |
| // | |
| if (!unsat) | |
| mark_redundant_clauses_with_eliminated_variables_as_garbage ( | |
| eliminator.ticks); | |
| int eliminated = stats.vars_all_elim - old_eliminated; | |
| #ifndef QUIET | |
| int64_t resolutions = stats.eliminate_resolved - old_resolutions; | |
| PHASE ("elim-round", stats.eliminations, | |
| "eliminated %d variables %.0f%% in %" PRId64 " resolutions", | |
| eliminated, percent (eliminated, scheduled), resolutions); | |
| #endif | |
| stats.ticks_elim += eliminator.ticks; | |
| stats.ticks += eliminator.ticks; | |
| last.elim.subsumephases = stats.subsume_phases; | |
| const int units = stats.vars_all_fixed - old_fixed; | |
| report ('e', !opts.reportall && !(eliminated + units)); | |
| MODE_SCOPE_EARLY_EXIT (ELIM); | |
| PROFILE_SCOPE_EARLY_EXIT (elim); | |
| if (!unsat && !terminated_asynchronously () && | |
| instantiator) // Do we have candidate pairs? | |
| instantiate (instantiator); | |
| return eliminated; // non-zero if successful | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| // Increase elimination bound (additional clauses allowed during variable | |
| // elimination), which is triggered if elimination with last bound completed | |
| // (including no new subsumptions). This was pioneered by GlueMiniSAT in | |
| // the SAT Race 2015 and then picked up Chanseok Oh in his COMinisatPS | |
| // solver, which in turn is used in the Maple series of SAT solvers. | |
| // The bound is no increased if the maximum bound is reached. | |
| void Internal::increase_elimination_bound () { | |
| if (lim.elimbound >= opts.elimboundmax) | |
| return; | |
| if (lim.elimbound < 0) | |
| lim.elimbound = 0; | |
| else if (!lim.elimbound) | |
| lim.elimbound = 1; | |
| else | |
| lim.elimbound *= 2; | |
| if (lim.elimbound > opts.elimboundmax) | |
| lim.elimbound = opts.elimboundmax; | |
| PHASE ("elim-phase", stats.eliminate_phases, | |
| "new elimination bound %" PRId64 "", lim.elimbound); | |
| // Now reschedule all active variables for elimination again. | |
| // | |
| #ifdef LOGGING | |
| int count = 0; | |
| #endif | |
| for (auto idx : vars) { | |
| if (!active (idx)) | |
| continue; | |
| if (flags (idx).elim) | |
| continue; | |
| mark_elim (idx); | |
| #ifdef LOGGING | |
| count++; | |
| #endif | |
| } | |
| LOG ("marked %d variables as elimination candidates", count); | |
| report ('^'); | |
| } | |
| void Internal::init_citten () { | |
| if (!opts.elimdef) | |
| return; | |
| assert (!citten); | |
| citten = citten_init (); | |
| } | |
| void Internal::reset_citten () { | |
| if (citten) { | |
| citten_release (citten); | |
| citten = 0; | |
| } | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| void Internal::elim (bool update_limits) { | |
| if (unsat) | |
| return; | |
| if (terminated_asynchronously ()) | |
| return; | |
| if (level) | |
| backtrack (); | |
| if (!propagate ()) { | |
| learn_empty_clause (); | |
| return; | |
| } | |
| stats.eliminate_phases++; | |
| PHASE ("elim-phase", stats.eliminate_phases, | |
| "starting at most %d elimination rounds", opts.elimrounds); | |
| if (external_prop) { | |
| assert (!level); | |
| private_steps = true; | |
| } | |
| #ifndef QUIET | |
| int old_active_variables = active (); | |
| int old_eliminated = stats.vars_all_elim; | |
| #endif | |
| // Make sure there was a complete subsumption phase since last | |
| // elimination | |
| // | |
| if (last.elim.subsumephases == stats.subsume_phases) | |
| subsume (); | |
| reset_watches (); // saves lots of memory | |
| init_citten (); | |
| // Alternate one round of bounded variable elimination ('elim_round') | |
| // and subsumption ('subsume_round'), blocked ('block') and covered | |
| // clause elimination ('cover') until nothing changes, or the round | |
| // limit is hit. The loop also aborts early if no variable could be | |
| // eliminated, the empty clause is resolved, it is asynchronously | |
| // terminated or a resolution limit is hit. | |
| // This variable determines whether the whole loop of this bounded | |
| // variable elimination phase ('elim') ran until completion. This | |
| // potentially triggers an incremental increase of the elimination | |
| // bound. | |
| // | |
| bool phase_complete = false, deleted_binary_clause = false; | |
| int round = 1; | |
| #ifndef QUIET | |
| int eliminated = 0; | |
| #endif | |
| bool round_complete = false; | |
| try { | |
| while (!unsat && !phase_complete && !terminated_asynchronously ()) { | |
| #ifndef QUIET | |
| int eliminated = | |
| #endif | |
| elim_round (round_complete, deleted_binary_clause); | |
| if (!round_complete) { | |
| PHASE ("elim-phase", stats.eliminate_phases, | |
| "last round %d incomplete %s", round, | |
| eliminated ? "but successful" : "and unsuccessful"); | |
| assert (!phase_complete); | |
| break; | |
| } | |
| if (round++ >= opts.elimrounds) { | |
| PHASE ("elim-phase", stats.eliminate_phases, | |
| "round limit %d hit (%s)", round - 1, | |
| eliminated ? "though last round successful" | |
| : "last round unsuccessful anyhow"); | |
| assert (!phase_complete); | |
| break; | |
| } | |
| // Prioritize 'subsumption' over blocked and covered clause | |
| // elimination. | |
| if (subsume_round ()) | |
| continue; | |
| if (block ()) | |
| continue; | |
| if (cover ()) | |
| continue; | |
| // Was not able to generate new variable elimination candidates after | |
| // variable elimination round, neither through subsumption, nor | |
| // blocked, nor covered clause elimination. | |
| // | |
| PHASE ("elim-phase", stats.eliminate_phases, | |
| "no new variable elimination candidates"); | |
| assert (round_complete); | |
| phase_complete = true; | |
| } | |
| if (phase_complete) { | |
| stats.eliminate_complete++; | |
| PHASE ("elim-phase", stats.eliminate_phases, | |
| "fully completed elimination %" PRId64 | |
| " at elimination bound %" PRId64 "", | |
| stats.eliminate_complete, lim.elimbound); | |
| } else { | |
| PHASE ("elim-phase", stats.eliminate_phases, | |
| "incomplete elimination %" PRId64 | |
| " at elimination bound %" PRId64 "", | |
| stats.eliminate_complete + 1, lim.elimbound); | |
| } | |
| reset_citten (); | |
| } catch (std::bad_alloc &exception) { | |
| reset_citten (); | |
| throw exception; | |
| } | |
| if (deleted_binary_clause) | |
| delete_garbage_clauses (); | |
| init_watches (); | |
| connect_watches (); | |
| if (unsat) | |
| LOG ("elimination derived empty clause"); | |
| else if (propagated < trail.size ()) { | |
| LOG ("elimination produced %zd units", | |
| (size_t) (trail.size () - propagated)); | |
| if (!propagate ()) { | |
| LOG ("propagating units after elimination results in empty clause"); | |
| learn_empty_clause (); | |
| } | |
| } | |
| // If we ran variable elimination until completion we increase the | |
| // variable elimination bound and reschedule elimination of all variables. | |
| // | |
| if (phase_complete) | |
| increase_elimination_bound (); | |
| #ifndef QUIET | |
| eliminated = stats.vars_all_elim - old_eliminated; | |
| PHASE ("elim-phase", stats.eliminate_phases, | |
| "eliminated %d variables %.2f%%", eliminated, | |
| percent (eliminated, old_active_variables)); | |
| #endif | |
| if (external_prop) { | |
| assert (!level); | |
| private_steps = false; | |
| } | |
| if (!update_limits) | |
| return; | |
| int64_t delta = scale (opts.elimint * (stats.eliminate_phases + 1)); | |
| lim.elim = stats.conflicts + delta; | |
| PHASE ("elim-phase", stats.eliminate_phases, | |
| "new limit at %" PRId64 " conflicts after %" PRId64 " conflicts", | |
| lim.elim, delta); | |
| last.elim.fixed = stats.vars_all_fixed; | |
| } | |
| } // namespace CaDiCaL |