Funktion optimiert auf Endlosschleife bei ‘gcc -O2’

Kontext

Ich wurde von einem meiner Freunde nach folgendem Rätsel gefragt:

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;
}

Ich weiß, dass es mehrere Lösungen geben kann, von denen einige Makros beinhalten und andere etwas über die Implementierung annehmen und C verletzen.

Eine bestimmte Lösung, an der ich interessiert war, besteht darin, bestimmte Annahmen über den Stapel zu treffen und den folgenden Code zu schreiben: (Ich verstehe, dass es sich um ein undefiniertes Verhalten handelt, aber es kann bei vielen Implementierungen wie erwartet funktionieren.)

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 */
}

Problem

Dieses Programm funktionierte in MSVC und gcc ohne Optimierung einwandfrei. Aber wenn ich es mit kompiliert habe gcc -O2 Flagge oder anprobiert IdeeSchleifen unendlich in Funktion fn.

Meine Beobachtung

Als ich die Datei mit kompiliert habe gcc -S vs gcc -S -O2 und verglichen, zeigt es deutlich gcc hielt eine Endlosschleife in Funktion fn.

Frage

Ich verstehe, weil der Code undefiniertes Verhalten aufruft, man kann es nicht als Fehler bezeichnen. Aber warum und wie analysiert der Compiler das Verhalten und hinterlässt eine Endlosschleife bei O2?

Viele Leute kommentierten, um das Verhalten zu kennen, wenn einige der Variablen in flüchtig geändert werden. Das Ergebnis ist wie erwartet:

• Wenn i oder j geändert wird volatileProgrammverhalten bleibt gleich.
• Wenn Array a gemacht wird volatileProgramm leidet nicht Endlosschleife.
• Außerdem, wenn ich den folgenden Patch anwende

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

Das Programmverhalten bleibt gleich (Endlosschleife)

Wenn ich den Code mit kompiliere gcc -O2 -fdump-tree-optimizederhalte ich folgende Zwischendatei:

;; 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

Dies bestätigt die Behauptungen, die nach den Antworten unten gemacht wurden.

Dies ist ein undefiniertes Verhalten, sodass der Compiler wirklich alles tun kann, wir finden ein ähnliches Beispiel in GCC vor 4.8 bricht defekte SPEC 2006-Benchmarkswo gcc nimmt eine Schleife mit undefiniertem Verhalten und optimiert sie zu:

L2:
    jmp .L2

Der Artikel sagt (Betonung von mir):

Das ist natürlich eine Endlosschleife. Da SATD() bedingungslos undefiniertes Verhalten ausführt (es ist eine Typ-3-Funktion), Jede Übersetzung (oder gar keine) ist ein absolut akzeptables Verhalten für einen korrekten C-Compiler. Das undefinierte Verhalten ist der Zugriff auf d[16] kurz vor dem Verlassen der Schleife. Im C99 Es ist zulässig, einen Zeiger auf ein Element eine Position nach dem Ende des Arrays zu erstellen, aber dieser Zeiger darf nicht dereferenziert werden. Ebenso darf auf die Array-Zelle ein Element nach dem Ende des Arrays nicht zugegriffen werden.

was, wenn wir Ihr Programm mit prüfen Gottriegel wir sehen:

fn:
.L2:
    jmp .L2

Die vom Optimierer verwendete Logik sieht wahrscheinlich so aus:

• Alle Elemente von a werden auf Null initialisiert
• a wird niemals vor oder innerhalb der Schleife geändert
• So a[j] != 5 ist immer wahr -> Endlosschleife
• Wegen der Unendlichkeit, der a[j] = 10; unerreichbar ist und damit wegoptimiert werden kann, so kann a und j da sie zur Bestimmung des Schleifenzustandes nicht mehr benötigt werden.

was dem Fall in dem Artikel ähnlich ist, in dem Folgendes angegeben ist:

int d[16];

analysiert die folgende Schleife:

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

so was:

beim Anblick d[++k], darf davon ausgehen, dass der inkrementierte Wert von k innerhalb der Array-Grenzen liegt, da sonst undefiniertes Verhalten auftritt. Für den Code hier kann GCC ableiten, dass k im Bereich 0..15 liegt. Etwas später, als GCC k<16 sieht, sagt es sich: „Aha – dieser Ausdruck ist immer wahr, also haben wir eine Endlosschleife.“

Ein vielleicht interessanter sekundärer Punkt ist, ob eine Endlosschleife als beobachtbares Verhalten angesehen wird (bzgl. der Als-ob-Regel) oder nicht, was sich darauf auswirkt, ob eine Endlosschleife auch wegoptimiert werden kann. Wir können von sehen C-Compiler widerlegen Fermats letzten Satz dass es vor C11 zumindest einen gewissen Interpretationsspielraum gab:

Viele sachkundige Leute (mich eingeschlossen) lesen dies so, dass das Beendigungsverhalten eines Programms nicht geändert werden darf. Offensichtlich sind einige Compiler-Autoren anderer Meinung oder glauben nicht, dass es darauf ankommt. Die Tatsache, dass vernünftige Menschen sich über die Interpretation nicht einig sind, scheint darauf hinzudeuten, dass der C-Standard fehlerhaft ist.

C11 fügt dem Abschnitt eine Klarstellung hinzu 6.8.5 Iterationsanweisungen und wird in dieser Antwort ausführlicher behandelt.

In der optimierten Version hat der Compiler ein paar Dinge entschieden:

1. Das Array a ändert sich vor diesem Test nicht.
2. Das Array a enthält kein 5.

Daher können wir den Code wie folgt umschreiben:

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

Jetzt können wir weitere Entscheidungen treffen:

1. Der gesamte Code nach der While-Schleife ist toter Code (nicht erreichbar).
2. j geschrieben, aber nie gelesen. Also können wir es loswerden.
3. a wird nie gelesen.

An dieser Stelle wurde Ihr Code reduziert auf:

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

Und das können wir festhalten a wird jetzt nie gelesen, also werden wir es auch los:

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

Nun der nicht optimierte Code:

In nicht optimiertem generiertem Code verbleibt das Array im Arbeitsspeicher. Und Sie werden es buchstäblich zur Laufzeit durchlaufen. Und es ist möglich, dass es eine geben wird 5 Das ist danach lesbar, sobald Sie am Ende des Arrays vorbeigehen.

Aus diesem Grund stürzt die nicht optimierte Version manchmal nicht ab und brennt nicht.

Wenn die Schleife tut In eine Endlosschleife optimiert werden, könnte es an statischen Codeanalysen liegen, die sehen, dass Ihr Array ist

1. nicht volatile

2. enthält nur 0

3. wird nie angeschrieben

und daher ist es nicht möglich, dass es die Nummer enthält 5. Was eine Endlosschleife bedeutet.

Selbst wenn dies nicht der Fall wäre, könnte Ihr Ansatz leicht scheitern. Zum Beispiel ist es möglich, dass ein Compiler Ihren Code optimiert, ohne Ihre Schleife unendlich zu machen, aber den Inhalt von füllt i in ein Register, wodurch es vom Stack nicht verfügbar ist.

Als Randbemerkung wette ich, was Ihr Freund eigentlich erwartet hat, war dies:

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 */
}

oder dies (ggf stdlib.h ist enthalten):

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 */
}