Optimierung von "statischen" Schleifen

Question

Ich schreibe eine kompilierte Sprache zum Spaß, und ich habe vor kurzem einen Kick bekommen, um meinen optimierenden Compiler sehr robust zu machen. Ich habe mehrere Möglichkeiten gefunden, einige Dinge zu optimieren, zum Beispiel 2 + 2 ist immer 4, also können wir diese Mathematik zur Kompilierzeit machen, wenn (falsch) {...} komplett entfernt werden kann usw., aber jetzt Ich habe Schleifen bekommen. Nach einigem Nachdenken denke ich, dass ich nicht gerade Loop Enrolling versuche, aber es ist immer noch eine Optimierungstechnik. Lassen Sie mich erklären.

Nehmen Sie den folgenden Code.

String s = ""; 
for(int i = 0; i < 5; i++){ 
    s += "x"; 
} 
output(s); 

Als Mensch, kann ich hier sitzen und sagen, dass dies 100% der Zeit zu

output("xxxxx"); 

So äquivalent zu gehen, in anderen Worten, diese Schleife „kompiliert werden aus "ganz Es ist nicht das Abrollen der Schleife, sondern das, was ich "vollständig statisch" nenne, dh es gibt keine Eingaben, die das Verhalten des Segments verändern würden. Meine Idee ist, dass alles, was vollständig statisch ist, in einen einzigen Wert aufgelöst werden kann, alles, was auf Eingaben beruht oder konditionale Ausgaben erzeugt, kann natürlich nicht weiter optimiert werden. Was muss ich aus der Sicht der Maschine beachten? Was macht eine Schleife "vollständig statisch?"

Ich habe drei Arten von Schleifen gefunden, die ich herausfinden muss, um zu kategorisieren. Schleifen, die nach jedem Lauf immer denselben Maschinenzustand haben, unabhängig von Eingaben, Schleifen, die NIE abgeschlossen werden, und Schleifen, die ich nicht in die eine oder andere Richtung herausfinden kann. In dem Fall, dass ich es nicht herausfinden kann (es ändert sich bedingt, wie oft es basierend auf dynamischen Eingaben laufen wird), mache ich mir keine Sorgen über die Optimierung. Schleifen, die unendlich sind, werden ein Kompilierfehler/eine Kompilierung sein, wenn sie vom Programmierer nicht spezifisch unterdrückt werden, und Schleifen, die jedes Mal gleich sind, sollten direkt überspringen, um die Maschine in den richtigen Zustand zu versetzen, ohne Schleife.

Der Hauptfall natürlich zu optimieren ist die statische Schleife Iterationen, wenn alle Funktionsaufrufe innerhalb sind auch statisch. Das Bestimmen, ob eine Schleife dynamische Komponenten hat, ist einfach genug und wenn sie nicht dynamisch ist, muss sie statisch sein. Was ich nicht herausfinden kann ist, wie man erkennt, ob es unendlich sein wird oder nicht. Hat jemand darüber irgendwelche Gedanken? Ich weiß, dass dies eine Teilmenge des Halteproblems ist, aber ich fühle, dass es lösbar ist. Das Halteproblem ist ein Problem aufgrund der Tatsache, dass man für einige Teilmengen von Programmen nicht sagen kann, dass es für immer laufen könnte, es mag nicht sein, aber ich möchte diese Fälle nicht berücksichtigen, ich möchte nur die Fälle betrachten wo es stehen bleibt, oder es wird nicht aufhören, aber zuerst muss ich zwischen den drei Zuständen unterscheiden.

Answer 1

Dies sieht wie eine Art symbolischer Löser aus, der für mehrere Klassen definiert werden kann, aber nicht allgemein.

Lassen Sie uns die Anforderungen ein wenig einschränken: keine Anzahl Überlauf, nur für Schleifen (während manchmal in Full for Loop umgewandelt werden kann, außer bei Verwendung von etc.), keine Brüche, keine Änderungen der Steuervariablen innerhalb der for-Schleife .

for (var i = S; E(i); i = U(i)) ...

wo E (i) und U (i) Ausdrücke sind, die symbolisch manipuliert werden können.Es gibt mehrere Klassen, die relativ einfach sind:

U(i) = i + CONSTANT: n -te Zyklus der Wert von i ist S + n * CONSTANT

U(i) = i * CONSTANT: n -te Zyklus der Wert von iS * CONSTANT^n ist

U(i) = i/CONSTANT: n -te Zyklus der Wert i ist S * CONSTANT^-n

U(i) = (i + CONSTANT) % M: n -te Zyklus der Wert von i ist (S + n * CONSTANT) % M

und einige andere ganz einfache Kombinationen (und einige sehr schwierige)

Feststellung, ob die Schleife für n sucht dort endet, wo E(i(n)) falsch ist. Dies kann durch einige symbolische Manipulationen in vielen Fällen geschehen, aber es ist eine Menge Arbeit damit verbunden, den Löser zu erstellen.

z.

• for(int i = 0; i < 5; i++),
• i(n) = 0 + n * 1 = n, E(i(n)) =>not(n < 5) =>
• n >= 5 => stoppt für n = 5

---

• for(int i = 0; i < 5; i--),
• i(n) = 0 + n * -1 = -n, E(i(n)) =>not(-n < 5) =>-n >= 5 =>
• n < -5 - da n eine nicht negative ganze Zahl ist dies nie wahr ist - hört nie

---

• for(int i = 0; i < 5; i = (i + 1) % 3),
• E(i(n)) = >not(n % 3 < 5) =>n % 3 >= 5 => das ist nie wahr => hört nie auf

---

• for(int i = 10; i + 10 < 500; i = i + 2 * i) =>
• for(int i = 10; i < 480; i = 3 * i),
• i(n) = 10 * 3^n,
• E(i(n)) =>not(10 * 3^n < 480) =>10 * 3^n >= 480 =>3^n >= 48 =>n >= log3(48) =>n >= 3.5... =>
• da n ganze => es wird für n = 4
stoppen

für andere Fälle wäre es gut, wenn sie auf diejenigen umgewandelt bekommen können Sie bereits lösen können ...

Viele Tricks für symbolische Manipulation von Lisp-Ära kommen, und sind nicht allzu schwierig. Obwohl die beschriebenen (oder Varianten) die gebräuchlichsten Arten sind, gibt es viele schwierigere und/oder unmöglich zu lösende Szenarien.