Granted Patent B2

US 12,632,299 · App. 18/344,345 · Granted May 19, 2026

Inventors: Nicole Khoun (Whitby, CA); Wei Wang (Yorktown Heights, NY); Prasanth Chatarasi (White Plains, NY)

Assignee: International Business Machines Corporation

G06F9/5016

Abstract

Claims (90)

1 . A computer-implemented method of induction variable replacement (IVR), the method comprising:

using a number of processors to perform:

identifying an IVR candidate in a program loop comprising a linearly chained series of eligible operations, wherein the IVR candidate is a derived induction variable derived from a basic induction variable in the program loop;

converting a composite memory operation that directly uses the IVR candidate to a unified form, wherein offset information and increment information are separated from the composite memory operation;

identifying a scalar add operation that precedes

the composite memory operation in the linearly chained series of eligible operations, the scalar add operation having a constant operand;

swapping constant values associated with the IVR candidate and the scalar add operation;

converting the composite memory operation in the unified form to a composite memory operation having an increment that accommodates the scalar add operation; moving the scalar add operation to a bottommost position within the linearly chained series of eligible operations using instruction merging;

substituting the basic induction variable with the IVR candidate in the program loop;

updating a yield value of the program loop based on a control flow resulting from the substitution of the IVR candidate for the basic induction variable;

moving a calculation of the basic induction variable outside the program loop; and

adjusting a result value produced by the program loop such that program behavior prior to IVR is preserved.

2 . The method of claim 1 , wherein identifying the IVR candidate in the program loop further comprises:

identifying the basic induction variable in the program loop;

determining that the basic induction variable is used by a derived induction variable via the scalar add or subtract operation having a constant operand; and

determining that the derived induction variable is used by the composite memory operation eligible for instruction merging.

3 . The method of claim 1 , wherein moving the scalar add operation to the bottommost position within the linearly chained series of eligible operations comprises:

merging a first scalar add or subtract operation in the linearly chained series through at least one subsequent instruction; and

repeating the merging until the first scalar add or subtract operation is merged through a last instruction in the linearly chained series of eligible operations.

4 . The method of claim 1 , wherein the substituting of the basic induction variable with the IVR candidate further comprises:

manipulating the IVR candidate to produce an equation equivalent to the basic induction variable;

replacing the basic induction variable using the equation; and

shifting constant terms to a right side of the equation.

5 . The method of claim 1 , further comprising executing bottom-up instruction merging prior to IVR, wherein the bottom-up instruction merging comprises:

merging a bottommost scalar add or subtract operation in the linearly chained series through a preceding instruction; and

repeating the merging until the bottommost scalar add or subtract operation is merged through a topmost instruction in the linearly chained series.

6 . The method of claim 1 , wherein the linearly chained series of eligible operations comprises: composite memory operations having constant values; and scalar add or subtract operations each having one constant operand, and wherein each operation in the linearly chained series directly consumes an output of a preceding operation in the linearly chained series.

7 . The method of claim 1 , further comprising transforming an operation in the linearly chained series of eligible operations by:

responsive to a determination that the operation is a composite memory operation, setting an offset of the composite memory operation to a new offset equal to an original offset minus an increment value minus a constant operand value; and

responsive to determining that the operation is a scalar add or subtract operation, removing the scalar add or subtract operation from the linearly chained series and

inserting a new scalar add operation before a first operation in the series.

8 . A system for induction variable replacement (IVR), the system comprising:

a storage device that stores program instructions;

one or more processors operably connected to the storage device and configured to execute the program instructions to cause the system to:

identify an IVR candidate in a program loop comprising a linearly chained series of eligible operations, wherein the IVR candidate is a derived induction variable derived from a basic induction variable in the program loop;

convert a composite memory operation that directly uses the IVR candidate to a unified form, wherein offset information and increment information are separated from the composite memory operation;

identifying a scalar add operation that precedes the composite memory operation in the linearly chained series of eligible operations, the scalar add operation having a constant operand; swap constant values associated with the IVR candidate and the scalar add operation;

convert the composite memory operation in the unified form to a composite memory operation having an increment that accommodates the scalar add operation; and move the scalar add operation to a bottommost position within the linearly chained series of eligible operations using instruction merging;

substitute the basic induction variable with the IVR candidate in the program loop;

update a yield value of the program loop based on a control flow resulting from the substitution of the IVR candidate for the basic induction variable;

move a calculation of the basic induction variable outside the program loop; and

adjust a result value produced by the program loop such that program behavior prior to IVR is preserved.

9 . The system of claim 8 , wherein the program instructions to identify the IVR candidate in the program loop further cause the system to:

identify the basic induction variable in the program loop;

determine that the basic induction variable is used by a derived induction variable via the scalar add or subtract operation having a constant operand; and

