| #include "internal.hpp" | |
| namespace CaDiCaL { | |
| /*------------------------------------------------------------------------*/ | |
| // We are using the address of 'decision_reason' as pseudo reason for | |
| // decisions to distinguish assignment decisions from other assignments. | |
| // Before we added chronological backtracking all learned units were | |
| // assigned at decision level zero ('Solver.level == 0') and we just used a | |
| // zero pointer as reason. After allowing chronological backtracking units | |
| // were also assigned at higher decision level (but with assignment level | |
| // zero), and it was not possible anymore to just distinguish the case | |
| // 'unit' versus 'decision' by just looking at the current level. Both had | |
| // a zero pointer as reason. Now only units have a zero reason and | |
| // decisions need to use the pseudo reason 'decision_reason'. | |
| // External propagation steps use the pseudo reason 'external_reason'. | |
| // The corresponding actual reason clauses are learned only when they are | |
| // relevant in conflict analysis or in root-level fixing steps. | |
| static Clause decision_reason_clause; | |
| Clause *Internal::decision_reason = &decision_reason_clause; | |
| // If chronological backtracking is used the actual assignment level might | |
| // be lower than the current decision level. In this case the assignment | |
| // level is defined as the maximum level of the literals in the reason | |
| // clause except the literal for which the clause is a reason. This | |
| // function determines this assignment level. For non-chronological | |
| // backtracking as in classical CDCL this function always returns the | |
| // current decision level, the concept of assignment level does not make | |
| // sense, and accordingly this function can be skipped. | |
| // In case of external propagation, it is implicitly assumed that the | |
| // assignment level is the level of the literal (since the reason clause, | |
| // i.e., the set of other literals, is unknown). | |
| inline int Internal::assignment_level (int lit, Clause *reason) { | |
| if (!reason || reason == external_reason) | |
| return level; | |
| int res = 0; | |
| for (const auto &other : *reason) { | |
| if (other == lit) | |
| continue; | |
| assert (val (other)); | |
| int tmp = var (other).level; | |
| if (tmp > res) | |
| res = tmp; | |
| } | |
| return res; | |
| } | |
| // calculate lrat_chain | |
| // | |
| void Internal::build_chain_for_units (int lit, Clause *reason, | |
| bool forced) { | |
| if (!lrat) | |
| return; | |
| if (assignment_level (lit, reason) && !forced) | |
| return; | |
| assert (lrat_chain.empty ()); | |
| for (auto &reason_lit : *reason) { | |
| if (lit == reason_lit) | |
| continue; | |
| assert (val (reason_lit)); | |
| const int signed_reason_lit = val (reason_lit) * reason_lit; | |
| int64_t id = unit_id (signed_reason_lit); | |
| lrat_chain.push_back (id); | |
| } | |
| lrat_chain.push_back (reason->id); | |
| } | |
| // same code as above but reason is assumed to be conflict and lit is not | |
| // needed | |
| // | |
| void Internal::build_chain_for_empty () { | |
| if (!lrat || !lrat_chain.empty ()) | |
| return; | |
| assert (!level || in_mode (BACKBONE)); | |
| assert (lrat_chain.empty ()); | |
| assert (conflict); | |
| LOG (conflict, "lrat for global empty clause with conflict"); | |
| for (auto &lit : *conflict) { | |
| assert (val (lit) < 0); | |
| int64_t id = unit_id (-lit); | |
| lrat_chain.push_back (id); | |
| } | |
| lrat_chain.push_back (conflict->id); | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| inline void Internal::search_assign (int lit, Clause *reason) { | |
| if (level) | |
| MODE_REQUIRE (SEARCH); | |
| assert (!flags (lit).unused ()); | |
| const int idx = vidx (lit); | |
| const bool from_external = reason == external_reason; | |
| assert (!val (idx)); | |
| assert (!flags (idx).eliminated () || reason == decision_reason || | |
| reason == external_reason); | |
| Var &v = var (idx); | |
| int lit_level; | |
| assert (!lrat || level || reason == external_reason || | |
| reason == decision_reason || !lrat_chain.empty ()); | |
| // The following cases are explained in the two comments above before | |
| // 'decision_reason' and 'assignment_level'. | |
| // | |
| // External decision reason means that the propagation was done by | |
| // an external propagation and the reason clause not known (yet). | |
| // In that case it is assumed that the propagation is NOT out of | |
| // order (i.e. lit_level = level), because due to lazy explanation, | |
| // we can not calculate the real assignment level. | |
| // The function assignment_level () will also assign the current level | |
| // to literals with external reason. | |
| if (!reason) | |
| lit_level = 0; // unit | |
| else if (reason == decision_reason) | |
| lit_level = level, reason = 0; | |
| else | |
| lit_level = assignment_level (lit, reason); | |
| if (!lit_level) | |
| reason = 0; | |
| 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++; | |
| if (!lit_level && !from_external) | |
| learn_unit_clause (lit); // increases 'stats.fixed' | |
| assert (lit_level || !from_external); | |
| const signed char tmp = sign (lit); | |
| set_val (idx, tmp); | |
| assert (val (lit) > 0); // Just a bit paranoid but useful. | |
| assert (val (-lit) < 0); // Ditto. | |
| if (!searching_lucky_phases) | |
| phases.saved[idx] = tmp; // phase saving during search | |
| 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 | |
| if (watching ()) { | |
| const Watches &ws = watches (-lit); | |
| if (!ws.empty ()) { | |
| const Watch &w = ws[0]; | |
| __builtin_prefetch (&w, 0, 1); | |
| } | |
| } | |
| lrat_chain.clear (); | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| // External versions of 'search_assign' which are not inlined. They either | |
| // are used to assign unit clauses on the root-level, in 'decide' to assign | |
| // a decision or in 'analyze' to assign the literal 'driven' by a learned | |
| // clause. This happens far less frequently than the 'search_assign' above, | |
| // which is called directly in 'propagate' below and thus is inlined. | |
| void Internal::assign_unit (int lit) { | |
| assert (!level); | |
| search_assign (lit, 0); | |
| } | |
| // Just assume the given literal as decision (increase decision level and | |
| // assign it). This is used below in 'decide'. | |
| void Internal::search_assume_decision (int lit) { | |
| MODE_REQUIRE (SEARCH); | |
| assert (propagated == trail.size ()); | |
| new_trail_level (lit); | |
| notify_decision (); | |
| LOG ("search decide %d", lit); | |
| search_assign (lit, decision_reason); | |
| } | |
| void Internal::search_assign_driving (int lit, Clause *c) { | |
| MODE_REQUIRE (SEARCH); | |
| search_assign (lit, c); | |
| notify_assignments (); | |
| } | |
| void Internal::search_assign_external (int lit) { | |
| MODE_REQUIRE (SEARCH); | |
| search_assign (lit, external_reason); | |
| notify_assignments (); | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| // The 'propagate' function is usually the hot-spot of a CDCL SAT solver. | |
| // The 'trail' stack saves assigned variables and is used here as BFS queue | |
| // for checking clauses with the negation of assigned variables for being in | |
| // conflict or whether they produce additional assignments. | |
| // This version of 'propagate' uses lazy watches and keeps two watched | |
| // literals at the beginning of the clause. We also use 'blocking literals' | |
| // to reduce the number of times clauses have to be visited (2008 JSAT paper | |
| // by Chu, Harwood and Stuckey). The watches know if a watched clause is | |
| // binary, in which case it never has to be visited. If a binary clause is | |
| // falsified we continue propagating. | |
| // Finally, for long clauses we save the position of the last watch | |
| // replacement in 'pos', which in turn reduces certain quadratic accumulated | |
| // propagation costs (2013 JAIR article by Ian Gent) at the expense of four | |
| // more bytes for each clause. | |
| bool Internal::propagate () { | |
| if (level) | |
| MODE_REQUIRE (SEARCH); | |
| assert (!unsat); | |
| LOG ("starting propagate"); | |
| // IPASIR-UP make everything harder. | |
| if (!imports.empty ()) | |
| activating_all_new_imported_literals (); | |
| PROFILE_SCOPE (propagate); | |
| // Updating statistics counter in the propagation loops is costly so we | |
| // delay until propagation ran to completion. | |
| // | |
| int64_t before = propagated; | |
| int64_t ticks = 0; | |
| while (!conflict && 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; | |
| ticks += 1 + cache_lines (ws.size (), sizeof *i); | |
| while (i != eow) { | |
| const Watch w = *j++ = *i++; | |
| const signed char b = val (w.blit); | |
| LOG (w.clause, "checking"); | |
| if (b > 0) | |
| continue; // blocking literal satisfied | |
| if (w.binary ()) { | |
| // assert (w.clause->redundant || !w.clause->garbage); | |
| // 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) | |
| conflict = w.clause; // but continue ... | |
| else { | |
| build_chain_for_units (w.blit, w.clause, 0); | |
| search_assign (w.blit, w.clause); | |
| // lrat_chain.clear (); done in search_assign | |
| ticks++; | |
| } | |
| } else { | |
| assert (w.clause->size > 2); | |
| if (conflict) | |
| break; // Stop if there was a binary conflict already. | |
| // 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. | |
| ticks++; | |
| if (w.clause->garbage) { | |
| j--; | |
| continue; | |
| } | |
| literal_iterator lits = w.clause->begin (); | |
| assert (lits[0] == lit || lits[1] == lit); | |
| // Simplify code by forcing 'lit' to be the second literal in the | |
| // clause. This goes back to MiniSAT. We use a branch-less version | |
| // for conditionally swapping the first two literals, since it | |
| // turned out to be substantially faster than this one | |
| // | |
| // if (lits[0] == lit) swap (lits[0], lits[1]); | |
| // | |
| // which achieves the same effect, but needs a branch. | |
| // | |
| const int other = lits[0] ^ lits[1] ^ lit; | |
| const signed char u = val (other); // value of the other watch | |
| if (u > 0) | |
| j[-1].blit = other; // satisfied, just replace blit | |
| else { | |
| // This follows Ian Gent's (JAIR'13) idea of saving the position | |
| // of the last watch replacement. In essence it needs two copies | |
| // of the default search for a watch replacement (in essence the | |
| // code in the 'if (v < 0) { ... }' block below), one starting at | |
| // the saved position until the end of the clause and then if that | |
| // one failed to find a replacement another one starting at the | |
| // first non-watched literal until the saved position. | |
| const int size = w.clause->size; | |
| const literal_iterator middle = lits + w.clause->pos; | |
| const const_literal_iterator end = lits + size; | |
| literal_iterator k = middle; | |
| // Find replacement watch 'r' at position 'k' with value 'v'. | |
| assert (lits + 2 <= k); | |
| LOG (w.clause, "search starting at %d", w.clause->pos); | |
| int r = 0; | |
| signed char v = -1; | |
| while (k != end && (v = val (r = *k)) < 0) | |
| k++; | |
| if (v < 0) { // need second search starting at the head? | |
| k = lits + 2; | |
| assert (w.clause->pos <= size); | |
| while (k != middle && (v = val (r = *k)) < 0) | |
| k++; | |
| } | |
| w.clause->pos = k - lits; // always save position | |
| 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'. | |
| ticks++; | |
| } 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); | |
| search_assign (other, w.clause); | |
| // lrat_chain.clear (); done in search_assign | |
| ticks++; | |
| // Similar code is in the implementation of the SAT'18 paper on | |
| // chronological backtracking but in our experience, this code | |
| // first does not really seem to be necessary for correctness, | |
| // and further does not improve running time either. | |
| // | |
| if (opts.chrono > 1) { | |
| const int other_level = var (other).level; | |
| if (other_level > var (lit).level) { | |
| // The assignment level of the new unit 'other' is larger | |
| // than the assignment level of 'lit'. Thus we should find | |
| // another literal in the clause at that higher assignment | |
| // level and watch that instead of 'lit'. | |
| assert (size > 2); | |
| int pos, s = 0; | |
| for (pos = 2; pos < size; pos++) | |
| if (var (s = lits[pos]).level == other_level) | |
| break; | |
| assert (s); | |
| assert (pos < size); | |
| LOG (w.clause, "unwatch %d in", lit); | |
| lits[pos] = lit; | |
| lits[0] = other; | |
| lits[1] = s; | |
| watch_literal (s, lit, w.clause); | |
| j--; // Drop this watch from the watch list of 'lit'. | |
| } | |
| } | |
| } else { | |
| assert (u < 0); | |
| assert (v < 0); | |
| // The other watch is assigned false ('u < 0') and all other | |
| // literals as well (still 'v < 0'), thus we found a conflict. | |
| conflict = w.clause; | |
| break; | |
| } | |
| } | |
| } | |
| } | |
| if (j != i) { | |
| while (i != eow) | |
| *j++ = *i++; | |
| ws.resize (j - ws.begin ()); | |
| } | |
| } | |
| if (searching_lucky_phases) { | |
| stats.ticks += ticks; | |
| if (conflict) | |
| LOG (conflict, "ignoring lucky conflict"); | |
| } else { | |
| // Avoid updating stats eagerly in the hot-spot of the solver. | |
| // | |
| stats.propagations_search += propagated - before; | |
| stats.propagations += propagated - before; | |
| stable ? stats.ticks_search_stable += ticks | |
| : stats.ticks_search_unstable += ticks; | |
| stats.ticks += ticks; | |
| if (!conflict) | |
| no_conflict_until = propagated; | |
| else { | |
| if (stable) | |
| stats.stable_conflicts++; | |
| stats.conflicts++; | |
| LOG (conflict, "conflict"); | |
| // The trail before the current decision level was conflict free. | |
| // | |
| no_conflict_until = control[level].trail; | |
| } | |
| } | |
| if (conflict && randomized_deciding) { | |
| if (!--randomized_deciding) | |
| VERBOSE (3, "last random decision conflict"); | |
| } | |
| assert (ticks >= 0); | |
| return !conflict; | |
| } | |
| /*------------------------------------------------------------------------*/ | |
| void Internal::propergate () { | |
| assert (!conflict); | |
| assert (propagated == trail.size ()); | |
| while (propergated != trail.size ()) { | |
| const int lit = -trail[propergated++]; | |
| LOG ("propergating %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++; | |
| LOG (w.clause, "propergate"); | |
| if (w.binary ()) { | |
| assert (val (w.blit) > 0); | |
| continue; | |
| } | |
| 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); | |
| // TODO: check if u == 0 can happen. | |
| if (u > 0) | |
| continue; | |
| assert (u < 0); | |
| const int size = w.clause->size; | |
| const literal_iterator middle = lits + w.clause->pos; | |
| const const_literal_iterator end = lits + size; | |
| literal_iterator k = middle; | |
| int r = 0; | |
| signed char v = -1; | |
| 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++; | |
| } | |
| assert (lits + 2 <= k), assert (k <= w.clause->end ()); | |
| w.clause->pos = k - lits; | |
| assert (v > 0); | |
| LOG (w.clause, "unwatch %d in", lit); | |
| lits[0] = other; | |
| lits[1] = r; | |
| *k = lit; | |
| watch_literal (r, lit, w.clause); | |
| j--; | |
| } | |
| if (j != i) { | |
| while (i != eow) | |
| *j++ = *i++; | |
| ws.resize (j - ws.begin ()); | |
| } | |
| } | |
| } | |
| } // namespace CaDiCaL |