Path: utzoo!mnetor!uunet!husc6!cca!mirror!ima!johnl From: johnl@ima.UUCP Newsgroups: comp.compilers Subject: Re: Questions of optimizations Message-ID: <820@ima.ISC.COM> Date: 23 Dec 87 15:11:22 GMT References: <783@ima.ISC.COM> Sender: johnl@ima.ISC.COM Reply-To: uiucdcs!uunet!geac!daveb (David Collier-Brown) Organization: The little blue rock next to that twinkly star. Lines: 62 Approved: compilers@ima.UUCP 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: ldiw 0 jc harold 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 maintainability. -- 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. -- Send compilers articles to ima!compilers or, in a pinch, to Levine@YALE.EDU Plausible paths are { ihnp4 | decvax | cbosgd | harvard | yale | bbn}!ima Please send responses to the originator of the message -- I cannot forward mail accidentally sent back to compilers. Meta-mail to ima!compilers-request