return-address stack: 같은 return이 이번 호출자에게 돌아가는 법
한 함수의 return 명령은 늘 같은 주소에 있다. 그런데 돌아갈 목적지는 그 함수를 어디서 호출했느냐에 따라 달라진다. return PC마다 마지막 목적지 하나를 기억하면, 호출 위치가 바뀔 때마다 이전 호출자의 주소를 따라갈 수 있다. return-address stack, RAS는 이 문제에 호출 순서라는 정보를 사용한다.
RAS에 저장하는 것은 함수의 시작 주소가 아니다. 호출을 끝내고 돌아와야 할 주소다. 정상적인 중첩 호출이 마지막 호출부터 돌아오는 순서를 이용하면 같은 return 명령에도 그때그때 맞는 목적지를 제공할 수 있다.
같은 return에 붙은 두 목적지
가상의 프로그램에서 0x100의 4바이트 call이 함수 f를 호출하고, f의 return은 0x40C에 있다고 하자. 이 호출이 돌아갈 주소는 0x104다. 다음에는 0x200의 call이 같은 f를 호출하면 동일한 return 0x40C의 목적지는 0x204다.
이 두 호출 위치가 번갈아 사용되면 return PC에 마지막 주소만 저장한 표는 0x104와 0x204를 번갈아 따라 배우게 된다. 이전 기록을 다음에 그대로 사용하면 틀린다. 반면 RAS는 각 call을 예측하거나 확인한 시점에 이번 return 주소를 push한다. f에서 돌아올 때 top을 목적지로 사용하고 pop하면 이번 호출자의 주소를 얻는다.
중첩 호출도 같은 원리다. 0x100에서 f를 호출하여 0x104를 push하고, f 안의 0x404에서 g를 호출하여 0x408을 push한다고 하자. g가 먼저 return하면 top인 0x408로 돌아간다. f가 이어 return하면 남은 0x104로 돌아간다. 이 순서에서는 각 함수의 return PC가 다르든 같든 중요한 정보는 아직 끝나지 않은 호출의 순서다.
BOOM의 NLP 문서는 return을 예측할 때 목적지를 RAS에서 받고, fetch 단계에서 해독한 call과 return에 따라 push와 pop을 수행한다고 설명한다. 예측할 목적지를 제공하는 일과 실제 레지스터 값으로 return을 실행하는 일은 구분된다. BOOM NLP, Predictions 및 RAS Updates
무엇을 call이라고 알아볼까
RISC-V에는 별도의 call opcode가 있는 것이 아니다. JAL과 JALR의 레지스터 사용으로 호출과 복귀의 힌트를 준다. 규범 원문은 JAL의 rd가 x1 또는 x5일 때 RAS에 return 주소를 push하는 조건을 설명한다. JALR는 rd와 rs1이 이 link register들을 어떻게 사용하는지에 따라 push, pop, 또는 둘 다를 제안한다. RISC-V RV32I, return-address prediction hints
따라서 모든 JALR를 return으로 보아 pop하면 안 된다. 일반적인 간접 점프에도 쓰이고, 간접 call에도 쓰인다. 표준 calling convention의 ret는 rd=x0, rs1=x1, immediate=0인 JALR로 표현되지만, 회로의 힌트 판정은 원문에 정의된 레지스터 관계를 따라야 한다. 다른 link register를 쓰는 경우와 두 register를 교환하는 제어 흐름도 고려한다.
저장할 다음 주소의 길이도 맞아야 한다. 앞의 예는 4바이트 call이라 PC+4를 썼다. compressed call을 지원하면 PC+2인 경우도 있다. 명령을 32비트 내부 표현으로 확장했다고 원래 길이까지 4바이트가 되는 것은 아니다. 이 길이를 잃으면 스택 순서가 정확해도 복귀 주소 자체가 틀린다. RISC-V Zca, C.JAL·C.JALR의 link 주소
순서에 맞지 않는 흐름과 유한한 깊이
RAS는 하드웨어에 무한히 깊은 스택을 만들지는 않는다. 예를 들어 두 주소만 보관하고 오래된 항목을 버리는 방식에서 호출이 세 겹 중첩되면 첫 호출의 주소가 남지 않을 수 있다. 마지막 두 복귀를 맞혔다고 첫 호출의 복귀까지 맞힌다고 보장할 수 없다. 실제 overflow와 underflow의 처리는 구현마다 다르므로 부족한 상태를 어떻게 표시하고 대체 예측을 쓰는지 확인해야 한다.
프로그램이 일반적인 호출·복귀 순서를 벗어나도 문제가 생길 수 있다. 함수 호출을 tail jump로 바꾸거나, 예외와 문맥 전환을 거치거나, 일반적인 stack return을 건너뛰는 제어 흐름에서는 어떤 동작을 RAS에 반영할지 정해야 한다. 단지 코드에 함수 이름이 있다는 사실만으로 push와 pop의 균형이 맞지는 않는다.
투기적인 경로에서 call을 보고 스택을 미리 바꾼다면, 그 경로가 취소될 때 이전 상태를 복구해야 한다. 스택 pointer만 되돌리는 것으로 충분한지는 저장 항목을 덮어썼는지에 달려 있다. 더 깊은 스택은 깊이 부족을 줄일 수 있지만 잘못된 경로의 업데이트나 잘못된 call 식별을 해결해 주지는 않는다.
RAS의 정확도는 중첩 깊이, 원래 명령 길이, 호출 힌트의 식별과 경로 취소를 함께 놓고 평가하는 것이 좋다. 독립적인 return 주소 두 개를 번갈아 쓰는 테스트만 통과한 뒤 복잡한 중첩까지 검증됐다고 읽을 수 없다.
return-address stack이 같은 return 명령의 여러 목적지를 구분하는 이유는 과거 주소를 더 많이 외워서만이 아니다. 아직 끝나지 않은 호출의 순서를 목적지 선택에 사용하기 때문이다. 그 순서와 주소를 온전히 유지할 때, PC 하나만으로 보이지 않던 호출자의 문맥이 예측에 드러난다.