Suchen und Ersetzen von Arrayelementen

Algorithmen, Sprachunabhängige Diskussionen zu Konzepten, Programmiersprachen-Design
Antworten
bobpcur
Beiträge: 13
Registriert: Mi Nov 30, 2016 10:03 am

Suchen und Ersetzen von Arrayelementen

Beitrag von bobpcur » Mi Nov 30, 2016 10:55 am

Hallo,
ich beschäftige mich momentan mit einem Assembler Code. Der Code wurde von einem Compiler generiert und benutzt deswegen deutlich mehr Variablen als wenn der Code von einem Menschen geschrieben werden würde. Nun, mir ist bewusst, dass Assembler keine Variablen, sondern nur Bits, Bytes und Register kennt. Als "Variablen" bezeichne ich einen bestimmten Wert, der zum festen Zeitpunkt zum Beispiel im Register R0 steht. Ich habe einen Algorithmus ausgedacht, mit denen man die Anzahl von verwendeten Registern reduzieren könnte und bitte darum, mir etwas Fachsprache bei der Formulierung von dem Algorithmus beizubringen.

Zunächst die Voraussetzungen: Was braucht mein Algorithmus?
Mein Algorithmus braucht den generierten Assemblercode -> check, diesen kann ich mir bereits in der Matlab Kommandozeile anzeigen lassen.
Mein Algorithmus braucht eine Liste der Variablennamen, welche im Code verwendet werden -> auch diese kann ich mir bereits anzeigen lassen.

Idee:
Wenn zum Beispiel m Assembler Code steht: add X Y, und die Variable X im Register 0 steht, die Variable Y im Register 1, dann werden beiden Variablen addiert und das Ergebnis in das Register 0 geschrieben. Falls nun im Code nirgendswo mehr die Variable Y, gelesen oder geschrieben wird, kann man diesen Namen (bzw. somit das Register 1) mit einem anderen Wert belegen. Das heisst, wenn weiter im Code eine Zeile auftaucht mit zum Bsp. add Z W, dann kann man die Y-Variable (und somit das Register 1) zum Beispiel der Variable Z geben. Somit wäre der Code um einen Register (der, wo Z steht) reduziert. Das Problem für den Algorithmus lässt sich zu einer Suche in einem Array reduzieren. Da der Code im wesentlichen ein Array darstellt, wo jedes Array Element eine Assembler Anweisung ist. Die Elemente nach denen gesucht werden soll, stehen dabei bereits in einem anderen Array zur Verfügung.

Umsetzung:
1. Öffnen Assembler Code (Array 1) und Variablenliste (Array 2)
2. Vertauschen der Reihenfolge der Code Zeilen ->damit wird erreicht, dass immer die zuletzt vorkommenden Variablen als erstes gelesen werden
3. Zeilenweise Einlesen des "geflippten" Code -> Bedienung für die While Schleife
4. Suche Array 1 nach jedem Element aus Array 2 durch und markiere die entsprechenden Stellen im Array 1 -> hier würde ich eine For Schleife benutzen, für die Anzahl der Elemente des Array 2
5. Speichere die ersten (eigentlich ja die letzten, weil das Array 1 geflippt ist) vorkommenden Variablennamen im Array 3 ab. -> über For Schleife Array 3 bauen
6. Ersetze im Array 1 die letzten markierten Stellen mit den Elementen aus Array 3.
7. Schließen und speichern.

Nun zu meinen Fragen. Bevor ich in Matlab drauflos programmiere, kann der Algorithmus überhaupt funktionieren, oder habe ich aufgrund des fehlenden Informatikwissens den letzten Unsinn formuliert?
Das Array 3 wird eine unbekannte Anzahl an Elementen haben, ich habe gelesen statt nur Arrays gibt es auch Listen. Der Hauptunterschied zu den Arrays ist, Listen haben Zeiger (sowas wie Vektoren in der Geometrie), mit denen man flexibel Elemente zu der Liste hinzufügen kann. Kann man über diese Zeiger die Elemente (aus Array 1 in meinem Fall) auch löschen? Ich hoffe ich übersehe nichts und konnte mein Problem kurz und verständlich darstellen.

Vielen Dank für die Aufmerksamkeit und beste Grüße, Robert.

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3081
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Suchen und Ersetzen von Arrayelementen

Beitrag von cloidnerux » Mi Nov 30, 2016 11:44 am

