Automatically assigned DDC number: 005453
Manually assigned DDC number: 005453

Number of references: 4

Title: Zero-cost Range Splitting

Author:

Author:

Subject: Steven M. Kurlander,Charles N. Fischer Zero-cost Range Splitting

Description: This paper presents a new optimization technique that uses empty delay slots to improve code scheduling. We are able to split live ranges for free, by inserting spill code into empty delay slots. Splitting a live range can reduce interferences with other live ranges and can sometimes free registers. Live ranges no longer interfering with the split live range can sometimes make use of the extra register. Our algorithm, as a final pass over the code, exploits empty delay slots that would remain unused if spill code was not inserted. This paper proposes a variety of optimizations that use the extra registers generated from live range splitting, including coalescing live ranges and improving code scheduling. We present an algorithm for improving code scheduling and present implementation results. 1 Introduction Compiler writers use heuristics for register allocation and instruction scheduling, as both are NP-Complete [Set75] [HG82] [PS90]. Instruction scheduling tries to minimize the numb...

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1998-08-17

Pubyear: 1994

Format: ps

Identifier: http://citeseer.ist.psu.edu/141800.html

Source: http://www.cs.wisc.edu/~fischer/zero-cost.ps

Language: en

Relation:

Relation:

Relation:

Relation:

Rights: unrestricted

Graph

<?xml version="1.0" encoding="UTF-8"?>

<references_metadata>

<rec ID="/221670.html" Type="inproceedings" CiteSeer_Book="SIGPLAN Conference on Programming Language Design and Implementation" CiteSeer_Volume="" Title="Improving Register Allocation for Subscripted Variables,">

<identifier Org="ISBN:0262050668" Paper_ID="/221670.html" Extracted="0262050668" DDC="004/.068/5" Normalized_DDC="0040685" Normalized_Weight="0.0625" />

<identifier Org="ISBN:0521582741" Paper_ID="/221670.html" Extracted="0521582741" DDC="005.4/53" Normalized_DDC="005453" Normalized_Weight="0.0625" />

<identifier Org="ISBN:0780304942" Paper_ID="/221670.html" Extracted="0780304942" />

<identifier Org="ISBN:0792393678" Paper_ID="/221670.html" Extracted="0792393678" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.0625" />

<identifier Org="ISBN:0849301920" Paper_ID="/221670.html" Extracted="0849301920" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.0625" />

<identifier Org="ISBN:1402075286" Paper_ID="/221670.html" Extracted="1402075286" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.0625" />

<identifier Org="ISBN:3540212973" Paper_ID="/221670.html" Extracted="3540212973" DDC="005.4/53" Normalized_DDC="005453" Normalized_Weight="0.0625" />

<identifier Org="ISBN:3540223770" Paper_ID="/221670.html" Extracted="3540223770" DDC="004.2/2" Normalized_DDC="00422" Normalized_Weight="0.0625" />

<identifier Org="ISBN:3540425128" Paper_ID="/221670.html" Extracted="3540425128" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.0625" />

<identifier Org="ISBN:3540539042" Paper_ID="/221670.html" Extracted="3540539042" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.0625" />

<identifier Org="ISBN:3540541519" Paper_ID="/221670.html" Extracted="3540541519" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.0625" />

<identifier Org="ISBN:354060765X" Paper_ID="/221670.html" Extracted="354060765X" DDC="005.4/53" Normalized_DDC="005453" Normalized_Weight="0.0625" />

<identifier Org="ISBN:3540616268" Paper_ID="/221670.html" Extracted="3540616268" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.0625" />

<identifier Org="ISBN:3540657177" Paper_ID="/221670.html" Extracted="3540657177" DDC="005.4/53" Normalized_DDC="005453" Normalized_Weight="0.0625" />

<identifier Org="ISBN:3540676686" Paper_ID="/221670.html" Extracted="3540676686" DDC="005.13/1" Normalized_DDC="005131" Normalized_Weight="0.0625" />

<identifier Org="ISBN:3540693297" Paper_ID="/221670.html" Extracted="3540693297" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.0625" />

<identifier Org="ISBN:3540715274" Paper_ID="/221670.html" Extracted="3540715274" DDC="621.39" Normalized_DDC="62139" Normalized_Weight="0.0625" />

</rec>

<rec ID="/42742.html" Type="techreport" CiteSeer_Book="" CiteSeer_Volume="" Title="A Retargetable Compiler for {ANSI} {C},">

<identifier Org="ISBN:0306467860" Paper_ID="/42742.html" Extracted="0306467860" DDC="621.39/16" Normalized_DDC="6213916" Normalized_Weight="0.1" />

<identifier Org="ISBN:052103311X" Paper_ID="/42742.html" Extracted="052103311X" DDC="005.453" Normalized_DDC="005453" Normalized_Weight="0.1" />

<identifier Org="ISBN:0546665896" Paper_ID="/42742.html" Extracted="0546665896" />

<identifier Org="ISBN:0780325540" Paper_ID="/42742.html" Extracted="0780325540" />

<identifier Org="ISBN:0818671777" Paper_ID="/42742.html" Extracted="0818671777" DDC="004.35" Normalized_DDC="00435" Normalized_Weight="0.1" />

<identifier Org="ISBN:0818675489" Paper_ID="/42742.html" Extracted="0818675489" DDC="621.39/5" Normalized_DDC="621395" Normalized_Weight="0.1" />

<identifier Org="ISBN:1558607021" Paper_ID="/42742.html" Extracted="1558607021" DDC="004.16" Normalized_DDC="00416" Normalized_Weight="0.1" />

<identifier Org="ISBN:1880446677" Paper_ID="/42742.html" Extracted="1880446677" />

<identifier Org="ISBN:3540411720" Paper_ID="/42742.html" Extracted="3540411720" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.1" />

