Data processing method and apparatus using occupancy indications to reserve storage space for a stack

Claim 2

A programmable data processing system for executing a program which includes a plurality of blocks and which includes program operators that order entry into and exit from the blocks, the system comprising: main memory means comprising a plurality of addressable memory means locations and having a first access time, one of the memory means locations storing a mark word for a first block which has been entered and which has ordered entry into a second block before having been exited, said mark-word-storing memory means location serving as a base location for a stack area having a depth, said stack area comprising a plurality of the memory means locations and storing a stack of words for the first block; and a data processor comprising: a. a local memory comprising a plurality of addressable localmemory locations and having a second access time which is lower than the first access time, the local-memory locations storing a stack of words, including a mark word and a top of stack word, for the second block, the mark word stored in the local memory containing a difference value pointing to said markword-storing memory means location and indicating the depth of said stack area, b. register means storing a pointer to a local-memory location that stores the word at the top of the local memory stack; c. a plurality of occupancy indicating means, each associated with a different one of the local memory locations and indicating whether its associated location stores a stack word, and each settable and resettable to indicate that its associated location respectively stores or does not store a stack word; d. means for accessing the main memory means to obtain program operators and stack-area-stack words; and e. reserving means responsive to an obtained program operator ordering an exit from the second block for reserving localmemory locations such that each of a plurality of stack-areastack words obtained after the second block is exited will have a local-memory location allocated for its storage, the reserving means comprising 1. for reading out said mark word stored in the local memory, 2. means responsive to said difference value contained in the read out mark word for producing a pointer and means for loading the produced pointer into the register means, and 3. means for resetting the occupancy indicating means associated with each of a plurality of local-memory locations to indicate that the associated locations have been allocated to store stack words but that the obtaining of stack words for storage therein has been at least temporarily postponed.

Claim 3

setting the pointer to point to the location of the first memory which was the top location of the stack for the first block.

Claim 4

setting the pointer to point to the location of the first memory which was the top location of the stack for the first block.

Claim 5

A system according to claim 1 wherein the reserving means includes means for simultaneously resetting all of the occupancy indicating means.

Claim 6

means responsive to said difference value contained in the read out mark word for producing a pointer and means for loading the produced pointer into the register means, and

Claim 7

means responsive to said difference value contained in the read out mark word for producing a pointer and means for loading the produced pointer into the register means, and

Claim 8

means for resetting the occupancy indicating means associated with each of a plurality of local-memory locations to indicate that the associated locations have been allocated to store stack words but that the obtaining of stack words for storage therein has been at least temporarily postponed.

Claim 9

means for resetting the occupancy indicating means associated with each of a plurality of local-memory locations to indicate that the associated locations have been allocated to store stack words but that the obtaining of stack words for storage therein has been at least temporarily postponed.

Claim 10

A system according to claim 2 wherein the reserving means further comprises transferring means operative to cooperate with the accessing means to transfer said mark word stored in the memory means to a predetermined local-memory location, the predetermined local-memory location being the one from which a mark word was read out, and means for setting the occupancy indicating means associated with said predetermined location.

Claim 11

A system according to claim 3 wherein the data processor further includes a first register storing a first address pointing to a memory means location indicating that the pointed to location has been allocated for storing the mark word for the second block, and includes address modifying means; and wherein the transferring means includes means for supplying to the address modifying means the difference value contained in the mark word for the second block and the first address, the address modifying means including means responsive to the supplied difference value and first address for producing an address pointing to the memory means location storing the mark word for the first block; and means responsive to the produced address for reading out the mark word for the first block. address

Claim 12

A system according to claim 4 including means for overwriting the first register with the produced address so as to deallocate the location which had been allocated for storing the mark word for the second block.

Claim 13

A system according to claim 5 wherein the data processor includes a second register storing a second address pointing to a memory means location which has been allocated for storing the word at the top of the local memory stack; and means responsive to the program operator ordering an exit from the second block for deallocating the location which had been allocated for storing the top of local-memory stack word, the last-named means including means responsive to the first address for overwriting the second register with an address pointing to the memory means location storing the stack-area stack word that is the top word in the stack area.

Claim 14

A system according to claim 6 further comprising a bistable device and wherein the reserving means includes means for detecting that said stack depth exceeds a predetermined number and means responsive to such detection for setting the bistable device.

Claim 15

