Method and apparatus for bypassing display register update during procedure entry

Claim 2

In a data processing system for executing a program arranged into procedural blocks each of which is assigned one of a plurality of level values and having a memory including a plurality of addressable storage locations each storing a different one of a plurality of mark words, with a plurality of displacement value fields each being contained in a different mark word and indicating the address of another one of the mark words, a plurality of the displacement value fields indicating the same address whereby the mark words are linked together to form a tree structured list having a plurality of paths each including a plurality of mark words and with the mark word stored in said same address being in a plurality of the paths, a plurality of display registers each corresponding to a different one of the level values with a plurality of addresses each being stored in a different one of the display registers, with each address being the address of a different one of the mark words that are linked together to form a first one of the plurality of paths of the tree structured list, means for reading out the addresses stored in the display registers to provide base addresses for base relative addressing during execution of a first procedural block, the data processing system being operative to stop execution of the first procedural block and make entry into a different, called procedural block for execution, and display register updating means responding to such an entry into the called procedural block for updating the display registers so that they store addresses of mark words that are linked together to form a second one of the plurality of paths for use as base addresses for base relative addressing during execution of the called procedural block, the display register updating means including means for storing into the display register corresponding to the level value assigned to the called procedural block an address of a first mark word having a displacement value field linking the first mark word into the second path of the tree structured list, means for making a series of memory accesses to obtain from mark words the displacement value fields indicating the addresses of other mark words which are linked by the obtained displacement value field into the second path of the tree and means for providing in a predetermined sequence the addresses indicated by the obtained displacement value fields to replace one by one the addresses which the display registers store, wherein the improvement comprises apparatus for bypassing the updating of display registers, the apparatus comprising: means operative during such updating for sequentially reading out the addresses stored in the display registers and address comparison means for comparing the address read out of a display register with the address provided to replace it, the address comparison means having means for producing an indicating signal when the compared addresses are the same, thereby indicating that the updating of a display register can be bypassed.

Claim 3

The apparatus as defined in claim 1 wherein the display register updating means includes a temporary storage register for storing one of the addresses provided to replace an address stored in a display register and the comparison means is a compare circuit having an input circuit coupled to the temporary storage register and coupled to the display registers and having an output circuit for producing the indicating signal when the address stored in the temporary storage register is the same as the address read out of the selected display register.

Claim 4

storing the level value assigned to the called block for indicating a display register;

Claim 5

storing the level value assigned to the called block for indicating a display register;

Claim 6

The apparatus as defined in claim 2 wherein the display register updating means includes an address register for the display registers, means for storing in the address register an initial level value corresponding to the level value assigned to the called procedural block, and means for sequentially changing the level value stored in the address register to define a sequence of level values, and the apparatus further comprises a register settable to store the level value assigned to the calling procedural block; level comparison means for producing an indicating signal when one of the sequence of level values stored in the address register is equal to or less than the level value assigned to the calling procedural block; and means responsive to the indicating signals produced by the address and level comparison means for producing a signal indicating that updating of the display registers is complete.

Claim 7

storing into the indicated display register the address of the control word that is in the addressing environment of the called block and that is associated with the same level value as the called block;

Claim 8

storing into the indicated display register the address of the control word that is in the addressing environment of the called block and that is associated with the same level value as the called block;

Claim 9

storing for comparison the address of the control word that is in the addressing environment of the first block and that is associated with the same level value as the first block;

Claim 10

storing for comparison the address of the control word that is in the addressing environment of the first block and that is associated with the same level value as the first block;

Claim 11

