14#include "mlir/Analysis/Liveness.h"
15#include "mlir/Dialect/Arith/IR/Arith.h"
16#include "mlir/Dialect/ControlFlow/IR/ControlFlowOps.h"
17#include "mlir/IR/Dominance.h"
18#include "mlir/IR/IRMapping.h"
19#include "mlir/IR/Matchers.h"
20#include "mlir/Transforms/RegionUtils.h"
21#include "llvm/ADT/ScopeExit.h"
22#include "llvm/Support/Debug.h"
23#include "llvm/Support/GenericIteratedDominanceFrontier.h"
28#define DEBUG_TYPE "llhd-deseq"
29#define VERBOSE_DEBUG(...) DEBUG_WITH_TYPE(DEBUG_TYPE "-verbose", __VA_ARGS__)
33#define GEN_PASS_DEF_DESEQPASS
34#include "circt/Dialect/LLHD/Transforms/LLHDPasses.h.inc"
42using llvm::SmallSetVector;
47 Deseq(ProcessOp process) : process(process) {}
50 bool analyzeProcess();
51 Value tracePastValue(Value pastValue);
57 TruthTable computeBoolean(BlockArgument value);
59 TruthTable computeBlockCondition(Block *block);
60 TruthTable computeSuccessorCondition(BlockOperand &operand);
61 TruthTable computeSuccessorBoolean(BlockOperand &operand,
unsigned argIdx);
62 ValueTable computeSuccessorValue(BlockOperand &operand,
unsigned argIdx);
67 ArrayRef<std::pair<DNFTerm, ValueEntry>> valueTable);
70 ArrayRef<std::pair<DNFTerm, ValueEntry>> valueTable);
72 void implementRegisters();
75 Value specializeValue(Value value,
FixedValues fixedValues);
76 ValueRange specializeProcess(
FixedValues fixedValues);
84 SmallSetVector<Value, 2> triggers;
88 SmallVector<Value, 2> pastValues;
90 SmallVector<DriveInfo> driveInfos;
100 ConstantTimeOp epsilonDelay;
102 DenseMap<Operation *, bool> staticOps;
105 DenseMap<Value, TruthTable> booleanLattice;
108 DenseMap<Value, ValueTable> valueLattice;
112 DenseMap<Block *, TruthTable> blockConditionLattice;
115 DenseMap<BlockOperand *, TruthTable> successorConditionLattice;
118 DenseMap<std::pair<BlockOperand *, unsigned>,
TruthTable>
119 successorBooleanLattice;
122 DenseMap<std::pair<BlockOperand *, unsigned>,
ValueTable>
123 successorValueLattice;
133 TruthTable getConstBoolean(
bool value)
const {
136 TruthTable getPastTrigger(
unsigned triggerIndex)
const {
139 TruthTable getPresentTrigger(
unsigned triggerIndex)
const {
153 return ValueTable(getConstBoolean(
true), value);
163 if (!analyzeProcess())
166 llvm::dbgs() <<
"Desequentializing " << process.getLoc() <<
"\n";
167 llvm::dbgs() <<
"- Feeds " << driveInfos.size() <<
" conditional drives\n";
168 llvm::dbgs() <<
"- " << triggers.size() <<
" potential triggers:\n";
169 for (
auto [index, trigger] :
llvm::enumerate(triggers)) {
170 llvm::dbgs() <<
" - ";
171 trigger.printAsOperand(llvm::dbgs(), OpPrintingFlags());
172 llvm::dbgs() <<
": past " << getPastTrigger(index);
173 llvm::dbgs() <<
", present " << getPresentTrigger(index);
174 llvm::dbgs() <<
"\n";
186 implementRegisters();
199bool Deseq::analyzeProcess() {
202 for (
auto &block : process.getBody()) {
203 for (
auto &op : block) {
204 if (isa<WaitOp, HaltOp>(op))
206 if (!isMemoryEffectFree(&op)) {
208 llvm::dbgs() <<
"Skipping " << process.getLoc()
209 <<
": contains side-effecting op ";
210 op.print(llvm::dbgs(), OpPrintingFlags().skipRegions());
211 llvm::dbgs() <<
"\n";
219 for (
auto &block : process.getBody()) {
220 if (
auto candidate = dyn_cast<WaitOp>(block.getTerminator())) {
222 LLVM_DEBUG(llvm::dbgs() <<
"Skipping " << process.getLoc()
223 <<
": has multiple waits\n");
230 LLVM_DEBUG(llvm::dbgs()
231 <<
"Skipping " << process.getLoc() <<
": has no wait\n");
236 SmallPtrSet<Operation *, 8> seenDrives;
237 for (
auto &use : process->getUses()) {
238 auto driveOp = dyn_cast<DrvOp>(use.getOwner());
240 LLVM_DEBUG(llvm::dbgs()
241 <<
"Skipping " << process.getLoc() <<
": feeds non-drive "
242 << use.getOwner()->getLoc() <<
"\n");
245 if (!seenDrives.insert(driveOp).second)
249 if (!driveOp.getEnable()) {
250 LLVM_DEBUG(llvm::dbgs()
251 <<
"Skipping " << process.getLoc()
252 <<
": feeds unconditional drive " << driveOp <<
"\n");
258 if (use.getOperandNumber() != 1 && use.getOperandNumber() != 2) {
259 LLVM_DEBUG(llvm::dbgs()
260 <<
"Skipping " << process.getLoc()
261 <<
": feeds drive operand that is neither value nor enable: "
266 driveInfos.push_back(
DriveInfo(driveOp));
270 for (
auto value : wait.getObserved()) {
271 if (!value.getType().isSignlessInteger(1)) {
272 LLVM_DEBUG(llvm::dbgs() <<
"Skipping " << process.getLoc()
273 <<
": observes non-i1 value\n");
276 triggers.insert(value);
281 if (triggers.empty() || triggers.size() > 2) {
282 LLVM_DEBUG(llvm::dbgs() <<
"Skipping " << process.getLoc() <<
": observes "
283 << triggers.size() <<
" values\n");
288 for (
auto [index, trigger] :
llvm::enumerate(triggers))
289 booleanLattice.insert({trigger, getPresentTrigger(index)});
293 for (
auto [operand, blockArg] :
294 llvm::zip(wait.getDestOperands(), wait.getDest()->getArguments())) {
295 if (!operand.getType().isSignlessInteger(1)) {
296 LLVM_DEBUG(llvm::dbgs() <<
"Skipping " << process.getLoc()
297 <<
": uses non-i1 past value\n");
300 auto trigger = tracePastValue(operand);
303 pastValues.push_back(trigger);
305 std::distance(triggers.begin(), llvm::find(triggers, trigger));
306 booleanLattice.insert({blockArg, getPastTrigger(index)});
315Value Deseq::tracePastValue(Value pastValue) {
318 SmallVector<Value> worklist;
319 SmallPtrSet<Value, 8> seen;
320 worklist.push_back(pastValue);
321 seen.insert(pastValue);
323 SmallPtrSet<Block *, 2> predSeen;
324 SmallSetVector<BlockOperand *, 4> predWorklist;
325 SmallPtrSet<Value, 2> distinctValues;
326 while (!worklist.empty()) {
327 auto value = worklist.pop_back_val();
328 auto arg = dyn_cast<BlockArgument>(value);
332 if (triggers.contains(value) || !arg) {
333 distinctValues.insert(value);
339 predWorklist.clear();
340 for (
auto *predecessor : arg.getOwner()->getPredecessors())
341 if (predSeen.insert(predecessor).second)
342 for (auto &operand : predecessor->getTerminator()->getBlockOperands())
343 if (operand.
get() == arg.getOwner())
344 predWorklist.insert(&operand);
348 unsigned argIdx = arg.getArgNumber();
349 for (
auto *blockOperand : predWorklist) {
350 auto *op = blockOperand->getOwner();
351 if (
auto branchOp = dyn_cast<cf::BranchOp>(op)) {
353 auto operand = branchOp.getDestOperands()[argIdx];
354 if (seen.insert(operand).second)
355 worklist.push_back(operand);
356 }
else if (
auto condBranchOp = dyn_cast<cf::CondBranchOp>(op)) {
358 unsigned destIdx = blockOperand->getOperandNumber();
359 auto operand = destIdx == 0
360 ? condBranchOp.getTrueDestOperands()[argIdx]
361 : condBranchOp.getFalseDestOperands()[argIdx];
365 if ((matchPattern(operand, m_One()) && destIdx == 0) ||
366 (matchPattern(operand, m_Zero()) && destIdx == 1))
367 operand = condBranchOp.getCondition();
369 if (seen.insert(operand).second)
370 worklist.push_back(operand);
372 LLVM_DEBUG(llvm::dbgs() <<
"Skipping " << process.getLoc()
373 <<
": unsupported terminator " << op->getName()
374 <<
" while tracing past value\n");
382 if (distinctValues.size() != 1) {
385 <<
"Skipping " << process.getLoc()
386 <<
": multiple past values passed for the same block argument\n");
389 auto distinctValue = *distinctValues.begin();
390 if (!triggers.contains(distinctValue)) {
391 LLVM_DEBUG(llvm::dbgs() <<
"Skipping " << process.getLoc()
392 <<
": unobserved past value\n");
395 return distinctValue;
406TruthTable Deseq::computeBoolean(Value value) {
407 assert(value.getType().isSignlessInteger(1));
411 if (value.getDefiningOp() == process)
412 return computeBoolean(
413 wait.getYieldOperands()[cast<OpResult>(value).getResultNumber()]);
418 if (
auto it = booleanLattice.find(value); it != booleanLattice.end())
420 booleanLattice[value] = getUnknownBoolean();
424 TypeSwitch<Value, TruthTable>(value).Case<OpResult, BlockArgument>(
425 [&](
auto value) {
return computeBoolean(value); });
429 llvm::dbgs() <<
"- Boolean ";
430 value.printAsOperand(llvm::dbgs(), OpPrintingFlags());
431 llvm::dbgs() <<
": " << result <<
"\n";
433 booleanLattice[value] = result;
443 if (value.getDefiningOp() == process)
445 wait.getYieldOperands()[cast<OpResult>(value).getResultNumber()]);
450 if (
auto it = valueLattice.find(value); it != valueLattice.end())
452 valueLattice[value] = getUnknownValue();
456 TypeSwitch<Value, ValueTable>(value).Case<OpResult, BlockArgument>(
457 [&](
auto value) {
return computeValue(value); });
461 llvm::dbgs() <<
"- Value ";
462 value.printAsOperand(llvm::dbgs(), OpPrintingFlags());
463 llvm::dbgs() <<
": " << result <<
"\n";
465 valueLattice[value] = result;
470TruthTable Deseq::computeBoolean(OpResult value) {
471 assert(value.getType().isSignlessInteger(1));
472 auto *op = value.getOwner();
475 if (
auto constOp = dyn_cast<hw::ConstantOp>(op))
476 return getConstBoolean(constOp.getValue().isOne());
479 if (
auto orOp = dyn_cast<comb::OrOp>(op)) {
480 auto result = getConstBoolean(
false);
481 for (
auto operand : orOp.getInputs()) {
482 result |= computeBoolean(operand);
490 if (
auto andOp = dyn_cast<comb::AndOp>(op)) {
491 auto result = getConstBoolean(
true);
492 for (
auto operand : andOp.getInputs()) {
493 result &= computeBoolean(operand);
494 if (result.isFalse())
501 if (
auto xorOp = dyn_cast<comb::XorOp>(op)) {
502 auto result = getConstBoolean(
false);
503 for (
auto operand : xorOp.getInputs())
504 result ^= computeBoolean(operand);
511 if (llvm::any_of(op->getOperands(), [&](
auto operand) {
514 if (!operand.getType().isSignlessInteger(1))
516 auto result = computeBoolean(operand);
517 return result.isPoison() || (result != getUnknownBoolean() &&
518 !result.isTrue() && !result.isFalse());
520 return getPoisonBoolean();
521 return getUnknownBoolean();
526ValueTable Deseq::computeValue(OpResult value) {
527 auto *op = value.getOwner();
530 if (isa<comb::MuxOp, arith::SelectOp>(op)) {
531 auto condition = computeBoolean(op->getOperand(0));
532 auto trueValue = computeValue(op->getOperand(1));
533 auto falseValue = computeValue(op->getOperand(2));
534 trueValue.addCondition(condition);
535 falseValue.addCondition(~condition);
536 trueValue.merge(std::move(falseValue));
541 return getKnownValue(value);
545TruthTable Deseq::computeBoolean(BlockArgument arg) {
546 auto *block = arg.getOwner();
549 if (block->getParentOp() != process)
550 return getUnknownBoolean();
554 auto result = getConstBoolean(
false);
555 SmallPtrSet<Block *, 4> seen;
556 for (
auto *predecessor : block->getPredecessors()) {
557 if (!seen.insert(predecessor).second)
559 for (
auto &operand : predecessor->getTerminator()->getBlockOperands()) {
560 if (operand.get() != block)
562 auto value = computeSuccessorBoolean(operand, arg.getArgNumber());
565 auto condition = computeSuccessorCondition(operand);
566 result |= value & condition;
578ValueTable Deseq::computeValue(BlockArgument arg) {
579 auto *block = arg.getOwner();
582 if (block->getParentOp() != process)
583 return getKnownValue(arg);
588 SmallPtrSet<Block *, 4> seen;
589 for (
auto *predecessor : block->getPredecessors()) {
590 if (!seen.insert(predecessor).second)
592 for (
auto &operand : predecessor->getTerminator()->getBlockOperands()) {
593 if (operand.get() != block)
595 auto condition = computeSuccessorCondition(operand);
596 if (condition.isFalse())
598 auto value = computeSuccessorValue(operand, arg.getArgNumber());
599 value.addCondition(condition);
608TruthTable Deseq::computeBlockCondition(Block *block) {
611 if (
auto it = blockConditionLattice.find(block);
612 it != blockConditionLattice.end())
614 blockConditionLattice[block] = getConstBoolean(
false);
618 auto result = getConstBoolean(
false);
619 SmallPtrSet<Block *, 4> seen;
620 for (
auto *predecessor : block->getPredecessors()) {
621 if (!seen.insert(predecessor).second)
623 for (
auto &operand : predecessor->getTerminator()->getBlockOperands()) {
624 if (operand.get() != block)
626 result |= computeSuccessorCondition(operand);
636 llvm::dbgs() <<
"- Block condition ";
637 block->printAsOperand(llvm::dbgs());
638 llvm::dbgs() <<
": " << result <<
"\n";
640 blockConditionLattice[block] = result;
646TruthTable Deseq::computeSuccessorCondition(BlockOperand &blockOperand) {
651 auto *op = blockOperand.getOwner();
653 return getConstBoolean(
true);
657 if (
auto it = successorConditionLattice.find(&blockOperand);
658 it != successorConditionLattice.end())
660 successorConditionLattice[&blockOperand] = getConstBoolean(
false);
664 auto destIdx = blockOperand.getOperandNumber();
665 auto blockCondition = computeBlockCondition(op->getBlock());
666 auto result = getUnknownBoolean();
667 if (
auto branchOp = dyn_cast<cf::BranchOp>(op)) {
668 result = blockCondition;
669 }
else if (
auto condBranchOp = dyn_cast<cf::CondBranchOp>(op)) {
670 auto branchCondition = computeBoolean(condBranchOp.getCondition());
672 result = blockCondition & branchCondition;
674 result = blockCondition & ~branchCondition;
676 result = getPoisonBoolean();
681 llvm::dbgs() <<
"- Successor condition ";
682 op->getBlock()->printAsOperand(llvm::dbgs());
683 llvm::dbgs() <<
"#succ" << destIdx <<
" -> ";
684 blockOperand.get()->printAsOperand(llvm::dbgs());
685 llvm::dbgs() <<
" = " << result <<
"\n";
687 successorConditionLattice[&blockOperand] = result;
693TruthTable Deseq::computeSuccessorBoolean(BlockOperand &blockOperand,
697 if (
auto it = successorBooleanLattice.find({&blockOperand, argIdx});
698 it != successorBooleanLattice.end())
700 successorBooleanLattice[{&blockOperand, argIdx}] = getUnknownBoolean();
704 auto *op = blockOperand.getOwner();
705 auto destIdx = blockOperand.getOperandNumber();
706 auto result = getUnknownBoolean();
707 if (
auto branchOp = dyn_cast<cf::BranchOp>(op)) {
708 result = computeBoolean(branchOp.getDestOperands()[argIdx]);
709 }
else if (
auto condBranchOp = dyn_cast<cf::CondBranchOp>(op)) {
711 result = computeBoolean(condBranchOp.getTrueDestOperands()[argIdx]);
713 result = computeBoolean(condBranchOp.getFalseDestOperands()[argIdx]);
715 result = getPoisonBoolean();
720 llvm::dbgs() <<
"- Successor boolean ";
721 op->getBlock()->printAsOperand(llvm::dbgs());
722 llvm::dbgs() <<
"#succ" << destIdx <<
" -> ";
723 blockOperand.get()->printAsOperand(llvm::dbgs());
724 llvm::dbgs() <<
"#arg" << argIdx <<
" = " << result <<
"\n";
726 successorBooleanLattice[{&blockOperand, argIdx}] = result;
733ValueTable Deseq::computeSuccessorValue(BlockOperand &blockOperand,
737 if (
auto it = successorValueLattice.find({&blockOperand, argIdx});
738 it != successorValueLattice.end())
740 successorValueLattice[{&blockOperand, argIdx}] = getUnknownValue();
744 auto *op = blockOperand.getOwner();
745 auto destIdx = blockOperand.getOperandNumber();
746 auto result = getUnknownValue();
747 if (
auto branchOp = dyn_cast<cf::BranchOp>(op)) {
748 result = computeValue(branchOp.getDestOperands()[argIdx]);
749 }
else if (
auto condBranchOp = dyn_cast<cf::CondBranchOp>(op)) {
751 result = computeValue(condBranchOp.getTrueDestOperands()[argIdx]);
753 result = computeValue(condBranchOp.getFalseDestOperands()[argIdx]);
755 result = getPoisonValue();
760 llvm::dbgs() <<
"- Successor value ";
761 op->getBlock()->printAsOperand(llvm::dbgs());
762 llvm::dbgs() <<
"#succ" << destIdx <<
" -> ";
763 blockOperand.get()->printAsOperand(llvm::dbgs());
764 llvm::dbgs() <<
"#arg" << argIdx <<
" = " << result <<
"\n";
766 successorValueLattice[{&blockOperand, argIdx}] = result;
777bool Deseq::matchDrives() {
778 for (
auto &drive : driveInfos)
779 if (!matchDrive(drive))
788bool Deseq::matchDrive(
DriveInfo &drive) {
789 LLVM_DEBUG(llvm::dbgs() <<
"- Analyzing " << drive.
op <<
"\n");
792 auto condition = computeBoolean(drive.
op.getEnable());
793 if (condition.isPoison()) {
794 LLVM_DEBUG(llvm::dbgs()
795 <<
"- Aborting: poison condition on " << drive.
op <<
"\n");
800 auto initialValueTable = computeValue(drive.
op.getValue());
801 initialValueTable.addCondition(condition);
803 llvm::dbgs() <<
" - Condition: " << condition <<
"\n";
804 llvm::dbgs() <<
" - Value: " << initialValueTable <<
"\n";
810 SmallVector<std::pair<DNFTerm, ValueEntry>> valueTable;
811 for (
auto &[condition, value] : initialValueTable.entries) {
812 auto dnf = condition.canonicalize();
813 if (dnf.isPoison() || value.isPoison()) {
814 LLVM_DEBUG(llvm::dbgs()
815 <<
"- Aborting: poison in " << initialValueTable <<
"\n");
818 for (
auto &orTerm : dnf.orTerms)
819 valueTable.push_back({orTerm, value});
825 if (valueTable.size() > 3) {
826 LLVM_DEBUG(llvm::dbgs() <<
"- Aborting: value table has "
827 << valueTable.size() <<
" distinct conditions\n");
832 if (triggers.size() == 2)
833 return matchDriveClockAndReset(drive, valueTable);
836 assert(triggers.size() == 1);
837 return matchDriveClock(drive, valueTable);
842bool Deseq::matchDriveClock(
843 DriveInfo &drive, ArrayRef<std::pair<DNFTerm, ValueEntry>> valueTable) {
846 if (valueTable.size() != 1) {
847 LLVM_DEBUG(llvm::dbgs() <<
"- Aborting: single trigger value table has "
848 << valueTable.size() <<
" entries\n");
853 for (
unsigned variant = 0; variant < (1 << 1); ++variant) {
854 bool negClock = (variant >> 0) & 1;
862 uint32_t clockEdge = (negClock ? 0b1001 : 0b0110) << 2;
863 auto clockWithoutEnable =
DNFTerm{clockEdge};
864 auto clockWithEnable =
DNFTerm{clockEdge | 0b01};
867 if (valueTable[0].first == clockWithEnable)
869 else if (valueTable[0].first != clockWithoutEnable)
876 if (!valueTable[0].second.isUnknown())
877 drive.
clock.
value = valueTable[0].second.value;
880 llvm::dbgs() <<
" - Matched " << (negClock ?
"neg" :
"pos")
882 drive.
clock.
clock.printAsOperand(llvm::dbgs(), OpPrintingFlags());
883 llvm::dbgs() <<
" -> " << valueTable[0].second;
885 llvm::dbgs() <<
" (with enable)";
886 llvm::dbgs() <<
"\n";
892 LLVM_DEBUG(llvm::dbgs() <<
"- Aborting: unknown clock scheme\n");
899bool Deseq::matchDriveClockAndReset(
900 DriveInfo &drive, ArrayRef<std::pair<DNFTerm, ValueEntry>> valueTable) {
903 if (valueTable.size() != 3) {
904 LLVM_DEBUG(llvm::dbgs() <<
"- Aborting: two trigger value table has "
905 << valueTable.size() <<
" entries\n");
912 for (
unsigned variant = 0; variant < (1 << 3); ++variant) {
913 bool negClock = (variant >> 0) & 1;
914 bool negReset = (variant >> 1) & 1;
915 unsigned clockIdx = (variant >> 2) & 1;
916 unsigned resetIdx = 1 - clockIdx;
923 uint32_t clockEdge = (negClock ? 0b1001 : 0b0110) << (clockIdx * 4 + 2);
924 uint32_t resetEdge = (negReset ? 0b1001 : 0b0110) << (resetIdx * 4 + 2);
925 uint32_t resetOn = (negReset ? 0b1000 : 0b0100) << (resetIdx * 4 + 2);
926 uint32_t resetOff = (negReset ? 0b0100 : 0b1000) << (resetIdx * 4 + 2);
931 auto reset =
DNFTerm{resetEdge};
932 auto clockWhileReset =
DNFTerm{clockEdge | resetOn};
933 auto clockWithoutEnable =
DNFTerm{clockEdge | resetOff};
934 auto clockWithEnable =
DNFTerm{clockEdge | resetOff | 0b01};
937 auto resetIt = llvm::find_if(
938 valueTable, [&](
auto &pair) {
return pair.first == reset; });
939 if (resetIt == valueTable.end())
942 auto clockWhileResetIt = llvm::find_if(
943 valueTable, [&](
auto &pair) {
return pair.first == clockWhileReset; });
944 if (clockWhileResetIt == valueTable.end())
947 auto clockIt = llvm::find_if(valueTable, [&](
auto &pair) {
948 return pair.first == clockWithoutEnable || pair.first == clockWithEnable;
950 if (clockIt == valueTable.end())
956 if (clockWhileResetIt->second != resetIt->second ||
957 resetIt->second.isUnknown()) {
958 LLVM_DEBUG(llvm::dbgs() <<
"- Aborting: inconsistent reset value\n");
969 if (clockIt->first == clockWithEnable)
972 if (!clockIt->second.isUnknown())
976 llvm::dbgs() <<
" - Matched " << (negClock ?
"neg" :
"pos")
978 drive.
clock.
clock.printAsOperand(llvm::dbgs(), OpPrintingFlags());
979 llvm::dbgs() <<
" -> " << clockIt->second;
981 llvm::dbgs() <<
" (with enable)";
982 llvm::dbgs() <<
"\n";
983 llvm::dbgs() <<
" - Matched active-" << (negReset ?
"low" :
"high")
985 drive.
reset.
reset.printAsOperand(llvm::dbgs(), OpPrintingFlags());
986 llvm::dbgs() <<
" -> " << resetIt->second <<
"\n";
992 LLVM_DEBUG(llvm::dbgs() <<
"- Aborting: unknown reset scheme\n");
1002void Deseq::implementRegisters() {
1003 for (
auto &drive : driveInfos)
1004 implementRegister(drive);
1014void Deseq::implementRegister(
DriveInfo &drive) {
1015 OpBuilder builder(drive.
op);
1016 auto loc = drive.
op.getLoc();
1020 auto &clockCast = materializedClockCasts[drive.
clock.
clock];
1022 clockCast = seq::ToClockOp::create(builder, loc, drive.
clock.
clock);
1023 auto clock = clockCast;
1025 auto &clockInv = materializedClockInverters[clock];
1027 clockInv = seq::ClockInverterOp::create(builder, loc, clock);
1042 auto &inv = materializedInverters[reset];
1045 inv = comb::XorOp::create(builder, loc, reset, one);
1053 if (!resetValue.getParentRegion()->isProperAncestor(&process.getBody())) {
1054 if (
auto *defOp = resetValue.getDefiningOp();
1055 defOp && defOp->hasTrait<OpTrait::ConstantLike>())
1056 defOp->moveBefore(process);
1058 resetValue = specializeValue(
1059 drive.
op.getValue(),
1060 FixedValues{{drive.clock.clock, !drive.clock.risingEdge,
1061 !drive.clock.risingEdge},
1062 {drive.reset.reset, !drive.reset.activeHigh,
1063 drive.reset.activeHigh}});
1071 if (enable && !enable.getParentRegion()->isProperAncestor(&process.getBody()))
1072 enable = drive.
op.getEnable();
1078 if (!value.getParentRegion()->isProperAncestor(&process.getBody())) {
1079 if (
auto *defOp = value.getDefiningOp();
1080 defOp && defOp->hasTrait<OpTrait::ConstantLike>())
1081 defOp->moveBefore(process);
1083 value = drive.
op.getValue();
1089 fixedValues.push_back(
1092 fixedValues.push_back(
1095 value = specializeValue(value, fixedValues);
1097 enable = specializeValue(enable, fixedValues);
1101 if (
auto sigOp = drive.
op.getSignal().getDefiningOp<llhd::SignalOp>())
1102 name = sigOp.getNameAttr();
1104 name = builder.getStringAttr(
"");
1107 auto reg = seq::FirRegOp::create(builder, loc, value, clock, name,
1109 IntegerAttr{}, reset, resetValue,
1117 OpBuilder::InsertionGuard guard(builder);
1118 builder.setInsertionPoint(reg);
1119 reg.getNextMutable().assign(comb::MuxOp::create(
1120 builder, loc, enable,
reg.getNext(),
reg.getResult(),
true));
1124 drive.
op.getValueMutable().assign(reg);
1125 drive.
op.getEnableMutable().clear();
1130 if (matchPattern(drive.
op.getTime(), m_Constant(&attr)) &&
1131 attr.getTime() == 0 && attr.getDelta() == 1 && attr.getEpsilon() == 0) {
1134 ConstantTimeOp::create(builder, process.getLoc(), 0,
"ns", 0, 1);
1135 drive.
op.getTimeMutable().assign(epsilonDelay);
1148Value Deseq::specializeValue(Value value,
FixedValues fixedValues) {
1149 auto result = dyn_cast<OpResult>(value);
1150 if (!result || result.getOwner() != process)
1152 return specializeProcess(fixedValues)[result.getResultNumber()];
1163ValueRange Deseq::specializeProcess(
FixedValues fixedValues) {
1164 if (
auto it = specializedProcesses.find(fixedValues);
1165 it != specializedProcesses.end())
1169 llvm::dbgs() <<
"- Specializing process for:\n";
1170 for (
auto fixedValue : fixedValues) {
1171 llvm::dbgs() <<
" - ";
1172 fixedValue.value.printAsOperand(llvm::dbgs(), OpPrintingFlags());
1173 llvm::dbgs() <<
": " << fixedValue.past <<
" -> " << fixedValue.present
1182 OpBuilder builder(process);
1183 auto executeOp = CombinationalOp::create(builder, process.getLoc(),
1184 process.getResultTypes());
1187 SmallVector<std::pair<Block *, Block *>> worklist;
1189 auto scheduleBlock = [&](
Block *block) {
1190 if (
auto *newBlock = mapping.lookupOrNull(block))
1192 auto *newBlock = &executeOp.getRegion().emplaceBlock();
1193 for (
auto arg : block->getArguments()) {
1194 auto newArg = newBlock->addArgument(arg.getType(), arg.getLoc());
1195 mapping.map(arg, newArg);
1197 mapping.map(block, newBlock);
1198 worklist.push_back({block, newBlock});
1203 auto &entryBlock = executeOp.getRegion().emplaceBlock();
1204 builder.setInsertionPointToStart(&entryBlock);
1205 auto i1 = builder.getI1Type();
1210 for (
auto fixedValue : fixedValues) {
1211 auto present = fixedValue.present ? trueValue : falseValue;
1212 auto past = fixedValue.past ? trueValue : falseValue;
1213 materializedFixedValues.insert({fixedValue.value, {past, present}});
1214 mapping.map(fixedValue.value, present);
1219 auto fixedTable = getConstBoolean(
true);
1220 for (
auto [index, value] :
llvm::enumerate(triggers)) {
1221 for (
auto fixedValue : fixedValues) {
1222 if (fixedValue.value != value)
1224 auto past = getPastTrigger(index);
1225 fixedTable &= fixedValue.past ? past : ~past;
1226 auto present = getPresentTrigger(index);
1227 fixedTable &= fixedValue.present ? present : ~present;
1234 SmallVector<Value> foldedResults;
1235 while (!worklist.empty()) {
1236 auto [oldBlock, newBlock] = worklist.pop_back_val();
1237 builder.setInsertionPointToEnd(newBlock);
1238 for (
auto &oldOp : *oldBlock) {
1240 if (
auto waitOp = dyn_cast<WaitOp>(oldOp)) {
1243 SmallVector<Value> operands;
1244 for (
auto operand : waitOp.getYieldOperands())
1245 operands.push_back(mapping.lookupOrDefault(operand));
1246 YieldOp::create(builder, waitOp.getLoc(), operands);
1251 if (
auto condBranchOp = dyn_cast<cf::CondBranchOp>(oldOp)) {
1252 SmallVector<Value> operands;
1253 auto condition = mapping.lookupOrDefault(condBranchOp.getCondition());
1254 if (matchPattern(condition, m_NonZero())) {
1255 for (
auto operand : condBranchOp.getTrueDestOperands())
1256 operands.push_back(mapping.lookupOrDefault(operand));
1257 cf::BranchOp::create(builder, condBranchOp.getLoc(),
1258 scheduleBlock(condBranchOp.getTrueDest()),
1262 if (matchPattern(condition, m_Zero())) {
1263 for (
auto operand : condBranchOp.getFalseOperands())
1264 operands.push_back(mapping.lookupOrDefault(operand));
1265 cf::BranchOp::create(builder, condBranchOp.getLoc(),
1266 scheduleBlock(condBranchOp.getFalseDest()),
1275 if (oldOp.getNumResults() == 1 &&
1276 oldOp.getResult(0).getType().isSignlessInteger(1)) {
1277 if (
auto it = booleanLattice.find(oldOp.getResult(0));
1278 it != booleanLattice.end()) {
1279 if ((it->second & fixedTable).isFalse()) {
1280 mapping.map(oldOp.getResult(0), falseValue);
1283 if ((it->second & fixedTable) == fixedTable) {
1284 mapping.map(oldOp.getResult(0), trueValue);
1291 for (
auto &blockOperand : oldOp.getBlockOperands())
1292 scheduleBlock(blockOperand.
get());
1293 auto *clonedOp = builder.clone(oldOp, mapping);
1297 if (succeeded(builder.tryFold(clonedOp, foldedResults)) &&
1298 !foldedResults.empty()) {
1299 for (
auto [oldResult, foldedResult] :
1300 llvm::zip(oldOp.getResults(), foldedResults))
1301 mapping.map(oldResult, foldedResult);
1304 foldedResults.clear();
1311 worklist.push_back({&process.getBody().front(), &entryBlock});
1313 builder.setInsertionPointToEnd(mapping.lookup(wait->getBlock()));
1318 for (
auto &block : process.getBody())
1319 mapping.erase(&block);
1325 if (wait.getDest()->hasOneUse()) {
1328 for (
auto [arg, pastValue] :
1329 llvm::zip(wait.getDest()->getArguments(), pastValues))
1330 mapping.map(arg, materializedFixedValues.lookup(pastValue).first);
1333 mapping.map(wait.getDest(), builder.getBlock());
1334 worklist.push_back({wait.getDest(), builder.getBlock()});
1337 auto *dest = scheduleBlock(wait.getDest());
1341 SmallVector<Value> destOperands;
1342 assert(pastValues.size() == wait.getDestOperands().size());
1343 for (
auto pastValue : pastValues)
1344 destOperands.push_back(materializedFixedValues.lookup(pastValue).first);
1345 cf::BranchOp::create(builder, wait.getLoc(), dest, destOperands);
1352 if (isOpTriviallyDead(trueValue))
1354 if (isOpTriviallyDead(falseValue))
1357 specializedProcesses.insert({fixedValues, executeOp.getResults()});
1358 return executeOp.getResults();
1366struct DeseqPass :
public llhd::impl::DeseqPassBase<DeseqPass> {
1367 void runOnOperation()
override;
1371void DeseqPass::runOnOperation() {
1372 SmallVector<ProcessOp> processes(getOperation().getOps<ProcessOp>());
1373 for (
auto process : processes)
1374 Deseq(process).deseq();
assert(baseType &&"element must be base type")
#define VERBOSE_DEBUG(...)
static void cloneBlocks(ArrayRef< Block * > blocks, Region ®ion, Region::iterator before, IRMapping &mapper)
Clone a list of blocks into a region before the given block.
Direction get(bool isOutput)
Returns an output direction if isOutput is true, otherwise returns an input direction.
SmallVector< FixedValue, 2 > FixedValues
A list of i1 values that are fixed to a given value.
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
reg(value, clock, reset=None, reset_value=None, name=None, sym_name=None)
Value clock
The value acting as the clock, causing the register to be set to a value in valueTable when triggered...
bool risingEdge
Whether the clock is sensitive to a rising or falling edge.
Value value
The value the register is set to when the clock is triggered.
Value enable
The optional value acting as an enable.
A single AND operation within a DNF.
A drive op and the clock and reset that resulted from trigger analysis.
ClockInfo clock
The clock that triggers a change to the driven value.
DrvOp op
The drive operation.
ResetInfo reset
The optional reset that triggers a change of the driven value to a fixed reset value.
Value value
The value the register is reset to.
Value reset
The value acting as the reset, causing the register to be set to value when triggered.
bool activeHigh
Whether the reset is active when high.
A boolean function expressed as a truth table.
static TruthTable getTerm(unsigned numTerms, unsigned term)
Create a boolean expression consisting of a single term.
static TruthTable getPoison()
static TruthTable getConst(unsigned numTerms, bool value)
Create a boolean expression with a constant true or false value.
static ValueEntry getUnknown()
static ValueEntry getPoison()
A table of SSA values and the conditions under which they appear.
void merge(const ValueTable &other)