Re: Questions of optimizations

uiucdcs!uunet!geac!daveb (David Collier-Brown)
23 Dec 87 15:11:22 GMT

          From comp.compilers

Related articles
Questions of optimizations (1987-12-10)
Re: Questions of optimizations uiucdcs!uunet!geac!daveb (1987-12-23)
| List of all articles for this month |

From: uiucdcs!uunet!geac!daveb (David Collier-Brown)
Newsgroups: comp.compilers
Date: 23 Dec 87 15:11:22 GMT
References: <783@ima.ISC.COM>
Organization: The little blue rock next to that twinkly star.

In article <783@ima.ISC.COM>, John footnoted a discussion of
link-time optimizations with the following:
>[A recent message mentioned that minix uses slightly squashed assembler for
>its object format. A message a few months ago in the discussion of writing
>a machine independent C compiler that compiled to bytecodes talked about a
>commercial compiler system from way back that used what we would now consider
>to be an intermediate compiler code as its object form. I'd be interested
>to hear how much slower this makes a linker, considering that most linkers
>are none too fast now. And is there any way to reconcile this with things
>like shared libraries and Multics-style dynamic linking? -John]

      I can't comment on the applicability of Andy's technique of using
(real) assembler as the linkable intermediate code, but I will bring
up Dave Hansen's technique again:

      In an old article in Software, Practice & Experience, he writes
about having one-pass compilers and assemblers emit a very
compressed human-readable code[1] which was linked by a slightly more
powerfull two-phase linker.
      I wrote a version of his linker in C as an experiment, and found
it to run notably faster than either my standard (absolute!)
assembler or regular linker for the machine in question. It seems
the basic algorithm is a merge-sort. (Known a priori to be rather
quick) The most obvious speedup was in taking the redundant
address resolutions out of the compiler and assembler and giving
them to the linker, whose main purpose becomes (wait for it...)
**linking***! [2]
    Because the linker had to deal with visibility problems (ie,
making local symbols passed to it in the intermediate code invisible
before linking non-local symbols), it appears to me that
designing-in hooks for shared libraries is easy. From playing
around with Multics, the dynamic linking appears to be a matter of
delaying resolutions and reformatting the linkage information for
eventual inclusion in the "known segment table".

  --dave (Multics is alive, well and living on the Riviera) c-b

[1] The code looked real ugly, but could be read and written quite
easily. A spurious example is:
    It was compact mainly because things like "0\n" (the second line
above) was 16 bits worth of ascii instead of a half a line of text
or (even worse) 36 bits of opcode/operand.

[2] I'll claim that the doing of ANY resolution is the compiler or
assembler is purely hysterical (oops, historical), due to size
limitations on linker address-resolution tables. In retrospect, its
a bad idea from the standpoint of both performance and
  David Collier-Brown. {mnetor|yetti|utgpu}!geac!daveb
  Geac Computers International Inc., | Computer Science loses its
  350 Steelcase Road,Markham, Ontario, | memory (if not its mind)
  CANADA, L3R 1B3 (416) 475-0525 x3279 | every 6 months.

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.