Floating point stack and exchange instruction

Claim 2

A processor for concurrently performing multiple operations, the operations being selected from an instruction set including floating point calculation instructions, floating point stack exchanges and instructions that push or pop a floating point stack, the processor comprising: an instruction decoder for decoding instructions in the instruction set including the floating point stack exchange instruction; a branch unit coupled to the instruction decoder for determining speculative execution of instructions in the instruction set, the branch unit for executing the floating point stack exchange instruction in accordance with the speculative execution; a floating point functional unit coupled to the instruction decoder for executing floating point calculation instructions; and a floating point stack coupled to the floating point functional unit including: a floating point stack array to store calculation results received from the floating point functional unit; a floating point stack pointer coupled to the floating point stack array to specify an array element; and a floating point stack remap array coupling the floating point stack pointer to the floating point stack array for reordering floating point stack array elements addressed by the stack pointer.

Claim 3

A processor as in claim 1 wherein the floating point stack is operable independent of the floating point functional unit so that floating point stack exchange instructions are executable concurrent with floating point calculations.

Claim 4

A processor as in claim 1 wherein the instruction set further includes a branch instruction, wherein the floating point stack further comprises: a lookahead remap array responsive to a floating point stack exchange instruction by exchanging array elements; and a lookahead stack pointer coupled to the lookahead remap array to specify an element of the floating point stack array and responsive to instructions that pop or push the floating point stack to adjust the pointer; wherein the branch unit is coupled to the lookahead remap array and the lookahead stack pointer, the branch unit further including: a memory to save the lookahead remap array responsive to a branch instruction, a branch predictor to predict whether the branch is taken or not taken; a branch comparator coupled to the branch predictor to determine whether the branch is predicted or mispredicted; first control lines coupled between the memory and the lookahead remap array, responsive to a mispredicted branch to communicate the saved values to the array; and second control lines coupling the lookahead remap array and stack pointer respectively to the floating point remap array and stack pointer, responsive to execution of a stack exchange instruction by respectively replacing floating point values with lookahead values.

Claim 5

A processor as in claim 1 wherein the floating point stack further includes: a floating point stack full/empty array coupled to the floating point remap array and designating whether a floating point stack element is empty or full, and a lookahead stack full/empty array coupled to the lookahead remap array to monitor a lookahead state of the floating point stack full/empty array.

Claim 10

A method as in claim 6, further comprising the steps of: setting and clearing an entry in a lookahead full/empty array responsive to instructions that push and pop the stack; and setting and clearing an entry in a lookahead full/empty array responsive to retiring of an instruction that pushes or pops the stack.

Claim 11

A method as in claim 7, further comprising the steps of: detecting a stack execution error including the steps of: determining whether all elements of the lookahead full/empty array are full; determining whether all elements of the lookahead full/empty array are empty; detecting a stack underflow error responsive to an instruction that pops the stack when all elements of the lookahead full/empty array are empty; and detecting a stack overflow error responsive to an instruction that pushes the stack when all elements of the lookahead full/empty array are full; and initiating a resynchronization response in response to a detected stack execution error.

Claim 12

A method as in claim 7, further comprising the steps of: detecting an exception condition; and copying the stack remap array to the lookahead stack remap array and copying the stack pointer to the lookahead stack pointer responsive to the detected exception condition.

Claim 13

A stack in a processor which performs an instruction set including stack exchange instructions and instructions that push or pop the stack, the stack comprising: an instruction decoder for decoding instructions in the instruction set including the stack exchange instruction; a branch unit coupled to the instruction decoder for determining speculative execution of instructions in the instruction set, the branch unit for executing the stack exchange instruction in accordance with the speculative execution; a stack memory array coupled to the instruction decoder and the branch unit; a stack pointer coupled to the stack memory array to designate a stack memory array element, the stack pointer being adjusted in response to instructions that push or pop the stack; and a stack remap array of pointers coupled to the stack pointer and coupled to the stack memory array to reorder stack array elements as they are addressed by the stack pointer, the pointers being exchanged in response to a stack exchange instruction.

Claim 14

