높은 수준/시맨틱 최적화

Question

컴파일러를 작성하고 있으며 최적화에 대한 리소스를 찾고 있습니다. 기계 코드로 컴파일하고 있으므로 런타임시 모든 것이 문제가되지 않습니다.

내가 최근에 찾고 있던 것은 코드 최적화가 적고 의미 론적/고급 최적화입니다. 예를 들어:

free(malloc(400)); // should be completely optimized away

이러한 기능이 완전히 상환 되더라도 결국에는 없을 수없는 OS 메모리 기능을 호출 할 수 있습니다. 컴파일러에 특수 사례 규칙을 구축하지 않고도 그 진술을 완전히 제거 할 수 있기를 바랍니다. malloc 또 다른 기능입니다).

또 다른 예:

string Parenthesize(string str) {
    StringBuilder b; // similar to C#'s class of the same name
    foreach(str : ["(", str, ")"])
        b.Append(str);
    return b.Render();
}

이 상황에서 나는 초기화 할 수 있기를 원합니다 b의 능력 str.Length + 2 (기억을 낭비하지 않고 결과를 정확하게 유지하기에 충분합니다).

완전히 솔직히 말해서, 나는이 문제를 해결하기 위해 어디에서 시작 해야할지 전혀 모른다. 그래서 나는 어딘가에 시작하기를 바랐다. 비슷한 영역에서 작업이 있었습니까? 일반적인 의미에서 이와 같은 것을 구현 한 컴파일러가 있습니까?

Answer 1

2 개 이상의 작업에서 최적화를하려면이 두 작업의 대수 관계를 이해해야합니다. 문제 영역에서 작업을 보면 종종 그러한 관계가 있습니다.

자유롭고 malloc은 저장 할당 도메인의 역전이기 때문에 무료 (Malloc (400))가 가능합니다. 많은 작업에는 반전이 있고 컴파일러가 역전을 가르치고, 하나의 데이터 흐름의 결과가 무조건 다른 것의 결과가 필요하다는 것을 보여줍니다. 당신은 당신의 역이 실제로 반전이며 어딘가에 놀라운 일이지 않도록해야합니다. a/x*x는 값 A처럼 보이지만 x는 0이면 트랩을 얻습니다. 트랩에 신경 쓰지 않으면 역입니다. 트랩에 관심이 있다면 최적화가 더 복잡합니다. (if (x == 0) 그런 다음 Trap () else a) Divide가 비싸다고 생각하면 여전히 좋은 최적화입니다.

다른 "대수"관계가 가능합니다. 예를 들어, 변수를 제로화 (동일한 값으로 반복적으로 설정) 등이있을 수 있습니다. 하나의 피연산자가 ID 요소처럼 작용하는 작업이 있습니다. x+0 ==> x 0의 경우 x와 0이 행렬이라면 여전히 사실이며 큰 시간 절약입니다.

코드가 수행하는 작업에 대해 추상적으로 추론 할 수있을 때 다른 최적화가 발생할 수 있습니다. "추상 해석"은 결과를 다양한 흥미로운 빈으로 분류하여 값에 대한 추론을위한 일련의 기술입니다 (예 :이 정수는 알려지지, 0, 음수 또는 긍정적입니다). 이를 위해서는 도움이되는 쓰레기통을 결정한 다음 각 지점에서 추상적 값을 계산해야합니다. 이것은 카테고리에 대한 테스트가있을 때 (예 : "if (x <0) {..."에 유용하며 X가 0보다 작다는 것을 추상적으로 알고 있습니다. 조건부를 최적화 할 수 있습니다.

또 다른 방법은 계산이 상징적으로 수행하는 일을 정의하고 계산을 시뮬레이션하여 결과를 확인하는 것입니다. 이것이 필요한 버퍼의 유효 크기를 계산 한 방법입니다. 루프가 시작되기 전에 버퍼 크기를 상징적으로 계산하고 모든 반복에 대한 루프를 실행하는 효과를 시뮬레이션했습니다. 이를 위해 프로그램 특성을 나타내는 기호 공식을 구성하고, 그러한 공식을 구성하며, 무례하게 복잡 할 때 그러한 공식을 단순화 할 수 있어야합니다 (추상 해석 체계에 페이드의 종류). 또한 위에서 설명한 대수 특성을 고려하기 위해 이러한 상징적 계산을 원합니다. 이를 잘 수행하는 도구는 공식을 구성하는 데 능숙하며 프로그램 변환 시스템은 종종 이에 대한 좋은 기초입니다. 이를 수행하는 데 사용할 수있는 하나의 소스 간 프로그램 변환 시스템은 다음과 같습니다. DMS 소프트웨어 리엔지니어링 툴킷.

어려운 것은 어떤 최적화가 가치가 있는지 결정하는 것입니다. 왜냐하면 당신은 대가를 지불하지 않을 수있는 방대한 양의 물건을 추적 할 수 있기 때문입니다. 컴퓨터주기가 저렴 해지므로 컴파일러에서 코드의 더 많은 속성을 추적하는 것이 합리적입니다.

Answer 2

그만큼 브로드 웨이 프레임 워크는 당신이 찾고있는 것의 정맥에있을 수 있습니다. "소스-소스 변환"에 관한 논문도 깨달을 것입니다.