[RFC] Lower Bound for Shape Variables

[yzhliu]

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

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

Approach

• Following the disucss, we would like to introduce AssertLowerBound, tvm.placeholder and tvm.compute inserts assert_lower_bound(i, 0) automatically.

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: #4486

@tqchen @icemelon9 @reminisce

[tqchen]

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

[tqchen]

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.

[icemelon]

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

[yzhliu]

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

[tqchen]

#4684