[CS:APP] 가변크기 배열(VLA)의 2차원 메모리 주소 곱셈(imulq)과 GCC 컴파일러의 덧셈 치환 루프 최적화

1. 2차원 배열은 메모리에 일렬(1차원)로 저장됩니다

컴퓨터 메모리는 가로세로 바둑판 모양이 아니라, 0번지부터 1씩 증가하는 1차원 직선 형태입니다.
따라서 2차원 배열 int A[n][m]은 1번째 행, 2번째 행, 3번째 행이 메모리에 빈틈없이 연속해서 이어 붙어 저장됩니다.

---

2. 2차원 배열 원소 A[i][j]의 메모리 주소 계산 공식

원소 1개의 크기가 4바이트(int)이고, 열 개수가 m개일 때:

A[i][j]의 메모리 주소 = 배열 시작 주소 + 4바이트 * (m * i + j)

1. i번째 행을 건너뛰기 위해서는 앞서 있는 행들의 원소 개수인 m * i개를 건너뛰어야 합니다.
2. 그 행 안에서 j번째 원소로 가기 위해 + j를 더합니다.
3. 원소 1개가 4바이트이므로 전체에 4를 곱합니다.

---

3. 고정 크기 배열과 가변 크기 배열(VLA)의 어셈블리 명령어 차이

• 고정 크기 배열 (int A[10][8]):
  • 열 개수 m이 숫자 8로 고정되어 있습니다.
  • $8 imes i$는 2진수 비트를 왼쪽으로 3번 이동하는 시프트 연산과 덧셈(leaq 명령어)만으로 1클럭 사이클 만에 빠르게 계산됩니다.
• 가변 크기 배열 (int A[n][m]):
  • 열 개수 m이 실행 중에 사용자가 입력한 변수입니다.
  • 비트 시프트로 바꿀 수 없으므로, CPU는 무거운 정수 곱셈 명령어인 imulq를 실행해야 합니다.

---

4. GCC 컴파일러의 루프 최적화: 곱셈을 덧셈으로 바꾸기 (강도 감쇄)

이중 루프 안에서 A[i][j]를 순회할 때 매번 m * i 곱셈을 하면 CPU 연산 시간이 크게 낭비됩니다.
GCC 컴파일러는 이를 다음과 같이 최적화합니다:

[최적화 전]: 매 반복마다 4 * (m * i + j)를 계산 (imulq 곱셈이 매번 실행됨)
[최적화 후]: 루프 시작 전 ptr = A[0] 주소를 잡아둠
             루프가 돌 때마다 ptr = ptr + 4 (다음 칸으로 4바이트 더하기만 수행)
             행이 바뀔 때는 ptr = ptr + (4 * m) (다음 행으로 덧셈만 수행)

• 무거운 곱셈 연산(imulq)을 가벼운 덧셈 연산(addq)으로 바꾸는 기법을 강도 감쇄(Strength Reduction) 최적화라고 부릅니다.

---

5. 어셈블리에서 4n과 n을 따로 사용하는 이유

• 4n: 포인터를 다음 행으로 건너뛰게 할 때 메모리 바이트 주소 전진용으로 사용됩니다 (int가 4바이트이므로 $n imes 4$ 바이트 필요).
• n: 루프가 $n$번 반복되었는지 반복문 탈출 조건 검사 카운터로 사용됩니다.