Computing-Stack-Bedarf für C++; Wie bekomme ich eine lesbare Symboltabelle?

Question

Angenommen, Sie haben nicht nur ausführbare Dateien, sondern auch Quellcodedateien.

Mein Problem ist zu berechnen korrekte Stapelgröße des laufenden Prozesses nur für lokale Variablen, Absenderadresse, Argument übergeben. Ich habe versucht, VMMap von MS entwickelt zu verwenden. Weil es reservierten Speicher im System mit Kategorien wie Stack fangen kann. Es enthält jedoch auch Guard-Seite, Auslagerungsdatei (en) und so weiter. Daher wurde die Stapelgröße von VMMap überschätzt.

Ich möchte den Weg ändern, um das Problem zu lösen. Ich werde den Stack aufzeichnen, um den tatsächlichen Aufrufbaum zu zeichnen, indem ich StackWalker64 von WinAPI verwende und die Symboltabelle entweder von der ausführbaren Datei oder vom Quellcode abrufe. Aber es gibt ein Problem, dass Symboltabelle von ausführbaren wie ELF nicht lesbar ist.

Nun, ich plane, doxygen, die Open-Source-Projekt mit Lexer des Compilers ist anzuwenden. Weil doxygen nur Funktionsliste mit ihrem Rückgabetyp und Funktionsargument zur Verfügung stellt, weiß ich nichts über lokale Variablen. Also brauche ich auch Lexer, um eine komplette Symboltabelle als Vorverarbeitung zu erstellen. Aber es ist irgendwie kompliziert. Ich bin mir nicht sicher, dass es die beste Lösung ist. Gibt es einen besseren Weg zu lösen?

Answer 1

Was OP tun möchte, ist die Worst-Case-Stapeltiefe statisch zu berechnen.

Dies ist sehr schwer zu tun. Um das zu erreichen es, er braucht:

• Der Quellcode für jede Funktion (als Rohstoff verwendet, um folgende Tatsachen herleiten)
• Die „Symboltabelle“ (alle Erklärungen) für jede Funktion
• Ein Anruf Graph der Anwendungscodes über Übersetzungseinheiten hinweg
• Ein tiefes Wissen von dem, was sein speziellen Compiler tut Code

die „Symboltabelle“ muss seinen Compiler genau so dass die Schätzung zu generieren und optimieren Prozess weiß, welche deklarierten Daten (konzeptionell) in den Stack gelangen. OP wird ein komplettes Compiler-Frontend für seinen speziellen C++ - Dialekt benötigen. [OP glaubt fälschlicherweise, dass ein "Lexer" ihm eine Symboltabelle geben wird. Es wird nicht].

Betrachten Sie nun das Erstellen des globalen Aufrufdiagramms. Die Grundlagen scheinen einfach zu sein; Wenn die Funktion "bar" "foo (x)" enthält, dann ruft "bar" "foo" auf. Aber es gibt viele Komplikationen: Überladen, virtuelle Funktionen, indirekte Aufrufe und Umwandlungen. Das Überladen wird vermutlich durch Auflösung des Namens und Typs gelöst; Das wird angesichts der Vorlagen unordentlich (siehe SFINAE). Virtuelle Funktionen und indirekte Aufrufe zwingen einen, einen konservativen Punkteanalysator zu bauen; ein hässlich genug Cast kann die Annahme eines Aufrufs zu beliebige Argument-kompatible Funktion erzwingen. Punkte-zu-Analyzer kommen in verschiedenen Graden von Präzision; Niedrige Genauigkeit kann einen Aufrufgraphen mit vielen falschen (konservativen) Kanten erzeugen, die die Größenschätzung abwerfen. Der Compiler wird dieses globale Aufrufdiagramm nicht bereitstellen, da es nur auf einzelnen Kompilierungseinheiten ausgeführt wird.

