Browse Prior Art Database

Space Sharing by Program Data

IP.com Disclosure Number: IPCOM000075929D
Original Publication Date: 1971-Dec-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 3 page(s) / 35K

Publishing Venue

IBM

Related People

McCarthy, M: AUTHOR

Abstract

In many current computing environments (time-sharing virtual memory, multi-programming), paged and hierarchical memories imply transfers of program data, as it passes between active and inactive states, from one storage class to another throughout execution. This transfer frequency can be significantly reduced if variables with discrete use spans are assigned a common storage location, thereby allowing maximal utilization of high-speed memory for variables with concurrent activity cycles.

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 54% of the total text.

Page 1 of 3

Space Sharing by Program Data

In many current computing environments (time-sharing virtual memory, multi-programming), paged and hierarchical memories imply transfers of program data, as it passes between active and inactive states, from one storage class to another throughout execution. This transfer frequency can be significantly reduced if variables with discrete use spans are assigned a common storage location, thereby allowing maximal utilization of high-speed memory for variables with concurrent activity cycles.

Global flow analysis - the determination of all possible execution paths from any straight-line program segment, or block, to any other block is currently done by a compiler's optimizer phase, to allow the movement of loop-invariant code to a less frequently executed path, deletion of redundant computation, and optimal register assignment across loops. Program statistics gathered in this process include points of use and definition of variables by block and loop, and initial and terminal status (active or inactive) of variables by these program subdivisions.

Using this information, a determination can be made by the compiler of the amount of physical storage actually required by local program data, and its order of placement can be influenced by the nesting depth of its active cycles.

An active cycle of the variable i is defined to extend from a definition of i to the point of furthest possible use of that definition. Letting C(ij) represent a particular active cycle of the variable i, then if

(Image Omitted)

where n is the minimum number of active cycles of i and k, then variables i and k may share a common storage location.

The condition is illustrated in the diagram, where the numbered circles represent program blocks, the lines between them program flow, the letters program variables, and the vertical lines beside them particular active cycles.

By inspection, several possibilities for storage sharing are apparent. The variables A and D can share space, for example, as can C and I.

The process can be focused at different levels of program segment loop region, block, statement or expression. In the example shown, the focus is at the block level, where any use of a variable within a block extends its...