팬티엄2/3에서 다시보는 XOR명령 [작성자 KCGON]

┌───────────────────────────────────┐
│  ▶ 번  호 : 150/150               ▶ 등록자 : KCGON                 │
│  ▶ 등록일 : 2000년 04월 27일 17:04                                  │
│  ▶ 제  목 : [참고] 팬티엄2/3에서 다시보는 XOR명령                   │
└───────────────────────────────────┘


    아주 오랜 옛날에 이런 어셈블리 문장을 본일이 있었습니다.

        xor     ax, dx
        xor     dx, ax
        xor     ax, dx

    위의 3줄의 구문이 별도의 레지스터나 메모리를 사용하지 않고
    두 레지스터의 내용을 교환한다는 것이었습니다.
    즉,

        xchg    ax, dx

    와 등가의 구문이라는 것입니다.

    그때는 하도 신기해서 수치를 대입해서 따라가 봤더니 진짜로 교환이
    되더라고요.
    아주 재미있는 일도 다 있네 하고 잊고 살았지요.

    그리고 

    세월은 흘러서 이제 제가 팬티엄2(셀러론)에서 어셈블리로
    정렬(sort)하는 프로그램을 최적화 하다 보니
    가능하면 조건부 점프를 제거해야 하는 문제에 봉착하게 되었읍니다.

    ;========================================================================
    ;==== 아래와 같은 구문입니다.
    ;========================================================================

        cmp     eax, edx        ;   .IF (eax < edx)          
        jae     @f              ;       xchg    eax, edx  
        xchg    eax, edx        ;   .ENDIF
