Summary: reg. alloc. and instr. sched

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 <berson@cs.pitt.edu>
David Neto <neto@csri.toronto.edu>
sc@idec02.inf.uni-jena.de (Sebastian Schmidt)
Steve <snovack@enterprise.ICS.UCI.EDU>
Stephen J Bevan <bevan@cs.man.ac.uk>
Timo Metzemakers <metzemak@labri.u-bordeaux.fr>
janh@voltaire.et.tudelft.nl (J. Hoogerbrugge)
andi@mips.complang.tuwien.ac.at (Andi Krall)
Rajiv Gupta <gupta@cs.pitt.edu>


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.




@PhDThesis{HSU:1987,
            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"
}


@conference{GOO:HSU:1988,
            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"
}


@conference{SMFJCRcgctt91,
            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


@conference{BRA:EGG:HEN:1991,
            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"
}


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


@InProceedings{ambrosch+94,
    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\%."
}


@Proceedings{plsa94,
    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


@InProceedings{rau+92,
    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."
}


@inproceedings
{ 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
``compiled''."
}


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


3 references


@inproceedings{Berson93,
          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
Parallelism},
          MONTH = {January},
          TITLE = {URSA: A Unified ReSource Allocator for Registers and Functional
Units in VLIW Architectures},
          YEAR = {1993}
}


3 references


@techreport{Berson94,
          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}
}


@inproceedings{EbNa89,
          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
}


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


@inproceedings{NPW91,
          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}
}


@techreport{NoNi92b,
          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
scheduling},
          YEAR = {1992}
}




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


2 references


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




@Article{frantsuzov:91,
    author = "Yu.A. Frantsuzov",
    title = "Code scheduling with delayed register allocation",
    journal = Programmirovanie,
    pages = "58--66",
    year = "1991",
}


3 references


@Article{pinter:93,
    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
                                  execution.",
}


---------------------------------------------------------------------------
Nandakumar Sankaran (nandu@cs.clemson.edu) (nsankar@hubcap.clemson.edu)
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
--

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