[TIL] 기계 수준 표현3 + RB Tree 삽입 구현(코드X)

1. 기계 수준 표현

1. 유효 주소 적재(Load Effective Address)

leaq S, D = D ← &S
: 메모리에서 레지스터로 읽어들이는 인스트럭션의 형태를 갖지만, 메모리를 전혀 참조하지 않는다.
  첫번째 오퍼랜드(S)의 유효 주소를 목적지(D)에 복사한다.

• 포인터를 생성하기 위해 사용
• 일반적인 산술 연산을 간결하게 설명하기 위해 사용
  • 예시 ) x in %rdi, y in %rsi
  • leaq (%rdi, %rsi, 4), %rdi  //x = x + 4*y 

---

2. 프로시저(Procedure)

procedure call 은 소프웨어에서의 주요 추상화
: 지정된 인자들과 반환 값으로 특정 기능을 구현하는 코드를 감싸주는 방법 제공
  무슨 값이 계산되고, 이 프로시저가 프로그램 상태에서 무슨 효과를 갖는지에 대한 명쾌하고 간결한 인터페이스 정의를 제공하지만,
  일부 동작의 구체적인 구현은 감춘다.

• 프로시저 P → 프로시저 Q → 프로시저 P
• 제어권 전달
  • 진입할 때 PC를 Q에 대한 코드의 시작 주소로 설정 
    • return address 스택에 저장 : Q가 종료되고 P가 시작되어야할 위치
  • 반환할 때 PC를 P에서 Q를 호출한 인스트럭션의 다음으로 설정
• 데이터 전달
  • P는 하나 이상의 매개변수를 Q에 제공
  • Q는 하나의 반환 값을 P에게 return
  • 데이터 전달은 레지스터를 통해 일어난다.
    • 필요한 값은 먼저 적절한 레지스터에 복사해두어야 한다.
• 메모리 할당과 반납
  • Q는 시작할 때 지역변수를 위한 공간을 할당받을 수 있다.
  • Q는 반환할 때 이 저장소를 반납할 수 있다.

★ 런타임 스택 ★

    : 프로시저들이 요구하는 저장장소를 관리할 수 있으며, 스택과 프로그램 레지스터들은 제어와 데이터를 전송, 메모리 할당하기 위해 필요한 정보를 저장한다.

• stack top = 현재 실행 중인 프로시저에 대한 프레임
• 프로시저 call, return을 지원하기 위해 필요한 저장 공간 관리
• 지역 저장소(Local variables)
  • 레지스터 수가 부족하거나
  • 연산자 &가 사용되어 변수의 주소를 생성할 수 있거나
  • 배열 또는 구조체여서 참조로 접근되는 경우
  • 지역 저장소에 스택 프레임을 할당한다.
• 각 procedure call은 스택 상에 자신만의 사적인 공간을 가지며 서로 간섭하지 않는다.

---

3. 배열의 할당과 접근

C언어에서 배열
: 스칼라 데이터를 보다 큰 자료형으로 연계시키는 수단
  배열 원소들에 대한 포인터를 만들고 이들 포인터 간에 연산을 하여 접근

• T A[N];
• T : type  / A : array name / N : 원소 개수 / *p = Xa : 배열의 시작 주소 / L : byte 단위
• i번째 원소의 주소 = Xa + L*i = p + i
• 다중 배열
  • T D[R][C];
  • Xd : 배열의 시작 주소 = D[0][0]
  • 행 우선(row major) 순서로 메모리에 저장
    • D[0] 행의 모든 원소들이 저장된 후에 D[1][0]이 저장된다.
  • &D[i][j] = Xd + L(C*i + j)

---

2. RB Tree 구현

RB Tree 삽입 과정 구현해본 방법

오늘 구현을 직접 해보면서 포인터를 많이 사용하는 시간이었다.
확실히 포인터의 사용법을 알아간 날이었다.
아직 NULL에 대한 경우를 다 처리하지 못해서 완전하지 않지만 내일 최대한 완료해야겠다.