Does C implement the first C compiler itself?

[=?ISO-8859-1?Q?Jo=E3o_Jer=F3nimo?=]

The order in which subexpressions are evaluated is compiler-dependent.
For example, if we have a function

int f (void* p);

then it is compiler-dependent whether in the expression

f (right) + f (left)

f (right) is called first or f (left) is called first.

I guess addition always associates from left to right in C...

But perhaps it's only relevant when you have more than two numbers being summed...
For example, a + b + c is always (a + b) + b, but the order in which a and b are evaluated is
compiler dependent... Did I understand correctly?

JJ

 

[Guest]

I guess addition always associates from left to right in C...

But perhaps it's only relevant when you have more than two numbers being summed...
For example, a + b + c is always (a + b) + b, but the order in which a and b are evaluated is
compiler dependent... Did I understand correctly?

It's a bit stronger than that.

a + b + c is always (a + b) + c, but the order in which not only a and
b but also c are evaluated is unspecified. It's possible for c to be
evaluated before, between, or after a and b.

 

[Guest]

a + b + c is always (a + b) + c, but the order in which not only a and
b but also c are evaluated is unspecified. It's possible for c to be
evaluated before, between, or after a and b.

Very well... But so... it's always added after a and b are added... Right?


It wasn't what I said, anyway... But I understand that the compiler is free to generate all the code
the way it wants as far as the code behaves as expected...

JJ

 

[Guest]

Very well... But so... it's always added after a and b are added... Right?

Yes, unless...

It wasn't what I said, anyway... But I understand that the compiler is free to generate all the code
the way it wants as far as the code behaves as expected...

....the compiler can prove that adding c earlier has no effect on the
result.

But -1 + INT_MAX + 1 cannot ever cause unexpected results due to
overflow, if that's what you mean.

 

[Keith Thompson]

Very well... But so... it's always added after a and b are added... Right?

The standard imposes a partial order on the evaluation of the
subexpressions.

The operands can be evaluated in any of 6 possible orders:

a,b,c a,c,b b,a,c b,c,a c,a,b c,b,a

The first addition must be evaluated after both a and b have been
evaluated, and the second addition must be evaluated after both the
first addition and c have been evaluated.

Or the compiler can re-order the operations arbitrarily *if* the
resulting execution always gives the same result as what's required.

It wasn't what I said, anyway... But I understand that the compiler
is free to generate all the code the way it wants as far as the code
behaves as expected...

Only if "as expected" matches the standard's requirements. Otherwise,
the result can easily violate your expectations. For example, if you
*expect*

printf("hello, ") + printf("world\n")

to print "hello, world", the compiler is free to disappoint you.

 

[Chris Hills]

