# US 2018/0024822 A1 · Partial connection of iterations during loop unrolling

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

- Number: US 2018/0024822 A1
- Document ID: US20180024822A1
- Status: Published application
- Kind: A1
- Application number: 15/214,620
- Filed: 2016-07-20
- Published: 2018-01-25
- Earliest claimed: 2016-07-20
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Andrew J. Craik; Vijay Sundaresan
- Web page: https://patentgrep.com/patent/US20180024822A1

## CPC

- G06F 8/443: {Optimisation}
- G06F 8/4441: {Reducing the execution time required by the program code}
- G06F 8/4452: {Software pipelining}
- G06F 8/452: {Loops}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method and system for partial connection of iterations during loop unrolling during compilation of a program by a compiler. Unrolled loop iterations of a loop in the program are selectively connected, including redirecting, to the head of the loop, undesirable edges of a control flow from one iteration to a next iteration of the loop. Merges on a path of hot code are removed to increase a scope for optimization of the program. The head of the loop and a start of a replicated loop body of the loop are equivalent points of the control flow. A sequence of blocks on the path of hot code, unpolluted by a control flow of a path of cold code, is extended during the compilation. Information computed by an optimizer about the hot code in a first iteration is used to further optimize a second iteration, and the loop is further unrolled.

## Claims

### Claim 1

A method for partial connection of iterations during loop unrolling during compilation of a program by a compiler, said method comprising:
selectively connecting, by one or more processors of a computer system during the compilation, unrolled loop iterations of a loop in the program, wherein said selectively connecting unrolled loop iterations comprises redirecting, to the head of the loop, edges of a control flow for the program that are classed as undesirable from one iteration of the loop to a next iteration of the loop, and wherein the head of the loop and a start of a replicated loop body of the loop are equivalent points of the control flow for the program;
removing, by the one or more processors during the compilation, merges on a path of hot code in the loop to increase a scope for optimization of the program; and
extending, by the one or more processors during the compilation, a sequence of blocks on the path of hot code, unpolluted by a control flow of a path of cold code, wherein information computed by an optimizer in or invoked by the compiler about the hot code in a first iteration of the loop is used to further optimize a second iteration of the loop, and wherein the loop is further unrolled.

### Claim 2 (depends on 1)

The method of claim 1, wherein selectively connecting unrolled loop iterations comprises:
connecting an exit block of the first iteration to an entry block of the second iteration, wherein the entry block of the first iteration is an equivalent point of the control flow to the entry block of the second iteration, and wherein edges from the first iteration are selectively redirected from the second iteration to the entry block of the first iteration.

### Claim 3 (depends on 1)

The method of claim 1, wherein said selectively connecting unrolled loop iterations comprises:
classifying the edges of the control flow as undesirable using predetermined criteria comprising cold or rarely executed paths, paths of the control flow containing calls and calls including virtual calls, failed side of a runtime inlined method guard, and paths which throw and catch exceptions.

### Claim 4 (depends on 1)

The method of claim 1, wherein said extending a sequence of blocks on the path of hot code comprises:
removing runtime method tests;
constraining side-effects of the calls and predetermined elements of the control flow to a region of the loop executed less than a predetermined number of times relative to other respective regions of the loop; and
modifying, by the optimizer, regions of the loop executed more than a predetermined number of times relative to the other respective regions of the loop.

### Claim 5 (depends on 1)

The method of claim 1, wherein the hot code comprises code blocks for which most of an execution time of the program is spent, and code blocks which are executed more often relative to other code blocks in the program, and wherein the cold code comprises code blocks for which less of the execution time of the respective program is spent, relative to the other code blocks in the respective program and code blocks which are executed less often relative to other code blocks in the respective program.

### Claim 6 (depends on 1)

The method of claim 1, wherein said loop unrolling is performed with respect to a language selected from the group consisting of a managed runtime language, a scripting environment language, and a procedural language.

### Claim 7 (depends on 1)

The method of claim 1, wherein said redirecting comprises redirecting edges of the control flow associated with the cold path to the loop header and edges of the control flow associated with the hot path to connect to the next iteration to form a segregation of the control flow that enables the information computed by the optimizer about a hot code sequence of the first iteration to further optimize the second, unrolled iteration.

### Claim 8

A computer program product, comprising one or more computer readable hardware storage devices having computer readable program instructions stored therein, said program instructions executable by one or more processors of a computer system to implement a method for partial connection of iterations during loop unrolling during compilation of a program by a compiler, said method comprising:
selectively connecting, by the one or more processors during the compilation, unrolled loop iterations of a loop in the program, wherein said selectively connecting unrolled loop iterations comprises redirecting, to the head of the loop, edges of a control flow for the program that are classed as undesirable from one iteration of the loop to a next iteration of the loop, and wherein the head of the loop and a start of a replicated loop body of the loop are equivalent points of the control flow for the program;
removing, by the one or more processors during the compilation, merges on a path of hot code in the loop to increase a scope for optimization of the program; and
extending, by the one or more processors during the compilation, a sequence of blocks on the path of hot code, unpolluted by a control flow of a path of cold code, wherein information computed by an optimizer in or invoked by the compiler about the hot code in a first iteration of the loop is used to further optimize a second iteration of the loop, and wherein the loop is further unrolled.

