Out of memory handling

I watched a video from CppCon 2014 where the speaker said during Q&A

[...] if you are on Linux, you know, malloc is never going to return NULL. It's always going to give you a chunk of memory, even if memory is full. It's going to say "I can get it from somewhere at some point", and if you actually runs out of memory, what happens is that the OS kills you.

I hear this a lot — there is no need to handle out of memory conditions as you'll never get NULL from malloc, and the OS will kill your process anyway. But it is wrong; there are at least two cases where malloc will return NULL on Linux:

• Per-process memory limits are configured, and the process is exceeding those.
• A 32-bit application running under a 64-bit kernel is trying to use more than about 4 gigabytes of memory.

So you need to deal with malloc returning NULL.

I'm not saying that you must handle out of memory conditions gracefully, although I would argue it is a good idea (especially if you are developing libraries). But you should at least check if malloc fails, as dereferencing NULL invokes undefined behavior in C, and may lead to surprising results from compiler optimizations.^1,2

---

¹ Such as this old Linux 2.6.30 kernel exploit.
² I cannot see how the compiler may introduce problems by exploiting the undefined behavior resulting from not checking for malloc failure, but I'm sure GCC will find a way...

Optimizing ESSL

The cartoon understanding of compiler design is that compilers consist of three parts:

• front end — handling everything that is language specific
• middle end — language- and hardware-independent optimizations
• back end — code generation, independent of the language

One point I was trying to make in my two previous posts is that the situation is more complex in reality; the backend may take advantage of the ESSL precision qualifiers during instruction selection/scheduling, and this affects what the optimizations are allowed to do. So you cannot use a language/hardware-independent middle end if you have a sufficiently strange architecture and want to take advantage of the latitude ESSL gives you.

There are many other considerations when writing a high-performance compiler for some specific market/language/hardware architecture that may be surprising if you have not worked in that area. I'll  give some examples below that have surprised me over the years.

Performance, power, and performance measurement

Mobile devices are power constrained, so the clock frequency is dynamically managed to prevent the GPU from running too hot. Different operations consume a different amount of power, and it is not obvious that the fastest shader measured in "number of cycles" is the fastest in "running time", as a slower shader using less power-hungry instructions may be run at a higher clock frequency. So the cycle count may deceive you when you are optimizing shaders.

It is actually very hard to get meaningful performance data when evaluating optimizations (on all systems — not only GPUs), and just implementing an optimization and observing the difference in run time may not tell you if the optimization is beneficial or not. My favorite paper on this is "Producing Wrong Data Without Doing Anything Obviously Wrong!" by Mytkowicz et al. that show that performance of real world applications depend surprisingly much on luck in things like alignment and cache effects. For example, changing the order of files when linking gives up to 15% performance variance for applications in the SPEC CPU2006 benchmark suite. And the result is different for different environments, so you may see a healthy 5% performance uplift in your environment, while the change is actually harmful and makes it slower for most other environments. I have seen many optimization results that I believe are due to this rather than any real improvement...

Compilation speed

High end mobile games may have hundreds of shaders, and shader compilation is done at application start up, so it is important that the compiler is fast. This means that the optimization strategy should be different compared to a desktop compiler, as you need to be more careful in the tradeoff between optimization run time and potential benefit, and not slow down the compiler by handling cases that are unlikely to happen in real world shaders.

Mobile CPUs have improved a lot the last couple of years, but they are still lagging the desktop when it comes to out-of-order execution etc. This makes the abstraction penalty more painful on mobile processors, and you may want to take that into account when designing an ESSL compiler.

Optimizations 

Desktop compilers are insanely complex, but most of that complexity deals with things that does not happen in shaders; ESSL does not have pointers, so data tracking and aliasing analysis is easy. Shaders does not work on large arrays, so you do not need to transform loops to get better memory accesses pattern. Vectorization is essentially software based warping, so that does not help warp based GPUs. Etc. etc.

And shaders are by necessity small — all mobile phones have high resolution screens, and you cannot spend that many cycles on each pixel if you want a decent frame rate.¹ There are not much opportunity for optimizations in small pieces of code, so the relevant optimizations are essentially what you had in an early 90's desktop compiler: inlining, simple loop unrolling, if-conversion, etc.

