Search

Various instances of the minimal-set poset (minset-poset for short) have been proposed in the literature, e.g., the representation of Picard and Queyranne for all st -minimum cuts of a flow network. We begin with an explanation of why this poset structure is common. We show any family of sets F that can be defined by a “labelling algorithm” (e.g., the Ford-Fulkerson labelling algorithm for maximum network flow) has an algorithm that constructs the minset poset for F . We implement this algorithm to efficiently find the nodes of the poset when F is the family of minimum edge cuts of an unweighted graph; we also give related algorithms to construct the entire poset for weighted graphs. The rest of the article discusses applications to edge- and vertex connectivity, both combinatorial and algorithmic, that we now describe. For digraphs, a natural interpretation of the minset poset represents all minimum edge cuts. In the special case of undirected graphs, the minset poset is proved to be a variant of the well-known cactus representation of all mincuts. We use the poset algorithms to construct the cactus representation for unweighted graphs in time O ( m +λ 2 n log (n/λ)) (λ is the edge connectivity) improving the previous bound O (λ n 2 ) for all but the densest graphs. We also construct the cactus representation for weighted graphs in time O ( nm log( n 2 / m )), the same bound as a previously known algorithm but in linear space O ( m ). The latter bound also holds for constructing the minset poset for any weighted digraph; the former bound also holds for constructing the nodes of that poset for any unweighted digraph. The poset is used in algorithms to increase the edge connectivity of a graph by adding the fewest edges possible. For directed and undirected graphs, weighted and unweighted, we achieve the time of the preceding two bounds, i.e., essentially the best-known bounds to compute the edge connectivity itself. Some constructions of minset posets for graph rigidity are also sketched. For vertex connectivity, the minset poset is proved to be a slight variant of the dominator tree. This leads to an algorithm to construct the dominator tree in time O ( m ) on a RAM. (The algorithm is included in the appendix, since other linear-time algorithms of similar simplicity have recently been presented.)

How does one verify that the output of a complicated program is correct? One can formally prove that the program is correct, but this may be beyond the power of existing methods. Alternatively, one can check that the output produced for a particular input satisfies the desired input--output relation by running a checker on the input--output pair. Then one only needs to prove the correctness of the checker. For some problems, however, even such a checker may be too complicated to formally verify. There is a third alternative: augment the original program to produce not only an output but also a correctness certificate , with the property that a very simple program (whose correctness is easy to prove) can use the certificate to verify that the input--output pair satisfies the desired input--output relation. We consider the following important instance of this general question: How does one verify that the dominator tree of a flow graph is correct? Existing fast algorithms for finding dominators are complicated, and even verifying the correctness of a dominator tree in the absence of additional information seems complicated. We define a correctness certificate for a dominator tree, show how to use it to easily verify the correctness of the tree, and show how to augment fast dominator-finding algorithms so that they produce a correctness certificate. We also relate the dominator certificate problem to the problem of finding divergent spanning trees in a flow graph, and we develop algorithms to find such trees. All our algorithms run in linear time. Previous algorithms apply just to the special case of only trivial dominators, and they take at least quadratic time.

In this work we devise an efficient algorithm that computes the liveness information of program variables. The algorithm employs SSA form and DJ-graphs as representation to build Merge sets. The Merge set of node n , M ( n ) is based on the structure of the Control Flow Graph (CFG) and consists of all nodes where a ϕ-function needs to be placed, if a definition of a variable appears in n . The merge sets of a CFG can be computed using DJ-graphs without prior knowledge of how the variables are used and defined. Later, we can answer the liveness query (as a part of other optimization or analysis phase) by utilizing the knowledge of the use/def of variables, the dominator tree and the pre-computed merge sets. On average, merge sets have been shown to be of size comparable to the Dominance Frontier(DF) set of a CFG and can be computed efficiently for all kinds of applications consisting of both reducible and irreducible loops. This is an advantage over existing algorithms which require additional complexities while handling applications using irreducible loops. For cases where the merge sets have already been created during the SSA construction step, the cost of our algorithm reduces even further when we use these merge sets for liveness computation. We have compared our new algorithm with a recent algorithm for computing liveness based on SSA form, and show how it performs better in practice, though being simpler to understand and implement.

