google / xls

XLS: Accelerated HW Synthesis
http://google.github.io/xls/
Apache License 2.0
1.2k stars 175 forks source link

Optimization opportunity avoiding zero-expansion for single bit manipulation ? #1217

Open hzeller opened 10 months ago

hzeller commented 10 months ago

Consider the following code that generates the same output -- OR-ing the last bit with a bool -- in two different ways:

/tmp/foo.x

fn foo(x: u32, b: u1) -> (u32, u32) {
  let r1 = x | (b as u32);
  let r2 = x[1:] ++ (x[0:1] | b);
  (r1, r2)
}

Only the last bit should be affected, all the other bits stay as-is from the input x.

Let's generate code from this

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

The optimization correctly realizes that the two ways are equivalent and selects one of these, the version in which we expand all the zero bits left of b, append b and OR-ing that with the other input:

module foo(
  input wire [31:0] x,
  input wire b,
  output wire [63:0] out
);
  wire [31:0] r1;
  assign r1 = x | {31'h0000_0000, b};
  assign out = {r1, r1};
endmodule

Expected Result

It would probably be more specific to only manipulate the bit in question without bothering OR-ing zeroes with all the rest, so my expectation would be that the other implementation would be chosen (and, in fact that a x | (b as u32); would be converted to this):

module foo(
  input wire [31:0] x,
  input wire b,
  output wire [63:0] out
);
  wire [31:0] r2;
  assign r2 = {x[31:1], x[0] | b};
  assign out = {r2, r2};
endmodule

Remarks

Maybe this actually does not make any difference as synthesis-tools might figure this out anyway and don't emit OR gates where not needed, so this should be first tested to see if it is worthwhile considering as an optimization.

hzeller commented 8 months ago

(edit: changed name of function from top to foo as the former is a keyword now)