[RFC] Translate complex LLVM IR constants to LLVM dialect

[mshockwave]

Problem definitions

Right now, the LLVM IR importer cannot translate some of the complex constants, llvm::ConstantStruct and llvm::ConstantAggregateZero for instance, into LLVMIR dialect directives. For example, give the following type definitions and global constants:

%sub_struct = type {i8, i32}
%my_struct = type {i8, i32, %sub_struct, i16*, i8*}

@.str.8 = private unnamed_addr constant [5 x i8] c"unix\00"
@my_global = global %my_struct {i8 8, i32 7,
                                %sub_struct zeroinitializer, i16* null, 
                                i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str.8, i32 0, i32 0)}

The importer will bail out with an error message: “error: unhandled constant {i8 8, i32 7, …}”.

The problem in this motivating example was three-fold:

1. The importer doesn’t recognize zeroinitializer, which is represented by llvm::ConstantAggregateZero.
2. The importer cannot translate llvm::ConstantAggregate with heterogeneous element types. Namely, llvm::ConstantStruct. Ideally, we should able to translate such concept into ArrayAttr (which actually doesn’t require elements to have same types).
3. Although the importer is able to handle null (i.e. llvm::ConstantPointerNull) and inlined i8* getelementptr (i.e. llvm::ConstantExpr), both of them will be lowered into an operation. Assuming we want to translate the enclosing struct into an ArrayAttr as mentioned in the first bullet point. The existing translation scheme cannot be fitted in (because ArrayAttr only takes Attribute rather than Value). Let’s say we want to go the other way around and reuse existing translation schemes (translate into operations), we will lower the initialization for the aggregate constant into a region. I couldn’t find a proper way to express “per-element” initialization on the aggregate constant in the current codebase (are we going to use llvm.getelementptr to access individual elements and assign operation values to them, which are part of a constant?).

Proposed solutions

I would like to propose several fixes in the LLVM dialect to address these problems. For the first issue, I’m planning to add a new attribute, #llvm.zeroinitializer<ty>, where ty is an aggregate type. In the motivating example above, ty will be %sub_struct.

The second and third issue are more tricky. There are 2 kinds of solutions for them:

1. Adding a new operation llvm.mlir.constant.aggregate that takes LLVMType values as operands and generate a constant with aggregate type. For instance, the motivating example can be rewritten into (some syntax and type annotations has been omitted):

