'gcc-O2'에서 무한 루프에 최적화된 기능

'gcc-O2'에서 무한 루프에 최적화된 기능

저는 제 친구 중 한 명으로부터 다음과 같은 퍼즐을 물었습니다.

void fn(void)
{
  /* write something after this comment so that the program output is 10 */
  /* write something before this comment */
}

int main()
{
  int i = 5;
  fn();
  printf("%d\n", i);
  return 0;
}

저는 여러 가지 해결책이 있을 수 있다는 것을 알고 있습니다. 일부는 매크로를 포함하고 일부는 구현과 C를 위반하는 것에 대해 가정합니다.

제가 관심을 가졌던 한 가지 특별한 해결책은 스택 및 쓰기 코드에 대한 특정 가정을 하는 것입니다. (정의되지 않은 동작이라는 것은 이해하지만 많은 구현에서 예상대로 작동할 수 있습니다.)

void fn(void)
{
  /* write something after this comment so that the program output is 10 */
  int a[1] = {0};
  int j = 0;
  while(a[j] != 5) ++j;  /* Search stack until you find 5 */
  a[j] = 10;             /* Overwrite it with 10 */
  /* write something before this comment */
}

ㅠㅠ
이 프로그램은 최적화 없이 MSVC와 gcc에서 잘 작동했습니다.하지만 내가 그것을 편집했을 때.gcc -O2플래그 또는 아이디어에 대해 시도한 결과, 기능이 무한히 순환됩니다.fn.

의 »
가 컴할때일파을로 했을 때.gcc -S 대gcc -S -O2그리고 비교해보면, 그것은 분명히 보여줍니다.gcc 무한루기유능니다습지했을프에서 무한 를 유지했습니다.fn.

입니다.
코드가 정의되지 않은 동작을 호출하기 때문에 버그라고 할 수 없다는 것을 이해합니다.그러나 컴파일러가 동작을 분석하고 무한 루프를 남기는 이유와 방법은 무엇입니까?O2?

---

많은 사람들이 변수 중 일부가 휘발성으로 변경될 경우의 동작을 알고자 댓글을 달았습니다.예상대로의 결과는 다음과 같습니다.

• 한다면i또는j 로변됨으로 되었습니다.volatile프로그램 동작이 동일하게 유지됩니다.
• array if 열a 들어짐만volatile프로그램은 무한 루프를 겪지 않습니다.
• 게다가 다음 패치를 적용하면,

-  int a[1] = {0};
+  int aa[1] = {0};
+  int *a = aa;

프로그램 동작이 동일하게 유지됩니다(무한 루프).

내가 컴경우할일파로 한다면,gcc -O2 -fdump-tree-optimized다음과 같은 중간 파일을 가져옵니다.

;; Function fn (fn) (executed once)

Removing basic block 3
fn ()
{
<bb 2>:

<bb 3>:
  goto <bb 3>;

}



;; Function main (main) (executed once)

main ()
{
<bb 2>:
  fn ();

}
Invalid sum of incoming frequencies 0, should be 10000

이렇게 하면 아래 답변 이후에 이루어진 주장을 확인할 수 있습니다.

이것은 정의되지 않은 동작이기 때문에 컴파일러는 정말로 무엇이든 할 수 있습니다. 우리는 GCC 4.8 이전의 깨진 SPEC 2006 벤치마크에서 유사한 예를 찾을 수 있습니다.gcc정의되지 않은 동작을 가진 루프를 사용하여 다음과 같이 최적화합니다.

L2:
    jmp .L2

이 기사는 다음과 같이 말합니다(내 것 강조).

물론 이것은 무한 루프입니다.SATD()는 정의되지 않은 동작(타입 3 함수)을 무조건 실행하므로 올바른 C 컴파일러에 대해 모든 변환(또는 전혀 없음)이 완벽하게 허용되는 동작입니다.루프를 종료하기 직전에 정의되지 않은 동작이 d[16]에 액세스하고 있습니다.C99에서는 배열의 끝을 지나 요소에 대한 포인터를 만드는 것이 합법적이지만 해당 포인터는 참조되지 않아야 합니다.마찬가지로 배열 끝을 지나 배열 셀 하나의 요소에 액세스해서는 안 됩니다.

우리가 godbolt로 당신의 프로그램을 조사하면 우리는 다음을 볼 수 있습니다.

fn:
.L2:
    jmp .L2

옵티마이저가 사용하는 논리는 다음과 같습니다.