ich beschäftige mich momentan mit einem Assembler Code. Der Code wurde von einem Compiler generiert und benutzt deswegen deutlich mehr Variablen als wenn der Code von einem Menschen geschrieben werden würd
Es stellt sich die Frage, warum es denn ein Problem ist, dass mehrere Register genutzt werden?
Wenn zum Beispiel m Assembler Code steht: add X Y, und die Variable X im Register 0 steht, die Variable Y im Register 1, dann werden beiden Variablen addiert und das Ergebnis in das Register 0 geschrieben. Falls nun im Code nirgendswo mehr die Variable Y, gelesen oder geschrieben wird, kann man diesen Namen (bzw. somit das Register 1) mit einem anderen Wert belegen. Das heisst, wenn weiter im Code eine Zeile auftaucht mit zum Bsp. add Z W, dann kann man die Y-Variable (und somit das Register 1) zum Beispiel der Variable Z geben. Somit wäre der Code um einen Register (der, wo Z steht) reduziert.
Auch hier die Aussage: macht das dein Compiler nicht schon? Weiterhin musst du auch beachten, dass der Wert in Register 1 an einer anderen Stelle genutzt werden könnte, die du nicht erfasst. Du musst also erfassen, ob ein Register nach der ersten Operation weiter verwendet wird oder nicht sowieso schon ein neuer Wert in dieses hinein geladen wird.

Auch ein prinzipieller Hinweis: CPU Register sind nicht Arbeitsspeicher, ungenutzte Register werden nicht der Allgemeinheit zurück gegeben, die Register bleiben immer dem aktuellen Thread zugeordnet. Ob dein Programm jetzt 2 oder alle Register nutzt spielt daher keine Rolle. Es kann sogar von vorteil sein. Durch das nutzten mehrerer Register können Werte schon geladen werden, während noch eine Operation in Gange ist. Auch kann es sein, dass der Compiler den Code für Branching und andere Optimierungen auslegt.
Dazu auch mal ein Verweis auf einen kleinen Wettbewerb den wir hier mal veranstaltet haben:
https://proggen.org/doku.php?id=project:wordcount
Das Resultat ist, dass man als Programmierer nicht besser darin ist, Assembler zu schreiben, als ein Compiler.

Zu deinem Algorithmus:
Du setzt soweit ich das nachvollziehen kann voraus, dass es ein Mapping Variable(Name)->Register gibt. Du gehst davon aus, dass alle Variablen Namen eindeutig in ihrem Namen und Verwendung sind. Du versuchst dann ein Array zu erstellen, dass die Verwendung der Variablen im Assembler Code nach ihrer Position im Code in umgekehrter Reinfolge zu erstellen und danach dann eine neue Zuweisung Variable->Register durchzuführen.
Dabei gibt es aber mehrere Probleme: Du hast Sprung und Verzweigungsoperationen, ein Laden von Daten in ein Register kann im Assemblercode später passieren, als die Nutzung des Wertes. Du hast Pointeroperationen, die die Variablennamen maskieren(Zugriff auf ein Array Element z.B).
Deine Variablennamen im Quellcode sind nicht immer eindeutig, du hast so sehr häufig Laufvariablen wie i oder andere häufig verwendete Namen.
Viele Assembleroperationen greifen auf Register zu, ohne diese explizit anzugeben. Dein Algorithmus muss also die Assemblerinstruktionen kennen, um zu verhindern, dass Ergebnisse aus Berechnungen nicht überschrieben werden.
Redundanz macht wiederholen unnötig.
quod erat expectandum

mfro
Beiträge: 305
Registriert: Mi Jan 16, 2013 4:58 pm

Re: Suchen und Ersetzen von Arrayelementen

Beitrag von mfro » Mi Nov 30, 2016 11:49 am

Eins voraus: ich habe nicht die leiseste Ahnung, ob ich das Problem, das Du da lösen willst, komplett verstanden habe.

Aber:

Assembler-Programme laufen in den seltensten Fällen linear "von oben nach unten" ab. Da gibt es Schleifen und Sprünge und solange Du den Programmfluß nicht komplett analysiert hast, kannst Du nicht davon ausgehen, daß "weiter oben" auch "zeitlich früher" heißt und weißt damit auch nicht, wann ein Register tatsächlich nicht mehr gebraucht wird. Der einzig klare Indikator dafür ist, wenn es mit einem neuen Wert überschrieben wird.

Bei Von-Neumann-Architekturen (das sind die meisten) können Code und Daten im Binärcode gemischt vorkommen. Ohne eine Ablaufanalyse kannst Du nicht wissen, was was ist und wirst möglicherweise Daten als Code interpretieren.

Kannst Du damit was anfangen?
It's as simple as that. And remember, Beethoven wrote his first symphony in C.

bobpcur
Beiträge: 13
Registriert: Mi Nov 30, 2016 10:03 am

Re: Suchen und Ersetzen von Arrayelementen

Beitrag von bobpcur » Mi Nov 30, 2016 12:03 pm

