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>

www.000webhost.com