Re: register allocation via graph coloring

preston@tera.com (Preston Briggs) writes:
|> I haven't read the paper (oops), but you mention one restriction,
|> namely "for a given schedule". This is the same sort of
|> simplification that Chaitin makes, I make, Chow&Hennessy make,
|> Callahan&Koblenz, make, etc. Interesting work that explores the
|> alternative (i.e., letting the schedule flex) includes
[deleted]


Also on this topic:


@InProceedings{bradlee+91asplos,
    author = "David G. Bradlee and Susan J. Eggers and Robert R. Henry",
    title = "Integrating Register Allocation and Instruction
Scheduling for {RISCs}",
    crossref = "asplos91",
    pages = "122--131"
}


@Proceedings{asplos91,
    key = "ASPLOS-IV",
    title = "Architectural Support for Programming Languages and
Operating Systems (ASPLOS-IV)",
    booktitle = "Architectural Support for Programming Languages and
Operating Systems (ASPLOS-IV)",
    year = "1991",
}


@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.
Secondly, during colouring the register selection
keeps dependence paths short, ensuring good
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}"
}


- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
--

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