A system according to claim 1 wherein the data processor further includes a first register storing a first address pointing to a location of the memory means and indicating that the pointed to location has been allocated for storing the mark word for the second block; address modifying means; means for supplying to the address modifying means the difference value contained in the mark word for the second block and the first address, the address modifying means including means responsive to the supplied difference value and first address for producing an address pointing to the main memory means location storing the mark word for the first block; means responsive to the produced address for reading out the mark word for the first block; and means for overwriting the first register with the produced address so as to deallocate the location which had been allocated for storing the mark word for the second block.

Claim 16

A system according to claim 8 wherein the data processor includes a second register storing a second address pointing to the memory means location which has been allocated for storing the word at the top of the local memory stack; and means responsive to the program operator ordering an exit from the second block for deallocating the location which had been allocated for storing the top of local-memory stack stack word, the last-named means including means responsive to the first address for overwriting the second register with an address pointing to the memory means location storing the stack-area stack word that is the top word in the stack area.

Claim 17

A system according to claim 9 wherein the data processor includes means for adding a new word to the local memory stack comprising means for incrementing the register means pointing to the local memory; means for incrementing the second register, thereby allocating an additional location of the memory means; means for writing the new word into the local memOry location pointed to by the incremented pointer; and means for setting the occupancy indicating means associated with the local memory location written into.

Claim 18

A system according to claim 10 further comprising a bistable device settable to indicate that all local memory locations have been allocated and resettable to indicate that at least one local memory location has not been allocated; means for detecting that a new word has been added to a predetermined location; and means responsive to such detection for setting the bistable device.

Claim 19

A system according to claim 1 further comprising a plurality of copy indicating means, each associated with a different local memory location and indicating whether its associated location stores a stack word which is a copy of a stack word stored in the memory means, and each settable and resettable to indicate that the stack word stored in its associated location is or is not respectively such a copy; and wherein the reserving means includes means for simultaneously resetting all of the copy indicating means.

Claim 20

A system according to claim 12 wherein the first block is associated with a first level value and includes program operators containing address indicia comprising a level pointer and an increment value, and wherein the second block is associated with a second level value; the combination further comprising: a level indicating register storing the second level value; a first register storing a pointer to a memory means location and indicating that the pointed to location has been allocated for storing the mark word for the second block; means responsive to the program operator ordering an exit from the second block for loading the first level value into the level indicating register; means responsive to the value contained in the mark word read out of the local memory for producing a pointer to said mark word stored in the memory means; means for loading the produced pointer into the first register; and word copying means for writing into the local memory a copy of a word in the memory means, the word copying means comprising means responsive to said address indicia of a program operator for detecting equality between the level pointer and said first level value loaded into the level indicating register, means responsive to such detection for combining the increment value with the pointer loaded into the mark word pointing register to produce an address of memory means, means for transferring a stack word stored at the address into a location of the local memory and means for setting the occupancy and copy indicating means associated with such location.

Claim 21

A system according to claim 12 wherein the data processor includes controllable means responsive to a program operator ordering an entry into a third block for transferring the stack for the second block to the memory means; means responsive to the copy indicating means to select stack words which are copies of stack words stored in the memory means; and means responsive to such detection for disabling the transfer of such copies.

Claim 22

A data processing system comprising: means for accumulating a stack of words including first register means, a stack storage apparatus, means for transferring words from the first register means into the stack storage apparatus for accumulation, and means for transferring accumulated words from the stack storage apparatus to the first register means in a last-in first-out order, the stack storage apparatus including a first plurality of memory locations, a second, smaller plurality of extension locations, and second register means settable to a selectable state to define an association between a selectable group of the memory locations and the extension locations such that each extension location is associated with a different one of the memory locations of the selected group to define corresponding pairs, each pair being reserved for storing a different pair of duplicate words; means setTable to identify each corresponding pair in a first condition wherein the pair stores the word for which it is reserved in the respective memory location and settable to identify each corresponding pair in a second condition wherein the pair stores the word for which it is reserved only in the respective extension location; setting means for the second register means including means for sequentially setting the second register means so that in sequence the second register means is set to a first state, then is changed to at least a second state, and then again is set to the first state; setting means for the identifying means including means for setting the identifying means so that it identifies a plurality of corresponding pairs as being in the first condition when the second register means is again set to the first state, and means for setting the identifying means so that it identifies a corresponding pair as being in the second condition upon accumulating a word in the respective extension location; and means operable when the state of the second register means is changed in the course of said sequence for transferring words from selected extension locations to the corresponding memory locations if the identifying means identifies the selected corresponding pair as being in the second condition.

Claim 23

