-
Notifications
You must be signed in to change notification settings - Fork 80
/
ands.c
88 lines (84 loc) · 2.32 KB
/
ands.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include "ands.h"
#include "eliminate.h"
#include "gates.h"
#include "inline.h"
bool kissat_find_and_gate (kissat *solver, unsigned lit,
unsigned negative) {
if (!GET_OPTION (ands))
return false;
size_t marked = kissat_mark_binaries (solver, lit);
if (!marked)
return false;
if (marked < 2) {
kissat_unmark_binaries (solver, lit);
return false;
}
unsigned not_lit = NOT (lit);
watches *not_watches = &WATCHES (not_lit);
ward *const arena = BEGIN_STACK (solver->arena);
value *marks = solver->marks;
const value *const values = solver->values;
clause *base = 0;
for (all_binary_large_watches (watch, *not_watches)) {
if (watch.type.binary)
continue;
const reference ref = watch.large.ref;
assert (ref < SIZE_STACK (solver->arena));
clause *c = (clause *) (arena + ref);
assert (!c->garbage);
base = c;
for (all_literals_in_clause (other, c)) {
if (other == not_lit)
continue;
const value value = values[other];
if (value > 0) {
kissat_eliminate_clause (solver, c, INVALID_LIT);
base = 0;
break;
}
if (value < 0)
continue;
const unsigned not_other = NOT (other);
signed char mark = marks[not_other];
if (mark)
continue;
base = 0;
break;
}
if (base)
break;
}
if (!base) {
kissat_unmark_binaries (solver, lit);
return false;
}
LOGCLS (base, "found and gate %s base clause", LOGLIT (not_lit));
for (all_literals_in_clause (other, base)) {
if (other == not_lit)
continue;
if (values[other])
continue;
const unsigned not_other = NOT (other);
assert (marks[not_other]);
marks[not_other] = 0;
}
watch tmp = kissat_binary_watch (0);
watches *watches = &WATCHES (lit);
for (all_binary_large_watches (watch, *watches)) {
if (!watch.type.binary)
continue;
const unsigned other = watch.binary.lit;
assert (!solver->values[other]);
if (marks[other]) {
marks[other] = 0;
continue;
}
tmp.binary.lit = other;
PUSH_STACK (solver->gates[negative], tmp);
}
tmp = kissat_large_watch (kissat_reference_clause (solver, base));
PUSH_STACK (solver->gates[!negative], tmp);
solver->gate_eliminated = GATE_ELIMINATED (ands);
INC (ands_extracted);
return true;
}