Branch Prediction

 

1. 관련문서

 

• RETBLEED: Arbitrary Speculative Code Execution with Return Instructions / 원문

 

2. 분기 예측

 

최근 CPU는 코드 예측 실행을 통해 지연¹원문에서 stalling으로 표현을 줄임으로써 전반적인 성능을 향상시킨다.

BPU(Branch Prediction Unit²분기 예측 유닛)는 실행 파이프라인의 앞쪽에 위치한다.

BPU가 직접 분기 또는 간접 분기를 만났을 때, 분기 예측기³branch predictor 한 세트를 사용하여 다음 명령의 주소를 예측한다.

x86 64비트 업계 표준에서 직접 분기는 조건 분기 또는 무조건 분기가 모두 가능하다.

하지만, 간접 분기는 항상 무조건이다.

 

아래 그림은 BPU를 단순화한 것이다.

BHB(Branch History Buffer⁴분기 히스토리 버퍼)는 과거에 실행한 분기의 흔적이다.

BPU는 기기 상태(PC 및 BHB 등)와 BTB(Branch Target Buffer⁵분기 위치 버퍼)를 통해 분기 위치를 예측한다.

리턴과 관련하여, 언더플로우 컨디션이 아니라면, 리턴 위치를 예측하기 위해 현재 RSB(Return Stack Buffer⁶리턴 스택 버퍼)의 TOS(Top Of Stack⁷스택 최상위) 포인터를 사용한다.

 

직접 분기 및 간접 분기 위치를 예측할 때, BTB를 사용한다.

BTB에는 해당 분기에서 분기할 수 있는 위치를 저장하고 있다.

BTB의 인덱싱은 마이크로 아키텍처에 따라 다르다.

다음 분기 위치를 정확하게 예측하기 위해, 현재 PC⁸Program Counter 및 BHB에 기록된 이전 분기와 같은 기기 상태를 사용한다.

Jann Horn은 스펙터를 연구할 때, 하스웰 마이크로 아키텍처의 BTB 인덱싱을 리버스 엔지니어링했다.⁹Reading privileged memory with a side-channel

그러나, 최신 인텔/AMD 마이크로 아키텍처에서는 다른 예측 스킴을 사용하기 때문에 위 정보는 유효하지 않다.¹⁰Teja Singh, Sundar Rangarajan, Deepesh John, Russell Schreiber, Spence Oliver, Rajit Seahra, and Alex Schaefer. 2.1 zen 2: The amd 7nm energy-efficient high-performance x86-64 microprocessor core. In ISSCC. IEEE, 2020.

 

직접 분기 및 간접 분기 예측 외에도, 최근 마이크로 아키텍처는 리턴 위치 예측에도 전용 스킴을 사용한다.

RSB는 다수 함수를 호출한 후 리턴 명령의 위치 주소를 예측하기 위해 마이크로 아키텍처 스택에 리턴 위치를 기록한다.

그러나, RSB의 용량이 제한되기 때문에 마이크로 아키텍처는 필요에 따라 다른 분기 예측 스킴을 사용할 수 있다.

일례로, 스카이레이크 마이크로 아키텍처는 RSB가 언더플로우될 때 다시 BTB로 예측하는 것으로 알려져 있다.¹¹Intel Corp. Retpoline: A Branch Target Injection Mitigation ¹²Anders Fogh. In debt to Retpoline ¹³David Woodhouse. LWN.net: Re: [RFC 09/10] x86/enter: Create macros to restrict/unrestrict Indirect Branch Speculation