No. An optimizer (if it's working properly) makes the target code run
more quickly; it doesn't change its behavior.

Suppose you have C sources for two C compilers, compiler1 and
compiler2. compiler1 includes a very clever optimizer; compiler2
doesn't. Use compiler2 to compile itself, yielding compiler2a.exe,
which compiles slowly. Use compiler1 to compile compiler2, yielding
compiler2b.exe, which compiles more quickly. But compiler2a.exe and
compiler2b.exe work the same way; the code they generate is identical.

That is incorrect. There are compilers I know that will compile for size
or speed. They generate different code depending on the flags.

Thus whilst the external functionality of both is the same the internal
behaviour is different. In some cases if you want faster code the
executable is larger because it will unwrap some calls and loops.
Register and memory usage is different.



Ps Keith I hadn't forgotten I owe you an answer to the other post on the
Safe C lib. I have to dig out the file and read it with some thought
Things are VERY hectic here including builders removing walls.
(Everything is covered in dust or in boxes or in store)

 

[Keith Thompson]

That is incorrect. There are compilers I know that will compile for
size or speed. They generate different code depending on the flags.

Thus whilst the external functionality of both is the same the
internal behaviour is different. In some cases if you want faster code
the executable is larger because it will unwrap some calls and
loops. Register and memory usage is different.

My point is that the code generated by a compiler is not (or should
not be) affected by any optimizations performed by the compiler used
to compile the compiler. The compiler itself may run more quickly
and/or use less memory, but it will generate the same code.

Let me try to make the point more clearly. Suppose I have a Pascal
compiler written in C. For simplicity, assume the Pascal compiler
source is a single C source file, "pas.c". Suppose I have a Pascal
program source file "foo.p".

(1) gcc -O0 pas.c -o pas_slow
(2) ./pas_slow foo.p -o foo0
(3) ./foo0

(4) gcc -O3 pas.c -o pas_fast
(5) ./pas_fast foo.p -o foo1
(6) ./foo1

Line 4 will likely take longer to execute than line 1, because gcc is
doing extra work. Line 5 will likely execute more quickly than line
2, because in line 5 I'm executing optimized code. But the "pas_slow"
and "pas_fast" programs (both Pascal compilers) should behave
identically (apart from their speed), which means they should produce
essentially identical code from the same Pascal source, and lines 3
and 6 should take the same time to execute (ignoring random
variations).

If pas_slow and pas_fast behave differently, in the sense of producing
different output, then the optimizer is broken, or possibly pas.c
depends on undefined behavior.

Ps Keith I hadn't forgotten I owe you an answer to the other post on
the Safe C lib. I have to dig out the file and read it with some
thought Things are VERY hectic here including builders removing
walls. (Everything is covered in dust or in boxes or in store)

Can you remind me which thread this is about (the subject header will
do)? Thanks.

 

[Chris Hills]

My point is that the code generated by a compiler is not (or should
not be) affected by any optimizations performed by the compiler used
to compile the compiler. The compiler itself may run more quickly
and/or use less memory, but it will generate the same code.

Let me try to make the point more clearly. Suppose I have a Pascal
compiler written in C. For simplicity, assume the Pascal compiler
source is a single C source file, "pas.c". Suppose I have a Pascal
program source file "foo.p".

(1) gcc -O0 pas.c -o pas_slow
(2) ./pas_slow foo.p -o foo0
(3) ./foo0

(4) gcc -O3 pas.c -o pas_fast
(5) ./pas_fast foo.p -o foo1
(6) ./foo1

Line 4 will likely take longer to execute than line 1, because gcc is
doing extra work. Line 5 will likely execute more quickly than line
2, because in line 5 I'm executing optimized code. But the "pas_slow"
and "pas_fast" programs (both Pascal compilers) should behave
identically (apart from their speed), which means they should produce
essentially identical code from the same Pascal source, and lines 3
and 6 should take the same time to execute (ignoring random
variations).

If pas_slow and pas_fast behave differently, in the sense of producing
different output, then the optimizer is broken, or possibly pas.c
depends on undefined behavior.

The functionality of the code generated by the compiler will be the same
no matter what the optimisation. The size of the code and it's
composition will be different .

IF I have a C compiler and an application APP that I compile and it
generates for example 64 K of executable by compiling using
optimisation for size I might get a 54K executable. If I compiler for
speed I might get a 70K executable.

In all three cases execution times of the running app will be different
except in the places where hardware timers and interrupts are used.

Also not only will the application size be different the amount of
memory will be different.

For example some optimisations are not doing integer promotion rules,
using 8 bit enums , data overlaying


I have a feeling we are arguing at cross purposes here though.

 

[Keith Thompson]

My point is that the code generated by a compiler is not (or should
not be) affected by any optimizations performed by the compiler used
to compile the compiler. The compiler itself may run more quickly
and/or use less memory, but it will generate the same code.

[snip]

The functionality of the code generated by the compiler will be the
same no matter what the optimisation. The size of the code and it's
composition will be different .

Of course.

IF I have a C compiler and an application APP that I compile and it
generates for example 64 K of executable by compiling using
optimisation for size I might get a 54K executable. If I compiler
for speed I might get a 70K executable.

In all three cases execution times of the running app will be
different except in the places where hardware timers and interrupts
are used.

Also not only will the application size be different the amount of
memory will be different.

For example some optimisations are not doing integer promotion rules,
using 8 bit enums , data overlaying

Yes, that's what optimization is all about.

I have a feeling we are arguing at cross purposes here though.

I don't know what we're arguing about at all.

The original question, which you can find up at the top of this
article, was whether repeatedly self-compiling an optimizating
compiler will cause the compiler executable to get smaller at each
iteration. The answer is no; it will get smaller the first time, but
not thereafter. I think that's what I've been consistently saying all
along. You said I was incorrect, but I think we're in agreement.

 

[Chris Hills]

[...]
If one has the C source code for an optimizing compiler, the
compiles the compiler, creating a new compiler, and repeats this
process over many iterations, will the compiler executable get
smaller and smaller each time?

No. An optimizer (if it's working properly) makes the target code run
more quickly; it doesn't change its behavior.

Suppose you have C sources for two C compilers, compiler1 and
compiler2. compiler1 includes a very clever optimizer; compiler2
doesn't. Use compiler2 to compile itself, yielding compiler2a.exe,
which compiles slowly. Use compiler1 to compile compiler2, yielding
compiler2b.exe, which compiles more quickly. But compiler2a.exe and
compiler2b.exe work the same way; the code they generate is identical.

That is incorrect. There are compilers I know that will compile for
size or speed. They generate different code depending on the flags.

Thus whilst the external functionality of both is the same the
internal behaviour is different. In some cases if you want faster code
the executable is larger because it will unwrap some calls and
loops. Register and memory usage is different.

My point is that the code generated by a compiler is not (or should
not be) affected by any optimizations performed by the compiler used
to compile the compiler. The compiler itself may run more quickly
and/or use less memory, but it will generate the same code.

[snip]

The functionality of the code generated by the compiler will be the
same no matter what the optimisation. The size of the code and it's
composition will be different .

Of course.

IF I have a C compiler and an application APP that I compile and it
generates for example 64 K of executable by compiling using
optimisation for size I might get a 54K executable. If I compiler
for speed I might get a 70K executable.

In all three cases execution times of the running app will be
different except in the places where hardware timers and interrupts
are used.

Also not only will the application size be different the amount of
memory will be different.

For example some optimisations are not doing integer promotion rules,
using 8 bit enums , data overlaying

Yes, that's what optimization is all about.

I have a feeling we are arguing at cross purposes here though.

I don't know what we're arguing about at all.

The original question, which you can find up at the top of this
article, was whether repeatedly self-compiling an optimizating
compiler will cause the compiler executable to get smaller at each
iteration. The answer is no; it will get smaller the first time, but
not thereafter. I think that's what I've been consistently saying all
along. You said I was incorrect, but I think we're in agreement.

We are.... it's been a heavy week. I have builders extending the office
and it is almost impossible to work sensibly. I had the feeling I was
arguing at cross purposes

 

[CBFalconer]

.... snip ...

The original question, which you can find up at the top of this
article, was whether repeatedly self-compiling an optimizating
compiler will cause the compiler executable to get smaller at
each iteration. The answer is no; it will get smaller the first
time, but not thereafter. I think that's what I've been
consistently saying all along. You said I was incorrect, but I

It takes at least two compiles, one with the old to produce the
more efficient output with a less efficient compiler, and then
another to produce the more efficient compiler. This assumes the
ancilliary code (libraries, etc) are not changed. The path is not
necessarily easy. I speak from experience, having been forced to
implement changes in multiple phases many times.