Compilers

Compilers

[David Given]

I've been playing with Minix, and in particular looking at its C compiler. 
Minix uses a cut-down version of the Amsterdam Compiler Kit, which used to 
cost serious money but is now open source.

It's nice.

It seems to be a full ANSI C compiler generating pretty good code. ELKS' 
compiler is bcc, which is a K&R C compiler with a nasty preprocessor that 
turns ANSI C into K&R C; this means that it will compile ANSI C, but you 
don't get the proper type checking. Minix' cc is designed to run self-hosted 
(there are up to *eight* seperate programs involved); on my 1MB machine 
there's a fair amount of disk churn because it has to keep reloading bits of 
code, which makes it slow. It would be way faster on a 2MB machine.

I've tried to compare the code produced by cc and bcc. I'm not entirely sure 
this is a fair comparison because I don't think I managed to invoke bcc's 
optimiser correctly, but here you go anyway. Fixed-pitch font recommended.

The source:

---snip---
extern int printf(char* format, ...);

int fnord(int i)
{
        int count = 0;

        while (i)
                count += i--;
        return count;
}

int main(int argc, char* argv[])
{
        printf("Hello, world!\n");
        printf("%d\n", fnord(argc));
        return 0;
}
---snip---

The output:

BCC				CC

_fnord:				_fnord:
push bp				push bp
mov bp,sp			mov bp,sp
dec sp				push si
dec sp				xor si,si
xor ax,ax			.4:
mov -2[bp],ax			cmp 4(bp),#0
jmp .2				je .3
.3:				mov dx,4(bp)
mov ax,4[bp]			mov cx,dx
dec ax				dec cx
mov 4[bp],ax			mov 4(bp),cx
inc ax
add ax,-2[bp]
mov -2[bp],ax			add si,dx
.2:				
mov ax,4[bp]			
test ax,ax
jne .3
.4:
.1:				.3:
mov ax,-2[bp]			mov ax,si
mov sp,bp
pop bp
ret				jmp .sret

The main() function produced by both compilers is identical apart from minor 
differences: cc likes using pop to do a stack retraction, where bcc does a 
mov sp,bp instead. This means that cc produces smaller but slower code, but 
bcc produces faster code. *shrug*

cc seems to have better register allocation and avoids using stack slots when 
it doesn't need to. bcc has put the loop conditional at the bottom instead of 
the top; not sure why, it makes the code larger.

Given that currently the ELKS kernel is about 70kB of code, a little 
problematic given the 64kB limit, anything that will make the code smaller is 
good! Plus, cc is a real ANSI compiler. When I get some spare time I'll see 
if I can have a look at building the ELKS kernel on Minix. Since the two 
compilers use the same calling conventions I don't think it would be terribly 
hard and I'd be interested in seeing what sort of differences there are in 
real code.

Incidentally, if you're interested in what ELKS might end up being, I strongly 
suggest you install a copy of Minix on something. It's fascinating just how 
usable it is, on such limited hardware.

-- 
+- David Given --McQ-+ 
|  dg@cowlark.com    | "All power corrupts, but we need electricity." ---
| (dg@tao-group.com) | Diana Wynne Jones, _Archer's Goon_
+- www.cowlark.com --+ 

Re: Compilers

[sandeep]

> Given that currently the ELKS kernel is about 70kB of code, a little 
> problematic given the 64kB limit, anything that will make the code smaller is 
Apart from using ways/tools to get smaller code to fit it 64KB, I guess couple 
of other options should also be possible. If you see elks features wish-list, 
with more wishes fulfilled it might not be possible to have it fit in 64KB, may 
be unless entire OS is handcoded in assembly and tweaks/hacks applied here and 
there as needed to produce mainly smaller (faster) code.

1. something like loadable modules / overlays that can help here. these overlays 
  needn't be overlays in dos .OVL file ways but part of executable, and 
executable header gives information about these. yeah it will require sllightly 
different/ modified executable format to be devised.

2. even if code and data for elks kernel is more than 64 KB, that will not be a 
problem if this code and data is not moved around b/w memory and disk, i.e. once 
loaded it stays there till reboot. within kernel code you can even have far 
pointers stored even as local variables.

-- 
regards
sandeep
--------------------------------------------------------------------------
Loose bits sink chips.
--------------------------------------------------------------------------

Re: Compilers

[Eduardo Pereira Habkost]

[-- Attachment #1: Type: text/plain, Size: 3920 bytes --]

Hi, all,

On Fri, May 28, 2004 at 11:42:38AM +0100, David Given wrote:
<snip>
> 
> I've tried to compare the code produced by cc and bcc. I'm not entirely sure 
> this is a fair comparison because I don't think I managed to invoke bcc's 
> optimiser correctly, but here you go anyway. Fixed-pitch font recommended.
> 
> The source:
> 
> ---snip---
> extern int printf(char* format, ...);
> 
> int fnord(int i)
> {
>         int count = 0;
> 
>         while (i)
>                 count += i--;
>         return count;
> }
> 
> int main(int argc, char* argv[])
> {
>         printf("Hello, world!\n");
>         printf("%d\n", fnord(argc));
>         return 0;
> }
> ---snip---
> 
> The output:
> 

Nice, I would like to compare with the code that gcc-8086 is producing
currently, too. Please note that there could be hiddend bugs that I've
seen yet.  :)

I've used -O3 for compilation:
(GNU as AT&T syntax used)

_fnord:
        push    %bp
        mov     %sp,%bp

        movw    2(%bp),%dx
        movw    $0x0,%ax
        cmpw    $0x0,%dx
        je      .L15
