필기용 블로그

●Procedure

 ▷특정 값을 Return하고, 반복해서 호출가능한 block

 ▶메커니즘

  ▶Passing control

   ▷call: 해당 Procedure의 시작으로 control 이동 (jump)

   ▷return: call 다음의 위치로 control 이동

  ▶Passing data

   ▷매개변수

   ▷return 값

  ▶Memory management

   ▷Procedure 진행 동안 메모리 할당 (allocate)

   ▷return시 메모리 반환 (deallocate)

 ▶Stack구조 활용

  ▷Procedure를 사용하기 위해 Stack을 활용함.

  ▷Bottom: 최상위 주소 (높은 주소)

  ▷Top: 낮은 주소, 높은 주소에서 내려오면서 할당.

  ▷%rsp: Stack Pointer

  ▷pushq Src: %rsp를 8 감소시키고, 해당 위치에 Src 저장.

  ▷popq Dest: 해당 위치의 값을 읽어들여 Dest에 저장하고, %rsp를 8 증가시킴.

○Passing Control (컨트롤 이동)

 ▶Precedure call: call [label]

  ▷return address를 stack에 push함.

   ▷return address: 함수가 return된 이후에 실행해야할 코드.

  ▷label로 jump (%rip - 다음 실행할 코드의 주소)

 ▶Procedure return: ret

  ▷stack에서 address를 pop함.

  ▷address로 jump. (%rip - 다음 실행할 코드의 주소)

○Passing Data (데이터 전달)

 ▶Arguments (매개변수)

  ▷처음 6개의 매개변수는 정해진 register에 저장. (int, 포인터..)

   ▷%rdi, %rsi, %rdx, %rcx, %r8, %r9

  ▷나머지 매개변수는 stack에 밀어넣음.

 ▶Return value

  ▷%rax

○Managing local data

 ▷함수가 여러 계층에 걸쳐 실행될 경우, local 데이터들을 저장할 필요 있음 (매개변수, 지역변수, return 주소)

 ▶위의 정보들을 저장하는 Stack frame 활용

  ▷한 Procedure당 하나의 frame 사용 (크기는 Procedure마다 다름)

  ▷Return주소(필수), Local storage, Frame pointer, ArgumentBuild등 사용.

  ▷Caller frame: Caller가 전달해주는 정보들 (Return주소, 매개변수)

  ▷call에 할당(push), ret에 해제(pop)

 ▶Local data의 저장 (여러 함수가 Stack으로 호출될 경우)

  ▶Caller Saved: Caller가 register값들을 백업함. (call된 procedure가 return된 이후 restore)

   ▷%rax (return value) 

   ▷[%rdi, %rsi, %rdx, %rcx, %r8, %r9] (Arguments),

   ▷[%r10, %r11] (Caller-saced temporaries)

   ▷Procedure(Callee)에서 수정해도 상관없음. 

  ▶Callee Saved: Callee가 register값들을 백업함. (return전에 restore)

   ▷[%rbx, %r12, %r13, %r14] (Callee-saved Temporaries)

   ▷%rbp (frame pointer)

   ▷%rsp (stack pointer) - Procedure 입장시 - (push), 나갈시 + (pop)

   ▷Callee가 저장해야함.

●Quene

 ▷데이터를 순차적으로 저장하는 자료 구조, First-in-First-out.

 ▶ADT

  ▷임의의 Object를 저장

  ▷삽입/삭제는 First-in-First-out 규칙을 따름

  ▶주요 명령

   ▷void queue(object): 데이터를 queue의 마지막에 삽입

   ▷object dequeue(): 가장 앞에 있는 데이터를 삭제함. 삭제한 데이터를 반환함.

  ▶보조 명령

   ▷object front(): 가장 앞에 있는 데이터를 반환함. (dequeue()과 다르게 삭제하지 않음)

   ▷int size(): 저장된 원소의 개수를 반환함.

   ▷bool empty(): 저장된 원소가 없으면 true 반환.

  ▶Exception

   ▷QueueEmpty: 빈 Queue의 요소에 접근하려 할 때. (front, dequeue)

   ▷QueueFull: Queue가 저장가능한 요소 이상으로 저장하려 할 때.

  ▶활용

   ▷직접: 대기열, Multiprogramming

   ▷간접: algorithm의 보조 데이터 구조, 다른 데이터 구조의 일부

