The POSTRISC architecture

This document describes the architecture of a non-existent virtual processor. The processor instruction set architecture and the processor itself are referred to as POSTRISC. This name is because «POST-RISC» is a common name for projects of hypothetical processors, replacing processors with the RISC architecture (Reduced Instruction Set Computer). The virtual processor POSTRISC combines the best (as it seems to me) qualities of existing and past architectures.

Main features of the POSTRISC architecture:

• fixed format based on packed bundles of instructions
• a large number of universal registers (128) of 128 bits, for deep loop unrolling and rescheduling
• register rotation (implemented a general-purpose hardware circular buffer)
• load/store architecture with strong separation memory access and computing instructions
• implicit predication (all instructions allow conditional execution under the control of predicate mask)
• fused operations («multiply-add», shift with addition or subtraction, indexed with scaling and memory access, compare and branch, addition with compare and branch)
• position independent code only
• vector SIMD-like instructions (128-bit universal registers can be used as vectors of integers or real numbers)
• hardware implementation of 128-bit (quadruple) floats
• additional hardware protection against software vulnerabilities

Sources are available at https://github.com/bdpx/postrisc. This repository contains source code, sample programs for POSTRISC, this description of the virtual processor. To build program cmake and clang++/g++ needed. To build this documentation from xml sources xsltproc/xmllint needed.

The postrisc is a console application for all basic tasks. Uses standard streams for input/output that need to be redirected from file or to file. It is called with different keys from the command line (table below). Additional parameters are set in the XML config file file.

--scan <src.s

--scan-html <src.s

--assemble <src.s >src.bin

--assemble-c

--disasm <src.bin

--dumpbin <src.bin

--execute <src.bin

--exeapp <src.bin

--html >out.html

--llvm

--export-definitions

--config file

--dump-file file

--log-file file

--log-level level

--log-subsystem list

--

For example, running POSTRISC ELF static-PIE image:

/path/to/postrisc \
    --exeapp --log-file "test-log.txt" \
    -- \
    postrisc-app -app-option1 -app-options2

The qtpostrisc is a Qt-based graphical application with assembler editor, debugger, doom graphical backend, etc (Qt5 required). Support same command-line options as console app.

For Wayland systems currently requires switch to X11 via «QT_QPA_PLATFORM=xcb» env:

QT_QPA_PLATFORM=xcb /path/to/qtpostrisc \
    --exeapp --log-file "doom-log.txt" \
    -- \
    doomgeneric.postrisc -doom -options

If this manual for the instruction architecture and assembler syntax doesn't exactly match the sample program (not yet updated), then this gen.html file contains a brief instruction set manual, automatically generated by the assembler.

Example program for assembler POSTRISC program.html does nothing sensible but uses all machine instructions and pseudo-instructions of assembler, all sections of the program, all addressing modes, and its only meaning is joint testing of assembler, disassembler, emulator in the process of writing them. It is a concatenation if separate little tests.

To run samples, assembler/emulator need configuration in xml format, its sample: config.xml.

The resulting binary program may be disassembled: out_diz.s and out_dump.s (with reported binary representation).

The results: result.txt. And full system dump: dump.html.

The POSTRISC building is based on cmake. Use generators "MSYS Makefiles" (Windows) or "Unix Makefiles" (Linux). Set -DCMAKE_BUILD_TYPE=Release as default. Set -DCMAKE_CXX_COMPILER=g++ or clang++ (MSVC isn't supported). The «USE_QUADMATH» macro controls the used long floating point internal implementation (quadmath or mpreal). Set -DUSE_QUADMATH=0 for clang (it doesn't support libquadmath), set 0 or 1 for g++.

The author is grateful in advance for reporting errors and inaccuracies in the virtual processor description and in the source code (which is far from error-free).

A set of tools for working with POSTRISC (assembler, disassembler, emulator is implemented) is incomplete. Further directions for improvement (the number in brackets like [2] characterizes the comparative complexity of the tasks):

1. Development of a set of sample programs to illustrate the capabilities of the virtual processor and assembler POSTRISC [1].
2. Development of a macroprocessor for the assembler POSTRISC[3].
3. Refactoring the formula calculation unit to introduce strict control over the use of object names in formulas (according to sections and segments of the program and the relocation types) [2].
4. Development of the object file format for a virtual processor compatible with the ELF standard, processing assembler for ELF [2].
5. Development of separate compilation tools, support for relocation records according to the ELF standard (Executable and Linkable Format) in assembler and the development of the linker [2].
6. Development of the block of floating-point calculations in the emulator (implemented), and support for real constants in assembler [3].
7. Development of a visual debugger for the emulator POSTRISC [2].
8. Development of a text editor with syntax highlighting of the assembler virtual processor [2].
9. Adding new «hardware» tools to the virtual processor architecture and its emulator: cache management, virtual memory and translation buffer [2].
10. Development of a simulator (cycle-accurate emulator) of the possible hardware implementation of a virtual processor, with the simulation of hardware such as multi-level instruction/data caches, translation buffers, branch prediction cache, return prediction stack, and other modern hardware. [5]

Content

Chapter 1. Choosing an instruction set

§ 1.1. Bottlenecks issue

§ 1.2. Memory non-uniformity problem

§ 1.3. The technologies of parallel operation execution

§ 1.4. Instruction format budget

Chapter 2. Instruction set architecture (ISA)

§ 2.1. General description of the instruction set

§ 2.2. Register files

§ 2.3. Instructions format

§ 2.4. Instruction addressing modes

§ 2.5. Data addressing modes

§ 2.6. Special registers

Chapter 3. Basic instruction set

§ 3.1. Register-register binary instructions

§ 3.2. Register-immediate instructions

§ 3.3. Immediate shift/bitcount instructions

§ 3.4. Register-register unary instructions

§ 3.5. Fused instructions

§ 3.6. Load/store instructions

§ 3.7. Branch instructions

§ 3.8. Miscellaneous instructions

Chapter 4. The software exceptions support

§ 4.1. Program state for exception

Chapter 5. The register stack

§ 5.1. Registers rotation

§ 5.2. Call/return instructions

§ 5.3. Register frame allocation

§ 5.4. The function prolog/epilog

§ 5.5. The register stack system management

§ 5.6. Calling convention

Chapter 6. Predication

§ 6.1. Conditional execution of instructions

§ 6.2. Nullification Instructions

§ 6.3. Nullification in assembler

Chapter 7. Physical memory

§ 7.1. Physical addressing

§ 7.2. Data alignment and atomicity

§ 7.3. Byte order

§ 7.4. Memory consistency model

§ 7.5. Atomic/synchronization instructions

§ 7.6. Memory attributes

§ 7.7. Memory map

§ 7.8. Memory-related instructions

Chapter 8. Virtual memory

§ 8.1. Virtual addressing

§ 8.2. Translation lookaside buffers

§ 8.3. Search for translations in memory

§ 8.4. Translation instructions

Chapter 9. The floating-point facility

§ 9.1. Floating-point formats

§ 9.2. Special floating-point values

§ 9.3. Selection for IEEE options

§ 9.4. Representation of floats in registers

§ 9.5. Floating-point computational instructions

§ 9.6. Floating-point branch and nullification instructions

§ 9.7. Logical vector instructions

§ 9.8. Integer vector operations

Chapter 10. Extended instruction set

§ 10.1. Helper Address Calculation Instructions

§ 10.2. Multiprecision arithmetic

§ 10.3. Software interrupts, system calls

§ 10.4. Cipher and hash instructions

§ 10.5. Random number generation instruction

§ 10.6. CPU identification instructions

§ 10.7. Instructions for the emulation support

Chapter 11. Application Model (Application Binary Interface)

§ 11.1. Sections and segments

§ 11.2. Data model

§ 11.3. Reserved registers

§ 11.4. Position independent code and GOT

§ 11.5. Program relocation

§ 11.6. Thread local storage

§ 11.7. Modules and private data

§ 11.8. Examples of assembler code

Chapter 12. Interrupts and hardware exceptions

§ 12.1. Classification of interrupts

§ 12.2. Processor state preservation upon interruption

§ 12.3. Exception Priority

§ 12.4. Interrupt handling

Chapter 13. External interrupts

§ 13.1. Programmable external interrupt controllers

§ 13.2. Built-in interrupt controller

§ 13.3. Handling external interrupts

§ 13.4. Handling local interrupts

§ 13.5. Processor identification and interprocessor messages

Chapter 14. Debugging and monitoring

§ 14.1. Debug Events

§ 14.2. Debug registers

§ 14.3. Monitoring registers

Chapter 15. PAL (Privileged Architecture Library)

§ 15.1. PAL instructions and functions

§ 15.2. PAL replacement

Chapter 16. LLVM backend

§ 16.1. LLVM backend intro

§ 16.2. LLVM backend limitations

§ 16.3. MUSL port

§ 16.4. DOOM port

Chapter 1. Choosing an instruction set

When creating instruction set for existing processor architectures in different years, their architects proceeded from various, often mutually exclusive, goals. Among these goals are the following:

• minimize program size;
• effective use of one or another hardware opportunity;
• compatibility within the family of machines with different performance;
• security of execution;
• built-in support of various constructions from high-level languages;
• optimized loading of pipeline functional units of the processor;
• minimize energy consumption;
• efficient solution to problems of a certain class;
• application for special purposes (embedded solutions);
• Maximum performance in single task mode;
• Maximum overall multitasking throughput.

There are different architectures - the ones far gone in one certain direction, up to explicit conceptualism, and universal, seeking a balance of priorities in different directions. The choice made at the stage of designing the instruction set architecture may subsequently affect the possibility of developing the architecture in one direction or another. Errors in the design of architecture can cut off the possibility of effective implementation of architecture on new technologies due to incorrect prediction of the trend of technological innovation, narrow the scope of architecture, reduce the effectiveness of the application of architecture.

§ 1.1. Bottlenecks issue

The traditional architecture of a programmable computing device is based on the principle of controlling the system by executing a program, which is a sequences of instructions stored in memory. The execution of the instruction consists of a sequence of steps:

• Fetch instructions;
• Decode instructions;
• Read processor state;
• Execute instruction;
• Update processor state and/or memory.

Naturally, processor performance equals the performance of the bottleneck of this system. It doesn't make sense to increase the capabilities of one pipeline stage if problems at other stages are not resolved. Accordingly, several processor bottlenecks arise:

• RAM bandwidth;
• Cache Bandwidth;
• Width (power) of the instruction decoder;
• Number of read ports (register file throughput);
• Number and type of computing devices;
• Number of write ports (register file throughput).

You can immediately say that the bandwidth of RAM is the fatal bottleneck of the processor, and this problem is only removed by increasing the amount of built-in cache.

§ 1.2. Memory non-uniformity problem

At the heart of traditional architecture are two principles that relate to the central element of this – memory architecture. This is the principle of random access to any memory element (uniformity property) and the principle of controlling the system by executing a program, which is a sequences of instructions stored in memory.

However, early computers already got summary registers, and later the counter registers and indexes appeared, stored as close as possible to the calculator. The emergence of architectures with general-purpose registers meant the final division of memory into fast registers and slower RAM. The appearance of registers made it possible to explicitly track, analyze and plan dependencies according to data in the instruction stream, and, if there are no dependencies, execute the instructions at the same time.

The further memory size increase, the computing devices miniaturization, an increased gap between the the memory and the processor speed gave rise to cache memory. Caching removed some of the problems with speed memory operations without changing the programming paradigm. However, more was needed. Cache levels of increasing size. Current computer circuit as follows: a set of specialized computing devices with its own register files relies on a system of logically uniform memory with implicit multi-layer caching.