An important part of compiler development, that is usually glossed over in the compiler literature, is implementing peephole optimizations that maps common code idioms to efficient instruction sequences. Application developers keep inventing strange code constructs, so this is a work package that is never finished. To take a random example from GCC: WebKit implements arithmetic right shift by 4 bits using the idiom

r = (v & ~15) / 16;

so GCC needed to add a rule to recognize as an "arithmetic shift right" instruction. A big part of creating a good compiler is to handle "all" such cases, and graphical shaders have different constructs compared to typical C/C++ code, so you need to invest lots of time looking at real world shaders.

---

¹ For example, 500MHz, 30fps, 1920x1080 translates to 8 cycles/pixel. Most GPUs have multiple cores (or whatever they are called — all GPU vendors have different terminology), so the cycle budget is larger for most devices. But still rather limited.

Floating point, precision quaifiers, and optimization

ESSL permits optimizations that may change the value of floating point expressions (lowp and mediump precision change, reassociation of addition/multiplication, etc.), which means that identical expressions may give different results in different shaders. This may cause problems with e.g. alignment of geometry in multi-pass algorithms, so output variables may be decorated with the invariant qualifier to force the compiler to be consistent in how it generates code for them. The compiler is still allowed to do value-changing optimizations for invariant expressions, but it need to do it in the same way for all shaders. This may give us interesting problems if optimizations and code generation are done without knowledge of each other...

Example 1

As an example of the problems we may get with invariant, consider an application that is generating optimized SPIR-V using an offline ESSL compiler, and uses the IR with a Vulkan driver having a simple backend. The backend works on one basic block at a time, and is generating FMA (Fused Multiply-Add) instructions when multiplication is followed by addition. This is fine for invariant, even though FMA changes the precision, as the backend is consistent and always generates FMA when possible (i.e. identical expressions in different shaders will generate identical instructions).

The application has a shader

#version 310 es

in float a, b, c;
out invariant float result;

void main() {
    float tmp = a * b;
    if (c < 0.0) {
       result = tmp - 1.0;
    } else {
       result = tmp + 1.0;
    }
}

This is generated exactly as written if no optimization is done; first a multiplication, followed by a compare and branch, and we have two basic blocks doing one addition each. But the offline compiler optimizes this with if-conversion, so it generates SPIR-V as if main was written as

void main()
{
    float tmp = a * b;
    result = (c < 0.0) ? (tmp - 1.0) : (tmp + 1.0);
}

The optimization has eliminated the branches, and the backend will now see that it can use FMA instructions as everything is in the same basic block.

But the application has one additional shader where main looks like

void main() {
    float tmp = a * b;
    if (c < 0.0) {
       foo();
       result = tmp - 1.0;
    } else {
       result = tmp + 1.0;
    }
}

The optimization cannot transform the if-statement here, as the basic blocks are too complex. So this will not use FMA, and will therefore break the invariance guarantee. 

Example 2

It is not only invariant expressions that are problematic — you may get surprising results from normal code too when optimizations done offline and in the backend interacts in interesting ways. For example, you can get different precision in different threads from "redundant computation elimination" optimizations. This happens for cases such as 

mediump float tmp = a + b;
if (x == 0) {
  /* Code not using tmp */
  ...
} else if (x == 1) {
  /* Code using tmp */
  ...
} else {
  /* Code using tmp */
  ...
}

where tmp is calculated, but not used, for the case "x == 0". The optimization moves the tmp calculation into the two basic blocks where it is used

if (x == 0) {
  /* Code not using tmp */
  ...
} else if (x == 1) {
  mediump float tmp = a + b;
  /* Code using tmp */
  ...
} else {
  mediump float tmp = a + b;
  /* Code using tmp */
  ...
}

and the backend may now chose to use different precisions for the two mediump tmp calculations. 

Offline optimization with SPIR-V

The examples above are of course silly — higher level optimizations should not be allowed to change control flow for invariant statements, and the "redundant computation elimination" does not make sense for warp-based architectures. But the first optimization would have been fine if used with a better backend that could combine instructions from different basic blocks. And not all GPUs are warp-based. That is, it is reasonable to do this kind of optimizations, but they need to be done in the driver where you have full knowledge about the backend and architecture.

