Method and apparatus for counting remaining loop instructions and pipelining the next instruction

• US 5,898,866 A
• Filed: 01/13/1994
• Issued: 04/27/1999
• Est. Priority Date: 12/21/1988
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Atkins, Mark D., Rundle, Alfred T., Ngai, Agnes Yee
• Primary Examiner(s): Pan, Daniel H.
• Application Number:
  US08/180,648
• Time in Patent Office: 1,930 Days
• Field of Search: 395/800, 395/375, 395/400, 395/425, 395/500, 395/250, 395/275, 395/384, 395/182.14, 395/387, 395/383, 395/572, 395/588, 364/DIG. 1, 364/DIG. 2, 711/125
• US Class Current: 712/241
• CPC Class Codes: G06F 9/325 for loops, e.g. loop detection or loop counter

Abstract

Method and apparatus to avoid the code space and time overhead of the software-loop. Loops (repeatedly executed blocks of instructions) are often used in software and microcode. Loops may be employed for array manipulation, storage initialization, division and square-root interpretation, and microinterpretation of instructions with variable-length operands. Software creates loops by keeping an iteration count in a register or in memory. During each iteration of the code loop, software decrements the count, and then branches to the "top" of the loop is the count remains nonzero. This apparatus puts the decrement, compare, and branch-to-top into hardware, reducing the number of instructions in the loop and speeding loop execution. Hardware further speeds loop execution by eliminating the wait for the branch to the top-of-loop instruction. That is, it prefetches the top-of-loop instruction near the bottom of the loop. The loop may be initialized for a fixed iteration count, or can accept a variable count in the iteration count register. The apparatus consists of counters for the number of instructions in the loop, an iteration counter, a pointer to the top-of-loop location, and an instruction to initiate the loop.

Claims

1. A computer system for executing a program loop a plurality of iterations, said program loop comprising one or more program instructions, said system comprising:

a first register for storing an address of one of said program instructions at a beginning of said loop;

a second register for storing an integer representing a number of iterations that said program loop has yet to be executed;

a third register for storing an integer representing a number of program instructions yet to be executed in a current iteration of said program loop; and

computer hardware means,

responsive to each program instruction within said program loop, for executing said each program instruction and decrementing said third register, responsive to completion of each iteration of said program loop, for decrementing said second register, and if said second register indicates that at least one more iteration is required, for continuing program execution with the program instruction whose address is stored in said first register, whereby no branch program instruction is required in said program loop, and if said second register indicates that all program iterations have been completed, for continuing program execution after said program loop, and

responsive to a value in said second register indicating a last iteration of said program loop and a value in said third register indicating that a predetermined integer greater than zero of program instructions remain to be executed in a last iteration of said program loop, for prefetching a next instruction to follow completion of a last program instruction in the last iteration of said program loop.

2. A computer system for executing a program loop a plurality of iterations and executing an initialization program instruction which immediately precedes said program loop, said program loop comprising one or more program instructions, said system comprising:

first, second and third registers; and

computer hardware means,

responsive to said initialization program instruction, for (a) loading said first register with an address of one of said program instructions at a beginning of said loop;

(b) loading said second register with an integer representing a total number of iterations that said program loop will be executed, (c) loading said third register with an integer representing a total number of program instructions within said program loop and (d) recognizing a next program instruction as a first program instruction in said program loop,

responsive to each program instruction within said program loop, for executing said each program instruction and decrementing said third register, and

responsive to completion of each iteration of said program loop, for decrementing said second register, and if said second register indicates that at least one more iteration is required, for continuing program execution with the program instruction whose address is stored in said first register, whereby no branch program instruction is required in said program loop, and if said second register indicates that all program iterations have been completed, for continuing program execution after said program loop.

3. A computer system for executing a program loop a plurality of iterations, said program loop comprising one or more program instructions, said system comprising:

a first register for storing an address of one of said program instructions at a beginning of said loop;

a second register for storing an integer representing a number of iterations that said program loop has yet to be executed;

a third register for storing an integer representing a number of program instructions yet to be executed in a current iteration of said program loop; and

computer hardware means,

responsive to each program instruction within said program loop, for executing said each program instruction and decrementing said third register,

responsive to completion of each iteration of said program loop, for decrementing said second register, and if said second register indicates that at least one more iteration is required, for continuing program execution with the program instruction whose address is stored in said first register, whereby no branch program instruction is required in said program loop, and if said second register indicates that all program iterations have been completed, for continuing program execution after said program loop, and

responsive to a value in said second register indicating a last iteration of said program loop and a value in said third register indicating that a predetermined integer greater than zero of program instructions remain to be executed in said last iteration of said program loop, for determining, before execution of a last program instruction in the last iteration, an address for an instruction to be executed immediately following said last program instruction in said last iteration.