컴파일러는 무한 루프를 제거할 수 있습니까?

컴파일러는 무한 루프를 제거할 수 있습니까?

컴파일러 최적화를 통해 무한 루프를 삭제할 수 있으며, 이것은 어떤 데이터도 바꾸지 않습니다.

while(1) 
  /* noop */;

데이터 흐름 그래프 컴파일러를 분석하면 그러한 루프가 아무런 부작용 없이 "죽은 코드"라는 것을 알 수 있습니다.

무한 루프 삭제는 C90/C99 표준에서 금지되어 있습니까?

C90이나 C99 표준은 컴파일러가 그러한 루프를 삭제하는 것을 허용합니까?

업데이트: "Microsoft C 버전 6.0은 본질적으로 이러한 최적화를 수행했습니다.". caf의 링크 참조.

label: goto label;
return 0;

로 변경될 예정입니다.

return 0;

C11은 C11 표준 초안 섹션에서 이 질문에 대한 답을 명확히 합니다.6.8.5 반복문은 다음 단락을 추가했습니다.

제어 표현식이 상수 표현식이 아니며,¹⁵⁶⁾ 입출력 동작을 수행하지 않으며, 휘발성 객체에 접근하지 않으며, 본체 내에서 동기화 또는 원자 동작을 수행하지 않으며, 표현식을 제어하거나, (a for문의 경우) 표현식-3,종료할 이행 상황을 가정할 수 있습니다.¹⁵⁷⁾

및 각주157다음과 같이 말합니다.

이것은 종료를 증명할 수 없는 경우에도 빈 루프를 제거하는 것과 같은 컴파일러 변환을 허용하기 위한 것입니다.

그렇다면 구체적인 예는 다음과 같습니다.

while(1) 
  /* noop */;

제어식은 상수식이므로 최적화를 위한 공정한 게임이 아닙니다.

UB로서의 무한 루프

그렇다면 컴파일러가 위에서 제공한 예외를 제외하고 무한 루프를 최적화할 수 있는 이유는 무엇입니까? Hans Boehm은 다음과 같이 무한 루프를 정의되지 않은 동작으로 만드는 근거를 제공합니다. 무한 루프에 대해 정의되지 않은 동작을 하는 이유는 무엇입니까? 다음 인용문은 관련된 문제에 대해 좋은 느낌을 줍니다.

N1509가 정확히 지적한 바와 같이, 현재 초안은 본질적으로 6.8.5p6에서 무한 루프에 정의되지 않은 동작을 부여합니다.그렇게 하는 데 있어 주요한 문제는 코드가 잠재적으로 비종단 루프를 가로질러 이동할 수 있게 한다는 것입니다.예를 들어, 다음과 같은 루프가 있다고 가정합니다. count와 count2는 전역 변수(또는 주소가 사용됨)이고 p는 주소가 사용되지 않은 로컬 변수입니다.

for (p = q; p != 0; p = p -> next) {
    ++count;
}
for (p = q; p != 0; p = p -> next) {
    ++count2;
}

이 두 루프가 합쳐져서 다음 루프로 대체될 수 있습니까?

for (p = q; p != 0; p = p -> next) {
        ++count;
        ++count2;
}

무한 루프에 대해 6.8.5p6의 특별한 분배가 없다면, 이는 허용되지 않습니다.q가 순환 리스트를 가리키기 때문에 첫 번째 루프가 종료되지 않으면 원본은 절대로 카운트 2에 기록하지 않습니다.따라서 카운트 2에 액세스하거나 업데이트하는 다른 스레드와 병렬로 실행될 수 있습니다.무한 루프에도 불구하고 카운트 2에 액세스하는 변환된 버전에서는 더 이상 안전하지 않습니다.따라서 이러한 전환은 잠재적으로 데이터 경쟁을 야기할 수 있습니다.

이와 같은 경우, 컴파일러가 루프 종료를 증명할 가능성은 거의 없습니다. q가 비순환 목록을 가리킨다는 것을 이해해야 할 것이고, 이는 대부분의 주류 컴파일러의 능력을 넘어서는 것이며, 전체 프로그램 정보 없이는 종종 불가능합니다.

C99

C99에는 이 조각이 없으므로 섹션에서 다루는 그대로의 규칙을 살펴봅니다.5.1.2.3기본적으로 컴파일러는 프로그램의 관찰 가능한 동작을 에뮬레이트하기만 하면 된다고 말하며 요구 사항은 다음과 같습니다.

적합한 구현에 대한 최소한의 요구사항은 다음과 같습니다.

• 시퀀스 포인트에서 휘발성 개체는 이전 액세스가 완료되고 이후 액세스가 아직 발생하지 않았다는 의미에서 안정적입니다.
• 프로그램 종료 시 파일에 기록되는 모든 데이터는 추상적 의미론에 따라 프로그램이 실행되었을 때 생성된 결과와 동일해야 합니다.
• 상호작용 장치의 입력 및 출력 역학은 7.19.3에 명시된 대로 이루어져야 합니다.이러한 요구 사항의 목적은 입력을 기다리는 프로그램 전에 실제로 프롬프트 메시지가 나타나도록 버퍼링되지 않거나 라인 버퍼링된 출력이 가능한 한 빨리 표시되도록 하는 것입니다.

이를 엄격하게 읽으면 구현이 무한 루프를 최적화할 수 있을 것으로 보입니다.우리는 무한 루프를 최적화하는 것이 관측 가능한 행동의 변화를 초래하는 시나리오를 확실히 생각해 낼 수 있습니다.

while(1) ;
printf( "hello world\n" ) ;

많은 사람들이 프로세스 종료에 영향을 미치는 것도 관찰 가능한 행동이라고 주장할 것이며, 이러한 입장은 C Compilers Disprove Fermat의 마지막 정리에서 취합니다.