○STL Queue

 ▷STL에서 제공하는 Queue타입, Vector를 기반으로 만들었으며 크기가 가변적임

○C++ Queue

○Array-based Queue

 ▷N size의 배열을 환형 순환형식으로 사용.

 ▷3개의 변수 필요

  ▷f: 처음 요소의 index

  ▷r: 끝 요소 다음의 index (다음에 넣을 index)

  ▷n: queue에 있는 요소들의 개수

○Linked-List-based Quene

 ▷Linked-List-based Stack과 비슷하지만, enquene은 Linked-List의 마지막에 새로운 요소를 삭제함.

○Circularly Linked-List-based Quene

 ▷Linked-List-based Quene에서 enquene의 효율성을 위해 양쪽 끝을 연결한 것.

 ▷가장 마지막 요소의 포인터인 cursor 변수를 이용. (cursor->next : 가장 처음 요소)

 ◎코드 (Elem: String)

  ▷Node

  ▷Circulary Linked List

  ▷Linked Quene

○제어문

 ▶Processor State: 현재 실행중인 프로그램에 대한 정보

  ▷임시 데이터 (%rax ...)

  ▷runtime stack 위치 (%rsp)

  ▷현재 코드 control point (%rip ...)

  ▶Condition Code 

   ▷CF (Carry flag): 최상위 비트로부터 carry/borrow out이 일어났는가? (unsigned overflow)

   ▷ZF (Zero flag): 0인가?

   ▷SF (Sign flag): 0보다 작은가? (signed로 취급) -> 최상위 비트가 1인가?

   ▷OF (Overflow flag): 2의 보수에서 overflow가 일어났는가? (a>0 && b>0 && t<0 || a<0 && b<0 && t>0)

   ▶코드 읽기 (SetX Instructions)

    ▷아래의 명령어들을 통해 한 바이트 값에 SetX 명령의 결과값을 입력한다. 

    ▷매개변수 = 이전 연산의 Condition Code

    ※규칙

      ▷n: not

      ▷s: signed

      ▷g: greater (signed)

      ▷l: less (signed)

      ▷e: equal

      ▷a: above (unsigned)

      ▷b: below (unsigned)

▷주로 최하위 비트를 이용한다.

    ▷주로 Zero Extension을 사용하여 결과를 확인한다.

 ▶Conditional Branch (가정문)

  ▶Jump

   ▷라벨의 부분(Label - ~: )으로 이동한다.

   ▷C의 goto문과 유사하다.

   ▷SetX와 유사한 조건을 공유한다.

   ◎If -> Jump

  ▶Conditional Move (cmov[조건])

   ▷if (조건) Dest <- Src

   ▷GCC가 해당 연산이 안전하다고 확인하면, Jump대신 사용한다.

   ▶장점

    ▷순차수행(Control Transfer가 일어나지 않음)하여 pipe-lining에 적합함.

   ▶불가능한 경우 (두 경우의 연산 모두 시행되기 때문에 생기는 위험)

    ▷연산의 비용이 높은 경우 (함수 호출)

    ▷연산이 조건에 영향을 주는 경우 (x += 1)

    ▷NUL포인터를 참조하는 경우

   ◎if -> cmov

 ▶Loop (반복문)

  ▷Do-While문의 해석을 기본으로 함.

  ▷do -> Label / while -> if(조건) go to do

  ▶While 해석

   ▷Jump-to-middle : 반복문 시작에 Do-while의 조건검사로 Jump

   ▷Do-while conversion : While문을 Do-while 형식으로 바꿈

  ▶For 해석

   ▷For문의 Init Test부분은 컴파일러에 따라 생략가능 (초기 상태를 지정하기 때문)

 ▶Switch

  ▷if-else문을 기본으로 하지만, 여러 예외를 경계해야함

   ▷Multiple case labels (여러 라벨이 동일 연산)

   ▷Fall through cases (break문이 없을 때 다음 case의 연산도 진행)

   ▷Missing cases (없는 조건)

  ▶Jump Table

   ▷case에 따른 CodeBlock으로 이동함.

   ▷조건 변수(x)가 양수이며, 어느정도 연속된 경우에는 x를 Index로 사용 가능

   ▷조건 변수가 서로 멀리 떨어져있는 경우, if-else문 처럼 해석

  ◎Jump Table을 이용한 Switch문 변환

  ▷ja .L8 : unsigned 비교를 통해 음수(최상위 비트가 1)와 범위보다 큰 양수값들을 default (.L8)로 보냄.

  ▷jmp *.L4(,%rdi,8) : L4+8*%rdi의 위치로 이동함. * -> 간접점프를 의미?

  ▷.quad : 8바이트 지정

  ▷x = 0, 4: default (,L8)

  ▷x = 1: .L3

  ▷x = 2, 3: 2에서 fall through 발생. w의 초기화를 x = 3에서 하는 이유는 초기화를 x = 3일 경우에만 하면 되기 때문, 그로 인해 x = 2에서 x = 3이 아니라 x = 2, 3이 동시에 진행하는 다른 Label(.L6)로 이동함.