My impression is that many developers believe that SPIR-V and Vulkan implies that the driver will just do simple code generation, and that all optimizations are done offline. But that will prevent some optimizations. It may work for a game engine generating IR for a known GPU, but I'm not sure that the GPU vendors will provide enough information on their architectures/backends that this will be viable either.

So my guess is that the drivers will continue to do all the current optimizations on SPIR-V too, and that offline optimizations will not matter...

Precision qualifiers in SPIR-V

SPIR-V is a bit inconsistent in how it handles types for graphical shaders and compute kernels. Kernels are using sized types, and there are explicit conversions when converting between sizes. Shaders are using 32-bit types for everything, but there are precision decorations that indicates which size is really used, and conversions between sizes are done implicitly. I guess much of this is due to historical reasons in how ESSL defines its types, but I think it would be good to be more consistent in the IR.

ESSL 1 played fast and loose with types. For example, it has an integer type int, but the platform is allowed to implement it as floating point, so it is not necessarily true that "a+1 != a" for a sufficiently large a. ESSL 3 strengthened the type system, so for example high precision integers are now represented as 32-bit values in two's complement form. The rest of this post will use the ESSL 3 semantics.

ESSL does not care much about the size of variables; it has only one integer type "int" and one floating point type "float". But you need to specify which precision to use in calculations by adding precision qualifiers when you declare your variables, such as

highp float x;

Using highp means that the calculations must be done in 32-bit precision, mediump means at least 16-bit precision, and lowp means using at lest 9 bits (yes, "nine". You cannot fit a lowp value in a byte). The compiler may use any size for the variables, as long as the precision is preserved.

So "mediump int" is similar to the int_least16_t type in C, but ESSL permits the compiler to use different precision for different instructions. It can for example use 16-bit precision for one mediump addition, and 32-bit for another, so it is not necessarily true that "a+b == a+b" for mediump integers a and b if the addition overflow 16 bits. The reason for having this semantics is to be able to use the hardware efficiently. Consider for example a processor having two parallel arithmetic units — one 16-bit and one 32-bit. If we have a shader where all instructions are mediump, then we could only reach 50% utilization by executing all instructions as 16-bit. But the backend can now promote half of them to 32-bit and thus be able to double the performance by using both arithmetic units.

SPIR-V is representing this by always using a 32-bit type and decorating the variables and instructions with PrecisionLow, PrecisionMedium, or PrecisionHigh. The IR does not have any type conversions for the precision as the actual type is the same, and it is only the precision of the instruction that differ. But ESSL has requirements on conversions when changing precision in operations that is similar to how size change is handled in other languages:

When converting from a higher precision to a lower precision, if the value is representable by the implementation of the target precision, the conversion must also be exact. If the value is not representable, the behavior is dependent on the type:

• For signed and unsigned integers, the value is truncated; bits in positions not present in the target precision are set to zero. (Positions start at zero and the least significant bit is considered to be position zero for this purpose.)

• For floating point values, the value should either clamp to +INF or -INF, or to the maximum or minimum value that the implementation supports. While this behavior is implementation dependent, it should be consistent for a given implementation

It is of course fine to have the conversions implicit in the IR, but the conversions are explicit for the similar conversion fp32 to fp16 in kernels, so it is inconsistent. I would in general want the shader and kernel IR to be as similar as possible in order to avoid confusion when writing SPIR-V tools working on both types of IR, and I think it is possible to improve this with minor changes:

• The highp precision qualifier means that the compiler must use 32-bit precision, i.e. a highp-qualified type is the same as as the normal non-qualified 32-bit type. So the PrecisionHigh does not tell the compiler anything; it just adds noise to the IR, and can be removed from SPIR-V.

• Are GPUs really taking advantage of lowp for calculations? I can understand how lowp may be helpful for e.g. saving power in varying interpolation, and those cases are handled by having the PrecisionLow decoration on variables. But it seems unlikely to me that any GPU have added the extra hardware to do arithmetic in lowp precision, and I would assume all GPUs use 16-bit or higher for lowp arithmetic. If so, then PrecisionLow should not be a valid decoration for instructions.

