RFC: Adding a proper interface for SideEffects

149 views
Skip to first unread message

River Riddle

unread,
Dec 9, 2019, 8:51:36 PM12/9/19
to MLIR

Modeling the Side-Effects of MLIR Operations

Side-Effects are a descriptive mechanism that help detail the effects of an operation on the world around it. Side effects may include reading memory, writing memory, throwing exceptions, etc. These effects are important for the compiler to be able to reason about and optimize the IR. In the worst case, the compiler must be extremely conservative about any unknown aspects about operations to ensure that the program is correctly translated. In MLIR, we currently have no formal mechanism for operations to provide information about their side effects aside from the all-or-nothing trait NoSideEffect. This essentially means that we can only model either completely pure/effect free operations, or worst case “could do absolutely anything” operations. It has come to a point where we are interested in writing more complicated analyses and transformations, requiring more detailed information.


There are many different aspects that come along with defining a representation for side effects, and many of these aspects can be split and discussed separately. As such, this RFC will only focus on setting up some of the initial building blocks for the representation and definition. From the compiler’s perspective, we can establish two separate granularities of information that we would like to query and understand.


  • The Effect being exhibited

This is the first aspect, and also the simplest. This is a coarse grain definition of the overarching effect being exhibited: reads memory, writes memory, throws exceptions, etc.


  • Where the Effect is applied

Knowing what the effect is may be enough for many different transformations, but it doesn’t encode all of the information that we want it to. Often times operations may have conflicting side effects that prohibit a transformation from being performed, e.g. we can’t opaquely move operations that reads before operations that write. In this case, the transformation is also interested in what resource the side effect applies to, as well as the range within that resource being affected. For example, an alias analysis will likely want to know what effects apply to which operands of the operation. Given that MLIR is multi-level, we may not have a formal definition of “main memory”, meaning that operations that have a write side effect may be operating on completely different memory resources.


