This is an archive of the discontinued LLVM Phabricator instance.

[MLIR] Simplify semi-affine expressions
ClosedPublic

Authored by yash on Jul 30 2020, 1:47 AM.

Details

Summary

Simplify semi-affine expression for the operations like ceildiv, floordiv and modulo by any given symbol by checking divisibilty by that symbol.

Some properties used in simplification are:

  1. Commutative property of the floordiv and ceildiv:

((expr1 floordiv expr2) floordiv expr3 ) = ((expr1 floordiv expr3) floordiv expr2)
((expr1 ceildiv expr2) ceildiv expr3 ) = ((expr1 ceildiv expr3) ceildiv expr2)
While simplification if operations are different no simplification is possible as there is no property that simplify expressions like these: ((expr1 ceildiv expr2) floordiv expr3) or ((expr1 floordiv expr2) ceildiv expr3).

  1. If both expr1 and expr2 are divisible by the expr3 then:

(expr1 % expr2) / expr3 = ((expr1 / expr3) % (expr2 / expr3)) "where / is divide symbol".

  1. If expr1 is divisible by expr2 then expr1 % expr2 = 0.

Signed-off-by: Yash Jain <yash.jain@polymagelabs.com>

Diff Detail

Event Timeline

yash created this revision.Jul 30 2020, 1:47 AM
Herald added a project: Restricted Project. · View Herald Transcript
yash requested review of this revision.Jul 30 2020, 1:47 AM
yash updated this revision to Diff 281838.Jul 30 2020, 1:55 AM

Minor update.

yash edited the summary of this revision. (Show Details)Jul 30 2020, 1:58 AM
yash added a reviewer: ftynse.
bondhugula requested changes to this revision.Jul 30 2020, 2:10 AM
bondhugula added inline comments.
mlir/lib/IR/AffineExpr.cpp
255–256

This is a bit fuzzy. If divOpKind can be mod as well, then we need a different name - may be divModOpKind. If it can be only floordiv, ceildiv, and mod, you need to also assert the precondition as the first thing.

258

'0' is divisible by all symbols (since all divisor symbols are expected to be positive and thus non-zero). So, this should be returning true for zero constant?

This revision now requires changes to proceed.Jul 30 2020, 2:10 AM
bondhugula added inline comments.Jul 30 2020, 2:13 AM
mlir/lib/IR/AffineExpr.cpp
273–275

This looks incorrect - shouldn't you be passing divOpKind as the third argument?

bondhugula added inline comments.Jul 30 2020, 2:20 AM
mlir/lib/IR/AffineExpr.cpp
305

Nit: nullptr -> null expression

386–390

The third argument for isDivisibleSymbol is always floor, ceil, or mod. Should assert at the method?

bondhugula added inline comments.Jul 30 2020, 3:20 AM
mlir/lib/IR/AffineExpr.cpp
249

Nit: signifies here ... -> specifies what kind of division or mod operation associates the two.

mlir/test/Dialect/Affine/simplify-affine-structures.mlir
287

Nit: with -> in

288

No need of $ prefix for map?

323

Terminate with a ful stop. simplify -> simplifies

yash updated this revision to Diff 281903.Jul 30 2020, 5:56 AM
yash marked 8 inline comments as done.

divOpKind changed to opKind.
Constant 0 can be divided handled.

bondhugula requested changes to this revision.Jul 30 2020, 7:16 AM
bondhugula added inline comments.
mlir/lib/IR/AffineExpr.cpp
264–266

Doesn't look there is a test case to cover this - please add one.

326

Nit: prefer to make it explicit: ... != 0

This revision now requires changes to proceed.Jul 30 2020, 7:16 AM

But no property for the expressions with different operations ((expr1 ceildiv expr2) floordiv expr3)

Please rephrase this.

yash edited the summary of this revision. (Show Details)Jul 30 2020, 8:28 PM
yash updated this revision to Diff 282117.Jul 30 2020, 8:33 PM
yash marked 2 inline comments as done.

Added test case for division of constant 0 by symbol.

Added test case for division of constant 0 by symbol.

I can't find the test case. Did you update the patch?

bondhugula added inline comments.Jul 31 2020, 2:07 AM
mlir/lib/IR/AffineExpr.cpp
1045–1047

-> // Simplify semi-affine expressions separately.

mlir/test/Dialect/Affine/simplify-affine-structures.mlir
330

Drop extra line at end of file. Please use git diff --check HEAD~ to check for whitespace errors.

yash updated this revision to Diff 282233.Jul 31 2020, 8:46 AM
yash marked 2 inline comments as done.

Removed the extra line and edited some comments.

bondhugula accepted this revision.Aug 1 2020, 12:05 AM

Thanks for revising. Looks good to me - minor comments.

mlir/lib/IR/AffineExpr.cpp
249–250

Sentence is broken.

252

expr -> `expr`

258

Nit: THe -> The

315

You can drop the "useful for ...". This is just implementing the said functionality.

316–317

Nit: Rephrase A null expression is returned ...

This revision is now accepted and ready to land.Aug 1 2020, 12:05 AM
yash updated this revision to Diff 282382.Aug 1 2020, 2:18 AM
yash marked 6 inline comments as done.

Minor update in comments.

bondhugula accepted this revision.Aug 4 2020, 7:51 AM
bondhugula edited the summary of this revision. (Show Details)
This revision was automatically updated to reflect the committed changes.