System and method of generating object code using aggregate instruction movement

Patent 5557761 Issued on September 17, 1996. Estimated Expiration Date:

January 25, 2014. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.

Abstract Claims Description Full Text

Inventors

Application

No. 186248 filed on 01/25/1994

US Classes:

717/156, Using flow graph717/144, Including graph or tree representation (e.g., abstract syntax tree or AST)717/146Including intermediate code

Examiners

Primary: Harrell, Robert B.

Attorney, Agent or Firm

Sterne, Kessler, Goldstein & Fox P.L.L.C.

International Class

G06F 009/45

Abstract

A system and method of generating object code from an intermediate representation of source code is described. The intermediate representation includes a plurality of basic blocks each being represented by a plurality dam dependency graphs, wherein each data dependency graph comprises a plurality of nodes each corresponding to an instruction from the target computer instruction set. The present invention operates by selecting a source basic block (that is one of the basic blocks of the intermediate representation) and a target basic block (that is another of the basic blocks of the intermediate representation), and by identifying a maximal set of instructions contained in the source basic block that are movable from the source basic block to the target basic block without violating any data dependency relationships of the data dependency graphs. An overall cost model of aggregately moving instructions of the maximal set from the source basic block to the target basic block is generated. This cost model specifies an executable cost of moving each of the instructions of the maximal set from the source basic block to the target basic block. Then, the present invention aggregately moves one or more instructions of the maximal set from the source basic block to the target basic block according to the cost model to form the object code.

Other References

Ford, Jr., L. R. and D. R. Fulkerson, "Static Maximal Flow", Flows in Networks, Publisher: Princeton University Press, pp. 1-22, 1962
Fisher, Joseph A., "Trace Scheduling: A Technical for Global Microcode Compaction", IEEE Transactions on Computers, vol. c-30, No. 7, pp. 478-490, Jul. 1981
Charlesworth, Alan E., "An Approach to Scientific Array Processing: The Architectural Design of the AP-120B/FPS-164 Family", Computer, pp. 18-27, 1981
Aho, Alfred V., Ravi Sethi and Jeffery D. Ullman, Compilers: Principles, Techniques, and Tools, Publisher: Addison-Wesley Publishing Company, pp. 10-23, 1986
Ellis, John R., Bulldog: A Compiler for VLIW Architectures, Publisher: The Massachusettes Institute of Technology, 1986
Nicolau, Alexandru, "A Fine-Grain Parallelizing Compiler", Scheduling, Computer Science Department, Cornell University, 1986
Ebcioglu, Kemal and Nicolau Alexandru, "A global resource-constrained parallelization technique", Scheduling, pp. 154-163, 1989
James C. Dehnert et al., "Compiling for the Cydra 5", The Journal of Supercomputing, 7, pp. 181-227 (1993)
Bernstein, David and Michael Rodeh, "Global Instruction Scheduling for Superscalar Machines", Proceedings of the ACM SIGPLAN '91 Conference on Programming Language Design and Implementation, Toronto, Canada, Jun. 26-28, 1991, pp. 241-255, 1991
Lowney, P. Geoffrey et al., "The Multiflow Trace Scheduling Compiler", The Journal of Supercomputing, vol. 7, pp. 51-55, 199