[optimization] GHC가 확실하게 수행 할 수있는 최적화 방법은 무엇입니까?

이 GHC Trac 페이지 는 패스를 상당히 잘 설명합니다. 이 페이지 는 Trac Wiki의 대부분과 마찬가지로 최적화 순서를 설명합니다.

구체적으로, 가장 좋은 방법은 특정 프로그램이 어떻게 컴파일되는지 보는 것입니다. 어떤 최적화가 수행되고 있는지 확인하는 가장 좋은 방법은 -v플래그를 사용하여 프로그램을 자세하게 컴파일하는 것 입니다. 내 컴퓨터에서 찾을 수있는 첫 번째 Haskell 조각을 예로 들어 보자.

Glasgow Haskell Compiler, Version 7.4.2, stage 2 booted by GHC version 7.4.1
Using binary package database: /usr/lib/ghc-7.4.2/package.conf.d/package.cache
wired-in package ghc-prim mapped to ghc-prim-0.2.0.0-7d3c2c69a5e8257a04b2c679c40e2fa7
wired-in package integer-gmp mapped to integer-gmp-0.4.0.0-af3a28fdc4138858e0c7c5ecc2a64f43
wired-in package base mapped to base-4.5.1.0-6e4c9bdc36eeb9121f27ccbbcb62e3f3
wired-in package rts mapped to builtin_rts
wired-in package template-haskell mapped to template-haskell-2.7.0.0-2bd128e15c2d50997ec26a1eaf8b23bf
wired-in package dph-seq not found.
wired-in package dph-par not found.
Hsc static flags: -static
*** Chasing dependencies:
Chasing modules from: *SleepSort.hs
Stable obj: [Main]
Stable BCO: []
Ready for upsweep
  [NONREC
      ModSummary {
         ms_hs_date = Tue Oct 18 22:22:11 CDT 2011
         ms_mod = main:Main,
         ms_textual_imps = [import (implicit) Prelude, import Control.Monad,
                            import Control.Concurrent, import System.Environment]
         ms_srcimps = []
      }]
*** Deleting temp files:
Deleting:
compile: input file SleepSort.hs
Created temporary directory: /tmp/ghc4784_0
*** Checking old interface for main:Main:
[1 of 1] Compiling Main             ( SleepSort.hs, SleepSort.o )
*** Parser:
*** Renamer/typechecker:
*** Desugar:
Result size of Desugar (after optimization) = 79
*** Simplifier:
Result size of Simplifier iteration=1 = 87
Result size of Simplifier iteration=2 = 93
Result size of Simplifier iteration=3 = 83
Result size of Simplifier = 83
*** Specialise:
Result size of Specialise = 83
*** Float out(FOS {Lam = Just 0, Consts = True, PAPs = False}):
Result size of Float out(FOS {Lam = Just 0,
                              Consts = True,
                              PAPs = False}) = 95
*** Float inwards:
Result size of Float inwards = 95
*** Simplifier:
Result size of Simplifier iteration=1 = 253
Result size of Simplifier iteration=2 = 229
Result size of Simplifier = 229
*** Simplifier:
Result size of Simplifier iteration=1 = 218
Result size of Simplifier = 218
*** Simplifier:
Result size of Simplifier iteration=1 = 283
Result size of Simplifier iteration=2 = 226
Result size of Simplifier iteration=3 = 202
Result size of Simplifier = 202
*** Demand analysis:
Result size of Demand analysis = 202
*** Worker Wrapper binds:
Result size of Worker Wrapper binds = 202
*** Simplifier:
Result size of Simplifier = 202
*** Float out(FOS {Lam = Just 0, Consts = True, PAPs = True}):
Result size of Float out(FOS {Lam = Just 0,
                              Consts = True,
                              PAPs = True}) = 210
