LLVM Discussion Forums

[RFC] Allowing Dialects to relax the SSA-dominance condition

I am not sure what you mean or how to connect this to the current discussion. We always tried to preserve the dominance definition even in a Module region.

Today I don’t believe so: it is just OK for MLIR to DCE the ^false block at the moment, it is unreachable.

What I’m saying is basically that cycles in SSA graphs are inherent to the existing case that LLVM and MLIR are trying to solve for. It is already incorrect to write code that assumes they don’t exist, except in the narrow case where the code is run in a context that knows no unreachable blocks exist.

I mentioned this in response to one of Sean’s comments above, but a bigger thing I’m trying to put forward here is that cycles are already part of SSA graphs, and dominance isn’t all that it is cracked up to be :-). That’s one of the reasons why I think that generalizing MLIR to support cyclic graphs natively (without regressing its support for the existing flow cases) makes a lot of sense.

-Chris

When building a general framework like LLVM and MLIR, the only thing you can define at a global level is “what passes the verifier”. In general, if you have code that introduces invalid IR, that is a bug - even if no one notices because something deletes the code before anyone notices.

That said, even with that there is wiggle room: within a pass, you’re allowed to cheat and create invalid IR. For example, you can null out operands, rearrange operations in invalid orders etc, the verification rules are there to ensure composability, and a consistent overall design.

-Chris

Yep, this is an interesting question and gets directly at @rjmccall’s point about front-end use of MLIR. Another directly relevant example is multiple entry points in Fortran functions. LLVM has never modeled this well, but MLIR could do this directly with something like you show above.

All of this boils down to “I think it makes sense for operations to turn off dominance checking within their region operands”. If you do that, you’d have to write custom verification code if you value something-like-dominance, but that flexibility is one of the things that makes MLIR really great.

-Chris

I don’t think you really addressed my concern, (which is somewhat independent of the original discussion) Today the verifier behavior is to “issue an error for used values in a CDFG which are not previously defined”. Is this a fundamental error, which should be changed to issue an “error for values used in a CDFG which are not previously defined AND are guaranteed to be reachable”.

My concern is that no pass can ever be sure that it has done ‘everything it needs to’ in order to ensure that its output passes the verifier. There seems to be something very subtle here, which is maybe avoided in practice because degenerate cycles in the dependence graph are almost always in blocks which ‘quickly’ (inside a single pass) become obviously unreachable and are removed.

Hi Stephen,

I think two concrete things should be done here:

  1. The existing dominance check in the verifier should be gated on whether or not the block is reachable from the entry block of a region, just like the equivalent LLVM check is. The dominator API currently used by the verifier already supports this query.

  2. We should introduce a new operation trait, either something along the lines of “MyRegionsCareAboutDominance” or 'MyRegionsDon’tCareAboutDominance" which gates the same check. The former is a lot more pure, and composes better with unknown operations, the later is less invasive.

-Chris

@clattner I fully understand the second point, and would like to have it. But why reachability is important when the attribute MyRegionsDon’tCareAboutDominance
is not set?

Dumitru

But coming back to the earlier question: doesn’t LLVM’s choice of returning true for anything dominating an unreachable use cause other second order issues like the following one: Consider nodes A, B, U where U is in an unreachable part (from entry), and A, B are in reachable parts such that neither A dom B nor B dom A. Now, LLVM’s properlyDominates will say A dominates U and B dominates U, and now you have a situation where A and B both dominate U but neither A dominates B nor B dominates A: this is a contradiction in a dominator tree. You wouldn’t have had this situation in the reachable parts (which we care about more?) if you returned false (based on reachable paths). Although dominance could be considered undefined in general on unreachable parts, is there a rationale for siding with “always return true” for dominance on unreachable uses? (Do point me to if this is documented/described somewhere in comments/other threads.)

Untangling the double negative: If the “MyRegionsDon’tCareAboutDominance” attribute is unset, this means the region does care about dominance.

This gets to the points I was making up thread - dominance is not defined in unreachable regions. Perhaps a different way of saying this is that the dominance checks need to themselves be aware of operations in unreachable regions.

Yes - a better way to model this is to have the “dominates” checks return tri-state: “yes, no, unreachable”. This was never done in the LLVM IR dominance APIs, but it would make a lot of sense to do that in the MLIR APIs, and it would also make sense to fix/upgrade LLVM’s.

