[CSAPP] 3.5 Arithmetic and Logical Operations(산술연자와 논리연산)

학습 주제

• arithmetic 그리고 logical 연산자들에 대해 살펴볼 것이다.

정리한 내용

개요

instruction classes

operand size에 따라 다양한 variation을 가질 수 있기 때문에 operation들은 instruction class로 제공된다.

instruction class ADD : addb, addw, addl, addq

이제 살펴볼 것

여러가지 operation을 봐볼 것이다. 이는 4개로 group지을 수 있다.

1. load effective address
2. unary
3. binary
4. shift

3.5.1 Load Effective Address

memory에서 register로 읽어들이는 명령어의 형태를 가진다. (단, 이 때 메모리에서의 reference는 없다.)

• 첫번째 operand는 해당 위치(주소)에서 값을 읽는 것이 아닌, 유효한 주소(effective address) 자체를 목적지에 copy하는 것이다.
• C 언어에서의 address operator인 &를 이용하여 표현 가능하다.

leaq instruction

leaq 7(%rdx, %rdx, 4), %rax

• &arr[4];
• 위와 같은 format을 가진다.
• operand
  • first operand : memory location
    • 다른 연산자들의 memory location과 동일한 형태를 가지고 있지만, memory reference는 일어나지 않는다.
  • second operand : destination operand
    • 무조건 register이다.
• rdx에 x가 들어가 있다고 할 때, 위 연산의 결과는 다음과 같다.
  • rax : x + 4x + 7 = 5x + 7
  • arithmetic oepration의 용도로 사용됨을 알 수 있다.

용도

• 이후 메모리 참조를 위한 pointer 생성
• 간단한 arithmetic 연산들을 설명하는 데에도 사용할 수 있다.

컴파일러는 leaq연산의 사용처를 주소 계산 이외의 다른 용도를 현명하게 찾는다.

연습문제 (3.6)

• 정답
  1. 9 + q
  2. q + p
  3. q + 3p
  4. 2 + 8p
  5. 14 + 3q
  6. 6 + p + 7q

실제 코드

long scale(long x, long y, long z)
{
	long t = x + 4 * y + 12 * z;
	return t;
}

책에 나와 있는 결과이다.

 

내 컴퓨터에선?

leaq.o:	file format mach-o 64-bit x86-64

Disassembly of section __TEXT,__text:

0000000000000000 <_scale>:
       0: 55                           	pushq	%rbp
       1: 48 89 e5                     	movq	%rsp, %rbp
       4: 48 8d 04 b7                  	leaq	(%rdi,%rsi,4), %rax
       8: 48 8d 0c 52                  	leaq	(%rdx,%rdx,2), %rcx
       c: 48 8d 04 88                  	leaq	(%rax,%rcx,4), %rax
      10: 5d                           	popq	%rbp
      11: c3                           	retq

• 위와 같이 덧셈이 leaq로 구성된 모습을 볼 수 있다.
• 즉, leaq instruction은 덧셈과 제한된 형태의 곱셈에서 유용하다.
• LEA VS ADD

3.5.2 Unary and Binary Operations

unary

• operand : register 또는 memory location 둘 중 하나가 온다.
  • source 와 destination을 전부 담당한다.
  • incq (%rsp) : stack pointer를 하나 증가시키는 instruction이다.
  • source도 %rsp이고, destination도 %rsp이다.

binary

• operand
  • first operand : immediate value, register, memory location들 중 하나가 온다.
    • source를 담당한다.
  • second oeprand : register 또는 memory location이 온다(저장을 위해).
    • 보통 source 와 destination을 전부 담당한다.
    • subq %rax, %rdx : rdx에 있는 값에서 rax에 있는 값을 뺀 결과를 rdx에 저장한다.
    • source로는 %rax와 %rdx를, destination으로는 %rdx를 사용하는 모습을 볼 수 있다.

연습문제 3.8

memory address와 value, register와 value를 나타내고 있다.

• 빈칸 채우기 정답
•                       destination                            value

  1	0x100	0x100( = OxFF + 1)
  2	0x108	0xA8( = OxAB - 3)
  3	0x118	0x110( = OX11 * 16)
  4	0x110	0x14( = (Ox13)++)
  5	%rcx	0x0
  6	%rax	0xFD( = Ox100 - 3)

3.5.3 Shift Operations

operand

• first operand : immediate value 또는 1byte register(%cl)을 허용한다.
  • shift amount를 나타낸다.
• second operand : register 또는 memory location을 허용한다.
  • source(shift할 number)와 destination(저장할 공간)을 담당한다.

※ %cl register operand에 대해

• 이렇게 특정 register만을 허용시키는 것은 특이한 일이다.
• x86-64에선 다음과 같은 특징을 갖는다
  • 연산할 data의 size를 $w$ bit
  • %cl register안에 들어 있는 값의 하위 $m$ bit만큼 shift한다. 이 때, $m$은 $2^{m} = w$를 만족한다.
  • 예 : salb instruction의 경우 data size는 8bit의 크기를 갖는다. → $w = 8$.
    • 따라서 $2^{3} = 8$이므로 $m = 3$ 임을 알 수 있다.
    • 이 때 %cl에 0xFF의 값이 들어있었다면, OxFF의 하위 3bit 만큼 bit shift하게 된다.
    • 즉, second operand에 대해 $111_{(2)}$, 즉 왼쪽으로 7bit만큼 shift를 하게 된다.

SAL, SHL

left shift를 수행하는 instruction이다. 오른쪽부터 0으로 채워진다. 두 instruction은 정확히 동일한 기능을 수행한다.

SAR, SHR

