Method for resolving arbitrarily complex expressions at link-time

• US 6,314,564 B1
• Filed: 11/17/1997
• Issued: 11/06/2001
• Est. Priority Date: 11/17/1997
• Status: Expired due to Term

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Agere Systems Guardian Corp. (Broadcom, Inc.)
• Inventors: Williams, Gerald S., Charles, David K.
• Primary Examiner(s): Powell, Mark R.
• Assistant Examiner(s): NGUYEN BA, HOANG VU A
• Application Number:
  US08/968,156
• Time in Patent Office: 1,450 Days
• Field of Search: 395/710, 395/709, 395/575, 395/708, 395/717
• US Class Current: 717/162
• CPC Class Codes: G06F 9/44521 Dynamic linking or loading; Link editing at or after load time, e.g. Java class loading

Abstract

A method of resolving arbitrarily-complex expressions during the linking operation of an object file is disclosed. This is accomplished by including stack operations in the relocation entries of relocatable object files. By adding stack operations to the relocation entries, postfix notation (also known as “reverse Polish notation”) can be utilized to allow the resolution of the arbitrarily-complex expressions during the linking operation and within the object file itself.

Claims

1. A method of resolving an arbitrarily-complex expression before it is inserted into an executable object file, said executable object file having at least one instruction and/or data item requiring relocation, comprising the steps of:

generating a relocatable object file having at least two relocation entries;

inserting one or more stack operations into each said relocation entry;

processing said relocatable object file with a linker; and

outputting the result of said processing by said linker to said executable object file, wherein two or more of said relocation entries may be applied to a single instruction and/or data item.

2. A method as set forth in claim 1, wherein said stack operations are inserted in relocation entries of said relocatable object file.

3. A method as set forth in claim 1, wherein said stack operations comprise PUSH, POP, and EVALUATE operations.

4. A method as set forth in claim 1, wherein said stack operations comprise PUSH, PUSH IMMEDIATE, POP, and EVALUATE operations.

5. A method as set forth in claim 3, wherein said EVALUATE operations comprise UNARY, BINARY, and TRINARY EVALUATE operations.

6. A method as set forth in claim 4, wherein said EVALUATE operations comprise UNARY, BINARY, and TRINARY EVALUATE operations.

7. A method of resolving an arbitrarily-complex expression before it is inserted into an executable object file, said executable object file having at least one instruction and/or data file requiring relocation, comprising the steps of:

generating a relocatable object file having at least two relocation entries;

extending said relocation entries to include one or more stack operations;

resolving said arbitrarily-complex expression using said stack operations;

inserting the results of said resolved expression into said relocatable object file;

processing said relocatable object file with a linker; and

outputting the result of said processing by said linker to said executable object file, wherein two or more of said relocation entries may be applied to a single instruction and/or data item.

8. A method as set forth in claim 7, wherein said stack operations are inserted in relocation entries of said relocatable object file.

9. A method as set forth in claim 7, wherein said stack operations comprise PUSH, POP, and EVALUATE operations.

10. A method as set forth in claim 7, wherein said stack operations comprise PUSH, PUSH IMMEDIATE, POP, and EVALUATE operations.

11. A method as set forth in claim 9, wherein said EVALUATE operations comprise UNARY, BINARY, and TRINARY EVALUATE operations.

12. A method as set forth in claim 10, wherein said EVALUATE operations comprise UNARY, BINARY, and TRINARY EVALUATE operations.

13. In a software system, a method of resolving an arbitrarily-complex operation before it is inserted into an executable object file, said executable object file having at least one instruction and/or item file requiring relocation, comprising the steps of:

generating a relocatable object file having at least one relocation entry;

extending said relocation entries to include one or more stack operations;

reading said extended relocation entries;

calculating a new value of the relocation entries using said stack operations;

inserting said new value into said relocatable object file;

processing said relocatable object file with a linker; and

outputting the result of said processing by said linker to said executable object file, wherein two or more of said relocation entries may be applied to a single instruction and/or data item.

14. A method as set forth in claim 13, wherein said stack operations are inserted in relocation entries of said relocatable object file.

15. A method as set forth in claim 13, wherein said stack operations comprise PUSH, POP, and EVALUATE operations.

16. A method as set forth in claim 13, wherein said stack operations comprise PUSH, PUSH IMMEDIATE, POP, and EVALUATE operations.

17. A method as set forth in claim 15, wherein said EVALUATE operations comprise UNARY, BINARY, and TRINARY EVALUATE operations.

18. A method as set forth in claim 16, wherein said EVALUATE operations comprise UNARY, BINARY, and TRINARY EVALUATE operations.

19. A computer-implemented system for resolving arbitrarily-complex expressions in a relocatable object file at link-time, said system configured to perform the following steps:

extend the relocation entries of said relocatable object file to include stack operations;

resolve said arbitrarily-complex expressions using said stack operations; and

insert the results of said resolved expressions into said relocatable object file.

20. A system as set forth in claim 19, wherein said stack operations are inserted in relocation entries of said relocatable object file.

21. A system as set forth in claim 19, wherein said stack operations comprise PUSH, POP, and EVALUATE operations.

22. A system as set forth in claim 19, wherein said stack operations comprise PUSH, PUSH IMMEDIATE, POP, and EVALUATE operations.

23. A system as set forth in claim 21, wherein said EVALUATE operations comprise UNARY, BINARY, and TRINARY EVALUATE operations.

24. A system as set forth in claim 22, wherein said EVALUATE operations comprise UNARY, BINARY, and TRINARY EVALUATE operations.