blob: dccd39774cbc2ca28d863a3cfee83dbc2c4db68f [file] [edit]
#include "internal.hpp"
namespace CaDiCaL {
/*------------------------------------------------------------------------*/
// This implements an inprocessing version of blocked clause elimination and
// is assumed to be triggered just before bounded variable elimination. It
// has a separate 'block' flag while variable elimination uses 'elim'.
// Thus it only tries to block clauses on a literal which was removed in an
// irredundant clause in negated form before and has not been tried to use
// as blocking literal since then.
/*------------------------------------------------------------------------*/
inline bool block_more_occs_size::operator() (unsigned a, unsigned b) {
size_t s = internal->noccs (-internal->u2i (a));
size_t t = internal->noccs (-internal->u2i (b));
if (s > t)
return true;
if (s < t)
return false;
s = internal->noccs (internal->u2i (a));
t = internal->noccs (internal->u2i (b));
if (s > t)
return true;
if (s < t)
return false;
return a > b;
}
/*------------------------------------------------------------------------*/
// Determine whether 'c' is blocked on 'lit', by first marking all its
// literals and then checking all resolvents with negative clauses (with
// '-lit') are tautological. We use a move-to-front scheme for both the
// occurrence list of negative clauses (with '-lit') and then for literals
// within each such clause. The clause move-to-front scheme has the goal to
// find non-tautological clauses faster in the future, while the literal
// move-to-front scheme has the goal to faster find the matching literal,
// which makes the resolvent tautological (again in the future).
bool Internal::is_blocked_clause (Clause *c, int lit) {
LOG (c, "trying to block on %d", lit);
assert (c->size >= opts.blockminclslim);
assert (c->size <= opts.blockmaxclslim);
assert (active (lit));
assert (!val (lit));
assert (!c->garbage);
assert (!c->redundant);
assert (!level);
mark (c); // First mark all literals in 'c'.
Occs &os = occs (-lit);
LOG ("resolving against at most %zd clauses with %d", os.size (), -lit);
bool res = true; // Result is true if all resolvents tautological.
// Can not use 'auto' here since we update 'os' during traversal.
//
const auto end_of_os = os.end ();
auto i = os.begin ();
Clause *prev_d = 0; // Previous non-tautological clause.
for (; i != end_of_os; i++) {
// Move the first clause with non-tautological resolvent to the front of
// the occurrence list to improve finding it faster later.
//
Clause *d = *i;
assert (!d->garbage);
assert (!d->redundant);
assert (d->size <= opts.blockmaxclslim);
*i = prev_d; // Move previous non-tautological clause
prev_d = d; // backwards but remember clause at this position.
LOG (d, "resolving on %d against", lit);
stats.blocked_resolutions++;
int prev_other = 0; // Previous non-tautological literal.
// No 'auto' since we update literals of 'd' during traversal.
//
const const_literal_iterator end_of_d = d->end ();
literal_iterator l;
for (l = d->begin (); l != end_of_d; l++) {
// Same move-to-front mechanism for literals within a clause. It
// moves the first negatively marked literal to the front to find it
// faster in the future.
//
const int other = *l;
*l = prev_other;
prev_other = other;
if (other == -lit)
continue;
assert (other != lit);
assert (active (other));
assert (!val (other));
if (marked (other) < 0) {
LOG ("found tautological literal %d", other);
d->literals[0] = other; // Move to front of 'd'.
break;
}
}
if (l == end_of_d) {
LOG ("no tautological literal found");
//
// Since we did not find a tautological literal we restore the old
// order of literals in the clause.
//
const const_literal_iterator begin_of_d = d->begin ();
while (l-- != begin_of_d) {
const int other = *l;
*l = prev_other;
prev_other = other;
}
res = false; // Now 'd' is a witness that 'c' is not blocked.
os[0] = d; // Move it to the front of the occurrence list.
break;
}
}
unmark (c); // ... all literals of the candidate clause.
// If all resolvents are tautological and thus the clause is blocked we
// restore the old order of clauses in the occurrence list of '-lit'.
//
if (res) {
assert (i == end_of_os);
const auto boc = os.begin ();
while (i != boc) {
Clause *d = *--i;
*i = prev_d;
prev_d = d;
}
}
return res;
}
/*------------------------------------------------------------------------*/
void Internal::block_schedule (Blocker &blocker) {
// Set skip flags for all literals in too large clauses.
//
for (const auto &c : clauses) {
if (c->garbage)
continue;
if (c->redundant)
continue;
if (c->size <= opts.blockmaxclslim)
continue;
for (const auto &lit : *c)
mark_skip (-lit);
}
// Connect all literal occurrences in irredundant clauses.
//
for (const auto &c : clauses) {
if (c->garbage)
continue;
if (c->redundant)
continue;
for (const auto &lit : *c) {
assert (active (lit));
assert (!val (lit));
occs (lit).push_back (c);
}
}
// We establish the invariant that 'noccs' gives the number of actual
// occurrences of 'lit' in non-garbage clauses, while 'occs' might still
// refer to garbage clauses, thus 'noccs (lit) <= occs (lit).size ()'. It
// is expensive to remove references to garbage clauses from 'occs' during
// blocked clause elimination, but decrementing 'noccs' is cheap.
for (auto lit : lits) {
if (!active (lit))
continue;
assert (!val (lit));
Occs &os = occs (lit);
noccs (lit) = os.size ();
}
// Now we fill the schedule (priority queue) of candidate literals to be
// tried as blocking literals. It is probably slightly faster to do this
// in one go after all occurrences have been determined, instead of
// filling the priority queue during pushing occurrences. Filling the
// schedule can not be fused with the previous loop (easily) since we
// first have to initialize 'noccs' for both 'lit' and '-lit'.
#ifndef QUIET
int skipped = 0;
#endif
for (auto idx : vars) {
if (!active (idx))
continue;
if (frozen (idx)) {
#ifndef QUIET
skipped += 2;
#endif
continue;
}
assert (!val (idx));
for (int sign = -1; sign <= 1; sign += 2) {
const int lit = sign * idx;
if (marked_skip (lit)) {
#ifndef QUIET
skipped++;
#endif
continue;
}
if (!marked_block (lit))
continue;
unmark_block (lit);
LOG ("scheduling %d with %" PRIu64 " positive and %" PRIu64
" negative occurrences",
lit, noccs (lit), noccs (-lit));
blocker.schedule.push_back (vlit (lit));
}
}
PHASE ("block", stats.blockings,
"scheduled %zd candidate literals %.2f%% (%d skipped %.2f%%)",
blocker.schedule.size (),
percent (blocker.schedule.size (), 2.0 * active ()), skipped,
percent (skipped, 2.0 * active ()));
}
/*------------------------------------------------------------------------*/
// A literal is pure if it only occurs positive. Then all clauses in which
// it occurs are blocked on it. This special case can be implemented faster
// than trying to block literals with at least one negative occurrence and
// is thus handled separately. It also allows to avoid pushing blocked
// clauses onto the extension stack.
void Internal::block_pure_literal (Blocker &blocker, int lit) {
if (frozen (lit))
return;
assert (active (lit));
Occs &pos = occs (lit);
Occs &nos = occs (-lit);
assert (!noccs (-lit));
#ifndef NDEBUG
for (const auto &c : nos)
assert (c->garbage);
#endif
stats.blocked_pure_literals++;
LOG ("found pure literal %d", lit);
#ifdef LOGGING
int64_t pured = 0;
#endif
for (const auto &c : pos) {
if (c->garbage)
continue;
assert (!c->redundant);
LOG (c, "pure literal %d in", lit);
blocker.reschedule.push_back (c);
if (proof) {
proof->weaken_minus (c);
}
external->push_clause_on_extension (lit, c);
stats.blocked_pure_clauses++;
mark_garbage (c);
#ifdef LOGGING
pured++;
#endif
}
erase_vector (pos);
erase_vector (nos);
mark_pure (lit);
stats.blocked_pure_clauses++;
LOG ("blocking %" PRId64 " clauses on pure literal %d", pured, lit);
}
/*------------------------------------------------------------------------*/
// If there is only one negative clause with '-lit' it is faster to mark it
// instead of marking all the positive clauses with 'lit' one after the
// other and then resolving against the negative clause.
void Internal::block_literal_with_one_negative_occ (Blocker &blocker,
int lit) {
assert (active (lit));
assert (!frozen (lit));
assert (noccs (lit) > 0);
assert (noccs (-lit) == 1);
Occs &nos = occs (-lit);
assert (nos.size () >= 1);
Clause *d = 0;
for (const auto &c : nos) {
if (c->garbage)
continue;
assert (!d);
d = c;
#ifndef NDEBUG
break;
#endif
}
assert (d);
nos.resize (1);
nos[0] = d;
if (d && d->size > opts.blockmaxclslim) {
LOG (d, "skipped common antecedent");
return;
}
assert (!d->garbage);
assert (!d->redundant);
assert (d->size <= opts.blockmaxclslim);
LOG (d, "common %d antecedent", lit);
mark (d);
int64_t blocked = 0;
#ifdef LOGGING
int64_t skipped = 0;
#endif
Occs &pos = occs (lit);
// Again no 'auto' since 'pos' is update during traversal.
//
const auto eop = pos.end ();
auto j = pos.begin (), i = j;
for (; i != eop; i++) {
Clause *c = *j++ = *i;
if (c->garbage) {
j--;
continue;
}
if (c->size > opts.blockmaxclslim) {
#ifdef LOGGING
skipped++;
#endif
continue;
}
if (c->size < opts.blockminclslim) {
#ifdef LOGGING
skipped++;
#endif
continue;
}
LOG (c, "trying to block on %d", lit);
// We use the same literal move-to-front strategy as in
// 'is_blocked_clause'. See there for more explanations.
int prev_other = 0; // Previous non-tautological literal.
// No 'auto' since literals of 'c' are updated during traversal.
//
const const_literal_iterator end_of_c = c->end ();
literal_iterator l;
for (l = c->begin (); l != end_of_c; l++) {
const int other = *l;
*l = prev_other;
prev_other = other;
if (other == lit)
continue;
assert (other != -lit);
assert (active (other));
assert (!val (other));
if (marked (other) < 0) {
LOG ("found tautological literal %d", other);
c->literals[0] = other; // Move to front of 'c'.
break;
}
}
if (l == end_of_c) {
LOG ("no tautological literal found");
// Restore old literal order in the clause because.
const const_literal_iterator begin_of_c = c->begin ();
while (l-- != begin_of_c) {
const int other = *l;
*l = prev_other;
prev_other = other;
}
continue; // ... with next candidate 'c' in 'pos'.
}
blocked++;
LOG (c, "blocked");
if (proof) {
proof->weaken_minus (c);
}
external->push_clause_on_extension (lit, c);
blocker.reschedule.push_back (c);
mark_garbage (c);
j--;
}
if (j == pos.begin ())
erase_vector (pos);
else
pos.resize (j - pos.begin ());
stats.blocked += blocked;
LOG ("blocked %" PRId64 " clauses on %d (skipped %" PRId64 ")", blocked,
lit, skipped);
unmark (d);
}
/*------------------------------------------------------------------------*/
// Determine the set of candidate clauses with 'lit', which are checked to
// be blocked by 'lit'. Filter out too large and small clauses and which do
// not have any negated other literal in any of the clauses with '-lit'.
size_t Internal::block_candidates (Blocker &blocker, int lit) {
assert (blocker.candidates.empty ());
Occs &pos = occs (lit); // Positive occurrences of 'lit'.
Occs &nos = occs (-lit);
assert (noccs (lit) <= pos.size ());
assert (noccs (-lit) == nos.size ()); // Already flushed.
// Mark all literals in clauses with '-lit'. Note that 'mark2' uses
// separate bits for 'lit' and '-lit'.
//
for (const auto &c : nos)
mark2 (c);
const auto eop = pos.end ();
auto j = pos.begin (), i = j;
for (; i != eop; i++) {
Clause *c = *j++ = *i;
if (c->garbage) {
j--;
continue;
}
assert (!c->redundant);
if (c->size > opts.blockmaxclslim)
continue;
if (c->size < opts.blockminclslim)
continue;
const const_literal_iterator eoc = c->end ();
const_literal_iterator l;
for (l = c->begin (); l != eoc; l++) {
const int other = *l;
if (other == lit)
continue;
assert (other != -lit);
assert (active (other));
assert (!val (other));
if (marked2 (-other))
break;
}
if (l != eoc)
blocker.candidates.push_back (c);
}
if (j == pos.begin ())
erase_vector (pos);
else
pos.resize (j - pos.begin ());
assert (pos.size () == noccs (lit)); // Now also flushed.
for (const auto &c : nos)
unmark (c);
return blocker.candidates.size ();
}
/*------------------------------------------------------------------------*/
// Try to find a clause with '-lit' which does not have any literal in
// clauses with 'lit'. If such a clause exists no candidate clause can be
// blocked on 'lit' since all candidates would produce a non-tautological
// resolvent with that clause.
Clause *Internal::block_impossible (Blocker &blocker, int lit) {
assert (noccs (-lit) > 1);
assert (blocker.candidates.size () > 1);
for (const auto &c : blocker.candidates)
mark2 (c);
Occs &nos = occs (-lit);
Clause *res = 0;
for (const auto &c : nos) {
assert (!c->garbage);
assert (!c->redundant);
assert (c->size <= opts.blockmaxclslim);
const const_literal_iterator eoc = c->end ();
const_literal_iterator l;
for (l = c->begin (); l != eoc; l++) {
const int other = *l;
if (other == -lit)
continue;
assert (other != lit);
assert (active (other));
assert (!val (other));
if (marked2 (-other))
break;
}
if (l == eoc)
res = c;
}
for (const auto &c : blocker.candidates)
unmark (c);
if (res) {
LOG (res, "common non-tautological resolvent producing");
blocker.candidates.clear ();
}
return res;
}
/*------------------------------------------------------------------------*/
// In the general case we have at least two negative occurrences.
void Internal::block_literal_with_at_least_two_negative_occs (
Blocker &blocker, int lit) {
assert (active (lit));
assert (!frozen (lit));
assert (noccs (lit) > 0);
assert (noccs (-lit) > 1);
Occs &nos = occs (-lit);
assert (noccs (-lit) <= nos.size ());
int max_size = 0;
// Flush all garbage clauses in occurrence list 'nos' of '-lit' and
// determine the maximum size of negative clauses (with '-lit').
//
const auto eon = nos.end ();
auto j = nos.begin (), i = j;
for (; i != eon; i++) {
Clause *c = *j++ = *i;
if (c->garbage)
j--;
else if (c->size > max_size)
max_size = c->size;
}
if (j == nos.begin ())
erase_vector (nos);
else
nos.resize (j - nos.begin ());
assert (nos.size () == noccs (-lit));
assert (nos.size () > 1);
// If the maximum size of a negative clause (with '-lit') exceeds the
// maximum clause size limit ignore this candidate literal.
//
if (max_size > opts.blockmaxclslim) {
LOG ("maximum size %d of clauses with %d exceeds clause size limit %d",
max_size, -lit, opts.blockmaxclslim);
return;
}
LOG ("maximum size %d of clauses with %d", max_size, -lit);
// We filter candidate clauses with positive occurrence of 'lit' in
// 'blocker.candidates' and return if no candidate clause remains.
// Candidates should be small enough and should have at least one literal
// which occurs negated in one of the clauses with '-lit'.
//
size_t candidates = block_candidates (blocker, lit);
if (!candidates) {
LOG ("no candidate clauses found");
return;
}
LOG ("found %zd candidate clauses", candidates);
// We further search for a clause with '-lit' that has no literal
// negated in any of the candidate clauses (except 'lit'). If such a
// clause exists, we know that none of the candidates is blocked.
//
if (candidates > 1 && block_impossible (blocker, lit)) {
LOG ("impossible to block any candidate clause on %d", lit);
assert (blocker.candidates.empty ());
return;
}
LOG ("trying to block %zd clauses out of %" PRIu64 " with literal %d",
candidates, noccs (lit), lit);
int64_t blocked = 0;
// Go over all remaining candidates and try to block them on 'lit'.
//
for (const auto &c : blocker.candidates) {
assert (!c->garbage);
assert (!c->redundant);
if (!is_blocked_clause (c, lit))
continue;
blocked++;
LOG (c, "blocked");
if (proof) {
proof->weaken_minus (c);
}
external->push_clause_on_extension (lit, c);
blocker.reschedule.push_back (c);
mark_garbage (c);
}
LOG ("blocked %" PRId64
" clauses on %d out of %zd candidates in %zd occurrences",
blocked, lit, blocker.candidates.size (), occs (lit).size ());
blocker.candidates.clear ();
stats.blocked += blocked;
if (blocked)
flush_occs (lit);
}
/*------------------------------------------------------------------------*/
// Reschedule literals in a clause (except 'lit') which was blocked.
void Internal::block_reschedule_clause (Blocker &blocker, int lit,
Clause *c) {
#ifdef NDEBUG
(void) lit;
#endif
assert (c->garbage);
for (const auto &other : *c) {
uint64_t &n = noccs (other);
assert (n > 0);
n--;
LOG ("updating %d with %" PRIu64 " positive and %" PRIu64
" negative occurrences",
other, noccs (other), noccs (-other));
if (blocker.schedule.contains (vlit (-other)))
blocker.schedule.update (vlit (-other));
else if (active (other) && !frozen (other) && !marked_skip (-other)) {
LOG ("rescheduling to block clauses on %d", -other);
blocker.schedule.push_back (vlit (-other));
}
if (blocker.schedule.contains (vlit (other))) {
assert (other != lit);
blocker.schedule.update (vlit (other));
}
}
}
// Reschedule all literals in clauses blocked by 'lit' (except 'lit').
void Internal::block_reschedule (Blocker &blocker, int lit) {
while (!blocker.reschedule.empty ()) {
Clause *c = blocker.reschedule.back ();
blocker.reschedule.pop_back ();
block_reschedule_clause (blocker, lit, c);
}
}
/*------------------------------------------------------------------------*/
void Internal::block_literal (Blocker &blocker, int lit) {
assert (!marked_skip (lit));
if (!active (lit))
return; // Pure literal '-lit'.
if (frozen (lit))
return;
assert (!val (lit));
// If the maximum number of a negative clauses (with '-lit') exceeds the
// occurrence limit ignore this candidate literal.
//
if (noccs (-lit) > (unsigned) opts.blockocclim)
return;
LOG ("blocking literal candidate %d "
"with %" PRIu64 " positive and %" PRIu64 " negative occurrences",
lit, noccs (lit), noccs (-lit));
stats.blocked_candidates++;
assert (blocker.reschedule.empty ());
assert (blocker.candidates.empty ());
if (!noccs (-lit))
block_pure_literal (blocker, lit);
else if (!noccs (lit)) {
// Rare situation, where the clause length limit was hit for 'lit' and
// '-lit' is skipped and then it becomes pure. Can be ignored. We also
// so it once happening for a 'elimboundmin=-1' and zero positive and
// one negative occurrence.
} else if (noccs (-lit) == 1)
block_literal_with_one_negative_occ (blocker, lit);
else
block_literal_with_at_least_two_negative_occs (blocker, lit);
// Done with blocked clause elimination on this literal and we do not
// have to try blocked clause elimination on it again until irredundant
// clauses with its negation are removed.
//
assert (!frozen (lit)); // just to be sure ...
unmark_block (lit);
}
/*------------------------------------------------------------------------*/
bool Internal::block () {
if (!opts.block)
return false;
if (unsat)
return false;
if (!stats.clauses_now_irr)
return false;
if (terminated_asynchronously ())
return false;
// Our current algorithm for producing the necessary clauses on the
// reconstruction stack for extending the witness requires a blocked
// literal addition step which (empirically) conflicts with flushing
// during restoring clauses (similar to cover).
// Example:
// on the reconstruction stack: (-3) 4 -1 -3 (1) 2 1 4 (-2) 5 -2
// current formula 3 -4, -3 6, 2 -5, -2 7, -3 4 2
// add incrementally -4, 3 (taints 3) and solve
// restore 4 -1 -3 (taints -1)
// restore 2 1 4 (skipped with '--restoreflush' due to fixed 2)
// reconstruction stack after restore: (-2) 5 -2
// solve returns satisfiable
// not extended model -1, 2, 3, -4, -5, 6, 7
// extend flips 2 due to unsatisfied 5 -2
// extended model -1, -2, 3, -4, -5, 6, 7 conflicts with
// (not restored) flushed clause 2 1 4
if (propagated < trail.size ()) {
LOG ("need to propagate %zd units first", trail.size () - propagated);
init_watches ();
connect_watches ();
if (!propagate ()) {
LOG ("propagating units results in empty clause");
learn_empty_clause ();
assert (unsat);
}
clear_watches ();
reset_watches ();
if (unsat)
return false;
}
MODE_SCOPE_SIMPLIFY (BLOCK);
PROFILE_SCOPE_SIMPLIFY (block);
stats.blockings++;
LOG ("block-%" PRId64 "", stats.blockings);
assert (!level);
assert (!watching ());
assert (!occurring ());
mark_satisfied_clauses_as_garbage ();
init_occs (); // Occurrence lists for all literals.
init_noccs (); // Number of occurrences to avoid flushing garbage clauses.
Blocker blocker (this);
block_schedule (blocker);
int64_t blocked = stats.blocked;
int64_t resolutions = stats.blocked_resolutions;
int64_t purelits = stats.blocked_pure_literals;
int64_t pured = stats.blocked_pure_clauses;
while (!terminated_asynchronously () && !blocker.schedule.empty ()) {
int lit = u2i (blocker.schedule.front ());
blocker.schedule.pop_front ();
block_literal (blocker, lit);
block_reschedule (blocker, lit);
}
blocker.erase ();
reset_noccs ();
reset_occs ();
resolutions = stats.blocked_resolutions - resolutions;
blocked = stats.blocked - blocked;
PHASE ("block", stats.blockings,
"blocked %" PRId64 " clauses in %" PRId64 " resolutions", blocked,
resolutions);
pured = stats.blocked_pure_clauses - pured;
purelits = stats.blocked_pure_literals - purelits;
int64_t ticks = 0; // currently not counted here
if (pured)
mark_redundant_clauses_with_eliminated_variables_as_garbage (ticks);
if (purelits)
PHASE ("block", stats.blockings,
"found %" PRId64 " pure literals in %" PRId64 " clauses",
purelits, pured);
else
PHASE ("block", stats.blockings, "no pure literals found");
report ('b', !opts.reportall && !blocked);
return blocked;
}
} // namespace CaDiCaL