Below I propose adding a new interface that will allow for defining and expressing a set of core memory effects in a way that can be interpreted by all parts of the compiler. This will act as a supplement to the existing traits that we have for expressing effects, e.g. `HasNoSideEffects’, and will not replace them.


Trait(/Interface): HasSideEffects<typename… Effects>

This trait/interface allows for statically, or dynamically, defining a set of effects that are exhibited by an operation. A set of core side effects are provided:


  • Read:

    • This effect indicates that the operation reads from some resource. A 'read' effect implies only dereferencing of the resource, and not any visible mutation.

  • Write:

    • This effect indicates that the operation writes to some resource. A 'write' effect implies only mutating a resource, and not any visible dereference or read.

  • UnModeled:

    • This effect indicates that the operation performs some unmodeled effect on a resource that is not captured by one of the other above effects. No other assumptions can be made about the specific effect applied, and the compiler must treat this effect conservatively.


The above are the baseline effects. We will likely extend Read/Write to support volatility, atomicity, etc. This is intentionally kept as future work to let this section focus on the infrastructure that drives the definition of such effects.


This trait also allows for defining dynamic side effects, and modeling recursive effects for operations that inherit effects from their regions. The interface definition is shown below:


/// An interface used to query information about the side effects applied by an

/// operation.

class SideEffectOpInterface : ... {

public:

  /// If the given effect is exhibited by this operation, return the effect

  /// instance. Otherwise, returns null.

  template <typename Effect> Effect *getEffect();


  /// Returns true if this operation exhibits the given effect.

  template <typename Effect> bool hasEffect();


  /// Returns if this operation only has the given effect.

  template <typename Effect> bool onlyHasEffect();


  /// Collects all of the effects that are exhibited by this operation and

  /// places them in `effects`.

  void collectEffects(SmallVectorImpl<SideEffects::Effect *> &effects);


  /// Returns true if the regions of this operation should be considered when

  /// checking if this operation has a side effect.

  bool hasRecursiveEffects();

};


/// The set of core effects.

namespace SideEffects {

  struct Read …;

  struct Write …;

  struct UnModeled …;

}


An example is shown below:


// Example operation definitions:

def LoadOp : My_Op<"load", [SideEffects<"SideEffects::Read">]> { }

def StoreOp : My_Op<"store", [SideEffects<"SideEffects::Write">]> { }


// Example interface usage:

Operation *op = …;

SideEffectOpInterface interface = cast<SideEffectOpInterface>(op);


// Operation has recursive side effects.

if (interface.hasRecursiveEffects())

  ;

// Operation writes to memory.

if (interface.hasEffect<SideEffects::Write>())

  ;

// Operation *only* reads from memory.

if (interface.onlyHasEffect<SideEffects::Read>())

  ;


This intention is for this interface to provide something that we can build on moving forward. Adding additional pieces as we work out the requirements and use cases, e.g. atomics/volatility, etc.


Thoughts? Just checking that everyone is on board before I start charging ahead.


Thanks, 

-- River


Uday Bondhugula

unread,
Dec 9, 2019, 9:44:21 PM12/9/19
to MLIR

Looks great to me! On a minor note, the name onlyHasEffect is weird (also its doc comment). Consider changing to hasSingleEffect() / hasOnlyEffect?

/// Returns if this operation only has the given effect.

--> /// Returns true if the given effect is the only one that the operation has.

Or else it could imply this operation is the only one that has this effect (static / operation-wide or for that dynamic instance).

~ Uday

Mehdi AMINI

unread,
Dec 10, 2019, 5:44:06 AM12/10/19
to River Riddle, MLIR
Am I missing the part of the interface that addresses the *which resource* the side-effect apply to?

Thanks,

-- 
Mehdi

Tres Popp

unread,
Dec 10, 2019, 6:08:54 AM12/10/19
to Mehdi AMINI, River Riddle, MLIR
I think it might be good for the interface to have from the beginning, either a  numOfEffects() or hasExactlyEffects(SmallVectorImpl<SideEffects::Effect *> effects) that are like onlyHasEffect() but with a number of effects greater than 1.  This is based on my assumption that the normal mode of operation is that operations are only safe when I have full knowledge of the side effects (while any other side effects will require me to not do anything).

The UnModeled sticks out to me as possibly causing problems because it might encourage people to be lazy and just use that enum rather than defining a new Effect, then encode the knowledge on the SideEffects only in code and might make incorrect assumptions about other uses of the effect. It's also nit picky and I can't think of a better name, but I think UnModeled is more like a name around an implementation detail rather than how it should be used as implying this could be any imaginable side effect.

--
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/CANF-O%3DZ%2ByDqOiuFxowuwXGDzj6ke1UtBCw94T%2B8s8yi5DADikQ%40mail.gmail.com.

Ben Vanik

unread,
Dec 10, 2019, 10:10:43 AM12/10/19
to Tres Popp, Mehdi AMINI, River Riddle, MLIR
Happy to see a proposal here! Thanks River!

I too am interested in seeing an example of what a resource-specific side effect would look like in ODS. For example, 
def LoadOp : My_Op<"load", [SideEffects<"SideEffects::Read">]> {
  let arguments = (ins MyType:$src);
}
How do I say $src is read? SideEffects::Read<["$src"]> on the op? If there are multiple would they all be part of the same SideEffects::Read? What about for external resources - could those be specified by key? ("reads and writes of abstract external resource "foo" must be ordered" - such as when "foo" is a work queue/scheduler, memory pool, physical device, etc)

Maybe the side effects are put on the operands themselves when they pertain to them, similar to function attributes + function arg/result attributes? Then it's possible to model op-specific side effects/external resources as well as operand-specific side effects. I could imagine some sugar to make this nice in the common case (`let arguments = (ins Read<MyType>:$src);`, etc). This would make it easier to have stronger typing around specific effect types -- for example, an external resource read could use SideEffects::ReadExternal("key") vs. an operand having SideEffects::ReadOperandRange($min, $max) (or whatever). Having side effects pertaining to operands live on the operands makes certain cases easier to reason about too like empty variadic operands (which I wouldn't want to ever be returned as having side effect when looking at a particular op).

The interface of querying based on side effect type seems a bit hard to use in the resource-specific case as most often queries would be about particular operands; "what's the side effect on operand $src?" or "which operands are read?" or, more generally, "is there a RAW/RAR/WAR/etc dependency between these two ops" (which would require matching the specific resources for all side effects between them). Same with specific external resources. It'd be nice not to have to getEffect<SideEffects::Read>() and getEffect<SideEffects::Write>() and then walk ranges (and switch based on operand type) to do these things. Or even worse have an arbitrary list of side effect types T that all code needs to know about and specifically query (if SideEffects::ReadRange was added would all code need to be changed to detect hazards, etc).




River Riddle

unread,
Dec 10, 2019, 2:17:33 PM12/10/19
to Tres Popp, Mehdi AMINI, MLIR
On Tue, Dec 10, 2019 at 3:08 AM Tres Popp <tp...@google.com> wrote:
I think it might be good for the interface to have from the beginning, either a  numOfEffects() or hasExactlyEffects(SmallVectorImpl<SideEffects::Effect *> effects) that are like onlyHasEffect() but with a number of effects greater than 1.  This is based on my assumption that the normal mode of operation is that operations are only safe when I have full knowledge of the side effects (while any other side effects will require me to not do anything).
I agree with you about the usefulness of such an API, though you don't always need to know everything about an operation. The way that this is structured is that the effects are something that can be reasoned about by any part of the compiler. There is the ability for users to define their own effects, but these can't supercede or replace the core effects. i.e. if the operation doesn't have the 'read' effect, it can be assumed that it doesn't read memory. It really boils down to the specific transformation being performed, and the information necessary at the time. That being said, I 100% agree that it should be easy to know if the operation has effects you either can't handle or don't know about.
 

The UnModeled sticks out to me as possibly causing problems because it might encourage people to be lazy and just use that enum rather than defining a new Effect, then encode the knowledge on the SideEffects only in code and might make incorrect assumptions about other uses of the effect. It's also nit picky and I can't think of a better name, but I think UnModeled is more like a name around an implementation detail rather than how it should be used as implying this could be any imaginable side effect.
The UnModeled is kind of an escape hatch for things that aren't directly modelable. For example, an operation may want to express that it reads from memory but it also does some crazy thing that it can't describe to you. This would let us know that it doesn't write to anything that is visible to us, but it can't just be removed if it has no uses. It was intended as a "I also do something else that isn't either of those things, so be conservative with me",

-- River

River Riddle

unread,
Dec 10, 2019, 2:38:11 PM12/10/19
to Ben Vanik, Tres Popp, Mehdi AMINI, MLIR
Hey Ben,

On Tue, Dec 10, 2019 at 7:10 AM Ben Vanik <benv...@google.com> wrote:
Happy to see a proposal here! Thanks River!

I too am interested in seeing an example of what a resource-specific side effect would look like in ODS. For example, 
Sorry about that. My post-work brain missed that when sending out the RFC. I added some details as specific replies to your inquiries below:
 
def LoadOp : My_Op<"load", [SideEffects<"SideEffects::Read">]> {
  let arguments = (ins MyType:$src);
How do I say $src is read?
It depends on how deep of an integration we want with ODS, and I may be a bit biased but I would say that having a deep integration for defining these is actually good. This will likely be one of the most used adornments? on operation definitions, so it should be really clean to add.
 
SideEffects::Read<["$src"]> on the op? If there are multiple would they all be part of the same SideEffects::Read? What about for external resources - could those be specified by key? ("reads and writes of abstract external resource "foo" must be ordered" - such as when "foo" is a work queue/scheduler, memory pool, physical device, etc)
This is looking at the next step, but this all depends on the abstraction we choose for aliasing. The biggest thing that needs to be really well-designed is how different resources interact with each other, alias each other, etc. I purposely put this as a next step so that we don't get bogged down on the different design choices when bringing up the base infra. For ordering, this should be something generically described on the `Read` effect itself, re. atomics.
 

Maybe the side effects are put on the operands themselves when they pertain to them, similar to function attributes + function arg/result attributes? Then it's possible to model op-specific side effects/external resources as well as operand-specific side effects. I could imagine some sugar to make this nice in the common case (`let arguments = (ins Read<MyType>:$src);`, etc). This would make it easier to have stronger typing around specific effect types -- for example, an external resource read could use SideEffects::ReadExternal("key") vs. an operand having SideEffects::ReadOperandRange($min, $max) (or whatever). Having side effects pertaining to operands live on the operands makes certain cases easier to reason about too like empty variadic operands (which I wouldn't want to ever be returned as having side effect when looking at a particular op).
Yes, this is essentially what I had in mind. We can have a really nice sugaring on specific ranges of operands that detail the effects being applied to them. ODS when then auto-generate the specific hook for detailing the effects on a specific operand group automatically. The intention is that we have a very similar API for checking effects on operands as we do for the operation itself. The variadic case is also interesting because that would let the operation itself have dynamic side effects depending on if specific operands are present.
 

The interface of querying based on side effect type seems a bit hard to use in the resource-specific case as most often queries would be about particular operands; "what's the side effect on operand $src?" or "which operands are read?" or, more generally, "is there a RAW/RAR/WAR/etc dependency between these two ops" (which would require matching the specific resources for all side effects between them). Same with specific external resources. It'd be nice not to have to getEffect<SideEffects::Read>() and getEffect<SideEffects::Write>() and then walk ranges (and switch based on operand type) to do these things. Or even worse have an arbitrary list of side effect types T that all code needs to know about and specifically query (if SideEffects::ReadRange was added would all code need to be changed to detect hazards, etc).
 There are two different pieces that should be separated here. One is the interface that makes it easy for operation to describe the information about its effects, the other is the collection of utilities/analyses/abstraction that we build on top of this to make it easy to answer more complex queries. I would prefer we avoid adding a bunch of complexity into the interface, and instead add an analysis/analyses that make it easy to unpack relations between different operations. The interface should be able to easily answer questions like :  "what's the side effect on operand $src?" or "which operands are read?"; but not go anywhere near answering questions related to dependence analysis.
 
-- River

Sean Silva

unread,
Dec 10, 2019, 5:09:59 PM12/10/19
to MLIR
Can you describe more the specifics of ops with regions? I'm worried that the obvious code that just checks "hasEffect" will silently do the wrong thing for ops with regions.

Also, it isn't clear from your RFC if hasRecursiveEffects just says "you need to check the regions" or whether it actually does the check itself.

-- Sean Silva

River Riddle

unread,
Dec 10, 2019, 5:21:24 PM12/10/19
to Sean Silva, MLIR
On Tue, Dec 10, 2019 at 2:10 PM 'Sean Silva' via MLIR <ml...@tensorflow.org> wrote:
Can you describe more the specifics of ops with regions? I'm worried that the obvious code that just checks "hasEffect" will silently do the wrong thing for ops with regions.

Also, it isn't clear from your RFC if hasRecursiveEffects just says "you need to check the regions" or whether it actually does the check itself.

hasEffect is intended just for the top-level operation itself. `hasRecursiveEffects` means that the user of the interface needs to check the regions. The main thing I'm trying to avoid is O(operations) amount of work every time you query side effects. I want to avoid the need to do a lot of work within the interface itself, and instead pushing the complexity on the user(analyses/utilities and not end users) to allow for more efficient computation/caching. I'm trying to avoid the dark world where interfaces become large state containing/compute heavy analyses in disguise.

-- River 
 
--
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.

Lucy Fox

unread,
Dec 10, 2019, 5:44:56 PM12/10/19
to River Riddle, Sean Silva, MLIR
On Tue, Dec 10, 2019 at 2:21 PM 'River Riddle' via MLIR <ml...@tensorflow.org> wrote:


On Tue, Dec 10, 2019 at 2:10 PM 'Sean Silva' via MLIR <ml...@tensorflow.org> wrote:
Can you describe more the specifics of ops with regions? I'm worried that the obvious code that just checks "hasEffect" will silently do the wrong thing for ops with regions.

Also, it isn't clear from your RFC if hasRecursiveEffects just says "you need to check the regions" or whether it actually does the check itself.

hasEffect is intended just for the top-level operation itself. `hasRecursiveEffects` means that the user of the interface needs to check the regions. The main thing I'm trying to avoid is O(operations) amount of work every time you query side effects. I want to avoid the need to do a lot of work within the interface itself, and instead pushing the complexity on the user(analyses/utilities and not end users) to allow for more efficient computation/caching. I'm trying to avoid the dark world where interfaces become large state containing/compute heavy analyses in disguise.

-- River 

I agree with the principle of keeping the interface lightweight.

Would collectEffects do those recursive checks? (I'm assuming not, based on the expectation that it acts analogously to hasEffect and thus only checks the top-level operation. But the name could be potentially confusing, so we should make sure the documentation is clear.)

Assuming the above assumption is correct: is the general idea that hasRecursiveEffects would check whether any of its regions have effects (i.e. call collectEffects on each region; hasRecursiveEffects is true if ever the `effects` vector has nonzero size) -- and then cache that value for future calls to hasRecursiveEffects?

Mehdi AMINI

unread,
Dec 10, 2019, 8:49:14 PM12/10/19
to River Riddle, MLIR
As far as I can tell, the interface so far allows us to go from "hasNoSideEffects" to differentiating between Read,Write, and UnModeled effect, without more information. My current thoughts are that:

1) I don't really see how the "unmodeled" would be more constraining than "write" on a resource? Could read and write be enough to describe effects?
Actually the literature tend to either add Alloc and Free as possible other effects when limiting to memory, or be more extensible to model things like locking/unlocking, throwing/catching, file open/close, etc.
I think it is interesting to think about the evolution in this direction as well: can the effect system be pluggable? The same way we have dialects for types/operation, we could register effects "domain" with their own list of effects. The "memory domain" could limit itself to read/write (and possibly alloc/free).

2) The "which resource" the side-effect applies to is really critical: it isn't clear to me that we can leave this out of the interface from the beginning. I actually suspect that the reason you added "unmodeled" as a side-effect in the first place is because the "which resource" aspect isn't addressed.
Specifically, the "unmodeled" effect seems to me to be similar to a "write" that applies to "everything" (the absolute top of a resource lattice).

A straw man high-level proposal of an interface that would query the list of side-effect for an operation and would return a list of effects. Each effect would have a kind (Read, Write, ... possibly in "domains"), but also a "resource identifier".
I haven't thought about an implementation for the resource identifier, but it would indicate if the effects applies to a given operand, result (in the case of alloc for example), or global (this does not have to point to an SSA value or a symbol, it can be a domain specific lattice: for example "<gpu:shared_mem>"). 

3) Sub-resource granularity access: at some point we may want to model more granular access. A write to a subset of a memref argument can touch a small subset of the memory. I don't see how this granularity access can be hard-coded in the interface, it would have to be specific to the domains and the resources that are manipulated. Also different analysis could provide different representation for sub-resource access description (for example in the memory domain a polyhedral analysis could provide affine maps describing polyhedra, an interval-based representation could limit to hyper-rectangular approximation).

4) May/Must: this is needed to be able to "kill" a definition for instance. Knowing that an operation *must* write entirely the memory behind a memref can help defining lifetime of the resource.

5) The information about side-effect may need an analysis query. It isn't totally clear to me right now if the operation itself can always answer the query behind the interface without even benefiting from an analysis. (I think there is a larger question here about our handling of analysis with respect to other components in MLIR like patterns and interfaces, we can just punt this).

Cheers,

-- 
Mehdi

River Riddle

unread,
Dec 10, 2019, 9:09:49 PM12/10/19
to Mehdi AMINI, MLIR
It depends on the granularity of resources and how aliasing works. I'm happy to punt until we have an actual user that would need something like this.
 
Actually the literature tend to either add Alloc and Free as possible other effects when limiting to memory, or be more extensible to model things like locking/unlocking, throwing/catching, file open/close, etc.
I think it is interesting to think about the evolution in this direction as well: can the effect system be pluggable? The same way we have dialects for types/operation, we could register effects "domain" with their own list of effects. The "memory domain" could limit itself to read/write (and possibly alloc/free).
The system doesn't prevent user defined effects, and it is trivial to define new ones. The main thing that we need to make sure is that domain specific effects play well together with, and don't overly pessimize the core effects. The main restriction is that effects should not imply each other, i.e. if I define an effect "Foo" it can't imply a "Write" effect. Operations using the "Foo" effect would need to also explicitly add "Write" as necessary.


2) The "which resource" the side-effect applies to is really critical: it isn't clear to me that we can leave this out of the interface from the beginning. I actually suspect that the reason you added "unmodeled" as a side-effect in the first place is because the "which resource" aspect isn't addressed.
"unmodeled" in no way has any relation to "which resource". They are completely unrelated.

Specifically, the "unmodeled" effect seems to me to be similar to a "write" that applies to "everything" (the absolute top of a resource lattice).

A straw man high-level proposal of an interface that would query the list of side-effect for an operation and would return a list of effects. Each effect would have a kind (Read, Write, ... possibly in "domains"), but also a "resource identifier".
Yes, I call these "EffectInstance" or an instance of an effect applied on a specific resource. 
 

  class EffectInstance {
  public:
    EffectInstance(Effect *effect, Resource *resource = DefaultResource::get());
    EffectInstance(Effect *effect, Value *value);

    /// Return the effect being applied.
    Effect *getEffect() const;

    /// Return the value the effect is applied on, or nullptr if this is
    /// effecting an external resource instead.
    Value *getValue() const;

    /// Return the resource that the effect applies to, or nullptr if this is
    /// effecting a value.
    Resource *getResource() const;
  };

I haven't thought about an implementation for the resource identifier, but it would indicate if the effects applies to a given operand, result (in the case of alloc for example), or global (this does not have to point to an SSA value or a symbol, it can be a domain specific lattice: for example "<gpu:shared_mem>"). 
What I had in mind is that you can either have an operand or result, for the exact reasons you mention, but also a `Resource`. This is a user defined class that acts as a sort of abstract global entity. There would be a default resources with conservative properties, e.g. for modeling things like ExternalMemOnly.  Example definition of a resource:

struct GPUSharedMem : public Resource::Base<GPUSharedMem> {
  /// Return a string name of the resource.
  StringRef getName() final { return "<gpu:shared_mem>"; }
};

  /// Returns the set of effected resources.
  void MyOp::getEffectInstances(SmallVectorImpl<EffectInstance> &instances) {
    // MyOp reads from GPUSharedMem.
    instances.push_back(EffectInstance(SideEffects::Read::get(), GPUSharedMem::get()));
  }


3) Sub-resource granularity access: at some point we may want to model more granular access. A write to a subset of a memref argument can touch a small subset of the memory. I don't see how this granularity access can be hard-coded in the interface, it would have to be specific to the domains and the resources that are manipulated. Also different analysis could provide different representation for sub-resource access description (for example in the memory domain a polyhedral analysis could provide affine maps describing polyhedra, an interval-based representation could limit to hyper-rectangular approximation).
I agree. This is the aspect that I wanted to push a bit further so that we could discuss this as its own thing. There is a lot of prior art for this, and it would be nice to really nail a representation for this. 

 

4) May/Must: this is needed to be able to "kill" a definition for instance. Knowing that an operation *must* write entirely the memory behind a memref can help defining lifetime of the resource.
This seems like a useful bit to have.
 

5) The information about side-effect may need an analysis query. It isn't totally clear to me right now if the operation itself can always answer the query behind the interface without even benefiting from an analysis. (I think there is a larger question here about our handling of analysis with respect to other components in MLIR like patterns and interfaces, we can just punt this).
I 100% agree here.

-- River
 

Cheers,

-- 
Mehdi

Lei Zhang

unread,
Dec 12, 2019, 11:44:24 AM12/12/19
to River Riddle, Ben Vanik, Tres Popp, Mehdi AMINI, MLIR
On Tue, Dec 10, 2019 at 2:38 PM 'River Riddle' via MLIR <ml...@tensorflow.org> wrote:
Hey Ben,

On Tue, Dec 10, 2019 at 7:10 AM Ben Vanik <benv...@google.com> wrote:
Happy to see a proposal here! Thanks River!

I too am interested in seeing an example of what a resource-specific side effect would look like in ODS. For example, 
Sorry about that. My post-work brain missed that when sending out the RFC. I added some details as specific replies to your inquiries below:
 
def LoadOp : My_Op<"load", [SideEffects<"SideEffects::Read">]> {
  let arguments = (ins MyType:$src);
How do I say $src is read?
It depends on how deep of an integration we want with ODS, and I may be a bit biased but I would say that having a deep integration for defining these is actually good. This will likely be one of the most used adornments? on operation definitions, so it should be really clean to add.
 
SideEffects::Read<["$src"]> on the op? If there are multiple would they all be part of the same SideEffects::Read? What about for external resources - could those be specified by key? ("reads and writes of abstract external resource "foo" must be ordered" - such as when "foo" is a work queue/scheduler, memory pool, physical device, etc)
This is looking at the next step, but this all depends on the abstraction we choose for aliasing. The biggest thing that needs to be really well-designed is how different resources interact with each other, alias each other, etc. I purposely put this as a next step so that we don't get bogged down on the different design choices when bringing up the base infra. For ordering, this should be something generically described on the `Read` effect itself, re. atomics.
 

Maybe the side effects are put on the operands themselves when they pertain to them, similar to function attributes + function arg/result attributes? Then it's possible to model op-specific side effects/external resources as well as operand-specific side effects. I could imagine some sugar to make this nice in the common case (`let arguments = (ins Read<MyType>:$src);`, etc). This would make it easier to have stronger typing around specific effect types -- for example, an external resource read could use SideEffects::ReadExternal("key") vs. an operand having SideEffects::ReadOperandRange($min, $max) (or whatever). Having side effects pertaining to operands live on the operands makes certain cases easier to reason about too like empty variadic operands (which I wouldn't want to ever be returned as having side effect when looking at a particular op).
Yes, this is essentially what I had in mind. We can have a really nice sugaring on specific ranges of operands that detail the effects being applied to them. ODS when then auto-generate the specific hook for detailing the effects on a specific operand group automatically. The intention is that we have a very similar API for checking effects on operands as we do for the operation itself. The variadic case is also interesting because that would let the operation itself have dynamic side effects depending on if specific operands are present.

+1 to this. The intention is to put single-entity constraints on the operand/attribute/result itself and leave cross-entity constraints on the op. I introduced `Confined` previously to allow attaching additional "atomic" constraints on attributes. It avoids us to define a new `Attr` subclass for each variant and the associated combinatorial explosion. I think we can introduce something similar for operands/results. Renaming existing `Confined` into `ConfinedAttr` (to follow convention of OptionalAttr/DefaultValuedAttr) and use `Confined` for operands/results we can have

let arguments = (ins
  Confined<MyType, [ReadSideEffect, ...]>:$my_operand
);

 

Mehdi AMINI

unread,
Dec 12, 2019, 12:02:49 PM12/12/19
to River Riddle, MLIR
If we push the idea of domains similarly to dialect, why do we need "core effects" in the first place? Seems like memory accesses could just one domain amongst other?
It would also force us to design from the beginning with extensibility in mind. How do you this by the way? Would we use a similar "range registration" mechanism as we do for types for custom "domains" to have their RTTI kinds?



2) The "which resource" the side-effect applies to is really critical: it isn't clear to me that we can leave this out of the interface from the beginning. I actually suspect that the reason you added "unmodeled" as a side-effect in the first place is because the "which resource" aspect isn't addressed.
"unmodeled" in no way has any relation to "which resource". They are completely unrelated.

I take your words for it, but I'm missing an explanation of what is "unmodeled" about ;) ; since you mentioned above to punt adding it, we can leave this discussion for when the time comes.
 
That said if we remove "unmodeled" we still need to define what to return when querying an operation that does register any traits, which I think has to be the most conservative set of effects from a memory point of view (this is what I was trying to express in the sentence right below).


Specifically, the "unmodeled" effect seems to me to be similar to a "write" that applies to "everything" (the absolute top of a resource lattice).

A straw man high-level proposal of an interface that would query the list of side-effect for an operation and would return a list of effects. Each effect would have a kind (Read, Write, ... possibly in "domains"), but also a "resource identifier".
Yes, I call these "EffectInstance" or an instance of an effect applied on a specific resource. 
 

  class EffectInstance {
  public:
    EffectInstance(Effect *effect, Resource *resource = DefaultResource::get());
    EffectInstance(Effect *effect, Value *value);

    /// Return the effect being applied.
    Effect *getEffect() const;

    /// Return the value the effect is applied on, or nullptr if this is
    /// effecting an external resource instead.
    Value *getValue() const;

    /// Return the resource that the effect applies to, or nullptr if this is
    /// effecting a value.
    Resource *getResource() const;
  };

OK that seems promising. But I'm not sure I understand how this all fits together with the interface proposed in the original email.

For example:

def LoadOp : My_Op<"load", [SideEffects<"SideEffects::Read">]> { … }
def StoreOp : My_Op<"store", [SideEffects<"SideEffects::Write">]> { … }

This traits is at the operation level and does not include informations about the instance.

The SideEffectOpInterface exposes a `template <typename Effect> Effect *getEffect();` method, and it isn't clear what the template is here, I would just expect something like an EffectInstance.
 

I haven't thought about an implementation for the resource identifier, but it would indicate if the effects applies to a given operand, result (in the case of alloc for example), or global (this does not have to point to an SSA value or a symbol, it can be a domain specific lattice: for example "<gpu:shared_mem>"). 
What I had in mind is that you can either have an operand or result, for the exact reasons you mention, but also a `Resource`. This is a user defined class that acts as a sort of abstract global entity. There would be a default resources with conservative properties, e.g. for modeling things like ExternalMemOnly.  Example definition of a resource:

struct GPUSharedMem : public Resource::Base<GPUSharedMem> {
  /// Return a string name of the resource.
  StringRef getName() final { return "<gpu:shared_mem>"; }
};

  /// Returns the set of effected resources.
  void MyOp::getEffectInstances(SmallVectorImpl<EffectInstance> &instances) {
    // MyOp reads from GPUSharedMem.
    instances.push_back(EffectInstance(SideEffects::Read::get(), GPUSharedMem::get()));
  }


3) Sub-resource granularity access: at some point we may want to model more granular access. A write to a subset of a memref argument can touch a small subset of the memory. I don't see how this granularity access can be hard-coded in the interface, it would have to be specific to the domains and the resources that are manipulated. Also different analysis could provide different representation for sub-resource access description (for example in the memory domain a polyhedral analysis could provide affine maps describing polyhedra, an interval-based representation could limit to hyper-rectangular approximation).
I agree. This is the aspect that I wanted to push a bit further so that we could discuss this as its own thing. There is a lot of prior art for this, and it would be nice to really nail a representation for this. 

I'm actually wondering if this can't be handle in the opaque "resource" so it can get extended. But the interface right now does not model operands as resources.

Thanks,

--
Mehdi

River Riddle

unread,
Dec 12, 2019, 12:39:17 PM12/12/19
to Mehdi AMINI, MLIR
I'm not sure if I totally understand what you are getting at, but I'm very wary of overlapping effects. If we did have different domains, which already technically possible to a certain extent, I would only be +1 if those domains can not affect or overlap(imply) each other. I don't want to have N different overlapping definitions for "read"ing from a resource.

 



2) The "which resource" the side-effect applies to is really critical: it isn't clear to me that we can leave this out of the interface from the beginning. I actually suspect that the reason you added "unmodeled" as a side-effect in the first place is because the "which resource" aspect isn't addressed.
"unmodeled" in no way has any relation to "which resource". They are completely unrelated.

I take your words for it, but I'm missing an explanation of what is "unmodeled" about ;) ; since you mentioned above to punt adding it, we can leave this discussion for when the time comes.
 
That said if we remove "unmodeled" we still need to define what to return when querying an operation that does register any traits, which I think has to be the most conservative set of effects from a memory point of view (this is what I was trying to express in the sentence right below).
This is part of my point about "unmodeled". If unmodeled can do literally anything(read/write/etc.), then we have overlapping effects which aren't ideal IMO. Unmodeled then becomes a special case everywhere given that users can no longer just assume that the absence of "Read" means that there isn't a read. It just makes the experience worse overall.
 


Specifically, the "unmodeled" effect seems to me to be similar to a "write" that applies to "everything" (the absolute top of a resource lattice).

A straw man high-level proposal of an interface that would query the list of side-effect for an operation and would return a list of effects. Each effect would have a kind (Read, Write, ... possibly in "domains"), but also a "resource identifier".
Yes, I call these "EffectInstance" or an instance of an effect applied on a specific resource. 
 

  class EffectInstance {
  public:
    EffectInstance(Effect *effect, Resource *resource = DefaultResource::get());
    EffectInstance(Effect *effect, Value *value);

    /// Return the effect being applied.
    Effect *getEffect() const;

    /// Return the value the effect is applied on, or nullptr if this is
    /// effecting an external resource instead.
    Value *getValue() const;

    /// Return the resource that the effect applies to, or nullptr if this is
    /// effecting a value.
    Resource *getResource() const;
  };

OK that seems promising. But I'm not sure I understand how this all fits together with the interface proposed in the original email.

For example:

def LoadOp : My_Op<"load", [SideEffects<"SideEffects::Read">]> { … }
def StoreOp : My_Op<"store", [SideEffects<"SideEffects::Write">]> { … }

This traits is at the operation level and does not include informations about the instance.

The SideEffectOpInterface exposes a `template <typename Effect> Effect *getEffect();` method, and it isn't clear what the template is here, I would just expect something like an EffectInstance.
Changing it to EffectInstance is fine. Or just having `hasEffect`.
 
 

I haven't thought about an implementation for the resource identifier, but it would indicate if the effects applies to a given operand, result (in the case of alloc for example), or global (this does not have to point to an SSA value or a symbol, it can be a domain specific lattice: for example "<gpu:shared_mem>"). 
What I had in mind is that you can either have an operand or result, for the exact reasons you mention, but also a `Resource`. This is a user defined class that acts as a sort of abstract global entity. There would be a default resources with conservative properties, e.g. for modeling things like ExternalMemOnly.  Example definition of a resource:

struct GPUSharedMem : public Resource::Base<GPUSharedMem> {
  /// Return a string name of the resource.
  StringRef getName() final { return "<gpu:shared_mem>"; }
};

  /// Returns the set of effected resources.
  void MyOp::getEffectInstances(SmallVectorImpl<EffectInstance> &instances) {
    // MyOp reads from GPUSharedMem.
    instances.push_back(EffectInstance(SideEffects::Read::get(), GPUSharedMem::get()));
  }


3) Sub-resource granularity access: at some point we may want to model more granular access. A write to a subset of a memref argument can touch a small subset of the memory. I don't see how this granularity access can be hard-coded in the interface, it would have to be specific to the domains and the resources that are manipulated. Also different analysis could provide different representation for sub-resource access description (for example in the memory domain a polyhedral analysis could provide affine maps describing polyhedra, an interval-based representation could limit to hyper-rectangular approximation).
I agree. This is the aspect that I wanted to push a bit further so that we could discuss this as its own thing. There is a lot of prior art for this, and it would be nice to really nail a representation for this. 

I'm actually wondering if this can't be handle in the opaque "resource" so it can get extended. But the interface right now does not model operands as resources.
The intention is to handle it in the opaque "resource", though I don't understand what you mean by "model operands as resources". IMO an operand is an instance, or a reference, to a resource. It doesn't model the resource itself. The intention is to model all of the connecting behavior in the Resource class, but I'd rather not try to design a full TBAA like abstraction as a starting point.

-- River

Mehdi AMINI

unread,
Dec 12, 2019, 3:14:49 PM12/12/19
to River Riddle, MLIR
I was thinking about purely non-overlapping effects (for instance locking and unlocking a mutex, opening/closing files, etc.).
But thinking more about the concept of domain, we may not need to model this behind a single global "SideEffects" interface and instead have one interface per what I called "domains".
Are you comfortable naming the current proposal (and interface) "MemoryEffects"?
What I meant by "model operands as resources" is that your straw man API has side-by-side:

    /// Return the value the effect is applied on, or nullptr if this is
    /// effecting an external resource instead.
    Value *getValue() const;

    /// Return the resource that the effect applies to, or nullptr if this is
    /// effecting a value.
    Resource *getResource() const;
 

For example if the effect is affecting a memref passed as an operand, the getResource() returns nullptr. So I don't see where you would attach the information about the sub-region of the memref that is read/written.

River Riddle

unread,
Dec 12, 2019, 4:09:05 PM12/12/19
to Mehdi AMINI, MLIR
+1 from me.
It depends on how we model resources on values. I was going back and forth on whether to let the specific op specify the resource, as opposed to letting some TBAA like registry explicitly know that `Type A` corresponds to `Resource Foo`. The only benefit of always specifying the resource is for the cases where the resource on a specific type is dependent on the operation processing it. That makes sense for "opaque" types, but it wasn't clear to me how prevalent/how much we should support it given that defining types in MLIR is easy.  

-- River
Reply all
Reply to author
Forward
0 new messages