Many parts of our code base relies on integer simplifications that involves
div/mod. These simplifications are in particular tricky due to the different
division mode, and the dependence on knowing the sign of the operand.
Here is a list of division variants:
## Trunc div/mod
IEEE standard integer division is truncated division, directly maps to the
hardware. This is the division used by C and TVM by default. The problem of
trunc div is that we usually relies on knowing the sign of both operands. For
example, we cannot simplify ```(x * 4 + 3)/4 => x ``` if x can be negative.
## Floor div/mod
Always round down. This is the division mode adopted by python. To simplify
floordiv, we usually need to know the sign of divisor, but not necessarily the
sign of dividend ```floordiv(x * 4 + 3,4) => x ```.
## Euclidean div/mod
Always ensures that the remainder is non-negative. This is the division mode
used by Halide by default. Note that when the divisor is positive, Euclidean
and floordiv are equivalent. But floordiv will produce a negative remainder
when the divisor is negative.
## Discussion
Different division mode has its own advantage and disadvantages. While Floor
and Euclidean mode enjoys better invariance in simplification. We will have
some trouble lowering them into the trunc div/mod, especially when we do not
know the sign. In general, it is good to know the sign when lowering. However,
this will leads to some slight differences, consider the following case:
```c++
for (x = 0; x < 100; x++) {
// trunc division
a [(x * 5 + 3)/ 4] = xyz.
}
```
```(x * 5 + 3)/4``` can be simplified to (x * 5 /4) , if we setup the
simplifier, with currect context(```x in [0, 100]```). However, there can be
cases where we forget to do so in our code, i that scenario the simplifcation
cannot be done. If instead we use
```c++
for (x = 0; x < 100; x++) {
// floor division
a [floordiv(x * 5 + 3, 4)] = xyz.
}
```
```(x * 5 + 3)/4``` can be simplified to floordiv(x * 5, 4) in the analysis.
However, to get the most efficient version of the code. We need to lower the
floor division to ```x * 5 / 4``` knowing that x is non-negative. The context
information is only needed during the floor division lowering.
In summary, using trunc div during analysis requires m
ore information each time we transform it, using floor/euclidean div makes
simplification easier, but still requires us to provide context information to
most efficiently lowers to trunc div/mod.
## Proposal to be Discussed: Adding Floor Div/Mod
It might be helpful to encourage the use of floor div/mod for integer analysis
while providing an effective way to lower to trunc div when necessary. To avoid
confusion between division mode, I propose we add an explicit floordiv/floormod
node and operator to the IR.
The reason to choose floordiv/mod over Euclidean is mainly due to floor is more
common(used by python) and easier to understand. The difference in behavior
happens when the divisor is negative, and in most cases, we will know the sign
of divisor.
The original truc div/mod simplification will be kept around for a while, but
we will encourage most index calculations to use floordiv/mod, and provide
rewriter to rewrite truc div/mod into floor version when the sign of the
dividend is positive
--
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/dmlc/tvm/issues/3478