*** Common sub-expression:
Result size of Common sub-expression = 210
*** Float inwards:
Result size of Float inwards = 210
*** Liberate case:
Result size of Liberate case = 210
*** Simplifier:
Result size of Simplifier iteration=1 = 206
Result size of Simplifier = 206
*** SpecConstr:
Result size of SpecConstr = 206
*** Simplifier:
Result size of Simplifier = 206
*** Tidy Core:
Result size of Tidy Core = 206
writeBinIface: 4 Names
writeBinIface: 28 dict entries
*** CorePrep:
Result size of CorePrep = 224
*** Stg2Stg:
*** CodeGen:
*** CodeOutput:
*** Assembler:
'/usr/bin/gcc' '-fno-stack-protector' '-Wl,--hash-size=31' '-Wl,--reduce-memory-overheads' '-I.' '-c' '/tmp/ghc4784_0/ghc4784_0.s' '-o' 'SleepSort.o'
Upsweep completely successful.
*** Deleting temp files:
Deleting: /tmp/ghc4784_0/ghc4784_0.c /tmp/ghc4784_0/ghc4784_0.s
Warning: deleting non-existent /tmp/ghc4784_0/ghc4784_0.c
link: linkables are ...
LinkableM (Sat Sep 29 20:21:02 CDT 2012) main:Main
   [DotO SleepSort.o]
Linking SleepSort ...
*** C Compiler:
'/usr/bin/gcc' '-fno-stack-protector' '-Wl,--hash-size=31' '-Wl,--reduce-memory-overheads' '-c' '/tmp/ghc4784_0/ghc4784_0.c' '-o' '/tmp/ghc4784_0/ghc4784_0.o' '-DTABLES_NEXT_TO_CODE' '-I/usr/lib/ghc-7.4.2/include'
*** C Compiler:
'/usr/bin/gcc' '-fno-stack-protector' '-Wl,--hash-size=31' '-Wl,--reduce-memory-overheads' '-c' '/tmp/ghc4784_0/ghc4784_0.s' '-o' '/tmp/ghc4784_0/ghc4784_1.o' '-DTABLES_NEXT_TO_CODE' '-I/usr/lib/ghc-7.4.2/include'
*** Linker:
'/usr/bin/gcc' '-fno-stack-protector' '-Wl,--hash-size=31' '-Wl,--reduce-memory-overheads' '-o' 'SleepSort' 'SleepSort.o' '-L/usr/lib/ghc-7.4.2/base-4.5.1.0' '-L/usr/lib/ghc-7.4.2/integer-gmp-0.4.0.0' '-L/usr/lib/ghc-7.4.2/ghc-prim-0.2.0.0' '-L/usr/lib/ghc-7.4.2' '/tmp/ghc4784_0/ghc4784_0.o' '/tmp/ghc4784_0/ghc4784_1.o' '-lHSbase-4.5.1.0' '-lHSinteger-gmp-0.4.0.0' '-lgmp' '-lHSghc-prim-0.2.0.0' '-lHSrts' '-lm' '-lrt' '-ldl' '-u' 'ghczmprim_GHCziTypes_Izh_static_info' '-u' 'ghczmprim_GHCziTypes_Czh_static_info' '-u' 'ghczmprim_GHCziTypes_Fzh_static_info' '-u' 'ghczmprim_GHCziTypes_Dzh_static_info' '-u' 'base_GHCziPtr_Ptr_static_info' '-u' 'base_GHCziWord_Wzh_static_info' '-u' 'base_GHCziInt_I8zh_static_info' '-u' 'base_GHCziInt_I16zh_static_info' '-u' 'base_GHCziInt_I32zh_static_info' '-u' 'base_GHCziInt_I64zh_static_info' '-u' 'base_GHCziWord_W8zh_static_info' '-u' 'base_GHCziWord_W16zh_static_info' '-u' 'base_GHCziWord_W32zh_static_info' '-u' 'base_GHCziWord_W64zh_static_info' '-u' 'base_GHCziStable_StablePtr_static_info' '-u' 'ghczmprim_GHCziTypes_Izh_con_info' '-u' 'ghczmprim_GHCziTypes_Czh_con_info' '-u' 'ghczmprim_GHCziTypes_Fzh_con_info' '-u' 'ghczmprim_GHCziTypes_Dzh_con_info' '-u' 'base_GHCziPtr_Ptr_con_info' '-u' 'base_GHCziPtr_FunPtr_con_info' '-u' 'base_GHCziStable_StablePtr_con_info' '-u' 'ghczmprim_GHCziTypes_False_closure' '-u' 'ghczmprim_GHCziTypes_True_closure' '-u' 'base_GHCziPack_unpackCString_closure' '-u' 'base_GHCziIOziException_stackOverflow_closure' '-u' 'base_GHCziIOziException_heapOverflow_closure' '-u' 'base_ControlziExceptionziBase_nonTermination_closure' '-u' 'base_GHCziIOziException_blockedIndefinitelyOnMVar_closure' '-u' 'base_GHCziIOziException_blockedIndefinitelyOnSTM_closure' '-u' 'base_ControlziExceptionziBase_nestedAtomically_closure' '-u' 'base_GHCziWeak_runFinalizzerBatch_closure' '-u' 'base_GHCziTopHandler_flushStdHandles_closure' '-u' 'base_GHCziTopHandler_runIO_closure' '-u' 'base_GHCziTopHandler_runNonIO_closure' '-u' 'base_GHCziConcziIO_ensureIOManagerIsRunning_closure' '-u' 'base_GHCziConcziSync_runSparks_closure' '-u' 'base_GHCziConcziSignal_runHandlers_closure'
link: done
*** Deleting temp files:
Deleting: /tmp/ghc4784_0/ghc4784_1.o /tmp/ghc4784_0/ghc4784_0.s /tmp/ghc4784_0/ghc4784_0.o /tmp/ghc4784_0/ghc4784_0.c
*** Deleting temp dirs:
Deleting: /tmp/ghc4784_0

