x86-64の配列・文字列・構造体ループを読む

本記事は講義を目的としています。 例はIntel構文を使い、pointer validity、object lifetime、aliasing、overflowはC/C++境界の契約として別途確認します。

実際のbinaryでは「開始アドレスから一定strideで進み、検査または累積する」ループが頻出する。配列、文字列、構造体配列は同じ骨格を持つが、終了条件とstrideが異なる。

四つの状態を探す

1. base/current pointer
2. index、end pointer、remaining count
3. accumulatorまたは検索結果
4. 終了条件とsignedness

xor eax, eax
xor r8d, r8d
loop_test:
    cmp r8, rdx
    jae loop_done
    add eax, dword ptr [rcx + r8*4]
    inc r8
    jmp loop_test
loop_done:
    ret

rcxはbase、r8はindex、eaxは累積値、unsigned r8 >= rdxが終了条件である。

indexとend pointer

lea rdx, [rdi + rsi*4]
xor eax, eax
cmp rdi, rdx
je done
loop_begin:
    add eax, dword ptr [rdi]
    add rdi, 4
    cmp rdi, rdx
    jne loop_begin
done:
    ret

明示indexがなくても、初期pointer、4バイト増加、end計算から同じ範囲を復元できる。機械語加算はwrapできるが、C/C++のpointer arithmeticは有効object範囲というより狭い契約を持つ。

長さとsentinel

C文字列は0バイトをsentinelにする。

strlen_like:
    mov rax, rcx
scan:
    cmp byte ptr [rax], 0
    je found
    inc rax
    jmp scan
found:
    sub rax, rcx
    ret

最大長がない代わりに、読み取り可能な範囲内へ必ずNULがあるという強い前提が必要である。バイト数、UTF-8 code unit、Unicode code point、grapheme clusterを混同しない。

検索失敗を-1で返す関数の戻り型がsize_tならbit patternはSIZE_MAXになる。callerとcalleeはsigned -1かunsigned最大値かを同じ契約で解釈する必要がある。

構造体のstrideとfield offset

xorps xmm0, xmm0
test rdx, rdx
jz done
loop_begin:
    cmp dword ptr [rcx + 12], 0
    je skip
    addss xmm0, dword ptr [rcx]
skip:
    add rcx, 16
    dec rdx
    jne loop_begin
done:
    ret

offset 12はfield、offset 0はfloat、step 16はsizeofの候補である。現在のbinary layoutの証拠であり、static_assertとcompiler layoutで確認する。

AoSでは一つのbaseにstrideと複数offsetが繰り返され、SoAではfieldごとの独立baseが現れやすい。特定fieldだけ大量処理する場合、layout変更がhandwritten ASMより大きな効果を持つことがある。

unrollとvector tail

loop4:
    add eax, [rcx]
    add eax, [rcx + 4]
    add eax, [rcx + 8]
    add eax, [rcx + 12]
    add rcx, 16
    sub rdx, 4
    jae loop4

machine loop一回が4要素を処理する。通常は0〜3要素のremainderがあるため、長さが4の倍数だと早合点しない。

movdqu xmm0, [rcx]
paddd  xmm1, xmm0

padddは32ビットlane四つであり、128ビット整数一個ではない。vector loopはprologue、main、scalar tailに分かれることが多い。

overlapとsize overflow

memcpyは非overlap、memmoveはoverlap対応、typed loopはさらにlifetime、alignment、aliasing契約を持つ。

bytes = count * sizeof(Item);

この積がwrapして小さなallocationになり、loopは元のcountで進むとheap overflowになる。allocation sizeとloop boundを一緒に監査し、count <= SIZE_MAX / sizeof(Item)を確認する。

チェックリスト

pointerの最小有効範囲、countのbyte/element単位、strideとoffset、index/end/sentinel終了、0個入力、one-past-end、remainder、overlap、size/pointer overflowを確認する。

まとめ

データループはpointer、stride、accumulator、終了条件へ分解する。sentinel loopは明示長の代わりにterminator存在を要求する。本文だけでなく空入力、tail、overlap、単位、overflowまで復元して初めてmemory contractが分かる。

公式資料

• Intel Software Developer's Manual
• AMD64 Programmer's Manual