Adding integer ceil and floor in Std Dialect

Right now, there is an implementation of integer ceil and floor “hidden” in AffineToStandard.cpp, which is used to lower the affine expressions (which has the floordiv and ceildiv).

This is not avail for regular computations (only for affine lowering), and only support positive denominator. In ONNX, we have need for regular computations with negative nominator and/or denominator

Would there be objections to add regular floordiv and ceildiv in the std dialect? I have worked an algorithm that works for positive/negative nominator/denominator, and uses only “integer divide” and “select” operations.

floorDiv(n, m) {
  x = (n<0) ? -1 : 1
  return (n*m<0) ? - ((-n+x) / m) -1 : n / m

ceilDiv(n, m) {
  x = (n > 0) ? -1 : 1
  return (n*m>0) ? ((n+x) / m) + 1 : - (-n / m)

where the “/” is the normal c++ divide integer operation.

1 Like

I support this idea. Currently, one has to resort to affine maps to express these operations in a way that is easy to optimize and I think it would be nice to break this requirement.

1 Like

I never implemented the negative-denominator lowering because affine maps don’t allow such cases, but we did think about that with @albertcohen. I think it is reasonable to have first-class operations for floordiv and ceildiv, as well as for Euclidean division, somewhere. If nothing else, this will at least simplify the lowering. One minor concern is not paying the cost of additional operations that support negative-denominator case when it is not necessary, such as lowering of affine map applications. I suppose it should be possible with canonicalization patterns and some form of assume operation.

Then there is the recurrent topic of having too much ops in Standard…

@ftynse I will leave the current handling of the floor/ceil in affine maps. The code is already there, and since there is one less “select,” it is more efficient. It make sense to keep it.

Unfortunately, some ONNX ops have ceil/floor with parameters (like steps) that can be negative. Thus my interest in adding support for this. I can certainly add it in a ONNX specific dialect, but it feels right to put it in standard as others will probably need it at some times too.

@ftynse

changed the test code so that we have the first select on the denominator being positive/negative. That way, if we have properties on the denominator being a positive number integer only, the first selects could be eliminated by having their test being a compile time constant “true” or “false”.

Please review implementation as you see fit here.

https://reviews.llvm.org/D89726

Thanks for all the useful feedback

1 Like

Hi @AlexEichenberger. As @ftynse mentioned we did look into making this an op. Motivated by having a portable path for lowering floor/ceildiv, avoiding common lowering errors (frequent and often not properly tested from my experience), abstracting away target- and language-specific variations, and closing this odd asymmetry between an essential operation in affine expressions that is not available as an op, and also benefiting from high-performance/sign-specialized versions.

As long as the more efficient positive-denominator version remains available, I don’t see a problem generalizing the op. Maybe using an attribute to specialize the op to the positive denominator case?