@@:                             ;
    
    테스트 결과 예측이 맞으면    2 [cpu clock]이 걸리고,
                예측이 빗나가면 12 [cpu clock]이 걸리는 것입니다.

    그러나 정렬의 문제에선 인텔이 그렇게 자랑하는 예측분기가 무용지물입니다.

    그럼 평균해서 7 [cpu clock]이 소요된다는 것입니다.

    문제는 어떻게 하면 이것을 줄일 수 있을까 하는 것입니다.
    여러가지의 시도와 테스트. 장장 이틀 동안 밤낮을 가리지 않고 몰두(?)하다가
    옛 추억을 떠올리게 되었읍니다.

    ;========================================================================
    ;==== 팬티엄2, 팬티엄3 에서 다시보는  XOR 명령
    ;========================================================================

        xor     eax, edx                ; <스탭1>
        xor     edx, eax                ; <스탭2>
        xor     eax, edx                ; <스탭3>

     주의깊게 분석한 결과 위의 3단계는 아래와 같은 기능을 수행한다는 것을
     알았습니다.

     <스탭1>은 두 레지스터의 'XOR 비트 패턴'을 만드는 것입니다.
             
     <스탭2>는 (edx)를 상대방(eax)으로 바꾸는 것입니다.

     <스탭3>은 (eax)를 상대방(edx)으로 바꾸는 것입니다.

    어떻게 그런 일이 일어나는지 쉽게 알 수 있도록
    놀고있는 (ecx)를 사용해 보도록 하겠습니다.

        mov     ecx, eax                ; <스탭1>
        xor     ecx, edx                ; <스탭1>

        xor     edx, ecx                ; <스탭2>
        xor     eax, ecx                ; <스탭3>

    <스탭1>은 (ecx)에 두 레지스터(eax, edx)의 'XOR 비트패턴'을 만든다.

    <스탭2>는 (edx)에 (ecx)를 XOR 시켜서 상대방(eax)으로 바꾼다.

    <스탭3>은 (eax)에 (ecx)를 XOR 시켜서 상대방(edx)으로 바꾼다.
            
    이제 잘 보면, 굳이 (ecx)를 사용하지 않고도 구현하는 것이 가능할 것입니다.
    즉 (ecx)를 제거하면 원래처럼 3단계의 XOR로 교환이 이루어 지는 것입니다.

    그러나 나는 단순히 교환을 하고자 하는 것이 아니라.
    조건에 따라서 교환이 되던가 또는 그대로 있는 것을 원하는 것입니다.

    이를테면 팬티엄프로 이상의 CPU에서만 가능한

    '컨디션 무브(조건부 이동)'- CMOVcc 와 같은

    '컨디션 익스체인지(조건부 교환)'를 원하는 것입니다.

    ;========================================================================
    ;==== ?
    ;========================================================================

    다시 한번 풀어놓은 코드를 보지요.

        mov     ecx, eax                ; <스탭1>
        xor     ecx, edx                ; <스탭1>

        xor     edx, ecx                ; <스탭2>
        xor     eax, ecx                ; <스탭3>

    만약에 <스탭1>과 <스탭2>사이에서

    'XOR 비트패턴'을 가지고 있는 (ecx)를
    조건에 따라서 마스크 시키면 어떻게 될까?

    즉 교환을 할때는

        and     ecx, -1                 ; -1 = 0ffffffffh

        (아무일도 없었던 것처럼 그냥 교환이 된다.)

    교환을 하지 않을때는

        and     ecx, 0

        (이제 (ecx)는 0이 되고 다른곳에 아무리 XOR를 해 대 봤자
         아무런 변화를 일으키지 못한다. 즉 두 레지스터는 그대로 있는다.)

    자, 이제 문제는

        어떻게 조건에 따라서 (-1) 또는 (0)을 만들까의 문제만 남았다.

    그러나 이는 의외로 간단한 문제다.

    이제 또 놀고있는 (ebx)를 사용해 보자.

        xor     ebx, ebx
        cmp     eax, edx                    ; sbb - 빌림을 고려한 뺄셈.
        sbb     ebx, ebx                    ; sbb - subtract with borrow

    그러면
        (eax >= edx)이면 (ebx)는 0이 된다.  ;  ebx = 0 - 0 - 0 = 0
        (eax < edx)이면 (ebx)는 -1이 된다.  ;  ebx = 0 - 0 - 1 = -1

    또는 아래의 코드를 사용해서도 구현할 수 있다.
                                
        xor     ebx, ebx        ; ebx = 0           ; ebx = 0
        cmp     eax, edx        ;(eax >= edx)       ; (eax < edx)
        setae   bl              ; ebx = 1           ; ebx = 0
        dec     ebx             ; ebx = 0           ; ebx = -1

    ;========================================================================
    ;==== 이제 두 루틴을 결합해 보자.
    ;========================================================================

    mov     ecx, eax            ; <스탭1>
    xor     ecx, edx            ; <스탭1>

    xor     ebx, ebx            ;
    cmp     eax, edx            ; 조건에 따라 (ebx)에 (-1)또는 (0)을 만듬.
    sbb     ebx, ebx            ;

    and     ecx, ebx            ; (ecx)를 마스크 시킴.

    xor     edx, ecx            ; <스탭2>
    xor     eax, ecx            ; <스탭3>


    이제 총 8단계로 무분기 '조건부 익스체인지'를 만들었다.
    한번 평가를 해 보자.

    1. 코드 사이즈는 16바이트이다. (모두 2바이트 명령들)

    2. 추가로 2개의 레지스터가 더 필요하다. (좀 심각한 문제)

    3. 실행 시간은 3 [cpu clock]이다.

    ;========================================================================
    ;==== "실행 시간은 3 [cpu clock]이다." 에 덧붙여서.
    ;========================================================================

    팬티엄2/3 에서는 잘 짜여진 코드는

    1 [cpu clock]에 최대 3개의 어셈블리 명령을 처리할 수 있다.

    어떻게 해야 최대 3개의 어셈블리 명령을 실행할 수 있는가의 문제는
    대단히 복잡하다.
    분명한 것은 더 이상 팬티엄식의 단순한 UV파이프가 아니라는 것이다.
    인텔의 팬티엄2/3 최적화 메뉴얼의 어디에도 UV파이프 어쩌구는 없다.

    한가지 확실한 대안은
    가능하면 아주 단순한 어셈블리명령으로 그 루틴을 재구성하라는 것이다.

    위의 코드는 3[cpu clock]에 수행되기 위해서는 아래처럼 재배치 되어야 한다.

    mov     ecx, eax            ; <스탭1>
    xor     ebx, ebx            ;;
    cmp     eax, edx            ;; 조건에 따라 (ebx)에 (-1)또는 (0)을 만듬.

    sbb     ebx, ebx            ;;
    xor     ecx, edx            ; <스탭1>
    and     ecx, ebx            ; (ecx)를 마스크 시킴.

    xor     edx, ecx            ; <스탭2>
    xor     eax, ecx            ; <스탭3>

    ;========================================================================
    ;==== 2. 추가의 레지스터 문제에 덧붙여서.
    ;========================================================================

    참고로 나는 <삼각형 출판사>에서 나온 '코드 체적화 테크닉'이란 책에서
    많은 영감을 얻었다.

    그 책의 원저자인 Michael Abrash가 팬티엄 최적화와 관련하여
    이런말을 한 것을 기억한다.

    "펜티엄에는 오직 7개의 범용 레지스터만이 있고, 필자는 중요한 루프의 경우
     EBP를 사용하도록 강력하게 권장한 바가 있다."

    7개란 스택을 위한 ESP를 빼고 한 말임. (eax, ebx, ecx, edx, esi, edi, ebp)

    또한 인텔의 팬티엄2/3 체적화 메뉴얼에도 이런말이 적혀있다.

    "만약 그 프로시저가 다른 프로시저를 호출하지 않는 말단의 프로시저라면,
     ESP를 베이스 레지스터로 사용해서 EBP를 자유롭게 하라."

    전적으로 공감하는 바이다.
    이에 덧붙여서 나는 이런 말을 하고 싶다.

    "팬티엄2/3 에서는 쓸데없이 ESP를 놀리지 마라."

    팬티엄에서는 PUSH와 POP이 아주 쓸만한 명령이었다.
    모두 U파이프와 V파이프에서 동시에 실행가능한 명령이다.
    더우고 1바이트 짜리 명령으로 코드사이즈가 더 없이 짧다.

    그러나 팬티엄2/3는 더이상 단순한 UV파이프의 개념이 아니다.

    PUSH와 POP명령은 이제 댓가가 크다.

    ;========================================================================
    ;==== 최종 비교.
    ;========================================================================
    
      (무분기 조건부 교환루틴)  ;   (조건부 점프루틴)
                                ;
        mov     ecx, eax        ;       cmp     eax, edx
        xor     ebx, ebx        ;       jae     @f
        cmp     eax, edx        ;       xchg    eax, edx
                                ; @@:
        sbb     ebx, ebx        ;
        xor     ecx, edx        ;
        and     ecx, ebx        ;
                                ;
        xor     edx, ecx        ;
        xor     eax, ecx        ;

1. 코드 사이즈      16 바이트  <->   6 바이트
2. 추가 레지스터     2 개      <->   0
3. 실행 사이클       3 클럭    <->   7 클럭 (평균치)
                                     예측이 맞으면(2클럭) 틀리면(12클럭)
                            (참고로, 예측이 틀리면 12클럭이 더 걸릴수 도 있음)

    <남겨진 과제>

    실행시간의 이득에 비해서 손실이 많다.
    특히 2개의 추가 레지스터 문제는 심각하다.

    1. 추가 레지스터를 1개로 줄일 수만 있다면 아주 좋겠는데.

    2. 무분기로 3개의 데이타를 정렬하는 루틴의 구현.

    (이상입니다. 긴 글을 끝까지 읽어 주셔서 대단히 고맙습니다.)