Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!samsung!ernie.viewlogic.com!m2c!umvlsi!dime!yodaiken
From: yodaiken@chelm.cs.umass.edu (victor yodaiken)
Newsgroups: comp.arch
Subject: Re: Register Count
Message-ID: <25106@dime.cs.umass.edu>
Date: 14 Jan 91 21:15:52 GMT
References: <11566@pt.cs.cmu.edu> <1991Jan14.163739.10786@rice.edu> <25090@dime.cs.umass.edu> <1991Jan14.191057.14242@rice.edu>
Sender: news@dime.cs.umass.edu
Reply-To: yodaiken@chelm.cs.umass.edu (victor yodaiken)
Organization: University of Massachusetts, Amherst
Lines: 27

In article <1991Jan14.191057.14242@rice.edu> preston@ariel.rice.edu (Preston Briggs) writes:
>I wrote:
>>>
>>>Optimality sounds like a fine reason to have lots of registers,
>>>especially since optimal choices by the compiler are undecidable.
>
>and yodaiken@chelm.cs.umass.edu (victor yodaiken) writes:
>>How's that? The compiler is allocating a finite set of resources. How
>>can this problem be undecidable? Dificult, yes; Intractable, maybe; but
>>I don't see where undecidability would come from. Did I miss something here?
>
>Because the path actually taken through the code can't, in general,
>be known at compile-time.
>
>Preston Briggs

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. 
If we have k registers of n bits each, memory
addresss in the range of 0 - 2^l for some l, where each memory word
holds  m bits plus some other stuff: then we get  approx 
x = 2^(n*k)*2^( (2^l -1)*m) + C  possible states 
(C represents things like carry bits etc).
Thus, in principle, we can check each possible path code. 
Where is the undecidability? In practice, we won't really have to check all
paths. See, H. Massalin " Superoptimizer: A look at the smallest
program" (ASPLOS II 1987) for a nice example of this principle in practice.