[Tracking Issue] Add exact_match argument for binary search block generation in LowerSparseIter pass

[yzh119]

Pitch

Currently, we only support two modes lower_bound/upper_bound for binary search. In some cases, we need to identify whether the given coordinate matches with any of the values in an indices list, and neither lower_bound nor upper_bound is enough in this case.

Solution

We should add an exact_match argument in the binary search block generation function. When exact_match is set to true, the generated binary search block will write a INVALID (a macro represents an invalid value) to output lookup array.

We also need to propagate the invalid property: if mid[vi] is INVALID, then A[mid[vi]] will be invalid memory access.
The correct way to process such a case is to invalidate the whole expression:

# for expressions, replace it with a given padding value
INVALID if mid[vi] is INVALID else A[mid[vi]]
# for statements, replace it with NOP
if mid[vi] is INVALID:
    T.evaluate(0)
else:
    A[mid[vi]] = ...