google / google/xls

Optimization opportunity: shift width with as result of +/- operation with constant could eliminate the `add` operation.

Open
#1,274 0 comments 0 reactions 0 assignees View on GitHub
optimizer
Dominant language
C++
Stars
1.9k
Forks
283
Avg merge
2d 10h
Merged PRs (30d)
135

Description

### Input

Let's consider this `/tmp/foo.x`, shifting a value with a parameter to which we add a constant:

```rust
fn foo(x: u32, y: u32) -> u32 {
x << (y + u32:1)
}
```

### Code generation
```python
IR_CONVERTER=bazel-bin/xls/dslx/ir_convert/ir_converter_main
IR_OPT=bazel-bin/xls/tools/opt_main
CODEGEN=bazel-bin/xls/tools/codegen_main
${IR_CONVERTER} /tmp/foo.x | ${IR_OPT} --top=__foo__foo - | ${CODEGEN} --module_name=foo --generator=combinational -
```

### Result
```verilog
module foo(
input wire [31:0] x,
input wire [31:0] y,
output wire [31:0] out
);
wire [31:0] add_9;
assign add_9 = y + 32'h0000_0001;
assign out = add_9 >= 32'h0000_0020 ? 32'h0000_0000 : x << add_9;
endmodule
```

This does as the original code input requests: do an add operation, then shift with the result.

However, in this case, the constant can be pulled out of the add operation, which would eliminate the `add` operation

```rust
let x = x << y;
x << 1
```

Which would result in something like the following, no add operation needed, just bit concatenation:

```verilog
module foo(
input wire [31:0] x,
input wire [31:0] y,
output wire [31:0] out
);
assign out = {y >= 32'h0000_001f ? 31'h0000_0000 : x[30:0] << y, 1'h0};
endmodule
```

... also with subtract operation
```rust
fn foo(x: u32, y: u32) -> u32 {
let x = x << y;
x >> 1
}
```

Here, XLS generates the following:
```verilog
module foo(
input wire [31:0] x,
input wire [31:0] y,
output wire [31:0] out
);
wire [31:0] x__1;
assign x__1 = y >= 32'h0000_0020 ? 32'h0000_0000 : x << y;
assign out = {1'h0, x__1[31:1]};
endmodule
```
(Arguably, the bit slice could probably before here, but that is another possible optimization)

### Diminishing returns if add-result needed otherwise
The optimization might not be fruitful if the result of the addition is also needed in some other dependent datapath, so could not necessarily be eliminated. However, it is probably also not actively harmful to do this operation in this case.

```rust
fn foo(x: u32, y: u32) -> (u32, u32) {
let shift = y + u32:1;
(y << shift, shift)
}
```

#### Notes
The whole comparison with max shift possible and then mux'ing in zero if it is too much of a shift -- is this really needed ?
If we limit the bits of the operation that returns the bit-width to the `clog2()` of the shiftee, we might not need that ?
In general: could we reduce the result of the shift-width already earlier ? (what if y is `uN[256]` ... but we only ever need maximum `u5` to shift all the way, but this will create some, uhm, large number compares and muxing:

```verilog
module foo(
input wire [31:0] x,
input wire [255:0] y,
output wire [31:0] out
);
wire [255:0] add_9;
assign add_9 = y + 256'h0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0001;
assign out = add_9 >= 256'h0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0020 ? 32'h0000_0000 : x << add_9;
endmodule
```
(maybe I should file this as a separate issue)

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.