In a programmable data processing system having a processor and an addressable main memory storing information including a plurality of program operators of a program that is arranged into a plurality of procedures, a predetermined one of the program operators directing the processor to stop executing one procedure and to commence executing a new procedure, the information further including control words each stored at a different address and having a displacement value field, the control words being linked together by the displacement value fields to form a tree structured list each path of which indicates an addressing environment for a different one of the plurality of procedures, the processor having a plurality of display registers each for storing a pointer to a different one of the control words in the addressing environment of a procedure being executed and having control and timing means responsive to the predetermined program operator to assume a plurality of different states and produce different control signals during the different states and being responsive to indications from other circuits in the processor to repeatedly cycle through a plurality of states, the processor having first and second means responsive to said control signals, the first means for selecting display registers one by one and the second means for obtaining from the displacement value fields stored in the main memory pointers to the control words in a path of the list indicating the addressing environment for the new procedure and for updating the display registers by storing the obtained pointers one by one into the selected display registers, wherein the improvement comprises apparatus for bypassing the updating of display registers, the apparatus comprising: a comparator for producing an indication that a pointer stored in a selected display register and the pointer obtained by the second means for storing in the second display register are the same; and means for causing the control and timing means to respond to said indication to bypass the updating of the remaining display registers.

Claim 12

In a programmable data processing system having a processor and an addressable main memory storing information including a plurality of program operators of a program that is arranged into a plurality of procedures, a predetermined one of the program operators directing the processor to stop executing one procedure and to commence executing a new procedure, the information further including control words each stored at a different address and having a displacement value field, the control words being linked together by the displacement value fields to form a tree structured list each path of which indicates an addressing environment for a different one of the plurality of procedures, the processor having a plurality of display registers each for storing a pointer to a different one of the control words in the addressing environment of a procedure being executed and having control and timing means responsive to the predetermined program operator to assume a plurality of different states and produce different control signals during the different states and being responsive to indications from other circuits in the processor to repeatedly cycle through a plurality of states, the processor having first and second means responsive to said control signals, the first means for selecting display registers one by one and the second means for obtaining from the displacement value fields stored in the main memory pointers to the control words in a path of the list indicating the addressing environment for the new procedure and for updating the display registers by storing the obtained pointers one by one into the selected display registers, wherein the improvement comprises apparatus for bypassing the updating of display registers, the apparatus comprising: a comparator for producing an indication that a pointer stored in a selected display register and the pointer obtained by the second means for storing in the second display register are the same; and means for causing the control and timing means to respond to said indication to bypass the updating of the remaining display registers.

Claim 13

changing the level value for indicating a display register so as to indicate a display register corresponding to a sequentially different level value;

Claim 14

changing the level value for indicating a display register so as to indicate a display register corresponding to a sequentially different level value;

Claim 15

In a system for processing information, the system having an addressable main memory including a plurality of addressable locations respectively storing a plurality of words that are linked together by a plurality of fields to form a tree structuRed list having a plurality of paths each including a plurality of the words, each word in the list being associated with one of a plurality of level values, the tree structured list having entered in it a word associated with the lowest of the level values and a plurality of words respectively associated with sequentially higher level values, each of said fields being contained in a different one of said words and linking the word containing the field to a word in the same path of the list and associated with the next lower level value, the system having a plurality of display registers each associated with a sequential one of the level values and each for storing an indication of the location in the memory of a word in a path of the tree structured list, the system being operative to store a new word into a memory location and link the new word into the tree structured list, wherein the improvement comprises apparatus for updating the display registers when the new word is entered in the tree structured list comprising: a first register for sequentially storing indications of the level values, the first register being coupled to the display registers for selecting the display register associated with the level value stored in the first register; means for initially setting the first register to store an indication of the level value of the new word entered in the list, thereby initially selecting the display register associated with the level value of the new word; means for storing in the initially selected display register an indication of the location of the new word; a second register for sequentially storing indications of the locations of words in the tree structured list; means for initially setting the second register to store an indication of the location of an old word in the tree path in which the new word is entered, which old word is associated with the next lower level below the level value of the new word entered in the list; a third register for sequentially storing words of the tree structured list; means operable for changing the indication stored in the first register so that the first register selects a different display register; the different display register being associated with the next lower level value below the level value of the display register selected before the operation; means operable for reading out the contents of the different display register; means operable for comparing the contents read out of the different display register and the contents of the second register, and for producing an indication of whether the different display register needs updating; means operable in response to an indication that the different display register needs updating for storing therein the contents of the second register; means responsive to the indication stored in the second register for reading out the word from the indicated location and storing the word in the third register; means responsive to the linking field within the read out word for changing the indication in the second register so as to indicate the location of another word in the same path of the tree; and means for causing the six last named means to operate in sequence until the means for comparing indicates that no further display register updating is necessary.