*** Simplifier:모든 최적화 단계가 발생 하는 처음 부터 끝까지 살펴보면 꽤 많이 볼 수 있습니다.

우선 Simplifier는 거의 모든 단계에서 실행됩니다. 이렇게하면 많은 패스를 훨씬 쉽게 작성할 수 있습니다. 예를 들어 많은 최적화를 구현할 때 변경 사항을 수동으로 수행하는 대신 전파하기 위해 다시 쓰기 규칙을 작성하기 만하면됩니다. 단순화 기는 인라인 및 퓨전을 포함한 여러 간단한 최적화를 포함합니다. 내가 아는 주요 제한 사항은 GHC가 재귀 함수를 인라인하지 않고 융합이 작동하도록 이름을 올바르게 지정해야한다는 것입니다.

다음으로 수행 된 모든 최적화의 전체 목록이 표시됩니다.

• 전문화

  전문화의 기본 아이디어는 함수가 호출되는 위치를 식별하고 다형성이 아닌 함수의 버전을 작성하여 다형성 및 과부하를 제거하는 것입니다. 이들은 호출되는 유형에 따라 다릅니다. 컴파일러에게 SPECIALISEpragma를 사용하여이를 수행하도록 지시 할 수도 있습니다 . 예를 들어, 계승 함수를 수행하십시오.

  fac :: (Num a, Eq a) => a -> a
  fac 0 = 1
  fac n = n * fac (n - 1)

  컴파일러는 사용할 곱셈의 속성을 알지 못하므로이를 최적화 할 수 없습니다. 그러나에 사용되는 것으로 확인 Int되면 이제 유형 만 다른 새 버전을 만들 수 있습니다.

  fac_Int :: Int -> Int
  fac_Int 0 = 1
  fac_Int n = n * fac_Int (n - 1)

  다음으로, 아래 언급 된 규칙이 실행될 수 있으며 Int, 원래보다 훨씬 빠른 unboxed에서 작동하는 것으로 끝납니다 . 전문화를 보는 또 다른 방법은 유형 클래스 사전 및 유형 변수에 대한 부분 적용입니다.

  소스는 여기에서 노트의 부하를 가지고있다.

• 플로트 아웃

  편집 : 나는 분명히 이것을 전에 오해했습니다. 내 설명이 완전히 바뀌 었습니다.

  이것의 기본 아이디어는 함수에서 반복해서는 안되는 계산을 옮기는 것입니다. 예를 들어, 우리가 이것을 가지고 있다고 가정하십시오 :

  \x -> let y = expensive in x+y

  위의 람다에서는 함수가 호출 될 때마다 y다시 계산됩니다. 떠 다니는 더 나은 기능은

  let y = expensive in \x -> x+y

  프로세스를 용이하게하기 위해 다른 변환이 적용될 수있다. 예를 들어, 다음이 발생합니다.

   \x -> x + f 2
   \x -> x + let f_2 = f 2 in f_2
   \x -> let f_2 = f 2 in x + f_2
   let f_2 = f 2 in \x -> x + f_2

  다시 반복 계산이 저장됩니다.

  소스는 이 경우에 매우 읽을 수 있습니다.

  현재 인접한 두 람다 사이의 바인딩은 플로팅되지 않습니다. 예를 들어, 이것은 발생하지 않습니다 :

  \x y -> let t = x+x in ...

  가다

   \x -> let t = x+x in \y -> ...

