On Tue, 15 Jul 2003 21:08:03 +0100, you wrote:

>Jon,
>
>> Quick questions.
>> 
>> Do all the compilers use the same associations on the MSP430? 
>
>Nope.  Not at all.

As I'm gathering.

>> Or do each of them make choices unique to
themselves in some 
>> way?  (Is there a collective standard in operation, in other
>> words?)
>
>I think we all use slightly different calling conventions; I believe
>ours happens to be the most useful, of course.  :-)

Hehe.  Is there a doc on it I could look at?

>> Are there compiler options which will change
this particular 
>> choice, evidenced by the assembly output posted?
>
>Not to my knowledge.

Okay.

>The only thing that IAR will offer is to not use
>R4/R5 for ROM monitor compatibility.  (Why would anybody now purchase
>the monitor version of C-SPY, though?)

Don't ask me!

Jon

Hello Jonathan,

> 
> Other alternative?  A simple register allocator that doesn't
> look forward through a basic block, at all?  (Hmm.  Does anyone
> do global [across blocks] register allocation?)
> 

The Archelon/Quadravox AQ430 C compiler uses a graph colouring register
allocator which considers the whole function when allocating registers.
It builds a flow graph of the generated assembly code, builds use-definition
chains, and all that good stuff, so that it can do register allocation
across basic blocks.

All the best,

Preston Gurd
Archelon Inc.

At 11:16 AM 7/16/2003 -0700, Jonathan Kirwan wrote:
>...>Heh, mind you, I haven't really thought
about it, but from your posts, I
> >was thinking that perhaps there are some special things, may be like
you
> >can take advantage of the comparison already done so you can skip some
of
> >the later steps :-)
>
>I guess I'm not following, here.  What later steps?  What
>comparison already done?  What special things?  Your thoughts
>about me sound intriguing, but I just wish I'd been thinking
>some of them so I could claim credit.  :)

Oh, things like may be tracking the condition code so you don't have to 
actually redo a == 0 type of things.

>.....>1) I need to figure out why it's
doing that. It shouldn't and and 
>doesn't
> >on ICCAVR, so I have forgotten to tune something in the register
allocator
> >(yes, we have a register allocator too. We don't use coloring. I
wrote a
> >coloring register 10 years ago, didn't like it much, so I am now
reverting
> >to the other viable alternative).
>
>Other alternative?  A simple register allocator that doesn't
>look forward through a basic block, at all?  (Hmm.  Does anyone
>do global [across blocks] register allocation?)

Tsk tsk. Would I do that? :-) A register allocator implies at least 
function level across basic block allocation.

What I was referring to is not to do coloring. Chaitin "invented"
coloring 
back in 1982 or so, but there are other techniques. The major downside of 
coloring is that it is a heuristic and that it can potentially be a O(n**2) 
algorithm. In practice, it almost never is since most functions in an 
embedded has a very tiny number of potential virtual registers. In anycase, 
I just don't like it for its lack of certain elegance. Oh heck, I just 
wanted to play with the other register allocation schemes used by the 2 
different companies that I worked for: the Digital GEM compiler and the 
Intermetric embedded compilers.

Any case, it's called bin-packing, or linear lifetime register allocation. 
There is certain amount of mathematical elegance to it.

>...
>
>Thanks, Richard.  Wish you'd posted the assembly output, though.
>;)

I am hoping to fix the problems in the next day or so, so I can send out 
good example :-) I am working on some new stuff right now... (shhhh... :-) )

// richard <http://www.imagecraft.com> 
<http://www.dragonsgate.net/mailman/listinfo> 

All,

> >Other alternative?  A simple register
allocator that doesn't look 
> >forward through a basic block, at all?  (Hmm.  Does anyone do global 
> >[across blocks] register allocation?)
> 
> Tsk tsk. Would I do that? :-) A register allocator implies at least 
> function level across basic block allocation.
> 
> What I was referring to is not to do coloring. Chaitin 
> "invented" coloring 
> back in 1982 or so, but there are other techniques. The major 
> downside of 
> coloring is that it is a heuristic and that it can 
> potentially be a O(n**2) 
> algorithm. In practice, it almost never is since most functions in an 
> embedded has a very tiny number of potential virtual 
> registers. In anycase, 
> I just don't like it for its lack of certain elegance. Oh 
> heck, I just 
> wanted to play with the other register allocation schemes 
> used by the 2 
> different companies that I worked for: the Digital GEM 
> compiler and the 
> Intermetric embedded compilers.

IIRC, register coloring is covered by at least three software patents,
which makes it problematic to implement in a real compiler without the
necessary machinery in place to avoid the pitfalls of patent
infringement, and even the necessity of preparing to defend your own
creation in the case of a challenge.