A stack in a processor which performs an instruction set including stack exchange instructions and instructions that push or pop the stack, the stack comprising: an instruction decoder for decoding instructions in the instruction set including the stack exchange instruction; a branch unit coupled to the instruction decoder for determining speculative execution of instructions in the instruction set, the branch unit for executing the stack exchange instruction in accordance with the speculative execution; a stack memory array coupled to the instruction decoder and the branch unit; a stack pointer coupled to the stack memory array to designate a stack memory array element, the stack pointer being adjusted in response to instructions that push or pop the stack; and a stack remap array of pointers coupled to the stack pointer and coupled to the stack memory array to reorder stack array elements as they are addressed by the stack pointer, the pointers being exchanged in response to a stack exchange instruction.

Claim 15

A stack as in claim 10, further comprising: a stack full/empty array coupled to the stack remap array and addressed through the stack remap array by the stack pointer to reorder stack array elements as they are addressed by the stack pointer, the stack full/empty array elements being respectively set and cleared in response to instructions that push and pop the stack, indicating respective addition or elimination of stack array entries.

Claim 16

A stack in a processor which concurrently fetches, decodes, executes and retires a plurality of instructions of an instruction set including branch instructions, stack exchange instructions, instructions that push the stack and instructions that pop the stack, the processor including a branch unit having a branch predictor responsive to a conditional branch instruction to predict whether a branch is taken or not taken and having a branch tester coupled to the branch predictor to subsequently determine whether the conditional branch is predicted or mispredicted, the stack comprising: a stack memory array; a stack pointer coupled to the stack memory array to designate a stack memory array element, the stack pointer being adjusted in response to instructions that push or pop the stack; a stack remap array of pointers coupled to the stack pointer and coupled to the stack memory array to reorder stack array elements addressed by the stack pointer, the pointers being exchanged in response to a stack exchange instruction; a lookahead stack pointer designating a lookahead state of the stack pointer, the lookahead stack pointer being adjusted in response to instructions that push or pop the stack; a lookahead remap array coupled to the lookahead stack pointer to reorder stack array elements addressed by the stack pointer, the elements of the lookahead remap array being exchanged in response to a stack exchange instruction; a memory coupled to the branch unit and responsive to a stack exchange instruction to save the lookahead remap array; a memory coupled to the branch unit and responsive to instructions that push or pop the stack to save the lookahead stack pointer; means coupled to the branch tester and responsive to a mispredicted branch for restoring the lookahead remap array and the lookahead stack pointer to saved values; and means responsive to retiring of a stack exchange instruction for replacing the stack remap array with the lookahead remap array.

Claim 17

A stack in a processor which concurrently fetches, decodes, executes and retires a plurality of instructions of an instruction set including branch instructions, stack exchange instructions, instructions that push the stack and instructions that pop the stack, the processor including a branch unit having a branch predictor responsive to a conditional branch instruction to predict whether a branch is taken or not taken and having a branch tester coupled to the branch predictor to subsequently determine whether the conditional branch is predicted or mispredicted, the stack comprising: a stack memory array; a stack pointer coupled to the stack memory array to designate a stack memory array element, the stack pointer being adjusted in response to instructions that push or pop the stack; a stack remap array of pointers coupled to the stack pointer and coupled to the stack memory array to reorder stack array elements addressed by the stack pointer, the pointers being exchanged in response to a stack exchange instruction; a lookahead stack pointer designating a lookahead state of the stack pointer, the lookahead stack pointer being adjusted in response to instructions that push or pop the stack; a lookahead remap array coupled to the lookahead stack pointer to reorder stack array elements addressed by the stack pointer, the elements of the lookahead remap array being exchanged in response to a stack exchange instruction; a memory coupled to the branch unit and responsive to a stack exchange instruction to save the lookahead remap array; a memory coupled to the branch unit and responsive to instructions that push or pop the stack to save the lookahead stack pointer; means coupled to the branch tester and responsive to a mispredicted branch for restoring the lookahead remap array and the lookahead stack pointer to saved values; and means responsive to retiring of a stack exchange instruction for replacing the stack remap array with the lookahead remap array.

Claim 18

A stack as in claim 12, further comprising: lookahead full/empty array coupled to the lookahead remap array and addressed through the lookahead remap array by lookahead stack pointer to reorder stack array elements, the lookahead full/empty array elements being respectively set and cleared in response to instructions that push and pop the stack, indicating respective addition or elimination of stack array entries.

