[Synth][FunctionalReduction] Refine equiv class candidates using counterexamples
Nobody has claimed this yet.
- Dominant language
- C++
- Stars
- 2.2k
- Forks
- 524
- Avg merge
- 3d 2h
- Merged PRs (30d)
- 46
Description
When the SAT solver returns SAT, the resulting model provides a counterexample that distinguishes two nodes previously thought to be equivalent. This counterexample can be used to refine the entire set of candidates through resimulation: https://github.com/llvm/circt/blob/5e21c9594ca4bd4545fd8b4d8a07a6c6c68eb0c9/lib/Dialect/Synth/Transforms/FunctionalReduction.cpp#L571-L572
This is quite effective to reduce the number of SAT calls.
So certainly the API change would be:
struct CexPattern {
DenseMap<Value, bool> inputAssignment;
};
FailureOr<CexPattern> extractCounterexample();
DenseMap<Value, bool> simulateSinglePattern(const CexPattern &pattern);
void refineCandidateClass(SmallVector<std::pair<Value, bool>> &members,
const DenseMap<Value, bool> &bitValues,
SmallVector<SmallVector<std::pair<Value, bool>>> &newClasses);
and changing the verification loop from the current:
for (member in class.drop_front())
verifyEquivalence(representative, member);
into a worklist:
SmallVector<SmallVector<Value>> pending = {members};
while (!pending.empty()) {
auto cls = pending.pop_back_val();
if (cls.size() <= 1) continue;
Value repr = chooseRepresentative(cls);
SmallVector<Value> proved{repr};
SmallVector<Value> disproved;
for (Value member : drop_front(cls)) {
switch (verifyEquivalence(repr, member)) {
case Proved:
proved.push_back(member);
break;
case Disproved: {
auto cex = extractCounterexample();
auto eval = simulateSinglePattern(*cex);
SmallVector<SmallVector<Value>> split;
refineCandidateClass(cls, eval, split);
pending.append(split.begin(), split.end());
goto next_class;
}
case Unknown:
// Give up a member.
}
}
recordProvenClass(proved);
next_class:;
}
This is a rough sketch so there might be a better way to implement this.
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start in lib/Dialect/Synth/Transforms/FunctionalReduction.cpp at the counterexample handling around lines 571-572 and inspect the current verification loop. Trace verifyEquivalence and the proposed CexPattern, simulateSinglePattern, and refineCandidateClass APIs before choosing an implementation approach. Done means counterexamples resimulate and split candidate classes, reducing unnecessary SAT calls.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- compilers
- Issue type
- Feature
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 45/100