The architecture of a computer with 16 general-purpose registers is certainly better than the architecture with 8 registers. And architecture with two pipelines of multiplication-addition of floating-point numbers is better than with one pipeline. It might seem that an architecture with 1024 registers and 16 multiplication-addition pipelines would be almost ideal. However, a register file of 1024 registers with 16×4=64 read/write ports would be a technological absurdity. Caching also reached its limit after the advent of four cache level. Further enhancement of parallel data processing capabilities is carried out by creating massively parallel systems with shared memory, which abandoned the property of uniformity of memory, leaving it only for the local memory of one multiprocessor node. But these issues already lie outside the processor architecture of the processor itself.

The new architecture doesn't abolish the traditional architecture based on logically homogeneous memory and doesn't offer a new programming paradigm. The architecture is still based on logically homogeneous RAM. Architectural changes can only affect the model of a computing device with its state explicitly described by internal registers.

§ 1.3. The technologies of parallel operation execution

In addition to the memory non-uniformity, there is another fundamental fact that determines the development of architectures – parallelism of operations. Unlike traditional strictly consistent architecture, modern architectures to achieve maximum performance seek to execute more than one instruction at a time, and more than one operation in one instruction.

The problem of parallel computing is ultimately reduced to the problem of organization consistent simultaneous access of many computing devices to logically homogeneous memory, that is, to the same problem of real memory non-uniformity and insufficient bandwidth. Accordingly, it is the level of parallel memory sharing that determines the parallelization technologies used.

There are several technologies for increasing the degree of parallelism of calculations, depending on the hierarchical level of memory for which they are intended. These technologies are implemented either at the ISA level (instruction set architecture) or at the software level. Here we are more interested in the first case, since we want to evaluate the possibilities of parallel operations due to the correct choice of ISA.

The commercially successful ISA implementation is a compromise between the implementation complexity and each technology benefits. Successful ISA implementation doesn't give preference to any one technology (isn't pure conceptual), but organically and in moderate doses combines several technologies.

SIMD (Single Instruction Multiple Data) are instructions for homogeneous vector operations on elements (8,16,32,64 bits long) of a wide register (64 or 128 bits long). They allow to perform several (2-16) operations in one instruction per cycle. However, software handling of exceptional situations is complicated (where is the error in the vector operation?). The program should contain a sufficient proportion of operations that allow vector execution, and the optimizing compiler must be able to find such operations. When accessing the memory there are problems with data alignment. Implementation of wide ports for reading and writing registers.

Fused instructions are three-operand instructions that combine two binary operations. For example: a = b × c + d. This reduces the total number of instructions and doubles (ideally) the number of computational operations performed per clock cycle (but not machine instructions). This requires a longer execution pipeline, and hence the increase in delays during branches. We need an additional read port for the third operand. The construction of an exception handler is becoming more complicated, since collisions are possible in both the first and second of the fused operations. It takes a place in the instruction to encode the fourth operand. There is a discrepancy in the formats of the computational instructions: binary and ternary formats, which complicates decoding, or you have to artificially convert all binary formats into ternary instructions. The program must contain operations that allow fusing, and the optimizing compiler must be able to find such operations. The percentage of fused operations should be large enough. The total number of possible fused instructions O(N²), where N is the number of basic operations, which is quite large. In practice, it is impossible to fuse all instructions, since the amount of decoding equipment and the place in the instruction allocated for the operation code are limited. Therefore, only some frequently occurring combinations of operations fuse.

Predication is conditional execution of instructions. Any instruction turns into a hardware-executed conditional branch statement. For example: if (a) b = c + d. An additional operand encodes the logical condition register. This technology replaces a control dependency with a data dependency and shifts a possible pipeline shutdown closer to the pipeline end. Most poorly predicted branches in short conditional calculations, and hence pipeline stops, It is eliminated due to the simultaneous execution of instructions from different branches of the conditional statement. However, this is a purely power method, which boils down to simultaneously issuing instructions from several execution branches under different predicates on the pipeline. It takes a place in the instruction to encode the extra operand – predicate register.

Superscalar (super-scalar) execution of instructions. Advantages: Execution of several (1-4) instructions per cycle. Disadvantages: Exception handling becomes more complicated, since the completion of instructions is required strictly in program order. Associative hardware of complexity O(N²) is required to analyze and select N simultaneously executed instructions. We need additional read and write ports, additional pipeline stages.

Out-of-order execution or OOOE is the execution of instructions is not in the manner prescribed by the program, and as the operands are ready, which allows you to bypass structural dependencies according to and do some useful things while waiting for the completion of previous instructions, such as reading from memory. However, the handling of exceptions is complicated, since the completion of instructions is required strictly in software order. Associative hardware of complexity O(N²) is required to analyze and select the next instruction from N buffered instructions. Additional pipeline stages are needed. A register file of sufficient size and equipment for dynamic renaming of registers are required.

VLIW (Very Long Instruction Word) or MIMD (Multiple Instruction Multiple Data) is the execution of instruction packages. Advantages: Execution of several (1-4) instructions per cycle. Disadvantages: Need synchronization – accurate knowledge of delay times for all pipelines and memory, and hence program intolerance when changing the processor model and incompatibility with data caching. Need additional read and write ports. The program must contain operations that allow synchronous execution, and the compiler must be able to find such operations. The increase in the size of the program due to empty slots for which no useful instructions were found.

§ 1.4. Instruction format budget

The program size should be as small as possible. The requirement of code density requires efficient usage of space in the instructions. The question arises about the most advantageous distribution of the bit budget between different types of information in the instruction. The following table shows what the instruction bit budget can be spent on:

A successful ISA implementation is a trade-off between the cost of instruction space and the benefits of using coding techniques. Preference should not be given to any one technique. The instruction set architecture combines different coding techniques at the ISA level.

In a broader sense, there is a question about splitting the workflow into separate instructions. The same sequence of operations can be represented in different ways as a sequence of instructions. The complication of the semantics of instructions makes it possible to increase their length and reduce the number without compromising the overall size of the program, and this, in turn, raises the question of a new redistribution of the bit budget.

However, for high-performance architectures, it's more important not even the size of the code at all, but the efficiency of using the cache for instructions. The cache line contains several instructions and begins with a naturally aligned address. The most effective option is to fetch all the instructions in one cache line starting from the first instruction. Fetches from not the line start require aligners and introduce delays, incomplete fetches use the cache not rationally.

Summarizing the above, we can say that a regular format of instructions is needed, which would shorten the data path without significantly complicating semantics and hardware support for each instruction would be dense enough, but when choosing between code density and caching efficiency would give preference to caching. The format of the instructions should give the scalability of parallel computing devices within a single portable architecture.

It should be noted that the growth in the volume of processed information is significantly ahead of the growth in the program complexity. The relative part of the RAM occupied by the program code is constantly decreasing. Therefore, the problem of minimizing the size of the program is gradually relegated to the background, remaining relevant only for embedded systems.

Pipeline parallel organization of a computing device requires a regular instruction format, that is, the constancy of the length of the portion supplied to the input of the pipeline decoder instructions. This is necessary in order to start decoding the next portion before decoding of instructions from the previous portion is completed.

The regularity of the instruction format means the finiteness of all instructions, the limitation of their length to the length of the decoded portion. However, not all instruction lengths are available for implementation. It should also be possible to determine the start of the next instruction before decoding the current instruction. The instructions must satisfy the conditions for the natural alignment of data in memory, which are constantly growing as memory systems evolve.

The first three rows of the table relate either to the legacy instruction architectures, or to special architectures for embedded applications for which the program size flashed directly into the ROM is more important than performance.

A regular 4-byte format is used by all modern RISC architectures. Now they are completing the cycle of their development, reaching the limits of improving this format. It is hardly worth hoping for significant progress based on new architectures based on this format.

The format of 8-byte instructions is used only on some vector and graphics processors, where there is generally no possibility of access to smaller memory atoms. Its application for general-purpose architecture would mean more than double the size of programs, which is unacceptable.

Chapter 2. Instruction set architecture (ISA)

This chapter provides a basic description of the POSTRISC virtual processor instruction architecture (instruction set architecture or ISA).

§ 2.1. General description of the instruction set

The architecture prefers security over performance. The exploitation of the unplanned program behavior should be avoided by design as possible. We should avoid ambiguous code interpretation. This was done for security reasons to prevent the return-oriented programming attacks like «return to libc» and to make all binary code available for inspection.

The variable-length instruction encoding allows starting execution from the middle of instruction and extracting unplanned instruction sequences. It is possible an alternative interpretations of program code via decoding from the middle of a variable-length instruction. It should be impossible to continue execution from the middle of the instruction. To ensure this, we can use a fixed format or variable-length self-synchronizing format. The POSTRISC chose a fixed format. So the variable-length instructions are forbidden and only fixed instruction encoding with aligned code chunks is allowed.

Some architectures allow placing data inside code, by design or due to the global data addressing limitations. In such architectures, data parts may be placed near a function that uses them or accumulated into bigger «data islands» for several functions. The data in a code section may lead to possible data execution and exploiting the unplanned program behavior. So the strong separation of code and data should be enforced at architecture level, and mixing of code and data in the code section should be prohibited. This also improves paging/caching/TLB.

The instruction set architecture is aimed to the most parallel extraction of instructions from memory and decoding. The format of the instructions is regular (the length of the decoded portion of the code is constant), but not strictly fixed (when all instructions are necessarily the same length), but almost fixed (inside the regular portion, the initial parts of the instructions are the same length, a possible continuation also has a fixed length). The unit of instruction flow is a 16-byte bundle assembled from three (usually) or two instructions. Bundles are always 16-byte aligned in memory.

Unlike traditional systems like VLIW (very long instruction word), the instruction bundling reflects a parallel fetching and decoding process only, but not the process of dispatching, executing, or completing instructions. The instruction bundles do not describe the binding of individual instructions to functional units, the possibility (or necessity) of parallel execution and/or completion, execution timings. The architecture doesn't expose microarchitectural details to software such as load data delays, branch delays, other fixed pipeline delays (pipeline hazards), or fixed set of functional units. This is necessary for programs portability within a family of machines with different microarchitecture/performance. It is assumed that the program can be used without recompilation on machines with different sets of functional units and timings.

Wherever possible, the instruction set tends to be uniform, that is, if some part of the instruction with the same meaning (for example, the number of the first register, the number of the second register, immediate value, etc.) is present in many instructions, then in all those instructions this part is placed at the same position.

Instruction set architecture uses the non-destructive instruction format for any calculation over registers, i.e. the result register is always encoded separately from the operand registers, unlike CISC dual-argument architectures, where the result is forcibly combined with one of the operands. Accordingly, two-argument unary instructions, three-argument binary instructions and four-argument fused instructions (trinary) are valid.

Fighting unpredictable branches or using vector extension requires the introduction of predicates and conditional execution, but to encode an additional predicate argument, each instruction needs extra space. The POSTRISC architecture uses implicit predication via nullification. Each instruction can be overridden to nop by the previous nullification instructions. Instructions are executed conditionally and canceled instructions are considered as non-ops. When we don't use predication, we don't pay for it in instruction bits.

