Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1998-11-03
2002-09-03
Black, Thomas (Department: 2121)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S154000, C717S156000
Reexamination Certificate
active
06446258
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field of the Invention
The present invention relates to compilers.
2. Background Art
A compiler is a program that reads a source program written in a source language and translates it into a target program in a target language. For example, a compiler may translate a high level source program (such as C++) into compiled code that can be understood by a processor, such as a microprocessor.
Block ordering (also called code placement) concerns the order in which instructions and blocks of instructions are to appear in physical memory. The block ordering may involve the selection of certain branch instructions between some of the blocks. It is generally true that it takes fewer cycles or other processor resources if the instruction is able to fall through to the next contiguous instruction in memory rather than branching to another instruction. Accordingly, block ordering involves attempting to pick the direction of a conditional branch such that it falls through to an instruction that is more likely to occur and branches to an instruction less likely to occur. Another benefit of doing so is that spatial locality is more likely to exist in a cache. Instruction scheduling involves moving instructions (called code motion) to better assign instructions to an execution unit for a particular cycle. The scheduler may move code within a block (called local code motion) or between blocks (called global code motion). Some schedulers are capable of only local code motion, while other schedulers are capable of local and global code motion.
In prior art compilers, block ordering and instruction scheduling are independent activities. For example, in the compiling process of some prior art compilers, first an instruction order and accordingly a block order is chosen. Next, instruction scheduling is performed. Instruction scheduling involves code motion or moving instructions to different locations in physical memory to attempt better utilization of execution units. If there are three execution units, an attempt is made to have each execution unit be busy during each cycle. Following the completion of scheduling, the physical order is re-evaluated to see if can be improved. For example, if an unconditional branch branches to the next sequential instruction in memory, the unconditional branch can be removed without changing the operation of the program. However, in making these changes to the physical order, the execution units may be less well utilized. Good block ordering increases performance. Good instruction scheduling also increases performance. In the prior art compilers, however, by treating instruction scheduling and ordering as sequential, independent activities, both the instruction ordering and scheduling suffer. Accordingly, performance suffers.
Accordingly, there is a need for a compiler with improved instruction scheduling and ordering.
SUMMARY
In some embodiments, the invention includes a method of compiling instructions of a program. The method includes receiving instructions for code motion and controlling the code motion while interacting with block ordering.
The code motion may be done as part of instruction scheduling. The scheduling may involve making an assessment of the cost of scheduling an instruction and determining whether to make the code motion based on the cost.
The scheduling may involve regeneration of predicate expressions to invert conditional branches.
REFERENCES:
patent: 4656583 (1987-04-01), Auslander et al.
patent: 5175856 (1992-12-01), Van Dyke et al.
patent: 5557761 (1996-09-01), Chan et al.
patent: 5787287 (1998-07-01), Bharadwaj
patent: 5790867 (1998-08-01), Schmidt et al.
patent: 5828886 (1998-10-01), Hayashi
patent: 5887174 (1999-03-01), Simons et al.
patent: 5894576 (1999-04-01), Bharadwaj
patent: 5978588 (1999-11-01), Wallace
patent: 5999738 (1999-12-01), Schlansker et al.
patent: 6044222 (2000-03-01), Simons et al.
patent: 6059840 (2000-05-01), Click, Jr.
patent: 6072951 (2000-06-01), Donovon et al.
patent: 6077314 (2000-06-01), Ng
patent: 6117185 (2000-09-01), Schmidt
patent: 6128775 (2000-10-01), Chow et al.
patent: 6151706 (2000-11-01), Lo et al.
patent: 6170083 (2001-01-01), Adl-Tabatabai
patent: 6243864 (2001-06-01), Odani et al.
patent: 6260190 (2001-07-01), Ju
Morgan, R.; Building an Optimizing Compiler. Digital Press, Wodburn, MA, Dec. 1997, sections 2.7-2.9 and 14.4.*
Morgan, B.; Building an Optimizing Compiler, Digtal Press, Dec. 01, 1997, chapter 14.*
Agrawal, G.; “Interprocedural Partial Redundancy Elimination With Application to Distributed Memory Compilation”. IEEE/IEE[online], IEEE Transactions on Parallel and Distributed Systems, p. 609(16), Jul. 1998.*
Aho et al.; Compilers: Principles, Techniques, and Tools. Reading MA, Addison-Wesley Publishing Co., Chapter 10, Dec. 1985.*
Muchnick, S.; Advanced Compiler Design and Implementation. San Francisco, CA, Morgan Kaufmann Publishers, Chapter 17, Aug. 1997.*
Morgan, B.; Building and Optimizing Compiler. New York, NY, Digital Press, Chapters 2 and 8, Dec. 1997.*
Nakatani et al.; “Using a Lookahead Window in a Compaction-Based Parallelizing Compiler”. IEEE/IEE[online], Proceedings of the 23rd Annual Workshop and Symposium on Microprogramming and Microarchitecture, p. 57(11), Nov. 1990.
Bharadwaj Jayashankar
McKinsey Christopher M.
Aldous Alan K.
Black Thomas
Booker Kelvin
Intle Corporation
LandOfFree
Interactive instruction scheduling and block ordering does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Interactive instruction scheduling and block ordering, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interactive instruction scheduling and block ordering will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2912953