• 안쪽으로 뜬다

  소스 코드 인용

  주요 목적은 floatInwards케이스의 브랜치에 떠 다니는 것이므로 할당하지 않고 스택에 저장 한 다음 선택한 브랜치에서 필요하지 않은 것을 발견합니다.

  예를 들어 다음과 같은 표현이 있다고 가정합니다.

  let x = big in
      case v of
          True -> x + 1
          False -> 0

  로 v평가 되면 아마도 큰 썽크 인 False을 할당함으로써 x시간과 공간을 낭비한 것입니다. 안쪽으로 부동하면 이것을 수정하여 다음을 생성합니다.

  case v of
      True -> let x = big in x + 1
      False -> let x = big in 0

  을 사용한 단순화로 대체됩니다.

  case v of
      True -> big + 1
      False -> 0

  이 문서 는 다른 주제를 다루지 만 상당히 명확한 소개를 제공합니다. 이름에도 불구하고 부동 및 부동은 두 가지 이유로 무한 루프에 빠지지 않습니다.

  1. float in float는 case문장 으로 들어가고 float out은 함수를 처리합니다.
  2. 고정 된 순서의 패스가 있으므로 무한대로 번갈아 가면 안됩니다.

• 수요 분석

  수요 분석 또는 엄격 성 분석은 변형이 적고 이름에서 알 수 있듯이 정보 수집 단계가 더 많습니다. 컴파일러는 항상 인수 (또는 적어도 일부)를 평가하는 함수를 찾고 필요에 따라 호출하는 대신 값별 호출을 사용하여 해당 인수를 전달합니다. 썽크의 오버 헤드를 피하기 때문에 종종 훨씬 빠릅니다. Haskell의 많은 성능 문제는이 패스 실패 또는 코드가 충분히 엄격하지 않아 발생합니다. 간단한 예는를 사용하는 것의 차이점입니다 foldr.foldl 및foldl'정수 목록을 합산하려면-첫 번째는 스택 오버플로를 유발하고 두 번째는 힙 오버플로를 유발하며 마지막은 엄격함으로 인해 잘 실행됩니다. 이것은 아마도 가장 이해하기 쉽고 가장 잘 설명되어 있습니다. 나는 다형성과 CPS 코드가 종종 이것을 패배한다고 생각합니다.

