Re: quotation source sought

paris.Berkeley.EDU!larus@ucbvax.Berkeley.EDU (James Larus)
10 Aug 88 15:55:53 GMT

          From comp.compilers
Related articles
quotation source sought wendt@arizona.edu (Alan Wendt) (1988-08-08)
Re: quotation source sought paris.Berkeley.EDU!larus@ucbvax.Berkeley.EDU (1988-08-10)
| List of all articles for this month |
From: paris.Berkeley.EDU!larus@ucbvax.Berkeley.EDU (James Larus)
Newsgroups: comp.compilers
Date: 10 Aug 88 15:55:53 GMT
References: <1987@ima.ISC.COM>

In article <1987@ima.ISC.COM>, wendt@arizona.edu (Alan Wendt) writes:
> From: wendt@arizona.edu (Alan Wendt)
> Subject: quotation source sought
> Date: 9 Aug 88 03:07:58 GMT
> Lines: 16
> Approved: compilers@ima.UUCP
>
> Does anyone know the source of the following statement,
> needed for a citation:
>
> Register allocation is trivial if instructions have been selected
> and ordered, because live ranges are known exactly. And instruction
> selection is easy if registers have been allocated. But since
> both cannot be done first, code generation in general (including
> both register allocation and instruction selection) is NP-complete.


I can't supply the source of the quote, but I can object to its
content. Register allocation is equivalent (i.e., reducible to) graph
coloring, which is an NP-complete problem---even after instructions
have been selected. If you look at graph coloring register allocators
(i.e., Chow), the first thing that they do is to compute the live
ranges and then they heuristically solve the coloring problem.


/Jim


ucbvax!larus
larus@ginger.Berkeley.EDU
--

Post a followup to this message

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