[Synth] Eagerly CSE in LowerVariadic #9712
Description
module Test(
input [5:0] in,
output out1, out2
);
assign out1 = in[0] & in[1] & in[2] & in[3] & in[4];
assign out2 = in[1] & in[2] & in[3] & in[4];
endmoduleCurrently it's lowered to 7 aig with depth 3.
./build/bin/circt-verilog test.sv | ./build/bin/circt-synth -format=mlir -output-longest-path=-
# Longest Path Analysis result for "Test"
Found 9 paths
Found 2 unique end points
Maximum path delay: 3
## Showing Levels
Level = 2 . Count = 1 . 50.00 %
Level = 3 . Count = 1 . 100.00 %
## Top 0 (out of 2) end points
module {
hw.module @Test(in %in : i6, out out1 : i1, out out2 : i1) {
%0 = comb.extract %in from 0 : (i6) -> i1
%1 = comb.extract %in from 1 : (i6) -> i1
%2 = comb.extract %in from 2 : (i6) -> i1
%3 = comb.extract %in from 3 : (i6) -> i1
%4 = comb.extract %in from 4 : (i6) -> i1
%5 = synth.aig.and_inv %2, %3 : i1
%6 = synth.aig.and_inv %0, %1 : i1
%7 = synth.aig.and_inv %5, %4 : i1
%8 = synth.aig.and_inv %6, %7 : i1
%9 = synth.aig.and_inv %2, %1 : i1
%10 = synth.aig.and_inv %3, %4 : i1
%11 = synth.aig.and_inv %9, %10 : i1
hw.output %8, %11 : i1, i1
}
}OTOH following is lowered to 4 aig with depth 3.
module Test(
input [5:0] in,
output out1, out2
);
assign out1 = in[0] & in[1] & in[2] & in[3] & in[4];
assign out2 = in[0] & in[1] & in[2] & in[3];
endmodule./build/bin/circt-verilog test.sv | ./build/bin/circt-synth -format=mlir -output-longest-path=-
# Longest Path Analysis result for "Test"
Found 9 paths
Found 2 unique end points
Maximum path delay: 3
## Showing Levels
Level = 2 . Count = 1 . 50.00 %
Level = 3 . Count = 1 . 100.00 %
## Top 0 (out of 2) end points
module {
hw.module @Test(in %in : i6, out out1 : i1, out out2 : i1) {
%0 = comb.extract %in from 0 : (i6) -> i1
%1 = comb.extract %in from 1 : (i6) -> i1
%2 = comb.extract %in from 2 : (i6) -> i1
%3 = comb.extract %in from 3 : (i6) -> i1
%4 = synth.aig.and_inv %0, %1 : i1
%5 = synth.aig.and_inv %2, %3 : i1
%6 = synth.aig.and_inv %4, %5 : i1
%7 = comb.extract %in from 4 : (i6) -> i1
%8 = synth.aig.and_inv %6, %7 : i1
hw.output %8, %6 : i1, i1
}
}We want to do perform similar lowering for the first example as well since the logic depth doesn't change.
For the first example, the IR before LowerVariadic is like this:
hw.module @Test(in %in : i6, out out1 : i1, out out2 : i1) {
%0 = comb.extract %in from 0 : (i6) -> i1
%1 = comb.extract %in from 1 : (i6) -> i1
%2 = comb.extract %in from 2 : (i6) -> i1
%3 = comb.extract %in from 3 : (i6) -> i1
%4 = comb.extract %in from 4 : (i6) -> i1
%5 = synth.aig.and_inv %0, %1, %2, %3, %4 : i1
%6 = synth.aig.and_inv %1, %2, %3, %4 : i1
hw.output %5, %6 : i1, i1
}Ideally we first want to lower %6, and use the result of %6 in lowering of %5. Is this fairly challenging to know upfront, so heuristic to
re-use existing operations would be good enough.