Re: Evaluation Tech. Needed for Register Allocation

yhshiau@csie.nctu.edu.tw (Yuh-Horng Shiau(dcp78804)) writes:
> I'm studying register allocation. I have given a new definition
>of live ranges for symbolic registers used in intermediate code. But I
>don't know how to evaluate it.


Well, you compare it with older approaches. I'm not sure exacly what you
mean by "a new definition of live ranges" so I can't advise you directly.
Generally though, you'd want to compare against Chaitin's definition
described in


    title="Register Allocation via Coloring",
    author="Gregory J. Chaitin and Marc A. Auslander and Ashok K. Chandra and
                    John Cocke and Martin E. Hopkins and Peter W. Markstein",
    journal="Computer Languages",
    volume=6,
    year=1981,
    month=jan,
    pages="47--57"


You'd basically need to make arguments on paper about why yours is better
(simply "new" isn't very interesting). Typical arguments might be that it
is cheaper to compute (in time or space) or more precise (somehow supports
more accurate coloring).


To get really wide acceptance, you'll probably have to do experimental
comparisons of your approach against some established approach. This is
fairly difficult to do convincingly since you end up needing to build two
register allocators and do a good job on both.


In my own experiments, I've always compared two closely related allocators
-- allocators differing in only one small respect. To compare against a
completely different allocator would be quite a bit more difficult.


There aren't really any standard benchmarks for such work. We used
Fortran routines, mostly collected from the Spec benchmark suite.


If you want to compare against a Chaitin-style allocator (the whole
allocator, not just the definition of live ranges), you'll want to use our
improvements as a standard. They're described in


    title="Coloring Heuristics for Register Allocation",
    author="Preston Briggs and Keith D. Cooper and Ken Kennedy
                and Linda Torczon",
    journal=sigplan,
    year=1989,
    month=jul,
    volume=24,
    number=7,
    note=pldi89,
    pages="275--284"


    title="Rematerialization",
    author="Preston Briggs and Keith D. Cooper and Linda Torczon",
    pages="311--321",
    journal=sigplan,
    year=1992,
    month=july,
    volume=27,
    number=7,
    note=pldi92


Of course, if you want to compare against other techniques, you'll want to
be sure to include all the appropriate improvements.


Preston Briggs
--

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