This paper presents a simple and fast algorithm with proof of correctness for analyzing dominance relations of control flow graphs (CFGs). A dominator tree and dominance frontiers are obtained by reducing a DAG, which is obtained by adding dummy vertexes to the original CFG to transmit dominance relation of irreducible loops to the resultant DAG. A specific order of stacking vertexes eliminates the necessity to search for reduction candidates. The computational complexity of the algorithm for a real-world CFG with M edges is O( M ), which is also confirmed by analyzing about 1700 CFGs extracted from real programs.

Coverage testing techniques, such as statement and decision coverage, play a significant role in improving the quality of software systems. Constructing a thorough set of tests that yield high coverage, however, is often a very tedious, time consuming task. In this paper we present a technique to find a small subset of a program's statements and decisions with the property that covering the subset implies covering the rest. We introduce the notion of a mega block which is a set of basic blocks spanning multiple procedures with the property that one basic block in it is executed iff every basic block in it is executed. We also present an algorithm to construct a data structure called the global dominator graph showing dominator relationships among mega blocks. A tester only needs to create test cases that are aimed at executing one basic block from each of the leaf nodes in this directed acyclic graph. Every other basic block in the program will automatically be covered by the same test set.

Loop identification is a necessary step in loop transformations for high-performance architectures. One classical technique for detecting loops is Tarjan's interval-finding algorithm. The intervals identified by Tarjan's method are single-entry, strongly connected subgraphs that closely reflect a program's loop structure. We present a simple algorithm for identifying both reducible and irreducible loops using DJ graphs. Our method is a generalization of Tarjan's method, as it identifies nested intervals (or loops) even in the presence of irreducibility.

Recently, Static Single-Assignment Form and Sparse Evaluation Graphs have been advanced for the efficient solution of program optimization problems. Each method is provided with an initial set of flow graph nodes that inherently affect a problem's solution. Other relevant nodes are those where potentially disparate solutions must combine. Previously, these so-called φ-nodes were found by computing the iterated dominance frontiers of the initial set of nodes, a process that could take worst-case quadratic time with respect to the input flow graph. In this article we present an almost-linear algorithm for determining exactly the same set of φ-nodes.

In optimizing compilers, data structure choices directly influence the power and efficiency of practical program optimization. A poor choice of data structure can inhibit optimization or slow compilation to the point that advanced optimization features become undesirable. Recently, static single assignment form and the control dependence graph have been proposed to represent data flow and control flow properties of programs. Each of these previously unrelated techniques lends efficiency and power to a useful class of program optimizations. Although both of these structures are attractive, the difficulty of their construction and their potential size have discouraged their use. We present new algorithms that efficiently compute these data structures for arbitrary control flow graphs. The algorithms use {\em dominance frontiers}, a new concept that may have other applications. We also give analytical and experimental evidence that all of these data structures are usually linear in the size of the original program. This paper thus presents strong evidence that these structures can be of practical use in optimization.

Existing algorithms for computing dominators are formulated for control flow graphs of single procedures. With the rise of computing power, and the viability of whole-program analyses and optimizations, there is a growing need to extend the dominator computation algorithms to context-sensitive interprocedural dominators. Because the transitive reduction of the interprocedural dominator graph is not a tree, as in the intraprocedural case, it is not possible to extend existing algorithms directly. In this article, we propose a new algorithm for computing interprocedural dominators. Although the theoretical complexity of this new algorithm is as high as that of a straightforward iterative solution of the data flow equations, our experimental evaluation demonstrates that the algorithm is practically viable, even for programs consisting of several hundred thousands of basic blocks.

We assume a directed graph whose nodes are labeled by integers between 1 and n . The arcs of this graph correspond to the flow of control between blocks of a computer program. The initial node of this graph (corresponding to the entry point of the program) is labeled by the integer 1. For optimizing the object code generated by a compiler, the relationship of immediate predominator has been used by Lowry and Medlock [3]. We say that node i predominates node k if every path from node 1 to node k passes through (i.e. both into and out of) node i . Node j is an immediate predominator of node k if node j predominates node k and if every other node i which predominates node k also predominates node j . It can easily be proved that if k ≠ 1 and node k is reachable from node 1t hen node k has exactly one immediate predominator. In case k = 1, or node k is not reachable from node 1, the immediate predominator of node k is undefined, and the value 0 will be given by the procedure PREDOMINATOR .