A primeval C compiler 
Author Message
 A primeval C compiler

Ah, the heady days of creation -- 1972 and 1973 -- when Unix was born.

Quote:

>I finally prepared another fossil for museum exhibition: from DECtapes
>written
>in 1972-73, there are exhumed C compilers (including source) to show
>what
>the very early stages of the language were like.  This was a highly
>transitional stage; for example, the earlier one anticipates a "long"
>type, but doesn't have struct; the 6-months-later compiler implements
>struct, but reuses long's slot in the type table.

> http://www.*-*-*.com/ ~dmr/primevalC.html

Thanks for the historic link, which has now been added to

http://www.*-*-*.com/

promoting the creation of public domain artificial intelligence (Mindix?)
as exemplified by the 19.Jul.1999 release of downloadable

http://www.*-*-*.com/

Quote:
>                Dennis



Tue, 15 Jan 2002 03:00:00 GMT  
 A primeval C compiler
Old Bell Labs C compiler may be "fossil" but from my recollection of
the pre-1976 Unix compiler, it has many methods and algorithms that are
superior to those in use today.  Off the top of my head some are: 1) better
expression parsing (this is documented in Gries' old compiler writing
text book), 2) better optimization because machine dependent throughout,
3) better use of intermediate forms and data structures.

An interesting archeological experiment would be to try those algorithms
on modermn ansii standard C compiler syntax.

I think the reasons those old algorithms may be superior are:
1) Computer Science was part of traditional science and Bell Labs
people used and believed in scientific method. This changed in
late 1970's and early 80';s EE departments took over traditional
(in Literate and Science schools) Computer Science departments
where evaluation became manufacturability,
2) a result of moving Computer Science to EE departments
is that evaluation and promotion has become tied to efficiency of
working with industry (cronyism?).

Just my two cents.
/Steve


Quote:
>Ah, the heady days of creation -- 1972 and 1973 -- when Unix was born.

>>I finally prepared another fossil for museum exhibition: from DECtapes
>>written
>>in 1972-73, there are exhumed C compilers (including source) to show
>>what
>>the very early stages of the language were like.  This was a highly
>>transitional stage; for example, the earlier one anticipates a "long"
>>type, but doesn't have struct; the 6-months-later compiler implements
>>struct, but reuses long's slot in the type table.

>> http://www.cs.bell-labs.com/~dmr/primevalC.html

>Thanks for the historic link, which has now been added to

>http://www.geocities.com/Athens/Agora/7256/c.html A C FAQ for

>promoting the creation of public domain artificial intelligence (Mindix?)
>as exemplified by the 19.Jul.1999 release of downloadable

>http://www.geocities.com/Athens/Agora/7256/mind-fpc.html Mind.Forth AI.

>>                Dennis

--
Steve Meyer                             Phone: (415) 296-7017
Pragmatic C Software Corp.              Fax:   (415) 296-0946

San Francisco, CA 94104


Tue, 15 Jan 2002 03:00:00 GMT  
 A primeval C compiler

Quote:

>Old Bell Labs C compiler may be "fossil" but from my recollection of
>the pre-1976 Unix compiler, it has many methods and algorithms that are
>superior to those in use today.  Off the top of my head some are: 1) better
>expression parsing (this is documented in Gries' old compiler writing
>text book), 2) better optimization because machine dependent throughout,
>3) better use of intermediate forms and data structures.
>An interesting archeological experiment would be to try those algorithms
>on modermn ansii standard C compiler syntax.

Interesting indeed, but note that part of the the old compiler's success
was due to the different language it was implementing: there were only 2
types, int (16 bit) and char; no unsigned types (though pointers were
implicitly signed); no unions; no casts.  The hardware it compiled for
was also simpler than modern chips; it had very few registers, and
supported several flavors of memory-to-memory operations.

--
        Amos Shapir
Paper: nSOF Parallel Software, Ltd.
       Givat-Hashlosha 48800, Israel
Tel: +972 3 9388551   Fax: +972 3 9388552        GEO: 34 55 15 E / 32 05 52 N



Fri, 18 Jan 2002 03:00:00 GMT  
 A primeval C compiler

Quote:

> The hardware it compiled for
> was also simpler than modern chips; it had very few registers, and
> supported several flavors of memory-to-memory operations.

Well that's the worst of all possible worlds, for compiler complexity.

With a simple accumulator architecture you have to load every operand from
memory, and store all results back in memory.

With a load-store architecture you know that you *have* to load all
operands into registers before you can use them.  With 32 or more
registers a simple compiler can just assume that everything will fit into
registers and make the user rewrite his code if it doesn't.

It's only with a machine with a medium number of registers and both
register-register and memory-register instructions (PDP11, x86, 68K all
fit both criteria) that you have to make those {*filter*} decisions about what
to load into registers and what to use directly from memory, and worry
about register allocation and spills/reloads.  {*filter*} stuff.

-- Bruce



Sat, 19 Jan 2002 03:00:00 GMT  
 A primeval C compiler

