Your first SIMD loop

A scalar loop that adds two arrays of twenty 32-bit integers runs twenty add instructions, one per element. On a 128-bit SIMDSIMD: Single Instruction, Multiple Data: one instruction that operates on several values at once inside a wide register. The processor divides the register into equal-sized lanes and runs the operation on every lane together. More in “SIMD concepts and CPU feature detection” unit one add covers four 32-bit lanes, so twenty elements take five vector passes; twenty-one take five passes and one scalar step for the leftover, and twenty-two take five and two.

Below, that loop is written in AArch64 Advanced SIMD, and its SSE2, AVX2 and RISC-V V versions are assembled and read back. A vector body does the bulk, a scalar tailloop tail: The leftover iterations of a vector loop that handle fewer elements than one vector pass covers, usually run as a short scalar loop. finishes the rest, and a plain scalar loop checks every result.

A vector loop adds several lanes at once

The NEON vector loopvector loop: A loop body that uses one SIMD instruction to process several lanes of a vector register per pass, in place of several scalar instructions. below adds two int32 arrays into a third. The vector registervector register: A register wider than a general-purpose one that holds several values side by side. A SIMD instruction treats it as a row of equal-sized slots and operates on every slot in parallel. More in “SIMD concepts and CPU feature detection” view v0.4s has four 32-bit lanesA lane is one slot of a vector register; a 4s view treats a 128-bit register as four 32-bit slots., and add v2.4s, v0.4s, v1.4s performs four lane-wise adds in one instruction. The post-index [x1], #16 on ld1 reads 16 bytes and moves x1 forward, so the loop is the familiar count-down with no separate pointer adds:

// A 128-bit NEON int32 add with a scalar tail (AArch64, Apple silicon).
//
// void vadd_neon(int32_t *c, const int32_t *a, const int32_t *b, size_t n)
//   - n / 4 vector passes of 4 int32 lanes each,
//   - then n % 4 scalar passes for the leftover elements.
//
// Mach-O: the exported name needs a leading underscore. AAPCS64 puts pointers in
// x0, x1, x2 and the count in x3; the function clobbers only caller-saved registers,
// so no stack frame is needed.

        .text
        .p2align 2
        .globl  _vadd_neon
_vadd_neon:
        lsr     x4, x3, #2              // x4 = n / 4, the number of full vectors
        cbz     x4, 2f                  // nothing to vectorise: go straight to the tail
1:      ld1     {v0.4s}, [x1], #16      // post-index: load 4 int32s from a, advance by 16
        ld1     {v1.4s}, [x2], #16      // load 4 int32s from b
        add     v2.4s, v0.4s, v1.4s     // lane-wise 32-bit add on 4 lanes at once
        st1     {v2.4s}, [x0], #16      // store the 4 sums and advance c by 16
        subs    x4, x4, #1              // one less vector pass to do
        b.ne    1b
2:      ands    x3, x3, #3              // x3 = n % 4, the leftover count
        b.eq    4f                      // no tail: done
3:      ldr     w5, [x1], #4            // scalar tail: one int32 at a time
        ldr     w6, [x2], #4
        add     w5, w5, w6
        str     w5, [x0], #4
        subs    x3, x3, #1
        b.ne    3b
4:      ret

// Drives vadd_neon for several values of n and checks each result against a plain
// C scalar loop.  Prints one line per n with the vector pass count, the tail count
// and whether the result matched.

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void vadd_neon(int32_t *c, const int32_t *a, const int32_t *b, size_t n);

static void scalar_ref(int32_t *c, const int32_t *a, const int32_t *b, size_t n) {
    for (size_t i = 0; i < n; i++) c[i] = a[i] + b[i];
}

int main(void) {
    static const size_t cases[] = {0, 3, 4, 10, 17};
    enum { MAX = 32 };
    int32_t a[MAX], b[MAX], c[MAX], ref[MAX];

    printf("  n   passes   tail   match\n");
    int all_ok = 1;
    for (size_t k = 0; k < sizeof cases / sizeof cases[0]; k++) {
        size_t n = cases[k];
        for (size_t i = 0; i < n; i++) { a[i] = (int32_t)(i + 1); b[i] = (int32_t)(10 * (i + 1)); }
        // Fill the slots after the last element with -1 and check them after the
        // call, so a store past c[n - 1] makes the row print NO.
        for (size_t i = n; i < MAX; i++) c[i] = -1;
        memset(c, 0, n * sizeof c[0]);
        vadd_neon(c, a, b, n);
        scalar_ref(ref, a, b, n);
        int ok = (memcmp(c, ref, n * sizeof c[0]) == 0);
        for (size_t i = n; i < MAX; i++) if (c[i] != -1) ok = 0;
        printf("%3zu   %5zu   %4zu   %s\n", n, n / 4, n % 4, ok ? "yes" : "NO");
        all_ok &= ok;
    }
    printf("summary: %s on every n\n", all_ok ? "match" : "mismatch");
    return all_ok ? 0 : 1;
}