• The precision decorations are placed on instructions, but it seems better to me to have the them on the type instead. If PrecisionLow and PrecisionHigh are removed, then PrecisionMedium is the only decoration left. But this can be treated as a normal 16-bit type from the optimizers point of view, so we could instead permit both 32- and 16-bit types for graphical shaders, and specify in the execution model that it is allowed to promote 16-bit to 32-bit. Optimizations and type conversions can then be done in exactly the same way as for kernels, and the backend can promote the types as appropriate for the hardware.

Comments on the SPIR-V provisional specification

Below are some random comments/thoughts/questions from my initial reading of the SPIR-V provisional specification (revision 30).

Many of my comments are that the specification is unclear. I may agree that it is obvious what the specification mean, but my experience from specification work is that it is often the case that everybody agree that it is obvious, but they do not agree on what the obvious thing is. So I think the specification need to be more detailed. Especially as one of the goals of SPIR-V is to "be targeted by new front ends for novel high-level languages", and those may generate constructs that are not possible in GLSL or OpenCL C, so it is important that all constraints are documented.

Some other comments are related to tradeoffs. I think the specification is OK, so my comments are mostly highlighting some limitations (and I may have chosen a different tradeoff for some of them...). It would be great to have the rationale described for this kind of decisions.

Const and Pure functions

Functions can be marked as Const or Pure. Const is described as

Compiler can assume this function has no side effects, and will not access global memory or dereference function parameters. Always computes the same result for the same argument values.

while Pure is described as

Compiler can assume this function has no side effect, but might read global memory or read through dereferenced function parameters. Always computes the same result for the same argument values.

I assume the intention is that the compiler is allowed to optimize calls to Const functions, such as moving function calls out of loops, CSE:ing function calls, etc. And similar for the Pure functions, as long as there are no writes to global memory that may affect the result.

But the specification talks about "global memory" without defining what it is. For example, is UniformConstant global variables included in this? Those cannot change, so we can do all the Const optimizations even if the function is reading from them.  And what about WorkgroupLocal? That name does not sound like global memory, but it does of course still prevent optimizations.

I would suggest the specification change to explicitly list the storage classes permitted in Const and Pure functions...

Storage Classes

I'm a bit confused by the Uniform and Function storage classes...

The Uniform storage class is a required capability for Shader. But the GLSL uniform is handled by the UniformConstant storage class, so what is the usage/semantics of Uniform?

Function is described as "A variable local to a function" and is also a required capability for Shader. But OpenCL does also have function-local variables... How are those handled? Why are they not handled in the same way for Shader and Kernel?

Restrict

The Restrict decoration is described as

Apply to a variable, to indicate the compiler may compile as if there is no aliasing.

This does not give you the full picture, as you can express that pointers do not alias as described in the Memory Model section. But pointers have different semantics compared to variables, and that introduces some complications.

OpenCL C defines restrict to work in the same way as for C99, and that is different from the SPIR-V specification. What C99 says is, much simplified, that a value pointed to by a restrict-qualified pointer cannot be modified through a pointer not based on that restrict-qualified pointer. So two pointers can alias if the have the correct "based-on" relationship, and are following some rules on how they are accessed. The frontend may of course decide to not decorate the pointers when it cannot express the semantics in the IR, but it is unclear to me that it is easy to detect the problematic cases.

I think this needs to be clarified along the line of what the LLVM Language Reference Manual does for noalias.

Volatile

There is a Memory Access value Volatile that is described as

This access cannot be optimized away; it has to be executed.

This does not really make sense... The memory model is still mostly TBD in the document, but the principle in GPU programming is that you need atomics or barriers in order to make memory accesses consistent. So there is no way you can observe the difference between the compiler respecting Volatile or not.

My understanding is that the rationale for Volatile in SPIR-V is to be able to work around compiler bugs by decorating memory operations with Volatile and in that way disable some compiler transformations. If so, then I think it would be useful to document this in order to make it more likely that compilers do the right thing. After all, I would expect the project manager to tell the team to do more useful work than fixing a bug for which you cannot see the difference between correct and incorrect behavior.

It has historically been rather common that C compilers miscompile volatile. A typical example is for optimizations such as store forwarding, that substitutes a loaded value by a previously stored value, where the developer forgets to check for volatility when writing the optimization. So a sequence such as

 7:             TypeInt 32 1
