Page MenuHomePhabricator

MLIR: add ceil/floor divide in Standard Dialect
ClosedPublic

Authored by AlexEichenberger on Oct 19 2020, 1:18 PM.

Details

Summary

Added support for ceil/floor divide in the standard dialect. It works with signed integers with pos/neg nominator and/or denominator. The formula used as as follows:

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

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

and was extensively tested before implementation. Note that there are two selects, and the first ones test whether the denominator is postive/negative. This test would go away in affine ceil/floor since the denominator is known to be negative. Since we do not have (I believe) the ability to indicate a non-negative signed integer at this time, the lowering of ceil/floor for affine functions are left in place, as it uses the more efficient technique with only 1 select per operation.

This patch added the constant folding, the canonicalization for div by 1, and lowering to LLVM. There are literal tests for each of these phases, and I added a more exhaustive integration test that verifies the correct results of divide by + or - 10 for integers from -20 to +20.

Diff Detail

Event Timeline

AlexEichenberger requested review of this revision.Oct 19 2020, 1:18 PM
ftynse added inline comments.Oct 21 2020, 9:11 AM
mlir/include/mlir/Dialect/StandardOps/IR/Ops.td
2849

This does not match the actual opcode

mlir/lib/Conversion/StandardToLLVM/StandardToLLVM.cpp
3290 ↗(On Diff #299136)

Please use auto when it improves readability, e.g. when the type is obvious from the RHS because of the cast/template or it would be too long to spell out.

aartbik added inline comments.Oct 21 2020, 11:00 AM
mlir/include/mlir/Dialect/StandardOps/IR/Ops.td
2839

Isn't the "leading bit as sign" a bit too much detail in this comment.
Doesn't it suffice to say that it treats the inputs as signed entities?

mlir/lib/Dialect/StandardOps/IR/Ops.cpp
3065

Just curious, did you make these (and below) column width changes on purpose
or did your editor clean these up automatically? :-)