The vector body runs n / 4 times; when n is not a multiple of four, a short scalar loop adds the rest one element at a time.

import pathlib
import sys

sys.path.insert(0, str(pathlib.Path(__file__).parent / "sessions"))
import session

# Build the NEON vadd with its scalar tail, run it for n = 0, 3, 4, 10 and 17,
# and check each result against a plain C scalar loop.  A row says yes only when
# the n sums match and every slot after them still holds -1.
session.run("""
clang -O1 -o vadd vadd.c neon/vadd.s
./vadd
""")

$ clang -O1 -o vadd vadd.c neon/vadd.s
$ ./vadd
  n   passes   tail   match
  0       0      0   yes
  3       0      3   yes
  4       1      0   yes
 10       2      2   yes
 17       4      1   yes
summary: match on every n

Every row says yes, including n = 0 (zero vector passes, zero tail passes). The driver, vadd.c, also fills the slots past the end with -1 and checks them, so a stray write would print NO.

The scalar tail handles the leftover

The vector body stops when its pass counter reaches zero, and the scalar tail then runs n % 4 times. The match column of the run compares each result with a scalar referencescalar reference: A plain non-SIMD implementation of the same function, used to check a vector routine's output lane by lane against an obviously correct one., a plain C loop over the same inputs.

The step-through follows the recorded n = 10 row: two vector passes, two scalar steps and the comparison with the C loop. A multiple of four needs no scalar step, as the n = 4 row shows, and a length below four needs no vector pass, as n = 3 shows. The function skips a loop whose count is zero, so one body handles every length: cbz x4 jumps over the vector body when n / 4 is 0, and ands with b.eq jumps over the tail when n % 4 is 0.

The same loop on x86-64 and RISC-V

SSE2 is the 128-bit baseline of x86-64. The loop uses movdqu for both loads, paddd for four 32-bit lane-wise adds and another movdqu for the store. An unaligned loadunaligned load: A load from any byte address, with no alignment requirement; its aligned counterpart faults when the address is not a multiple of the operand size. such as movdqu reads any address; its aligned sibling movdqa needs a 16-byte-aligned one and raises a general-protection exceptiongeneral-protection exception: The x86 exception #GP, raised for a protection violation such as an aligned vector instruction like movaps whose memory operand is not on a 16-byte boundary. Linux delivers it to a user program as SIGSEGV. More in “Stack alignment and the crashes it causes” otherwise. Both x86 listings show the vector body only, for a length that fills whole vectors.

AVX2 brings the integer add to the 256-bit ymm registers, so each pass adds eight 32-bit lanes with vpaddd ymm0, ymm0, [rdx], a three-operand VEX form. The loop ends with vzeroupper, which the Intel manual recommends when AVX code meets legacy SSE code, to avoid a false dependency on the upper register halves.

The RISC-V V extension picks a different shape. vsetvli t0, a3, e32, m1, ta, ma asks for 32-bit elements and writes into t0 how many lanes this pass gets. When fewer than a full register of elements remain, t0 is simply smaller, so the same body handles the last pass and no scalar tail exists. The next lesson covers this style for RVV, SVE and SME.

; SSE2 int32 add on 4 lanes per pass (Linux System V AMD64, assembled with NASM).
; void vadd_sse2(int32_t *c, const int32_t *a, const int32_t *b, size_t n), n % 4 == 0.
; System V puts the four arguments in rdi, rsi, rdx and rcx.
;
; The unaligned move movdqu reads 16 bytes from any address.  Its aligned sibling
; movdqa needs a 16-byte-aligned address, or the CPU raises a #GP (SIGSEGV on Linux).
; b is loaded with movdqu too: a legacy SSE paddd with a memory operand would need
; that operand 16-byte aligned.

default rel

section .text
        global  vadd_sse2
vadd_sse2:
        shr     rcx, 2                  ; rcx = n / 4
        jz      .done
.loop:  movdqu  xmm0, [rsi]             ; 4 int32s from a (unaligned load is fine)
        movdqu  xmm1, [rdx]             ; 4 int32s from b
        paddd   xmm0, xmm1              ; lane-wise 32-bit add
        movdqu  [rdi], xmm0             ; store 16 bytes into c
        add     rsi, 16
        add     rdx, 16
        add     rdi, 16
        dec     rcx
        jnz     .loop