A data processing system comprising: means for accumulating a stack of words including first register means, a stack storage apparatus, means for transferring words from the first register means into the stack storage apparatus for accumulation, and means for transferring accumulated words from the stack storage apparatus to the first register means in a last-in first-out order, the stack storage apparatus including a first plurality of memory locations, a second, smaller plurality of extension locations, and second register means settable to a selectable state to define an association between a selectable group of the memory locations and the extension locations such that each extension location is associated with a different one of the memory locations of the selected group to define corresponding pairs, each pair being reserved for storing a different pair of duplicate words; means setTable to identify each corresponding pair in a first condition wherein the pair stores the word for which it is reserved in the respective memory location and settable to identify each corresponding pair in a second condition wherein the pair stores the word for which it is reserved only in the respective extension location; setting means for the second register means including means for sequentially setting the second register means so that in sequence the second register means is set to a first state, then is changed to at least a second state, and then again is set to the first state; setting means for the identifying means including means for setting the identifying means so that it identifies a plurality of corresponding pairs as being in the first condition when the second register means is again set to the first state, and means for setting the identifying means so that it identifies a corresponding pair as being in the second condition upon accumulating a word in the respective extension location; and means operable when the state of the second register means is changed in the course of said sequence for transferring words from selected extension locations to the corresponding memory locations if the identifying means identifies the selected corresponding pair as being in the second condition.

Claim 24

A data processing system comprising: addressable memory means; data processing means including a last-in first-out stack store which includes a plurality of memory locations in said memory means; the last-in first-out stack store comprising: a plurality of extension storage locations, one for each of said plurality of memory locations; occupied store indicator and copy store indicator for each extension location; means for selectively storing information in the memory locations and the extension locations; means for selectively setting an occupied store indicator to indicate storage of information in the corresponding extension location; means for selectively setting a copy indicator to indicate information is stored in the corresponding memory location; means responsive to the occupancy indication or lack thereof, respectively, for selectively obtaining information from the corresponding extension location or the corresponding memory location; and means responsive to the copy indicator for transferring information from extension locations to corresponding memory locations for which the copy indication is absent.

Claim 25

A data processing system comprising: addressable memory means; data processing means including a last-in first-out stack store which includes a plurality of memory locations in said memory means; the last-in first-out stack store comprising: a plurality of extension storage locations, one for each of said plurality of memory locations; occupied store indicator and copy store indicator for each extension location; means for selectively storing information in the memory locations and the extension locations; means for selectively setting an occupied store indicator to indicate storage of information in the corresponding extension location; means for selectively setting a copy indicator to indicate information is stored in the corresponding memory location; means responsive to the occupancy indication or lack thereof, respectively, for selectively obtaining information from the corresponding extension location or the corresponding memory location; and means responsive to the copy indicator for transferring information from extension locations to corresponding memory locations for which the copy indication is absent.

Claim 26

In a data processing system for executing a string of program operators forming a program having first and second blocks, having a program operator within the first block that orders entry into the second block and having a program operator within the second block that orders exit to the first block, the processing system including a first memory which has a plurality of locations and including a second memory which has a larger plurality of locations than the first memory but which has a longer access time, each memory for storing words which are accumulated during the execution of the program, a method for allocating the storage of the words between the locations of the first memory and the second memory, the method comprising the steps of: a. accumulating in the first memory a plurality of words during the execution of the first block by push-down and pop-up operations; a push-down operation causing a word to be written into a location of the first memory and added to the total accumulated words; and a pop-up operation causing the word last written into the first memory by a push-down operation to be read out of the first memory and removed from the total of accumulated words; the accumulating step thereby forming an expanding and contracting stack wherein the location storing the last word pushed down and not yet popped up is the top location of the stack; b. storing a pointer to said top location and updating the pointer as the stack expands and contracts; c. marking tHe locations of the first memory containing the accumulated words to indicate such locations are occupied; d. detecting the program operator ordering entry into the second block, and responsive to such detection transferring to the second memory the accumulated words for the first block; e. accumulating in the first memory a plurality of words during the execution of the second block by push-down and pop-up operations and, meanwhile, repeating steps b and c; and f. detecting the program operator ordering an exit from the second block, and responsive to such detection

Claim 27

