Loading [MathJax]/extensions/tex2jax.js
CIRCT 22.0.0git
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Mem2Reg.cpp
Go to the documentation of this file.
1//===- Mem2Reg.cpp - Promote signal/memory slots to values ----------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
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"
19
20#define DEBUG_TYPE "llhd-mem2reg"
21
22namespace circt {
23namespace llhd {
24#define GEN_PASS_DEF_MEM2REGPASS
25#include "circt/Dialect/LLHD/Transforms/LLHDPasses.h.inc"
26} // namespace llhd
27} // namespace circt
28
29using namespace mlir;
30using namespace circt;
31using namespace llhd;
32using llvm::PointerIntPair;
33using llvm::SmallDenseSet;
34using llvm::SmallSetVector;
35using llvm::SpecificBumpPtrAllocator;
36
37/// Check whether a value is defined by `llhd.constant_time <0ns, 0d, 1e>`.
38static bool isEpsilonDelay(Value value) {
39 if (auto timeOp = value.getDefiningOp<ConstantTimeOp>()) {
40 auto t = timeOp.getValue();
41 return t.getTime() == 0 && t.getDelta() == 0 && t.getEpsilon() == 1;
42 }
43 return false;
44}
45
46/// Check whether a value is defined by `llhd.constant_time <0ns, 1d, 0e>`.
47static bool isDeltaDelay(Value value) {
48 if (auto timeOp = value.getDefiningOp<ConstantTimeOp>()) {
49 auto t = timeOp.getValue();
50 return t.getTime() == 0 && t.getDelta() == 1 && t.getEpsilon() == 0;
51 }
52 return false;
53}
54
55/// Check whether an operation is a `llhd.drive` with an epsilon delay. This
56/// corresponds to a blocking assignment in Verilog.
57static bool isBlockingDrive(Operation *op) {
58 if (auto driveOp = dyn_cast<DrvOp>(op))
59 return isEpsilonDelay(driveOp.getTime());
60 return false;
61}
62
63/// Check whether an operation is a `llhd.drive` with a delta delay. This
64/// corresponds to a non-blocking assignment in Verilog.
65static bool isDeltaDrive(Operation *op) {
66 if (auto driveOp = dyn_cast<DrvOp>(op))
67 return isDeltaDelay(driveOp.getTime());
68 return false;
69}
70
71//===----------------------------------------------------------------------===//
72// Reaching Definitions and Placeholders
73//===----------------------------------------------------------------------===//
74
75namespace {
76/// Information about whether a definition is driven back onto its signal. For
77/// example, probes provide a definition for their signal that does not have to
78/// be driven back onto the signal. Drives on the other hand provide a
79/// definition that eventually must be driven onto the signal.
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);
85 }
86
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;
91 }
92
93 Value getCondition() const { return conditionAndMode.getPointer(); }
94 void setCondition(Value condition) { conditionAndMode.setPointer(condition); }
95
96 bool operator==(const DriveCondition &other) const {
97 return conditionAndMode == other.conditionAndMode;
98 }
99 bool operator!=(const DriveCondition &other) const {
100 return conditionAndMode != other.conditionAndMode;
101 }
102
103private:
104 enum {
105 Never,
106 Always,
107 Conditional,
108 };
109 typedef PointerIntPair<Value, 2> ConditionAndMode;
110 ConditionAndMode conditionAndMode;
111
112 DriveCondition(ConditionAndMode conditionAndMode)
113 : conditionAndMode(conditionAndMode) {}
114 friend DenseMapInfo<DriveCondition>;
115};
116
117/// A definition for a memory slot that may not yet have a concrete SSA value.
118/// These are created for blocks which need to merge distinct definitions for
119/// the same slot coming from its predecssors, as a standin before block
120/// arguments are created. They are also created for drives, where a concrete
121/// value is already available in the form of the driven value.
122struct Def {
123 Block *block;
124 Type type;
125 Value value;
126 DriveCondition condition;
127 bool valueIsPlaceholder = false;
128 bool conditionIsPlaceholder = false;
129
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) {}
135
136 Value getValueOrPlaceholder();
137 Value getConditionOrPlaceholder();
138};
139} // namespace
140
141/// Return the SSA value for this definition if it already has one, or create
142/// a placeholder value if no value exists yet.
143Value Def::getValueOrPlaceholder() {
144 if (!value) {
145 auto builder = OpBuilder::atBlockBegin(block);
146 value = UnrealizedConversionCastOp::create(builder, builder.getUnknownLoc(),
147 type, ValueRange{})
148 .getResult(0);
149 valueIsPlaceholder = true;
150 }
151 return value;
152}
153
154/// Return the drive condition for this definition. Creates a constant false or
155/// true SSA value if the drive mode is "never" or "always", respectively. If
156/// the mode is "conditional", return the its condition value if it already has
157/// one, or create a placeholder value if no value exists yet.
158Value Def::getConditionOrPlaceholder() {
159 if (!condition.getCondition()) {
160 auto builder = OpBuilder::atBlockBegin(block);
161 Value value;
162 if (condition.isNever()) {
163 value = hw::ConstantOp::create(builder, builder.getUnknownLoc(),
164 builder.getI1Type(), 0);
165 } else if (condition.isAlways()) {
166 value = hw::ConstantOp::create(builder, builder.getUnknownLoc(),
167 builder.getI1Type(), 1);
168 } else {
169 value =
170 UnrealizedConversionCastOp::create(builder, builder.getUnknownLoc(),
171 builder.getI1Type(), ValueRange{})
172 .getResult(0);
173 conditionIsPlaceholder = true;
174 }
175 condition.setCondition(value);
176 }
177 return condition.getCondition();
178}
179
180// Allow `DriveCondition` to be used as hash map key.
181template <>
182struct llvm::DenseMapInfo<DriveCondition> {
189 static unsigned getHashValue(DriveCondition d) {
191 d.conditionAndMode);
192 }
193 static bool isEqual(DriveCondition lhs, DriveCondition rhs) {
194 return lhs == rhs;
195 }
196};
197
198//===----------------------------------------------------------------------===//
199// Lattice to Propagate Needed and Reaching Definitions
200//===----------------------------------------------------------------------===//
201
202/// The slot a reaching definition specifies a value for, alongside a bit
203/// indicating whether the definition is from a delayed drive or a blocking
204/// drive.
205using DefSlot = PointerIntPair<Value, 1>;
206static DefSlot blockingSlot(Value slot) { return {slot, 0}; }
207static DefSlot delayedSlot(Value slot) { return {slot, 1}; }
208static Value getSlot(DefSlot slot) { return slot.getPointer(); }
209static bool isDelayed(DefSlot slot) { return slot.getInt(); }
210static Type getStoredType(Value slot) {
211 return cast<hw::InOutType>(slot.getType()).getElementType();
212}
213static Type getStoredType(DefSlot slot) {
214 return getStoredType(slot.getPointer());
215}
216static Location getLoc(DefSlot slot) { return slot.getPointer().getLoc(); }
217
218namespace {
219
220struct LatticeNode;
221struct BlockExit;
222struct ProbeNode;
223struct DriveNode;
224struct SignalNode;
225
226struct LatticeValue {
227 LatticeNode *nodeBefore = nullptr;
228 LatticeNode *nodeAfter = nullptr;
229 SmallDenseSet<Value, 1> neededDefs;
231};
232
233struct LatticeNode {
234 enum class Kind { BlockEntry, BlockExit, Probe, Drive, Signal };
235 const Kind kind;
236 LatticeNode(Kind kind) : kind(kind) {}
237};
238
239struct BlockEntry : public LatticeNode {
240 Block *block;
241 LatticeValue *valueAfter;
242 SmallVector<BlockExit *, 2> predecessors;
243 SmallVector<std::pair<Value, Def *>, 0> insertedProbes;
245
246 BlockEntry(Block *block, LatticeValue *valueAfter)
247 : LatticeNode(Kind::BlockEntry), block(block), valueAfter(valueAfter) {
248 assert(!valueAfter->nodeBefore);
249 valueAfter->nodeBefore = this;
250 }
251
252 static bool classof(const LatticeNode *n) {
253 return n->kind == Kind::BlockEntry;
254 }
255};
256
257struct BlockExit : public LatticeNode {
258 Block *block;
259 LatticeValue *valueBefore;
260 SmallVector<BlockEntry *, 2> successors;
261 Operation *terminator;
262 bool suspends;
263
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;
270 }
271
272 static bool classof(const LatticeNode *n) {
273 return n->kind == Kind::BlockExit;
274 }
275};
276
277struct OpNode : public LatticeNode {
278 Operation *op;
279 LatticeValue *valueBefore;
280 LatticeValue *valueAfter;
281
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;
290 }
291
292 static bool classof(const LatticeNode *n) {
293 return isa<ProbeNode, DriveNode, SignalNode>(n);
294 }
295};
296
297struct ProbeNode : public OpNode {
298 Value slot;
299
300 ProbeNode(PrbOp op, Value slot, LatticeValue *valueBefore,
301 LatticeValue *valueAfter)
302 : OpNode(Kind::Probe, op, valueBefore, valueAfter), slot(slot) {}
303
304 static bool classof(const LatticeNode *n) { return n->kind == Kind::Probe; }
305};
306
307struct DriveNode : public OpNode {
308 DefSlot slot;
309 Def *def;
310
311 DriveNode(DrvOp op, Value slot, Def *def, LatticeValue *valueBefore,
312 LatticeValue *valueAfter)
313 : OpNode(Kind::Drive, op, valueBefore, valueAfter),
314 slot(isDeltaDrive(op) ? delayedSlot(slot) : blockingSlot(slot)),
315 def(def) {
317 }
318
319 /// Returns true if the op does not drive an entire slot, but only a part of a
320 /// slot through a projection.
321 bool drivesProjection() const { return op->getOperand(0) != getSlot(slot); }
322
323 /// Return the drive op.
324 DrvOp getDriveOp() const { return cast<DrvOp>(op); }
325
326 static bool classof(const LatticeNode *n) { return n->kind == Kind::Drive; }
327};
328
329struct SignalNode : public OpNode {
330 Def *def;
331
332 SignalNode(SignalOp op, Def *def, LatticeValue *valueBefore,
333 LatticeValue *valueAfter)
334 : OpNode(Kind::Signal, op, valueBefore, valueAfter), def(def) {}
335
336 SignalOp getSignalOp() const { return cast<SignalOp>(op); }
337 DefSlot getSlot() const { return blockingSlot(getSignalOp()); }
338
339 static bool classof(const LatticeNode *n) { return n->kind == Kind::Signal; }
340};
341
342/// A lattice of block entry and exit nodes, nodes for relevant operations such
343/// as probes and drives, and values flowing between the nodes.
344struct Lattice {
345 /// Create a new value on the lattice.
346 LatticeValue *createValue() {
347 auto *value = new (valueAllocator.Allocate()) LatticeValue();
348 values.push_back(value);
349 return value;
350 }
351
352 /// Create a new node on the lattice.
353 template <class T, typename... Args>
354 T *createNode(Args... args) {
355 auto *node =
356 new (getAllocator<T>().Allocate()) T(std::forward<Args>(args)...);
357 nodes.push_back(node);
358 return node;
359 }
360
361 /// Create a new reaching definition.
362 template <typename... Args>
363 Def *createDef(Args... args) {
364 auto *def = new (defAllocator.Allocate()) Def(std::forward<Args>(args)...);
365 defs.push_back(def);
366 return def;
367 }
368
369 /// Create a new reaching definition for an existing value in the IR.
370 Def *createDef(Value value, DriveCondition mode) {
371 auto &slot = defsForValues[{value, mode}];
372 if (!slot) {
373 slot = new (defAllocator.Allocate()) Def(value, mode);
374 defs.push_back(slot);
375 }
376 return slot;
377 }
378
379#ifndef NDEBUG
380 void dump(llvm::raw_ostream &os = llvm::dbgs());
381#endif
382
383 /// All nodes in the lattice.
384 std::vector<LatticeNode *> nodes;
385 /// All values in the lattice.
386 std::vector<LatticeValue *> values;
387 /// All reaching defs in the lattice.
388 std::vector<Def *> defs;
389 /// The reaching defs for concrete values in the IR. This map is used to
390 /// create a single def for the same SSA value to allow for pointer equality
391 /// comparisons.
392 DenseMap<std::pair<Value, DriveCondition>, Def *> defsForValues;
393
394private:
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;
402
403 // Helper function to get the correct allocator given a lattice node class.
404 template <class T>
405 SpecificBumpPtrAllocator<T> &getAllocator();
406};
407
408// Specializations for the `getAllocator` template that map node types to the
409// correct allocator.
410template <>
411SpecificBumpPtrAllocator<BlockEntry> &Lattice::getAllocator() {
412 return blockEntryAllocator;
413}
414template <>
415SpecificBumpPtrAllocator<BlockExit> &Lattice::getAllocator() {
416 return blockExitAllocator;
417}
418template <>
419SpecificBumpPtrAllocator<ProbeNode> &Lattice::getAllocator() {
420 return probeAllocator;
421}
422template <>
423SpecificBumpPtrAllocator<DriveNode> &Lattice::getAllocator() {
424 return driveAllocator;
425}
426template <>
427SpecificBumpPtrAllocator<SignalNode> &Lattice::getAllocator() {
428 return signalAllocator;
429}
430
431} // namespace
432
433#ifndef NDEBUG
434/// Print the lattice in human-readable form. Useful for debugging.
435void Lattice::dump(llvm::raw_ostream &os) {
436 // Helper functions to quickly come up with unique names for things.
437 llvm::MapVector<Block *, unsigned> blockNames;
438 llvm::MapVector<Value, unsigned> memNames;
439 llvm::MapVector<Def *, unsigned> defNames;
440
441 auto blockName = [&](Block *block) {
442 unsigned id = blockNames.insert({block, blockNames.size()}).first->second;
443 return std::string("bb") + llvm::utostr(id);
444 };
445
446 auto memName = [&](DefSlot value) {
447 unsigned id =
448 memNames.insert({getSlot(value), memNames.size()}).first->second;
449 return std::string("mem") + llvm::utostr(id) +
450 (isDelayed(value) ? "#" : "");
451 };
452
453 auto defName = [&](Def *def) {
454 unsigned id = defNames.insert({def, defNames.size()}).first->second;
455 return std::string("def") + llvm::utostr(id);
456 };
457
458 // Ensure the blocks are named in the order they were created.
459 for (auto *node : nodes)
460 if (auto *entry = dyn_cast<BlockEntry>(node))
461 blockName(entry->block);
462
463 // Iterate over all block entry nodes.
464 os << "lattice {\n";
465 for (auto *node : nodes) {
466 auto *entry = dyn_cast<BlockEntry>(node);
467 if (!entry)
468 continue;
469
470 // Print the opening braces and predecessors for the block.
471 os << " " << blockName(entry->block) << ":";
472 if (entry->predecessors.empty()) {
473 os << " // no predecessors";
474 } else {
475 os << " // from";
476 for (auto *node : entry->predecessors)
477 os << " " << blockName(node->block);
478 }
479 os << "\n";
480
481 // Print all nodes following the block entry, up until the block exit.
482 auto *value = entry->valueAfter;
483 while (true) {
484 // Print the needed defs at this lattice point.
485 if (!value->neededDefs.empty()) {
486 os << " -> need";
487 for (auto mem : value->neededDefs)
488 os << " " << memName(blockingSlot(mem));
489 os << "\n";
490 }
491 if (!value->reachingDefs.empty()) {
492 os << " -> def";
493 for (auto [mem, def] : value->reachingDefs) {
494 os << " " << memName(mem) << "=" << defName(def);
495 if (def->condition.isNever())
496 os << "[N]";
497 else if (def->condition.isAlways())
498 os << "[A]";
499 else
500 os << "[C]";
501 }
502 os << "\n";
503 }
504 if (isa<BlockExit>(value->nodeAfter))
505 break;
506
507 // Print the node.
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";
514 else
515 os << " unknown\n";
516
517 // Advance to the next node.
518 value = cast<OpNode>(value->nodeAfter)->valueAfter;
519 }
520
521 // Print the closing braces and successors for the block.
522 auto *exit = cast<BlockExit>(value->nodeAfter);
523 if (isa<WaitOp>(exit->terminator))
524 os << " wait";
525 else if (exit->successors.empty())
526 os << " halt";
527 else
528 os << " goto";
529 for (auto *node : exit->successors)
530 os << " " << blockName(node->block);
531 if (exit->suspends)
532 os << " // suspends";
533 os << "\n";
534 }
535
536 // Dump the memories.
537 for (auto [mem, id] : memNames)
538 os << " mem" << id << ": " << mem << "\n";
539
540 os << "}\n";
541}
542#endif
543
544//===----------------------------------------------------------------------===//
545// Projection Utilities
546//===----------------------------------------------------------------------===//
547
548namespace {
549/// A single projection operation, together with the concrete value of the
550/// signal being projected into. This helper is useful to unpack a stack of
551/// projections to get the targeted value, change it, and then pack the stack
552/// back up into an updated value.
553struct Projection {
554 /// The projection operation.
555 Operation *op;
556 /// The value being projected into. This is not the op's target signal, but
557 /// rather the value of the op's target signal.
558 Value into;
559};
560} // namespace
561
562/// A stack of projection operations.
563using ProjectionStack = SmallVector<Projection>;
564
565/// Collect the `llhd.sig.*` projection ops between `fromSignal` and `toSlot`.
566/// The `fromSignal` value must be derived from `toSlot` through only
567/// `llhd.sig.*` operations. The result is a stack; the op producing
568/// `fromSignal` appears first in the vector, while the final op projecting into
569/// `toSlot` appears last in the vector.
570static ProjectionStack getProjections(Value fromSignal, Value toSlot) {
571 ProjectionStack stack;
572 while (fromSignal != toSlot) {
573 auto *op = cast<OpResult>(fromSignal).getOwner();
574 stack.push_back({op, Value()});
575 fromSignal = op->getOperand(0);
576 }
577 return stack;
578}
579
580/// Resolve a stack of projections by taking a value and descending into its
581/// subelements until the final value targeted by the projection stack remains,
582/// which is then returned. Also updates the `into` fields of the projections in
583/// the stack to represent the concrete value of intermediate projections. This
584/// allows a later `packProjections` to reconstruct the root value with the
585/// field targeted by the projection updated to a different value.
586static Value unpackProjections(OpBuilder &builder, Value value,
587 ProjectionStack &projections) {
588 for (auto &projection : llvm::reverse(projections)) {
589 projection.into = value;
590 value =
591 TypeSwitch<Operation *, Value>(projection.op)
592 .Case<SigArrayGetOp>([&](auto op) {
593 return builder.createOrFold<hw::ArrayGetOp>(op.getLoc(), value,
594 op.getIndex());
595 })
596 .Case<SigStructExtractOp>([&](auto op) {
597 return builder.createOrFold<hw::StructExtractOp>(
598 op.getLoc(), value, op.getFieldAttr());
599 })
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);
605 });
606 }
607 return value;
608}
609
610/// Undo a stack of projections by taking the value of the projected field and
611/// injecting it into the surrounding aggregate value that the projection
612/// targets. This requires the `into` fields to be set to the concrete value of
613/// the intermediate projections.
614///
615/// Example:
616/// ```
617/// auto projections = getProjections(...);
618/// auto fieldValue = unpackProjections(..., aggregateValue, projections);
619/// fieldValue = update(fieldValue);
620/// aggregateValue = packProjections(..., fieldValue, projections);
621/// ```
622static Value packProjections(OpBuilder &builder, Value value,
623 const ProjectionStack &projections) {
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);
629 })
630 .Case<SigStructExtractOp>([&](auto op) {
631 return builder.createOrFold<hw::StructInjectOp>(
632 op.getLoc(), projection.into, op.getFieldAttr(), value);
633 })
634 .Case<SigExtractOp>([&](auto op) {
635 return comb::createDynamicInject(builder, op.getLoc(),
636 projection.into,
637 op.getLowBit(), value);
638 });
639 }
640 return value;
641}
642
643//===----------------------------------------------------------------------===//
644// Drive/Probe to SSA Value Promotion
645//===----------------------------------------------------------------------===//
646
647namespace {
648/// The main promoter forwarding drives to probes within a region.
649struct Promoter {
650 Promoter(Region &region) : region(region) {}
651 LogicalResult promote();
652
653 void findPromotableSlots();
654 Value resolveSlot(Value projectionOrSlot);
655
656 void captureAcrossWait();
657 void captureAcrossWait(PrbOp probeOp, ArrayRef<WaitOp> waitOps,
658 Liveness &liveness, DominanceInfo &dominance);
659
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);
668
669 void insertProbeBlocks();
670 void insertProbes();
671 void insertProbes(BlockEntry *node);
672
673 void insertDriveBlocks();
674 void insertDrives();
675 void insertDrives(BlockExit *node);
676 void insertDrives(DriveNode *node);
677
678 void resolveDefinitions();
679 void resolveDefinitions(ProbeNode *node);
680 void resolveDefinitions(DriveNode *node);
681 void resolveDefinitionValue(DriveNode *node);
682 void resolveDefinitionCondition(DriveNode *node);
683
684 void insertBlockArgs();
685 bool insertBlockArgs(BlockEntry *node);
686 void replaceValueWith(Value oldValue, Value newValue);
687
688 void removeUnusedLocalSignals();
689 void removeUnusedLocalSignal(SignalNode *signal);
690
691 /// The region we are promoting in.
692 Region &region;
693
694 /// The slots we are promoting. Mostly `llhd.sig` ops in practice. This
695 /// establishes a deterministic order for slot allocations, such that
696 /// everything else in the pass can operate using unordered maps and sets.
697 SmallVector<Value> slots;
698 /// A mapping from projections to the root slot they are projecting into.
699 SmallDenseMap<Value, Value> projections;
700 /// A set of all promotable signal SSA values. This is the union of `slots`
701 /// and `projections` of those slots.
702 SmallDenseSet<Value> promotable;
703
704 /// The lattice used to propagate needed definitions backwards and reaching
705 /// definitions forwards.
706 Lattice lattice;
707 /// A worklist of lattice nodes used within calls to `propagate*`.
708 SmallPtrSet<LatticeNode *, 4> dirtyNodes;
709
710 /// Helper to clean up unused ops.
711 UnusedOpPruner pruner;
712};
713} // namespace
714
715LogicalResult Promoter::promote() {
716 if (region.empty())
717 return success();
718
719 findPromotableSlots();
720 if (slots.empty())
721 return success();
722
723 captureAcrossWait();
724
725 constructLattice();
726 LLVM_DEBUG({
727 llvm::dbgs() << "Initial lattice:\n";
728 lattice.dump();
729 });
730
731 // Propagate the needed definitions backward across the lattice.
732 propagateBackward();
733 LLVM_DEBUG({
734 llvm::dbgs() << "After backward propagation:\n";
735 lattice.dump();
736 });
737
738 // Insert probes wherever a def is needed for the first time.
739 insertProbeBlocks();
740 insertProbes();
741 LLVM_DEBUG({
742 llvm::dbgs() << "After probe insertion:\n";
743 lattice.dump();
744 });
745
746 // Propagate the reaching definitions forward across the lattice.
747 propagateForward();
748 LLVM_DEBUG({
749 llvm::dbgs() << "After forward propagation:\n";
750 lattice.dump();
751 });
752
753 // Resolve definitions.
754 resolveDefinitions();
755
756 // Insert drives wherever a reaching def can no longer propagate.
757 insertDriveBlocks();
758 insertDrives();
759 LLVM_DEBUG({
760 llvm::dbgs() << "After def resolution and drive insertion:\n";
761 lattice.dump();
762 });
763
764 // Insert the necessary block arguments.
765 insertBlockArgs();
766
767 // Remove local signals that are never probed.
768 removeUnusedLocalSignals();
769
770 // Erase operations that have become unused.
771 pruner.eraseNow();
772
773 return success();
774}
775
776/// Identify any promotable slots probed or driven under the current region.
777void Promoter::findPromotableSlots() {
778 SmallPtrSet<Value, 8> seenSlots;
779 SmallPtrSet<Operation *, 8> checkedUsers;
780 SmallVector<Operation *, 8> userWorklist;
781
782 region.walk([&](Operation *op) {
783 for (auto operand : op->getOperands()) {
784 if (!seenSlots.insert(operand).second)
785 continue;
786
787 // We can only promote probes and drives on a locally-defined signal.
788 // Other signals, such as the ones brought into a module through a port,
789 // have an unknown aliasing relationship with the other ports.
790 if (!operand.getDefiningOp<llhd::SignalOp>())
791 continue;
792
793 // Ensure the slot is not used in any way we cannot reason about.
794 auto checkUser = [&](Operation *user) -> bool {
795 // We don't support nested probes and drives.
796 if (region.isProperAncestor(user->getParentRegion()))
797 return false;
798 // Ignore uses outside of the region.
799 if (user->getParentRegion() != &region)
800 return true;
801 // Projection operations are okay.
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});
807 return true;
808 }
809 return isa<PrbOp>(user) || isBlockingDrive(user) || isDeltaDrive(user);
810 };
811 checkedUsers.clear();
812 if (!llvm::all_of(operand.getUsers(), [&](auto *user) {
813 auto allOk = true;
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();
819 return allOk;
820 }))
821 continue;
822
823 slots.push_back(operand);
824 }
825 });
826
827 // Populate `promotable` with the slots and projections we are promoting.
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);
834
835 LLVM_DEBUG(llvm::dbgs() << "Found " << slots.size() << " promotable slots, "
836 << promotable.size() << " promotable values\n");
837}
838
839/// Resolve SSA values in `projection` to the `slot` they are projecting into.
840/// Simply returns the given value if it is not in `projections`.
841Value Promoter::resolveSlot(Value projectionOrSlot) {
842 if (auto slot = projections.lookup(projectionOrSlot))
843 return slot;
844 return projectionOrSlot;
845}
846
847/// Explicitly capture any probes that are live across an `llhd.wait` as block
848/// arguments and destination operand of that wait. This ensures that replacing
849/// the probe with a reaching definition later on will capture the value of the
850/// reaching definition before the wait.
851void Promoter::captureAcrossWait() {
852 if (region.hasOneBlock())
853 return;
854
855 SmallVector<WaitOp> waitOps;
856 for (auto &block : region)
857 if (auto waitOp = dyn_cast<WaitOp>(block.getTerminator()))
858 waitOps.push_back(waitOp);
859
860 DominanceInfo dominance(region.getParentOp());
861 Liveness liveness(region.getParentOp());
862
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();
872 }
873 }
874 }
875}
876
877/// Add a probe as block argument to a list of wait ops and update uses of the
878/// probe to use the added block arguments as appropriate. This may insert
879/// additional block arguments in case the probe and added block arguments both
880/// reach the same block.
881void Promoter::captureAcrossWait(PrbOp probeOp, ArrayRef<WaitOp> waitOps,
882 Liveness &liveness, DominanceInfo &dominance) {
883 LLVM_DEBUG({
884 llvm::dbgs() << "Capture " << probeOp << "\n";
885 for (auto waitOp : waitOps)
886 llvm::dbgs() << "- Across " << waitOp << "\n";
887 });
888
889 // Calculate the merge points for this probe once it gets promoted to block
890 // arguments across the wait ops.
891 auto &domTree = dominance.getDomTree(&region);
892 llvm::IDFCalculatorBase<Block, false> idfCalculator(domTree);
893
894 // Calculate the set of blocks which will define this probe as a distinct
895 // value.
896 SmallPtrSet<Block *, 4> definingBlocks;
897 definingBlocks.insert(probeOp->getBlock());
898 for (auto waitOp : waitOps)
899 definingBlocks.insert(waitOp.getDest());
900 idfCalculator.setDefiningBlocks(definingBlocks);
901
902 // Calculate where the probe is live.
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);
908
909 // Calculate the merge points where we will have to insert block arguments for
910 // this probe.
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");
918
919 // Perform a depth-first search starting at the block containing the probe,
920 // which dominates all its uses. When we encounter a block that is a merge
921 // point, insert a block argument.
922 struct WorklistItem {
923 DominanceInfoNode *domNode;
924 Value reachingDef;
925 };
926 SmallVector<WorklistItem> worklist;
927 worklist.push_back({domTree.getNode(probeOp->getBlock()), probeOp});
928
929 while (!worklist.empty()) {
930 auto item = worklist.pop_back_val();
931 auto *block = item.domNode->getBlock();
932
933 // If this block is a merge point, insert a block argument for the probe.
934 if (mergePoints.contains(block))
935 item.reachingDef =
936 block->addArgument(probeOp.getType(), probeOp.getLoc());
937
938 // Replace any uses of the probe in this block with the current reaching
939 // definition.
940 for (auto &op : *block)
941 op.replaceUsesOfWith(probeOp, item.reachingDef);
942
943 // If the terminator of this block branches to a merge point, add the
944 // current reaching definition as a destination operand.
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);
953 }
954
955 for (auto *child : item.domNode->children())
956 worklist.push_back({child, item.reachingDef});
957 }
958}
959
960//===----------------------------------------------------------------------===//
961// Lattice Construction and Propagation
962//===----------------------------------------------------------------------===//
963
964/// Populate the lattice with nodes and values corresponding to the blocks and
965/// relevant operations in the region we're promoting.
966void Promoter::constructLattice() {
967 // Create entry nodes for each block.
969 for (auto &block : region) {
970 auto *entry = lattice.createNode<BlockEntry>(&block, lattice.createValue());
971 blockEntries.insert({&block, entry});
972 }
973
974 // Create nodes for each operation that is relevant for the pass.
975 for (auto &block : region) {
976 auto *valueBefore = blockEntries.lookup(&block)->valueAfter;
977
978 // Handle operations.
979 for (auto &op : block.without_terminator()) {
980 // Handle probes.
981 if (auto probeOp = dyn_cast<PrbOp>(op)) {
982 if (!promotable.contains(probeOp.getSignal()))
983 continue;
984 auto *node = lattice.createNode<ProbeNode>(
985 probeOp, resolveSlot(probeOp.getSignal()), valueBefore,
986 lattice.createValue());
987 valueBefore = node->valueAfter;
988 continue;
989 }
990
991 // Handle drives.
992 if (auto driveOp = dyn_cast<DrvOp>(op)) {
993 if (!isBlockingDrive(&op) && !isDeltaDrive(&op))
994 continue;
995 if (!promotable.contains(driveOp.getSignal()))
996 continue;
997 auto condition = DriveCondition::always();
998 if (auto enable = driveOp.getEnable())
999 condition = DriveCondition::conditional(enable);
1000 // Drives that target a slot directly provide the driven value as a
1001 // definition for the slot. Drives to projections have their value
1002 // calculated later on.
1003 auto slot = resolveSlot(driveOp.getSignal());
1004 auto *def = driveOp.getSignal() == slot
1005 ? lattice.createDef(driveOp.getValue(), condition)
1006 : lattice.createDef(driveOp->getBlock(),
1007 getStoredType(slot), condition);
1008 auto *node = lattice.createNode<DriveNode>(
1009 driveOp, slot, def, valueBefore, lattice.createValue());
1010 valueBefore = node->valueAfter;
1011 continue;
1012 }
1013
1014 // Handle local signals.
1015 if (auto signalOp = dyn_cast<SignalOp>(op)) {
1016 if (!promotable.contains(signalOp))
1017 continue;
1018 auto *def =
1019 lattice.createDef(signalOp.getInit(), DriveCondition::never());
1020 auto *node = lattice.createNode<SignalNode>(signalOp, def, valueBefore,
1021 lattice.createValue());
1022 valueBefore = node->valueAfter;
1023 continue;
1024 }
1025 }
1026
1027 // Create the exit node for the block.
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);
1033 }
1034 }
1035}
1036
1037/// Propagate the lattice values backwards against control flow until a fixed
1038/// point is reached.
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);
1046 }
1047}
1048
1049/// Propagate the lattice value after a node backward to the value before a
1050/// 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);
1056 }
1057 };
1058
1059 // Probes need a definition for the probed slot to be available.
1060 if (auto *probe = dyn_cast<ProbeNode>(node)) {
1061 auto needed = probe->valueAfter->neededDefs;
1062 needed.insert(probe->slot);
1063 update(probe->valueBefore, needed);
1064 return;
1065 }
1066
1067 // Blocking unconditional drives to an entire slot kill the need for a
1068 // definition to be available, since they provide a definition themselves.
1069 // Conditional drives propagate the need for a definition, since they have to
1070 // forward an incoming reaching def in case they are disabled. Drives to
1071 // projections need a definition to be available such that they can partially
1072 // update it.
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);
1080 return;
1081 }
1082
1083 // Local signal declarations kill the need for a definition to be available,
1084 // since the op is the first time a signal becomes available and the op
1085 // provides an initial value as a definition.
1086 if (auto *signal = dyn_cast<SignalNode>(node)) {
1087 auto needed = signal->valueAfter->neededDefs;
1088 needed.erase(signal->getSignalOp());
1089 update(signal->valueBefore, needed);
1090 return;
1091 }
1092
1093 // Block entries simply trigger updates to all their predecessors.
1094 if (auto *entry = dyn_cast<BlockEntry>(node)) {
1095 for (auto *predecessor : entry->predecessors)
1096 markDirty(predecessor);
1097 return;
1098 }
1099
1100 // Block exits merge any needed definitions from their successors.
1101 if (auto *exit = dyn_cast<BlockExit>(node)) {
1102 if (exit->suspends)
1103 return;
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);
1109 return;
1110 }
1111
1112 assert(false && "unhandled node in backward propagation");
1113}
1114
1115void Promoter::propagateForward() {
1116 DominanceInfo dominance(region.getParentOp());
1117 propagateForward(true, dominance);
1118 propagateForward(false, dominance);
1119}
1120
1121/// Propagate the lattice values forwards along with control flow until a fixed
1122/// point is reached. If `optimisticMerges` is true, block entry points
1123/// propagate definitions from their predecessors into the block without
1124/// creating a merge definition even if the definition is not available in all
1125/// predecessors. This is overly optimistic, but initially helps definitions
1126/// propagate through loop structures. If `optimisticMerges` is false, block
1127/// entry points create merge definitions for definitions that are not available
1128/// in all predecessors.
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);
1137 }
1138}
1139
1140/// Propagate the lattice value before a node forward to the value after a node.
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);
1147 }
1148 };
1149
1150 // Probes simply propagate any reaching defs.
1151 if (auto *probe = dyn_cast<ProbeNode>(node)) {
1152 update(probe->valueAfter, probe->valueBefore->reachingDefs);
1153 return;
1154 }
1155
1156 // Drives propagate the driven value as a reaching def. Blocking drives kill
1157 // earlier non-blocking drives. This reflects Verilog and VHDL behaviour,
1158 // where a drive sequence like
1159 //
1160 // a <= #10ns 42; // A
1161 // a <= 43; // B
1162 // a = 44; // C
1163 //
1164 // would see (B) override (A), because it happens earlier, and (C) override
1165 // (B), because it in turn happens earlier.
1166 if (auto *drive = dyn_cast<DriveNode>(node)) {
1167 auto reaching = drive->valueBefore->reachingDefs;
1168
1169 // If the drive is conditional or driving a projection of a slot, merge any
1170 // incoming reaching def into the reaching def created by the drive. This is
1171 // necessary since a conditional drive following an unconditional drive may
1172 // have to insert a multiplexer to forward to subsequent probes.
1173 if (drive->drivesProjection() || drive->getDriveOp().getEnable()) {
1174 auto *inDef = reaching.lookup(drive->slot);
1175 if (inDef) {
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();
1182 }
1183 }
1184
1185 reaching[drive->slot] = drive->def;
1186 if (!isDelayed(drive->slot))
1187 reaching.erase(delayedSlot(getSlot(drive->slot)));
1188 update(drive->valueAfter, reaching);
1189 return;
1190 }
1191
1192 // Signals propagate their initial value as a reaching def. They also kill any
1193 // earlier definitions, which should not be able to reach the signal in the
1194 // first place.
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);
1200 return;
1201 }
1202
1203 // Block entry points propagate any reaching definitions available in all
1204 // predecessors, plus any probes inserted locally.
1205 if (auto *entry = dyn_cast<BlockEntry>(node)) {
1206 // Propagate reaching definitions for each inserted probe.
1208 for (auto [slot, insertedProbe] : entry->insertedProbes) {
1209 reaching[blockingSlot(slot)] = insertedProbe;
1210 reaching[delayedSlot(slot)] = insertedProbe;
1211 }
1212
1213 // Propagate reaching definitions from predecessors, creating new
1214 // definitions in case of a merge.
1216 for (auto *predecessor : entry->predecessors) {
1217 if (predecessor->suspends)
1218 continue;
1219 // Propogate signal definitions only to blocks that are dominated by the
1220 // signal itself.
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))
1225 continue;
1226 reachingDefs.insert(defEntry);
1227 }
1228 }
1229
1230 for (auto pair : reachingDefs) {
1231 DefSlot slot = pair.first;
1232 Def *reachingDef = pair.second;
1233 DriveCondition reachingDefCondition = reachingDef->condition;
1234
1235 // Do not override inserted probes.
1236 if (reaching.contains(slot))
1237 continue;
1238
1239 // Check if all predecessors provide a definition for this slot. If any
1240 // multiple definitions for the same slot reach us, simply set the
1241 // `reachingDef` to null such that we can insert a new merge definition.
1242 // Separately track whether the drive mode of all definitions is
1243 // identical. This is often the case, for example when the definitions of
1244 // two unconditional drives converge, and we would like to preserve that
1245 // both drives were unconditional, even if the driven value differs.
1246 if (llvm::any_of(entry->predecessors, [&](auto *predecessor) {
1247 return predecessor->suspends;
1248 }))
1249 continue;
1250
1251 for (auto *predecessor : entry->predecessors) {
1252 auto otherDef = predecessor->valueBefore->reachingDefs.lookup(slot);
1253 if (!otherDef && optimisticMerges)
1254 continue;
1255 // If the definitions are not identical, indicate that we will have
1256 // to create a new merge def.
1257 if (reachingDef != otherDef)
1258 reachingDef = nullptr;
1259 // If the definitions have different modes, indicate that we will
1260 // have to create a conditional drive later.
1261 auto condition =
1262 otherDef ? otherDef->condition : DriveCondition::never();
1263 if (reachingDefCondition != condition)
1264 reachingDefCondition = DriveCondition::conditional();
1265 }
1266
1267 // Create a merge definition if different definitions reach us from our
1268 // predecessors.
1269 if (!reachingDef)
1270 reachingDef = entry->mergedDefs.lookup(slot);
1271 if (!reachingDef) {
1272 reachingDef = lattice.createDef(entry->block, getStoredType(slot),
1273 reachingDefCondition);
1274 entry->mergedDefs.insert({slot, reachingDef});
1275 } else {
1276 reachingDef->condition = reachingDefCondition;
1277 }
1278 reaching.insert({slot, reachingDef});
1279 }
1280
1281 update(entry->valueAfter, reaching);
1282 return;
1283 }
1284
1285 // Block exits simply trigger updates to all their successors.
1286 if (auto *exit = dyn_cast<BlockExit>(node)) {
1287 for (auto *successor : exit->successors)
1288 markDirty(successor);
1289 return;
1290 }
1291
1292 assert(false && "unhandled node in forward propagation");
1293}
1294
1295/// Mark a lattice node to be updated during propagation.
1296void Promoter::markDirty(LatticeNode *node) {
1297 assert(node);
1298 dirtyNodes.insert(node);
1299}
1300
1301//===----------------------------------------------------------------------===//
1302// Drive/Probe Insertion
1303//===----------------------------------------------------------------------===//
1304
1305/// Insert additional probe blocks where needed. This can happen if a definition
1306/// is needed in a block which has a suspending and non-suspending predecessor.
1307/// In that case we would like to insert probes in the predecessor blocks, but
1308/// cannot do so because of the suspending predecessor.
1309void Promoter::insertProbeBlocks() {
1310 // Find all blocks that have any needed definition that can't propagate beyond
1311 // one of its predecessors. If that's the case, we need an additional probe
1312 // block after that predecessor.
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))
1321 ++numIncoming;
1322 if (numIncoming != 0 && numIncoming != entry->predecessors.size())
1323 partialSlots.push_back(slot);
1324 }
1325 for (auto *predecessor : entry->predecessors)
1326 if (llvm::any_of(partialSlots, [&](auto slot) {
1327 return !predecessor->valueBefore->neededDefs.contains(slot);
1328 }))
1329 worklist.insert({predecessor, entry});
1330 }
1331 }
1332
1333 // Insert probe blocks after all blocks we have identified.
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);
1346
1347 // Create new nodes in the lattice for the added block.
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);
1356 }
1357}
1358
1359/// Insert probes wherever a definition is needed for the first time. This is
1360/// the case in the entry block, after any suspensions, and after operations
1361/// that have unknown effects on memory slots.
1362void Promoter::insertProbes() {
1363 for (auto *node : lattice.nodes) {
1364 if (auto *entry = dyn_cast<BlockEntry>(node))
1365 insertProbes(entry);
1366 }
1367}
1368
1369/// Insert probes at the beginning of a block for definitions that are needed in
1370/// this block but not in its predecessors.
1371void Promoter::insertProbes(BlockEntry *node) {
1372 auto builder = OpBuilder::atBlockBegin(node->block);
1373 for (auto neededDef : slots) {
1374 if (!node->valueAfter->neededDefs.contains(neededDef))
1375 continue;
1376 if (!node->predecessors.empty() &&
1377 llvm::all_of(node->predecessors, [&](auto *predecessor) {
1378 return predecessor->valueBefore->neededDefs.contains(neededDef);
1379 }))
1380 continue;
1381 LLVM_DEBUG(llvm::dbgs() << "- Inserting probe for " << neededDef
1382 << " in block " << node->block << "\n");
1383 OpBuilder::InsertionGuard guard(builder);
1384 // If the neededDef is in the same block, one can't just insert at top.
1385 if (Operation *op = neededDef.getDefiningOp()) {
1386 if (op->getBlock() == node->block)
1387 builder.setInsertionPointAfterValue(neededDef);
1388 }
1389 auto value = PrbOp::create(builder, neededDef.getLoc(), neededDef);
1390 auto *def = lattice.createDef(value, DriveCondition::never());
1391 node->insertedProbes.push_back({neededDef, def});
1392 }
1393}
1394
1395/// Insert additional drive blocks where needed. This can happen if a definition
1396/// continues into some of a block's successors, but not all of them.
1397void Promoter::insertDriveBlocks() {
1398 // Find all blocks that have any reaching definition that can't propagate
1399 // beyond one of its successors. If that's the case, we need an additional
1400 // drive block before that successor.
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())
1407 continue;
1408 unsigned numContinues = 0;
1409 for (auto *successor : exit->successors)
1410 if (successor->valueAfter->reachingDefs.contains(slot))
1411 ++numContinues;
1412 if (numContinues != 0 && numContinues != exit->successors.size())
1413 partialSlots.push_back(slot);
1414 }
1415 for (auto *successor : exit->successors)
1416 if (llvm::any_of(partialSlots, [&](auto slot) {
1417 return !successor->valueAfter->reachingDefs.contains(slot);
1418 }))
1419 worklist.insert({exit, successor});
1420 }
1421 }
1422
1423 // Insert drive blocks before all blocks we have identified.
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);
1436
1437 // Create new nodes in the lattice for the added block.
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);
1447 }
1448}
1449
1450/// Insert drives wherever a reaching definition can no longer propagate. This
1451/// is the before any suspensions and before operations that have unknown
1452/// effects on memory slots.
1453void Promoter::insertDrives() {
1454 for (auto *node : lattice.nodes) {
1455 if (auto *exit = dyn_cast<BlockExit>(node))
1456 insertDrives(exit);
1457 else if (auto *drive = dyn_cast<DriveNode>(node))
1458 insertDrives(drive);
1459 }
1460}
1461
1462/// Insert drives at block terminators for definitions that do not propagate
1463/// into successors.
1464void Promoter::insertDrives(BlockExit *node) {
1465 auto builder = OpBuilder::atBlockTerminator(node->block);
1466
1467 ConstantTimeOp epsilonTime;
1468 ConstantTimeOp deltaTime;
1469 auto getTime = [&](bool delta) {
1470 if (delta) {
1471 if (!deltaTime)
1472 deltaTime = ConstantTimeOp::create(builder, node->terminator->getLoc(),
1473 0, "ns", 1, 0);
1474 return deltaTime;
1475 }
1476 if (!epsilonTime)
1477 epsilonTime = ConstantTimeOp::create(builder, node->terminator->getLoc(),
1478 0, "ns", 0, 1);
1479 return epsilonTime;
1480 };
1481
1482 auto insertDriveForSlot = [&](DefSlot slot) {
1483 auto reachingDef = node->valueBefore->reachingDefs.lookup(slot);
1484 if (!reachingDef || reachingDef->condition.isNever())
1485 return;
1486 if (!node->suspends && !node->successors.empty() &&
1487 llvm::all_of(node->successors, [&](auto *successor) {
1488 return successor->valueAfter->reachingDefs.contains(slot);
1489 }))
1490 return;
1491 LLVM_DEBUG(llvm::dbgs() << "- Inserting drive for " << getSlot(slot) << " "
1492 << (isDelayed(slot) ? "(delayed)" : "(blocking)")
1493 << " before " << *node->terminator << "\n");
1494 auto time = getTime(isDelayed(slot));
1495 auto value = reachingDef->getValueOrPlaceholder();
1496 auto enable = reachingDef->condition.isConditional()
1497 ? reachingDef->getConditionOrPlaceholder()
1498 : Value{};
1499 DrvOp::create(builder, getLoc(slot), getSlot(slot), value, time, enable);
1500 };
1501
1502 for (auto slot : slots)
1503 insertDriveForSlot(blockingSlot(slot));
1504 for (auto slot : slots)
1505 insertDriveForSlot(delayedSlot(slot));
1506}
1507
1508/// Remove drives to slots that we are promoting. These have been replaced with
1509/// new drives at block exits.
1510void Promoter::insertDrives(DriveNode *node) {
1511 if (!promotable.contains(getSlot(node->slot)))
1512 return;
1513 LLVM_DEBUG(llvm::dbgs() << "- Removing drive " << *node->op << "\n");
1514 pruner.eraseNow(node->op);
1515 node->op = nullptr;
1516}
1517
1518//===----------------------------------------------------------------------===//
1519// Drive-to-Probe Forwarding
1520//===----------------------------------------------------------------------===//
1521
1522/// Forward definitions throughout the IR.
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);
1529 }
1530}
1531
1532/// Replace probes with the corresponding reaching definition.
1533void Promoter::resolveDefinitions(ProbeNode *node) {
1534 if (!promotable.contains(node->slot))
1535 return;
1536 auto *def = node->valueBefore->reachingDefs.lookup(blockingSlot(node->slot));
1537 assert(def && "no definition reaches probe");
1538
1539 // Gather any projections between the probe and the underlying slot.
1540 auto projections = getProjections(node->op->getOperand(0), node->slot);
1541
1542 // Extract the projected value from the aggregate.
1543 auto builder = OpBuilder(node->op);
1544 auto value = def->getValueOrPlaceholder();
1545 value = unpackProjections(builder, value, projections);
1546
1547 // Replace the probe result with the projected value.
1548 LLVM_DEBUG(llvm::dbgs() << "- Replacing " << *node->op << " with " << value
1549 << "\n");
1550 replaceValueWith(node->op->getResult(0), value);
1551 pruner.eraseNow(node->op);
1552 node->op = nullptr;
1553}
1554
1555/// Mutate reaching definitions for conditional drives or drives that target
1556/// projections of a slot.
1557void Promoter::resolveDefinitions(DriveNode *node) {
1558 if (!promotable.contains(getSlot(node->slot)))
1559 return;
1560
1561 // Check whether the drive already has a value and condition set for its
1562 // reaching def. This is the case for drives to an entire slot. Conditional
1563 // drives and drives to a projection will have no value set initially, in
1564 // which case either the value is null or it is a placeholder.
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);
1571}
1572
1573void Promoter::resolveDefinitionValue(DriveNode *node) {
1574 // Get the slot definition reaching the drive. This is the value the drive has
1575 // to update.
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");
1580
1581 // Gather any projections between the drive and the underlying slot.
1582 auto projections = getProjections(driveOp.getSignal(), getSlot(node->slot));
1583
1584 // Extract the current value from the aggregate.
1585 auto builder = OpBuilder(driveOp);
1586 auto value = inDef->getValueOrPlaceholder();
1587 value = unpackProjections(builder, value, projections);
1588
1589 // Update the value according to the drive.
1590 pruner.eraseLaterIfUnused(value);
1591 if (!driveOp.getEnable())
1592 value = driveOp.getValue();
1593 else
1594 value = builder.createOrFold<comb::MuxOp>(
1595 driveOp.getLoc(), driveOp.getEnable(), driveOp.getValue(), value);
1596
1597 // Inject the updated value into the aggregate.
1598 value = packProjections(builder, value, projections);
1599
1600 // Track the updated slot value in the drive's reaching def.
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;
1608 }
1609 node->def->value = value;
1610}
1611
1612void Promoter::resolveDefinitionCondition(DriveNode *node) {
1613 // Get the slot definition reaching the drive. This contains the condition the
1614 // drive has to update.
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);
1620
1621 // Adjust the drive condition by combining the incoming condition with the
1622 // enable of this drive op.
1623 Value condition;
1624 if (inDef->condition.isNever())
1625 condition = driveOp.getEnable();
1626 else
1627 condition =
1628 builder.createOrFold<comb::OrOp>(driveOp.getLoc(), driveOp.getEnable(),
1629 inDef->getConditionOrPlaceholder());
1630
1631 // Track the updated drive condition in the drive's reaching def.
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;
1639 }
1640 node->def->condition.setCondition(condition);
1641}
1642
1643//===----------------------------------------------------------------------===//
1644// Block Argument Insertion
1645//===----------------------------------------------------------------------===//
1646
1647/// Insert block arguments into the IR.
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);
1655 }
1656}
1657
1658/// Insert block arguments for any merging definitions for which a placeholder
1659/// value has been created. Also insert corresponding successor operands to any
1660/// ops branching here. Returns true if any arguments were inserted.
1661///
1662/// This function may create additional placeholders in predecessor blocks.
1663/// Creating block arguments in a later block may uncover additional arguments
1664/// to be inserted in a previous one. Therefore this function must be called
1665/// until no more block arguments are inserted.
1666bool Promoter::insertBlockArgs(BlockEntry *node) {
1667 // Determine which slots require a merging definition. Use the `slots` array
1668 // for this to have a deterministic order for the block arguments. We only
1669 // insert block arguments for the def's value or drive condition if
1670 // placeholders have been created for them, indicating that they are actually
1671 // used.
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});
1681 }
1682 }
1683 };
1684 for (auto slot : slots) {
1685 addNeededSlot(blockingSlot(slot));
1686 addNeededSlot(delayedSlot(slot));
1687 }
1688 if (neededSlots.empty())
1689 return false;
1690 LLVM_DEBUG(llvm::dbgs() << "- Adding " << neededSlots.size()
1691 << " args to block " << node->block << "\n");
1692
1693 // Add the block arguments.
1694 for (auto [slot, which] : neededSlots) {
1695 auto *def = node->mergedDefs.lookup(slot);
1696 assert(def);
1697 switch (which) {
1698 case Which::Value: {
1699 // Create an argument for the definition's value and replace any
1700 // placeholder we might have created earlier.
1701 auto *placeholder = def->value.getDefiningOp();
1702 assert(isa_and_nonnull<UnrealizedConversionCastOp>(placeholder) &&
1703 "placeholder replaced but valueIsPlaceholder still set");
1704 auto arg = node->block->addArgument(getStoredType(slot), getLoc(slot));
1705 replaceValueWith(placeholder->getResult(0), arg);
1706 pruner.eraseNow(placeholder);
1707 def->value = arg;
1708 def->valueIsPlaceholder = false;
1709 break;
1710 }
1711 case Which::Condition: {
1712 // If the definition's drive mode is conditional, create an argument for
1713 // the drive condition and replace any placeholder we might have created
1714 // earlier.
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;
1724 break;
1725 }
1726 }
1727 }
1728
1729 // Add successor operands to the predecessor terminators.
1730 for (auto *predecessor : node->predecessors) {
1731 // Collect the interesting reaching definitions in the predecessor.
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);
1736 switch (which) {
1737 case Which::Value:
1738 if (def) {
1739 args.push_back(def->getValueOrPlaceholder());
1740 } else {
1741 auto type = getStoredType(slot);
1742 auto flatType = builder.getIntegerType(hw::getBitWidth(type));
1743 Value value =
1744 hw::ConstantOp::create(builder, getLoc(slot), flatType, 0);
1745 if (type != flatType)
1746 value = hw::BitcastOp::create(builder, getLoc(slot), type, value);
1747 args.push_back(value);
1748 }
1749 break;
1750 case Which::Condition:
1751 if (def) {
1752 args.push_back(def->getConditionOrPlaceholder());
1753 } else {
1754 args.push_back(hw::ConstantOp::create(builder, getLoc(slot),
1755 builder.getI1Type(), 0));
1756 }
1757 break;
1758 }
1759 }
1760
1761 // Add the reaching definitions to the branch op.
1762 auto branchOp = cast<BranchOpInterface>(predecessor->terminator);
1763 for (auto &blockOperand : branchOp->getBlockOperands())
1764 if (blockOperand.get() == node->block)
1765 branchOp.getSuccessorOperands(blockOperand.getOperandNumber())
1766 .append(args);
1767 }
1768
1769 return true;
1770}
1771
1772/// Replace all uses of an old value with a new value in the IR, and update all
1773/// mentions of the old value in the lattice to the new value.
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);
1782 }
1783}
1784
1785//===----------------------------------------------------------------------===//
1786// Cleanup
1787//===----------------------------------------------------------------------===//
1788
1789/// Remove all unused local signals.
1790void Promoter::removeUnusedLocalSignals() {
1791 for (auto *node : lattice.nodes)
1792 if (auto *signal = dyn_cast<SignalNode>(node))
1793 removeUnusedLocalSignal(signal);
1794}
1795
1796/// Remove a local signal if it is only used by projection ops and drives, but
1797/// never probed. Since the signal is local and cannot be observed in any other
1798/// way, we can safely remove it along with any projection ops and drives.
1799void Promoter::removeUnusedLocalSignal(SignalNode *signal) {
1800 // Check if the signal is only ever projected into and driven, but never
1801 // probed.
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))
1809 return;
1810 for (auto *user : op->getUsers())
1811 if (users.insert(user))
1812 worklist.push_back(user);
1813 }
1814
1815 // If we get here, the local signal is never probed. This means we can safely
1816 // remove it.
1817 LLVM_DEBUG(llvm::dbgs() << "- Removing local signal " << *signal->op << "\n");
1818 for (auto *op : llvm::reverse(users))
1819 pruner.eraseNow(op);
1820}
1821
1822//===----------------------------------------------------------------------===//
1823// Pass Infrastructure
1824//===----------------------------------------------------------------------===//
1825
1826namespace {
1827struct Mem2RegPass : public llhd::impl::Mem2RegPassBase<Mem2RegPass> {
1828 void runOnOperation() override;
1829};
1830} // namespace
1831
1832void Mem2RegPass::runOnOperation() {
1833 SmallVector<Region *> regions;
1834 getOperation()->walk<WalkOrder::PreOrder>([&](Operation *op) {
1835 if (isa<ProcessOp, FinalOp, CombinationalOp>(op)) {
1836 auto &region = op->getRegion(0);
1837 if (!region.empty())
1838 regions.push_back(&region);
1839 return WalkResult::skip();
1840 }
1841 return WalkResult::advance();
1842 });
1843 for (auto *region : regions)
1844 if (failed(Promoter(*region).promote()))
1845 return signalPassFailure();
1846}
static bool isAlways(Attribute attr, bool expected)
Definition ArcFolds.cpp:22
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)
Definition Mem2Reg.cpp:209
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...
Definition Mem2Reg.cpp:622
static Location getLoc(DefSlot slot)
Definition Mem2Reg.cpp:216
static bool isDeltaDrive(Operation *op)
Check whether an operation is a llhd.drive with a delta delay.
Definition Mem2Reg.cpp:65
static ProjectionStack getProjections(Value fromSignal, Value toSlot)
Collect the llhd.sig.
Definition Mem2Reg.cpp:570
static bool isDeltaDelay(Value value)
Check whether a value is defined by llhd.constant_time <0ns, 1d, 0e>.
Definition Mem2Reg.cpp:47
static DefSlot blockingSlot(Value slot)
Definition Mem2Reg.cpp:206
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 ...
Definition Mem2Reg.cpp:586
static DefSlot delayedSlot(Value slot)
Definition Mem2Reg.cpp:207
static Value getSlot(DefSlot slot)
Definition Mem2Reg.cpp:208
SmallVector< Projection > ProjectionStack
A stack of projection operations.
Definition Mem2Reg.cpp:563
static bool isBlockingDrive(Operation *op)
Check whether an operation is a llhd.drive with an epsilon delay.
Definition Mem2Reg.cpp:57
static Type getStoredType(Value slot)
Definition Mem2Reg.cpp:210
static bool isEpsilonDelay(Value value)
Check whether a value is defined by llhd.constant_time <0ns, 0d, 1e>.
Definition Mem2Reg.cpp:38
PointerIntPair< Value, 1 > DefSlot
The slot a reaching definition specifies a value for, alongside a bit indicating whether the definiti...
Definition Mem2Reg.cpp:205
static StringAttr append(StringAttr base, const Twine &suffix)
Return a attribute with the specified suffix appended.
create(data_type, value)
Definition hw.py:441
create(data_type, value)
Definition hw.py:433
Direction get(bool isOutput)
Returns an output direction if isOutput is true, otherwise returns an input direction.
Definition CalyxOps.cpp:55
static bool operator==(const ModulePort &a, const ModulePort &b)
Definition HWTypes.h:35
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
bool operator!=(uint64_t a, const FVInt &b)
Definition FVInt.h:685
Utility that tracks operations that have potentially become unused and allows them to be cleaned up a...
static DriveCondition getEmptyKey()
Definition Mem2Reg.cpp:183
static DriveCondition getTombstoneKey()
Definition Mem2Reg.cpp:186
static bool isEqual(DriveCondition lhs, DriveCondition rhs)
Definition Mem2Reg.cpp:193
static unsigned getHashValue(DriveCondition d)
Definition Mem2Reg.cpp:189