목차
2023학년도 2학기 충남대학교 이민선 교수님의 컴파일러개론 수업 정리자료입니다.
프로그램의 여러가지 메모리 중 Stack에 대해 살펴보자.
📁 Memory Organization (Stack)
Stack과 Heap은 런타임에 크기가 변한다.
Stack은 아래쪽으로 증가하고, Heap은 위로 증가한다.
이때 Stack과 heap 위치가 바뀔 수 있다.
Code, Static Data : 컴파일러에 의해 크기가 결정된다.
📁 Run-Time Stack
Run-Time Stack이란 Call-Stack이라고도 불리며 함수 하나를 호출할때마다 생성되는 Frame 혹은 Activation record이 구성하는 Stack을 말한다.
이때 스택에 쌓이는 한칸을 Activation record라고 부른다.
Activation record 내에는 주로 함수 내에 들어있는 로컬변수가 들어있고, 함수의 인자, 리턴값, 3-addr 코드에서 많이 생기는 임시변수 중 레지스터에 넣지 못하는 것들이 들어있다.
Run-time Stack이 진행되는 방식은 다음과 같다.
- f가 호출되면 f의 frame을 stack에 push한다.
- f가 return되면 f에 대한 frame을 pop-up한다.
stack의 Top Frame은 현재 수행중인 함수의 frame이다.
예를 들어 main()을 호출하면 main()에 대한 frame이 한칸 쌓이고, 그 안에서 f()를 부르면 f()에 대한 frame이 그 위에 쌓인다. 이후 코드가 진행되다가 f()가 리턴돼서 stack 내에서 pop-up되면 이제 main()만 남고, 프로그램이 끝나면 main()이 최종적으로 pop-up된다.
📁 Stack Pointers
일반적인 Stack은 stack top을 가리키는 포인터를 하나 두고 사용하는데, 메모리의 Stack은 이렇게 사용할 수가 없다. 일반적인 자료구조 stack은 구성요소가 integer나 string처럼 한 스택에 대해 동일한 타입의 구성요소가 들어있기 때문에 모든 구성요소의 크기가 똑같다. 그래서 포인터 사용이 가능하지만, 메모리 스택은 어떤 엔트리는 로컬 변수가 많아서 크기가 클 수도 있고, 어떤 엔트리는 크기가 작을수도 있다. 그래서 어디부터 어디까지가 stack top인지 표현하기 위해서는 보통 시작과 끝 두 지점을 가리키는 포인터 두개를 사용하고, 위의 포인터를 SP, 아래 포인터를 FP라고 지칭한다.
stack top을 표시하기 위해 꼭 포인터를 두개 사용할 필요는 없다. 하나만 사용해도 표현이 가능하지만 두개를 사용하는 이유는 stack top 내부의 변수 하나를 가리키고 싶을 때 그 위치의 주소를 구해야하는데 보통 이런 주소를 구할 때 절대주소를 구하지 않고 포인터로부터 어느정도 떨어졌는지의 offset을 구한다. 그래서 포인터를 두 개 사용하면 더 가까운 포인터를 기준으로 offset을 구할 수 있어서 offset의 최댓값이 작아지는 Small offset 효과를 얻을 수 있다. offset 크기가 작으면 어떠한 명령을 내릴때 instruction의 길이도 짧아진다. 곧 전체 프로그램의 길이도 작아진다.
SP가 가변적이라서 주로 FP를 이용해서 접근하고, SP는 다른 일을 맡는다.
Stack은 아래 방향으로 자란다!
ELF Memory Image를 보자.
연두색 부분이 컴파일 이후 a.out으로 만들어지는 프로그램의 구성이다. 그 프로그램에는 main이 존재하고, main 이전에 startup routine이 있다. 그리고 static하게 링크한 xx.o와 xxx.o가 있다.(?)
또한 global 변수를 함께 갖고있는데, 글로벌 변수의 일부는 여기에 없다. 보통 초기화한 글로별 변수가 들어있음.
여기까지가 디스크에 있는 프로그램. 이제 이 이후에 프로그램을 프로세스로 만들게 되면 더 많은 메모리 공간을 확보해야한다. 그 중 첫번째로 확보하는게 초기값이 없는 글로벌변수. 굳이 디스크를 잡아먹지 않고, 런타임에 메모리에서 확보. 다음으로 힙과 스택. 스택은 함수가 호출될 때 마다 증가했다가 사라졌다가 하겠지. 힙도 마찬가지로 말록 등이 호출될때마다 증가할 것. 그 가운데에 shard library가 있는 경우가 있음. 명시적으로 링크하지 않아도 printf 등을 쓰는것과 같음.
main 프레임이 있기 전에 회색 부분이 시스템에서 env, argv, argc 등을 미리 넣어주는 부분. 그 다음 main()호출. 저 안에 main의 로컬변수 등이 들어감. 그러고나서 main 안에서 함수를 func(72, 73)을 호출하면 func() 스택 쌓임. 리턴되면 이부분 사라지고 다시 ebp와 esp 원위치.
Run-time stack을 자세히 보자.
어떤 함수를 호출할 때 는 하늘색 부분에서 노란색 부분을 호출한 것. 이렇게되면 param1~n으로 표현된 실 인자들과 return address를 하늘색 부분에 넣어두고, caller가 callee를 부르는 jump 수행. callee는 제일 먼저 previous fp, 즉 파란 부분만 있었을 때의 FP부분을 저장해둬야 나중에 복원 가능하니까. 이후 이제 로컬변수 정의. 그 다음에 또 다른 프로그램을 부를 때, 하늘색 때처럼 param1~n와 return address를 넣음. 이제 아래 다른 프레임이 쌓이겠지.
나중에 노란색 부분이 pop-up되면 previous fp 보고 fp 복원. sp를 따로 저장하지 않는 이유는 현재의 FP부분이 이후의 SP이니까.
오른쪽의 Temp1 ~ n은 임시변수. 3-addr 코드 등에서 필요해서 만드는 임시변수들. 지금은 고려하지 말자.
int f(int a) {
int b, c;
}
void g(int a) {
int b, c;
...
b = f(a+c);
...
}
main() {
int a, b;
...
g(a+b);
...
}
처음에 분홍색 부분 main()이 있고, g를 부르면 파라미터랑 리턴주소 넣고, 파란 스택 프레임에 FP 넣고 쌓임. 다음에 f가 불리면 파라미터랑 리턴주소 넣고, 이때 리턴주소는 b=f(a+c)부분이겠지. 다음에 노란색 스택 프레임에 FP 넣고 쌓임.
📝 문제 풀어보기
void foo(int a) {
int x=0;
if (a <= 1) return ;
foo(a-1);
foo(a-2);
}
main() {
int z = 3;
foo(z);
}1. main에서 시작해서 run-time stack 의 변화 모습을 그려보시오.
2. 프로그램 수행 중에 생 성되는 frame의 순간-최 대 갯수를 구하시오.