Claim 16

In a system for processing information, the system having an addressable main memory including a plurality of addressable locations respectively storing a plurality of words that are linked together by a plurality of fields to form a tree structuRed list having a plurality of paths each including a plurality of the words, each word in the list being associated with one of a plurality of level values, the tree structured list having entered in it a word associated with the lowest of the level values and a plurality of words respectively associated with sequentially higher level values, each of said fields being contained in a different one of said words and linking the word containing the field to a word in the same path of the list and associated with the next lower level value, the system having a plurality of display registers each associated with a sequential one of the level values and each for storing an indication of the location in the memory of a word in a path of the tree structured list, the system being operative to store a new word into a memory location and link the new word into the tree structured list, wherein the improvement comprises apparatus for updating the display registers when the new word is entered in the tree structured list comprising: a first register for sequentially storing indications of the level values, the first register being coupled to the display registers for selecting the display register associated with the level value stored in the first register; means for initially setting the first register to store an indication of the level value of the new word entered in the list, thereby initially selecting the display register associated with the level value of the new word; means for storing in the initially selected display register an indication of the location of the new word; a second register for sequentially storing indications of the locations of words in the tree structured list; means for initially setting the second register to store an indication of the location of an old word in the tree path in which the new word is entered, which old word is associated with the next lower level below the level value of the new word entered in the list; a third register for sequentially storing words of the tree structured list; means operable for changing the indication stored in the first register so that the first register selects a different display register; the different display register being associated with the next lower level value below the level value of the display register selected before the operation; means operable for reading out the contents of the different display register; means operable for comparing the contents read out of the different display register and the contents of the second register, and for producing an indication of whether the different display register needs updating; means operable in response to an indication that the different display register needs updating for storing therein the contents of the second register; means responsive to the indication stored in the second register for reading out the word from the indicated location and storing the word in the third register; means responsive to the linking field within the read out word for changing the indication in the second register so as to indicate the location of another word in the same path of the tree; and means for causing the six last named means to operate in sequence until the means for comparing indicates that no further display register updating is necessary.

Claim 17

reading out the address stored in the display register indicated by the level value as changed by Step 5;

Claim 18

reading out the address stored in the display register indicated by the level value as changed by Step 5;

Claim 19

In a programmable data processing system for processing a program that is arranged into a plurality of procedural blocks, each of the blocks being assigned one of a plurality of level values, the first one of the blocks having declared therein a second one of the blocks, the second block being a calling procedure that orders programmatic entry into a third, called one of the blocks, the system having a memory including a plurality of storage locations each having an address, said locations storing information including a plurality of control words each stored at a different address and each associated with one of the plurality of level values, the control Words being linked together to form a tree structured list each path of which indicates an addressing environment for a different one of the blocks, the system having a plurality of display registers each corresponding to a sequential one of the plurality of level values and each for storing the address of a control word associated with its corresponding level value, a method of updating the display registers comprising the steps of:

Claim 20

In a programmable data processing system for processing a program that is arranged into a plurality of procedural blocks, each of the blocks being assigned one of a plurality of level values, the first one of the blocks having declared therein a second one of the blocks, the second block being a calling procedure that orders programmatic entry into a third, called one of the blocks, the system having a memory including a plurality of storage locations each having an address, said locations storing information including a plurality of control words each stored at a different address and each associated with one of the plurality of level values, the control Words being linked together to form a tree structured list each path of which indicates an addressing environment for a different one of the blocks, the system having a plurality of display registers each corresponding to a sequential one of the plurality of level values and each for storing the address of a control word associated with its corresponding level value, a method of updating the display registers comprising the steps of:

Claim 21

