# US 2021/0232422 A1 · Method and apparatus for predicting and scheduling copy instruction for software pipelined loops

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0232422 A1
- Document ID: US20210232422A1
- Status: Published application
- Kind: A1
- Application number: 16/750,734
- Filed: 2020-01-23
- Published: 2021-07-29
- Earliest claimed: 2020-01-23
- Assignees: Huawei Technologies Co., Ltd.
- Inventors: Ehsan AMIRI; Ning XIE
- Web page: https://patentgrep.com/patent/US20210232422A1

## CPC

- G06F 8/41: Compilation
- G06F 8/443: {Optimisation}
- G06F 8/4452: {Software pipelining}
- G06F 9/30007: {to perform operations on data operands}
- G06F 9/325: {for loops, e.g. loop detection or loop counter}
- G06F 9/3836: {Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution}
- G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method for scheduling instructions for execution on a computer system includes scanning a plurality of loop instructions that are modulo scheduled to identify a first instruction and a second instruction that both utilize a register of the computer system upon execution of the plurality of instructions. The loop has a first initiation interval. The first instruction defines a first value of the register in a first iteration of the loop and he second instruction redefines the value of the register to a second value in a subsequent iteration of the loop prior to a use of the first value in the first iteration of the loop. A copy instruction is inserted in the loop instructions to copy the first value prior to execution of the second instruction. A schedule is determined after the insertion of the one or more copy instructions giving a second initiation interval.

## Claims

### Claim 1

A method for scheduling instructions for execution on a computer system, the method comprising:
scanning a plurality of loop instructions that are modulo scheduled to identify a first instruction and a second instruction of the plurality of loop instructions that both utilize a register of the computer system upon execution of the plurality of instructions, the loop having a first initiation interval, the first instruction defining a first value of the register in a first iteration of the loop, the second instruction redefining the value of the register to a second value in a subsequent iteration of the loop prior to a use of the first value in the first iteration of the loop;
inserting one or more copy instructions in the plurality of loop instructions to copy the first value prior to execution of the second instruction;
determining a schedule for the plurality of loop instructions after the insertion of the one or more copy instructions, the schedule comprising a second initiation interval.

### Claim 2 (depends on 1)

The method of claim 1 further comprising comparing the schedule to a second schedule of the plurality of loop instructions, and selecting one of the schedule and the second schedule.

### Claim 3 (depends on 1)

The method of claim 1 wherein the first instruction and the second instruction form a disjoint set of virtual registers defined by the plurality of instructions.

### Claim 4 (depends on 3)

The method of claim 3 wherein the disjoint set further comprises a root node, the root node acting as a key to a hash table, the hash table comprising a pointer to an address of the first instruction and an address of the second instruction.

### Claim 5 (depends on 4)

The method of claim 4 wherein the address of the first instruction and the address of the second instruction both comprise an iteration, a stage, and a cycle.

### Claim 6 (depends on 3)

The method of claim 3 wherein the first instruction and the second instruction are tied operands.

### Claim 7 (depends on 1)

The method of claim 1 wherein the plurality of loop instructions have a static single assignment form and the first instruction is a phi node.

### Claim 8 (depends on 1)

The method of claim 1 wherein the register of the computer system corresponds to a physical register of a target processor or the plurality of loop instructions.

### Claim 9 (depends on 1)

The method of claim 1 wherein the one or more copy instructions comprises two copy instructions, the first of the two copy instructions inserted after the second instruction and prior to the use of the first value in the first iteration of the loop.

### Claim 10 (depends on 1)

The method of claim 1 wherein the one or more copy instructions comprises one copy instruction inserted after the second instruction and in parallel to the use of the first value in the first iteration of the loop.

### Claim 11 (depends on 1)

The method of claim 1 wherein the one or more copy instructions comprises one copy instruction inserted in parallel with the second instruction and prior to the use of the first value in the first iteration of the loop.

### Claim 12

An apparatus for scheduling instructions for execution on a computer system, the apparatus comprising:
a CPU; and
a non-transitory computer readable storage medium configured to store compiler instructions to control the CPU to perform steps of:
scanning a plurality of loop instructions that are modulo scheduled to identify a first instruction and a second instruction of the plurality of instructions that both utilize a register of the computer system upon execution of the plurality of instructions, the loop having a first initiation interval, the first instruction defining a first value of the register in a first iteration of the loop, the second instruction redefining the value of the register to a second value in a subsequent iteration of the loop prior to a use of the first value in the first iteration of the loop;
inserting one or more copy instructions in the plurality of loop instructions to copy the first value prior to execution of the second instruction;
determining a schedule for the plurality of loop instructions after the insertion of the one or more copy instructions, the schedule comprising a second initiation interval.

### Claim 13 (depends on 2)

The apparatus of claim 2 further comprising the steps of comparing the schedule to a second schedule of the plurality of loop instructions, and selecting one of the schedule and the second schedule.

### Claim 14 (depends on 12)

The apparatus of claim 12 wherein the first instruction and the second instruction form a disjoint set of virtual registers defined by the plurality of instructions.

### Claim 15 (depends on 14)

The apparatus of claim 14 wherein the disjoint set further comprises a root node, the root node acting as a key to a hash table, the hash table comprising a pointer to an address of the first instruction and an address of the second instruction.

### Claim 16 (depends on 15)

The apparatus of claim 15 wherein the address of the first instruction and the address of the second instruction both comprise an iteration, a stage, and a cycle.

### Claim 17 (depends on 14)

The apparatus of claim 14 wherein the first instruction and the second instruction are tied operands.

### Claim 18 (depends on 12)

The apparatus of claim 12 wherein the plurality of loop instructions have a static single assignment form and the first instruction is a phi node.

### Claim 19 (depends on 12)

The apparatus of claim 12 wherein the register of the computer system corresponds to a physical register of a target processor or the plurality of loop instructions.

### Claim 20

A non-transitory computer readable medium storing instructions executable in one or more processors, the instructions when executed in the one or more processors causing operations comprising:
scanning a plurality of loop instructions that are modulo scheduled to identify a first instruction and a second instruction of the plurality of instructions that both utilize a register of the computer system upon execution of the plurality of instructions, the loop having a first initiation interval, the first instruction defining a first value of the register in a first iteration of the loop, the second instruction redefining the value of the register to a second value in a subsequent iteration of the loop prior to a use of the first value in the first iteration of the loop;
inserting one or more copy instructions in the plurality of loop instructions to copy the first value prior to execution of the second instruction;
determining a schedule for the plurality of loop instructions after the insertion of the one or more copy instructions, the schedule comprising a second initiation interval.
