Debugging für Profis
Branch Coverage für optimierten Code
Fortsetzung des Artikels von Teil 2
Wichtig ist der Kontrollfluss
Aus den gewonnenen Trace-Daten ein Statement Coverage abzuleiten, ist noch keine allzu große Kunst. Kniffeliger wird es hingegen beim Branch Coverage, denn nun sind auch Informationen zur Programmstruktur notwendig, die sich auf einen sogenannten Kontrollflussgraphen abbilden lassen (Bild 1). Der Kontrollflussgraph spiegelt wieder, wie Basisblöcke, sprich rein sequenzieller Code ohne Verzweigungen, Schleifen oder Einsprungpunkte, während der Ausführung miteinander in Beziehung stehen. Dabei folgt der Programmfluss ausschließlich den Kanten im Graphen zwischen den Basisblöcken.
Für die Ermittlung des Branch Coverages muss auf die Informationen des Kontrollflussgraphen zurückgegriffen werden. Erst mit ihrer Hilfe lässt sich anhand der getracten Adressen die Richtung ermitteln, welche die Programmausführung nach einer bedingten Verzweigung eingeschlagen hat und auch, welche Programmteile überhaupt nicht ausgeführt wurden. Letzte sind ja im Trace schlichtweg nicht vorhanden.
Aus nicht-optimiertem Code lässt sich der Kontrollfluss noch relativ einfach aus dem verfügbaren Quellcode und den Debug-Informationen im ELF-File herleiten, da beides dem Debugger typischerweise ohnehin zur Verfügung steht. Bei optimiertem Code wird es hingegen sehr schnell kompliziert. In den seltensten Fällen wird der Quellcode direkt in ausführbare Maschineninstruktionen übersetzt. Das wäre weder hinsichtlich der Laufzeit noch vom Speicherbedarf her optimal. Compiler nutzen daher verschiedene Strategien zur Optimierung, die teilweise recht aggressiv die Struktur des Maschinencodes verändern. So können zum Beispiel Basisblöcke vervielfältigt, zusammengefasst oder eliminiert werden. Solche Programmtransformationen treten häufig bei Schleifentransformationen (Schleifenspaltung, -vereinigung oder -expansion), If-then-else-Transformationen (z. B. Eliminierung eines Anweisungszweiges) oder bei der Umwandlung von Basisblöcken in Tabellenzugriffe auf, wie man sie oft bei Switch-Statements sieht. Durch solche Maßnahmen geht zwangsläufig die eindeutige Zuordnung von Basisblöcken des Quellcodes zu denen des Maschinencodes verloren. Dies wiederum wirkt sich natürlich negativ auf die Berechenbarkeit des Branch Coverages aus.
Einfluss der Optimierung
Am Beispiel einer normalen Switch-Anweisung in C/C++ (Bild 2) soll verdeutlicht werden, welchen Einfluss die Optimierung des erzeugten Maschinencode hat und wie sich dies auf das Branch Coverage auswirkt. Bild 3 zeigt einen vom Compiler ohne jegliche Optimierung erzeugten Maschinencode, der den Basisblöcken der Switch-Anweisung noch zugeordnet werden kann. Für den besseren Überblick ist die Zuordnung der Basisblöcke in den Abbildungen farblich hervorgehoben. Im nicht-optimierten Fall wird zu Beginn jedes Blockes überprüft, ob der Wert im Kopf der Switch-Anweisung mit der Case-Konstante übereinstimmt. Falls nicht, wird das nächste Label angesprungen und veranlasst, dass die nächste Prüfung mit der jeweiligen Case-Konstanten stattfindet. Wenn vorher alle anderen Vergleiche fehlschlugen, wird schlussendlich der Default-Block ausgeführt. Durch die direkten Sprünge ist genau bekannt, welche Sprungziele überhaupt für die Code-Sequenz existieren. Die dann tatsächlich genommenen Sprünge lassen sich über den Code-Trace ermitteln. Es muss nur geschaut werden, welche Instruktion nach der jeweiligen Verzweigung ausgeführt wurde, also entweder das Sprungziel oder diejenige der nachfolgenden Adresse. Damit lässt sich das Branch Coverage leicht berechnen.
Doch selbst für dieses noch sehr einfache Beispiel gibt es bereits mehrere Optimierungsmöglichkeiten, die eine Ermittlung des Brach Coverages alleine aus dem Code Trace deutlich erschweren. So kann die Case-Konstante beispielsweise als Index für eine Sprungtabelle verwendet werden, welche die Adressen der Label für die Case-Blöcke und damit für die Wertezuweisungen enthält (Bild 4). Dies spart zwar die Vergleichsbasisblöcke ein, aber nun kann der Debugger nicht mehr ohne Weiteres alleine aus den Binaries die tatsächliche Anzahl möglicher Sprungziele, also die Anzahl von Einträgen der Sprungtabelle, ermitteln. Der Code-Trace liefert nur die Verzweigungen, die auch tatsächlich durch die Testfälle stimuliert wurden. Im Beispiel von Bild 4 würden sogar nur die zwei Verzweigung zum Default-Label als solche erkannt. Die eigentlichen Pfade durch die Case-Blöcke blieben unerkannt und das errechnete Branch Coverage wäre schlichtweg falsch. Erst wenn auch der Kontrollflussgraph der optimierten Variante bekannt ist, aus dem sich alle möglichen Wege durch die Sprungtabelle ablesen lassen, ist ein exaktes Branch Coverage berechenbar. Das Kontrollflussgraphen nicht Bestandteil der herkömmlichen, dem Debugger ohnehin zur Verfügung stehenden Informationen sind, ist in diesem Zusammenhang zwar bedauerlich. Trotzdem können sie für die Berechnung des Branch Coverages recht einfach bereitgestellt werden, wie noch deutlich werden wird.
Bei einer noch aggressiveren Optimierung reicht der Code Trace alleine tatsächlich nicht mehr aus. Wenn alle Anweisungen innerhalb der Case-Blöcke konstante Werte zurückliefern, kann der Compiler die Rückgabewerte in einer Wertetabelle ablegen und die Case-Konstante wiederum als Index verwenden. Alle Case-Blöcke sind nun in einem einzigen Basisblock vereint und Sprünge dadurch gänzlich überflüssig (Bild 5). Hier hilft auch der Kontrollflussgraph nicht mehr weiter, da der optimierte Maschinencode nun eher datenorientiert ist. Eigentlich müsste an dieser Stelle die Coverage-Analyse anhand der Speicherzugriffe ermitteln, um welchen ausgeführten Case-Zweig es sich handelt. Dafür wäre neben Code Trace zusätzlich aber auch noch zwingend Daten-Trace erforderlich. Doch spätestens an diesem Punkt kapitulieren derzeit verfügbare Tools. Momentan obliegt es also letztlich noch einzig der Verantwortung der jeweiligen Entwickler und Tester, ob solche aggressiven Optimierungen tatsächlich zugelassen sind oder wie diese durch die Qualitätssicherung behandelt werden.
Jobangebote+ passend zum Thema
- Branch Coverage für optimierten Code
- Daten gewinnen
- Wichtig ist der Kontrollfluss
- Der Compiler kooperiert
Lesen Sie mehr zum Thema
Das könnte Sie auch interessieren
