# US 10,120,666 B2 · Conditional branch instruction compaction for regional code size reduction

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

- Number: US 10,120,666 B2
- Document ID: US10120666B2
- Status: Granted
- Kind: B2
- Application number: 15/047,161
- Filed: 2016-02-18
- Published: 2016-06-09
- Granted: 2018-11-06
- Earliest claimed: 2014-06-25
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Patrick R. Doyle; Vijay Sundaresan
- Web page: https://patentgrep.com/patent/US10120666B2

## CPC

- G06F 8/4442: {Reducing the number of cache misses; Data prefetching (cache prefetching G06F12/0862)}
- G06F 8/4434: {Reducing the memory space required by the program code}
- G06F 9/30054: {Unconditional branch instructions}
- G06F 9/30058: {Conditional branch instructions}
- G06F 9/30145: {Instruction analysis, e.g. decoding, instruction word fields}
- G06F 9/30181: {Instruction operation extension or modification}
- G06F 11/3466: {Performance evaluation by tracing or monitoring}
- G06F 11/302: {where the computing system component is a software system}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

In an approach for decreasing an execution time of a computer code, one or more processors identify a long-form conditional branch that is included in a first region of a computer code. The one or more processors generate a long-form unconditional branch with a target that is a target of a long-form conditional branch. The one or more processors modify the long-form conditional branch to be a short-form conditional branch. The one or more processors insert the long-form unconditional branch into the computer code within a branch distance of the short-form conditional branch. The one or more processors modify a target of the short-form conditional branch to be a location of the long-form unconditional branch in the computer code.

## Claims

### Claim 1

A method for decreasing an execution time of a computer code, the method comprising:
identifying, by one or more processors, a long-form conditional branch that is included in a first executed region of a computer code;
responsive to a determination that the first executed region is executed frequently, determining, by one or more processors, whether the long-form conditional branch in the first executed region of the computer code is infrequently taken; and
responsive to a determination that the long-form conditional branch is infrequently taken, initiating, by the one or more processors, modification of the long-form conditional branch to be the short-form conditional branch by:
generating, by the one or more processors, a long-form unconditional branch with a target that is a target of the long-form conditional branch;
modifying, by the one or more processors, the long-form conditional branch to be a short-form conditional branch;
inserting, by the one or more processors, the long-form unconditional branch into the computer code within a branch distance of the short-form conditional branch; and
modifying, by the one or more processors, a target of the short-form conditional branch to be a location of the long-form unconditional branch in the computer code.

### Claim 2 (depends on 1)

The method of claim 1, wherein one or more of: (i) the long-form conditional branch is converted into a short-form conditional branch that branches to a trampoline unconditional branch that is inserted into a puddle, wherein the puddle is a group of consecutive trampoline unconditional branches that serve as targets for one or more short-form conditional branches that replace one or more long-form unconditional branches, (ii) the puddle is located immediately following a basic block that cannot transfer control to the puddle, wherein the last instruction in the basic block is an unconditional branch, (iii) the long-form conditional branch is converted into the short-form conditional branch that branches to an unconditional branch that in turn branches to the target of the long-form conditional branch, (iv) the long-form conditional branch is located at an exit point of a first basic block that branches to an entry point of a second basic block, and (v) wherein the first basic block and the second basic block are executed more frequently than an average frequency of execution relative to other basic blocks.

### Claim 3 (depends on 1)

The method of claim 1, the method comprising:
receiving, by the one or more processors, the computer code; and
determining, by the one or more processors, whether the first executed region of the computer code is executed frequently.

### Claim 4 (depends on 1)

The method of claim 1, wherein the inserting, by one or more processors, the long-form unconditional branch into the computer code within a branch distance of the short-form conditional branch comprises:
selecting, by the one or more processors, a location to insert the long-form unconditional branch in the computer code, wherein the location is within the branch distance of the short-form conditional branch and the location immediately follows an unconditional branch in the computer code; and
inserting, by the one or more processors, the long-form unconditional branch at the location in the computer code.

### Claim 5 (depends on 1)

The method of claim 1, the method comprising:
executing, by the one or more processors, the computer code; and
monitoring, by the one or more processors, executed computer code for the first executed region of the computer code.

### Claim 6 (depends on 1)

The method of claim 1, the method comprising:
executing, by the one or more processors, the computer code;
determining, by the one or more processors, that a first basic block and a second basic block are expected to be executed frequently relative to other basic blocks; and
monitoring, by the one or more processors, executed computer code for the long-form conditional branch in the first executed region of the computer code, wherein the long-form conditional branch is located at an exit point of the first basic block that branches to an entry point of the second basic block.

### Claim 7

A computer program product for decreasing an execution time of a computer code, the computer program product comprising:
one or more computer readable storage media and program instructions stored on the one or more computer readable storage media, the program instructions comprising:
program instructions to identify a long-form conditional branch that is included in a first executed region of a computer code;
program instructions to respond to a determination that the first executed region is executed frequently by determining whether the long-form conditional branch in the first executed region of the computer code is infrequently taken; and
program instructions to respond to a determination that the long-form conditional branch is infrequently taken by initiating modification of the long-form conditional branch to be the short-form conditional branch by executing:
program instructions to generate a long-form unconditional branch with a target that is a target of the long-form conditional branch;
program instructions to modify the long-form conditional branch to be a short-form conditional branch;
program instructions to insert the long-form unconditional branch into the computer code within a branch distance of the short-form conditional branch; and
program instructions to modify a target of the short-form conditional branch to be a location of the long-form unconditional branch in the computer code.

