High-performance pipelined central processor for predicting the occurrence of executing single-cycle instructions and multicycle instructions

Abstract

A pipelined central processor capable of executing both single-cycle instructions and multicycle instructions is provided. An instruction fetch stage of the processor includes an instruction cache memory and a prediction cache memory that are commonly addressed by a program counter register. The instruction cache memory stores instructions of a program being executed and microinstructions of a multicycle instruction interpreter. The prediction cache memory stores interpreter call predictions and interpreter entry addresses at the addresses of the multicycle intructions. When a call prediction occurs, the entry address of the instruction interpreter is loaded into the program counter register on the processing cycle immediately following the call prediction, and a return address is pushed onto a stack. The microinstructions of the interpreter are fetched sequentially from the instruction cache memory. When the interpreter is completed, the prediction cache memory makes a return prediction. The return address is transferred from the stack to the program counter register on the processing cycle immediately following the return prediction, and normal program flow is resumed. The prediction cache memory also stores branch instruction predictions and branch target addresses.

What is claimed is: 
     
       1. Digital processing apparatus for executing stored program instructions including single-cycle instructions and multicycle instructions during multiple processing cycles, comprising: instruction memory means for providing said program instructions in response to program addresses and for providing microinstructions of a multicycle instruction interpreter in response to microinstruction addresses;   prediction means responsive to different ones of said program addresses for making predictions of multicycle instructions and predictions of single cycle instructions, said predictions of multicycle instructions including predictions of calls to said instruction interpreter and predictions of returns from said instruction interpreter, said prediction means including a cache memory for storage and readout of said call predictions and instruction interpreter entry addresses respectively associated with each of said call predictions, each of said call predictions and said entry addresses being stored at an address corresponding to the program address for which the call prediction is made, and for storage and readout of each of said return predictions at an address corresponding to the microinstruction address for which the return prediction is made;   control means for providing successive program addresses to said instruction memory means for accessing said program instructions in response to predictions of single-cycle instructions and for providing successive microinstruction addresses to said instruction memory means in response to each prediction of a multicycle instruction until completion of the multicycle instruction interpreter, said control means including program counter means for holding a current address for accessing said instruction memory means on each processing cycle and for incrementing the current address on successive processing cycles,   stack memory means coupled to said program counter means,   control logic means responsive to each of said call predictions for loading a return program address from said program counter means into said stack memory means, and   selector means responsive to each of said call predictions for loading the entry address into said program counter means and responsive to each of said return predictions for transferring said return program address from said stack memory means to said program counter means;     means responsive to said program instructions and said microinstructions provided by said instruction memory means for executing said program instructions and said microinstructions; and   means for validating said predictions and for updating said prediction means when said predictions are incorrect.   
     
     
       2. Digital processing apparatus as defined in claim 1 wherein said prediction means comprises memory means that is addressed by said program addresses. 
     
     
       3. Digital processing apparatus as defined in claim 1 wherein said prediction means comprises a cache memory for storage and readout of each of said predictions at an address corresponding to the program address for which the prediction is made. 
     
     
       4. Digital processing apparatus as defined in claim 1 wherein said prediction means comprises a cache memory for storage and readout of each of said predictions and an associated entry address of said instruction interpreter at an address corresponding to the program address for which the prediction is made. 
     
     
       5. Digital processing apparatus as defined in claim 1 wherein said prediction means further includes means responsive to said program addresses for making predictions of branch instructions. 
     
     
       6. Digital processing apparatus as defined in claim 5 wherein said cache memory includes means for storage and readout of each of said branch instruction predictions and an associated branch instruction address at an address corresponding to the program address for which the branch prediction is made. 
     
     
       7. Digital processing appratus as defined in claim 6 wherein said prediction means includes means for making subroutine call predictions, subroutine return predictions and interpreter branch predictions within said interpreter. 
     
     
       8. Digital processing apparatus as defined in claim 7 wherein said cache memory includes a program section for storing interpreter call predictions and branch instruction predictions and an interpreter section for storing interpreter subroutine call predictions, interpreter subroutine return predictions, interpreter branch predictions and interpreter return predictions and wherein said control means includes means for providing an interpreter mode bit in said program addresses and said microinstruction addresses for selectively addressing said program section and said interpreter section of said cache memory. 
     
     
       9. Digital processing apparatus as defined in claim 1 wherein said control means includes means for providing microinstruction addresses starting on the processing cycle immediately after each of said predictions of multicycle instructions. 
     
     
       10. Digital processing apparatus as defined in claim 1 wherein said control means includes means for providing said entry address of said instruction interpreter to said instruction memory means on the processing cycle immediately after each of said call predictions. 
     
     
       11. Digital processing apparatus as defined in claim 1 wherein said prediction means further includes means responsive to said program addresses for making predictions of branch instructions. 
     
     
       12. Digital processing apparatus as defined in claim 11 wherein said cache memory includes means for storage and readout of said branch instruction predictions and branch instruction addresses respectively associated with each of said branch instruction predictions, each of said branch instruction predictions and said branch instruction addresses being stored at an address corresponding to the program address for which the branch instruction prediction is made. 
     
     
       13. Digital processing apparatus as defined in claim 12 wherein said selector means further includes means responsive to branch instruction predictions for loading said branch instruction address into said register means. 
     
     
       14. Digital processing apparatus as defined in claim 1 wherein said means for executing said program instructions includes means for decoding said program instructions and providing an operation code representative of the program instruction type and wherein said means for validating said predictions includes means for comparing each operation code with the associated prediction and providing an invalid prediction indicator when said prediction does not correspond to said operation code. 
     
     
       15. Digital processing apparatus as defined in claim 1 wherein said validating means includes means responsive to each of said program instructions for detecting a multicyle instruction on a processing cycle subsequent to the processing cycle on which said call prediction was made and providing a multicycle detected signal, and means for providing an invalid prediction indicator when said call prediction does not correspond to said multicycle detected signal. 
     
     
       16. In pipelined digital processor for executing a stored program including single-cycle instructions and multicycle instructions, instruction addressing apparatus comprising: control means for providing a program address during a first processing cycle;   prediction means responsive to said program address for predicting a multicycle instruction and making an instruction interpreter entry prediction during said first processing cycle, said prediction means including means responsive to microinstruction addresses for making a prediction of a return from said instruction interpreter, said prediction means including a cache memory for storage and readout of said entry prediction and said entry address at a cache memory address corresponding to the program address for which the entry prediction is made and for storage and readout of said return prediction at a cache memory address corresponding to the microinstruction address or which the return prediction is made;   said control means further including means responsive to said prediction for providing during a second processing cycle an entry address of an instruction interpreter comprising a plurality of microinstructions and for providing successive microinstruction addresses during processing cycles subsequent to said second processing cycle; and   instruction memory means responsive to said program address for providing said multicycle instruction during said second processing cycle, responsive to said entry address for providing a first microinstruction during a third processing cycle and responsive to said microinstruction addresses for providing microinstructions during processing cycles subsequent to said third processing cycle, said control means comprising program counter means for holding a current address for accessing said instruction memory means and for incrementing the current address on successive processing cycles,   stack memory means coupled to said program counter means,   control logic means responsive to said entry prediction for loading a return program address from said program counter means into said stack means, and   selector means responsive to said entry prediction for loading said entry address into said program counter means and responsive to said return prediction for transferring said return program address from said stack memory means to said program counter means.     
     
     
       17. Instruction addressing apparatus as defined in claim 16 wherein said control means includes means for providing said entry address to said instruction memory means on said second processing cycle immediately following said first processing cycle. 
     
     
       18. Digital processing apparatus for executing a stored program including single-cycle instructions and multicycle instructions during multiple processing cycles, comprising: instruction memory means responsive to program addresses for providing program instructions and responsive to microinstruction addresses for providing microinstructions of a multicycle instruction interpreter;   prediction memory means responsive to various ones of said program addresses corresponding to multicycle instructions for readout of instruction interpreter entry predictions and associated entry addresses and responsive to various ones of said microinstruction addresses for making predictions of returns from said instruction interpreter;   program counter means for holding a current address for accessing said instruction memory means and for incrementing the current address on successive processing cycles;   stacking memory means coupled to said program counter means,   control logic means responsive to each of said call predictions for loading a return program address from said program counter means into said stack memory means;   selector means responsive to each of said call predictions for loading the associated entry address into said program counter means and responsive to each of said return predictions for transferring said return program address from stack memory means to said program counter means,   means for executing said program instructions and said microinstructions; and   means for validating each of said predictions and for updating said prediction memory means when one of said predictions is incorrect, said prediction memory means including a program section for storing interpreter call predictions and branch instruction predictions and an interpreter section for storing interpreter subroutine call predictions, interpreter subroutine return predictions, interpreter branch predictions and interpreter return predictions and wherein said control logic means includes means for providing an interpreter mode bit in said program addresses and said microinstruction addresses for selectively addressing said program section and said interpreter section of said prediction memory means.   
     
     
       19. Digital processing apparatus as defined in claim 18 wherein said prediction memory means further includes means responsive to said program addresses for making predictions of branch instructions. 
     
     
       20. Digital processing apparatus as defined in claim 19 wherein said prediction memory means includes means for storage and readout of said branch instruction predictions and branch instruction addresses respectively associated with each of said branch instruction predictions, each of said branch instruction predictions and said branch instruction addresses being stored at an address corresponding to the program address for which the branch instruction prediction is made. 
     
     
       21. Digital processing apparatus as defined in claim 20 wherein said selector means further includes means responsive to branch instruction predictions for loading said branch instruction address into said register means. 
     
     
       22. Digital processing apparatus as defined in claim 18 wherein said control logic means includes means for providing said entry address of said instruction interpreter to said instruction memory means on the processing cycle immediately after each of said call predictions. 
     
     
       23. A method for executing stored program instructions including single-cycle instructions and multicycle instructions during multiple processing cycles comprising the steps of: storing program instructions and microinstructions of a multicycle instruction interpreter in an instruction memory;   providing successive program addresses to the instruction memory for accessing the program instructions;   making predictions of multicycle instructions based on the program addresses provided to the instruction memory, the step of making predictions of multicycle instructions including the steps of making call predictions for entering said instruction interpreter in response to multicycle instruction addresses, and making return predictions for returns from said instruction interpreter in response to specified microinstruction addresses, the step of making call predictions including the step of storing said call predictions in a cache memory at addresses corresponding to said multicycle instruction addresses and the step of making return predictions including the step of storing said return predictions in said cache memory at addresses corresponding to said specified microinstruction addresses;   interrupting the program addresses and providing successive microinstruction addresses to the instruction memory for accessing the microinstructions, in response to each prediction of a multicycle instruction; and   executing the program instructions and the microinstructions, the steps of storing program instructions and microinstructions, and executing the program instructions and the microinstruction being performed in separate stages of a pipelined digital processor.   
     
     
       24. A method for executing stored program instructions as defined in claim 23 wherein the step of providing successive microinstruction addresses includes the step of providing to said instruction memory an entry address of the instruction interpreter on the processing cycle immediately following each of said call predictions. 
     
     
       25. A method for executing storage program instructions as defined in claim 24 further including the step of providing a return address to said instruction memory on the processing cycle immediately following each of said return predictions. 
     
     
       26. A method for executing stored program instructions as defined in claim 25 further including the step of making predictions of branch instructions based on the program instructions provided to the instruction memory. 
     
     
       27. Digital processing apparatus for executing stored program instructions including single-cycle instructions and multicycle instructions during multiple processing cycles comprising: an instruction fetching stage comprising instruction memory means for providing said program instructions in response to program addresses and for providing microinstructions of a multicycle instruction interpreter in response to microinstruction addresses,   prediction means responsive to different ones of said program addresses for making predictions of multicycle instructions and predictions of single cycle instructions, said predictions of multicycle instructions including predictions of calls to said instruction interpreter and predictions of returns from said instruction interpreter, said prediction means including a cache memory for storage and readout of said call predictions and instruction interpreter entry addresses respectively associated with each of said call predictions, each of said call predictions and said entry addresses being stored at an address corresponding to the program address for which the call prediction is made, and for storage and readout of each of said return predictions at an address corresponding to the microinstruction address for which the return prediction is made, and   control means for providing successive program addresses to said instruction memory means for accessing said program instructions in response to predictions of single cycle instructions and for providing successive microinstruction addresses to said instruction memory means in response to each prediction of a multicycle instruction until completion of the multicycle instruction interpreter, said control means including program counter means for holding a current address for accessing said instruction memory means on each processing cycle and for incrementing the current address on successive processing cycles, stack memory means coupled to said program counter means, control logic means responsive to each of said call predictions for loading a return program address from said program counter means into said stack memory means, and selector means responsive to each of said call predictions for loading the entry address into said program counter means and responsive to each of said return predictions for transferring said return program address from said stack memory means to said program counter means;     an instruction decoder stage for decoding said single-cycle instructions, said multicycle instructions and said microinstructions;   an effective address formation stage responsive to outputs of said instruction decoder stage for determining addresses of operands referenced by said single-cycle instructions and said microinstructions;   an operand memory stage responsive to said operand addresses for providing operands referenced by said single-cycle instructions and said microinstructions;   an execute stage responsive to said operands provided by said operand memory stage and the outputs of said decoder stage for executing said single-cycle instructions and said microinstructions; and   a writer stage for storing the results of said execute stage.   
     
     
       28. Digital processing apparatus as defined in claim 27 further including means for validating said predictions and means for updating said prediction means when said predictions are incorrect. 
     
     
       29. Digital processing apparatus as defined in claim 28 wherein said validating means includes a program counter register associated with each of said stages, means for advancing said predictions through said program counter registers and means for comparing instruction types provided by said instruction decoder stage with the predictions in the associated program counter register.