Back to results
US 8,555,270 B2Granted
Profile-based global live-range splitting
AssigneeInternational Business Machines Corporation
InventorsTakuya Nakaike, Tatsushi Inagaki, Hideaki Komatsu
Life of this patent
Estimating the term…
Abstract
A method and system are provided for splitting a live-range of a variable in frequently executed regions of program instructions. The live-range of a variable is split into multiple sub-ranges, each of which can be assigned to a different register or spilled into memory. The amount of spill code is reduced in frequently used regions of code by coalescing the live ranges based on profile information obtained after splitting the live ranges at every join and fork point in a control flow graph.
Claims6
A method for minimizing spill code in hot regions comprising:
- splitting each live range of a variable into multiple sub-ranges on all edges leading to joint points and all edges coming from fork points in a control flow graph before coloring nodes in a corresponding interference graph, wherein a portion of sub-ranges is inactive;
- profiling each sub-range based upon traversal of a basic building block of said control flow graph;
- selecting frequently executed regions of code;
- limiting a process of coalescing sub-ranges to said selected frequently executed regions of code based upon profiles thereby removing copies dividing initial live ranges into sub-ranges in said frequently executed regions and absent coalescing in regions other than said frequently executed regions;
- and
- selecting a set of sub-ranges in less used regions for spilling into memory, absent spilling any sub-ranges during the coloring phase and absent leaving any redundant sub-ranges to the coloring phase, wherein said sub-ranges are selected initially from those classified as significant-inactive and secondarily from those classified as significant-active.
3 more elements
A method for minimizing spill code in hot regions comprising:
- splitting each live range of a variable into multiple sub-ranges on all edges leading to joint points and all edges coming from fork points in a control flow graph before coloring nodes in a corresponding interference graph, including creating two adjacent sub-ranges which are split on an edge between two basic building blocks that have similar execution frequencies;
- profiling each sub-range based upon traversal of a basic building block of said control flow graph;
- selecting frequently executed regions of code;
- limiting a process of coalescing sub-ranges to said selected frequently executed regions of code based upon profiles thereby removing copies dividing initial live ranges into sub-ranges in said frequently executed regions;
- and
- selecting a set of sub-ranges in less used regions for spilling into memory, absent spilling any sub-ranges during the coloring phase and absent leaving any redundant sub-ranges to the coloring phase, wherein said sub-ranges are selected initially from those classified as significant-inactive and secondarily from those classified as significant-active.
3 more elements
A method for minimizing spill code in hot regions comprising:
- splitting each live range of a variable into multiple sub-ranges on all edges leading to joint points and all edges coming from fork points in a control flow graph before coloring nodes in a corresponding interference graph;
- analyzing a sub-range by assigning a category to said sub-ranges based upon activity of said sub-range across a saturation point, wherein said category is selected from a group consisting of:
- inactive, active, significant inactive, and significant active;
- selecting frequently executed regions of code;
- limiting a process of coalescing sub-ranges to said selected frequently executed regions of code based upon profiles thereby removing copies dividing initial live ranges into sub-ranges in said frequently executed regions and absent coalescing in regions other than said frequently executed regions;
- and
- selecting a set of sub-ranges in less used regions for spilling into memory, absent spilling any sub-ranges during the coloring phase and absent leaving any redundant sub-ranges to the coloring phase, wherein said sub-ranges are selected initially from those classified as significant-inactive and secondarily from those classified as significant-active.
4 more elements
Dependencies are inferred from the claim text.