Summary: reg. alloc. and instr. sched
Sat, 9 Apr 1994 15:25:55 GMT

          From comp.compilers

Related articles
Register Allocation and Instruction Scheduling (1994-03-23)
Summary: reg. alloc. and instr. sched (1994-04-09)
| List of all articles for this month |

Newsgroups: comp.compilers
Keywords: registers, optimize, bibliography, summary
Organization: Compilers Central
References: 94-03-101
Date: Sat, 9 Apr 1994 15:25:55 GMT

I has posted a message sometime back asking for references to literature
that discusses the pros and cons of performing Instruction Scheduling and
Register Allocation in conjunction. Thanks to all those replied:

David A. Berson <>
David Neto <> (Sebastian Schmidt)
Steve <snovack@enterprise.ICS.UCI.EDU>
Stephen J Bevan <>
Timo Metzemakers <> (J. Hoogerbrugge) (Andi Krall)
Rajiv Gupta <>

Some of them were even kind enough to annote the references. The
following are the pointers I received. If more than one pointer was
obtained, the exact number is listed above the reference.

            Author = "Wei-Chung Hsu",
            Title = Register Allocation and Code Scheduling for
                                    Load\discretionary {-}{}{/}Store Architectures",
            School = "University of Wisconsin- Madsion",
            Year = 1987,
            Month = Oct,
            Note = "Computer Science Technical Report \#722"

            author = "Goodman, James R. and Hsu, Wei-Chung ",
            title = "Code scheduling and register allocation in large
                                      basic blocks ",
            booktitle = "Proceedings of the International Conference
                                                on Supercomputing",
            year = 1988,
            month = Jul,
            address = "St. Malo, France",
            pages = "442--452"

            author = "Freudenberger, Stefan M. and Ruttenberg, John C.",
          title = "Place Ordering of Register Allocation and
                                    Instruction Scheduling",
            booktitle = "Code Generation---Concepts, Tools and Techniques",
          year = 1991,

2 references

            author = "${}^{\clubsuit}$Bradlee, David G. and Eggers,
                                      Susan J. and Henry, Robert R.",
            title = "Integrating Register allocation and instruction
                                      scheduling for {RISC}s",
            booktitle = ASPLOS,
            year = 1991,
            month = Apr # " 8--11",
            pages = "122--131",
            organisation = ACM,
            address = "Santa Clara, California",
            note = "Issue 26(4),1991 of SIGPLAN Notices"

            author = "${}^{\clubsuit}$Norris, C. and Pollock, L. L. ",
            title = "A Scheduler-sensitive Global Register Allocator",
            booktitle = "Proceedings of the International Conference on
            year = 1993,
            month = nov,
            address = "Portland, Oregon",
            pages = "804--813"

    author = "Wolfgang Ambrosch and M. Anton Ertl and Felix Beer
                                    and Andreas Krall",
    title = "Dependence-Conscious Global Register Allocation",
    crossref = "plsa94",
    pages = "125--136",
    abstract = "Register allocation and instruction scheduling are
                                    antagonistic optimizations: Whichever is applied
                                    first, it will impede the other. To solve this problem, we
                                    propose dependence-conscious colouring, a register
                                    allocation method that takes the dependence graph
                                    used by the instruction scheduler into
                                    consideration. Dependence-conscious colouring
                                    consists of two parts: First, the interference graph
                                    is built by analysing the dependence graphs,
                                    resulting in fewer interference edges and less
                                    spilling than the conventional preordering approach.
                                    Second, during colouring the register selection
                                    keeps dependence paths short, ensuring good
                                    scheduling.\comment{ Finally, spill cost estimates
                                    become more accurate by considering the effects of
                                    instruction scheduling.} Dependence-conscious
                                    colouring reduces the number of interference edges
                                    by 7\%--24\% and antidependences by 46\%--100\%."

    title = "Programming Languages and System Architectures",
    booktitle = "Programming Languages and System Architectures",
    year = "1994",
    key = "PLSA",
    editor = "J{\"u}rg Gutknecht",
    publisher = "Springer LNCS~782",
    address = "{Z\"urich}"

2 references

    author = "B. R. Rau and M. Lee and P. P. Tirumalai and
M. S. Schlansker",
    title = "Register Allocation for Software Pipelined Loops",
    crossref = "sigplan92",
    pages = "283--299",
    OPTnote = "The problem of register allocation in modulo
                                  scheduled loops is to allocate the registers in a way
                                  that minimizes register idle time. The constraints
                                  on allocations depend on the code generation strategy
                                  (hardware support, preconditioning vs.\ multiple loop
                                  exits etc.). Registers are heuristically
                                  allocated to lifetimes in a heuristically determined
                                  order. The best heuristics work very well and produce
                                  allocations at or near the lower bound. Therefore the
                                  authors recommend choosing a code generation strategy
                                  that minimizes the produced code."