In the new architecture, to reduce the data path, a limited number of frequently encountered combinations of operations are fused (combined in one machine instruction): addition (or subtraction) with a shift; multiplication with addition or subtraction; addition with a constant and memory access (base + displacement addressing mode); register addition (with shift) and memory access (indexed scaled addressing mode); comparison with the branch according to the result of the comparison; change of the cycle counter with comparison and branch according to the result of the comparison, etc. The architecture assumes the true hardware support for fused operations, rather than just compiling the code with hardware breakdown into the original operations.

In architecture, superscalar out-of-order instruction execution equipment can be effectively used. To do this, the instruction set has several limitations. There are no implicit or optional instruction results, no global registers and flags. The number of possible side effects of the instructions is limited. Most instructions have a single register result. Several instructions have two register results. The number of operands is limited to three (and for most instructions, two) registers.

For the POSTRISC instruction architecture, the underlying technology is parallel (super-scalar) out-of-order execution of complex (fused) instructions with implicit predication.

The instruction fetching and decoding will occur sequentially in program order. Out-of-order concurrent execution will be used to process at least one instruction bundle per cycle. The final completion of the instructions with the analysis of exceptions occurs sequentially in a program order.

All operations on integer data occur in general registers, with 2-3 registers of the source operands (there may be a direct meaning or a direct shift) and one register of the result.

All actions on floating-point data occur in general registers, with 1, 2 or 3 registers of the source operands and one register of the result. Floating-point instructions work on single/double/quadruple precision numbers in scalar or packed vector forms.

Many scalar operation codes are complemented by a wide range of vector operations. A special vector extension is used to process multimedia and numerical data in ordinary registers.

The architecture is of type load/store. Memory accesses are limited to load or store instructions that move data between registers and memory, and don't overlap whit using the loaded value. The memory access instructions usually expect strictly one memory access with a single virtual address translation. The unaligned memory accesses are possible, but strict data alignment is preferred.

Global flags and dedicated registers prevent efficient parallel execution of instructions, but duplicating resources and introducing explicit dependencies between instructions also require extra bits to be explicitly described in the instruction. Branch instructions do not use flags but check the values of general registers. The basic operation is the combination of «compare and jump» in one instruction.

To speed up the subroutine calls, to pass arguments through registers, and to reduce the number of memory accesses, a hardware circular buffer of rotated registers is implemented. It also improves code density by minimizing function prologs and epilogues. The second protected stack for rotating registers also protects the contents of all register frames from erroneous changes. The register rotation also complicates the return-oriented programming - there is no known assumption about the correspondence between the physical registers between different function frames.

Optional hints about the frequency and nature of future cache line accesses carried out (if such information is available) in separate instructions.

For immediates encoding there exist different variants with optional compression, interpreting binary values as signed/unsigned, separate sign bit and unsigned value, etc. The POSTRISC uses simple 2-complement binary representation. Each immediate class is defined as signed or unsigned depend on its usage. Base addressing displacements are defined as always signed. Shift amounts are always unsigned. Compare immediates for less/greater are signed or unsigned depend on type. Compare immediates for equal are chosen to be signed.

§ 2.2. Register files

Processor resources include register files, special registers, associative search structures, interrupts. Some resources are available for user programs, others are necessary for the functioning of the operating system. Each processor core has its own set of registers that contain the current state of the core. All registers are divided into register files. There are no registers that are not included in any register file.

It is known that for the usual code, increasing the register file size above 32 has negligible results. But using more registers has a sense for high-performance computing, digital signal processing, accelerating 3D graphics, and game physics. IBM uses the 128x128 SIMD register file in its POWER VMX extension and 64x128 in its POWER VSX extension. Fujitsu uses the 256x128 register file in its SPARC FX HPC-ACE extension. Intel Itanium had 128x82 floating-point registers for HPC.

For the POSTRISC architecture, the 128x128 register file is chosen as a compromise between ordinary usage and special computing purposes.

§ 2.3. Instructions format

Existing RISC architectures have exhausted the possibilities of a fixed 32-bit instruction format. Deep loop unrolling, function inlining, other compiler optimization technologies require more than 32 general-purpose (and floating-point) registers, preferably at least 128. However, increasing the number of registers over 32 with the 32-bit RISC instruction length turned out to be difficult. The three-address format requires at least 3×log₂(128) or 21 bits for register numbers (and a four-address fused instruction even 28 bits).

The decision to separate code and data forces us to support the effective addressing modes to access global/static/const data outside code section. The approach with several instructions (like the high/low offset parts) to access global data seems unfit. But existing 32-bit instructions aren't enough to access the global data from any code position by one instruction. For the biggest known projects, their size is estimated as 150-250 MiB (210 MiB Chromium, 380 MiB Linux kernel «allyesconfig» build, various CADs, etc), which requires offsets with at least 28-30 bit size for future code blow. The POSTRISC supports programs up to 256 MiB with direct access to global data in one instruction.

Some vector processors (like NEC SX Aurora) or video cards use a longer fixed 64-bit format. But this doubles the program size and doesn't justify the possible benefits for the general purpose architecture. There remains the only intermediate format, consistent with the 2ⁿ byte alignment, with 3 instructions for 42 bits (slots), packed in 128-bit bundles. With the 128-bit format we can't transfer control to any instruction in the bundle, except the first, and execute part of the bundle. The bundle is a minimal execution unit. This approach for encoding is similar to Intel IA64 Itanium.

The POSTRISC architecture defines that a 128-bit bundle consists of a 2-bit template and three 42-bit slots. There are two types of instructions: one or two bundle slots length. A bundle may contain three simple one-slot instructions, or a dual-slot instruction and a one-slot (direct order), or a one-slot instruction and a dual-slot (reversed order).

All operation codes are placed in the first slot of double-slot instruction, so the second slot is used for the immediate extensions only. If the instruction format allows expansion to the second slot and the formation of a long instruction, then some immediate fields may have different lengths in short and long formats. For example, simm21(63) means that it is a 21-bit short format field, expandable to 63 bits in a long format.

The splitting of a bundle into instructions is completely determined by a 2-bit template, so that the main and additional instruction codes for different lengths of the instruction format do not overlap. However, they are defined to be always identical. The long instructions are always the extended versions of short instructions with the extended immediates. The following table shows the packaging of the template and instructions into bundles.

The following table shows the instruction formats and the instruction fields lengths in bits for one-slot instructions. The high 7 bits of {35:41} always define the primary operation code (or just opcode) of the instruction. Many instructions also have one or two extended opcode (opx). The remaining bits of the instruction contain one or more fields in various formats.

Formats marked in the table with asterisk (*) allow the instruction continuation to the next bundle slot with the formation of a two-slot instruction. The primary codes of single and dual-slot instructions are the same. The assembled code should directly specify a forced extension of the instruction to the second slot by the additional suffix «.l» (long). The assembler adds dummy nop instructions to the code if the long instruction doesn't fit in the rest of the bundle and need to start a new bundle.

addi    r23, r23, 1234
addi.l  r23, r23, 1234

Notes: Btw, 42-bit slot format is in line with the «Answer to the Ultimate Question of Life, The Universe, and Everything»!

§ 2.4. Instruction addressing modes

The calculation of effective addresses takes place with cyclic rounding modulo 2⁶⁴. Absolute addressing directly in the instructions is missing. Only position independent code (PIC) can be used. Target addresses for addressing executable code can only be calculated relative to the address of the current instruction bundle (instruction pointer ip) or relative to the base addresses in general registers.

The architecture supports 2 modes for ip-relative code addressing:

EA = ip + 16 × sign_extend(disp)

The call/jump offset takes up 28 bits in the instruction slot and allows to encode the branch to a maximum of ±2 GiB in both directions from the current address. If the two-slot instruction is used, the branch distance is maximum ±8 EiB on either side of the current address.

The branch offset takes 17 bits in the instruction slot and allows to encode the branch to a maximum of ±1 MiB in both directions from the current address. If the two-slot instruction is used, the offset takes 30 bits, and the branch distance is ±8 GiB in both directions. The branch condition is encoded by the other parts of the instruction.

The linker, creating the image of the program module, must correctly replace all symbolic links for procedures and global data with offsets, where the symbol is accessed, to the location of the symbol itself. That is, for example, calls to the same static procedure from different places in the program occur with different relative offsets.

The architecture also supports the base-relative instruction addressing. The effective address is computed as a sum of 2 registers aligned to the bundle boundary.

EA = (GR[base] + GR[index]) & mask{63:4}.

§ 2.5. Data addressing modes

Absolute data addressing isn't directly supported. The architecture makes it impossible to put absolute static addresses into the instruction code. Only a position-independent code is available (PIC/PIE). Target absolute addresses can be calculated relative to the address of the current instruction bundle or reserved base registers only. The architecture supports the following data addressing modes:

1. base ip-relative
2. base plus displacement addressing mode or later simply base with offset addressing
3. base plus scaled index addressing mode or later simply scaled indexed addressing
4. base with base immediate pre or post-update

For relative addressing, the immediate unsigned disp field, which is 28 bits or 64 bits for a dual-slot instruction, after unsigned extension, is added to the contents of the instruction pointer to produce a 64-bit effective address. We assume that the program data sections like «.data» or «.rodata» are placing strictly after the code sections like «.text» in the loaded program. The 28-bit immediate value allows to address 256 MiB forward from the current bundle. The dual-slot instructions allow addressing full 64-bit address space.

EA = ip + zero_extend(disp)

For the base plus displacement addressing mode the disp offset, which is 21 bits or 63 bits for a dual-slot instruction, after sign extension, is added to the contents of the base register, to produce a 64-bit effective address. The 21-bit immediate value disp allows addressing ±1 MiB in both directions from the base address.

EA = GR [base] + sign_extend(disp)

For scaled indexed addressing mode, firstly, the contents of the index register is extended according to sm instruction modifier. The sm instruction modifier may be x64 (no extension), u32 (32 bit unsigned), i32 (32 bit signed). Secondly, extended index is shifted left by the scale, then added with a 9-bit signed offset disp (−256…255), and added with the contents of the base register to produce a 64-bit effective address.

EA = GR[base] + (SM(GR[index]) << scale) + sign_extend(disp)

For base with base immediate post-update addressing mode the 10-bit stride immediate is added to base after memory access.

EA = GR[base]

GR[base] = EA + sign_extend(stride)

For base with base immediate pre-update addressing mode the 10-bit stride immediate is added to base before memory access.

EA = GR[base] + sign_extend(stride)

GR[base] = EA

Other addressing methods can be implemented through the above. Absolute addressing of data can be implemented by using any register with a value of 0 as the base. Static data should be aligned to 4-byte boundary, but if not - can be addressed by base+displacement addressing after placing the base address in one of the free registers. The special instruction ldar (load address relative) makes this preparation easier.

ldar base, text_hi (ip_relative_offset)
ldd dst, base, text_lo (ip_relative_offset)

Here ip_relative_offset is the label of the loaded object in the immutable data segment, text_hi is a built-in assembler function for calculating the relative address of the instruction bundle (or aligned 16-byte data portion), text_lo is a built-in assembler function for calculating the displacement within a bundle (portion). Using the ldar instruction, you can address 1 GiB on either side of the current position, or the entire address space, if you use the two-slot version of ldar:

ldar.l base, text_hi (ip_relative_offset)
ldd dst, base, text_lo (ip_relative_offset)

Addressing of private data can be implemented by first placing the correct base address in one of the free registers. Special instruction ldan (load address near) allows to calculate the nearest base address pointing to the middle of the page containing the desired object.

ldan base, gp, data_hi (gp_relative_offset)
ldd dst, base, data_lo (gp_relative_offset)

