Browse Prior Art Database

STRUCTURAL ANALYSIS: A NEW APPROACH .'::F~OW ANALYSIS IN OPTIMIZING COMPILERS

IP.com Disclosure Number: IPCOM000128174D
Original Publication Date: 1979-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 12 page(s) / 41K

Publishing Venue

Software Patent Institute

Related People

M. Sharir: AUTHOR [+3]

Abstract

In this paper we present a new approach to program flow analysis. It extends the improved interval analysis and interval-based data-flow analysis methods of Schwartz and Sharir [SSI in the sense that it also detects standard structured control-flow patterns, such as 'if-then-else', 'begin-end', 'while-do' etc. and then uses explicit formulae of Rosen's kind [Rol I to analyze the data-flow within these structures. Assuming a standard intermediate-level code representation of the program to be analyzed (i.e. a flow-graph consisting of basic blocks [He], [AU]), our approach begins with a structural analysis phase. This is a generalized interval analysis step which uses a depth-first spanning tree to construct a hierarchical tree structure of flow subgraphs imbedded within each other. These subgraphs (control structures) can be either the standard control-flow patterns mentioned above, or else general intervals (with or without imbedded irreducibilities) of the kind described in [SSI. If the program to be analyzed is well-structured, then our structural analysis will uncover most of the program's original control structures and can therefore be regarded as an improved 'unparser' of the program control flow. Unlike the graph-grammar approach of [FKZ] our, method can process any flow graph, tolerates irreducibilities and 'localizes' them as in [SS3, but in addition its performance will improve as the programs to be analyzed become more well structured.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 10% of the total text.

Page 1 of 12

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

STRUCTURAL ANALYSIS: A NEW APPROACH .'::F~OW ANALYSIS IN OPTIMIZING COMPILERS

by M. Sharir

October 1979 Report No. 015 This work is based upon work supported in part by the National Science Foundation under Grant No. MCS-76-00116: and in part by the U. S. Department of Energy, Contract No. EY-76-C-02-3077.

Any opinions, findings and conclusions or recommendations expressed in this publication are those of the author and do not necessarily reflect the view of the NSF^.

1. Introduction

In this paper we present a new approach to program flow analysis. It extends the improved interval analysis and interval-based data-flow analysis methods of Schwartz and Sharir [SSI in the sense that it also detects standard structured control-flow patterns, such as 'if-then-else', 'begin-end', 'while-do' etc. and then uses explicit formulae of Rosen's kind [Rol I to analyze the data-flow within these structures. Assuming a standard intermediate-level code representation of the program to be analyzed (i.e. a flow-graph consisting of basic blocks [He], [AU]), our approach begins with a structural analysis phase. This is a generalized interval analysis step which uses a depth-first spanning tree to construct a hierarchical tree structure of flow subgraphs imbedded within each other. These subgraphs (control structures) can be either the standard control-flow patterns mentioned above, or else general intervals (with or without imbedded irreducibilities) of the kind described in [SSI. If the program to be analyzed is well- structured, then our structural analysis will uncover most of the program's original control structures and can therefore be regarded as an improved 'unparser' of the program control flow. Unlike the graph-grammar approach of [FKZ] our, method can process any flow graph, tolerates irreducibilities and 'localizes' them as in [SS3, but in addition its performance will improve as the programs to be analyzed become more well structured.

A similar structural analysis technique has been described by Baker (Ba], though only for the purpose of source-to-source program transformation; our algorithm is relatively simpler and handles nonstructured control flow patterns in a way more suitable for data flow analysis. The benefits of this type of structural analysis are as follows: (i) It facilitates the use of elimination techniques which use explicit data-flow formulae of Rosen's kind [Roll for subsequent data-flow analysis. Our technique generalizes similar interval-based techniques in [SS], but turns out to be faster for well structured programs. (ii) Our techniques indicate that flow-graph based program analysis and direct analysis of the program's parse-tree, as considered by Rosen [Roll and in a completely context by Wulf et al.[Wu1, are not as different as they may seem, but that uniform program analysis procedures can handle either kind of representation by essentially the same...