In a data processing apparatus having memory means storing information that is arranged into a plurality of different stack areas, the information including a plurality of groups of mark words and a plurality of reference values respectively contained in a plurality of the mark words, the mark words being respectively positioned in the plurality of stack areas, each reference value referencing another mark word in a preselected sequence to link the mark word containing the reference value to the same group of mark words that includes the mark word being referenced by the reference value for linking the stack areas together to form a tree structured stack, the apparatus further having a plurality of display registers for respectively storing a plurality of addresses, each address indicating the position of a different one of the mark words that are linked together in any selected one of the groups, and display register updating means operable for changing the addresses stored in the display registers so that they respectively indicate the positions of the mark words in a first group that is different from a second group that was so indicated before the operation, the updating means including means for sequentially utilizing the reference values in a series of linked mark words stored in the memory for forming a series of addresses to which the display registers are to be set, means for sequentially storing the formed addresses in the order they are formed into the display registers, whereby updating of the display registers proceeds in a predetermined sequence; wherein the improvement comprises: means for detecting when a series of addresses being formed are addresses of mark words that are in both the first and second groups whereby said series of addresses being formed are respectively the same as the addresses in the corresponding display registers into which such formed addresses are to be stored, and means responsive to the detection for disabling the updating means.

Claim 22

In a data processing apparatus having memory means storing information that is arranged into a plurality of different stack areas, the information including a plurality of groups of mark words and a plurality of reference values respectively contained in a plurality of the mark words, the mark words being respectively positioned in the plurality of stack areas, each reference value referencing another mark word in a preselected sequence to link the mark word containing the reference value to the same group of mark words that includes the mark word being referenced by the reference value for linking the stack areas together to form a tree structured stack, the apparatus further having a plurality of display registers for respectively storing a plurality of addresses, each address indicating the position of a different one of the mark words that are linked together in any selected one of the groups, and display register updating means operable for changing the addresses stored in the display registers so that they respectively indicate the positions of the mark words in a first group that is different from a second group that was so indicated before the operation, the updating means including means for sequentially utilizing the reference values in a series of linked mark words stored in the memory for forming a series of addresses to which the display registers are to be set, means for sequentially storing the formed addresses in the order they are formed into the display registers, whereby updating of the display registers proceeds in a predetermined sequence; wherein the improvement comprises: means for detecting when a series of addresses being formed are addresses of mark words that are in both the first and second groups whereby said series of addresses being formed are respectively the same as the addresses in the corresponding display registers into which such formed addresses are to be stored, and means responsive to the detection for disabling the updating means.

Claim 23

comparing for equality the address read out in Step 5 and the address stored for comparison;

Claim 24

comparing for equality the address read out in Step 5 and the address stored for comparison;

Claim 25

when the operation of Step 7 indicates inequality, writing into the display register indicated by the level value as changed in Step 5 the address stored for comparison;

Claim 26

when the operation of Step 7 indicates inequality, writing into the display register indicated by the level value as changed in Step 5 the address stored for comparison;

Claim 27

In a data processing apparatus as defined in claim 7 including register means For storing the address of a mark word positioned in a preselected one of the stack areas, said address forming means comprising means for combining the reference value in each mark word in such series with the address stored in the register means and thereby form the addresses to which the display registers are to be set.

Claim 28

In a data processing apparatus according to claim 8 wherein said detecting means comprises means for reading out the content of said display registers in the order they are being updated, means for comparing the addresses being formed with said addresses being read from said display registers for detecting an equality therebetween and means responsive to said detection of equality for disabling the updating means.

Claim 29

replacing the address stored for comparison with the address of the work linked to the word contained in the address being replaced;

Claim 30

replacing the address stored for comparison with the address of the work linked to the word contained in the address being replaced;

Claim 31

repeating Steps 5 through 9 until the operation of Step 7 indicates equality responsive thereto terminating Steps 5 through 9.

Claim 32

repeating Steps 5 through 9 until the operation of Step 7 indicates equality responsive thereto terminating Steps 5 through 9.

Claim 33

In a data processing apparatus according to claim 9 wherein said detecting means comprises storage means for storing a signal indicative of a display register used before the updating operation to store an address of a preselected one of the mark words in the second group, storage means for sequentially indicating each display register in the order they are updated and means for comparing the content of the last two named storage means for a predetermined correspondence, said means for disabling being responsive to the combination of said detection of equality and said predetermined correspondence for disabling the updating means.

