Goals and limits

• Goals
  • minimize number of instructions
    • 1번 이상의 연산 금지
    • 필요없는 연산 한번에 하기 금지
    • “느린” 연산 금지(곱하기, 나누기)
  • avoid waiting for memory
    • 레지스터에 다 넣어놓기
    • 캐시-친화적 패턴으로 메모리 관리하기
    • load from memory early, ONCE
  • avoid branching
    • 분기문 피하기
• limits
  • cannot improve algorithmic complexity
    • 물론 상수는 수십배 수백배 바꿀 수 있다.
  • 작동 방식에 변화가 생기면 안됨
    • edge case, exception 등을 놓쳐선 안된다

Two Kinds of Optimizations

• (참고) 최적화 종류
• local optimizations
  • inside single basic block
    • constant folding
    • strength reduction
    • dead code elimination
    • local CSE(common subexpression elimination)
• Global optimizations
  • entire controlflow graph
    • loop transformations
    • code motion
    • global CSE

Local Optimizations

• Constant folding 계산을 직접 해서 상수로 쓴다

  

• reduction in strength 연산자를 심플하게 바꾼다(곱셈, 나눗셈: “비싸다”)

  • 비트 시프트 연산 애용하기 16*x → x<<4

    • 그냥 곱셈은 3사이클이나 사용한다.

  • 곱셈 대신 덧셈으로 대체할수 있다면 대체하기

    

    ni를 n*i로 하는게 아니라 n씩 더한다.

• dead code elimination jetbrain rider에서 해주는 것이다

  • 실행되지 않을 분기문 삭제

  • 덮어씌워질 코드 삭제

    

• common subexpression elimination(CSE) jetbrain rider에서 해주는 것이다

  • 반복되는 접근 또는 연산 밖으로 빼내기

    

• share common subexpressions -o1 옵션으로 돌리면 자동으로 해준다. 표현식 일부분 겹치는 것을 재사용하는 느낌 (한번 곱해놓고 더하기 빼기만 하는 식으로)

  

• code motion

  • move calculations out of a loop 루프 내에서 최소의 연산만 한다.

    

    위와 같은 최적화는 -o1 옵션에서 자동으로 해준다.

• inlining

  • 함수를 호출되는 곳에 전부 집어 넣는다

    • 여러 가지 최적화를 하게 할 수 있다
    • 최적화를 하지 않고 그냥 넣으면 더 느려질 뿐이다(함수가 커져서)

    

    

    보면 pred를 통째로 func 안의 pred 자리에 전부 넣었다. 그 뒤에 최적화를 한다.

Example: Bubble Sort optimization

for (i = n-1; i>=1; i--){
	for(j=1; j<=i;j++){
		if(A[j] > A[j+1]){
			//swap
			temp = A[j]; 
			A[j] = A[j+1];
			A[j+1] = temp;
		}
	}
}

translated pseudocode