blob: 3964e20ab28c8a46d06c757d859562675043945d [file] [edit]
#include "cadical.hpp"
#include "internal.hpp"
namespace CaDiCaL {
// The idea of warmup is to reuse the strength of CDCL, namely
// propagating, before calling random walk that is not good at
// propagating long chains. Therefore, we propagate (ignoring all conflicts)
// discovered along the way.
// The asignmend is the same as the normal assignment however, it updates
// the target phases so that local search can pick them up later
// specific warmup version with saving of the target.
inline void Internal::warmup_assign (int lit, Clause *reason) {
assert (level); // no need to learn unit clauses here
MODE_REQUIRE (SEARCH);
const int idx = vidx (lit);
assert (reason != external_reason);
assert (!vals[idx]);
assert (!flags (idx).eliminated () || reason == decision_reason);
assert (!searching_lucky_phases);
assert (lrat_chain.empty ());
Var &v = var (idx);
int lit_level;
assert (
!(reason == external_reason &&
((size_t) level <= assumptions.size () + (!!constraint.size ()))));
assert (reason);
assert (level || reason == decision_reason);
// we purely assign in order here
lit_level = level;
v.level = lit_level;
v.trail = get_trail_size ();
v.reason = reason;
assert ((int) num_assigned < max_var);
assert (num_assigned == trail.size ());
num_assigned++;
const signed char tmp = sign (lit);
phases.saved[idx] = tmp;
set_val (idx, tmp);
assert (val (lit) > 0);
assert (val (-lit) < 0);
trail.push_back (lit);
#ifdef LOGGING
if (!lit_level)
LOG ("root-level unit assign %d @ 0", lit);
else
LOG (reason, "search assign %d @ %d", lit, lit_level);
#endif
assert (watching ());
const Watches &ws = watches (-lit);
if (!ws.empty ()) {
const Watch &w = ws[0];
__builtin_prefetch (&w, 0, 1);
}
}
void Internal::warmup_propagate_beyond_conflict () {
assert (!unsat);
PROFILE_SCOPE (propagate);
assert (!ignore);
int64_t before = propagated;
while (propagated != trail.size ()) {
const int lit = -trail[propagated++];
LOG ("propagating %d", -lit);
Watches &ws = watches (lit);
const const_watch_iterator eow = ws.end ();
watch_iterator j = ws.begin ();
const_watch_iterator i = j;
while (i != eow) {
const Watch w = *j++ = *i++;
const signed char b = val (w.blit);
if (b > 0)
continue; // blocking literal satisfied
if (w.binary ()) {
// In principle we can ignore garbage binary clauses too, but that
// would require to dereference the clause pointer all the time with
//
// if (w.clause->garbage) { j--; continue; } // (*)
//
// This is too costly. It is however necessary to produce correct
// proof traces if binary clauses are traced to be deleted ('d ...'
// line) immediately as soon they are marked as garbage. Actually
// finding instances where this happens is pretty difficult (six
// parallel fuzzing jobs in parallel took an hour), but it does
// occur. Our strategy to avoid generating incorrect proofs now is
// to delay tracing the deletion of binary clauses marked as garbage
// until they are really deleted from memory. For large clauses
// this is not necessary since we have to access the clause anyhow.
//
// Thanks go to Mathias Fleury, who wanted me to explain why the
// line '(*)' above was in the code. Removing it actually really
// improved running times and thus I tried to find concrete
// instances where this happens (which I found), and then
// implemented the described fix.
// Binary clauses are treated separately since they do not require
// to access the clause at all (only during conflict analysis, and
// there also only to simplify the code).
if (b < 0)
// ignoring conflict
++stats.walk_warmup_conflicts;
else {
warmup_assign (w.blit, w.clause);
}
} else {
assert (w.clause->size > 2);
// The cache line with the clause data is forced to be loaded here
// and thus this first memory access below is the real hot-spot of
// the solver. Note, that this check is positive very rarely and
// thus branch prediction should be almost perfect here.
if (w.clause->garbage) {
j--;
continue;
}
literal_iterator lits = w.clause->begin ();
const int other = lits[0] ^ lits[1] ^ lit;
const signed char u = val (other);
if (u > 0)
j[-1].blit = other;
else {
const int size = w.clause->size;
const const_literal_iterator end = lits + size;
const literal_iterator middle = lits + w.clause->pos;
literal_iterator k = middle;
signed char v = -1;
int r = 0;
while (k != end && (v = val (r = *k)) < 0)
k++;
if (v < 0) {
k = lits + 2;
assert (w.clause->pos <= size);
while (k != middle && (v = val (r = *k)) < 0)
k++;
}
#if 0 // my intuiton: does not make sense to update here
w.clause->pos = k - lits; // always save position
#endif
assert (lits + 2 <= k), assert (k <= w.clause->end ());
if (v > 0) {
// Replacement satisfied, so just replace 'blit'.
j[-1].blit = r;
} else if (!v) {
// Found new unassigned replacement literal to be watched.
LOG (w.clause, "unwatch %d in", lit);
lits[0] = other;
lits[1] = r;
*k = lit;
watch_literal (r, lit, w.clause);
j--; // Drop this watch from the watch list of 'lit'.
} else if (!u) {
assert (v < 0);
// The other watch is unassigned ('!u') and all other literals
// assigned to false (still 'v < 0'), thus we found a unit.
//
build_chain_for_units (other, w.clause, 0);
warmup_assign (other, w.clause);
} else {
assert (u < 0);
assert (v < 0);
// ignoring conflict
++stats.walk_warmup_conflicts;
}
}
}
}
if (j != i) {
ws.resize (j - ws.begin ());
}
}
assert (propagated == trail.size ());
stats.walk_warmup_propagate += (trail.size () - before);
}
int Internal::warmup_decide_assumptions () {
assert (!satisfied ());
PROFILE_SCOPE (decide);
int res = 0;
if ((size_t) level < assumptions.size ()) {
const int lit = assumptions[level];
assert (assumed (lit));
const signed char tmp = val (lit);
if (tmp < 0) {
LOG ("assumption %d falsified", lit);
res = 20;
} else if (tmp > 0) {
LOG ("assumption %d already satisfied", lit);
new_trail_level (0);
LOG ("added pseudo decision level");
notify_decision ();
} else {
LOG ("deciding assumption %d", lit);
search_assume_decision (lit);
}
} else if ((size_t) level == assumptions.size () && constraint.size ()) {
int satisfied_lit = 0; // The literal satisfying the constrain.
int unassigned_lit = 0; // Highest score unassigned literal.
int previous_lit = 0; // Move satisfied literals to the front.
const size_t size_constraint = constraint.size ();
#ifndef NDEBUG
unsigned sum = 0;
for (auto lit : constraint)
sum += lit;
#endif
for (size_t i = 0; i != size_constraint; i++) {
// Get literal and move 'constraint[i] = constraint[i-1]'.
int lit = constraint[i];
constraint[i] = previous_lit;
previous_lit = lit;
const signed char tmp = val (lit);
if (tmp < 0) {
LOG ("constraint literal %d falsified", lit);
continue;
}
if (tmp > 0) {
LOG ("constraint literal %d satisfied", lit);
satisfied_lit = lit;
break;
}
assert (!tmp);
LOG ("constraint literal %d unassigned", lit);
if (!unassigned_lit || better_decision (lit, unassigned_lit))
unassigned_lit = lit;
}
if (satisfied_lit) {
constraint[0] = satisfied_lit; // Move satisfied to the front.
LOG ("literal %d satisfies constraint and "
"is implied by assumptions",
satisfied_lit);
new_trail_level (0);
LOG ("added pseudo decision level for constraint");
notify_decision ();
} else {
// Just move all the literals back. If we found an unsatisfied
// literal then it will be satisfied (most likely) at the next
// decision and moved then to the first position.
if (size_constraint) {
for (size_t i = 0; i + 1 != size_constraint; i++)
constraint[i] = constraint[i + 1];
constraint[size_constraint - 1] = previous_lit;
}
if (unassigned_lit) {
LOG ("deciding %d to satisfy constraint", unassigned_lit);
search_assume_decision (unassigned_lit);
} else {
LOG ("failing constraint");
unsat_constraint = true;
res = 20;
}
}
#ifndef NDEBUG
for (auto lit : constraint)
sum -= lit;
assert (!sum); // Checksum of literal should not change!
#endif
} else {
assert (false);
}
if (res)
marked_failed = false;
return res;
}
void Internal::warmup_decide () {
assert (!satisfied ());
PROFILE_SCOPE (decide);
assert ((size_t) level >= assumptions.size ());
assert (!constraint.size () || (size_t) level > assumptions.size ());
const bool target = (stable || opts.target == 2);
stats.walk_warmup_decision++;
int idx = next_decision_variable ();
if (flags (idx).eliminated ())
++stats.walk_warmup_dummy;
int decision = decide_phase (idx, target);
new_trail_level (decision);
warmup_assign (decision, decision_reason);
}
int Internal::decide_and_propagate_all_assumptions (
std::vector<int> &set_literals) {
LOG ("decide and propagate all assumptions to fill the vectors");
assert (!private_steps);
int res = 0;
int last_assumption_level = assumptions.size ();
if (constraint.size ())
last_assumption_level++;
if (!last_assumption_level)
return res;
while (!res) {
if (unsat)
res = 20;
else if (unsat_constraint)
res = 20;
else if (!propagate ()) {
// let analyze run to get failed assumptions
if (!unsat)
analyze ();
else
break;
} else if (satisfied ()) {
assert (!res);
/* TODO: satisfied branch was never tested due to wrong condition
if (external_prop) {
LOG ("found satisfied assignment ignoring the external propagator, "
"so probably not valid");
} else {
res = 10;
}
*/
break;
} else {
if (level >= last_assumption_level)
break;
notify_assignments ();
res = decide ();
}
}
if (unsat || unsat_constraint)
res = 20;
set_literals.reserve (trail.size ());
for (auto lit : trail)
set_literals.push_back (lit);
if (!res) {
// we need to repropagate now due to out-of-order units and renotify
// them
backtrack ();
if (propagated < trail.size () && !propagate ()) {
LOG ("empty clause after root level propagation");
learn_empty_clause ();
res = 20;
}
} else {
assert (res == 20);
notify_assignments ();
}
return res;
}
int Internal::warmup () {
assert (!unsat);
assert (!level);
if (!opts.warmup)
return 0;
MODE_REQUIRE (WALK);
PROFILE_SCOPE (warmup);
++stats.walk_warmup;
int res = 0;
#if !defined(QUIET) && !defined(NMETRICS)
const int64_t warmup_propagated = (int64_t) stats.walk_warmup_propagate;
const int64_t decision = (int64_t) stats.walk_warmup_decision;
const int64_t dummydecision = (int64_t) stats.walk_warmup_dummy;
#endif
LOG ("starting warmup");
// first propagate assumptions in case we find a conflict. One subtle
// thing, if we find a conflict in the assumption, then we actually do
// need the notifications. Otherwise, we there should be no notification
// at all (not even the `backtrack ()` at the end). Also, we cannot not
// ignore conflicts at all, meaning that we cannot use our special
// propagation function, even if it could counts ticks.
const size_t assms_contraint_level =
assumptions.size () + !constraint.empty ();
while (!res && !conflict && (size_t) level < assms_contraint_level &&
num_assigned < (size_t) max_var) {
assert (num_assigned < (size_t) max_var);
res = warmup_decide_assumptions ();
if (!res && !propagate ()) {
res = 20;
marked_failed = false;
break;
}
}
if (conflict && !res)
marked_failed = false, res = 20;
const bool no_backtrack_notification =
(level ==
0); // if no assumptions or only already satisfied ones, don't notify
LOG ("no_backtrack_notification = %d, notified_level= %d",
no_backtrack_notification, notified_level);
// now we do not need any notification and can simply propagate
assert (res || propagated == trail.size ());
assert (!private_steps);
private_steps = true;
LOG ("propagating beyond conflicts to warm-up walk");
while (!res && num_assigned < (size_t) max_var - stats.vars_unused) {
assert (propagated == trail.size ());
warmup_decide ();
warmup_propagate_beyond_conflict ();
LOG (lrat_chain, "during warmup with lrat chain:");
}
assert (res || num_assigned + stats.vars_unused == (size_t) max_var);
#if !defined(QUIET) && !defined(NMETRICS)
// constrains with empty levels break this
// assert (res || stats.walk_warmup_propagate - warmup_propagated ==
// (int64_t)num_assigned);
VERBOSE (3,
"warming-up needed %" PRIu64 " propagations including %" PRIu64
" decisions (with %" PRIu64 " dummy ones)",
(int64_t) stats.walk_warmup_propagate - warmup_propagated,
(int64_t) stats.walk_warmup_decision - decision,
(int64_t) stats.walk_warmup_dummy - dummydecision);
#endif
// now we backtrack, notifying only if there was something to
// notify.
private_steps = no_backtrack_notification;
if (!res)
backtrack_without_updating_phases ();
private_steps = false;
return res;
}
} // namespace CaDiCaL