CIR Dialect Struct Type Recursive Reference

[chenghuaWang]

In CIRTypes.td. Struct Type is defined. And it's parameters is shown below:

let parameters = (ins
    ArrayRefParameter<"mlir::Type", "members">:$members,
    "mlir::StringAttr":$typeName,
    "bool":$body,
    "bool":$packed,
    "std::optional<::mlir::cir::ASTRecordDeclAttr>":$ast
  );

You used a Array of mlir::Type(ArrayRefParameter<"mlir::Type", "members">) to figure out the content in a struct type.

But how do I represent Recursive Reference using CIR_StructType? The Recursive Reference will lowring to llvm dialect like code below:

!llvm.struct<"a", ptr<struct<"a">>>  // example of recursive reference

[sitio-couto]

Hey @chenghuaWang,

I believe you can use the same approach as your LLVM example.

In CIR's case, the recursive reference member would be a CIR_StructType with the same name and no members.

For example:

struct S1 {
  int a;
  struct S1 *b;
};

Would generate:

!cir.struct<"struct.S1", !s32i, !cir.ptr<!cir.struct<"struct.S1">>>

But there are a few complications to this approach. Currently, the previous C code actually generates two separate types with the same name:

!s32i = !cir.int<s, 32>
!ty_22struct2ES122 = !cir.struct<"struct.S1", incomplete, #cir.recdecl.ast>
!ty_22struct2ES1221 = !cir.struct<"struct.S1", !s32i, !cir.ptr<!ty_22struct2ES122>>

Before being able to represent self-references in CIR, we will likely have to replace occurrences of incomplete types by !cir.struct<"name"> after the full definition of a struct is found. This would ensure that a name is bound to a single type. I believe this could be done during codegen.

[sitio-couto]

Related to #152

[chenghuaWang]

Thanks @sitio-couto
You mean the !ty_22struct2ES122 type in

!ty_22struct2ES1221 = !cir.struct<"struct.S1", !s32i, !cir.ptr<!ty_22struct2ES122>>

will be replaced by !cir.struct<"struct.S1"> ?

[sitio-couto]

@chenghuaWang that's right!

The !ty_22struct2ES122 is just an alias, so the second type (!ty_22struct2ES1221) is equivalent to:

!ty_22struct2ES1221 = !cir.struct<"struct.S1", !s32i, !cir.ptr<!cir.struct<"struct.S1", incomplete, #cir.recdecl.ast>>>

You could interpret the !cir.struct<"struct.S1", incomplete, #cir.recdecl.ast> as a recursive reference, but it would be better to differentiate an incomplete type from a recursive reference, i.e. to convert the type to:

!ty_22struct2ES1221 = !cir.struct<"struct.S1", !s32i, !cir.ptr<!cir.struct<"struct.S1">>>

[chenghuaWang]

Suppose we have type !ty_22struct2ES1221 = !cir.struct<"struct.S1", !s32i, !cir.ptr<!cir.struct<"struct.S1">>>. And I get the pointer element(!cir.ptr<!cir.struct<"struct.S1">>) from a value who has type !ty_22struct2ES1221. But the pointer doesn't know what struct.S1 looks like.

For example, the following code

struct S1 {
  int a;
  struct S1 *b;
};

// S1.b's type is !cir.ptr<!cir.struct<"struct.S1">>
// after load S1.b to memory, %0 = !cir.load %b, %0 just have a type !cir.struct<"struct.S1">
// So, how to let %0 to know that `a` is its member? 
int c = S1.b->a 

btw, can a type be represented in mlir's IR directly(I'm not quite familiar with mlir, !ty_22struct2ES1221 = !cir.struct<"struct.S1", !s32i, !cir.ptr<!cir.struct<"struct.S1">>> seems can't be represented in mlir's IR)? Or using a symbol to represent it?

dialect.declare_struct_symbol @StructFoo : !dialect.struct<"Foo", i32, !dialect.struct<"Foo">>

[bcardosolopes]

Perhaps one route we could go for is to add a special type !cir.self<"name"> and force cir.struct_element_addr builder to translate the resulting type into the most recent lexical parent struct type or tag with "name" to help with inner structs that are also recursive types.