-Chris

This has been implemented in the following diffs:

https://reviews.llvm.org/D79922
https://reviews.llvm.org/D80358

1 Like

Awesome! Thanks for implementing this. Glad we found something that is not too intrusive. This is powerful functionality for the infra!

Thank you for driving this Stephen!

The second patch LGTM as a step. The primary problem with it is that it won’t work with MLIR files that don’t have registered ops. To fix this, we need to either:

  1. invert the polarity of the flag - making dominance checking “opt-in”, or
  2. Have specific “verbose” syntax for unregistered ops that reflects this property, and a bit in Operation that tracks this (because the trait won’t exist if the op isn’t registered).

The discussion about the tradeoffs of these are involved, so I think it makes sense to land this patch (unregistered ops aren’t super critical IMO), and debate the best way to solve this in this thread. I’m curious to know what other folks think about this.

I considered making it opt-in, but it would be a much more invasive change to existing dialects. I see this as a stepping stone at the moment, which might allow us to make the more invasive change with confidence after gaining some experience using this trait. I hadn’t thought about the problem of unregistered ops… i’m a little concerned that adding syntactic representation of this leads to a slippery slope. We actually have a nice syntactic representation of this property (and all other dialect properties in fact!): it’s called the registered dialect! I don’t think we want to start shoving all the information about a dialect into each op in the textual syntax.

I rather spend the time now to make it right than landing as is, otherwise I’m afraid we won’t spend the time to fix it (and in particular when nothing is blocked on this upstream as far as I know, which does not provide any sense of urgency for this patch right now: you can keep it downstream).

About unregistered ops: we have been very consistent about always having a “safe” way of interpreting the IR without registering operations, so this would be a significant departure.

Some of the things about this patch that likely deserve some answers (not everything need to be addressed, but I’d rather at least have a plan):

  • what is the status of the passes in MLIR? (What would break when there is a DominanceFreeScope?)
  • Are we gonna update the infra and the passes to check for this property everywhere upstream? The conversion framework expects operands to be visited before we convert an op for example.
  • There is the syntactic/structural property of dominance that you relax here, piggybacking on the “unreachable blocks” relaxed semantics. However the definition of a basic block is that operation are executed in sequence: I am not sure what are the implications about this?

Are you arguing that this should be opt-in, and the default semantics of unregistered dialects does not require dominance? Or are you argument for Chris’s idea to represent the property syntactically in unregistered ops?

I haven’t stressed this yet. I expect that the pass infrastructure might have a few kinks that need to get ironed out. I expect that most core passes (like canonicalize) would have reasonable interpretations. Rewrite systems have been built in other frameworks with similar graph structures without requiring dominance, so I think that this can clearly be supported, even if the current implemation does not. Personally, I’d rather see this developed in tree, rather than outside, but this is
a reasonable concern, I think.

I see this slightly differently. I see the implementation as being very similar for unreachable blocks and DominanceFreeScope to be very similar, but I think they are semantically very different. One deals with a property of CDFGs which allows for verification to happen on code which has not had obivously unreachable code removed. The other is a property of certain semantic models. One thing that bothers me quite a bit is that MLIR often has an implied abstract semantics, or semantic requirements on models, but these are informally specified. There is no direct way for a dialect to specify semantics other than lowering to something else which is probably equally informally specified. I see this as a big whole and without more detailed description of some concepts,even basic things like ‘sequential’ it all seems like a bit of a house of cards.

I wasn’t expressing a preference on the way to solve this. My argument was just that we have spent a large amount of time trying to make the system work for unregistered ops (which may be a registered dialect, some of them allow unregister ops) in a conservative way, and while continuing this route is not something set in stone I would prefer that we don’t deviate too easily.

Looking back to the RFC from last year, it seems that we settled to not change the default and rely on an attribute instead of a Trait like you propose here.

We propose to introduce a new unit-type attribute in the standard dialect: std.noncfg. In the absence of this attribute on the enclosing operation, the region is assumed to be a CFG. We consider this as a pragmatic choice: CFG-based representation are pervasive and making it the default seems sensible. In the future we may consider adding an enum attribute (or a string attribute) to record specific type of regions as needed. For instance if/when we get to a point where the GPU kernel representation requires different semantics (around convergence for example) than the traditional CFG, we could introduce a SIMT or SPMD region kind.

