Affine restrictions in affine_apply

[Nicolas Vasilache]

The affine_apply operation is currently "doubly" affine and conflates two things:

1. it applies an affine map to a list of values of type `index` that are defined as either dim or symbol

2. it restricts (and propagates constraints on) the provenance of dims and symbols to a small subset of ops for which more restrictive polyhedral constraints.

Point 2. is related to the ability to form so-called static control parts and is related to dependence analysis and legality of transformations.

Point 1. however is completely independent, the only local implication of dims and symbol for affine_apply is that dims compose while symbols concatenate as well the structural constraint that dims may not be multiplied.

The properties of composition and canonicalization in affine_apply are more generally useful for the std dialect.

This is a higher-level abstraction for arithmetic expressions, irrespective of what is useful for polyhedral style analysis.

It seems affine_apply would be a good candidate to be moved to std assuming the restrictions can be successfully lifted from the op without breaking affine analyses.

Another possibility would be to also have a std.apply operation. 

However this would result in quite some code duplication for little envisioned benefits (i.e. it is unclear a generalization of affine_apply would be useful in the absence of examples).

What are people's thoughts on this? 

[Uday Bondhugula]

Hi Nicolas,

I think this is an interesting topic. Comments inline.

On Saturday, October 19, 2019 at 1:49:49 AM UTC+5:30, Nicolas Vasilache wrote:

The affine_apply operation is currently "doubly" affine and conflates two things:

1. it applies an affine map to a list of values of type `index` that are defined as either dim or symbol

2. it restricts (and propagates constraints on) the provenance of dims and symbols to a small subset of ops for which more restrictive polyhedral constraints.

Point 2. is related to the ability to form so-called static control parts and is related to dependence analysis and legality of transformations.

Point 1. however is completely independent, the only local implication of dims and symbol for affine_apply is that dims compose while symbols concatenate as well the structural constraint that dims may not be multiplied.

The properties of composition and canonicalization in affine_apply are more generally useful for the std dialect.

This is a higher-level abstraction for arithmetic expressions, irrespective of what is useful for polyhedral style analysis.

I agree. 

 

It seems affine_apply would be a good candidate to be moved to std assuming the restrictions can be successfully lifted from the op without breaking affine analyses.

It actually won't break any affine passes/utilities if the symbol/dim restriction checks for affine_apply's are implemented as part of affine.for and affine.if verifiers -- this had been the case just before the affine ops were moved from the std dialect to the affine dialect. The symbol/dim restrictions on affine.load, affine.store, affine.apply (formerly load, store, affine_apply) used to be verified as part of affine.for's and affine.if's verifiers (@River had suggested and made this change at one point). Are the motivating use cases you have in mind for an std.affine_apply in the presence of affine.for's/if's or in their absence or both? If it's the second scenario, there is another solution:

1) change affine.apply op's verifier to not check for dim and symbol restrictions

2) then enforce this from the verifiers of affine.for and affine.if. 

