[RFC] Making `LLVMStructType` immutable

MLIR
1

Motivation

Prior to the switch to opaque pointers, LLVM’s type system used to be recursive. A linked list may e.g. be implemented as %node = { %node*, ... }. With opaque pointers this is no longer the case, as pointer types no longer have an element type. Directly recursive struct types such as %foo = { %foo } have also never been allowed which is verified eagerly since https://github.com/llvm/llvm-project/commit/4831e0aa88debb3b7d0528bfd85db73a6a03aeff

To support recursion the LLVMStructType required to be mutable (to be able to first construct the type before then using it within its own body using a setBody method).

As the support for mutable types in MLIR is immature compared to immutable types and requires a lot more complexity, this RFC proposes to switch the struct type to be immutable instead.
Please see the PR implementing the RFC here: [mlir][LLVM] Make struct types immutable by zero9178 · Pull Request #116035 · llvm/llvm-project · GitHub
Note that lines changed currently consist of 195 added and 1110 lines removed.

A similar discussion for LLVM proper has occurred here: Recursive types - #4 by nikic

Semantics changes

One affordance it being a mutable type gives us is the ability to autorename structs: One could use LLVMStructType::getNewIdentified which would be guaranteed to have a unique name within the MLIR context.
Implementing this with immutable types is much more difficult and I believe redundant.

Instead, this RFC proposes making the name a normal type parameter that is part of uniquing as any others. Two struct types are then considered equal if both the name and the body matches.
This retains advantages of named structs from LLVM:

  • We retain type inequality between two structs with the same body but different names.
  • Structs remain more readable thanks to being able to be named.

Unlike LLVM IR, two structs may share the same name (e.g. struct<"foo", ()> and struct<"foo", (i32)>).
These would nevertheless not be considered equal in MLIR and will get assigned unique names once exported to LLVM IR.
Besides readability, I am not aware of any issues with allowing this case.

API Changes

Care has been taken to make sure as many of the APIs remain compatible as possible to reduce downstream breakage.
Nevertheless, due to the semantic changes, some APIs had to be changed or removed instead:

  • getIdentified, getIdentifiedChecked and getNewIdentified have been removed in favour of the more conventional get method.
    getIdentified, getIdentifiedChecked would previously create structs with empty bodies that could be set later. getNewIdentified would assign a unique name to the struct.
    Neither functionality is supported once struct types are immutable.
  • setBody and isInitialized are no longer supported as the type is now immutable.

Corresponding C APIs have also been removed.

Out of scope changes

Following changes may be done or discussed in the future but are out of scope for this PR:

  • Removing opaque structs. I believe these no longer have any uses with opaque pointers as well.
  • Removing named structs. This could theoretically be done and literal types used everywhere.
    I don’t see great motivation to do so.

CC @gysit @Dinistro @definelicht @Mogball @bcardosolopes @nikic

6 Likes
2

I think this part is problematic. The “charter” of the LLVM dialect is to reflect LLVM IR. If something is supported by the LLVM IR, in this case renaming, we should also look for supporting this in the dialect somehow. That being said, this is only a one-way requirement. We may (and actually do) have something more general in the dialect assuming trivial, implicit and unambiguous translation is possible. Though I’d prefer to keep differences to a minimum to avoid cognitive load.

To make progress on this, please consider how importing from LLVM IR would operate, in particular in presence of multiple LLVM IR modules with named structs in them that are being placed into one MLIR meta-module, there is a use case of that in, e.g., some Polygeist workflows.

cc: @wsmoses

3

Thank your for your comment!

I think this part is problematic. The “charter” of the LLVM dialect is to reflect LLVM IR. If something is supported by the LLVM IR, in this case renaming, we should also look for supporting this in the dialect somehow. That being said, this is only a one-way requirement. We may (and actually do) have something more general in the dialect assuming trivial, implicit and unambiguous translation is possible. Though I’d prefer to keep differences to a minimum to avoid cognitive load.

I believe this is a fair criticism. Note that we don’t currently support renaming (i.e. setName) the way that LLVM IR does, but rather only setting the body (via setBody).
The later might be removed in LLVM IR soon according to Recursive types - #4 by nikic and I don’t mind waiting for that or pushing that change myself if you feel that is necessary.

Allowing structs with identical names I see as an inherent limitation with immutable types as it is difficult to implement the renaming mechanism. I believe the current approach to be a good compromise as it is semantically more permissive and a superset of the semantics of LLVM IR proper that imports and exports with identical execution semantics.

To make progress on this, please consider how importing from LLVM IR would operate, in particular in presence of multiple LLVM IR modules with named structs in them that are being placed into one MLIR meta-module, there is a use case of that in, e.g., some Polygeist workflows.

