14#include "mlir/Analysis/Liveness.h"
15#include "mlir/Dialect/ControlFlow/IR/ControlFlowOps.h"
16#include "mlir/IR/Dominance.h"
17#include "llvm/Support/Debug.h"
18#include "llvm/Support/GenericIteratedDominanceFrontier.h"
20#define DEBUG_TYPE "llhd-mem2reg"
24#define GEN_PASS_DEF_MEM2REGPASS
25#include "circt/Dialect/LLHD/Transforms/LLHDPasses.h.inc"
32using llvm::PointerIntPair;
33using llvm::SmallDenseSet;
34using llvm::SmallSetVector;
35using llvm::SpecificBumpPtrAllocator;
39 if (
auto timeOp = value.getDefiningOp<ConstantTimeOp>()) {
40 auto t = timeOp.getValue();
41 return t.getTime() == 0 && t.getDelta() == 0 && t.getEpsilon() == 1;
48 if (
auto timeOp = value.getDefiningOp<ConstantTimeOp>()) {
49 auto t = timeOp.getValue();
50 return t.getTime() == 0 && t.getDelta() == 1 && t.getEpsilon() == 0;
58 if (
auto driveOp = dyn_cast<DrvOp>(op))
66 if (
auto driveOp = dyn_cast<DrvOp>(op))
80struct DriveCondition {
81 static DriveCondition never() {
return ConditionAndMode(Value{},
Never); }
82 static DriveCondition always() {
return ConditionAndMode(Value{}, Always); }
83 static DriveCondition conditional(Value condition = {}) {
84 return ConditionAndMode(condition, Conditional);
87 bool isNever()
const {
return conditionAndMode.getInt() ==
Never; }
88 bool isAlways()
const {
return conditionAndMode.getInt() == Always; }
89 bool isConditional()
const {
90 return conditionAndMode.getInt() == Conditional;
93 Value getCondition()
const {
return conditionAndMode.getPointer(); }
94 void setCondition(Value condition) { conditionAndMode.setPointer(condition); }
96 bool operator==(
const DriveCondition &other)
const {
97 return conditionAndMode == other.conditionAndMode;
99 bool operator!=(
const DriveCondition &other)
const {
100 return conditionAndMode != other.conditionAndMode;
109 typedef PointerIntPair<Value, 2> ConditionAndMode;
110 ConditionAndMode conditionAndMode;
112 DriveCondition(ConditionAndMode conditionAndMode)
113 : conditionAndMode(conditionAndMode) {}
114 friend DenseMapInfo<DriveCondition>;
126 DriveCondition condition;
127 bool valueIsPlaceholder =
false;
128 bool conditionIsPlaceholder =
false;
130 Def(Value value, DriveCondition condition)
131 : block(value.getParentBlock()), type(value.getType()), value(value),
132 condition(condition) {}
133 Def(Block *block, Type type, DriveCondition condition)
134 : block(block), type(type), condition(condition) {}
136 Value getValueOrPlaceholder();
137 Value getConditionOrPlaceholder();
143Value Def::getValueOrPlaceholder() {
145 auto builder = OpBuilder::atBlockBegin(block);
146 value = UnrealizedConversionCastOp::create(builder, builder.getUnknownLoc(),
149 valueIsPlaceholder =
true;
158Value Def::getConditionOrPlaceholder() {
159 if (!condition.getCondition()) {
160 auto builder = OpBuilder::atBlockBegin(block);
162 if (condition.isNever()) {
164 builder.getI1Type(), 0);
165 }
else if (condition.isAlways()) {
167 builder.getI1Type(), 1);
170 UnrealizedConversionCastOp::create(builder, builder.getUnknownLoc(),
171 builder.getI1Type(), ValueRange{})
173 conditionIsPlaceholder =
true;
175 condition.setCondition(value);
177 return condition.getCondition();
193 static bool isEqual(DriveCondition lhs, DriveCondition rhs) {
193 static bool isEqual(DriveCondition lhs, DriveCondition rhs) {
…}
211 return cast<hw::InOutType>(slot.getType()).getElementType();
227 LatticeNode *nodeBefore =
nullptr;
228 LatticeNode *nodeAfter =
nullptr;
229 SmallDenseSet<Value, 1> neededDefs;
234 enum class Kind { BlockEntry, BlockExit, Probe, Drive, Signal };
236 LatticeNode(Kind kind) : kind(kind) {}
239struct BlockEntry :
public LatticeNode {
241 LatticeValue *valueAfter;
242 SmallVector<BlockExit *, 2> predecessors;
243 SmallVector<std::pair<Value, Def *>, 0> insertedProbes;
246 BlockEntry(Block *block, LatticeValue *valueAfter)
247 : LatticeNode(Kind::BlockEntry), block(block), valueAfter(valueAfter) {
248 assert(!valueAfter->nodeBefore);
249 valueAfter->nodeBefore =
this;
252 static bool classof(
const LatticeNode *n) {
253 return n->kind == Kind::BlockEntry;
257struct BlockExit :
public LatticeNode {
259 LatticeValue *valueBefore;
260 SmallVector<BlockEntry *, 2> successors;
261 Operation *terminator;
264 BlockExit(Block *block, LatticeValue *valueBefore)
265 : LatticeNode(Kind::BlockExit), block(block), valueBefore(valueBefore),
266 terminator(block->getTerminator()),
267 suspends(isa<HaltOp, WaitOp>(terminator)) {
268 assert(!valueBefore->nodeAfter);
269 valueBefore->nodeAfter =
this;
272 static bool classof(
const LatticeNode *n) {
273 return n->kind == Kind::BlockExit;
277struct OpNode :
public LatticeNode {
279 LatticeValue *valueBefore;
280 LatticeValue *valueAfter;
282 OpNode(Kind kind, Operation *op, LatticeValue *valueBefore,
283 LatticeValue *valueAfter)
284 : LatticeNode(kind), op(op), valueBefore(valueBefore),
285 valueAfter(valueAfter) {
286 assert(!valueBefore->nodeAfter);
287 assert(!valueAfter->nodeBefore);
288 valueBefore->nodeAfter =
this;
289 valueAfter->nodeBefore =
this;
292 static bool classof(
const LatticeNode *n) {
293 return isa<ProbeNode, DriveNode, SignalNode>(n);
297struct ProbeNode :
public OpNode {
300 ProbeNode(PrbOp op, Value slot, LatticeValue *valueBefore,
301 LatticeValue *valueAfter)
302 : OpNode(Kind::Probe, op, valueBefore, valueAfter), slot(slot) {}
304 static bool classof(
const LatticeNode *n) {
return n->kind == Kind::Probe; }
307struct DriveNode :
public OpNode {
311 DriveNode(DrvOp op, Value slot, Def *def, LatticeValue *valueBefore,
312 LatticeValue *valueAfter)
313 : OpNode(Kind::Drive, op, valueBefore, valueAfter),
321 bool drivesProjection()
const {
return op->getOperand(0) !=
getSlot(slot); }
324 DrvOp getDriveOp()
const {
return cast<DrvOp>(op); }
326 static bool classof(
const LatticeNode *n) {
return n->kind == Kind::Drive; }
329struct SignalNode :
public OpNode {
332 SignalNode(SignalOp op, Def *def, LatticeValue *valueBefore,
333 LatticeValue *valueAfter)
334 : OpNode(Kind::Signal, op, valueBefore, valueAfter), def(def) {}
336 SignalOp getSignalOp()
const {
return cast<SignalOp>(op); }
339 static bool classof(
const LatticeNode *n) {
return n->kind == Kind::Signal; }
346 LatticeValue *createValue() {
347 auto *value =
new (valueAllocator.Allocate()) LatticeValue();
348 values.push_back(value);
353 template <
class T,
typename... Args>
354 T *createNode(Args... args) {
356 new (getAllocator<T>().Allocate()) T(std::forward<Args>(args)...);
357 nodes.push_back(node);
362 template <
typename... Args>
363 Def *createDef(Args... args) {
364 auto *def =
new (defAllocator.Allocate()) Def(std::forward<Args>(args)...);
370 Def *createDef(Value value, DriveCondition mode) {
371 auto &slot = defsForValues[{value, mode}];
373 slot =
new (defAllocator.Allocate()) Def(value, mode);
374 defs.push_back(slot);
380 void dump(llvm::raw_ostream &os = llvm::dbgs());
384 std::vector<LatticeNode *> nodes;
386 std::vector<LatticeValue *> values;
388 std::vector<Def *> defs;
392 DenseMap<std::pair<Value, DriveCondition>, Def *> defsForValues;
395 SpecificBumpPtrAllocator<LatticeValue> valueAllocator;
396 SpecificBumpPtrAllocator<Def> defAllocator;
397 SpecificBumpPtrAllocator<BlockEntry> blockEntryAllocator;
398 SpecificBumpPtrAllocator<BlockExit> blockExitAllocator;
399 SpecificBumpPtrAllocator<ProbeNode> probeAllocator;
400 SpecificBumpPtrAllocator<DriveNode> driveAllocator;
401 SpecificBumpPtrAllocator<SignalNode> signalAllocator;
405 SpecificBumpPtrAllocator<T> &getAllocator();
411SpecificBumpPtrAllocator<BlockEntry> &Lattice::getAllocator() {
412 return blockEntryAllocator;
415SpecificBumpPtrAllocator<BlockExit> &Lattice::getAllocator() {
416 return blockExitAllocator;
419SpecificBumpPtrAllocator<ProbeNode> &Lattice::getAllocator() {
420 return probeAllocator;
423SpecificBumpPtrAllocator<DriveNode> &Lattice::getAllocator() {
424 return driveAllocator;
427SpecificBumpPtrAllocator<SignalNode> &Lattice::getAllocator() {
428 return signalAllocator;
435void Lattice::dump(llvm::raw_ostream &os) {
437 llvm::MapVector<Block *, unsigned> blockNames;
438 llvm::MapVector<Value, unsigned> memNames;
439 llvm::MapVector<Def *, unsigned> defNames;
441 auto blockName = [&](
Block *block) {
442 unsigned id = blockNames.insert({block, blockNames.size()}).first->second;
443 return std::string(
"bb") + llvm::utostr(
id);
446 auto memName = [&](
DefSlot value) {
448 memNames.insert({
getSlot(value), memNames.size()}).first->second;
449 return std::string(
"mem") + llvm::utostr(
id) +
453 auto defName = [&](Def *def) {
454 unsigned id = defNames.insert({def, defNames.size()}).first->second;
455 return std::string(
"def") + llvm::utostr(
id);
459 for (
auto *node : nodes)
460 if (auto *entry = dyn_cast<BlockEntry>(node))
461 blockName(entry->block);
465 for (
auto *node : nodes) {
466 auto *entry = dyn_cast<BlockEntry>(node);
471 os <<
" " << blockName(entry->block) <<
":";
472 if (entry->predecessors.empty()) {
473 os <<
" // no predecessors";
476 for (
auto *node : entry->predecessors)
477 os <<
" " << blockName(node->block);
482 auto *value = entry->valueAfter;
485 if (!value->neededDefs.empty()) {
487 for (
auto mem : value->neededDefs)
491 if (!value->reachingDefs.empty()) {
493 for (
auto [mem, def] : value->reachingDefs) {
494 os <<
" " << memName(mem) <<
"=" << defName(def);
495 if (def->condition.isNever())
497 else if (def->condition.isAlways())
504 if (isa<BlockExit>(value->nodeAfter))
508 if (
auto *node = dyn_cast<ProbeNode>(value->nodeAfter))
509 os <<
" probe " << memName(
blockingSlot(node->slot)) <<
"\n";
510 else if (
auto *node = dyn_cast<DriveNode>(value->nodeAfter))
511 os <<
" drive " << memName(node->slot) <<
"\n";
512 else if (
auto *node = dyn_cast<SignalNode>(value->nodeAfter))
513 os <<
" signal " << memName(node->getSlot()) <<
"\n";
518 value = cast<OpNode>(value->nodeAfter)->valueAfter;
522 auto *exit = cast<BlockExit>(value->nodeAfter);
523 if (isa<WaitOp>(exit->terminator))
525 else if (exit->successors.empty())
529 for (
auto *node : exit->successors)
530 os <<
" " << blockName(node->block);
532 os <<
" // suspends";
537 for (
auto [mem,
id] : memNames)
538 os <<
" mem" << id <<
": " << mem <<
"\n";
572 while (fromSignal != toSlot) {
573 auto *op = cast<OpResult>(fromSignal).getOwner();
574 stack.push_back({op, Value()});
575 fromSignal = op->getOperand(0);
588 for (
auto &projection : llvm::reverse(projections)) {
589 projection.into = value;
591 TypeSwitch<Operation *, Value>(projection.op)
592 .Case<SigArrayGetOp>([&](
auto op) {
596 .Case<SigStructExtractOp>([&](
auto op) {
598 op.getLoc(), value, op.getFieldAttr());
600 .Case<SigExtractOp>([&](
auto op) {
601 auto type = cast<hw::InOutType>(op.getType()).getElementType();
602 auto width = type.getIntOrFloatBitWidth();
603 return comb::createDynamicExtract(builder, op.getLoc(), value,
604 op.getLowBit(), width);
624 for (
auto projection : projections) {
625 value = TypeSwitch<Operation *, Value>(projection.op)
626 .Case<SigArrayGetOp>([&](
auto op) {
627 return builder.createOrFold<hw::ArrayInjectOp>(
628 op.getLoc(), projection.into, op.getIndex(), value);
630 .Case<SigStructExtractOp>([&](
auto op) {
631 return builder.createOrFold<hw::StructInjectOp>(
632 op.getLoc(), projection.into, op.getFieldAttr(), value);
634 .Case<SigExtractOp>([&](
auto op) {
635 return comb::createDynamicInject(builder, op.getLoc(),
637 op.getLowBit(), value);
650 Promoter(Region ®ion) : region(region) {}
651 LogicalResult promote();
653 void findPromotableSlots();
654 Value resolveSlot(Value projectionOrSlot);
656 void captureAcrossWait();
657 void captureAcrossWait(PrbOp probeOp, ArrayRef<WaitOp> waitOps,
658 Liveness &liveness, DominanceInfo &dominance);
660 void constructLattice();
661 void propagateBackward();
662 void propagateBackward(LatticeNode *node);
663 void propagateForward();
664 void propagateForward(
bool optimisticMerges, DominanceInfo &dominance);
665 void propagateForward(LatticeNode *node,
bool optimisticMerges,
666 DominanceInfo &dominance);
667 void markDirty(LatticeNode *node);
669 void insertProbeBlocks();
671 void insertProbes(BlockEntry *node);
673 void insertDriveBlocks();
675 void insertDrives(BlockExit *node);
676 void insertDrives(DriveNode *node);
678 void resolveDefinitions();
679 void resolveDefinitions(ProbeNode *node);
680 void resolveDefinitions(DriveNode *node);
681 void resolveDefinitionValue(DriveNode *node);
682 void resolveDefinitionCondition(DriveNode *node);
684 void insertBlockArgs();
685 bool insertBlockArgs(BlockEntry *node);
686 void replaceValueWith(Value oldValue, Value newValue);
688 void removeUnusedLocalSignals();
689 void removeUnusedLocalSignal(SignalNode *signal);
697 SmallVector<Value> slots;
702 SmallDenseSet<Value> promotable;
708 SmallPtrSet<LatticeNode *, 4> dirtyNodes;
715LogicalResult Promoter::promote() {
719 findPromotableSlots();
727 llvm::dbgs() <<
"Initial lattice:\n";
734 llvm::dbgs() <<
"After backward propagation:\n";
742 llvm::dbgs() <<
"After probe insertion:\n";
749 llvm::dbgs() <<
"After forward propagation:\n";
754 resolveDefinitions();
760 llvm::dbgs() <<
"After def resolution and drive insertion:\n";
768 removeUnusedLocalSignals();
777void Promoter::findPromotableSlots() {
778 SmallPtrSet<Value, 8> seenSlots;
779 SmallPtrSet<Operation *, 8> checkedUsers;
780 SmallVector<Operation *, 8> userWorklist;
782 region.walk([&](Operation *op) {
783 for (
auto operand : op->getOperands()) {
784 if (!seenSlots.insert(operand).second)
790 if (!operand.getDefiningOp<llhd::SignalOp>())
794 auto checkUser = [&](Operation *user) ->
bool {
796 if (region.isProperAncestor(user->getParentRegion()))
799 if (user->getParentRegion() != ®ion)
802 if (isa<SigArrayGetOp, SigExtractOp, SigStructExtractOp>(user)) {
803 for (
auto *projectionUser : user->getUsers())
804 if (checkedUsers.insert(projectionUser).second)
805 userWorklist.push_back(projectionUser);
806 projections.insert({user->getResult(0), operand});
811 checkedUsers.clear();
812 if (!llvm::all_of(operand.getUsers(), [&](
auto *user) {
814 if (checkedUsers.insert(user).second)
815 userWorklist.push_back(user);
816 while (!userWorklist.empty() && allOk)
817 allOk &= checkUser(userWorklist.pop_back_val());
818 userWorklist.clear();
823 slots.push_back(operand);
828 promotable.insert(slots.begin(), slots.end());
829 for (
auto [projection, slot] :
llvm::make_early_inc_range(projections))
830 if (!promotable.contains(slot))
831 projections.erase(projection);
832 for (
auto [projection, slot] : projections)
833 promotable.insert(projection);
835 LLVM_DEBUG(llvm::dbgs() <<
"Found " << slots.size() <<
" promotable slots, "
836 << promotable.size() <<
" promotable values\n");
841Value Promoter::resolveSlot(Value projectionOrSlot) {
842 if (
auto slot = projections.lookup(projectionOrSlot))
844 return projectionOrSlot;
851void Promoter::captureAcrossWait() {
852 if (region.hasOneBlock())
855 SmallVector<WaitOp> waitOps;
856 for (
auto &block : region)
857 if (auto waitOp = dyn_cast<WaitOp>(block.getTerminator()))
858 waitOps.push_back(waitOp);
860 DominanceInfo dominance(region.getParentOp());
861 Liveness liveness(region.getParentOp());
863 SmallVector<WaitOp> crossingWaitOps;
864 for (
auto &block : region) {
865 for (
auto probeOp : block.getOps<PrbOp>()) {
866 for (
auto waitOp : waitOps)
867 if (liveness.getLiveness(waitOp->getBlock())->
isLiveOut(probeOp))
868 crossingWaitOps.push_back(waitOp);
869 if (!crossingWaitOps.empty()) {
870 captureAcrossWait(probeOp, crossingWaitOps, liveness, dominance);
871 crossingWaitOps.clear();
881void Promoter::captureAcrossWait(PrbOp probeOp, ArrayRef<WaitOp> waitOps,
882 Liveness &liveness, DominanceInfo &dominance) {
884 llvm::dbgs() <<
"Capture " << probeOp <<
"\n";
885 for (
auto waitOp : waitOps)
886 llvm::dbgs() <<
"- Across " << waitOp <<
"\n";
891 auto &domTree = dominance.getDomTree(®ion);
892 llvm::IDFCalculatorBase<Block, false> idfCalculator(domTree);
896 SmallPtrSet<Block *, 4> definingBlocks;
897 definingBlocks.insert(probeOp->getBlock());
898 for (
auto waitOp : waitOps)
899 definingBlocks.insert(waitOp.getDest());
900 idfCalculator.setDefiningBlocks(definingBlocks);
903 SmallPtrSet<Block *, 16> liveInBlocks;
904 for (
auto &block : region)
905 if (liveness.getLiveness(&block)->isLiveIn(probeOp))
906 liveInBlocks.insert(&block);
907 idfCalculator.setLiveInBlocks(liveInBlocks);
911 SmallVector<Block *> mergePointsVec;
912 idfCalculator.calculate(mergePointsVec);
913 SmallPtrSet<Block *, 16> mergePoints(mergePointsVec.begin(),
914 mergePointsVec.end());
915 for (
auto waitOp : waitOps)
916 mergePoints.insert(waitOp.getDest());
917 LLVM_DEBUG(llvm::dbgs() <<
"- " << mergePoints.size() <<
" merge points\n");
922 struct WorklistItem {
923 DominanceInfoNode *domNode;
926 SmallVector<WorklistItem> worklist;
927 worklist.push_back({domTree.getNode(probeOp->getBlock()), probeOp});
929 while (!worklist.empty()) {
930 auto item = worklist.pop_back_val();
931 auto *block = item.domNode->getBlock();
934 if (mergePoints.contains(block))
936 block->addArgument(probeOp.getType(), probeOp.getLoc());
940 for (
auto &op : *block)
941 op.replaceUsesOfWith(probeOp, item.reachingDef);
945 if (
auto branchOp = dyn_cast<BranchOpInterface>(block->getTerminator())) {
946 for (
auto &blockOperand : branchOp->getBlockOperands())
947 if (mergePoints.contains(blockOperand.
get()))
948 branchOp.getSuccessorOperands(blockOperand.getOperandNumber())
949 .
append(item.reachingDef);
950 }
else if (
auto waitOp = dyn_cast<WaitOp>(block->getTerminator())) {
951 if (mergePoints.contains(waitOp.getDest()))
952 waitOp.getDestOperandsMutable().append(item.reachingDef);
955 for (
auto *child : item.domNode->children())
956 worklist.push_back({child, item.reachingDef});
966void Promoter::constructLattice() {
969 for (
auto &block : region) {
970 auto *entry = lattice.createNode<BlockEntry>(&block, lattice.createValue());
971 blockEntries.insert({&block, entry});
975 for (
auto &block : region) {
976 auto *valueBefore = blockEntries.lookup(&block)->valueAfter;
979 for (
auto &op : block.without_terminator()) {
981 if (
auto probeOp = dyn_cast<PrbOp>(op)) {
982 if (!promotable.contains(probeOp.getSignal()))
984 auto *node = lattice.createNode<ProbeNode>(
985 probeOp, resolveSlot(probeOp.getSignal()), valueBefore,
986 lattice.createValue());
987 valueBefore = node->valueAfter;
992 if (
auto driveOp = dyn_cast<DrvOp>(op)) {
995 if (!promotable.contains(driveOp.getSignal()))
997 auto condition = DriveCondition::always();
998 if (
auto enable = driveOp.getEnable())
999 condition = DriveCondition::conditional(enable);
1003 auto slot = resolveSlot(driveOp.getSignal());
1004 auto *def = driveOp.getSignal() == slot
1005 ? lattice.createDef(driveOp.getValue(), condition)
1006 : lattice.createDef(driveOp->getBlock(),
1008 auto *node = lattice.createNode<DriveNode>(
1009 driveOp, slot, def, valueBefore, lattice.createValue());
1010 valueBefore = node->valueAfter;
1015 if (
auto signalOp = dyn_cast<SignalOp>(op)) {
1016 if (!promotable.contains(signalOp))
1019 lattice.createDef(signalOp.getInit(), DriveCondition::never());
1020 auto *node = lattice.createNode<SignalNode>(signalOp, def, valueBefore,
1021 lattice.createValue());
1022 valueBefore = node->valueAfter;
1028 auto *exit = lattice.createNode<BlockExit>(&block, valueBefore);
1029 for (
auto *otherBlock : exit->terminator->getSuccessors()) {
1030 auto *otherEntry = blockEntries.lookup(otherBlock);
1031 exit->successors.push_back(otherEntry);
1032 otherEntry->predecessors.push_back(exit);
1039void Promoter::propagateBackward() {
1040 for (
auto *node : lattice.nodes)
1041 propagateBackward(node);
1042 while (!dirtyNodes.empty()) {
1043 auto *node = *dirtyNodes.begin();
1044 dirtyNodes.erase(node);
1045 propagateBackward(node);
1051void Promoter::propagateBackward(LatticeNode *node) {
1052 auto update = [&](LatticeValue *value,
auto &neededDefs) {
1053 if (value->neededDefs != neededDefs) {
1054 value->neededDefs = neededDefs;
1055 markDirty(value->nodeBefore);
1060 if (
auto *probe = dyn_cast<ProbeNode>(node)) {
1061 auto needed = probe->valueAfter->neededDefs;
1062 needed.insert(probe->slot);
1063 update(probe->valueBefore, needed);
1073 if (
auto *drive = dyn_cast<DriveNode>(node)) {
1074 auto needed = drive->valueAfter->neededDefs;
1075 if (drive->drivesProjection())
1076 needed.insert(
getSlot(drive->slot));
1077 else if (!
isDelayed(drive->slot) && !drive->getDriveOp().getEnable())
1078 needed.erase(
getSlot(drive->slot));
1079 update(drive->valueBefore, needed);
1086 if (
auto *signal = dyn_cast<SignalNode>(node)) {
1087 auto needed = signal->valueAfter->neededDefs;
1088 needed.erase(signal->getSignalOp());
1089 update(signal->valueBefore, needed);
1094 if (
auto *entry = dyn_cast<BlockEntry>(node)) {
1095 for (
auto *predecessor : entry->predecessors)
1096 markDirty(predecessor);
1101 if (
auto *exit = dyn_cast<BlockExit>(node)) {
1104 SmallDenseSet<Value, 1> needed;
1105 for (
auto *successors : exit->successors)
1106 needed.insert(successors->valueAfter->neededDefs.begin(),
1107 successors->valueAfter->neededDefs.
end());
1108 update(exit->valueBefore, needed);
1112 assert(
false &&
"unhandled node in backward propagation");
1115void Promoter::propagateForward() {
1116 DominanceInfo dominance(region.getParentOp());
1117 propagateForward(
true, dominance);
1118 propagateForward(
false, dominance);
1129void Promoter::propagateForward(
bool optimisticMerges,
1130 DominanceInfo &dominance) {
1131 for (
auto *node : lattice.nodes)
1132 propagateForward(node, optimisticMerges, dominance);
1133 while (!dirtyNodes.empty()) {
1134 auto *node = *dirtyNodes.begin();
1135 dirtyNodes.erase(node);
1136 propagateForward(node, optimisticMerges, dominance);
1141void Promoter::propagateForward(LatticeNode *node,
bool optimisticMerges,
1142 DominanceInfo &dominance) {
1143 auto update = [&](LatticeValue *value,
auto &reachingDefs) {
1144 if (value->reachingDefs != reachingDefs) {
1145 value->reachingDefs = reachingDefs;
1146 markDirty(value->nodeAfter);
1151 if (
auto *probe = dyn_cast<ProbeNode>(node)) {
1152 update(probe->valueAfter, probe->valueBefore->reachingDefs);
1166 if (
auto *drive = dyn_cast<DriveNode>(node)) {
1167 auto reaching = drive->valueBefore->reachingDefs;
1173 if (drive->drivesProjection() || drive->getDriveOp().getEnable()) {
1174 auto *inDef = reaching.lookup(drive->slot);
1176 if (drive->def->value != inDef->value)
1177 drive->def->value = {};
1178 if (inDef->condition.isAlways() || drive->def->condition.isAlways())
1179 drive->def->condition = DriveCondition::always();
1180 else if (drive->def->condition != inDef->condition)
1181 drive->def->condition = DriveCondition::conditional();
1185 reaching[drive->slot] = drive->def;
1188 update(drive->valueAfter, reaching);
1195 if (
auto *signal = dyn_cast<SignalNode>(node)) {
1196 auto reaching = signal->valueBefore->reachingDefs;
1197 reaching[signal->getSlot()] = signal->def;
1198 reaching.erase(
delayedSlot(signal->getSignalOp()));
1199 update(signal->valueAfter, reaching);
1205 if (
auto *entry = dyn_cast<BlockEntry>(node)) {
1208 for (
auto [slot, insertedProbe] : entry->insertedProbes) {
1216 for (
auto *predecessor : entry->predecessors) {
1217 if (predecessor->suspends)
1221 for (
auto &defEntry : predecessor->valueBefore->reachingDefs) {
1222 auto slot =
getSlot(defEntry.getFirst());
1223 auto *slotBlock = slot.getDefiningOp()->getBlock();
1224 if (!dominance.dominates(slotBlock, entry->block))
1226 reachingDefs.insert(defEntry);
1230 for (
auto pair : reachingDefs) {
1232 Def *reachingDef = pair.second;
1233 DriveCondition reachingDefCondition = reachingDef->condition;
1236 if (reaching.contains(slot))
1246 if (llvm::any_of(entry->predecessors, [&](
auto *predecessor) {
1247 return predecessor->suspends;
1251 for (
auto *predecessor : entry->predecessors) {
1252 auto otherDef = predecessor->valueBefore->reachingDefs.lookup(slot);
1253 if (!otherDef && optimisticMerges)
1257 if (reachingDef != otherDef)
1258 reachingDef =
nullptr;
1262 otherDef ? otherDef->condition : DriveCondition::never();
1263 if (reachingDefCondition != condition)
1264 reachingDefCondition = DriveCondition::conditional();
1270 reachingDef = entry->mergedDefs.lookup(slot);
1272 reachingDef = lattice.createDef(entry->block,
getStoredType(slot),
1273 reachingDefCondition);
1274 entry->mergedDefs.insert({slot, reachingDef});
1276 reachingDef->condition = reachingDefCondition;
1278 reaching.insert({slot, reachingDef});
1281 update(entry->valueAfter, reaching);
1286 if (
auto *exit = dyn_cast<BlockExit>(node)) {
1287 for (
auto *successor : exit->successors)
1288 markDirty(successor);
1292 assert(
false &&
"unhandled node in forward propagation");
1296void Promoter::markDirty(LatticeNode *node) {
1298 dirtyNodes.insert(node);
1309void Promoter::insertProbeBlocks() {
1313 SmallDenseSet<std::pair<BlockExit *, BlockEntry *>, 1> worklist;
1314 for (
auto *node : lattice.nodes) {
1315 if (
auto *entry = dyn_cast<BlockEntry>(node)) {
1316 SmallVector<Value> partialSlots;
1317 for (
auto slot : entry->valueAfter->neededDefs) {
1318 unsigned numIncoming = 0;
1319 for (
auto *predecessor : entry->predecessors)
1320 if (predecessor->valueBefore->neededDefs.contains(slot))
1322 if (numIncoming != 0 && numIncoming != entry->predecessors.size())
1323 partialSlots.push_back(slot);
1325 for (
auto *predecessor : entry->predecessors)
1326 if (
llvm::any_of(partialSlots, [&](auto slot) {
1327 return !predecessor->valueBefore->neededDefs.contains(slot);
1329 worklist.insert({predecessor, entry});
1334 for (
auto [predecessor, successor] : worklist) {
1335 LLVM_DEBUG(llvm::dbgs() <<
"- Inserting probe block towards " << successor
1336 <<
" after " << *predecessor->terminator <<
"\n");
1337 OpBuilder builder(predecessor->terminator);
1338 auto *newBlock = builder.createBlock(successor->block);
1339 for (
auto oldArg : successor->block->getArguments())
1340 newBlock->addArgument(oldArg.getType(), oldArg.
getLoc());
1341 cf::BranchOp::create(builder, predecessor->terminator->getLoc(),
1342 successor->block, newBlock->getArguments());
1343 for (
auto &blockOp : predecessor->terminator->getBlockOperands())
1344 if (blockOp.
get() == successor->block)
1345 blockOp.set(newBlock);
1348 auto *value = lattice.createValue();
1349 value->neededDefs = successor->valueAfter->neededDefs;
1350 auto *newEntry = lattice.createNode<BlockEntry>(newBlock, value);
1351 auto *newExit = lattice.createNode<BlockExit>(newBlock, value);
1352 newEntry->predecessors.push_back(predecessor);
1353 newExit->successors.push_back(successor);
1354 llvm::replace(successor->predecessors, predecessor, newExit);
1355 llvm::replace(predecessor->successors, successor, newEntry);
1362void Promoter::insertProbes() {
1363 for (
auto *node : lattice.nodes) {
1364 if (
auto *entry = dyn_cast<BlockEntry>(node))
1365 insertProbes(entry);
1371void Promoter::insertProbes(BlockEntry *node) {
1372 auto builder = OpBuilder::atBlockBegin(node->block);
1373 for (
auto neededDef : slots) {
1374 if (!node->valueAfter->neededDefs.contains(neededDef))
1376 if (!node->predecessors.empty() &&
1377 llvm::all_of(node->predecessors, [&](
auto *predecessor) {
1378 return predecessor->valueBefore->neededDefs.contains(neededDef);
1381 LLVM_DEBUG(llvm::dbgs() <<
"- Inserting probe for " << neededDef
1382 <<
" in block " << node->block <<
"\n");
1383 OpBuilder::InsertionGuard guard(builder);
1385 if (Operation *op = neededDef.getDefiningOp()) {
1386 if (op->getBlock() == node->block)
1387 builder.setInsertionPointAfterValue(neededDef);
1389 auto value = PrbOp::create(builder, neededDef.getLoc(), neededDef);
1390 auto *def = lattice.createDef(value, DriveCondition::never());
1391 node->insertedProbes.push_back({neededDef, def});
1397void Promoter::insertDriveBlocks() {
1401 SmallDenseSet<std::pair<BlockExit *, BlockEntry *>, 1> worklist;
1402 for (
auto *node : lattice.nodes) {
1403 if (
auto *exit = dyn_cast<BlockExit>(node)) {
1404 SmallVector<DefSlot> partialSlots;
1405 for (
auto [slot, reachingDef] : exit->valueBefore->reachingDefs) {
1406 if (reachingDef->condition.isNever())
1408 unsigned numContinues = 0;
1409 for (
auto *successor : exit->successors)
1410 if (successor->valueAfter->reachingDefs.contains(slot))
1412 if (numContinues != 0 && numContinues != exit->successors.size())
1413 partialSlots.push_back(slot);
1415 for (
auto *successor : exit->successors)
1416 if (
llvm::any_of(partialSlots, [&](auto slot) {
1417 return !successor->valueAfter->reachingDefs.contains(slot);
1419 worklist.insert({exit, successor});
1424 for (
auto [predecessor, successor] : worklist) {
1425 LLVM_DEBUG(llvm::dbgs() <<
"- Inserting drive block towards " << successor
1426 <<
" after " << *predecessor->terminator <<
"\n");
1427 OpBuilder builder(predecessor->terminator);
1428 auto *newBlock = builder.createBlock(successor->block);
1429 for (
auto oldArg : successor->block->getArguments())
1430 newBlock->addArgument(oldArg.getType(), oldArg.
getLoc());
1431 cf::BranchOp::create(builder, predecessor->terminator->getLoc(),
1432 successor->block, newBlock->getArguments());
1433 for (
auto &blockOp : predecessor->terminator->getBlockOperands())
1434 if (blockOp.
get() == successor->block)
1435 blockOp.set(newBlock);
1438 auto *value = lattice.createValue();
1439 value->neededDefs = successor->valueAfter->neededDefs;
1440 value->reachingDefs = predecessor->valueBefore->reachingDefs;
1441 auto *newEntry = lattice.createNode<BlockEntry>(newBlock, value);
1442 auto *newExit = lattice.createNode<BlockExit>(newBlock, value);
1443 newEntry->predecessors.push_back(predecessor);
1444 newExit->successors.push_back(successor);
1445 llvm::replace(successor->predecessors, predecessor, newExit);
1446 llvm::replace(predecessor->successors, successor, newEntry);
1453void Promoter::insertDrives() {
1454 for (
auto *node : lattice.nodes) {
1455 if (
auto *exit = dyn_cast<BlockExit>(node))
1457 else if (
auto *drive = dyn_cast<DriveNode>(node))
1458 insertDrives(drive);
1464void Promoter::insertDrives(BlockExit *node) {
1465 auto builder = OpBuilder::atBlockTerminator(node->block);
1467 ConstantTimeOp epsilonTime;
1468 ConstantTimeOp deltaTime;
1469 auto getTime = [&](
bool delta) {
1472 deltaTime = ConstantTimeOp::create(builder, node->terminator->getLoc(),
1477 epsilonTime = ConstantTimeOp::create(builder, node->terminator->getLoc(),
1482 auto insertDriveForSlot = [&](
DefSlot slot) {
1483 auto reachingDef = node->valueBefore->reachingDefs.lookup(slot);
1484 if (!reachingDef || reachingDef->condition.isNever())
1486 if (!node->suspends && !node->successors.empty() &&
1487 llvm::all_of(node->successors, [&](
auto *successor) {
1488 return successor->valueAfter->reachingDefs.contains(slot);
1491 LLVM_DEBUG(llvm::dbgs() <<
"- Inserting drive for " <<
getSlot(slot) <<
" "
1492 << (
isDelayed(slot) ?
"(delayed)" :
"(blocking)")
1493 <<
" before " << *node->terminator <<
"\n");
1495 auto value = reachingDef->getValueOrPlaceholder();
1496 auto enable = reachingDef->condition.isConditional()
1497 ? reachingDef->getConditionOrPlaceholder()
1499 DrvOp::create(builder,
getLoc(slot),
getSlot(slot), value, time, enable);
1502 for (
auto slot : slots)
1504 for (
auto slot : slots)
1510void Promoter::insertDrives(DriveNode *node) {
1511 if (!promotable.contains(
getSlot(node->slot)))
1513 LLVM_DEBUG(llvm::dbgs() <<
"- Removing drive " << *node->op <<
"\n");
1514 pruner.eraseNow(node->op);
1523void Promoter::resolveDefinitions() {
1524 for (
auto *node : lattice.nodes) {
1525 if (
auto *probe = dyn_cast<ProbeNode>(node))
1526 resolveDefinitions(probe);
1527 else if (
auto *drive = dyn_cast<DriveNode>(node))
1528 resolveDefinitions(drive);
1533void Promoter::resolveDefinitions(ProbeNode *node) {
1534 if (!promotable.contains(node->slot))
1536 auto *def = node->valueBefore->reachingDefs.lookup(
blockingSlot(node->slot));
1537 assert(def &&
"no definition reaches probe");
1540 auto projections =
getProjections(node->op->getOperand(0), node->slot);
1543 auto builder = OpBuilder(node->op);
1544 auto value = def->getValueOrPlaceholder();
1548 LLVM_DEBUG(llvm::dbgs() <<
"- Replacing " << *node->op <<
" with " << value
1550 replaceValueWith(node->op->getResult(0), value);
1551 pruner.eraseNow(node->op);
1557void Promoter::resolveDefinitions(DriveNode *node) {
1558 if (!promotable.contains(
getSlot(node->slot)))
1565 if (!node->def->value || node->def->valueIsPlaceholder)
1566 resolveDefinitionValue(node);
1567 if (node->def->condition.isConditional() &&
1568 (!node->def->condition.getCondition() ||
1569 node->def->conditionIsPlaceholder))
1570 resolveDefinitionCondition(node);
1573void Promoter::resolveDefinitionValue(DriveNode *node) {
1576 auto *inDef = node->valueBefore->reachingDefs.lookup(node->slot);
1577 assert(inDef &&
"no definition reaches drive");
1578 auto driveOp = node->getDriveOp();
1579 LLVM_DEBUG(llvm::dbgs() <<
"- Injecting value for " << driveOp <<
"\n");
1585 auto builder = OpBuilder(driveOp);
1586 auto value = inDef->getValueOrPlaceholder();
1590 pruner.eraseLaterIfUnused(value);
1591 if (!driveOp.getEnable())
1592 value = driveOp.getValue();
1595 driveOp.getLoc(), driveOp.getEnable(), driveOp.getValue(), value);
1601 if (node->def->valueIsPlaceholder) {
1602 auto *placeholder = node->def->value.getDefiningOp();
1603 assert(isa_and_nonnull<UnrealizedConversionCastOp>(placeholder) &&
1604 "placeholder replaced but valueIsPlaceholder still set");
1605 replaceValueWith(placeholder->getResult(0), value);
1606 pruner.eraseNow(placeholder);
1607 node->def->valueIsPlaceholder =
false;
1609 node->def->value = value;
1612void Promoter::resolveDefinitionCondition(DriveNode *node) {
1615 auto *inDef = node->valueBefore->reachingDefs.lookup(node->slot);
1616 assert(inDef &&
"no definition reaches drive");
1617 auto driveOp = node->getDriveOp();
1618 LLVM_DEBUG(llvm::dbgs() <<
"- Mutating condition for " << driveOp <<
"\n");
1619 OpBuilder builder(driveOp);
1624 if (inDef->condition.isNever())
1625 condition = driveOp.getEnable();
1628 builder.createOrFold<
comb::OrOp>(driveOp.getLoc(), driveOp.getEnable(),
1629 inDef->getConditionOrPlaceholder());
1632 if (node->def->conditionIsPlaceholder) {
1633 auto *placeholder = node->def->condition.getCondition().getDefiningOp();
1634 assert(isa_and_nonnull<UnrealizedConversionCastOp>(placeholder) &&
1635 "placeholder replaced but conditionIsPlaceholder still set");
1636 replaceValueWith(placeholder->getResult(0), condition);
1637 pruner.eraseNow(placeholder);
1638 node->def->conditionIsPlaceholder =
false;
1640 node->def->condition.setCondition(condition);
1648void Promoter::insertBlockArgs() {
1649 bool anyArgsInserted =
true;
1650 while (anyArgsInserted) {
1651 anyArgsInserted =
false;
1652 for (
auto *node : lattice.nodes)
1653 if (auto *entry = dyn_cast<BlockEntry>(node))
1654 anyArgsInserted |= insertBlockArgs(entry);
1666bool Promoter::insertBlockArgs(BlockEntry *node) {
1672 enum class Which { Value, Condition };
1673 SmallVector<std::pair<DefSlot, Which>> neededSlots;
1674 auto addNeededSlot = [&](
DefSlot slot) {
1675 if (
auto *def = node->mergedDefs.lookup(slot)) {
1676 if (node->valueAfter->reachingDefs.contains(slot)) {
1677 if (def->valueIsPlaceholder)
1678 neededSlots.push_back({slot, Which::Value});
1679 if (def->conditionIsPlaceholder)
1680 neededSlots.push_back({slot, Which::Condition});
1684 for (
auto slot : slots) {
1688 if (neededSlots.empty())
1690 LLVM_DEBUG(llvm::dbgs() <<
"- Adding " << neededSlots.size()
1691 <<
" args to block " << node->block <<
"\n");
1694 for (
auto [slot, which] : neededSlots) {
1695 auto *def = node->mergedDefs.lookup(slot);
1698 case Which::Value: {
1701 auto *placeholder = def->value.getDefiningOp();
1702 assert(isa_and_nonnull<UnrealizedConversionCastOp>(placeholder) &&
1703 "placeholder replaced but valueIsPlaceholder still set");
1705 replaceValueWith(placeholder->getResult(0), arg);
1706 pruner.eraseNow(placeholder);
1708 def->valueIsPlaceholder =
false;
1711 case Which::Condition: {
1715 auto *placeholder = def->condition.getCondition().getDefiningOp();
1716 assert(isa_and_nonnull<UnrealizedConversionCastOp>(placeholder) &&
1717 "placeholder replaced but conditionIsPlaceholder still set");
1718 auto conditionArg = node->block->addArgument(
1719 IntegerType::get(region.getContext(), 1),
getLoc(slot));
1720 replaceValueWith(placeholder->getResult(0), conditionArg);
1721 pruner.eraseNow(placeholder);
1722 def->condition.setCondition(conditionArg);
1723 def->conditionIsPlaceholder =
false;
1730 for (
auto *predecessor : node->predecessors) {
1732 SmallVector<Value> args;
1733 for (
auto [slot, which] : neededSlots) {
1734 auto *def = predecessor->valueBefore->reachingDefs.lookup(slot);
1735 auto builder = OpBuilder::atBlockTerminator(predecessor->block);
1739 args.push_back(def->getValueOrPlaceholder());
1742 auto flatType = builder.getIntegerType(hw::getBitWidth(type));
1745 if (type != flatType)
1747 args.push_back(value);
1750 case Which::Condition:
1752 args.push_back(def->getConditionOrPlaceholder());
1755 builder.getI1Type(), 0));
1762 auto branchOp = cast<BranchOpInterface>(predecessor->terminator);
1763 for (
auto &blockOperand : branchOp->getBlockOperands())
1764 if (blockOperand.
get() == node->block)
1765 branchOp.getSuccessorOperands(blockOperand.getOperandNumber())
1774void Promoter::replaceValueWith(Value oldValue, Value newValue) {
1775 oldValue.replaceAllUsesWith(newValue);
1776 for (
auto *def : lattice.defs) {
1777 if (def->value == oldValue)
1778 def->value = newValue;
1779 if (def->condition.isConditional() &&
1780 def->condition.getCondition() == oldValue)
1781 def->condition.setCondition(newValue);
1790void Promoter::removeUnusedLocalSignals() {
1791 for (
auto *node : lattice.nodes)
1792 if (auto *signal = dyn_cast<SignalNode>(node))
1793 removeUnusedLocalSignal(signal);
1799void Promoter::removeUnusedLocalSignal(SignalNode *signal) {
1802 SmallSetVector<Operation *, 8> users;
1803 SmallVector<Operation *> worklist;
1804 worklist.push_back(signal->op);
1805 while (!worklist.empty()) {
1806 auto *op = worklist.pop_back_val();
1807 if (!isa<SignalOp, DrvOp, SigArrayGetOp, SigArraySliceOp, SigExtractOp,
1808 SigStructExtractOp>(op))
1810 for (
auto *user : op->getUsers())
1811 if (users.insert(user))
1812 worklist.push_back(user);
1817 LLVM_DEBUG(llvm::dbgs() <<
"- Removing local signal " << *signal->op <<
"\n");
1818 for (
auto *op :
llvm::reverse(users))
1819 pruner.eraseNow(op);
1827struct Mem2RegPass :
public llhd::impl::Mem2RegPassBase<Mem2RegPass> {
1828 void runOnOperation()
override;
1832void Mem2RegPass::runOnOperation() {
1833 SmallVector<Region *> regions;
1834 getOperation()->walk<WalkOrder::PreOrder>([&](Operation *op) {
1835 if (isa<ProcessOp, FinalOp, CombinationalOp>(op)) {
1836 auto ®ion = op->getRegion(0);
1837 if (!region.empty())
1838 regions.push_back(®ion);
1839 return WalkResult::skip();
1841 return WalkResult::advance();
1843 for (
auto *region : regions)
1844 if (failed(Promoter(*region).promote()))
1845 return signalPassFailure();
static bool isAlways(Attribute attr, bool expected)
static bool isLiveOut(Value val)
assert(baseType &&"element must be base type")
static void dump(DIModule &module, raw_indented_ostream &os)
static bool isDelayed(DefSlot slot)
static Value packProjections(OpBuilder &builder, Value value, const ProjectionStack &projections)
Undo a stack of projections by taking the value of the projected field and injecting it into the surr...
static Location getLoc(DefSlot slot)
static bool isDeltaDrive(Operation *op)
Check whether an operation is a llhd.drive with a delta delay.
static ProjectionStack getProjections(Value fromSignal, Value toSlot)
Collect the llhd.sig.
static bool isDeltaDelay(Value value)
Check whether a value is defined by llhd.constant_time <0ns, 1d, 0e>.
static DefSlot blockingSlot(Value slot)
static Value unpackProjections(OpBuilder &builder, Value value, ProjectionStack &projections)
Resolve a stack of projections by taking a value and descending into its subelements until the final ...
static DefSlot delayedSlot(Value slot)
static Value getSlot(DefSlot slot)
SmallVector< Projection > ProjectionStack
A stack of projection operations.
static bool isBlockingDrive(Operation *op)
Check whether an operation is a llhd.drive with an epsilon delay.
static Type getStoredType(Value slot)
static bool isEpsilonDelay(Value value)
Check whether a value is defined by llhd.constant_time <0ns, 0d, 1e>.
PointerIntPair< Value, 1 > DefSlot
The slot a reaching definition specifies a value for, alongside a bit indicating whether the definiti...
static StringAttr append(StringAttr base, const Twine &suffix)
Return a attribute with the specified suffix appended.
Direction get(bool isOutput)
Returns an output direction if isOutput is true, otherwise returns an input direction.
static bool operator==(const ModulePort &a, const ModulePort &b)
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
bool operator!=(uint64_t a, const FVInt &b)
Utility that tracks operations that have potentially become unused and allows them to be cleaned up a...
static DriveCondition getEmptyKey()
static DriveCondition getTombstoneKey()
static bool isEqual(DriveCondition lhs, DriveCondition rhs)
static unsigned getHashValue(DriveCondition d)