Claim 34

A data processing system comprising: an accessible main memory including a plurality of addressable locations each storing a mark word, each mark word being associated with one of a plurality of level values, some of the mark words being associated with the same level value, each of a plurality of the mark words containing a displacement value field indicating the address of a mark word associated with a sequentially different level value from the mark word containing the displacement value field, a plurality of the displacement value fields each indicating the same address so that the mark words are linked together to form a tree structured list having a plurality of paths, each path including a plurality of the mark words, and with at least the mark word stored in said same address being in both a first and a second one of the paths; a display register memory including a plurality of display registers each corresponding to a sequential one of the level values and each for storing the address of a mark word associated with its corresponding level value, a plurality of the display registers respectively storing the addresses of the mark words linked in the first path of the list; means for updating the display registers so that they store the addresses of the mark words in the second path of the list, the updating means being operative to bypass the updating of display registers that store addresses of mark words that are linked into both the first and second paths, the updating means comprising: means operative for sequentially providing the address of each mark word linked in the second path of the list including means operative to utilize each of the addresses indicated by the displacement value fields of the mark words in the second path for making a main memory access to obtain a displacement value field indicating the address of another mark word in the second path; means for sequentially comparing pairs of addresses, each pair of addresses including one of the sequentially provided addresses and a sequentially selected one of the addresses stored in the display register memory, the comparing means including means for sequentially indicating whether the compared addresses are not equal or equal; means for storing into the display register memory each provided address indicated as not equal to the address compared with it so as to replace the address compared with it; and means responsive to an indication that the compared addresses are equal for terminating the operation of said means for making a main memory access.

Claim 35

A data processing system comprising: an accessible main memory including a plurality of addressable locations each storing a mark word, each mark word being associated with one of a plurality of level values, some of the mark words being associated with the same level value, each of a plurality of the mark words containing a displacement value field indicating the address of a mark word associated with a sequentially different level value from the mark word containing the displacement value field, a plurality of the displacement value fields each indicating the same address so that the mark words are linked together to form a tree structured list having a plurality of paths, each path including a plurality of the mark words, and with at least the mark word stored in said same address being in both a first and a second one of the paths; a display register memory including a plurality of display registers each corresponding to a sequential one of the level values and each for storing the address of a mark word associated with its corresponding level value, a plurality of the display registers respectively storing the addresses of the mark words linked in the first path of the list; means for updating the display registers so that they store the addresses of the mark words in the second path of the list, the updating means being operative to bypass the updating of display registers that store addresses of mark words that are linked into both the first and second paths, the updating means comprising: means operative for sequentially providing the address of each mark word linked in the second path of the list including means operative to utilize each of the addresses indicated by the displacement value fields of the mark words in the second path for making a main memory access to obtain a displacement value field indicating the address of another mark word in the second path; means for sequentially comparing pairs of addresses, each pair of addresses including one of the sequentially provided addresses and a sequentially selected one of the addresses stored in the display register memory, the comparing means including means for sequentially indicating whether the compared addresses are not equal or equal; means for storing into the display register memory each provided address indicated as not equal to the address compared with it so as to replace the address compared with it; and means responsive to an indication that the compared addresses are equal for terminating the operation of said means for making a main memory access.

Claim 36

A system according to claim 11 whereIn the means for sequentially comparing includes a first register for storing a level value to select a display register, means for storing in the first register an initial level value, means for sequentially changing the level value stored in the first register by a predetermined amount, means for reading out one by one the addresses stored in the display registers selected by the sequentially level values, a second register for storing one by one the provided addresses, and a compare circuit having an input circuit coupled to the second register and coupled to the display registers and having an output circuit for producing an indication signal when the address stored by the second register is the same as the address read out of a selected display register.

Claim 37