Register coloring, in my experience, is a very neat solution.  It's
simple to understand for an ideal machine when there is no spilling
involved.  Not all machines are ideal though, and many of the textbooks
do *not* go into the things required to make register allocation and
assignment work in a real situation.  The knack, of course, is to find a
coloring with a minimal number of spills.  Appel's book is pretty good
in this respect, having an almost-working register allocator and
assigner.

As such, I haven't implemented a coloring register allocator in our
compiler.  To advertise such a thing might invite a challenge, which I
don't relish.  I have, of course, actually experimented with such an
allocator, but it's of no practical use (for me).

-- Paul.

Al,

> GCD:
> 	CMP	R14,R15		;CHECK IF A = B
> 	JNE	L1		;IF NOT SKIP TO OTHER TESTS
> 	CMP	#0,R15		;WERE THEY BOTH = 0?
> 	JNZ	L2		;IF NOT RETURN B = A != 0
> 	INC	R15		;ELSE RETURN B = 1
> L2:
> 	RET
> L1:
> 	CMP	#0,R15		;TEST FOR A != 0 B = 0
> 	JEQ	L6		;AND IF SO RETURN B = A;
> 	CMP	#0,R14		;TEST FOR A = 0 B != 0 RETURN B = B
> 	JZ	L2
> L3:

***

> 	CMP	R14,R15		;TEST IF R14 = R15 YET
> 	JC	L4		;IF B >= A THEN SUB A FROM B
> 	SUB	R15,R14		;ELSE R14 -= R15
> 	JMP	L5
> L4:
> 	SUB	R14,R15		;R15 -= R14
> L5:
> 	CMP	R14,R15
> 	JNZ	L3
> L6:
> 	MOV	R14,R15
> 	RET

***

The bits between the stars are easily rewritten:

_gcd1:
	sub.w   r15, r14
	jz      ret
	jc	  _gcd1
	add.w   r15, r14
	sub.w   r14, r15
	jmp     _gcd1
ret:    ret

This saves three instructions.

-- Paul.

On Wed, 16 Jul 2003 22:33:37 +0100, Paul wrote:

>> >Other alternative?  A simple register
allocator that doesn't look 
>> >forward through a basic block, at all?  (Hmm.  Does anyone do
global 
>> >[across blocks] register allocation?)
>> 
>> Tsk tsk. Would I do that? :-) A register allocator implies at least 
>> function level across basic block allocation.
>> 
>> What I was referring to is not to do coloring. Chaitin 
>> "invented" coloring 
>> back in 1982 or so, but there are other techniques. The major 
>> downside of 
>> coloring is that it is a heuristic and that it can 
>> potentially be a O(n**2) 
>> algorithm. In practice, it almost never is since most functions in an 
>> embedded has a very tiny number of potential virtual 
>> registers. In anycase, 
>> I just don't like it for its lack of certain elegance. Oh 
>> heck, I just 
>> wanted to play with the other register allocation schemes 
>> used by the 2 
>> different companies that I worked for: the Digital GEM 
>> compiler and the 
>> Intermetric embedded compilers.
>
>IIRC, register coloring is covered by at least three software patents,
>which makes it problematic to implement in a real compiler without the
>necessary machinery in place to avoid the pitfalls of patent
>infringement, and even the necessity of preparing to defend your own
>creation in the case of a challenge.
>
>Register coloring, in my experience, is a very neat solution.  It's
>simple to understand for an ideal machine when there is no spilling
>involved.  Not all machines are ideal though, and many of the textbooks
>do *not* go into the things required to make register allocation and
>assignment work in a real situation.  The knack, of course, is to find a
>coloring with a minimal number of spills.  Appel's book is pretty good
>in this respect, having an almost-working register allocator and
>assigner.
>
>As such, I haven't implemented a coloring register allocator in our
>compiler.  To advertise such a thing might invite a challenge, which I
>don't relish.  I have, of course, actually experimented with such an
>allocator, but it's of no practical use (for me).

Register coloring is also particularly useful in helping to
manage register spills, by the way.  So it's not just the case
that coloring is for ideal situations where spills don't take
place.  But I'm guessing that you meant this as part of "simple
to understand" in that context.

By the way, I'm COMPLTELY IGNORANT of patents in this regard.
However, I do remember reading about register coloring very
early on in my "compiler playing" days.  I can't pinpoint the
year, but my perhaps poor recollection is that it goes back to
roughly 1980, or so.  And that, being articles which were pretty
descriptive about it and not just random tidbits that would
later be collected under that title.

I also remember that the patent office was refusing software
patents until Reagan's administration, roughly.  But dates elude
me on that.

Anyway.  Thanks, Paul, for the discussion.  I enjoy thinking
about these things.

Jon

At 10:33 PM 7/16/2003 +0100, Paul Curtis wrote:
>...IIRC, register coloring is covered by at least
three software patents,
>which makes it problematic to implement in a real compiler without the
>necessary machinery in place to avoid the pitfalls of patent
>infringement, and even the necessity of preparing to defend your own
>creation in the case of a challenge.

