Digital data processing system including efficient arrangement to support branching within trap shadows

Abstract

A digital computer includes an efficient mechanism by which an exception handler can traverse the instruction stream in a reverse direction to identify the instruction which gave rise to the exception condition after a discontinuity in an instruction stream. The digital computer is provided with both a program counter and an "old program counter." For points in an instruction sequence at which a discontinuity may occur, the "branch taken" portion of the instruction stream is provided with a predetermined type of instruction to enable the old program counter to be saved in a predetermined location. When the instruction is executed, the old program counter will contain a pointer to the "branch not taken" portion of the instruction sequence. When an exception condition is detected during processing of an "excepting" instruction, when an exception handler is called to locate the excepting instruction, when the exception handler performs a reverse traversal operation of the instruction sequence to locate the excepting instruction, if it encounters a read old program counter instruction (which can occur if there was a discontinuity in the instruction sequence), it can determine the location of the "branch not taken" portion of the instruction sequence by referencing the saved old program counter contents in the location identified by the read old program counter instruction.

What is claimed as new and desired to be secured by Letters Patent of the United States is: 
     
       1. A digital computer comprising: A. a plurality of storage locations, each identified by a storage location identifier, at least some of said storage locations being configured to store program code comprising a sequence of instructions to be executed by said digital computer, said instructions being stored in respective ones of said storage locations;   B. a program counter configured to store a current instruction storage location identifier identifying one of said storage locations containing one of said instructions currently being executed by said digital computer;   C. an old program counter configured to store a prior instruction storage location identifier identifying one of said storage locations containing one of said instructions executed by said digital computer prior to the one of the instructions currently being executed by said digital computer; and   D. an execution control element configured to control execution of said instructions, said execution control element including: i. a program counter control configured to control the current instruction storage location identifier in said program counter and said prior instruction storage location identifier in said old program counter as it executes said instructions in said series; and   ii. a read old program counter instruction type execution control configured to control execution of an instruction of a read old program counter instruction type by copying the prior instruction storage location identifier from the old program counter to the one of said storage locations identified by the instruction of the read old program counter instruction type.     
     
     
       2. A digital computer as defined in claim 1 in which said instruction of said read old program counter instruction type comprises an operation code identifying the instruction as being of the read old program counter instruction type and a destination identifier identifying one of said storage locations to which the prior instruction storage location identifier is to be copied. 
     
     
       3. A digital computer as defined in claim 1 in which said old program counter comprises a selected one of said storage locations. 
     
     
       4. A digital computer as defined in claim 3 in which said program counter control is configured to, when the execution control element enables execution of each respective one of said instructions, copy the instruction storage location identifier from the program counter to the selected one of said storage locations and modify the current instruction storage location identifier to point to the one of said storage locations containing the respective one of said instructions. 
     
     
       5. A digital computer as defined in claim 1 in which said program counter control is configured to, when the execution control element enables execution of each respective one of said instructions, copy the instruction storage location identifier from the program counter to the old program counter and modify the current instruction storage location identifier to point to the one of said storage locations containing the respective one of said instructions. 
     
     
       6. A digital computer as defined in claim 1 in which said program counter control is configured to control said prior instruction storage location identifier in said old program counter to point to the storage location which stores the instruction in said series executed immediately prior to the instruction currently being executed by the digital computer. 
     
     
       7. A digital computer as defined in claim 6 in which said program counter control is configured to, when the execution control initiates execution of an instruction in said series, copy the current storage location identifier from the program counter to the old program counter as the prior instruction storage location identifier, and increment the current instruction storage location identifier to point to the instruction to be executed as the one of said instructions currently being executed by said digital computer. 
     
     
       8. A digital computer as defined in claim 1 further comprising an exception handler configured to handle at least one exception condition in connection with execution of at least one of said instructions. 
     
     
       9. A digital computer as defined in claim 8 in which said exception handler comprises an instruction locator configured to locate one of said instructions in said series which gave rise to an exception condition, said instruction locator being further configured to process successive instructions in a reverse traversal operation in connection with said series of instruction from the instruction in the one of said storage locations identified by the program counter when the exception condition is detected, said instruction locator during said reverse traversal operation being responsive to an instruction of the read old program counter instruction type to continue the reverse traversal operation from the instruction in the one of said storage locations identified by the contents of the storage location identified by the destination identifier of the instruction of the read old program counter instruction. 
     
     
       10. A digital computer as defined in claim 9 in which said instruction locator comprises: A. a storage location counter configured to point to one of said storage locations, the storage location counter being initialized to point to one of said storage locations containing an instruction being executed when an exception condition is detected;   B. an excepting instruction detector configured to determine whether the instruction in the storage location pointed to by the storage location counter gave rise to an exception condition; and   C. a storage location counter control configured to control the storage location counter if the excepting instruction detector determines that the instruction in the storage location pointed to by the storage location counter did not give rise to the exception condition, the storage location counter control determining whether the instruction in the storage location pointed to by the storage location counter is an instruction of the read old instruction counter type and if so copying contents from said one of said storage locations identified by the instruction of the read old instruction type to the storage location counter, and otherwise controlling the storage location counter to point to the storage location containing the preceding instruction in the sequence.   
     
     
       11. An excepting instruction locator for use in connection with an exception handler in a digital computer, the digital computer having a plurality of storage locations each identified by a storage location identifier, at least some of said storage locations storing program code comprising a sequence of instructions to be executed by said digital computer, said instructions being stored in respective ones of said storage locations, said instruction locator being configured to locate one of said instructions which gives rise to an exception condition, the instruction locator comprising: A. a storage location counter configured to point to one of said storage locations, the storage location counter being initialized to point to one of said storage locations containing an instruction being executed when an exception condition is detected;   B. an excepting instruction detector configured to determine whether the instruction in the storage location pointed to by the storage location counter gave rise to an exception condition; and   C. a storage location counter control configured to control the storage location counter if the excepting instruction detector determines that the instruction in the storage location pointed to by the storage location counter did not give rise to the exception condition, the storage location counter control being configured to determine whether the instruction in the storage location pointed to by the storage location counter is an instruction of a read old instruction counter instruction type and if so to copy contents from said one of said storage locations identified by the instruction of the read old instruction type to the storage location counter, and otherwise to control the storage location counter to point to the storage location containing the preceding instruction in the sequence.   
     
     
       12. A method of controlling operations of a digital computer comprising: i. a plurality of storage locations, each identified by a storage location identifier, at least some of said storage locations storing program code comprising a sequence of instructions to be executed by said digital computer, said instructions being stored in respective ones of said storage locations;   ii. a program counter for storing a current instruction storage location identifier identifying one of said storage locations containing one of said instructions currently being executed by said digital computer; and   ii. an old program counter for storing a prior instruction storage location identifier identifying one of said storage locations containing one of said instructions executed by said digital computer prior to the one of the instructions currently being executed by said digital computer; the method including the steps of:   A. controlling the current instruction storage location identifier in said program counter and said prior instruction storage location identifier in said old program counter as the digital computer executes said instructions in said series; and   B. controlling execution an instruction of a read old program counter instruction type by copying the prior instruction storage location identifier from the old program counter to the one of said storage locations identified by the instruction of the read old program counter instruction type.     
     
     
       13. A method as defined in claim 12 in which said instruction of said read old program counter instruction type comprises an operation code identifying the instruction as being of the read old program counter instruction type and a destination identifier identifying one of said storage locations to which the prior instruction storage location identifier is to be copied. 
     
     
       14. A method as defined in claim 12 in which said old program counter comprises a selected one of said storage locations. 
     
     
       15. A method as defined in claim 14 in which the current instruction storage location identifier control step includes the steps of copying the instruction storage location identifier from the program counter to the selected one of said storage locations and modifying the current instruction storage location identifier to point to the one of said storage locations containing the respective one of said instructions. 
     
     
       16. A method as defined in claim 12 in which the current instruction storage location identifier control step includes the steps of copying the instruction storage location identifier from the program counter to the old program counter and modifying the current instruction storage location identifier to point to the one of said storage locations containing the respective one of said instructions. 
     
     
       17. A method as defined in claim 12 in which said current instruction storage location identifier control step includes the step of controlling said prior instruction storage location identifier in said old program counter to point to the storage location which stores the instruction in said series executed immediately prior to the instruction currently being executed by the digital computer. 
     
     
       18. A method as defined in claim 17 in which the current instruction storage location identifier control step includes the step of copying the current storage location identifier from the program counter to the old program counter as the prior instruction storage location identifier, and incrementing the current instruction storage location identifier to point to the instruction to be executed as the one of said instructions currently being executed by said digital computer. 
     
     
       19. A method as defined in claim 12 further comprising the step of handling at least one exception condition in connection with execution of at least one of said instructions. 
     
     
       20. A method as defined in claim 19 in which said exception condition handling step includes the step of locating one of said instructions in said series which gave rise to an exception condition, said excepting instruction locating step including the step of processing successive instructions in a reverse traversal operation in connection with said series of instructions from the instruction in the one of said storage locations identified by the program counter when the exception condition is detected, during said reverse traversal operation being responsive to an instruction of the read old program counter instruction type to continue the reverse traversal operation from the instruction in the one of said storage locations identified by the contents of the storage location identified by the destination identifier of the instruction of the read old program counter instruction. 
     
     
       21. A method as defined in claim 20 in which said excepting instruction locating step includes the steps of; A. establishing a storage location counter for pointing to one of said storage locations, the storage location counter being initialized to point to one of said storage locations containing an instruction being executed when an exception condition is detected;   B. determining whether the instruction in the storage location pointed to by the storage location counter gave rise to an exception condition; and   C. controlling the storage location counter if the instruction in the storage location pointed to by the storage location counter did not give rise to the exception condition by determining whether the instruction in the storage location pointed to by the storage location counter is an instruction of the read old instruction counter type and if so copying contents from said one of said storage locations identified by the instruction of the read old instruction type to the storage location counter, and otherwise controlling the storage location counter to point to the storage location containing the preceding instruction in the sequence.   
     
     
       22. A method of locating an instruction which gives rise to an exception condition in a digital computer, the digital computer having a plurality of storage locations each identified by a storage location identifier, at least some of said storage locations storing program code comprising a sequence of instructions to be executed by said digital computer, said instructions being stored in respective ones of said storage locations, the method comprising the steps of: A. establishing a storage location counter for pointing to one of said storage locations, the storage location counter being initialized to point to one of said storage locations containing an instruction being executed when an exception condition is detected;   B. determining whether the instruction in the storage location pointed to by the storage location counter gave rise to an exception condition; and   C. controlling the storage location counter if the instruction in the storage location pointed to by the storage location counter did not give rise to the exception condition by determining whether the instruction in the storage location pointed to by the storage location counter is an instruction of a read old instruction counter instruction type and if so copying contents from said one of said storage locations identified by the instruction of the read old instruction type to the storage location counter, and otherwise controlling the storage location counter to point to the storage location containing the preceding instruction in the sequence.   
     
     
       23. A computer program product for controlling a digital computer, the digital computer comprising: i. a plurality of storage locations, each identified by a storage location identifier, at least some of said storage locations storing program code comprising a sequence of instructions to be executed by said digital computer, said instructions being stored in respective ones of said storage locations;   ii. a program counter for storing a current instruction storage location identifier identifying one of said storage locations containing one of said instructions currently being executed by said digital computer; and   ii. an old program counter for storing a prior instruction storage location identifier identifying one of said storage locations containing one of said instructions executed by said digital computer prior to the one of the instructions currently being executed by said digital computer; the computer program product comprising a computer-readable medium having encoded thereon:   A. a program counter control module configured to enable the computer to control the current instruction storage location identifier in said program counter and said prior instruction storage location identifier in said old program counter as it executes said instructions in said series; and   B. a read old program counter instruction type execution control module configured to enable the computer to control execution an instruction of a read old program counter instruction type by copying the prior instruction storage location identifier from the old program counter to the one of said storage locations identified by the instruction of the read old program counter instruction type.     
     
     
       24. A computer program product as defined in claim 23 in which said instruction of said read old program counter instruction type comprises an operation code identifying the instruction as being of the read old program counter instruction type and a destination identifier identifying one of said storage locations to which the prior instruction storage location identifier is to be copied. 
     
     
       25. A computer program product as defined in claim 23 in which said old program counter comprises a selected one of said storage locations. 
     
     
       26. A computer program product as defined in claim 25 in which said program counter control module is configured to enable said computer to copy the instruction storage location identifier from the program counter to the selected one of said storage locations and modify the current instruction storage location identifier to point to the one of said storage locations containing the respective one of said instructions. 
     
     
       27. A computer program product as defined in claim 23 in which, when the program counter control module is configured to enable the computer to copy the instruction storage location identifier from the program counter to the old program counter and modify the current instruction storage location identifier to point to the one of said storage locations containing the respective one of said instructions. 
     
     
       28. A computer program product as defined in claim 23 in which said program counter control module is configured to enable said computer to control said prior instruction storage location identifier in said old program counter to point to the storage location which stores the instruction in said series executed immediately prior to the instruction currently being executed by the computer. 
     
     
       29. A computer program product as defined in claim 28 in which the program counter control is configured to enable the computer to copy the current storage location identifier from the program counter to the old program counter as the prior instruction storage location identifier, and increment the current instruction storage location identifier to point to the instruction to be executed as the one of said instructions currently being executed by said digital computer. 
     
     
       30. A computer program product as defined in claim 23 further comprising an exception handler module configured to enable the computer to handle at least one exception condition in connection with execution of at least one of said instructions. 
     
     
       31. A computer program product as defined in claim 30 in which said exception handler module comprises an instruction locator module configured to enable said computer to locate one of said instructions in said series which gave rise to an exception condition, said instruction locator module being configured to enable the computer to process successive instructions in a reverse traversal operation in connection with said series of instruction from the instruction in the one of said storage locations identified by the program counter when the exception condition is detected, said instruction locator module being configured to enable the computer during said reverse traversal operation to respond to an instruction of the read old program counter instruction type by continuing the reverse traversal operation from the instruction in the one of said storage locations identified by the contents of the storage location identified by the destination identifier of the instruction of the read old program counter instruction. 
     
     
       32. A computer program product as defined in claim 31 in which said instruction locator module comprises: A. a storage location counter module configured to enable the computer to establish a storage location counter for pointing to one of said storage locations, the storage location counter being initialized to point to one of said storage locations containing an instruction being executed when an exception condition is detected;   B. an excepting instruction detector module configured to enable the computer to determine whether the instruction in the storage location pointed to by the storage location counter gave rise to an exception condition; and   C. a storage location counter control module configured to enable the computer to control the storage location counter if the instruction in the storage location pointed to by the storage location counter did not give rise to the exception condition, the storage location counter control module being configured to enable the computer to determine whether the instruction in the storage location pointed to by the storage location counter is an instruction of the read old instruction counter type and if so copy contents from said one of said storage locations identified by the instruction of the read old instruction type to the storage location counter, and otherwise control the storage location counter to point to the storage location containing the preceding instruction in the sequence.   
     
     
       33. A computer program product for use in connection with a digital computer to provide an excepting instruction locator, the computer having a plurality of storage locations each identified by a storage location identifier, at least some of said storage locations storing program code comprising a sequence of instructions to be executed by said digital computer, said instructions being stored in respective ones of said storage locations, the excepting instruction locator locating one of said instructions which gives rise to an exception condition, the computer program product comprising a computer-readable medium having encoded thereon: A. a storage location counter module configured to enable the computer to establish a storage location counter for pointing to one of said storage locations, the storage location counter being initialized to point to one of said storage locations containing an instruction being executed when an exception condition is detected;   B. an excepting instruction detector module configured to enable the computer to determine whether the instruction in the storage location pointed to by the storage location counter gave rise to an exception condition; and   C. a storage location counter control module configured to enable the computer to control the storage location counter if the instruction in the storage location pointed to by the storage location counter did not give rise to the exception condition, the storage location counter control module being configured to enable the computer to determine whether the instruction in the storage location pointed to by the storage location counter is an instruction of the read old instruction counter instruction type and if so copy contents from said one of said storage locations identified by the instruction of the read old instruction type to the storage location counter, and otherwise control the storage location counter to point to the storage location containing the preceding instruction in the sequence.