|
Softpanorama |
May the source be with you, but remember the KISS principle ;-)
Softpanorama Search
|
| Old News | See Also | Recommended Books | Recommended Links | Algorithms Implementations | Minimal spanning trees | Humor | Etc |
Dominance was first introduced by Prosser in a 1959 paper on analysis of flow diagrams. Prosser did not present an algorithm for computing dominance, which had to wait ten years for Lowry and Medlock. Ron Cytron rekindled in the interest in dominance in 1989 when he applied it to efficient computation of φ functions, which are used in static single assignment form.
|
|||||||
[PDF] Microsoft PowerPoint - dfa3
|
File Format:
PDF/Adobe Acrobat -
View as HTML “Dominators” needed to explain. reducibility. In reducible flow graphs, loops are well. defined, retreating edges are unique. (and called “back” edges). ... suif.stanford.edu/~courses/cs243/lectures/dfa3.pdf - |
[PPT] M.Sc. of Software Engineering for the e-Economy CO7206 System ...
| File
Format: Microsoft Powerpoint -
View as HTML Dominators / Post-dominators; Control-dependence Analysis. Data Flow Analysis; Program and System Dependence Graphs; Slicing. Program Analysis Outline ... www.cs.le.ac.uk/~mer14/week5-2.ppt - |
Doug Simon Structuring Assembly Programs
Doug's 1997 Honours thesis, under the supervision of Cristina Cifuentes, involved the creation of a new structuring algorithm to structure assembly-based program flow graphs. This new algorithm was prompted as a way to simplify the expensive data structures and analysis required by the algorithms used in the dcc project.
Doug implemented the algorithms used by Cristina in the dcc project (see Structuring Decompiled Graphs or Chapter 6 of the PhD thesis Reverse Compilation Techniques) as well as the new, simplified, structuring algorithms we devised in 1997. Both algorithms are compared in a tool called AST (assembly structuring tool) for SPARC assembly programs.
Abstract
An automated assembly to high level language (e.g. C) translator would be of great benefit to maintainers of legacy assembly programs. A component of such a translator would derive higher level constructs such as conditional, loops and sequences from the original source. This can be done by applying an algorithm to structure the control flow graph of the assembly source. This is commonly referred to as a structuring algorithm.
Most existing techniques for control flow structuring not easily adapted to structuring assembly code. During research into the feasibility of a binary decompiler, an algorithm more suited to the task of structuring assembly code was developed. This seminar focuses on a number of modifications to this algorithm that were developed as part of an honour's thesis. In particular we discuss techniques for generating `better' high level code from unstructured assembly control flow graphs. Unstructured graphs are those that will require the use of gotos in the high level code. The quality of the code can be measured by the number of gotos generated.
In addition to our attempt to improve the functionality of the original algorithm, we also seek to improve the runtime speed of the translator by investigating less expensive data structures. Ideally, any improvement in speed will not involve a trade off with functionality.
We present the results of a prototype assembly structuring tool. The results were generated by running the tool on a number of well known, large benchmark programs used by those in the compiler community. From these results, we discuss what combination of improvements in speed and functionality are optimal in some well defined sense.Code
The assembly structuring tool, AST, is distributed under a BSD license and it is (C) Doug Simon, 1997.
The code base was last compiled on a SPARC Solaris platform with gcc 3.1 on 1st March 2002.
Two versions of the AST tool can be built: ast and ast_old. The ast tool implements the new algorithms, based on dominators and post-dominators of a graph's underlying tree. The ast_old tool implements the algorithms used in the dcc project, which are based on intervals and the derived sequence of graphs. The Makefile provided in the distribution compiles the ast tool, to compile the ast_old tool, you need to uncomment some lines in the Makefile.
Code base: ast.tar.gz (49 KB)
[PPT] A New Simpler Linear Time Dominators Algorithm
File Format: Microsoft Powerpoint 97 - View as HTML
Use augmented graphs of microtrees to summarize the arcs from G into the trees; determine internal immediate dominators (ie idoms residing inside a ...
www.cs.wustl.edu/~raa4/projects/bkrw/cs531bkrw-2.PPT -Similar pages
[PDF] Finding Dominators in Practice
File Format: PDF/Adobe Acrobat - View as HTML
dominators in the graph obtained from G by reversing all arc orientations. ... memory and compute dominators for each graph in sequence, measuring the total ...
www.daimi.au.dk/~loukas/dominators_esa04.pdf -Similar pages [PDF] Finding Dominators Revisited
File Format: PDF/Adobe Acrobat - View as HTML
Algorithm for finding dominators in reducible graphs [1]. Lemma 5.1. For any vertex w = r, idom(w) is the. nearest common ancestor of sdom(w) and parent(w) ...
www.daimi.au.dk/~loukas/dominators_soda04.pdf -Similar pages
In the summer of 1998, I worked with Anne Rogers and Adam Buchsbaum at AT&T Labs Research. We studied three major algorithms used to find important vertices called dominators in flowgraphs (directed, rooted graphs). A node d dominates n if every path from the root to n includes d. Dominator analysis is an important problem, with applications ranging from optimizing compilers to network flow analysis.
Programmers primarily use one of three algorithms to find dominators in flowgraphs; these are Purdom-Moore, Bit Vector, and Lengauer-Tarjan. On graphs with n vertices and m edges, the respective running times for each algorithm are O(m n), O(m n^2), and O(m alpha(m,n)) (where alpha is the inverse Ackermann function, which grows extremely slowly). When Lengauer and Tarjan introduced their algorithm in a 1979 paper, they used randomly generated flowgraphs as input to compare the actual running times for each of these algorithms. In their paper, they found the Lengauer-Tarjan algorithm showed better performance, even for small graphs, reporting that their algorithm out-performed Purdome-Moore for all test graphs larger than twelve nodes, and it outperformed Bitvector for all test graphs.
Over the summer, I explored whether modern machines with caches exhibit different results and whether using compiler-generated flowgraphs as input affects runtime. I implemented Purdom Moore, and Bit Vector and modified an existing Lengauer-Tarjan implementation. We collected running times for all three algorithms on two classes of graphs: random graphs and flowgraphs generated using the MACHINE SUIF compiler (from Harvard/Stanford) on programs from the SPEC benchmarks. In my analysis, I found that for both random and compiler generated graphs, Lengauer-Tarjan still proved fastest for large graphs. However, in the experiment, Purdom-Moore lost ground, moving the crossover point by Lengauer-Tarjan to seven nodes. We also found the bit vector algorithm does compete with Lengauer-Tarjan for small graphs. Therefore, the conclusions of the original paper still stand, even with modern machine caches and compiler generated graphs.
Although this work did not overturn existing ideas about dominator algorithms, I gained a great deal from the experience. On my return to school, I was able to leverage my experience with dominators in a class project where I used Visual C++ and MFC to create a Windows visualization tool for animating graph algorithms. The program allows users to create directed graphs and monitor the progress of various algorithms on them, including Purdom-Moore. My experience with dominators was more than just research; it was a unique opportunity for me to gain confidence in my research skills, to work with talented researchers, and to bring my summer experience to the classroom.
[PDF] Finding Dominators in Practice
File Format: PDF/Adobe Acrobat - View as HTML
Stephen Alstrup, Dov Harel,
Peter W. Lauridsen and Mikkel
Thorup.
Dominators in
linear time.
Vol. 28(6), 2117-2132,1999, Siam Journal on Computing.
A New, Simpler Linear-Time Dominators Algorithm - Buchsbaum (ResearchIndex)
Abstract: this article is organized as follows. Section 2 outlines Lengauer and Tarjan's approach. Section 3 gives a broad overview of our algorithm and differentiates it from previous work. Section 4 presents our algorithm in detail, and Section 5 analyzes its running time. Section 6 presents our new path-compression result, on which the analysis relies. Section 7 describes our implementation, and Section 8 reports experimental results. We conclude in Section 9. (Update)
Dominators in
Linear Time - Alstrup, Harel, Lauridsen, Thorup (ResearchIndex) Dominators in Linear
Time (1996) (Make
Corrections) (14 citations)
Stephen Alstrup, Peter W. Lauridsen, Mikkel Thorup DIKU
technical report
Dominators in Linear Time - Alstrup, Harel, Lauridsen, Thorup (1999) (14 citations) (Correct)
.... and program optimization [2, 3, 4, 5, 10, 15] The problem was first
raised in 1969 by Lowry and Medlock [15] where an O(n 4 ) algorithm for the
problem was proposed (as usual, n is the number of nodes and m the number of
edges in a graph) The result has been improved several times (see e.g.
[1, 2, 17, 20]) and in 1979 an O(mff(m; n) algorithm
was found by Lengauer and Tarjan [14] Finally, at STOC 85, Dov Harel [11]
announced a linear time algorithm. Based on Harel s result, linear time
algorithms have been found for many other problems (see e.g. 4, 5, 10] Harel s
description was, however, ....
R.E. Tarjan. Finding dominators in directed graphs.
SIAM Journal on Computing, 3(1):62--89, 1974.
Notes on Graph Algorithms Used in Optimizing Compilers - Offner (ResearchIndex)
Notes on Graph Algorithms Used in Optimizing Compilers (1995) (Make Corrections) (2 citations)
A New, Simpler Linear-Time Dominators Algorithm - Adam Buchsbaum Haim (1998) (1 citation) (Correct)....theory, with crucial applications in global flow analysis and program optimization [2, 7, 9, 15] Lorry and Medlock [15] introduced an O(n 4 ) time algorithm, where n = jV j and m = jAj, to find all the immediate dominators in a flowgraph. Successive improvements to this time bound were achieved [2, 20,22], culminating in Lengauer and Tarjan s [13] O(mff(m; n) time algorithm; ff is the standard functional inverse of the Ackermann function and is slightly superlinear [25] The Lengauer Tarjan (LT) algorithm is extremely efficient in practice. Reducing the asymptotic time complexity of finding ....
An O(|V|*|E|) Algorithm for Finding Immediate Multiple-Vertex Dominators (1996) - Alstrup, Clausen.. (1996) (Correct)
Abstract: We present an O(jV j jEj) algorithm for finding immediate multiple-vertex dominators in a graph with vertices V and edges E. 1 Introduction. Finding dominators in a graph has been investigated in many papers [6, 7, 8, 9, 10] in connection with global flow analysis and program optimization. Recently Gupta extended the problem to find generalized dominators [4, 5], which can be used for e.g. propagating loop invariant statements out of the loop in cases, where no single vertex dominates the... (Update)
Abstract: . Recently it has been discovered that control flow graphs of structured programs have bounded treewidth. In this paper we show that this knowledge can be used to design fast algorithms for control flow analysis. We give a linear time algorithm for the problem of finding the immediate multiple-vertex dominator set for all nodes in a control flow graph. The problem was originally proposed by Gupta (Generalized dominators and post-dominators, ACM Symp. on Principles of Programming Languages,... (Update)
[patch] new dominance calculator
| +/* Compute dominator
relationships using new flow graph structures in + nearly
linear time. */ void compute_flow_dominators (dominators,
post_dominators) + ... gcc.gnu.org/ml/gcc-patches/2000-06/msg00794.html - 8k - |
soot.toolkits.graph (Soot API)
| DominatorsFinder, General
interface for a dominators analysis.
ExceptionalGraph, Defines the interface for navigating a
control flow graph which ... www.sable.mcgill.ca/soot/doc/ soot/toolkits/graph/package-summary.html - 21k - |
protected DominatorsFinder · dominators. protected HashMap · godeToDode "gode" is a node in the original graph, "dode" is a node in the dominator tree. ...
www.sable.mcgill.ca/soot/doc/ soot/toolkits/graph/DominatorTree.html - 31k -Cached - Similar pages
[PDF] The Machine-SUIF Control Flow Analysis Library
| File
Format: PDF/Adobe Acrobat -
View as HTML Call find dominators to compute the dominator relation in the forward graph. Then access this infor-. mation through the following methods. immed dom(n) ... www.eecs.harvard.edu/hube/software/nci/cfa.pdf - |
dom_nav. public static final jwutil.graphs.Navigator dom_nav ... public void calculateDominanceFrontier(Dominators.DominatorNode tree) ...
joeq.sourceforge.net/apidocs/ joeq/Compiler/Quad/Dominators.html - 29k -Cached - Similar pages
Doug Simon Structuring Assembly Programs
Doug's 1997 Honours thesis, under the supervision of Cristina Cifuentes, involved the creation of a new structuring algorithm to structure assembly-based program flow graphs. This new algorithm was prompted as a way to simplify the expensive data structures and analysis required by the algorithms used in the dcc project.
Doug implemented the algorithms used by Cristina in the dcc project (see Structuring Decompiled Graphs or Chapter 6 of the PhD thesis Reverse Compilation Techniques) as well as the new, simplified, structuring algorithms we devised in 1997. Both algorithms are compared in a tool called AST (assembly structuring tool) for SPARC assembly programs.
Abstract
An automated assembly to high level language (e.g. C) translator would be of great benefit to maintainers of legacy assembly programs. A component of such a translator would derive higher level constructs such as conditional, loops and sequences from the original source. This can be done by applying an algorithm to structure the control flow graph of the assembly source. This is commonly referred to as a structuring algorithm.
Most existing techniques for control flow structuring not easily adapted to structuring assembly code. During research into the feasibility of a binary decompiler, an algorithm more suited to the task of structuring assembly code was developed. This seminar focuses on a number of modifications to this algorithm that were developed as part of an honour's thesis. In particular we discuss techniques for generating `better' high level code from unstructured assembly control flow graphs. Unstructured graphs are those that will require the use of gotos in the high level code. The quality of the code can be measured by the number of gotos generated.
In addition to our attempt to improve the functionality of the original algorithm, we also seek to improve the runtime speed of the translator by investigating less expensive data structures. Ideally, any improvement in speed will not involve a trade off with functionality.
We present the results of a prototype assembly structuring tool. The results were generated by running the tool on a number of well known, large benchmark programs used by those in the compiler community. From these results, we discuss what combination of improvements in speed and functionality are optimal in some well defined sense.Code
The assembly structuring tool, AST, is distributed under a BSD license and it is (C) Doug Simon, 1997.
The code base was last compiled on a SPARC Solaris platform with gcc 3.1 on 1st March 2002.
Two versions of the AST tool can be built: ast and ast_old. The ast tool implements the new algorithms, based on dominators and post-dominators of a graph's underlying tree. The ast_old tool implements the algorithms used in the dcc project, which are based on intervals and the derived sequence of graphs. The Makefile provided in the distribution compiles the ast tool, to compile the ast_old tool, you need to uncomment some lines in the Makefile.
Code base: ast.tar.gz (49 KB)
[PDF] Enterprise Navigator: A System for Visualizing and Analyzing ...
| File
Format: PDF/Adobe Acrobat -
View as HTML 2.4 Graph Dominators (Dominator). The Enterprise Navigator uses the Dominator tool to ... dominators of a graph. In a graph with a selected root node R, ... www.research.att.com/resources/ trs/TRs/99/99.16/99.16.1.body.pdf - |
[PDF] A Fast Algorithm for Finding Dominators in a Flowgraph
| File
Format: PDF/Adobe Acrobat -
View as HTML TARJAN, R. Finding dominators in directed graphs. SIAM J. Comptng. 3. (1974), 62-89. ACM Transactions on Programming Languages and Systems, Vol. 1, No. ... www.cs.princeton.edu/courses/ archive/spr03/cs423/download/dominators.pdf - |
[PDF] The Program Dependence Graph and Its Use in Optimization
| File Format:
PDF/Adobe Acrobat -
View as HTML and dominators [l, 31. The Appendix contains the basic graph theoretic termi- ... flow graph is equivalent to computing dominators [l] in the reverse ... www.cs.utexas.edu/users/ less/reading/spring00/ferrante.pdf - |
Abstract. This paper describes an algorithm for finding dominators in an arbitrary directed graph. The algorithm uses depth-first search and efficient algorithms for computing disjoint set unions and manipulating priority queues to achieve a time bound of $O(V\log V + E)$ if $V$ is the number of vertices and $E$ is the number of edges in the graph. This bound compares favorably with the $O(V(V + E))$ time bound of previously known algorithms for finding dominators in arbitrary directed graphs, and with the $O(V + E\log E)$ time bound of a known algorithm for finding dominators in reducible graphs. If $E \geqq V\log V$, the new algorithm requires $O(E)$ time and is optimal to within a constant factor.
Keywords. algorithm, binary tree, complexity, connectivity, depth-first search, directed graph, dominator, equivalence algorithm, graph, immediate dominator, priority queue, search, set union, stack, topological sorting, tree
Full Text (pdf)
Copyright © 1996-2009 by Dr. Nikolai Bezroukov. www.softpanorama.org was created as a service to the UN Sustainable Development Networking Programme (SDNP) in the author free time. Submit comments This document is an industrial compilation designed and created exclusively for educational use and is placed under the copyright of the Open Content License(OPL). Site uses AdSense so you need to be aware of Google privacy policy. Original materials copyright belong to respective owners. Quotes are made for educational purposes only in compliance with the fair use doctrine.
Disclaimer:
Last modified: August 15, 2009