.done:  ret

section .note.GNU-stack noalloc noexec nowrite progbits

; AVX2 int32 add on 8 lanes per pass (Linux System V AMD64, assembled with NASM).
; void vadd_avx2(int32_t *c, const int32_t *a, const int32_t *b, size_t n), n % 8 == 0.
;
; AVX uses VEX-encoded instructions on 256-bit ymm registers.  vzeroupper on the way
; out zeroes bits 255..128 of ymm0 to ymm15: the Intel manual recommends it "when
; transitioning between AVX and legacy SSE code" to avoid false dependencies.

default rel

section .text
        global  vadd_avx2
vadd_avx2:
        shr     rcx, 3                  ; rcx = n / 8
        jz      .out
.loop:  vmovdqu ymm0, [rsi]             ; 8 int32s from a
        vpaddd  ymm0, ymm0, [rdx]       ; AVX2 add, three-operand VEX form; b read in place
        vmovdqu [rdi], ymm0             ; 32 bytes into c
        add     rsi, 32
        add     rdx, 32
        add     rdi, 32
        dec     rcx
        jnz     .loop
.out:   vzeroupper
        ret

section .note.GNU-stack noalloc noexec nowrite progbits

// RISC-V V 1.0 strip-mined int32 add (Linux riscv64, assembled with llvm-mc -mattr=+v).
//
// void vadd_rvv(int32_t *c, const int32_t *a, const int32_t *b, size_t n)
//   a0 = c, a1 = a, a2 = b, a3 = n.  LP64D.
//
// vsetvli sets vl, the number of elements this pass gets (never more than VLMAX for
// e32 m1, and exactly the count left once that count is VLMAX or less).  No scalar
// tail is needed: the last pass simply runs over fewer elements.

        .text
        .globl  vadd_rvv
vadd_rvv:
1:      vsetvli t0, a3, e32, m1, ta, ma // t0 = vl for the a3 elements still to do
        vle32.v v0, (a1)                // load t0 int32s from a
        vle32.v v1, (a2)                // load t0 int32s from b
        vadd.vv v2, v0, v1              // lane-wise add on t0 lanes
        vse32.v v2, (a0)                // store t0 int32s into c
        sub     a3, a3, t0              // n -= elements done this pass
        slli    t1, t0, 2               // t1 = t0 * sizeof(int32_t)
        add     a1, a1, t1
        add     a2, a2, t1
        add     a0, a0, t1
        bnez    a3, 1b
        ret

        .section .note.GNU-stack,"",@progbits

import pathlib
import sys

sys.path.insert(0, str(pathlib.Path(__file__).parent / "sessions"))
import session

# Assemble the x86-64 and riscv64 versions of the same vadd as Linux objects and
# read them back with llvm-objdump.  The listings show what the assemblers emitted;
# the functions themselves run only on their own processors.
# Each sed command prints from the function label to the end of the listing.
session.run("""
nasm -f elf64 -o vadd_sse2.o x86/vadd_sse2.asm && echo "SSE2 assembled"
llvm-objdump -d --no-show-raw-insn -M intel vadd_sse2.o | sed -n '/<vadd_sse2>:/,$p'
nasm -f elf64 -o vadd_avx2.o x86/vadd_avx2.asm && echo "AVX2 assembled"
llvm-objdump -d --no-show-raw-insn -M intel vadd_avx2.o | sed -n '/<vadd_avx2>:/,$p'
llvm-mc --triple=riscv64-linux-gnu -mattr=+d,+v -filetype=obj -o vadd_rvv.o riscv/vadd_rvv.s && echo "RVV assembled"
llvm-objdump -d --mattr=+d,+v --no-show-raw-insn vadd_rvv.o | sed -n '/<vadd_rvv>:/,$p'
""")

$ nasm -f elf64 -o vadd_sse2.o x86/vadd_sse2.asm && echo "SSE2 assembled"
SSE2 assembled
$ llvm-objdump -d --no-show-raw-insn -M intel vadd_sse2.o | sed -n '/<vadd_sse2>:/,$p'
0000000000000000 <vadd_sse2>:
       0:      	shr	rcx, 0x2
       4:      	je	0x27 <vadd_sse2.done>

0000000000000006 <vadd_sse2.loop>:
       6:      	movdqu	xmm0, xmmword ptr [rsi]
       a:      	movdqu	xmm1, xmmword ptr [rdx]
       e:      	paddd	xmm0, xmm1
      12:      	movdqu	xmmword ptr [rdi], xmm0
      16:      	add	rsi, 0x10
      1a:      	add	rdx, 0x10
      1e:      	add	rdi, 0x10
      22:      	dec	rcx
      25:      	jne	0x6 <vadd_sse2.loop>