Claim 19

A stack as in claim 13 in a processor further including an instruction decoder coupled to the lookahead stack pointer, the lookahead remap array and the lookahead full/empty array, the stack including: means coupled to the instruction decoder and responsive to a stack exchange instruction for exchanging pointers in the lookahead remap array; and means coupled to the instruction decoder and responsive to instructions that push the stack and to instructions that pop the stack for adjusting the lookahead stack pointer and respectively adding and eliminating entries in the lookahead full/empty array.

Claim 20

A stack as in claim 14, wherein the stack further includes: means coupled to the instruction decoder for detecting a stack execution error; and means responsive to the detecting means stack error detection for initiating a resynchronization response.

Claim 21

A stack as in claim 13 in a processor further including a reorder buffer coupled to the stack pointer and to the remap array and a register file coupled to the stack memory array, the stack further including: a stack full/empty array coupled to the reorder buffer and coupled to the stack pointer through the stack remap array.

Claim 22

A stack as in claim 16, the processor including an exception condition detector, wherein the stack further comprises: means coupled to the instruction decoder and responsive to an exception condition for replacing the lookahead remap array with the stack remap array, replacing the lookahead stack full/empty array with the stack full/empty array, and replacing the lookahead stack pointer with the stack pointer.

Claim 23

A stack as in claim 13, the processor further including a floating point functional unit, wherein the floating point functional unit operates on data contained within the stack memory array.

Claim 24

A processor which concurrently executes a plurality of instructions from an instruction set including branch instructions, stack element exchange instructions and instructions that push and pop the stack, the stack comprising: a register file including a stack memory array; a reorder buffer coupled to the register file including: a stack pointer to specify a stack memory array element and a stack remap array coupling the stack pointer to the stack memory array to reorder stack memory elements addressed by the stack pointer; an instruction decoder coupled to the register file and the reorder buffer including: a lookahead stack pointer; a lookahead remap array coupled to the lookahead stack pointer; a decoder circuit coupled to the lookahead stack pointer and the lookahead remap array; means responsive to decoding of a stack element exchange instruction for exchanging lookahead remap array elements; means responsive to a decoding of an instruction that pushes or pops the stack for adjusting the lookahead stack pointer; a branch unit, coupled to the instruction decoder to receive copies of the lookahead remap array and the lookahead stack pointer, including: a memory responsive to a branch instruction to save copies of the lookahead remap array and the lookahead stack pointer therein; a branch predictor responsive to a conditional branch instruction to predict whether a branch is taken or not taken; a branch tester coupled to the branch predictor to subsequently determine whether the conditional branch is predicted or mispredicted; means responsive to a mispredicted branch for replacing the lookahead remap array with the saved lookahead remap array and replacing the lookahead stack pointer with the saved lookahead stack pointer; and means responsive to completion of execution of a stack element exchange instruction for replacing the stack remap array with the saved lookahead remap array.

Claim 25

A processor which concurrently executes a plurality of instructions from an instruction set including branch instructions, stack element exchange instructions and instructions that push and pop the stack, the stack comprising: a register file including a stack memory array; a reorder buffer coupled to the register file including: a stack pointer to specify a stack memory array element and a stack remap array coupling the stack pointer to the stack memory array to reorder stack memory elements addressed by the stack pointer; an instruction decoder coupled to the register file and the reorder buffer including: a lookahead stack pointer; a lookahead remap array coupled to the lookahead stack pointer; a decoder circuit coupled to the lookahead stack pointer and the lookahead remap array; means responsive to decoding of a stack element exchange instruction for exchanging lookahead remap array elements; means responsive to a decoding of an instruction that pushes or pops the stack for adjusting the lookahead stack pointer; a branch unit, coupled to the instruction decoder to receive copies of the lookahead remap array and the lookahead stack pointer, including: a memory responsive to a branch instruction to save copies of the lookahead remap array and the lookahead stack pointer therein; a branch predictor responsive to a conditional branch instruction to predict whether a branch is taken or not taken; a branch tester coupled to the branch predictor to subsequently determine whether the conditional branch is predicted or mispredicted; means responsive to a mispredicted branch for replacing the lookahead remap array with the saved lookahead remap array and replacing the lookahead stack pointer with the saved lookahead stack pointer; and means responsive to completion of execution of a stack element exchange instruction for replacing the stack remap array with the saved lookahead remap array.

