US4961141A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Generating efficient code for a computer with dissimilar register spaces
Assignee: International Business Machines Corp
•
Filing: 1988-12-16
•
Granted: 1990-10-02
•
Expires: 2008-12-16
Abstract
Abstract A compiler generates compiled object code from source code of a computer program in a manner that produces efficient object code for a computer with dissimilar register spaces. The technique comprising the steps of (1) generating code that references symbolic registers in which the register class is not distinguished, (2) making entries in a table denoting the context in which each symbolic register occurs and constructing an equivalence tree of symbolic registers for move instructions assigned to a same equivalence class, (3) for each equivalence class, forming the logical OR function of register usage information for all symbolic registers in the class, and for each symbolic register that appears in more than one register space context, generating new symbolic register numbers so that there is one number for each register space, and storing the numbers in said table, and (4) if a definition point of a symbolic register is encountered and that symbolic register is used in more than one register space context, inserting code in said program to either do the same operation as is done at the definition point in each register space or move a value in the symbolic register from one space to another. The improvement achieved is in object code space and time of execution.
Inventors
- 👤 Martin E. Hopkins
- 👤 Henry S. Warren, Jr.
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 10:27
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/44; G06F8/441
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
214 words
In a compiler which generates compiled object code from source code of a computer program, a computer performed method of generating efficient object code for a computer with dissimilar register spaces comprising the steps of: generating by a computer code that references symbolic registers in which a register class is not distinguished; making entries in a table by the computer denoting a context in which each symbolic register occurs and constructing an equivalence tree of symbolic registers for move instructions assigned to a same equivalence class; for each equivalence class, forming by the computer a logical OR function of register usage information for all symbolic registers in the equivalence class, and for each symbolic register that appears in more than one register space context, generating by the computer new symbolic register numbers so that there is one number for each register space, and storing the new symbolic register numbers in said table; and if a definition point of a symbolic register is encountered and that symbolic register is used in more than one register space context, inserting by the computer code in said program to either do a same operation as is done at the definition point in each register space or move a value in the symbolic register from one space to another.
Claim 2
Dependent Claim
214 words
In a compiler which generates compiled object code from source code of a computer program, a computer performed method of generating efficient object code for a computer with dissimilar register spaces comprising the steps of: generating by a computer code that references symbolic registers in which a register class is not distinguished; making entries in a table by the computer denoting a context in which each symbolic register occurs and constructing an equivalence tree of symbolic registers for move instructions assigned to a same equivalence class; for each equivalence class, forming by the computer a logical OR function of register usage information for all symbolic registers in the equivalence class, and for each symbolic register that appears in more than one register space context, generating by the computer new symbolic register numbers so that there is one number for each register space, and storing the new symbolic register numbers in said table; and if a definition point of a symbolic register is encountered and that symbolic register is used in more than one register space context, inserting by the computer code in said program to either do a same operation as is done at the definition point in each register space or move a value in the symbolic register from one space to another.
Claim 3
Dependent Claim
57 words
The method of generating efficient object code for a computer as recited in claim 1 wherein said step of making entries in a table further comprises the step of checking by the computer each instruction to determine if it is a move register instruction, and if so, putting source and target registers in a same equivalence class.
Claim 4
Dependent Claim
55 words
The method of generating efficient object code for a computer as recited in claim 1 wherein said step of making entries in a table further comprises the step of checking by the computer each instruction to determine if it is a conditional branch instruction, and if so, noting a conditional register context for that register.
Claim 5
Dependent Claim
54 words
The method of generating efficient object code for a computer as recited in claim 1 wherein said step of making entries in a table further comprises the step of checking by the computer each instruction to determine if it is a compare instruction, and if so, noting a conditional register context for that register.
Claim 6
Dependent Claim
109 words
The method of generating efficient object code for a computer as recited in claim 1 wherein said step of making entries in a table further comprises the steps of: checking by the computer each instruction to determine if it is a move register instruction, and if so, putting source and target registers in a same equivalence class; checking by the computer each instruction to determine if it is a conditional branch instruction, and if so, noting a conditional register context for that register; and checking by the computer each instruction to determine if it is a compare instruction, and if so, noting a conditional register context for that register.
Claim 7
Dependent Claim
60 words
The method of generating efficient object code for a computer as recited in claim 5 wherein the step of making entries in a table further comprises the steps of: noting by the computer a floating point register context for all referenced floating point registers; and noting by the computer a general purpose register context for all referenced general purpose registers.
Claim 8
Dependent Claim
96 words
The method of generating efficient object code for a computer as recited in claim 6 wherein the steps of forming the logical OR function and generating new symbolic register numbers further comprise the steps of: testing by the computer each register to determine if it is assigned to an equivalence class, and if not, putting that register in a class by itself; and testing by the computer each register to determine if it appears in more than one context, and if so, making up new names so that there is a different one for each context.
Claim 9
Dependent Claim
59 words
The method of generating efficient object code for a computer as recited in claim 7 wherein said step of inserting code further comprises the step of checking by the computer each instruction to determine if it is a move register instruction, and if it is, inserting by the computer code to do the move instruction in that register space.
Claim 10
Dependent Claim
95 words
The method of generating efficient object code for a computer as recited in claim 7 wherein said step of inserting code further comprises the step of checking by the computer each target register to determine if that register appears in more than one context, and if so, determining by the computer if an operation can be done efficiently in alternate register spaces, and if so, inserting by the computer code to do the operation in the alternate register spaces, but otherwise, inserting by a computer code to move the result to the alternate register spaces.
Claim 11
Dependent Claim
66 words
The method of generating efficient object code for a computer as recited in claim 7 wherein said step of inserting code further comprises the steps of testing by the computer each source register to determine if it appears in more than one context, and if so, changing by the computer an register to a new name that is in the appropriate space for a corresponding operation.
Claim 12
Dependent Claim
169 words
The method of generating efficient object code for a computer as recited in claim 7 wherein said step of inserting code further comprises the steps of: checking by the computer each instruction to determine if it is a move register instruction, and if it is, inserting by the computer code to do the move instruction in that register space; checking by the computer each target register to determine if that register appears in more than one context, and if so, determining by the computer if an operation can be done efficiently in alternate register spaces, and if so, inserting by the computer code to do the operation in the alternate register spaces, but otherwise, inserting by the computer code to move the result to the alternate register spaces; and testing by the computer each source register to determine if it appears in more than one context, and if so, changing by the computer the register to a new name that is in an appropriate space for a corresponding operation.
References Cited (Backward Citations)
US4571678A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-10-01 | 1994-04-02 | 1994-10-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-10-01 | 1998-04-02 | 1998-10-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-10-01 | 2002-04-02 | 2002-10-02 | $7700.00 | Window Closed / Lapsed |