Have you thought about using an attribute?

Right: my concern isn’t that it would not be possible, but just trying to understand the plan. For example: are we just gonna add this trait and stop here until someone volunteer to make it work or are we gonna actively try to make it work in every components?
And it is perfectly fine IMO to develop all this incrementally in-tree, as long as we have some consensus here the general direction/plan.

Yes, I didn’t mean that these are the same, in fact I was trying to point that while the mechanism of the patch is the same there is a semantic difference indeed! (which is what I was trying to express with the “sequential” execution). Basically in a very general way, I’m looking into what kind of change should we look for under https://mlir.llvm.org/docs/

That’s an interesting discussion to have, but I’m afraid to derail the thread here :slight_smile:

No… (going back and rereading the old thread again) It didn’t seem like there was consensus on that. An attribute seems awkward to me since for registered dialects it seems already part of the op type, so why spend the storage to specify it again?

The option I considered the most was to make DominanceFree be the default and Dominance be an opt-in property specified by an MLIR Interface. This Interface would then support Dominance queries, rather than having users that care about DominanceInfo creating it directly. To me this a clean structure where it’s easy to find out where users are that care about Dominance. In this case, unregistered dialects would have operations with DominanceFreeScopes, so they would inherently be valid, but without additional syntactic representation, Dominace violators would not be detected.

Going back and thinking on these lines… should the generic format for operation be required to contain a syntactic representation of all Traits? could Traits for unregistered operations be represented dynamically (perhaps as additional trailing objects) while Traits for registered operations could be elided in the runtime object representation?

My plan is to continue to develop this, but I can’t offer a detailed timeline. We are committed to determine how MLIR can be used for hardware design and this seems like a key enabler.

Responding to a few points:

  • Waiting for River to return makes perfect sense.
  • I don’t think it should be a requirement to enumerate all of the passes and audit them. It is not the case that all passes work with all IR: There are lots of invariants that are expressible in MLIR dialects that could be perturbed by existing passes; this would be no different.
  • I don’t think it makes sense to use an operation attribute for this - this is a core aspect of how an operation works, it isn’t something that can be toggled on a instance-by-instance basis.

We discussed this up-thread, but the “pure” and correct way to handle this is to make dominance checking opt in with a trait. Dominance checking is another invariant that ops with regions may have, and making it opt-in ensures we get the right behavior for unregistered operations etc - recall that unregistered ops have a LOT of missing verification checks.

In any case, I think it makes sense to continue the discussion when River returns.

-Chris

Sure: the idea wasn’t to toggle it per instance, but an operation builder can always set this attribute, and the operation verifier can force this attribute to always be there.
The alternatives we saw were to either change the default (which we thought would face strong opposition at the time) or change the grammar to have some sort of region tag

I agree that a lot of passes don’t have to make sense in such a region, they would mostly be just taught to ignore these regions. And to be clear: “audit all the passes” is extreme, I’m not suggesting to do this.

What I had in mind is more taking one or two examples of passes to think about the kind of patterns/queries passes are making that would break after. The motivation being to get some insights that can generalize: I don’t see each individual pass as being interesting, but maybe just helping building some sort of taxonomy about what would/wouldn’t work in these new regions. For example would the block ordering make sense? Would we assert that passes don’t use the block ordering in these regions?

There are also more central piece of infrastructure than individual passes (for example things like DRR and the conversion framework).

And we don’t need to have the answer to everything and figure to the plan for the entire world, but it still seems good to me to look a little bit into this kind of things (even making the unknown explicit is valuable like “XYZ would have to be updated, we don’t know how yet but we’ll figure out when we get there”).

With the attribute we went with opt-out to favor the common case (CFG), but that was because an attribute is more intrusive than the traits. In terms of passes/code in general, no matter how we store the information (attribute, trait, new bits on the region, etc.) we’d have to insert checks for it everywhere I think.
So the only “extra cost” of making it opt-in with the trait is that we have to annotate all the current operations with regions instead of annotating the one that want the non-strict dominance, right? (we likely can hide most this in ODS anyway)
Any other drawback I miss?