10

Proebsting's Law asserts that improvements to compiler technology double the performance of typical programs every 18 years, but even granted that this is somewhat tongue-in-cheek, it's not really accurate; what tends to happen in practice is that each compiler that has serious effort put into optimization, spends a few years implementing those optimizations we know how to do, and further progress trails off asymptotically.

This is illustrated by the very first compiler, the original FORTRAN, proposed in 1953, specified in 1954 and shipped in 1957. Much of the development time was accounted for by the fact that computers were scarce and expensive and the developers believed (probably correctly) that the compiler would not be accepted unless it generated code that was reasonably competitive with handwritten assembly, so they put a lot of effort into implementing an optimizer that by all accounts would be considered pretty decent even by today's standards.

Perhaps the best-known example of a modern optimizing compiler collection is LLVM, which uses a language-specific front end to parse source code to an SSA intermediate format where most of the optimization is done, before generating machine code with a platform-specific back end. The intermediate format is primarily designed for C++, which means it has issues with Fortran which makes different default assumptions about pointer aliasing.

But the original FORTRAN could not have been designed that way; there was no thought at the time of making any of the code portable between different source languages or target platforms, SSA was not yet invented, and memory was much more constrained. On the other hand, it must've used some kind of intermediate representation; you cannot do heavy optimization in a single pass.

What kind of intermediate representation did it use?

4
  • 6
    Early compilers used an incredible by today's standards number of passes. Each pair of passes effectively defined an intermediate representation according to the contract between the passes.
    – Leo B.
    Jul 28 at 5:11
  • 4
    The "Systems manual for 704 FORTRAN and 709 FORTRAN" describes the internal data structures in depth. It used a bunch of tables to keep track of information about the program. After the first phase of processing, most of the program has been compiled and is stored internally as symbolic assembly instructions (not machine code); optimizations are performed based on the assembly and on the various tables.
    – texdr.aft
    Jul 28 at 5:39
  • 2
    Rather detailed accounts of the FORTRAN compiler by its authors can be found here
    – WimC
    Jul 28 at 12:02
  • 2
    @LeoB. - One of my favorite books from just after I graduated college and was working for compiler house is "A Concurrent Pascal Compiler for Minicomputers (Hartmann, LNCS 50) - it describes a seven pass compiler - and half the book is actually syntax diagrams (railroad charts) of the input language and the six intermediate languages! "The Concurrent Pascal compiler has been running on a DEC PDP-11/45... It requires 16,500 16-bit words of storage and compiles source text at the rate of 240 characters per second (about 9-10 lines per second)." Generated code for an interpreted VM. 16K!
    – davidbak
    Jul 28 at 13:53
4

What kind of intermediate representation did it use?

None. At least not any in a way as it's thought of today.

Fortran is made to be translated rather straight into Assembly/Machine code, thus the compiler structure is only mildly abstract. It goes mostly like this:

  • Read the source cards
  • Collect all card for a statement
  • Classify statement into corresponding table entries as there are:
    • Data
      • Constant list
      • Variable list
      • Array list
    • Statement list
      • Arithmetic statements
      • DO statements
      • IF and GO TO
      • Subroutines
      • Functions
      • ... some more
    • Format, End, etc.

At that point the structure can be compared to a modern tokenized format, except it's already checked for all validation that can be made within a single statement and its entries are in most cases already direct equivalences of Assembly instructions or sequences.

  • Write out all table entries into distinct tables.
    • Subsequent passes will be based on these tables
  • Check tables for cross referencing errors, like
    • Missing targets (loops, format, etc.)
    • Never executed sections
    • Wrongly nested loops

At that point most table entries qualifying executable statements can (and will) be translated literal into Assembly instructions modified by data access and DO handling. All further processing is on chunks of Assembly instructions identified by statement numbers. Next step is

  • Merging instructions
    • Rejoining all instructions from the various tables using their statement numbers
    • Adjusting addressing resources

With the essentially done program optimization can be done:

  • Identify continuous execution segments
  • Analyze sequence and probability
  • Reorder when useful
  • Assign addressing resources

Repeat this for larger sections

  • Identify regions (larger blocks)
  • Assign addressing resources

Resolve data access

  • Resolve all data addressing

All left now is

  • Writing out binary for each instruction.

So, no, there isn't much similarity to today's compiler structure, nor the way they optimize.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.