|
|
Home | Switchboard | Unix Administration | Red Hat | TCP/IP Networks | Neoliberalism | Toxic Managers |
| (slightly skeptical) Educational society promoting "Back to basics" movement against IT overcomplexity and bastardization of classic Unix | |||||||
| Old News | Control Flow Decompilation via Program Graph Decomposition | Recommended Books | Recommended Links | Algorithms Implementations | Minimal spanning trees | Humor | Etc |
|
|
|
|
From article Dominator ( Wikipedia)
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.
The key application of dominators in computer science is the analysis of control flow and deconstruction of control structures. In a control-flow graph (CFG), block M dominates block N if every path from the entry that reaches block N has to pass through block M. The entry block dominates all blocks.
Block M immediately dominates block N if M dominates N, and there is no intervening block P such that M dominates P and P dominates N. In other words, M is the last dominator on any path from entry to N. Each block has a unique immediate dominator, if it has any at all.
See also Control Flow Decompilation via Program Graph Decomposition
|
|
Switchboard | ||||
| Latest | |||||
| Past week | |||||
| Past month | |||||
 |
 |
 |
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 -
|
|
|
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'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
[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
[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
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.
Google matched content |
Dominator - Wikipedia, the free encyclopedia
[PDF] Finding Dominators in Practice
File Format: PDF/Adobe Acrobat - View as HTMLStephen 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) + ...> soot.toolkits.graph (Soot API)
gcc.gnu.org/ml/gcc-patches/2000-06/msg00794.html - 8k - Cached - Similar pages
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 - Cached - Similar pages
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 -
[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
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)
Enterprise Navigator: A System for Visualizing and Analyzing ... [PDF]
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 - Similar pages
A Fast Algorithm for Finding Dominators in a Flowgraph[PDF]
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
The Program Dependence Graph and Its Use in Optimization [PDF]
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 - Similar pages
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)
Society
Groupthink : Two Party System as Polyarchy : Corruption of Regulators : Bureaucracies : Understanding Micromanagers and Control Freaks : Toxic Managers : Harvard Mafia : Diplomatic Communication : Surviving a Bad Performance Review : Insufficient Retirement Funds as Immanent Problem of Neoliberal Regime : PseudoScience : Who Rules America : Neoliberalism : The Iron Law of Oligarchy : Libertarian Philosophy
Quotes
War and Peace : Skeptical Finance : John Kenneth Galbraith :Talleyrand : Oscar Wilde : Otto Von Bismarck : Keynes : George Carlin : Skeptics : Propaganda : SE quotes : Language Design and Programming Quotes : Random IT-related quotes : Somerset Maugham : Marcus Aurelius : Kurt Vonnegut : Eric Hoffer : Winston Churchill : Napoleon Bonaparte : Ambrose Bierce : Bernard Shaw : Mark Twain Quotes
Bulletin:
Vol 25, No.12 (December, 2013) Rational Fools vs. Efficient Crooks The efficient markets hypothesis : Political Skeptic Bulletin, 2013 : Unemployment Bulletin, 2010 : Vol 23, No.10 (October, 2011) An observation about corporate security departments : Slightly Skeptical Euromaydan Chronicles, June 2014 : Greenspan legacy bulletin, 2008 : Vol 25, No.10 (October, 2013) Cryptolocker Trojan (Win32/Crilock.A) : Vol 25, No.08 (August, 2013) Cloud providers as intelligence collection hubs : Financial Humor Bulletin, 2010 : Inequality Bulletin, 2009 : Financial Humor Bulletin, 2008 : Copyleft Problems Bulletin, 2004 : Financial Humor Bulletin, 2011 : Energy Bulletin, 2010 : Malware Protection Bulletin, 2010 : Vol 26, No.1 (January, 2013) Object-Oriented Cult : Political Skeptic Bulletin, 2011 : Vol 23, No.11 (November, 2011) Softpanorama classification of sysadmin horror stories : Vol 25, No.05 (May, 2013) Corporate bullshit as a communication method : Vol 25, No.06 (June, 2013) A Note on the Relationship of Brooks Law and Conway Law
History:
Fifty glorious years (1950-2000): the triumph of the US computer engineering : Donald Knuth : TAoCP and its Influence of Computer Science : Richard Stallman : Linus Torvalds : Larry Wall : John K. Ousterhout : CTSS : Multix OS Unix History : Unix shell history : VI editor : History of pipes concept : Solaris : MS DOS : Programming Languages History : PL/1 : Simula 67 : C : History of GCC development : Scripting Languages : Perl history : OS History : Mail : DNS : SSH : CPU Instruction Sets : SPARC systems 1987-2006 : Norton Commander : Norton Utilities : Norton Ghost : Frontpage history : Malware Defense History : GNU Screen : OSS early history
Classic books:
The Peter Principle : Parkinson Law : 1984 : The Mythical Man-Month : How to Solve It by George Polya : The Art of Computer Programming : The Elements of Programming Style : The Unix Hater’s Handbook : The Jargon file : The True Believer : Programming Pearls : The Good Soldier Svejk : The Power Elite
Most popular humor pages:
Manifest of the Softpanorama IT Slacker Society : Ten Commandments of the IT Slackers Society : Computer Humor Collection : BSD Logo Story : The Cuckoo's Egg : IT Slang : C++ Humor : ARE YOU A BBS ADDICT? : The Perl Purity Test : Object oriented programmers of all nations : Financial Humor : Financial Humor Bulletin, 2008 : Financial Humor Bulletin, 2010 : The Most Comprehensive Collection of Editor-related Humor : Programming Language Humor : Goldman Sachs related humor : Greenspan humor : C Humor : Scripting Humor : Real Programmers Humor : Web Humor : GPL-related Humor : OFM Humor : Politically Incorrect Humor : IDS Humor : "Linux Sucks" Humor : Russian Musical Humor : Best Russian Programmer Humor : Microsoft plans to buy Catholic Church : Richard Stallman Related Humor : Admin Humor : Perl-related Humor : Linus Torvalds Related humor : PseudoScience Related Humor : Networking Humor : Shell Humor : Financial Humor Bulletin, 2011 : Financial Humor Bulletin, 2012 : Financial Humor Bulletin, 2013 : Java Humor : Software Engineering Humor : Sun Solaris Related Humor : Education Humor : IBM Humor : Assembler-related Humor : VIM Humor : Computer Viruses Humor : Bright tomorrow is rescheduled to a day after tomorrow : Classic Computer Humor
The Last but not Least Technology is dominated by two types of people: those who understand what they do not manage and those who manage what they do not understand ~Archibald Putt. Ph.D
Copyright © 1996-2021 by Softpanorama Society. www.softpanorama.org was initially created as a service to the (now defunct) UN Sustainable Development Networking Programme (SDNP) without any remuneration. This document is an industrial compilation designed and created exclusively for educational use and is distributed under the Softpanorama Content License. Original materials copyright belong to respective owners. Quotes are made for educational purposes only in compliance with the fair use doctrine.
FAIR USE NOTICE This site contains copyrighted material the use of which has not always been specifically authorized by the copyright owner. We are making such material available to advance understanding of computer science, IT technology, economic, scientific, and social issues. We believe this constitutes a 'fair use' of any such copyrighted material as provided by section 107 of the US Copyright Law according to which such material can be distributed without profit exclusively for research and educational purposes.
This is a Spartan WHYFF (We Help You For Free) site written by people for whom English is not a native language. Grammar and spelling errors should be expected. The site contain some broken links as it develops like a living tree...
|
|
You can use PayPal to to buy a cup of coffee for authors of this site |
Disclaimer:
The statements, views and opinions presented on this web page are those of the author (or referenced source) and are not endorsed by, nor do they necessarily reflect, the opinions of the Softpanorama society. We do not warrant the correctness of the information provided or its fitness for any purpose. The site uses AdSense so you need to be aware of Google privacy policy. You you do not want to be tracked by Google please disable Javascript for this site. This site is perfectly usable without Javascript.
Last modified: March, 12, 2019
