blob: a7ad9657a40703a42aefc77be134563fb5b564ac [file] [edit]
#include "internal.hpp"
namespace CaDiCaL {
/*------------------------------------------------------------------------*/
// Implements a variant of elimination with a much lower limit to be run as
// preprocessing. See elim for comments
/*------------------------------------------------------------------------*/
// Flush garbage clause, check fast elimination limits and return number of
// remaining occurrences (or 'fastelimbound + 1' if some limit was hit).
int64_t Internal::flush_elimfast_occs (int lit) {
const int64_t occslim = opts.fastelimocclim;
const int64_t clslim = opts.fastelimclslim;
const int64_t failed = occslim + 1;
Occs &os = occs (lit);
const const_occs_iterator end = os.end ();
occs_iterator j = os.begin (), i = j;
int64_t res = 0;
while (i != end) {
Clause *c = *i++;
if (c->collect ())
continue;
*j++ = c;
if (c->size > clslim) {
res = failed;
break;
}
if (++res > occslim) {
assert (opts.fastelimbound < 0 || res == failed);
break;
}
}
if (i != j) {
while (i != end)
*j++ = *i++;
os.resize (j - os.begin ());
shrink_occs (os);
}
return res;
}
/*------------------------------------------------------------------------*/
// 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::elimfast_resolvents_are_bounded (Eliminator &eliminator,
int pivot) {
assert (eliminator.gates.empty ());
assert (!eliminator.definition_unit);
stats.eliminate_tried++;
assert (!unsat);
assert (active (pivot));
const Occs &ps = occs (pivot);
const Occs &ns = occs (-pivot);
// 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 ()));
int64_t pos = ps.size ();
int64_t neg = ns.size ();
int64_t bound = opts.fastelimbound;
if (!pos || !neg)
return bound >= 0;
const int64_t sum = pos + neg;
const int64_t product = pos * neg;
if (bound > sum)
bound = sum;
LOG ("checking number resolvents on %d bounded by "
"%" PRId64 " = %" PRId64 " + %" PRId64 " + %d",
pivot, bound, pos, neg, opts.fastelimbound);
if (product <= bound) {
LOG ("fast elimination occurrence limits sufficiently small enough");
return true;
}
// 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.
for (const auto &c : ps) {
if (terminated_asynchronously ())
return false;
++eliminator.ticks;
assert (!c->redundant);
if (c->garbage)
continue;
for (const auto &d : ns) {
++eliminator.ticks;
assert (!d->redundant);
if (d->garbage)
continue;
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.fastelimclslim) {
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;
else if (terminated_asynchronously ())
return false;
}
}
LOG ("need %" PRId64 " <= %" PRId64 " non-tautological resolvents",
resolvents, bound);
return true;
}
/*------------------------------------------------------------------------*/
/*------------------------------------------------------------------------*/
// Add all resolvents on 'pivot' and connect them.
inline void Internal::elimfast_add_resolvents (Eliminator &eliminator,
int pivot) {
assert (eliminator.gates.empty ());
assert (!eliminator.definition_unit);
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) {
++eliminator.ticks;
if (unsat)
break;
if (d->garbage)
continue;
// Similar to elim (see the comment there), we cannot propagate
// eagerly. This means that we miss more units than in elim due
// to the `product <= bound` path.
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);
}
/*------------------------------------------------------------------------*/
// Try to eliminate 'pivot' by bounded variable elimination.
void Internal::try_to_fasteliminate_variable (Eliminator &eliminator,
int pivot,
bool &deleted_binary_clause) {
if (!active (pivot))
return;
assert (!frozen (pivot));
// First flush garbage clauses and check limits.
const int64_t occ_bound = opts.fastelimocclim;
int64_t bound = opts.fastelimbound;
int64_t pos = flush_elimfast_occs (pivot);
int64_t neg = flush_elimfast_occs (-pivot);
if (neg && pos > occ_bound) {
LOG ("too many occurrences thus not eliminated %d", pivot);
assert (!eliminator.schedule.contains (abs (pivot)));
return;
}
if (pos && neg > occ_bound) {
LOG ("too many occurrences thus not eliminated %d", -pivot);
assert (!eliminator.schedule.contains (abs (pivot)));
return;
}
const int64_t product = pos * neg;
const int64_t sum = pos + neg;
if (bound > sum)
bound = sum;
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);
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 (!unsat && !val (pivot)) {
if (product <= bound ||
elimfast_resolvents_are_bounded (eliminator, pivot)) {
LOG ("number of resolvents on %d are bounded", pivot);
elimfast_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);
}
/*------------------------------------------------------------------------*/
// 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::elimfast_round (bool &completed,
bool &deleted_binary_clause) {
assert (opts.fastelim);
assert (!unsat);
if (terminated_asynchronously ())
return 0;
MODE_SCOPE_SIMPLIFY (ELIM);
PROFILE_SCOPE_SIMPLIFY (fastelim);
stats.eliminate_fast_rounds++;
assert (!level);
int64_t resolution_limit;
if (opts.elimlimited) {
int64_t delta = stats.propagations_search;
delta *= opts.elimeffort;
if (delta < opts.elimmineff)
delta = opts.elimmineff;
if (delta > opts.elimmaxeff)
delta = opts.elimmaxeff;
PHASE ("fastelim-round", stats.eliminate_fast_rounds,
"limit of %" PRId64 " resolutions", delta);
resolution_limit = stats.eliminate_resolved + delta;
} else {
PHASE ("fastelim-round", stats.eliminate_fast_rounds,
"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 (terminated_asynchronously ())
break;
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.fastelimfactor && 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 ("fastelim-round", stats.eliminate_fast_rounds,
"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.
//
const int64_t garbage_limit =
(2 * stats.irredundant_literals / 3) + (1 << 20);
// 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_fasteliminate_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 ();
PHASE ("fastelim-round", stats.eliminate_fast_rounds,
"tried to eliminate %" PRId64 " variables %.0f%% (%zd remain)",
tried, percent (tried, scheduled), schedule.size ());
schedule.erase ();
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;
stats.vars_all_elim_fast += eliminated;
stats.ticks_fastelim += eliminator.ticks;
stats.ticks += eliminator.ticks;
#ifndef QUIET
int64_t resolutions = stats.eliminate_resolved - old_resolutions;
PHASE ("fastelim-round", stats.eliminate_fast_rounds,
"eliminated %d variables %.0f%% in %" PRId64 " resolutions",
eliminated, percent (eliminated, scheduled), resolutions);
#endif
const int units = stats.vars_all_fixed - old_fixed;
report ('e', !opts.reportall && !(eliminated + units));
return eliminated; // non-zero if successful
}
/*------------------------------------------------------------------------*/
void Internal::elimfast () {
if (!opts.fastelim)
return;
if (unsat)
return;
if (terminated_asynchronously ())
return;
if (level)
backtrack ();
if (!propagate ()) {
learn_empty_clause ();
return;
}
stats.eliminate_fast_phases++;
PHASE ("fastelim-phase", stats.eliminate_fast_phases,
"starting at most %d elimination rounds", opts.fastelimrounds);
if (external_prop) {
assert (!level);
private_steps = true;
}
#ifndef QUIET
int old_active_variables = active ();
int old_eliminated = stats.vars_all_elim;
#endif
reset_watches (); // saves lots of memory
// 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;
while (!unsat && !phase_complete && !terminated_asynchronously ()) {
#ifndef QUIET
int eliminated =
#endif
elimfast_round (round_complete, deleted_binary_clause);
if (!round_complete) {
PHASE ("fastelim-phase", stats.eliminate_phases,
"last round %d incomplete %s", round,
eliminated ? "but successful" : "and unsuccessful");
assert (!phase_complete);
break;
}
if (round++ >= opts.fastelimrounds) {
PHASE ("fastelim-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;
// Was not able to generate new variable elimination candidates after
// variable elimination round, neither through subsumption, nor blocked,
// nor covered clause elimination.
//
PHASE ("fastelim-phase", stats.eliminate_phases,
"no new variable elimination candidates");
assert (round_complete);
phase_complete = true;
}
for (auto idx : vars) {
if (active (idx))
flags (idx).elim = true;
}
if (phase_complete) {
stats.eliminate_complete++;
PHASE ("fastelim-phase", stats.eliminate_phases,
"fully completed elimination %" PRId64
" at elimination bound %" PRId64 "",
stats.eliminate_complete, lim.elimbound);
} else {
PHASE ("fastelim-phase", stats.eliminate_phases,
"incomplete elimination %" PRId64
" at elimination bound %" PRId64 "",
stats.eliminate_complete + 1, lim.elimbound);
}
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 ();
}
}
#ifndef QUIET
eliminated = stats.vars_all_elim - old_eliminated;
PHASE ("fastelim-phase", stats.eliminate_phases,
"eliminated %d variables %.2f%%", eliminated,
percent (eliminated, old_active_variables));
#endif
if (external_prop) {
assert (!level);
private_steps = false;
}
}
} // namespace CaDiCaL