1 #include "internal.hpp"
2
3 namespace CaDiCaL {
4
5 /*------------------------------------------------------------------------*/
6
Internal()7 Internal::Internal ()
8 :
9 mode (SEARCH),
10 unsat (false),
11 iterating (false),
12 localsearching (false),
13 preprocessing (false),
14 force_saved_phase (false),
15 termination_forced (false),
16 searching_lucky_phases (false),
17 stable (false),
18 reported (false),
19 rephased (0),
20 vsize (0),
21 max_var (0),
22 level (0),
23 vals (0),
24 scinc (1.0),
25 scores (this),
26 conflict (0),
27 ignore (0),
28 propagated (0),
29 propagated2 (0),
30 best_assigned (0),
31 target_assigned (0),
32 no_conflict_until (0),
33 proof (0),
34 checker (0),
35 tracer (0),
36 opts (this),
37 #ifndef QUIET
38 profiles (this),
39 force_phase_messages (false),
40 #endif
41 arena (this),
42 prefix ("c "),
43 internal (this),
44 external (0)
45 {
46 control.push_back (Level (0, 0));
47 binary_subsuming.redundant = false;
48 binary_subsuming.size = 2;
49 }
50
~Internal()51 Internal::~Internal () {
52 for (const auto & c : clauses)
53 delete_clause (c);
54 if (proof) delete proof;
55 if (tracer) delete tracer;
56 if (checker) delete checker;
57 if (vals) { vals -= vsize; delete [] vals; }
58 }
59
60 /*------------------------------------------------------------------------*/
61
62 // Values in 'vals' can be accessed in the range '[-max_var,max_var]' that
63 // is directly by a literal. This is crucial for performance. By shifting
64 // the start of 'vals' appropriately, we achieve that negative offsets from
65 // the start of 'vals' can be used. We also need to set both values at
66 // 'lit' and '-lit' during assignments. In MiniSAT integer literals are
67 // encoded, using the least significant bit as negation. This avoids taking
68 // the 'abs ()' (as in our solution) and thus also avoids a branch in the
69 // hot-spot of the solver (clause traversal in propagation). That solution
70 // requires another (branch less) negation of the values though and
71 // debugging is harder since literals occur only encoded in clauses.
72 // The main draw-back of our solution is that we have to shift the memory
73 // and access it through negative indices, which looks less clean (but still
74 // as far I can tell is properly defined C / C++). You might a warning by
75 // static analyzers though. Clang with '--analyze' thought that this idiom
76 // would generate memory leak.
77
enlarge_vals(size_t new_vsize)78 void Internal::enlarge_vals (size_t new_vsize) {
79 signed_char * new_vals;
80 new_vals = new signed char [ 2*new_vsize ] { 0 };
81
82 // Warning that this produces a memory leak can be ignored.
83 //
84 new_vals += new_vsize;
85
86 if (vals) memcpy (new_vals - max_var, vals - max_var, 2*max_var + 1);
87 vals -= vsize;
88 delete [] vals;
89 vals = new_vals;
90 }
91
92 /*------------------------------------------------------------------------*/
93
94 template<class T>
enlarge_init(vector<T> & v,size_t N,const T & i)95 static void enlarge_init (vector<T> & v, size_t N, const T & i) {
96 while (v.size () < N)
97 v.push_back (i);
98 }
99
100 template<class T>
enlarge_only(vector<T> & v,size_t N)101 static void enlarge_only (vector<T> & v, size_t N) {
102 while (v.size () < N)
103 v.push_back (T ());
104 }
105
106 template<class T>
enlarge_zero(vector<T> & v,size_t N)107 static void enlarge_zero (vector<T> & v, size_t N) {
108 enlarge_init (v, N, (const T &) 0);
109 }
110
111 /*------------------------------------------------------------------------*/
112
enlarge(int new_max_var)113 void Internal::enlarge (int new_max_var) {
114 assert (!level);
115 size_t new_vsize = vsize ? 2*vsize : 1 + (size_t) new_max_var;
116 while (new_vsize <= (size_t) new_max_var) new_vsize *= 2;
117 LOG ("enlarge internal size from %zd to new size %zd", vsize, new_vsize);
118 // Ordered in the size of allocated memory (larger block first).
119 enlarge_only (wtab, 2*new_vsize);
120 enlarge_only (vtab, new_vsize);
121 enlarge_only (links, new_vsize);
122 enlarge_zero (btab, new_vsize);
123 enlarge_zero (stab, new_vsize);
124 enlarge_init (ptab, 2*new_vsize, -1);
125 enlarge_only (ftab, new_vsize);
126 enlarge_vals (new_vsize);
127 enlarge_zero (frozentab, new_vsize);
128 const Phase val = opts.phase ? 1 : -1;
129 enlarge_init (phases.saved, new_vsize, val);
130 enlarge_zero (phases.target, new_vsize);
131 enlarge_zero (phases.best, new_vsize);
132 enlarge_zero (phases.prev, new_vsize);
133 enlarge_zero (phases.min, new_vsize);
134 enlarge_zero (marks, new_vsize);
135 vsize = new_vsize;
136 }
137
init(int new_max_var)138 void Internal::init (int new_max_var) {
139 if (new_max_var <= max_var) return;
140 if (level) backtrack ();
141 LOG ("initializing %d internal variables from %d to %d",
142 new_max_var - max_var, max_var + 1, new_max_var);
143 if ((size_t) new_max_var >= vsize) enlarge (new_max_var);
144 #ifndef NDEBUG
145 for (int i = -new_max_var; i < -max_var; i++) assert (!vals[i]);
146 for (int i = max_var + 1; i <= new_max_var; i++) assert (!vals[i]);
147 for (int i = max_var + 1; i <= new_max_var; i++) assert (!btab[i]);
148 for (int i = 2*(max_var + 1); i <= 2*new_max_var+1; i++)
149 assert (ptab[i] == -1);
150 #endif
151 assert (!btab[0]);
152 int old_max_var = max_var;
153 max_var = new_max_var;
154 init_queue (old_max_var, new_max_var);
155 init_scores (old_max_var, new_max_var);
156 int initialized = new_max_var - old_max_var;
157 stats.vars += initialized;
158 stats.unused += initialized;
159 stats.inactive += initialized;
160 LOG ("finished initializing %d internal variables", initialized);
161 }
162
add_original_lit(int lit)163 void Internal::add_original_lit (int lit) {
164 assert (abs (lit) <= max_var);
165 if (lit) {
166 original.push_back (lit);
167 } else {
168 if (proof) proof->add_original_clause (original);
169 add_new_original_clause ();
170 original.clear ();
171 }
172 }
173
174 /*------------------------------------------------------------------------*/
175
176 // This is the main CDCL loop with interleaved inprocessing.
177
cdcl_loop_with_inprocessing()178 int Internal::cdcl_loop_with_inprocessing () {
179
180 int res = 0;
181
182 START (search);
183
184 if (stable) { START (stable); report ('['); }
185 else { START (unstable); report ('{'); }
186
187 while (!res) {
188 if (unsat) res = 20;
189 else if (!propagate ()) analyze (); // propagate and analyze
190 else if (iterating) iterate (); // report learned unit
191 else if (satisfied ()) res = 10; // found model
192 else if (terminating ()) break; // limit hit or async abort
193 else if (restarting ()) restart (); // restart by backtracking
194 else if (rephasing ()) rephase (); // reset variable phases
195 else if (reducing ()) reduce (); // collect useless clauses
196 else if (probing ()) probe (); // failed literal probing
197 else if (subsuming ()) subsume (); // subsumption algorithm
198 else if (eliminating ()) elim (); // variable elimination
199 else if (compacting ()) compact (); // collect variables
200 else res = decide (); // next decision
201 }
202
203 if (stable) { STOP (stable); report (']'); }
204 else { STOP (unstable); report ('}'); }
205
206 STOP (search);
207
208 return res;
209 }
210
211 /*------------------------------------------------------------------------*/
212
213 // Most of the limits are only initialized in the first 'solve' call and
214 // increased as in a stand-alone non-incremental SAT call except for those
215 // explicitly marked as being reset below.
216
init_limits()217 void Internal::init_limits () {
218
219 const bool incremental = lim.initialized;
220 if (incremental) LOG ("reinitializing limits incrementally");
221 else LOG ("initializing limits and increments");
222
223 const char * mode = 0;
224
225 /*----------------------------------------------------------------------*/
226
227 if (incremental) mode = "keeping";
228 else {
229 last.reduce.conflicts = -1;
230 lim.reduce = stats.conflicts + opts.reduceint;
231 mode = "initial";
232 }
233 (void) mode;
234 LOG ("%s reduce limit %" PRId64 " after %" PRId64 " conflicts",
235 mode, lim.reduce, lim.reduce - stats.conflicts);
236
237 /*----------------------------------------------------------------------*/
238
239 if (incremental) mode = "keeping";
240 else {
241 lim.flush = opts.flushint;
242 inc.flush = opts.flushint;
243 mode = "initial";
244 }
245 (void) mode;
246 LOG ("%s flush limit %" PRId64 " interval %" PRId64 "",
247 mode, lim.flush, inc.flush);
248
249 /*----------------------------------------------------------------------*/
250
251 if (incremental) mode = "keeping";
252 else {
253 lim.subsume = stats.conflicts + scale (opts.subsumeint);
254 mode = "initial";
255 }
256 (void) mode;
257 LOG ("%s subsume limit %" PRId64 " after %" PRId64 " conflicts",
258 mode, lim.subsume, lim.subsume - stats.conflicts);
259
260 /*----------------------------------------------------------------------*/
261
262 if (incremental) mode = "keeping";
263 else {
264 last.elim.marked = -1;
265 lim.elim = stats.conflicts + scale (opts.elimint);
266 mode = "initial";
267 }
268 (void) mode;
269 LOG ("%s elim limit %" PRId64 " after %" PRId64 " conflicts",
270 mode, lim.elim, lim.elim - stats.conflicts);
271
272 // Initialize and reset elimination bounds in any case.
273
274 lim.elimbound = opts.elimboundmin;
275 LOG ("elimination bound %" PRId64 "", lim.elimbound);
276
277 /*----------------------------------------------------------------------*/
278
279 if (incremental) mode = "keeping";
280 else {
281 lim.probe = stats.conflicts + opts.probeint;
282 mode = "initial";
283 }
284 (void) mode;
285 LOG ("%s probe limit %" PRId64 " after %" PRId64 " conflicts",
286 mode, lim.probe, lim.probe - stats.conflicts);
287
288 /*----------------------------------------------------------------------*/
289
290 if (!incremental) {
291
292 last.ternary.marked = -1; // TODO explain why this is necessary.
293
294 lim.compact = stats.conflicts + opts.compactint;
295 LOG ("initial compact limit %" PRId64 " increment %" PRId64 "",
296 lim.compact, lim.compact - stats.conflicts);
297 }
298
299 /*----------------------------------------------------------------------*/
300
301 // Initialize or reset 'rephase' limits in any case.
302
303 lim.rephase = stats.conflicts + opts.rephaseint;
304 lim.rephased[0] = lim.rephased[1] = 0;
305 LOG ("new rephase limit %" PRId64 " after %" PRId64 " conflicts",
306 lim.rephase, lim.rephase - stats.conflicts);
307
308 /*----------------------------------------------------------------------*/
309
310 // Initialize or reset 'restart' limits in any case.
311
312 lim.restart = stats.conflicts + opts.restartint;
313 LOG ("new restart limit %" PRId64 " increment %" PRId64 "",
314 lim.restart, lim.restart - stats.conflicts);
315
316 /*----------------------------------------------------------------------*/
317
318 // Initialize or reset 'report' limits in any case.
319
320 reported = false;
321 lim.report = 0;
322
323 /*----------------------------------------------------------------------*/
324
325 if (!incremental) {
326 stable = opts.stabilize && opts.stabilizeonly;
327 if (stable) LOG ("starting in always forced stable phase");
328 else LOG ("starting in default non-stable phase");
329 init_averages ();
330 } else if (opts.stabilize && opts.stabilizeonly) {
331 LOG ("keeping always forced stable phase");
332 assert (stable);
333 } else if (stable) {
334 LOG ("switching back to default non-stable phase");
335 stable = false;
336 swap_averages ();
337 } else LOG ("keeping non-stable phase");
338
339 inc.stabilize = opts.stabilizeint;
340 lim.stabilize = stats.conflicts + inc.stabilize;
341 LOG ("new stabilize limit %" PRId64 " after %" PRId64 " conflicts",
342 lim.stabilize, inc.stabilize);
343
344 if (opts.stabilize && opts.reluctant) {
345 LOG ("new restart reluctant doubling sequence period %d",
346 opts.reluctant);
347 reluctant.enable (opts.reluctant, opts.reluctantmax);
348 } else reluctant.disable ();
349
350 /*----------------------------------------------------------------------*/
351
352 // Conflict and decision limits.
353
354 if (inc.conflicts < 0) {
355 lim.conflicts = -1;
356 LOG ("no limit on conflicts");
357 } else {
358 lim.conflicts = stats.conflicts + inc.conflicts;
359 LOG ("conflict limit after %" PRId64 " conflicts at %" PRId64 " conflicts",
360 inc.conflicts, lim.conflicts);
361 }
362
363 if (inc.decisions < 0) {
364 lim.decisions = -1;
365 LOG ("no limit on decisions");
366 } else {
367 lim.decisions = stats.decisions + inc.decisions;
368 LOG ("conflict limit after %" PRId64 " decisions at %" PRId64 " decisions",
369 inc.decisions, lim.decisions);
370 }
371
372 /*----------------------------------------------------------------------*/
373
374 // Initial preprocessing and local search rounds.
375
376 if (inc.preprocessing <= 0) {
377 lim.preprocessing = 0;
378 LOG ("no preprocessing");
379 } else {
380 lim.preprocessing = inc.preprocessing;
381 LOG ("limiting to %d preprocessing rounds", lim.preprocessing);
382 }
383
384 if (inc.localsearch <= 0) {
385 lim.localsearch = 0;
386 LOG ("no local search");
387 } else {
388 lim.localsearch = inc.localsearch;
389 LOG ("limiting to %d local search rounds", lim.localsearch);
390 }
391
392 /*----------------------------------------------------------------------*/
393
394 lim.initialized = true;
395 }
396
397 /*------------------------------------------------------------------------*/
398
preprocess_round(int round)399 bool Internal::preprocess_round (int round) {
400 (void) round;
401 if (unsat) return false;
402 if (!max_var) return false;
403 START (preprocess);
404 struct { int64_t vars, clauses; } before, after;
405 before.vars = active ();
406 before.clauses = stats.current.irredundant;
407 stats.preprocessings++;
408 assert (!preprocessing);
409 preprocessing = true;
410 PHASE ("preprocessing", stats.preprocessings,
411 "starting round %" PRId64 " with %d variables and %" PRId64 " clauses",
412 round, before.vars, before.clauses);
413 int old_elimbound = lim.elimbound;
414 if (opts.probe) probe (false);
415 if (opts.elim) elim (false);
416 after.vars = active ();
417 after.clauses = stats.current.irredundant;
418 assert (preprocessing);
419 preprocessing = false;
420 PHASE ("preprocessing", stats.preprocessings,
421 "finished round %d with %" PRId64 " variables and %" PRId64 " clauses",
422 round, after.vars, after.clauses);
423 STOP (preprocess);
424 report ('P');
425 if (unsat) return false;
426 if (after.vars < before.vars) return true;
427 if (old_elimbound < lim.elimbound) return true;
428 return false;
429 }
430
preprocess()431 int Internal::preprocess () {
432 if (opts.simplify)
433 for (int i = 0; i < lim.preprocessing; i++)
434 if (!preprocess_round (i))
435 break;
436 if (unsat) return 20;
437 return 0;
438 }
439
440 /*------------------------------------------------------------------------*/
441
try_to_satisfy_formula_by_saved_phases()442 int Internal::try_to_satisfy_formula_by_saved_phases () {
443 LOG ("satisfying formula by saved phases");
444 assert (!level);
445 assert (!force_saved_phase);
446 assert (propagated == trail.size ());
447 force_saved_phase = true;
448 int res = 0;
449 while (!res) {
450 if (satisfied ()) {
451 LOG ("formula indeed satisfied by saved phases");
452 res = 10;
453 } else if (decide ()) {
454 LOG ("inconsistent assumptions with redundant clauses and phases");
455 res = 20;
456 } else if (!propagate ()) {
457 LOG ("saved phases do not satisfy redundant clauses");
458 assert (level > 0);
459 backtrack ();
460 conflict = 0; // ignore conflict
461 assert (!res);
462 break;
463 }
464 }
465 assert (force_saved_phase);
466 force_saved_phase = false;
467 return res;
468 }
469
470 /*------------------------------------------------------------------------*/
471
produce_failed_assumptions()472 void Internal::produce_failed_assumptions () {
473 LOG ("producing failed assumptions");
474 assert (!level);
475 assert (!assumptions.empty ());
476 while (!unsat) {
477 assert (!satisfied ());
478 if (decide ()) break;
479 while (!unsat && !propagate ())
480 analyze ();
481 }
482 if (unsat) LOG ("formula is actually unsatisfiable unconditionally");
483 else LOG ("assumptions indeed failing");
484 }
485
486 /*------------------------------------------------------------------------*/
487
local_search_round(int round)488 int Internal::local_search_round (int round) {
489
490 assert (round > 0);
491
492 if (unsat) return false;
493 if (!max_var) return false;
494
495 START_OUTER_WALK ();
496 assert (!localsearching);
497 localsearching = true;
498
499 // Determine propagation limit quadratically scaled with rounds.
500 //
501 int64_t limit = opts.walkmineff;
502 limit *= round;
503 if (LONG_MAX / round > limit) limit *= round;
504 else limit = LONG_MAX;
505
506 int res = walk_round (limit, true);
507
508 assert (localsearching);
509 localsearching = false;
510 STOP_OUTER_WALK ();
511
512 report ('L');
513
514 return res;
515 }
516
local_search()517 int Internal::local_search () {
518
519 if (unsat) return 0;
520 if (!max_var) return 0;
521 if (!opts.walk) return 0;
522
523 int res = 0;
524
525 for (int i = 1; !res && i <= lim.localsearch; i++)
526 res = local_search_round (i);
527
528 if (res == 10) {
529 LOG ("local search determined formula to be satisfiable");
530 assert (!stats.walk.minimum);
531 res = try_to_satisfy_formula_by_saved_phases ();
532 } else if (res == 20) {
533 LOG ("local search determined assumptions to be inconsistent");
534 assert (!assumptions.empty ());
535 produce_failed_assumptions ();
536 }
537
538 return res;
539 }
540
541 /*------------------------------------------------------------------------*/
542
solve()543 int Internal::solve () {
544 assert (clause.empty ());
545 START (solve);
546 if (level) backtrack ();
547 int res = 0;
548 if (unsat) {
549 LOG ("already inconsistent");
550 res = 20;
551 } else if (!propagate ()) {
552 LOG ("root level propagation produces conflict");
553 learn_empty_clause ();
554 res = 20;
555 } else {
556
557 init_limits ();
558
559 if (opts.restoreall <= 1 &&
560 external->tainted.empty ()) {
561 LOG ("no tainted literals and nothing to restore");
562 report ('*');
563 } else {
564 report ('+');
565 external->restore_clauses ();
566 internal->report ('r');
567 if (!unsat && !propagate ()) {
568 LOG ("root level propagation after restore produces conflict");
569 learn_empty_clause ();
570 res = 20;
571 }
572 }
573
574 if (!res) res = preprocess ();
575 if (!res) res = local_search ();
576 if (!res) res = lucky_phases ();
577 if (!res) {
578 if (terminating ()) res = 0;
579 else res = cdcl_loop_with_inprocessing ();
580 }
581 }
582 if (termination_forced) {
583 termination_forced = false;
584 LOG ("reset forced termination");
585 }
586 if (res == 10) report ('1');
587 else if (res == 20) report ('0');
588 else report ('?');
589 STOP (solve);
590 return res;
591 }
592
593 /*------------------------------------------------------------------------*/
594
print_stats()595 void Internal::print_stats () {
596 stats.print (this);
597 if (checker) checker->print_stats ();
598 }
599
600 /*------------------------------------------------------------------------*/
601
602 // Only useful for debugging purposes.
603
dump(Clause * c)604 void Internal::dump (Clause * c) {
605 for (const auto & lit : *c)
606 printf ("%d ", lit);
607 printf ("0\n");
608 }
609
dump()610 void Internal::dump () {
611 int64_t m = assumptions.size ();
612 for (int idx = 1; idx <= max_var; idx++)
613 if (fixed (idx)) m++;
614 for (const auto & c : clauses)
615 if (!c->garbage) m++;
616 printf ("p cnf %d %" PRId64 "\n", max_var, m);
617 for (int idx = 1; idx <= max_var; idx++) {
618 const int tmp = fixed (idx);
619 if (tmp) printf ("%d 0\n", tmp < 0 ? -idx : idx);
620 }
621 for (const auto & c : clauses)
622 if (!c->garbage) dump (c);
623 for (const auto & lit : assumptions)
624 printf ("%d 0\n", lit);
625 fflush (stdout);
626 }
627
628 /*------------------------------------------------------------------------*/
629
traverse_clauses(ClauseIterator & it)630 bool Internal::traverse_clauses (ClauseIterator & it) {
631 vector<int> eclause;
632 if (unsat) return it.clause (eclause);
633 for (const auto & c : clauses) {
634 if (c->garbage) continue;
635 if (c->redundant) continue;
636 bool satisfied = false;
637 for (const auto & ilit : *c) {
638 const int tmp = fixed (ilit);
639 if (tmp > 0) { satisfied = true; break; }
640 if (tmp < 0) continue;
641 const int elit = externalize (ilit);
642 eclause.push_back (elit);
643 }
644 if (!satisfied && !it.clause (eclause))
645 return false;
646 eclause.clear ();
647 }
648 return true;
649 }
650
651 }
652