Softpanorama
(slightly skeptical) Open Source Software Educational Society

May the source be with you, but remember the KISS principle ;-)

Softpanorama Search

Control Flow Decompilation via Program Graph Decomposition

News

 See Also Recommended Books Control quants Hammock-based decompositions Oulsnam  Works Baker decomposition Intervals Parsing of graphs and grammar based approaches
Dominators Peephole based approaches Prolog Reducibility and normalization of program graph Simplistic structured programming approaches   History Humor Etc

Most classic approaches use construction of the flow graph as the first stage. That means that heuristic clues like presence of the counter for the detection of the for loop are partially lost although they can be reintroduced on later stage in some approaches (for example based on control quants).  There are several classic approaches to recreation of  high level control structures from an assembler code based on program graph decomposition 

  1. Decomposition of program graph into "single entry-single exit" subgraphs (hammocks). All control in a hammock must be passed to the entry note called head and all control from the quants should pass via the exit note called focus. This idea was suggested by  Kasyanov in V. N. Kas'janov. Distinguishing hammocks in a directed graph. Soviet Math. Doklady, 16(5):448--450, 1975.  Kasyanov's decomposition algorithm was weak and later he completely lost track of his own idea. Essentially the same idea was independendently reinvented by Gordon Oulsnam who proposed the first practically usable decomposition algorithm based of direct and reverse dominators (Oulsnam work was recieved in August 1984, but published in 1987).  Later Oulsnam applied this decomposition to complexity metric of the program.  Unfortunately I lost my copy of his papers.
     
  2. The idea of prime hammocks or control quants.  Control quant is non-decomposable subgraph of the graph of the program with just one entry and one exit node. That means that all control quants are  hammocks but not vise versa.  control quants can be also called "prime hammocks" to use the analogy with prime numbers.   This idea was invented by R.A. Maddux in his  Ph.D. dissertation "Study of Program Structure, University of Waterloo (July 1975). Note that this was the same year Kas'janov paper was published. Maddux called his control structures "prime programs."  Similar approach was independently reinvented myself much later (I was not aware about his work, but was aware about Kasyanov's and Oulsnam works.  I called such structures "prime hammocks" or control quants, as they are not further decomposable into simpler structures). See

    Nikolai  Bezroukov. “Quantum Decomposition of Program Schemata on Prime Hammocks”, Software Maintenance for Real Time Software Systems Based on Micro and Mini Computers. [in Russian] Kiev Institute of Civil Aviation Engineers.  Kiev (1988),  pp. 3-17. 

    The short summary of  Maddux work and enumeration of control quants can be found in Terrence W Pratt and Marvin V. Zelkowitz book "Programming languages: design and implementation".

    The problem with this approach is that multilevel jumps (exception handling)  strongly affect program decomposition. This can be mitigated by the "normalization" of program graph before decomposition or by  minimization of the number of components (backtracking based) approaches.

    I created a pilot system used for the analyses of air traffic control programs based ont his approach but my grant ended before I managed to get practically important results and later I switched to the malware analysis and disassembly and never returned to this topic. 
     

  3. The third more eclectic school is based on the ideas of structured programming  The seminal paper on this approach is probably B. Baker "An algorithm for structuring flowgraphs," JACM 24(1) pp. 98-120 (January 1977).  Baker's work differs from the hammock-based approache and control quants based approaches above in that it presents a structuring algorithm that uses classic control structures and multilevel break and next statements. The important of her work stems from the fact that along with  straight line code, a stop statement, if-then-else, repeat, goto her algorithm was able to recognize multilevel break and next constructs. The break and continue constructs statements in C are examples of these parameterized jumps when the value of the parameter is 1. In general, next(i) is a multilevel continue and transfers control to the beginning of the i'th enclosing loop like in PL/1 and Perl. The break(i) is similar except that the transfer is to the statement following the end of the i'th enclosing loop. It is also present in PL/1 and Perl.  Her algorithm initially orders the nodes in the graph by constructing a spanning tree of the graph in a depth first manner.
     
  4. The forth school is connected with optimization of program in compilers. Here the motivation is not decomposition, but refactoring but the approaches are relevant to the decomposition as well. The first ideas in this area were formulated by F.Allen and J. Cocke in the early 1970 s who proposed so called intervals.
    F. Allen and J. Cocke. Graph-theoretic constructs for program control flow analysis. Technical Report RC-3923, IBM Research, 1972.

    An interval I(h) is the maximal, single entry subgraph in which h is the only entry node and in which all closed paths contain h. The unique interval node h is called the header node.
     

  5. Peephole and more complex grammar based approaches.   Peephole optimization  should be probably called refactoring to make it sound more modern and fashionable :-)   It essentially a the pattern matching and multistage conditional replacement that reminds Floyd-Evans production parsing algorithms as described by Gries in his famous book "compiler construction for digital computers" .  It is performed on small sliding window called peephole.  This approach can be used for the decomplation of control flow. By pattern matching the tuples of the control flow graph we can determine if they can be replaced by an equivalent higher level construction.  Regular expressions are the most natural candidate for recognition of simple control structures. The most relevant paper for this usage of regular expressions is:

    GOTO Removal Based On Regular Expressions - Paul Morris Ronald      

    ......our GOTO removal program served as a bridge to extend the range of the software. We have also applied this work to the process of "levitating" IBM 370 assembly language code to higher-level forms (Morris et al., 1996). Previous work (Ashcroft et al., 1972, Peterson et al., 1973, Ramshaw, 1988, Erosa et al., 1994), while highly developed and abstract in nature, treats GOTO removal as an isolated problem in the area of programming languages. This paper is based on the observation that GOTO removal for flowcharts resembles the problem of converting finite-state transition networks to regular expressions, and ......

    ......preferred over maintaining the existing structure. The algorithm presented here is applicable to nonreducible programs, and meets the lesser path-equivalence standard. Subjectively, this standard appears to produce more readable results than approaches that introduce auxiliary variables, such as (Erosa et al., 1994), and is easier to relate to the source presented for restructuring. These considerations are important for reverse-engineering. While the algorithm discussed in this paper has worked well in practical contexts, we feel its most significant feature is the link to important concepts in computer ......

    Erosa, A. M. and Hendron, L. J. (1994). `Taming Control Flow: A structured Approach to Eliminating Goto Statements,' Proc. IEEE International Conference on Computer Languages, 229--240.

    More general, grammar-based approaches were used in PLM-80 Decompiler (Program Transformation Wiki - History Of Decompilation 2 ):

    The Information Technology Division of the Australian Department of Defence researched into decompilation for defence applications, such as maintenance of obsolete code, production of scientific and technical intelligence, and assessment of systems for hazards to safety or security. This work was described by S.T. Hood in [ Hood91 ].

    Techniques for the construction of decompilers using definite-clause grammars, an extension of context-free grammars, in a Prolog environment are described. A Prolog database is used to store the initial assembler code and the recognised syntactic structures of the grammar. A prototype decompiler for Intel 8085 assembler programs compiled by a PLM-80 compiler was written in Prolog. The decompiler produced target programs in Small-C, a subset of the C language. The definite-clause grammar given in this report was capable of recognizing if-then control structures, and while loops, as well as static (global) and automatic (local) variables of simple types (i.e. character, integers, and longs). A graphical user interface was written to display the assembler and pseudo-C programs, and to enable the user to assign variable names, and comments. This interface also asked the user for the entry point to the main program, and allowed him to select the control construct to be recognized.

    Another example in this area the Systematic Decompilation thesis by John O'Gorman who used a pattern matching technique used for decompiling VAX binaries into Pascal source code.

    The technique requires the availability of the compiler used, performs a coverage of constructs available in the language, and creates small test programs that use the constructs, in order to derive the patterns of machine code used for each high-level construct. When decompiling a Pascal executable, the patterns are matched to determine which Pascal construct to recreated. Unoptimized code is used.

    The thesis is available for downloading (ftp) in postscript format: ftp://www.csis.ul.ie/techrpts/ul-91-12.ps.

Old News ;-)

[Mar 25, 2006] Headway Software - Products - Structure101  An interesting static byte code analyzer for Java

Structure101 for Java parses your byte code and creates an implementation model of all the dependencies mapped up through the compositional hierarchy.  It does this at a rate of mega-SLOCs per minute. You can browse the model and view dependency diagrams at any level - method, class, package or jar. (More...)

We consider structure to be important through the life of an application - not just something that gets fixed in an expensive 'Big Bang'. At the same time, we realize that many of our customers only begin looking at structure when they get the feeling it is out of control.

...Structure101TM, currently available for Java only, is designed for live, evolving, imperfect, real projects, where ongoing development must continue. We have focused on making sense of large, difficult code-bases. Structure101 lets you keep a lid on the structural complexity so that it doesn't get any worse, and enables you to gradually streamline the structure while still working to hard delivery schedules.

We have been doing structure since 1999. The core engine of Structure101, the Higraph, is on its 3rd incarnation, lightning fast and massively scalable. It is our passion to continually find new ways to understand and control structure - to make structure simple.

It is very common for packages and classes to outgrow themselves.  Big fat packages or classes tend to be difficult to work with because they lack the structure that helps to guide human understanding.  Structure101 helps by letting you view even very large dependency graphs of the package or class contents.  To help further, Structure101 can perform an Auto-partition on the graph, to reveal the hidden, inherent structure.  As well has helping you understand what you've got, seeing the inherent structure may help you to decide how to add structure by creating sub-packages or classes.

A Formal Basis For Removing Goto Statements - group of 7 » View as HTML - Web Search - BL Direct

[PS] Re-engineering - group of 6 »
M van den Brand, P Klint - cwi.nl
... 10 Page 15. [Oul82] G. Oulsnam. Unraveling unstructured programs. The Computer
Journal, 25(3):379{387, 1982. [PP94a] S. Paul and A. Prakash. ...
View as HTML - Web Search

Cristina Cifuentes wrote several (largely similar) review style papers on the theme of decomplation and she tried to cover the decomplation of control structures in a couple of papers: 

Assembly to High-Level Language Translation (1998)  (Make Corrections)  (6 citations)
Cristina Cifuentes, Doug Simon, Antoine Fraboulet
ICSM

Abstract: Translation of assembly code to high-level language code is of importance in the maintenance of legacy code, as well as in the areas of program understanding, porting, and recovery of code. We present techniques used in the asm2c translator, a SPARC assembly to C translator. The techniques involve data and control flow analyses. The data flow analysis eliminates machine dependencies from the assembly code and recovers high-level language expressions. The control flow analysis recovers... (Update)

Decompilation of Binary Programs - Cifuentes, Gough (ResearchIndex)

Decompilation of Binary Programs (1995)  (Make Corrections)  (14 citations)
Cristina Cifuentes, K. John Gough

 

Hammock-based decompositions

[PS] Hammock-on-Ears Decomposition: A Technique for the Efficient Parallel Solution of Shortest Paths and … - group of 9 »
D Kavvadias, GE Pantziou, PG Spirakis, CD … - Theoretical Computer Science, 1996 - cti.gr
... Our work combines and extends the sequential hammock decomposition technique intro-
duced by Frederickson and the parallel ear decomposition technique, thus we ...
Cited by 7 - View as HTML - Web Search - Library Search - BL Direct

 

Using Hammock Graphs to Structure Programs - group of 8 »
F Zhang, EH D Hollander - IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, 2004 - doi.ieeecomputersociety.org
Advanced computer architectures rely mainly on compiler optimizations for
parallelization, vectorization, and pipelining. Efficient code generation is based ...

April 2004 (Vol. 30, No. 4)   pp. 231-245 Using Hammock Graphs to Structure Programs
Fubo Zhang  Erik H. D'Hollander, IEEE

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/TSE.2004.1274043

Abstract Advanced computer architectures rely mainly on compiler optimizations for parallelization, vectorization, and pipelining. Efficient code generation is based on a control dependence analysis to find the basic blocks and to determine the regions of control. However, unstructured branch statements, such as jumps and goto's, render the control flow analysis difficult, time-consuming, and result in poor code generation. Branches are part of many programming languages and occur in legacy and maintenance code as well as in assembler, intermediate languages, and byte code. A simple and effective technique is presented to convert unstructured branches into hammock graph control structures. Using three basic transformations, an equivalent program is obtained in which all control statements have a well-defined scope. In the interest of predication and branch prediction, the number of control variables has been minimized, thereby allowing a limited code replication. The correctness of the transformations has been proven using an axiomatic proof rule system. With respect to previous work, the algorithm is simpler and the branch conditions are less complex, making the program more readable and the code generation more efficient. Additionally, hammock graphs define single entry single exit regions and therefore allow localized optimizations. The restructuring method has been implemented into the parallelizing compiler FPT and allows to extract parallelism in unstructured programs. The use of hammock graph transformations in other application areas such as vectorization, decompilation, and assembly program restructuring is also demonstrated.  References
[1] S. Alagic, and M.A. Arbib, The Design of Well-Structured and Correct Programs. Springer, 1978.
[2] J.-R. Allen, K. Kennedy, C. Porterfield, and J. Warren, Conversion of Control Dependence to Data Dependence Proc. 10th Ann. ACM Symp. Principles of Programming Languages, pp. 177-189, Jan. 1983.
[3] Z. Ammarguellat, A Control-Flow Normalization Algorithm and Its Complexity IEEE Trans. Software Eng., vol. 18, no. 3, pp. 237-251, 1992.
[4] M.A. Arbib, and S. Alagic, Proof Rules for Gotos Acta Informatica, vol. 11, pp. 139-148, 1979.
[5] E. Ashcroft, and Z. Manna, The Translation of Goto Programs into While Programs Proc. IFIP Congress 71, C. Freiman, J. Griffith, and J. Rosenfeld, eds., vol. 1, pp. 250-255, 1972.
[6] B. Dutertre, Elements of Mathematical Analysis in PVS Proc. Ninth Int'l Conf. Theorem Proving in Higher Order Logics TPHOL, J. Von Wright, J. Grundy, and J. Harrison, eds., Aug. 1996.
[7] C. Boehm, and G. Jacopini, Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules Comm. ACM, vol. 9, no. 5, pp. 366-371, May 1966.
[8] L. Carter, B. Simon, B. Calder, L. Carter, and J. Ferrante, Path Analysis and Renaming for Predicated Instruction Scheduling Int'l J. Parallel Programming, vol. 28, no. 6, pp. 563-588, 2000.
[9] C. Cifuentes, Structuring Decompiled Graphs Lecture Notes in Computer Science, vol. 1060, pp. 91-104, 1996.
[10] B. De Bus, D. Kästner, D. Chanet, L. Van Put, and B. De Sutter, Post-Pass Compaction Techniques Comm. ACM, vol. 46, no. 8, pp. 41-46, 2003.
[11] E.H. D'Hollander, and F. Zhang, Restructuring Program Transformations with Proof Verification Using PVS Technical Report RUG/ELIS01, p. 47, 2001.
[12] E.H. D'Hollander, F. Zhang, and Q. Wang, The Fortran Parallel Transformer and Its Programming Environment Information Sciences, vol. 106, nos. 3-4, pp. 293-317, 1998.
[13] A.M. Erosa, and L.J. Hendren, Taming Control Flow: A Structured Approach to Eliminating Goto Statements Proc. Fifth Int'l Conf. Computer Languages, pp. 229-240, 1994.
 
[14] J. Ferrante, K.J. Ottenstein, and J.D. Warren, The Program Dependence Graph and Its Use in Optimization ACM Trans. Programming Languages and Systems, vol. 9, no. 3, pp. 319-349, 1987.
[15] P. Havlak, Nesting of Reducible and Irreducible Loops ACM Trans. Programming Languages and Systems (TOPLAS), vol. 19, no. 4, pp. 557-567, 1997.
[16] M.S. Hecht, and J.D. Ullman, Characterizations of Reducible Flow Graphs J. ACM, vol. 21, no. 3, pp. 367-375, 1974.
[17] C.A.R. Hoare, An Axiomatic Basis of Computer Programming Comm. ACM, vol. 12, pp. 576-580, 1969.
[18] C.A.R. Hoare, An Axiomatic Definition of the Programming Language Pascal Acta Informatca, vol. 2, pp. 335-355, 1973.
[19] J. Janssen, and H. Corporaal, Making Graphs Reducible with Controlled Node Splitting ACM Trans. Programming Languages and Systems, vol. 19, no. 6, pp. 1031-1052, 1997.
[20] V.N. Kas'janov, Distinguishing Hammocks in a Directed Graph Soviet Math. Doklady, vol. 16, no. 5, pp. 448-450, 1975.
[21] A. Klauser, T. Austin, D. Grunwald, and B. Calder, Dynamic Hammock Predication for Non-Predicated Instruction Set Architectures Proc. 1998 Int'l Conf. Parallel Architectures and Compilation Techniques (PACT '98), pp. 278-285, Oct. 1998.
[22] L. Lamport, How to Make a Multiprocessor Computer that Correctly Executes Multiprocess Programs IEEE Trans. Computers, vol. 28, no. 9, pp. 690-691, 1979.
[23] P. Morris, R.A. Gray, and R.E. Filman, GOTO Removal Based on Regular Expressions J. Software Maintenance Research and Practice, vol. 9, no. 1, pp. 47-66, Jan./Feb. 1997.
[24] H.R. Nielson, and F. Nielson, Semantics with Applications. John Wiley and Sons, 1993.
[25] G. Oulsnam, Unravelling Unstructured Programs The Computer J., vol. 25, no. 3, pp. 379-387, Aug. 1982.
[26] G. Oulsnam, The Algorithmic Transformation of Schemas to Structured Form The Computer J., vol. 30, no. 1, pp. 43-51, Feb. 1987.
[27] S. Owre, J. Rushby, N. Shankar, and F. von Henke, "Formal Verification for Fault-Tolerant Architectures: Prolegomena to the Design of PVS," IEEE Trans. Software Eng., vol. 21, pp. 107-125, Feb. 1995.
 
[28] S. Owre, J.M. Rushby, and N. Shankar, PVS: A Prototype Verification System Proc. 11th Int'l Conf. Automated Deduction (CADE-11), D. Kapur, ed., June 1992.
[29] W.W. Peterson, T. Kasami, and N. Tokura, On the Capabilities of While, Repeat, and Exit Statements Comm. ACM, vol. 16, no. 8, pp. 503-512, Aug. 1973.
[30] L. Ramshaw, Eliminating Goto's While Preserving Program Structure J. ACM, vol. 35, no. 4, pp. 893-920, Oct. 1988.
[31] N. Shankar, Steps Towards Mechanizing Program Transformations Using PVS Science of Computer Programming, vol. 26, nos. 1-3, pp. 33-57, May 1996.
[32] S. Unger, and F. Mueller, Handling Irreducible Loops: Optimized Node Splitting Versus DJ-Graphs ACM Trans. Programming Languages and Systems (TOPLAS), vol. 24, no. 4, pp. 299-333, 2002.
[33] M. Weiser, Program Slicing IEEE Trans. Software Eng., vol. 10, no. 4, pp. 352-357, July 1984.
[34] M.H. Williams, Generating Structured Flow Diagrams: The Nature of Unstructuredness The Computer J., vol. 20, no. 1, pp. 45-50, Feb. 1977.
[35] M.H. Williams, and G. Chen, Restructuring Pascal Programs Containing Goto Statements The Computer J., vol. 28, no. 2, pp. 134-137, 1985.
[36] M.H. Williams, and H.L. Ossher, Conversion of Unstructured Flow Diagrams to Structured Form The Computer J., vol. 21, no. 2, pp. 161-167, 1978.
[37] F. Zhang, FPT: A Parallel Programming Environment PhD thesis, Dept. of Electrical Eng., Univ. of Ghent, 1996.
[38] F. Zhang, and E.H. D'Hollander, Extracting the Parallelism in Programs with Unstructured Control Statements Proc. Int'l Conf. Parallel and Distributed Systems, (ICPADS '94), pp. 264-270, Dec. 1994.
 
  Index Terms- Program transformation, structured programming, compilers, optimization, parallel processing, software/program verification, correctness proofs.

Citation:  Fubo Zhang, Erik H. D'Hollander, "Using Hammock Graphs to Structure Programs," IEEE Transactions on Software Engineering, vol. 30,  no. 4,  pp. 231-245,  Apr.,  2004.
The Program Structure Tree: Computing Control Regions in.. - Johnson, Pearson, Pingali (1994)   (28 citations)  (Correct)

....applications of the PST to parallel and incremental program analysis. 2 Single entry single exit regions and the program structure tree In the literature, the term single entry single exit region is not used consistently there appear to be several related constructs aliased to this term [Kas75, Val78, TV80, GPS90] Therefore, we begin this section with a formal definition of single entry single exit regions as used in this paper . This definition is motivated in part by considerations of control dependence, as will be made precise in Section 5. We then show that single entry single ....

V. N. Kas'janov. Distinguishing hammocks in a directed graph. Soviet Math. Doklady, 16(5):448--450, 1975.

Range Searching Over Tree Cross Products - Buchsbaum, Goodrich, Westbrook (2000)   (7 citations)  (Correct)

....node, t. A node u dominates a node v if every path from s to v goes through u. A node v post dominates a node u if every path from u to t goes through v. The hammock between two nodes u and v is the set of nodes dominated by u and post dominated by v. This modi es the de nition due to Kas janov [18]. Johnson, Pearson, and Pingali [17] de ne a canonical, nested hammock structure, which is useful in compiler control ow analysis, and devise an O(m) time algorithm to discover it. n = jV j, and m = jEj. No previous result, however, allows ecient, on line queries of the form: return the ....

V. N. Kas'janov. Distinguishing hammocks in a directed graph. Sov. Math. Dokl., 16(2):448-50, 1975.

Finding Regions Fast: Single Entry Single Exit and.. - Johnson, Pearson.. (1993)   (8 citations)  (Correct)

....behavior. The topmost SESE region on this stack when DFS reaches the entry node of a SESE region R 1 is the name of the smallest SESE region containing R 1 . 5. 3 Discussion As a final remark, we note that a concept related to SESE regions called a hammock has been defined in the literature [Kas75]. Although it appears common practice to confuse hammocks and SESE regions, they are in fact different. The exit node of a hammock can be the target of edges outside the hammock; therefore, there are hammocks that are not SESE regions, as shown in Figure 7. Also, the entry node of a hammock cannot ....

....node of a hammock cannot be the target of an edge from the exit of the hammock; therefore, there are SESE regions that are hammocks. For example, a repeat until loop in a structured program is a SESE region but it is not a hammock. The standard algorithm for finding hammocks has complexity O(EN ) [Kas75]. It may be possible to use the ideas of this paper to find hammocks in O(E) time, but we have not explored this further. 6 Extensions We conclude this paper by describing three open problems related to this work. A small program transformation can increase the number of SESE regions in the ....

V. N. Kas'janov. Distinguishing hammocks in a directed graph. Soviet Math. Doklady, 16(5):448-- 450, 1975.

Dependence-Based Program Analysis - Johnson, Pingali (1993)   (52 citations)  (Correct)

....ffl e 1 dominates e 2 , e 2 postdominates e 1 , and every cycle containing e 1 also contains e 2 and vice versa. ffl e 1 and e 2 have the same control dependences. For lack of space, we omit the proof of this theorem. A related structure called a hammock has been discussed in the literature [Kas75] Hammocks are not the same as singleentry single exit regions since the exit node in a hammock can be the target of edges outside the hammock; besides, the algorithm for finding hammocks is O(EN ) Just as def use chains are intercepted by OE functions in the SSA representation, they are ....

V. N. Kas'janov. Distinguishing hammocks in a directed graph. Soviet Math. Doklady, 16(5):448--450, 1975.

Efficient Parallel Shortest-Paths in Digraphs with a Separator Decomposition - group of 7 »
E Cohen - J. Algorithms, 1996 - portal.acm.org
... Their algorithm is based on paralleliz- ing the hammock decomposition technique
introduced by Fredrickson [5]. Their algorithm runs in 0(log2 n) time and ...

Dependence-Based Program Analysis - group of 6 »
R Johnson, K Pingali - PLDI, 1993 - portal.acm.org
... node in a hammock can be the target of edges outside the hammock; besides, the ... Thus
these regions give a hierarchical decomposition of a control flow graph’s ...
Cited by 58 - Web Search - BL Direct

Function Recovery Based on Program Slicing - group of 4 »
F Lanubile, G Visaggio - ICSM, 1993 - ieeexplore.ieee.org
... In order to extract our components we need a decomposition method which uses both
data ... Definition 3: An hammock graph HG is a quadruple (N, E, IQ, ne), where (N ...
Cited by 16 - Web Search

Oulsnam  Works

G. Oulsnam: Unravelling Unstructured Programs. Comput. J. 25(3): 379-387 (1982)

The Computer Journal, Volume 25, Issue 3, pp. 379-387 Abstract.

Department of Computer Science, University of Queensland, St. Lucia, Australia

A method is presented for converting unstructured program schemas to strictly equivalent structured form. The predicates of the original schema are left intact with structuring being achieved by the duplication of the original decision nodes without the introduction of compound predicate expressions, or, where possible, by function duplication alone. It is shown that structured schemas must have at least as many decision nodes as the original unstructured schema, and must have more when the original schema contains schema contains branches out of alternation constructs. The structuring method allows the complete avoidance of function duplication, but only at the expense of decision node duplication. It is shown that structured schemas always require an increase in space-time requirements, and it is suggested that this increase can be used as a complexity measure for the original schema.

The Algorithmic Transformation of Schemas to Structured Form -- Oulsnam 30 (1) 43 -- The Computer Journal

G. Oulsnam: The Algorithmic Transformation of Schemas to Structured Form. Comput. J. 30(1): 43-51 (1987)

G. Oulsnam *

Department of Computer Science, University College, Cork, Republic of Ireland, UK

Algorithms are given to transform unstructured program schemas into equivalent structured forms. These algorithms are shown to have a computational complexity which is linearly related to schema size for almost all schemas, but at worst exponential with an exponent greater than but asymptotically close to one for large problems. Structuring is achieved by first identifying the forward paths of the schema and reducing them to an equivalent structured elementary path E. Each back path of E is then recursively structured to an equivalent single back arc, thus reducing the original schema to a single elementary path together with a set of possibly overlapping back arcs. The remaining unstructuredness is removed by recursive application of a loop-structuring algorithm. The algorithms are illustrated by application to a complex hypothetical schema and to two practical problems.
Received August 1984.

G. Oulsnam: Cyclomatic Numbers Do Not Measure Complexity of Unstructured Programs. Inf. Process. Lett. 9(5): 207-211 (1979)

Interactive Control Restructurin g - group of 2 » DJ Rosenkrantzl, JM Bruno, GE Co - portal.acm.org
... Our algorithm uses Oulsnam's technique of repeatedly structurin g and condensing subgraphs of the flowgraph until the graph has ... Web Search

Baker Decomposition

Extracting the Parallelism in Program with non-structured.. - Fubo Zhang And   (Correct)

....be applied to generate a doall loop. The program structuring is based on a hammock transformation which makes the resulting program readable and clarifies the control scope. A lot of related work has been done on the program structuring. These techniques are applied either on reducible graphs [8, 15, 19, 20] or on irreducible graphs [7] New variables are introduced to register the state of the condition of a if goto statement. The newly proposed technique focuses on the discussion of forward, backward and exit branches. The processing of reducible and irreducible flow graph is not distinguished. ....

....are structured by flow diagrams transformations. A reducible flow graph is a graph to which an interval analysis can be applied to structure the graph. R.E. Tarjan [17] has discussed the properties of a reducible flow graph and an algorithm is proposed to reduce a reducible graph. B.S. Baker [8] proposed an algorithm to transform a flow graph into a structured program. L. Ramshaw [15] gave theorems and rules to eliminate goto s and preserve the program structure. These techniques are only applied on reducible graphs. However, unstructured forms may remain in the irreducible flow graph of ....

Baker, B., "An algorithm for structuring flowgraphs," JACM, vol 24, no. 1, 1977.

Recognizing a Program's Design: A Graph-Parsing Approach - group of 4 »
C Rich, LM Wills - IEEE Software, 1990 - portal.acm.org
... Recognizing a Program's Design: A Graph-Parsing Approach. Full text, Full
text available on the Publisher sitePublisher Site. Source, ...
Cited by 115 - Web Search

 

Etc

[PS] Good and semi-strong colorings of oriented planar graphs - group of 5 »
A Raspaud, E Sopena - Information Processing Letters, 1994 - labri.fr
... Ak coloring of an oriented graph G = (V; A) is an assignment c of one of the colors
1; 2; : : :; k to each vertex of the graph such that, for every arc (x; y ...
Cited by 45 - View as HTML - Web Search - BL Direct

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