6

Very early C compilers, (mostly K&R C, as seen in UNIX V6, or this compiler for the Atari ST called "Megamax C") came with a "code improver". This was apparently a separate binary, named c2, and was not part of the C compiler. That's presumably because of memory constraints.

That means that middle-end optimisations like constant propagation or dead-code elimination must have either been left to c1, or not done at all. And it means that the optimisations done by c2 were probably limited to:

  • very machine-specific micro-optimisations, such as seeing if an add should be replaced by an increment (or addq on the m68k).

  • various peephole optimisations like eliminating push a; pull a

  • miscellaneous obvious and simple things, like replacing a jump, which targets a jump, with the instruction it points to.

Were these Code Improvers written with the output of c1 in mind? Or were they really written and intended as general-purpose object code improvers for the target platform? Could they, and were they, used with f77 or as for example?

  • 1
    I rather prefer the nomenclature, "code improver", to the modern-day "optimiser". If we call them optimisers, it implies that their output is optimal! – Wilson Jun 25 '18 at 12:58
  • 1
    A bigger issue is that there are two different kinds of utilities--those that take a sequence of code and replace it with an alternative form that will be equivalent in all cases, and those which will take a sequence of code and replace with with an alternative form that will behave identically only in a subset of the possible cases (typically the minimum set defined by the author's interpretation of the C Standard) and may behave arbitrarily in cases outside that subset. Unfortunately, neither "code improver" nor "optimizer" would seem more applicable to one kind or the other. – supercat Jun 25 '18 at 19:58
  • 1
    In cases where an execution environment documents a characteristic behavior in a situation where the Standard would impose no requirements, and where this behavior provides functionality that would not otherwise be available, an optimizer that promises not to affect such behaviors may be useful, but one that replaces code which the environment would process in documented and predictable fashion in certain cases with code that will behave nonsensically in those cases would be worse than useless. – supercat Jun 25 '18 at 20:05
11

The 32V paper, A UNIX™ Operating System for the DEC VAX-11/780 Computer (by Thomas B. London and John F. Reiser) has a few interesting tidbits about c2.

Two features of the VAX-11 architecture — three-address instructions and indexed addressing mode — were difficult to model within the basic structure of the compiler. The full implementation of three-address instructions proved to be so difficult that it was not really attempted. Instead, c2, the assembly language code improver, tries to merge several instructions into an appropriate three-address instruction.

This suggests that c2 was somewhat akin to a second (or third, since the C compiler used c0 and c1) pass for the C compiler, albeit assembly language-oriented: it makes up for lacunae in the main C compiler. (Its naming is consistent with this approximation, at least when compared with as2, the second pass of the assembler.)

c2. The code improver for the assembly language generated by the VAX-11 C compiler is based on a similar program for the PDP-11. A ’backwards’ register usage pass, performed once and before anything else, was a major addition. Knowing that no temporary register is live across a backwards jump, the register usage pass introduces three-address instructions wherever possible. It also recognizes situations where jump on bit (jbc, jbs, jlbc, jlbs,) extract field (extzv, movzbl) and move address (moval, movab, pushal, pushab) instructions can be used. The code for insertion of fancy loop control instructions sob, aob, acb was also extended.

This also suggests that c2 was specifically written to process the code produced by the C compiler.

as doesn’t support any option to invoke c2 (or any other improver); I imagine the authors wouldn’t have expected hand-written assembly language to need improving after assembly! f77 replaced the first pass of the C compiler, feeding into c1 and c2 (if the -O option was provided), so c2 was used for compiled Fortran code which had been processed by the C compiler’s code generator anyway (see Portability of C Programs and the UNIX System by S. C. Johnson and D. M. Ritchie, published in The Bell System Technical Journal, volume 57, number 6, part 2, July/August 1978).

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.