Here gp_relative_offset is the label of the object in the data segment, data_hi is a built-in assembler function to calculate the older part of the relative offset (relative to gp) to the middle of the data page where the label is located, data_lo is a built-in assembler function to calculate the offset of the label relative to the middle of the page. Using the ldan instruction, you can address 1 GiB of private data (or the entire address space if you use the two-slot version of ldan).

You can also immediately use the dual-slot memory access instructions with addressing 2⁶³ bytes in both directions from the base address.

ldd.l dst, gp, gp_relative_offset

§ 2.6. Special registers

There are several special registers, each 64 bit length. Not all special registers are available for direct access, most are available only for privileged software (at the system level). The table provides information on the purpose of special registers and their availability in protected and privileged mode.

Direct access to special registers can be obtained using instructions mfspr (move from special-purpose register) and mtspr (move to special-purpose register). You can copy the special register to the general register (mfspr), perform the necessary operations, and then put the new value in a special register (mtspr).

Syntax:

mfspr ra, spr
mtspr ra, spr

The special register instruction pointer (ip) stores the address of the end of the bundle containing the currently executing instruction. Or, in other words, the address of the next bundle in the case of sequential execution without branch. The register ip can be read directly via mfspr instruction, but better to get the iprelative address (including those with zero offset) using the ldar/ldafr instruction. The register ip cannot be changed directly (via mtspr instruction), but it automatically increases at the end of the bundle execution, and also receives a new value as a result of the execution of taken branch instructions. Also ip is an implicitly implied operand in a relative branch. Because the instruction format is regular and instruction bundles have a fixed length of 16 bytes and are aligned on a 16-byte boundary. The ip register lower 4 bits are always zero, writing them is ignored.

Special floating-point status/control register (fpcr) designed to control the floating-point unit FPU.

Special registers rsc, rsp are used to control register rotation and flushing the contents of the circular register buffer into memory.

Special registers eip (exception instruction pointer), reip (returnable default exception instruction pointer), ebs (exception bit stack), eca (exception context address) are used to implement almost zero-cost software exceptions (like C++ try/catch/throw).

The 64-bit special processor status register (psr) controls the current core behavior. It is writable only at the most privileged level, its changing requires explicit serialization.

Special registers bsp (bottom stack pointer) stores bottom limit for downward grown stack, which current position is stored in general register sp. The architecture assumes that all not-used stack pages will be premapped as guard pages and might be allocated in any order, it doesn't use pre-touching for allocated stack frames. The bsp should be page-aligned.

Special registers peb (process env block) and teb (thread env block) store read-only user-mode addresses of the associated process and thread data blocks respectively.

Special register interval time counter (itc) is an unsigned 64-bit number for measuring time intervals and synchronization in intervals of the order of nanoseconds. The increase in itc is based on a fixed ratio with the processor frequency. itc increases by one time in N cycles, where N is an integer defined by the implementation, the power of two is from 1 to 32. Applications can directly read itc for time-based computing and performance measurements. itc can only be written at the most privileged level. The OS must ensure that an interrupt from the system timer occurs before itc overflows. For itc, it is not architecturally guaranteed that any other processors in the multiprocessor system will be synchronized with the time interval counters, nor with the system clock. The software must calibrate itc with a valid calendar time and periodically adjust possible drift.

Modifications of itc aren't necessarily synchronized with the instruction thread. Explicit synchronization may be required to ensure that modifications to itc are observed by the subsequent program instructions. The software should take into account the possible spread of errors when reading the interval timer due to various machine stops, such as interrupts, etc.

Special interval timer match register (itm) is a 64-bit unsigned number which contains the future value of itc at which an «interval time match» interrupt will occur.

Special register pta (page table address) controls the hardware address translation and stores root addresss for page table.

Special registers iip, iipa, ipsr save part of the context (state) of the processor upon interruption.

Special registers iva, cause, ifa, iib manage the interrupt table (iva), as well as recognition and processing of interrupts.

Special registers lid, iv, tpr, irr0 - irr3, isr0 - isr3, itcv, tsv, pmv, cmcv are for the embedded programmable interrupt controller and manage external interrupts.

Special registers ibr0-ibr3, dbr0-dbr3, mr-mr7, are for debugging and monitoring facility.

Chapter 3. Basic instruction set

This chapter describes the basic virtual processor instruction set. It is approximately 300 truly machine instructions and 30 pseudo-instructions (assembler instructions that do not have exact machine analogs and are replaced by assembler with other machine instructions, possibly with argument correction). It includes instructions for working with general registers, branch instructions, instructions for working with special registers. It doesn't include privileged instructions, floating-point instructions, multimedia instructions, support instructions for an extended (virtual) memory system.

§ 3.1. Register-register binary instructions

The register-register binary instructions have 3 arguments. The first argument is the result register number, the second and third are the numbers of the operand registers.

Syntax:

INSTRUCTION_NAME ra, rb, rc

The architecture doesn't use bit flags to store comparison results and doesn't use them as implicit operands/results, as, for example, do the architectures Intel X86, SPARC, IBM POWER. The comparison result as a value of 0 or 1 is stored in the general register. In this sense, POSTRISC is similar to MIPS or Alpha architectures. Additionally, to reduce the data path, instructions for determining the minimum/maximum are implemented (comparison and selection in one instruction).

These eight bitwise register-register instructions are enough to implement any binary logic function with a single instruction.

The shift value for the register-register shift instructions is defined as the lower bits of the third register: 5 bits (for 32 bit operations) or 6 bits (for 64-bit operations) or 7 bits (for 128 bit operations). High bits are ignored.

The shift right as division instructions produce a right shift according to the rules for dividing numbers with a sign. First, an arithmetic right shift is performed (with the expansion of the sign bit). If the obtained value is negative, and when shifting to the right, the non-zero bits were forced out (to the left), then the result is corrected (adding a unit). The instruction was introduced to quickly divide signed numbers by 2^shift according to the language rules like C/C++, for dividing negative numbers. With this division, the result is symmetrical with respect to zero, and the remainder can be negative.

§ 3.2. Register-immediate instructions

The register-immediate arithmetic instructions. The first argument is the number of the register of the result, the second is the number of the register-operand, the third is an immediate value of 21 or 63 bit length, sign or zero extended to 64 bits. Instructions of this group allow continuation of the immediate to the next bundle slot with the formation of a dual-slot instruction.

Syntax:

INSTRUCTION_NAME ra, rb, simm
INSTRUCTION NAME ra, rb, imm

For bitwise register-immediate instructions the immediate value is always sign extended. Since it is possible to invert the immediate in advance, 5 instructions are enough instead of 8 for two registers.

§ 3.3. Immediate shift/bitcount instructions

Binary instructions register and immediate shift. Shift or rotation instructions shift the value from the src register for a fixed number of bits in shift. Syntax:

INSTRUCTION_NAME dst, src, shift

Here the first argument is the number of the result register, second argument is the register number, third is the shift/rotate immediate value from 0 to 63.

The instructions cntpop, cntlz, cnttz count the ones/zeros in the interval of shift bits. cntpop – the total number of ones. cntlz – the length of a continuous sequence of zeros from the beginning interval (the most significant bits), or shift + 1 if there are all zeroes. cnttz – The length of a continuous sequence of zeros from the end span (least significant bits), or shift + 1 if there are all zeroes.

The instruction permb (permute bits) reverses the order of bits/bytes in the register according to the immediate mask shift. The mask determines the sequential involvement in the rearrangement of neighbors: bits, pairs of bits, nibbles (four bits), bytes, byte pairs, and four bytes of the original 64-bit value. For example, a maximum mask of 63 (all units) means a permutation of all pairs (a complete inversion of the order of the bits to the reverse as for FFT), mask 1 is only permutation of adjacent bits, mask 32 is permutation of four bytes, mask 32 + 16 + 8 is reverse order of bytes (endianness) in the register, mask 16 + 8 is reverse the byte order in each four bytes in the register.

§ 3.4. Register-register unary instructions

Instruction mov (move register) copies data from one register to another.

Syntax:

mov   ra, rb

§ 3.5. Fused instructions

Fused instructions have more that two input paarameters and can perform two or more actions in one instruction.

mov2    ra,rb,rc,rd

addadd  ra,rb,rc,rd

addsub  ra,rb,rc,rd

subsub  ra,rb,rc,rd

muladd  ra,rb,rc,rd

mulsub  ra,rb,rc,rd

mulsubf ra,rb,rc,rd

mbsel   ra,rb,rc,rd

slp     ra,rb,rc,rd

srp     ra,rb,rc,rd

slsrl   ra,rb,rc,rd

slsra   ra,rb,rc,rd

sladd   ra,rb,rc,shift

slsub   ra,rb,rc,shift

slsubf  ra,rb,rc,shift

srpi    ra,rb,rc,shift

slsrli  ra,rb,shift,count

slsrai  ra,rb,shift,count

deps    ra,rb,shift,count

depc    ra,rb,shift,count

depa    ra,rb,shift,count

dep     ra,rb,rc,shift,pos

rlmi    ra,rb,shift,count,pos

The instruction mov2 (move 2 registers) moves 2 registers. It may be used for register values swapping and just code path reduction.

Fused instructions of the type shift-addition are intended to reduce the critical data path in address calculations. They combine in one machine instruction a left shift (by the number of bits from 0 to 7) with addition (or subtraction). The open question remains about handling overflow during shear with addition that may occur. with intermediate calculations (shift), but no place for the final result.

Pair shift instructions slp (shift left pair), srp (shift right pair) and srpi (shift right pair immediate) shift two registers as a whole to the left (right) by count bits, and puts the lowest part of the integer in the result register. srp takes the count low bits from the second, high bits from the first. The first argument is the result register number, the second and third are the numbers of the pair of shifted operand registers, fourth is register or immediate count from 0 to 63 to indicate the amount of shift. The instruction can be used to implement many useful 64-bit operations: rotation by a fixed number of bits, left or right shift, extraction of a part of the register:

Double shift instructions produce a left and then a right shift (with arithmetic or logical extension). They can be used to extract the bit portion from the register and other manipulations.

The dep (deposit) instruction combines the count the least significant bits from the first operand register and the remaining bits from the second operand register. dep takes high bits from the second, count low bits from the first. The first argument is the number of the register of the result, the second and third are the numbers of the combined registers, the fourth param count is immediate number from 0 to 63 to indicate the portion size of the first merged register.

Direct deposit instructions copy from one register to another with a change in part of the register: deps (deposit set) – insert a unit block, depc (deposit clear) – insert a block of zeros, depa (deposit alter) – invert the block of bits. The block has a length of count bits and is located after the first shift bits. If the value of count+shift is greater than the size of the register (64 bits), ones/zeros bit filling or inversion continues from the beginning of the register. The first argument is the number of the result register, the second is the number of the source operand register, the third and fourth are immediate values shift and count from 0 to 63.

The rlmi instruction extracts a portion of bits of a given length/position from the register and puts it at the specified position in the result register.

§ 3.6. Load/store instructions

The 1st group of the general-purpose register load/store instructions uses the base plus offset addressing mode. The first argument is the number of the loaded (stored) register target, second is the base register number, third is an 21 bits length immediate offset disp. The instructions in this group allow continuation of the immediate value disp in the instruction code for the next slot of the bundle with the formation of a dual-slot instruction (63 bit offset). The offset disp after the sign extension is added to the base register to produce a 64-bit effective address.

EA = gr[base] + sign_extend(disp)

