Page MenuHomePhabricator

[mlir][affine] Fold affine.min with constant zero expressions
Needs RevisionPublic

Authored by antiagainst on May 27 2021, 5:19 AM.

Details

Summary

Such affine.min ops can be folded into constant zero op, given
that affine ops works on the index type, which by definition
cannot be negative.

Depends On D103243

Diff Detail

Unit TestsFailed

TimeTest
250 msx64 windows > LLVM.DebugInfo/X86::basic-block-sections-debug-loc-const-value-1.ll
Script: -- : 'RUN: at line 1'; c:\ws\w2\llvm-project\premerge-checks\build\bin\llc.exe C:\ws\w2\llvm-project\premerge-checks\llvm\test\DebugInfo\X86\basic-block-sections-debug-loc-const-value-1.ll --dwarf-version=4 --basic-block-sections=none -filetype=obj -o C:\ws\w2\llvm-project\premerge-checks\build\test\DebugInfo\X86\Output\basic-block-sections-debug-loc-const-value-1.ll.tmp
200 msx64 windows > LLVM.DebugInfo/X86::basic-block-sections-debug-loc-const-value-2.ll
Script: -- : 'RUN: at line 1'; c:\ws\w2\llvm-project\premerge-checks\build\bin\llc.exe C:\ws\w2\llvm-project\premerge-checks\llvm\test\DebugInfo\X86\basic-block-sections-debug-loc-const-value-2.ll --dwarf-version=4 --basic-block-sections=none -filetype=obj -o C:\ws\w2\llvm-project\premerge-checks\build\test\DebugInfo\X86\Output\basic-block-sections-debug-loc-const-value-2.ll.tmp
240 msx64 windows > LLVM.DebugInfo/X86::basic-block-sections-debug-loc-split-range.ll
Script: -- : 'RUN: at line 1'; c:\ws\w2\llvm-project\premerge-checks\build\bin\llc.exe C:\ws\w2\llvm-project\premerge-checks\llvm\test\DebugInfo\X86\basic-block-sections-debug-loc-split-range.ll --dwarf-version=4 --basic-block-sections=none -filetype=obj -o C:\ws\w2\llvm-project\premerge-checks\build\test\DebugInfo\X86\Output\basic-block-sections-debug-loc-split-range.ll.tmp
230 msx64 windows > LLVM.DebugInfo/X86::basic-block-sections-debug-loc.ll
Script: -- : 'RUN: at line 5'; c:\ws\w2\llvm-project\premerge-checks\build\bin\llc.exe C:\ws\w2\llvm-project\premerge-checks\llvm\test\DebugInfo\X86\basic-block-sections-debug-loc.ll --dwarf-version=4 --basic-block-sections=none -filetype=obj -o C:\ws\w2\llvm-project\premerge-checks\build\test\DebugInfo\X86\Output\basic-block-sections-debug-loc.ll.tmp
240 msx64 windows > LLVM.DebugInfo/X86::basic-block-sections-debug-loclist-1.ll
Script: -- : 'RUN: at line 1'; c:\ws\w2\llvm-project\premerge-checks\build\bin\llc.exe C:\ws\w2\llvm-project\premerge-checks\llvm\test\DebugInfo\X86\basic-block-sections-debug-loclist-1.ll --dwarf-version=4 --basic-block-sections=none -filetype=obj -o C:\ws\w2\llvm-project\premerge-checks\build\test\DebugInfo\X86\Output\basic-block-sections-debug-loclist-1.ll.tmp
View Full Test Results (9 Failed)

Event Timeline

antiagainst created this revision.May 27 2021, 5:19 AM
antiagainst requested review of this revision.May 27 2021, 5:19 AM
ftynse added a subscriber: ftynse.May 27 2021, 5:22 AM

I'm not sure that values of index type cannot be negative. Index are signless, so the interpretation of the most significant bit depends on the operation.

ftynse requested changes to this revision.May 27 2021, 5:25 AM

https://github.com/llvm/llvm-project/blob/86627be23312bd227e5afa88c206771a9aaf6589/mlir/test/Conversion/AffineToStandard/lower-affine.mlir#L158 relies on having index with negative value, for example, and so does https://github.com/llvm/llvm-project/blob/main/mlir/test/Conversion/StandardToSPIRV/std-ops-to-spirv.mlir#L525.

The only restriction on non-negative values I know is in the RHS of floordiv/ceildiv/mod of affine expressions, but that is not related to the type.

This revision now requires changes to proceed.May 27 2021, 5:25 AM

Ah, I think you are right. I just checked the definition for index type; indeed it's just spec'ed as "signless integer whose size is equal to the natural machine word of the target". I was under the wrong impression due to its close relationship with indices/sizes. Thanks for pointing out!! :)

What I'm trying to do is clean up some of the affine.mins that are used as indices/sizes (as shown in the modified test cases), that shouldn't be negative (otherwise I think there is a problem). Do you know what's the proper way to do that?

bondhugula requested changes to this revision.May 27 2021, 7:31 AM
bondhugula added a subscriber: bondhugula.

index type can be negative as well - very much!

I'm not sure we restrict indices to be positive either... If there is an op that clearly requires values to be non-negative and has undefined behavior otherwise, we could follow a C-compiler approach and assume the value passed to this op must not be negative in valid programs. This isn't something we usually do in MLIR though, so I would think carefully before introducing such transformations.

A more robust, but possibly less aggressive approach, is to reason about the sets of values that each result of the affine map used in affine.min can take. I see two cases:

  • symbolic-only: there is an affine result expression that being subtracted from other expressions always results in a non-negative constant expression, i.e. is symbolically known to be less than others; for example, in (d0 + 3, d0, d0 - 1, d0), we can try (d0) - (d0 - 1) = 1, (d0 + 3) - (d0 - 1) = 4 and prove that d0 - 1 is the smallest expression always, and replace affine.min with affine.apply; I think we have a similar simplification to remove affine loops that never iterate.
  • integer set based: given (partial) knowledge about the sets of values each dimension or symbol can take, we can compute the set of values each affine map result can take (or, combining with the previous case, each difference between expressions can take); if all values in one of the sets are less than or equal to any value in all the other sets, then that expression from which the set is constructed is the minimum and we can simplify again (for the difference case, we want the set of possible differences to be non-negative). For example, if we know that d0 is a loop induction variable going from 1 to N, we can prove that d0 is the minimum of (d0, 2*d0 - 1, 3*d0). This subsumes the symbolic approach, but relies on more complex things internally.
nicolasvasilache resigned from this revision.Wed, Jul 28, 2:21 AM