A system according to claim 12 wherein the means for terminating includes a third register and means for setting the third register to store the level value associated with a preselected one of the mark words in the first path and further includes level value comparison means for producing an indication signal when the level value stored in the first register is equal to or less than the level value stored in the third register; and means responsive to the indication signals produced by the address and level value comparison means for producing an operation complete signal.

Claim 38

A programmable data processing system comprising: a main memory including a first plurality and a second plurality of locations each location having an address, the first plurality of the locations storing program operators for first and second program procedures respectively associated with first and second ones of a plurality of level values; a data processor for executing the procedures stored in the main memory and including a display register memory; the program operators for the first procedure including a program operator ordering the processor to programmatically enter the second procedure for execution; the second plurality of locations including a first preselected location storing a first mark word associated with the first one of the level values and being programmatically addressable during execution of the first procedure, a second predetermined location storing a second mark word associated with the second one of the level values and being programmatically addressable during execution of the second procedure, a third predetermined location storing a third mark word associated with a third one of the level values and being programmatically addressable during execution of either the first or the second procedure, and a plurality of locations respectively storing a plurality of other mark words, each mark word including a displacement value for indicating the address of a location storing another mark word so that the mark words are linked together in a list, a plurality of the displacement values each indicating the same address so that the list is tree structured; the display register memory including a plurality of display registers each associated with a different level value, the display register associated with the first one of the level values storing during execution of the first procedure an indication of the address of the first preselected location, the display register associated with the third level value storing an address of the third preselected location during execution of the first procedure, and the display registers associated with level values in between the first and third level values storing an indication of addresses of locations storing mark words in the list linking the first to the third mark word; means responsive to the program operator ordering programmatic entry into the second procedure for updating the display register memory, the updating means including means for storing into the display register associated with the second level value an indication of the address of the second predetermined location; means for sequentially obtaining an indication of the addRess of each location storing a mark word linking the second to the third mark word; means for sequentially accessing each display register associated with a level value between the first and third level to read out the respective indications stored therein; means for sequentially comparing the obtained indications and the indications read out from the display registers and for identifying when the respectively compared indications are the same, thereby indicating whether the updating of an accessed display register can be bypassed; and means for sequentially storing into each accessed display register that cannot be bypassed a respective one of the obtained indications.

Claim 39

A programmable data processing system comprising: a main memory including a first plurality and a second plurality of locations each location having an address, the first plurality of the locations storing program operators for first and second program procedures respectively associated with first and second ones of a plurality of level values; a data processor for executing the procedures stored in the main memory and including a display register memory; the program operators for the first procedure including a program operator ordering the processor to programmatically enter the second procedure for execution; the second plurality of locations including a first preselected location storing a first mark word associated with the first one of the level values and being programmatically addressable during execution of the first procedure, a second predetermined location storing a second mark word associated with the second one of the level values and being programmatically addressable during execution of the second procedure, a third predetermined location storing a third mark word associated with a third one of the level values and being programmatically addressable during execution of either the first or the second procedure, and a plurality of locations respectively storing a plurality of other mark words, each mark word including a displacement value for indicating the address of a location storing another mark word so that the mark words are linked together in a list, a plurality of the displacement values each indicating the same address so that the list is tree structured; the display register memory including a plurality of display registers each associated with a different level value, the display register associated with the first one of the level values storing during execution of the first procedure an indication of the address of the first preselected location, the display register associated with the third level value storing an address of the third preselected location during execution of the first procedure, and the display registers associated with level values in between the first and third level values storing an indication of addresses of locations storing mark words in the list linking the first to the third mark word; means responsive to the program operator ordering programmatic entry into the second procedure for updating the display register memory, the updating means including means for storing into the display register associated with the second level value an indication of the address of the second predetermined location; means for sequentially obtaining an indication of the addRess of each location storing a mark word linking the second to the third mark word; means for sequentially accessing each display register associated with a level value between the first and third level to read out the respective indications stored therein; means for sequentially comparing the obtained indications and the indications read out from the display registers and for identifying when the respectively compared indications are the same, thereby indicating whether the updating of an accessed display register can be bypassed; and means for sequentially storing into each accessed display register that cannot be bypassed a respective one of the obtained indications.