This way you could use unrestricted affine.apply's from within loop.for and loop.if and get your abstraction for higher level arithmetic expressions. And if you are just looking for affine.applys in flat basic blocks, that's already possible in the current state of things since an affine.apply is always valid at a top level block (as long as it's using index typed operands of course). 

And finally, if we are looking at exploiting unrestricted affine.applys while not being forced to lower away affine.for/if (because there is perhaps still use for them): I think affine.grayboxes will address this. You can put the graybox - it then makes your otherwise invalid affine.apply's valid, optimize and then use the graybox elimination/promotion utility ( https://github.com/bondhugula/mlir/blob/graybox/rfc/rfc-graybox.md#helpers-utilities-and-passes ). This way you won't be throwing any high level information. Note that affine apply composition / normalization / simplification etc. can traverse graybox boundaries.

Depending on the use cases, you also have the path of first lowering affine.for's to loop.for without lowering affine.apply's to add/mul/div/mod, and then exploit whatever you wanted to with affine.applys - there'll be no dim/symbols restrictions on them then, and you won't need grayboxes here. 

 

Another possibility would be to also have a std.apply operation. 

However this would result in quite some code duplication for little envisioned benefits (i.e. it is unclear a generalization of affine_apply would be useful in the absence of examples).

What are people's thoughts on this? 

It would just look a bit weird that affine_apply would be in the std dialect while there is an affine dialect containing the other (for/if) ops. Instead, we could just explore using the existing affine.apply in conjunction with the other standard/loop dialect ops for the use cases / transformations you have in mind.

 

Best,

Uday

[Nicolas Vasilache]

Hi Uday,

Thanks for your reply.

The first use case is #189 where I jacked out the dim/sym verification to see the attached test run end to end.

I am away for 1 week so if anyone wants to pick this up it should be relatively easy given what you wrote.

Otherwise I'll pick it up the week after next.

Thanks!

--
You received this message because you are subscribed to the Google Groups "MLIR" group.
To unsubscribe from this group and stop receiving emails from it, send an email to mlir+uns...@tensorflow.org.
To view this discussion on the web visit https://groups.google.com/a/tensorflow.org/d/msgid/mlir/72b9953e-2d7c-498f-86a8-949d247ce8b1%40tensorflow.org.

[Nicolas Vasilache]

Addressed in a770e358a041598589a3e64bf639c4d7681106c7.

To unsubscribe from this group and stop receiving emails from it, send an email to mlir+unsubscribe@tensorflow.org.

[Mehdi AMINI]

On Fri, Oct 18, 2019 at 1:19 PM 'Nicolas Vasilache' via MLIR <ml...@tensorflow.org> wrote:

The affine_apply operation is currently "doubly" affine and conflates two things:

1. it applies an affine map to a list of values of type `index` that are defined as either dim or symbol

2. it restricts (and propagates constraints on) the provenance of dims and symbols to a small subset of ops for which more restrictive polyhedral constraints.

Point 2. is related to the ability to form so-called static control parts and is related to dependence analysis and legality of transformations.

Point 1. however is completely independent, the only local implication of dims and symbol for affine_apply is that dims compose while symbols concatenate as well the structural constraint that dims may not be multiplied.

The properties of composition and canonicalization in affine_apply are more generally useful for the std dialect.

 

This is a higher-level abstraction for arithmetic expressions, irrespective of what is useful for polyhedral style analysis.

It seems affine_apply would be a good candidate to be moved to std assuming the restrictions can be successfully lifted from the op without breaking affine analyses.

I don't really understand why would affine.apply need to move to std? What is limiting in having it in the affine dialect?

 

Another possibility would be to also have a std.apply operation. 

However this would result in quite some code duplication for little envisioned benefits (i.e. it is unclear a generalization of affine_apply would be useful in the absence of examples).

What are people's thoughts on this? 

I am not sure I totally understand the proposal: would std.apply operate on an affine map? (in which case I have strong concerns about this: our most recent discussions are about making std dialect thinner, and decouple affine maps from core to move these into the affine dialect, and it seems to goes against it).

Or would std.apply operate  the arithmetic operations in the std dialect? Would it take a region? Can you provide an example about how would this work?

Thanks,

-- 

Mehdi

[Nicolas Vasilache]

On Tue, Nov 26, 2019 at 1:34 PM Mehdi AMINI <joke...@gmail.com> wrote:

On Fri, Oct 18, 2019 at 1:19 PM 'Nicolas Vasilache' via MLIR <ml...@tensorflow.org> wrote:

The affine_apply operation is currently "doubly" affine and conflates two things:

1. it applies an affine map to a list of values of type `index` that are defined as either dim or symbol

2. it restricts (and propagates constraints on) the provenance of dims and symbols to a small subset of ops for which more restrictive polyhedral constraints.

Point 2. is related to the ability to form so-called static control parts and is related to dependence analysis and legality of transformations.

Point 1. however is completely independent, the only local implication of dims and symbol for affine_apply is that dims compose while symbols concatenate as well the structural constraint that dims may not be multiplied.

The properties of composition and canonicalization in affine_apply are more generally useful for the std dialect.

 

This is a higher-level abstraction for arithmetic expressions, irrespective of what is useful for polyhedral style analysis.

It seems affine_apply would be a good candidate to be moved to std assuming the restrictions can be successfully lifted from the op without breaking affine analyses.

I don't really understand why would affine.apply need to move to std? What is limiting in having it in the affine dialect?

It could but does not need to.

The underlying point is that affine_apply is not an affine dialect "thing" that needs to be restricted by dim and symbol type constraints, it is a more general index arithmetic "thing". 

 

 

Another possibility would be to also have a std.apply operation. 

However this would result in quite some code duplication for little envisioned benefits (i.e. it is unclear a generalization of affine_apply would be useful in the absence of examples).

What are people's thoughts on this? 

I am not sure I totally understand the proposal: would std.apply operate on an affine map? (in which case I have strong concerns about this: our most recent discussions are about making std dialect thinner, and decouple affine maps from core to move these into the affine dialect, and it seems to goes against it).

There is no proposal, a recent commit relaxed the affine restrictions and is sufficient.

Re std, note that generally, AffineExpr and AffineMap are not types that strictly belong to the affine dialect. 

The fact that they share the same name is circumstantial.

It makes sense to use AffineExpr and AffineMap types with functions or polynomials.  

 

Or would std.apply operate  the arithmetic operations in the std dialect?

affine_apply now supports arithmetic operations on arbitrary `index` types.

 

Would it take a region? Can you provide an example about how would this work?

Works the same as it used to but does not need to fail verification on dim + symbol checking.

Thanks,

-- 

Mehdi

--

N