fix when binary search find invalid value

[qelk123]

This is a simple fix up for the situation when binary searh find invalid indices,which contains: 1.An IfThenElse stmt after binary search,if the index is invalid,then return -1 as an invalid index value. 2.add a postprocess pass after lower sparse buffer,for those sparse data buffer,if the index value is a invalid value,then return a 0 from the sparse data buffer.

[yzh119]

Good job @qelk123 ! Thanks for your contribution, it's a behavior I should have fixed but never did, I'll leave my feedback later.

[qelk123]

Dear Zihao Ye,

Thank you for your reply.This is the first time I propose a PR,so although this modification works fine in my case,I believe there are inconsiderate parts in my code.Please give me your feedback so that I could refine it later.

Michael

[yzh119]

I had a proposal months before: https://github.com/uwsampl/SparseTIR/issues/74, the really tricky part is INVALID flag propagation:

Suppose lookup_result stores the binary search results, and we then use this value as an index to access another buffer: A[lookup_result[...]], the whole expression should be marked as invalid. However, I accept your solution for now and we can improve it later on.

[qelk123]

From my perspective，even the binary search results is not a valid index in the indices buffer,the buffer load result like A[lookup_result[...]] probably should not directly return a invalid flag,but a default value about the sparse buffer.In TACO,this default value can be spcified when declare a tensor. In an Union operation like add,when we do co-iteration on two sparse axis,as long as current index is valid in one axis,the result in related index of the output tensor should be set to the correct value，instead of invalid value. Currently,it only support 0 as the default value,but maybe we can improve it by letting users to specify the default value later on?

[yzh119]

From my perspective，even the binary search results is not a valid index in the indices buffer,the buffer load result like A[lookup_result[...]] probably should not directly return a invalid flag,but a default value about the sparse buffer.In TACO,this default value can be spcified when declare a tensor.

Yes we should return a default value, what do I mean by "invalid flag" is a indicator that whole expression containing it should be invalidated and return its default value.

Back to my example A[lookup_result[...]], if we return the default value 0 for an unsuccessful lookup_result, then we will get A[0], but what we really need is default value for buffer A, and such information need to be propagated in some way.

We can leave it for another PR.

[qelk123]

From my perspective，even the binary search results is not a valid index in the indices buffer,the buffer load result like A[lookup_result[...]] probably should not directly return a invalid flag,but a default value about the sparse buffer.In TACO,this default value can be spcified when declare a tensor.

Yes we should return a default value, what do I mean by "invalid flag" is a indicator that whole expression containing it should be invalidated and return its default value.

Back to my example A[lookup_result[...]], if we return the default value 0 for an unsuccessful lookup_result, then we will get A[0], but what we really need is default value for buffer A, and such information need to be propagated in some way.

We can leave it for another PR.

Actually, current solution is let lookup_result[...] return -1 as an invalid index.Do you mean return "-1" is not a proper way to represent invalid index?

[yzh119]

From my perspective，even the binary search results is not a valid index in the indices buffer,the buffer load result like A[lookup_result[...]] probably should not directly return a invalid flag,but a default value about the sparse buffer.In TACO,this default value can be spcified when declare a tensor.

Yes we should return a default value, what do I mean by "invalid flag" is a indicator that whole expression containing it should be invalidated and return its default value. Back to my example A[lookup_result[...]], if we return the default value 0 for an unsuccessful lookup_result, then we will get A[0], but what we really need is default value for buffer A, and such information need to be propagated in some way. We can leave it for another PR.

Actually, current solution is let lookup_result[...] return -1 as an invalid index.Do you mean return "-1" is not a proper way to represent invalid index?

We support non-affine indices, and the buffer access indices could be value loaded from another buffer access (e.g. A[B[C[...]]]), my example shows that we need to return default value for the entire expression A[B[C[...]]] if binary search is invalid, not only C[...] or B[C[...]].

[qelk123]

From my perspective，even the binary search results is not a valid index in the indices buffer,the buffer load result like A[lookup_result[...]] probably should not directly return a invalid flag,but a default value about the sparse buffer.In TACO,this default value can be spcified when declare a tensor.

Yes we should return a default value, what do I mean by "invalid flag" is a indicator that whole expression containing it should be invalidated and return its default value. Back to my example A[lookup_result[...]], if we return the default value 0 for an unsuccessful lookup_result, then we will get A[0], but what we really need is default value for buffer A, and such information need to be propagated in some way. We can leave it for another PR.

Actually, current solution is let lookup_result[...] return -1 as an invalid index.Do you mean return "-1" is not a proper way to represent invalid index?

We support non-affine indices, and the buffer access indices could be value loaded from another buffer access (e.g. A[B[C[...]]]), my example shows that we need to return default value for the entire expression A[B[C[...]]] if binary search is invalid, not only C[...] or B[C[...]].

I thought when facing the situation like A[B[C[...]]] if the binary search is failed in C,then C[...] will return a default value,and we can use this value to index B,the expression is still available?

[yzh119]

From my perspective，even the binary search results is not a valid index in the indices buffer,the buffer load result like A[lookup_result[...]] probably should not directly return a invalid flag,but a default value about the sparse buffer.In TACO,this default value can be spcified when declare a tensor.

Yes we should return a default value, what do I mean by "invalid flag" is a indicator that whole expression containing it should be invalidated and return its default value. Back to my example A[lookup_result[...]], if we return the default value 0 for an unsuccessful lookup_result, then we will get A[0], but what we really need is default value for buffer A, and such information need to be propagated in some way. We can leave it for another PR.

Actually, current solution is let lookup_result[...] return -1 as an invalid index.Do you mean return "-1" is not a proper way to represent invalid index?

We support non-affine indices, and the buffer access indices could be value loaded from another buffer access (e.g. A[B[C[...]]]), my example shows that we need to return default value for the entire expression A[B[C[...]]] if binary search is invalid, not only C[...] or B[C[...]].

I thought when facing the situation like A[B[C[...]]] if the binary search is failed in C,then C[...] will return a default value,and we can use this value to index B,the expression is still available?

I believe you're correct. Let's stick with this solution until rare cases.

[yzh119]

Hi @qelk123 do you need any assistance on rebase? It seems the codebase disappears and the PR is closed.