Multiplication by constant is not optimized if output width is the same as arguments' widths
- Dominant language
- C++
- Stars
- 1.9k
- Forks
- 283
- Avg merge
- 2d 10h
- Merged PRs (30d)
- 135
Description
**Describe the bug**
Multiplication by constant is not well optimized if output width is the same as arguments' widths. It is possible to write addition with shifts in loop that is faster.
**To Reproduce**
Steps to reproduce the behavior:
1. Write following code:
`foo.x`
```rust
const CONSTANT = u32:0x1e35a7bd;
fn umul_slow(val: u32) -> u32 {
val * CONSTANT
}
fn umul_fast(val: u32) -> u32 {
for (i, result):(u32, u32) in range(u32:0, u32:32) {
if (CONSTANT >> i) as u1 {
result + (val << i)
} else {
result
}
}(u32:0)
}
proc UmulSlow {
in_r: chan in;
out_s: chan out;
config(in_r: chan in, out_s: chan out) {
(in_r, out_s)
}
init { }
next (state: ()) {
let (tok, val) = recv(join(), in_r);
send(tok, out_s, umul_slow(val));
}
}
proc UmulFast {
in_r: chan in;
out_s: chan out;
config(in_r: chan in, out_s: chan out) {
(in_r, out_s)
}
init { }
next (state: ()) {
let (tok, val) = recv(join(), in_r);
send(tok, out_s, umul_fast(val));
}
}
```
2. Build the optimized IR benchmarks and P&R.
```bazel
xls_dslx_library(
name = "foo_dslx",
srcs = ["foo.x"],
deps = [],
)
xls_dslx_verilog(
name = "umul_fast_verilog",
codegen_args = {
"module_name": "UmulFast",
"delay_model": "asap7",
"pipeline_stages": "8",
"reset": "rst",
"use_system_verilog": "false",
},
dslx_top = "UmulFast",
library = ":foo_dslx",
verilog_file = "umul_fast.v",
)
xls_benchmark_ir(
name = "umul_fast_opt_ir_benchmark",
src = ":umul_fast_verilog.opt.ir",
benchmark_ir_args = {
"pipeline_stages": "8",
"delay_model": "asap7",
},
)
verilog_library(
name = "umul_fast_lib",
srcs = [
":umul_fast.v",
],
)
synthesize_rtl(
name = "umul_fast_asap7",
standard_cells = "@org_theopenroadproject_asap7sc7p5t_28//:asap7-sc7p5t_rev28_rvt",
top_module = "UmulFast",
deps = [
":umul_fast_lib",
],
)
place_and_route(
name = "umul_fast_place_and_route",
clock_period = "750",
core_padding_microns = 2,
min_pin_distance = "0.09",
placement_density = "0.30",
stop_after_step = "global_routing",
synthesized_rtl = ":umul_fast_asap7",
target_die_utilization_percentage = "10",
)
xls_dslx_verilog(
name = "umul_slow_verilog",
codegen_args = {
"module_name": "UmulSlow",
"delay_model": "asap7",
"pipeline_stages": "8",
"reset": "rst",
"use_system_verilog": "false",
},
dslx_top = "UmulSlow",
library = ":foo_dslx",
verilog_file = "umul_slow.v",
)
xls_benchmark_ir(
name = "umul_slow_opt_ir_benchmark",
src = ":umul_slow_verilog.opt.ir",
benchmark_ir_args = {
"pipeline_stages": "8",
"delay_model": "asap7",
},
)
verilog_library(
name = "umul_slow_lib",
srcs = [
":umul_slow.v",
],
)
synthesize_rtl(
name = "umul_slow_asap7",
standard_cells = "@org_theopenroadproject_asap7sc7p5t_28//:asap7-sc7p5t_rev28_rvt",
top_module = "UmulSlow",
deps = [
":umul_slow_lib",
],
)
place_and_route(
name = "umul_slow_place_and_route",
clock_period = "750",
core_padding_microns = 2,
min_pin_distance = "0.09",
placement_density = "0.30",
stop_after_step = "global_routing",
synthesized_rtl = ":umul_slow_asap7",
target_die_utilization_percentage = "10",
)
```
4. Check results
* `umul_slow`
```none
Pipeline:
nodes: 7, delay: 964ps
[Stage 0] flops: 0 ( 0 dups, 0 constant)
nodes: 0, delay: 0ps
```
```none
-1003.386 slack (VIOLATED)
```
* `umul_fast`
```none
Pipeline:
nodes: 17, delay: 351ps
[Stage 0] flops: 115 ( 0 dups, 0 constant)
nodes: 34, delay: 348ps
[Stage 1] flops: 128 ( 1 dups, 0 constant)
nodes: 10, delay: 340ps
[Stage 2] flops: 75 ( 1 dups, 0 constant)
nodes: 6, delay: 323ps
[Stage 3] flops: 46 ( 0 dups, 0 constant)
nodes: 4, delay: 284ps
[Stage 4] flops: 0 ( 0 dups, 0 constant)
nodes: 0, delay: 0ps
```
```none
-118.949 slack (VIOLATED)
```
**Environment (this can be helpful for troubleshooting):**
- OS: Arch Linux x86_64
- Kernel version: 6.11.6-arch1-1
- XLS hash: 53db8ecc53dbd6d6e6eb1d7ebfb8ccf86b97e7e9
Contributor guide
Assessment
This issue has not been assessed yet.