grunwald@m.cs.uiuc.edu (Dirk Grunwald) (12/11/87)
Here's a topic to stir things up. I've taking a seminar on optimizations this semester. Recently, we read the papers from WRL concerning link-time register allocation. In the paper (it appears in the last ASPLOS, I think?) Wahl says that link time register allocation allows for better global register analysis, which is rather an obvious statement, since you're linking the parts into the global whole. Are there compilers other than the DEC-WRL suite which compile to a link time form and do optimizations at link time? Any references? There would seem to be a large number of global optimizations available at that time: alias analysis, register allocation, in-line expansion, parallelism detection, etc. Realisticlly, it would also favour the edit-compile cycle. With the optimizations deferred until the later stages of the compile, the lexical and syntactic analysis would be faster. The size of intermediate files might increase a great deal, but the performance gains would certainly be worthwhile. dirk grunwald univ of illinois [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] -- Send compilers articles to ima!compilers or, in a pinch, to Levine@YALE.ARPA 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
johnl@ima.UUCP (12/23/87)
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