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.