• SAR : arithmetic right shift
  • 왼쪽부터 MSB와 동일한 bit로 채워진다.
  • 책에서의 기호 : $>>_A$
• SHR : logical right shift
  • 왼쪽부터 0으로 채워진다.
  • 책에서의 기호 : $>>_L$.

연습문제 3.9

• 정답
  1. SAL $4 %rax
  2. SAR %cl %rax

3.5.4 Discussion

위에서 봤듯이, right shift instruction을 제외하고 전부 unsigned와 signed 둘 모두에 사용이 가능하다. 이는 two’s complement system이 사랑받는 이유이다.

 

3.5.5 Special Arithmetic Operations

개요

2.3절에서 2개의 64-bit integer들을 곱할 때 128-bit가 필요한 결과물이 생길 수도 있다고 했다. 이 때 x86-64의 instruction set에서는 이러한 128-bit에 대한 지원을 제한적으로 제공해준다.

 

이를 oct word(16byte size)라고 한다.

IMUL instruction class

1. “Two operand” multiply instruction
   • 2개의 64-bit integer들간의 곱셈이다.
   • 64-bit로 truncate된 결과값을 제공한다.
   • 2.3.4 ~ 2.3.5절에서 배운 $^{u}_{64}$ 와 $^{t}_{64}$의 operation들을 구현하는데에 사용된다.
2. “One operand” multiply instruction
   • 2개의 64-bit integere들간의 곱셈이다.
     • mulq : for unsigned
     • imulq : for signed
   • 단, 64-bit로 truncate되지 않고 128-bit 값을 저장한다.
   • 어떻게 저장할까?
   • 이는 %rdx와 %rax 두 register를 사용하여, 상위 64-bit는 %rdx에, 하위 64-bit는 %rax에 저장하여 총 16byte를 저장할 수 있도록 한다.

How is “one operand” instruction possible?

어떻게 operand 1개로 두개의 64-bit integer들의 곱을 계산하는가?

• 계산하려는 한 값은 %rax register에 들어 있어야 한다.
• 나머지 하나는 imulq 명령어의 인자로 주어진다.

이와 같은 방식으로 하나의 operand를 갖도록 할 수 있다. 그럼 왜 인자를 하나로 갖도록 하였는가?

• 위에서 봤듯이 imulq 는 두개의 인자를 갖는 다른 기능의 instruction이 또하나 있다.
• 즉, operand의 개수로 구분해주기 위해 위함이다.

예시

• 직접 실행해보기

#include <inttypes.h>

void store_prod(__int128 *dest, int64_t x, int64_t y) {
    *dest = x * (__int128)y;
}

책에서의 결과(assembly code)

store_prod(__int128*, long, long):
        movq    %rsi, %rax      # x, D.2924
        imulq   %rdx  # y
        movq    %rax, (%rdi)    # D.2924, *dest_7(D)
        movq    %rdx, 8(%rdi)   # D.2924, *dest_7(D)
        ret

• 밑에서 두번째 코드와 밑에서 세번째 코드를 봐보자.
  • movq %rax, (%rdi) : dest에 하위 8byte를 copy하는 연산이다.
  • movq %rdx, 8(%rdi) : dest + 8에 상위 8byte를 copy하는 연산이다.
  • 왜? little endian → 상위 byte가 상위 address에 위치하게 되기 때문에 %rdx의 값을 dest + 8에 저장해준 것이다.

Division and Modulus Operations

위에서 살펴본 single operand multiplication instruction과 마찬가지로 인자를 하나만 갖는다.

• dividend(나눠지는 수)
  • %rdx와 %rax에 imulq instruction과 동일하게 저장을 미리 해놔야 한다.
  • 똑같이 high-order 64bits를 %rdx에, low-order 64bits를 %rax에 넣는다.
• dividor
  • idivl 의 인자로 주어진다.
• 저장
  • %rax에는 quotient(몫)이 저장
  • %rdx에는 remainder(나머지)가 저장

cqto instruction

64-bit 덧셈을 가지는 대부분의 응용프로그램에선 나눠지는 수가 64-bit로 제공된다.

• 이 때, 이 나눠지는 수는 %rax에 저장되어야만 한다.

위의 idivl instruction을 사용하게 되면 기본적으로 rdx와 rax를 같이 16byte의 integer로 해석한다.

• 따라서 64-bit 나눗셈 계산을 하는 경우에는 %rdx에 적절한 값을 넣어야 한다
• 적절한 값
  • unsigned : %rdx를 0으로 만든다. (cqo instruction)
  • signed : %rdx를 %rax의 sign-bit(MSB)로 채워넣는다. (cqto instruction)

gcc compiler에 -O1 최적화 옵션을 주고 그 결과를 lldb로 확인한 assembly code이다. (macOS, m1 processor)

• 위 코드를 보면 %r8 register에 %rdx의 내용물을 옮겨담고 있다. 이는 idivq instruction에서 %rdx를 사용할 것이기 때문이다.
  • ※ %rdx에 값이 들어있는 이유는 Intel x86-64에서의 인자의 호출 규약 때문이다.
    • 첫번째 인자는 %rdi
    • 두번째 인자는 %rsi
    • 세번째 인자는 %rdx
    • 네번째 인자는 %rbx
    • 그 이후엔 r8, r9
    • 그 이후엔 stack pointer에 하나씩 추가한다.
    • 위와 같은 규칙으로 넣고 함수를 call 하도록 되어 있다.
    • 더 보기

※ 왜 위에서 -O1의 최적화 옵션을 사용했는가?

• 책에서와 동일한 코드를 보고자 한다면 -O1의 최적화 옵션을 주어야 한다.
• 바로 위 그림은 최적화 옵션을 주지 않았을 때의 코드이다.