@sitio-couto your recent work on get_member will break a current testcase that "works" (even though it's wrong) based on this. For instance

struct S1 {
  int a;
  struct S1 *b;
};

int f(S1 s) {
  return s.b->a; 
}

Right now it works because cir.struct_element_addr verifier doesn't check the index bounds. I'm afraid that this will break CIRGen from one important internal testcase (aka big TU), even though we don't use any of this just yet.

[chenghuaWang]

Current cir.struct with imcomplete body seems played same role as cir.self? Seperating struct to two mlir types make it too complex.

And, if we have type ptr<ptr<struct<"foo">>>. When cir.struct_element_addr trying to handle this kind of type, it need to replace the innermost struct type. It may have too many corner cases which will make cir.struct_element_addr hard to impl?

Can we just give a body atteibute to struct type? I'm not sure if the code below can be represented using mlir.

dialect.declare @StructFoo : !dialect.struct <"Foo", i32, !dialect.ptr<!dialect.struct<"Foo">{body=@StructFoo}>>

%0 = dialect.alloca : !dialect.struct<"Foo">{body=@StructFoo} -> !dialect.ptr<!dialect.struct<"Foo">{body=@StructFoo}>
%1 = dialect.struct_ele_addr %0[%idx_1] : (!dialect.ptr<!dialect.struct<"Foo">{body=@StructFoo}>) -> !dialect.ptr<!dialect.struct<"Foo">{body=@StructFoo}>
%2 = dialect.struct_ele_addr %0[%idx_0] : (!dialect.ptr<!dialect.struct<"Foo">{body=@StructFoo}>) -> !dialect.ptr<i32>

The verifier could just lookup the topmost module where dialect.declare op exists to get the full def of struct type.

[sitio-couto]

@chenghuaWang,

It may have too many corner cases which will make cir.struct_element_addr hard to impl?

I do not think there will be many corner cases. IMO, I just see two scenarios: the type being loaded by struct_element_addr either has or hasn't self-references. To solve this, we could:

• Recursively iterate through the type being loaded.
• Identify if a cir.struct is actually a self-reference, and if so, expand it to the full type.
• Avoid recursing into an expanded self-reference to avoid infinite loops.

This should ensure self-references are handled and that MLIR type match works properly. Do you think there are cases where this approach wouldn't work?

Can we just give a body atteibute to struct type? I'm not sure if the code below can be represented using mlir.

I think it is possible to create a workaround as you've mentioned in MLIR, but this approach seems a bit too hacky and complex. Replacing the self-references with the full types can be achieved with a symbol table for named structs, which should be somewhat simple to do.

we could go for is to add a special type !cir.self<"name">

That is an interesting idea. It might avoid more bloat in the current StructType and make CIR code more readable.

@chenghuaWang do you intend to tackle this problem? I was planning to work on this over the next two weeks.

[bcardosolopes]

Current cir.struct with imcomplete body seems played same role as cir.self?

I don't think so, by not using cir.struct we're greatly reducing the scope of that entity might refer to.

Seperating struct to two mlir types make it too complex.

And, if we have type ptr<ptr<struct<"foo">>>. When cir.struct_element_addr trying to handle this kind of type, it need to replace the innermost struct type. It may have too many corner cases which will make cir.struct_element_addr hard to impl?

The way I see it, any reference to the recursive reference must be already be resolved in the final form for the cir.struct_element_addr call.

Can we just give a body atteibute to struct type? I'm not sure if the code below can be represented using mlir.

I'm not convinced by this body approach, IMO it doesn't seem to communicate what's going on and what really CIR is translating from source code.

[chenghuaWang]

@sitio-couto

This should ensure self-references are handled and that MLIR type match works properly. Do you think there are cases where this approach wouldn't work?

Indeed, there are not many scenarios that we need to consider. The scenarios I can think of at the moment are:

struct S1 {
  int a;
  struct S1 **b; // ptr<ptr<struct>>
};

At this point, I think @bcardosolopes proposal

we could go for is to add a special type !cir.self<"name"> and force cir.struct_element_addr builder to translate the resulting type into the most recent lexical parent struct type or tag with "name" to help with inner structs that are also recursive types.

would be a better fit for CIR.

do you intend to tackle this problem? I was planning to work on this over the next two weeks.

I'm afraid I don't have enough time, I have a lot of exams to prepare for at the moment. 😢

By the way, in code link, where you set the result type of cir.struct_element_addr?

[sitio-couto]

@chenghuaWang,

where you set the result type of cir.struct_element_addr?

When calling the builder for the StructElementAddr operation, the first argument is usually the resulting type of the operation, or, in other words, the type of the field being fetched. Take the example below:

clangir/clang/lib/CIR/CodeGen/CIRGenExpr.cpp

Lines 73 to 74 in bb87caa

	auto sea = CGF.getBuilder().create<mlir::cir::StructElementAddr>(
	loc, fieldPtr, Base.getPointer(), fieldName, fieldIndex);

Here, fieldPtr tell us the type of the member that will be fetched by cir.struct_element_addr.

I'm afraid I don't have enough time

I'll try to work on this then! Once I have a PR ready it should link to this issue for you to take a look!

[yugr]

This was probably fixed in #303

[sitio-couto]

Fixed in #303.