Browse Prior Art Database

Execution Time Optimizer

IP.com Disclosure Number: IPCOM000076534D
Original Publication Date: 1972-Mar-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Hopkins, ME: AUTHOR

Abstract

Described is a scheme which enables a computer to perform some of the functions of an optimizing compiler during execution of an object program. The program is represented in main storage as an execution list and dictionary. The execution list indicates the sequencing through the statements, While the dictionary shows the expression trees with the operations exposed.

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

Page 1 of 2

Execution Time Optimizer

Described is a scheme which enables a computer to perform some of the functions of an optimizing compiler during execution of an object program. The program is represented in main storage as an execution list and dictionary. The execution list indicates the sequencing through the statements, While the dictionary shows the expression trees with the operations exposed.

Execution of a program proceeds sequentially through the execution list, except when altered by a transfer of control (branch) instruction or a hardware interrupt. The operands of the execution list instructions point to expression trees in the dictionary rather than to data. The dictionary contains a number of entries and each entry has a function field as well as a A and B operand. The functions are similar to normal computer operations such as load, add, multiply and the like. The A and B operands are of several types: a storage location or machine register, an immediate value, another dictionary entry. Translation of the following source: A = (A + B) * (C - D) C = (A + B) / (C - D) would result in the following Dictionary Execution List F A B SET t(1), t(7) t(1) L RA A SET t(3), t(8) t(2) L RA B t(3) L RA C t(4) L RA D t(5) + t(j) t(2) t(6) - t(3) t(4) t(7) * t(5) t(6) t(8) / t(5) t(6).

The common subexpressions are eliminated in the dictionary. Also, the operation L (load) is interpreted as a store when it is the left-hand operand of a SET.

Executions of an instruction results in the evaluation of the expression tree to which that instructions operands point. The result and all intermediate values are placed in an associative memory, referred to as a hopper. The hopper contains the following fields:

1) The value associated with the temporary

2) The T number which indicates the dictionary entry that caused this value to be computed

3) The P number is used to distinguish identical T numbers which were compiled separately, or where recursion has led to the computation of different generations of a variable or expression. The P number is derived from a counter which is incremented at each CALL and decremented at each R...