llvm.mlir.global constant @my_global() : !llvm.struct<my_struct> {
  %0 = llvm.mlir.constant(8) : i8
  %1 = llvm.mlir.constant(7) : i8
  %2 = llvm.mlir.constant(#llvm.zeroinitializer<"llvm.struct<sub_struct>">) : !llvm.struct<sub_struct>
  %3 = llvm.mlir.null : !llvm.ptr<i16>
  %4 = llvm.getelementptr ...
  %final = llvm.mlir.constant.aggregate(%0, %1, %2, %3, %4)
  llvm.return %final
}

Pros: Reuse the existing translation code for llvm::ConstantExpr and llvm::CosntantPointerNull.
Cons: The ConstantLike trait – which requires zero (value) operand – cannot be applied on llvm.mlir.constant.aggregate, this might hinder some optimization opportunities. The initialization region also look cumbersome.

2. Create attributes for llvm::ConstantPointerNull (e.g. #llvm.null<ty>) and every kinds of llvm::ConstantExpr (e.g. #llvm.constexpr.getelementptr<...>), such that they can be composed (with other attributes) into a single ArrayAttr. For instane, the motivating example can be rewritten into (some syntax and type annotations has been omitted):

llvm.mlir.global constant @my_global([8, 7, #llvm.zeroinitializer<"llvm.struct<sub_struct>">, #llvm.null<"llvm.ptr<i16>">, #llvm.constexpr.getelementptr<...>]) : !llvm.struct<my_struct>

Pros: Both llvm::ConstantPointerNull and llvm::ConstantExpr are constants in the LLVM land, so it modeling them as constants – namely, attributes – in MLIR flows much naturally.
Cons: There are many kinds of llvm::ConstantExpr.

Personally, I’m lean toward solution 2 since its downside (I can think of now) is not really an issue once we have a consensus here.

Your comments on this topic are much appreciated!

[ftynse]

Thanks for the RFC!

Let me start by noting that LLVM IR import is an extremely experimental code that lacks many features. The fact that the importer doesn’t support something is quite likely due to the importer itself, not the inability to express it in the LLVM dialect.

In particular, your motivational example can be expressed in the LLVM dialect as

llvm.mlir.global constant @".str.8"("unix\00") : !llvm.array<5 x i8>
llvm.mlir.global @my_global() : !llvm.struct<"my_struct", (i8, i32, struct<"sub_struct", (i8, i32)>, ptr<i16>, ptr<i8>)> {
  %0 = llvm.mlir.undef : !llvm.struct<"my_struct", (i8, i32, struct<"sub_struct", (i8, i32)>, ptr<i16>, ptr<i8>)>
  %c8 = llvm.mlir.constant(8) : i8
  %c7 = llvm.mlir.constant(7) : i32
  %c0 = llvm.mlir.constant(0) : i8
  %c0_2 = llvm.mlir.constant(0) : i32
  %1 = llvm.insertvalue %c8, %0[0] : !llvm.struct<"my_struct", (i8, i32, struct<"sub_struct", (i8, i32)>, ptr<i16>, ptr<i8>)>
  %2 = llvm.insertvalue %c7, %1[1] : !llvm.struct<"my_struct", (i8, i32, struct<"sub_struct", (i8, i32)>, ptr<i16>, ptr<i8>)>
  %inner = llvm.mlir.undef : !llvm.struct<"sub_struct", (i8, i32)>
  %inner_2 = llvm.insertvalue %c0, %inner[0] : !llvm.struct<"sub_struct", (i8, i32)>
  %inner_3 = llvm.insertvalue %c0_2, %inner_2[1] : !llvm.struct<"sub_struct", (i8, i32)>
  %3 = llvm.insertvalue %inner_3, %2[2] : !llvm.struct<"my_struct", (i8, i32, struct<"sub_struct", (i8, i32)>, ptr<i16>, ptr<i8>)>
  %4 = llvm.mlir.null : !llvm.ptr<i16>
  %5 = llvm.insertvalue %4, %3[3] : !llvm.struct<"my_struct", (i8, i32, struct<"sub_struct", (i8, i32)>, ptr<i16>, ptr<i8>)>
  %6 = llvm.mlir.addressof @".str.8" : !llvm.ptr<array<5 x i8>>
  %7 = llvm.getelementptr %6[0, 0] : (!llvm.ptr<array<5 x i8>>) -> !llvm.ptr<i8>
  %8 = llvm.insertvalue %7, %5[4] : !llvm.struct<"my_struct", (i8, i32, struct<"sub_struct", (i8, i32)>, ptr<i16>, ptr<i8>)>
  llvm.return %8 : !llvm.struct<"my_struct", (i8, i32, struct<"sub_struct", (i8, i32)>, ptr<i16>, ptr<i8>)>
}

Converting this back to LLVM IR gives exactly the original code.

Now, this is pretty verbose and we are open to ideas on how to reduce this verbosity without significantly changing other design decisions. An important difference with LLVM IR is the handling of constants (that enables compiler parallelization): constants are not values, at least not directly. We have values that are known to be produced by constant-like operations, but the values are just values like others. Attributes are a property of the operation, so we don’t exactly model constants as attributes either.

This in turn allows MLIR not to recreate a parallel hierarchy of pseudo-instructions in constants and just use the regular instructions such as GEP and insertvalue to create constant values. For example, there is no need to have a special llvm.mlir.aggregate when one can just use a chain of llvm.insertvalues to the same effect. This simplicity has its benefits in the amount of the compiler code we need to write. It also has drawbacks, in particular the IR verbosity, but conciseness is not the primary objective of this dialect.

Therefore, I don’t think we would like to copy over the ConstantExpr hierarchy into MLIR attributes, or even operations. Zeroinitializer might be an exception, but I would like it to be motivated by something relevant for MLIR (e.g., makes it easier to do analysis/transforms) or missed opportunities in LLVM IR if we don’t produce it properly, rather than cargo cult of LLVM IR.

Adding support for complex constants to the importer is a good idea though.

[mshockwave]

@ftynse

An important difference with LLVM IR is the handling of constants (that enables compiler parallelization): constants are not values, at least not directly.

@ftynse

This in turn allows MLIR not to recreate a parallel hierarchy of pseudo-instructions in constants and just use the regular instructions such as GEP and insertvalue to create constant values.

I’m still adapting to MLIR’s design philosophy so thank you for your clarifications. Let me see if I understand you correctly: Unlike LLVM, in which constants are global SSA values (have use list) that might prevent the compiler from being parallelized, constants in MLIR are mostly local. Therefore, we don’t really need to invent special pseudo instructions (as I proposed here) for constants – we can just use normal operations to create constants.

@ftynse

This simplicity has its benefits in the amount of the compiler code we need to write. It also has drawbacks, in particular the IR verbosity, but conciseness is not the primary objective of this dialect.

The benefit you mentioned is a good point. And for the drawback, a big part of my original proposal was indeed accounting for conciseness, but now I am convinced that creating complex constants using existing operations is probably the track we want to take.

@ftynse

Zeroinitializer might be an exception, but I would like it to be motivated by something relevant for MLIR (e.g., makes it easier to do analysis/transforms) or missed opportunities in LLVM IR if we don’t produce it properly, rather than cargo cult of LLVM IR.

Adding support for complex constants to the importer is a good idea though.

I don’t have any use case where a standalone zeroinitializer attribute can benefit optimizations or analysis so I’ll just use llvm.insertvalue to implement that. Right now my first priority is making sure my source IR can be translated to LLVM Dialect.

I will make changes to the importer, and possibly the exporter (LLVM dialect → LLVM IR), to support complex constants and send some patches.