▷x = 5, 6 / default: 5, 6은 같은 Label이용.

●Stack

 ▷제한적으로 접근 가능한 나열구조, Last-in-first-out.

 ▶ADT

  ▷임의의 Object를 저장

  ▷삽입/삭제는 Last-in-first-out 규칙을 따름

  ▶주요 명령

   ▷void push(object): 데이터를 삽입.

   ▷object pop(): 마지막에 넣은(최상위) 데이터를 삭제함. 삭제한 데이터를 반환함.

  ▶보조 명령

   ▷object top(): 마지막에 넣은 데이터를 반환함. (pop()과 다르게 삭제하지 않음)

   ▷int size(): 저장된 원소의 개수를 반환함.

   ▷bool empty(): 저장된 원소가 없으면 true 반환.

  ▶Exception

   ▷StackEmpty: 빈 Stack의 요소에 접근하려 할 때. (top, pop)

   ▷Stackfull: Array기반의 Stack에서 Array에 더이상 데이터를 넣을 수 없을 때.

 ▶활용

  ▷직접: 웹 브라우저, 텍스트 에디터의 뒤로가기/취소, C++의 Chain method call

  ▷간접: algorithm의 보조 데이터 구조, 다른 데이터 구조의 일부.

 ▷C++ Stack Interface (c++ STL class의 Stack과 다름)

○Array-based Stack

 ▷배열을 이용해 Stack 구현 (왼쪽(0)부터 오른쪽(n)으로 데이터를 채워나간다.)

 ▷왼쪽(0)부터 오른쪽(n)으로 데이터를 채워나간다.

 ▷최대 크기가 정해져있고, 가장 오른쪽의 데이터를 지정하는 index를 저장하는 변수가 필요.

 ▶성능 (n-Stack의 요소 개수)

  ▷공간복잡도 : O(n)

  ▷각 연산의 시간복잡도 : O(1)

 ▶한계

  ▷Maximum Size가 존재하며, 이를 바꿀 수 없음.

  ▷가득찬 Stack에 데이터를 넣으면 StackFull Exception이 발생함.

 ▶코드

○Linked List-based Stack

 ▷(Singly) Linked List를 이용해 Stack을 구현.

 ▷Linked List의 특성에 따라 최대 크기의 제한이 없음.

 ▶코드(노드)

 ▶코드(Linked-List)

 ▶코드(Stack)

●Template

 ▷Function, Class가 generic type(나중에 선언되는 타입)으로 연산가능하게 함.

 ▷다른 타입에 대해 각각 Overloading할 필요 없이 동작 가능하도록 함.

 ▷C++에서 Template