blob: de296dde69c0c53ff7d487ead4936d87f2588902 [file] [edit]
#include "internal.hpp"
namespace CaDiCaL {
/*------------------------------------------------------------------------*/
// Signed marking or unmarking of a clause or the global 'clause'.
void Internal::mark (Clause *c) {
for (const auto &lit : *c)
mark (lit);
}
void Internal::mark2 (Clause *c) {
for (const auto &lit : *c)
mark2 (lit);
}
void Internal::unmark (Clause *c) {
for (const auto &lit : *c)
unmark (lit);
}
void Internal::mark_clause () {
for (const auto &lit : clause)
mark (lit);
}
void Internal::unmark_clause () {
for (const auto &lit : clause)
unmark (lit);
}
/*------------------------------------------------------------------------*/
// Mark the variables of an irredundant clause to 'have been removed', which
// will trigger these variables to be considered again in the next bounded
// variable elimination phase. This is called from 'mark_garbage' below.
// Note that 'mark_removed (int lit)' will also mark the blocking flag of
// '-lit' to trigger reconsidering blocking clauses on '-lit'.
void Internal::mark_removed (Clause *c, int except) {
LOG (c, "marking removed");
assert (!c->redundant);
for (const auto &lit : *c)
if (lit != except)
mark_removed (lit);
}
// Mark the variables of a (redundant or irredundant) clause to 'have been
// added', which triggers clauses with such a variables, to be considered
// both as a subsumed or subsuming clause in the next subsumption phase.
// This function is called from 'new_clause' below as well as in situations
// where a clause is shrunken (and thus needs to be at least considered
// again to subsume a larger clause). We also use this to tell
// 'ternary' preprocessing reconsider clauses on an added literal as well as
// trying to block clauses on it.
inline void Internal::mark_added (int lit, int size, bool redundant) {
mark_subsume (lit);
if (size == 3)
mark_ternary (lit);
if (!redundant)
mark_block (lit);
if (size <= opts.factorsize && (opts.factorredundant > 1 || !redundant ||
(opts.factorredundant == 1 && size == 2)))
mark_factor (lit);
}
void Internal::mark_added (Clause *c) {
LOG (c, "marking added");
assert (likely_to_be_kept_clause (c));
for (const auto &lit : *c)
mark_added (lit, c->size, c->redundant);
}
/*------------------------------------------------------------------------*/
Clause *Internal::new_clause (bool red, int glue, int64_t new_id) {
assert (clause.size () <= (size_t) INT_MAX);
const int size = (int) clause.size ();
assert (size >= 2);
if (glue >= size)
glue = size - 1;
size_t bytes = Clause::bytes (size);
Clause *c = (Clause *) new char[bytes];
DeferDeleteArray<char> clause_delete ((char *) c);
c->id = new_id ? new_id : ++clause_id;
c->conditioned = false;
c->covered = false;
c->enqueued = false;
c->frozen = false;
c->garbage = false;
c->gate = false;
c->hyper = false;
c->instantiated = false;
c->moved = false;
c->reason = false;
c->redundant = red;
c->transred = false;
c->subsume = false;
c->swept = false;
c->flushed = false;
c->vivified = false;
c->vivify = false;
c->used = 0;
c->glue = glue;
c->size = size;
c->pos = 2;
for (int i = 0; i < size; i++)
c->literals[i] = clause[i];
// Just checking that we did not mess up our sophisticated memory layout.
// This might be compiler dependent though. Crucial for correctness.
//
assert (c->bytes () == bytes);
stats.clauses_now_total++;
stats.clauses++;
if (red) {
stats.clauses_now_red++;
stats.clauses_redundant++;
} else {
stats.irredundant_literals += size;
stats.clauses_now_irr++;
stats.clauses_irredundant++;
}
if (size == 2)
new_binary_since_dedup = true;
clauses.push_back (c);
clause_delete.release ();
#ifdef LOGGING
if (opts.logpointer)
LOG (c, "new pointer %p", (void *) c);
else
LOG (c, "new");
#endif
if (likely_to_be_kept_clause (c))
mark_added (c);
return c;
}
/*------------------------------------------------------------------------*/
void Internal::promote_clause (Clause *c, int new_glue) {
assert (c->redundant);
assert (new_glue);
const int tier1limit = tier1[false];
const int tier2limit = max (tier1limit, tier2[false]);
if (!c->redundant)
return;
if (c->hyper)
return;
int old_glue = c->glue;
if (new_glue >= old_glue)
return;
c->used = max_used;
if (old_glue > tier1limit && new_glue <= tier1limit) {
LOG (c, "promoting with new glue %d to tier1", new_glue);
stats.clause_promoted_tier1++;
} else if (old_glue > tier2limit && new_glue <= tier2limit) {
LOG (c, "promoting with new glue %d to tier2", new_glue);
stats.clause_promoted_tier2++;
} else if (old_glue <= tier2limit)
LOG (c, "keeping with new glue %d in tier2", new_glue);
else
LOG (c, "keeping with new glue %d in tier3", new_glue);
stats.clause_improved_glue++;
c->glue = new_glue;
}
/*------------------------------------------------------------------------*/
void Internal::promote_clause_glue_only (Clause *c, int new_glue) {
assert (c->redundant);
assert (new_glue);
if (c->hyper)
return;
int old_glue = c->glue;
const int tier1limit = tier1[false];
const int tier2limit = max (tier1limit, tier2[false]);
if (new_glue >= old_glue)
return;
if (new_glue <= tier1limit) {
LOG (c, "promoting with new glue %d to tier1", new_glue);
stats.clause_promoted_tier1++;
} else if (old_glue > tier2limit && new_glue <= tier2limit) {
LOG (c, "promoting with new glue %d to tier2", new_glue);
stats.clause_promoted_tier2++;
} else if (old_glue <= tier2limit)
LOG (c, "keeping with new glue %d in tier2", new_glue);
else
LOG (c, "keeping with new glue %d in tier3", new_glue);
stats.clause_improved_glue++;
c->glue = new_glue;
}
/*------------------------------------------------------------------------*/
// Shrinking a clause, e.g., removing one or more literals, requires to fix
// the 'pos' field, if it exists and points after the new last literal. We
// also have adjust the global statistics counter of irredundant literals
// for irredundant clauses, and also adjust the glue value of redundant
// clauses if the size becomes smaller than the glue. Also mark the
// literals in the resulting clause as 'added'. The result is the number of
// (aligned) removed bytes, resulting from shrinking the clause.
//
size_t Internal::shrink_clause (Clause *c, int new_size) {
if (opts.check && is_external_forgettable (c->id))
mark_garbage_external_forgettable (c->id);
assert (new_size >= 2);
int old_size = c->size;
assert (new_size < old_size);
#ifndef NDEBUG
for (int i = c->size; i < new_size; i++)
c->literals[i] = 0;
#endif
if (c->pos >= new_size)
c->pos = 2;
size_t old_bytes = c->bytes ();
c->size = new_size;
size_t new_bytes = c->bytes ();
size_t res = old_bytes - new_bytes;
if (c->redundant)
promote_clause_glue_only (c, min (c->size - 1, c->glue));
else {
int delta_size = old_size - new_size;
assert (stats.irredundant_literals >= delta_size);
stats.irredundant_literals -= delta_size;
}
if (likely_to_be_kept_clause (c))
mark_added (c);
return res;
}
// Makes a redundant clause irredundant and update the statistics
void Internal::make_irredundant (Clause *subsuming) {
assert (subsuming->redundant);
assert (!subsuming->garbage);
LOG ("turning redundant subsuming clause into irredundant clause");
subsuming->redundant = false;
if (proof)
proof->strengthen (subsuming->id);
stats.clauses_now_irr++;
stats.clauses_irredundant++;
stats.irredundant_literals += subsuming->size;
assert (stats.clauses_now_red > 0);
stats.clauses_now_red--;
assert (stats.clauses_redundant > 0);
stats.clauses_redundant--;
// ... and keep 'stats.clauses'.
}
// This is the 'raw' deallocation of a clause. If the clause is in the
// arena nothing happens. If the clause is not in the arena its memory is
// reclaimed immediately.
void Internal::deallocate_clause (Clause *c) {
char *p = (char *) c;
if (arena.contains (p))
return;
#ifdef LOGGING
if (opts.logpointer)
LOG (c, "deallocate pointer %p", (void *) c);
else
LOG (c, "deallocate");
#endif
delete[] p;
}
void Internal::delete_clause (Clause *c) {
#ifdef LOGGING
if (opts.logpointer)
LOG (c, "delete pointer %p", (void *) c);
else
LOG (c, "delete");
#endif
size_t bytes = c->bytes ();
stats.collected += bytes;
if (c->garbage) {
assert (stats.garbage_bytes >= (int64_t) bytes);
stats.garbage_bytes -= bytes;
assert (stats.garbage_clauses > 0);
stats.garbage_clauses--;
assert (stats.garbage_literals >= c->size);
stats.garbage_literals -= c->size;
// See the discussion in 'propagate' on avoiding to eagerly trace binary
// clauses as deleted (produce 'd ...' lines) as soon they are marked
// garbage. We avoid this and only trace them as deleted when they are
// actually deleted here. This allows the solver to propagate binary
// garbage clauses without producing incorrect 'd' lines. The effect
// from the proof perspective is that the deletion of these binary
// clauses occurs later in the proof file.
//
if (proof && c->size == 2 && !c->flushed) {
proof->delete_clause (c);
}
}
deallocate_clause (c);
}
// We want to eagerly update statistics as soon clauses are marked garbage.
// Otherwise 'report' for instance gives wrong numbers after 'subsume'
// before the next 'reduce'. Thus we factored out marking and accounting
// for garbage clauses.
//
// Eagerly deleting clauses instead is problematic, since references to
// these clauses need to be flushed, which is too costly to do eagerly.
//
// We also update garbage statistics at this point. This helps to
// determine whether the garbage collector should be called during for
// instance bounded variable elimination, which usually generates lots of
// garbage clauses.
//
// In order not to miss any update to these clause statistics we call
// 'check_clause_stats' after garbage collection in debugging mode.
//
void Internal::mark_garbage (Clause *c) {
assert (!c->garbage);
// Delay tracing deletion of binary clauses. See the discussion above in
// 'delete_clause' and also in 'propagate'.
//
if (proof && (c->size != 2 || !watching ())) {
c->flushed = true;
proof->delete_clause (c);
}
// Because of the internal model checking, external forgettable clauses
// must be marked as removed already upon mark_garbage, can not wait until
// actual deletion.
if (opts.check && is_external_forgettable (c->id))
mark_garbage_external_forgettable (c->id);
assert (stats.clauses_now_total > 0);
stats.clauses_now_total--;
size_t bytes = c->bytes ();
if (c->redundant) {
assert (stats.clauses_now_red > 0);
stats.clauses_now_red--;
} else {
assert (stats.clauses_now_irr > 0);
stats.clauses_now_irr--;
assert (stats.irredundant_literals >= c->size);
stats.irredundant_literals -= c->size;
mark_removed (c);
}
stats.garbage_bytes += bytes;
stats.garbage_clauses++;
stats.garbage_literals += c->size;
c->garbage = true;
c->used = 0;
#ifdef LOGGING
if (opts.logpointer)
LOG (c, "marked garbage pointer %p", (void *) c);
else
LOG (c, "marked garbage");
#endif
}
/*------------------------------------------------------------------------*/
// Almost the same function as 'search_assign' except that we do not pretend
// to learn a new unit clause (which was confusing in log files).
void Internal::assign_original_unit (int64_t id, int lit) {
assert (!unsat);
const int idx = vidx (lit);
assert (!vals[idx]);
assert (!flags (idx).eliminated ());
Var &v = var (idx);
v.level = 0;
v.trail = get_trail_size ();
v.reason = 0;
const signed char tmp = sign (lit);
set_val (idx, tmp);
trail.push_back (lit);
num_assigned++;
const unsigned uidx = vlit (lit);
if (lrat || frat)
unit_clauses (uidx) = id;
LOG ("original unit assign %d", lit);
assert (num_assigned == trail.size () || level);
mark_fixed (lit);
if (level)
return;
}
// New clause added through the API, e.g., while parsing a DIMACS file.
// Also used by external_propagate in various different modes.
// clause, original, lrat_chain and external->eclause are set.
// from_propagator and force_no_backtrack change the behaviour.
// sometimes the pointer to the new clause is needed, therefore it is
// made sure that newest_clause points to the new clause upon return.
void Internal::add_new_original_clause (int64_t id) {
if (!from_propagator && level && !opts.ilb) {
backtrack_without_updating_phases ();
} else if (earliest_changed_val) {
assert (val (earliest_changed_val));
int new_level = var (earliest_changed_val).level - 1;
assert (new_level >= 0);
backtrack_without_updating_phases (new_level);
}
assert (!earliest_changed_val);
LOG (original, "original clause");
assert (clause.empty ());
bool skip = false;
unordered_set<int> learned_levels;
size_t unassigned = 0;
newest_clause = 0;
if (unsat) {
LOG ("skipping clause since formula is already inconsistent");
skip = true;
} else {
assert (clause.empty ());
for (const auto &lit : original) {
int tmp = marked (lit);
if (tmp > 0) {
LOG ("removing duplicated literal %d", lit);
} else if (tmp < 0) {
LOG ("tautological since both %d and %d occur", -lit, lit);
skip = true;
} else {
mark (lit);
tmp = fixed (lit);
if (tmp < 0) {
LOG ("removing falsified literal %d", lit);
if (lrat) {
int elit = externalize (lit);
unsigned eidx = (elit > 0) + 2u * (unsigned) abs (elit);
// the external units are handled somewhere else
if (!external->ext_units[eidx]) {
int64_t uid = unit_id (-lit);
lrat_chain.push_back (uid);
}
}
} else if (tmp > 0) {
LOG ("satisfied since literal %d true", lit);
skip = true;
} else {
clause.push_back (lit);
assert (flags (lit).status != Flags::UNUSED);
tmp = val (lit);
if (tmp)
learned_levels.insert (var (lit).level);
else
unassigned++;
}
}
}
for (const auto &lit : original)
unmark (lit);
}
if (skip) {
if (from_propagator) {
stats.up_learn_satisfied++;
// In case it was a skipped external forgettable, we need to mark it
// immediately as removed
if (opts.check && is_external_forgettable (id))
mark_garbage_external_forgettable (id);
}
if (proof) {
proof->delete_external_original_clause (id, false, external->eclause);
}
} else {
int64_t new_id = id;
const size_t size = clause.size ();
if (original.size () > size) {
new_id = ++clause_id;
if (proof) {
if (lrat)
lrat_chain.push_back (id);
proof->add_derived_clause (new_id, false, clause, lrat_chain);
proof->delete_external_original_clause (id, false,
external->eclause);
}
external->check_learned_clause ();
if (from_propagator) {
// The original form of the added clause is immediately forgotten
// TODO: shall we save and check the simplified form? (one with
// new_id)
if (opts.check && is_external_forgettable (id))
mark_garbage_external_forgettable (id);
}
}
external->eclause.clear ();
lrat_chain.clear ();
if (!size) {
if (from_propagator)
stats.up_learn_empty++;
assert (!unsat);
if (!original.size ())
VERBOSE (1, "found empty original clause");
else
VERBOSE (1, "found falsified original clause");
unsat = true;
conflict_id = new_id;
marked_failed = true;
conclusion.push_back (new_id);
} else if (size == 1) {
handle_external_clause (0, new_id);
} else {
move_literals_to_watch ();
#ifndef NDEBUG
check_watched_literal_invariants ();
#endif
int glue = (int) (learned_levels.size () + unassigned);
assert (glue <= (int) clause.size ());
bool clause_redundancy = from_propagator && ext_clause_forgettable;
Clause *c = new_clause (clause_redundancy, glue, new_id);
original.clear ();
handle_external_clause (c); // handle_external_clause uses clause
watch_clause (c); // and may change the watched literal
clause.clear (); // therefore it is cleared afterwards
newest_clause = c;
}
}
clause.clear ();
lrat_chain.clear ();
}
// Add learned new clause during conflict analysis and watch it. Requires
// that the clause is at least of size 2, and the first two literals
// are assigned at the highest decision level.
//
Clause *Internal::new_learned_redundant_clause (int glue) {
assert (clause.size () > 1);
#ifndef NDEBUG
for (size_t i = 2; i < clause.size (); i++)
assert (var (clause[0]).level >= var (clause[i]).level),
assert (var (clause[1]).level >= var (clause[i]).level);
#endif
external->check_learned_clause ();
if (proof) {
proof->add_derived_clause (clause_id + 1, true, clause, lrat_chain);
}
Clause *res = new_clause (true, glue);
assert (watching ());
watch_clause (res);
return res;
}
// Add hyper binary resolved clause during 'probing'.
//
Clause *Internal::new_hyper_binary_resolved_clause (bool red, int glue) {
external->check_learned_clause ();
if (proof) {
proof->add_derived_clause (clause_id + 1, red, clause, lrat_chain);
}
Clause *res = new_clause (red, glue);
assert (watching ());
watch_clause (res);
return res;
}
// Add hyper ternary resolved clause during 'ternary'.
//
Clause *Internal::new_hyper_ternary_resolved_clause (bool red) {
external->check_learned_clause ();
if (proof) {
proof->add_derived_clause (clause_id + 1, red, clause, lrat_chain);
}
size_t size = clause.size ();
Clause *res = new_clause (red, size);
assert (!watching ());
return res;
}
Clause *Internal::new_factor_clause (int witness) {
external->check_learned_clause ();
stats.factor_added_clauses++;
stats.factor_added_literals += clause.size ();
if (proof) {
if (witness)
proof->add_derived_rat_clause (
clause_id + 1, false, externalize (witness), clause, lrat_chain);
else
proof->add_derived_clause (clause_id + 1, false, clause, lrat_chain);
}
Clause *res = new_clause (false, 0);
assert (!watching ());
assert (occurring ());
for (const auto &lit : *res) {
occs (lit).push_back (res);
}
return res;
}
// Add hyper ternary resolved clause during 'congruence' and watch it
//
Clause *
Internal::new_hyper_ternary_resolved_clause_and_watch (bool red,
bool full_watching) {
external->check_learned_clause ();
if (proof) {
proof->add_derived_clause (clause_id + 1, red, clause, lrat_chain);
}
size_t size = clause.size ();
Clause *res = new_clause (red, size);
if (full_watching) {
assert (watching ());
watch_clause (res);
}
return res;
}
// Add a new clause with same glue and redundancy as 'orig' but literals are
// assumed to be in 'clause' in 'decompose' and 'vivify'.
//
Clause *Internal::new_clause_as (const Clause *orig) {
external->check_learned_clause ();
if (proof) {
proof->add_derived_clause (clause_id + 1, orig->redundant, clause,
lrat_chain);
}
const int new_glue = orig->glue;
Clause *res = new_clause (orig->redundant, new_glue);
assert (watching ());
watch_clause (res);
return res;
}
// Add resolved clause during resolution, e.g., bounded variable
// elimination, but do not connect its occurrences here.
//
Clause *Internal::new_resolved_irredundant_clause () {
external->check_learned_clause ();
if (proof) {
proof->add_derived_clause (clause_id + 1, false, clause, lrat_chain);
}
Clause *res = new_clause (false);
assert (!watching ());
return res;
}
void Internal::decay_clauses_upon_incremental_clauses () {
if (!opts.incdecay)
return;
if (!stats.searches)
return;
if (stats.conflicts < lim.incremental_decay)
return;
PHASE ("decay", stats.incremental_decay,
"decaying clauses with next decaying at conflict %" PRId64
"(after the next incremental call)",
lim.incremental_decay);
for (auto c : clauses) {
if (c->garbage)
continue;
if (!c->redundant)
continue;
if (c->id >= last.incremental_decay.last_id)
continue;
switch (opts.incdecay) {
case 1: // my intuition
++c->glue;
break;
case 2: // Armin's idea
if (c->glue < tier1[false])
c->used = 1;
break;
case 3:
if (c->glue < tier1[false])
c->used = 1;
++c->glue;
break;
default:
break;
}
}
lim.incremental_decay += stats.conflicts + opts.incdecayint;
++stats.incremental_decay;
last.incremental_decay.last_id = clause_id;
}
} // namespace CaDiCaL