The 2nd group of general-purpose load/store instructions uses the ip-relative addressing. The first argument is the number of the loaded (or stored) register target, second is an unsigned forward offset disp with a length of 28 bits. The instructions in this group allow continuation of the immediate value disp in the instruction code for the next slot of the bundle with the formation of a dual-slot instruction (64 bit offset).

EA = ip + zero_extend(disp)

The 3rd group of general register load/store instructions uses the basic scaled indexed addressing method. The first argument is the number of the loaded or saved register target, second is base register number base, third is index register index, next is shift amount scale, last is short offset disp 9 bits long, sign extended to 64 bits. The instructions in this group allow continuation of the immediate value disp in the instruction code for the next slot of the bundle with the formation of a dual-slot instruction (52 bit offset).

EA = gr[base] + (SM(gr[index]) << scale) + sign_extend(disp)

The 4th group of load/store instructions use base addressing with base updating after usage by the immediate stride. Arguments: target register, base register, signed immediate stride (10 bits). The instructions in this group allow continuation of the immediate value stride in the instruction code for the next slot of the bundle with the formation of a dual-slot instruction (52 bit offset).

For load: (ld[s]Nmia):

EA = gr[base]
tmp = MEM(EA)
gr[base] = gr[base] + sign_extend(stride)
gr[target] = tmp

For store: (stNmia):

EA = gr[base]
MEM(EA) = gr[target]
gr[base] = gr[base] + sign_extend(stride)

The 5th group of load/store instructions use base addressing with base updating before usage by the immediate stride. Arguments are same as for post-update.

For load: (ld[s]Nmib):

EA = gr[base] + sign_extend(stride)
tmp = MEM(EA)
gr[base] = EA
gr[target] = tmp

For store: (stNmib):

EA = gr[base] + sign_extend(stride)
MEM(EA) = gr[target]
gr[base] = EA

The signed immediate disp is added to base to form an effective base. The signed immediate stride (non-zero 11-bit) is added to base to form a new base. For loads, if target is same as base, base update doesn't occurs or loaded value replaces updated base. For stores, if target is same as base, base update occurs after the old value memory storing.

INSN target,base,disp21

INSN target,disp28

INSN target,base,index,scale,disp

INSN target,base,stride

INSN target,base,stride

§ 3.7. Branch instructions

Instructions of the unconditional branch will jump to the effective address. Additionally, the return address can be stored in the general register. Using predication can turn an unconditional jump into a conditional jump.

jmp    label

jmpr   rb,rc

jmpth  rb,rc

jmptw  rb,rc

Branch relative forms is an universal instructions conditional or unconditional static branch or procedure call to a relative address.

Relative branch instructions are generated according to the LDAR rule. After the operation code, there is a register for saving a possible return address, and a 28-bit field for encoding the offset (with a sign) relative to ip. This gives a maximum distance of ±2 GiB in both directions from the current position for a one-slot instruction and all available address space for a long instruction. The jmp instruction allows the continuation of the immediate offset in the instruction code to the next slot of the bundle with the formation of a dual-slot instruction.

ip = ip + 16 × simm

The instruction jmpr (branch register indirect) is used to branch according to the base addresses in the register. The instruction jmpr, when calculating the target address, discards the 4 least significant bits of the result, so that the address always aligned with the beginning of the bundle is always obtained.

ip = (gr[base] + gr[index]) & mask{63: 4}

The jmpth, jmptw (jump table) instructions are intended for organizing table-driven select statements (C language operator switch with continuous distribution of variants, preferably starting from zero). Traditionally, in most architectures, the table-driven switch operator uses table of absolute addresses for storing entry points into the code of options. This table is private for each process (if the loader base code address is different). If the architecture implements the possibility of relative addressing, then the table of absolute addresses can be replaced by a table of relative offsets, shared by all processes, and put it in the read-only data section. The idea is from the HP PA-RISC architecture.

EA = base {2 | 4} × index

EA = mem {2 | 4} [EA]

ip = ip + 16 × EA

.text
; limit = 7
 bdgti  selector, limit, default
 ldafr  base, table
 jmptw  base, selector
label_0:
...
label_1:
...
...
label_7:
...
default:
...
.rodata
table:
dwsecrel (label_0) - secrel (label_0) + 1,
...,
dwsecrel (label_7) - secrel (label_0) + 1

The instructions for the conditional branch calculate the condition and (if the condition is true) jump to the effective address. Traditionally (x86, x64, SPARC), conditional branch is implemented using two instructions – comparison (with the generation of flags of the logical result) and conditional branch (by flags). However, conditional branches are very common in programs. Therefore, POSTRISC uses combined compare and conditional branch instructions to compress code and shorten the critical data path.

bdeq     ra, rb, label

bdne     ra, rb, label

bdlt     ra, rb, label

bdltu    ra, rb, label

bdle     ra, rb, label

bdleu    ra, rb, label

bdgt     ra, rb, label

bdgtu    ra, rb, label

bdge     ra, rb, label

bdgeu    ra, rb, label

bdeqi    ra, simm, label

bdnei    ra, simm, label

bdlti    ra, simm, label

bdgti    ra, simm, label

bdltui   ra, uimm, label

bdgtui   ra, uimm, label

bweq     ra, rb, label

bwne     ra, rb, label

bwlt     ra, rb, label

bwltu    ra, rb, label

bwle     ra, rb, label

bwleu    ra, rb, label

bwgt     ra, rb, label

bwgtu    ra, rb, label

bwge     ra, rb, label

bwgeu    ra, rb, label

bweqi    ra, simm, label

bwnei    ra, simm, label

bwlti    ra, simm, label

bwgti    ra, simm, label

bwltui   ra, uimm, label

bwgtui   ra, uimm, label

bbs      ra, rb, label

bbsi     ra, shift, label

bbc      ra, rb, label

bbci     ra, shift, label

bmall    ra, uimm, label

bmany    ra, uimm, label

bmnone   ra, uimm, label

bmnotall ra, uimm, label

Relative branch instructions are formed according to the rules BRC, BRCI, BRCIU, BBIT. After the operation code, the first compared register, the second compared register (or shift immediate), and a 16-bit field for encoding the offset (with a sign) relative to ip. This gives a maximum distance of ±1 MiB in both directions from the current position. In the case of a long instruction, the maximum distance increases to ±8 GiB on both sides of the current position.

Instructions bgt (blt), bge (ble), bgtu (bltu), bgeu (bleu) are pseudo-instructions with a replacement of the order of the arguments and are reduced to instructions «less».

Relative branch instructions which use immediate. After the operation code, the first compared register, the second compared register (or constant), and a 17-bit field for encoding the offset (with a sign) relative to ip. This gives a maximum distance of ±1 MiB in both directions from the current position. In the case of a long instruction, the maximum distance increases to ±8 GiB on both sides of the current position.

The loop control instructions are for optimization (by shortening the critical execution path) the most common forms of loops with a constant step. Loop control instructions add step (1 or -1) to the loop counter (first argument register) according to loop condition, check the loop continuation condition (compare the counter with the second argument register), and, if the condition is true, make a relative branch to the effective address (label argument).

Syntax:

INSTRUCTION_NAME ra, rb, label

A variant of loop control instructions in which register numbers are the same is a special case. The architecture determined that in this case, in comparison (as the boundary of the counter change) the old register value will participate. This can be used, for example, for branch that occur in the event of an overflow.

A similar style of loop implementation with minimal software management costs found on almost all DSP (digital signal processor) processors. The general purpose processors have limited form (with special register iteration counter) implemented in the IBM PowerPC and Intel Itanium architectures, and universal instructions for general-purpose type add-compare-jump registers are available in the HP PA-RISC architecture (instructions addb, addib), in the DEC VAX architecture (aobleq, aoblss, sobgeq, sobgtr), in the IBM S/390 architecture (brct, bctr, bxle).

§ 3.8. Miscellaneous instructions

Instruction ldi (load immediate) loads a constant into the register (high 64 bits are reset). The first argument of the instruction ldi is the register number of the result, the second is the immediate value 28 bits long (for the short form it sign extended to 64 bits) or full 64 bits (for a dual-slot instruction).

Instruction ldih (load immediate into high 64-bit) loads a constant into the upper part of the 128-bit register (the lower 64 bits remain unchanged). The first argument of the instruction is the result register number, the second is the immediate value 28 bits long (for the short form it sign extended to 64 bits) or full 64 bits (for a dual-slot instruction).

INSTRUCTION_NAME dst, simm

The instruction nop (dummy none operation instruction) intended for the sole purpose is the code alignment to fill in the missing slots in the bundles of instructions, and for the optimal selection of instructions (fetch) from memory.

For example, if necessary, insert a label in the code, the compiler should add (if necessary) the last (incomplete) bundle with dummy instructions, and put the first instruction after the label in a new bundle (since the branch is possible only at the beginning of the bundle). Or, for example, various implementations can gain performance gains, if the destination address of the frequently performed jump is aligned on the 32/64/128-byte boundary (not just the beginning of the bundle, but the beginning of the cache line).

This instruction should not be used for any other purpose. The architecture doesn't contain software delays when loading data (load delays), conditional branch (branch delays), pipeline delays (pipeline hazards).

The nop instruction is processed at the sampling stage, but may not be fed to the next stages of the pipeline (issue), retire and never cause an interrupt (detect stage) itself. This instruction has no dependencies on either reading or writing.

The nop instruction is automatically added by the assembler to populate incomplete instruction bundle, if necessary, place the next instruction in a new bundle (in the case of a tag or a long instruction). The instruction has one immediate argument (unused).

Undefined instruction codes are reserved, and can be used for future extensions (new instructions). But one instruction undef is specially defined forever as reserved. It can automatically be added by assembler to fill in an incomplete bundle of instructions. after instructions to unconditionally jump, call a function, or return from a function. It is also used to fill the tail of code segments. The instruction has one immediate argument (unused).

Chapter 4. The software exceptions support

Software exceptions are for C++-like throw/try/catch exceptions and for more common SEH-like exceptions. The POSTRISC is planned to support deterministic exception handling via frame-based unwinding with sufficient hardware support. The really zero-cost for exception usage is expected for no-exception cases and fast unwinding for exception cases.

The 128-bit link register r0 preserves 18-bit eip offset, which allow alternate return point in case of exception. The exception landing pad address should be after current return address no further than 4 MiB offset. The return instructions may jump to usual return address or to the landing pad depending on exception state.

alternate_retaddr = retaddr + 16 × ZEXT(eip_offset)

§ 4.1. Program state for exception

Special register eip always holds the address of next proper part of unwinding code. This register is automatically restored during normal subroutine return. It's modified during object construction and destruction. Special register eca holds the throwing value (usually the address of throwing object).

Two return address will be saved to link register during subroutine call: for normal return and for exception return. Because registers are 128 bits long, it's enough place for both. But because we need store also frameinfo and previous future vector, exception return address is stored as an positive offset from normal return address. Exception landing pad should be after function body near 4MiB.

So we don't need to return some optional pair (normal return value and optional exception info), and always do the check after each call for possible software exception. Excepted subroutine finally return directly to the proper next part of unwinding code.

The instruction ehthrow sets special register eca to the value (gr[src] + simm21). Usually it should be the address of exception context. This triggers execution to jump to eip address.

The instruction ehadj should be called after the successful construction of the object which requires destruction. It checks the current eca context and jumps to current eip if exception is set. Otherwize, it adjusts eip register to the new actual unwinding code address and continues normally to the next instruction.

