내 컴파일러에 대한 테일 호출 최적화를 어느 단계에서 구현해야합니까?

저는 Racket에서 스킴과 유사한 언어를 사용하여 작은 컴파일러를 작성했습니다. 이제 컴파일러에 TCO를 구현하고 싶습니다.내 컴파일러에 대한 테일 호출 최적화를 어느 단계에서 구현해야합니까?

제 아이디어는 인터럽트 표현으로 변환하기 전에 테일 호출을 감지해야합니다. 그러나이 page에서 TCO는 일반적으로 어셈블리 레벨에서 call을 jmp으로 변경하여 처리하는 것처럼 보입니다. 나는 여기에 좀 붙어있다.

의견을 보내 주시면 감사하겠습니다.

EDIT : 내 대상은 x86 어셈블리 코드입니다. 사용 된 IR은 세 개의 주소 코드입니다.

그리고 여기 내 컴파일러 12 개 패스하고, 패턴 화 된 패스는 내가 소스 코드 나에게

(define test-passes 
(list 
`("uniquify"    ,(uniquify '())         ,interp-scheme) 
`("reveal-functions"  ,(reveal-functions '())       ,interp-F) 
`("convert-to-closures"  ,convert-to-closure        ,interp-F) 
`("expose allocation"  ,expose-allocation        ,interp-F) 
`("flatten"     ,(flatten #f)          ,interp-C) 
`("instruction selection" ,select-instructions        ,interp-x86) 
`("liveness analysis"  ,(uncover-live (void))       ,interp-x86) 
`("build interference"  ,(build-interference (void) (void) (void) (void)) ,interp-x86) 
`("allocate register"  ,allocate-registers        ,interp-x86) 
`("lower-conditionals"  ,lower-conditionals        ,interp-x86) 
`("patch-instructions"  ,patch-instructions        ,interp-x86) 
`("x86"      ,print-x86          #f) 
))

출처

2016-09-30 齐天大圣

ANF (또는 CPS)에서 수행하는 것과 달리 IR에 들어가기 전에 왜 이것을해야합니까? –

[ANF] (https://en.wikipedia.org/wiki/Administrative_Normal_Form), [CPS] (https://en.wikipedia.org/wiki/Continuation-passing_style), [IR] (https : // ko .wikipedia.org/wiki/Intermediate_representation). –

아 그래, 링크를 포함 해 주셔서 감사합니다. –

IR 변환을 경우, 장소는 꼬리 호출 최적화를 구현하는 것의 과정을 시작하는 것입니다 명시 적 언어 구조를 통해이를 감지합니다. 이는 접근 방식이 Clojure's recur operator 인 것과 유사 할 수 있습니다. 이는 이것이 작동 할 수있는 가장 간단한 이유이기 때문입니다. 이렇게하면 꼬리 호출을 인식하는 하나의 프로 시저와 꼬리 호출을 구현하는 다른 프로 시저가 생성됩니다.

꼬리 호출을 자동으로 인식하기위한 추가 개발은 첫 번째 절차의 수정이됩니다. 최적화를 개선하기위한 추가 개발은 두 번째 절차의 수정이됩니다. 각각의 개발은 독립적으로 일어날 수 있습니다.

출처

2016-09-30 19:01:43

꼬리 재귀의 특별한 경우와 함께 일반적으로 꼬리 호출을 혼란스럽게합니다. –

답변은 컴파일 대상에 따라 다릅니다.

당신이 다음 (압둘라지즈 Ghuloum에 의해 "컴파일러 건설하기 위해 증분 접근"예를 들어, 참조 코드 생성기에 꼬리 호출을 처리 할 수있는 어셈블러 (또는 기계 코드)로 컴파일하는 경우.

대상 언어 인 경우 C와 비슷한 (즉, 빌드 컨텍스트를 호출하는 경우) 컴파일러를 원하는 방식에 따라 몇 가지 옵션이 있습니다. 다른 것들은 ANF와 CPS를 중간 폼으로 언급했습니다. 또한 트램펄린을 도입 할 수도 있습니다. "Scheme Implementation Techniques "by Felix Winkelman (전략 목록)

대상 언어가 꼬리 재귀를 지원하는 경우 Scheme 호출이 tra 인 전략 사용을 고려하십시오 대상 언어로 호출에 포함됩니다.

어쨌든 : Scheme을 컴파일하는 데 관심이 있다면, Christian Queinnec의 LiSP : Lisp 복사본을 작은 조각에 담아서 주저하지 마십시오.

출처

2016-09-30 21:16:47 soegaard

대상이 x86 어셈블리 인 경우 어떻게해야합니까? 이미 IR로 3 개의 주소 코드를 사용했습니다. 여전히 ANF 나 CPS를 사용할 수 있습니까? (미안하지만 바보 같지만 어디에서 시작해야할지 모르겠 음) –

그런 경우 "컴파일러 구성에 대한 점진적인 접근"을 살펴보십시오. 또한 x86 작업 코드에 대한 Intels 매뉴얼의 사본을 얻고 함수 호출에 관한 섹션을 연구하십시오. (정확하게 기억한다면 Aziz의 논문에 참고 자료가 있습니다.) – soegaard

꼬리 호출을 아주 일찍, 이상하게도 람다 해제 직후에 감지 할 수 있습니다 (명시 적으로 말하지 않았지만 클로저로 변환 통과가 그럴 가능성이 있음).

그런 다음 꼬리로 표시된 호출은 나중 단계에서 낮출 수 있지만 점프하는 것만 큼 간단하지는 않습니다 - 먼저 스택 프레임을 정리해야합니다 (함수 인수를 전달하기 위해 스택을 사용하는 경우).). 인수를 전달하기 위해서만 레지스터를 사용하는 것이 더 쉽습니다.

출처

2016-10-02 12:49:10

내 컴파일러에 대한 테일 호출 최적화를 어느 단계에서 구현해야합니까?

답변

관련 문제