<snip>

Quote:

>Interesting indeed, but note that part of the the old compiler's success
>was due to the different language it was implementing: there were only 2
>types, int (16 bit) and char; no unsigned types (though pointers were
>implicitly signed); no unions; no casts.  The hardware it compiled for
>was also simpler than modern chips; it had very few registers, and
>supported several flavors of memory-to-memory operations.

That is not my recollection from studying the Unix Bell Labs C compiler
that was on the Unix systems at UC Berkeley in computer science Dept.
in 1973 and 1974 while I was a graduate student.  I think it was most
of K&R Book (first edition).  I am sure it had floating point for maybe
PDP 11/70?.
/Steve

--
Steve Meyer                             Phone: (415) 296-7017
Pragmatic C Software Corp.              Fax:   (415) 296-0946

San Francisco, CA 94104



Sun, 20 Jan 2002 03:00:00 GMT  
 A primeval C compiler

Quote:

>Well that's the worst of all possible worlds, for compiler complexity.
> [...]
>It's only with a machine with a medium number of registers and both
>register-register and memory-register instructions (PDP11, x86, 68K all
>fit both criteria) that you have to make those {*filter*} decisions about what
>to load into registers and what to use directly from memory, and worry
>about register allocation and spills/reloads.  {*filter*} stuff.

This is true for optimizing compilers, but for pcc and similar compilers
these machines were good targets.  The user was responsible for register
allocation.  VAX pcc assigned "register" variables to r11..r6 in order
of declaration.  Very simple.  Subexpressions were evaluated into r0..r5
which were reserved for that purpose, probably using a simple algorithm
based on the internal tree structure (I never examined this part of pcc,
but see the dragon book for discussion).  On a VAX it didn't matter if a
variable was register or memory.  The same instruction worked in either
case, and unlike modern x86 a read/modify/write instruction was faster
than a load/op/store sequence.

--



Sun, 20 Jan 2002 03:00:00 GMT  
 A primeval C compiler

Quote:
> On a VAX it didn't matter if a variable was register or memory.  The same
> instruction worked in either case, and unlike modern x86 a read/modify/write
> instruction was faster than a load/op/store sequence.

That is in all likelihood only true for some of the initial implementations
of the VAX architecture. I suspect the 8600/8650 and the 9000, and I am pretty
sure the NVAX/NVAX+-based ones (the last VAX xhip to be designed) used an
approach similar to the Pentium et al.: make the RISC-like subset go fast at
the expense of the rest of the instruction set, especially the complications
arising from multiple memory accesses and exceptions in one instruction.

        Jan



Sun, 20 Jan 2002 03:00:00 GMT  
 A primeval C compiler

Quote:

>It's only with a machine with a medium number of registers and both
>register-register and memory-register instructions (PDP11, x86, 68K all
>fit both criteria) that you have to make those {*filter*} decisions about what
>to load into registers and what to use directly from memory, and worry
>about register allocation and spills/reloads.  {*filter*} stuff.

I wouldn't call PDP11 a "machine with a medium number of registers" (and
the others are pretty tight too).  The C compiler mentioned here had only
3 free registers -- R7 was the PC, R6 the SP, R5 the FP, R0 & R1 were
reserved for function return values, so only R2-R4 were free.  The
compiler used them for intermediate results only (unless, in a later
version, it was told otherwise by the "register" keyword); so it did not
have to worry much about register allocation.

--
        Amos Shapir
Paper: nSOF Parallel Software, Ltd.
       Givat-Hashlosha 48800, Israel
Tel: +972 3 9388551   Fax: +972 3 9388552        GEO: 34 55 15 E / 32 05 52 N



Sun, 20 Jan 2002 03:00:00 GMT  
 A primeval C compiler


Quote:

>> On a VAX it didn't matter if a variable was register or memory.  The same
>> instruction worked in either case, and unlike modern x86 a read/modify/write
>> instruction was faster than a load/op/store sequence.

>That is in all likelihood only true for some of the initial implementations
>of the VAX architecture. I suspect the 8600/8650 and the 9000, and I am pretty
>sure the NVAX/NVAX+-based ones (the last VAX xhip to be designed) used an
>approach similar to the Pentium et al.: make the RISC-like subset go fast at
>the expense of the rest of the instruction set, especially the complications
>arising from multiple memory accesses and exceptions in one instruction.

Late model VAXes are limited by operand decode so reducing instruction
count is valuable.   There is a paper on the NVAX talking about the
analysis that led them to decode only 1 operand specifier per cycle.  I
did some timing tests on a VAX 9000 a few years back.  incl (reg) took
2 cycles, the same as movl (reg),reg even though it adds an ALU op and
a store  Apparently a store (as on many modern processors) reads its
data fairly late in the pipeline.

As far as I know, only a couple 8??? models pipelined microinstructions.
On these RISC style coding might have been good.

--



Sun, 20 Jan 2002 03:00:00 GMT  
 A primeval C compiler

