SPIR-V translator violates logical layout.

[bader]

Quote from SPIR-V specification section 2.4:
"9. All type declarations (OpTypeXXX instructions), all constant instructions, and all global variable declarations (all OpVariable instructions whose Storage Class is not Function). All operands in all these instructions must be declared before being used. Otherwise, they can be in any order. This section is also the first section to allow use of OpLine debug information."

LLVM/SPIR-V translator place type declarations first, constant declarations next and global variables after that. That order violates requirement "All operands in all these instructions must be declared before being used." for the following OpenCL code:

constant float f[2] = {0.f, 0.f};

SPIR-V code produced by translator:

     %2 = OpTypeInt 32 0
     %4 = OpTypeFloat 32
     %5 = OpTypeArray %4 %3 ; <<< here we %3 is used but defined below.
     %7 = OpTypePointer UniformConstant %5
     %3 = OpConstant %2 2
     %6 = OpConstantNull %5
     %8 = OpVariable %7 UniformConstant %6

[yxsamliu]

This is a spec issue:

Length is the number of elements in the array. It must be at least 1. Length must come from a constant instruction of an integer-type scalar whose value is at least 1.

[bader]

I didn't get this. I think this case can be fixed in SPIR-V translator:

 %2 = OpTypeInt 32 0
 %3 = OpConstant %2 2
 %4 = OpTypeFloat 32
 %5 = OpTypeArray %4 %3
 %7 = OpTypePointer UniformConstant %5
 %6 = OpConstantNull %5
 %8 = OpVariable %7 UniformConstant %6

To resolve cyclic dependencies in type definition there is OpTypeForwardPointer. I'm not sure it's enough to resolve all cases though.

Could you clarify what's wrong in the specification?

[yxsamliu]

Sorry, I thought all types must be defined before constants. I was wrong.

We can emit integer types first, then integer constants, then other types and constants.

[bader]

Proposed solution will solve particular test case I showed, but won't solve the problem - there is no guarantee that "All operands in type, constant and global variables are declared before being used."
For instance, recently I did a fix for translation of recursive data types and regression test I added also violates that rule (https://github.com/KhronosGroup/SPIRV-LLVM/pull/99/files).
Currently there are three different container for types, constants and global variables. I think we should have one container for all of them (maybe create one before writing to SPIR-V file, but it's better to have one all the way during translation). Than we can either insert SPIRVEntries into that container that will preserve required order or we can insert them in any order and sort just before serializing into the file.

[yxsamliu]

Merge arrays of type, constants and global variables may solve the order issue since the translator only translates a type/constant/global var after it translates their operands, so the merged array should naturally follow the dependence order.

However it won't solve the cyclic dependence issue which happens with the cyclically defined structure type. One way I can think of is to break the cyclic by change the type of a member to opaque pointer, but we need to find all uses of this member and insert bitcasts. I hope there is better way.

Also it is messier since types and constants/global vars will be mixed together, whereas types in most cases do not depend on constants/global variables except array types depend on integer constants. And constants usually do not depend on global variables except constant exprs.

Probably we could sort like this:

1. integer types goes first
2. integer constants
3. other types
4. constants do not depend on global vars
5. global vars
6. constants depend on global vars

[bader]

However it won't solve the cyclic dependence issue which happens with the cyclically defined structure type.

There should be no cyclic dependency issue: AFAIK the only way to create cyclic dependency is to declare a pointer to incomplete type and SPIR-V has OpTypeForwardPointer to resolve the dependency in this case. We already doing everything right except the structure type - we put it before it's operands.

Any way if we merge all three containers into one and sort entries to satisfy the requirement: "All operands must be declared before being used".

[AlexeySotkin]

I would not specifically separate constants and global variables, because they can be kind of tightly coupled like in the following example:

          %2 = OpTypeInt 32 0
          %3 = OpConstant %2 0
          %4 = OpConstant %2 1
          %5 = OpTypeStruct %2 %2 %2
          %7 = OpTypePointer UniformConstant %5
          %9 = OpTypeSampler
         %11 = OpTypePointer UniformConstant %9
          %6 = OpConstantComposite %5 %3 %4 %3
         %10 = OpSpecConstantOp %9 Bitcast %8
          %8 = OpVariable %7 UniformConstant %6
         %12 = OpVariable %11 UniformConstant %10

Here %12 is a variable which depends on constant %10, which depends on variable %8, which depends on constant %6.

[yxsamliu]

Right. I forgot variable could have an initializer which depends on other variables. So spec constants and variables could be mixed. However, non-spec constants should not depend on variables.

[AlexeySotkin]

My example has a bug. Per the specification, all constants (spec and non-spec) can only depend on other constants. In particular for OpSpecConstantOp

Operands are the operands required by opcode, and satisfy the semantics of opcode. In addition, all Operands must be the s of other constant instructions.

So I think all constant should go as a single group, after types and before variables.

[bader]

Constants can't go after types, since array type depends on constant or SpecConst that must be defined before the array type.

[AlexeySotkin]

I forgot about constant with integer types. They must be declared after integer types and before other types including array type.

[AlexeySotkin]

Fixed by #133