Method for optimizing computer code to provide more efficient execution on computers having cache memories
First Claim
1. A method for operating a digital computer, including a memory for the storage of computer instructions and data, to convert a first computer program to a second computer program, said first computer program comprising a set of basic blocks of computer code arranged in a first linear order and said second computer program comprising a second set of basic blocks in a second linear order, each basic block of said second set of basic blocks being derived from one of said basic blocks of said first set of basic blocks, said method comprising the steps of:
- (a) determining the frequency with which each basic block of said first set of basic blocks transfers control to each other basic block of said first set of basic blocks when said first computer program is executed with test data;
(b) providing an indicator for each pair of said basic blocks of said first set of basic blocks having a determined transfer frequency greater than zero, each said indicator having a first state and a second state, each said indicator being initialized to said first state;
(c) determining which pair of basic blocks of said first set of basic blocks for which said indicator corresponding to said pair is in said first state has the largest transfer frequency and setting said indicator corresponding to said pair to said second state;
(d) combining a pair of chains of said first set of basic blocks to form a new chain which replaces said pair of chains if a source basic block for said pair of chains is the tail of one of said chains and a target basic block is the head of the other of said chains, said source basic block and target basic block being said pair of basic blocks determined in step (c);
(e) repeating steps (c) and (d) until all said indicators are in said second state; and
(f) arranging said chains in a linear order to generate said second computer program.
2 Assignments
0 Petitions
Accused Products
Abstract
The method uses statistical information obtained by running the computer code with test data to determine a new ordering for the code blocks. The new order places code blocks that are often executed after one another close to one another in the computer'"'"'s memory. The method first generates chains of basic blocks, and then merges the chains. Finally, basic blocks that were not executed by the test data that was used to generate the statistical information are moved to a distant location to allow the blocks that were used to be more closely grouped together.
188 Citations
6 Claims
-
1. A method for operating a digital computer, including a memory for the storage of computer instructions and data, to convert a first computer program to a second computer program, said first computer program comprising a set of basic blocks of computer code arranged in a first linear order and said second computer program comprising a second set of basic blocks in a second linear order, each basic block of said second set of basic blocks being derived from one of said basic blocks of said first set of basic blocks, said method comprising the steps of:
-
(a) determining the frequency with which each basic block of said first set of basic blocks transfers control to each other basic block of said first set of basic blocks when said first computer program is executed with test data; (b) providing an indicator for each pair of said basic blocks of said first set of basic blocks having a determined transfer frequency greater than zero, each said indicator having a first state and a second state, each said indicator being initialized to said first state; (c) determining which pair of basic blocks of said first set of basic blocks for which said indicator corresponding to said pair is in said first state has the largest transfer frequency and setting said indicator corresponding to said pair to said second state; (d) combining a pair of chains of said first set of basic blocks to form a new chain which replaces said pair of chains if a source basic block for said pair of chains is the tail of one of said chains and a target basic block is the head of the other of said chains, said source basic block and target basic block being said pair of basic blocks determined in step (c); (e) repeating steps (c) and (d) until all said indicators are in said second state; and (f) arranging said chains in a linear order to generate said second computer program. - View Dependent Claims (2, 3, 4)
-
-
5. In a digital computer system including a computer memory, a method for causing said digital computer system to load a computer program comprising a plurality of procedures, wherein at least some of said procedures when executed by said computer system call others of said procedures, into said computer memory, said method comprising the steps of:
-
(a) determining the frequency with which each procedure calls each other procedure in said computer program; and (b) placing said procedures in said computer'"'"'s memory in an order that depends on said determined frequencies, wherein said step of placing said procedures comprises the steps of; (c) defining groups of said procedures, each group initially comprising one of said procedures, each group being defined as being determined or incompletely determined, said groups being initially defined to be incompletely determined; (d) defining a weight for each pair of said groups, said weight initially being the determined frequency with which said procedure in one group of said each pair called said procedure in the other group of said each pair; (e) combining a pair of said groups having the highest weight to form a new group which replaces each group in said pair of groups; (f) determining an order for the procedures in said new group if one of the groups in said combined pair was defined as being incompletely determined, said new group being defined as being determined if an order is determined for all procedures in said new group, and being defined as incompletely determined otherwise; (g) defining weight for each pair of groups containing said new group, is said weight being the sum of the frequencies with which said new group called the other group in said each pair of groups; and (h) repeating steps (e) through (g) until only one group remains, the order in which said procedures are loaded into said computer memory being determined by the order of said procedures in said remaining group. - View Dependent Claims (6)
-
Specification