When importing one LLVM IR module, all struct types are guaranteed to have a unique name. The corresponding struct types in MLIR will therefore also have unique names and semantics identical.

In the multi-module case, the difference that may occur is that both modules may have structs with the exact same name and bodies. If one were to merge in LLVM IR, these would get renamed to preserve nominal type inequality. When merging in MLIR with immutable structs, the two struct types would be seen as identical types and have type equality. When exporting back to LLVM IR this would make the types more permissive (via merging), but execution semantics preserved.

I’d love to hear more if you think this could break things anywhere in e.g. Polygeist or elsewhere

4

Thanks for implementing this patch and writing up the RFC.

Mutable attributes are not well supported in MLIR and for the debug info representation a lot of effort went in working around them. I am thus in favor of simplifying the struct type despite the small semantic difference. Of course we should make sure this does not break existing use cases (e.g. in Polygeist).

If one were to merge in LLVM IR, these would get renamed to preserve nominal type inequality. When merging in MLIR with immutable structs, the two struct types would be seen as identical types and have type equality.

I believe it would be possible to implement LLVM’s merging behavior in MLIR using attribute walkers to rename conflicting struct types in a nested module. However, maybe this is not even needed if name conflicts are acceptable.

1 Like
5

Seems like overall goodness, nice!

From ClangIR perspective on LLVM lowering I don’t see any fundamental problem with this approach.

7

I would love to get rid of attribute and type mutability in MLIR in general. It’s not well-supported as observed, but I don’t see it being used very often. While we can support a “rename” by performing a recursive type replace, that’s considerably more expensive than just swapping the string pointer inside the singleton type instance.

While I think the LLVM dialect should model LLVMIR, does that imply the LLVM dialect should also model the same modifications you can make to LLVMIR? It’s not clear to me whether it’s necessary to support an O(1) struct rename in MLIR.

8

ClangIR uses mutable types for structs, which is a natural way to support recursive and mutually recursive types. [CIR][CIRGen] Support mutable and recursive named records by sitio-couto · Pull Request #303 · llvm/clangir · GitHub is the PR that switched to that and explains the benefits compared to the previous solution not using recursive types.

9

+1 for not getting rid of mutable types. They are also used in FIR in flang because Fortran derived types can also be recursive and when working with the IR at the language level, having opaque pointers would be cumbersome.

1 Like
10

Yeah, I meant autorenaming on conflict specifically, not changing the name.

(Not) allowing is the right way to think about this. Can we disallow that through verifiers somehow? We don’t have to make such pairs of types impossible to construct.

There’s also a stupid solution of documenting one is not supposed to create such conflicting types and have a check in the constructor ifdef-ed by the “expensive checks” flag. The check would, under lock, iterate through all known types and see if creating the new type would conflict, asserting if it is the case.

The use case I have in mind is putting a C++ attribute on a type and using that fact to make assumptions about the type. Along the lines of what @chelini presented at the last dev meeting. This usually boils down to have a set of type objects for which the assumption holds and checking for set inclusion. The very specific example I have is marking certain types as “values of this type can never be active” for the purposes of activity analysis during automatic differentiation (Polygeist+Enzyme combo) that merges multiple modules to have a global view of the program, where it would be highly undesirable if such a type would inadvertently merge with another type for type comparison reasons, values of which have no such guarantee, leading to correctness issues.

Admittedly, this is a peculiar edge case, so I won’t demand that everybody in the community bends backward to support it. We can find a workaround. But I would much prefer there to be a clear warning that something is wrong with my usage of MLIR and my intuition as to how the LLVM dialect operates given prior exposure to LLVM IR, as opposed to the LLVM dialect silently doing the wrong thing for me.

This is beyond the scope here. If you see issues, please report or fix them.

11

Hello! To give a quick update on the status of this RFC: I thought about the cost-benefit of the change more and decided for now to try and implement as many of the benefits of immutable types (mainly around ODS support etc) that were mentioned above as possible while still having the type be mutable.
Partly to make the comparison of the fairer in terms of LOC but also to not be blocked on what is a much larger and controversial change. Two of these have already landed: [mlir][LLVM][NFC] Move `LLVMStructType` to ODS by zero9178 · Pull Request #117485 · llvm/llvm-project · GitHub and [mlir][LLVM][NFC] Implement `print/parse` for `LLVMStructType` by zero9178 · Pull Request #117930 · llvm/llvm-project · GitHub. In the future I’d like to also be able to move as much printing and parsing into ODS as is possible (escaping to custom otherwise).

I personally still think that making struct types immutable would be ideal in the future, but also sympthazize with the fact that this would diverge from LLVM quite a bit. I think It’d be a no-brainer if LLVM were to change or culture around the use of struct types.

12

