diff --git a/mlir/docs/SPIRVToLLVMDialectConversion.md b/mlir/docs/SPIRVToLLVMDialectConversion.md new file mode 100644 --- /dev/null +++ b/mlir/docs/SPIRVToLLVMDialectConversion.md @@ -0,0 +1,573 @@ +# SPIR-V Dialect to LLVM Dialect conversion manual + +This manual describes the conversion from [SPIR-V Dialect](Dialects/SPIR-V.md) +to [LLVM Dialect](Dialects/LLVM.md). It assumes familiarity with both, and +describes the design choices behind the modelling of SPIR-V conscepts in LLVM +Dialect. The conversion is an ongoing work, and is expected to grow as more +features are implemented. + +Conversion can be performed by invoking an appropriate conversion pass: + +```shell +mlir-opt -convert-spirv-to-llvm +``` + +This pass performs type and operation conversions for SPIR-V operations as +described in this document. + +[TOC] + +## Type Conversion + +This section describes how SPIR-V Dialect types are mapped to LLVM Dialect. + +### Scalar types + +SPIR-V Dialect | LLVM Dialect +:----------------------------------: | :----------------------------------: +`i` | `!llvm.i` +`si` | `!llvm.i` +`ui` | `!llvm.i` +`f16` | `!llvm.half` +`f32` | `!llvm.float` +`f64` | `!llvm.double` + +### Vector types + +SPIR-V Dialect | LLVM Dialect +:----------------------------------: | :----------------------------------: +`vector< x >` | `!llvm<"< x >">` + +### Pointer types + +SPIR-V pointer also takes a Storage Class. At the moment, conversion does +**not** take it into account. + +SPIR-V Dialect | LLVM Dialect +:-------------------------------------------: | :-------------------------------------------: +`!spv.ptr< , >` | `!llvm.element-type*` + +### Array types + +SPIR-V distiguishes between array type and run-time array type, the length of +which is not known at compile time. In LLVM, it is possible to index beyond the +end of the array. Therfore, runtime array can be implemented as a zero length +array type. + +Moreover, SPIR-V supports the notion of array stride. Note that this is **not** +supported by type conversion at the moment. + +SPIR-V Dialect | LLVM Dialect +:-----------------------------------: | :-----------------------------------: +`!spv.array< x >`| `!llvm<"[ x ]">` +`!spv.rtarray< >` | `!llvm<"[0 x ]">` + +### Struct types + +Members of SPIR-V struct types may have decorations and offset information. +Currently, there is **no** support of member decorations conversion for structs. +For more information see section on [Decorations](#Decorations-conversion). + +Usually we expect that each struct member has a natural size and alignment. +However, there are cases (*e.g.* in graphics) where one would place struct +members explicitly specifying particular offsets. This case is **not** supported +at the moment. Hence, we adhere to the following mapping: + +* Structs with no offset are modelled as LLVM packed structures. + +* Structs with natural offset (*i.e.* offset that equals to cumulative size of + the previous struct elements or is a natural alignment) are mapped to + naturally padded structs. Nested structs with offset are **not** supported. + +* Structs with unnatural offset (*i.e.* offset that is not equal to cumulative + size of the previous struct elements) are **not** supported. In this case, + offsets can be emulated with padding fields (*e.g.* integers). However, such + a design would require index recalculation in the conversion of ops that + involve memmory addressing. + +Examples of SPIR-V struct conversion are: +```mlir +// !llvm<"<{ i8, i32> }>"> +!spv.struct + +// !llvm<"{ i8, i32> }"> +!spv.struct + +// error +!spv.struct +``` + +### Not supported types + +The rest of the types not mentioned explicitly above are not supported by the +conversion. This includes `ImageType` and `MatrixType`. + +## Operation Conversion + +This section describes how SPIR-V Dialect operations are converted to LLVM +Dialect. It lists already working conversion patterns, as well as those that are +an ongoing work. + +There are also multiple ops for which there is no clear mapping in LLVM. +Conversion for those have to be discussed within the community on the +case-by-case basis. + +### Arithmetic ops + +SPIR-V arithmetic ops mostly have a direct equivalent in LLVM Dialect. Such +exceptions as `spv.SMod` and `spv.FMod` are rare. +SPIR-V Dialect op | LLVM Dialect op +:-----------------------------------: | :-----------------------------------: +`spv.FAdd` | `llvm.fadd` +`spv.FDiv` | `llvm.fdiv` +`spv.FNegate` | `llvm.fneg` +`spv.FMul` | `llvm.fmul` +`spv.FRem` | `llvm.frem` +`spv.FSub` | `llvm.fsub` +`spv.IAdd` | `llvm.add` +`spv.IMul` | `llvm.mul` +`spv.ISub` | `llvm.sub` +`spv.SDiv` | `llvm.sdiv` +`spv.SRem` | `llvm.srem` +`spv.UDiv` | `llvm.udiv` +`spv.UMod` | `llvm.urem` + +### Bitwise ops + +SPIR-V has a range of bit ops that are mapped to LLVM dialect ops, intrinsics or +may have a specific conversion pattern. + +#### Direct conversion + +As with arithmetic ops, most of bitwise ops have a semantically equivalent op in +LLVM: + +SPIR-V Dialect op | LLVM Dialect op +:-----------------------------------: | :-----------------------------------: +`spv.BitwiseAnd` | `llvm.and` +`spv.BitwiseOr` | `llvm.or` +`spv.BitwiseXor` | `llvm.xor` + +Also, some of bitwise ops can be modelled with LLVM intrinsics: + +SPIR-V Dialect op | LLVM Dialect intrinsic +:-----------------------------------: | :-----------------------------------: +`spv.BitCount` | `llvm.intr.ctpop` +`spv.BitReverse` | `llvm.intr.bitreverse` + +#### `spv.Not` + +`spv.Not` is modelled with a `xor` operation with a mask with all bits set. + +```mlir +// %mask = llvm.mlir.constant(-1 : i32) : !llvm.i32 +// %0 = llvm.xor %op, %mask : !llvm.i32 +%0 = spv.Not %op : i32 +``` + +#### Bit manipulation ops + +SPIR-V dialect has three bit manipulation ops: `spv.BitFieldInsert`, +`spv.BitFieldSExtract` and `spv.BitFieldUExtract`. This section will first +outline the general design of conversion patterns for this ops, and then +describe each of them. + +All of these ops take `base`, `offset` and `count` (`insert` for +`spv.BitFieldInsert`) as arguments. There are two important things +to note: + +* `offset` and `count` are always scalar. This means that we can have the + following case: + + ```mlir + %0 = spv.BitFieldSExtract %base, %offset, %count : vector<2xi32>, i8, i8 + ``` + + To be able to proceed with conversion algorithms described below, all + operands have to be of the same type and bitwidth. This requires + broadcasting of `offset` and `count` to vectors, for example for the case + above it gives: + + ```mlir + // Broadcasting offset + %offset0 = llvm.mlir.undef : !llvm<"<2 x i8>"> + %zero = llvm.mlir.constant(0 : i32) : !llvm.i32 + %offset1 = llvm.insertelement %offset, %offset0[%zero : !llvm.i32] : !llvm<"<2 x i8>"> + %one = llvm.mlir.constant(1 : i32) : !llvm.i32 + %vec_offset = llvm.insertelement %offset, %offset1[%one : !llvm.i32] : !llvm<"<2 x i8>"> + + // Broadcasting count + // ... + ``` + +* `offset` and `count` may have different bitwidths from `base`. In this case, + both of these operands have to be zero extended (since they are treated as + unsigned by the specification) or truncated. For the above example it would + be: + + ```mlir + // Zero extending offest after broadcasting + %res_offset = llvm.zext %vec_offset: !llvm<"<2 x i8>"> to !llvm<"<2 x i32>"> + ``` + + Also, note that if the bitwidth of `offset` or `count` is greater than the + bitwidth of `base`, truncation is still safe. This is beacuse the ops have a + defined behaviour with `offset` and `count` being less than the size of + `base`. It creates a natural upper bound on what values `offset` and `count` + can take, which is 64. This can be expressed in less than 8 bits. + +Now, having these two cases in mind, we can proceed with conversion for the ops +and their operands. + +##### `spv.BitFieldInsert` + +This operation is implemented as a series of LLVM Dialect operations. First step +would be to create a mask with bits set outside +[`offset`, `offset` + `count` - 1]. Then, unchanged bits are extracted from +`base` that are outside of [`offset`, `offset` + `count` - 1]. The result is +`or`ed with shifted `insert`. + +```mlir +// Create mask +// %minus_one = llvm.mlir.constant(-1 : i32) : !llvm.i32 +// %t0 = llvm.shl %minus_one, %count : !llvm.i32 +// %t1 = llvm.xor %t0, %minus_one : !llvm.i32 +// %t2 = llvm.shl %t1, %offset : !llvm.i32 +// %mask = llvm.xor %t2, %minus_one : !llvm.i32 + +// Extract unchanged bits from the Base +// %new_base = llvm.and %base, %mask : !llvm.i32 + +// Insert new bits +// %sh_insert = llvm.shl %insert, %offset : !llvm.i32 +// %res = llvm.or %new_base, %sh_insert : !llvm.i32 +%res = spv.BitFieldInsert %base, %insert, %offset, %count : i32, i32, i32 +``` + +##### `spv.BitFieldSExtract` + +To implement `spv.BitFieldSExtract`, `base` is shifted left by [sizeof(`base`) - +(`count` + `offset`)], so that the bit at `offset` + `count` - 1 is the most +significant bit. After, the result is shifted right, filling the bits with the +sign bit. + +```mlir +// Calculate the amount to shift left. +// %size = llvm.mlir.constant(32 : i32) : !llvm.i32 +// %t0 = llvm.add %count, %offset : !llvm.i32 +// %t1 = llvm.sub %size, %t0 : !llvm.i32 + +// Shift left and then right to extract the bits +// %sh_left = llvm.shl %base, %t1 : !llvm.i32 +// %t2 = llvm.add %offset, %t1 : !llvm.i32 +// %res = llvm.ashr %sh_left, %t2 : !llvm.i32 +%res = spv.BitFieldSExtract %base, %offset, %count : i32, i32, i32 +``` + +##### `spv.BitFieldUExtract` + +For this op a similar pattern as for `spv.BitFieldInsert` is used. First, a mask +with bits set at [0, `count` - 1] is created. Then `base` is shifted by `offset` +and the mask is applied. + +```mlir +// Create a mask +// %minus_one = llvm.mlir.constant(-1 : i32) : !llvm.i32 +// %t0 = llvm.shl %minus_one, %count : !llvm.i32 +// mask = llvm.xor %t0, %minus_one : !llvm.i32 + +// Shift Base and apply mask +// %sh_base = llvm.lshr %base, %offset : !llvm.i32 +// %res = llvm.and %sh_base, %mask : !llvm.i32 +%res = spv.BitFieldUExtract %base, %offset, %count : i32, i32, i32 +``` + +### Cast ops + +#### Direct conversions + +SPIR-V Dialect op | LLVM Dialect op +:-----------------------------------: | :-----------------------------------: +`spv.ConvertFToS` | `llvm.fptosi` +`spv.ConvertFToU` | `llvm.fptoui` +`spv.ConvertSToF` | `llvm.sitofp` +`spv.ConvertUToF` | `llvm.uitofp` + +#### spv.Bitcast +This operation has a direct counterpart in LLVM: `llvm.bitcast`. It is treated +separately since it also supports pointer to pointer bit pattern-preserving type +conversion, apart from regular scalar or vector of numerical type. + +#### Special cases +Special cases include `spv.FConvert`, `spv.SConvert` and `spv.UConvert`. These +operations are either a truncate or extend. Let's denote the operand component +width as A, and result component width as R. Then, the following mappings are +used: + +##### `spv.FConvert` +Case | LLVM Dialect op +:-------------: | :-----------------------------------: +A < R | `llvm.fpext` +A > R | `llvm.fptrunc` + +##### `spv.SConvert` +Case | LLVM Dialect op +:-------------: | :-----------------------------------: +A < R | `llvm.sext` +A > R | `llvm.trunc` + +##### `spv.UConvert` +Case | LLVM Dialect op +:-------------: | :-----------------------------------: +A < R | `llvm.zext` +A > R | `llvm.trunc` + +The case when A = R is not supported, based on SPIR-V Dialect specification: +> The component width cannot equal the component width in Result Type. + +### Comparison ops + +SPIR-V comparison ops are mapped to LLVM `icmp` and `fcmp` operations. + +SPIR-V Dialect op | LLVM Dialect op +:-----------------------------------: | :-----------------------------------: +`spv.IEqual` | `llvm.icmp "eq"` +`spv.INotEqual` | `llvm.icmp "ne"` +`spv.FOrdEqual` | `llvm.fcmp "oeq"` +`spv.FOrdGreaterhan` | `llvm.fcmp "ogt"` +`spv.FOrdGreaterThanEqual` | `llvm.fcmp "oge"` +`spv.FOrdLessThan` | `llvm.fcmp "olt"` +`spv.FOrdLessThanEqual` | `llvm.fcmp "ole"` +`spv.FOrdNotEqual` | `llvm.fcmp "one"` +`spv.FUnordEqual` | `llvm.fcmp "ueq"` +`spv.FUnordGreaterhan` | `llvm.fcmp "ugt"` +`spv.FUnordGreaterThanEqual` | `llvm.fcmp "uge"` +`spv.FUnordLessThan` | `llvm.fcmp "ult"` +`spv.FUnordLessThanEqual` | `llvm.fcmp "ule"` +`spv.FUnordNotEqual` | `llvm.fcmp "une"` +`spv.SGreaterThan` | `llvm.icmp "sgt"` +`spv.SGreaterThanEqual` | `llvm.icmp "sge"` +`spv.SLessThan` | `llvm.icmp "slt"` +`spv.SLessThanEqual` | `llvm.icmp "sle"` +`spv.UGreaterThan` | `llvm.icmp "ugt"` +`spv.UGreaterThanEqual` | `llvm.icmp "uge"` +`spv.ULessThan` | `llvm.icmp "ult"` +`spv.ULessThanEqual` | `llvm.icmp "ule"` + +### Control flow ops + +**Note: these conversions have not been implemented yet** + +### Logical ops + +Logical ops follow a similar pattern as bitwise ops, with the difference that +they operate on `i1` or vector of `i1` values. The following mapping is used to +emulate SPIR-V ops behaviour: + +SPIR-V Dialect op | LLVM Dialect op +:-----------------------------------: | :-----------------------------------: +`spv.LogicalAnd` | `llvm.and` +`spv.LogicalOr` | `llvm.or` +`spv.LogicalEqual` | `llvm.icmp "eq"` +`spv.LogicalNotEqual` | `llvm.icmp "ne"` + +`spv.LogicalNot` has the same conversion pattern as bitwise `spv.Not`. It is +modelled with `xor` operation with a mask with all bits set. + +```mlir +// %mask = llvm.mlir.constant(-1 : i1) : !llvm.i1 +// %0 = llvm.xor %op, %mask : !llvm.i1 +%0 = spv.LogicalNot %op : i1 +``` + +### Function conversion and related ops + +This section describes the conversion of function-related operations from SPIR-V +to LLVM dialect. + +#### `spv.func` +This op declares or defines a SPIR-V function and it is converted to `llvm.func`. +This conversion handles signarture conversion, and function control attributes +remapping to LLVM dialect function [`passthrough` attribute](Dialects/LLVM.md#Attribute-pass-through). + +The following mapping is used to map [SPIR-V function control](SPIRVFunctionAttributes) to +[LLVM function attributes](LLVMFunctionAttributes): + +SPIR-V Function Control Attributes | LLVM Function Attributes +:-----------------------------------: | :-----------------------------------: +None | No function attributes passed +Inline | `alwaysinline` +DontInline | `noinline` +Pure | `readonly` +Const | `readnone` + +#### `spv.FunctionCall` + +`spv.FunctionCall` maps to `llvm.call`. For example: + +```mlir +// %0 = llvm.call @foo() : () -> !llvm.float +%0 = spv.FunctionCall @foo() : () -> i32 + +// llvm.call @bar(%0) : (!llvm.float) -> () +spv.FunctionCall @bar(%0) : (i32) -> () +``` + +#### `spv.Return` and `spv.ReturnValue` + +In LLVM IR, functions may return either 1 or 0 value. Hence, we map both ops to +`llvm.return` with or without a return value. + +### Miscellaneous ops + +There are multiple SPIR-V ops that do not fit in a particular group. Their +conversion is addressed in this section. + +#### Direct conversions + +SPIR-V Dialect op | LLVM Dialect op +:-----------------------------------: | :-----------------------------------: +`spv.Select` | `llvm.select` +`spv.Undef` | `llvm.mlir.undef` + +#### `spv.constant` + +At the moment `spv.constant` conversion supports scalar and vector constants +**only**. + +##### Mapping + +`spv.constant` is mapped to `llvm.mlir.constant`. This is a strightforward +conversion pattern with a special case when the argument is signed or unsigned. + +##### Special case + +SPIR-V constant can be a signed or unsigned integer. Since LLVM Dialect does not +have signedness semantics, this case should be handeled separately. + +The conversion casts constant value attribute to a signless integer or a vector +of signless integers. Removing the sign bit may have unexpected behaviour. +However, it is better to handle it case-by-case, given that the purpose of the +conversion is not to cover all possible corner cases. + +```mlir +// %0 = llvm.mlir.constant(0 : i8) : !llvm.i8 +%0 = spv.constant 0 : i8 + +// %1 = llvm.mlir.constant(dense<[2, 3, 4]> : vector<3xi32>) : !llvm<"<3 x i32>"> +%1 = spv.constant dense<[2, 3, 4]> : vector<3xui32> +``` + +### Module ops + +Module in SPIR-V has one region that contains one block. It is defined via +`spv.module` op that also takes a range of attributes: + +* Addressing model +* Memory model +* Version-Capability-Extension attribute + +`spv.module` is converted into `ModuleOp`. This plays a role of enclosing scope +to LLVM ops. At the moment, SPIR-V module attributes are ignored. + +`spv._module_end` is mapped to an equivalent terminator `ModuleTerminatorOp`. + +### Shift ops + +Shift operates on two operands: `shift` and `base`. + +In SPIR-V dialect, `shift` and `base` may have different bit width. On the +contrary, in LLVM Dialect both `base` and `shift` have to be of the same +bitwidth. This leads to the following conversions: + +* if `base` has the same bitwidth as `shift`, the conversion is + straightforward. + +* if `base` has a greater bit width than `shift`, shift is sign or zero + extended first. Then the extended value is passed to the shift. + +* otherwise, the conversion is considered to be illegal. + +```mlir +// %res0 = llvm.ashr %0, %2 : !llvm.i32 +%res0 = spv.ShiftRightArithmetic %0, %2 : i32, i32 + +// %ext = llvm.sext %1 : !llvm.i16 to !llvm.i32 +// %res1 = llvm.ashr %0, %ext: !llvm.i32 +%res1 = spv.ShiftRightArithmetic %0, %1 : i32, i16 +``` + +## Decorations conversion + +**Note: these conversions have not been implemented yet** + +## GLSL extended instriction set + +**Note: these conversions have not been implemented yet** + +This section describes how SPIR-V ops from GLSL extended instructions set are +mapped to LLVM Dialect. + +### Direct conversions + +SPIR-V Dialect op | LLVM Dialect op +:-----------------------------------: | :-----------------------------------: +`spv.GLSL.Ceil` | `llvm.intr.ceil` +`spv.GLSL.Cos` | `llvm.intr.cos` +`spv.GLSL.Exp` | `llvm.intr.exp` +`spv.GLSL.FAbs` | `llvm.intr.fabs` +`spv.GLSL.Floor` | `llvm.intr.floor` +`spv.GLSL.FMax` | `llvm.intr.maxnum` +`spv.GLSL.FMin` | `llvm.intr.minnum` +`spv.GLSL.Log` | `llvm.intr.log` +`spv.GLSL.Sin` | `llvm.intr.sin` +`spv.GLSL.Sqrt` | `llvm.intr.sqrt` + +### Special cases + +TODO: add more patterns for special cases. + +`spv.Tan` is mapped to: +```mlir +// %sin = "llvm.intr.sin"(%arg) : (!llvm.float) -> !llvm.float +// %cos = "llvm.intr.cos"(%arg) : (!llvm.float) -> !llvm.float +// %res = fdiv %sin, %cos : !llvm.float +%res = spv.Tan %arg : f32 +``` + +## Not supported ops + +There is no support of the following ops: + +* All Atomic ops +* All matrix ops +* All GLSL ops +* All GroupNonUniform ops +* spv.AccessChain +* spv._address_of +* spv.Branch +* spv.BranchConditional +* spv.CompositeConstruct +* spv.CompositeExtract +* spv.CompositeInsert +* spv.ControlBarrier +* spv.CopyMemory +* spv.EntryPoint +* spv.ExecutionMode +* spv.FMod +* spv.globalVariable +* spv.Load +* spv.loop +* spv.MemoryBarrier +* spv._merge +* spv._reference_of +* spv.selection +* spv.SMod +* spv.specConstant +* spv.Store +* spv.SubgroupBallotKHR +* spv.Variable +* spv.Unreachable + +[LLVMFunctionAttributes]: https://llvm.org/docs/LangRef.html#function-attributes +[SPIRVFunctionAttributes]: https://www.khronos.org/registry/spir-v/specs/unified1/SPIRV.html#_a_id_function_control_a_function_control