Zweig (Informatik)

A Zweig ist eine Anweisung in a Computer Programm Dies kann dazu führen, dass ein Computer mit der Ausführung einer anderen Anweisungssequenz beginnt und somit von seinem Standardverhalten der Ausführung von Anweisungen in der Reihenfolge abweichen.^[a] Zweig (oder Verzweigung, verzweigt) kann auch auf den Akt des Umschaltens auf eine andere Befehlssequenz als Ergebnis der Ausführung eines Zweiganweiss verweisen. Branch -Anweisungen werden zur Implementierung verwendet Steuerfluss In Programmschleifen und Bedingungen (d. H. Ausführende Ausführung einer bestimmten Anweisungen nur dann, wenn bestimmte Bedingungen erfüllt sind).

Ein Zweiganweis kann entweder eine sein bedingungslose Zweige, was immer zu Verzweigungen oder a führt bedingter Zweig, was je nach Bedingung Verzweigungen verursachen kann oder nicht. Je nachdem, wie sie die Adresse der neuen Anweisungssequenz (die Adresse "Ziel) angibt, wird eine Zweiganweisung allgemein als klassifiziert als Direkte, indirekt oder relativDies bedeutet, dass die Anweisung die Zieladresse enthält oder angibt, wo die Zieladresse gefunden wird (z. B. ein Register- oder Speicherort), oder die Differenz zwischen den Strom- und Zieladressen angibt.

Implementierung

Zweiganweisungen können den Inhalt des Zentralprozessor's Programm zähler (oder PC) (oder Anweisungszeiger auf Intel -Mikroprozessoren). Der PC führt die Speicheradresse der nächsten Maschinenanweisung bei, die abgerufen und ausgeführt werden soll. Wenn eine Zweigstelle ausgeführt wird, führt die CPU dazu, Code aus einer neuen Speicheradresse auszuführen und die Programmlogik gemäß dem vom Programmierer geplanten Algorithmus zu ändern.

Eine Art von Maschinenebene -Zweig ist der Sprunganweisung. Diese können dazu führen, dass der PC mit einem neuen, anderen Wert geladen oder geändert wird, als es normalerweise gewesen wäre (inkrementiert an der aktuellen Anweisung, um auf die folgende Anweisung zu verweisen). Sprünge haben normalerweise bedingungslos und bedingt Formen, an denen letzteres sein kann vergriffen oder nicht vergeben (Der PC wird abhängig von einer Bedingung geändert oder nicht).

Die zweite Art von Maschinenebene -Zweig ist der Anrufanweisung die zur Implementierung verwendet wird Unterroutinen. Wie Jump -Anweisungen können Anrufe den PC nach Bedingungscodes ändern oder nicht. Zusätzlich ist jedoch a Absender wird an einem sicheren Ort im Speicher gespeichert (normalerweise in einer Speicher Datenstruktur, die als a genannt wird Stapel). Nach Abschluss der Unterroutine wird diese Absenderadresse auf den PC wiederhergestellt. Daher wird die Programmausführung mit der Anweisung nach der Anrufbefehlsnutzung fortgesetzt.

Die dritte Art von Maschinenebene -Zweig ist der Anweisung zurückgeben. Diese "Pops" einer Rückgabedresse aus dem Stapel und lädt ihn in das PC -Register ein, wodurch die Kontrolle an die Anrufroutine zurückgibt. Rückgabebehörungen können auch bedingt ausgeführt werden. Diese Beschreibung betrifft die gewöhnliche Praxis; Der Maschinenprogrammierer verfügt jedoch über beträchtliche Befugnisse, um die Absenderadresse auf dem Stapel zu manipulieren und die Programmausführung auf eine beliebige Anzahl von unterschiedlichen Arten umzuleiten.

Abhängig vom Prozessor können Sprung- und Anrufanweisungen den Inhalt des PC -Registers auf unterschiedliche Weise ändern. Eine absolute Adresse kann geladen werden, oder der aktuelle Inhalt des PC kann einen gewissen Wert (oder eine Verschiebung) aufweisen oder von seinem aktuellen Wert subtrahiert werden, wodurch die Zieladresse relativ zum aktuellen Ort im Programm ist. Die Quelle des Verschiebungswerts kann variieren, z. B. ein in die Anweisung eingebetteter unmittelbarer Wert oder der Inhalt eines Prozessorregisters oder Speicherorts oder der Inhalt eines Ortes, der einem Indexwert hinzugefügt wurde.

Der Begriff Zweig kann auch verwendet werden, wenn sie sich auf Programme in beziehen hochrangige Programmiersprachen. In diesen Zweigen nehmen normalerweise die Form von an Bedingte Aussagen von verschiedenen Formen, die die Anweisungssequenz zusammenfassen, die ausgeführt wird, wenn die Bedingungen erfüllt sind. Bedingungslose Zweiganweisungen wie z. GEHE ZU werden verwendet, um bedingungslos zu einer anderen Anweisungssequenz zu springen. Wenn der Algorithmus einen bedingten Zweig erfordert, wird der GOTO (oder der Gosub -Unterroutine -Aufruf) von einem vorgegangen WENN, DANN Anweisung, in dem die Bedingungen angegeben werden. Alle Sprachen auf hoher Ebene unterstützen Algorithmen, die Code als Wiederverwendung als Wiederverwendung Schleife, Eine Kontrollstruktur, die eine Abfolge von Anweisungen wiederholt, bis ein gewisses Zustand erfüllt ist, der dazu führt, dass die Schleife endet. Loops qualifizieren sich auch als Zweiganweisungen. Auf Maschinenebene werden Schleifen als gewöhnliche bedingte Sprünge implementiert, die die Ausführung in den Wiederholungscode umleiten.

In CPUs mit FahnenregisterEine frühere Anweisung legt eine Bedingung im Flag -Register fest. Die frühere Anweisung kann sein Arithmetik oder eine Logik Anweisung. Es liegt oft in der Nähe des Zweigs, wenn auch nicht unbedingt die Anweisung sofort vor dem Zweig. Der gespeicherte Zustand wird dann in einem Zweig wie verwendet, z. Springen Sie, wenn Überlauf-Flag-Set. Diese temporären Informationen werden häufig in einem Flaggenregister gespeichert, können jedoch auch an anderer Stelle gefunden werden. Ein Flag -Registerdesign ist in langsameren, einfachen Computern einfach. In schnellen Computern kann ein Flag -Register einen Engpass für Geschwindigkeit platzieren, da Anweisungen, die sonst parallel funktionieren könnten (in mehreren Ausführungseinheiten) müssen die Flag -Bits in einer bestimmten Reihenfolge einstellen.

Es gibt auch Maschinen (oder bestimmte Anweisungen) Branch <Label> Wenn registrieren x negativ. In einfachen Computerkonstruktionen führen Vergleichszweige mehr Arithmetik aus und können mehr Strom als Flag -Registerzweige verwenden. In schnellen Computer -Designs können Vergleichszweige schneller als Flag -Registerzweige ausgeführt werden, da Vergleichszweige mit denselben CPU -Mechanismen wie Berechnungsberechnung auf die Register zugreifen können.

Einige frühe und einfache CPU -Architekturen, die immer noch in Mikrocontrollern enthalten sind, implementieren möglicherweise keinen bedingten Sprung, sondern nur einen bedingten "Überspringen Sie den nächsten Anweisungen". Ein bedingter Sprung oder Aufruf wird somit als bedingte Übersprung eines bedingungslosen Sprung- oder Anrufbefehls implementiert.

Beispiele

Abhängig von Rechnerarchitektur, das Montagesprache mnemonisch Für eine Sprunganweisung ist normalerweise eine verkürzte Form des Wortes springen oder das Wort Zweigoft zusammen mit anderen informativen Buchstaben (oder einem zusätzlichen Parameter), die die Bedingung darstellen. Manchmal sind auch andere Details enthalten, wie z. B. der Bereich des Sprung (die Offset -Größe) oder einen speziellen Adressierungsmodus, mit dem der tatsächliche effektive Offset lokalisiert werden sollte.

Diese Tabelle listet den Maschinenstufe-Zweig oder die Sprunganweisungen in mehreren bekannten Architekturen auf:

^* X86, PDP-11, VAX und einige andere setzen die Tragflagge auf Signal ausleihen und löschen Sie die Tragflagge, um zu signalisieren Kein Ausleihen. ARM, 6502Das Bild und einige andere tun das Gegenteil für subtraktive Operationen. Diese umgekehrte Funktion des Tragflags für bestimmte Anweisungen ist gekennzeichnet durch ((^*), das ist, liehen =nicht tragen In einigen Teilen der Tabelle, aber wenn nicht sonst nicht notiert, bloßaren Zeig. Die additiven Operationen werden jedoch von den meisten Architekturen auf die gleiche Weise behandelt.

Leistungsprobleme mit Branchenanweisungen

Um hohe Leistung zu erzielen, sind moderne Prozessoren Pipeline. Sie bestehen aus mehreren Teilen, die jeweils teilweise eine Anweisung verarbeiten, ihre Ergebnisse in die nächste Stufe in der Pipeline versorgen und an der nächsten Anweisung im Programm arbeiten. Dieses Design erwartet Anweisungen in einer bestimmten unveränderlichen Sequenz. Bedingte Zweiganweisungen machen es unmöglich, diese Sequenz zu kennen. Daher können bedingte Zweige "Stände" verursachen, in denen die Pipeline in einem anderen Teil des Programms neu gestartet werden muss.

Verbesserung der Leistung durch Reduzierung von Ständen aus Zweigen

Verschiedene Techniken verbessern die Geschwindigkeit, indem sie die Stände aus bedingten Zweigen reduzieren.

Zweigvorhersage Hinweise

Historisch gesehen hat die Vorhersage der Branche Statistiken und das Ergebnis zur Optimierung des Codes verwendet. Ein Programmierer würde eine Testversion eines Programms zusammenstellen und mit Testdaten ausführen. Der Testcode zählte, wie die Zweige tatsächlich genommen wurden. Die Statistiken aus dem Testcode wurden dann vom Compiler verwendet, um die Zweige des freigegebenen Code zu optimieren. Die Optimierung würde ordnen, dass die schnellste Zweigrichtung (genommen oder nicht) immer der am häufigsten übernommene Kontrollflusspfad ist. Um dies zuzulassen, muss CPUs mit vorhersehbarem Zweig -Timing ausgelegt sein (oder zumindest). Einige CPUs haben Anweisungssätze (wie die Macht ISA), die mit "Zweignoten" entworfen wurden, damit ein Compiler einer CPU erkennen kann, wie jeder Zweig genommen werden soll.

Das Problem bei der Vorhersage von Software Branch ist, dass es einen komplexen Softwareentwicklungsprozess erfordert.

Hardware -Zweig -Prädiktoren

Hardware ausführen, um eine Software auszuführen Zweigprädiktoren bewegte die Statistiken in die Elektronik. Zweigprädiktoren sind Teile eines Prozessors, die das Ergebnis eines bedingten Zweigs erraten. Dann spielt die logischen Spiele des Prozessors auf der Vermutung, indem sie den erwarteten Befehlsfluss ausführen. Ein Beispiel für ein einfaches Vorhersageschema für Hardware -Zweig -Vorhersagen ist die Annahme, dass alle Rückwärtszweige (d. H. Zu einem kleineren Programmzähler) (weil sie Teil einer Schleife sind) und alle Vorwärtszweige (zu einem größeren Programmzähler) nicht eingenommen werden (Weil sie eine Schleife verlassen). Bessere Branchenprädiktoren werden statistisch entwickelt und validiert, indem sie in einer Vielzahl von Testprogrammen in Simulation ausgeführt werden. Gute Prädiktoren zählen normalerweise die Ergebnisse früherer Hinrichtungen einer Niederlassung. Schnellere, teurere Computer können dann schneller laufen, indem sie in eine Elektronik für eine bessere Zweigvorhersage -Elektronik investieren. In einer CPU mit Hardware Branch Prediction lassen Zweig -Hinweise die vermutlich überlegene Branchenvorhersage des Compilers die vereinfachte Vorhersage der Hardware überschreiben.

Zweigfreier Code

Eine Logik kann ohne Zweige oder mit weniger Zweigen geschrieben werden. Es ist oft möglich zu verwenden Bitgewise Operations, bedingte Bewegungen oder andere Prädikation anstelle von Zweigen.^[1][2] In der Tat ist der Zweig-freie Code ein Muss für die Kryptographie aufgrund von Timing -Angriffe.^[3]

Verspätungsschlitz

Eine andere Technik ist a Zweigverzögerungsschlitz.Bei diesem Ansatz wird immer eine Anweisung nach einem Zweig ausgeführt.Daher kann der Computer diese Anweisung verwenden, um nützliche Arbeiten zu erledigen, unabhängig davon, ob seine Pipeline -Stände stehen oder nicht.Dieser Ansatz war historisch beliebt in RISC Computers.In einer Familie kompatibler CPUs kompliziert es Multicycle-CPUs (ohne Pipeline), schnellere CPUs mit länger als erwarteten Pipelines und über-superscalarar-CPUs (die Anweisungen außerhalb der Reihenfolge ausführen können).

Siehe auch

• Zweigverzögerungsschlitz
• Branchenprädikation
• Zweigtisch
• Bedingt (Programmierung)
• Steuerfluss
• Indirekter Zweig
• Programm zähler
• Subroutine
• Spaghetti -Code

Anmerkungen

Verweise

Externe Links

• Kostenlose Dokumentation IA-32 und X86-64, bereitgestellt von Intel
• Die PDP-11-FAQ
• Der Armleitungssatz