GetMemberOp verification failure on recursive types

[gitoleg]

Let's discuss recursive types again.

The long story short - I have a verification failure in the GetMemberOp: index out of bounds.

The code to reproduce is the following:

typedef struct SomeStruct {
    struct SomeStruct* prev;
    struct SomeStruct* next;
    int x;
} A;

typedef struct {
    A some;
} B;

void foo(B* b, A* a) {    
    a->x = 42;     // <---- getMemberOp failed
}

Note, if we swap arguments as foo(A* a, B* b) everything will be fine.

I spent a huge amount of time trying to understand the reason ( what is probably bad for me :) )
And what I came to is approximately the following.

First of all, the CIRGenTypes.cpp and CIRRecordLayoutBuilder.cpp have a similar implementation to one in clang/Codegen. But the behaviour is different. I'm sure that the difference caused by CIR StructType implementation and by the fact that instances of llvm::Type counterpart are stored by pointer and are mutable.
For example, this is how the type is updated in the CGRecordLayoutBuilder :
Ty->setBody(Builder.FieldTypes....
And how it's done in CIR:
*Ty = Builder.getStructTy(builder.fieldTypes, ... ,
i.e. we create a new instance of mlir::Type here. This is matter for the TypeCache in the CIRGenTypes: the type entry is stored by value. So when we create a new instance - nothing is reflected anywhere.

As I said, once we swap foo's arguments, everything will be fine - i.e. it depends on order in which we create types and recursively traverse them.

There are several solution I can think of:

1. relax the verification - may be it will help, since my test code worked with the StructElementAddr before, where no verification was used.
2. add kind of a mutability in StructType, so we will be able to actually change something during the recursive calls of ConverType. Also we will need to be careful with passing types as arguments, i.e. pass them by reference.
3. Something else, e.g. don't cache incomplete types.

So.. what thoughts do you have? May be it's a known issue and the answer is simple one?

[sitio-couto]

Hey @gitoleg,

Let's discuss recursive types again.

Let's! 😆

So.. what thoughts do you have? May be it's a known issue and the answer is simple one?

I've been thinking about how to deal with the self-reference issue and I haven't found a simple solution, but it would be nice to have someone to brainstorm with!

To see if we are on the same page, my understanding here is the following (I'll refer to SomeStruct as A):

• Function uses A* triggering its codegen
• Type for A is recursively created:
  • struct *A is visited in A's body while the A type is still incomplete
  • Therefore, the type for A* is then cached as incomplete (!cir.ptr<!cir.struct<struct "A" incomplete>>)
• Once the visitation for A is over, the function can get it's A* type.
• However, A* was cached while the A type was still incomplete
• So the function sets its second argument as it was found in the cache:

!cir.ptr<!cir.struct<struct "A" incomplete>>

Since A is already a complete type at the point where it is used by the function, the second argument should not be incomplete. In other words, this is not the expected behavior.

1. relax the verification

Actually, this should already be the case. @bcardosolopes requested me to do so when I implemented getMemberOp, but reading your issue I realized I didn't do it correctly! I'll submit a patch for it.

2. add kind of a mutability in StructType

I do not think this is feasible. Types in MLIR are immutable, so updating a type attribute would simply generate a new MLIR type. As a consequence, types that have already been defined (e.g. !cir.ptr<!cir.struct<struct "A" incomplete>>) will not be updated.

3. Something else, e.g. don't cache incomplete types.

About not caching incomplete types, I think it could work, but there might be too many corner cases. When caching pointers, for instance, we would have to avoid pointers where the pointee is an incomplete type. Handling these particularities might end up not being a scalable approach both in terms of performance and code maintenance.

My Current Idea:

When a named CIR struct is not the outermost type, it should be referenced, not expanded. For example:

!SomeStruct = !cir.struct<struct "SomeStruct" {!cir.ptr<!cir.struct<"SomeStruct">>, !cir.ptr<!cir.struct<"SomeStruct">>, !s32i}>
!cir.ptr<!cir.struct<"A">>

This should, in theory, allow us to hold a symbol table where we can lookup the struct by name. In this case, if the complete type of a named struct is found, we can mutate the symbol table entry, ensuring that type checks are made using the struct type's complete version. This should be relatively cheap and fairly generic.

Although there might be issues that I'm just not seeing yet. At the MLIR level, for instance, we might need this struct symbol table for diagnostics, but I'm not sure if we would be able to recreate it.

[gitoleg]

I'll submit a patch for it.

That would be awesome!

[bcardosolopes]

@gitoleg thanks for pushing into this discussion. BTW, @sitio-couto just landed a fix that relaxes the verifier for now.

When a named CIR struct is not the outermost type, it should be referenced, not expanded

I like it, and it looks clean!

[sitio-couto]

@bcardosolopes I was giving more thought to this idea and I found a fatal flaw in it: if the type is only referenced and never explicitly used, MLIR will not generate it. But I think I have a solution in mind now.

@gitoleg suggested adding a "kind of mutability in StructType", to which I wrongly answered saying that "types in MLIR are immutable". It is actually possible to have mutable attributes and types in MLIR.

This greatly simplifies things since we can update cached incomplete types in place, replacing all their references with complete types (if there is one). The downside is that we can't use tablegen (yet) to enable this feature.

I'll see if I can implement this until next week!

[bcardosolopes]

@bcardosolopes I was giving more thought to this idea and I found a fatal flaw in it: if the type is only referenced and never explicitly used, MLIR will not generate it.

This is usually fine, can you share the example that bothers you?

@gitoleg suggested adding a "kind of mutability in StructType", to which I wrongly answered saying that "types in MLIR are immutable". It is actually possible to have mutable attributes and types in MLIR.

I'm against this approach, my understanding is that this should be used with specific targets, meaning usually one param or another that doesn't become part of uniquing inside an attribute or type. We certainly don't wanna lose the uniquing we get for free and implement our own. What are your plans here?

I believe we have two distinct problems here: (a) updating the codegen cache (b) updating the types. It's totally fine that we can create new types and replace older ones (e.g. incomplete) in (a), even if that requires some sort of recursive RAUW when doing (b).

[sitio-couto]

@bcardosolopes

can you share the example that bothers you?

struct A { int i; };
struct B { int j; struct A val; };
void func(struct B* ptr) {
  B->j = 0;
}

Since the type struct A is never explicitly used, we might be left with a reference to !cir.struct<"A"> that doesn't actually exist in the CIR code.

We certainly don't wanna lose the uniqueing we get for free and implement our own. [...] What are your plans here?

I don't think we need to worry about this. Uniqueing of named structs is trivial: just use the struct's name. For unnamed structs, we can use the members as immutable parameters. The LLVM_StructType is implemented this way, so it can serve as a reference.

I believe we have two distinct problems here

I supposed so, but my point is that mutating types in-place will solve (b) and (a). Solving (b) will have no effect on types that are already being used by operations in the module being built.

we can create new types and replace older ones (e.g. incomplete) in (a), even if that requires some sort of recursive RAUW when doing (b).

This is a bad idea, I think. The RAUW here cannot operate on types AFAIK, so it will have to replace all operations that use the old types. It seems detrimental to both performance and code maintenance.

[bcardosolopes]

Since the type struct A is never explicitly used, we might be left with a reference to !cir.struct<"A"> that doesn't actually exist in the CIR code.

Thanks for the example. That's odd, I'd expect any underlying type to get the full package. Did you actually run into that while implementing stuff or is it more speculation?

For unnamed structs, we can use the members as immutable parameters.

Sweet, that indeed makes it more palatable.

I supposed so, but my point is that mutating types in-place will solve (b) and (a).

Indeed. Avoid some of my previously mentioned problems for sure.

[sitio-couto]

Did you actually run into that while implementing stuff or is it more speculation?

It's more of a speculation, though I did a test to see if that would be the case: If you roundtrip a CIR code through cir-opt, any type that is not explicitly used is dropped.