Optimize priority_sel with same values as cases

[vincent-mirian-google]

With a priority select with the same value for the cases, e.g.

x23: bits[27] = priority_sel(x10, cases=[x1, x1, x1, x1, x1], id=80, pos=[(0,21,29)])

remains untouched after optimization.

x23: bits[27] = priority_sel(x10, cases=[x1, x1, x1, x1, x1], id=80, pos=[(0,21,29)])

We can perform an optimization that reduces the amount of cases, and, thus the bits for the selector. The latter would enable less area in the HW design.

x11: bits[1] = or_reduce(x10)
x23: bits[27] = priority_sel(x11, cases=[x1], id=80, pos=[(0,21,29)])

Note that, although synthesis tools may perform these types/style of optimizations, from an XLS perspective, it would produce more readable Verilog and may enable quicker JIT execution.

[taktoa]

You can even optimize substrings, like:

foo: bits[32] = priority_sel(selector, cases=[a, a, a, b, b, b, b, c])

turns into

a_cases: bits[3] = bit_slice(selector, start=0, width=3)
b_cases: bits[4] = bit_slice(selector, start=3, width=4)
c_cases: bits[1] = bit_slice(selector, start=7, width=1)
if_a: bits[1] = or_reduce(a_cases)
if_b: bits[1] = or_reduce(b_cases)
if_c: bits[1] = or_reduce(c_cases)
new_selector: bits[3] = concat(if_c, if_b, if_a)
foo: bits[32] = priority_sel(new_selector, cases=[a, b, c])

(not sure if I got the ordering exactly correct, will need to be careful about that lest we introduce a tricky bug)

[vincent-mirian-google]

Yes. Good point. That is an extension of the optimization that I was mentioning.

Thanks.

[ericxu233]

Hi all. I'd like to try and implement this optimization! I'm new to XLS but have worked with LLVM before (within my company). I am actually a current intern on Intel's HLS compiler team targeting FPGAs. This seems like a really fun optimization! My company's compiler also has these kinds of optimization opportunities in the middle end but l won't get a chance to implement them since they will be optimized by our backend or Quartus synthesis.

I'd assume this optimization could be added inside the select_simplification_pass.cc right?