determine that the derived induction variable is used by the composite memory operation eligible for instruction merging.

10 . The system of claim 8 , wherein the program instructions to move the scalar add operation to the bottommost position within the linearly chained series eligible operations cause the system to:

merge a first scalar add or subtract operation in the linearly chained series of through at least one subsequent instruction; and

repeat the merging until the first scalar add or subtract operation is merged through a last instruction in the linearly chained series of eligible operations.

11 . The system of claim 8 , wherein the program instructions to substitute the basic induction variable with the IVR candidate further cause the system to:

manipulate the IVR candidate to produce an equation equivalent to the basic induction variable;

replace the basic induction variable using the equation; and

shift constant terms to a right side of the equation.

12 . The system of claim 8 , further comprising program instructions to cause the system to execute bottom-up instruction merging prior to IVR, wherein the bottom-up instruction merging causes the system to:

merge a bottommost scalar add or subtract operation in the linearly chained series through a preceding instruction; and

repeat the merging until the bottommost scalar add or subtract operation is merged through a topmost instruction in the linearly chained series.

13 . The system of claim 8 , wherein the program instructions further cause the system to transform an operation in the linearly chained series of eligible operations by:

responsive to a determination that the operation is a composite memory operation, setting an offset of the composite memory operation to a new offset equal to an original offset minus an increment value minus a constant operand value; and

responsive to determining that the operation is a scalar add or subtract operation, removing the scalar add or subtract operation from the linearly chained series and

inserting a new scalar add operation before a first operation in the linearly chained series.

14 . A computer program product for induction variable replacement (IVR), the computer program product comprising:

a persistent storage medium having program instructions configured to cause one or more processors to:

identify an IVR candidate in a program loop comprising a linearly chained series of eligible operations, wherein the IVR candidate is a derived induction variable derived from a basic induction variable in the program loop;

convert a composite memory operation that directly uses the IVR candidate to a unified form, wherein offset information and increment information are separated from the composite memory operation;

identify a scalar add operation that precedes the composite memory operation in the linearly chained series of eligible operations, the scalar add operation having a constant operand; swapping constant values associated with the IVR candidate and the scalar add operation;

convert the composite memory operation in the unified form to a composite memory operation having an increment that accommodates the scalar add operation;

moving the scalar add operation to a bottommost position within the linearly chained series of eligible operations using instruction merging;

substitute the basic induction variable with the IVR candidate in the program loop;

update a yield value of the program loop based on a control flow resulting from the substitution of the IVR candidate for the basic induction variable;

move a calculation of the basic induction variable outside the program loop; and

adjust a result value produced by the program loop such that program behavior prior to IVR is preserved.

15 . The computer program product of claim 14 , wherein the program instructions to identify the IVR candidate in the program loop further cause the processors to:

identify the basic induction variable in the program loop;

determine that the basic induction variable is used by a derived induction variable via a scalar add or subtract operation having a constant operand; and

determine that the derived induction variable is used by a composite memory operation eligible for instruction merging.

16 . The computer program product of claim 14 , wherein the program instructions to move the scalar add operation to the bottommost position within the linearly chained series of eligible operations cause the processors to:

merge a first scalar add or subtract operation in the linearly chained series through at least one subsequent instruction; and

repeat the merging until the first scalar add or subtract operation is merged through a last instruction in the linearly chained series of eligible operations.

17 . The computer program product of claim 14 , wherein the program instructions to substitute the basic induction variable with the IVR candidate further cause the processors to:

manipulate the IVR candidate to produce an equation equivalent to the basic induction variable;

replace the basic induction variable using the equation; and

shift constant terms to a right side of the equation.

18 . The computer program product of claim 14 , further comprising program instructions to cause the processors to execute bottom-up instruction prior to IVR, wherein the bottom-up instruction merging causes the processors to:

merge a bottommost scalar add or subtract operation in the linearly chained series through a preceding instruction; and

repeat the merging until the bottommost scalar add or subtract operation is merged through a topmost instruction in the linearly chained series.

19 . The computer program product of claim 14 , wherein the linearly chained series of eligible operations comprises: composite memory operations having constant values; and scalar add or subtract operations each having one constant operand, and wherein each operation in the linearly chained series directly consumes an output of a preceding operation in the linearly chained series.

20 . The computer program product of claim 14 , wherein the program instructions further cause the processors to transform an operation in the linearly chained series of eligible operations by:

responsive to a determination that the operation is a composite memory operation, setting an offset of the composite memory operation to a new offset equal to an original offset minus an increment value minus a constant operand value; and

responsive to determining that the operation is the scalar add or subtract operation, removing the scalar add or subtract operation from the linearly chained series and

inserting a new scalar add operation before a first operation in the series.

Assignments (1)

Continuity (1)

References Cited (26)