컴파일러는 C 프로그램을 구현하는 방법에 대해 상당한 자유가 주어지지만, 그 출력은 표준에 설명된 "C 추상 기계"에 의해 해석될 때 프로그램이 가질 수 있는 것과 동일한 외부적으로 보이는 동작을 가져야 합니다.저를 포함한 많은 지식인들은 프로그램 종료 행동이 변경되어서는 안 된다고 이것을 읽었습니다.분명히 일부 컴파일러 작성자들은 동의하지 않거나, 그렇지 않으면 중요하다고 믿지 않습니다.합리적인 사람들이 해석에 동의하지 않는다는 것은 C 표준에 결함이 있음을 나타내는 것으로 보입니다.

갱신하다

나는 위 기사의 후속편인 컴파일러와 터미네이션 리바이티드를 놓쳤는데 그것은 다음과 같은 부분입니다.5.1.2.3:

두 번째 요건은 까다로운 것입니다.추상 기계에서 실행 중인 프로그램의 종료에 대해 이야기하고 있다면, 우리의 프로그램이 종료되지 않기 때문에 명확하게 충족됩니다.컴파일러에 의해 생성된 실제 프로그램의 종료를 말하는 것이라면, 파일에 쓰여진 데이터(stdout은 파일)가 추상 기계에 의해 쓰여진 데이터와 다르기 때문에 C 구현은 버그가 있습니다.(이 책은 한스 보엠 때문입니다. 저는 이 미묘한 점을 표준에 맞지 않게 놀리지 못했습니다.)

또한 빈 루프 제거를 허용하기 위해 C11에서 조각을 생성해야 할 필요성은 이전에는 허용 가능한 최적화가 아니었음을 의미한다는 약한 주장을 할 수 있습니다.

이것은 무한 고투 루프에도 적용됩니까?

이는 무한한 고투루프에도 적용된다는 취지라고 생각합니다.C++에서는 섹션 이후로 분명히 해당됩니다.1.10 [intro.multithread]는 다음과 같이 말합니다.

구현 시 모든 스레드가 최종적으로 다음 중 하나를 수행할 것으로 가정할 수 있습니다.

• 종료,
• 도서관 I/O 기능에 전화를 걸며,
• 휘발성 객체에 접근하거나 수정하거나,
• 동기화 동작 또는 원자 연산을 수행합니다.

그 다음에 표현된 것과 같이 의도를 갖습니다.N1528C와 C++ 표준이 일치한다는 것입니다.

컴파일러 백엔드는 일반적으로 C와 C++ 컴파일러 간에 공유되기 때문에, WG14와 WG21은 채택되는 솔루션에 대해 합의하는 것이 가장 중요해 보입니다.대안은 백엔드로 두 언어를 특별하게 처리하거나 C 코드를 처리할 때 최적화를 비활성화하는 것입니다.어느 쪽도 바람직하지 않은 것 같습니다.

그리고 마지막에 이렇게 말합니다.

WG21은 치료법을 일관성 있게 만드는 개선된 문구를 고려하고 있습니다.WG14가 결과적인 변화를 추적하기를 바랍니다.

현재 C11 표준에는 섹션에 유사한 문구가 포함되어 있지 않습니다.5.1.2.4 멀티스레드 실행 및 데이터 레이스를 고려하지만,N1528컴파일러가 C와 C++에서 무한한 고투 루프를 정의되지 않은 동작으로 취급한다고 가정하는 것이 현명해 보입니다.

참고로 여기 미국 코멘트 38과 이번 변경이 적용된 논문인 N3196도 참조하시기 바랍니다.

무한 루프를 보편적으로 감지할 수 있는 방법은 없습니다. 중단 문제를 참조하십시오.따라서 모든 컴파일러가 할 수 있는 최선의 방법은 적절한 추측을 하는 것입니다. 예를 들어 OP에서 언급된 명백한 경우입니다.

하지만 왜 이것이 바람직할까요?경고를 표시하면서도 동작을 허용하는 것은 볼 수 있었지만, 루프를 제거하는 것은 "최적화"가 아니라 프로그램의 동작을 변경하는 것입니다!

루프는 데드 코드가 아닙니다. 기본적으로 프로그램이 다음에 오는 것을 방지하는 것입니다.이것은 만약 루프가 제거된다면 일어날 일이 아니기 때문에 컴파일러가 루프를 제거할 수 없습니다.

스레드가 더 이상 아무것도 하지 않을 것임을 프로세서에 알리는 플랫폼 의존 유휴 명령어로 대체할 수 있습니다.

컴파일러가 할 수 있는 일은 루프 뒤에 오는 모든 코드를 제거하는 것입니다. 왜냐하면 코드는 도달할 수 없기 때문이고 절대 실행되지 않을 것이기 때문입니다.

이것은 이전에도 여러번 논의된 바 있습니다.comp.lang.c(예: 여기) 합의 결과가 없는 것으로 알고 있습니다.

그들은 데몬을 쓸 때 필수품입니다.왜 그들을 데드 코드라고 부르고 싶었습니까?

새로운 표준은 코드 조각이 휘발성 변수에 접근할 수 없는 경우 I/O 등을 수행하도록 명시적으로 규정하고 있다고 생각합니다. 첫 번째 조각에서 계산된 어떤 것에도 의존하지 않는 다른 코드는 그 이전에 임의로 배열될 수 있습니다.무한 루프가 I/O를 수행하지 않거나 프로그램의 나중에 사용되는 값을 계산하지 않으면 컴파일러는 다른 모든 것이 완료될 때까지 루프의 실행을 단순히 연기할 수 있습니다.

언급URL : https://stackoverflow.com/questions/2178115/are-compilers-allowed-to-eliminate-infinite-loops