### Claim 8 (depends on 7)

The computer program product of claim 7, wherein one or more of: (i) the long-form conditional branch is converted into a short-form conditional branch that branches to a trampoline unconditional branch that is inserted into a puddle, wherein the puddle is a group of consecutive trampoline unconditional branches that serve as targets for one or more short-form conditional branches that replace one or more long-form unconditional branches, (ii) the puddle is located immediately following a basic block that cannot transfer control to the puddle, wherein the last instruction in the basic block is an unconditional branch, (iii) the long-form conditional branch is converted into the short-form conditional branch that branches to an unconditional branch that in turn branches to the target of the long-form conditional branch, (iv) the long-form conditional branch is located at an exit point of a first basic block that branches to an entry point of a second basic block, and (v) wherein the first basic block and the second basic block are executed more frequently than an average frequency of execution relative to other basic blocks.

### Claim 9 (depends on 7)

The computer program product of claim 7, the program instructions comprising:
program instructions to receive the computer code; and
program instructions to determine whether the first executed region of the computer code is executed frequently.

### Claim 10 (depends on 7)

The computer program product of claim 7, wherein the program instructions to insert the long-form unconditional branch into the computer code within a branch distance of the short-form conditional branch comprises:
program instructions to select a location to insert the long-form unconditional branch in the computer code, wherein the location is within the branch distance of the short-form conditional branch and the location immediately follows an unconditional branch in the computer code; and
program instructions to insert the long-form unconditional branch at the location in the computer code.

### Claim 11 (depends on 7)

The computer program product of claim 7, the program instructions comprising:
program instructions to execute the computer code; and
program instructions to monitor executed computer code for the first executed region of the computer code.

### Claim 12 (depends on 7)

The computer program product of claim 7, the program instructions comprising:
program instructions to execute the computer code;
program instructions to determine that a first basic block and a second basic block are expected to be executed frequently relative to other basic blocks; and
program instructions to monitor executed computer code for the long-form conditional branch in the first executed region of the computer code, wherein the long-form conditional branch is located at an exit point of the first basic block that branches to an entry point of the second basic block.

### Claim 13

A computer system for decreasing an execution time of a computer code, the computer system comprising:
one or more computer processors;
one or more computer readable storage media; and
program instructions stored on the computer readable storage media for execution by at least one of the one or more processors, the program instructions comprising:
program instructions to identify a long-form conditional branch that is included in a first executed region of a computer code;
program instructions to respond to a determination that the first executed region is executed frequently by determining whether the long-form conditional branch in the first executed region of the computer code is infrequently taken; and
program instructions to respond to a determination that the long-form conditional branch is infrequently taken by initiating modification of the long-form conditional branch to be the short-form conditional branch by executing:
program instructions to generate a long-form unconditional branch with a target that is a target of the long-form conditional branch;
program instructions to modify the long-form conditional branch to be a short-form conditional branch;
program instructions to insert the long-form unconditional branch into the computer code within a branch distance of the short-form conditional branch; and
program instructions to modify a target of the short-form conditional branch to be a location of the long-form unconditional branch in the computer code.

### Claim 14 (depends on 13)

The computer system of claim 13, wherein one or more of: (i) the long-form conditional branch is converted into a short-form conditional branch that branches to a trampoline unconditional branch that is inserted into a puddle, wherein the puddle is a group of consecutive trampoline unconditional branches that serve as targets for one or more short-form conditional branches that replace one or more long-form unconditional branches, (ii) the puddle is located immediately following a basic block that cannot transfer control to the puddle, wherein the last instruction in the basic block is an unconditional branch, (iii) the long-form conditional branch is converted into the short-form conditional branch that branches to an unconditional branch that in turn branches to the target of the long-form conditional branch, (iv) the long-form conditional branch is located at an exit point of a first basic block that branches to an entry point of a second basic block, and (v) wherein the first basic block and the second basic block are executed more frequently than an average frequency of execution relative to other basic blocks.

### Claim 15 (depends on 13)

The computer system of claim 13, the program instructions comprising:
program instructions to receive the computer code; and
program instructions to determine whether the first executed region of the computer code is executed frequently.

### Claim 16 (depends on 13)

The computer system of claim 13, wherein the program instructions to insert the long-form unconditional branch into the computer code within a branch distance of the short-form conditional branch comprises:
program instructions to select a location to insert the long-form unconditional branch in the computer code, wherein the location is within the branch distance of the short-form conditional branch and the location immediately follows an unconditional branch in the computer code; and
program instructions to insert the long-form unconditional branch at the location in the computer code.

### Claim 17 (depends on 13)

The computer system of claim 13, the program instructions comprising:
program instructions to execute the computer code;
program instructions to determine that a first basic block and a second basic block are expected to be executed frequently relative to other basic blocks; and
program instructions to monitor executed computer code for the long-form conditional branch in the first executed region of the computer code, wherein the long-form conditional branch is located at an exit point of the first basic block that branches to an entry point of the second basic block.