| Use of different color sequences for variables of different sizes and different semantics -> Monitor Keywords |
|
|
 
Use of different color sequences for variables of different sizes and different semanticsRelated Patent Categories: Data Processing: Software Development, Installation, And Management, Software Program Development Tool (e.g., Integrated Case Tool Or Stand-alone Development Tool), Translation Of Code, Compiling Code, Analysis Of Code Form, Including Graph Or Tree Representation (e.g., Abstract Syntax Tree Or Ast)Use of different color sequences for variables of different sizes and different semantics description/claimsThe Patent Description & Claims data below is from USPTO Patent Application 20070074190, Use of different color sequences for variables of different sizes and different semantics. Brief Patent Description - Full Patent Description - Patent Application Claims
CROSS-REFERENCE TO PARENT APPLICATION [0001] This application is a divisional application of U.S. patent application Ser. No. 10/402,736 filed on Mar. 28, 2003, which is incorporated by reference herein in its entirety. CROSS-REFERENCE TO COMPUTER PROGRAM LISTING APPENDIX [0002] Note that a computer program listing Appendix A originally filed in U.S. patent application Ser. No. 10/402,736 (see above) is hereby expressly incorporated by reference herein in its entirety. [0003] Appendix A contains the following files which form a part of the present disclosure: CLRGRP.TXT, CLRIDENT.TXT, FUNC.TXT, INST.TXT, PARSER.TXT, REGALLOC.TXT, and STMNT.TXT. The files of Appendix A form source code of computer programs for an illustrative embodiment of the present invention. [0004] The file PARSER.TXT contains a definition of the syntax of a high level language and software for a parser for the language. The file STMNT.TXT contains functions which operate on data structures that represent statements in the program being compiled. The file FUNC.TXT contains functions which operate on data structures that represent functions in the program being compiled. The file INST.TXT contains data structures for instructions. [0005] The files CLRIDENT.TXT and CLRGRP.TXT are extracted from one or more of the above-described files, and respectively illustrate FIGS. 2B and 2C described below. Also, the file REGALLOC.TXT illustrates FIGS. 4A and 4B. [0006] The software in Appendix A is written in object oriented Perl, version 5.6 and can be interpreted using an interpreter available from the Internet address obtained by replacing "-" with "." In the following: www-cpan-org. The software in Appendix A can be used with a workstation available from SUN MICROSYSTEMS, INC running the UNIX or SOLARIS operating system. The software can be used for compiling programs written in a C-like language for execution on a network processor, such as nP7510 available from APPLIED MICRO CIRCUITS CORPORATION (AMCC) of San Diego, Calif. The assembler code generated by such compilation can be assembled using an assembler available from AMCC. COPYRIGHT NOTICE [0007] A portion of the disclosure of this patent document contains material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the U.S. Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever. BACKGROUND [0008] Program compilation is comprised of a number of steps one of which is register allocation for variables in the program. One popular allocation method uses graph coloring and was first described by Chaitin, e.g. in U.S. Pat. No. 4,571,678 that is incorporated by reference herein in its entirety. See also an article entitled "Register Allocation Via Coloring" by G. J. Chaitin et al. appearing in Computer Languages, Vol. 6, pages 47-57, Pergamon Press, Great Britain, 1981 that is incorporated by reference herein in its entirety. [0009] Chaitin's allocator assumes that the software program can use an unlimited number of registers (also called "virtual registers"), constructs an interference graph that models conflicts between virtual registers. The vertices of the interference graph represent virtual registers, and edges connect virtual registers that cannot be assigned to the same real register. [0010] After interference graph has been built, the interference graph's nodes are ordered, and then for each node in this order, a color is chosen from a list of k colors, where k represents the number of real registers in the computer. Each node is colored with a color different from the color of any node to which it is connected (also called "neighbor"). If such a k-coloring cannot be found, one or more values (in virtual registers) are spilled to memory, and the allocator repeats the entire process (but with spilled registers removed from among the virtual registers to be allocated). [0011] In the case of irregular hardware architecture, where irregularity is in the fact that there are registers in which the most significant part and least significant part can be referenced as separate hardware resources Chaitin's allocator overspills e.g. spills virtual registers even in cases where real registers are available in the computer. Such overspillage may be reduced by adding extra edges or extra nodes. Use of extra edges is described by Preston Briggs, Keith D. Cooper and Linda Torczon in an article entitled "Coloring Register Pairs", ACM Letters on Programming Languages and Systems, 1(1):3-13, March 1992 that is incorporated by reference herein in its entirety. Use of extra nodes is described by B. Nickerson in an article entitled "Graph Coloring Register Allocation for Processors with Multi-Register Operands," Proc. SIGPLAN' 90, Conf. on Programming Language Design and Implementation, pp 40-52, June 1990. [0012] However, use of extra edges and/or extra nodes increases the complexity of the interference graph. Instead, weights may be assigned to nodes in the interference graph as stated by Michael D. Smith and Glenn Holloway in an article entitled "Graph-Coloring Register Allocation for Architectures with Irregular Register Resources." This article is believed to have been submitted for publication to the ACM SIGPLAN 2002 Conference on Programming Language Design and Implementation, June 2002, and is incorporated by reference herein in its entirety. [0013] FIGS. 1A and 1B illustrate the register allocator's view of general purpose register resources that are available in the well known x86 instruction set architecture. A resource array having 10 elements is used for the x86 general purpose register file. This resource array is shown in FIG. 1A by a bit vector 101. Each square of the array represents an allocable register resource. The shaded squares in FIG. 1A indicate resources consumed by a particular register name. [0014] As shown in FIG. 1A, register AX consumes the same resources as the two individual registers AL and AH. Specifically, the first two elements of the bit vector (collectively labeled as 112 in FIG. 1A) that are consumed by register AX are same as two elements that are individually consumed by registers AL and AH (labeled as 111A and 111B). Moreover, register EAX is represented by these same two elements of the bit vector (which are labeled as 113), because the upper half of EAX is inaccessible. [0015] Bit vector 101 forms a component of a register class data structure that is used by the register allocator. The register class data structure includes, in addition to bit vector 101, a resource mask 121 (to indicate which hardware resources are available to candidates of a class), weights 122, placements 123, and the following lists of register names: [0016] Ca: {AX, EAX, BX, EBX, CX, ECX, DX, EDX} [0017] Cb: {AL, AH, BL, BH, CL, CH, DL, DH} [0018] Ci: {DI, EDI, SI, ESI} [0019] Cm: {AX, EAX, BX, EBX, CX, ECX, DX, EDX, DI, EDI, SI, ESI} [0020] Class Ca represents the 16- and 32 bit variants of the A, B, C and D registers, and Class Cb represents the nameable 8 bit portions of these registers; class Ci represents 16 bit and 32 bit variants of DI and Si; and Class Cm is a multi-bank register class comprising candidates from Ca and Ci. Class Ci is assigned to all weighted interference graph (WIG) nodes representing registers DI and SI, and class Cm is used for all other 16/32 bit candidates. [0021] The above name lists are used when allocating colors. When a candidate `n` is popped from the stack, the register allocator visits each neighbor of n in the WIG and builds a list of used (unavailable) colors. The register allocator determines the resources used by each neighbor by use of bit vector 101. It then intersects a vector of unavailable colors against the hardware resources used by each of the register names in n's class. If the intersection is the empty bit vector, that register name is an available color for n. In the case of registers AX and EAX, the actual register name returned is the one whose bit size matches the bit size of the register candidate. SUMMARY [0022] Colors in accordance with the invention are arranged in prioritized order, to form a number of sequences. Each sequence is associated with one or more attributes (e.g. size and/or type) of variables whose nodes in an interference graph can be colored by colors in the sequence. In an example, there are a total of three groups, a first group to hold colors suitable for 8 bit variables, a second group to hold colors suitable for 16 bit variables, and a third group to hold colors suitable for variables that are pointers to memory. [0023] In addition to the above-described grouping, colors within a group are arranged in prioritized order to form a sequence. The specific prioritization that is used may depend on, for example, an attribute (such as size) and also on a predetermined preference. One example of such a predetermined preference is that colors that represents registers of smaller size are to be prioritized before colors that represent registers of bigger size (e.g. colors are prioritized in ascending order, based on the size of registers that they represent). Continue reading about Use of different color sequences for variables of different sizes and different semantics... Full patent description for Use of different color sequences for variables of different sizes and different semantics Brief Patent Description - Full Patent Description - Patent Application Claims Click on the above for other options relating to this Use of different color sequences for variables of different sizes and different semantics patent application. ###  How KEYWORD MONITOR works... a FREE service from FreshPatents1. Sign up (takes 30 seconds). 2. Fill in the keywords to be monitored. 3. Each week you receive an email with patent applications related to your keywords. Start now! - Receive info on patent apps like Use of different color sequences for variables of different sizes and different semantics or other areas of interest. ### Previous Patent Application: Summarizing application performance in a large system from a components perspective Next Patent Application: Computing platform having transparent access to resources of a host platform Industry Class: Data processing: software development, installation, and management ### FreshPatents.com Support Thank you for viewing the Use of different color sequences for variables of different sizes and different semantics patent info. IP-related news and info Results in 0.09397 seconds Other interesting Feshpatents.com categories: Qualcomm , Schering-Plough , Schlumberger , Seagate , Siemens , Texas Instruments , 174 |
 * Protect your Inventions * US Patent Office filing 
PATENT INFO |
|
