From: ctm@ardi.com (Clifford T. Matthews)
Subject: Re: The need for an assembler
Organization: ARDI
Date: Sun, 6 Sep 92 20:08:37 GMT

Dear currently Gentle, but soon to be Bored Beyond Belief, Reader,

It has been pointed out to me that some of you don't know C and
some of you don't know m68k assembly, so here's a brief breakdown of the
C code I posted, and the code that gcc produced

The macro I wrote to do range testing was:

#define INRANGE(x, lower, upper)                                        \
((upper - lower < 0) ?                                                  \
    danger_will_robinson_you_need_assemblerman_post_to_a_f_computers()  \
:                                                                       \
    (unsigned) (x - lower) <= (upper - lower))

I called it in three different places, because context is very important
when dealing with the output of an optimizing compiler.  In fact, people
who write optimizing compilers often get people complaining that there are
bugs in the compiler when they take a look at the assembly that is produced
and can't immediately understand all the optimizations that have been
performed.  The first call was:

    x = 3;

    if (INRANGE(x, -4, 10))
        printf("x ( =3 ) is between -4 and 10\n");

In this example the code that was generated to do the test was "" (i.e.
*0 lines of assembly*; the test was performed at compile time and found to
be true, so printf was called without a test).  Note:  x = 3 is an assignment
of three to the *variable* x.  Gcc's using "static flow analysis" to
understand what's going on.  This is not "constant folding".

The second call was:

    x = somefunctiondefinedelsewhere();

    if (INRANGE(x, -4, 10))
        printf("x ( =? ) is between -4 and 10\n");

In this example, it is important to realize that "somefunctiondefinedelsewhere"
is not defined in this module, for if it were, gcc would "inline" it and
quite possibly use static flow analysis to perform the test at compile time.
However, since there's nothing known about somefunctiondefinedelsewhere(), gcc
produces these *four lines of assembly*:

        addql #4,d0
        moveq #14,d1
        cmpl d0,d1
        jcs L3
	
Now an interesting thing is happening here.  Gcc is doing something that I
probably wouldn't have done, had I been hand assembling this code (of course
I would now; I can learn from gcc, just as the authors of gcc can learn from
assembler writers).  Specifically it uses a moveq and then a register based
compare instead of a compare immediate.  The former is two instructions, while
the latter is only one instruction.  However, on a 68020, the two instructions
execute faster than the one instruction.  I put the test in a loop so I could
time it:

roland% cat moveq.s

.text
.globl _main
_main:
        movel   #10000000,      d3
        movel   #10,            d0
1:
        moveq #14,d1
        cmpl d0,d1
        jcs L3
        subql   #1,     d3
        bne     1b
        rts
L3:     jbsr    _abort

roland% cat cmpl.s  

.text
.globl _main
_main:
        movel   #10000000,      d3
        movel   #10,            d0
1:
        cmpil   #14,    d0
        jcc L3
        subql   #1,     d3
        bne     1b
        rts
L3:     jbsr    _abort

roland% time ./moveq
8.1u 0.0s 0:08 99% 0+8k 2+0io 0pf+0w

roland% time ./cmpl
9.1u 0.0s 0:09 100% 0+0k 0+0io 0pf+0w

So the net result is that gcc chose to use four instructions instead of
three, even though three was a more obvious choice (toy compilers, like
the ones you write in an introduction to compiler construction class would
only have one template for doing a compare and it would be the generic case
which is slower on an 020).

The final use of INRANGE was 

    if (INRANGE(x, 0, 40))
        printf("x ( =? ) is between 0 and 40\n");

which compiled into these *three lines of assembly*:

        moveq #40,d1
        cmpl d3,d1
        jcs L4

Here an extra step was removed because the compiler knew that subtracting
zero was not necessary.  Again, just as in the above case, these three lines
of assembly could have been two lines if an immediate compare was done instead
of a register compare.

With a powerful macro facility, you can spend large amounts of time making
assembler be almost like a compiler, but in the end it takes much more work
than just getting a good optimizing compiler (especially since gcc is available,
*in source form*, for FREE).

				--Cliff
				
Missed the beginning of this thread?  Here's what I stumbled across one day
as I perused alt.folklore.computers out of boredom:

	"No, I am referring to the "programming gem" type stuff.
	Here's a little one: It is possible to range-check an
	integer as being between fixed limits using only one test,
	while intuitively you might think it needs two.  You go
	code this in high-level language.  I'll supply the assembler
	version.  You show me a) a solution at all b) that it is
	the same code or better in terms of efficiency.  To rule
	out really silly stuff, we will exclude the case of a
	2^N-sized table to do a table branch on since it occupies
	2^N spaces in memory :-).  (Fastest method but too terrible
	a space trade-off :-).)  I doubt if you can accomplish a).
	I'll put a bet down on b) if you can even get a)."

I figured the author was someone new to programming and I figured
I'd send some e-mail with an example and a pointer to look at the
source to gcc.  After all, gcc is either already available for any
given 32 bit CPU, or it can be made so without much work (a former
ARDI employee targetted GCC for the clipper in about two weeks,
but he's an exceedingly talented programmer).

My letter was met with vehement denials that the code I submitted
fulfilled b, or even a.  After a few rounds of e-mail, it was clear
that arguing was fruitless.  However, I was very surprised to see
cjl later post to the net and mention this challenge with an aside
that no one had sent a correct solution.  cjl alluded to some e-mail
correspondence that he had but insisted the sender's solution was
incorrect because of *something to do with longwords*!

His latest commentary on my solution is:

	Matthews' example is very interesting; considering the assembly
	version is FIVE instructions.

Oh well, I guess it's up to you, the bored-beyond-belief reader to
determine whether or not the above C solution fits with challenge-a
and challenge-b.  As I've said repeatedly, this little exchange is
far too limited to be useful for comparing HLL's and assembly, you
could easily teach a semester long (introductory) course in computer
science.  It does show cjl's intransigence, and, coupled with the
rest of his discourses on the subject, hints at the root cause of
his faulty reasoning, claims without substance, and stubborn refusal
to admit to being wrong w.r.t. range checking.  Hint:  "_________
is bliss."

	--Cliff
Newsgroups: alt.folklore.computers,comp.os.ms-windows.apps,comp.os.ms-windows.misc