In a data processing system for executing a string of program operators forming a program having first and second blocks, having a program operator within the first block that orders entry into the second block and having a program operator within the second block that orders exit to the first block, the processing system including a first memory which has a plurality of locations and including a second memory which has a larger plurality of locations than the first memory but which has a longer access time, each memory for storing words which are accumulated during the execution of the program, a method for allocating the storage of the words between the locations of the first memory and the second memory, the method comprising the steps of: a. accumulating in the first memory a plurality of words during the execution of the first block by push-down and pop-up operations; a push-down operation causing a word to be written into a location of the first memory and added to the total accumulated words; and a pop-up operation causing the word last written into the first memory by a push-down operation to be read out of the first memory and removed from the total of accumulated words; the accumulating step thereby forming an expanding and contracting stack wherein the location storing the last word pushed down and not yet popped up is the top location of the stack; b. storing a pointer to said top location and updating the pointer as the stack expands and contracts; c. marking tHe locations of the first memory containing the accumulated words to indicate such locations are occupied; d. detecting the program operator ordering entry into the second block, and responsive to such detection transferring to the second memory the accumulated words for the first block; e. accumulating in the first memory a plurality of words during the execution of the second block by push-down and pop-up operations and, meanwhile, repeating steps b and c; and f. detecting the program operator ordering an exit from the second block, and responsive to such detection

Claim 28

A data processing system comprising: processing means including means for sequentially providing a plurality of information items to be accumulated as a stack and means for receiving information items retrieved from the stack; an addressable memory; a last-in, first-out store and store accessing means for transferring information items into and out of the store to accumulate the stack, the store comprising a multiplicity of memory locations in the memory and a plurality of extension locations; settable means for identifying as currently reserved one of a plurality of groups of memory locations, each extension location corresponding to a different one of the reserved memory locations; first setting means for setting the identifying means to sequentially select each of a plurality of groups with a first group and a second group being sequentially selected and subsequently the first plurality being re-selected copying means operable for transferring information items in either direction between corresponding memory and extension locations such that each information item transferred to an extension location by operation of the copying means is a copy of the information item in its corresponding memory location; a plurality of indicators, each associated with a different extension location and having first, second, and third states, the first state indicating that there is stored in a memory location an information item of which there is not a copy in the corresponding extension location, the second state indicating that there is stored in a memory location an information item of which there is a copy in the corresponding extension location, and the third state indicating that there is stored in an extension location a new information item that is not a copy; the store accessing means including means operative to store into each of a plurality of extension locations a respective one of a plurality of information items provided by the processing means while the first group is currently reserved; means for setting to the third state each of the indicators associated with said each of a plurality of extension locations; means for setting to the second state each of the indicators associated with extension locations to which an information item is transferred by operation of the copying means; means responsive to the first setting means for setting indicators to the first state such that when the first group is reselected a plurality of extension locations are reserved for storing copies of information items thereby to at least temporarily postpone transfer of information items thereto; and the store accessing means including means for retrieving information items for the processing means with the retrieving means including means responsive to the indicators for accessing one of the extension locations if the associated indicator is in the second or third state and from the corresponding memory location if the associated indicator is in the first state.

Claim 29

A data processing system comprising: processing means including means for sequentially providing a plurality of information items to be accumulated as a stack and means for receiving information items retrieved from the stack; an addressable memory; a last-in, first-out store and store accessing means for transferring information items into and out of the store to accumulate the stack, the store comprising a multiplicity of memory locations in the memory and a plurality of extension locations; settable means for identifying as currently reserved one of a plurality of groups of memory locations, each extension location corresponding to a different one of the reserved memory locations; first setting means for setting the identifying means to sequentially select each of a plurality of groups with a first group and a second group being sequentially selected and subsequently the first plurality being re-selected copying means operable for transferring information items in either direction between corresponding memory and extension locations such that each information item transferred to an extension location by operation of the copying means is a copy of the information item in its corresponding memory location; a plurality of indicators, each associated with a different extension location and having first, second, and third states, the first state indicating that there is stored in a memory location an information item of which there is not a copy in the corresponding extension location, the second state indicating that there is stored in a memory location an information item of which there is a copy in the corresponding extension location, and the third state indicating that there is stored in an extension location a new information item that is not a copy; the store accessing means including means operative to store into each of a plurality of extension locations a respective one of a plurality of information items provided by the processing means while the first group is currently reserved; means for setting to the third state each of the indicators associated with said each of a plurality of extension locations; means for setting to the second state each of the indicators associated with extension locations to which an information item is transferred by operation of the copying means; means responsive to the first setting means for setting indicators to the first state such that when the first group is reselected a plurality of extension locations are reserved for storing copies of information items thereby to at least temporarily postpone transfer of information items thereto; and the store accessing means including means for retrieving information items for the processing means with the retrieving means including means responsive to the indicators for accessing one of the extension locations if the associated indicator is in the second or third state and from the corresponding memory location if the associated indicator is in the first state.