• 의모든요의 a으로 됩니다.
• a 이전 .
• 그렇게a[j] != 5참입니다 -> 루프는 -> 는 항상 참입니다.
• 것 에, 때문에기하한무,,에▁the▁because한▁infinite.a[j] = 10;할 수 에 할 수 .a그리고.j루프 조건을 결정하는 데 더 이상 필요하지 않기 때문입니다.

이는 다음과 같은 내용이 제시된 기사의 경우와 유사합니다.

int d[16];

에서는 다음 루프를 분석합니다.

for (dd=d[k=0]; k<16; dd=d[++k]) 

다음과 같이:

d[+k]를 보면 k의 증분 값이 배열 범위 내에 있다고 가정할 수 있습니다. 그렇지 않으면 정의되지 않은 동작이 발생하기 때문입니다.여기서 코드의 경우, GCC는 k가 0.15 범위에 있다고 추론할 수 있습니다.조금 후, GCC가 k<16을 볼 때, "아하- 그 표현은 항상 진실이고, 그래서 우리는 무한 루프를 가지고 있습니다."라고 스스로에게 말합니다.

아마도 흥미로운 2차 포인트는 무한 루프가 관찰 가능한 동작(있는 그대로 규칙에 대한 w.r.t)으로 간주되는지 여부이며, 이는 무한 루프도 최적화될 수 있는지 여부에 영향을 미칩니다.우리는 C 컴파일러 반프 페르마의 마지막 정리를 통해 C11 이전에는 적어도 해석의 여지가 있었다는 것을 알 수 있습니다.

저를 포함한 많은 지식 있는 사람들은 프로그램의 종료 동작이 변경되어서는 안 된다고 말하며 이 글을 읽었습니다.분명히 일부 컴파일러 작가들은 동의하지 않거나, 그렇지 않으면 그것이 중요하다고 믿지 않습니다.합리적인 사람들이 해석에 동의하지 않는다는 사실은 C 기준에 결함이 있다는 것을 나타내는 것으로 보입니다.

C11은 섹션에 설명을 추가합니다.6.8.5 반복 설명 및 이 답변에서 자세히 설명합니다.

최적화된 버전에서 컴파일러는 다음과 같은 몇 가지 사항을 결정했습니다.

1. 열a테스트 전에는 변경되지 않습니다.
2. 열a이 5.

따라서 코드를 다음과 같이 다시 작성할 수 있습니다.

void fn(void) {
  int a[1] = {0};
  int j = 0;
  while(true) ++j;
  a[j] = 10;
}

이제 추가 결정을 내릴 수 있습니다.

1. while 루프 이후의 모든 코드는 dead code(연결 불가능)입니다.
2. j기록되지만 읽지는 않습니다.그래서 우리는 그것을 없앨 수 있습니다.
3. a절대 읽지 않습니다.

이 시점에서 코드는 다음과 같이 축소되었습니다.

void fn(void) {
  int a[1] = {0};
  while(true);
}

그리고 우리는 다음과 같이 기록할 수 있습니다.a이제는 절대 읽지 않습니다. 그러니 그것도 없애죠.

void fn(void) {
  while(true);
}

최적화되지 않은 코드:

최적화되지 않은 생성된 코드에서는 배열이 메모리에 남아 있습니다.그리고 말 그대로 런타임에 걷게 될 것입니다.그리고 그것이 일어날 가능성이 있습니다.5배열의 끝을 지나면 읽을 수 있습니다.

이것이 최적화되지 않은 버전이 때때로 충돌하거나 굽지 않는 이유입니다.

루프가 무한 루프로 최적화되는 경우, 정적 코드 분석을 통해 어레이가

1. 것은 아니다.volatile

2. 포함만0

3. 에 기록되지 않음

따라서 숫자를 포함하는 것은 불가능합니다.5그것은 무한 루프를 의미합니다.

이렇게 하지 않더라도 접근 방식은 쉽게 실패할 수 있습니다.예를 들어, 일부 컴파일러가 루프를 무한대로 만들지 않고 코드를 최적화할 수 있지만 내용은 다음과 같습니다.i스택에서 사용할 수 없도록 레지스터에 추가합니다.

참고로, 당신의 친구가 실제로 기대했던 것은 다음과 같습니다.

void fn(void)
{
  /* write something after this comment so that the program output is 10 */
  printf("10\n"); /* Output 10 */
  while(1); /* Endless loop, function won't return, i won't be output */
  /* write something before this comment */
}

또는 이것(만약)stdlib.h포함):

void fn(void)
{
  /* write something after this comment so that the program output is 10 */
  printf("10\n"); /* Output 10 */
  exit(0); /* Exit gracefully */
  /* write something before this comment */
}

언급URL : https://stackoverflow.com/questions/28631378/function-optimized-to-infinite-loop-at-gcc-o2