Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!elroy.jpl.nasa.gov!decwrl!world!iecc!compilers-sender
From: preston@ariel.rice.edu (Preston Briggs)
Newsgroups: comp.compilers
Subject: Re: C Compilers which use full 486 capabilities
Keywords: C, design, assembler
Message-ID: <1991Mar19.234108.25208@rice.edu>
Date: 19 Mar 91 23:41:08 GMT
References: <wbsAAQr0BwwMR4Tu8E@transarc.com> <1991Mar15.173551.13702@rice.edu> <15501@june.cs.washington.edu>
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: preston@ariel.rice.edu (Preston Briggs)
Organization: Rice University, Houston
Lines: 89
Approved: compilers@iecc.cambridge.ma.us

pardo@cs.washington.edu (David Keppel) writes:

about exchange instructions (finding uses, not really defending to the death)

>Here is code that the compiler could recognize as using exchange.  I
>saw this code yesterday in a data compression algorithm:
>
>	t := prev_val;
>	prev_val := a[i];
>	a[i] := t;
>
>A reasonable implementation could make use of exchange, and a simple
>peephole optimizer could replace instances of
>
>	mov rx, ry
>	ld rx, addr
>	st ry addr
>with
>	xchg rx, addr
>
>(as long as `ry' is not used subsequently).

I wouldn't have constrained prev_val to be in rx before and after.
Instead, realize that prev_val actually denotes 2 disjoint live
ranges.  Therefore

	-- prev_val in rx
	ld ry, addr
	st rx, addr
	-- prev_val in ry

with both registers surviving.
However, the code might contained in a loop and the two appearances of
prev_val actually part of one live range.  In this case, I'd need
the extra move at some point.



>  I can imagine a register
>allocator that instead of doing spills and restores with
>
>	mov r0, -46[fp]
>	mov -50[fp], r0
>
>figures out the lifetimes of the variables, figures out that they're
>disjoint (after all, the stack slots got generated in the first place
>becase there weren't enough empty registers...), creates one merged
>stack slot, and replaces the above with
>
>	xchg  r0, -44[fp]
>
>This has advantages of (a) smaller code size and (b) better stack
>locality (decreasing the stack size and increasing the utilization of
>particular stack slots).  Note that no analysis of user code is needed
>for this latter operation, the spills and restores are compiler-generated.

Please don't make me do this!

The problem of merging spill locations is just graph coloring all over again
(the figure out lifetimes and note when they're disjoint).  Then you require
the register colors to match and the stack locations to match.

Besides being difficult, the 1st version (separate load and store) has the
advantage that we can attempt to schedule the load in advance of its use
(especially if it turns out we've overspilled slightly, which happens).

I can imagine a 3rd use (which I also don't expect to generate).  We might
have parameters passed in registers, with the 1st parameter in r1, the 2nd
in r2, and so forth.  Given the following source:

	void zip(i, j)
	    int i, j;
	{
	    ...
	    zap(j, i);
	    ...
	}

using moves alone requires going through memory or another register.

I guess I believe that exchange is just a little too CISCish for my taste;
tiny payoffs and hard to use.  Of course, the synchronization case
is very important, but I'd expect that to be hidden in a system routine
and code in assembler.

Preston Briggs
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.