Claim 26

A processor as in claim 19, further comprising: means coupled to the instruction decoder for detecting a stack execution error; and means responsive to the detecting means stack error detection for initiating a resynchronization response.

Claim 27

A processor as in claim 19, further comprising: means for detecting an exception condition and, means coupled to the instruction decoder and responsive to an exception condition for replacing the lookahead remap array with the stack remap array, replacing the lookahead stack full/empty array with the stack full/empty array, and replacing the lookahead stack pointer with the stack pointer.

Claim 28

A processor as in claim 19, further comprising: a floating point functional unit, wherein the floating point functional unit operates on data contained within the stack memory array.

Claim 29

A stack in a processor which performs instructions from an instruction set including stack pushes and pops and branch instructions, the processor including a decoder which dispatches instructions, a branch unit coupled to the decoder which predicts conditional branch instructions and detects mispredictions, a plurality of functional units coupled to the decoder to speculatively execute instructions in reliance on the predictions and a memory coupled to the decoder and the functional units to receive results of retired instructions, the stack comprising: a plurality of storage elements coupled to the reorder buffer; a pointer coupled to the storage elements and coupled to the reorder buffer for addressing ones of the plurality of storage elements; a lookahead pointer coupled to the decoder for addressing ones of the plurality of storage elements when the functional units are speculatively executing instructions; a stack controller coupled to the storage elements, the pointer, the lookahead pointer, and the decoder, including: means responsive to dispatching of stack pushes and stack pops for updating the lookahead pointer; means responsive to retiring of stack pushes and stack pops for copying the lookahead pointer to the pointer; means responsive to dispatching of a conditional branch instruction for saving the lookahead pointer; and means responsive to a branch misprediction for restoring the lookahead pointer to the saved value.

Claim 30

A stack in a processor which performs instructions from an instruction set including stack pushes and pops and branch instructions, the processor including a decoder which dispatches instructions, a branch unit coupled to the decoder which predicts conditional branch instructions and detects mispredictions, a plurality of functional units coupled to the decoder to speculatively execute instructions in reliance on the predictions and a memory coupled to the decoder and the functional units to receive results of retired instructions, the stack comprising: a plurality of storage elements coupled to the reorder buffer; a pointer coupled to the storage elements and coupled to the reorder buffer for addressing ones of the plurality of storage elements; a lookahead pointer coupled to the decoder for addressing ones of the plurality of storage elements when the functional units are speculatively executing instructions; a stack controller coupled to the storage elements, the pointer, the lookahead pointer, and the decoder, including: means responsive to dispatching of stack pushes and stack pops for updating the lookahead pointer; means responsive to retiring of stack pushes and stack pops for copying the lookahead pointer to the pointer; means responsive to dispatching of a conditional branch instruction for saving the lookahead pointer; and means responsive to a branch misprediction for restoring the lookahead pointer to the saved value.

Claim 31

A stack as in claim 23, further comprising: a full/empty array coupled to the pointer and having elements corresponding to ones of the plurality of storage elements to indicate whether the storage elements are full or empty, wherein the stack controller further comprises: means responsive to dispatching of stack pushes and stack pops for adjusting the full/empty array; means responsive to retiring of stack pushes and stack pops for adjusting the full/empty array; means responsive to a conditional branch instruction prediction for saving the full/empty array; and means responsive to a branch misprediction for restoring the full/empty array to the saved value.

Claim 32