.L13:
        addw    %dx,%ax
        addw    $0xffffffff,%dx
        cmpw    $0x0,%dx
        jne     .L13
.L15:

        leave
        ret

Some things that can be noted: There is not 'dec' instruction, yet. It
can be added. It is using 'leave' for function exit. IIRC, it is a
80186 instruction, so it is better have an option to use is better have
an option for the user choosing to use it or not.

One bug appeared: it is using 2(%bp) for getting the function
parameter. It doesn't look correct.  :)

A -fno-frame-pointer option would be nice, too. I guess that most people
wouldn't want them on ELKS, and it will make code smaller and use less
stack space.

> BCC                             CC
> 
> _fnord:                         _fnord:
> push bp                         push bp
> mov bp,sp                       mov bp,sp
> dec sp                          push si
> dec sp                          xor si,si
> xor ax,ax                       .4:
> mov -2[bp],ax                   cmp 4(bp),#0
> jmp .2                          je .3
> .3:                             mov dx,4(bp)
> mov ax,4[bp]                    mov cx,dx
> dec ax                          dec cx
> mov 4[bp],ax                    mov 4(bp),cx
> inc ax
> add ax,-2[bp]
> mov -2[bp],ax                   add si,dx
> .2:                             
> mov ax,4[bp]                    
> test ax,ax
> jne .3
> .4:
> .1:                             .3:
> mov ax,-2[bp]                   mov ax,si
> mov sp,bp
> pop bp
> ret                             jmp .sret
> 
> The main() function produced by both compilers is identical apart from minor 
> differences: cc likes using pop to do a stack retraction, where bcc does a 
> mov sp,bp instead. This means that cc produces smaller but slower code, but 
> bcc produces faster code. *shrug*
> 
> cc seems to have better register allocation and avoids using stack slots when 
> it doesn't need to. bcc has put the loop conditional at the bottom instead of 
> the top; not sure why, it makes the code larger.
> 
> Given that currently the ELKS kernel is about 70kB of code, a little 
> problematic given the 64kB limit, anything that will make the code smaller is 
> good! Plus, cc is a real ANSI compiler. When I get some spare time I'll see 
> if I can have a look at building the ELKS kernel on Minix. Since the two 
> compilers use the same calling conventions I don't think it would be terribly 
> hard and I'd be interested in seeing what sort of differences there are in 
> real code.
> 
> Incidentally, if you're interested in what ELKS might end up being, I strongly 
> suggest you install a copy of Minix on something. It's fascinating just how 
> usable it is, on such limited hardware.
> 

-- 
Eduardo

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: Compilers

[Mark Junker]

Eduardo Pereira Habkost schrieb:

> 
> _fnord:
>         push    %bp
>         mov     %sp,%bp
> 
>         movw    2(%bp),%dx
should be "movw    4(%bp),%dx"

>         movw    $0x0,%ax
>         cmpw    $0x0,%dx
>         je      .L15
> .L13:
>         addw    %dx,%ax
>         addw    $0xffffffff,%dx
should be:
addw    $0xffff,%dx

$0xffffffff is a 32 bit constant

>         cmpw    $0x0,%dx
>         jne     .L13
> .L15:
> 
>         leave
"leave" is only available on 186+

>         ret
> 
> Some things that can be noted: There is not 'dec' instruction, yet. It
> can be added. It is using 'leave' for function exit. IIRC, it is a
> 80186 instruction, so it is better have an option to use is better have
> an option for the user choosing to use it or not.
You're right.

> One bug appeared: it is using 2(%bp) for getting the function
> parameter. It doesn't look correct.  :)
Again, you're right. It's not correct

> A -fno-frame-pointer option would be nice, too. I guess that most people
> wouldn't want them on ELKS, and it will make code smaller and use less
> stack space.
This can (sometimes) produce smaller code.

Regards,
Mark Junker

Re: Compilers

[David Given]

Mark Junker wrote:
[...]
>> A -fno-frame-pointer option would be nice, too. I guess that most people
>> wouldn't want them on ELKS, and it will make code smaller and use less
>> stack space.
> 
> This can (sometimes) produce smaller code.

The main advantage is that you free up a register that can be used for 
other things. On the register-starved x86 family this is a huge benefit.

I really don't know why people use a frame pointer anyway. Given that 
the i86 can do arbitrary relative stack addressing there's no real need 
for it. It makes debugging marginally easier, but then the debug 
information should provide all the necessary data to find the stack 
frame from any point in the code...

(I work for a company that produces embedded operating systems, with our 
own cross-platform compiler architecture. The PowerPC has 32 
general-purpose registers. Guess how many the 386 has? *Five*. That 
leads to interesting scalability issues in our register allocation code...)

-- 
dg@cowlark.com --- http://www.cowlark.com
My other account has a real signature.

Re: Compilers

[Mark Junker]

David Given schrieb:

> I really don't know why people use a frame pointer anyway. Given that 
> the i86 can do arbitrary relative stack addressing there's no real need 
> for it. It makes debugging marginally easier, but then the debug 
> information should provide all the necessary data to find the stack 
> frame from any point in the code...

The main problem is that the value of the stack pointer changes during 
the execution of a function and sometimes it's not easy to realize that

mov.l @(r15,12),r1
.
.
.
mov.l @(r15,8),r2

may refer to the same argument ...

> (I work for a company that produces embedded operating systems, with our 
> own cross-platform compiler architecture. The PowerPC has 32 
> general-purpose registers. Guess how many the 386 has? *Five*. That 
> leads to interesting scalability issues in our register allocation code...)

I work on embedded systems using the Renesas SH4 (it has 16 (+ 8) int 
and 16 fp GP registers)  so I think I know what you mean.

Regards,
Mark Junker