Hello,
we’ve been developing an mlir-link tool and when implementing linking for the LLVM dialect we ran into the LLVMStructType uniqing across modules. Modules containing two struct type with same names but different bodies cause a collision and trigger an error (when loading them into the same context). If I understand this correctly, this RFC would solve that, since the body of the type would participate in the uniqing, is that right? Is there a plan to move forward with this in the forseeable future? Or should we look into different ways of resolving the collision and consequent error?

2 Likes
13

We may want to see which direction does LLVM IR take: Recursive types - #9 by nikic.

14

This RFC would solve that but is not necessarily the only solution. Working around it within your tool is probably the best solution.
One could potentially conceive some scoping mechanism which would benefit all mutable types and attributes, but that’d be another RFC unrelated to making structs immutable.

I agree with Alex right now that we probably want to track what LLVM is doing for now.

1 Like
15

I think with regard to type immutability on the LLVM IR side, there are two parts here:

  • Ability to change the body of a struct after it has been created. This is something we’d like to get rid of, but it’s fairly hard to make it a reality. As we no longer support recursive types, I also consider this an implementation detail of the LLVM API: It only affects how you can construct IR, not what the final IR can look like. As such, I think that MLIR should feel free to not support this.
  • Having a notion of identified, non-uniqued struct types. I think that as long as we have a notion of named structs at all, I would expect these to not be uniqued based on the name+body combination, as this would somewhat defeat their purpose (it would not be possible to reference them by name alone). LLVM handles name clashes (primarily during IR linking) by adding .0 style suffixes to type names (and then trying to reduce redundant types that are actually isomorphic). I expect that eventually we will be removing the notion of named structs entirely, simply because they are becoming increasingly useless over time (the getelementptr → ptradd migration will remove one of the main places they are still being used).
3 Likes
16

One would need to replicate this mechanism, likely by hacking the dialect type parser which isn’t possible downstream (it’s already possible to force MLIR to suffix names when calling dedicated type constructors, just not the default get). I’m curious to see suggestions…

17

As in there is a generic mechanism in MLIR for this? I have only been aware of the LLVMStructType::getNewIdentified but that always creates a new identifier, even if a deduplicated type with the same body already exists.

I have an experimental solution (modifying the parser) that just goes through all the candidates for name deduplication and checks if the bodies match - basically copying the idea of getNewIdentified but relaxing the check here. If it does not find an already existing type with a matching body it creates a new type with a properly suffixed name. I think that it should work in principle, but I’m aware of two main issues:

  • It does not fail on malformed modules containing two types with the same name but different bodies. I’m not sure if it would be possible to handle this in the parser.
  • As it does not remember any state it always goes through all the candidates. It should not impact the single module case (unless there is a conflict in names, which is a malformed IR), but in the case of more modules it does string comparisons on the names every time the occupied name is encountered. And that happens every time a conflicting type is encountered in the additional modules. Handling this in a lightweight way seems quite challenging

We’ve also had another idea but it would consist of non-trivially modifying how the struct type is being handled:
Having something like a LLVMNamedStructDefOp that would define a symbol with the name of the type and contain the body. Then any op using the struct type could just have LLVMNamedStructType<@name>. Since the symbol table is attached to each (sub)module, it should refer to the correct defining op. This solution would remove the requirement to handling cross-module duplicates while parsing (and would move the workload to the tool, if it needs to join the modules). It would also mimic more closely what LLVM does as it also defines the named structs at the top of the module.

2 Likes
18

We are now also running into similar issues when loading multiple modules into the same MLIR context. The fact that the IR parser fails even before attempting to combine any modules is problematic. While I understand that linking modules together into one has the requirement of unique struct names, this should not be enforced on a context level.

As a concrete example: Parsing the following modules after each other into the same MLIR context is not possible.

module @mod0 {
  llvm.func @a(%ptr: !llvm.ptr) {
    llvm.load %ptr : !llvm.ptr -> !llvm.struct<"a", (i32)>
    llvm.return
  }
}

module @mod1 {
  llvm.func @b(%ptr: !llvm.ptr) {
    llvm.load %ptr : !llvm.ptr -> !llvm.struct<"a", (i64)>
    llvm.return
  }
}

While I understand a certain desire to stay in line with what LLVM IR allows, sacrificing multi-module support for this seems a bit extreme. Therefore, I would prefer to push @zero9178 's implementation forward and, if we really want to, add an isolated verification step that checks that there are no conflicting struct types.

4 Likes
19

FYI: We implemented a flag for the LLVM to MLIR import that treats all struct types as literal types, i.e., drops their name: [MLIR][LLVM] Add import-structs-as-literals flag to the IR import by Dinistro · Pull Request #140098 · llvm/llvm-project · GitHub

Note that this is a workaround and it only works when MLIR is produced with the aid of the LLVM to MLIR import. If one does not control where the MLIR modules are coming from, this change will not help.