### Claim 9 (depends on 8)

The computer program product of claim 8, wherein selectively connecting unrolled loop iterations comprises:
connecting an exit block of the first iteration to an entry block of the second iteration, wherein the entry block of the first iteration is an equivalent point of the control flow to the entry block of the second iteration, and wherein edges from the first iteration are selectively redirected from the second iteration to the entry block of the first iteration.

### Claim 10 (depends on 8)

The computer program product of claim 8, wherein said selectively connecting unrolled loop iterations comprises:
classifying the edges of the control flow as undesirable using predetermined criteria comprising cold or rarely executed paths, paths of the control flow containing calls and calls including virtual calls, failed side of a runtime inlined method guard, and paths which throw and catch exceptions.

### Claim 11 (depends on 8)

The computer program product of claim 8, wherein said extending a sequence of blocks on the path of hot code comprises:
removing runtime method tests;
constraining side-effects of the calls and predetermined elements of the control flow to a region of the loop executed less than a predetermined number of times relative to other respective regions of the loop; and
modifying, by the optimizer, regions of the loop executed more than a predetermined number of times relative to the other respective regions of the loop.

### Claim 12 (depends on 8)

The computer program product of claim 8, wherein the hot code blocks for which most of an execution time of the program is spent, and code blocks which are executed more often relative to other code blocks in the program, and wherein the cold code comprises code blocks for which less of the execution time of the respective program is spent, relative to the other code blocks in the respective program and code blocks which are executed less often relative to other code blocks in the respective program.

### Claim 13 (depends on 8)

The computer program product of claim 8, wherein said loop unrolling is performed with respect to a language selected from the group consisting of a managed runtime language, a scripting environment language, and a procedural language.

### Claim 14 (depends on 8)

The computer program product of claim 8, wherein said redirecting comprises redirecting edges of the control flow associated with the cold path to the loop header and edges of the control flow associated with the hot path to connect to the next iteration to form a segregation of the control flow that enables the information computed by the optimizer about a hot code sequence of the first iteration to further optimize the second, unrolled iteration.

### Claim 15

A computer system, comprising one or more processors, one or more memories, and one or more computer readable hardware storage devices, said one or more hardware storage device containing program instructions executable by the one or more processors via the one or more memories to implement a method for partial connection of iterations during loop unrolling during compilation of a program by a compiler, said method comprising:
selectively connecting, by the one or more processors during the compilation, unrolled loop iterations of a loop in the program, wherein said selectively connecting unrolled loop iterations comprises redirecting, to the head of the loop, edges of a control flow for the program that are classed as undesirable from one iteration of the loop to a next iteration of the loop, and wherein the head of the loop and a start of a replicated loop body of the loop are equivalent points of the control flow for the program;
removing, by the one or more processors during the compilation, merges on a path of hot code in the loop to increase a scope for optimization of the program; and
extending, by the one or more processors during the compilation, a sequence of blocks on the path of hot code, unpolluted by a control flow of a path of cold code, wherein information computed by an optimizer in or invoked by the compiler about the hot code in a first iteration of the loop is used to further optimize a second iteration of the loop, and wherein the loop is further unrolled.

### Claim 16 (depends on 15)

The computer system of claim 15, wherein selectively connecting unrolled loop iterations comprises:
connecting an exit block of the first iteration to an entry block of the second iteration, wherein the entry block of the first iteration is an equivalent point of the control flow to the entry block of the second iteration, and wherein edges from the first iteration are selectively redirected from the second iteration to the entry block of the first iteration.

### Claim 17 (depends on 15)

The computer system of claim 15, wherein said selectively connecting unrolled loop iterations comprises:
classifying the edges of the control flow as undesirable using predetermined criteria comprising cold or rarely executed paths, paths of the control flow containing calls and calls including virtual calls, failed side of a runtime inlined method guard, and paths which throw and catch exceptions.

### Claim 18 (depends on 15)

The computer system of claim 15, wherein said extending a sequence of blocks on the path of hot code comprises:
removing runtime method tests;
constraining side-effects of the calls and predetermined elements of the control flow to a region of the loop executed less than a predetermined number of times relative to other respective regions of the loop; and
modifying, by the optimizer, regions of the loop executed more than a predetermined number of times relative to the other respective regions of the loop.

### Claim 19 (depends on 15)

The computer system of claim 15, wherein the hot code blocks for which most of an execution time of the program is spent, and code blocks which are executed more often relative to other code blocks in the program, and wherein the cold code comprises code blocks for which less of the execution time of the respective program is spent, relative to the other code blocks in the respective program and code blocks which are executed less often relative to other code blocks in the respective program.

### Claim 20 (depends on 15)

The computer system of claim 15, wherein said redirecting comprises redirecting edges of the control flow associated with the cold path to the loop header and edges of the control flow associated with the hot path to connect to the next iteration to form a segregation of the control flow that enables the information computed by the optimizer about a hot code sequence of the first iteration to further optimize the second, unrolled iteration.
