Instruction reducing predicate copy

Details Instruction reducing predicate copy Instruction reducing predicate copy

2000-03-01

2003-10-21

Dam, Tuan Q. (Department: 2122)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S144000, C717S150000, C717S155000, C717S156000, C717S159000, C717S161000, C709S241000, C709S241000, C712S226000

Reexamination Certificate

active

06637026

ABSTRACT:

FIELD
The present invention relates generally to the compilation of software, and more specifically to register allocation for processors that support predication.
BACKGROUND OF THE INVENTION
Modem processors that support predication guard the execution of instructions using predicates. A predicate is a value in a register, typically a single bit, that if set, allows instructions to be executed, and if clear, does not allow an instruction to execute. Predicates are set by predicate generating instructions that affect the instruction flow of the software program executing on the processor.
Predicate generating instructions are placed in the program in or before blocks that affect the control flow. For example, when a first block branches to a second block, and the second block is guarded by a predicate, the first block typically sets the predicate prior to the branch.
When multiple blocks follow a block that changes the control flow, multiple predicates are typically set prior to the branch, one predicate for each block in the future control flow. Oftentimes the multiple predicates are set based on the same condition, and the predicate generating instructions are redundant. Park and Schlansker present an algorithm to generate predicate generating instructions for predicated code. See J. C. H. Park & M. S. Schlansker, “On Predicated Execution,” Tech. Rep. HPL-91-58, HP Laboratories, Palo Alto, Calif., May 1991.
During compilation, a virtual name for a predicate is associated with each block in a control flow graph (CFG). During register allocation, the virtual names for the predicates are mapped to the physical registers in the processor. The number of physical registers is typically much smaller than the number of virtual predicate names. Allocating registers to predicates can be a difficult problem. A discussion of mapping predicates to registers can be found in: David M. Gillies, Dz-ching Roy Ju, Richard Johnson & Michael Schlansker, “Global Predicate Analysis and its Application to Register Allocation,” Proceedings of the 29th Annual International Symposium on Microarchitecture (MICRO), December 1996.
As described above, typical algorithms for compilation create redundant predicate generating instructions. Also, typical algorithms for register allocation map multiple virtual predicates corresponding to redundant predicate generating instructions to different physical registers, which are part of a finite resource. For the reasons stated above, and for other reasons stated below which will become apparent to those skilled in the art upon reading and understanding the present specification, there is a need in the art for an alternate method and apparatus for reducing the number of predicate generating instructions in software.


REFERENCES:
patent: 5920716 (1999-07-01), Johnson et al.
patent: 5937195 (1999-08-01), Ju et al.
patent: 6009512 (1999-12-01), Christie
patent: 6157996 (2000-12-01), Christie et al.
patent: 6260190 (2001-07-01), Ju
patent: 6282708 (2001-08-01), Augusteijn et al.
patent: 6594824 (2003-07-01), Volkonsky et al.
August, David I., Connors, Daniel A., Mahlke, Scott A., Sias, John W./, Crozier, Kevin M., Cheng, Ben-Chung, Eaton, Patrick Olaniran, Qudus B., Hwu, Wen-mei W., Integrated Predicated and Speculative Execution in the IMPACT EPIC Architecture, 1998, IEEE.*
August, David I., Hwu, Wne-mei, Mahlke, Scott A., “A Framework for Balancing Control Flow and Predication”, 1997, IEEE, retrieved Jul. 2, 2002.*
Gillies, David M., Ju, Dz-ching Roy, Johnson, Richard, Schlansker, Michael, “Global Predicate Analysis and its Application to Register Allocation”, 1996, ACM database, retrieved Jul. 11, 2002.*
Klaluser, Artur, Austin, Todd, Grunwald, Dirk, Calder, Brad, “Dynamic Hammock Predication for Non-Predicated Instruction Set Architectures”, 1998, IEEE, retrieved Jul. 11, 2002.*
Gillies, D.M., et al., “Global Predicate Analysis and its Application to Register Allocation”,IEEE 1996,114-125, (1996).
Park, J.C., et al., “On Predicated Execution”,Software and Systems Laboratory, HPL-91-58Copyright Hewlett-Packard Company 1991, 1-25, (1991).

Affiliated with

Also associated with

Rating

Instruction reducing predicate copy does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Instruction reducing predicate copy, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Instruction reducing predicate copy will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3135797