| #include "cover.hpp" | |
| #include "internal.hpp" | |
| #include "message.hpp" | |
| namespace CaDiCaL { | |
| #define FACTORS 1 | |
| #define QUOTIENT 2 | |
| #define NOUNTED 4 | |
| inline bool factor_occs_size::operator() (unsigned a, unsigned b) { | |
| const int comp = internal->opts.factorschedule; | |
| if (comp == 0) { | |
| size_t s = internal->occs (internal->u2i (a)).size (); | |
| size_t t = internal->occs (internal->u2i (b)).size (); | |
| if (s > t) | |
| return true; | |
| if (s < t) | |
| return false; | |
| } else if (comp == 1) { | |
| auto s = internal->score (internal->u2i (a)); | |
| auto t = internal->score (internal->u2i (b)); | |
| if (s > t) | |
| return true; | |
| if (s < t) | |
| return false; | |
| } else if (comp == 2) { | |
| size_t s = internal->bumped (internal->u2i (a)); | |
| size_t t = internal->bumped (internal->u2i (b)); | |
| if (s > t) | |
| return true; | |
| if (s < t) | |
| return false; | |
| } | |
| // else (comp == 3) and default if any value is the same. | |
| return a > b; | |
| } | |
| // do full occurence list as in elim.cpp but filter out useless clauses | |
| void Internal::factor_mode (bool redundant_only) { | |
| reset_watches (); | |
| assert (!watching ()); | |
| init_occs (); | |
| if (opts.factorxor && opts.factorsize > 2) | |
| init_noccs (); | |
| const int size_limit = opts.factorsize; | |
| vector<unsigned> bincount, largecount; | |
| const unsigned max_lit = 2 * (max_var + 1); | |
| enlarge_zero (bincount, max_lit); | |
| if (size_limit > 2) | |
| enlarge_zero (largecount, max_lit); | |
| vector<Clause *> candidates; | |
| int64_t &ticks = stats.ticks_factor; | |
| ticks += 1 + cache_lines (clauses.size (), sizeof (Clause *)); | |
| // push binary clauses on the occurrence stack. | |
| for (const auto &c : clauses) { | |
| ticks++; | |
| if (terminated_asynchronously ()) | |
| return; | |
| if (c->garbage) | |
| continue; | |
| if (redundant_only && !c->redundant) | |
| continue; | |
| if (!redundant_only && !opts.factorredundant && c->redundant) | |
| continue; | |
| if (!redundant_only && opts.factorredundant == 1 && c->redundant && | |
| c->size > 2) | |
| continue; | |
| if (c->size > size_limit) | |
| continue; | |
| if (c->size == 2) { | |
| const int lit = c->literals[0]; | |
| const int other = c->literals[1]; | |
| bincount[vlit (lit)]++; | |
| bincount[vlit (other)]++; | |
| occs (lit).push_back (c); | |
| occs (other).push_back (c); | |
| continue; | |
| } | |
| candidates.push_back (c); | |
| for (const auto &lit : *c) { | |
| largecount[vlit (lit)]++; | |
| } | |
| } | |
| if (size_limit == 2) | |
| return; | |
| // iterate counts of larger clauses rounds often. | |
| // longer clauses can always be useful with XORs. | |
| const unsigned rounds = opts.factorcandrounds; | |
| unsigned candidates_before = 0; | |
| for (unsigned round = 1; !opts.factorxor && round <= rounds; round++) { | |
| if (terminated_asynchronously ()) | |
| return; | |
| LOG ("factor round %d", round); | |
| if (candidates.size () == candidates_before) | |
| break; | |
| ticks += 1 + cache_lines (candidates.size (), sizeof (Clause *)); | |
| candidates_before = candidates.size (); | |
| vector<unsigned> newlargecount; | |
| enlarge_zero (newlargecount, max_lit); | |
| const auto begin = candidates.begin (); | |
| auto p = candidates.begin (); | |
| auto q = p; | |
| const auto end = candidates.end (); | |
| while (p != end) { | |
| Clause *c = *q++ = *p++; | |
| ticks++; | |
| for (const auto &lit : *c) { | |
| const auto idx = vlit (lit); | |
| if (bincount[idx] + largecount[idx] < 2) { | |
| q--; | |
| goto CONTINUE_WITH_NEXT_CLAUSE; | |
| } | |
| } | |
| for (const auto &lit : *c) { | |
| const auto idx = vlit (lit); | |
| newlargecount[idx]++; | |
| } | |
| CONTINUE_WITH_NEXT_CLAUSE: | |
| continue; | |
| } | |
| candidates.resize (q - begin); | |
| largecount.swap (newlargecount); | |
| } | |
| // finally push remaining clause on the occurrence stack | |
| for (const auto &c : candidates) { | |
| if (terminated_asynchronously ()) | |
| return; | |
| for (const auto &lit : *c) | |
| occs (lit).push_back (c); | |
| } | |
| PHASE ("factor", stats.factorings, | |
| "initialized %zd clauses using %" PRId64 " ticks", | |
| candidates.size (), ticks); | |
| } | |
| // go back to two watch scheme | |
| void Internal::reset_factor_mode () { | |
| reset_occs (); | |
| if (opts.factorxor && opts.factorsize > 2) | |
| reset_noccs (); | |
| init_watches (); | |
| connect_watches (); | |
| } | |
| Factoring::Factoring (Internal *i, int64_t l) | |
| : internal (i), limit (l), schedule (i) { | |
| const unsigned max_var = internal->max_var; | |
| const unsigned max_lit = 2 * (max_var + 1); | |
| initial = max_var; | |
| bound = internal->opts.factorbound - 1; | |
| if (internal->opts.factorboundelim) | |
| bound += internal->opts.elimboundmax; | |
| else | |
| bound += internal->lim.elimbound; | |
| enlarge_zero (count, max_lit); | |
| quotients.first = quotients.last = quotients.xorites = 0; | |
| } | |
| Factoring::~Factoring () { | |
| // breaks when memory allocation fails during factor | |
| // assert (counted.empty ()); | |
| // assert (nounted.empty ()); | |
| // assert (flauses.empty ()); | |
| internal->release_quotients (*this); | |
| schedule.erase (); // actually not necessary | |
| } | |
| double Internal::tied_next_factor_score (int lit) { | |
| double res = occs (lit).size (); | |
| LOG ("watches score %g of %d", res, lit); | |
| return res; | |
| } | |
| // the marks in cadical have 6 bits for marking but work on idx | |
| // to mark everything (FACTORS, QUOTIENT, NOUNTED) we shift the bits | |
| // depending on the sign of factor (+ bitmask) | |
| // i.e. if factor is positive, we apply a bitmask to only get | |
| // the first three bits (& 7u) | |
| // otherwise we leftshift by 3 (>> 3) to get the bits 4,5,6 | |
| // use markfact, unmarkfact, getfact for this purpose. | |
| // | |
| Quotient *Internal::new_quotient (Factoring &factoring, int factor) { | |
| assert (!getfact (factor, FACTORS)); | |
| markfact (factor, FACTORS); | |
| Quotient *res = new Quotient (factor); | |
| res->next = 0; | |
| res->matched = 0; | |
| Quotient *last = factoring.quotients.last; | |
| res->bid = 0; | |
| if (last) { | |
| assert (factoring.quotients.first); | |
| assert (!last->next); | |
| last->next = res; | |
| res->id = last->id + 1; | |
| } else { | |
| assert (!factoring.quotients.first); | |
| factoring.quotients.first = res; | |
| res->id = 0; | |
| } | |
| factoring.quotients.last = res; | |
| res->prev = last; | |
| LOG ("new quotient[%zu] with factor %d", res->id, factor); | |
| return res; | |
| } | |
| void Internal::release_quotients (Factoring &factoring) { | |
| for (Quotient *q = factoring.quotients.first, *next; q; q = next) { | |
| next = q->next; | |
| int factor = q->factor; | |
| assert (getfact (factor, FACTORS)); | |
| unmarkfact (factor, FACTORS); | |
| delete q; | |
| } | |
| if (factoring.quotients.xorites) { | |
| // these are not marked. | |
| delete factoring.quotients.xorites; | |
| } | |
| factoring.quotients.first = factoring.quotients.last = | |
| factoring.quotients.xorites = 0; | |
| } | |
| size_t Internal::first_factor (Factoring &factoring, int factor) { | |
| assert (!factoring.quotients.first); | |
| Quotient *quotient = new_quotient (factoring, factor); | |
| vector<Clause *> &qlauses = quotient->qlauses; | |
| int64_t ticks = 0; | |
| for (const auto &c : occs (factor)) { | |
| qlauses.push_back (c); | |
| ticks++; | |
| } | |
| size_t res = qlauses.size (); | |
| LOG ("quotient[0] factor %d size %zu", factor, res); | |
| // This invariant can of course be broken by previous factorings | |
| // assert (res > 1); | |
| stats.ticks_factor += ticks; | |
| return res; | |
| } | |
| void Internal::clear_nounted (vector<int> &nounted) { | |
| for (const auto &lit : nounted) { | |
| assert (getfact (lit, NOUNTED)); | |
| unmarkfact (lit, NOUNTED); | |
| } | |
| nounted.clear (); | |
| } | |
| void Internal::clear_flauses (vector<Clause *> &flauses) { | |
| for (auto c : flauses) { | |
| assert (c->swept); | |
| c->swept = false; | |
| } | |
| flauses.clear (); | |
| } | |
| // Compute an xor or ite quotient. Use noccs to count the number of matches | |
| // for each second potential literal. Reset by using a vector. | |
| Quotient *Internal::xorite_quotient (Factoring &factoring, int first_factor, | |
| int *reduction_ptr) { | |
| LOG ("xorite for %d", first_factor); | |
| // fast skip if the maximum number of matched clauses is to low | |
| // factoring.bound is at least -1 | |
| #if 0 // sanity check that noccs are used correctly | |
| for (auto &lit : lits) { | |
| assert (!noccs (lit)); | |
| } | |
| #endif | |
| const size_t min_match_limit = 5 + factoring.bound; | |
| if (occs (first_factor).size () < min_match_limit || | |
| occs (-first_factor).size () < min_match_limit) | |
| return 0; | |
| if (val (first_factor)) | |
| return 0; | |
| // init quotient. | |
| Quotient *res = new Quotient (first_factor); | |
| DeferDeletePtr<Quotient> delete_res (res); | |
| // these are set to 0 for sanity (but not used). | |
| res->next = 0; | |
| res->prev = 0; | |
| res->matched = 0; | |
| res->bid = 0; | |
| res->id = 0; | |
| vector<int> seconds; | |
| vector<int> thirds; | |
| vector<int> pairs; | |
| // match clause c (containing first_factor) with | |
| // a clause d (containing -first_factor). | |
| // The two clauses should coincide except on one literal. | |
| const int64_t limit = factoring.limit; | |
| int64_t ticks = stats.ticks_factor; | |
| ticks += cache_lines (occs (first_factor).size (), sizeof (Clause *)); | |
| for (auto *c : occs (first_factor)) { | |
| ticks++; | |
| if (c->garbage) | |
| continue; | |
| if (c->size < 3) | |
| continue; | |
| if (ticks > limit) | |
| break; | |
| if (terminated_asynchronously ()) | |
| break; | |
| for (auto &lit : *c) { | |
| markfact (lit, NOUNTED); | |
| } | |
| ticks += cache_lines (occs (-first_factor).size (), sizeof (Clause *)); | |
| for (auto *d : occs (-first_factor)) { | |
| ticks++; | |
| if (d->garbage) | |
| continue; | |
| if (d->size != c->size) | |
| continue; | |
| if (ticks > limit) | |
| break; | |
| bool matched = true; | |
| int other = 0; | |
| for (auto &lit : *d) { | |
| // match with c. | |
| if (lit == -first_factor) | |
| continue; | |
| if (getfact (lit, NOUNTED)) | |
| continue; | |
| if (other) { | |
| matched = false; | |
| break; | |
| } | |
| other = lit; | |
| } | |
| if (!matched) | |
| continue; | |
| if (!other) // Technically self-subsuming but continue | |
| continue; | |
| if (!noccs (abs (other))++) { | |
| thirds.push_back (abs (other)); | |
| } | |
| pairs.push_back (0); | |
| pairs.push_back (other); | |
| res->qlauses.push_back (c); | |
| res->qlauses.push_back (d); | |
| LOG (c, "xorite factor matched first"); | |
| LOG (d, "xorite factor matched second"); | |
| // also continue... | |
| } | |
| for (auto &lit : *c) { | |
| unmarkfact (lit, NOUNTED); | |
| } | |
| } | |
| { | |
| // drop candidates that did not have enough matches. | |
| const auto end = thirds.end (); | |
| auto begin = thirds.begin (); | |
| auto p = begin; | |
| auto q = begin; | |
| while (p != end) { | |
| const auto &lit = *q++ = *p++; | |
| const auto tmp = noccs (lit); | |
| noccs (lit) = 0; | |
| if (tmp < min_match_limit) { | |
| q--; | |
| LOG ("dropping candidate third %d with %" PRIu64 " matches", lit, | |
| tmp); | |
| } | |
| LOG ("keeping candidate third %d with %" PRIu64 " matches", lit, tmp); | |
| } | |
| thirds.resize (q - begin); | |
| } | |
| // find highest pair count (using noccs). | |
| size_t matches = 0; | |
| int best_second = 0; | |
| int best_third = 0; | |
| for (auto &third : thirds) { | |
| if (res->qlauses.size () < 2 * min_match_limit) | |
| break; | |
| ticks += cache_lines (res->qlauses.size (), sizeof (Clause *)); | |
| for (size_t idx = 0; 2 * idx < res->qlauses.size (); idx++) { | |
| int pair = pairs[2 * idx + 1]; | |
| if (pair != third && pair != -third) | |
| continue; | |
| Clause *c = res->qlauses[2 * idx]; | |
| Clause *d = res->qlauses[2 * idx + 1]; | |
| for (auto &lit : *d) { | |
| markfact (lit, NOUNTED); | |
| } | |
| int other = 0; | |
| for (auto &lit : *c) { | |
| if (lit == first_factor) | |
| continue; | |
| if (getfact (lit, NOUNTED)) | |
| continue; | |
| assert (!other); | |
| other = lit; | |
| } | |
| assert (other); | |
| assert (pairs.size () > 2 * idx && !pairs[2 * idx]); | |
| pairs[2 * idx] = other; | |
| for (auto &lit : *d) { | |
| unmarkfact (lit, NOUNTED); | |
| } | |
| LOG ("factor pair (%d, %d)", other, pair); | |
| if (pair == -third) | |
| other = -other; | |
| if (!noccs (other)++) | |
| seconds.push_back (other); | |
| } | |
| // noccs (other) contains count for (third, other) and (-third, -other). | |
| // seconds may contain both other and -other. | |
| for (auto &other : seconds) { | |
| const uint64_t tmp = noccs (other); | |
| noccs (other) = 0; | |
| if (opts.factorxorite == 0 && other != -third) | |
| continue; | |
| if (opts.factorxorite == 2 && other == -third) | |
| continue; | |
| if (tmp > matches) { | |
| matches = tmp; | |
| best_second = other; | |
| best_third = third; | |
| } else if (!opts.factorxorrand && tmp == matches && other != -third) { | |
| matches = tmp; | |
| best_second = other; | |
| best_third = third; | |
| } else if (opts.factorxorrand && tmp == matches) { | |
| Random random (internal->opts.seed); | |
| random += stats.factorings + other; | |
| if (random.generate_bool ()) { | |
| matches = tmp; | |
| best_second = other; | |
| best_third = third; | |
| } | |
| } | |
| } | |
| } | |
| stats.ticks_factor = ticks; | |
| // Remove all clauses except for the best. | |
| // Ensure that no clause is kept multiple times (due to duplicated | |
| // matching clause) with the "swept" flag. | |
| // Unfortunately this can lead to fewer matches. | |
| auto begin = res->qlauses.begin (); | |
| auto p = res->qlauses.begin (); | |
| auto q = res->qlauses.begin (); | |
| auto end = res->qlauses.end (); | |
| size_t idx = 0; | |
| while (p != end) { | |
| Clause *c = *q++ = *p++; | |
| Clause *d = *q++ = *p++; | |
| int second = pairs[idx++]; | |
| int third = pairs[idx++]; | |
| bool parity = false; | |
| if (second == best_second && third == best_third) | |
| parity = true; | |
| else if (second == -best_second && third == -best_third) | |
| parity = false; | |
| else { | |
| q -= 2; | |
| continue; | |
| } | |
| if (c->swept || d->swept) { | |
| q -= 2; | |
| LOG ("factor decrement matches due to duplicate clause"); | |
| assert (matches); | |
| matches -= 1; | |
| continue; | |
| } | |
| // remember wether we matched on second or third for later. | |
| res->matches.push_back (parity); | |
| c->swept = true; | |
| d->swept = true; | |
| // keep and continue. | |
| } | |
| res->qlauses.resize (q - begin); | |
| res->second = best_second; | |
| res->third = best_third; | |
| for (auto c : res->qlauses) { | |
| assert (c->swept); | |
| c->swept = false; | |
| } | |
| #if 0 // sanity check that noccs are used correctly | |
| for (auto &lit : lits) { | |
| assert (!noccs (lit)); | |
| } | |
| #endif | |
| assert (res->qlauses.size () == 2 * matches); | |
| *reduction_ptr = matches - 4; | |
| assert (!factoring.quotients.xorites); | |
| factoring.quotients.xorites = res; | |
| delete_res.release (); | |
| return res; | |
| } | |
| Quotient *Internal::best_quotient (Factoring &factoring, | |
| int *best_reduction_ptr) { | |
| size_t factors = 1, best_reduction = 0; | |
| Quotient *best = 0; | |
| for (Quotient *q = factoring.quotients.first; q; q = q->next) { | |
| size_t quotients = q->qlauses.size (); | |
| size_t before_factorization = quotients * factors; | |
| size_t after_factorization = quotients + factors; | |
| if (before_factorization == after_factorization) | |
| LOG ("quotient[%zu] factors %zu clauses into %zu thus no change", | |
| factors - 1, before_factorization, after_factorization); | |
| else if (before_factorization < after_factorization) | |
| LOG ("quotient[%zu] factors %zu clauses into %zu thus %zu more", | |
| factors - 1, before_factorization, after_factorization, | |
| after_factorization - before_factorization); | |
| else { | |
| size_t delta = before_factorization - after_factorization; | |
| LOG ("quotient[%zu] factors %zu clauses into %zu thus %zu less", | |
| factors - 1, before_factorization, after_factorization, delta); | |
| if (!best || best_reduction < delta) { | |
| best_reduction = delta; | |
| best = q; | |
| } | |
| } | |
| factors++; | |
| } | |
| if (!best) { | |
| LOG ("no decreasing quotient found"); | |
| return 0; | |
| } | |
| LOG ("best decreasing quotient[%zu] with reduction %zu", best->id, | |
| best_reduction); | |
| *best_reduction_ptr = best_reduction; | |
| return best; | |
| } | |
| int Internal::next_factor (Factoring &factoring, unsigned *next_count_ptr) { | |
| Quotient *last_quotient = factoring.quotients.last; | |
| assert (last_quotient); | |
| vector<Clause *> &last_clauses = last_quotient->qlauses; | |
| vector<unsigned> &count = factoring.count; | |
| vector<int> &counted = factoring.counted; | |
| vector<Clause *> &flauses = factoring.flauses; | |
| assert (counted.empty ()); | |
| assert (flauses.empty ()); | |
| const int initial = factoring.initial; | |
| int64_t ticks = 1 + cache_lines (last_clauses.size (), sizeof (Clause *)); | |
| for (auto c : last_clauses) { | |
| assert (!c->swept); | |
| int min_lit = 0; | |
| unsigned factors = 0; | |
| size_t min_size = 0; | |
| ticks++; | |
| for (const auto &other : *c) { | |
| if (getfact (other, FACTORS)) { | |
| if (factors++) | |
| break; | |
| } else { | |
| assert (!getfact (other, QUOTIENT)); | |
| markfact (other, QUOTIENT); | |
| const size_t other_size = occs (other).size (); | |
| if (!min_lit || other_size < min_size) { | |
| min_lit = other; | |
| min_size = other_size; | |
| } | |
| } | |
| } | |
| assert (factors); | |
| if (factors == 1) { | |
| assert (min_lit); | |
| const int c_size = c->size; | |
| vector<int> &nounted = factoring.nounted; | |
| assert (nounted.empty ()); | |
| ticks += 1 + cache_lines (occs (min_lit).size (), sizeof (Clause *)); | |
| for (auto d : occs (min_lit)) { | |
| if (c == d) | |
| continue; | |
| ticks++; | |
| if (d->swept) | |
| continue; | |
| if (d->size != c_size) | |
| continue; | |
| int next = 0; | |
| for (const auto &other : *d) { | |
| if (getfact (other, QUOTIENT)) | |
| continue; | |
| if (getfact (other, FACTORS)) | |
| goto CONTINUE_WITH_NEXT_MIN_WATCH; | |
| if (getfact (other, NOUNTED)) | |
| goto CONTINUE_WITH_NEXT_MIN_WATCH; | |
| if (next) | |
| goto CONTINUE_WITH_NEXT_MIN_WATCH; | |
| next = other; | |
| } | |
| assert (next); | |
| if (abs (next) > abs (initial)) | |
| continue; | |
| if (!active (next)) | |
| continue; | |
| assert (!getfact (next, FACTORS)); | |
| assert (!getfact (next, NOUNTED)); | |
| markfact (next, NOUNTED); | |
| nounted.push_back (next); | |
| d->swept = true; | |
| flauses.push_back (d); | |
| if (!count[vlit (next)]) | |
| counted.push_back (next); | |
| count[vlit (next)]++; | |
| CONTINUE_WITH_NEXT_MIN_WATCH:; | |
| } | |
| clear_nounted (nounted); | |
| } | |
| for (const auto &other : *c) | |
| if (getfact (other, QUOTIENT)) | |
| unmarkfact (other, QUOTIENT); | |
| stats.ticks_factor += ticks; | |
| ticks = 0; | |
| if (stats.ticks_factor > factoring.limit) | |
| break; | |
| } | |
| clear_flauses (flauses); | |
| unsigned next_count = 0; | |
| int next = 0; | |
| if (stats.ticks_factor <= factoring.limit) { | |
| unsigned ties = 0; | |
| for (const auto &lit : counted) { | |
| const unsigned lit_count = count[vlit (lit)]; | |
| if (lit_count < next_count) | |
| continue; | |
| if (lit_count == next_count) { | |
| assert (lit_count); | |
| ties++; | |
| } else { | |
| assert (lit_count > next_count); | |
| next_count = lit_count; | |
| next = lit; | |
| ties = 1; | |
| } | |
| } | |
| if (next_count < 2) { | |
| LOG ("next factor count %u smaller than 2", next_count); | |
| next = 0; | |
| } else if (ties > 1) { | |
| LOG ("found %u tied next factor candidate literals with count %u", | |
| ties, next_count); | |
| double next_score = -1; | |
| for (const auto &lit : counted) { | |
| const unsigned lit_count = count[vlit (lit)]; | |
| if (lit_count != next_count) | |
| continue; | |
| double lit_score = tied_next_factor_score (lit); | |
| assert (lit_score >= 0); | |
| LOG ("score %g of next factor candidate %d", lit_score, lit); | |
| if (lit_score <= next_score) | |
| continue; | |
| next_score = lit_score; | |
| next = lit; | |
| } | |
| assert (next_score >= 0); | |
| assert (next); | |
| LOG ("best score %g of next factor %d", next_score, next); | |
| } else { | |
| assert (ties == 1); | |
| LOG ("single next factor %d with count %u", next, next_count); | |
| } | |
| } | |
| for (const auto &lit : counted) | |
| count[vlit (lit)] = 0; | |
| counted.clear (); | |
| assert (!next || next_count > 1); | |
| *next_count_ptr = next_count; | |
| return next; | |
| } | |
| void Internal::factorize_next (Factoring &factoring, int next, | |
| unsigned expected_next_count) { | |
| Quotient *last_quotient = factoring.quotients.last; | |
| Quotient *next_quotient = new_quotient (factoring, next); | |
| assert (last_quotient); | |
| vector<Clause *> &last_clauses = last_quotient->qlauses; | |
| vector<Clause *> &next_clauses = next_quotient->qlauses; | |
| vector<size_t> &matches = next_quotient->matches; | |
| vector<Clause *> &flauses = factoring.flauses; | |
| assert (flauses.empty ()); | |
| int64_t ticks = 1 + cache_lines (last_clauses.size (), sizeof (Clause *)); | |
| size_t i = 0; | |
| for (auto c : last_clauses) { | |
| assert (!c->swept); | |
| int min_lit = 0; | |
| unsigned factors = 0; | |
| size_t min_size = 0; | |
| ticks++; | |
| for (const auto &other : *c) { | |
| if (getfact (other, FACTORS)) { | |
| if (factors++) | |
| break; | |
| } else { | |
| assert (!getfact (other, QUOTIENT)); | |
| markfact (other, QUOTIENT); | |
| const size_t other_size = occs (other).size (); | |
| if (!min_lit || other_size < min_size) { | |
| min_lit = other; | |
| min_size = other_size; | |
| } | |
| } | |
| } | |
| assert (factors); | |
| if (factors == 1) { | |
| assert (min_lit); | |
| const int c_size = c->size; | |
| ticks += 1 + cache_lines (occs (min_lit).size (), sizeof (Clause *)); | |
| for (auto d : occs (min_lit)) { | |
| if (c == d) | |
| continue; | |
| ticks++; | |
| if (d->swept) | |
| continue; | |
| if (d->size != c_size) | |
| continue; | |
| for (const auto &other : *d) { | |
| if (getfact (other, QUOTIENT)) | |
| continue; | |
| if (other != next) | |
| goto CONTINUE_WITH_NEXT_MIN_WATCH; | |
| } | |
| LOG (c, "matched"); | |
| LOG (d, "keeping"); | |
| next_clauses.push_back (d); | |
| matches.push_back (i); | |
| flauses.push_back (d); | |
| d->swept = true; | |
| break; | |
| CONTINUE_WITH_NEXT_MIN_WATCH:; | |
| } | |
| } | |
| for (const auto &other : *c) | |
| if (getfact (other, QUOTIENT)) | |
| unmarkfact (other, QUOTIENT); | |
| i++; | |
| } | |
| clear_flauses (flauses); | |
| stats.ticks_factor += ticks; | |
| assert (expected_next_count <= next_clauses.size ()); | |
| (void) expected_next_count; | |
| } | |
| // We only need to enlarge factoring.count as everything else is | |
| // initialized in internal | |
| void Internal::resize_factoring (Factoring &factoring, int lit) { | |
| assert (lit > 0); | |
| size_t new_var_size = lit + 1; | |
| size_t new_lit_size = 2 * new_var_size; | |
| enlarge_zero (factoring.count, new_lit_size); | |
| } | |
| void Internal::flush_unmatched_clauses (Quotient *q) { | |
| Quotient *prev = q->prev; | |
| vector<size_t> &q_matches = q->matches, &prev_matches = prev->matches; | |
| vector<Clause *> &q_clauses = q->qlauses, &prev_clauses = prev->qlauses; | |
| const size_t n = q_clauses.size (); | |
| assert (n == q_matches.size ()); | |
| bool prev_is_first = !prev->id; | |
| size_t i = 0; | |
| while (i < q_matches.size ()) { | |
| size_t j = q_matches[i]; | |
| q_matches[i] = i; | |
| assert (i <= j); | |
| if (!prev_is_first) { | |
| size_t matches = prev_matches[j]; | |
| prev_matches[i] = matches; | |
| } | |
| Clause *c = prev_clauses[j]; | |
| prev_clauses[i] = c; | |
| i++; | |
| } | |
| LOG ("flushing %zu clauses of quotient[%zu]", prev_clauses.size () - n, | |
| prev->id); | |
| if (!prev_is_first) | |
| prev_matches.resize (n); | |
| prev_clauses.resize (n); | |
| } | |
| // special case when we have two quotients with negated factors. | |
| // in this case, factoring does not make sense, and instead we | |
| // can resolve the clauses of the two quotients. | |
| // this subsumes all clauses in all quotients. | |
| void Internal::add_self_subsuming_factor (Quotient *q, Quotient *p) { | |
| const int factor = q->factor; | |
| const int not_factor = p->factor; | |
| assert (-factor == not_factor); | |
| LOG ( | |
| "adding self subsuming factor because blocked clause is a tautology"); | |
| for (auto c : q->qlauses) { | |
| for (const auto &lit : *c) { | |
| if (lit == factor) | |
| continue; | |
| clause.push_back (lit); | |
| } | |
| if (lrat) { | |
| for (auto d : p->qlauses) { | |
| bool match = true; | |
| for (const auto &lit : *d) { | |
| if (lit == not_factor) | |
| continue; | |
| if (std::find (clause.begin (), clause.end (), lit) == | |
| clause.end ()) { | |
| match = false; | |
| break; | |
| } | |
| } | |
| if (match) { | |
| lrat_chain.push_back (d->id); | |
| break; | |
| } | |
| } | |
| lrat_chain.push_back (c->id); | |
| assert (lrat_chain.size () == 2); | |
| } | |
| if (clause.size () > 1) { | |
| new_factor_clause (0); | |
| } else { | |
| const int unit = clause[0]; | |
| const signed char tmp = val (unit); | |
| if (!tmp) | |
| assign_unit (unit); | |
| else if (tmp < 0) { | |
| if (lrat) { | |
| int64_t id = unit_id (-unit); | |
| lrat_chain.push_back (id); | |
| std::reverse (lrat_chain.begin (), lrat_chain.end ()); | |
| } | |
| learn_empty_clause (); | |
| clause.clear (); | |
| lrat_chain.clear (); | |
| break; | |
| } | |
| } | |
| clause.clear (); | |
| lrat_chain.clear (); | |
| } | |
| } | |
| bool Internal::self_subsuming_factor (Quotient *q) { | |
| Quotient *x = 0, *y = 0; | |
| bool found = false; | |
| for (Quotient *p = q; p; p = p->prev) { | |
| const int factor = p->factor; | |
| Flags &f = flags (factor); | |
| if (f.seen) { | |
| assert (std::find (analyzed.begin (), analyzed.end (), -factor) != | |
| analyzed.end ()); | |
| found = true; | |
| x = p; | |
| for (Quotient *r = q; r; r = r->prev) { | |
| if (r->factor != -factor) | |
| continue; | |
| y = r; | |
| break; | |
| } | |
| break; | |
| } | |
| analyzed.push_back (factor); | |
| f.seen = true; | |
| } | |
| assert (!found || (x && y)); | |
| clear_analyzed_literals (); | |
| if (found) { | |
| add_self_subsuming_factor (x, y); | |
| return true; | |
| } | |
| return false; | |
| } | |
| // this is a pure binary clauses containing fresh and one other literal | |
| // it is added for all applicable quotients. | |
| void Internal::add_factored_divider (Factoring &factoring, Quotient *q, | |
| int fresh) { | |
| const int factor = q->factor; | |
| LOG ("factored %d divider %d", factor, fresh); | |
| clause.push_back (fresh); | |
| clause.push_back (factor); | |
| factoring.fresh.back ().push_back (vidx (factor)); | |
| new_factor_clause (fresh); | |
| clause.clear (); | |
| if (lrat) | |
| mini_chain.push_back (-clause_id); | |
| } | |
| // this clause is blocked on fresh, i.e., it contains all literals from | |
| // the binaries above, but negated. This is only added to the proof, to | |
| // make checking easier. | |
| void Internal::blocked_clause (Quotient *q, int not_fresh) { | |
| if (!proof) | |
| return; | |
| int64_t new_id = ++clause_id; | |
| q->bid = new_id; | |
| assert (clause.empty ()); | |
| clause.push_back (not_fresh); | |
| for (Quotient *p = q; p; p = p->prev) | |
| clause.push_back (-p->factor); | |
| assert (!lrat || mini_chain.size ()); | |
| proof->add_derived_rat_clause (new_id, true, externalize (not_fresh), | |
| clause, mini_chain); | |
| mini_chain.clear (); | |
| clause.clear (); | |
| } | |
| // this is the other side of the factored clauses. To derive these, | |
| // one can resolved the blocked clause on all matching clauses of | |
| // one type | |
| void Internal::add_factored_quotient (Quotient *q, int not_fresh) { | |
| LOG ("adding factored quotient[%zu] clauses", q->id); | |
| const int factor = q->factor; | |
| assert (lrat_chain.empty ()); | |
| auto qlauses = q->qlauses; | |
| for (unsigned idx = 0; idx < qlauses.size (); idx++) { | |
| const auto c = qlauses[idx]; | |
| assert (clause.empty ()); | |
| for (const auto &other : *c) { | |
| if (other == factor) { | |
| continue; | |
| } | |
| clause.push_back (other); | |
| } | |
| if (lrat) { | |
| assert (proof); | |
| assert (q->bid); | |
| unsigned idxtoo = idx; | |
| for (Quotient *p = q; p; p = p->prev) { | |
| lrat_chain.push_back (p->qlauses[idxtoo]->id); | |
| if (p->prev) | |
| idxtoo = p->matches[idx]; | |
| } | |
| lrat_chain.push_back (q->bid); | |
| } | |
| clause.push_back (not_fresh); | |
| new_factor_clause (0); | |
| clause.clear (); | |
| lrat_chain.clear (); | |
| } | |
| if (proof) { | |
| clause.push_back (not_fresh); | |
| for (Quotient *p = q; p; p = p->prev) { | |
| clause.push_back (-p->factor); | |
| } | |
| proof->delete_clause (q->bid, true, clause); | |
| clause.clear (); | |
| } | |
| } | |
| // this adds first the ITE definition (fresh = if factor then second else | |
| // third) and then for each pair in qlauses the resulting unfactored clause. | |
| // XOR is just the special case where second = -third. | |
| void Internal::add_factor_xorite (Quotient *q, int fresh) { | |
| const int factor = q->factor; | |
| const int second = q->second; | |
| const int third = q->third; | |
| LOG ("factored ite %d = if %d then %d else %d", fresh, factor, second, | |
| third); | |
| assert (clause.empty ()); | |
| assert (lrat_chain.empty ()); | |
| { | |
| clause.push_back (fresh); | |
| clause.push_back (factor); | |
| clause.push_back (second); | |
| new_factor_clause (fresh); | |
| if (lrat) | |
| mini_chain.push_back (clause_id); | |
| clause.clear (); | |
| } | |
| { | |
| clause.push_back (fresh); | |
| clause.push_back (-factor); | |
| clause.push_back (third); | |
| new_factor_clause (fresh); | |
| if (lrat) { | |
| mini_chain.push_back (clause_id); | |
| // add the last two clauses | |
| lrat_chain.push_back (-clause_id); | |
| lrat_chain.push_back (-clause_id + 1); | |
| } | |
| clause.clear (); | |
| } | |
| { | |
| clause.push_back (-fresh); | |
| clause.push_back (factor); | |
| clause.push_back (-second); | |
| // but don't clear as lrat is the same. | |
| new_factor_clause (-fresh); | |
| if (lrat) | |
| mini_chain.push_back (clause_id); | |
| clause.clear (); | |
| } | |
| { | |
| clause.push_back (-fresh); | |
| clause.push_back (-factor); | |
| clause.push_back (-third); | |
| new_factor_clause (-fresh); | |
| if (lrat) { | |
| mini_chain.push_back (clause_id); | |
| lrat_chain.clear (); | |
| } | |
| clause.clear (); | |
| } | |
| // mini_chain contains the relevant ids. | |
| // add simplified clauses. | |
| for (size_t idx = 0; 2 * idx < q->qlauses.size (); idx++) { | |
| Clause *c = q->qlauses[2 * idx]; | |
| Clause *d = q->qlauses[2 * idx + 1]; | |
| // resolve tells us wether we matched on second or third. | |
| size_t resolve = q->matches[idx]; | |
| int64_t first_tmp_id = ++clause_id; | |
| int64_t second_tmp_id = ++clause_id; | |
| if (proof) { | |
| for (auto &lit : *c) { | |
| if (lit == second || lit == -second) | |
| continue; | |
| clause.push_back (lit); | |
| } | |
| if (!resolve) | |
| clause.push_back (fresh); | |
| else | |
| clause.push_back (-fresh); | |
| if (lrat) { | |
| lrat_chain.push_back (c->id); | |
| lrat_chain.push_back (mini_chain[resolve * 2]); | |
| } | |
| proof->add_derived_clause (first_tmp_id, true, clause, lrat_chain); | |
| lrat_chain.clear (); | |
| clause.clear (); | |
| for (auto &lit : *d) { | |
| if (lit == third || lit == -third) | |
| continue; | |
| clause.push_back (lit); | |
| } | |
| if (!resolve) | |
| clause.push_back (fresh); | |
| else | |
| clause.push_back (-fresh); | |
| if (lrat) { | |
| lrat_chain.push_back (d->id); | |
| lrat_chain.push_back (mini_chain[resolve * 2 + 1]); | |
| } | |
| proof->add_derived_clause (second_tmp_id, true, clause, lrat_chain); | |
| lrat_chain.clear (); | |
| clause.clear (); | |
| } | |
| // ite-clause could contain -second and -third. | |
| for (auto &lit : *c) { | |
| if (lit == factor) | |
| continue; | |
| else if (lit == -second) { | |
| assert (!resolve); | |
| continue; | |
| } else if (lit == second) { | |
| assert (resolve); | |
| continue; | |
| } | |
| clause.push_back (lit); | |
| } | |
| if (!resolve) | |
| clause.push_back (fresh); | |
| else | |
| clause.push_back (-fresh); | |
| if (lrat) { | |
| lrat_chain.push_back (first_tmp_id); | |
| lrat_chain.push_back (second_tmp_id); | |
| } | |
| new_factor_clause (0); | |
| lrat_chain.clear (); | |
| clause.clear (); | |
| if (proof) { | |
| // ite-clause could contain -second and -third. | |
| for (auto &lit : *c) { | |
| if (lit == second || lit == -second) | |
| continue; | |
| clause.push_back (lit); | |
| } | |
| if (!resolve) | |
| clause.push_back (fresh); | |
| else | |
| clause.push_back (-fresh); | |
| proof->delete_clause (first_tmp_id, true, clause); | |
| clause.clear (); | |
| // ite-clause could contain second and third. | |
| for (auto &lit : *d) { | |
| if (lit == third || lit == -third) | |
| continue; | |
| clause.push_back (lit); | |
| } | |
| if (!resolve) | |
| clause.push_back (fresh); | |
| else | |
| clause.push_back (-fresh); | |
| proof->delete_clause (second_tmp_id, true, clause); | |
| clause.clear (); | |
| } | |
| } | |
| mini_chain.clear (); | |
| } | |
| // remove deleted clauses once factored. | |
| void Internal::eagerly_remove_from_occurences (Clause *c) { | |
| for (const auto &lit : *c) { | |
| auto &occ = occs (lit); | |
| auto p = occ.begin (); | |
| auto q = occ.begin (); | |
| auto begin = occ.begin (); | |
| auto end = occ.end (); | |
| while (p != end) { | |
| *q = *p++; | |
| if (*q != c) | |
| q++; | |
| } | |
| assert (q + 1 == p); | |
| occ.resize (q - begin); | |
| } | |
| } | |
| // delete the factored clauses | |
| void Internal::delete_unfactored (Quotient *q) { | |
| LOG ("deleting unfactored quotient[%zu] clauses", q->id); | |
| for (auto c : q->qlauses) { | |
| eagerly_remove_from_occurences (c); | |
| mark_garbage (c); | |
| stats.factor_removed_lits += c->size; | |
| if (c->redundant) | |
| stats.factor_removed_red++; | |
| else | |
| stats.factor_removed_irr++; | |
| } | |
| } | |
| // update the priority queue for scheduling | |
| // NOTE: this temporarily breaks the heap invariant. | |
| void Internal::update_factored (Factoring &factoring, Quotient *q) { | |
| const int factor = q->factor; | |
| update_factor_candidate (factoring, factor); | |
| update_factor_candidate (factoring, -factor); | |
| for (auto c : q->qlauses) { | |
| LOG (c, "deleting unfactored"); | |
| for (const auto &lit : *c) | |
| if (lit != factor) | |
| update_factor_candidate (factoring, lit); | |
| } | |
| } | |
| bool Internal::apply_factoring (Factoring &factoring, Quotient *q) { | |
| for (Quotient *p = q; p->prev; p = p->prev) | |
| flush_unmatched_clauses (p); | |
| if (self_subsuming_factor (q)) { | |
| for (Quotient *p = q; p; p = p->prev) | |
| delete_unfactored (p); | |
| for (Quotient *p = q; p; p = p->prev) | |
| update_factored (factoring, p); | |
| return true; | |
| } | |
| const int fresh = get_new_extension_variable (); | |
| assert (!watching ()); | |
| if (!fresh) | |
| return false; | |
| stats.factored++; | |
| stats.factored_and++; | |
| factoring.fresh.emplace_back (); | |
| factoring.fresh.back ().push_back (fresh); | |
| for (Quotient *p = q; p; p = p->prev) | |
| add_factored_divider (factoring, p, fresh); | |
| const int not_fresh = -fresh; | |
| blocked_clause (q, not_fresh); | |
| add_factored_quotient (q, not_fresh); | |
| for (Quotient *p = q; p; p = p->prev) | |
| delete_unfactored (p); | |
| for (Quotient *p = q; p; p = p->prev) | |
| update_factored (factoring, p); | |
| assert (fresh > 0); | |
| resize_factoring (factoring, fresh); | |
| return true; | |
| } | |
| // XOR factoring. | |
| bool Internal::apply_xorite_factoring (Factoring &factoring, Quotient *q) { | |
| const int fresh = get_new_extension_variable (); | |
| if (!fresh) | |
| return false; | |
| factoring.fresh.emplace_back (); | |
| factoring.fresh.back ().push_back (fresh); | |
| factoring.fresh.back ().push_back (vidx (q->second)); | |
| stats.factored++; | |
| if (q->second == -q->third) | |
| stats.factored_xor++; | |
| else { | |
| stats.factored_ite++; | |
| factoring.fresh.back ().push_back (vidx (q->third)); | |
| } | |
| add_factor_xorite (q, fresh); | |
| delete_unfactored (q); | |
| update_factored (factoring, q); | |
| assert (fresh > 0); | |
| resize_factoring (factoring, fresh); | |
| return true; | |
| } | |
| void Internal::update_factor_candidate (Factoring &factoring, int lit) { | |
| FactorSchedule &schedule = factoring.schedule; | |
| const size_t size = occs (lit).size (); | |
| const unsigned idx = vlit (lit); | |
| if (schedule.contains (idx)) | |
| schedule.update (idx); | |
| else if (size > 1) { | |
| schedule.push_back (idx); | |
| } | |
| } | |
| void Internal::schedule_factorization (Factoring &factoring) { | |
| for (const auto &idx : vars) { | |
| if (active (idx)) { | |
| Flags &f = flags (idx); | |
| const int lit = idx; | |
| const int not_lit = -lit; | |
| if (f.factor & 1) | |
| update_factor_candidate (factoring, lit); | |
| if (f.factor & 2) | |
| update_factor_candidate (factoring, not_lit); | |
| } | |
| } | |
| #ifndef QUIET | |
| size_t size_cands = factoring.schedule.size (); | |
| VERBOSE (2, "scheduled %zu factorization candidate literals %.0f %%", | |
| size_cands, percent (size_cands, max_var)); | |
| #endif | |
| } | |
| void Internal::adjust_scores_and_phases_of_fresh_variables ( | |
| Factoring &factoring) { | |
| activating_all_new_imported_literals (); | |
| if (factoring.fresh.empty ()) | |
| return; | |
| // mark variables as elim candidates. | |
| if (opts.factorelim == 1) { | |
| for (auto def : factoring.fresh) { | |
| const auto &lit = def[0]; | |
| mark_elim (lit); | |
| } | |
| } // else if (opts.factorelim == 0) | |
| if (opts.factorbumpheap == 1) { | |
| const double delta = 1.0 / (double) (internal->max_var); | |
| for (auto def : factoring.fresh) { | |
| const auto &lit = def[0]; | |
| assert (lit > 0 && internal->max_var); | |
| const double old_score = score (lit); | |
| // COVER (!scores.contains (lit)); | |
| if (!scores.contains (lit)) | |
| continue; | |
| double new_score = old_score; | |
| for (const auto &other : def) { | |
| if (other == lit) | |
| continue; | |
| if (score (other) > new_score) | |
| new_score = score (other); | |
| } | |
| new_score += delta; | |
| LOG ("factor heap bumping %s=%lf (old=%lf)", LOGLIT (lit), new_score, | |
| old_score); | |
| score (lit) = new_score; | |
| scores.update (lit); | |
| } | |
| } else if (opts.factorbumpheap == 2) { | |
| double new_score = score_inc; | |
| for (auto idx : vars) { | |
| const double tmp = score (idx); | |
| if (tmp > new_score) | |
| new_score = tmp; | |
| } | |
| for (auto def : factoring.fresh) { | |
| const auto &lit = def[0]; | |
| assert (lit > 0 && internal->max_var); | |
| // COVER (!scores.contains (lit)); | |
| if (!scores.contains (lit)) | |
| continue; | |
| score (lit) = new_score; | |
| scores.update (lit); | |
| } | |
| } // else if (opts.factorbumpheap == 0) | |
| if (opts.factorbumpqueue == 0) { | |
| for (auto def : factoring.fresh) { | |
| const auto lit = def[0]; | |
| if (fixed (lit)) | |
| continue; | |
| LOG ("dequeuing %s", LOGLIT (lit)); | |
| queue.dequeue (links, lit); | |
| } | |
| for (auto def : factoring.fresh) { | |
| const auto &lit = def[0]; | |
| if (fixed (lit)) | |
| continue; | |
| LOG ("enqueuing %s at bottom", LOGLIT (lit)); | |
| queue.bury (links, lit); | |
| } | |
| // fix the scores with negative numbers | |
| int lit = queue.first; | |
| queue.bumped = 0; | |
| while (lit) { | |
| bumped (lit) = ++queue.bumped; | |
| lit = links[lit].next; | |
| } | |
| stats.vars_bumped = queue.bumped; | |
| update_queue_unassigned (queue.last); | |
| } else if (opts.factorbumpqueue == 1) { | |
| vector<int> replace; | |
| for (auto def : factoring.fresh) { | |
| const auto &lit = def[0]; | |
| if (fixed (lit)) | |
| continue; | |
| LOG ("dequeuing %s", LOGLIT (lit)); | |
| queue.dequeue (links, lit); | |
| int after = 0; | |
| int64_t score = 0; | |
| for (const auto &other : def) { | |
| if (other == lit) | |
| continue; | |
| // opts.reverse can lead to negative scores. | |
| if (!after || bumped (other) > score) { | |
| after = other; | |
| score = bumped (other); | |
| } | |
| } | |
| replace.push_back (after); | |
| } | |
| size_t i = 0; | |
| for (auto def : factoring.fresh) { | |
| const auto &lit = def[0]; | |
| if (fixed (lit)) | |
| continue; | |
| const auto &other = replace[i++]; | |
| if (fixed (lit)) | |
| continue; | |
| if (!other) { | |
| // this cover hit only after refining the semantics of | |
| // importing variables: | |
| // COVER (true); | |
| LOG ("enqueuing %s at bottom", LOGLIT (lit)); | |
| queue.bury (links, lit); | |
| } else if (!scores.contains (other)) { | |
| // This cover got triggered on the cluster: | |
| // COVER (!scores.contains (other)); | |
| LOG ("enqueuing %s at bottom", LOGLIT (lit)); | |
| queue.bury (links, lit); | |
| } else { | |
| LOG ("enqueuing %s after %s", LOGLIT (lit), LOGLIT (other)); | |
| queue.insert_after (links, lit, other); | |
| } | |
| } | |
| // fix the scores with negative numbers | |
| int lit = queue.first; | |
| queue.bumped = 0; | |
| while (lit) { | |
| bumped (lit) = ++queue.bumped; | |
| lit = links[lit].next; | |
| } | |
| stats.vars_bumped = queue.bumped; | |
| update_queue_unassigned (queue.last); | |
| } // else if (opts.factorbumpqueue == 2) | |
| #ifndef NDEBUG | |
| for (auto v : vars) | |
| assert (!flags (v).active () || val (v) || scores.contains (v)); | |
| int lit = queue.first; | |
| int next_lit = links[lit].next; | |
| while (next_lit) { | |
| assert (bumped (lit) < bumped (next_lit)); | |
| const int tmp = links[next_lit].next; | |
| assert (!tmp || links[tmp].prev == next_lit); | |
| lit = next_lit; | |
| next_lit = tmp; | |
| } | |
| lit = queue.last; | |
| next_lit = links[lit].prev; | |
| while (next_lit) { | |
| assert (bumped (lit) > bumped (next_lit)); | |
| const int tmp = links[next_lit].prev; | |
| assert (!tmp || links[tmp].next == next_lit); | |
| lit = next_lit; | |
| next_lit = tmp; | |
| } | |
| assert (queue.first); | |
| assert (queue.last); | |
| #endif | |
| factoring.fresh.clear (); | |
| } | |
| bool Internal::run_factorization (int64_t limit) { | |
| Factoring factoring = Factoring (this, limit); | |
| schedule_factorization (factoring); | |
| bool done = false; | |
| #ifndef QUIET | |
| unsigned factored = 0; | |
| #endif | |
| int64_t *ticks = &stats.ticks_factor; | |
| VERBOSE (3, "factorization limit of %" PRIu64 " ticks", limit - *ticks); | |
| while (!unsat && !done && !factoring.schedule.empty ()) { | |
| const unsigned ufirst = factoring.schedule.pop_front (); | |
| LOG ("next factor candidate %d", ufirst); | |
| const int first = u2i (ufirst); | |
| const int first_idx = vidx (first); | |
| if (!active (first_idx)) | |
| continue; | |
| if (!occs (first).size ()) { | |
| factoring.schedule.clear (); | |
| break; | |
| } | |
| if (*ticks > limit) { | |
| VERBOSE (2, "factorization ticks limit hit"); | |
| break; | |
| } | |
| if (terminated_asynchronously ()) // TODO: somehow a ticks update is | |
| // missed with this | |
| break; | |
| Flags &f = flags (first_idx); | |
| const unsigned bit = 1u << (first < 0); | |
| if (!(f.factor & bit)) | |
| continue; | |
| f.factor &= ~bit; | |
| const size_t first_count = first_factor (factoring, first); | |
| // extract XOR matches after the "normal" factors in this loop. | |
| if (first_count > 1) { | |
| for (; opts.factorxor < 2;) { | |
| unsigned next_count; | |
| const int next = next_factor (factoring, &next_count); | |
| if (next == 0) | |
| break; | |
| assert (next_count > 1); | |
| if (next_count < 2) | |
| break; | |
| factorize_next (factoring, next, next_count); | |
| } | |
| // only initialize to remove non-initialized warning later. | |
| int reduction = 0; | |
| // This is the best AND-gate factor (classical BVA). | |
| Quotient *q = best_quotient (factoring, &reduction); | |
| // only try XOR/ITE factoring once per variable | |
| // (as opposed to once per literal) | |
| if (opts.factorxor && opts.factorsize > 2 && | |
| (!opts.factorxorsave || (f.factor & (1u << (first > 0))))) { | |
| // Get an XOR quotient which is better then the best | |
| // classical quotient (or 0). | |
| int xorite_reduction = 0; | |
| Quotient *p = xorite_quotient (factoring, first, &xorite_reduction); | |
| LOG ("best xorite quotient with %d reduction in clauses", | |
| xorite_reduction); | |
| // need 4 clauses for xor or ite definition. | |
| // prefer XOR over AND gates. | |
| if (p && xorite_reduction >= reduction) { | |
| q = p; | |
| reduction = xorite_reduction; | |
| } | |
| } | |
| if (q && reduction > factoring.bound) { | |
| // q->second tells us wether we are doing XOR or AND factors. | |
| if (!q->second && apply_factoring (factoring, q)) { | |
| #ifndef QUIET | |
| factored++; | |
| #endif | |
| } else if (q->second && apply_xorite_factoring (factoring, q)) { | |
| #ifndef QUIET | |
| factored++; | |
| #endif | |
| } else | |
| done = true; | |
| } | |
| } | |
| release_quotients (factoring); | |
| } | |
| // since we cannot remove elements from the heap we check wether the | |
| // first element in the heap has occurences | |
| bool completed = factoring.schedule.empty (); | |
| if (!completed) { | |
| const unsigned idx = factoring.schedule.front (); | |
| completed = occs (u2i (idx)).empty (); | |
| } | |
| adjust_scores_and_phases_of_fresh_variables (factoring); | |
| #ifndef QUIET | |
| report ('f', !factored); | |
| #endif | |
| return completed; | |
| } | |
| // TODO: bump variable based on what definition is introduced. | |
| // i.e., use the variables... | |
| int Internal::get_new_extension_variable () { | |
| const int current_max_external = external->max_var; | |
| const int new_external = current_max_external + 1; | |
| const int new_internal = external->internalize (new_external, true); | |
| // one sideeffect of internalize is enlarging the internal datastructures | |
| // which can initialize the watches (wtab) | |
| if (watching ()) | |
| reset_watches (); | |
| // it does not enlarge otab, however, so we do this manually | |
| init_occs (); | |
| if (opts.factorxor && opts.factorsize > 2) | |
| init_noccs (); | |
| assert (vlit (new_internal)); | |
| return new_internal; | |
| } | |
| // TODO: redundant mode (+ flag for elim). | |
| bool Internal::factor () { | |
| if (unsat) | |
| return false; | |
| if (terminated_asynchronously ()) | |
| return false; | |
| if (!opts.factor) | |
| return false; | |
| int v_active = active (); | |
| if (!v_active) | |
| return false; | |
| size_t log_active = log10 (v_active); | |
| size_t eliminations = stats.eliminations; | |
| size_t delay = opts.factordelay; | |
| size_t delay_limit = eliminations + delay; | |
| if (delay && log_active > delay_limit) { | |
| VERBOSE (3, | |
| "factorization delayed as %zu = log10 (%u)" | |
| "> eliminations + delay = %zu + %zu = %zu", | |
| log_active, v_active, eliminations, delay, delay_limit); | |
| return false; | |
| } | |
| // The following assertion fails if there are *only* user propagator | |
| // clauses (which are redundant). | |
| // assert (stats.mark_factor || clauses.empty ()); | |
| if (last.factor.marked >= stats.mark_factor) { | |
| VERBOSE (3, | |
| "factorization skipped as no literals have been" | |
| "marked to be added (%" PRIu64 " < %" PRIu64 ")", | |
| last.factor.marked, stats.mark_factor); | |
| return false; | |
| } | |
| assert (!level); | |
| const bool is_preprocessing = !stats.factorings; | |
| SET_EFFORT_LIMIT (limit, factor, stats.factorings); | |
| if (preprocessing) | |
| limit += opts.factoriniticks * 1e6; | |
| mark_duplicated_binary_clauses_as_garbage (); | |
| MODE_SCOPE_SIMPLIFY (FACTOR); | |
| PROFILE_SCOPE_SIMPLIFY (factor); | |
| stats.factorings++; | |
| struct { | |
| int64_t | |
| #ifndef QUIET | |
| variables, | |
| clauses, | |
| #endif | |
| ticks; | |
| } before, after, delta; | |
| #ifndef QUIET | |
| before.variables = stats.variables_extension + stats.variables_original; | |
| before.clauses = stats.clauses_now_irr; | |
| #endif | |
| before.ticks = stats.ticks_factor; | |
| // TODO: redundant mode sometimes? | |
| factor_mode (!is_preprocessing && opts.factorredundant == 3); | |
| bool completed = run_factorization (limit); | |
| reset_factor_mode (); | |
| propagated = 0; | |
| if (!unsat && !propagate ()) { | |
| learn_empty_clause (); | |
| } | |
| after.ticks = stats.ticks_factor; | |
| delta.ticks = after.ticks - before.ticks; | |
| #ifndef QUIET | |
| after.variables = stats.variables_extension + stats.variables_original; | |
| after.clauses = stats.clauses_now_irr; | |
| delta.variables = after.variables - before.variables; | |
| delta.clauses = before.clauses - after.clauses; | |
| VERBOSE (2, "used %f million factorization ticks", delta.ticks * 1e-6); | |
| phase ("factorization", stats.factorings, | |
| "introduced %" PRId64 " extension variables %.0f%%", | |
| delta.variables, percent (delta.variables, before.variables)); | |
| phase ("factorization", stats.factorings, | |
| "removed %" PRId64 " irredundant clauses %.0f%%", delta.clauses, | |
| percent (delta.clauses, before.clauses)); | |
| #endif | |
| stats.ticks += delta.ticks; | |
| if (completed) | |
| last.factor.marked = stats.mark_factor; | |
| return true; | |
| } | |
| } // namespace CaDiCaL |