{ Karr:acmcc:1984
, author= "Michael Karr"
, title= "Code Generation by Coagulation"
, crossref= "acmcc:1984"
, pages= "1--12"
, checked= 19940202
, source= "dept. library"
, sjb= "Aims to solve the problem represented by the cliche that
``instruction selection is trivial once register allocation is done,
and register allocation is trivial once instruction selection is
done.'' by narrowing down the area being ``compiled'' such that it is
small enough for both to be done at the same time. These small pieces
are then joined to form larger pieces (coagulation) until the whole
program has been compiled. At the time the paper was written, the
approach had not been implemented."
, abstract= "This paper describes a new approach to code-generation.
The central tenet is that there must be a more intimate coupling
between register allocation and instruction selection than exists in
present-day technology. This is achieved by generating code in very
small regions and gradually coalescing the part of the program that is

{ acmcc:1984
, title= "Proceedings of the SIGPLAN '84 Symposium on Compiler
, booktitle= "Proceedings of the SIGPLAN '84 Symposium on Compiler
, organization= "ACM"
, year= 1984
, publisher= "ACM"
, source= "Dept. library"
, note= "SIGPLAN Notices 19(6)"

3 references

          ADDRESS = {Orlando, FL},
          AUTHOR = {D. Berson and R. Gupta and M.L. Soffa},
          BOOKTITLE = {Proceedings of the IFIP Working Conference on Architectures
and Compilation Techniques for Fine and Medium Grain
          MONTH = {January},
          TITLE = {URSA: A Unified ReSource Allocator for Registers and Functional
Units in VLIW Architectures},
          YEAR = {1993}

3 references

          ADDRESS = {Computer Science Department},
          AUTHOR = {D. Berson and R. Gupta and M.L. Soffa},
          INSTITUTION = {University of Pittsburgh},
          NUMBER = {94-09},
          TITLE = {Resource Spackling: A Framework for Integrating Register
          Allocation in Local and Global Schedulers},
          YEAR = {1994}

          ADDRESS = {Urbana, IL},
          AUTHOR = {K. Ebcioglu and T. Nakatani},
          BOOKTITLE = {Proceedings of the 2nd Workshop on Programming Languages and
                    Compilers for Parallel Computing},
          TITLE = {A New Compilation Technique for Parallelizing Loops with
                  Unpredictable Branches on a VLIW Architecture},
          YEAR = 1989

          ADDRESS = {Portland, OR},
          AUTHOR = {S. Moon and K. Ebcioglu},
          BOOKTITLE = {Proceedings of the 25th Annual International Symposium on
          MONTH = {December},
          TITLE = {An Efficient Resource Constrained Global Scheduling Technique
for Superscalar and VLIW processors},
          YEAR = {1992}

          AUTHOR = {A.~Nicolau and R.~Potasman and H.~Wang},
          BOOKTITLE = {Proceedings of the 4th International Workshop on Languages
          and Compilers for Parallel Processing},
          TITLE = {Register allocation, renaming and their impact on parallelism},
          YEAR = {1991}

          AUTHOR = {S. Novack and A. Nicolau},
          INSTITUTION = {University of California at Irvine},
          NOTE = {Also appears in the Proceedings of the 1993 International
Conference on Parallel Processing, St. Charles, IL., August 1993},
          NUMBER = {TR-92-56},
          TITLE = {Trailblazing: A hierarchical approach to percolation
          YEAR = {1992}

@Article{ bradlee:91a,
    author = "David G.~Bradlee and Susan J.~Eggers and Robert
    title = "The marion system for retargetable instruction
    volume = 26,
    number = "6",
    pages = "229--240",
    note = pldi91,
    journal = sigplan,
    year = 1991,
    month = jun,
    organization = acm,
    address = "Toronto, Ontario, Canada"

2 references

    author = "David Gordon Bradlee",
    title = "Retargetable Instruction Scheduling for Pipelined
    school = "University of Washington",
    year = "1991",
    crossref = "bradlee:91a",
    annote = "Design and evaluation of the Marion retargetable
instruction scheduler"

    author = "Yu.A. Frantsuzov",
    title = "Code scheduling with delayed register allocation",
    journal = Programmirovanie,
    pages = "58--66",
    year = "1991",

3 references

    author = "Schlomit S. Pinter",
    title = "Register Allocation with Instruction Scheduling: {A}
                                  New Approach",
    pages = "248--257",
    journal = sigplan,
    year = "1993",
    month = jun,
    volume = "28",
    number = "6",
    note = pldi93,

@Tutorial{ lam:92,
    crossref = pldi92,
    title = "Instruction Scheduling",
    author = "Monica Lam and Michael Smith",
    annote = "The first part of this tutorial discussed control and
                                  data dependence constraints for instruction scheduling
                                  on machines with instruction level parallelism (i.e.
                                  i860, R4000, SuperSPARC, Alpha, RS6000). There was a
                                  review of cycle vs. operation scheduling and the
                                  interaction between register allocation and instruction
                                  scheduling. The recommended method was an integrated
                                  register allocation and instruction scheduler. The
                                  second topic dealt with higher level scheduling.
                                  Methods for code motion and duplication were discussed.
                                  Several global code schedulers were reviewed. The
                                  proposed algorithms were for machines with small
                                  amounts of processor level parallelism (4 processor
                                  multiprocessor). Hardware assistance was also
                                  discussed. The third topic was software pipelining -
                                  unrolling loops in order to interleave operations which
                                  the machine can do in parallel. Methods for handling
                                  both acyclic and cyclic control flow graphs were
                                  discussed. Suggestion was made that a mix of hardware
                                  and software scheduling was best - hardware should only
                                  provide interlocks and support for speculative

Nandakumar Sankaran ( (
311-8 Old Greenville Hwy. Clemson SC 29631-1651 (803)653-7749
G34 Jordan Hall Comp. Sci. Dept. Clemson Univ. SC 29634 (803)656-6979

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.