\item Kontrollflussabhängigkeit: Bei Verzweigungsknoten $v$ mit direkten Nachfolgern $a$ und $b$: $y$ kontrollflussabhängig von $v$$\Leftrightarrow$ mindestens ein Pad von $a$ zum Exit-Knoten ohne $y$ und jeder Pfad von $b$ zum Exit-Knoten über $y$
\item Berechnung von $\mathrm{ImmDom}\lbrack w\rbrack$ durch Durchlaufen in Tiefenordnung von $\mathrm{SemDom}\lbrack w\rbrack$ nach $w$ (ohne $\mathrm{SemDom}\lbrack w\rbrack$):\begin{itemize}
\item Erkennung durch Prüfung der Reduzierbarkeit des Graphs: \begin{itemize}
\item Entfernung der Rückwärtskanten aus KFG $\rightarrow$ azyklischer Graph, in dem jeder Knoten von der Wurzel erreicht werden kann $\Leftrightarrow$ KFG frei von unnatürlichen Schleifen
\item Alternative mit Transformationen: Am Ende Graph aus einem einzigen Knoten $\Leftrightarrow$ KFG reduzierbar (ohne Zyklen) \begin{description}
\item[T1-Transformation] Selbstschleifen aus Graph löschen
\item[T2-Transformation] Knoten mit eindeutigem Vorgänger mit diesem zusammenfassen
\item Zurücksetzen wenn Original oder Kopie mindestens schwach definiert wird
\item Anfangsbelegung: false
\item Vorverarbeitung: und
\end{itemize}
\item Verfügbare Ausdrücke: \begin{itemize}
\item auf allen Pfaden von Entry-Knoten aus wird Ausdruck bestimmt und verwendete Variablen anschließend nicht mehr schwach definiert
\item Optimierungen: \begin{itemize}
\item Elimination gleicher Teilausdrücke
\item Wiederverwendung statt Neuberechnung
\end{itemize}
\item Umsetzung: \begin{itemize}
\item Eine Bitposition pro wertnummeriertem (Teil-)Ausdruck
\item Setzen wenn Ausdruck ausgewertet wird
\item Zurücksetzen wenn vorkommende Variable mindestens schwach definiert wird
\item Anfangsbelegung: false
\item Vorverarbeitung: und sowie Ausdruck muss auf allen Pfaden verfügbar sein
\end{itemize}
\end{itemize}
\item Lebendige Variablen: \begin{itemize}
\item lebendig in Knoten $D$, wenn es einen Pfad von $D$ zum Exit-Knoten gibt, auf der die Variable ohne vorherige Redefinition schwach benutzt wird; sonst tot
\item Optimierungen: \begin{itemize}
\item Tote Variablen müssen nicht ausgerechnet werden
\item Weniger Registerdruck
\item Elimination redudanter Schleifenlaufvariablen nach der Schleife
\end{itemize}
\item Umsetzung: \begin{itemize}
\item Eine Bitposition pro Variable
\item Setzen bei Verwendung der Variable
\item Zurücksetzen bei starker Redefinition
\item Anfangsbelegung: false
\item Vorverarbeitung: oder
\end{itemize}
\end{itemize}
\item Erreichbare Nutzungen: \begin{itemize}
\item Alle Nutzungen einer Variable durch Bestimmen der Pfade, auf denen Variable ohne vorherige Redefinition verwendet wird
\item Zweck: Hilfreich für Lebendigkeitsspannen und Registerallokation
\end{itemize}
\item Vorhersehbare Ausdrücke: \begin{itemize}
\item auf allen Pfaden zum Exit-Knoten wird Ausdruck bestimmt und verwendete Variablen werden nicht vorher schwach redefiniert
\item Optimierungen: \begin{itemize}
\item Vorziehen der Ausdrucksberechnung zur Verkleinerung der Code-Größe
\item Geringerer Registerdruck in folgenden Zweigen
\end{itemize}
\item Umsetzung: \begin{itemize}
\item Eine Bitposition pro (Teil-)Ausdruck
\item Setzen bei Auswertung des Audrucks
\item Zurücksetzen bei mindestens schwacher Redefinition einer der verwendeten Variablen
\item Anfangsbelegung: false
\item Vorverarbeitung: und
\end{itemize}
\end{itemize}
\end{itemize}
\section{Wertnummerierung in Grundblock}
\begin{itemize}
\item Post-Order-Traversierung des Ausdrucksbaums
\item Jede referenzierte Variable bekommt eindeutige Id
\item Kombination aus Operator und beiden Argumenten bekommt entweder frische Id oder bei Duplikat (auch kommutativ) bereits verwendete
\item Jede Variable hat exakt eine starke und keine schwache Definition
\item erfordert Verwendung von $\phi$-Funktionen, die verschiedene Variablen zusammenführt
\end{itemize}
\subsection{Konstruktion der SSA-Form}
\begin{itemize}
\item In isoliertem Grundblock trivial: Erzeugung einer neuen Variable $x_i$ bei jeder Definition
\item$\phi$-Funktionen sollten möglichst sparsam nur wenn notwendig eingefügt werden
\end{itemize}
\subsubsection{Iteratives Dominanzgrenzenverfahren nach Cytron ($\mathcal{O}(N^2)$)}
\begin{itemize}
\item Dominanzgrenzenkriterium: Aus Definition von $v$ in Grundblock $X$ folgt eine $\phi$-Funktion für $v$ in jedem Grundblock der Dominanzgrenze von $X$
\item Eingefügte $\phi$-Funktionen werden Variablen zugewiesen, für die das Dominanzgrenzenkriterium erneut angewendet werden muss
\end{itemize}
\subsubsection{Wertnummerierungsverfahren nach Click}
\begin{itemize}
\item Wertnummerierung für jeden Grundblock $Z$ durchführen: \begin{itemize}
\item Wenn $Z$ Entry-Knoten, alle Wertnummern der Tupel in $Z$ auf ungültig setzen
\item Bei zwei Vorgängern $X, Y$ von $Z$, welche beide bereits besucht sind:\begin{itemize}
\item Wenn $\mathrm{wn}_X(t)\neq\mathrm{wn}_Y(t)$, dann neue Wertnummer $x$ für $\mathrm{wn}_Z(t)$ einführen und $\mathrm{wn}_Z(t)=\phi(\mathrm{wn}_X(t), \mathrm{wn}_Y(t))$ generieren
\item Wertnummerierung für alle Tupel $t$ in $Z$ durchführen
\item Nach Durchführung für alle Blöcke, $\phi'$-Funktionen korrigieren: \begin{itemize}
\item Besondere Wertnummern in $X$ durch letzte in $X$ gültige Wertnummer ersetzen
\item Offene $\phi'$-Funktionen durch abgeschlossene $\phi$-Funktion mit ersetzten Werten ersetzen
\item Falls $t$ in unbesuchten Blöcken nicht geändert wurde, $\mathrm{wn}_Z(t)=\phi'(\mathrm{wn}_X(t),\mathrm{wn}_Y(t))$ löschen und alle Verwendungen von $\mathrm{wn}_Z(t)$ durch $\mathrm{wn}_X(t)$ ersetzen
\item Aus $v_i = c$ können alle Verwendungen von $v_i$ durch die Konstante $c$ ersetzt werden
\item Aus $v_i =\phi(c_1, c_2, \textellipsis)$ kann $v_i$ durch $c_1$ ersetzt werden, wenn alle $c_i$ gleich sind
\item Datenflussanalyse muss nach Ersetzung nicht wiederholt werden, Worklist-Algorithmus reicht aus
\end{itemize}
\item Kopienfortschreibung: Aus $v_i = y_j$ kann jede Verwendung von $v_i$ durch $y_j$ ersetzt werden
\item Lebendigkeit einer Variable lässt sich direkt aus weiterem lesenden Zugriff erkennen
\item Gemeinsame Teilausdrücke, verfügbare Ausdrücke und vorhersehbare Ausdrücke lassen sich durch Wertnummerierung in gesamter Prozedur leicht erkennen
\item Variablen können auch nur schwach definiert sein, etwa durch Zeiger auf Variablen oder Seiteneffekte von Prozeduren auf globale Variablen $\rightarrow$ Hilfsfunktion $\mathrm{isAlias}(p, v)$\begin{itemize}
\item\begin{equation*}
\mathrm{isAlias}(p, v) = \begin{cases}
*p &\text{falls}\, p = \&v\\
v &\text{sonst}
\end{cases}
\end{equation*}
\item Für jede Zuweisung $*p =$ für jede Variable $v_i$, auf die $p$ zeigen könnte, neue Zuweisung $v_{i+1}=\mathrm{isAlias}(p, v_i)$ einfügen
\item Aliase: Verschiedene Möglichkeiten auf gleiche Speicherstelle zuzugreifen
\item Sprachabhängige Quellen von Aliasen: \begin{itemize}
\item dynamisch allokierte Datenstrukturen
\item Zeiger
\item überlappende Speicherbereiche
\item Referenzen auf Arrays, -Abschnitte, -Dimensionen und -Elemente
\item Prozedurparameter
\item Zeigerarithmetik
\end{itemize}
\item Sprachunabhängige Quellen wie Transitivität ($a$ zeigt auf $b$ und $b$ zeigt auf $c$$\rightarrow$$c$ ist von $a$ erreichbar)
\item TODO: Aliase in Fortran, Pascal, C und Java (VL-07)
\item mögliche Aliase (may) müssen nur in einem Pfad Aliase sein
\item sichere Aliase (must) müssen in allen Pfaden Aliase sein
\item Fluss-ignorierende Analyse bestimmt, ob Namen irgendwo im KFG Aliase sein können: \begin{itemize}
\item vergleichsweise einfach berechenbar
\item oft für interprozedurale Analyse eingesetzt
\item Relation $\mathrm{Alias}(a, b)$ gibt an, dass $a$ und $b$ für ganze Prozedur Aliase sind, ist reflexiv, symmetrisch und bei must-Analyse auch transitiv
\end{itemize}
\item Fluss-sensitive Analyse bestimmt, ob Namen in einem Basisblock Aliase sein können: \begin{itemize}
\item aufwändige Berechnung
\item oft für intraprozedurale Analyse eingesetzt
\item Funktion $\mathrm{Alias}(P, v)= S$ gibt an, dass $v$ an Programmpunkt $P$ auf Speicherstelle $S$ zeigen kann
\item Bei may-Analyse: \begin{itemize}
\item$\mathrm{Alias}(P, v_1)\cap\mathrm{Alias}(P, v_2)\neq\emptyset\Leftrightarrow$$v_1, v_2$ sind in $P$ Aliase
\item nicht transitiv
\end{itemize}
\item Bei must-Analyse: \begin{itemize}
\item$\vert\mathrm{Alias}(P, v)\vert=1$, Aliase wenn Speicherstelle gleich
\item transitiv
\end{itemize}
\end{itemize}
\item intraprozedurale Analyse: \begin{itemize}
\item Betrachtung einer einzelnen Prozedur
\item Worst-Case-Annahmen bei Aufruf anderer Prozedur
\item häufig auf Datenflussproblem zurückgeführt
\end{itemize}
\item interprozedurale Analyse: \begin{itemize}
\item Standard-Verfahren
\item Andersens Algorithmus
\item Steensgards Algorithmus
\end{itemize}
\end{itemize}
\subsection{DFA-Ansatz zur intraprozeduralen, fluss-sensitiven may-Analyse nach Muchnick}
\item\texttt{*x = a}: $\mathit{ptr}_P(x)=\mathit{ptr}_{P'}(x)$, zusätzlich wenn \texttt{*x} Zeiger $\mathit{ptr}_P(*x)=\mathit{ptr}_{P'}(*x)\cup\mathit{ptr}_{P'}(a)$
\item\texttt{f(...)}: \begin{itemize}
\item$G$: Menge der global sichtbaren Zeiger
\item$L$: Menge der lokalen Variablen im Aufrufer, deren Adresse berechnet wurde
\item$\forall x \in G \cup L:\,\mathit{ptr}_P(x)=\left(\cup_{g \in(G \cup\mathit{mem}(G))}\mathit{ref}_{P'}(g)\right)\cup\left(\cup_{l\in L}\mathit{ref}_{P'}(l)\right)$
\item Alias-Quellen in Sprachen ohne \&-Operator: \begin{itemize}
\item Übergabe globaler Variable an Funktion
\item Übergabe der gleichen Variable an mehrere formale Parameter einer Funktion
\item Zugriff auf umgebende Variablen/formale Parameter bei geschachtelten Prozeduren (vgl. globale Variablen)
\end{itemize}
\item Prozeduraufrufgraph (PCG): \begin{itemize}
\item Knoten: Prozeduren des Programms
\item Gerichtete Kante von $p$ nach $q$ wenn $p$$q$ aufrufen kann
\end{itemize}
\item Variablenbindungsgraph: \begin{itemize}
\item Knoten: formale Parameter
\item Gerichtete Kante von $x$ nach $y$ wenn $(p, q)$ in PCG, $x$ formaler Parameter von $p$ und $x$ Argument für formalen Parameter $y$ von $q$
\item transitiver Abschluss liefert Alias-Menge der formalen Parameter (aber globale Variablen sind nicht berücksichtigt)
\end{itemize}
\item Paarbindungsgraph: \begin{itemize}
\item Knoten: alle Paare formaler Parameter
\item Gerichtete Kante von $(x, y)$ nach $(X, Y)$, wenn \begin{itemize}
\item$(x,y)$ bei einem Anruf an $(X,Y)$ gebunden werden oder
\item$(x,y)$ bei einem Aufruf im Inneren einer geschachtelten Prozedur an $(X, Y)$ gebunden werden, wobei ggf. Aliase von $x$ oder $y$ verwendet werden
\item Bindungen von globalen Variablen an formalen Parametern entdecken
\item Aus Pfaden in Variablenbindungsgraph zusätzliche formale Parameter, an die globale Variable weitergegeben werden können, bestimmen (in topologischer Reihenfolge durchlaufen; bei Zyklen bis Fixpunkt erreicht)
\item Aliase der globalen Variablen ablesen
\end{enumerate}
\item Parameterpaare als Aliase: Zwei formale Parameter sind Aliase, wenn \begin{itemize}
\item die gleiche Variable an beide übergeben wird
\item eine globale Variable und einer ihrer Aliase übergeben wird
\end{itemize}\begin{enumerate}
\item Betrachtung aller Paare formaler Parameter
\item Markierung der Paare, die beim Aufruf zu Alias-Paaren werden können
\item Propagation von Alias-Informationen durch den PCG
\item$b$ ist kein Zeiger bzw. noch nicht erkannt: Annotiere $b$ mit $\lbrace a = b\rbrace$ (Falls später Zeigerziel $y$ von $b$ entdeckt wird, muss Kante von $a$ nach $y$ ergänzt werden)
\item Markierung aller konstanten Ausdrücke und Variablen, sowie alle Markierung, deren erreichende Definitionen außerhalb der Schleife liegen, als schleifeninvariant
\item Solange neue Markierungen auftreten: alle Instruktionen/Variablen als schleifeninvariant markieren, wenn \begin{itemize}
\item sie konstant sind oder
\item wenn alle erreichenden Definitionen außerhalb der Schleife liegen oder
\item wenn genau eine erreichende Definition existiert und diese als schleifeninvariant markiert ist
\end{itemize}
\end{enumerate}
\item Herausziehen von schleifeninvarianten (Teil-)Ausdrücken vor den Schleifenkopf unter Beachtung von Seiteneffekten/Fehlern immer möglich
\item Auswahl von herausziehbaren Zuweisungen: \begin{enumerate}
\item Berechnung der Dominanz, erreichenden Definitionen und Anwendung von Konstantenfaltung
\item Berechnung der invarianten Instruktionen
\item Bestimmung der Schleifenausgänge, also Knoten, die KFG-Nachfolger außerhalb der natürlichen Schleife besitzen
\item Alle Anforderungen an Zuweisungen müssen für Herausziehbarkeit gelten:\begin{itemize}
\item in Grundblock, der alle Schleifenausgänge, nach denen die Variable lebendig ist, dominiert und alle die Variable nutzenden Blöcke strikt dominiert (oder in definierendem Block nach Definition auftritt)
\item einzige Zuweisung zu Variable in der ganzen Schleife
\end{itemize}
\item Herausziehen vor den Schleifenkopf in Breitensuchreihenfolge zur Bewahrung der Datenabhängigkeiten zwischen herausgezogenen Zuweisungen
\end{enumerate}
\item Sonderfall while-Schleife: Schleifenausgang wird von keinem anderen Grundblock in der Schleife dominiert, also keine herausziehbaren Zuweisungen in der Schleife $\rightarrow$ erst Umbau zu do-while-Schleife
\item Optimierung bei invariantem Test: Generierung einer eigenen Schleife für jeden Fall
\item Induktionsvariable: Variable, die bei jeder Schleifeniteration um konstanten Wert inkrementiert oder dekrementiert wird
\item Einfache Induktionsvariable: Variable $x$, die nur durch $x = x \pm c$ mit schleifeninvariantem $c$ verändert wird
\item Abhängige Induktionsvariable: Variable $y$, die in der Schleife durch $y = a \cdot x \pm b$ mit schleifeninvarianten $a$ und $b$ als lineare Funktion aus Induktionsvariable $x$ berechnet wird
\item Berechnung der Familie einer einfachen Induktionsvariable $x$: Menge der Induktionsvariablen $y$, die mit linearer Funktion $y = c_1\cdot x \pm c_2$ von $x$ mit schleifeninvarianten $c_1$ und $c_2$ abhängen: \begin{itemize}
\item Zuweisung der Form $y = c_1\cdot x \pm c_2$
\item Zuweisung der Form $y = c_1\cdot z \pm c_2$, wobei $z \in\mathrm{Familie}(x)$ und \begin{itemize}
\item keine Veränderung von $x$ zwischen Zuweisung zu $z$ und Zuweisung zu $y$
\item keine von außerhalb der Schleife erreichende Definition von $z$ erreicht Zuweisung zu $y$
\end{itemize}
\end{itemize}
\item Berechnungen der Tripel $(x, c_1, c_2)$ für alle Induktionsvariablen $y$ einer Schleife:\begin{enumerate}
\item Berechnung von Schleifeninvarianz und erreichenden Definitionen
\item Bestimmung aller einfachen Induktionsvariablen durch Code-Inspektion (\enquote{Pattern Matching})
\item Bestimmung aller Variablen $y$ mit einziger (oder identischen) Zuweisung der Form $y = x \pm c$ oder $y = c \cdot x$ mit $x$ Induktionsvariable und $c$ schleifeninvariant:\begin{itemize}
\item$x$ ist einfache Induktionsvariable:
\begin{equation*}
\mathrm{Tripel}(y) = \begin{cases*}
(x, 1, c) & falls $y = x + c$ oder $y = c + x$\\
(x, 1, -c)& falls $y = x - c$\\
(x, c, 0)& sonst ($y = x \cdot c$ oder $y = c \cdot x$)
\end{cases*}
\end{equation*}
\item$x$ ist abhängige Induktionsvariable mit Tupel $(u, d_1, d_2)$:
\begin{equation*}
\mathrm{Tripel}(y) = \begin{cases*}
(u, d_1, d_2 + c) & falls $y = x + c$ oder $y = c + x$\\
(u, d_1, d_2 - c) & falls $y = x - c$\\
(u, d_1 \cdot c, d_2 \cdot c_2) & sonst ($y = c \cdot x$ oder $y = x \cdot c$)
\end{cases*}
\end{equation*}
\end{itemize}
\end{enumerate}
\item Vereinfachung der Berechnungsvorschrift von Schleifenlaufvariablen pro Iteration (Reduktion der Ausdrucksstärke, \enquote{Strength Reduction}) für jede einfache Induktionsvariable $x$: \begin{enumerate}
\item Für jede von $x$ abhängige Induktionsvariable $y$ mit Tripel $(x, a, b)$:\begin{enumerate}
\item Einführung neuer Variable $y'$
\item Ersetzung der Zuweisung zu $y$ durch $y = y'$
\item Einfügen der Zuweisung $y' = y' \pm(a \cdot c)$ nach jeder Zuweisung $x = x \pm c$
\item Einfügen der Zuweisung $y' = x\cdot a + b$ vor dem Schleifenkopf
\end{enumerate}
\end{enumerate}
\item Modifikation von bedingten Sprüngen ggf. möglich
\item Verringerung der Anzahl von Array-Bereichstests ggf. möglich
\item lexikographische Ordnung auf Iterationsvektoren
\item$i \angle j$$\Leftrightarrow$ Iteration $i$ zur Laufzeit vor Iteration $j$
\end{itemize}
\item Iterationsraum: Menge aller möglichen Iterationsvektoren
\item Abhängigkeitsdistanz (bei geschachtelten Schleifen Vektor) $d$: Bei Datenabhängigkeit zwischen Iteration $i_\mathrm{source}$ und $j_\mathrm{target}$ und $i_\mathrm{source}\angle j_\mathrm{target}$, dann $i_\mathrm{source}+ d = j_\mathrm{target}$
\item Abhängigkeitsrichtung: Vergröberung der Abhängigkeitsdistanz mit folgenden Ersetzungen an jeder Position des Vektors: \begin{equation*}
r_i = \begin{cases*}
= & falls $0= d_i$\\
< & falls $0 < d_i$\\
> & falls $0 > d_i$
\end{cases*}
\end{equation*}
\item Richtungsvektor: Zusammenfassung aller Abhängigkeitsrichtungen einer Schleife:\begin{itemize}
\item\enquote{übliche} Zusammenfassungen (z.B. $=$ und $<$ zu $\leq$)
\item keine Aussage $*$ bei $<$ und $>$
\end{itemize}
\item Die Abhängigkeit tragende Schleife $p$ folgt aus der Struktur der Abhängigkeitsdistanzen bei Inkrementschleifen:
\item Parallele Ausführbarkeit aller Iterationen einer Schleife $p$ gegeben, wenn \begin{itemize}
\item diese keine Abhängigkeit trägt (alle Abhängigkeitsdistanzen haben $d_p =0$) oder
\item jede schleifengetragene Abhängigkeit von einer $p$ umgebenden Schleife getragen wird (für jede Abhängigkeitsdistanz $\exists q < p: d_q > 0$)
\end{itemize}
\item Parallele Ausführung nicht immer gewinnbringend, da auf Cache-Ebene Abhängigkeiten auftreten können (\enquote{False Sharing})
\item Optimierungsmöglichkeiten:\begin{itemize}
\item Skalare Ersetzung von Array-Ausdrücken (\enquote{register pipelining}), wenn: \begin{itemize}
\item Abhängigkeit wird von innerster Schleife getragen
\item Konstante Abhängigkeitsdistanz $d$
\item$d+1$ freie Register
\end{itemize}\begin{enumerate}
\item Vor Schleife Initialisierung der Register und \enquote{Abschälen} der ersten $d$ Iterationen
\item In Schleife Benutzung der Register bei Lesezugriff und Speicherung der Registerinhalte bei Speicherzugriff, sowie am Anfang des Rumpfs \enquote{Aufrücken} der Register
\end{enumerate}
\item Skalar-Vervielfachung: Einführung eines Arrays zur Elimination von unnötigen Abhängigkeiten einer Temporärvariable
\item Verbesserung der zeitlichen Lokalität durch optimierte Registerverwendung
\item Verbesserung der räumlichen Lokalität durch optimierte Cache-Verwendung
\item Parallelisierung/Vektorisierung von Schleifen
\item Daten-/Prozessplatzierung zur Kommunikationsoptimierung
\item$\exists I, J: I=(i_1, \textellipsis, i_d)\angle J =(j_1, \textellipsis, j_d)$ mit $I, J$ innerhalb der Schleifengrenzen (Ungleichunssystem mit Nebenbedingungen)
\item$\forall p: f_p(I)= g_p(J)$ (Gleichungssystem mit Schleifenlaufvariablen als Variablen und Konstanten aus linearem Index-Ausdruck als Koeffizienten)
\end{itemize}
\item Aus Laufzeitgründen lediglich Tests, sonst pessimistische Grundannahme: \begin{itemize}
\item GGT-Test:\begin{enumerate}
\item Gleichsetzen der beiden Array-Ausdrücke
\item Konstante auf eine Seite umformen
\item Abhängigkeit nur dann möglich, wenn der größte gemeinsame Teiler der Koeffizienten die Konstante teilt
\item Für verschiedene Arten der Abhängigkeit in obige Kriterien einsetzen
\item Legalität: Für jede Datenabhängigkeit muss die relative Reihenfolge auch nach Anwendung der Transformation bzw. Restrukturierung erhalten bleiben, d.h. die entstehenden Abhängigkeits\-distanz\-vektoren dürfen nicht lexikographisch negativ sein und müssen ihre Datenabhängigkeitsart behalten
\item Zusammenfassen der Rümpfe mehrerer Schleifen
\item Voraussetzungen:\begin{itemize}
\item beide Schleifen haben gleichen Indexbereich
\item Namensgleichheit beider Laufvariablen kann durch Umbenennung erreicht werden
\item Bei keiner Skalarnutzung in zweiter Schleife darf es erreichende Definition aus anderer Schleife geben
\end{itemize}
\item Legalität: Es darf keine Abhängigkeit zwischen einer Instruktion aus der zweiten Schleife mit einer aus der ersten in einer späteren Iteration entstehen
\item Reduktion des Schleifenoverheads
\item größere Grundblöcke erlauben effizientere lokale Optimierungen
\item ggf. verbesserte zeitliche Lokalität
\end{itemize}
\item Rumpfteilen:\begin{itemize}
\item Aufteilen des Rumpfs einer Schleife auf mehrere Schleifen
\item Gegenteil der Verschmelzung
\item Legalität: \begin{itemize}
\item Anweisungen, die in starken Zusammenhangskomponenten des Abhängigkeitsgraphs der zu teilenden Schleife liegen, dürfen nicht auf verschiedene Schleifen verteilt werden
\item Reihenfolge der Schleifen muss Abhängigkeiten vor dem Teilen widerspiegeln