Loop Optimization

Compiler Backend 동작

1) Register allocation => 무한개의 virtual register를 유한개의 실제 register에 map

2) Optimmizer => programmer나 frontend의 비효율 제거

3) Scheduler =< pseudo-assembly 적용하고 target machine에 맞춤

 

대부분의 execution time이 loop에서 소모되기 때문에 loop 최적화가 매우 중요

loop is single entry, multiple exit region

 

Natural loop

=> 단일 entry point를 가진다. 그리고 이 entry point node(header)가 그아래 형성된 모든 노드를 dominate(지배)함

 

Loop invariant code Motion => loop에서 변하지 않는 녀석을 loop 밖으로 이동

Induction variable Detection => 변수에서의 모든 변화가 단지 증가 또는 감소가 constant value로 발생 하는 경우

 

Loop Fusion

=> 같은 range의 여러개의 loop를 하나로 합침

=> instruction cache miss 등이 늘어나서 오히려 성능이 줄수 있음

=> loop carried true dependency가 없어야 함

 

Loop Fission

=> loop body를 나누는 것
=> locality of reference에 좋음, Instruction caceh ratio를 올림

=> task parallelism에 좋음

 

Loop Splitting/Peeling

=> iteration space로 나누는 것

=> loop peeling: 첫번째 한두 iteration만 나누는 것

 

Loop Sectioning 

=> loop을 두개의 nested loop으로 만들어서 vectorization을 좋게 하기 위한 목적

 

Loop Interchange

=> nested된 두개의 loop의 순서를 바꿈

=> 각 loop가 independent 해야되며 같은 dependence direction을 가져야 됨