silvas added a subscriber: silvas.Oct 21 2020, 6:07 PM
silvas added inline comments.
mlir/lib/Conversion/StandardToLLVM/StandardToLLVM.cpp
3279 ↗(On Diff #299136)

Can we instead have patterns that lower this to other std ops? That seems more reusable. Is there anything LLVM-specific here? Much as we have the lib/Dialect/Shape/Transforms/ShapeToShapeLowering.cpp that breaks down shape.num_elements into more primitive shape dialect ops, I think we can do the same here.

you can easily populate such patterns into the std-to-llvm conversion using a function analogous to populateShapeRewritePatterns

mlir/lib/Conversion/StandardToLLVM/StandardToLLVM.cpp
3279 ↗(On Diff #299136)

@silvas That makes a lot of sense. I wanted to go this direction but was not sure if introducing a new pass would be too intrusive. Technically, since I translate std -> std in order to implement the ceil and floor, that is technically the right approach. Will transform the code to go that route, using the populateShapeRewritePatterns as a model.

Followed the suggestion to include the handling of ceil and floor (generic version supporting arbitrary pos/neg nominator/denominator) as a separate std to std pass. I also removed "auto" where easily substituted by the actual type, fixed the description of the ops as requested, and fixed a couple of other suggestions.

mlir/include/mlir/Dialect/StandardOps/IR/Ops.td
2839

I adjusted the prior definition of div; it is now simplified a bit, agreed it was a bit fussy.

2849

Thanks, fixed that

mlir/lib/Conversion/StandardToLLVM/StandardToLLVM.cpp
3290 ↗(On Diff #299136)

replaced by the actual types in the new version.

mlir/lib/Dialect/StandardOps/IR/Ops.cpp
3065

Using VS Code, hope its ok. If not, I can revert the changes manually.

silvas added inline comments.Oct 28 2020, 1:00 PM
mlir/lib/Dialect/StandardOps/Transforms/StdToStdLowering.cpp
1 ↗(On Diff #301379)

comment out of date

9 ↗(On Diff #301379)

comment out of date

15 ↗(On Diff #301379)

can you trim down this list of includes?

37 ↗(On Diff #301379)

nit: remove blank line

80 ↗(On Diff #301379)

nit: remove blank line.

136 ↗(On Diff #301379)

mlir:: shouldn't be needed.

Thanks for factoring out the std-to-std! That part looks good! (consider my drive-by comment addressed :) )

@silvas Will push an update with fixes for your comment. One thing I do not know and input would be appreciated. Should this pass be added in the "mlir driver"? If so, can you recommend where the pass should be added. Thanks

@silvas Will push an update with fixes for your comment. One thing I do not know and input would be appreciated. Should this pass be added in the "mlir driver"? If so, can you recommend where the pass should be added. Thanks

There is currently no "mlir driver" (in the sense of "clang driver" that sets up all the needed passes). I'm in the process of trying to add a concept of a "reference backend" to MLIR upstream which would be a great place to include this pass.

removed redundant includes and mlir:: qualifier, corrected the comments copied over (sorry)

ftynse requested changes to this revision.Oct 29 2020, 7:51 AM
ftynse added inline comments.
mlir/include/mlir/Dialect/StandardOps/Transforms/Passes.td
25

I'd use a more descriptive name. What about std-expand-divs? (both "std-to-std" and "lowering" sound out of place in the general pass list)

mlir/lib/Dialect/StandardOps/IR/Ops.cpp
3512

This actually fits into 80 cols... Your editor seems to be using 78. Let's please avoid spurious stylistic changes for places that don't contradict our current style guide.

mlir/lib/Dialect/StandardOps/Transforms/StdToStdLowering.cpp
55 ↗(On Diff #301419)

This can overflow on relatively small numbers... Let's just use logic operations instead:
%nneg = cmpi "lt" %n, 0
%mneg = cmpi "lt" %m, 0
%resneg = xor %nneg, %mneg

mlir/test/Transforms/constant-fold.mlir
438

Please don't check irrelevant pieces of the IR. Here, -NEXT does not look necessary, neither does the check for values being returned from the function (return is only necessary to prevent DCE).

This revision now requires changes to proceed.Oct 29 2020, 7:51 AM
AlexEichenberger updated this revision to Diff 301809.

responded to comments, including the removal of the n*m>0 test that may overflow by a logical equivalent using n and m compares only.

mlir/include/mlir/Dialect/StandardOps/Transforms/Passes.td
25

@ftynse Context: my original implementation had this inside the std-to-llvm lowering, and then @silvas recommended to do a separate pass taking Shape to Shape as an example. The generic name anticipates that there may be additional ops that would use a std to std lowering scheme.

Given that background, if you still want the more specific name, I have no problems doing so.

mlir/lib/Dialect/StandardOps/IR/Ops.cpp
3065

Reverted all changes to comments

3512

Thanks for the explanation. Did revert all these spurious changes.

mlir/lib/Dialect/StandardOps/Transforms/StdToStdLowering.cpp
55 ↗(On Diff #301419)

Implemented your changes, had to be a bit careful to properly handle the cases where n is zero. Tested the changes systematically to make sure the code is equivalent.

Thanks for this good suggestion.

9 ↗(On Diff #301379)

updated both out of date comments

15 ↗(On Diff #301379)

Good catch, did prune the list.

136 ↗(On Diff #301379)

thanks, removed

mlir/test/Transforms/constant-fold.mlir
438

removed the check on the return, here and other places I had the same pattern.

ftynse accepted this revision.Tue, Nov 3, 1:56 AM
ftynse added inline comments.
mlir/include/mlir/Dialect/StandardOps/Transforms/Passes.td
25

Shape-to-shape is more of an outlier than a rule. I didn't catch its name when it was introduced, I would have pushed back :) We usually reserve X-to-Y pass names for conversions between dialect X and dialect Y. The main goal of a pass is thus sufficiently described by the pass name. We have passes that consume and produce the same dialect and use descriptive names for those. Imagine if we had -scf-to-scf or -affine-to-affine that does all the transformations respective passes currently do (tiling, fusion, permutation, unrolling) based on some additional options? We also managed to survive without "standard-to-standard" transformations for over 2 years, so I don't think provisioning a name for some future transformations that fall into that category is necessary. Even if we did, it is not guaranteed that somebody will always need all of the transformations that would be eventually included in such a pass.

Bottomline, please use a more descriptive name :)

This revision is now accepted and ready to land.Tue, Nov 3, 1:56 AM
mlir/include/mlir/Dialect/StandardOps/Transforms/Passes.td
25

That make perfect sense. Will change ASAP.

implemented the requested changes, including the pass name change from -std-to-std-lowering to -std-expand-divs.

renamed pattern rewriter function to match the StdExpandDivs theme.