Greedy Faerbungsalgorithmus für eine Variablenreduktion
Verfasst: Di Jan 10, 2017 2:05 pm
Hallo,
ich möchte für mein Projekt einen "Compiler" Optimierer schreiben, welcher mir die benutzten Variablen im erzeugten Code reduziert. Dazu parse ich die erzeugten Codezeilen und trenne die Variablen zeilenweise, die nur beschrieben werden, von denen, die nur gelesen werden. Der erzeugte Code ist eine Assembler artige Zwischensprache, welche jede Zeile zu einem Zeitpunkt abarbeitet. Deswegen, wenn eine Variable in einer Zeile nur noch gelesen wird und nie wieder beschrieben, ´wird der Name dieser Variable frei und somit reduziert sich die Gesamtanzahl der Variablen.
Ich habe etwas recherchiert und festgestellt, solche Probleme werden mit Hilfe der Graphentheorie, speziell Faerbungsproblem gelöst. Leider ist das Finden der optimalen chromatischen Zahl ein NP vollständiges Problem, deswegen möchte ich erstmal auf den Greedy Algorithmus zurueckweichen.
Zunächst muss ich meinen erzuegten Code und meine beiden Variablenlisten als einen Graphen repräsentieren. Dabei bilden meine Variablennamen und Anweisungen Knoten. Und schon komme ich nicht klar, im Output des Algorithmus möchte ich einen neuen erzeugten Code mit weniger verwendeter Variablen, ich bin mir aber absolut nicht sicher wie ich den Algorithmus anweden soll.
Ich frage nicht nach einem fertigem Code oder aehnlichem, ich schreibe je in Matlab und das ist glaube ich diesem Forum etwas fremd. Ich braeuchte lediglich Hilfe bei dem Übertragen meines spezifischen Problems auf ein allg. graphentheoretisches Problem.
Viele Grüße, bob.
ich möchte für mein Projekt einen "Compiler" Optimierer schreiben, welcher mir die benutzten Variablen im erzeugten Code reduziert. Dazu parse ich die erzeugten Codezeilen und trenne die Variablen zeilenweise, die nur beschrieben werden, von denen, die nur gelesen werden. Der erzeugte Code ist eine Assembler artige Zwischensprache, welche jede Zeile zu einem Zeitpunkt abarbeitet. Deswegen, wenn eine Variable in einer Zeile nur noch gelesen wird und nie wieder beschrieben, ´wird der Name dieser Variable frei und somit reduziert sich die Gesamtanzahl der Variablen.
Ich habe etwas recherchiert und festgestellt, solche Probleme werden mit Hilfe der Graphentheorie, speziell Faerbungsproblem gelöst. Leider ist das Finden der optimalen chromatischen Zahl ein NP vollständiges Problem, deswegen möchte ich erstmal auf den Greedy Algorithmus zurueckweichen.
Zunächst muss ich meinen erzuegten Code und meine beiden Variablenlisten als einen Graphen repräsentieren. Dabei bilden meine Variablennamen und Anweisungen Knoten. Und schon komme ich nicht klar, im Output des Algorithmus möchte ich einen neuen erzeugten Code mit weniger verwendeter Variablen, ich bin mir aber absolut nicht sicher wie ich den Algorithmus anweden soll.
Ich frage nicht nach einem fertigem Code oder aehnlichem, ich schreibe je in Matlab und das ist glaube ich diesem Forum etwas fremd. Ich braeuchte lediglich Hilfe bei dem Übertragen meines spezifischen Problems auf ein allg. graphentheoretisches Problem.
Viele Grüße, bob.