A stack in a processor which performs instructions from an instruction set including stack pushes and pops and branch instructions, the processor including a decoder which dispatches instructions, a branch unit coupled to the decoder which predicts conditional branch instructions and detects mispredictions, a plurality of functional units coupled to the decoder to speculatively execute instructions in reliance on the predictions and a memory coupled to the decoder and the functional units to receive results of retired instructions, the stack comprising: a plurality of storage elements coupled to the reorder buffer; a remap array coupled to the storage elements and the reorder buffer to reorder ones of the plurality of storage elements; a pointer coupled to the storage elements through the remap array to address ones of the plurality of storage elements; a lookahead pointer coupled to the decoder and addressing ones of the plurality of storage elements when the functional units are speculatively executing instructions; a lookahead remap array coupled to the storage elements and the decoder for reordering ones of the plurality of storage elements when the functional units are speculatively executing instructions for dispatched stack exchange instructions; a stack controller connected to the storage elements, the remap array, the pointer, the lookahead pointer, the speculative branch lookahead pointer and the lookahead remap array, including: means coupled to the decoder and responsive to dispatching of stack pushes and stack pops for updating the lookahead pointer; means coupled to the reorder buffer and responsive to retiring of stack pushes and stack pops for copying the lookahead pointer to the pointer; means coupled to the decoder and responsive to dispatching of a conditional branch instruction for saving the lookahead pointer; means coupled to the branch unit and responsive to a branch misprediction for restoring the lookahead pointer to the saved value; means coupled to the branch unit and responsive to dispatching of a stack exchange instruction for exchanging elements of the lookahead remap array; means coupled to the branch unit and responsive to dispatching of a conditional branch instruction prediction for saving the lookahead remap array to the speculative branch lookahead remap array; means coupled to the branch unit and responsive to a branch misprediction for restoring the lookahead remap array to the saved value; and means coupled to the reorder buffer and responsive to retiring of a stack exchange instruction for copying the lookahead remap array to the remap array.

Claim 33

A stack in a processor which performs instructions from an instruction set including stack pushes and pops and branch instructions, the processor including a decoder which dispatches instructions, a branch unit coupled to the decoder which predicts conditional branch instructions and detects mispredictions, a plurality of functional units coupled to the decoder to speculatively execute instructions in reliance on the predictions and a memory coupled to the decoder and the functional units to receive results of retired instructions, the stack comprising: a plurality of storage elements coupled to the reorder buffer; a remap array coupled to the storage elements and the reorder buffer to reorder ones of the plurality of storage elements; a pointer coupled to the storage elements through the remap array to address ones of the plurality of storage elements; a lookahead pointer coupled to the decoder and addressing ones of the plurality of storage elements when the functional units are speculatively executing instructions; a lookahead remap array coupled to the storage elements and the decoder for reordering ones of the plurality of storage elements when the functional units are speculatively executing instructions for dispatched stack exchange instructions; a stack controller connected to the storage elements, the remap array, the pointer, the lookahead pointer, the speculative branch lookahead pointer and the lookahead remap array, including: means coupled to the decoder and responsive to dispatching of stack pushes and stack pops for updating the lookahead pointer; means coupled to the reorder buffer and responsive to retiring of stack pushes and stack pops for copying the lookahead pointer to the pointer; means coupled to the decoder and responsive to dispatching of a conditional branch instruction for saving the lookahead pointer; means coupled to the branch unit and responsive to a branch misprediction for restoring the lookahead pointer to the saved value; means coupled to the branch unit and responsive to dispatching of a stack exchange instruction for exchanging elements of the lookahead remap array; means coupled to the branch unit and responsive to dispatching of a conditional branch instruction prediction for saving the lookahead remap array to the speculative branch lookahead remap array; means coupled to the branch unit and responsive to a branch misprediction for restoring the lookahead remap array to the saved value; and means coupled to the reorder buffer and responsive to retiring of a stack exchange instruction for copying the lookahead remap array to the remap array.

Claim 36

A method as in claim 26, further comprising the steps of: monitoring whether the stack array elements are empty or full using a full/empty array coupled to the pointer, the full/empty array having elements that correspond to elements of the stack array, wherein the stack controller further comprises: adjusting a lookahead copy of the full/empty array by respectively adding and eliminating entries as directed in response to dispatching of instructions that push and pop the stack, adjusting a permanent copy of the full/empty array by respectively adding and eliminating entries as directed in response to retiring of instructions that push and pop the stack, saving the lookahead full/empty array in response to a conditional branch instruction prediction, and restoring the lookahead full/empty array to the saved speculative branch lookahead full/empty array in response to detection of a branch misprediction.