Visual representation of Control Flow Graphs (CFG) is a feature available in many tools, such as decompilers. These tools often rely on graph drawing frameworks which implement the Sugiyama hierarchical style graph drawing method, a well known method for drawing directed graphs. The main disadvantage of the Sugiyama framework, is the fact that it does not take into account the nature of the graph to be visualized, specically loops are treated as second class citizens. The question this paper attempts to answer is; how can we improve the visual representation of loops in the graph? A method based on the Sugiyama framework was developed and implemented in Qt. It was evaluated by informally interviewing test subjects, who were allowed to test the implementation and compare it to the normal Sugiyama. The results show that all test subjects concluded that loops, as well as the overall representation of the graph was improved, although with reservations. The method presented in this paper has problems which need to be adressed, before it can be seen as an optimal solution for drawing Control Flow Graphs. / Visuell representation av flödesscheman (eng. Control Flow Graph, CFG) är en funktion tillgänglig hos många verktyg, bland annat dekompilerare. Dessa verktyg använder sig ofta av grafritande ramverk som implementerar Sugiyamas metod för uppritning av hierarkiska grafer, vilken är en känd metod för uppritning av riktade grafer. Sugiyamas stora nackdelär att metoden inte tar hänsyn till grafens natur, loopar i synnerhet behandlas som andra klassens medborgare. Frågeställningen hos denna rapport är; Hur kan vi förbättra den visuella representationen av loopar i en graf? En metod som bygger vidare på Sugiyama-ramverket utvecklades och implementerades i Qt. Metoden testades genom att hålla informella kvalitativa intervjuer med testpersoner, vilka fick testa implementeringen och jämföra den med den vanliga Sugiyama-metoden. Resultaten visar att alla testpersonerna stämmer in på att loopar, så väl som den overskådliga representionen av grafen förbättrades, dock med vissa reservationer. Metoden som presenteras i denna rapport har vissa problem, vilka bör adresseras innan den kan ses som en optimal lösning för uppritning av flödesscheman.

Data-flow analysis is an integral part of any aggressive optimizing compiler. We propose a framework for improving the precision of data-flow analysis in the presence of complex control-flow. We initially perform data-flow analysis to determine those control-flow merges which cause the loss in data-flow analysis precision. The control-flow graph of the program is then restructured such that performing data-flow analysis on the resulting restructured graph gives more precise results. The proposed framework is both simple, involving the familiar notion of product automata, and also general, since it is applicable to any forward or backward data-flow analysis. Apart from proving that our restructuring process is correct, we also show that restructuring is effective in that it necessarily leads to more optimization opportunities. Furthermore, the framework handles the trade-off between the increase in data-flow precision and the code size increase inherent in the restructuring. We show that determining an optimal restructuring is NP-hard, and propose and evaluate a greedy heuristic. The framework has been implemented in the Scale research compiler, and instantiated for the specific problems of Constant Propagation and Liveness analysis. On the SPECINT 2000 benchmark suite we observe an average speedup of 4% in the running times over Wegman-Zadeck conditional constant propagation algorithm and 2% over a purely path profile guided approach for Constant Propagation. For the problem of Liveness analysis, we see an average speedup of 0.8% in the running times over the baseline implementation.