Frank wrote:
> Block Localization
wurde schon erklärt
> Code Motion
>
> "Code motion moves blocks of instructions from one place to another to
> reduce the number of jump instructions in the final program."
Ein (sequenzielles) Programm besteht aus basic blocks (BB) und edges
(E). Ein BB ist ein Stück linear ablaufender Code, ohne Verzweigungen
und ohne Labels. Diese elementaren Elemente kann man sich als Kanten in
einem gerichteten Graph vorstellen. Die Knoten im Graph sind die Edges,
das sind wie gesagt verzweigungen im Programmfluß und Stellen, an denen
der Programmfluß wieder zusammenführt.
Im Speicher steht das "geplättete" Darstellung des Programms; die BBs
stehen in irgendeiner Reihenfolge und sind über (bedingte) Sprünge
verbunden. Je nachdem, wie man den Graph platt macht, gibt es
unterschiedlich viele und weite Sprünge.
Ja nach Architektur kosten Sürünge unterschiedlich viel, zB je nach
-- Sprungweite
-- ob vor oder zurückgesprungen wird
-- Zustand einer Befehls-Pipeline
-- Zustand eines Befehls-Caches
Durch Umarrangieren der BBs kann man Sprünge sparen, bzw Laufzeit gegen
Codegröße austauschen.
Beispiel 1
Beispiel 2
In #1 sind mehr Sprünge als in #2. Hier wird #2 vermutlich längeren Code
geben, weil BB C in #2 2x austaucht. Aber der Code ist schneller, weil
vor C kein Sprung steht. A und C verschmelzen zu einem neuen BB AC, dito
für B und C zu BC. Zusätzlich sind andere Optimierungen möglich, weil in
#2 innerhalb von AC bzw. BC optimiert werden kann, was in #1 nicht so
einfach möglich ist, weil man zur Compilezeit nicht weiß, welchen Pfad
das Programm zur Laufzeit nimmt.
Johann