非アライメントアドレスでのメモリコピー

実際にコードを書くときはこういうことを考える(こともある)例として. ここの情報はPentiumの頃のものです. 考え方は使えるとは思いますがペアリング条件は現在のCPUとは異なります.
アラインされている時は4byte転送あたり1clock(以下)ですが, そうでない時はP5で3clock, K6で1clockのペナルティが発生します.
しかし, これはメモリがL1キャッシュにヒットしている時であって普通はもっとかかります. その時は4byte読み込んでシフトして4byte書き込むという方法の方が速いのです.
(例) 『0|1234|5678|9...』を『|0123|4567|89...』と転送する部分を作成する.
(`|'は4の倍数のアドレス境界の意味) 
/**
    dst = 4n, src = 4m+3 の形の時の n byte転送の擬似コード
*/

void memcpy1(char *dst, const char *src, int n)
{
    unsigned int *psrc, *dst, temp1;
    int i;

    psrc = (int *)(src-3);
    pdst = (int *)dst;
    temp2 = *psrc++;

    for (i = 0; i < (n-1)/4; i++) {
        temp1 = *psrc++;
        *pdst++ = (temp1 << 8) | (temp2 >> 24);
        temp2 = temp1;
    }
    /* 後残り省略 */
}
このメインループを素直にASMに書き直すとこうなるでしょう. 
;esi : psrcの始まりアドレス
;edi : pdstの始まりアドレス
;ecx : (n-1)/4
.lp:
    mov     eax, [esi]  ;temp1 = *psrc;                ;u    1
    mov     ebx, eax    ;eaxを退避                     ;u    2
    shl     eax, 8                                     ;u    3
    shr     edx, 24                                    ;u    4
    or      eax, edx    ;(temp1 << 8) | (temp2 >> 24)  ;u    5
    mov     edx, ebx    ;temp2 = temp1;                ;v
    mov     [edi], eax  ;*pdstに書き込む               ;u    6
    add     esi, 4      ;psrc++;                       ;v
    add     edi, 4      ;pdst++;                       ;u    7
    dec     ecx         ;i--;                          ;v
    jnz     .lp         ;0になるまでループ             ;v    8
単位ループあたり8clockかかっています(横のu, vはuパイプとvパイプの意味です).
esi, ediは4つずつ増えているのでまとめてみましょう. 
;esi : psrcの始まりアドレス
;edi : pdstの始まりアドレス - psrcの始まりアドレス -4
;ecx : (n-1)/4
.lp:
    mov     eax, [esi]     ;temp1 = *psrc;                ;u    1
    add     esi, 4         ;psrc++;                       ;v
    mov     ebx, eax       ;eaxを退避                     ;u    2
    shl     eax, 8                                        ;u    3
    shr     edx, 24                                       ;u    4
    or      eax, edx       ;(temp1 << 8) | (temp2 >> 24)  ;u    5
    mov     edx, ebx       ;temp2 = temp1;                ;u    6
    mov     [edi+esi], eax ;*pdstに書き込む               ;v
    dec     ecx            ;i--;                          ;u    7
    jnz     .lp            ;0になるまでループ             ;v
1clock減りました. 全部で10命令あるので完全にペアリングが出来れば5clockで出来るはずです. それを実現することは可能なのでしょうか.
まず上の命令群の依存関係を眺めます. すると
  1. mov eax, [mem]
  2. mov ebx, eax
  3. shl eax, 8
  4. shr ebx, 24
  5. or eax, ecx
  6. mov ecx, ebx
  7. mov [mem], eax
というグループ(a)と
  1. add esi
  2. dec ecx
  3. jnz .lp
というグループ(b)に分かれます. この二つのグループの間には依存関係はありません. それぞれの依存関係を図にしてみました.
dependency
グループ(A)の1の後は2, 2の後は3か4のどちらでもよい, 3の後は5, 4と5はどちらが先でも良い, 5の後は6か7のどちらでもよい, という意味で書いています.
グループ(b)はA, B, Cが順に並んでいます.
さてこれを見てどういう順序にすればよいかを考えます.
まず 6, 7のペアは動かせません.
すると 4, 5のペアが決まります.
(b) グループの中で 3とペアに出来るのはA:add かB:dec ですがjnzを分けるわけにはいかないので Cはaddに決まります.
よって A, Bはそれぞれdec, jnzでなければなりません.
幸いこれらは1, 2とペアリング可能です.
以上の結果を並べるとループは3からスタートすればよいことが分かります. 
;esi : psrc + 4
;edi : pdst - psrc - 8
;eax : *(psrc+4)
;ebx : *psrc
.lp:
    shl eax, 8          ;u  1
    add esi, 4          ;v
    shr ebx, 24         ;u  2
    or  eax, edx        ;v
    mov edx, ebx        ;u  3
    mov [edi+esi], eax  ;v
    mov eax, [esi]      ;u  4
    dec ecx             ;v
    mov ebx, eax        ;u  5
    jnz .lp             ;v
これで完全なペアリングが完成しました. 後はこの前後にはみでた部分を追加するだけです(以下略:それが大変なんだが).
[Back]
御意見は光成滋生<herumi@nifty.com>までお願いします