Reply by Paul Curtis July 18, 20032003-07-18
Hi Jon,

> >OK, as promised to Jonathan, here's the
listing from 
> ImageCraft ICC430. 
> >The
> >minor suboptimal code of moving "b" out of R14 is fixed. It 
> will go out in 
> >the next release. 42 bytes.
> 
> Thanks much!  I'll take a look at these over the next few 
> days. It's always some fun trying to infer some of the 
> mechanics of the compilers from what they produce.  This 
> isn't lot to go on, but some things may shine through, anyway.
> 
> Thanks, again.  To you and the others posting outputs.

We all pretty much generate identical code now.  I believe IAR will
generate identical code too, except it will use R12 & R14.

-- Paul.

Beginning Microcontrollers with the MSP430

Reply by Jonathan Kirwan July 17, 20032003-07-17
On Thu, 17 Jul 2003 18:20:33 -0700, Richard wrote:

>OK, as promised to Jonathan, here's the listing
from ImageCraft ICC430. The 
>minor suboptimal code of moving "b" out of R14 is fixed. It will
go out in 
>the next release. 42 bytes.

Thanks much!  I'll take a look at these over the next few days.
It's always some fun trying to infer some of the mechanics of
the compilers from what they produce.  This isn't lot to go on,
but some things may shine through, anyway.

Thanks, again.  To you and the others posting outputs.

Jon


Reply by Richard F. Man July 17, 20032003-07-17
OK, as promised to Jonathan, here's the listing from ImageCraft ICC430. The

minor suboptimal code of moving "b" out of R14 is fixed. It will go
out in 
the next release. 42 bytes.

(0001)    unsigned int gcd (unsigned int a, unsigned int b)
(0002)    {
(0003)          if (a == 0 && b == 0)
_gcd:
   b                    --> R15
   a                    --> R14
     306C 930E           tst     R14
     306E 2004           jne     3078
     3070 930F           tst     R15
     3072 2002           jne     3078
(0004)              b= 1;
     3074 431F           mov     #1,R15
     3076 3C0E           jmp     3094
(0005)          else if (b == 0)
     3078 930F           tst     R15
     307A 2002           jne     3080
(0006)              b= a;
     307C 4E0F           mov     R14,R15
     307E 3C0A           jmp     3094
(0007)          else if (a != 0)
     3080 930E           tst     R14
     3082 2408           jeq     3094
     3084 3C05           jmp     3090
(0008)              while (a != b)
(0009)                  if (a < b)
     3086 9F0E           cmp     R15,R14
     3088 2C02           jc      308E
(0010)                      b -= a;
     308A 8E0F           sub     R14,R15
     308C 3C01           jmp     3090
(0011)                  else
(0012)                      a -= b;
     308E 8F0E           sub     R15,R14
     3090 9F0E           cmp     R15,R14
     3092 23F9           jne     3086
(0013)
(0014)      return b;
     3094 4130           ret

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


Reply by onestone July 17, 20032003-07-17
Jonathan Kirwan wrote:

> On Thu, 17 Jul 2003 17:10:59 +0930, Al wrote:
> 
>>
>>YOU HAVE A STRANGE IDEA OF WHAT CONSTITUTES FUN ;@\, and people call me 
>>warped and twisted!!
>>
>>Al
> 
> 
> Hehe.  I just went to a dinner party with a group, tonight.  Got
> back an hour ago.  At that party is a mathematician working on
> M-theory ideas.  Guess what we spent the dinner time talking
> about?  Tensors in various dimensions, tortions elements in
> otherwise symmetric matrices, intrinsic and extrinsic
> curvatures, rotational degrees of freedom, gauge degrees of
> freedom (charge, EM, SU(2), etc.), and a fair mix of related
> subjects from phase/gauge, Weyl and Goedel, and you name it.
> When we left, my wife just noted to me that "You probably didn't
> hear any of the discussion, but XXX thought you were cute and
> funny."
> 
> Whatever that might mean.
> 
> Jon

I read the Lancet, NEJM, Nature, Physics, Scientific American, National 
Geographic, Circuit Cellar and Nuts and Volts, I willingly admit to only 
understanding the latter 3, but usually manage to glean at least a 
little insight from the others, and enjoy the reading anyway. I would 
never public admit to reading these, in public, and at dinner I'm more 
the National Enquirer type. :*{

Al


Reply by Jonathan Kirwan July 17, 20032003-07-17
On Thu, 17 Jul 2003 17:10:59 +0930, Al wrote:

>Jonathan Kirwan wrote:
>
>> 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
>
>YOU HAVE A STRANGE IDEA OF WHAT CONSTITUTES FUN ;@\, and people call me 
>warped and twisted!!
>
>Al

Hehe.  I just went to a dinner party with a group, tonight.  Got
back an hour ago.  At that party is a mathematician working on
M-theory ideas.  Guess what we spent the dinner time talking
about?  Tensors in various dimensions, tortions elements in
otherwise symmetric matrices, intrinsic and extrinsic
curvatures, rotational degrees of freedom, gauge degrees of
freedom (charge, EM, SU(2), etc.), and a fair mix of related
subjects from phase/gauge, Weyl and Goedel, and you name it.
When we left, my wife just noted to me that "You probably didn't
hear any of the discussion, but XXX thought you were cute and
funny."

Whatever that might mean.

Jon


Reply by onestone July 17, 20032003-07-17
Jonathan Kirwan wrote:

> 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

YOU HAVE A STRANGE IDEA OF WHAT CONSTITUTES FUN ;@\, and people call me 
warped and twisted!!

Al


Reply by Jonathan Kirwan July 17, 20032003-07-17
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


Reply by onestone July 17, 20032003-07-17
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/ 
> 
> 
> 


Reply by Jonathan Kirwan July 16, 20032003-07-16
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


Reply by Richard F. Man July 16, 20032003-07-16
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>