Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!cs.utexas.edu!rice!news
From: preston@ariel.rice.edu (Preston Briggs)
Newsgroups: comp.arch
Subject: Re: Register Count
Message-ID: <1991Jan15.172335.12695@rice.edu>
Date: 15 Jan 91 17:23:35 GMT
References: <25106@dime.cs.umass.edu> <1991Jan14.233249.21161@rice.edu> <25118@dime.cs.umass.edu>
Sender: news@rice.edu (News)
Organization: Rice University, Houston
Lines: 64

I wrote optimal spill choice being undecidable

>>)>Because the path actually taken through the code can't, in general,
>>)>be known at compile-time.

And yodaiken@chelm.cs.umass.edu (victor yodaiken) writes:

>>)Still don't see it.  The system state, i.e. contents of store and registers,
>>)appears to determine the path taken through a piece of code. 

And Mark Hall (my former officemate) expanded

>>   I think preston is referring to programs which read input in the 
>> phrase "in general".
>> 
>>   Can you predict the state of registers for all possible 
>> (possibly infinite) inputs streams? 

and Yodaiken continued

>Not personally, but in principle, it can be done. The input streams 
>comprise a regular language. Thus, we have a finite representation, and 
>we have some k, so that any input stream of length greater than k repeats
>state.  

We seem to be edging toward a little argument over trivia.

I was speculating about compiling a single subroutine,
where we have no knowledge (or very little knowledge)
about arguments, global memory, and input.
This seems to be a pretty typical starting point
for building (or thinking about) a compiler or optimizer.

So, if we see a stupid routine that looks like

	routine dumbcode(arg)
	  A
	  if arg = 0 then
	     B
	  else
	     C
	  endif
	  D
	  return
        end

and for some reason, there's enough register pressure that we must
choose to improve one of B or C at the expense of the other.
How can we choose?  I don't see how we can (with all the assumptions).

But if I've got enough registers, the question doesn't arise.
This allows a significant simplification in optimization:

    "Always assume you've got enough registers."

Probably due to John Cocke, this assumption allows us to avoid many hard
(and somtime undecidable) choices.

Machines with enough of registers make this a valid assumption.

Graph coloring allocators (that attempt to minimize the number of required
registers) make the assumption valid on more machines and more code.

Preston Briggs