Use of run-time code generation to create speculation recovery code in a computer system5854928Abstract In a computer system, programming code includes speculative code. The speculative code is code which is executed early based on speculation that the results from execution of the speculative code will be needed in the future. When executing instructions within a speculative sequence of code which includes memory accesses, any memory faults are ignored. When utilizing data generated during the speculative sequence of code a determination is made as to whether any memory fault occurred when the speculative sequence of code was executed. If it is determined that a memory fault occurred when the speculative sequence of code was executed, recovery code is generated which when executed performs a recovery from the memory fault. Claims I claim: Description BACKGROUND
TABLE 1
______________________________________
if((a/b) > 3.2) {
c = *d + 1;
}
______________________________________
In the example of code shown in Table 1, the variables "a" and "b" are floating point numbers, the variable "c" is an integer and the variable "*d" is the integer pointed to by the pointer "d". The statement "c=*d+1" needs to be executed if the condition clause ((a/b)>3.2) is true. Normally, compiler 92 will generate code such that the condition clause ((a/b)>3.2) is computed and then the following statement "c=*d+1" is executed only if the condition clause ((a/b)>3.2) is true. However, many modern computers have multiple arithmetic functional units which can operate in parallel. In such computers, it can speed execution of code such as that set out in Table 1 above, to perform a portion of the statement "c=*d+1" prior to or in parallel with the condition clause ((a/b)>3.2). In order, to facilitate such parallel execution, optimizer 94 reorders the example of code in Table 1, for example, to look like the code in Table 2 below.
TABLE 2
______________________________________
temp = *d + 1; ›speculatively executed code!
if((a/b) > 3.2) {
c = temp;
______________________________________
In the example of code shown in Table 2, the statement "c=temp" is executed if the condition clause ((a/b)>3.2) is true. If the condition clause ((a/b)>3.2) is false, the speculatively executed result (*d+1) stored in "temp" is simply not used and is effectively discarded. The simple re-ordering of code in Table 2 below can present a problem. Specifically, a requirement of speculation is that speculatively executed code does not introduce any externally visible behavior different from an unspeculated version. In the code set out in Table 2, if the pointer "d" is invalid, de-referencing pointer "d" (i.e., using pointer "d" to access the integer "*d") will cause a memory fault. This memory fault will occur when the code in Table 2 is executed. However, when executing the code in Table 1, if the condition clause ((a/b)>3.2) is always false, the pointer "d" is never de-referenced and the memory fault will never be exposed. Because executing the code in Table 2 may result in handling a memory fault which might not be detected when executing the code in Table 1, the executing the speculative code in Table 2 may introduce externally visible behavior different from the unspeculated version of the code in Table 1. A solution to the above problem is to architecturally define a mechanism for delaying faults on speculatively executed memory references until it is assured that the speculatively executed code is truly needed. When the speculatively executed code is truly needed, then there can be memory references without fear of incorrectly exposing a memory fault. This is illustrated by assembly language code set out in Table 3 and Table 4 below. Table 3 sets out an assembly language version of the code set out in Table 1 above. The code in Table 3 is in assembly language used for Precision Architecture (PA) 1.1. Further information about Precision Architecture is available from Hewlett-Packard Company.
TABLE 3
______________________________________
//** if((a/b) > 3.2) {**//
FDW a,b,ftemp ; divide a by b
FCMP, > ftemp,3,2
;compare to 3.2
B,n out ; Conditional branch around
; clause
//** c = *d + 1 **//
LDW 0 (d), temp ; De-reference d
ADDI 1,temp,temp ; add 1 to *d
COPY temp,c ; Place incremented value in c
out:
______________________________________
Table 4 sets out speculative assembly code version of the assembly language set out in Table 3. In the speculative assembly code version set out in Table 4, faults on speculatively executed memory references are delayed until it is assured that the speculatively executed code is truly needed. When the speculatively executed code is determined to be needed, then any deferred memory faults are raised.
TABLE 4
______________________________________
//** temp = *d + 1 **//
LDW,speculative 0 (d), temp
; De-reference d using
; speculative version of
; LDW which will
; defer trapping
ADDI 1,temp,temp ; add 1 to *d
//** if((a/b) > 3.2) {**//
FDIV a,b,ftemp ; divide a by b
FCMP, > ftemp,3,2 ; compare to 3.2
B,n out ; Conditional branch
; around clause
//** c = temp **//
CHECK 0 (d), temp ; Check validity of d to
; see if it is necessary to
; trap, and if so trap
COPY temp,c ; Place incremented
; value in c
out:
______________________________________
The code in Table 4 introduces speculative code. When code within the speculative code makes a memory reference, there is no memory fault until a decision is made that the speculative code would have been executed in code which does not include speculation. In the code in Table 4, there are two new instructions: "LDW,speculative" and "CHECK". "LDW,speculative" is similar in function to LDW used in the code in Table 3, with the exception that "LDW,speculative" will not raise any memory faults. Further, if a memory fault would have been raised when executing the "LDW,speculative", the value loaded in the target register is undefined. The instruction "CHECK" is similar in function to LDW used in the code in Table 3, except that "CHECK" only checks to see if a memory fault would have occurred when the LDW would have executed. If a memory fault would have occurred when the LDW would have executed, CHECK performs the trapping which would normally have occurred during the execution of LDW. In most modern computer architectures, a program can recover from a memory fault by fixing the problem which caused the fault. This is done by redoing the memory reference instruction and then continuing with execution. This presents a real problem when, as discussed above, speculation has resulted in the delay in handling the memory fault. This is because as a result of not detecting the memory fault, a "garbage" value can be loaded when executing a speculative instruction which accesses memory with an invalid pointer. For example, for the code given in Table 4 above, suppose the pointer "d" contains an invalid pointer. If so, any data referenced using pointer "d" will be a garbage value. If this garbage value is used by other instructions, the results of these other operations also will be corrupted. When the memory fault is detected, it will be necessary to recalculate any corrupted values which were tainted by use of the garbage value. The annotations in Table 5 below illustrate what happens when an invalid pointer is used within speculative code.
TABLE 5
______________________________________
//** temp = *d + 1 **//
LDW,speculative 0 (d), temp
; De-reference d using
; speculative
; version of LDW which will
; defer trapping
## Since the pointer "d" is invalid, normally the LDW
command would have resulted in a memory fault.
However, since an LDW, speculative command is used,
the memory fault and associated trap is deferred.
ADDI 1,temp,temp ; add 1 to *d
## the value "d" is incremented; however, since the
pointer "d" is invalid, *d is a garbage value, and the
result of the incrementation is also a garbage value.
//** if((a/b) > 3.2) {**//
FDIV a,b,ftemp ; divide a by b
FCMP, > ftemp,3,2 ; compare to 3.2
B,n out ; Conditional branch around
; clause
//** c = temp **//
CHECK0(d),temp ; Check validity of d to see if
; it is necessary to trap, and
; if so trap
## At the CHECK instruction, it is recognized that pointer
"d" is a bad value, and a trap occurs. The trap handler
desires to correct pointer "d" to be a good pointer and to
redo the operation. If speculation had not been done, the
trap handler could make the corrections and then load
the value "*d" into "temp". However, in this case where
speculation has occurred, the incrementation has
already occurred, and without some sort of recovery, the
incrementation will not be reflected in the value loaded
into c and thus the code will not operate properly.
COPY temp,c ; Place incremented value
; in c
out:
______________________________________
One solution to the problem described in the annotation to the code in Table 5 of how to recover from memory fault in speculated code is to generate, by optimizer 94, speculation recovery code which can be utilized when memory faults occur in code which is executed speculatively. For example, speculative recovery code for the code set out in Table 5 is the line of code set out in Table 6 below:
TABLE 6
______________________________________
ADDI 1,temp,temp
______________________________________
Thus the recovery code re-performs any operations which were done using a "garbage" value created by the speculative memory reference prior to discovery of a memory fault when the operation "CHECK" is performed. One problem with this solution is that recovery code can be expensive in terms of space. Optimizer 94 would like to utilize many speculative operations, but the recovery code can take up a significant amount of space in the executable file. This represents an inefficient use of space since generally it is extremely rare for a program to need to perform the kind of memory fault recovery described above. In the preferred embodiment of the present invention, optimizer 94 does not generate any speculative recovery code. Rather, dynamic translator 100 generates any needed speculative recovery code at run time. This speculative recovery code then becomes part of translated code 101 and can be stored in translated code cache 20. In order to generate the speculative recovery code, dynamic translator 100 essentially creates translated code which re-performs any operations which were executed using a "garbage" value created by the speculative memory reference prior to discovery of a memory fault. FIG. 2 is a flowchart which illustrates how dynamic translator 100 analyzes object code within application executable code 41 and generates recovery code sequences. The flowchart applies when a user wishes to recover from a deferred trap. In a step 61, various initializations are performed. A variable SPEC.sub.-- LOAD.sub.-- PC is set to the address of the speculated memory reference instruction associated with the deferred trap. The variable CHECK.sub.-- PC is set to the address of instruction which caused the deferred trap to be expressed. The variable CURRENT.sub.-- PC is set to the current value of the variable SPEC.sub.-- LOAD.sub.-- PC. The variable TARGET REGISTER is set to the target register of the instruction at SPEC.sub.-- LOAD.sub.-- PC. TOUCHED.sub.-- LIST is created and initialized as a NULL list of registers. TARGET.sub.-- REGISTER is then added to TOUCHED.sub.-- LIST. INSTRUCTION.sub.-- LIST is created and initialized as a NULL list of instruction addresses. CURRENT.sub.-- PC is then incremented to point to the instruction following CURRENT.sub.-- PC. In a step 62, the instruction at CURRENT.sub.-- PC is examined and a list of all of its source registers (CURRENT.sub.-- SOURCES) and all of its target registers (CURRENT.sub.-- TARGETS) is created. In a step 63, a determination is made as to whether any of CURRENT.sub.-- SOURCES are contained within TOUCHED.sub.-- LIST. If so, in a step 64, then CURRENT.sub.-- TARGETS is added to TOUCHED.sub.-- LIST and CURRENT.sub.-- PC is added to INSTRUCTION.sub.-- LIST. If in step 63 none of CURRENT.sub.-- SOURCES are contained within TOUCHED.sub.-- LIST, step 64 is skipped. In a step 65, CURRENT.sub.-- PC is incremented to point to the instruction following CURRENT.sub.-- PC. In a step 66, a determination is made as to whether CURRENT.sub.-- PC is equal to CHECK.sub.-- PC. If not, steps 62 through 66 are repeated. If in step 66 CURRENT.sub.-- PC is equal to CHECK.sub.-- PC, then in a step 67, a recovery code sequence is created by copying all instructions identified in INSTRUCTION.sub.-- LIST. Table 7 below sets out pseudo-code which implements the flowchart set out in FIG. 2 and thus further illustrates how dynamic translator 100 analyzes object code within application executable code 41 and generates recovery code sequences.
TABLE 7
______________________________________
if (user wishes to recover from deferred trap) {
set SPEC.sub.-- LOAD.sub.-- PC to address of speculated memory
reference instruction associated with the deferred trap
set CHECK.sub.-- PC to address of instruction which caused the
deferred trap to be expressed
set CURRENT.sub.-- PC to SPEC.sub.-- LOAD.sub.-- PC
examine the instruction at SPEC.sub.-- LOAD.sub.-- PC and set
TARGET.sub.-- REGISTER to its target register
create a NULL list of registers named TOUCHED.sub.-- LIST
add TARGET.sub.-- REGISTER to TOUCHED.sub.-- LIST
create a NULL list of instruction addresses named
INSTRUCTION.sub.-- LIST
set CURRENT.sub.-- PC to the instruction following
CURRENT.sub.-- PC
set DONE = FALSE
while (not DONE) do {
examine instruction at CURRENT.sub.-- PC and create a list
of all of its source registers (CURRENT.sub.-- SOURCES)
and all of its target registers (CURRENT.sub.-- TARGETS)
if any of CURRENT.sub.-- SOURCES are contained within
TOUCHED.sub.-- LIST then
add CURRENT.sub.-- TARGETS to TOUCHED.sub.-- LIST and
add CURRENT.sub.-- PC to INSTRUCTION.sub.-- LIST
set CURRENT.sub.-- PC to the instruction following
CURRENT.sub.-- PC
if CURRENT.sub.-- PC is equal to CHECK.sub.-- PC then set DONE
to true
create recovery code sequence by copying all instructions
identified in INSTRUCTION.sub.-- LIST
}
______________________________________
In some cases, particularly when control flow makes it ambiguous which instruction follows CURRENT.sub.-- PC, supplemental information is supplied, for example by optimizer 94 in the form of code annotations. These code annotations are utilized by dynamic translator 100 when analyzing control flow. In another alternative embodiment of the present invention, optimizer 94 generates a compact representation of the necessary recovery code. This compact representation of the recovery code is either interpreted when needed, or used as a template for recovery code generation. This embodiment may be used in conjunction with the use of dynamic translator 100 generating recovery code. The foregoing discussion discloses and describes merely exemplary methods and embodiments of the present invention. As will be understood by those familiar with the art, the invention may be embodied in other specific forms without departing from the spirit or essential characteristics thereof. Accordingly, the disclosure of the present invention is intended to be illustrative, but not limiting, of the scope of the invention, which is set forth in the following claims.
|
Same subclass Same class Consider this |
||||||||||