Skip to content

Commit 24d394b

Browse files
uenokuuenoku
authored
[LowerSeqToSV] Make createTree iterative, NFCI (#5303)
As we expand mux into nested-if, the nest level could reach to O(10000). To avoid stack overflow this PR changes `createTree` to iterative algorithm.
1 parent 3813743 commit 24d394b

File tree

2 files changed

+62
-42
lines changed

2 files changed

+62
-42
lines changed

‎lib/Dialect/Seq/Transforms/LowerSeqToSV.cpp‎

Lines changed: 57 additions & 37 deletions
Original file line numberDiff line numberDiff line change
@@ -486,17 +486,38 @@ FirRegLower::tryRestoringSubaccess(OpBuilder &builder, Value reg, Value term,
486486

487487
void FirRegLower::createTree(OpBuilder &builder, Value reg, Value term,
488488
Value next) {
489-
// If term and next values are equivalent, we don't have to create an
490-
// assignment.
491-
if (areEquivalentValues(term, next))
492-
return;
493-
auto mux = next.getDefiningOp<comb::MuxOp>();
494-
if (mux && mux.getTwoState()) {
495-
addToIfBlock(
496-
builder, mux.getCond(),
497-
[&]() { createTree(builder, reg, term, mux.getTrueValue()); },
498-
[&]() { createTree(builder, reg, term, mux.getFalseValue()); });
499-
} else {
489+
490+
SmallVector<std::tuple<Block *, Value, Value, Value>> worklist;
491+
auto addToWorklist = [&](Value reg, Value term, Value next) {
492+
worklist.push_back({builder.getBlock(), reg, term, next});
493+
};
494+
495+
auto getArrayIndex = [&](Value reg, Value idx) {
496+
// Create an array index op just after `reg`.
497+
OpBuilder::InsertionGuard guard(builder);
498+
builder.setInsertionPointAfterValue(reg);
499+
return builder.create<sv::ArrayIndexInOutOp>(reg.getLoc(), reg, idx);
500+
};
501+
502+
SmallVector<Value, 8> opsToDelete;
503+
addToWorklist(reg, term, next);
504+
while (!worklist.empty()) {
505+
OpBuilder::InsertionGuard guard(builder);
506+
Block *block;
507+
Value reg, term, next;
508+
std::tie(block, reg, term, next) = worklist.pop_back_val();
509+
builder.setInsertionPointToEnd(block);
510+
if (areEquivalentValues(term, next))
511+
continue;
512+
513+
auto mux = next.getDefiningOp<comb::MuxOp>();
514+
if (mux && mux.getTwoState()) {
515+
addToIfBlock(
516+
builder, mux.getCond(),
517+
[&]() { addToWorklist(reg, term, mux.getTrueValue()); },
518+
[&]() { addToWorklist(reg, term, mux.getFalseValue()); });
519+
continue;
520+
}
500521
// If the next value is an array creation, split the value into
501522
// invidial elements and construct trees recursively.
502523
if (auto array = next.getDefiningOp<hw::ArrayCreateOp>()) {
@@ -508,54 +529,53 @@ void FirRegLower::createTree(OpBuilder &builder, Value reg, Value term,
508529
addToIfBlock(
509530
builder, cond,
510531
[&]() {
511-
Value nextReg;
512-
{
513-
// Create an array index op just after `reg`.
514-
OpBuilder::InsertionGuard guard(builder);
515-
builder.setInsertionPointAfterValue(reg);
516-
nextReg = builder.create<sv::ArrayIndexInOutOp>(reg.getLoc(),
517-
reg, index);
518-
}
532+
Value nextReg = getArrayIndex(reg, index);
533+
// Create a value to use for equivalence checking in the
534+
// recursive calls. Add the value to `opsToDelete` so that it can
535+
// be deleted afterwards.
519536
auto termElement =
520537
builder.create<hw::ArrayGetOp>(term.getLoc(), term, index);
521-
createTree(builder, nextReg, termElement, trueValue);
522-
termElement.erase();
538+
opsToDelete.push_back(termElement);
539+
addToWorklist(nextReg, termElement, trueValue);
523540
},
524541
[]() {});
525542
++numSubaccessRestored;
526-
return;
543+
continue;
527544
}
528545
// Compat fix for GCC12's libstdc++, cannot use
529546
// llvm::enumerate(llvm::reverse(OperandRange)). See #4900.
530-
SmallVector<Value> reverseOpValues(llvm::reverse(array.getOperands()));
531-
for (auto [idx, value] : llvm::enumerate(reverseOpValues)) {
532-
547+
// SmallVector<Value> reverseOpValues(llvm::reverse(array.getOperands()));
548+
for (auto [idx, value] : llvm::enumerate(array.getOperands())) {
549+
idx = array.getOperands().size() - idx - 1;
533550
// Create an index constant.
534551
auto idxVal = getOrCreateConstant(
535552
array.getLoc(),
536553
APInt(std::max(1u, llvm::Log2_64_Ceil(array.getOperands().size())),
537554
idx));
538555

539556
auto &index = arrayIndexCache[{reg, idx}];
540-
if (!index) {
541-
// Create an array index op just after `reg`.
542-
OpBuilder::InsertionGuard guard(builder);
543-
builder.setInsertionPointAfterValue(reg);
544-
index =
545-
builder.create<sv::ArrayIndexInOutOp>(reg.getLoc(), reg, idxVal);
546-
}
557+
if (!index)
558+
index = getArrayIndex(reg, idxVal);
547559

560+
// Create a value to use for equivalence checking in the
561+
// recursive calls. Add the value to `opsToDelete` so that it can
562+
// be deleted afterwards.
548563
auto termElement =
549564
builder.create<hw::ArrayGetOp>(term.getLoc(), term, idxVal);
550-
createTree(builder, index, termElement, value);
551-
// This value was used to check the equivalence of elements so useless
552-
// anymore.
553-
termElement.erase();
565+
opsToDelete.push_back(termElement);
566+
addToWorklist(index, termElement, value);
554567
}
555-
return;
568+
continue;
556569
}
570+
557571
builder.create<sv::PAssignOp>(term.getLoc(), reg, next);
558572
}
573+
574+
while (!opsToDelete.empty()) {
575+
auto value = opsToDelete.pop_back_val();
576+
assert(value.use_empty());
577+
value.getDefiningOp()->erase();
578+
}
559579
}
560580

561581
FirRegLower::RegLowerInfo FirRegLower::lower(FirRegOp reg) {

‎test/Dialect/Seq/firreg.mlir‎

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -585,8 +585,8 @@ hw.module @ArrayElements(%a: !hw.array<2xi1>, %clock: i1, %cond: i1) -> (b: !hw.
585585
%5 = comb.mux bin %cond, %0, %2 : i1
586586
%6 = hw.array_create %5, %4 : i1
587587
hw.output %r : !hw.array<2xi1>
588-
// CHECK: %[[r2:.+]] = sv.array_index_inout %r[%true] : !hw.inout<array<2xi1>>, i1
589-
// CHECK-NEXT: %[[r1:.+]] = sv.array_index_inout %r[%false] : !hw.inout<array<2xi1>>, i1
588+
// CHECK: %[[r1:.+]] = sv.array_index_inout %r[%false] : !hw.inout<array<2xi1>>, i1
589+
// CHECK-NEXT: %[[r2:.+]] = sv.array_index_inout %r[%true] : !hw.inout<array<2xi1>>, i1
590590
// CHECK: sv.always posedge %clock {
591591
// CHECK-NEXT: sv.if %cond {
592592
// CHECK-NEXT: sv.passign %[[r1]], %1 : i1
@@ -694,10 +694,10 @@ hw.module @NestedSubaccess(%clock: i1, %en_0: i1, %en_1: i1, %en_2: i1, %addr_0:
694694
%31 = comb.mux bin %en_1, %27, %30 : !hw.array<3xi32>
695695
%32 = hw.array_create %26, %24, %22 : i32
696696
%33 = comb.mux bin %en_0, %31, %32 : !hw.array<3xi32>
697-
// CHECK: %[[IDX4:.+]] = sv.array_index_inout %r[%addr_3] : !hw.inout<array<3xi32>>, i2
698-
// CHECK: %[[IDX3:.+]] = sv.array_index_inout %r[%addr_2] : !hw.inout<array<3xi32>>, i2
699-
// CHECK: %[[IDX2:.+]] = sv.array_index_inout %r[%addr_1] : !hw.inout<array<3xi32>>, i2
700697
// CHECK: %[[IDX1:.+]] = sv.array_index_inout %r[%addr_0] : !hw.inout<array<3xi32>>, i2
698+
// CHECK: %[[IDX2:.+]] = sv.array_index_inout %r[%addr_1] : !hw.inout<array<3xi32>>, i2
699+
// CHECK: %[[IDX3:.+]] = sv.array_index_inout %r[%addr_2] : !hw.inout<array<3xi32>>, i2
700+
// CHECK: %[[IDX4:.+]] = sv.array_index_inout %r[%addr_3] : !hw.inout<array<3xi32>>, i2
701701
// CHECK: sv.always posedge %clock {
702702
// CHECK-NEXT: sv.if %en_0 {
703703
// CHECK-NEXT: sv.if %en_1 {

0 commit comments

Comments
 (0)