15:      7(int) Constant 0
                Store 14(tmp) 15 
16:      7(int) Load 11(b) 
17:      7(int) Load 14(tmp) 
18:      7(int) IMul 16 17
                Store 10(a) 18

corresponding to

volatile int tmp = 0;
a = b * tmp;

gets the ID 17 substituted by the constant 0, and is then optimized to

 7:             TypeInt 32 1
15:      7(int) Constant 0
                Store 14(tmp) 15 
17:      7(int) Load 14(tmp) 
                Store 10(a) 15

which is not what it is expected. But you can argue that this actually follows the SPIR-V specification — we have not optimized away the memory accesses!

Volatile and OpenCL

The OpenCL C specification says that

The type qualifiers const, restrict and volatile as defined by the C99 specification are supported.

which I interpret as volatile works in exactly the same way as for C99. And C99 says

An object that has volatile-qualified type may be modified in ways unknown to the implementation or have other unknown side effects. Therefore any expression referring to such an object shall be evaluated strictly according to the rules of the abstract machine, as described in 5.1.2.3. Furthermore, at every sequence point the value last stored in the object shall agree with that prescribed by the abstract machine, except as modified by the unknown factors mentioned previously. What constitutes an access to an object that has volatile-qualified type is implementation-defined.

That is, the compiler is not allowed to reorder volatile memory accesses, even if it know that they do not alias. So the definition of the SPIR-V Volatile need to be strengthened if that is meant to be used for implementing the OpenCL volatile. Although I guess you may get around this by a suitable implementation-defined definition of what constitutes an access to an object...

Differences between graphical shaders and OpenCL

The Validation Rules says that for graphical shaders

• Scalar integer types can be parameterized only as:
– 32-bit signed
– 32-bit unsigned

while OpenCL cannot use signed/unsigned

• OpTypeInt validation rules
  – The bit width operand can only be parameterized as 8, 16, 32 and 64 bit.
  – The sign operand must always be 0

I guess this lack of signed/unsigned information is the reason why there are Function Parameter Attributes called Zext and Sext described as

Value should be zero/sign extended if needed.

Both choices regarding the signed/unsigned information are fine for an IR, but why is SPIR-V treating graphics and OpenCL differently?

Endianness

Khronos thinks that SPIR-V is an in-memory format, not a file format, which means that the words are stored in the host's native byte order. But one of of the goals of SPIR-V is "enabling shared tools to generate or operate on it", so it will be passed in files between tools. The specification has a helpful hint that you can use the magic number to detect endianness, but that means that all tools need to do the (admittedly simple) extra work to handle both big and little endian.

I think that the specification should define one file format encoding (preferably with a standardized file name extension), and say that all tools should use this encoding.

By the way, are there really any big endian platforms in the target market?

SPIR-V

I'm going to play some with SPIR-V, and the first step is to look at existing projects/blogs. Below is what I have found so far. Have I missed anything relevant?

Blogs

Redefining the shading languages ecosystem with SPIR-V

Great overview of the benefits of SPIR-V, and what problems it does not solve.

Software

glslang

Khronos' reference compiler front end for the OpenGL ES and OpenGL shading languages. This can now generate SPIR-V.

lunarglass

LunarGLASS: LunarG's LLVM Adaptation to Shader Compiler Stacks.

It compiles shaders to LLVM IR using the glslang frontend, and it can use the SPIR-V output from glslang, so it seems to contain most code needed to convert SPIR-V to LLVM IR.

https://github.com/cheery/spirthon

Translation from python bytecode to SPIR-V.

This also contains

• A SPIR-V decoder/encoder (assembler/disassembler)
• Machine readable specification for SPIR-V in json -format that can be used to drive a decoder/encoder. And the script used to generate it.

https://github.com/Philip-Trettner/SpirvNet

SPIR-V generator for .NET IL written in C#.

https://github.com/jteeuwen/spirv

A SPIR-V encoder/decoder written in Go.

https://github.com/kusma/SPIR-V

Simple SPIR-V parser written in C.

https://github.com/Philip-Trettner/SpirvSpecToJson

SPIR-V HTML Specification to JSON converter written in C#.

https://github.com/GeirGrusom/spirv-emit

SPIR-V bytecode emitter written in C#.