Oh yea, darned pesky patents!

>Register coloring, in my experience, is a very neat
solution.  It's
>simple to understand for an ideal machine when there is no spilling
>involved.  Not all machines are ideal though, and many of the textbooks
>do *not* go into the things required to make register allocation and
>assignment work in a real situation.  The knack, of course, is to find a
>coloring with a minimal number of spills.  Appel's book is pretty good
>in this respect, having an almost-working register allocator and
>assigner.

Things to watch out for: register pair (although Preston Briggs has a paper 
on that, I believe), unorthogonal registers, etc.

>As such, I haven't implemented a coloring
register allocator in our
>compiler.  To advertise such a thing might invite a challenge, which I
>don't relish.  I have, of course, actually experimented with such an
>allocator, but it's of no practical use (for me).

The patents are somewhat stoopid. Oh well, I wrote mine before the patents 
were granted, and the products it was in, is no longer :-( Larger companies 
(e.g. Sun, HP etc.) must have patent cross-licensing so it's us small guys 
that suffer.

So what do you use, if I may ask?

// richard <http://www.imagecraft.com> 
<http://www.dragonsgate.net/mailman/listinfo> 

On Wed, 16 Jul 2003 16:00:58 -0700, Richard wrote:

><snip>
>The patents are somewhat stoopid. Oh well, I wrote mine before the patents 
>were granted, and the products it was in, is no longer :-( Larger companies 
>(e.g. Sun, HP etc.) must have patent cross-licensing so it's us small
guys 
>that suffer.

Perhaps they just ignore it.  The patents are probably easily
broken, push comes to shove.  And the patent holders don't want
to spend the money and risk the counter-suits.  So it stays a
stalemate.  But they work great to keep the small fries from
using them.  Which serves both the patent holder, a little, and
the big folks ignoring them, as well.

Just a thought?

Jon

As I said, looking at it I knew I could do better, that it could shrink 
further. There just seemed to be too many compares. Now when your 
compiler finds your revised solution everytime I'll take two. ;@} Of 
course I don't expect a compiler to come up with the solution Jon provided.

Al

Paul Curtis wrote:
> Al,
> 
> 
>>GCD:
>>	CMP	R14,R15		;CHECK IF A = B
>>	JNE	L1		;IF NOT SKIP TO OTHER TESTS
>>	CMP	#0,R15		;WERE THEY BOTH = 0?
>>	JNZ	L2		;IF NOT RETURN B = A != 0
>>	INC	R15		;ELSE RETURN B = 1
>>L2:
>>	RET
>>L1:
>>	CMP	#0,R15		;TEST FOR A != 0 B = 0
>>	JEQ	L6		;AND IF SO RETURN B = A;
>>	CMP	#0,R14		;TEST FOR A = 0 B != 0 RETURN B = B
>>	JZ	L2
>>L3:
> 
> 
> ***
> 
> 
>>	CMP	R14,R15		;TEST IF R14 = R15 YET
>>	JC	L4		;IF B >= A THEN SUB A FROM B
>>	SUB	R15,R14		;ELSE R14 -= R15
>>	JMP	L5
>>L4:
>>	SUB	R14,R15		;R15 -= R14
>>L5:
>>	CMP	R14,R15
>>	JNZ	L3
>>L6:
>>	MOV	R14,R15
>>	RET
> 
> 
> ***
> 
> The bits between the stars are easily rewritten:
> 
> _gcd1:
> 	sub.w   r15, r14
> 	jz      ret
> 	jc	  _gcd1
> 	add.w   r15, r14
> 	sub.w   r14, r15
> 	jmp     _gcd1
> ret:    ret
> 
> This saves three instructions.
> 
> -- Paul.
> 
> 
> .
> 
>  
> 
> ">http://docs.yahoo.com/info/terms/ 
> 
> 
> 

On Thu, 17 Jul 2003 15:25:23 +0930, Al wrote:

>As I said, looking at it I knew I could do better,
that it could shrink 
>further. There just seemed to be too many compares. Now when your 
>compiler finds your revised solution everytime I'll take two. ;@} Of 
>course I don't expect a compiler to come up with the solution Jon
provided.

Actually, Al, I think I can expect them to get there soon.

It just hit me, remembering something on a proof (or was it yet
to be verified when I read it) from Bennett, I believe though it
certainly could be bad memory operating here, who formally
showed that first-order predicate logic is the same as point-set
topology... and an insight has just arrived about how I might
develop transforms which are topologically invariant on the
important properties, yet quite dissimilar in the specific
sequential logic.  Could be a totally bogus insight, but it's
going to be an interesting week playing with this when I find
that week to play.  Damn, it's going to be fun.  :)

Jon