Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!rpi!uwm.edu!uwvax!primost.cs.wisc.edu!larus From: larus@primost.cs.wisc.edu (James Larus) Newsgroups: comp.arch Subject: Re: Register Count Message-ID: <1991Jan16.145923.23399@spool.cs.wisc.edu> Date: 16 Jan 91 14:59:23 GMT References: <11566@pt.cs.cmu.edu> Sender: news@spool.cs.wisc.edu (The News) Reply-To: larus@cs.wisc.edu Organization: University of Wisconsin--Madison Lines: 15 I believe that Preston is correct is claiming that register allocation is an undecidable problem. It can be shown with a simple varient of Turing's halting argument (see disclaimers below): Consider a function F that contains two parts: an arbitrary computation C and another (register-intensive) computation C' procedure F () C; C'; If C does not halt then a register allocator should allocate all registers to C since C' will never be executed and this will `minimize' the computation time. However, if C halts, then the registers should be divided more equitably between C and C'. A register allocator that could make this choice for an aribtrary computation C solves the Turing halting problem. The big problem with this argument is that the behavior of register allocators on non-terminating programs is (always?) left unspecified. Also, as someone noted, real computers are not Turing machines with infinite tapes, so in theory the number of states that a real computer can reach is finite and all we have to do is look for a repetition in the sequence of states to detect an infinite loop. Of course, in practice, a machine with a non-trivial amount of memory has too many states to make this argument sensible. /Jim