Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1999-02-17
2002-10-08
Khatri, Anil (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S145000, C717S151000
Reexamination Certificate
active
06463579
ABSTRACT:
FIELD OF THE INVENTION
The present invention is related to computer programming, and more particularly to the use of recovery code to recover from incorrect speculation.
BACKGROUND INFORMATION
Even as processor speeds increase into the gigahertz range, there is an increased realization that speed alone will not provide adequate performance. Designers are therefore turning to processor architectures which execute two or more instructions per clock cycle (IPC). Superscalar processors and very-long-instruction-word (or VLIW) processors are two examples of processors capable of executing two or more instructions per clock cycle.
Compilers can be designed to exploit efficiencies inherent in a processor having an IPC of greater than one. For instance, a compiler may search during compile time for instructions which can be executed in parallel and may even reorder instructions within the program to enhance parallel execution. Sometimes, the compiler may speculate as to a control path (control speculation) or a data value (data speculation). In these cases, the compiler should provide a way to recover from incorrect speculation.
One approach to recover from compiler-controlled speculation is to provide a recoverable interval of instructions in the object code (called “recovery code”) for the processor to execute in the case of failed speculation. This interval of instructions is essentially a copy of the thread of computation which was previously executed speculatively. This implies that the compiler must update the instructions in this recovery code as it speculates loads and their subsequent uses. The bookkeeping for this task is further complicated in that not all uses of a speculative load may execute speculatively. Adding recovery code also complicates optimization in that it adds control flow to the optimization scope. This may prove too difficult or expensive to update for many optimizations since dependence information is built atop control flow information.
One such recovery approach can be described as consisting of two phases. The first phase is during scheduling when a load is speculated. The successors of the load are visited in topological order computing a live-set of values which may be upwards exposed uses in the recoverable interval. These are those values that will be live into the recovery code for the load's recovery check. This is conservative in that it assumes that all uses of the speculative value will move above the check.
Such an approach can lead to poor performance. For instance, in the case of the following conservative line interval calculation:
ld.a r
32
=
chk.a r
32
,
ld r
34
=[a]
add r
33
=r
34
,r
32
the load of“r
32
” speculates and leaves a check behind. (In this example, “ld” is a load instruction, “ld.a” is a speculative load instruction and “chk.a” is a check on the speculative load instruction.) The successors of the load are visited and the live-set of the recovery interval is computed. In this case the “add r
33
=r
34
,r
32
” adds the value “r
34
” to the live-set of the check. Since “r
34
” is now live into the check, the “Id r
34
=[a]” can not move above the check because of a write-live dependence.
The second major phase involves generating the recovery for each check after instruction scheduling is completed. The speculative chains are identified and the flow dependencies are followed, adding instructions to the recovery code as each instruction is visited which topologically precedes the speculative load check. One major problem with generating recovery code in this manner is that it is difficult to combine control checks without effecting the schedule.
Another recovery code approach is described by William Yu-Wei Chen, Jr. in his Ph.D. thesis entitled
Data Preload for Superscalar and VLIW Processors
, University of Illinois at Urbana-Champaign, 1993. Chen teaches that a memory conflict buffer (or MCB) can be used to track and correct cases where a load from a memory location is moved above a store to the same location. In one approach, a conflict bit is associated with each general purpose register. At each preload, the location from which the preload is read is stored into an address register corresponding to the destination register of the preload. On a store, a comparison is made to the addresses stored in each of the address registers. If there is a match, the conflict bit corresponding to the general destination register is set. A subsequent check instruction notes the conflict bit and branches to the recovery code.
Neither of the approaches described above addresses the problem of handling recovery code coming to the instruction scheduler from other phases in the compiler. That is, if an earlier phase of compilation were to also exploit hardware based speculation and construct recovery code, the scheduler cannot simply reconstruct all recovery code from scratch (i.e. it must honor the recovery code which came to it). This can be complicated by the fact that an instruction scheduler's local analysis may not be able to determine the extent of a speculative lifetime and the relationships between subsequent uses. In other words, local analysis might not be aware of when a use of a speculative value is crossing a check that checks the use's operands. An example is shown below for a local lifetime analysis code fragment:
ld.a r
32
=
add r
33
=
1
,r
32
while (! change) do
ld r
34
=
chk.a r
32
, rec
1
xor r
35
=r
33
,r
34
od;
Since most instruction schedulers would not include the loop region and the region outside of the loop together, an instruction scheduler would only include the entire loop body as a single region at best. Because of this, it is difficult to know that the “xor” inside the loop is reading a speculative value that is being checked by the “chk.a r
32
” before it.
What is needed is a system and method for dynamically creating and updating control and data speculative recovery code during more than one phase of compilation, including the instruction scheduling phase.
SUMMARY OF THE INVENTION
According to one aspect of the present invention, a system and method of compiling source code is described which generates intermediate code from the source code, generates object code instructions from the intermediate code and schedules the object code instructions. Object code instructions are scheduled by inserting a speculation check into the object code instructions, storing recovery code associated with the speculation check and generating a control flow graph. The control flow graph is generated by converting the speculation check to a non-flow control check instruction, attaching one or more pseudo instructions to the check instruction and converting the non-flow control check instruction to a flow control check instruction, wherein the pseudo instructions represent recovery code behavior for the recovery code associated with the check instruction.
REFERENCES:
patent: 4667290 (1987-05-01), Goss et al.
patent: 5287510 (1994-02-01), Hall et al.
patent: 5613117 (1997-03-01), Davidson et al.
patent: 5655122 (1997-08-01), Wu
patent: 5692169 (1997-11-01), Kathail et al.
patent: 5701489 (1997-12-01), Bates et al.
patent: 5778219 (1998-07-01), Amerson et al.
patent: 5778233 (1998-07-01), Besaw et al.
patent: 5790867 (1998-08-01), Schmidt et al.
patent: 5854928 (1998-12-01), Buzbee
patent: 6070009 (2000-05-01), Dean et al.
patent: 6202204 (2001-03-01), Wu et al.
patent: 6338133 (2002-01-01), Schroter
patent: 98/000769 (1998-01-01), None
Data Preload for Superscalar and VLIW Processors, by William Yu-Wei Chen, Jr. Thesis for Doctor of Philosophy in Electrical Engineering, University of Illinois at Urbana-Champaign, 1993.*
Bharadwaj et al, “Wavefront scheduling path based data representation and scheduling of subgraph”, IEEE, pp. 262-271, 1999.*
Ranganthan et al, “Using speculative and larger instruction window to narrow the performance gap between memory consistency models”, ACM SPAA, pp 199-210.*
Rogers et al, “Software support
Intel Corporation
Khatri Anil
Schwegman Lundberg Woessner & Kluth P.A.
LandOfFree
System and method for generating recovery code does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for generating recovery code, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for generating recovery code will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2969552