How can we make it easy to "one-hot-select" from an array?

[ericastor]

To circle back to the original customer pain, let's say I have an array of booleans (to select a value), and a corresponding array of non-bits (i.e. more complex types) values. Can we make it easy to use OHS and priority_sel to select a value?

Originally posted by @dank-openai in #209

Summarizing the discussion: suppose we have a list of bools (maybe as a tuple, an array, or a uN[K]) and an array of values with the same width. We want to select the first entry in the array for which the corresponding bool is true.

1. How can we do this most cleanly & optimally in DSLX?

2. What if we know the set of bools is one-hot? Can we somehow make sure XLS emits optimal codegen for this, and skips priority resolution?

[ericastor]

Currently, if you have your selectors in a 9-wide tuple called selector_bools, and your desired values in a 9-wide array, I think the best (EDIT: revised; see the next comment for why) one option you have is to write:

let selected_value = match (selector_bools) {
  (true, _, _, _, _, _, _, _, _) -> value[0],
  (_, true, _, _, _, _, _, _, _) -> value[1],
  // ...
  (_, _, _, _, _, _, _, _, true) -> value[8],
};

If you'd like to recommend a syntactic sugar for match expressions of this form (not sure what to call it), that could be great! I'd probably suggest filing that as a new enhancement request.

You almost certainly don't want to use an explicit one_hot_sel; as mentioned in our documentation, "This is included largely for testing purposes and for bespoke 'intrinsic-style programming' use cases." If you find that your QoR is subpar when you do this, please file a report; it's always great to have more examples we can use to improve our analyses & codegen!

---

NOTE: If your selectors are instead packed into a selector: uN[9], you'd need to unpack them first:

let selector_bools = (selector[0+:u1], selector[1+:u1], ..., selector[8+:u1]);

Similarly, if they're packed into an array as selector: bool[9]:

let selector_bools = (selector[0], selector[1], ..., selector[8]);

[ericastor]

Actually, I think we have one other option that's very clean if you can assume the selecting bools are one-hot. Assuming your selector bools are packed into a selector: uN[9], and your values are in a 9-wide array, you could instead write:

let selected_value = value[encode(selector)];

This uses our standard-library function (https://google.github.io/xls/dslx_std/#encode) that translates a one-hot input into the number n for which the input's hot bit is in position n. If the input isn't one-hot, the result is the bitwise-OR of the hot indices... but that's probably okay for your use case? It's also quite efficient, last I checked.

@dank-openai, what do you think of this option?

---

NOTE: If your selectors are packed into an array, you can probably use an array conversion to get them into a uN[9] (possibly with a reversal tacked on, depending on your case ordering):

let selector = selector_array as uN[9];

If they're instead packed into a tuple, you might need to concat them manually, but I'm not sure:

let selector = selector_tuple.1 ++ selector_tuple.2 ++ ... ++ selector_tuple.9;

or

let selector = selector_tuple.9 ++ selector_tuple.8 ++ ... ++ selector_tuple.1;

depending on the case ordering.

[proppy]

Can we make it easy to use OHS and priority_sel to select a value?

Is that similar to #1729 ?

One workaround that I've been using (as discussed in #1913 and #1909) is:

match true {
   condition0 => result0,
   condition1 => result1,
   condition2 => result2,
   // ...
   conditionN => resultN,
}

which test condition0 -> conditionN in order and return the first resultX for which the corresponding condition is true.