Browse Prior Art Database

Algorithm for Mapping Self Describing Records

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

Publishing Venue

IBM

Related People

Seaman, RP: AUTHOR

Abstract

The method presently used for mapping data structures, in for example, the PL/I Optimizer compiler can use a thousand machine instructions on a comparatively simple structure in which the REFER option is used. Described is an algorithm which shows a considerable increase in efficiency by using a table driven method, which is used at execution time to determine address offsets of the elements of an adjustable structure.

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

Page 1 of 3

Algorithm for Mapping Self Describing Records

The method presently used for mapping data structures, in for example, the PL/I Optimizer compiler can use a thousand machine instructions on a comparatively simple structure in which the REFER option is used. Described is an algorithm which shows a considerable increase in efficiency by using a table driven method, which is used at execution time to determine address offsets of the elements of an adjustable structure.

In the general case, suppose a structure involves REFER objects with values v1, v2, v3, ---vK and the padding within the structure has values p1, p2, p3, ----
pN. Then the address of any element of the structure is an expression involving multiplication and addition operations only on the values v1, v2, and p1, p2 ---. The expression depends upon the fixed parts of the structure. All relevant properties of the structure mapping algorithm are taken account of in the p1, p2 -- values and do not contribute to the complexity of the expression. The values p1, p2 -- can be evaluated at execution time by table look-up, the size of the table being at worst Q**K, where Q is the "granularity" of the structure mapping. By "granularity" of a structure mapping algorithm is meant, the smallest positive integer h for which a change of h in any extent of any structure has no effect on padding amounts in that structure. (The granularity of the IBM PL/I structure mapping algorithm is 8.)

Structures with No Padding: Consider a structure where there is no padding involved, e.g., all items in the structure have the same alignment requirement. Then the offset of any element down the structure may be obtained by adding together the sizes of elements which precede E. If E itself is an array of structures or an array of scalers which inherit a dimension from a containing structure, then the sizes of elements which follow E must be taken into account in determining the multipliers of E, but this again is a straight-forward process. To illustrate the kind of calculations involved two examples are shown. Example 1 DCL 1 S BASED, 2 N FIXED BIN(31), 2 X(*REFER(N)) FIXED BIN (31), 2 E; The offset of E is 4+4*N Example 2 DCL 1 S BASED(P) 2 N FIXED BIN(31), 2 X(*REFER(N)) FIXED BIN(31) 2 A(*REFER(N)), 3 El CHAR(1), 3 E2 CHAR(6) 2 B CHAR(7) For a reference to A(k) its address is: AO (k-LB)*M where, AO = Actual origin of A = 4 + 4* N + address of S. LB = Lower bound of A = 1. M = Multiplier of A = 7. On substituting these values the address calculation is: value(P) + 4 + 4* N + (k-1) * 7 A reference to B has the address: value(P) + 4 + 4* N + 7*N.

Structures involving Padding: The amount of padding between structure elements is determined by the structure mapping rules. In the case of PL/I, these are rather complex and it would be difficult to generate efficient object code which would implement those rules for the general case. The basic idea of this description is to evaluate the padding at execution tim...