0000000000000027 <vadd_sse2.done>:
      27:      	ret
$ nasm -f elf64 -o vadd_avx2.o x86/vadd_avx2.asm && echo "AVX2 assembled"
AVX2 assembled
$ llvm-objdump -d --no-show-raw-insn -M intel vadd_avx2.o | sed -n '/<vadd_avx2>:/,$p'
0000000000000000 <vadd_avx2>:
       0:      	shr	rcx, 0x3
       4:      	je	0x23 <vadd_avx2.out>

0000000000000006 <vadd_avx2.loop>:
       6:      	vmovdqu	ymm0, ymmword ptr [rsi]
       a:      	vpaddd	ymm0, ymm0, ymmword ptr [rdx]
       e:      	vmovdqu	ymmword ptr [rdi], ymm0
      12:      	add	rsi, 0x20
      16:      	add	rdx, 0x20
      1a:      	add	rdi, 0x20
      1e:      	dec	rcx
      21:      	jne	0x6 <vadd_avx2.loop>

0000000000000023 <vadd_avx2.out>:
      23:      	vzeroupper
      26:      	ret
$ llvm-mc --triple=riscv64-linux-gnu -mattr=+d,+v -filetype=obj -o vadd_rvv.o riscv/vadd_rvv.s && echo "RVV assembled"
RVV assembled
$ llvm-objdump -d --mattr=+d,+v --no-show-raw-insn vadd_rvv.o | sed -n '/<vadd_rvv>:/,$p'
0000000000000000 <vadd_rvv>:
       0:      	vsetvli	t0, a3, e32, m1, ta, ma
       4:      	vle32.v	v0, (a1)
       8:      	vle32.v	v1, (a2)
       c:      	vadd.vv	v2, v0, v1
      10:      	vse32.v	v2, (a0)
      14:      	sub	a3, a3, t0
      18:      	slli	t1, t0, 0x2
      1c:      	add	a1, a1, t1
      20:      	add	a2, a2, t1
      24:      	add	a0, a0, t1
      28:      	bnez	a3, 0x0 <vadd_rvv>
      2c:      	ret

The read-back shows one shape in all three: load a and b, add, store. Four variants change it. A movdqa version is the same length as movdqu but faults on an address that is not a multiple of 16. An overlapping last vector ends exactly at the array end and rewrites a few lanes the body already wrote. Padding every array to a multiple of four lets the vector body run alone. A saturating add such as uqadd on NEON or paddusb on x86 clips an overflow at the type’s maximum.

Practise

Work on a copy of the examples folder and predict before each run.

1. Change the cases list in vadd.c to {1, 2, 7, 8, 31}, predict the passes and tail columns for each n, then run neon_vadd_session.py; every row must still say yes.
2. Replace both movdqu loads in x86/vadd_sse2.asm with movdqa, predict whether the offsets of later instructions move, then run cross_asm_session.py.
3. Delete cbz x4, 2f from neon/vadd.s, work out what subs x4, x4, #1 leaves in x4 when n is 0, then run neon_vadd_session.py: it dies before its first row until the line is back.

Finishing a vector loop safely: tails, overlaps and guard pages Pro: opens with a Pro, Premium or Ultimate pass

SSE2 and AVX2 in depth: the bytes, alignment and vzeroupper Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Why does a 128-bit NEON int32 add need a scalar tail when the array length is not a multiple of four?

Each add v2.4s does four 32-bit lanes at once, so a loop of n / 4 passes finishes when the length is 4k. For a length such as 10 or 17 the last 2 or 1 elements fall outside the last vector pass. If the loop stops there they are simply not written: the output buffer holds whatever was there before the call. The usual fix is a short scalar loop for the remaining n % 4 elements. The next lesson covers predicated instructions that handle the tail inside the vector body.

Three deeper questions in the module’s bank build on this one, with a first step and follow-ups for each:

Key takeaways

• A 128-bit NEON int32 add writes four lanes per instruction, so n int32s take n / 4 vector passes.
• A scalar tail of n % 4 passes handles the leftover elements; the function tests both counts and skips a loop whose count is zero.
• SSE2 keeps the four-lane shape with movdqu and paddd; AVX2 doubles it to eight lanes with vmovdqu and vpaddd and ends with vzeroupper.
• RISC-V V picks the lane count per pass with vsetvli, so the vector loop handles the leftover itself.
• Checking a SIMD routine against a scalar reference, with lengths that leave every remainder from 0 to 3, catches the bugs a reader misses.