C pointers are not hardware pointers

Pointers in the C language are more abstract than pointers in the hardware, and the compiler may surprise developers that think that pointers in C work in the same way as pointers in the CPU.

A C pointer points into what the standard calls an object, points to the byte following the object, or has the value NULL. The concept of "object" here is very different from the C++ object — an object in the C standard is a range of bytes allocated as a unit,¹ so x and y are objects in

int x;
struct foo y[10];

and the memory returned by a call to malloc is an object.

Dangling pointers are dangerous, and may invoke undefined behavior even when they are not dereferenced. The reason is that the value of a pointer becomes indeterminate when the object it points to (or just past) reaches the end of its lifetime. That is, a dangling pointer is treated the same way as an uninitialized pointer, and all use of uninitialized values invokes undefined behavior.

void foo(int *p, int *q)
{
    free(p);
    if (p == q)  // Undefined behavior!
        bar();
}

The pointer p has indeterminate value after free(p), so the comparison invokes undefined behavior.

Comparing pointers using the relational operators (<, >, <=, and >=) requires them to point into the same object (or the byte following the object). That is

int *p = malloc(64 * sizeof(int));
int *q = p + i;
if (p < q)
   foo();

is fine (provided that 0 ≤ i ≤ 64), but

int *p = malloc(64 * sizeof(int));
int *q = malloc(64 * sizeof(int));
if (p < q)  // Undefined behavior!
   foo();

invokes undefined behavior. Similarly, subtraction of pointers are only allowed for array objects, and both pointers must point into the same array object (or the byte following the object).

Arithmetic on a pointer cannot make it point outside the object (more than on the byte following the object). In particular, arithmetic on a pointer cannot make it point into another object. This is useful for compilers, as they can use this to track memory accesses and trivially determine that reads and writes through pointers derived from different objects do not conflict. Actually, it would be very hard for the compiler to place variables in registers if writes through pointers could modify arbitrary objects!

There is however one special case where a pointer can point to the address of another object — two objects may be placed next to each other in memory, which is typical for cases such as as

int x, y;

and p and q can now have the same value after

int *p = &x + 1;
int *q = &y;

But the pointer p does not really point to y — it points to the address following x. Dereferencing p invokes undefined behavior, so you cannot really use the fact that p and q have the same value.

GCC has a somewhat aggressive interpretation on the standard, so it compiles p == q to false if it determines that they are derived from different objects (see GCC bug 61502 for details). This has the fun effect that it is possible to get pointers p and q that point at the same memory address, but p == q evaluates to false, as in

#include <stdio.h>

int main(void)
{
    int x, y;
    int *p = &x + 1;
    int *q = &y;
    printf("%p %p %d\n", (void*)p, (void*)q, p == q);
    return 0;
}

that prints

0x7f7fffffdafc 0x7f7fffffdafc 0

on my development machine when compiled with a recent GCC.

---

1. The C standard's definition of object is a bit more involved, as it also involves the type of the data within the range of bytes, but this does not affect the discussion in this blog post. I'll come back to the type related part in a future blog post on aliasing.

This blog post was updated 2016-05-19:

• Added casts in last example
• Changed 256 to 64*sizeof(int) in examples

How undefined signed overflow enables optimizations in GCC

Signed integers are not allowed to overflow in C and C++, and this helps compilers generate better code. I was interested in how GCC is taking advantage of this, and here are my findings.¹

Signed integer expression simplification

The nice property of overflow being undefined is that signed integer operations works as in normal mathematics — you can cancel out values so that (x*10)/5 simplifies to x*2, or (x+1)<(y+3) simplifies to x<(y+2). Increasing a value always makes it larger, so x<(x+1) is always true.

