11#include "mlir/Analysis/Liveness.h"
12#include "mlir/Dialect/ControlFlow/IR/ControlFlowOps.h"
13#include "mlir/IR/Matchers.h"
14#include "llvm/Support/Debug.h"
16#define DEBUG_TYPE "llhd-hoist-signals"
20#define GEN_PASS_DEF_HOISTSIGNALSPASS
21#include "circt/Dialect/LLHD/Transforms/LLHDPasses.h.inc"
28using llvm::PointerUnion;
29using llvm::SmallSetVector;
38 ProbeHoister(Region ®ion) : region(region) {}
41 void findValuesLiveAcrossWait(Liveness &liveness);
49 DenseSet<Value> liveAcrossWait;
52 DenseMap<Value, PrbOp> hoistedProbes;
56void ProbeHoister::hoist() {
57 Liveness liveness(region.getParentOp());
58 findValuesLiveAcrossWait(liveness);
73void ProbeHoister::findValuesLiveAcrossWait(Liveness &liveness) {
76 SmallVector<Value> worklist;
77 for (
auto &block : region)
78 if (isa<WaitOp>(block.getTerminator()))
79 for (auto value : liveness.getLiveOut(&block))
80 if (value.getParentRegion() == ®ion)
81 if (liveAcrossWait.insert(value).second)
82 worklist.push_back(value);
88 while (!worklist.empty()) {
89 auto value = worklist.pop_back_val();
90 if (
auto *defOp = value.getDefiningOp()) {
91 for (
auto operand : defOp->getOperands())
92 if (operand.getParentRegion() == ®ion)
93 if (liveAcrossWait.insert(operand).second)
94 worklist.push_back(operand);
96 auto blockArg = cast<BlockArgument>(value);
97 for (
auto &use : blockArg.getOwner()->getUses()) {
98 auto branch = dyn_cast<BranchOpInterface>(use.getOwner());
101 auto operand = branch.getSuccessorOperands(
102 use.getOperandNumber())[blockArg.getArgNumber()];
103 if (operand.getParentRegion() == ®ion)
104 if (liveAcrossWait.insert(operand).second)
105 worklist.push_back(operand);
110 LLVM_DEBUG(llvm::dbgs() <<
"Found " << liveAcrossWait.size()
111 <<
" values live across wait\n");
119void ProbeHoister::hoistProbes() {
120 auto findExistingProbe = [&](Value signal) {
121 for (
auto *user : signal.getUsers())
122 if (auto probeOp = dyn_cast<PrbOp>(user))
123 if (probeOp->getParentRegion()->isProperAncestor(®ion))
128 for (
auto &block : region) {
131 if (!llvm::all_of(block.getPredecessors(), [](
auto *predecessor) {
132 return isa<WaitOp>(predecessor->getTerminator());
136 for (
auto &op :
llvm::make_early_inc_range(block)) {
137 auto probeOp = dyn_cast<PrbOp>(op);
143 if (isMemoryEffectFree(&op))
150 if (liveAcrossWait.contains(probeOp)) {
151 LLVM_DEBUG(llvm::dbgs()
152 <<
"- Skipping (live across wait) " << probeOp <<
"\n");
158 if (!probeOp.getSignal().getParentRegion()->isProperAncestor(®ion)) {
159 LLVM_DEBUG(llvm::dbgs()
160 <<
"- Skipping (local signal) " << probeOp <<
"\n");
166 auto &hoistedOp = hoistedProbes[probeOp.getSignal()];
168 LLVM_DEBUG(llvm::dbgs() <<
"- Replacing " << probeOp <<
"\n");
169 probeOp.replaceAllUsesWith(hoistedOp.getResult());
172 LLVM_DEBUG(llvm::dbgs() <<
"- Hoisting " << probeOp <<
"\n");
173 if (
auto existingOp = findExistingProbe(probeOp.getSignal())) {
174 probeOp.replaceAllUsesWith(existingOp.getResult());
176 hoistedOp = existingOp;
178 if (
auto *defOp = probeOp.getSignal().getDefiningOp())
179 probeOp->moveAfter(defOp);
181 probeOp->moveBefore(region.getParentOp());
198 typedef PointerUnion<Value, IntegerAttr, TimeAttr, Type> Data;
202 DriveValue() :
data(Value{}) {}
205 static DriveValue dontCare(Type type) {
return DriveValue(type); }
208 DriveValue(IntegerAttr attr) :
data(attr) {}
211 DriveValue(TimeAttr attr) :
data(attr) {}
215 DriveValue(Value value) :
data(value) {
217 if (
auto *defOp = value.getDefiningOp())
218 if (m_Constant(&attr).match(defOp))
219 TypeSwitch<Attribute>(attr).Case<IntegerAttr, TimeAttr>(
220 [&](
auto attr) {
data = attr; });
223 bool operator==(
const DriveValue &other)
const {
return data == other.data; }
224 bool operator!=(
const DriveValue &other)
const {
return data != other.data; }
226 bool isDontCare()
const {
return isa<Type>(data); }
227 explicit operator bool()
const {
return bool(data); }
229 Type getType()
const {
230 return TypeSwitch<Data, Type>(data)
231 .Case<Value, IntegerAttr, TimeAttr>([](
auto x) {
return x.getType(); })
232 .Case<Type>([](
auto type) {
return type; });
236 explicit DriveValue(Data data) :
data(
data) {}
240struct DriveOperands {
251 SmallPtrSet<Operation *, 2> ops;
256 DriveOperands uniform;
261 const DriveValue &dv) {
265 TypeSwitch<DriveValue::Data>(dv.data)
266 .Case<Value, IntegerAttr, TimeAttr>([&](
auto x) { os << x; })
267 .Case<Type>([&](
auto) { os <<
"dont-care"; });
278 DriveHoister(ProcessOp processOp) : processOp(processOp) {}
281 void findHoistableSlots();
282 void collectDriveSets();
283 void finalizeDriveSets();
292 SmallSetVector<Value, 8> slots;
293 SmallVector<Operation *> suspendOps;
298void DriveHoister::hoist() {
299 findHoistableSlots();
308void DriveHoister::findHoistableSlots() {
309 SmallPtrSet<Value, 8> seenSlots;
310 processOp.walk([&](DrvOp op) {
311 auto slot = op.getSignal();
312 if (!seenSlots.insert(slot).second)
317 if (!slot.getDefiningOp<llhd::SignalOp>())
319 if (!slot.getParentRegion()->isProperAncestor(&processOp.getBody()))
323 if (!llvm::all_of(slot.getUsers(), [&](
auto *user) {
325 if (!processOp.getBody().isAncestor(user->getParentRegion()))
327 return isa<PrbOp, DrvOp>(user);
333 LLVM_DEBUG(llvm::dbgs() <<
"Found " << slots.size()
334 <<
" slots for drive hoisting\n");
343void DriveHoister::collectDriveSets() {
344 auto trueAttr = BoolAttr::get(processOp.getContext(),
true);
345 for (
auto &block : processOp.getBody()) {
347 auto *terminator = block.getTerminator();
348 if (!isa<WaitOp, HaltOp>(terminator))
350 suspendOps.push_back(terminator);
352 SmallPtrSet<Value, 8> drivenSlots;
353 for (
auto &op :
llvm::make_early_inc_range(
354 llvm::reverse(block.without_terminator()))) {
355 auto driveOp = dyn_cast<DrvOp>(op);
361 if (isMemoryEffectFree(&op))
368 if (!slots.contains(driveOp.getSignal())) {
369 LLVM_DEBUG(llvm::dbgs()
370 <<
"- Skipping (slot unhoistable) " << driveOp <<
"\n");
375 if (!drivenSlots.insert(driveOp.getSignal()).second) {
376 LLVM_DEBUG(llvm::dbgs()
377 <<
"- Skipping (driven later) " << driveOp <<
"\n");
382 auto operands = DriveOperands{
385 driveOp.getEnable() ? DriveValue(driveOp.getEnable())
386 : DriveValue(trueAttr),
388 auto &driveSet = driveSets[driveOp.getSignal()];
389 driveSet.ops.insert(driveOp);
390 driveSet.operands.insert({terminator, operands});
399void DriveHoister::finalizeDriveSets() {
400 auto falseAttr = BoolAttr::get(processOp.getContext(),
false);
401 for (
auto &[slot, driveSet] : driveSets) {
405 for (
auto *suspendOp : suspendOps) {
406 auto operands = DriveOperands{
407 DriveValue::dontCare(
408 cast<hw::InOutType>(slot.getType()).getElementType()),
409 DriveValue::dontCare(TimeType::get(processOp.getContext())),
410 DriveValue(falseAttr),
412 driveSet.operands.insert({suspendOp, operands});
418 auto unify = [](DriveValue &accumulator, DriveValue other) {
419 if (other.isDontCare())
421 if (accumulator == other)
423 accumulator = accumulator.isDontCare() ? other : DriveValue();
425 assert(!driveSet.operands.empty());
426 driveSet.uniform = driveSet.operands.begin()->second;
427 for (
auto [terminator, otherOperands] : driveSet.operands) {
428 unify(driveSet.uniform.value, otherOperands.value);
429 unify(driveSet.uniform.delay, otherOperands.delay);
430 unify(driveSet.uniform.enable, otherOperands.enable);
437 auto clearIfNonConst = [&](DriveValue &driveValue) {
438 if (isa_and_nonnull<Value>(driveValue.data))
439 driveValue = DriveValue();
441 clearIfNonConst(driveSet.uniform.value);
442 clearIfNonConst(driveSet.uniform.delay);
443 clearIfNonConst(driveSet.uniform.enable);
447 for (
auto slot : slots) {
448 const auto &driveSet = driveSets[slot];
449 llvm::dbgs() <<
"Drives to " << slot <<
"\n";
450 if (driveSet.uniform.value)
451 llvm::dbgs() <<
"- Uniform value: " << driveSet.uniform.value <<
"\n";
452 if (driveSet.uniform.delay)
453 llvm::dbgs() <<
"- Uniform delay: " << driveSet.uniform.delay <<
"\n";
454 if (driveSet.uniform.enable)
455 llvm::dbgs() <<
"- Uniform enable: " << driveSet.uniform.enable <<
"\n";
456 for (
auto *suspendOp : suspendOps) {
457 auto operands = driveSet.operands.lookup(suspendOp);
458 llvm::dbgs() <<
"- At " << *suspendOp <<
"\n";
459 if (!driveSet.uniform.value)
460 llvm::dbgs() <<
" - Value: " << operands.value <<
"\n";
461 if (!driveSet.uniform.delay)
462 llvm::dbgs() <<
" - Delay: " << operands.delay <<
"\n";
463 if (!driveSet.uniform.enable)
464 llvm::dbgs() <<
" - Enable: " << operands.enable <<
"\n";
474void DriveHoister::hoistDrives() {
475 if (driveSets.empty())
477 LLVM_DEBUG(llvm::dbgs() <<
"Hoisting drives of " << driveSets.size()
481 OpBuilder builder(processOp);
484 auto materialize = [&](DriveValue driveValue) -> Value {
485 OpBuilder builder(processOp);
486 return TypeSwitch<DriveValue::Data, Value>(driveValue.data)
487 .Case<Value>([](
auto value) {
return value; })
488 .Case<IntegerAttr>([&](
auto attr) {
489 auto &slot = materializedConstants[attr];
494 .Case<TimeAttr>([&](
auto attr) {
495 auto &slot = materializedConstants[attr];
498 builder.create<llhd::ConstantTimeOp>(processOp.getLoc(), attr);
501 .Case<Type>([&](
auto type) {
503 unsigned numBits = hw::getBitWidth(type);
506 processOp.getLoc(), builder.getIntegerType(numBits), 0);
507 if (value.getType() != type)
516 for (
auto *suspendOp : suspendOps) {
517 LLVM_DEBUG(llvm::dbgs()
518 <<
"- Adding yield operands to " << *suspendOp <<
"\n");
519 MutableOperandRange yieldOperands =
520 TypeSwitch<Operation *, MutableOperandRange>(suspendOp)
521 .Case<WaitOp, HaltOp>(
522 [](
auto op) {
return op.getYieldOperandsMutable(); });
524 auto addYieldOperand = [&](DriveValue uniform, DriveValue nonUniform) {
526 yieldOperands.append(materialize(nonUniform));
529 for (
auto slot : slots) {
530 auto &driveSet = driveSets[slot];
531 auto operands = driveSet.operands.lookup(suspendOp);
532 addYieldOperand(driveSet.uniform.value, operands.value);
533 addYieldOperand(driveSet.uniform.delay, operands.delay);
534 addYieldOperand(driveSet.uniform.enable, operands.enable);
539 SmallVector<Type> resultTypes(processOp->getResultTypes());
540 auto oldNumResults = resultTypes.size();
541 auto addResultType = [&](DriveValue uniform, DriveValue nonUniform) {
543 resultTypes.push_back(nonUniform.getType());
545 for (
auto slot : slots) {
546 auto &driveSet = driveSets[slot];
547 auto operands = driveSet.operands.begin()->second;
548 addResultType(driveSet.uniform.value, operands.value);
549 addResultType(driveSet.uniform.delay, operands.delay);
550 addResultType(driveSet.uniform.enable, operands.enable);
552 auto newProcessOp = builder.create<ProcessOp>(processOp.getLoc(), resultTypes,
553 processOp->getOperands(),
554 processOp->getAttrs());
555 newProcessOp.getBody().takeBody(processOp.getBody());
556 processOp.replaceAllUsesWith(
557 newProcessOp->getResults().slice(0, oldNumResults));
559 processOp = newProcessOp;
564 builder.setInsertionPointAfter(processOp);
565 auto newResultIdx = oldNumResults;
567 auto useResultValue = [&](DriveValue uniform) {
569 return processOp.getResult(newResultIdx++);
570 return materialize(uniform);
573 auto removeIfUnused = [](Value value) {
575 if (
auto *defOp = value.getDefiningOp())
576 if (defOp && isOpTriviallyDead(defOp))
580 auto trueAttr = builder.getBoolAttr(
true);
581 for (
auto slot : slots) {
582 auto &driveSet = driveSets[slot];
585 auto value = useResultValue(driveSet.uniform.value);
586 auto delay = useResultValue(driveSet.uniform.delay);
587 auto enable = driveSet.uniform.enable != DriveValue(trueAttr)
588 ? useResultValue(driveSet.uniform.enable)
591 builder.create<DrvOp>(slot.getLoc(), slot, value, delay, enable);
592 LLVM_DEBUG(llvm::dbgs() <<
"- Add " << newDrive <<
"\n");
595 for (
auto *oldOp : driveSet.ops) {
596 auto oldDrive = cast<DrvOp>(oldOp);
597 LLVM_DEBUG(llvm::dbgs() <<
"- Remove " << oldDrive <<
"\n");
598 auto delay = oldDrive.getTime();
599 auto enable = oldDrive.getEnable();
601 removeIfUnused(delay);
602 removeIfUnused(enable);
604 driveSet.ops.clear();
606 assert(newResultIdx == processOp->getNumResults());
614struct HoistSignalsPass
615 :
public llhd::impl::HoistSignalsPassBase<HoistSignalsPass> {
616 void runOnOperation()
override;
620void HoistSignalsPass::runOnOperation() {
621 SmallVector<Region *> regions;
622 getOperation()->walk<WalkOrder::PreOrder>([&](Operation *op) {
623 if (isa<ProcessOp, FinalOp>(op)) {
624 auto ®ion = op->getRegion(0);
626 regions.push_back(®ion);
627 return WalkResult::skip();
629 return WalkResult::advance();
631 for (
auto *region : regions) {
632 ProbeHoister(*region).hoist();
633 if (
auto processOp = dyn_cast<ProcessOp>(region->getParentOp()))
634 DriveHoister(processOp).hoist();
assert(baseType &&"element must be base type")
OS & operator<<(OS &os, const InnerSymTarget &target)
Printing InnerSymTarget's.
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)