Page MenuHomePhabricator

[MLIR][Affine] Simplify nested modulo operations when able
ClosedPublic

Authored by krzysz00 on Sep 16 2021, 2:42 PM.

Details

Summary

It is the case that, for all positive a and b such that b divides a
(e mod (a * b)) mod b = e mod b. For example, ((d0 mod 35) mod 5) can
be simplified to (d0 mod 5), but ((d0 mod 35) mod 4) cannot be simplified
further (x = 36 is a counterexample).

This change enables more complex simplifications. For example,
((d0 * 72 + d1) mod 144) mod 9 can now simplify to (d0 * 72 + d1) mod 9
and thus to d1 mod 9. Expressions with chained modulus operators are
reasonably common in tensor applications, and this change _should_
improve code generation for such expressions.

Diff Detail

Event Timeline

krzysz00 created this revision.Sep 16 2021, 2:42 PM
krzysz00 requested review of this revision.Sep 16 2021, 2:42 PM
krzysz00 updated this revision to Diff 373082.Sep 16 2021, 2:54 PM

Add a null pointer check

krzysz00 updated this revision to Diff 373084.Sep 16 2021, 2:56 PM

(Apparently I called arc diff --update wrong)

mlir/lib/IR/AffineExpr.cpp
833

can you just check the constants are positive and avoid future miscompiles?

krzysz00 updated this revision to Diff 373247.Sep 17 2021, 9:05 AM
  • Check if intermediate constant is positive
nicolasvasilache added inline comments.
mlir/lib/IR/AffineExpr.cpp
835

rhsConst >= 1 too ?

mlir/test/IR/affine-map.mlir
382

nit: newline

This revision is now accepted and ready to land.Sep 17 2021, 10:36 AM
krzysz00 updated this revision to Diff 373279.Sep 17 2021, 10:39 AM
krzysz00 marked an inline comment as done.
  • Check if intermediate constant is positive
krzysz00 updated this revision to Diff 373281.Sep 17 2021, 10:44 AM
krzysz00 marked 2 inline comments as done.

(Rebase and clean up commits, no substantial changes)