Browse Prior Art Database

An Improved Representation of Nested Cyclic Regions

IP.com Disclosure Number: IPCOM000038143D
Original Publication Date: 1989-Nov-01
Included in the Prior Art Database: 2005-Jan-31
Document File: 2 page(s) / 13K

Publishing Venue

IBM

Related People

Malek, G: AUTHOR

Abstract

During the optimization phase of compilation, part of the representation of the program is as a directed graph. In order to do global optimization, data flow equations are created for each node in the graph. This flow graph may be acyclic, or it may have nested cyclic regions (loops). In the latter case, part of the processing is done with these cyclic regions represented as single nodes. To be fully optimizable, these cyclic regions must be reducible regions. Reducible regions can have multiple exits, and when such a region is represented by a single node, the data flow equations for that node become complex and difficult to process.

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

Page 1 of 2

An Improved Representation of Nested Cyclic Regions

During the optimization phase of compilation, part of the representation of the program is as a directed graph. In order to do global optimization, data flow equations are created for each node in the graph. This flow graph may be acyclic, or it may have nested cyclic regions (loops). In the latter case, part of the processing is done with these cyclic regions represented as single nodes. To be fully optimizable, these cyclic regions must be reducible regions. Reducible regions can have multiple exits, and when such a region is represented by a single node, the data flow equations for that node become complex and difficult to process.

This invention represents a way of restructuring a control flow graph in such a way as to eliminate that impediment. This is because it makes the propagation of data flow equations between inner loops and outer loops and between outer loops and acyclic code easier, and this proagation must be done if global optimization is to be done.

In this invention, instead of replacing each nested cyclic region by a single node, each nested cyclic region is placed by one node for the entrance and one for each exit. Also, instead of constructing a special region table, these nodes are embedded in the original flow graph, so they can become the recipients of any code which can be moved out of the loop. The entrance nodes are called pre- headers, and the exit nodes are called post-exits. In order to process the "regio...