Re: Evaluation Tech. Needed for Register Allocation

Dear Sir,


                Thanks for your response. Instead of defining a live range based
on single touchstone, such as instruction number in Chaitin's algorithm
and basic block number in the priority-based algorithm (proposed by Chow
and Hennessy), we define a live range by using a two-dimensional
representation (T, B). Where T is a global time stamp for each
instruction in considering, and B is the basic block number that contains
the instruction in considering. For example,


        +--------+
        | |
        | sr <- | Symbolic register sr is first defined in time Td in block B1.
        | |
        +--------+
                |
                V
        +--------+
        | |
        | <- sr | Symbolic register sr is last used in time Tu in block B2.
        | |
        +--------+


The live range of symbolic register sr is defined as a set of pairs as
follows:


                LR(sr) = {(T, B) | Td <= T <= Tu, B <= {B1, B2}} (simplified).


Using this definition, we can exhibit the real life time of a symbolic
register (Td --> Tu) that instruction number and basic block number cannot
exhibit.


                With a different definition on live ranges, we design an algorithm
based on graph coloring techniques. To evaluate the performance (spill
cost intro- duced, execution time, etc.) of the algorithm, are there any
other evaluation techniques that can be used to evaluate it easily and
soundly, instead of benchmarking (compiling some benchmark programs with
the proposed algorithm)?


                I am looking forward to further comments.


Sincerely yours,
Yuh-Horng Shiau, 1993/05/25


--
Yuh-Horng Shiau yhshiau@csie.nctu.edu.tw, yhshiau@arch9.csie.nctu.edu.tw
Inst. of Computer Science and Information Engineering
National Chiao Tung University
Hsinchu, Taiwan 30050, Republic of China
--

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