cloidnerux hat geschrieben: Es stellt sich die Frage, warum es denn ein Problem ist, dass mehrere Register genutzt werden?
Ein Grund ist die Lesbar- und Wartbarkeit des Assemblercodes. Ein anderer ist die Rechengeschwindigkeit.
cloidnerux hat geschrieben:Auch hier die Aussage: macht das dein Compiler nicht schon? Weiterhin musst du auch beachten, dass der Wert in Register 1 an einer anderen Stelle genutzt werden könnte, die du nicht erfasst. Du musst also erfassen, ob ein Register nach der ersten Operation weiter verwendet wird oder nicht sowieso schon ein neuer Wert in dieses hinein geladen wird.
Der Compiler macht das nur bedingt (den Assembler Code generieren wir uns aus Simulink Modellen), ich bin quasi der jenige, der jetzt versucht diese Option zu implementieren :D.
cloidnerux hat geschrieben: https://proggen.org/doku.php?id=project:wordcount
Das Resultat ist, dass man als Programmierer nicht besser darin ist, Assembler zu schreiben, als ein Compiler.
Das ist ja cool, ich werde es mir heute noch genauer anschauen.
cloidnerux hat geschrieben: Zu deinem Algorithmus:
Du setzt soweit ich das nachvollziehen kann voraus, dass es ein Mapping Variable(Name)->Register gibt. Du gehst davon aus, dass alle Variablen Namen eindeutig in ihrem Namen und Verwendung sind. Du versuchst dann ein Array zu erstellen, dass die Verwendung der Variablen im Assembler Code nach ihrer Position im Code in umgekehrter Reinfolge zu erstellen und danach dann eine neue Zuweisung Variable->Register durchzuführen.
Genau das möchte ich erreichen.
cloidnerux hat geschrieben: Dabei gibt es aber mehrere Probleme: Du hast Sprung und Verzweigungsoperationen, ein Laden von Daten in ein Register kann im Assemblercode später passieren, als die Nutzung des Wertes. Du hast Pointeroperationen, die die Variablennamen maskieren(Zugriff auf ein Array Element z.B).
Deine Variablennamen im Quellcode sind nicht immer eindeutig, du hast so sehr häufig Laufvariablen wie i oder andere häufig verwendete Namen.
Viele Assembleroperationen greifen auf Register zu, ohne diese explizit anzugeben. Dein Algorithmus muss also die Assemblerinstruktionen kennen, um zu verhindern, dass Ergebnisse aus Berechnungen nicht überschrieben werden.
Die Laufvariablen sind ein sehr großes Problem, da diese bei mir automatisch entstehen, wenn ich Simulink Subsysteme in Assembler übersetze. Dabei werden die Elemente aus den Subsystemen gelöscht und auf höhere Ebene so oft kopiert, wie viele Iterationen es gibt. Alleine dadurch entstehen sehr viele Variablennamen. Ein anderer Teil um den ich mich kümmere in diesem Zusammenhang, ist eine sinnvolle Bennenug von Variablen, damit diese eben eindeutig im Code werden.

mfro hat geschrieben: Assembler-Programme laufen in den seltensten Fällen linear "von oben nach unten" ab. Da gibt es Schleifen und Sprünge und solange Du den Programmfluß nicht komplett analysiert hast, kannst Du nicht davon ausgehen, daß "weiter oben" auch "zeitlich früher" heißt und weißt damit auch nicht, wann ein Register tatsächlich nicht mehr gebraucht wird. Der einzig klare Indikator dafür ist, wenn es mit einem neuen Wert überschrieben wird.
Sowas habe ich mir schon gedacht, das es eben zum Bsp. JMP - Anweisungen gibt. Jedoch nicht bei dem Assembler Code, der bei mir generiert wird. Dieser wird bei uns aus Simulink Modellen erstellt, welche nur aus selbst gebauten Bibliothek Elementen bestehen, extra für diesen Verwendungszweck.
mfro hat geschrieben: Bei Von-Neumann-Architekturen (das sind die meisten) können Code und Daten im Binärcode gemischt vorkommen. Ohne eine Ablaufanalyse kannst Du nicht wissen, was was ist und wirst möglicherweise Daten als Code interpretieren.

Kannst Du damit was anfangen?
Ich habe tatsächlich zwei separate Arrays, eines mit Code, eines mit Variablennamen. Und es werden auch zwei Binärfiles generiert, eben einer mit Variablen, anderer mit Zuweisungen. Deswegen ist ein eindeutiges Mapping gewährleistet.

Nochmal zu der Bedinung, bei der der Algorithmus feststellen soll, ob ein Register noch verwendet wird oder nicht. Es gibt ja die verschiedenen Permutation von "read" und "write". Ein Register würde "frei werden" wenn der Fall "read read" eintrifftt. Das heisst, im Code, wenn das Register das letze mal gelesen wurde. Seh ich das richtig?

Ich bin froh, dass mein Algorithmus halbwegs verständlich ist, und nun werde ich versuchen, das Schritt für Schritt in Matlab zu umsetzen.
Grüße, Robert.

Antworten