Ich schreibe aus Spaß eine kompilierte Sprache, und ich habe kürzlich einen Kick bekommen, 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. Lass es mich erklären.
Nimm den folgenden Code.
%Vor%Als Mensch kann ich hier sitzen und Ihnen sagen, dass dies zu 100% der Zeit mit
gleichzusetzen ist %Vor%Mit anderen Worten, diese Schleife kann vollständig "kompiliert" werden. 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 mir drei Arten von Loops ausgedacht, 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 Kompilierungsfehler / eine Warnung sein, wenn sie vom Programmierer nicht speziell 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 der Optimierung sind natürlich die statischen Schleifeniterationen, wenn alle Funktionsaufrufe im Inneren ebenfalls statisch sind. 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 so 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.
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: kein Nummernüberlauf, nur für Schleifen (während manchmal in volle for-Schleife umgewandelt werden kann, außer bei Verwendung von usw.), keine Brüche, keine Änderungen der Steuervariablen innerhalb der for-Schleife.
for (var i = S; E(i); i = U(i)) ...
wobei 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 -ter Zyklus Der Wert von i ist S + n * CONSTANT
U(i) = i * CONSTANT : n -ter Zyklus Der Wert von i ist S * CONSTANT^n
U(i) = i / CONSTANT : n -ter Zyklus Der Wert von i ist S * CONSTANT^-n
U(i) = (i + CONSTANT) % M : n -ter Zyklus Der Wert von i ist (S + n * CONSTANT) % M
und einige andere recht einfache Kombinationen (und einige sehr schwierige)
Das Bestimmen, ob die Schleife endet, sucht nach n , wobei E(i(n)) falsch ist.
Dies kann durch eine symbolische Manipulation für viele Fälle geschehen, aber es ist eine Menge Arbeit damit verbunden, den Löser zu erstellen.
z. B.
for(int i = 0; i < 5; i++) , i(n) = 0 + n * 1 = n , E(i(n)) = & gt; not(n < 5) = & gt; n >= 5 = & gt; stoppt für n = 5
for(int i = 0; i < 5; i--) , i(n) = 0 + n * -1 = -n , E(i(n)) = & gt; not(-n < 5) = & gt; -n >= 5 = & gt; n < -5 - da n eine nicht negative ganze Zahl ist, ist dies nie wahr - hört niemals auf for(int i = 0; i < 5; i = (i + 1) % 3) , E(i(n)) = & gt; not(n % 3 < 5) = & gt; n % 3 >= 5 = & gt; das ist nie wahr = & gt; hört nie auf for(int i = 10; i + 10 < 500; i = i + 2 * i) = & gt; for(int i = 10; i < 480; i = 3 * i) , i(n) = 10 * 3^n , E(i(n)) = & gt; not(10 * 3^n < 480) = & gt; 10 * 3^n >= 480 = & gt; 3^n >= 48 = & gt; n >= log3(48) = & gt; n >= 3.5... = & gt; n = 4
Für andere Fälle wäre es gut, wenn sie in diejenigen umgewandelt werden könnten, die Sie bereits lösen können ...
Viele Tricks zur symbolischen Manipulation kommen aus der Lisp-Ära 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.
Tags und Links language-agnostic optimization compiler-construction theory