Arranging binary code based on call graph partitioning
Mechanisms are provided for arranging binary code to reduce instruction cache conflict misses. These mechanisms generate a call graph of a portion of code. Nodes and edges in the call graph are weighted to generate a weighted call graph. The weighted call graph is then partitioned according to the weights, affinities between nodes of the call graph, and the size of cache lines in an instruction cache of the data processing system, so that binary code associated with one or more subsets of nodes in the call graph are combined into individual cache lines based on the partitioning. The binary code corresponding to the partitioned call graph is then output for execution in a computing device.
1. A computer program product comprising a non-transitory computer readable storage medium having a computer readable program stored therein, wherein the computer readable program, when executed on a data processing system, causes the data processing system to:
generate a call graph of a portion of code;
weight nodes and edges in the call graph to generate a weighted call graph;
partition the weighted call graph according to the weights, affinities between nodes of the call graph, and the size of cache lines in an instruction cache of the data processing system, so that binary code associated with one or more subsets of nodes in the call graph are combined into individual cache lines based on the partitioning; and
output the binary code corresponding to the partitioned call graph for execution in a computing device, wherein each node in the call graph is weighted according to a size of code associated with the node and each edge in the call graph is weighted according to an estimate of a number of calls between nodes of the edge, and wherein partitioning the weighted call graph comprises performing the following operations iteratively until an edge having a maximum weight cannot be selected from unprocessed edges of the weighted call graph:
selecting an edge from the unprocessed edges of the weighted call graph that has a maximum weight of the weights of the unprocessed edges;
determining if nodes of the selected edge should be merged into a new node or not; and
merging the nodes of the selected edge into a new node in response to a determination that the nodes of the selected edge should be merged.
2. The computer program product of claim 1 , wherein if an edge having a maximum weight in the unprocessed edges cannot be selected, remaining procedures associated with remaining nodes connected to unprocessed edges are combined into a single node in a single cache line.
3. The computer program product of claim 1 , wherein determining if nodes of the selected edge should be merged into a new node or not comprising comparing weights of the nodes of the selected edge to a predetermined size of a cache line of an instruction cache of the data processing system.
4. The computer program product of claim 3 , wherein comparing weights of the nodes of the selected edge to the predetermined size of the cache line comprises:
comparing a sum of the weights of the nodes to the predetermined size of the cache line; and
in response to the sum of the weights of the nodes being less than or equal to the predetermined size of the cache line, merging the nodes into a new node.
5. The computer program product of claim 4 , wherein merging the nodes into a new node further comprises:
setting a weight of the new node equal to a sum of the weights of the nodes of the selected edge;
setting, for each other node coupled by an edge to one of the nodes of the selected edge, a weight of the edge to a sum of the weights of the edges between the other node and a corresponding one of the nodes of the selected edge; and
eliminating the selected edge from the weighted call graph.
6. The computer program product of claim 4 , wherein, in response to the sum of the weights of the nodes not being less than or equal to the predetermined size of the cache line, marking the selected edge as processed.
7. The computer program product of claim 1 , wherein each of the nodes in the call graph of the portion of code represent objects of the portion of code that utilize direct target jump operations.
8. An apparatus, comprising:
a processor; and
a memory coupled to the processor, wherein the memory comprises instructions that configure the processor to:
generate a call graph of a portion of code;
weight nodes and edges in the call graph to generate a weighted call graph;
partition the weighted call graph according to the weights, affinities between nodes of the call graph, and the size of cache lines in an instruction cache of the data processing system, so that binary code associated with one or more subsets of nodes in the call graph are combined into individual cache lines based on the partitioning; and
output the binary code corresponding to the partitioned call graph for execution in a computing device, wherein each node in the call graph is weighted according to a size of code associated with the node and each edge in the call graph is weighted according to an estimate of a number of calls between nodes of the edge, and wherein partitioning the weighted call graph comprises performing the following operations iteratively until an edge having a maximum weight cannot be selected from unprocessed edges of the weighted call graph:
selecting an edge from the unprocessed edges of the weighted call graph that has a maximum weight of the weights of the unprocessed edges;
determining if nodes of the selected edge should be merged into a new node or not; and
merging the nodes of the selected edge into a new node in response to a determination that the nodes of the selected edge should be merged.
9. The apparatus of claim 8 , wherein if an edge having a maximum weight in the unprocessed edges cannot be selected, the processor is configured to combine remaining procedures associated with remaining nodes connected to unprocessed edges into a single node in a single cache line.
10. The apparatus of claim 8 , wherein the processor is configured to determine if nodes of the selected edge should be merged into a new node or not at least by comparing weights of the nodes of the selected edge to a predetermined size of a cache line of an instruction cache of the data processing system.
11. The apparatus of claim 10 , wherein the processor is configured to compare weights of the nodes of the selected edge to the predetermined size of the cache line at least by:
comparing a sum of the weights of the nodes to the predetermined size of the cache line; and
in response to the sum of the weights of the nodes being less than or equal to the predetermined size of the cache line, merging the nodes into a new node.
12. The apparatus of claim 11 , wherein the processor is configured to merge the nodes into a new node further by:
setting a weight of the new node equal to a sum of the weights of the nodes of the selected edge;
setting, for each other node coupled by an edge to one of the nodes of the selected edge, a weight of the edge to a sum of the weights of the edges between the other node and a corresponding one of the nodes of the selected edge; and
eliminating the selected edge from the weighted call graph.
13. The apparatus of claim 11 , wherein, in response to the sum of the weights of the nodes not being less than or equal to the predetermined size of the cache line, the processor is configured to mark the selected edge as processed.
14. The apparatus of claim 8 , wherein each of the nodes in the call graph of the portion of code represent objects of the portion of code that utilize direct target jump operations.