Proving correctness of the GCC match.pd — Part 1

The idea behind ALIVe is that you can eliminate a large class of compiler bugs in LLVM by generating peephole optimizations from a specification that is proved correct using an SMT solver. GCC is already generating some such optimizations from a specification, so the "only" thing remaining is to prove that the transformations in the specification are correct.

The transformations are specified in a file called match.pd, and work on the GCC middle-end GENERIC and GIMPLE IR that is a somewhat higher level representation than the LLVM IR. GENERIC is the representation generated by the front end, and is almost immediately transformed to GIMPLE that is used for the majority of the middle-end optimizations. Both use mostly the same operations, but GENERIC has some higher level constructs, and it is not in SSA form.

GCC does not have an external format for the IR, but you can get an idea of what the GIMPLE IR looks like from the debug dumps generated with the -fdump-tree-all command-line option. For example, the C function

int foo(int a, int b, int c, int d)
{
  int tmp;
  if (a)
    tmp = b + c + d;
  else
    tmp = 23;
  return tmp;
}

is generated in GIMPLE as

foo (int a, int b, int c, int d)
{
  int tmp;
  int D.2721;
  int D.2719;

<bb 2>:
  if (a_2(D) != 0)
    goto <bb 3>;
  else
    goto <bb 4>;

<bb 3>:
  D.2719_5 = b_3(D) + c_4(D);
  tmp_7 = D.2719_5 + d_6(D);
  goto <bb 5>;

<bb 4>:
  tmp_8 = 23;

<bb 5>:
  # tmp_1 = PHI <tmp_7(3), tmp_8(4)>
  D.2721_9 = tmp_1;
  return D.2721_9;
}

This IR looks very different from the LLVM IR, but it is mostly because the debug dumps tries to be helpful and writes e.g. addition as "a + b" instead of using the operation name followed by the operands, such as "plus a, b", which would have been more convenient, as this is how we will need to write the matching rules in match.pd...

One thing I like about this IR is that it may contain information about parentheses from the original language. This is used by the Fortran compiler, as the Fortran standard allows the compiler to optimize floating point calculations (reassociation, etc.), but it requires the compiler to respect the order of evaluation specified by parentheses. I think this is the best way of handling floating point, and I wish more languages had chosen this semantic... As an example of how parentheses looks like in the IR, consider

a = (b + 1.0) - 1.0;

that is generated as

_3 = *b_2(D);
_4 = _3 + 1.0e+0;
_5 = ((_4));
_6 = _5 - 1.0e+0;
*a_7(D) = _6;

As mentioned above, I think the syntax would have been clearer if the parenthesis was written as

_5 = paren _4;

as this is how it is represented within the compiler — the right parenthesis is implied by the evaluation order.

We are mostly isolated from the details of the IR when doing the peephole optimizations, as they only work on small sequences of instructions, and both LLVM IR and GENRIC/GIMPLE looks similar on that level. The transformation specifications in match.pd are written in a similar way as for ALIVe, although using a "lispy" syntax. As trivial example, for eliminating double bitwise negation, that for ALIVe looks like

; ~~x -> x
%1 = xor %x, -1
%2 = xor %1, -1
  =>
%2 = %x

is written as

/* ~~x -> x */
(simplify
  (bit_not (bit_not @0))
  @0)

in the GCC match.pd. The major difference between LLVM and GCC that will affect us is that GCC uses information from the type system to determine wrapping behavior (unsigned integers may wrap, but the behavior is undefined if signed integers overflow), so the transformation rules need to look at the type in order to determine the wrapping semantics. GCC also have types such as complex numbers that is not a basic type in LLVM, and those extra types complicates some transformations.

The next blog post will look at the details of how the transformations are specified in match.pd.

Verifying optimizations using SMT solvers

I found a nice talk "Verifying optimizations using SMT solvers" from the 2013 LLVM Developers' Meeting where Nuno Lopes talked about similar things as my previous blog post (but more detailed and better).

In the talk he argues for using SMT solvers during compiler development. The obvious example is things like the bug PR17827 where the developers were unsure if a transformation is valid or not, but he also has an example of using it to help when implementing things like the LLVM ConstantRange data-structure. I'm not convinced it will help that often in reality, but I will definitely give it a try next time I have similar problems...