GCC iterates over the IR (the compiler's Internal Representation of the program), and does the following transformations (x, and y are signed integers, c, c1, and c2 are positive constants, and cmp is a comparison operator. I have only listed the transformations for positive constants, but GCC handles negative constants too in the obvious way)

• Eliminate multiplication in comparison with 0

  (x * c) cmp 0   ->   x cmp 0 
  

• Eliminate division after multiplication
  

  (x * c1) / c2   ->   x * (c1 / c2) if c1 is divisible by c2
  

• Eliminate negation

  (-x) / (-y)     ->   x / y
  

• Simplify comparisons that are always true or false

  x + c < x       ->   false
  x + c <= x      ->   false
  x + c > x       ->   true
  x + c >= x      ->   true
  

• Eliminate negation in comparisons

  (-x) cmp (-y)   ->   y cmp x
  

• Reduce magnitude of constants

  x + c > y       ->   x + (c - 1) >= y
  x + c <= y      ->   x + (c - 1) < y
  

• Eliminate constants in comparisons

  (x + c1) cmp c2         ->   x cmp (c2 - c1)
  (x + c1) cmp (y + c2)   ->   x cmp (y + (c2 - c1)) if c1 <= c2
  

  The second transformation is only valid if c1 <= c2, as it would otherwise introduce an overflow when y has the value INT_MIN.

Pointer arithmetic and type promotion

If an operation does not overflow, then we will get the same result if we do the operation in a wider type. This is often useful when doing things like array indexing on 64-bit architectures — the index calculations are typically done using 32-bit int, but the pointers are 64-bit, and the compiler may generate more efficient code when signed overflow is undefined by promoting the 32-bit integers to 64-bit operations instead of generating type extensions.

One other aspect of this is that undefined overflow ensures that a[i] and a[i+1] are adjacent. This improves analysis of memory accesses for vectorization etc.

Value range calculations

The compiler keeps track of the variables' range of possible values at each point in the program, i.e. for code such as

int x = foo();
if (x > 0) {
  int y = x + 5;
  int z = y / 4;

it determines that x has the range [1, INT_MAX] after the if-statement, and can thus determine that y has the range [6, INT_MAX] as overflow is not allowed. And the next line can be optimized to

  int z = y >> 2;

as the compiler knows that y is non-negative.

The undefined overflow helps optimizations that need to compare two values (as the wrapping case would give possible values of the form [INT_MIN, (INT_MIN+4)] or [6, INT_MAX] that prevents all useful comparisons with < or >), such as

• Changing comparisons x<y to true or false if the ranges for x and y does not overlap
• Changing min(x,y) or max(x,y) to x or y if the ranges do not overlap
• Changing abs(x) to x or -x if the range does not cross 0
• Changing x/c to x>>log2(c) if x>0 and the constant c is a power of 2
• Changing x%c to x&(c-1) if x>0 and the constant c is a power of 2

Loop analysis and optimization

The canonical example of why undefined signed overflow helps loop optimizations is that loops like

for (int i = 0; i <= m; i++)

are guaranteed to terminate for undefined overflow. This helps architectures that have specific loop instructions, as they do in general not handle infinite loops.

But undefined signed overflow helps many more loop optimizations. All analysis such as determining number of iteration, transforming induction variables, and keeping track of memory accesses are using everything in the previous sections in order to do its work. In particular, the set of loops that can be vectorized are severely reduced when signed overflow is allowed.

---

1. Using GCC trunk r233186,  "gcc version 6.0.0 20160205 (experimental)"

This blog post was updated 2016-02-23:

• Corrected first sentence to say "overflow"instead of "wrap".
• Removed one incorrect transformation from "Eliminate Negation" where I had misread the GCC source code.
• Corrected the ranges in the "Value range calculations" example.

More Turing-completeness in surprising places

My twitter feed was full of “printf is Turing-complete” tweets after the 32c3 talk "New memory corruption attacks: why can't we have nice things?" (see printbf for the paper and the implementation discussed in the video), and that inspired me to read some more articles about Turing-complete¹ mechanisms hiding in surprising places...

C++ exception stack unwinding is Turing-complete

The DWARF debugging information format is complex, which is needed in order to describe optimized code. For example, an expression such as i+1 may be placed in a register reg, and i is not available anywhere in the registers or memory in the optimized program. But the debugger should be able to display the value of i, so the debug information must be able to express that i has the value reg-1. And optimized code can be transformed in much more complex ways than this, so DWARF does (surprisingly) define a stack machine that can do arbitrary computation in order to be able to represent the information.

Exception handling need to unwind the stack and restore registers, which is functionality that can be represented by the debug information, so DWARF was adopted (with some minor modifications) for the exception handling. The stack unwinding code can thus execute programs "hidden" in the DWARF information while unwinding the stack.

The Turing-completeness of this is not strange in the same way as the others I have written about previously; DWARF is designed to be general! But it is probably surprising to most developers that this functionality exists... The paper "Exploiting the hard-working DWARF: Trojan and Exploit Techniques With No Native Executable Code" looks at what can be done with this. The stack machine is rather easy to work with — here is an example from the paper that calculates the length of a string that is located just below the stack frame:

  # Value at −0x8(%rbp) on stack
  DW_OP_breg6 −8
  DW_OP_lit0  # initial strlen
  DW_OP_swap
  DW_OP_dup
LOOP:
  DW_OP_deref_size 1
  # Branch if top of stack nonzero
  DW_OP_bra NOT_DONE
  DW_OP_skip FINISH
NOT_DONE:
  # Increment the counted length
  DW_OP_swap
  DW_OP_lit1
  DW_OP_plus
  DW_OP_swap
  # Add length to char pointer
  DW_OP_plus
  DW_OP_skip LOOP
FINISH:
  # Finally put the character count on the top of the stack
  # as return value
  DW_OP_swap

ELF metadata is Turing-complete

The Runtime Linker/Loader (RTLD) is responsible for loading shared libraries into a process' address space and updating the symbol references in the object code using the relocation and symbol tables. The RTLD can be viewed as a machine that is executing the relocation tables, and the paper "“Weird Machines” in ELF: A Spotlight on the Underappreciated Metadata" shows that this machine is Turing-complete by constructing an assembly-like  language  composed  of  three  instructions

• mov — move
• add — addition
• jnz — jump if not zero

where each instruction is built from a sequence of relocations.

There are two kinds of structures involved in the relocation:

• The symbol tables contain information about the symbols, where each symbol is described by the ELF64_Sym structure

  typedef struct
  {
    Elf64_Word    st_name;      /* Symbol name (string table index) */
    unsigned char st_info;      /* Symbol type and binding */
    unsigned char st_other;     /* Unused */
    Elf64_Section st_shndx;     /* Section index */
    Elf64_Addr    st_value;     /* Symbol value */
    Elf64_Xword   st_size;      /* Symbol size */
  } Elf64_Sym;
  

• The relocation tables specify how to modify the binary, where each relocation is described by the Elf64_Rela structure
  

  typedef struct
  {
    Elf64_Addr    r_offset;     /* Address to patch */
    Elf64_Xword   r_info;       /* Relocation type and symbol index */
    Elf64_Sxword  r_addend;     /* Addend */
  } Elf64_Rela;
  

The construct of the machine is using three kinds of relocations, R_X86_64_COPY, R_X86_64_64, and R_X86_64_RELATIVE, which have the functionality

R_X86_64_COPY         memcpy(base + r.r_offset, s.st_value, s.st_size)
R_X86_64_64           *(base + r.r_offset) = s.st_value + r.addend + base
R_X86_64_RELATIVE     *(base + r.r_offset) = r.r_addend + base

where r is the relocation, s is the symbol referenced by the relocation, and base is the ELF object’s base address (that is typically 0 for an executable). These relocations directly correspond to move and addition instructions of the form

mov *0xbeef0000, $0x02        # *(uint64_t*)0xbeef0000 = 2;
mov *0xbeef0000, [%foo]       # *(uint64_t*)0xbeef0000 = *(uint64_t*)foo;
add *0xbeef0000, %foo, $0x02  # *(uint64_t*)0xbeef0000 = foo + 2;

For example, an addition instruction

add *0xbeef0000, %foo, $0x02

is encoded as a relocation entry with r_offset=0xbeef0000, r_addend=2, and r_info specifying relocation type R_X86_64_64 and the symbol foo.

Branch instructions are implemented by modifying the data RTLD is using while processing the relocations. The RTLD is maintaining a doubly linked list of link_map structures containing information for each ELF object, and it iterates over this list in reverse order when relocating the binary

while (lm != NULL) {
  r = lm->dyn[DT_RELA];
  end = r + lm->dyn[DT_RELASZ];
  for (r ; r < end; r++)
    relocate(lm, r, &dyn[DT_SYM]);
  lm = lm->prev;
}

A branch instruction can be implemented by relocations modifying lm->prev, lm->dyn[DT_RELASZ], or lm->dyn[DT_RELA] so that an lm structure is skipped, handled partially, or handled multiple times. There are some complications such as finding the address to modify, and to save/restore the original value to be able to exit the program. I refer to the paper for the details.

The only thing remaining is a conditional branch instruction. The paper constructs the jnz instruction by noting that symbols of the type STT_GNU_IFUNC are treated differently depending on if the section index is 0 or not, and the symbol can be initialized so that an add instruction of the form

add *0xbeef0000, %foo, $0x00

has the effect

*(uint64_t*)0xbeef0000 = (s.st_shindx != 0) ? CONSTANT : 0;

where s is the Elf64_Sym structure describing foo. This can now be used when rewriting the end marker lm->dyn[DT_RELASZ] so that RTLD does not enter the for-loop for the link map when the condition is 0 (and the machine is thus not jumping to the part of the program defined by those relocations), by relocations first writing the condition to test to s.st_shindx of a temporary symbol s, and then writing the symbol (by adding 0 to it) to lm->dyn[DT_RELASZ].

---

1. I'm playing fast and loose with the concept “Turing-complete”, as does most papers I have read. I had expected computer scientists to be more careful, and use terms like "linear bounded automaton" or similar...

spirv-tools — status, problems, and plans

I have done some work on spirv-tools since the posts about the human friendly SPIR-V representation and Python API, so it makes sense to do a status update now.

Most of the development has been to actually make the code work. And I think it does now. For example, one of my tests is to disassemble all the shaders from the Mesa shader-db (containing shaders from some old games), assemble the result, and verifying that the binaries are identical.

API

IR improvements

The major user-visible change in the API is that the IR has been modified so that

• An ID is represented by an ID object. The ir.Id class contains a reference to the instruction defining the ID, so there is no need to use module.id_to_inst[id] each time you want to get the instruction (which you usually want each time you have an ID). The instruction is now accessed as id.inst.
• A literal number is represented as an integer.
• A literal string is represented as a string.
• An enumerated value is represented as a string of the enumeration name. I choose this representation in order to make it easy to see what the code does. For example

  if inst.operands[0] == 'FPFastMathMode':
  

  checks if a decoration is specifying the floating-point fast math flags.
• A mask is represented as a list of strings of the enumeration names, and the empty list is used when no value is set in the mask. Checking if a bit is set is done as

  if 'NotNaN' in inst.operands[1]:
  

Optimizations

I have also added optimization passes corresponding to the LLVM instcombine, constprop, die (Dead Instruction Elimination), and simplifycfg passes. And a mem2reg pass will be available soon.

I'm mostly working on the optimizations just to verify that the API makes sense, and some of the passes (constprop and instcombine) are essentially placeholders right now, but I will finish up the code when the final SPIR-V specification is released.

Plans

My short-term plan for the API:

1. Make this a real Python package, installable with pip. And make it work for Python 3.x too.
2. Add a mem2reg pass (including infrastructure for simple data flow analysis).
3. Implement a better API for handling constants, types, and global instructions.
4. Clean up the API. There are some things that need to be renamed and tweaked a little bit (for example some functions having "uses" in their name treat decorations as a usage, and some does not).
5. Document the API. Add examples/tutorials.

Assembler / disassembler

The biggest user-visible change in the assembler/disassembler is that global symbols now use normal ID tokens (such as %main) instead of prefixing the name with @ (such as @main). The original implementation used @ in order to simplify parsing of a more convenient syntax for declaring global variables

@gl_FragColor = Output <4 x f32> BuiltIn(FragColor)

but decorations are appended to normal instructions, so this is not much more convenient than using an OpVariable instruction

%gl_FragColor = OpVariable %44 BuiltIn(FragColor) Output

The only real difference is that the type must be specified as a pointer type for OpVariable, so it is not pretty-printed (The reason is that the pointer type contains a storage class, and I have not found a good way to include it in a pretty-printed type. The storage class is an operand to OpVariable too, so this could be written as

%gl_FragColor = OpVariable *<4 x f32> BuiltIn(FragColor) Output

if the assembler is updated to infer the storage class from the instruction. But I'm not sure if that is a good idea or not...).


The assembler/disassembler are mostly done, but two things needs to be implemented:

1. Floating-point literals
2. Correct name handling

And there are lots of minor things that could be improved...

Floating-point literals

The assembler is supposed to allow

%52 = OpFSub <4 x f32> %49, (0.5, 0.5, 0.5, 0.5)

instead of

%50 = OpConstant f32 0x3f000000
%51 = OpConstantComposite <4 x f32> %50, %50, %50, %50
%52 = OpFSub <4 x f32> %49, %51

but the current implementation does only handle integer/Boolean literals.

Name handling

The assembler accepts named IDs (such as %main) and the disassembler is using the names from OpName decorations to create named IDs. But there are some problems with the implementation:

• Name mangling need to be implemented in order to handle polymorphism (the disassembler currently use the numerical value for IDs if it finds several identical names in the binary, and the assembler returns errors for re-declared names).
• ID names declared within a function should be local to the function.
• How should the tools handle multiple names for the same ID? For example, if the name in OpEntryPoint differs from the name in an OpName debug instruction for the function. Or if one instruction is decorated with multiple OpName names.

Minor tweaks

SPIR-V spreads out some information over the file (e.g. decorations are placed in the beginning of the file, far from the instruction they refer to), and the goal of the textual representation is to collect it in a way that makes it is easy to see all relevant details affecting each instruction, as well as supressing irrelevant details. But it is a bit unclear how to make this as useful as possible...

Some examples of things to consider:

• Is it better to be consistent or compact? Decorations are written after the instruction name, and a FPFastMathMode decoration is currently written as

  %52 = OpFSub <4 x f32> FPFastMathMode(NotNaN | NotInf) %49, %50
  

  The values are unique, so it could be written more compact, without the FPFastMathMode keyword

  %52 = OpFSub <4 x f32> NotNaN | NotInf %49, %50
  

  But there may exist better ways of improving this...
• Pointers are heavily used in Kernels, so it makes sense to pretty-print them. But how should the storage class be handled?
• Should structures be pretty printed?
• Are OpLoopMerge and OpSelectionMerge instructions necessary, or should the assembler insert them automatically when needed?

I need to look at lots of real world shaders in order to get an idea of what makes sense, but that need to wait for the SPIR-V specification to be released and shader compilers becoming available. And I need to find relevant modern shaders to look at...

Plans

My short-term plan for the assembler/disassembler:

1. Implement floating-point literals
2. Document the assembler syntax

Instruction-less computation – technical details

This blog post continues the previous post by describing the technical details.

Configuring x86 hardware

The IA-32 hardware is configured by a combination of architectural registers and descriptors in memory. The construction of the movdbz machine uses four different kinds of descriptors:

• memory translation tables
  The memory translation is done through a two-level page table, where the first level is called a "page directory". The CR3 register contains the physical address of the page directory to use.

• TSS – Task-State Segment
  The TSS is a structure where the processor state (registers, status flags, etc.) is stored when the task is not running.

• GDT – Global Descriptor Table
  The GDT is an array of "segment descriptors" containing a pointer to a segment (such as a TSS) and some flags. The task switching mechanism access the TSS by indexing the GDT. For example,

  ljmp $24, $0

  switches to a new task whose TSS is described at offset 24 in the GDT.

• IDT – Interrupt Descriptor Table
  The IDT defines how each interrupt is handled by providing an interrupt descriptor for each interrupt type. We configure it to switch to a new task for #PF and #DF exceptions, and each descriptor contains an offset into the GDT corresponding to the target TSS.

Interrupts, task switching, and memory translation tables

The branch targets in the instructions are specified by the IDT, so it needs to be changed when stepping into a new instruction (i.e. when switching to a new task). The task switch cannot change it directly, but the IDT is placed in virtual memory, and the TSS contains CR3 that points to the page directory, so the new task may map a new page for the IDT, and thus modify the branch targets for the new instruction.

This does, however, give us new problems... The TSS contains the stack pointer which is used to encode the register value, so the TSS is now used to represent both a register and an instruction, and we need to separate them.

The TSS is defined as:

We can place this structure in memory so that it crosses a page boundary, where the stack pointer (ESP) is in one page, and CR3 in the other. That is, the TSS is mapped as a combination of a "register page" and an "instruction page".

The implementation places the TSS so that the page boundary is between ECX and EDX (ESP is thus placed 8 bytes from the top of the page).

Handling source and destination registers

The execution of one instruction in the movdbz machine is done in three steps:

1. Read the TSS for the new instruction.
2. Generate exception (as the program counter is invalid). If the stack pointer is not zero, write status and update the stack pointer.
3. Store the TSS.

The registers are represented by the stack pointer stored in the TSS, but the instructions use two registers (source and destination), so the read and write of the stack pointer should be to different TSS structures.

The TSS is stored in virtual memory, and we may play some tricks with the memory translation. The "read TSS" step reads the state (including the CR3) from the TSS, which updates the memory translation. We may use this to map a new register page for the TSS as a side effect of reading the TSS, and the "store TSS" will now write to this new register page (i.e. the destination register). So we will in some sense have two TSS structures; one "source TSS" and one "destination TSS".

Task switching to itself

There is a hardware restriction that task switching must be done to a new task – it is not possible to switch to the currently running task. This means that instructions of the form

loop:    movdbz r0, r0, loop, done

are invalid. But this is not much of a problem as it is easily fixed by inserting a NOP instruction

loop:    movdbz r0, r0, nop, done
nop:     movdbz discard, 0, loop, loop

TSS segment descriptor busy flag

The IA-32 tries to prevent recursive task switching; it has a "busy flag" that is set in the TSS segment descriptor when a task is entered from an interrupt, and the flag must be cleared before the task can be run a second time.

We need to clear this flag, and we do this by mapping the GDT page containing the instruction's segment descriptor as the instruction page in the destination TSS. Writing the TSS will now overwrite the six last segment descriptors in that GDT page. The descriptor at offset 0x0ff8 is overwritten by the value of EAX and EDX, so the instruction page initializes those registers with the original descriptor value, which clears the flag when they are written to the TSS.

This means that we can only have one TSS segment descriptor per page, and the GDT has a maximum size of 16 pages, so we can only have 16 segment descriptors (and thus only 16 TSS). But each instruction sets up the page tables, so we may remap these to correspond to different instructions over time. There are restrictions; each instruction needs to have its own and its destinations' TSS mapped, so their TSS segment descriptors must be different. The trapcc implementation handles this by graph coloring, but there are simpler ways (see "Generating assembler instructions" below).

Encoding of the instructions

We now have everything we need in order to describe the implementation.

The instless_comp uses three TSS segment descriptors for the instructions, at GDT offset 0x1ff8, 0x2ff8, and 0x3ff8, and have the corresponding TSS mapped at address 0x40ffd0, 0x41ffd0, and 0x42ffd0 in the virtual address space.

The instructions are encoded in four pages:

• Page Directory
  The page directory sets up five virtual address ranges:
  
  • STACK – the stack for the movdbz machine
  • INST – mappings for the movdbz instruction (where TSS  and IDT are placed)
  • GDT – the GDT
  • X86 – the code and data for the CPU (only needed to access the TSS when exiting the movdbz machine)
  • PROG – the movdbz program
  It is only the INST address range that is specific for the instruction – the other ranges have identical mappings in all instructions.

• Page Table
  This maps the IDT page, the destination TSS (destination register page and GDT page) for the current instruction, and the source TSS (source register page and instruction page) for the successor instructions, into the address space.

• Instruction page
  The instruction page of the TSS is set up so that
  
  • CR3 points to the page directory.
  • The program counter (EIP) is set to an invalid address.
  • EAX and EDX have the value of the corresponding TSS segment descriptor.
  • EFLAGS, that contains miscellaneous flags for the system state, is set to the value used when running the CPU.

• IDT page
  The IDT page contains an IDT that handles #PF and #DF exceptions by switching to a task corresponding to the destination instruction.

The movdbz machine is started by switching to the task corresponding to the first instruction, and it is possible to exit from the machine by letting it switch to the task identified by GDT index 0x18, which is the task for the original program running on the CPU.

Generating assembler instructions

The restrictions on the instructions make it hard to write assembly code, and are annoying when doing code generation. The assembler in instless_comp solves this by generating each assembler instruction as three "real" instructions, so that an instruction of the form

label:    movdbz rdest, rsrc, label_nonzero, label_zero

is generated as

label:    movdbz discard, 1, label+2, label+2
label+1:  movdbz discard, 1, label+2, label+2
label+2:  movdbz rdest, rsrc, label_nonzero, label_zero+1

The first instruction is always encoded with the TSS descriptor at offset 0x1ff8, the second at offset  0x2ff8, and the third at offset 0x3ff8, so this always satisfies the constraints without needing graph coloring. And it also handles the assembler instruction branching to itself, as that will branch from the last instruction to one of the two preceding NOP instructions.

We also know that the target in an assembly instruction always is a NOP, so its input register is always the constant 1, and we do not need to propagate the input registers to its predecessors.

Instruction-less computation

The paper "The Page-Fault Weird Machine: Lessons in Instruction-less Computation" show that you can run programs on the X86 fault handling mechanism, i.e. without executing any instructions on the CPU!

The construction of this weird machine is using two properties of the IA-32 architecture:

• Task switching
  The IA-32 has hardware support for task switching — storing the CPU state (registers and status flags), and resuming execution with a new memory map and previously stored CPU state. The interrupt controller may be configured so that a task switch happens when an exception is raised.
• Interrupts writes an error code to the stack
  The Page-Fault Exception (#PF) writes a 32-bit error code to the stack and decrements the stack pointer before handling the exception, which lets us modify the stack pointer without executing any CPU instructions. The stack pointer cannot wrap, so a Double Fault Exception (#DF) is raised instead of #PF if the stack pointer is less than four.

This can be used to  create a machine with registers r0, r1, ..., and a move-branch-if-zero-or-decrement instruction

movdbz rdest, rsrc, label_nonzero, label_zero

that is doing the work corresponding to

if (rsrc == 0) {
    rdest = rsrc;
    goto label_zero;
} else {
    rdest = rsrc - 1;
    goto label_nonzero;
}

The movdbz instruction is Turing-complete (see e.g. Wikipedia "One instruction set computer"¹, or this blog post that describes a BF compiler that only generates movdbz instructions). The paper comes with an implementation in trapcc, and I have made a somewhat simpler and more user-friendly implementation in instless_comp.²

A simplified description of the construction is that each register is represented by a task where the stack pointer contains the register's value multiplied by four. Each instruction is represented by an interrupt vector that switches to new tasks (including a new interrupt vector), where #DF switches to the task corresponding to label_zero and #PF switches to label_nonzero. All tasks have invalid program counters, so the new task will raise a new #PF exception (or #DF if the stack pointer is zero), and the machine steps into the next instruction. The implementation is however much more involved, and I describe the construction in detail in a separate blog post.

The stack pointer needs to point to valid memory (or we will get other interrupts), so the registers can only have values that are represented as valid stack addresses, and we cannot represent 32-bit values even if we map all memory for the stack (the decrement is done by subtracting four from the stack pointer, so we lose the two least significant bits...). It is natural to just map page 0 for the stack to give us registers that are 10 bits wide.

It is possible to make the registers wider by adding more pages to the stack, but it does not help much; the machine can only do subtraction, so e.g. addition

a = b + c;

need to be done by subtracting from a maximum value

a = MAX_VAL - (MAX_VAL - b - c);

And the machine can only decrement by one, so the subtractions need to be done by looping

tmp = MAX_VAL;
while (b--)
    tmp--;
while (c--)
    tmp--;
a = MAX_VAL;
while (tmp--)
    a--;

That is, the running time of addition is exponential in the bit width of the registers, so wide registers are not that useful.

The blog post is continued in part 2 that describes the technical details.

---

1. movdbz reduces trivially to the subtract-and-branch-if-nonzero instruction.

2. The trapcc need to do global analysis (graph coloring etc.) when generating the instructions in order to satisfy some annoying hardware constraints. My implementation uses a less efficient instruction encoding that makes it possible to handle each instruction independently (and makes it easier to write assembly manually).

mov-only code generation

I stumbled on the M/o/Vfuscator compiler that only use mov instructions in the generated code¹ using ideas from the "mov is Turing-complete" paper.

It proves to be surprisingly easy to generate such code. This blog post shows how it is done using a somewhat idealized version of the CPU, but it should be easy to map it on the real X86 ISA. The examples use registers r0, r1, …, and a mov instruction that can be in one of the three forms

mov rdest, rsrc
mov rdest, [rsrc + roffset]      ; Load indexed
mov [rdest + roffset], rsrc      ; Store indexed

It is possible to use an immediate constant instead of rsrc, or for the rdest and roffset in the addresses. The width of the move can be 8 bits (movb) or 32 bits (movl). We'll only use 8-bit values for the computations — wider widths can be handled by working on one byte at a time. Pointers are assumed to be 32 bits wide.

if-statements

We'll begin with if-statements. Comparing two registers r1 == r2 and placing the result in r0 can be done as

movb [&scratch + r1], 0
movb [&scratch + r2], 1
movb r0, [&scratch + r1]

where scratch is an array

uint8_t scratch[256];

We cannot have any flow control when only using mov instructions, so the idea is to handle if-statements by executing both the true and false parts, and ignoring the result from the false part. E.g. code of the form

if (r1 == r2)
    r0 = r3;
else
    r0 = r4;

is compiled as if written

r0 = (r1 == r2) ? r3 : r4;

which can be done as

movb [&scratch + r1], 0
movb [&scratch + r2], 1
movb r0, [&scratch + r1]
movb [&scratch + 1], r3
movb [&scratch + 0], r4
movb r0, [&scratch + r0]

This works fine as long as everything is in registers, or both the true and false parts write to the same memory. The case where they write different memory need to be handled by writing to a dummy location for the cases where no value should be stored. For example,

if (r1 == r2)
    a = r3;

is compiled to

movb [&scratch + r1], 0
movb [&scratch + r2], 4
movb r0, [&scratch + r1]
movl [&tmp + 4], &a
movl [&tmp + 0], &dummy
movl r0, [&tmp + r0]
movb [r0 + 0], r3

where tmp and dummy are defined as

uint32_t tmp[2];
uint8_t dummy;

Addition

Addition by a constant can be implemented by leveraging the addition done within the addressing mode by indexing in a constant array

const uint8_t constants[512] = {
    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
       ...
    0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff,
    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
       ...
    0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff
};

so e.g. adding 23 to r0 is done as

movb r0, [&(constants+23) + r0]

Loops etc.

We now have nearly everything needed to implement a Turing machine where the tape is implemented as an array that is indexed by the current position. The only problem is that we only can do straight line code... So we cheat by adding a jmp instruction at the end of our program, jumping back to the first instruction. This works fine for implementing a Turing machine, as it is typically written as

while (1) {
    if (current_state == 0) {
        /* Do the work for this state */
        current_state = /* State transition */
    } else if (current_state == 1) {
        /* Do the work for this state */
        current_state = /* State transition */
    } else if ...
}

But the same approach works for normal languages too, by treating each basic block as a state, and to do a state transition for each branch.

Program termination

Finally, we need a way to terminate the program. This is done by writing to address 0

movb [0 + 0], 0

which terminates the process with a segmentation fault. Conditional termination is done with the same dummy-variable trick as for the conditional store above.

---

1. This is not completely true – it need exactly one jmp instruction in addition to the mov instructions.

Proving correctness of the GCC match.pd — Part 2

The previous post talked about the background and the GCC GIMPLE IR. This post continues with a look at the format of match.pd.

The match.pd contains transformation rules for the IR, written in a "lispy" domain-specific language. Each transformation rule is specified by the simplify expression that has two operands: a template expression that is matched to the IR, and a replacement expression that replaces the matching expression in the IR. For example

/* x & ~0 -> x */
(simplify
  (bit_and @0 integer_all_onesp)
  @0)

match expressions corresponding to "x&~0" and replaces them with "x".

A template operand of the form @<number> is called a "capture" — it captures the operand so you can refer to it in other parts of the simplify expression. Using the same capture multiple times in a template means that the operands need to be identical, e.g.

/* x & x -> x */
(simplify
  (bit_and @0 @0)
  @0)

match a bit_and with two identical operands.

The predicates, such as integer_all_onesp in the first example above, are the normal predicates used in the GCC middle-end. It is possible to capture operators and predicates too, so you may write

/* x | ~0 -> ~0 */
(simplify
  (bit_ior @0 integer_all_onesp@1)
  @1)

for the rule that changes "x|~0" to "~0".

Pattern matching for commutative operators may use the :c decoration to match the operands in any order. For example

/* x | ~0 -> ~0 */
(simplify
  (bit_ior:c @0 integer_all_onesp@1)
  @1)

will match both "x|~0" and "~0|x" (although it does not matter in this case, as the GCC IR always has the constant as its second argument for commutative operations).

There are cases where you cannot express the replacement using this syntax, so it is possible to generate the replacement expression using C++ code by placing it between curly braces

/* x ^ x -> 0 */
(simplify
  (bit_xor @0 @0)
  { build_zero_cst (type); })

The type of the outermost matching expression (i.e. the type of the bit_xor) is available in the variable type.

It is often the case that additional conditions need to be fulfilled in order to permit the replacement. This can be handled with an if expression:

/* x / -1 -> -x */
(simplify
  (exact_div @0 integer_minus_onep)
  (if (!TYPE_UNSIGNED (type))
   (negate @0)))

This replaces the original expression only if the type of the outermost expression is signed. The operand to if is a C-style expression, so it is possible to create complex conditions, such as

(if (!HONOR_SNANS (element_mode (type))
     && (!HONOR_SIGNED_ZEROS (element_mode (type))
         || !COMPLEX_FLOAT_TYPE_P (type)))

Many rules are identical for several operations, and you can handle this with a for expression

/* x / -1 -> -x */
(for div (trunc_div ceil_div floor_div round_div exact_div)
 (simplify
   (div @0 integer_minus_onep)
   (if (!TYPE_UNSIGNED (type))
    (negate @0))))

The if and for can be nested arbitrarily, and you can use them to construct complex rules where multiple simplifications are done within the same for or if expression.

Finally, there are some additional functionality, such as specifying parts of templates optional, but I'll wait with that until I have made some progress with the functionality described so far...

The next blog post will look at actually proving things.