The instruction ehcatch copys the exception context eca to general register, clears eca, and adjust new eip value to ip+offset×16.

The instruction ehcatch should be called before the catch block or before the object destructor. For the catch block it adjusts eip register to the end of catch block. Before object destructor it should adjusts eip register to the position after destructor.

The instruction ehnext should be called after the object destructor. It restores exception context saved in ehcatch before destructor call and checks for possible double exception fault. If it is the second software exception at the time of unwinding first software exception, then hardware exception occurs. Otherwise, if it is normal destructor call during unwinding first software exception, execution continues to new eip address. Otherwise, if it is normal destructor call without any unwinding, execution continues to next instruction.

Chapter 5. The register stack

§ 5.1. Registers rotation

Traditionally (in most architectures) the register file is a global resource, where all registers are visible to all program procedures. If the procedure wants to use a register, the contents of this register must be stored in memory, and later restored from memory. The work of saving/restoring registers is usually divided between the procedure that makes the call (caller) and the one that is called (callee). For example, the first 14 registers out of 32 existing may be required to save caller, then the remaining 18 registers must save callee. The optimal split depends on the processor architecture: the number of registers and their universality (orthogonality), and for new architectures it is usually determined experimentally by comparing the code effectiveness for different variants, based on the analysis of a statistically large codebase.

Within one procedure, you can optimize the use of registers well, but in the case of several procedures, and especially if they are compiled separately, the use of register resources becomes suboptimal. A typical example of extreme inefficiency is recursive procedures. Even if the recursive procedure uses only one of the N available registers, each recursive call to such a procedure wants to use exactly this specific register, therefore, this register is repeatedly spilled/filled, despite the presence of many unused registers.

Summing up these arguments, we can say that a significant percentage of all memory accesses are the operations of spilling/filling registers, which in essence are not related to useful work. This fraction is not very dependent on the total number of registers due to the binding of the procedure code to specific registers. So an increase in the number of registers, although it helps to improve the efficiency of large and complex procedures, doesn't help in any way to reduce inter-procedure save and restore registers. This proportion grows with an increase in the number of procedures and a decrease in their average size (as is usually the case for object-oriented programming languages).

The solution to this problem is to implement hardware registers rotation. The registers is no more global resource. Each procedure called gets its own working subset of registers. The registers saving/restoring is not required while the registers working set of several called procedures fits in the register file.

For example, in the POSTRISC architecture, a file of 128 general-purpose registers is divided into two subsets: up to 120 rotable or stackable registers r0 - r119 (locally visible only to the current procedure) and 8 static registers g0 - g4, tp, sp, gz (globally visible to all procedures). The mechanism of the register stack is implemented through the circular renaming of registers as a side effect of procedure calls and returns from procedures. The renaming mechanism is not visible to the program. There 128 rotate registers in the hardware circular buffer, which allows an easy way to cyclically calculate the remainder. In total, the general-purpose logical file of registers has 136 (128 + 8) registers, of which up to 128 maximum are simultaneously available to the program.

Static registers must be maintained and restored at the procedure boundary in accordance with programmatic conventions (APIs). Stackable registers are automatically saved and restored by the corresponding hardware mechanism without the explicit participation of the program. All other register files are visible for all procedures and must be saved/restored programmatically in accordance with program agreements.

The above diagram shows the process of using the hardware buffer of local rotate registers. Five procedures A, B, C, D, E call each other, pass call arguments through the register buffer, place their local variables in the buffer. As the hardware circular buffer is exhausted (in procedure D), the registers are flushed onto the stack in memory and the buffer is reused from the beginning. Of course, not the entire buffer is discarded, but the necessary count to create a new frame.

In general, the register buffer contains the following five parts (order matters):

Each procedure «sees» only its local registers, and the first physical local register is visible under the logical number r0.

The diagram below shows an example of working with the register stack. First, we have a register frame for the current function of 17 registers (r0 - r16). The last 5 of them (r12 - r16) the function uses to place the parameters for calling the next function. The return address when calling will fall into the first register parameter (r12), as well as the number of stored registers and output frame size (12, 5) - these two numbers can be packed together with return address in link register. This register number for the return address, as the boundary between the stored registers and the output parameters, is indicated in the call instructions.

After the call, the second function has at its disposal a register frame of 5 registers. The return address is visible in the register r0. Then the second function expands its register frame to the required number of registers for local computing (up to 10 registers).

After completion of work, the second function restores the saved part of the frame of the first function, and gives the parameter registers back to it. The number of registers to be returned is indicated in the instructions for returning from the function, and, according to ABI, it must match the number of incoming parameter registers.

special register register stack control (rsc) stores information about the status of the circular register buffer, and the current active frame of local general purpose registers.

Four fields hidden from direct access store the positions and sizes of register portions local to the rotation buffer. Their sizes depend on the implementation (register ring buffer size), except for sof whose size is always 7 bits. So, for example, for a buffer of 128 registers, the number of bits for each position is 7, for 256 is 8. Field sof (size of frame) is the size of the last active frame (possibly empty), Field bof (bottom of frame) is the position in the buffer of the beginning of the last active frame and border with the dirty section, Field soc (size of clean) is the size of the clean section, The ndirty field is the number of dirty registries.

The special register stack pointer (rsp) contains the memory address, where the next local register should be saved when the hardware circular register buffer is full. Since the address must be aligned on an 16-byte register size boundary for register spilling/filling, then the lower 4 bits of the register rsp are always zero, the writing them is ignored. A specific architecture implementation can spill/fill the registers in aligned groups of 2-16 registers at a time to optimize the work with memory, so the additional least significant bits of the register may be fixed as zero.

In the Berkeley RISC research project, where register rotation was first applied (?), only eight of the 64 existing registers were visible to the program. A full set of 64 registers is called the register file, and a portion of eight – register window. The file allows up to eight procedure calls with their own sets of registers. Until the program calls a chain longer than eight calls, the registers never had to be stored in RAM, which is scary slow compared to register access. For many programs, a chain of six calls is enough.

A direct descendant of the RISC Berkeley project is Sun Microsystems' SPARC (UltraSPARC) architecture. Compared to the prototype, this processor provides the simultaneous visibility of four sets of eight registers each (has 32 simultaneously visible registers). Of these, 8 are global and 24 are windowed. Three sets, eight registers each, are implemented as a «register window». The eight registers i0…i7 are input to the current procedure, eight registers l0…l7 are local to the procedure of the current level, and eight registers o0…o7 are the output for calling the next level procedure. When a new procedure is called, the register window shifts to sixteen registers, hiding old input registers and old local registers, and making the output registers of the current procedure the input registers of the new procedure. Additionally, eight registers g0…g7 are globally visible to procedures at all levels.

The size of the frame and the number of output registers, unfortunately, are fixed in SPARC. It's also bad that flashing registers pushed from the stack into memory is implemented through interrupts, and the fact that the dumping place is not separated from the regular stack of automatic objects.

In the AMD 29000 architecture (64 global and 128 window visible registers), the register rotation design was further refined with variable-sized windows, which helps resource utilization in the general case, when fewer than eight registers are needed to call the procedure. A second separate stack for saving registers was also implemented.

Register rotation was used in the architecture of Intel 80960 (i960) processors for embedded applications (32 visible registers, of which 16 global and 16 windowed, with a fixed rotation step of 16 registers).

The last (of implemented) known processor that uses register rotation is Intel Itanium (IA64 architecture). It has 128 registers, of which 32 are static and 96 are windowed. It is possible to set a frame of any size from 0 to 96 registers with any number of output registers. To spill registers into memory without processor interrupting, an asynchronous hardware mechanism is implemented. The spill occurs on a separate (second) stack, which grows towards the main stack and is not visible to the user program explicitly. Both stacks share the same memory array.

The rotation of the registers is also applied in the new architecture of the educational processor MMIX, which replaced the legacy MIX processor in examples for new editions of Donald Knuth's book «The Art of Programming». MMIX architecture has a register file of 256 registers visible to the program, allows using the variable window size of visible registers, and even allows to change the boundary between the global and rotate registers visible to the program dynamically, which is usually not used in real architectures.

§ 5.2. Call/return instructions

Because the POSTRISC architecture uses hardware register rotation, then the call/return instructions execution is closely related to the operation of the circular buffer of local registers. When the procedure is called, the current frame of local registers is partially saved, when returning from the procedure, the previous frame is restored.

The POSTRISC may be extended in the future by big-SIMD facilities (256 or even 512 bit) using register pairs/groups for SIMD. Such SIMD register pairs/groups shouldn't cross a register frame boundary. The register frame base (bottom of frame) and the preserved frame size should be a multiple of register pair/group (2 or 4) to guarantee SIMD register pairs/groups alignment. The link info may be stored only in the even (or multiple 4) register to guarantee register pairs alignment. Currently, only 2-register alignment is required for frame size.

Procedure call instructions callr, callri, callmi, callmrw, callplt perform similar actions. They vary by way of computing the target call address only.

The first argument for all call instructions is the register in which the return address and other link info will be stored. All local registers starting from r0 with lower numbers up to it exclusively will be hidden after the register window rotation. All local registers, starting from the register specified in the instructions and with greater numbers, that are currently allocated will become the initial frame of the new procedure.

Then, the branch effective address is calculated (differently for different instructions). The return address along with the current frame info is stored in the return register.

Then the register window is rotated, the frame of local registers is partially saved, and the branch to the target address is performed. The new procedure always sees its return address and previous frame info in the first rotated register r0, and the input parameters in the following registers r1, r2 ...

If the call instruction is the last in the bundle, call instruction saves the return address as a pointer to the next bundle after the current bundle, and and the stored slot number ri is set to zero. If the call instruction isn't the last in the bundle, then the current bundle address and the next slot number ri were saved.

In the general case, return to middle of bundle may be less optimal but saves code size. The processor anyhow fetch and execute whole bundle, but nullifies execution of first ri instructions. For better performance, the bundle before call instruction may be filled with dummy nop instructions to shift call instruction to the end of bundle. There is corresponding compiler command line params to choose between «dense» and «aligned» calls.

For example, dense calls:

ldi %r33, 1234    ; r33 is future r1 (param for myfunc)
callr %r32, myfunc    ; r32 is future r0 (link info)
callr %r32, myfunc2
callr %r32, myfunc3

For example, aligned call:

ldi %r33, 1234    ; r33 is future r1 (param for myfunc)
nop   0
callr %r32, myfunc    ; r32 is future r0 (link info)
; this is next bundle and aligned return address
add %r34, %r12, %r12    ; next instruction after return from myfunc
sub %r14, %r22, %r11

callr   dst,label

callri  dst,base,index

callmi  dst,base,disp11

callmrw dst,base,disp11

callplt dst,uimm28

alloc   framesize

allocsp framesize,uimm21

ret

retf    uimm21

The instruction callr (call relative) makes a procedure call using ip-relative addressing using 28-bit immediate signed offset. This gives the maximum distance of the ±2 GiB to both sides of the current position for a one-word instruction. A long form of instruction is also implemented.

EA = ip + 16 × simm

call (EA)

Instruction callri (call register indirect) is the address of the procedure call from the register. The branch address is calculated as base plus index. The callri instruction discards the 4 least significant bits of the address, so the call address is always aligned at the beginning of the bundle.

EA = (gr[base] + gr[index]) & mask {63:4},

call (EA)