Schließlich können wir eine Stapelgrößenschätzung erstellen. Hier muss man die Größen und Ausrichtungen verstehen, die verwendet werden, um jeden deklarierten Datentyp darzustellen, und wie der jeweilige interessierende Compiler dem Stapel lokale Variablen zuordnet. Im Allgemeinen sequentielle Codierungsblöcke {...} {...} überlappen Stapelpositionen. Man muss auch verstehen, wie Ausdrücke ausgewertet werden und wie Argumente übergeben werden, da diese die Stack-Nutzung beeinflussen.Schließlich muss man verstehen, wie der Compiler die Register zuweist und welche Optimierungen der Compiler anwenden kann (d. H.?), Da solche Optimierungen die Verwendung des Ausdrucksstapels sowie die Anzahl der tatsächlich dem Stack zugewiesenen lokalen Variablen beeinflussen. Dies ist eine Menge zu wissen, und die einzige vertrauenswürdige Quelle des Wissens ist der Compiler selbst. Anstatt zu versuchen, all diese Maschinerie zu replizieren, ist es wahrscheinlich besser, entweder den Compiler dazu zu bringen, seine tatsächliche Stapelgrößenzuweisung pro Funktion bereitzustellen (ich glaube, dass GCC dies tun wird) oder aufzugeben, ein präzises Ergebnis zu erhalten und die Stapelanforderung konservativ zu schätzen unter der Annahme, dass jedes deklarierte lokale Stack-Space verbraucht (in diesem Fall ist unklar, was man tun sollte, um die Verwendung des Expression-Stacks zu schätzen; man könnte annehmen, dass jedes Ergebnis der Variablen und des intermediären Ausdrucks Stack-Platz entsprechend seinem Typ benötigt).

Mit Stapelspeicherabschätzungen pro Funktion und einem Aufrufdiagramm kann eine einfache Analyse des Aufrufdiagramms Stapelanforderungen pro Aufrufkette vom Stamm erzeugen. Das Maximum davon ist die erforderliche Stapelschätzung. (Anmerkung: Dies setzt voraus, dass jede Funktion ihren vollen Stapelbedarf für jeden Aufruf verwendet; das ist eindeutig eine konservative Schätzung). Dieser Teil ist ziemlich einfach.

Insgesamt ist dies eine komplexe Analyse. Im Idealfall können Sie den Compiler dazu bringen, Stapelgrößenschätzungen und grundlegende Call-Graph-Fakten bereitzustellen. Die Erstellung der Punkt-zu-Punkt-Analyse ist schwierig und wird sehr schwierig, wenn die Größe der Anwendung groß wird.

Möglicherweise können Sie GCC biegen, um die Daten der Kompilierungseinheit bereitzustellen. Clang ist vermutlich so entworfen, dass er gebogen werden kann, um dieselben Daten bereitzustellen. Beide bieten meines Wissens keine spezifische Unterstützung für globale Punkte-zu-Analyse. Es ist unklar, dass GCC und Clang die Windows-Dialekte von C++ behandeln; Sie können.

Unser DMS Software Reengineering Toolkit und sein C++ - Frontend wurden entwickelt, um Symboltabellen, das Ergebnis der Namensauflösung (z. B. Auflösung von Überladungen), bereitzustellen und lokale Aufruffakten einfach extrahieren zu können. Es behandelt sowohl GCC- als auch MS-Dialekte von C++. DMS bietet auch Unterstützung für die Erstellung globaler Punkteanalysen und ein globales Anrufdiagramm. Während wir dies nicht speziell für C++ verwendet haben, haben wir damit C-Anwendungen von etwa 16 Millionen Zeilen verarbeitet.

All diese Schwierigkeiten erklären, warum Leute oft kicken und versuchen zu sehen, wie groß der Stack mit dynamischer Analyse ist. Wenn OP einen statischen Analysator benötigt, muss er bereit sein, einen erheblichen Aufwand dafür zu investieren.