Quote:
> >That is in all likelihood only true for some of the initial implementations
> >of the VAX architecture. I suspect the 8600/8650 and the 9000, and I am pretty
> >sure the NVAX/NVAX+-based ones (the last VAX xhip to be designed) used an
> >approach similar to the Pentium et al.: make the RISC-like subset go fast at
> >the expense of the rest of the instruction set,

No; the 8700/NVAX/NVAX-successors decoded into microinstructions which
were then pipelined, as opposed to the 8650, which pipelined VAX
instructions directly. This gets talked about all the time, since it's
the canonical example for this being done before Intel "invented"
it. Notice that this is different from "making a RISC-like subset go
fast".

-- g



Mon, 21 Jan 2002 03:00:00 GMT  
 A primeval C compiler

Quote:

> No; the 8700/NVAX/NVAX-successors decoded into microinstructions which
> were then pipelined, as opposed to the 8650, which pipelined VAX
> instructions directly. This gets talked about all the time, since it's
> the canonical example for this being done before Intel "invented"
> it. Notice that this is different from "making a RISC-like subset go
> fast".

Quite. But I distinctly remember reading that Digital Technical Journal (RIP)
article on the NVAX that they threw the hardware a RISC-like subset, and that
the complicated do-everything-in-one-go instruction variants suffered for it.

        Jan



Mon, 21 Jan 2002 03:00:00 GMT  
 A primeval C compiler


   :>It's only with a machine with a medium number of registers and both
   :>register-register and memory-register instructions (PDP11, x86,
   :>68K all fit both criteria) that you have to make those {*filter*}
   :>decisions about what to load into registers and what to use
   :>directly from memory, and worry about register allocation and
   :>spills/reloads.  {*filter*} stuff.

   :I wouldn't call PDP11 a "machine with a medium number of registers"
   :(and the others are pretty tight too).

The x86 is in a worse position than the others. As for whether they have
a "medium" number of registers, perhaps this could be defined on the
scale minimal, medium, and sufficient?
--
the desk lisard     communa     time's taught the killing game herself



Mon, 21 Jan 2002 03:00:00 GMT  
 A primeval C compiler

Quote:
> The x86 is in a worse position than the others. As for whether they have
> a "medium" number of registers, perhaps this could be defined on the
> scale minimal, medium, and sufficient?

The x86 is a very poor design and has only survived for the sole reason it
ran DOS and runs Windows.

Rob.



Tue, 22 Jan 2002 03:00:00 GMT  
 A primeval C compiler


Quote:

>> No; the 8700/NVAX/NVAX-successors decoded into microinstructions which
>> were then pipelined, as opposed to the 8650, which pipelined VAX
>> instructions directly.

Perhaps I was confused by the Digital Technical Journal article's use
of "macropipelining" to describe the NVAX.  But the more important part
of my statement was the one specifier per cycle decode limit.  Compare
addl (r0),(r1),(r2)                                     3 decode cycles
movl (r0),r3;movl (r1),r4;addl2 r3,r4;movl r4,(r2)      8 decode cycles

Quote:
>Quite. But I distinctly remember reading that Digital Technical Journal (RIP)
>article on the NVAX that they threw the hardware a RISC-like subset, and that
>the complicated do-everything-in-one-go instruction variants suffered for it.

The article is http://www.digital.com/info/DTJ701/DTJ701SC.TXT.

--



Tue, 22 Jan 2002 03:00:00 GMT  
 A primeval C compiler

Quote:

> > The x86 is in a worse position than the others. As for whether they have
> > a "medium" number of registers, perhaps this could be defined on the
> > scale minimal, medium, and sufficient?

> The x86 is a very poor design and has only survived for the sole reason it
> ran DOS and runs Windows.

Yep, an accident of history and timing.  When IBM determined to create
the PC almost twenty years ago, the microprocessor market was alive with
a plethora of 8-bit CPU's from Intel, Motorola, Zilog, and others (Who
made the 6502? I forget.)  IBM wanted to differentiate the PC with new
16-bit technology.  At the time, Intel 8086 was the only player willing
to play.  The mere size of the IBM demand frightened the other producers
away.  Intel was big enough.  They (Intel) even agreed to cripple the
8086 into the 8-bit-bus 8088, just for IBM.  We all knew they were both
crazy.

--

"Everything should be made as simple as possible, but not simpler."
                    --- Albert Einstein ---



Tue, 22 Jan 2002 03:00:00 GMT  
 
 [ 494 post ]  Go to page: [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33]

 Relevant Pages 

1. A primeval C compiler

2. A primeval C compiler

3. to CS: or not to CS: in F-PC assembler

4. Camp Smalltalk (CS 6) registration

5. APL as First Language for CS

6. SoftEng or CS Graduate Program Search

7. Test and Set (TS) vs Compare and Swap (CS)

8. Refactored Plus All Missing CS ANSI Tests In SIF

9. Camp Smalltalk (CS 6) registration

10. vwnc@cs.uiuc.edu

11. Next instr of the week - CS please

 

 
Powered by phpBB® Forum Software