• 작업자 래퍼 바인딩

  작업자 / 래퍼 변환의 기본 아이디어는 간단한 구조에서 긴 루프를 수행하여 끝에서 해당 구조로 변환하는 것입니다. 예를 들어,이 함수를 사용하면 숫자의 계승을 계산할 수 있습니다.

  factorial :: Int -> Int
  factorial 0 = 1
  factorial n = n * factorial (n - 1)

  IntGHC 에서 정의를 사용하면

  factorial :: Int -> Int
  factorial (I# 0#) = I# 1#
  factorial (I# n#) = I# (n# *# case factorial (I# (n# -# 1#)) of
      I# down# -> down#)

  코드가 I#s에서 어떻게 다루어 졌는지 주목하십시오 . 다음을 수행하여 제거 할 수 있습니다.

  factorial :: Int -> Int
  factorial (I# n#) = I# (factorial# n#)
  
  factorial# :: Int# -> Int#
  factorial# 0# = 1#
  factorial# n# = n# *# factorial# (n# -# 1#)

  이 특정 예제는 SpecConstr에 의해 수행 될 수도 있지만 작업자 / 래퍼 변환은 수행 할 수있는 작업에서 매우 일반적입니다.

• 공통 하위 표현식

  이것은 엄격도 분석과 같이 매우 효과적인 또 다른 간단한 최적화입니다. 기본 개념은 동일한 두 개의 표현식이있는 경우 동일한 값을 갖게된다는 것입니다. 예를 들어 fib피보나치 수 계산기 인 경우 CSE는

  fib x + fib x

  으로

  let fib_x = fib x in fib_x + fib_x

  계산을 반으로 줄입니다. 불행히도, 이것은 때때로 다른 최적화를 방해 할 수 있습니다. 또 다른 문제는 두 표현이 같은 장소에 있어야하며 구문 적으로 동일해야하며 값이 같지 않아야한다는 것입니다. 예를 들어 CSE는 많은 인라인없이 다음 코드에서 실행되지 않습니다.

  x = (1 + (2 + 3)) + ((1 + 2) + 3)
  y = f x
  z = g (f x) y

  그러나 llvm을 통해 컴파일하는 경우 Global Value Numbering 패스로 인해이 중 일부가 결합 될 수 있습니다.

• 해방 사건

  이것은 코드 폭발을 일으킬 수 있다는 사실 외에도 끔찍하게 문서화 된 변환 인 것 같습니다. 여기 내가 찾은 작은 문서의 재구성 된 (그리고 약간 다시 작성된) 버전이 있습니다.

  이 모듈은를 Core살펴보고 case자유 변수를 찾습니다 . case재귀 호출 경로에 비어있는 변수 가 있으면 재귀 호출이 펼치기로 바뀝니다. 예를 들어

  f = \ t -> case v of V a b -> a : f t

  내부 f가 교체됩니다. 만들다

  f = \ t -> case v of V a b -> a : (letrec f = \ t -> case v of V a b -> a : f t in f) t

  섀도 잉의 필요성에 유의하십시오. 단순화, 우리는 얻는다

  f = \ t -> case v of V a b -> a : (letrec f = \ t -> a : f t in f t)

  에서보다 프로젝션 할 필요없이 ainner 내부에서 자유 로워 지기 때문에 더 나은 코드 letrec입니다 v. 참고로이 상품의 자유 변수 를 다루는 SpecConstr 달리, 인수 알려진 형태이다.

  SpecConstr에 대한 자세한 내용은 아래를 참조하십시오.

• SpecConstr-다음과 같은 프로그램을 변환합니다

  f (Left x) y = somthingComplicated1
  f (Right x) y = somethingComplicated2

  으로

  f_Left x y = somethingComplicated1
  f_Right x y = somethingComplicated2
  
  {-# INLINE f #-}
  f (Left x) = f_Left x
  f (Right x) = f_Right x

  확장 된 예로 다음과 같은 정의를 사용하십시오 last.

  last [] = error "last: empty list"
  last (x:[]) = x
  last (x:x2:xs) = last (x2:xs)

  우리는 먼저 그것을

  last_nil = error "last: empty list"
  last_cons x [] = x
  last_cons x (x2:xs) = last (x2:xs)
  
  {-# INLINE last #-}
  last [] = last_nil
  last (x : xs) = last_cons x xs

  다음으로 단순화가 실행되고

  last_nil = error "last: empty list"
  last_cons x [] = x
  last_cons x (x2:xs) = last_cons x2 xs
  
  {-# INLINE last #-}
  last [] = last_nil
  last (x : xs) = last_cons x xs

  우리는 목록의 앞면을 반복적으로 권투하고 unboxing하지 않기 때문에 프로그램이 더 빨라졌습니다. 또한 새로운보다 효율적인 정의를 실제로 사용할 수있을뿐만 아니라 재귀적인 정의를 향상시킬 수 있으므로 인라이닝이 중요합니다.

  SpecConstr은 여러 휴리스틱에 의해 제어됩니다. 논문에 언급 된 내용은 다음과 같습니다.

  1. 람다는 명백하고 arity는 a입니다.
  2. 오른쪽은 “충분히 작은”플래그로 제어되는 것입니다.
  3. 이 함수는 재귀 적이며 특수 호출이 오른쪽에 사용됩니다.
  4. 함수에 대한 모든 인수가 있습니다.
  5. 적어도 하나의 인수는 생성자 응용 프로그램입니다.
  6. 이 주장은 함수 어딘가에서 사례 분석됩니다.

  그러나 휴리스틱은 거의 확실하게 변경되었습니다. 실제로, 논문은 대안적인 여섯 번째 휴리스틱을 언급합니다 :

  인수에 전문 x경우에만 x됩니다 만 a로 자세히 조사 case하고, 일반 함수에 전달되지 않았거나 결과의 일부로 반환.

이것은 매우 작은 파일 (12 줄)이므로 많은 최적화를 유발하지는 않았을 것입니다. 또한 왜 패스를 선택했는지 그리고 왜 순서대로 넣었는지 알려주지 않습니다.

답변

(sum xs + 1) / (sum xs + 2)

let s = sum xs in (s+1)/(s+2)

foo (0:_ ) = "zero"
foo (1:_ ) = "one"
foo (_:xs) = foo xs
foo (  []) = "end"

foo xs =
  case xs of
    y:ys ->
      case y of
        0 -> "zero"
        1 -> "one"
        _ -> foo ys
    []   -> "end"

map g . map f

{-# RULES "map/map" forall f g xs. map f (map g xs) = map (f.g) xs #-}

let v = rhs
    l = \x-> v + x
in map l [1..100]