The instruction callmi (call memory indirect) takes the callee address from memory using base+displacement addressing. The instruction discards the 4 least significant bits of the loaded value, so that the address always aligned with the beginning of the bundle is always obtained. The instruction is intended to load from address table with aditional checks for finalized state of virtual page. The vtables should be relocated by linker and set as finalized to disable future access rights changes (hardware-assisted one way relro). The 10-bit displacement is enough to support vtables (or other function pointer tables) with up to 1024 items.

EA = gr[base] + sign_extend(simm10)

EA = mem8 (EA)

EA = EA & mask {63:4},

call (EA)

The instruction callmrw (call memory indirect relative word) takes the callee relative offset from memory using base+displacement addressing. This offset is used to compute callee address relative to base address. The instruction discards the 4 least significant bits of the loaded value, so that the address always aligned with the beginning of the bundle is always obtained. The instruction is intended to load from address table with aditional checks for finalized state of virtual page. The vtables should be relocated by linker and set as finalized to disable future access rights changes (hardware-assisted one way relro). The 10-bit displacement is enough to support vtables (or other function pointer tables) with up to 1024 items.

EA = gr[base] + sign_extend(simm10)

offset = mem4(EA)

EA = (base + offset) & mask {63:4},

call (EA)

The callplt instruction (call procedure linkage table) takes the address of the call from memory using ip-relative addressing. The instruction discards the 4 least significant bits of the loaded value, so that the address always aligned with the beginning of the bundle is always obtained. The instruction is intended to load from address table with aditional checks for finalized state of virtual page. The import tables should be relocated by linker and set as finalized to disable future access rights changes (hardware-assisted one way relro).

EA = ip + zero_extend(uimm28)

EA = mem8 (EA)

EA = EA & mask {63:4},

call (EA)

The ret and retf instructions (return from subroutine) is used to return control from the procedure. It also restores the caller procedure register window state, and retf roll-back fixed-size stack frame.

Unlike other branch instructions, these instructions may use special hardware structures to predict the destination branch address. If the prediction array branch target buffer is generally used for branch address prediction, then for ret instructions it can be additionally (for better prediction accuracy) implemented hardware branch target stack as a short stack of saved return addresses.

While restoring the previous frame state the ret instructions may load part or all of the previous frame from memory if necessary (when the circular hardware register buffer overflows). Instruction may return control until a complete recovery from memory is completed, but the architecture guarantees that attempts to use not yet recovered from memory local registers in the subsequent instructions will be delayed until recovery is performed (via the scoreboard mechanism of the registers).

The link register is implicit argument for both ret instructions. It is the first current function local register and provides the return address and the previous frame info. The argument for retf is the displacement which is used for the optional stack rollback (maybe be 0). The instruction may cause an error if link register contains a broken frame info and there is no place in the local registers for the outgoing and preserved frame parts of the previous procedure since the maximum frame size is 120 registers.

§ 5.3. Register frame allocation

Each callee procedure after call obtains the remaining frame part of the calling procedure starting from the link register(the parameters and maybe slightly more). If callee wants to increase the size of its register frame it should use the alloc (allocate register stack frame) instruction. The first parameter of the instruction is local register, which will be the last in the frame of our procedure (from r0 to r119).

If there is not enough free space in the rotate registers hardware buffer to accommodate a new frame, the alloc instruction flushes registers from the previous functions frames onto the register stack in memory. The instruction can return control before a complete flush is completed, but the architecture guarantees that attempts by the subsequent instructions to use local registers not yet flushed to the stack will be delayed until the flush (through the scoreboard mechanism of the registers).

The new eip is set up from reip. The reip should point to simple universal function epilog with just ret instruction. This epilog should live in the highest corresponding usermode/kernel region. The reip should be set up during thread start.

The next minimum program for a virtual processor demonstrates the use of the callr, alloc and ret instructions.

.text
; at the beginning of the program, the register stack is empty
alloc  54   ; expand frame to 54 registers
ehadj  endfunc
ldi    %r47, 1  ; will be saved when called
ldi    %r53, 3  ; first argument
ldi    %r52, 2  ; second argument
ldi    %r51, 1  ; third argument
; func procedure call, all registers up to 50 will be saved,
; return address, eip, frame size (50) are saved in r50
callr  %r50, func
; at this point, after returning, the frame will be again 54
halt
func:
; at the starting point, the func procedure has a 4-register frame
; their previous numbers are 50, 51, 52, 53, new - 0, 1, 2, 3
; extend the frame to 10 registers (plus regs 4,5,6,7,8,9)
alloc  10
write  "r0 = %x128(r0)"    ; print packed return info
write  "r1 = %i64(r1)"    ; print 1st argument
write  "r2 = %i64(r2)"    ; print 2nd argument
write  "r3 = %i64(r3)"    ; print 3rd argument
ret
endfunc:
.end

Result of execution:

r0 = 000000010000c232_fffffffff1230020
r1 = 1
r2 = 2
r3 = 3

Here: 0xfffffffff1230020 - return bundle address, 0x0000c232 - packed: previous frame size (50 registers), and output frame size (3 parameters and link), offset between return address and previous eip exception return address (endfunc label). 0x00000001 - previous future mask, nonzero because callr is a middle from 3 instructions in the bundle, so we return to the bundle middle and skip one instruction.

The instruction allocsp is introduced for code compression. Its function similar to alloc, but additionally it push usual stack. The allocsp adiust sp down by immediate size.

alloc    framesize
allocsp  framesize, uimm21

§ 5.4. The function prolog/epilog

The type of prolog/epilog depend on:

• if instructions inside function may generate software/hardware exceptions
• if function need to allocate local registers
• if function need to allocate fixed-size stack frame
• if function need to allocate fixed-size stack frame more than pagesize
• if function need to extend stack frame with variable size (using variable length arrays or alloca function)

In the examples below r1…r5 are arguments, and r6…r10 are optional local registers. The frame stack grows from up to down addresses.

The simplest function which doesn't allocate local registers (uses arguments only) and doesn't allocate stack frame. All instructions inside function don't generate software/hardware exceptions (never touch memory, divide, etc). Then it's enough just:

insn    # can't fail, can use only args r1..r5
...
insn    # can't fail, can use only args r1..r5
ret

The next function can generate software/hardware exceptions but doesn't allocate local registers (uses arguments only) and doesn't allocate stack frame. Here in case of exception control can be transferred to eip, so we need proper eip before execution.

The special register reip is introduced to not blow code with multiple copies of standard universal epilog which consists from only ret instruction. It stores the address of such epilog. The proper initialization of reip to avalable standard universal epilog is at runtime at thread start.

Each call instruction setup eip by reip copy, so we won't worry about proper eip just after call. So even if instructions may fail, we don't need additional setup at function start.

insn    # can fail, can use only args r1..r5
...
insn    # can fail, can use only args r1..r5
ret

The next function doesn't allocate stack frame but allocate local registers. The alloc instruction here does the local registers allocation. The register allocation may trigger register spilling to memory so may fail and trigger hardware exception. But again, because eip stores the copy of reip, we won't worry about eip.

alloc   11
insn    # can fail, can use r1..r5 and r6..r10
...
ret

The next function allocates local registers and allocates the fixed-size stack frame. In this case we need to set new eip before execution to the label before return for proper traditional stack unwinding. The stack frame should be no bigger than pagesize, so we don't touch next page after the stack guard page.

std     %gz, %sp, -frame_size_immediate # touch new stack frame
allocsp 11, frame_size_immediate
ehadj   before_return   # immediately after allocsp
...
insn    # can fail, can use r1..r10
ldwz    %r7, %sp, +offset # using sp for local frame addressing
...
before_return:
addi    %sp, %sp, frame_size_immediate
ret

The next function allocates local registers and allocates the fixed-size stack frame. The stack frame is bigger than pagesize so proper guard-page extension via store probing is required.

# guard page probing for frame size bigger than pagesize
std     %gz, %sp, -page_size * 1
std     %gz, %sp, -page_size * 2
...
std     %gz, %sp, -page_size * n
# allocation only after probing
allocsp 11, frame_size_immediate
ehadj   before_return   # immediately after allocsp
...
insn    # can fail, can use r1..r10
ldwz    %r7, %sp, +offset # using sp for local frame addressing
...
before_return:
addi    %sp, %sp, frame_size_immediate
ret

The before_return block:

...
before_return:
addi    %sp, %sp, frame_size_immediate
ret

may be changed to one retf instruction:

...
before_return:
retf    frame_size_immediate

and, if there is a space in previous bundle, then retf may be copied into it, and before_return block may be potentially amortized once for several functions with same frame size:

...
retf    frame_size_immediate
before_return:
retf    frame_size_immediate

The next function allocates local registers and allocates stack frame with variable size (uses variable length arrays or alloca function) possibly with initial size more than pagesize. In this case we have 2 rollback points: for the case of failure in local register alocation, and for the case of failure in initial stack alocation. The sp can't be used for access local stack frame (because of variable frame size), so some local temp register is used to save/restore old sp value (r6 in example) with negative offsets.

# optional guard page probing for frame size bigger than pagesize
std    %gz, %sp, -page_size * 1
std    %gz, %sp, -page_size * 2
...
std     %gz, %sp, -page_size * n
# allocation only after probing, r6 is allocated on the fly
allocsp 11, initial_frame_size_immediate
addi    %r6, %sp, initial_frame_size_immediate
ehadj   before_return   # immediately after saving fp in r6
...
insn    # can fail, can use r1..r10
ldwz    %r7, %r6, -offset # using r6 for local frame addressing

# alloca or VLA
# optional guard page probing for big frame size
std    %gz, %sp, -page_size * 1    
std    %gz, %sp, -page_size * 2
...
std    %gz, %sp, -page_size * m
# allocation only after probing
sub    %sp, %sp, additional_frame_size
# end of alloca or VLA

stw    %r7, %r6, -offset # using r6 for local frame addressing
...
before_return:
mov    %sp, %r6
ret

§ 5.5. The register stack system management

One alloc instruction, along with instructions for calling procedures and returning control, in principle, it is enough for user programs to handle the register stack. But for system programs that handle interrupt processing, returning from an interrupt, context switching, initialization of the register stack, some more instructions are needed.

Instruction without parameters rscover (register stack cover frame) is used, to put the last (active) frame of the register stack into the dirty state (registers belonging to inactive procedure frames). After executing this instruction, the size of the active frame of the local registers is zero. This instruction prepares the register stack for subsequent disconnection or switching.

Instruction without parameters rsflush (register stack flush) used to flush all inactive frames of the register stack into memory (transfer from the dirty state to the clean state). After executing this instruction, the register stack can be disabled without fear of data loss.

Instruction without parameters rsload (register stack load) used to load from memory the last inactive frame of the register stack and be ready to activate it. After executing this instruction, the register stack is ready to work (a group of clean registers appears in it).

§ 5.6. Calling convention

ABI defines a standard relationship function relationship, namely stack frame location, using registers, passing parameters.

The standard function call convention applies only to global functions. Local functions (not available from other object files) may be used by other agreement unless it prevents the correct recovery after an exception.

Convention about the use of registers in standard function calls divides all the global registers available to the program into two categories: saved (preserved) and non-saved (scratch) registers.

preserved registers are guaranteed to be saved when the procedure is called. The called procedure (callee) guarantees the safety of the contents of such a register with a normal return from it. She either doesn't touch this register, or saves it contents somewhere and restores before returning.

Unsaved (scratch) registers may not be saved when a procedure is called. The calling procedure (caller) must store the contents of such a register in memory (on the stack) or in another, but persistent register, if it doesn't want to lose its contents when calling callee. The callee function called uses this register for its needs without restriction.

