Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!bu.edu!m2c!umvlsi!dime!yodaiken
From: yodaiken@chelm.cs.umass.edu (victor yodaiken)
Newsgroups: comp.arch
Subject: Re: Register Count
Message-ID: <25154@dime.cs.umass.edu>
Date: 15 Jan 91 20:07:52 GMT
References: <25106@dime.cs.umass.edu> <1991Jan14.233249.21161@rice.edu> <25118@dime.cs.umass.edu> <1991Jan15.172335.12695@rice.edu>
Sender: news@dime.cs.umass.edu
Reply-To: yodaiken@chelm.cs.umass.edu (victor yodaiken)
Organization: University of Massachusetts, Amherst
Lines: 38

In article <1991Jan15.172335.12695@rice.edu> preston@ariel.rice.edu (Preston Briggs) writes:
>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).
>

If we don't know how many registers we have, or how much program 
memory is addressable, then certainly we cannot hope to optimize
register use. But, if we are taking this code and generating machine
code that will run on  machine X with some limit of adressable memory
per process, and some known number of registers, then we can in principle
minimize register spilling. This is simply because machine X is a finite
state system, and finite state machines can be minimized effectively.
This does not mean that we can necessarily find  a practical algorithm which
will solve the register spilling problem for some class of interesting 
computers and some programming lanugage. But,  there is no theoretical
result which says that such algorithms do not exist. If we were building
a compiler for a turing machine, then we would have a problem, but
generally, we work with much more limited machines.