<identifier Org="ISBN:354043075X" Paper_ID="/42742.html" Extracted="354043075X" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.1" />

<identifier Org="ISBN:3540576592" Paper_ID="/42742.html" Extracted="3540576592" DDC="005.2" Normalized_DDC="0052" Normalized_Weight="0.1" />

<identifier Org="ISBN:3540617361" Paper_ID="/42742.html" Extracted="3540617361" DDC="005.2" Normalized_DDC="0052" Normalized_Weight="0.1" />

<identifier Org="ISBN:3540633715" Paper_ID="/42742.html" Extracted="3540633715" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.1" />

<identifier Org="ISBN:3540708804" Paper_ID="/42742.html" Extracted="3540708804" />

<identifier Org="ISBN:812032725X" Paper_ID="/42742.html" Extracted="812032725X" />

</rec>

<rec ID="/45071.html" Type="inproceedings" CiteSeer_Book="SIGPLAN Conference on Programming Language Design and Implementation" CiteSeer_Volume="" Title="Register Allocation with Instruction Scheduling: A New Approach,">

<identifier Org="ISBN:0769510191" Paper_ID="/45071.html" Extracted="0769510191" DDC="004.2/2" Normalized_DDC="00422" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:0792352939" Paper_ID="/45071.html" Extracted="0792352939" DDC="519.7/6" Normalized_DDC="51976" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:0818657855" Paper_ID="/45071.html" Extracted="0818657855" DDC="004.2" Normalized_DDC="0042" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:0818671262" Paper_ID="/45071.html" Extracted="0818671262" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:0818673494" Paper_ID="/45071.html" Extracted="0818673494" DDC="005.6" Normalized_DDC="0056" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:081868108X" Paper_ID="/45071.html" Extracted="081868108X" />

<identifier Org="ISBN:084931240X" Paper_ID="/45071.html" Extracted="084931240X" DDC="005.4/53" Normalized_DDC="005453" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:0897916905" Paper_ID="/45071.html" Extracted="0897916905" />

<identifier Org="ISBN:0897917073" Paper_ID="/45071.html" Extracted="0897917073" />

<identifier Org="ISBN:0898713498" Paper_ID="/45071.html" Extracted="0898713498" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:1558607021" Paper_ID="/45071.html" Extracted="1558607021" DDC="004.16" Normalized_DDC="00416" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:3540009043" Paper_ID="/45071.html" Extracted="3540009043" DDC="005.4/53" Normalized_DDC="005453" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:354041861X" Paper_ID="/45071.html" Extracted="354041861X" />

<identifier Org="ISBN:3540578404" Paper_ID="/45071.html" Extracted="3540578404" DDC="005.13" Normalized_DDC="00513" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:3540603212" Paper_ID="/45071.html" Extracted="3540603212" DDC="005.2" Normalized_DDC="0052" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:3540610537" Paper_ID="/45071.html" Extracted="3540610537" DDC="005.4/53" Normalized_DDC="005453" Normalized_Weight="0.08333333333333333" />

<identifier Org="ISBN:3540678581" Paper_ID="/45071.html" Extracted="3540678581" />

</rec>

<rec ID="/289623.html" Type="inproceedings" CiteSeer_Book="Proceedings of the ACM SIGPLAN 86 Symposium on Compiler Construction" CiteSeer_Volume="" Title="Global register allocation at link-time,">

<identifier Org="ISBN:0818607769" Paper_ID="/289623.html" Extracted="0818607769" DDC="004.22" Normalized_DDC="00422" Normalized_Weight="0.1" />

<identifier Org="ISBN:0818608056" Paper_ID="/289623.html" Extracted="0818608056" />

<identifier Org="ISBN:0818670940" Paper_ID="/289623.html" Extracted="0818670940" DDC="004.2/4/011" Normalized_DDC="00424011" Normalized_Weight="0.1" />

<identifier Org="ISBN:0818679778" Paper_ID="/289623.html" Extracted="0818679778" DDC="005.6" Normalized_DDC="0056" Normalized_Weight="0.1" />

<identifier Org="ISBN:084931240X" Paper_ID="/289623.html" Extracted="084931240X" />

<identifier Org="ISBN:0897913949" Paper_ID="/289623.html" Extracted="0897913949" DDC="004.2/2" Normalized_DDC="00422" Normalized_Weight="0.1" />

<identifier Org="ISBN:1558603204" Paper_ID="/289623.html" Extracted="1558603204" DDC="005.4/53" Normalized_DDC="005453" Normalized_Weight="0.1" />

<identifier Org="ISBN:3540197575" Paper_ID="/289623.html" Extracted="3540197575" DDC="005.4/5" Normalized_DDC="00545" Normalized_Weight="0.1" />

<identifier Org="ISBN:3540559841" Paper_ID="/289623.html" Extracted="3540559841" DDC="005.4/53" Normalized_DDC="005453" Normalized_Weight="0.1" />

<identifier Org="ISBN:3540575022" Paper_ID="/289623.html" Extracted="3540575022" DDC="005.2" Normalized_DDC="0052" Normalized_Weight="0.1" />

<identifier Org="ISBN:354060054X" Paper_ID="/289623.html" Extracted="354060054X" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.1" />

<identifier Org="ISBN:3540625992" Paper_ID="/289623.html" Extracted="3540625992" />

<identifier Org="ISBN:3540657177" Paper_ID="/289623.html" Extracted="3540657177" DDC="005.4/53" Normalized_DDC="005453" Normalized_Weight="0.1" />

</rec>

<rec ID="SELF" Type="SELF" CiteSeer_Book="SELF" CiteSeer_Volume="SELF" Title="Zero-cost Range Splitting" />

</references_metadata>