The architecture provides 128 general purpose registers of 128 bits, and several 64/128 bit special purpose registers. General purpose registers are divided into global (static) and rotatable. The following table shows how registers are used.

Static registers g0-g7 must retain their values in the process of accessing the function. Functions that use these registers must save their values before changing, and restore them before returning from the function.

External signals can interrupt the flow of instructions at any time. Functions called during signal processing do not have any special restrictions on their use of registers. In addition, when the signal processing function returns control, the process resumes its work with correctly restored registers. Therefore, programs and compilers are free to use all registers above except reserved for use by the system without fear of signal processing programs that inadvertently change their values.

The operating system provides each thread with its own stack, in which data is placed on both sides. The stack of rotated registers grows from the bottom towards the higher addresses, work with it under the control of the equipment and is not visible to ABI. The usual stack of software local objects grows from top to bottom towards lower addresses. Each frame (frame) corresponds to an activation record of a procedure in a call chain. The stack pointer sp (stack pointer) always points to the first byte after the top of the stack. The stack frame should be aligned at the 16-byte boundary, and should be a multiple of 16 bytes in size.

The last function in the call chain, which itself doesn't call anyone, may not have its own frame. Such functions are called leaf or terminal (in the graph of dependencies between functions). All other functions must have their own stack frame in the dynamic stack. The following figure shows the organization of the stack frame. sp in the figure means the pointer (register r1) of the top of the stack the called function after it has executed the code setting the stack frame.

Stack frame organization

highest address

        + -> Frame header (return address, gp, rsc)
        | Register storage area (aligned on the boundary of 16 bytes)
        | Local variable space (aligned on the boundary of 16 bytes)
sp ---> + - The title of the next frame (sp + 0)

lowest address

The following requirements apply to the stack frame:

• The pointer to the top of the stack should always be aligned on a 16-byte boundary.
• The pointer to the top of the stack should point to the beginning of the most recently placed stack frame – 8-byte number of «return address». The stack should grow down towards lower addresses.
• The first 8-byte number of the stack frame should always point to the previously allocated frame (in the direction of the older addresses) of the stack, except for the first frame of the stack, which must have a null pointer.
• Pointer to the top of the stack, if required, should be reduced by the called function in its prolog and restored before returning.
• Before a function calls another function, it must save the value of the register lp in the storage area for the return address.
• Some space below the stack top may be available as volatile storage (red zone), which is not saved when the function is called. Interrupt routines and any other functions that can be performed without an explicit call should take care to guard this region. If the function doesn't need more stack space than is available in this area, then it doesn't need to have its own stack frame.

The header of the stack frame consists of a pointer to the previous frame (link info), storage areas rsc, lp and gp, resulting in 32 bytes. Link info always contains a pointer to the previous frame in the stack. Before function B refers to another function C, it must save the contents of the communication register received from function A in the storage area lp for the stack frame of function A, and must set its own stack frame.

Except for the header of the stack frame and inserts for alignment at the 16-byte boundary, the function should not allocate space for areas that it doesn't use. If the function doesn't call other functions and doesn't require anything from the rest of the stack frame, then it should not set the stack frame. The parameter saving area follows the stack frame, the register saving area should not contain any inserts.

For machines of the RISC type (where there are many registers) it is generally more efficient to pass arguments to the called functions in the registers (real and general purpose), rather than constructing a list of arguments in memory or pushing them onto the stack. Since all calculations must somehow be performed in registers, then extra memory traffic can be eliminated if the caller can calculate the arguments in the registers and pass them in the same registers of the called function (callee), and she can immediately use them for its calculations. The number of arguments that can be passed in this form is limited by the number of available registers in the processor architecture.

For POSTRISC, up to 16 parameters are passed in general registers and are visible in the callee new frame in registers r1…r16. The caller passes parameters starting from any register. Exact register number on the caller side depend on caller local frame size.

Parameter storage area, which is located at a fixed distance of 32 bytes from the pointer to the top of the stack, reserved in each frame of the stack for use under the argument list. A minimum of 8 double words is always reserved. The size of this area should be sufficient to preserve the longest list of arguments passed to the function if it owns a stack frame. Although not all arguments for a particular call are in storage, consider their list formation in this area, with each argument occupying one or more double words.

If more arguments are passed than are allowed to be stored in registers, the remaining arguments are stored in the parameter storage area. Values passed through the stack are bitwise identical to those that would be placed in registers.

For variable argument lists, the ABI uses the type va_list, which is a pointer to the location in memory of the next parameter. Using the simple va_list type means that variable arguments should always stay in the same location despite the type, so that they can be found at runtime. This ABI defines the location, which is the common registers r8-r18 for the first eight double words and the parameter storage area on the stack for the rest. Alignment requirements, such as for real types, may require so that the va_list pointer is pre-aligned before accessing the value.

The return value of the function. Functions must return type values int, long, long long, enum, short, char, or pointers to any type, in register r1, extended to 64 bits (zeros or sign).

Arrays of characters up to 8 bytes long, or bit strings up to 64 bits long, will be returned in the g8 register, right justified. Structures or joins of any length, and character strings longer than 8 bytes, will be returned in the storage buffer allocated by the caller. The caller passes the address of this buffer as a hidden optional argument.

Functions must return a single real result of type float, double, long double (quadruple) in the r1 register, rounded to the desired precision. Functions must return complex numbers in the registers r1 (real part) and r2 (imaginary part), rounded to the desired accuracy.

Chapter 6. Predication

§ 6.1. Conditional execution of instructions

The architecture defines a model in which the control flow is passed to the next sequential instruction in memory, unless otherwise directed by a jump instruction or interrupt. The architecture requires the program to appear that the processor is executing instructions in the order in which they are located in memory, although in reality the order can be changed inside the processor. The instruction execution model described in this chapter provides a logical representation of the steps involved in executing the instruction. The branch and interrupt sections show how flow control can be changed during program execution.

If the branch direction is incorrectly predicted, the branch instruction causes the pipeline to stop. All speculatively launched instructions are reset from the fetch stage to the stage of writing results – for almost the entire length of the pipeline.

Predication is a conditional execution of instructions. The purpose of conditional execution is to remove badly predicted branches from the program. In this case, any instruction becomes a hardware-executed conditional branch operator. For example:

if (a) b = c + d.

add (a) b = c, d

The optional argument «a» (predicate) sets the logical condition – to execute the instruction or not. This technology replaces a control dependency with a data dependency and shifts a possible pipeline shutdown closer to the pipeline end. All instructions issued with a false value of the predicate are rejected at the completion stage (retire) or earlier (up to the decode stage) without interruptions.

The instruction predication may be explicit or implicit. With explicit predication, each instruction contains an additional argument – a one-bit predicate register, and, accordingly, the architecture contains a file of several predicate registers (16 predicates in the ARM-32 architecture, 64 in Intel-Itanium).

When implicit predication, the architecture contains a special register-mask for storing information about the conditionality of the execution of future instructions. Before executing the instruction, the first bit from this register is taken as its predicate. Then the register is shifted by one bit, while the current bit is lost. The subsequent instruction takes the second bit as the predicate. The register is constantly updated from the other end with «clean» bits corresponding to unconditionally executed instructions.

Some instructions may write data to this register, thereby canceling the unconditional execution of some future instructions according to the bitmask. These are the so-called nullification instructions. For example, using mask 0b10011 containing 3 1-bits, the 3 instructions (1, 2, and 5th) after the nullification instruction will be canceled.

The advantage of conditional execution is the elimination of most branches in short conditional calculations, and hence the pipeline stops. However, this is a purely power method, which boils down to simultaneously issuing instructions from several execution branches under different predicates on the pipeline. In addition, when explicitly predicting, a place in the instruction is required to explicitly encode the optional argument – the predicate register.

Predication is more suitable for short conditional calculations. It makes no sense to apply predication for loops, or conditional statements longer than the gain from the continuous operation of the pipeline without branches. However, it is the only means of removing downtime for poorly predictable branches (for example, a conditional branch depending on unpredictable data).

An implicit predication scheme was chosen for the POSTRISC architecture. This is due to the fact that according to statistics collected for other architectures where there is a predication, approximately 90% of instructions are executed without using predication, so spending several bits for the predicate in each instruction is not profitable. On the other hand, the remaining 10% of the instructions depend on unpredictable data and, without predication, introduce a significant delay in the pipeline operation. Therefore, architecture without predication will also be suboptimal.

The special field psr.future is used to control the nullification of the subsequent instructions. The least significant bit of the register corresponds to the current instruction, other bits correspond to the subsequent instructions. At the end of the instruction, a right shift occurs. In the case of the branch, the future mask is completely cleared, thereby canceling all possible established nullifications.

Based on the condition of nullification (for different instructions consists of 2 registers, or register and shift, or register and immediate value) either the next «n-yes» instructions are nullified or the next «n-no» subsequent instructions (after first block «n-yes» instructions) are nullified in the psr.future.

The following are examples of removing branches from short conditional statements and the corresponding use of nullification. In all cases, the management dependency is converted to data dependence and masking for future instructions. Everywhere it is assumed that the calculation of conditions gives side effects in the form of possible exceptional situations and should occur strictly predictively. If there can be no side effects in the form of exceptional situations, then, naturally, the calculation of a difficult condition can be done without predication and reduce unnecessary manipulations.

if (c1) {x1; }
else {x2; }

c1 c1yes, c1no
x1 (c1no)
x2 (c1yes)

if (c1) {
 x1;
 if (c2) x2;
 else x3;
 x4;
} else {
 x5;
 if (c3) x6;
 else x7;
 x8;
}

c1 c1yes, c1no
x1 (c1no)
c2 c2yes, c2no (c1no)
x2 (c1no, c2no)
x3 (c1no, c2yes)
x4 (c1no)
x5 (c1yes)
c3 c3yes, c3no (c1yes)
x6 (c1yes, c3no)
x7 (c1yes, c3yes)
x8 (c1yes)

if (c1) {x1;
} else if (c2) {x2;
} else if (c3) {x3;
} else {x4;
}

c1 c1yes, c1no
c2 c2yes, c2no (c1yes)
c3 c3yes, c3no (c1yes, c2yes)
x1 (c1yes)
x2 (c2yes)
x3 (c3no)
x4 (c3yes)

if (c1 & & c2) {x1; }
else {x2; }

c1 c1yes, c1no
c2 c2yes, c2no (c1no)
x1 (c1no, c2no)
x2 (c2yes)

if (c1 || c2) {x1;
} else {x2;
}

c1 c1yes, c1no
c2 c2yes, c2no (c1yes)
x1 (c2no)
x2 (c1yes, c2yes)

if (c1 || (c2 & & c3)) {
 x1;
} else {
 x2;
}

c1 (p0) p2, p3
c2 (p3) p4, p5 (unc)
c3 (p4) p2, p3
x1 (p2)
x2 (p3)

if (c1 & & (c2 || c3)) {
 x1;
} else {
 x2;
}

c1 (p0) p2, p3
c2 (p2) p4, p5 (unc)
c3 (p5) p4, p5 (unc)
x1 (p4)
x2 (p3)

§ 6.2. Nullification Instructions

Nullification instructions mark in the special field psr.future the fact that the execution of the subsequent instructions was canceled. Nullification instructions create mask of 1s for nullified instruction for if or else block, and or them with current future mask. Nullification instructions assume that the «if»-block precedes the «else»-block.

Next instructions cancel future instructions depending on the result of comparing two registers.