[SPIRV 6/6] Add the module analysis pass and the simplest tests

[iliya-diyachkov]

Summary

This patch adds one SPIRV analysis pass and extends AsmPrinter. It is essential for minimum SPIR-V output. Also it adds several simplest tests to show that the target basically works.

[rengolin]

You don't seem to have tests checking if the encoding of the instructions are correct when printing or parsing, leaving the Printer/Parser completely untested.

I'm guessing you don't have any arguments or return values because you haven't yet implemented prologue/epilogue and frame lowering.

Without that, it's hard to really test anything, but also makes the two passes a bit pointless, because you're not testing them either.

llvm/lib/Target/SPIRV/SPIRVBlockLabeler.cpp

11 ↗

(On Diff #396830)

Isn't this guaranteed by IR passes and the verifier?

What would create basic blocks that don't have a suitable terminator that still passes the verify?

llvm/lib/Target/SPIRV/SPIRVGlobalTypesAndRegNumPass.cpp

23 ↗

(On Diff #396830)

That's a bit scary. Is that what created BBs without terminators?

llvm/lib/Target/SPIRV/SPIRVTargetMachine.cpp

149

I don't see where this is called in this code...

[iliya-diyachkov]

I think all the CHECKs we have in the added tests do check instruction Printer (we don't use Parser) since all the lines in asm output (OpName, OpType***, OpFunction, OpLabel, OpFunctionParameter etc) are instructions in terms of SPIR-V and Printer prints them as normal instructions. As you can see, some of them have arguments that are also checked for correctness.

The actual reason for adding the only simplest tests is not the missed frame lowering. SPIR-V uses high-level type information that should be maintained after IR translator and other GlobalISel passes. The necessary passes and utility code have not been added yet, since the simplest tests can be passed without them. However, if we want to have a test that contains something substantial, these functionality (>1k lines) should be added. But I'm not sure we really need that in this series of patches.

By the way, slightly extending the second pass I can add a test that has a simple argument usage with value returning.

The 2 passes in this patch are actually checked by the added tests because the tests check the instructions added during the passes (e.g. OpLabel/OpFunctionEnd in the first pass and OpSource/OpName in the second one).

llvm/lib/Target/SPIRV/SPIRVBlockLabeler.cpp

11 ↗

(On Diff #396830)

It looks like an outdated description. In any case, I can't immediately find a test that would require additional terminators at the time of the pass invocation.

The main purpose of the pass is to insert OpLabel instructions and to put the corresponding registers to OpBranchConditional, OpBranch, and OpPhi instructions. Also OpFunctionEnd (last instruction in functions) is inserted here.

These instructions are required to pass simple tests with defined functions.

llvm/lib/Target/SPIRV/SPIRVGlobalTypesAndRegNumPass.cpp

23 ↗

(On Diff #396830)

Actually the pass creates a dummy function that represents the global context of the module containing types, constants, global variables and other SPIR-V specific global information. This dummy function has a linear CFG, and in fact its BBs do not contain terminators, however, they can be inserted or a single BB can be used here (because all these BBs are created just for the convenience of the code motion from real functions to this dummy one).

This pass works just before the code emission and does not break any other passes. It is expected that the verifier will not work after it, since registers are renamed according to requirements for SPIR-V code emission, and it will be wrong for the verifier.

llvm/lib/Target/SPIRV/SPIRVTargetMachine.cpp

149

It's overrided standard LLVM pass which is called immediately before machine code is emitted (llvm/include/llvm/CodeGen/TargetPassConfig.h:443).

[MaskRay]

llvm/test/CodeGen/SPIRV/optnone.ll

6 ↗

(On Diff #396830)

Without a positive test in the same file, a negative pattern can easily go stale without being noticed.

Consider split-file to place highly related tests together.

17 ↗

(On Diff #396830)

delete unneeded attributes

27 ↗

(On Diff #396830)

incorrect version.

delete unneeded metadata

[arsenm]

llvm/lib/Target/SPIRV/SPIRVBlockLabeler.cpp

102 ↗

(On Diff #396830)

Why does this need to be a codegen pass? Can't you handle this during the encoding/emission?

104 ↗

(On Diff #396830)

Using MachineIRBuilder outside of a globalisel pass is weird

llvm/lib/Target/SPIRV/SPIRVGlobalTypesAndRegNumPass.cpp

23 ↗

(On Diff #396830)

I think having the verifier fail at any point is a problem. Why does this have to be a dedicated pass, and not just part of the AsmPrinter?

232 ↗

(On Diff #396830)

MI print includes the newline already

llvm/test/CodeGen/SPIRV/metadata-opencl12.ll

1 ↗

(On Diff #396830)

Probably should make global-isel the target default so you don't have to add the flag to every test

[iliya-diyachkov]

llvm/lib/Target/SPIRV/SPIRVBlockLabeler.cpp

102 ↗

(On Diff #396830)

Each OpLabel defines a virtual register which is used in terminator instructions. I'm not sure that creating OpLabels, then finding and patching correspondent terminators is an appropriate task for the encoding/emission. Moreover the next pass (SPIRVGlobalTypesAndRegNumPass) should rename all virtual registers globally (i.e. each register in a module gets an unique number). As a result OpLabels and terminators (since they have registers) should be processed before SPIRVGlobalTypesAndRegNumPass.

104 ↗

(On Diff #396830)

Yes, we need to use BuildMI like in addPreEmitPass2's passes of other targets.

llvm/lib/Target/SPIRV/SPIRVGlobalTypesAndRegNumPass.cpp

23 ↗

(On Diff #396830)

Currently only a part of this pass is presented in the review. The entire pass works at module level and performs following things:

• create a dummy function with some instructions;
• move some other instructions from regular functions to that dummy function;
• rename all registers globally, each new register name is unique in a whole module.

I don't think that operating at global level (copying instructions from one function to another and global naming of registers) can be implemented using the AsmPrinter (please correct me if I'm wrong). However we can try to move some functionality to AsmPrinter and make MIR consistent after this pass, which solves the verifier issue.

llvm/test/CodeGen/SPIRV/metadata-opencl12.ll

1 ↗

(On Diff #396830)

Yes, I agree.

llvm/test/CodeGen/SPIRV/optnone.ll

6 ↗

(On Diff #396830)

Actually this is a positive test with the confusing checker name CHECK-SPIRV-NO-EXT. It was copied form SPIRV Translator test base as many of our LIT tests (sometimes with simplification). I suppose it is not a good candidate for this series, so I'll find another one instead.

[iliya-diyachkov]

The issues noted by Fangrui Song and Matt Arsenault have been eliminated.

[iliya-diyachkov]

This change makes LIT tests passed on LLVM which is built with -DLLVM_ENABLE_EXPENSIVE_CHECKS=ON -DLLVM_ENABLE_ABI_BREAKING_CHECKS=ON.

[iliya-diyachkov]

Correct the code format.

[rengolin]

I'm still not convinced that these passes are the right way to go, but I won't block if others think it has merit, even if just temporary, until the proper implementation emerges.

We don't need these patches to be perfect, just good enough to generate some instructions and tell us that the direction the target is going is in sync with what we think should be.

If this is something that can be changed later, I'd be fine with it.

@arsenm @MaskRay

[zuban32]

In D116465#3289893, @rengolin wrote:

I'm still not convinced that these passes are the right way to go, but I won't block if others think it has merit, even if just temporary, until the proper implementation emerges.

We don't need these patches to be perfect, just good enough to generate some instructions and tell us that the direction the target is going is in sync with what we think should be.

If this is something that can be changed later, I'd be fine with it.

@arsenm @MaskRay

@rengolin what would be considered as a proper implementation? Currently the only reasonable way this can be modified is by moving the hoisting and deduplication logic to the printing/emission stage, and it's difficult to see another alternative due to the gap between SPIR-V and MIR in this matter - obviously MIR is not able to represent arbitrary instructions not belonging to a MachineFunction (and I don't even think it should be). So it seems the activity performed by these passes should be moved to a level lower than MIR, but for now it looks like that's the only major enhancement that could be done here.

[rengolin]

In D116465#3290716, @zuban32 wrote:

@rengolin what would be considered as a proper implementation?

I don't think I have quite understood what the problem is, tbh.

If this is just some global value numbering, why is it being done so late (ie, not in IR)?

If this is a SPIR-V hardware requirement, that needs a specific guaranteed shape that cannot rely on the state of IR->MIR conversions (especially the generic parts), then there may not be another way out.

But I'll leave for others to express their opinions, as I'm not familiar with the problem.

[zuban32]

In D116465#3290818, @rengolin wrote:

In D116465#3290716, @zuban32 wrote:

@rengolin what would be considered as a proper implementation?

I don't think I have quite understood what the problem is, tbh.

If this is just some global value numbering, why is it being done so late (ie, not in IR)?

If this is a SPIR-V hardware requirement, that needs a specific guaranteed shape that cannot rely on the state of IR->MIR conversions (especially the generic parts), then there may not be another way out.

But I'll leave for others to express their opinions, as I'm not familiar with the problem.

Then let me describe the problem in more details, I'd like us all to be on the same page with this.

This patch adds 2 passes SPIRVGlobalTypesAndRegNumPass and SPIRVBlockLabelerPass.

The latter seems to be a minor problem - the reason for it to exist is SPIRV binary format requiring global numbering of all the defined values, i.e. if there're 2 functions each containing only 1 instruction then these instructions can't be both numbered %0.

The former one attempts to solve a bigger problem. Basically the SPIRV binary is structured as following:

...
types, constants
...
functions definitions

Let me provide a short example in SPIR-V:

%0 = OpTypeInt 32
%1 = OpTypeInt 64
%2 = OpConstant %1, 5

%3 = OpFunction %1 ...
%4 = OpFunctionParameter %0
%5 = OpFunctionParameter %1
%6 = OpUConvert %1 %4
%7 = OpIAdd %1 %6 %5
%8 = OpIMul %1 %7 %2
OpReturnValue %8
OpFunctionEnd

%9 = OpFunction %1 ...
%10 = OpFunctionParameter %0
%11 = OpFunctionParameter %1
%12 = OpUConvert %1 %10
%13 = OpISub %1 %12 %11
%14 = OpIMul%1 %13 %2
OpReturnValue %14
OpFunctionEnd

The LLVM IR counterparts for the functions above are the following:

define i64 @foo(i32 %a, i64 %b)
  %0 = i64 zext i32 %a to i64
  %1 = i64 add %0, %b
  %2 = i64 mul %1, 5
  ret %2

define i64 @bar(i32 %a, i64 %b)
  %0 = i64 zext i32 %a to i64
  %1 = i64 sub %0, %b
  %2 = i64 mul %1, 5
  ret %2

In the example above you can see that OpType*, OpConstant are out of any function's scope, they're global to the whole module, and this can't be natively expressed in MIR. Because of that in our approach each MachineFunction has its own copies of type decls and constants (and other stuff like that) during the whole translation process, but eventually they need to be deduplicated and 'globalized'. That can be done either on MIR level or during binary emission, but it has done be done anyway.

Hope this helps

[rengolin]

In D116465#3290957, @zuban32 wrote:

Then let me describe the problem in more details, I'd like us all to be on the same page with this.

Awesome! This is much clearer to me, thanks!

The latter seems to be a minor problem - the reason for it to exist is SPIRV binary format requiring global numbering of all the defined values, i.e. if there're 2 functions each containing only 1 instruction then these instructions can't be both numbered %0.

Do you have a maximum ID? If not, than in theory, you just need a static global auto-increment ID (like a get_next_id() on some target emission class) and off you go emitting globally unique IDs.

The former one attempts to solve a bigger problem. Basically the SPIRV binary is structured as following:

...
types, constants
...
functions definitions

I see, so your "global" function contain the type and constant declarations, that the functions use in their own declarations.

So, you're not "moving" anything, just creating a placeholder for those definitions and indexing them.

in our approach each MachineFunction has its own copies of type decls and constants (and other stuff like that) during the whole translation process, but eventually they need to be deduplicated and 'globalized'. That can be done either on MIR level or during binary emission, but it has done be done anyway.

IIUC, they're in each function because you generate for each function you pass through, so:

func1
  %0 = OpTypeInt 32
  %1 = OpTypeInt 64
  ...
func2
  %0 = OpTypeFloat 32
  %1 = OpTypeFloat 64
  ...

and then you need to get all types of the same "type" and call a single ID.

So, these passes seem *necessary* if you want a lean and tidy representation, but not necessary if you can cope with duplicate definitions while still keeping unique IDs.

For example, using the auto-increment proposal above, we could have:

func1
  %0 = OpTypeInt 32
  %1 = OpTypeInt 64
  ...
func2
  %2 = OpTypeFloat 32
  %3 = OpTypeInt 64
  ...

Note two definitions of Int 64 but with two different IDs. Would that be a binary format error for (native?) types? Would that be an error for constants, too?

If each type can only be defined once, you could have a list of all possible types and defined them in the beginning (in your "global" function), from %0 to %N. Then, while emitting each function, you just use those IDs and you don't need to deduplicate.

Of course, this doesn't work with constants, but I'm guessing it's more likely that, if there is a rule of single-declaration for types, there may not be for constants (otherwise compilers would suffer regardless of representation).

In that sense, you wouldn't need either pass, just initialisation of the known types, declaration of the global function with them, and reuse in each function, using the global auto-increment for all the IDs.

Does that fit with the spec?

[iliya-diyachkov]

In D116465#3291049, @rengolin wrote:

Do you have a maximum ID? If not, than in theory, you just need a static global auto-increment ID (like a get_next_id() on some target emission class) and off you go emitting globally unique IDs.

Actually we need to output Bound (not implemented in this series) so all IDs should satisfy "0 < id < Bound". I need to note that according to the SPIR-V specification "Bound should be small, smaller is better, with all IDs in a module being densely packed and near 0".

I would say that we use a numbering similar to described get_next_id() but inside this pass. We store its results in a map and substitute them during emission. I suppose numbering on emission with get_next_id() would also use Register - ID mapping to give same IDs to the same registers.

Note two definitions of Int 64 but with two different IDs. Would that be a binary format error for (native?) types? Would that be an error for constants, too?

Yes for types. From the specification: "Two different type IDs form, by definition, two different types. It is invalid to declare multiple nonaggregate, non-pointer type IDs having the same opcode and operands..."

As I know constant duplication is not forbidden, but such duplication looks like a bad solution since the Bound of IDs is recommended to be small. Also our reference tool (SPIRV-LLVM-Translator) does not duplicate constants as possible, and we would like to be conformant with it so the translator users will get similar results with the SPIRV LLVM backend (on transition to this tool).

If each type can only be defined once, you could have a list of all possible types and defined them in the beginning (in your "global" function), from %0 to %N. Then, while emitting each function, you just use those IDs and you don't need to deduplicate.

"a list of all possible types" would be very long because it includes not only simple types but also pointer types, composite types, builtin types... And please remember about densely packed IDs: types also have IDs and we don't want to have gaps in ID space due to type IDs unused in a module.

In addition to types and constants, we need to put global variables, external function declaration, annotations, debug info and some other instructions to that "global" function. All this is presented in the form of instructions with their register operands. These instructions should be only in the global function with no duplication in regular functions (however, there are a few exceptions)!

All these instructions are generated in regular functions at first, and we need a pass (running on module) to copy them to the "global" function. Also we avoid duplication of all of the instructions where possible (as SPIRV-LLVM-Translator does too).

In the last implementation we copy required instructions to the "global" function in SPIRVGlobalTypesAndRegNum pass. We keep in the regular functions the instructions (that were copied to the "global" function) till emission but do not emit them (while the instructions' copies in the "global" function are emitted). Also we number all registers globally avoiding duplication. These global register numbers are stored in a "register alias" map. On emission we output IDs from the map instead of the old local register numbers.

In this way MIR is still consistent after the pass (unlike we had in the earlier implementation) and verifier does not output errors. If it's desirable I can provide MIR/SPIR-V dumps demonstrating how it works on specific tests.

[zuban32]

In D116465#3291049, @rengolin wrote:

In D116465#3290957, @zuban32 wrote:

Then let me describe the problem in more details, I'd like us all to be on the same page with this.

Awesome! This is much clearer to me, thanks!

The latter seems to be a minor problem - the reason for it to exist is SPIRV binary format requiring global numbering of all the defined values, i.e. if there're 2 functions each containing only 1 instruction then these instructions can't be both numbered %0.

Do you have a maximum ID? If not, than in theory, you just need a static global auto-increment ID (like a get_next_id() on some target emission class) and off you go emitting globally unique IDs.

The former one attempts to solve a bigger problem. Basically the SPIRV binary is structured as following:

...
types, constants
...
functions definitions

I see, so your "global" function contain the type and constant declarations, that the functions use in their own declarations.

So, you're not "moving" anything, just creating a placeholder for those definitions and indexing them.

in our approach each MachineFunction has its own copies of type decls and constants (and other stuff like that) during the whole translation process, but eventually they need to be deduplicated and 'globalized'. That can be done either on MIR level or during binary emission, but it has done be done anyway.

IIUC, they're in each function because you generate for each function you pass through, so:

You're right, we want our MIR to pass the verification on all the stages. But in SPIR-V every instruction producing a value has its resulting type as an operand so types should be already defined. And since we can't emit MIR instructions out of a function scope (and can't use machine operands of instructions from another functions each MF has its own copies of the types/consts/etc used within its body. Since in the final binary those types/consts/etc should be in the global scope we create some placeholder MF for this purpose, and since these items may be duplicated in different functions so we'd like to deduplicate them during the hoisting.

func1
  %0 = OpTypeInt 32
  %1 = OpTypeInt 64
  ...
func2
  %0 = OpTypeFloat 32
  %1 = OpTypeFloat 64
  ...

and then you need to get all types of the same "type" and call a single ID.

So, these passes seem *necessary* if you want a lean and tidy representation, but not necessary if you can cope with duplicate definitions while still keeping unique IDs.

For example, using the auto-increment proposal above, we could have:

func1
  %0 = OpTypeInt 32
  %1 = OpTypeInt 64
  ...
func2
  %2 = OpTypeFloat 32
  %3 = OpTypeInt 64
  ...

Note two definitions of Int 64 but with two different IDs. Would that be a binary format error for (native?) types? Would that be an error for constants, too?

If each type can only be defined once, you could have a list of all possible types and defined them in the beginning (in your "global" function), from %0 to %N. Then, while emitting each function, you just use those IDs and you don't need to deduplicate.

Of course, this doesn't work with constants, but I'm guessing it's more likely that, if there is a rule of single-declaration for types, there may not be for constants (otherwise compilers would suffer regardless of representation).

In that sense, you wouldn't need either pass, just initialisation of the known types, declaration of the global function with them, and reuse in each function, using the global auto-increment for all the IDs.

Does that fit with the spec?

Well, in fact the space allows multiple definitions of both types (my bad, types are not allowed as Illiya mentioned above) and constants. But that may lead to a huge binary size increase and such a suboptimal codegen quality will become an obstacle to convincing people use our backend instead of the existing translator.

[rengolin]

I didn't mean the duplicated types/constants would survive into codegen, but I get your meaning, it would have to be commoned up at some point.

So, what about a singleton emitter for types and constants?

Instead of just get_next_id() you could have a get_type(...) and get_constant(...) that returns a cached MIR node if it has created a similar one already, or creates a new one, caches and returns it.

In this way, there's only ever one copy of each and they're only generated once, with no need to deduplicate.

The only issue with this implementation is that types, constants, functions, instructions will all have intertwined IDs, but never refer to larger IDs, by design.

When emitting "int foo()", if int hadn't been emitted before, it'd get the next id (say, %23) and then foo would get %24 and would refer to %23 as its type.

Eventually, all types used in the program would have been emitted already and be brought up from the cache every time.

This way, there's no need to renumber or common up and the space is still optimal.

What am I missing?

[zuban32]

In D116465#3292037, @rengolin wrote:

I didn't mean the duplicated types/constants would survive into codegen, but I get your meaning, it would have to be commoned up at some point.

So, what about a singleton emitter for types and constants?

Instead of just get_next_id() you could have a get_type(...) and get_constant(...) that returns a cached MIR node if it has created a similar one already, or creates a new one, caches and returns it.

In this way, there's only ever one copy of each and they're only generated once, with no need to deduplicate.

The only issue with this implementation is that types, constants, functions, instructions will all have intertwined IDs, but never refer to larger IDs, by design.

When emitting "int foo()", if int hadn't been emitted before, it'd get the next id (say, %23) and then foo would get %24 and would refer to %23 as its type.

Eventually, all types used in the program would have been emitted already and be brought up from the cache every time.

This way, there's no need to renumber or common up and the space is still optimal.

What am I missing?

Which stage are you talking about here: InstPrinter, any post-InstructionSelection pass, etc? On gMIR level I don't understand how that'd work if we define VReg %1 in func f1 and then use it in both f1 and f2.

[rengolin]

In D116465#3292079, @zuban32 wrote:

Which stage are you talking about here: InstPrinter, any post-InstructionSelection pass, etc? On gMIR level I don't understand how that'd work if we define VReg %1 in func f1 and then use it in both f1 and f2.

Whatever level you were planning to do the de-duplication. My point is just to replace de-duplication by enforcement (as post-generation pass) to de-duplication by construction (a singleton generator).

Though, I am not super familiar with MIR's representation, as that was introduced after I stopped working on back-ends directly, so don't take my word on that.

Perhaps @arsenm can chime in?

[iliya-diyachkov]

So, what about a singleton emitter for types and constants?

Instead of just get_next_id() you could have a get_type(...) and get_constant(...) that returns a cached MIR node if it has created a similar one already, or creates a new one, caches and returns it.

In this way, there's only ever one copy of each and they're only generated once, with no need to deduplicate.

I agree that this is a natural desire to use some caching in this situation. But I join Alexander in the question how the proposed caching would work at module (cross-function) level? As I understand we can define %type1 register in func1 and refer to the register inside func1, but it's illegal to refer %type1 in func2 without a local definition of %type1 (let me remind that in SPIR-V the type definition is a regular MIR instruction which produces %type register).

In fact we do map types, constants, global vars and external function decls but at local function level (however I did not include this implementation to this series, replacing this with simple type/const instruction copying in extractInstructionsWithGlobalRegsToMetablockForMBB for now, in the next patches it will be changed to the map using). In llvm/lib/Target/SPIRV/SPIRVGlobalRegistry.h you can find the interface getOrCreateSPIRVType, which returns either existing OpType*** instruction or create new one. Then in GlobalTypesAndRegNumPass we walk the map and create only required type/const/var/fdecl instructions in the "global" function.
Anyway in this approach we need to leave the instructions' copies in regular functions to pass the verifier (in LLVM build with -DLLVM_ENABLE_EXPENSIVE_CHECKS=on -DLLVM_ENABLE_ABI_BREAKING_CHECKS=on).

Taking into account the implemented mapping now we keep duplicates at function level to make MIR consistent. For example:

After generation:

func1
  %0 = OpTypeInt 32
  %1 = OpTypeInt 64
  ...
  %4 = OpIAdd %1 %2 %3
  ...
func2
  %0 = OpTypeInt 32
  %1 = OpTypeInt 64
  ...
  %4 = OpIMul %1 %2 %3
  ...

After GlobalTypesAndRegNumPass:

global_func:
  %0 = OpTypeInt 32
  %1 = OpTypeInt 64
...
func1
  %0 = OpTypeInt 32
  %1 = OpTypeInt 64
  ...
  %4 = OpIAdd %1 %2 %3
  ...
func2
  %0 = OpTypeInt 32
  %1 = OpTypeInt 64
  ...
  %4 = OpIMul %1 %2 %3
  ...

After emitting:

global_func:
  %0 = OpTypeInt 32
  %1 = OpTypeInt 64
...
func1
  ...
  %4 = OpIAdd %1 %2 %3
  ...
func2
  ...
  %7 = OpIMul %1 %5 %6
  ...

And as far as I understand your suggestion this de-duplicated variant will break the verifier (after generation):

func1
  %0 = OpTypeInt 32
  %1 = OpTypeInt 64
  ...
  %4 = OpIAdd %1 %2 %3
  ...
func2
  // (no definition of %1)
  ... 
  %4 = OpIMul %1 %2 %3
  ...

[rengolin]

In D116465#3293156, @iliya-diyachkov wrote:

And as far as I understand your suggestion this de-duplicated variant will break the verifier (after generation):

func1
  %0 = OpTypeInt 32
  %1 = OpTypeInt 64
  ...
  %4 = OpIAdd %1 %2 %3
  ...
func2
  // (no definition of %1)
  ... 
  %4 = OpIMul %1 %2 %3
  ...

No, I'm suggestion you emit on every function (as is functionally correct) but reuse the same ID, and keep that same ID on global_function.

The singleton is just caching the VReg numbers, not the actual MNodes.

Code emission will be the same as what you have today after that.

I agree that this is a natural desire to use some caching in this situation. But I join Alexander in the question how the proposed caching would work at module (cross-function) level? As I understand we can define %type1 register in func1 and refer to the register inside func1, but it's illegal to refer %type1 in func2 without a local definition of %type1 (let me remind that in SPIR-V the type definition is a regular MIR instruction which produces %type register).

By just re-declaring each used type/constant in each subsequent function with the same VReg ID.

In your example:

After generation:

func1
  %0 = OpTypeInt 32
  %1 = OpTypeInt 64
  ...
  %4 = OpIAdd %1 %2 %3
  ...
func2
  %0 = OpTypeInt 32
  %1 = OpTypeInt 64
  ...
  %4 = OpIMul %1 %2 %3
  ...

After GlobalTypesAndRegNumPass:

global_func:
  %0 = OpTypeInt 32
  %1 = OpTypeInt 64
...
func1
  %0 = OpTypeInt 32
  %1 = OpTypeInt 64
  ...
  %4 = OpIAdd %1 %2 %3
  ...
func2
  %0 = OpTypeInt 32
  %1 = OpTypeInt 64
  ...
  %4 = OpIMul %1 %2 %3
  ...

To have the same MIR in your second example, straight from generation, you have to follow these steps:

• First time you see, generate a new type (OpTypeInt 32) with a new auto-increment ID, cache the ID for the original type, emit on global_func and *also* on the function you're generating.
• Every other time you see, get the cached VReg ID and re-emit (a new MNode) using that same ID.

In your example:

• Inside func1 you generate a new type (OpTypeInt 32) and call it %0, cache %0 for i32, emit on global_func and *also* on func1.
• Inside func2 you get the cached version (of i32 as %0) and generate it *again* only on func2 (on a new Node, using %0). global_func already have it's the same VReg number on all previous functions.

If you use a global auto-increment next_id(), there's no way VReg IDs for operations in any function will clash with previously defined types and constants (in previous functions).

The VReg numbers on the later functions will be (numerically) large, but the number of different IDs in each function will still be the same, so code generation should be equally efficient.

[zuban32]

In D116465#3293196, @rengolin wrote:

In D116465#3293156, @iliya-diyachkov wrote:

And as far as I understand your suggestion this de-duplicated variant will break the verifier (after generation):

func1
  %0 = OpTypeInt 32
  %1 = OpTypeInt 64
  ...
  %4 = OpIAdd %1 %2 %3
  ...
func2
  // (no definition of %1)
  ... 
  %4 = OpIMul %1 %2 %3
  ...

No, I'm suggestion you emit on every function (as is functionally correct) but reuse the same ID, and keep that same ID on global_function.

The singleton is just caching the VReg numbers, not the actual MNodes.

Code emission will be the same as what you have today after that.

I agree that this is a natural desire to use some caching in this situation. But I join Alexander in the question how the proposed caching would work at module (cross-function) level? As I understand we can define %type1 register in func1 and refer to the register inside func1, but it's illegal to refer %type1 in func2 without a local definition of %type1 (let me remind that in SPIR-V the type definition is a regular MIR instruction which produces %type register).

By just re-declaring each used type/constant in each subsequent function with the same VReg ID.

In your example:

After generation:

func1
  %0 = OpTypeInt 32
  %1 = OpTypeInt 64
  ...
  %4 = OpIAdd %1 %2 %3
  ...
func2
  %0 = OpTypeInt 32
  %1 = OpTypeInt 64
  ...
  %4 = OpIMul %1 %2 %3
  ...

After GlobalTypesAndRegNumPass:

global_func:
  %0 = OpTypeInt 32
  %1 = OpTypeInt 64
...
func1
  %0 = OpTypeInt 32
  %1 = OpTypeInt 64
  ...
  %4 = OpIAdd %1 %2 %3
  ...
func2
  %0 = OpTypeInt 32
  %1 = OpTypeInt 64
  ...
  %4 = OpIMul %1 %2 %3
  ...

To have the same MIR in your second example, straight from generation, you have to follow these steps:

• First time you see, generate a new type (OpTypeInt 32) with a new auto-increment ID, cache the ID for the original type, emit on global_func and *also* on the function you're generating.
• Every other time you see, get the cached VReg ID and re-emit (a new MNode) using that same ID.

In your example:

• Inside func1 you generate a new type (OpTypeInt 32) and call it %0, cache %0 for i32, emit on global_func and *also* on func1.
• Inside func2 you get the cached version (of i32 as %0) and generate it *again* only on func2 (on a new Node, using %0). global_func already have it's the same VReg number on all previous functions.

If you use a global auto-increment next_id(), there's no way VReg IDs for operations in any function will clash with previously defined types and constants (in previous functions).

The VReg numbers on the later functions will be (numerically) large, but the number of different IDs in each function will still be the same, so code generation should be equally efficient.

Not sure how we can control the VReg IDs emitted for the types - it seems it'd require customizing IRTranslator which is not allowed by the current GlobalISel design. Am I missing something?

[rengolin]

In D116465#3293994, @zuban32 wrote:

Not sure how we can control the VReg IDs emitted for the types - it seems it'd require customizing IRTranslator which is not allowed by the current GlobalISel design. Am I missing something?

As I said, I haven't worked with MIR directly (it was after my time on back-ends), so very likely I am the one missing context.

I don't mind this as it is on an experimental target, but it would be nice to not have to do that in the long run (though, it wouldn't be tragic either).

If @arsenm and @MaskRay are happy with this patch, I'm happy too. I'll let them approve this one.

[iliya-diyachkov]

In D116465#3293196, @rengolin wrote:

If you use a global auto-increment next_id(), there's no way VReg IDs for operations in any function will clash with previously defined types and constants (in previous functions).

The VReg numbers on the later functions will be (numerically) large, but the number of different IDs in each function will still be the same, so code generation should be equally efficient.

Thanks for the explanation, now I see the whole idea and I like it in general. The following example illustrates its work.

After func1 translation:

global_func
  %0 = OpTypeConstGVarFDecl1

func1
  %0 = OpTypeConstGVarFDecl1
  ...
  %3 = OpIAdd %0 %1 %2
  ...
  %N = ...

After func2 translation:

global_func
  %0 = OpTypeConstGVarFDecl1
  %N+1 = OpTypeConstGVarFDecl2

func2
  %0 = OpTypeConstGVarFDecl1
  %N+1 = OpTypeConstGVarFDecl2
  ...
  %N+4 = OpIMul %0 %N+2 %N+3
  %N+7 = OpIAdd %N+1 %N+5 %N+6
  ...
  %M = ...

And so on... However I see several issues:

1. We probably need to operate with global_func and the current function (func1 or func2 in the example) simultaneously when we generate a new type. I'm not sure is it possible in a MachineFunctionPass.

Perhaps we would introduce a new ModulePass which generates most of type/const/gvar/fdecl instrs. But some of the instrs can be generated in CallLowering and InstructionSelector which are not module-level, so we could not modify both global_func and the current function.

2. As Aleksander wrote some virtual registers in regular functions are generated by IRTranslator and we don't directly control their numbers (normally it starts from %0).

We could use some weird (or "non-statutory") approaches for setting first NumVirtRegs in each next regular function so it will generate %N+1, %N+2 as in example. I have just implemented such one without changes in target-independent code. But since this is a non-standard thing, we cannot be sure that it will work always and reliably.

Either we could make a new method in IRTranslator that allows to start NumVirtRegs from desirable number, but it will be a target independent feature and its justification (it is unlikely that it will ever be needed for other targets), review and commit may take a noticeable time.

3. This may require a noticeable rework of the current implementation (I don't mean this patch series, but the entire backend that is in Khronos repository, because all changes we do in this patch series are implemented in the main code base at first with checking for no degradation on >200 LITs and OpenCL CTS).

So if we don't have obvious solutions for the 1st and 2nd issues, I would add this suggestion to the TODO list (we'll take it in mind during further code revisions) and go forward with the existing GlobalTypesAndRegNumPass.

[rengolin]

In D116465#3295139, @iliya-diyachkov wrote:

So if we don't have obvious solutions for the 1st and 2nd issues, I would add this suggestion to the TODO list (we'll take it in mind during further code revisions) and go forward with the existing GlobalTypesAndRegNumPass.

Agreed. With that in mind, this looks good to me.

I'll let the other reviewers have the final approval, just to make sure we all agree.

Thanks!

[iliya-diyachkov]

SPIRVBlockLabeler pass was removed and its functionality migrated to SPIRVAsmPrinter. The change was inspired by Renato's suggestion about get_next_id().

[arsenm]

llvm/lib/Target/SPIRV/SPIRVGlobalTypesAndRegNumPass.cpp

23 ↗

(On Diff #396830)

This sounds like a function of emission to me. I don't see why you need a dummy MIR function or move anything for the purpose of having a global value. You could just emit the global values directly where they need to go as part of the emission of the individual operation.

The AsmPrinter is a module pass, so it's possible to operate globally

[arsenm]

llvm/lib/Target/SPIRV/SPIRVGlobalTypesAndRegNumPass.cpp

23 ↗

(On Diff #396830)

Basically the dummy function feels like an awkward hack of SPIR-V's constraints into MIR. It would be more natural to handle the structural differences in representation when actually producing the final SPIR-V

[zuban32]

llvm/lib/Target/SPIRV/SPIRVGlobalTypesAndRegNumPass.cpp

23 ↗

(On Diff #396830)

The AsmPrinter is a module pass, so it's possible to operate globally

But it seems currently AsmPrinter is a MachineFunctionPass

[zuban32]

llvm/lib/Target/SPIRV/SPIRVGlobalTypesAndRegNumPass.cpp

23 ↗

(On Diff #396830)

Ok, now I see, AsmPrinter still has emit* methods operating on the whole module (but it's still a MachineFunctionPass, isn't there some design flaw?)

[arsenm]

llvm/lib/Target/SPIRV/SPIRVGlobalTypesAndRegNumPass.cpp

23 ↗

(On Diff #396830)

The final module necessarily requires emitting module level directives of some kind. This is fine as long as you aren't relying on changes in other functions when emitting another

[iliya-diyachkov]

This sounds like a function of emission to me. I don't see why you need a dummy MIR function or move anything for the purpose of having a global value. You could just emit the global values directly where they need to go as part of the emission of the individual operation.

The AsmPrinter is a module pass, so it's possible to operate globally
Basically the dummy function feels like an awkward hack of SPIR-V's constraints into MIR. It would be more natural to handle the structural differences in representation when actually producing the final SPIR-V

Thanks for your explanation, Matt. I agree that a dummy "global" function looks like a kind of hack, and working with the function is not elegant and not very convenient.

Believing that AsmPrinter can be used as a module pass, I have implemented a prototype of moved GlobalTypesAndRegNum functionality to AsmPrinter with partial success. And I have found this issue.

If GlobalTypesAndRegNum pass is removed (it was a global pass and the last pass before AsmPrinter), we have following sequence of passes/calls for a program with N functions:

SPIRVAsmPrinter::doInitialization 
    AsmPrinter::emitStartOfAsmFile

func1:
SPIRVGISelPass1 ... SPIRVGISelPassLast
AsmPrinter::runOnMachineFunction
    SPIRVAsmPrinter::emitFunctionHeader
        emit func1's instructions by SPIRVAsmPrinter::emitInstruction
***
funcN:
SPIRVGISelPass1...SPIRVGISelPassLast
AsmPrinter::runOnMachineFunction
    SPIRVAsmPrinter::emitFunctionHeader
        emit funcN's instructions by SPIRVAsmPrinter::emitInstruction

SPIRVAsmPrinter::emitEndOfAsmFile

I.e. at the moment of AsmPrinter::runOnMachineFunction invocation for func1 we have not whole MIR and cannot number registers globally and output global instruction at the beginning of the module but func1's instructions should be emitted.

In this pass sequence I don't see a point where all functions' MIR is available in AsmPrinter and the first func1 is not emitted yet. Therefore global register numbering and the global instruction output cannot be applied correctly (on the entire MIR).

On other hand if I leave an empty global pass as a last of post GISel passes, the sequence is different:

SPIRVAsmPrinter::doInitialization
    AsmPrinter::emitStartOfAsmFile

func1:
SPIRVGISelPass1 ... SPIRVGISelPassLast
***
funcN:
SPIRVGISelPass1 ... SPIRVGISelPassLast

SPIRVDummyGlobalPass

func1:
AsmPrinter::runOnMachineFunction
    SPIRVAsmPrinter::emitFunctionHeader
        emit func1's instructions by SPIRVAsmPrinter::emitInstruction
***
funcN:
AsmPrinter::runOnMachineFunction
    SPIRVAsmPrinter::emitFunctionHeader
        emit funcN's instructions by SPIRVAsmPrinter::emitInstruction

SPIRVAsmPrinter::emitEndOfAsmFile

Now I can run the functionality ported from GlobalTypesAndRegNum on the first invocation of AsmPrinter::runOnMachineFunction and get correct register numbering and global instruction output. Using this way the backend has passed all our LIT tests.

@arsenm, when you suggested moving GlobalTypesAndRegNum' operations to AsmPrinter, did you implied that we need to insert SPIRVDummyGlobalPass after all SPIRVGISel passes to have whole MIR at the first run of AsmPrinter? Or is there another approach (or some pass configuration) to achieve the correct processing of the whole MIR in AsmPrinter?

[zuban32]

In D116465#3320801, @iliya-diyachkov wrote:

@arsenm, when you suggested moving GlobalTypesAndRegNum' operations to AsmPrinter, did you implied that we need to insert SPIRVDummyGlobalPass after all SPIRVGISel passes to have whole MIR at the first run of AsmPrinter? Or is there another approach (or some pass configuration) to achieve the correct processing of the whole MIR in AsmPrinter?

[I'm not Matt but] to me it seems like a hack which is not much better that the one we used to have with the MIR pass. I suppose the passes ordering would be the same if we just made the AsmPrinter a module pass instead of adding a dummy one, not sure about the potential consequences in the other targets though. @arsenm what do you think?

[iliya-diyachkov]

In D116465#3320976, @zuban32 wrote:

In D116465#3320801, @iliya-diyachkov wrote:

@arsenm, when you suggested moving GlobalTypesAndRegNum' operations to AsmPrinter, did you implied that we need to insert SPIRVDummyGlobalPass after all SPIRVGISel passes to have whole MIR at the first run of AsmPrinter? Or is there another approach (or some pass configuration) to achieve the correct processing of the whole MIR in AsmPrinter?

[I'm not Matt but] to me it seems like a hack which is not much better that the one we used to have with the MIR pass. I suppose the passes ordering would be the same if we just made the AsmPrinter a module pass instead of adding a dummy one, not sure about the potential consequences in the other targets though. @arsenm what do you think?

Thanks for your opinion, Aleksandr. I think this would be a smaller hack than we have now. I'll share the rough implementation in Khronos soon, so (since you know the full implementation of SPIRVGlobalTypesAndRegNumPass.cpp) you can appreciate the efficiency of this approach. In short, using it, we don't need to

1. create the dummy "global" function,
2. copy global MIs from real functions to the "global" one,
3. make MIR consistent in the "global" and real functions after 1 and 2.

Also the implementation becomes shorter and looks simpler and more natural.

What about making AsmPrinter a module pass, it's a big target-independent change, I'm not sure that it can be justified only by the fact that the SPIRV experimental backend can get some advantage.

[arsenm]

In D116465#3320801, @iliya-diyachkov wrote:

@arsenm, when you suggested moving GlobalTypesAndRegNum' operations to AsmPrinter, did you implied that we need to insert SPIRVDummyGlobalPass after all SPIRVGISel passes to have whole MIR at the first run of AsmPrinter? Or is there another approach (or some pass configuration) to achieve the correct processing of the whole MIR in AsmPrinter?

If you can emit this global information at the end of the printed module instead of the start, that would be easiest. If you really have to emit it at the top, you may be able to get away with something similar to what AMDGPU does for reporting total register counts used in the presence of indirect function calls. AMDGPUAsmPrinter depends on a module analysis, AMDGPUResourceUsageAnalysis. This effectively forces all functions to be codegened before final emission (which does have an associated compile time / memory cost)

[iliya-diyachkov]

In D116465#3321209, @arsenm wrote:

In D116465#3320801, @iliya-diyachkov wrote:

@arsenm, when you suggested moving GlobalTypesAndRegNum' operations to AsmPrinter, did you implied that we need to insert SPIRVDummyGlobalPass after all SPIRVGISel passes to have whole MIR at the first run of AsmPrinter? Or is there another approach (or some pass configuration) to achieve the correct processing of the whole MIR in AsmPrinter?

If you can emit this global information at the end of the printed module instead of the start, that would be easiest. If you really have to emit it at the top, you may be able to get away with something similar to what AMDGPU does for reporting total register counts used in the presence of indirect function calls. AMDGPUAsmPrinter depends on a module analysis, AMDGPUResourceUsageAnalysis. This effectively forces all functions to be codegened before final emission (which does have an associated compile time / memory cost)

Thanks for the advice, Matt! The SPIR-V specification requires the info at the beginning of the module.

So we need to implement SPIRVModuleAnalysis, make SPIRVAsmPrinter to be depended on it and use the analysis results in the first invocation of AsmPrinter::runOnMachineFunction to output global instructions before all real functions.

[iliya-diyachkov]

In general the approach works fine, but if we have no functions at module, SPIRVAsmPrinter::runOnMachineFunction() is not called and we have to output global instructions later, during AsmPrinter::doFinalization(). At this point, calling getAnalysis<SPIRVModuleAnalysis>() fails because Resolver (in Pass::getAnalysisID(AnalysisID PI)) cannot find SPIRVModuleAnalysis.

The issue can be solved by storing the analysis results in a static member of SPIRVModuleAnalysis. In such implementation, the results are available both in SPIRVAsmPrinter::runOnMachineFunction() and in SPIRVAsmPrinter::doFinalization() and we don't even need to call getAnalysis<SPIRVModuleAnalysis>() in SPIRVAsmPrinter.

I think this small trick is acceptable for the experimental backend if there is no other way to get the analysis results in doFinalization().

[iliya-diyachkov]

The functionality of SPIRVGlobalTypesAndRegNum pass was moved to SPIRVModuleAnalysis pass and extended AsmPrinter.

[iliya-diyachkov]

The formatting issue is fixed.

[iliya-diyachkov]

I think all noticed issues are fixed in this patch, as well as in others in the series. The patches were rebased to the latest LLVM version (0712c575b90a7eb508bf43d15c38c1c0b0d69695, Fri Feb 18). Also the regular and special builds (suggested by Fengrui Song in the first patch) were passed without new fails in LIT tests.

@arsenm @MaskRay could you please review the updated patches again.

[iliya-diyachkov]

Gentle ping.

[iliya-diyachkov]

Move MS static array inside struct ModuleAnalysisInfo.

[iliya-diyachkov]

@arsenm @MaskRay could you please review the patches again?

As I wrote earlier, all issues were fixed in all patches of the series. The day before yesterday I rebased all patches to the latest LLVM version (17a68065c378, Sun Mar 6) and checked the regular and special builds (suggested in the first patch).

[iliya-diyachkov]

Fixed typos in comments.

[iliya-diyachkov]

Update after the last changes in the previous patches.

[iliya-diyachkov]

Gentle ping.

[iliya-diyachkov]

Update after the last changes in the 3th and 4th patches.

[iliya-diyachkov]

Update after the last change in the 5th patch.

[iliya-diyachkov]

The format issue is fixed.

[mpaszkowski]

Gentle ping for final review and acceptance :)

Hi @arsenm, could you please take a look at the 4th, 5th, and 6th patch and let us know whether your suggestions were resolved? We would like to kindly ask for "LGTM".

[iliya-diyachkov]

In D116465#3380567, @iliya-diyachkov wrote:

Gentle ping.

@arsenm @MaskRay could you please continue or finish the review of the 4th, 5th and 6th patches? As I wrote earlier, all the issues were fixed in all patches of the series.

[iliya-diyachkov]

I updated LLVM to today's revision 73777b4c35a3 and retested all recommended builds. All of them are passed.

[iliya-diyachkov]

The patch has been updated after the changes in 4th and 5th ones. Also, "unsigned int"s were replaced with "unsigned"s, and missed dots were inserted into comments, as Fangrui recommended in the 4th patch.

[iliya-diyachkov]

Update after the change in the 3rd patch.

[arsenm]

llvm/lib/Target/SPIRV/SPIRVAsmPrinter.cpp

43

Might as well use SPIRVSubtarget?

47

getSubtarget<SPIRVSubtarget>() instead of static_cast

118

Can't have global constructors

136

Typo correspnding

137

static?

161

If this isn't checked by the verifier (which would be preferable), should be report_fatal_error

llvm/lib/Target/SPIRV/SPIRVModuleAnalysis.cpp

162

I don't think this can fail at this point? If not, should early continue or assert and reduce indentation

201

Ditto

[iliya-diyachkov]

llvm/lib/Target/SPIRV/SPIRVAsmPrinter.cpp

43

You probably mean removing STI and using OutContext.getSubtargetInfo().

47

As I see we need to have either MachineFunction or Function to call getSubtarget<SPIRVSubtarget>().
However in SPIRVAsmPrinter ST is required even if there are no functions in the module. I don't see any other way than to use static_cast as some other targets do (e.g. in NVPTXAsmPrinter::emitStartOfAsmFile or in AVRAsmPrinter::emitStartOfAsmFile). If you know, please advise.

118

I'll move BBNumToRegMap into struct ModuleAnalysisInfo.

137

getOrCreateMBBRegister() was not static since it was called in SPIRVMCInstLower.cpp (outside of this module). I'll make getOrCreateMBBRegister() a member of struct ModuleAnalysisInfo as well as BBNumToRegMap.

161

I believe that it is not checked. I'll add the appropriate TODO and change llvm_unreachable to report_fatal_error.

llvm/lib/Target/SPIRV/SPIRVModuleAnalysis.cpp

162

This can fail if F is a declaration. I'll add early continue.

[iliya-diyachkov]

The patch was updated after the last changes in the 5th one. Also ModuleSectionType and ModuleAnalysisInfo were placed in the SPIRV namespace.

[iliya-diyachkov]

The changes in SPIRVUtils from the 6th patch were moved to the 5th patch. The last case of "unsigned int" was replaced with "unsigned".

@arsenm, @MaskRay, I think all the issues have been fixed. Could you please take the last look at the patches?

[rengolin]

This one still has some unactioned comments...

[iliya-diyachkov]

In D116465#3431960, @rengolin wrote:

This one still has some unactioned comments...

@rengolin, do you mean that some issues pointed out by Matt have not been fixed? I thought everything was done, except for the suggestion to use getSubtarget<SPIRVSubtarget>() instead of static_cast in SPIRVAsmPrinter constructor. I explained that it was not clear how to efficiently apply this suggestion to our case.

[rengolin]

Apologies, it seems I was looking into a very old version of the review!

This looks good to me. @arsenm did that answer your comment?

[arsenm]

llvm/lib/Target/SPIRV/SPIRVAsmPrinter.cpp

47

Oh, this points out a deeper issue that you're using the global subtarget. Ideally you're always querying the subtarget from the context function

[arsenm]

In D116465#3432021, @rengolin wrote:

Apologies, it seems I was looking into a very old version of the review!

This looks good to me. @arsenm did that answer your comment?

Yes, but it points to another issue (one that SPIRV specifically probably doesn't care about)

[iliya-diyachkov]

llvm/lib/Target/SPIRV/SPIRVAsmPrinter.cpp

47

I understand this, but in some cases we have a module without functions, and we still need to use Subtarget.

We could get Subtarget using static_cast when initializing AsmPrinter. Then if there are MachineFunctions in the module, we will get Subtarget using MF.getSubtarget<SPIRVSubtarget>() in emitFunctionHeader() for each MachineFunction.
Does this approach make sense?

[arsenm]

llvm/lib/Target/SPIRV/SPIRVAsmPrinter.cpp

47

Yes, each function should query the subtarget

[iliya-diyachkov]

llvm/lib/Target/SPIRV/SPIRVAsmPrinter.cpp

47

Ok, I'll implement it later today.

[iliya-diyachkov]

Query ST for each function (in SPIRVAsmPrinter).

[iliya-diyachkov]

Updated after the last changes in the 4th and 5th patches.

[mpaszkowski]

Ping! We kindly ask for "LGTM" :)

[iliya-diyachkov]

Gentle ping. @arsenm please take a look at the final version of this patch.

[arsenm]

LGTM with nit

llvm/lib/Target/SPIRV/SPIRVModuleAnalysis.cpp

210–216

Could use another continue and indentation reduction

[iliya-diyachkov]

The indentation issue has been fixed.

[iliya-diyachkov]

Thank you for finishing the review of this series, Matt!

llvm/lib/Target/SPIRV/CMakeLists.txt

add_llvm_target(SPIRVCodeGen
   SPIRVAsmPrinter.cpp
   SPIRVCallLowering.cpp
   SPIRVGlobalRegistry.cpp
   SPIRVInstrInfo.cpp
   SPIRVInstructionSelector.cpp
   SPIRVISelLowering.cpp
   SPIRVLegalizerInfo.cpp
   SPIRVMCInstLower.cpp
+  SPIRVModuleAnalysis.cpp
   SPIRVRegisterBankInfo.cpp
   SPIRVRegisterInfo.cpp
   SPIRVSubtarget.cpp
   SPIRVTargetMachine.cpp
   SPIRVUtils.cpp
 
   LINK_COMPONENTS
   Analysis

llvm/lib/Target/SPIRV/MCTargetDesc/SPIRVInstPrinter.cpp

 //===-- SPIRVInstPrinter.cpp - Output SPIR-V MCInsts as ASM -----*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This class prints a SPIR-V MCInst to a .s file.
 //
 //===----------------------------------------------------------------------===//
 
 #include "SPIRVInstPrinter.h"
+#include "SPIRV.h"
+#include "SPIRVBaseInfo.h"
 #include "llvm/CodeGen/Register.h"
 #include "llvm/MC/MCAsmInfo.h"
 #include "llvm/MC/MCExpr.h"
 #include "llvm/MC/MCInst.h"
 #include "llvm/MC/MCInstrInfo.h"
 #include "llvm/MC/MCSymbol.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/ErrorHandling.h"

 
 void SPIRVInstPrinter::recordOpExtInstImport(const MCInst *MI) {
   llvm_unreachable("Unimplemented recordOpExtInstImport");
 }
 
 void SPIRVInstPrinter::printInst(const MCInst *MI, uint64_t Address,
                                  StringRef Annot, const MCSubtargetInfo &STI,
                                  raw_ostream &OS) {
+  const unsigned OpCode = MI->getOpcode();
   printInstruction(MI, Address, OS);
+
+  if (OpCode == SPIRV::OpDecorate) {
+    printOpDecorate(MI, OS);
+  } else if (OpCode == SPIRV::OpExtInstImport) {
+    recordOpExtInstImport(MI);
+  } else if (OpCode == SPIRV::OpExtInst) {
+    printOpExtInst(MI, OS);
+  } else {
+    // Print any extra operands for variadic instructions.
+    MCInstrDesc MCDesc = MII.get(OpCode);
+    if (MCDesc.isVariadic()) {
+      const unsigned NumFixedOps = MCDesc.getNumOperands();
+      const unsigned LastFixedIndex = NumFixedOps - 1;
+      const int FirstVariableIndex = NumFixedOps;
+      if (NumFixedOps > 0 &&
+          MCDesc.OpInfo[LastFixedIndex].OperandType == MCOI::OPERAND_UNKNOWN) {
+        // For instructions where a custom type (not reg or immediate) comes as
+        // the last operand before the variable_ops. This is usually a StringImm
+        // operand, but there are a few other cases.
+        switch (OpCode) {
+        case SPIRV::OpTypeImage:
+          OS << ' ';
+          printAccessQualifier(MI, FirstVariableIndex, OS);
+          break;
+        case SPIRV::OpVariable:
+          OS << ' ';
+          printOperand(MI, FirstVariableIndex, OS);
+          break;
+        case SPIRV::OpEntryPoint: {
+          // Print the interface ID operands, skipping the name's string
+          // literal.
+          printRemainingVariableOps(MI, NumFixedOps, OS, false, true);
+          break;
+        }
+        case SPIRV::OpExecutionMode:
+        case SPIRV::OpExecutionModeId:
+        case SPIRV::OpLoopMerge: {
+          // Print any literals after the OPERAND_UNKNOWN argument normally.
+          printRemainingVariableOps(MI, NumFixedOps, OS);
+          break;
+        }
+        default:
+          break; // printStringImm has already been handled
+        }
+      } else {
+        // For instructions with no fixed ops or a reg/immediate as the final
+        // fixed operand, we can usually print the rest with "printOperand", but
+        // check for a few cases with custom types first.
+        switch (OpCode) {
+        case SPIRV::OpLoad:
+        case SPIRV::OpStore:
+          OS << ' ';
+          printMemoryOperand(MI, FirstVariableIndex, OS);
+          printRemainingVariableOps(MI, FirstVariableIndex + 1, OS);
+          break;
+        case SPIRV::OpImageSampleImplicitLod:
+        case SPIRV::OpImageSampleDrefImplicitLod:
+        case SPIRV::OpImageSampleProjImplicitLod:
+        case SPIRV::OpImageSampleProjDrefImplicitLod:
+        case SPIRV::OpImageFetch:
+        case SPIRV::OpImageGather:
+        case SPIRV::OpImageDrefGather:
+        case SPIRV::OpImageRead:
+        case SPIRV::OpImageWrite:
+        case SPIRV::OpImageSparseSampleImplicitLod:
+        case SPIRV::OpImageSparseSampleDrefImplicitLod:
+        case SPIRV::OpImageSparseSampleProjImplicitLod:
+        case SPIRV::OpImageSparseSampleProjDrefImplicitLod:
+        case SPIRV::OpImageSparseFetch:
+        case SPIRV::OpImageSparseGather:
+        case SPIRV::OpImageSparseDrefGather:
+        case SPIRV::OpImageSparseRead:
+        case SPIRV::OpImageSampleFootprintNV:
+          OS << ' ';
+          printImageOperand(MI, FirstVariableIndex, OS);
+          printRemainingVariableOps(MI, NumFixedOps + 1, OS);
+          break;
+        case SPIRV::OpCopyMemory:
+        case SPIRV::OpCopyMemorySized: {
+          const unsigned NumOps = MI->getNumOperands();
+          for (unsigned i = NumFixedOps; i < NumOps; ++i) {
+            OS << ' ';
+            printMemoryOperand(MI, i, OS);
+            if (MI->getOperand(i).getImm() &
+                static_cast<unsigned>(SPIRV::MemoryOperand::Aligned)) {
+              assert(i + 1 < NumOps && "Missing alignment operand");
+              OS << ' ';
+              printOperand(MI, i + 1, OS);
+              i += 1;
+            }
+          }
+          break;
+        }
+        case SPIRV::OpConstantI:
+        case SPIRV::OpConstantF:
+          printOpConstantVarOps(MI, NumFixedOps, OS);
+          break;
+        default:
+          printRemainingVariableOps(MI, NumFixedOps, OS);
+          break;
+        }
+      }
+    }
+  }
+
   printAnnotation(OS, Annot);
 }
 
 void SPIRVInstPrinter::printOpExtInst(const MCInst *MI, raw_ostream &O) {
   llvm_unreachable("Unimplemented printOpExtInst");
 }
 
 void SPIRVInstPrinter::printOpDecorate(const MCInst *MI, raw_ostream &O) {
-  llvm_unreachable("Unimplemented printOpDecorate");
+  // The fixed operands have already been printed, so just need to decide what
+  // type of decoration operands to print based on the Decoration type.
+  MCInstrDesc MCDesc = MII.get(MI->getOpcode());
+  unsigned NumFixedOps = MCDesc.getNumOperands();
+
+  if (NumFixedOps != MI->getNumOperands()) {
+    auto DecOp = MI->getOperand(NumFixedOps - 1);
+    auto Dec = static_cast<SPIRV::Decoration>(DecOp.getImm());
+
+    O << ' ';
+
+    switch (Dec) {
+    case SPIRV::Decoration::BuiltIn:
+      printBuiltIn(MI, NumFixedOps, O);
+      break;
+    case SPIRV::Decoration::UniformId:
+      printScope(MI, NumFixedOps, O);
+      break;
+    case SPIRV::Decoration::FuncParamAttr:
+      printFunctionParameterAttribute(MI, NumFixedOps, O);
+      break;
+    case SPIRV::Decoration::FPRoundingMode:
+      printFPRoundingMode(MI, NumFixedOps, O);
+      break;
+    case SPIRV::Decoration::FPFastMathMode:
+      printFPFastMathMode(MI, NumFixedOps, O);
+      break;
+    case SPIRV::Decoration::LinkageAttributes:
+    case SPIRV::Decoration::UserSemantic:
+      printStringImm(MI, NumFixedOps, O);
+      break;
+    default:
+      printRemainingVariableOps(MI, NumFixedOps, O, true);
+      break;
+    }
+  }
 }
 
 static void printExpr(const MCExpr *Expr, raw_ostream &O) {
 #ifndef NDEBUG
   const MCSymbolRefExpr *SRE;
 
   if (const MCBinaryExpr *BE = dyn_cast<MCBinaryExpr>(Expr))
     SRE = cast<MCSymbolRefExpr>(BE->getLHS());
else if (Op.isExpr())
       printExpr(Op.getExpr(), O);
     else
       llvm_unreachable("Unexpected operand type");
   }
 }
 
 void SPIRVInstPrinter::printStringImm(const MCInst *MI, unsigned OpNo,
                                       raw_ostream &O) {
-  llvm_unreachable("Unimplemented printStringImm");
+  const unsigned NumOps = MI->getNumOperands();
+  unsigned StrStartIndex = OpNo;
+  while (StrStartIndex < NumOps) {
+    if (MI->getOperand(StrStartIndex).isReg())
+      break;
+
+    std::string Str = getSPIRVStringOperand(*MI, OpNo);
+    if (StrStartIndex != OpNo)
+      O << ' '; // Add a space if we're starting a new string/argument.
+    O << '"';
+    for (char c : Str) {
+      if (c == '"')
+        O.write('\\'); // Escape " characters (might break for complex UTF-8).
+      O.write(c);
+    }
+    O << '"';
+
+    unsigned numOpsInString = (Str.size() / 4) + 1;
+    StrStartIndex += numOpsInString;
+
+    // Check for final Op of "OpDecorate %x %stringImm %linkageAttribute".
+    if (MI->getOpcode() == SPIRV::OpDecorate &&
+        MI->getOperand(1).getImm() ==
+            static_cast<unsigned>(SPIRV::Decoration::LinkageAttributes)) {
+      O << ' ';
+      printLinkageType(MI, StrStartIndex, O);
+      break;
+    }
+  }
 }
 
 void SPIRVInstPrinter::printExtInst(const MCInst *MI, unsigned OpNo,
                                     raw_ostream &O) {
   llvm_unreachable("Unimplemented printExtInst");
 }
 
-// Methods for printing textual names of SPIR-V enums.
-#define GEN_INSTR_PRINTER_IMPL(EnumName)                                       \
-  void SPIRVInstPrinter::print##EnumName(const MCInst *MI, unsigned OpNo,      \
-                                         raw_ostream &O) {                     \
-    llvm_unreachable("Unimplemented print" #EnumName);                         \
-  }
-GEN_INSTR_PRINTER_IMPL(Capability)
-GEN_INSTR_PRINTER_IMPL(SourceLanguage)
-GEN_INSTR_PRINTER_IMPL(ExecutionModel)
-GEN_INSTR_PRINTER_IMPL(AddressingModel)
-GEN_INSTR_PRINTER_IMPL(MemoryModel)
-GEN_INSTR_PRINTER_IMPL(ExecutionMode)
-GEN_INSTR_PRINTER_IMPL(StorageClass)
-GEN_INSTR_PRINTER_IMPL(Dim)
-GEN_INSTR_PRINTER_IMPL(SamplerAddressingMode)
-GEN_INSTR_PRINTER_IMPL(SamplerFilterMode)
-GEN_INSTR_PRINTER_IMPL(ImageFormat)
-GEN_INSTR_PRINTER_IMPL(ImageChannelOrder)
-GEN_INSTR_PRINTER_IMPL(ImageChannelDataType)
-GEN_INSTR_PRINTER_IMPL(ImageOperand)
-GEN_INSTR_PRINTER_IMPL(FPFastMathMode)
-GEN_INSTR_PRINTER_IMPL(FPRoundingMode)
-GEN_INSTR_PRINTER_IMPL(LinkageType)
-GEN_INSTR_PRINTER_IMPL(AccessQualifier)
-GEN_INSTR_PRINTER_IMPL(FunctionParameterAttribute)
-GEN_INSTR_PRINTER_IMPL(Decoration)
-GEN_INSTR_PRINTER_IMPL(BuiltIn)
-GEN_INSTR_PRINTER_IMPL(SelectionControl)
-GEN_INSTR_PRINTER_IMPL(LoopControl)
-GEN_INSTR_PRINTER_IMPL(FunctionControl)
-GEN_INSTR_PRINTER_IMPL(MemorySemantics)
-GEN_INSTR_PRINTER_IMPL(MemoryOperand)
-GEN_INSTR_PRINTER_IMPL(Scope)
-GEN_INSTR_PRINTER_IMPL(GroupOperation)
-GEN_INSTR_PRINTER_IMPL(KernelEnqueueFlags)
-GEN_INSTR_PRINTER_IMPL(KernelProfilingInfo)
+void SPIRVInstPrinter::printCapability(const MCInst *MI, unsigned OpNo,
+                                       raw_ostream &O) {
+  if (OpNo < MI->getNumOperands()) {
+    SPIRV::Capability e =
+        static_cast<SPIRV::Capability>(MI->getOperand(OpNo).getImm());
+    O << SPIRV::getCapabilityName(e);
+  }
+}
+
+void SPIRVInstPrinter::printSourceLanguage(const MCInst *MI, unsigned OpNo,
+                                           raw_ostream &O) {
+  if (OpNo < MI->getNumOperands()) {
+    SPIRV::SourceLanguage e =
+        static_cast<SPIRV::SourceLanguage>(MI->getOperand(OpNo).getImm());
+    O << SPIRV::getSourceLanguageName(e);
+  }
+}
+
+void SPIRVInstPrinter::printExecutionModel(const MCInst *MI, unsigned OpNo,
+                                           raw_ostream &O) {
+  if (OpNo < MI->getNumOperands()) {
+    SPIRV::ExecutionModel e =
+        static_cast<SPIRV::ExecutionModel>(MI->getOperand(OpNo).getImm());
+    O << SPIRV::getExecutionModelName(e);
+  }
+}
+
+void SPIRVInstPrinter::printAddressingModel(const MCInst *MI, unsigned OpNo,
+                                            raw_ostream &O) {
+  if (OpNo < MI->getNumOperands()) {
+    SPIRV::AddressingModel e =
+        static_cast<SPIRV::AddressingModel>(MI->getOperand(OpNo).getImm());
+    O << SPIRV::getAddressingModelName(e);
+  }
+}
+
+void SPIRVInstPrinter::printMemoryModel(const MCInst *MI, unsigned OpNo,
+                                        raw_ostream &O) {
+  if (OpNo < MI->getNumOperands()) {
+    SPIRV::MemoryModel e =
+        static_cast<SPIRV::MemoryModel>(MI->getOperand(OpNo).getImm());
+    O << SPIRV::getMemoryModelName(e);
+  }
+}
+
+void SPIRVInstPrinter::printExecutionMode(const MCInst *MI, unsigned OpNo,
+                                          raw_ostream &O) {
+  if (OpNo < MI->getNumOperands()) {
+    SPIRV::ExecutionMode e =
+        static_cast<SPIRV::ExecutionMode>(MI->getOperand(OpNo).getImm());
+    O << SPIRV::getExecutionModeName(e);
+  }
+}
+
+void SPIRVInstPrinter::printStorageClass(const MCInst *MI, unsigned OpNo,
+                                         raw_ostream &O) {
+  if (OpNo < MI->getNumOperands()) {
+    SPIRV::StorageClass e =
+        static_cast<SPIRV::StorageClass>(MI->getOperand(OpNo).getImm());
+    O << SPIRV::getStorageClassName(e);
+  }
+}
+
+void SPIRVInstPrinter::printDim(const MCInst *MI, unsigned OpNo,
+                                raw_ostream &O) {
+  if (OpNo < MI->getNumOperands()) {
+    SPIRV::Dim e = static_cast<SPIRV::Dim>(MI->getOperand(OpNo).getImm());
+    O << SPIRV::getDimName(e);
+  }
+}
+
+void SPIRVInstPrinter::printSamplerAddressingMode(const MCInst *MI,
+                                                  unsigned OpNo,
+                                                  raw_ostream &O) {
+  if (OpNo < MI->getNumOperands()) {
+    SPIRV::SamplerAddressingMode e = static_cast<SPIRV::SamplerAddressingMode>(
+        MI->getOperand(OpNo).getImm());
+    O << SPIRV::getSamplerAddressingModeName(e);
+  }
+}
+
+void SPIRVInstPrinter::printSamplerFilterMode(const MCInst *MI, unsigned OpNo,
+                                              raw_ostream &O) {
+  if (OpNo < MI->getNumOperands()) {
+    SPIRV::SamplerFilterMode e =
+        static_cast<SPIRV::SamplerFilterMode>(MI->getOperand(OpNo).getImm());
+    O << SPIRV::getSamplerFilterModeName(e);
+  }
+}
+
+void SPIRVInstPrinter::printImageFormat(const MCInst *MI, unsigned OpNo,
+                                        raw_ostream &O) {
+  if (OpNo < MI->getNumOperands()) {
+    SPIRV::ImageFormat e =
+        static_cast<SPIRV::ImageFormat>(MI->getOperand(OpNo).getImm());
+    O << SPIRV::getImageFormatName(e);
+  }
+}
+
+void SPIRVInstPrinter::printImageChannelOrder(const MCInst *MI, unsigned OpNo,
+                                              raw_ostream &O) {
+  if (OpNo < MI->getNumOperands()) {
+    SPIRV::ImageChannelOrder e =
+        static_cast<SPIRV::ImageChannelOrder>(MI->getOperand(OpNo).getImm());
+    O << SPIRV::getImageChannelOrderName(e);
+  }
+}
+
+void SPIRVInstPrinter::printImageChannelDataType(const MCInst *MI,
+                                                 unsigned OpNo,
+                                                 raw_ostream &O) {
+  if (OpNo < MI->getNumOperands()) {
+    SPIRV::ImageChannelDataType e =
+        static_cast<SPIRV::ImageChannelDataType>(MI->getOperand(OpNo).getImm());
+    O << SPIRV::getImageChannelDataTypeName(e);
+  }
+}
+
+void SPIRVInstPrinter::printImageOperand(const MCInst *MI, unsigned OpNo,
+                                         raw_ostream &O) {
+  if (OpNo < MI->getNumOperands()) {
+    unsigned e = static_cast<unsigned>(MI->getOperand(OpNo).getImm());
+    O << SPIRV::getImageOperandName(e);
+  }
+}
+
+void SPIRVInstPrinter::printFPFastMathMode(const MCInst *MI, unsigned OpNo,
+                                           raw_ostream &O) {
+  if (OpNo < MI->getNumOperands()) {
+    unsigned e = static_cast<unsigned>(MI->getOperand(OpNo).getImm());
+    O << SPIRV::getFPFastMathModeName(e);
+  }
+}
+
+void SPIRVInstPrinter::printFPRoundingMode(const MCInst *MI, unsigned OpNo,
+                                           raw_ostream &O) {
+  if (OpNo < MI->getNumOperands()) {
+    SPIRV::FPRoundingMode e =
+        static_cast<SPIRV::FPRoundingMode>(MI->getOperand(OpNo).getImm());
+    O << SPIRV::getFPRoundingModeName(e);
+  }
+}
+
+void SPIRVInstPrinter::printLinkageType(const MCInst *MI, unsigned OpNo,
+                                        raw_ostream &O) {
+  if (OpNo < MI->getNumOperands()) {
+    SPIRV::LinkageType e =
+        static_cast<SPIRV::LinkageType>(MI->getOperand(OpNo).getImm());
+    O << SPIRV::getLinkageTypeName(e);
+  }
+}
+
+void SPIRVInstPrinter::printAccessQualifier(const MCInst *MI, unsigned OpNo,
+                                            raw_ostream &O) {
+  if (OpNo < MI->getNumOperands()) {
+    SPIRV::AccessQualifier e =
+        static_cast<SPIRV::AccessQualifier>(MI->getOperand(OpNo).getImm());
+    O << SPIRV::getAccessQualifierName(e);
+  }
+}
+
+void SPIRVInstPrinter::printFunctionParameterAttribute(const MCInst *MI,
+                                                       unsigned OpNo,
+                                                       raw_ostream &O) {
+  if (OpNo < MI->getNumOperands()) {
+    SPIRV::FunctionParameterAttribute e =
+        static_cast<SPIRV::FunctionParameterAttribute>(
+            MI->getOperand(OpNo).getImm());
+    O << SPIRV::getFunctionParameterAttributeName(e);
+  }
+}
+
+void SPIRVInstPrinter::printDecoration(const MCInst *MI, unsigned OpNo,
+                                       raw_ostream &O) {
+  if (OpNo < MI->getNumOperands()) {
+    SPIRV::Decoration e =
+        static_cast<SPIRV::Decoration>(MI->getOperand(OpNo).getImm());
+    O << SPIRV::getDecorationName(e);
+  }
+}
+
+void SPIRVInstPrinter::printBuiltIn(const MCInst *MI, unsigned OpNo,
+                                    raw_ostream &O) {
+  if (OpNo < MI->getNumOperands()) {
+    SPIRV::BuiltIn e =
+        static_cast<SPIRV::BuiltIn>(MI->getOperand(OpNo).getImm());
+    O << SPIRV::getBuiltInName(e);
+  }
+}
+
+void SPIRVInstPrinter::printSelectionControl(const MCInst *MI, unsigned OpNo,
+                                             raw_ostream &O) {
+  if (OpNo < MI->getNumOperands()) {
+    unsigned e = static_cast<unsigned>(MI->getOperand(OpNo).getImm());
+    O << SPIRV::getSelectionControlName(e);
+  }
+}
+
+void SPIRVInstPrinter::printLoopControl(const MCInst *MI, unsigned OpNo,
+                                        raw_ostream &O) {
+  if (OpNo < MI->getNumOperands()) {
+    unsigned e = static_cast<unsigned>(MI->getOperand(OpNo).getImm());
+    O << SPIRV::getLoopControlName(e);
+  }
+}
+
+void SPIRVInstPrinter::printFunctionControl(const MCInst *MI, unsigned OpNo,
+                                            raw_ostream &O) {
+  if (OpNo < MI->getNumOperands()) {
+    unsigned e = static_cast<unsigned>(MI->getOperand(OpNo).getImm());
+    O << SPIRV::getFunctionControlName(e);
+  }
+}
+
+void SPIRVInstPrinter::printMemorySemantics(const MCInst *MI, unsigned OpNo,
+                                            raw_ostream &O) {
+  if (OpNo < MI->getNumOperands()) {
+    unsigned e = static_cast<unsigned>(MI->getOperand(OpNo).getImm());
+    O << SPIRV::getMemorySemanticsName(e);
+  }
+}
+
+void SPIRVInstPrinter::printMemoryOperand(const MCInst *MI, unsigned OpNo,
+                                          raw_ostream &O) {
+  if (OpNo < MI->getNumOperands()) {
+    unsigned e = static_cast<unsigned>(MI->getOperand(OpNo).getImm());
+    O << SPIRV::getMemoryOperandName(e);
+  }
+}
+
+void SPIRVInstPrinter::printScope(const MCInst *MI, unsigned OpNo,
+                                  raw_ostream &O) {
+  if (OpNo < MI->getNumOperands()) {
+    SPIRV::Scope e = static_cast<SPIRV::Scope>(MI->getOperand(OpNo).getImm());
+    O << SPIRV::getScopeName(e);
+  }
+}
+
+void SPIRVInstPrinter::printGroupOperation(const MCInst *MI, unsigned OpNo,
+                                           raw_ostream &O) {
+  if (OpNo < MI->getNumOperands()) {
+    SPIRV::GroupOperation e =
+        static_cast<SPIRV::GroupOperation>(MI->getOperand(OpNo).getImm());
+    O << SPIRV::getGroupOperationName(e);
+  }
+}
+
+void SPIRVInstPrinter::printKernelEnqueueFlags(const MCInst *MI, unsigned OpNo,
+                                               raw_ostream &O) {
+  if (OpNo < MI->getNumOperands()) {
+    SPIRV::KernelEnqueueFlags e =
+        static_cast<SPIRV::KernelEnqueueFlags>(MI->getOperand(OpNo).getImm());
+    O << SPIRV::getKernelEnqueueFlagsName(e);
+  }
+}
+
+void SPIRVInstPrinter::printKernelProfilingInfo(const MCInst *MI, unsigned OpNo,
+                                                raw_ostream &O) {
+  if (OpNo < MI->getNumOperands()) {
+    SPIRV::KernelProfilingInfo e =
+        static_cast<SPIRV::KernelProfilingInfo>(MI->getOperand(OpNo).getImm());
+    O << SPIRV::getKernelProfilingInfoName(e);
+  }
+}

llvm/lib/Target/SPIRV/SPIRV.h

 class SPIRVSubtarget;
 class InstructionSelector;
 class RegisterBankInfo;
 
 InstructionSelector *
 createSPIRVInstructionSelector(const SPIRVTargetMachine &TM,
                                const SPIRVSubtarget &Subtarget,
                                const RegisterBankInfo &RBI);
+
+void initializeSPIRVModuleAnalysisPass(PassRegistry &);
 } // namespace llvm
 
 #endif // LLVM_LIB_TARGET_SPIRV_SPIRV_H

llvm/lib/Target/SPIRV/SPIRVAsmPrinter.cpp

 // of machine-dependent LLVM code to the SPIR-V assembly language.
 //
 //===----------------------------------------------------------------------===//
 
 #include "MCTargetDesc/SPIRVInstPrinter.h"
 #include "SPIRV.h"
 #include "SPIRVInstrInfo.h"
 #include "SPIRVMCInstLower.h"
+#include "SPIRVModuleAnalysis.h"
+#include "SPIRVSubtarget.h"
 #include "SPIRVTargetMachine.h"
+#include "SPIRVUtils.h"
 #include "TargetInfo/SPIRVTargetInfo.h"
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/CodeGen/AsmPrinter.h"
 #include "llvm/CodeGen/MachineConstantPool.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/TargetLoweringObjectFileImpl.h"
 #include "llvm/MC/MCAsmInfo.h"
 #include "llvm/MC/MCInst.h"
 #include "llvm/MC/MCStreamer.h"
 #include "llvm/MC/MCSymbol.h"
 #include "llvm/MC/TargetRegistry.h"
 #include "llvm/Support/raw_ostream.h"
+
 using namespace llvm;
 
 #define DEBUG_TYPE "asm-printer"
 
 namespace {
 class SPIRVAsmPrinter : public AsmPrinter {
-
 public:
   explicit SPIRVAsmPrinter(TargetMachine &TM,
                            std::unique_ptr<MCStreamer> Streamer)
-      : AsmPrinter(TM, std::move(Streamer)) {}
+      : AsmPrinter(TM, std::move(Streamer)), ST(nullptr), TII(nullptr) {}
+  bool ModuleSectionsEmitted;
+  const SPIRVSubtarget *ST;
+  const SPIRVInstrInfo *TII;
 
   StringRef getPassName() const override { return "SPIRV Assembly Printer"; }
   void printOperand(const MachineInstr *MI, int OpNum, raw_ostream &O);
-
   bool PrintAsmOperand(const MachineInstr *MI, unsigned OpNo,
                        const char *ExtraCode, raw_ostream &O) override;
 
-  void emitInstruction(const MachineInstr *MI) override;
+  void outputMCInst(MCInst &Inst);
+  void outputInstruction(const MachineInstr *MI);
+  void outputModuleSection(SPIRV::ModuleSectionType MSType);
+  void outputEntryPoints();
+  void outputDebugSourceAndStrings(const Module &M);
+  void outputOpMemoryModel();
+  void outputOpFunctionEnd();
+  void outputExtFuncDecls();
+  void outputModuleSections();
 
+  void emitInstruction(const MachineInstr *MI) override;
   void emitFunctionEntryLabel() override {}
   void emitFunctionHeader() override;
   void emitFunctionBodyStart() override {}
-  void emitBasicBlockStart(const MachineBasicBlock &MBB) override {}
+  void emitFunctionBodyEnd() override;
+  void emitBasicBlockStart(const MachineBasicBlock &MBB) override;
   void emitBasicBlockEnd(const MachineBasicBlock &MBB) override {}
   void emitGlobalVariable(const GlobalVariable *GV) override {}
+  void emitOpLabel(const MachineBasicBlock &MBB);
+  void emitEndOfAsmFile(Module &M) override;
+  bool doInitialization(Module &M) override;
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+  SPIRV::ModuleAnalysisInfo *MAI;
 };
 } // namespace
 
+void SPIRVAsmPrinter::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.addRequired<SPIRVModuleAnalysis>();
+  AU.addPreserved<SPIRVModuleAnalysis>();
+  AsmPrinter::getAnalysisUsage(AU);
+}
+
+// If the module has no functions, we need output global info anyway.
+void SPIRVAsmPrinter::emitEndOfAsmFile(Module &M) {
+  if (ModuleSectionsEmitted == false) {
+    outputModuleSections();
+    ModuleSectionsEmitted = true;
+  }
+}
+
 void SPIRVAsmPrinter::emitFunctionHeader() {
+  if (ModuleSectionsEmitted == false) {
+    outputModuleSections();
+    ModuleSectionsEmitted = true;
+  }
+  // Get the subtarget from the current MachineFunction.
+  ST = &MF->getSubtarget<SPIRVSubtarget>();
+  TII = ST->getInstrInfo();
   const Function &F = MF->getFunction();
 
   if (isVerbose()) {
     OutStreamer->GetCommentOS()
         << "-- Begin function "
         << GlobalValue::dropLLVMManglingEscape(F.getName()) << '\n';
   }
 
   auto Section = getObjFileLowering().SectionForGlobal(&F, TM);
   MF->setSection(Section);
 }
 
+void SPIRVAsmPrinter::outputOpFunctionEnd() {
+  MCInst FunctionEndInst;
+  FunctionEndInst.setOpcode(SPIRV::OpFunctionEnd);
+  outputMCInst(FunctionEndInst);
+}
+
+// Emit OpFunctionEnd at the end of MF and clear BBNumToRegMap.
+void SPIRVAsmPrinter::emitFunctionBodyEnd() {
+  outputOpFunctionEnd();
+  MAI->BBNumToRegMap.clear();
+}
+
+void SPIRVAsmPrinter::emitOpLabel(const MachineBasicBlock &MBB) {
+  MCInst LabelInst;
+  LabelInst.setOpcode(SPIRV::OpLabel);
+  LabelInst.addOperand(MCOperand::createReg(MAI->getOrCreateMBBRegister(MBB)));
+  outputMCInst(LabelInst);
+}
+
+void SPIRVAsmPrinter::emitBasicBlockStart(const MachineBasicBlock &MBB) {
+  // If it's the first MBB in MF, it has OpFunction and OpFunctionParameter, so
+  // OpLabel should be output after them.
+  if (MBB.getNumber() == MF->front().getNumber()) {
+    for (const MachineInstr &MI : MBB)
+      if (MI.getOpcode() == SPIRV::OpFunction)
+        return;
+    // TODO: this case should be checked by the verifier.
+    report_fatal_error("OpFunction is expected in the front MBB of MF");
+  }
+  emitOpLabel(MBB);
+}
+
 void SPIRVAsmPrinter::printOperand(const MachineInstr *MI, int OpNum,
                                    raw_ostream &O) {
   const MachineOperand &MO = MI->getOperand(OpNum);
 
   switch (MO.getType()) {
   case MachineOperand::MO_Register:
     O << SPIRVInstPrinter::getRegisterName(MO.getReg());
     break;
 
   case MachineOperand::MO_Immediate:
     O << MO.getImm();
     break;
 
   case MachineOperand::MO_FPImmediate:
     O << MO.getFPImm();
     break;
 
   case MachineOperand::MO_MachineBasicBlock:
     O << *MO.getMBB()->getSymbol();
     break;
 
bool SPIRVAsmPrinter::PrintAsmOperand(const MachineInstr *MI, unsigned OpNo,
                                       const char *ExtraCode, raw_ostream &O) {
   if (ExtraCode && ExtraCode[0])
     return true; // Invalid instruction - SPIR-V does not have special modifiers
 
   printOperand(MI, OpNo, O);
   return false;
 }
 
+static bool isFuncOrHeaderInstr(const MachineInstr *MI,
+                                const SPIRVInstrInfo *TII) {
+  return TII->isHeaderInstr(*MI) || MI->getOpcode() == SPIRV::OpFunction ||
+         MI->getOpcode() == SPIRV::OpFunctionParameter;
+}
+
+void SPIRVAsmPrinter::outputMCInst(MCInst &Inst) {
+  OutStreamer->emitInstruction(Inst, *OutContext.getSubtargetInfo());
+}
+
+void SPIRVAsmPrinter::outputInstruction(const MachineInstr *MI) {
+  SPIRVMCInstLower MCInstLowering;
+  MCInst TmpInst;
+  MCInstLowering.lower(MI, TmpInst, MAI);
+  outputMCInst(TmpInst);
+}
+
 void SPIRVAsmPrinter::emitInstruction(const MachineInstr *MI) {
+  if (!MAI->getSkipEmission(MI))
+    outputInstruction(MI);
+
+  // Output OpLabel after OpFunction and OpFunctionParameter in the first MBB.
+  const MachineInstr *NextMI = MI->getNextNode();
+  if (!MAI->hasMBBRegister(*MI->getParent()) && isFuncOrHeaderInstr(MI, TII) &&
+      (!NextMI || !isFuncOrHeaderInstr(NextMI, TII))) {
+    assert(MI->getParent()->getNumber() == MF->front().getNumber() &&
+           "OpFunction is not in the front MBB of MF");
+    emitOpLabel(*MI->getParent());
+  }
+}
+
+void SPIRVAsmPrinter::outputModuleSection(SPIRV::ModuleSectionType MSType) {
+  for (MachineInstr *MI : MAI->getMSInstrs(MSType))
+    outputInstruction(MI);
+}
+
+void SPIRVAsmPrinter::outputDebugSourceAndStrings(const Module &M) {
+  // Output OpSource.
+  MCInst Inst;
+  Inst.setOpcode(SPIRV::OpSource);
+  Inst.addOperand(MCOperand::createImm(static_cast<unsigned>(MAI->SrcLang)));
+  Inst.addOperand(
+      MCOperand::createImm(static_cast<unsigned>(MAI->SrcLangVersion)));
+  outputMCInst(Inst);
+}
+
+void SPIRVAsmPrinter::outputOpMemoryModel() {
+  MCInst Inst;
+  Inst.setOpcode(SPIRV::OpMemoryModel);
+  Inst.addOperand(MCOperand::createImm(static_cast<unsigned>(MAI->Addr)));
+  Inst.addOperand(MCOperand::createImm(static_cast<unsigned>(MAI->Mem)));
+  outputMCInst(Inst);
+}
 
+// Before the OpEntryPoints' output, we need to add the entry point's
+// interfaces. The interface is a list of IDs of global OpVariable instructions.
+// These declare the set of global variables from a module that form
+// the interface of this entry point.
+void SPIRVAsmPrinter::outputEntryPoints() {
+  // Find all OpVariable IDs with required StorageClass.
+  DenseSet<Register> InterfaceIDs;
+  for (MachineInstr *MI : MAI->GlobalVarList) {
+    assert(MI->getOpcode() == SPIRV::OpVariable);
+    auto SC = static_cast<SPIRV::StorageClass>(MI->getOperand(2).getImm());
+    // Before version 1.4, the interface's storage classes are limited to
+    // the Input and Output storage classes. Starting with version 1.4,
+    // the interface's storage classes are all storage classes used in
+    // declaring all global variables referenced by the entry point call tree.
+    if (ST->getSPIRVVersion() >= 14 || SC == SPIRV::StorageClass::Input ||
+        SC == SPIRV::StorageClass::Output) {
+      MachineFunction *MF = MI->getMF();
+      Register Reg = MAI->getRegisterAlias(MF, MI->getOperand(0).getReg());
+      InterfaceIDs.insert(Reg);
+    }
+  }
+
+  // Output OpEntryPoints adding interface args to all of them.
+  for (MachineInstr *MI : MAI->getMSInstrs(SPIRV::MB_EntryPoints)) {
     SPIRVMCInstLower MCInstLowering;
     MCInst TmpInst;
-  MCInstLowering.lower(MI, TmpInst);
-  EmitToStreamer(*OutStreamer, TmpInst);
+    MCInstLowering.lower(MI, TmpInst, MAI);
+    for (Register Reg : InterfaceIDs) {
+      assert(Reg.isValid());
+      TmpInst.addOperand(MCOperand::createReg(Reg));
+    }
+    outputMCInst(TmpInst);
+  }
+}
+
+void SPIRVAsmPrinter::outputExtFuncDecls() {
+  // Insert OpFunctionEnd after each declaration.
+  SmallVectorImpl<MachineInstr *>::iterator
+      I = MAI->getMSInstrs(SPIRV::MB_ExtFuncDecls).begin(),
+      E = MAI->getMSInstrs(SPIRV::MB_ExtFuncDecls).end();
+  for (; I != E; ++I) {
+    outputInstruction(*I);
+    if ((I + 1) == E || (*(I + 1))->getOpcode() == SPIRV::OpFunction)
+      outputOpFunctionEnd();
+  }
+}
+
+void SPIRVAsmPrinter::outputModuleSections() {
+  const Module *M = MMI->getModule();
+  // Get the global subtarget to output module-level info.
+  ST = static_cast<const SPIRVTargetMachine &>(TM).getSubtargetImpl();
+  TII = ST->getInstrInfo();
+  MAI = &SPIRVModuleAnalysis::MAI;
+  assert(ST && TII && MAI && M && "Module analysis is required");
+  // Output instructions according to the Logical Layout of a Module:
+  // TODO: 1,2. All OpCapability instructions, then optional OpExtension
+  // instructions.
+  // TODO: 3. Optional OpExtInstImport instructions.
+  // 4. The single required OpMemoryModel instruction.
+  outputOpMemoryModel();
+  // 5. All entry point declarations, using OpEntryPoint.
+  outputEntryPoints();
+  // 6. Execution-mode declarations, using OpExecutionMode or OpExecutionModeId.
+  // TODO:
+  // 7a. Debug: all OpString, OpSourceExtension, OpSource, and
+  // OpSourceContinued, without forward references.
+  outputDebugSourceAndStrings(*M);
+  // 7b. Debug: all OpName and all OpMemberName.
+  outputModuleSection(SPIRV::MB_DebugNames);
+  // 7c. Debug: all OpModuleProcessed instructions.
+  outputModuleSection(SPIRV::MB_DebugModuleProcessed);
+  // 8. All annotation instructions (all decorations).
+  outputModuleSection(SPIRV::MB_Annotations);
+  // 9. All type declarations (OpTypeXXX instructions), all constant
+  // instructions, and all global variable declarations. This section is
+  // the first section to allow use of: OpLine and OpNoLine debug information;
+  // non-semantic instructions with OpExtInst.
+  outputModuleSection(SPIRV::MB_TypeConstVars);
+  // 10. All function declarations (functions without a body).
+  outputExtFuncDecls();
+  // 11. All function definitions (functions with a body).
+  // This is done in regular function output.
+}
+
+bool SPIRVAsmPrinter::doInitialization(Module &M) {
+  ModuleSectionsEmitted = false;
+  // We need to call the parent's one explicitly.
+  return AsmPrinter::doInitialization(M);
 }
 
 // Force static initialization.
 extern "C" LLVM_EXTERNAL_VISIBILITY void LLVMInitializeSPIRVAsmPrinter() {
   RegisterAsmPrinter<SPIRVAsmPrinter> X(getTheSPIRV32Target());
   RegisterAsmPrinter<SPIRVAsmPrinter> Y(getTheSPIRV64Target());
 }

llvm/lib/Target/SPIRV/SPIRVMCInstLower.h

 //=- SPIRVMCInstLower.h -- Convert SPIR-V MachineInstr to MCInst --*- C++ -*-=//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_LIB_TARGET_SPIRV_SPIRVMCINSTLOWER_H
 #define LLVM_LIB_TARGET_SPIRV_SPIRVMCINSTLOWER_H
 
 #include "llvm/Support/Compiler.h"
 
 namespace llvm {
 class MCInst;
 class MachineInstr;
+namespace SPIRV {
+class ModuleAnalysisInfo;
+} // namespace SPIRV
 
 // This class is used to lower a MachineInstr into an MCInst.
 class LLVM_LIBRARY_VISIBILITY SPIRVMCInstLower {
 public:
-  void lower(const MachineInstr *MI, MCInst &OutMI) const;
+  void lower(const MachineInstr *MI, MCInst &OutMI,
+             SPIRV::ModuleAnalysisInfo *MAI) const;
 };
 } // namespace llvm
 
 #endif // LLVM_LIB_TARGET_SPIRV_SPIRVMCINSTLOWER_H

llvm/lib/Target/SPIRV/SPIRVMCInstLower.cpp

 //=- SPIRVMCInstLower.cpp - Convert SPIR-V MachineInstr to MCInst -*- C++ -*-=//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file contains code to lower SPIR-V MachineInstrs to their corresponding
 // MCInst records.
 //
 //===----------------------------------------------------------------------===//
 
 #include "SPIRVMCInstLower.h"
+#include "SPIRV.h"
+#include "SPIRVModuleAnalysis.h"
+#include "SPIRVUtils.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/IR/Constants.h"
 
 using namespace llvm;
 
-void SPIRVMCInstLower::lower(const MachineInstr *MI, MCInst &OutMI) const {
+void SPIRVMCInstLower::lower(const MachineInstr *MI, MCInst &OutMI,
+                             SPIRV::ModuleAnalysisInfo *MAI) const {
   OutMI.setOpcode(MI->getOpcode());
-
+  const MachineFunction *MF = MI->getMF();
   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
     const MachineOperand &MO = MI->getOperand(i);
-
     MCOperand MCOp;
     switch (MO.getType()) {
     default:
       llvm_unreachable("unknown operand type");
-    case MachineOperand::MO_Register:
-      MCOp = MCOperand::createReg(MO.getReg());
+    case MachineOperand::MO_GlobalAddress: {
+      Register FuncReg = MAI->getFuncReg(MO.getGlobal()->getGlobalIdentifier());
+      assert(FuncReg.isValid() && "Cannot find function Id");
+      MCOp = MCOperand::createReg(FuncReg);
+      break;
+    }
+    case MachineOperand::MO_MachineBasicBlock:
+      MCOp = MCOperand::createReg(MAI->getOrCreateMBBRegister(*MO.getMBB()));
+      break;
+    case MachineOperand::MO_Register: {
+      Register NewReg = MAI->getRegisterAlias(MF, MO.getReg());
+      MCOp = MCOperand::createReg(NewReg.isValid() ? NewReg : MO.getReg());
       break;
+    }
     case MachineOperand::MO_Immediate:
       MCOp = MCOperand::createImm(MO.getImm());
       break;
     case MachineOperand::MO_FPImmediate:
       MCOp = MCOperand::createDFPImm(
           MO.getFPImm()->getValueAPF().convertToFloat());
       break;
     }
 
     OutMI.addOperand(MCOp);
   }
 }

llvm/lib/Target/SPIRV/SPIRVModuleAnalysis.h

+//===- SPIRVModuleAnalysis.h - analysis of global instrs & regs -*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// The analysis collects instructions that should be output at the module level
+// and performs the global register numbering.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIB_TARGET_SPIRV_SPIRVMODULEANALYSIS_H
+#define LLVM_LIB_TARGET_SPIRV_SPIRVMODULEANALYSIS_H
+
+#include "MCTargetDesc/SPIRVBaseInfo.h"
+#include "SPIRVSubtarget.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/StringMap.h"
+
+namespace llvm {
+class MachineFunction;
+class MachineModuleInfo;
+
+namespace SPIRV {
+// The enum contains logical module sections for the instruction collection.
+enum ModuleSectionType {
+  //  MB_Capabilities, MB_Extensions, MB_ExtInstImports, MB_MemoryModel,
+  MB_EntryPoints, // All OpEntryPoint instructions (if any).
+  //  MB_ExecutionModes, MB_DebugSourceAndStrings,
+  MB_DebugNames,           // All OpName and OpMemberName intrs.
+  MB_DebugModuleProcessed, // All OpModuleProcessed instructions.
+  MB_Annotations,          // OpDecorate, OpMemberDecorate etc.
+  MB_TypeConstVars,        // OpTypeXXX, OpConstantXXX, and global OpVariables.
+  MB_ExtFuncDecls,         // OpFunction etc. to declare for external funcs.
+  NUM_MODULE_SECTIONS      // Total number of sections requiring basic blocks.
+};
+
+using InstrList = SmallVector<MachineInstr *>;
+// Maps a local register to the corresponding global alias.
+using LocalToGlobalRegTable = std::map<Register, Register>;
+using RegisterAliasMapTy =
+    std::map<const MachineFunction *, LocalToGlobalRegTable>;
+
+// The struct contains results of the module analysis and methods
+// to access them.
+struct ModuleAnalysisInfo {
+  SPIRV::MemoryModel Mem;
+  SPIRV::AddressingModel Addr;
+  SPIRV::SourceLanguage SrcLang;
+  unsigned SrcLangVersion;
+  // Contains the list of all global OpVariables in the module.
+  SmallVector<MachineInstr *, 4> GlobalVarList;
+  // Maps function names to coresponding function ID registers.
+  StringMap<Register> FuncNameMap;
+  // The set contains machine instructions which are necessary
+  // for correct MIR but will not be emitted in function bodies.
+  DenseSet<MachineInstr *> InstrsToDelete;
+  // The table contains global aliases of local registers for each machine
+  // function. The aliases are used to substitute local registers during
+  // code emission.
+  RegisterAliasMapTy RegisterAliasTable;
+  // The counter holds the maximum ID we have in the module.
+  unsigned MaxID;
+  // The array contains lists of MIs for each module section.
+  InstrList MS[NUM_MODULE_SECTIONS];
+  // The table maps MBB number to SPIR-V unique ID register.
+  DenseMap<int, Register> BBNumToRegMap;
+
+  Register getFuncReg(std::string FuncName) {
+    auto FuncReg = FuncNameMap.find(FuncName);
+    assert(FuncReg != FuncNameMap.end() && "Cannot find function Id");
+    return FuncReg->second;
+  }
+  InstrList &getMSInstrs(unsigned MSType) { return MS[MSType]; }
+  void setSkipEmission(MachineInstr *MI) { InstrsToDelete.insert(MI); }
+  bool getSkipEmission(const MachineInstr *MI) {
+    return InstrsToDelete.contains(MI);
+  }
+  void setRegisterAlias(const MachineFunction *MF, Register Reg,
+                        Register AliasReg) {
+    RegisterAliasTable[MF][Reg] = AliasReg;
+  }
+  Register getRegisterAlias(const MachineFunction *MF, Register Reg) {
+    auto RI = RegisterAliasTable[MF].find(Reg);
+    if (RI == RegisterAliasTable[MF].end()) {
+      return Register(0);
+    }
+    return RegisterAliasTable[MF][Reg];
+  }
+  bool hasRegisterAlias(const MachineFunction *MF, Register Reg) {
+    return RegisterAliasTable.find(MF) != RegisterAliasTable.end() &&
+           RegisterAliasTable[MF].find(Reg) != RegisterAliasTable[MF].end();
+  }
+  unsigned getNextID() { return MaxID++; }
+  bool hasMBBRegister(const MachineBasicBlock &MBB) {
+    return BBNumToRegMap.find(MBB.getNumber()) != BBNumToRegMap.end();
+  }
+  // Convert MBB's number to corresponding ID register.
+  Register getOrCreateMBBRegister(const MachineBasicBlock &MBB) {
+    auto f = BBNumToRegMap.find(MBB.getNumber());
+    if (f != BBNumToRegMap.end())
+      return f->second;
+    Register NewReg = Register::index2VirtReg(getNextID());
+    BBNumToRegMap[MBB.getNumber()] = NewReg;
+    return NewReg;
+  }
+};
+} // namespace SPIRV
+
+struct SPIRVModuleAnalysis : public ModulePass {
+  static char ID;
+
+public:
+  SPIRVModuleAnalysis() : ModulePass(ID) {}
+
+  bool runOnModule(Module &M) override;
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+  static struct SPIRV::ModuleAnalysisInfo MAI;
+
+private:
+  void setBaseInfo(const Module &M);
+  template <typename T> void collectTypesConstsVars();
+  void processDefInstrs(const Module &M);
+  void collectFuncNames(MachineInstr &MI, const Function &F);
+  void processOtherInstrs(const Module &M);
+  void numberRegistersGlobally(const Module &M);
+
+  const SPIRVSubtarget *ST;
+  SPIRVGlobalRegistry *GR;
+  const SPIRVInstrInfo *TII;
+  MachineModuleInfo *MMI;
+};
+} // namespace llvm
+#endif // LLVM_LIB_TARGET_SPIRV_SPIRVMODULEANALYSIS_H

llvm/lib/Target/SPIRV/SPIRVModuleAnalysis.cpp

+//===- SPIRVModuleAnalysis.cpp - analysis of global instrs & regs - C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// The analysis collects instructions that should be output at the module level
+// and performs the global register numbering.
+//
+// The results of this analysis are used in AsmPrinter to rename registers
+// globally and to output required instructions at the module level.
+//
+//===----------------------------------------------------------------------===//
+
+#include "SPIRVModuleAnalysis.h"
+#include "SPIRV.h"
+#include "SPIRVGlobalRegistry.h"
+#include "SPIRVSubtarget.h"
+#include "SPIRVTargetMachine.h"
+#include "SPIRVUtils.h"
+#include "TargetInfo/SPIRVTargetInfo.h"
+#include "llvm/CodeGen/MachineModuleInfo.h"
+#include "llvm/CodeGen/TargetPassConfig.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "spirv-module-analysis"
+
+char llvm::SPIRVModuleAnalysis::ID = 0;
+
+namespace llvm {
+void initializeSPIRVModuleAnalysisPass(PassRegistry &);
+} // namespace llvm
+
+INITIALIZE_PASS(SPIRVModuleAnalysis, DEBUG_TYPE, "SPIRV module analysis", true,
+                true)
+
+// Retrieve an unsigned from an MDNode with a list of them as operands.
+static unsigned getMetadataUInt(MDNode *MdNode, unsigned OpIndex,
+                                unsigned DefaultVal = 0) {
+  if (MdNode && OpIndex < MdNode->getNumOperands()) {
+    const auto &Op = MdNode->getOperand(OpIndex);
+    return mdconst::extract<ConstantInt>(Op)->getZExtValue();
+  }
+  return DefaultVal;
+}
+
+void SPIRVModuleAnalysis::setBaseInfo(const Module &M) {
+  MAI.MaxID = 0;
+  for (int i = 0; i < SPIRV::NUM_MODULE_SECTIONS; i++)
+    MAI.MS[i].clear();
+  MAI.RegisterAliasTable.clear();
+  MAI.InstrsToDelete.clear();
+  MAI.FuncNameMap.clear();
+  MAI.GlobalVarList.clear();
+
+  // TODO: determine memory model and source language from the configuratoin.
+  MAI.Mem = SPIRV::MemoryModel::OpenCL;
+  MAI.SrcLang = SPIRV::SourceLanguage::OpenCL_C;
+  unsigned PtrSize = ST->getPointerSize();
+  MAI.Addr = PtrSize == 32   ? SPIRV::AddressingModel::Physical32
+             : PtrSize == 64 ? SPIRV::AddressingModel::Physical64
+                             : SPIRV::AddressingModel::Logical;
+  // Get the OpenCL version number from metadata.
+  // TODO: support other source languages.
+  MAI.SrcLangVersion = 0;
+  if (auto VerNode = M.getNamedMetadata("opencl.ocl.version")) {
+    // Construct version literal according to OpenCL 2.2 environment spec.
+    auto VersionMD = VerNode->getOperand(0);
+    unsigned MajorNum = getMetadataUInt(VersionMD, 0, 2);
+    unsigned MinorNum = getMetadataUInt(VersionMD, 1);
+    unsigned RevNum = getMetadataUInt(VersionMD, 2);
+    MAI.SrcLangVersion = 0 | (MajorNum << 16) | (MinorNum << 8) | RevNum;
+  }
+}
+
+// True if there is an instruction in the MS list with all the same operands as
+// the given instruction has (after the given starting index).
+// TODO: maybe it needs to check Opcodes too.
+static bool findSameInstrInMS(const MachineInstr &A,
+                              SPIRV::ModuleSectionType MSType,
+                              SPIRV::ModuleAnalysisInfo &MAI,
+                              bool UpdateRegAliases,
+                              unsigned StartOpIndex = 0) {
+  for (const auto *B : MAI.MS[MSType]) {
+    const unsigned NumAOps = A.getNumOperands();
+    if (NumAOps == B->getNumOperands() && A.getNumDefs() == B->getNumDefs()) {
+      bool AllOpsMatch = true;
+      for (unsigned i = StartOpIndex; i < NumAOps && AllOpsMatch; ++i) {
+        if (A.getOperand(i).isReg() && B->getOperand(i).isReg()) {
+          Register RegA = A.getOperand(i).getReg();
+          Register RegB = B->getOperand(i).getReg();
+          AllOpsMatch = MAI.getRegisterAlias(A.getMF(), RegA) ==
+                        MAI.getRegisterAlias(B->getMF(), RegB);
+        } else {
+          AllOpsMatch = A.getOperand(i).isIdenticalTo(B->getOperand(i));
+        }
+      }
+      if (AllOpsMatch) {
+        if (UpdateRegAliases) {
+          assert(A.getOperand(0).isReg() && B->getOperand(0).isReg());
+          Register LocalReg = A.getOperand(0).getReg();
+          Register GlobalReg =
+              MAI.getRegisterAlias(B->getMF(), B->getOperand(0).getReg());
+          MAI.setRegisterAlias(A.getMF(), LocalReg, GlobalReg);
+        }
+        return true;
+      }
+    }
+  }
+  return false;
+}
+
+// Look for IDs declared with Import linkage, and map the imported name string
+// to the register defining that variable (which will usually be the result of
+// an OpFunction). This lets us call externally imported functions using
+// the correct ID registers.
+void SPIRVModuleAnalysis::collectFuncNames(MachineInstr &MI,
+                                           const Function &F) {
+  if (MI.getOpcode() == SPIRV::OpDecorate) {
+    // If it's got Import linkage.
+    auto Dec = MI.getOperand(1).getImm();
+    if (Dec == static_cast<unsigned>(SPIRV::Decoration::LinkageAttributes)) {
+      auto Lnk = MI.getOperand(MI.getNumOperands() - 1).getImm();
+      if (Lnk == static_cast<unsigned>(SPIRV::LinkageType::Import)) {
+        // Map imported function name to function ID register.
+        std::string Name = getStringImm(MI, 2);
+        Register Target = MI.getOperand(0).getReg();
+        // TODO: check defs from different MFs.
+        MAI.FuncNameMap[Name] = MAI.getRegisterAlias(MI.getMF(), Target);
+      }
+    }
+  } else if (MI.getOpcode() == SPIRV::OpFunction) {
+    // Record all internal OpFunction declarations.
+    Register Reg = MI.defs().begin()->getReg();
+    Register GlobalReg = MAI.getRegisterAlias(MI.getMF(), Reg);
+    assert(GlobalReg.isValid());
+    // TODO: check that it does not conflict with existing entries.
+    MAI.FuncNameMap[F.getGlobalIdentifier()] = GlobalReg;
+  }
+}
+
+// Collect the given instruction in the specified MS. We assume global register
+// numbering has already occurred by this point. We can directly compare reg
+// arguments when detecting duplicates.
+static void collectOtherInstr(MachineInstr &MI, SPIRV::ModuleAnalysisInfo &MAI,
+                              SPIRV::ModuleSectionType MSType,
+                              bool IsConstOrType = false) {
+  MAI.setSkipEmission(&MI);
+  if (findSameInstrInMS(MI, MSType, MAI, IsConstOrType, IsConstOrType ? 1 : 0))
+    return; // Found a duplicate, so don't add it.
+  // No duplicates, so add it.
+  MAI.MS[MSType].push_back(&MI);
+}
+
+// Some global instructions make reference to function-local ID regs, so cannot
+// be correctly collected until these registers are globally numbered.
+void SPIRVModuleAnalysis::processOtherInstrs(const Module &M) {
+  for (auto F = M.begin(), E = M.end(); F != E; ++F) {
+    if ((*F).isDeclaration())
+      continue;
+    MachineFunction *MF = MMI->getMachineFunction(*F);
+    assert(MF);
+    unsigned FCounter = 0;
+    for (MachineBasicBlock &MBB : *MF)
+      for (MachineInstr &MI : MBB) {
+        if (MI.getOpcode() == SPIRV::OpFunction)
+          FCounter++;
+        if (MAI.getSkipEmission(&MI))
+          continue;
+        const unsigned OpCode = MI.getOpcode();
+        const bool IsFuncOrParm =
+            OpCode == SPIRV::OpFunction || OpCode == SPIRV::OpFunctionParameter;
+        const bool IsConstOrType =
+            TII->isConstantInstr(MI) || TII->isTypeDeclInstr(MI);
+        if (OpCode == SPIRV::OpName || OpCode == SPIRV::OpMemberName) {
+          collectOtherInstr(MI, MAI, SPIRV::MB_DebugNames);
+        } else if (OpCode == SPIRV::OpEntryPoint) {
+          collectOtherInstr(MI, MAI, SPIRV::MB_EntryPoints);
+        } else if (TII->isDecorationInstr(MI)) {
+          collectOtherInstr(MI, MAI, SPIRV::MB_Annotations);
+          collectFuncNames(MI, *F);
+        } else if (IsConstOrType || (FCounter > 1 && IsFuncOrParm)) {
+          // Now OpSpecConstant*s are not in DT,
+          // but they need to be collected anyway.
+          enum SPIRV::ModuleSectionType Type =
+              IsFuncOrParm ? SPIRV::MB_ExtFuncDecls : SPIRV::MB_TypeConstVars;
+          collectOtherInstr(MI, MAI, Type, IsConstOrType);
+        } else if (OpCode == SPIRV::OpFunction) {
+          collectFuncNames(MI, *F);
+        }
+      }
+  }
+}
+
+// Number registers in all functions globally from 0 onwards and store
+// the result in global register alias table.
+void SPIRVModuleAnalysis::numberRegistersGlobally(const Module &M) {
+  for (auto F = M.begin(), E = M.end(); F != E; ++F) {
+    if ((*F).isDeclaration())
+      continue;
+    MachineFunction *MF = MMI->getMachineFunction(*F);
+    assert(MF);
+    for (MachineBasicBlock &MBB : *MF) {
+      for (MachineInstr &MI : MBB) {
+        for (MachineOperand &Op : MI.operands()) {
+          if (!Op.isReg())
+            continue;
+          Register Reg = Op.getReg();
+          if (MAI.hasRegisterAlias(MF, Reg))
+            continue;
+          Register NewReg = Register::index2VirtReg(MAI.getNextID());
+          MAI.setRegisterAlias(MF, Reg, NewReg);
+        }
+      }
+    }
+  }
+}
+
+struct SPIRV::ModuleAnalysisInfo SPIRVModuleAnalysis::MAI;
+
+void SPIRVModuleAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.addRequired<TargetPassConfig>();
+  AU.addRequired<MachineModuleInfoWrapperPass>();
+}
+
+bool SPIRVModuleAnalysis::runOnModule(Module &M) {
+  SPIRVTargetMachine &TM =
+      getAnalysis<TargetPassConfig>().getTM<SPIRVTargetMachine>();
+  ST = TM.getSubtargetImpl();
+  GR = ST->getSPIRVGlobalRegistry();
+  TII = ST->getInstrInfo();
+
+  MMI = &getAnalysis<MachineModuleInfoWrapperPass>().getMMI();
+
+  setBaseInfo(M);
+
+  // TODO: Process type/const/global var/func decl instructions, number their
+  // destination registers from 0 to N, collect Extensions and Capabilities.
+
+  // Number rest of registers from N+1 onwards.
+  numberRegistersGlobally(M);
+
+  // Collect OpName, OpEntryPoint, OpDecorate etc, process other instructions.
+  processOtherInstrs(M);
+
+  return false;
+}

llvm/lib/Target/SPIRV/SPIRVTargetMachine.cpp

 
 extern "C" LLVM_EXTERNAL_VISIBILITY void LLVMInitializeSPIRVTarget() {
   // Register the target.
   RegisterTargetMachine<SPIRVTargetMachine> X(getTheSPIRV32Target());
   RegisterTargetMachine<SPIRVTargetMachine> Y(getTheSPIRV64Target());
 
   PassRegistry &PR = *PassRegistry::getPassRegistry();
   initializeGlobalISel(PR);
+  initializeSPIRVModuleAnalysisPass(PR);
 }
 
 static std::string computeDataLayout(const Triple &TT) {
   std::string DataLayout = "e-m:e";
 
   const auto Arch = TT.getArch();
   if (Arch == Triple::spirv32)
     DataLayout += "-p:32:32";
TargetPassConfig *SPIRVTargetMachine::createPassConfig(PassManagerBase &PM) {
   return new SPIRVPassConfig(*this, PM);
 }
 
 void SPIRVPassConfig::addIRPasses() { TargetPassConfig::addIRPasses(); }
 
 void SPIRVPassConfig::addISelPrepare() { TargetPassConfig::addISelPrepare(); }
 
 bool SPIRVPassConfig::addIRTranslator() {
   addPass(new IRTranslator(getOptLevel()));
   return false;
 }
 
 // Use a default legalizer.
 bool SPIRVPassConfig::addLegalizeMachineIR() {
   addPass(new Legalizer());
   return false;
 }

llvm/test/CodeGen/SPIRV/function/identity-function.ll

+; RUN: llc -O0 %s -o - | FileCheck %s
+
+target triple = "spirv32-unknown-unknown"
+
+; CHECK-DAG: OpName [[VALUE:%.+]] "value"
+; CHECK-DAG: OpName [[IDENTITY:%.+]] "identity"
+
+; CHECK: [[INT:%.+]] = OpTypeInt 32
+; CHECK: [[FN:%.+]] = OpTypeFunction [[INT]] [[INT]]
+
+; CHECK: [[IDENTITY]] = OpFunction [[INT]] None [[FN]]
+; CHECK-NEXT: [[VALUE]] = OpFunctionParameter [[INT]]
+; CHECK-NEXT: {{%.+}} = OpLabel
+; CHECK-NEXT: OpReturnValue [[VALUE]]
+; CHECK-NEXT: OpFunctionEnd
+
+define i32 @identity(i32 %value) {
+  ret i32 %value
+}

llvm/test/CodeGen/SPIRV/function/trivial-function-definition.ll

+; RUN: llc -O0 %s -o - | FileCheck %s
+
+target triple = "spirv32-unknown-unknown"
+
+; Debug info:
+; CHECK: OpName [[FOO:%.+]] "foo"
+
+; Types:
+; CHECK: [[VOID:%.+]] = OpTypeVoid
+; CHECK: [[FN:%.+]] = OpTypeFunction [[VOID]]
+
+; Functions:
+; CHECK: [[FOO]] = OpFunction [[VOID]] None [[FN]]
+; CHECK-NOT: OpFunctionParameter
+; NOTE: In 2.4, it isn't explicitly written that a function always has a least
+;       one block. In fact, 2.4.11 seems to imply that there are at least two
+;       blocks in functions with a body, but that doesn't make much sense.
+;       However, in order to distinguish between function declaration and
+;       definition, a function needs at least one block, hence why this test
+;       expects one OpLabel + OpReturn.
+; CHECK: OpLabel
+; CHECK: OpReturn
+; CHECK-NOT: OpLabel
+; CHECK: OpFunctionEnd
+define void @foo() {
+  ret void
+}

llvm/test/CodeGen/SPIRV/function/trivial-function-with-attributes.ll

+; RUN: llc -O0 %s -o - | FileCheck %s
+
+target triple = "spirv32-unknown-unknown"
+
+; FIXME: Are there any attributes that would make the IR invalid for SPIR-V?
+
+; Names:
+; CHECK-DAG: OpName [[FN1:%.+]] "fn1"
+; CHECK-DAG: OpName [[FN2:%.+]] "fn2"
+; CHECK-DAG: OpName [[FN3:%.+]] "fn3"
+; CHECK-DAG: OpName [[FN4:%.+]] "fn4"
+; CHECK-DAG: OpName [[FN5:%.+]] "fn5"
+; CHECK-DAG: OpName [[FN6:%.+]] "fn6"
+; CHECK-DAG: OpName [[FN7:%.+]] "fn7"
+
+; CHECK-NOT: DAG-FENCE
+
+; Types:
+; CHECK: [[VOID:%.+]] = OpTypeVoid
+; CHECK: [[FN:%.+]] = OpTypeFunction [[VOID]]
+
+
+; Functions:
+
+define void @fn1() noinline {
+  ret void
+}
+; CHECK: [[FN1]] = OpFunction [[VOID]] DontInline [[FN]]
+; CHECK-NOT: OpFunctionParameter
+; CHECK: OpFunctionEnd
+
+
+attributes #0 = { noinline }
+define void @fn2() #0 {
+  ret void
+}
+; CHECK: [[FN2]] = OpFunction [[VOID]] DontInline [[FN]]
+; CHECK: OpFunctionEnd
+
+
+define void @fn3() alwaysinline {
+  ret void
+}
+; CHECK: [[FN3]] = OpFunction [[VOID]] Inline [[FN]]
+; CHECK: OpFunctionEnd
+
+
+; NOTE: inlinehint is not an actual requirement.
+define void @fn4() inlinehint {
+  ret void
+}
+; CHECK: [[FN4]] = OpFunction [[VOID]] None [[FN]]
+; CHECK: OpFunctionEnd
+
+
+define void @fn5() readnone {
+  ret void
+}
+; CHECK: [[FN5]] = OpFunction [[VOID]] Pure [[FN]]
+; CHECK: OpFunctionEnd
+
+
+define void @fn6() readonly {
+  ret void
+}
+; CHECK: [[FN6]] = OpFunction [[VOID]] Const [[FN]]
+; CHECK: OpFunctionEnd
+
+
+define void @fn7() alwaysinline readnone {
+  ret void
+}
+; CHECK: [[FN7]] = OpFunction [[VOID]] Inline|Pure [[FN]]
+; CHECK: OpFunctionEnd

llvm/test/CodeGen/SPIRV/function/trivial-function-with-call.ll

+; RUN: llc -O0 %s -o - | FileCheck %s
+
+target triple = "spirv32-unknown-unknown"
+
+; Debug info:
+; CHECK: OpName [[FOO:%.+]] "foo"
+; CHECK: OpName [[BAR:%.+]] "bar"
+
+; Types:
+; CHECK-DAG: [[I32:%.+]] = OpTypeInt 32
+; CHECK-DAG: [[VOID:%.+]] = OpTypeVoid
+; CHECK-DAG: [[FNVOID:%.+]] = OpTypeFunction [[VOID]] [[I32]]
+; CHECK-DAG: [[FNI32:%.+]] = OpTypeFunction [[I32]] [[I32]]
+; Function decl:
+; CHECK: [[BAR]] = OpFunction [[I32]] None [[FNI32]]
+; CHECK-NEXT: OpFunctionParameter [[I32]]
+; CHECK-NEXT: OpFunctionEnd
+declare i32 @bar(i32 %x)
+; Function def:
+; CHECK: [[FOO]] = OpFunction [[VOID]] None [[FNVOID]]
+; CHECK: OpFunctionParameter
+; CHECK: OpLabel
+; CHECK: OpFunctionCall [[I32]] [[BAR]]
+; CHECK: OpReturn
+; CHECK-NOT: OpLabel
+; CHECK: OpFunctionEnd
+define spir_func void @foo(i32 %x) {
+  %call1 = call spir_func i32 @bar(i32 %x)
+  ret void
+}

llvm/test/CodeGen/SPIRV/lit.local.cfg

+if not 'SPIRV' in config.root.targets:
+    config.unsupported = True

llvm/test/CodeGen/SPIRV/metadata-opencl.ll

+; RUN: split-file %s %t
+; RUN: llc -O0 %t/metadata-opencl12.ll -o - | FileCheck %t/metadata-opencl12.ll
+; RUN: llc -O0 %t/metadata-opencl20.ll -o - | FileCheck %t/metadata-opencl20.ll
+; RUN: llc -O0 %t/metadata-opencl22.ll -o - | FileCheck %t/metadata-opencl22.ll
+
+;--- metadata-opencl12.ll
+target triple = "spirv32-unknown-unknown"
+
+!opencl.ocl.version = !{!0}
+!0 = !{i32 1, i32 2}
+
+; We assume the SPIR-V 2.2 environment spec's version format: 0|Maj|Min|Rev|
+; CHECK: OpSource OpenCL_C 66048
+;--- metadata-opencl20.ll
+target triple = "spirv32-unknown-unknown"
+
+!opencl.ocl.version = !{!0}
+!0 = !{i32 2, i32 0}
+
+; We assume the SPIR-V 2.2 environment spec's version format: 0|Maj|Min|Rev|
+; CHECK: OpSource OpenCL_C 131072
+;--- metadata-opencl22.ll
+target triple = "spirv32-unknown-unknown"
+
+!opencl.ocl.version = !{!0}
+!0 = !{i32 2, i32 2}
+
+; We assume the SPIR-V 2.2 environment spec's version format: 0|Maj|Min|Rev|
+; CHECK: OpSource OpenCL_C 131584

llvm/test/CodeGen/SPIRV/transcoding/readonly.ll

+; RUN: llc -O0 %s -o - | FileCheck %s --check-prefix=CHECK-SPIRV
+
+; CHECK-SPIRV: OpDecorate %[[PARAM:[0-9]+]] FuncParamAttr NoWrite
+; CHECK-SPIRV: %[[PARAM]] = OpFunctionParameter %{{.*}}
+
+; ModuleID = 'readonly.bc'
+source_filename = "readonly.cpp"
+target datalayout = "e-i64:64-v16:16-v24:32-v32:32-v48:64-v96:128-v192:256-v256:256-v512:512-v1024:1024-n8:16:32:64"
+target triple = "spirv64-unknown-unknown"
+
+; Function Attrs: norecurse nounwind readonly willreturn
+define dso_local spir_kernel void @_ZTSZ4mainE15kernel_function(i32 addrspace(1)* readonly %_arg_) local_unnamed_addr #0 {
+entry:
+  ret void
+}
+
+attributes #0 = { norecurse nounwind }
+
+!llvm.module.flags = !{!0}
+!opencl.spir.version = !{!1}
+!spirv.Source = !{!2}
+!llvm.ident = !{!3}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{i32 1, i32 2}
+!2 = !{i32 4, i32 100000}
+!3 = !{!"clang version 13.0.0 (https://github.com/intel/llvm.git)"}