[apache/incubator-tvm] [RFC] Lower Bound for Shape Variables (#4487)

[Yizhi Liu <no...@github.com>]

## Motivation
As we have replaced `truncdiv`/`truncmod` by `floordiv`/`floormod` in most places, there's a large demand for simplification to know the sign of the expression. For example, knowing the tensor shape bound can help reduce the if/else conditions significantly.

Here's an example of generated cuda code for the tvm program posted in this [troubleshooting](https://discuss.tvm.ai/t/significant-increase-in-the-amount-of-cuda-code-gen-after-migrating-indexdiv-mod-to-floordiv-mod/)

* without knowing `tindex >= 0`:  https://gist.github.com/yzhliu/f1aa7c1f25cfd8788cda75a350c4b274
* knowing that `tindex >= 0`: https://gist.github.com/yzhliu/217e997157efcfc2a34e5c27b357fcaa

## Approach

* Following [the disucss](https://discuss.tvm.ai/t/discuss-embed-more-bound-information-into-var-or-expr/), we would like to introduce `AssertLowerBound`, `tvm.placeholder` and `tvm.compute` inserts `assert_lower_bound(i, 0)` automatically.

```cpp
class AssertLowerBound : public ExprNode {
 public:
  Expr value;
  Expr bound;

  void VisitAttrs(AttrVisitor* v) {
    v->Visit("value", &value);
    v->Visit("bound", &bound);
  }

  TVM_DLL static Expr make(Expr value, Expr bound);

  static constexpr const char* _type_key = "AssertLowerBound";
  TVM_DECLARE_NODE_TYPE_INFO(AssertLowerBound, ExprNode);
};
```

* `ConstIntBoundAnalyzer` will recognize `AssertLowerBound` and generate the Bound accordingly for the variables.
* Modify `CodeGenC` and `CodeGenLLVM` to support `AssertLowerBound` - simply replace with its value. (Should we insert extra assertion instructions?)

Here is a draft of the implement: https://github.com/apache/incubator-tvm/pull/4486

@tqchen @icemelon9 @reminisce 



-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/apache/incubator-tvm/issues/4487

Re: [apache/incubator-tvm] [RFC] Lower Bound for Shape Variables (#4487)

[Tianqi Chen <no...@github.com>]

I am not sure if we want to introduce this specialized assertion as a special Expr. It might be a better idea to have it as an intrinsic



-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/apache/incubator-tvm/issues/4487#issuecomment-563508946

Re: [apache/incubator-tvm] [RFC] Lower Bound for Shape Variables (#4487)

[Tianqi Chen <no...@github.com>]

Closed #4487.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/apache/incubator-tvm/issues/4487#event-3020120551

Re: [apache/incubator-tvm] [RFC] Lower Bound for Shape Variables (#4487)

[Tianqi Chen <no...@github.com>]

I am also thinking about pushing a parallel change to allow IterVar as a sub-class of Var.  Note that it won't solve the problem of shape var bounds, but might also help some of the situations.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/apache/incubator-tvm/issues/4487#issuecomment-563509238

Re: [apache/incubator-tvm] [RFC] Lower Bound for Shape Variables (#4487)

[Tianqi Chen <no...@github.com>]

https://github.com/apache/incubator-tvm/pull/4684

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/apache/incubator-tvm/issues/4487#issuecomment-583770764

Re: [apache/incubator-tvm] [RFC] Lower Bound for Shape Variables (#4487)

[Haichen Shen <no...@github.com>]

Yes, I agree we should have a general `AssertExpr` instead of `AssertLowerBound`, and put the asserted condition in the expr..

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/apache/incubator-tvm/issues/4487#issuecomment-563510011

Re: [apache/incubator-tvm] [RFC] Lower Bound for Shape Variables (#4487)

[Yizhi Liu <no...@github.com>]

Thanks @tqchen @icemelon9 I'll change to use intrinsic and make it more general.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/apache/incubator-tvm/issues/4487#issuecomment-564298170