Integer constant folding for division and mod

Development
#1

@sgrechanik-h @tqchen @yzhliu
My understanding is that TVM uses truncated division/mod, unlike Halide that uses Euclidean division/mod. Nevertheless, TVM uses div_imp (imlementation below) to do constant folding for division. Seems like this implementation is coming from Halide source code. This seems like a bug to me unless I’m missing something. If I get confirmation on this bug, I’ll open an issue and send a PR in Github.

template<typename T>
inline T div_imp(T a, T b) {
    Type t = type_of<T>();
    if (t.is_int()) {
        int64_t q = a / b;
        int64_t r = a - q * b;
        int64_t bs = b >> (t.bits() - 1);
        int64_t rs = r >> (t.bits() - 1);
        return (T) (q - (rs & bs) + (rs & ~bs));
    } else {
        return a / b;
    }
}
#2

I think div_imp should simply return a/b

#3

I agree, let us fix it

#4

I tried the fix but a few TVM testcases started to fail. I think those testcases were assuming that division was Euclidean and that’s why they were passing before. I need more time to investigate and fix them.

#5

Given that we are moving toward the new simplification infra, perhaps we can leave some of that as they are and push forward to adopt the new infra https://github.com/dmlc/tvm/issues/2588

#6

The investigation I’m doing will affect both the old and new infra. So far I have found out that we currently have simplification rules that are not correct. For example, we simplify (x4 + y) / 2 to x2 + y/2 which is not correct in general but is true if we prove that x*4+y and y are both non-negative (sufficient conditions).
For now I’m trying to identify such (infra-independent) problems. The fixes then can be applied independently to new and old infras.

#7

I believe that the new infra will not perform such simplification. If they did, then it is a BUG that we need to fix and you are more than welcomed to open an issue or help to fix that.

#8

You’re right. I just checked those specific rules in the new infra and they were fixed. I had mistakenly assumed that the rules of the new infra were copied from the old infra without further changes.

On an orthogonal but related topic: I believe it’s still important to fix bugs in old releases for two reasons: 1) it’s not known when the new infra (or in general new features) will be enabled. Between now and then there is a known bug and I’d rather see it fixed 2) There could be (possibly heavily-customized) forks of TVM off of release 0.5 (or any old release, for that matter) that may not be able to upgrade to 0.6 (or later) as soon as 0.6 is released for stability purposes. These forks could be actually in use by customers’ who are reluctant to make drastic changes. For those types of TVM forks, I believe there is a need to fix important bugs in maintenance releases (e.g., 0.5.1) What do you think?

If we decide to have maintenance releases, we need to come up with a process on what kind of bugs we fix in release bugs, how often, etc.

#9

Is there a way to enable the new infra (and disable the old one) to be able to evaluate it, for example, for unit testcases, bugs we encounter in customized forks of TVM, etc.?

#10

One thing I am thinking of is to just drop in the implementation of Simplify and CanonicalSimplify and run all the regression testcases