22#include "mlir/IR/PatternMatch.h"
23#include "llvm/Support/Debug.h"
25#define DEBUG_TYPE "llhd-desequentialization"
29#define GEN_PASS_DEF_DESEQUENTIALIZATION
30#include "circt/Dialect/LLHD/Transforms/LLHDPasses.h.inc"
48 APInt compute(ArrayRef<Value> primitives, ArrayRef<APInt> truthTable,
49 uint64_t width, Value root) {
50 assert(primitives.size() == truthTable.size() &&
"must have same size");
52 for (
auto [p, t] : llvm::zip(primitives, truthTable))
57 DenseSet<Operation *> visited;
58 SmallVector<Value> worklist;
59 worklist.push_back(root);
61 while (!worklist.empty()) {
62 auto curr = worklist.back();
63 if (results.contains(curr)) {
68 auto *defOp = curr.getDefiningOp();
74 if (!visited.contains(defOp)) {
75 visited.insert(defOp);
77 bool addedToWorklist =
78 TypeSwitch<Operation *, bool>(defOp)
80 worklist.append(llvm::to_vector(op->getOperands()));
83 .Case([&](comb::ICmpOp op) {
84 if ((op.getPredicate() == circt::comb::ICmpPredicate::eq ||
85 op.getPredicate() == circt::comb::ICmpPredicate::ne) &&
86 op.getLhs().getType().isSignlessInteger(1)) {
87 worklist.append(llvm::to_vector(op->getOperands()));
93 results[op.getResult()] = op.getValue().getBoolValue()
94 ? APInt::getAllOnes(width)
103 dispatchCombinationalVisitor(defOp);
107 return results[root];
111 auto res = APInt::getAllOnes(width);
112 for (
auto operand : op->getOperands())
113 res &= results[operand];
114 results[op.getResult()] = res;
118 auto res = APInt(width, 0);
119 for (
auto operand : op->getOperands())
120 res |= results[operand];
121 results[op.getResult()] = res;
125 auto res = results[op->getOperands()[0]];
126 for (
auto operand : op->getOperands().drop_front())
127 res ^= results[operand];
128 results[op.getResult()] = res;
131 void visitComb(comb::ICmpOp op) {
132 auto res = results[op.getLhs()];
133 res ^= results[op.getRhs()];
134 if (op.getPredicate() == comb::ICmpPredicate::eq)
135 res ^= APInt::getAllOnes(width);
136 results[op.getResult()] = res;
141 void visitComb(
comb::AddOp op) { visitInvalidComb(op); }
142 void visitComb(
comb::SubOp op) { visitInvalidComb(op); }
143 void visitComb(
comb::MulOp op) { visitInvalidComb(op); }
144 void visitComb(
comb::DivUOp op) { visitInvalidComb(op); }
145 void visitComb(
comb::DivSOp op) { visitInvalidComb(op); }
146 void visitComb(
comb::ModUOp op) { visitInvalidComb(op); }
147 void visitComb(
comb::ModSOp op) { visitInvalidComb(op); }
148 void visitComb(
comb::ShlOp op) { visitInvalidComb(op); }
149 void visitComb(
comb::ShrUOp op) { visitInvalidComb(op); }
150 void visitComb(
comb::ShrSOp op) { visitInvalidComb(op); }
153 void visitComb(comb::ReplicateOp op) { visitInvalidComb(op); }
155 void visitComb(
comb::MuxOp op) { visitInvalidComb(op); }
158 DenseMap<Value, APInt> results;
171 static StringRef stringify(
const Trigger::Kind &kind) {
173 case Trigger::Kind::PosEdge:
175 case Trigger::Kind::NegEdge:
177 case Trigger::Kind::Edge:
180 llvm::llvm_unreachable_internal(
"all cases considered above");
184 SmallVector<Value> clocks;
188 SmallVector<Kind> kinds;
197 return os << Trigger::stringify(kind);
205 DnfAnalyzer(Value value) : root(value) {
206 assert(value.getType().isSignlessInteger(1) &&
207 "only 1-bit signless integers supported");
210 LogicalResult prepareAnalyzer(function_ref<
bool(Value)> sampledInPast,
211 unsigned maxPrimitives) {
212 DenseSet<Value> alreadyAdded;
214 SmallVector<Value> worklist;
215 worklist.push_back(root);
217 while (!worklist.empty()) {
218 Value curr = worklist.pop_back_val();
219 auto *defOp = curr.getDefiningOp();
221 if (!alreadyAdded.contains(curr)) {
222 primitives.push_back(curr);
223 primitiveSampledInPast.push_back(sampledInPast(curr));
224 alreadyAdded.insert(curr);
229 TypeSwitch<Operation *>(defOp)
231 worklist.append(llvm::to_vector(op->getOperands()));
233 .Case([&](comb::ICmpOp op) {
234 if ((op.getPredicate() == circt::comb::ICmpPredicate::eq ||
235 op.getPredicate() == circt::comb::ICmpPredicate::ne) &&
236 op.getLhs().getType().isSignlessInteger(1)) {
237 worklist.append(llvm::to_vector(op->getOperands()));
239 if (!alreadyAdded.contains(curr)) {
240 primitives.push_back(curr);
241 primitiveSampledInPast.push_back(sampledInPast(curr));
242 alreadyAdded.insert(curr);
246 .Case<hw::ConstantOp>([](
auto op) { })
247 .Default([&](
auto op) {
248 if (!alreadyAdded.contains(curr)) {
249 primitives.push_back(curr);
250 primitiveSampledInPast.push_back(sampledInPast(curr));
251 alreadyAdded.insert(curr);
257 for (
auto val : primitives)
258 llvm::dbgs() <<
" - Primitive variable: " << val <<
"\n";
261 if (primitives.size() > maxPrimitives) {
262 LLVM_DEBUG({ llvm::dbgs() <<
" Too many primitives, skipping...\n"; });
266 this->isClock = SmallVector<bool>(primitives.size(),
false);
267 this->dontCare = SmallVector<APInt>(primitives.size(),
268 APInt(1ULL << primitives.size(), 0));
277 computeTriggers(OpBuilder &builder, Location loc,
278 function_ref<
bool(Value, Value)> sampledFromSameSignal,
279 SmallVectorImpl<Trigger> &triggers) {
286 if (failed(computeClockValuePairs(sampledFromSameSignal)))
290 simplifyTruthTable();
293 llvm::dbgs() <<
" - Truth table:\n";
295 for (
auto [t, d] :
llvm::zip(truthTable, dontCare))
296 llvm::dbgs() <<
" " <<
FVInt(std::move(t), std::move(d)) <<
"\n";
298 SmallVector<char> str;
302 for (
unsigned i = 0; i < result.getBitWidth() - str.size(); ++i)
305 llvm::dbgs() << str <<
"\n";
311 materializeTriggerEnables(builder, loc);
314 extractTriggerList(triggers);
317 canonicalizeTriggerList(triggers, builder, loc);
323 FVInt computeEnableKey(
unsigned tableRow) {
325 for (
unsigned k = 0; k < primitives.size(); ++k) {
326 if (dontCare[k][tableRow])
329 if (primitiveSampledInPast[k])
337 key.
setBit(k, truthTable[k][tableRow]);
343 void extractTriggerList(SmallVectorImpl<Trigger> &triggers) {
344 for (uint64_t i = 0, e = 1ULL << primitives.size(); i < e; ++i) {
348 auto key = computeEnableKey(i);
350 for (
auto clk : clockPairs) {
351 if (dontCare[
clk.second][i] && dontCare[
clk.first][i])
354 trigger.clocks.push_back(primitives[
clk.second]);
355 trigger.kinds.push_back(truthTable[
clk.second][i]
356 ? Trigger::Kind::PosEdge
357 : Trigger::Kind::NegEdge);
359 trigger.enable = enableMap[key];
361 if (!trigger.clocks.empty())
362 triggers.push_back(trigger);
366 void materializeTriggerEnables(OpBuilder &builder, Location loc) {
369 for (uint64_t i = 0, e = 1ULL << primitives.size(); i < e; ++i) {
373 auto key = computeEnableKey(i);
375 if (!enableMap.contains(key)) {
376 SmallVector<Value> conjuncts;
377 for (
unsigned k = 0; k < primitives.size(); ++k) {
381 if (primitiveSampledInPast[k])
389 if (truthTable[k][i]) {
390 conjuncts.push_back(primitives[k]);
394 builder.create<
comb::XorOp>(loc, primitives[k], trueVal));
396 if (!conjuncts.empty())
398 builder.createOrFold<
comb::AndOp>(loc, conjuncts,
false);
403 LogicalResult computeClockValuePairs(
404 function_ref<
bool(Value, Value)> sampledFromSameSignal) {
405 for (
unsigned k = 0; k < primitives.size(); ++k) {
409 for (
unsigned l = k + 1; l < primitives.size(); ++l) {
410 if (sampledFromSameSignal(primitives[k], primitives[l]) &&
411 (primitiveSampledInPast[k] != primitiveSampledInPast[l])) {
412 if (primitiveSampledInPast[k])
413 clockPairs.emplace_back(k, l);
415 clockPairs.emplace_back(l, k);
420 if (primitiveSampledInPast[k] && !isClock[k])
427 void simplifyTruthTable() {
428 uint64_t numEntries = 1 << primitives.size();
434 for (uint64_t i = 0; i < numEntries; ++i) {
438 for (uint64_t k = i + 1; k < numEntries; ++k) {
442 unsigned differenceCount = 0;
443 for (
unsigned l = 0; l < primitives.size(); ++l) {
444 if (truthTable[l][i] != truthTable[l][k])
446 if (differenceCount > 1)
450 if (differenceCount == 1) {
451 for (
unsigned l = 0; l < primitives.size(); ++l) {
452 dontCare[l].setBit(k);
453 if (truthTable[l][i] != truthTable[l][k])
454 dontCare[l].setBit(i);
461 void computeTruthTable() {
462 uint64_t numEntries = 1 << primitives.size();
463 for (
auto _ [[maybe_unused]] : primitives)
464 truthTable.push_back(APInt(numEntries, 0));
466 for (uint64_t i = 0; i < numEntries; ++i)
467 for (
unsigned k = 0; k < primitives.size(); ++k)
468 truthTable[k].setBitVal(i, APInt(64, i)[k]);
471 CombInterpreter().compute(primitives, truthTable, numEntries, root);
474 void canonicalizeTriggerList(SmallVectorImpl<Trigger> &triggers,
475 OpBuilder &builder, Location loc) {
476 for (
auto *iter1 = triggers.begin(); iter1 != triggers.end(); ++iter1) {
477 for (
auto *iter2 = iter1 + 1; iter2 != triggers.end(); ++iter2) {
478 if (iter1->clocks == iter2->clocks && iter1->kinds == iter2->kinds) {
480 builder.create<
comb::OrOp>(loc, iter1->enable, iter2->enable);
481 triggers.erase(iter2--);
491 SmallVector<Value> primitives;
492 SmallVector<bool> isClock;
493 SmallVector<bool> primitiveSampledInPast;
494 SmallVector<APInt> truthTable;
495 SmallVector<APInt> dontCare;
496 SmallVector<std::pair<unsigned, unsigned>> clockPairs;
497 DenseMap<FVInt, Value> enableMap;
501struct DesequentializationPass
502 :
public llhd::impl::DesequentializationBase<DesequentializationPass> {
503 DesequentializationPass()
504 : llhd::impl::DesequentializationBase<DesequentializationPass>() {}
505 DesequentializationPass(
const llhd::DesequentializationOptions &options)
506 : llhd::impl::DesequentializationBase<DesequentializationPass>(options) {
507 maxPrimitives.setValue(options.maxPrimitives);
509 void runOnOperation()
override;
510 void runOnProcess(llhd::ProcessOp procOp)
const;
512 isSupportedSequentialProcess(llhd::ProcessOp procOp,
514 SmallVectorImpl<Value> &observed)
const;
518LogicalResult DesequentializationPass::isSupportedSequentialProcess(
520 SmallVectorImpl<Value> &observed)
const {
529 llvm::dbgs() <<
" Combinational process -> no need to desequentialize\n";
534 if (numTRs > 2 || procOp.getBody().getBlocks().size() != 3) {
536 { llvm::dbgs() <<
" Complex sequential process -> not supported\n"; });
540 bool seenWait =
false;
541 WalkResult result = procOp.walk([&](llhd::WaitOp op) -> WalkResult {
542 LLVM_DEBUG({ llvm::dbgs() <<
" Analyzing Wait Operation:\n"; });
543 for (
auto obs : op.getObserved()) {
544 observed.push_back(obs);
545 LLVM_DEBUG({ llvm::dbgs() <<
" - Observes: " << obs <<
"\n"; });
547 LLVM_DEBUG({ llvm::dbgs() <<
"\n"; });
555 trAnalysis.
getBlockTR(op.getOperation()->getBlock())))
559 return WalkResult::advance();
562 if (result.wasInterrupted() || !seenWait) {
564 { llvm::dbgs() <<
" Complex sequential process -> not supported\n"; });
569 { llvm::dbgs() <<
" Sequential process, attempt lowering...\n"; });
574void DesequentializationPass::runOnProcess(llhd::ProcessOp procOp)
const {
576 std::string line(74,
'-');
577 llvm::dbgs() <<
"\n===" << line <<
"===\n";
578 llvm::dbgs() <<
"=== Process\n";
579 llvm::dbgs() <<
"===" << line <<
"===\n";
585 SmallVector<Value> observed;
586 if (failed(isSupportedSequentialProcess(procOp, trAnalysis, observed)))
589 OpBuilder builder(procOp);
590 WalkResult result = procOp.walk([&](llhd::DrvOp op) {
591 LLVM_DEBUG({ llvm::dbgs() <<
"\n Lowering Drive Operation\n"; });
593 if (!op.getEnable()) {
594 LLVM_DEBUG({ llvm::dbgs() <<
" - No enable condition -> skip\n"; });
595 return WalkResult::advance();
598 Location loc = op.getLoc();
599 builder.setInsertionPoint(op);
600 int presentTR = trAnalysis.
getBlockTR(op.getOperation()->getBlock());
602 auto sampledInPast = [&](Value value) ->
bool {
603 if (isa<BlockArgument>(value))
606 if (!procOp->isAncestor(value.getDefiningOp()))
609 return trAnalysis.
getBlockTR(value.getDefiningOp()->getBlock()) !=
613 LLVM_DEBUG({ llvm::dbgs() <<
" - Analyzing enable condition...\n"; });
615 SmallVector<Trigger> triggers;
616 auto sampledFromSameSignal = [](Value val1, Value val2) ->
bool {
617 if (
auto prb1 = val1.getDefiningOp<llhd::PrbOp>())
618 if (
auto prb2 = val2.getDefiningOp<llhd::PrbOp>())
619 return prb1.getSignal() == prb2.getSignal();
626 DnfAnalyzer analyzer(op.getEnable());
627 if (failed(analyzer.prepareAnalyzer(sampledInPast, maxPrimitives)) ||
628 failed(analyzer.computeTriggers(builder, loc, sampledFromSameSignal,
631 llvm::dbgs() <<
" Unable to compute trigger list for drive condition, "
634 return WalkResult::interrupt();
638 if (triggers.empty())
639 llvm::dbgs() <<
" - no triggers found!\n";
643 for (
auto trigger : triggers) {
644 llvm::dbgs() <<
" - Trigger\n";
645 for (
auto [clk, kind] :
llvm::zip(trigger.clocks, trigger.kinds))
646 llvm::dbgs() <<
" - " << kind <<
" "
647 <<
"clock: " <<
clk <<
"\n";
650 llvm::dbgs() <<
" with enable: " << trigger.enable <<
"\n";
655 if (triggers.size() > 2 || triggers.empty())
656 return WalkResult::interrupt();
659 if (triggers[0].clocks.size() != 1 || triggers[0].clocks.size() != 1)
660 return WalkResult::interrupt();
663 if (triggers[0].kinds[0] == Trigger::Kind::Edge)
664 return WalkResult::interrupt();
666 if (!llvm::any_of(observed, [&](Value val) {
667 return sampledFromSameSignal(val, triggers[0].clocks[0]) &&
668 val.getParentRegion() != procOp.getBody();
670 return WalkResult::interrupt();
672 Value clock = builder.create<seq::ToClockOp>(loc, triggers[0].clocks[0]);
673 Value reset, resetValue;
675 if (triggers[0].kinds[0] == Trigger::Kind::NegEdge)
676 clock = builder.create<seq::ClockInverterOp>(loc, clock);
678 if (triggers[0].enable)
679 clock = builder.create<seq::ClockGateOp>(loc, clock, triggers[0].enable);
681 if (triggers.size() == 2) {
683 if (triggers[1].clocks.size() != 1 || triggers[1].kinds.size() != 1)
684 return WalkResult::interrupt();
687 if (triggers[1].kinds[0] == Trigger::Kind::Edge)
688 return WalkResult::interrupt();
691 if (triggers[1].enable)
692 return WalkResult::interrupt();
694 if (!llvm::any_of(observed, [&](Value val) {
695 return sampledFromSameSignal(val, triggers[1].clocks[0]) &&
696 val.getParentRegion() != procOp.getBody();
698 return WalkResult::interrupt();
700 reset = triggers[1].clocks[0];
701 resetValue = op.getValue();
703 if (triggers[1].kinds[0] == Trigger::Kind::NegEdge) {
712 Value regOut = builder.create<
seq::CompRegOp>(loc, op.getValue(), clock,
715 op.getEnableMutable().clear();
716 op.getValueMutable().assign(regOut);
718 builder.
create<llhd::ConstantTimeOp>(loc, 0,
"ns", 0, 1);
719 op.getTimeMutable().assign(epsilonTime);
722 { llvm::dbgs() <<
" Lowered Drive Operation successfully!\n\n"; });
724 return WalkResult::advance();
727 if (result.wasInterrupted())
730 IRRewriter rewriter(builder);
731 auto &entryBlock = procOp.getBody().getBlocks().front();
734 for (Block &block : procOp.getBody().getBlocks()) {
735 block.getTerminator()->erase();
737 if (!block.isEntryBlock())
738 entryBlock.getOperations().splice(entryBlock.end(),
739 block.getOperations());
742 rewriter.inlineBlockBefore(&entryBlock, procOp);
745 LLVM_DEBUG({ llvm::dbgs() <<
"Lowered process successfully!\n"; });
748void DesequentializationPass::runOnOperation() {
751 llvm::make_early_inc_range(moduleOp.getOps<llhd::ProcessOp>()))
752 runOnProcess(procOp);
assert(baseType &&"element must be base type")
Four-valued arbitrary precision integers.
SmallString< 16 > toString(unsigned radix=10, bool uppercase=true) const
Convert an FVInt to a string.
static FVInt getAllX(unsigned numBits)
Construct an FVInt with all bits set to X.
void setBit(unsigned index, Bit bit)
Set the value of an individual bit.
This helps visit Combinational nodes.
create(cls, result_type, reset=None, reset_value=None, name=None, sym_name=None, **kwargs)
OS & operator<<(OS &os, const InnerSymTarget &target)
Printing InnerSymTarget's.
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
int getBlockTR(Block *) const
unsigned getNumTemporalRegions() const
bool hasSingleExitBlock(int tr) const