Zero-overhead looping

Zero-overhead looping is a feature of some processor instruction sets whose hardware can repeat the body of a loop automatically, rather than requiring software instructions which take up cycles (and therefore time) to do so.[1][2] Zero-overhead loops are common in digital signal processors and some CISC instruction sets.

Background

In many instruction sets, a loop must be implemented by using instructions to increment or decrement a counter, check whether the end of the loop has been reached, and if not jump to the beginning of the loop so it can be repeated. Although this typically only represents around 3–16 bytes of space for each loop, even that small amount could be significant depending on the size of the CPU caches. More significant is that those instructions each take time to execute, time which is not spent doing useful work.

The overhead of such a loop is apparent compared to a completely unrolled loop, in which the body of the loop is duplicated exactly as many times as it will execute. In that case, no space or execution time is wasted on instructions to repeat the body of the loop. However, the duplication caused by loop unrolling can significantly increase code size, and the larger size can even impact execution time due to cache misses. (For this reason, it's common to only partially unroll loops, such as transforming it into a loop which performs the work of four iterations in one step before repeating. This balances the advantages of unrolling with the overhead of repeating the loop.) Moreover, completely unrolling a loop is only possible for a limited number of loops: those whose number of iterations is known at compile time.

For example, the following C code could be compiled and optimized into the following x86 assembly code:

C codeAssembly
unsigned int array[100];
unsigned int i;

for (i = 0; i < 100; i++) {
    array[i] = i;
}

; Set up number of loop iterations.
; Note that the compiler has reversed the loop
; so that it counts backwards from 99 to 0,
; rather than up from 0 to 99.
mov eax, 99

.LABEL:
; array[i] = i
mov DWORD PTR array[0+eax*4], eax

; Decrement i
sub eax, 1

; Check i >= 0. If true, repeat the loop.
jnb .LABEL

Implementation

Processors with zero-overhead looping have machine instructions and registers to automatically repeat one or more instructions. Depending on the instructions available, these may only be suitable for count-controlled loops ("for loops") in which the number of iterations can be calculated in advance, or only for condition-controlled loops ("while loops") such as operations on null-terminated strings.

PIC

In the PIC instruction set, the REPEAT and DO instructions implement zero-overhead loops.[1] REPEAT only repeats a single instruction, while DO repeats a specified number of following instructions.

Blackfin

Blackfin offers two zero-overhead loops.[3] The loops can be nested; if both hardware loops are configured with the same "loop end" address, loop 1 will behave as the inner loop and repeat, and loop 0 will behave as the outer loop and repeat only if loop 1 would not repeat.

Loops are controlled using the LTx and LBx registers (x either 0 to 1) to set the top and bottom of the loop — that is, the first and last instructions to be executed, which can be the same for a loop with only one instruction — and LCx for the loop count. The loop repeats if LCx is nonzero at the end of the loop, in which case LCx is decremented.

The loop registers can be set manually, but this would typically consume 6 bytes to load the registers, and 8–16 bytes to set up the values to be loaded. More common is to use the loop setup instruction (represented in assembly as either LOOP with pseudo-instruction LOOP_BEGIN and LOOP_END, or in a single line as LSETUP), which optionally initializes LCx and sets LTx and LBx to the desired values. This only requires 4–6 bytes, but can only set LTx and LBx within a limited range relative to where the loop setup instruction is located.

P0 = array + 396;
R0 = 100;
LC0 = R0;
LOOP my_loop LC0;   // sets LT0 and LB0

LOOP_BEGIN my_loop;   // pseudo-instruction; generates a label used to compute LT0
// LC0 cannot be written directly to memory,
// so we must use a temporary register.
R0 += -1;   // equally fast and small would be R0 = LC0
[P0--] = R0;
LOOP_END my_loop;   // pseudo-instruction; generates a label used to compute LB0

x86

The x86 assembly language REP prefixes implement zero-overhead loops for a few instructions (namely MOVS/STOS/CMPS/LODS/SCAS).[4] Depending on the prefix and the instruction, the instruction will be repeated a number of times with (E)CX holding the repeat count, or until a match (or non-match) is found with AL/AX/EAX or with DS:[(E)SI]. This can be used to implement some types of searches and operations on null-terminated strings.

References
  1. "Zero Overhead Loops". Retrieved 2020-08-18.
  2. "Understanding Advanced Processor Features Promotes Efficient Coding" (PDF). Analog Devices. Retrieved 2020-08-18.
  3. "Blackfin Processor Programming Reference, Revision 2.2" (PDF). Analog Devices. February 2013. Retrieved 2020-08-18.
  4. "REP/REPE/REPZ/REPNE/REPNZ: Repeat String Operation Prefix (x86 Instruction Set Reference)". c9x.me. Retrieved 2020-08-18.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.