Browse Prior Art Database

Identifying Inner Loops of Programs

IP.com Disclosure Number: IPCOM000085381D
Original Publication Date: 1976-Mar-01
Included in the Prior Art Database: 2005-Mar-02
Document File: 3 page(s) / 29K

Publishing Venue

IBM

Related People

Chandra, AK: AUTHOR

Abstract

Given a flow chart program it is valuable to know which statements are executed most often so that a compiler may preferentially optimize these (owing to a limitation in the time resource of the compiler, and the fact that optimization often increases the size of the code generated). If frequency counts are not available the compiler has to work from the syntactic description of the program.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Identifying Inner Loops of Programs

Given a flow chart program it is valuable to know which statements are executed most often so that a compiler may preferentially optimize these (owing to a limitation in the time resource of the compiler, and the fact that optimization often increases the size of the code generated). If frequency counts are not available the compiler has to work from the syntactic description of the program.

The present method provides a way of determining the inner loops of flow chart programs, which corresponds to the notion of "being executed more often", in a manner superior to an obvious method. The method can also be applied to a recursive program where it would determine the procedures called most often.

Convert the flow chart program into its control graph, where each node in the graph corresponds to a statement in the flow chart, and there is an edge between two nodes corresponding to two statements of the flow chart if control can flow from the first statement to the second. It is assumed that every node in the graph can be reached from the initial node in the graph by some path (if not, delete the node), and that there is a path from each node to some final node (if not, replace the node by a special final statement, and delete all its outgoing edges).

For two nodes A, B in the graph, it can be said A>/-B if (and only if) for every path from the initial to a final statement #A>/-#B-1 (where #A is the number of A's on the path, likewise for #B). If A>/-B and B>/-A it can be said A, B are in the same cycle, but if A>/-B, B not>/-A it is said A is an inner loop relative to B. The justification is the observation that A>/-B if and only if every cycle from B to itself must pass through A. (A cycle dominates B.)

Also A>/-B and B not>/-A if and only if the statement corresponding to A can be executed arbitrarily many times more than B, but not conversely - in fact B can be executed at most once more than A. The above also shows that the relation >/-...