From compilers Sun Sep 01 05:00:09 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: compilers-request@iecc.cambridge.ma.us (John R. Levine) Subject: comp.compilers monthly message and Frequently Asked Questions Message-ID: Keywords: administrivia Sender: compilers-sender@iecc.cambridge.ma.us Supersedes: Organization: Compilers Central Date: Sun, 01 Sep 91 09:00:05 GMT Approved: compilers@iecc.cambridge.ma.us Expires: 1 Oct 91 23:59:00 GMT This is the comp.compilers monthly message, last edited September 1991. NOTE: At the end of this message are some answers to frequently asked questions. Please read them before you post. -- What is comp.compilers? It is a moderated usenet news group addressing the topics of compilers in particular and programming language design and implementation in general. It started in 1986 as a moderated mailing list, but interest quickly grew to the point where it was promoted to a news group. Recent topics have included optimization techniques, language design issues, announcements of new compiler tools, and book reviews. Messages come from a wide variety of people ranging from undergraduate students to well-known experts in industry and academia. Authors live all over the world -- there are regular messages from the U.S, Canada, Europe, Australia, and Japan, with occasional ones from as far away as Malaysia. I have no idea how large the readership is, since the anarchic nature of usenet makes it impossible to tell who reads it, but I wouldn't be surprised if the total were in the tens of thousands. Unless there is specific language to the contrary, each message represents only the personal opinion of its author. I claim no compilation copyright on comp.compilers. As far as I am concerned, anyone can reproduce any message for any purpose. Individual authors may retain rights to their messages, although I will not knowingly post anything that does not permit at least unlimited non-commercial distribution. If you find comp.compilers useful in writing a book, producing a product, etc., I would appreciate an acknowledgement of usenet and comp.compilers. -- How do I receive it? By reading comp.compilers on a system that gets net news. People sometimes ask me to send them messages as mail, but I don't have the resources to maintain a mailing list as well as a news group. (If you saw my computer, you'd know why.) If you absolutely cannot get net news, ask a nearby site that does get it to forward messages to you as mail. As far as I know, there are no formal forwarders to LISTSERV mailers or other networks or services, though I would be happy to help set them up if demand warranted it and someone wanted to arrange it. -- How do I submit a message? Mail it to compilers@iecc.cambridge.ma.us, also known as compilers@iecc.uucp or iecc!compilers. (iecc used to be known as esegue, some sites with stale routing data may still have that name.) I review messages nearly every day, usually including weekends, and most messages are posted to the net within a day after I receive them. Occasionally when I go on vacation there may be up to a week's delay, though I try to send out a message when that will happen. Most net news systems will automatically turn posted messages into mail to compilers, but some, particularly systems running notes at Hewlett Packard, don't do that correctly. As a result, I sometimes receive fifty copies of a message, all mangled slightly differently. Please mail your contributions unless you're sure your posting software works correctly. When you send a message to compilers, I understand that to mean that you want me to post it to usenet, which means it will be sent to tens of thousands of potential readers at thousands of computers all around the world. If you don't want me to post something, send it instead to compilers-request. (See below.) -- What happens to submitted messages? Barring mail problems, they arrive in a special mailbox here at iecc. I then edit the headers, trim down quoted text, fix typos and grammatical errors, remove cute signatures, and then post them to usenet. If I think a message needs more editing than that, I return it to the author for rewriting. The main reasons I return a message are that it appears more appropriate for another group, the message is too garbled to fix, it contains too much quoted material relative to the amount of new material, or I don't understand it. I also usually return messages that directly attack individuals, since the net has plenty of other places for ad-hominem battles. If a message asks a simple question I sometimes answer it myself rather than posting it. When two or three messages arrive with the same answer to a question, I usually post only one of them, with a comment crediting the others. If you send in a message and don't either see it posted or receive something back in a few days, it probably got lost in the mail and you should contact me, preferably via a different mail route. I post or respond to all messages except for ones that appear to have been sent by mistake, e.g. no contents, or contents consisting only of another quoted message. Sometimes when I'm feeling exasperated I disregard messages that re-ask one of the frequently asked questions that are answered below. One of the most time-consuming jobs in moderating the group is trimming down the quotes in followup articles. In most cases, you can expect readers to have seen the previous article, so only a few lines of quoted text should be needed to remind the reader of the context. I have installed a simple-minded quote filter that mechanically returns to the sender any message that contains more quoted than unquoted lines. Please edit your quotes before you send in a response, to avoid having the filter bounce your message. Since the quote filter is pretty dumb, I do look at bounced messages myself. If the filter bounces a message of yours by mistake, don't panic -- it'll get posted anyway. -- How do I respond to the author of a message? I try to be sure that every message contains valid From: and Reply-To: headers. The automatic "reply" commands in most news readers let you send mail to the author. Some obsolete news readers attempt to reply using the Path: header, but for technical reasons the Path: header in a moderated message cannot point to the actual author. In fact, the Path: header in a compilers message is deliberately a bad mail address, so if you have such a news reader you'll have to edit the addresses in responses yourself and, I hope, encourage your system manager to update your news and mail software. Sometimes mail to an author bounces, either because a gateway isn't working or because the return address is unregistered or otherwise bad. Please don't ask me to forward it, my machine is no better connected than anyone else's. (It's not on the Internet and only talks uucp.) If you send me a message obviously intended for the author of an item, I will discard it on the theory that if it wasn't important enough for you to send it to the right place, it isn't important enough for me, either. -- How do I contact the moderator? Send me mail at compilers-request@iecc.cambridge.ma.us. If for some reason your system chokes on that address (it shouldn't, it's registered) mail to Levine@yale.edu will get to me. I treat messages to compilers-request as private messages to me unless they state that they are for publication. -- Are back issues available? I have complete archives going back to the original mailing list in 1986. The archives now fill about 3 megabytes, and are growing at about 100K per month. People with ftp access can get them from primost.cs.wisc.edu, where James Larus has kindly provided space. Sooner or later I will set up an automated mail server, but in the meantime I handle requests by hand. Don't ask for a full set of back issues by mail, you won't get them. The archives are available via modem from Channel One, an excellent local BBS. You have to register, but no payment is needed to download the archives which are in Area 6. (If you call more than once or twice, it would be nice to sign up for at least the $25 trial membership.) The 2400 BPS telephone number is +1 617 354 8873, and the Telebit number is +1 617 354 0470. I have also published a printed edition of the 1990 messages grouped by thread and topic, and with some indexes. Send me mail for further details, or see the message about the book which should immediately follow this one. -- Some Frequently Asked Questions: NOTE: The various files that I have are in the compilers archive at primost.cs.wisc.edu. If you can FTP them, please do so rather than asking me to send them to you. * Where can I get a C or C++ grammar in yacc? Jim Roskind has written one of each, available for ftp from ics.uci.edu or mach1.npac.syr.edu. Another C grammar was posted to comp.sources.misc in June 1990, v13 i52, archive name ansi-c_su. GCC and G++ are based on yacc grammars and are available via FTP from prep.ai.mit.edu, among other places. * Where can I get a Fortran grammar in yacc? I have a small subset parser in the archive mentioned above. The F2C Fortran to C translator contains a full F77 parser and is available in source form via FTP from research.att.com and by mail from netlib@research.att.com. * Where can I get a Pascal grammar in yacc? I have one of those, too, in the archive mentioned above though I haven't tried to use it. * Where can I get a Cobol grammar in yacc? Nowhere, as far as I can tell. This question is asked every few months and there has never, ever, been any positive response. Perhaps some of the interested people could get together and write one. * Where can I get a Basic grammar in yacc? Take a look at uunet.uu.net:comp.sources.unix/volume2/basic which contains a Basic interpreter with yacc parser. * How can I get started with yacc and lex and compiler writing in general? By reading any of the many books on the topic. Here are a few of them: Aho, Sethi, and Ullman, "Compilers: Principles, Techniques, and Tools," Addison Wesley, 1986, ISBN 0-201-10088-6. Describes clearly and completely lexing and parsing techniques including the ones in yacc and lex. The authors work or have worked at Bell Labs with Steve Johnson and Mike Lesk, the authors of Yacc and Lex. Alan Holub, "Compiler Design in C," Prentice-Hall, 1990, ISBN 0-13-155045-4. A large book containing the complete source code to a reimplementation of yacc and lex. Quite well written, too, though it has a lot of errors. The fourth printing is supposed to correct most of them. Mason and Brown, "lex & yacc," O'Reilly, 1990, ISBN 0-937175-49-8. A short introduction with some completely worked out examples. The writing in the 1990 edition can be murky, but the next edition should be better. Donnely and Stallman, "The Bison Manual," part of the on-line distrubution of the FSF's Bison, a reimplementation of yacc. As with everything else from the FSF, full source code is included. Axel T. Schreiner and H. George Friedman, Jr., "Introduction to Compiler Construction with UNIX," Prentice-Hall, 1985. Oriented to tutorial work. Good for beginners. Develops a small subset-of-C compiler through the book. (Recommended by Eric Hughes .) Richard Hash comments that the book has many typographical errors, and readers should be suspicious of the examples until they actually try them. Richard Y. Kim reports that sources are available for FTP as a.cs.uiuc.edu:pub/friedman/tar. Bennett,J.P. "Introduction to Compiling Techniques - A First Course Using Ansi C, Lex and Yacc," McGraw Hill Book Co, 1990, ISBN 0-07-707215-4. It's intended for a first course in modern compiler techniques, is very clearly written, and has a full chapter on YACC. I found it to be a good introductory text before getting into the 'Dragon book'. (Recommended by John Merlin .) If anyone sends in others, I'll be happy to add them to the list. * Are there free versions of yacc and lex ? Vern Paxton's flex is a superior reimplementation of lex. It is available from the same places as Gnu sources. Berkeley Yacc is a quite compatible PD version of yacc by Bob Corbett available from ucbarpa.berkeley.edu. Gnu Bison is derived from an earlier version of Corbett's work and is also fairly compatible with yacc. Regards, John Levine, comp.compilers moderator -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Sun Sep 01 05:00:15 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: compilers-request@iecc.cambridge.ma.us (John R. Levine) Subject: Comp.compilers 1990 Annual Message-ID: Keywords: administrivia Sender: compilers-sender@iecc.cambridge.ma.us Supersedes: Organization: Compilers Central Date: Sun, 01 Sep 91 09:00:12 GMT Approved: compilers@iecc.cambridge.ma.us Expires: 1 Oct 91 23:59:00 GMT NOTE: This is a monthly repost of the message about the printed version of the 1990 comp.compilers message. Comp.compilers 1990 Annual Edited by John R. Levine The Comp.compilers 1990 Annual is a printed edition of the messages posted to the usenet newsgroup comp.compilers in 1990. Usenet is an informal distributed electronic bulletin board system connecting thousands of computers around the world. Most of the systems attached to it run some version of Unix, though others systems ranging from MS-DOS personal computers to Cray mainframes now participate. Comp.compilers is a moderated usenet news group addressing the topics of compilers in particular and programming language design and implementation in general. It started in 1986 as a moderated mailing list, but interest quickly grew to the point where it was promoted to a news group. Recent topics have included optimization techniques, language design issues, announcements of new compiler tools, and book reviews. Messages come from a wide variety of people ranging from undergraduate students to well-known experts in industry and academia. Authors live all over the world - there are regular messages from the U.S, Canada, Europe, Australia, and Japan, with occasional ones from as far away as Malaysia. The anarchic nature of usenet makes it impossible to tell how large the readership is, but the total is probably in the tens of thousands. The book's contents include 807 of the year's total 914 messages, leaving out only administrative messages and unanswered questions. The messages themselves are unedited except for removing boilerplate header and trailer lines. The book is 604 pages, each 11 x 8.5 inches with two pages of text side by side in reasonably legible 8 point type. Messages are grouped by topic (C, optimization, book reviews, etc.) and within each topic messages in a thread are grouped together. There is a permuted subject index, a keyword index, and an author index. The book is GBC bound, a plastic spiral binding that lies flat. Pricing The price is $40 per book, plus $2 sales tax for copies delivered in Massachusetts, plus appropriate postage and packaging per copy: Pick up in Cambridge free | Foreign surface $10 U.S. surface $3 | Foreign airmail: U.S. priority $5 | Americas $12 U.S. Federal Express $20 | Europe $20 Canada $7 | All other $30 No further discounts apply on single copies of the book, as this price is pre-discounted from the list price of $50. Quantity discounts and shipping charges for large or unusual orders can be negotiated. How to order All orders must be prepaid. Send a check payable to I.E.C.C. along with the delivery address. We cannot take purchase orders, credit cards, or COD orders. Foreign orders must be prepaid in U.S. dollars, preferably by a check on a U.S. bank, but anything our bank can handle is acceptable. (They charge $20 extra for foreign checks and $5 for incoming bank wires.) The mailing address is: I.E.C.C. P.O. Box 349 Cambridge MA 02238-0349 The book is also available at list price from several bookstores. Being real bookstores, they take credit cards and the like. Computer Literacy Bookshop, 2590 N 1st St, San Jose CA 95131 +1 408 435 1118 Quantum Books, 4 Cambridge Center, Cambridge MA 02141 +1 617 494 5042 The book has ISBN 0-944954-02-2, and is under the imprint of Center Book Publishers, Inc. -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Sun Sep 01 19:03:06 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: pardo@gar.cs.washington.edu (David Keppel) Subject: Re: HLL from Assembler Message-ID: <91-09-003@comp.compilers> Keywords: disassemble, FTP Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: pardo@gar.cs.washington.edu (David Keppel) Organization: Computer Science & Engineering, U. of Washington, Seattle References: <91-08-155@comp.compilers> Date: Sun, 1 Sep 91 21:51:32 GMT Approved: compilers@iecc.cambridge.ma.us motcid!ebony!bachww@uunet.UU.NET (Bud Bach) writes: >Looking for references on converting assembler to a HLL. There is program `decomp' by Jim Reuter that converts VAX object code to something approaching C. It makes a number of assumptions, but might be interesting nonetheless. It is available via anonymous ftp from `cs.washington.edu' (128.95.1.4) in `pub/decomp.tar.Z'. ;-D oN ( De Compiler, Boss, De Compiler! ) Pardo -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Mon Sep 02 18:06:24 EDT 1991 Xref: iecc comp.parallel:2120 comp.compilers:1835 Newsgroups: comp.parallel,comp.compilers,comp.vlsi Path: iecc!compilers-sender From: ds@theory.lcs.mit.edu (Denise Sergent) Subject: 1992 Brown/MIT Conference on VLSI and Parallel Systems Message-ID: <91-09-004@comp.compilers> Keywords: CFP, parallel Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: ds@theory.lcs.mit.edu (Denise Sergent) Organization: Laboratory for Computer Science, MIT Date: Fri, 30 Aug 1991 14:46:24 GMT Approved: compilers@iecc.cambridge.ma.us Call for Papers 1992 Brown/MIT Conference Advanced Research in VLSI and Parallel Systems The design of highly integrated or large-scale systems involves a set of interrelated disciplines, including circuits and devices, design automation, VLSI architecture, software systems, and theory. Successful research in any of these disciplines increasingly relies on an understanding of the other areas. This conference, the 14th in a series that has been held at Caltech, MIT, UNC Chapel Hill, Stanford, and UC Santa Cruz, seeks to promote interaction among researchers in all disciplines that relate to highly integrated systems. papers are solicited in the following and related areas: CIRCUITS AND DEVICES: Innovative electrical circuits, optical computing, automated semiconductor manufacturing, wafer-scale systems. DESIGN AUTOMATION: Synthesis and silicon compilation, layout and routing, analysis and simulation, novel design methods, architectural design support, design for test. VLSI ARCHITECTURE: Highly parallel architectures, special-purpose VLSI chips and systems, novel small-scale systems, I/O and secondary storage, packaging, and fault tolerance. SOFTWARE SYSTEMS: Architecture-driven programming models, parallel languages, compiling for concurrency, operating systems, synchronization. THEORY: Parallel algorithms, VLSI theory, layout and wireability analysis, I/O complexity, interconnection networks, reliability. Keynote Speaker STEPHEN NELSON Head of massively parallel systems development at Cray Research CONTRIBUTED PAPERS: Submit five copies of a draft paper, not to exceed 15 pages, with a 500-word abstract by TUESDAY, OCTOBER 8, 1991 to: Brown/MIT VLSI Conference 545 Technology Square Cambridge, MA 02139 Please include address, phone number, and email address, if available, for the contact author. Notification of acceptances will be sent by December 3, 1991. Camera-ready copy of accepted papers is due January 7, 1992 so that the proceedings can be available at the conference. ORGANIZATION OF THE CONFERENCE: The conference is organized jointly by the Department of Computer Science, Brown University and the MIT VLSI and Parallel Systems Group. The Conference Chair is Charles E. Leiserson (MIT) and the Local Arrangements Chair is Dan Lopresti (Brown). In order to keep the conference small and informal, attendance is by invitation only. If you would like an invitation or further information about the conference, contact Denise Sergent at the above address or at (617) 253-2046 (phone) or ds@theory.lcs.mit.edu (email). PROGRAM COMMITTEE: Program committee co-chairs are John Savage (Brown) and Tom Knight (MIT). The program committee consists of Sandeep Bhatt (Yale), Gaetano Borriello (U. Washington), Rich Brown (U. Michigan), Randy Bryant (Carnegie Mellon U.), Srinivas Devadas (MIT), Gershon Kedem (Duke U.), Monica Lam (Stanford), Jack Raffel (MIT Lincoln Labs), Sartaj Sahni (U. Florida), Carlo Sequin (U.C. Berkeley), Bob Sproull (Sun Microsystems) and Jeff Vitter (Brown). -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Mon Sep 02 18:18:39 EDT 1991 Xref: iecc comp.compilers:1836 comp.object:4212 Newsgroups: comp.compilers,comp.object Path: iecc!compilers-sender From: compres!chris@crackers.clearpoint.com (Chris Clark) Subject: Object-oriented parsers Message-ID: <91-09-005@comp.compilers> Keywords: yacc, parse, OOP Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: compres!chris@crackers.clearpoint.com (Chris Clark) Organization: Compilers Central References: <91-08-150@comp.compilers> Date: Mon, 2 Sep 91 09:36:43 EDT Approved: compilers@iecc.cambridge.ma.us Steve Boswell made a claim that the object-oriented parser generators Yacc++ and the Language Objects Library or Bison++ are not very OOP because they don't support a particular model of grammar development. I think of the method he describes as object-oriented recursive descent parsing. It is a very natural method of merging oop with parsing, and was an initial design approach we discussed for Yacc++. However, what Steve asks for can be easily done with (even non-oop) parser generators. Yacc++ has oop features which address other problems. I further argue that oop recursive-descent parsing is equivalent to [E]LL(k) methods unless the 1) host language supports non-deterministic or lazy-parallel procedure calls or something equivalent or 2) the parser writers use an arbitrary look-ahead technique in their parsing methods. Kevin Wall (kww@cblph.att.com) wrote text marked with > Steve Boswell (whatis@gnu.ai.mit.edu) wrote text marked with >> Adam (adam@visix.com) wrote text marked with >>> My notes refer to sections marked with [%d] >> Lexical/syntactic/semantic style parsing, while affording division of >> labor, is really only suited to procedural programming properties. . . . >> IDENTIFIER >> >> LOCAL_VARIABLE CLASS_ATTRIBUTE >> \ / >> \ / >> V V >> READ_ONLY WRITABLE FUNCTION PROCEDURE >> \ / | / >> \ / | / >> V V V V >> VALUE OPERATION >> \ / >> \ / >> V V >> IDENTIFIER_BASE [1] >> >> Thus, once an identifier is lexed, the symbol table can be consulted and >> the proper descendent of IDENTIFIER_BASE can be created and attached to >> IDENTIFIER (or returned by IDENTIFIER if IDENTIFIER is a pure parsing >> class.) IDENTIFIER is allowed to know about all the descendents of >> IDENTIFIER_BASE. [2] >> Then dynamic binding on the resulting types can be used to weed through the >> possibilities in whatever rule is being parsed. [3] . . . >> The parsing method of STATEMENT would have to tell whether an initial >> IDENTIFIER starts an ASSIGNMENT or PROCEDURE_CALL. [4] . . . >> So by dynamic binding, the correct parsing method would be called. [5] > I may be missing something here, but what I think you are saying is that > the language's grammar for which you are buiding a parser is implemented > via the class inheritance lattice!?! . . . [6] >> Mostly, yes. It keeps the grammar implementation abstract and it's >> very extendible (which is one of the main benefits of OOP anyways). [7] > Maybe I'm just old fashioned but I think parser generators based on > (extended) BNF notations (e.g., bison, yacc++) are a bit easier to change > if all you want to do is tweak the grammar a bit. >> I disagree. Shift/reduce and reduce/reduce errors are a pain in the >> arse, especially when the semantics of the language could resolve the >> ambiguity. [8] >> Tweaking the grammar in big ways (e.g. adding a new type >> of OPERATION called ONCE for Eiffel) is comparatively easy. [9] > I think that you definitely would need an OOPL that was well suited to > prototyping to be able to construct an "as-yet-undefined" language in > this manner. (No doubt one reason you thought CLOS to be suitable.) >> Actually, the only reason I suggested CLOS was that it allowed dynamic >> binding on its arguments and not just the object. (I know C++ does >> too, but I personally dislike C++.) This approach would also lend >> itself to languages being extended/redefined, which languages tend to >> do now and then. [10] > I for one, find this a case of simply trying to shoe-horn a problem into > an OOD. I always say (sometimes) "use the paradigm that fits the problem; > don't try to fit the problem to the paradigm". >>> Sorry, but I'll have to turn the accusation around. Simply because yacc >>> and lex are so well understood, most language designers assume that they >>> are the "best" paradigm to use. [11] What Steve Boswell is arguing for [1-7] is what I think of as OOP recursive-descent parsing. The model is basically this: Create a class for each terminal and non-terminal. Create methods for each non-terminal which correspond to each production that define the non-terminal. Use the inheritance hierarchy to provide generalizations of the non-terminals and terminals. The basic thrust here is that productions are mapped onto procedures (methods) which parse the corresponding sentences. This is the recursive-descent model. How does one do this with a parser generator? One performs the mapping in reverse. In particular, one can determine how to support the dynamic binding Steve desires with the features provided in any parser generator including yacc. Just define the non-terminals and terminals from the classes, define the productions that correspond to the parser methods, and define the inheritance hierarchy using productions. Here is how to do Steve's example: First, create a lexer which returns leaf types for the desired inheritance hierarchy based upon some form of semantic analysis. With Yacc++ and the Language Objects Library, this can be done with the following semantic action code in the lexer. IDENTIFIER : ('a'..'z')* ; { my_sym_ptr = yy_lookup(yy_lex_token(), yy_lex_len(), IDENTIFIER_); yy_lex_rdc() = yy_sym_type_this(my_sym_ptr); } This code says to find the identifier object in the symbol table and cause the lexer to return the type associated with that object. This is what Steve asked for in [2]. This precisely matches the runtime lookup of an object type within a class hierarchy. Different semantic models can be implemented by changing how the return type is selected. Second, define the inheritance hierarchy [1,6] as a series of productions in the parser. The way to read these productions is the class on the LHS is a base class for the derived classes on the RHS. In this model multiple inheritance is easy, just list the derived class in the RHS for each of its parent classes. For Steve's example [1] it would be: WRITABLE : LOCAL_VARIABLE | CLASS_ATTRIBUTE; VALUE : READ_ONLY | WRITABLE; OPERATION : FUNCTION | PROCEDURE; IDENTIFIER_BASE : VALUE | OPERATION; The reason this does exactly what Steve wants is certainly worth further discussion, but not in this posting. It can provide semantic disambiguation as he requests in [8]. Third, define the productions using the appropriate members of the hierarchy. This is what Steve requires in [4]. PROCEDURE_CALL : PROCEDURE "(" VALUE ("," VALUE)* ")" ";" When this grammar definition is run through a parser generator, the generator determines which token types are legal at each stage of the parse. The parser generator takes care of [3] and [5]. Steve argues in [7,9] that his model makes extension easier. Is it easier to add a new class to an inheritance hierarchy than it is to add a production to a grammar? He then brings up shift-reduce and reduce-reduce conflicts and semantic disambiguation [8]. Here lies the crux of his easy extension argument. If the host language, supports non-determinism, lazy-parallel evaluation of procedures, unification, dynamic programming, or something similar, then there may be an advantage to oop recursive-descent parsing. Otherwise, oop recursive-descent parsing is essentially equivalent to using an [E]LL(k) parser generator. How do I justify that claim??? At runtime the code must call a parsing method which will parse the sentence. In his example [4], he bases the parsing of the sentence upon its first token (and presumably the current context). If all tokens are read left-to-right (i.e. you always get tokens via get-next-token), this is exactly equivalent to [E]LL(1) parsing. If you allow yourself to read k-tokens of the sentence before determining which production to apply, you have [E]LL(k) parsing. If you allow yourself even more freedom, such as reading to the end of the token stream and using a Turing machine to decide which production to apply, you can get a much larger grammar class, but that is essentially defining your way out of the problem by using a more powerful method to begin with. [Since in most lisp dialects you can construct calls with an arbitrary number of arguments at runtime, I presume you can make CLOS (or whatever your implementation choice is) do your arbitrary dispatch. Personally, I find it hard to imagine how you would describe the parameter bindings for such vary-adic methods. I would probably use regular-expressions but that shows my bias :-). But I must admit, I'm a C++ person and do not know any of the oop extensions to lisp.] Also, if you start depending on scanning ahead too much, you may find it difficult explaining exactly what language your system supports. Unfortunately, aside from the arbitrary look-ahead via the runtime vary-adic call case, Steve's dynamic binding has not bought anything, except perhaps some runtime efficiency and cleanliness of code. Recursive-descent compilers based upon switching on the first k-tokens are a well-known technology. Some compiler writers like them. It is certainly easy to hack them. How does a [E][LA]LR(k) parser generator differ? When the generator runs, it simulates calling the parsing methods in parallel. As long as there is a token (within k tokens after the end of the production) which allows the parser generator to make a deterministic decision on which parsing method should have been called, the parser generator produces a conflict free parser. Thus, parser generators effectively support a deterministic form of parallelism and the class of languages they support is larger than the LL-class. The class of languages supported by LR(k) parser generators is generally large enough for most syntax descriptions, particularly if you allow the lexer the priviledge of inspecting the symbol table before determining the type of an object. The "dreaded" conflicts come from grammars which are ambiguous. Some methods for handling conflicts are well-known. The precedence directives of most parser generators do a good job of handling most shift-reduce conflicts. Kjell's recent proposal improves that for many dynamic cases. Using regular-expression (ELR) grammars can help eliminate any reduce-reduce conflicts. I suggest that you will find it is easier to eliminate conflicts than to rewrite a grammar to LL(1) form, which you need to do to use simple recursive-descent. Reason: all LL(1) grammars are LR(1) grammars. [Note, Yacc++ fixes a problem found in most yacc implementations of mid-production action code where yacc introduces artificial reductions which can cause spurious conflicts. Yacc++ executes mid-production action code as part of the shift and this reduces the number of conflicts.] I think the point of an abstract representation [7] is actually better served by a non-procedural representation of the language to be parsed. That is exactly what a grammar is. A grammar does not specify the method used to parse it. If the grammar is LL(1), an LL parser, an LR parser, a Turing machine, or some other mechanism could be used to parse it. A parser generator is merely a way to convert the non-procedural representation into a procedural representation. If the parser is written as a series of procedures in a programming language, it is much harder to switch to using a different parsing method. This is also my answer to [11]. Grammars are the best solution because they are non-procedural and capture exactly what we want to define. We usually find a well written ELR grammar to be one of the most concise, precise, and readable definitions of a language. The issues of extending a grammar [7,9,10] are certainly well worth consideration. Here is where we feel oop features should be added to parser generators. In particular, Yacc++ supports inheritance of productions from one language to another. This makes it easy to build experimental extensions of a language by simply deriving the extended language from the base language and then changing the appropriate productions in the extended grammar. We feel that the appropriate use of dynamic binding in an object oriented lexer/parser system is in allowing lexer or parser definitions to be switched at runtime, and this is the model that Yacc++ supports. This allows a system to easily support a family of dialects, such as a base language and its descendents. It can also facilitate parsing streams which come from more than one source (as in a distributed application). Chris Clark email : crackers.clearpoint.com!compres!chris Compiler Resources, Inc. voice : (508) 435-5016 3 Proctor Street fax : (508) 435-4847 Hopkinton, MA 01748 -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Tue Sep 03 22:38:05 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: paj@gec-mrc.co.uk Subject: Re: Object-oriented parsers Message-ID: <91-09-006@comp.compilers> Keywords: parse, OOP Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: paj@gec-mrc.co.uk Organization: Compilers Central References: <91-08-150@comp.compilers> Date: 3 Sep 1991 08:58:39-BST Approved: compilers@iecc.cambridge.ma.us In article <91-08-150@comp.compilers> whatis@gnu.ai.mit.edu (Steve Boswell) writ es: >Actually, the only reason I suggested CLOS was that it allowed dynamic >binding on its arguments and not just the object. (I know C++ does >too, but I personally dislike C++.) This approach would also lend >itself to languages being extended/redefined, which languages tend to >do now and then. Point of information: C++ does not allow dynamic binding on feature arguments. It allows overloading of feature names and uses type information to disambiguate the different features. As Dr. Meyer has pointed out, this is static, not dynamic. -- Paul Johnson Telex: 995016 GECRES G | Tel: +44 245 73331 Inet: paj@gec-mrc.co.uk | Fax: +44 245 75244 [I thought recent versions of C++ had at least limited dynamic binding.-John] -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Tue Sep 03 22:40:55 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: salomon@ccu.umanitoba.ca (Dan Salomon) Subject: Re: language design references wanted Message-ID: <91-09-007@comp.compilers> Summary: Designing new languages is a necessary evil. Keywords: design Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: salomon@ccu.umanitoba.ca (Dan Salomon) Organization: University of Manitoba, Winnipeg, Canada References: <91-08-147@comp.compilers> <91-08-149@comp.compilers> Date: Tue, 3 Sep 91 20:49:04 GMT Approved: compilers@iecc.cambridge.ma.us In article <91-08-149@comp.compilers> preston@helena.rice.edu (Preston Briggs) writes: >murphy@mips.com (Mike Murphy) writes: > >I usually think of language design as "The Pit of Despair". This argument is getting rather emotional. Let me try to enumerate the pros and cons of designing new languages. I) Language design for professionals by professionals: A) PRO 1) We do not yet have the ultimate language for any of the language design models: imperative, functional, or declarative. Anyone who says we do should post his nomination for the perfect programming language, and get ready for a barrage of critical rebuffs. 2) Language standardization committees only standardize well tried features. So, for example, the FORTRAN 90 committee needed input from people who had extended FORTRAN in useful and reliable ways. Other committees for C, Modula-2, Pascal, Etc. need the same kind of input. This is an argument for implementors adding features to the language they are implementing. 3) Programming techniques keep changing and languages must keep up. The latest example of this is the trend toward object-oriented programming. What new methods or styles lie ahead? B) CON 1) There are already too many languages. A recent "language list" posted on comp.lang.misc lists 950 languages! (It has probably grown since I unsubscribed.) Do you really want to add more bricks to the Tower of Babel? 2) Most new languages or new features are not really new, or are not significantly different. If the designer had looked a little harder, he could have found what he wanted, or something better. 3) Most "new" languages or new language features are designed with a highly egocentric point of view. The designer knows what he prefers, and discounts other opinions. For example, the design of Ada, which was supposed to be the ultimate imperative language shows a definite military stamp. II) Experimental languages designed by academics or students. A) PRO 1) It is a very educational process. The real difficulty of designing a beautiful, consistent, and powerful language is not fully appreciated until one tries. 2) Most really novel programming language ideas come out of and academic setting. Most go down the drain, but some stay and permanently affect the programming language landscape. B) CON 1) Proving the value of a new language or language feature is very difficult in an academic setting. It is tough to show that the set of problems that the language solves better is an important one, or that the set exists at all. It is impossible to win arguments of the form, "Well, this way of expressing the solution seems clearer to me," or "seems more natural to me." 2) Language design is very shaky ground on which to build an academic career. Niklaus Wirth is one of the most influential language designers, but he has had serious academic career trouble. 3) Similarly, trying to make a thesis out of a language design or feature design is risky business. You may be able to get away with it for a master's thesis, but it will be very tough to do it for a doctoral thesis. My opinion is that designing new languages is a necessary evil. Do it, but don't expect users to carry you off on their shoulders cheering. -- Dan Salomon -- salomon@ccu.UManitoba.CA Dept. of Computer Science / University of Manitoba Winnipeg, Manitoba, Canada R3T 2N2 / (204) 275-6682 -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Thu Sep 05 17:30:52 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: mark@hubcap.clemson.edu (Mark Smotherman) Subject: MIPSco -- compiler technology patents? Message-ID: <91-09-008@comp.compilers> Keywords: question Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: mark@hubcap.clemson.edu (Mark Smotherman) Organization: Compilers Central Date: Wed, 4 Sep 91 12:00:57 -0400 Approved: compilers@iecc.cambridge.ma.us I noticed at the end of Suneel Jain's SIGPLAN '91 paper, "Circular scheduling: A new technique to perform software pipelining," the following notice: "A patent application has been filed by MIPS Computer Systems, Inc. on some of the algorithms descirbed in this paper." I have several questions based on this: 1) Does MIPSco currently hold a number of compiler technology patents? 2) Is there a (new?) MIPSco corporate strategy to move as much of their compiler technology as possible under patent protection? 3) Is there a place in the design effort where patent infringement risk analysis is done? For example, are hardware designers and compiler writers given a list of patented devices/algorithms that they must avoid using? 4) When a new patent is issued to a competitor on an independently- discovered technique but the competitor happened to file first (and there being no prior art), is the offending design ripped out? Is the design reengineered to differ enough to escape infringement? Is licensing undertaken? Or, do you wait for the competitor to search for infringements? (Can you answer this in public? :-) ) 5) What is the relationship of a patented algorithm to research? Can grad students hack on the algorithm to investigate and improve? At what point must you license the algorithm? -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Thu Sep 05 17:32:25 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: David.Chase@Eng.Sun.COM (David Chase) Subject: Language design Message-ID: <91-09-009@comp.compilers> Keywords: design Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: David.Chase@Eng.Sun.COM (David Chase) Organization: Sun Microsystems, Mt. View, Ca. References: <91-08-147@comp.compilers> <91-08-149@comp.compilers> Date: Wed, 4 Sep 91 13:48:13 PDT Approved: compilers@iecc.cambridge.ma.us preston@helena.rice.edu (Preston Briggs) writes: >At any rate, the local lore is that compiler writers should _not_ design >languages. Instead, they should be confined to tiny cages and forced to >implement the language as specified, dammit. Sort of a corollary of the >old adage "give them an inch, they'll take a mile". I disagree, somewhat. The crucial point is that compiler writers must not be allowed to design the language AFTER it has been specified. BEFORE it is specified, if the people designing the language have any inclination towards designing an "efficiently executed" language, then compiler-writers had better be involved. They can offer advice about (1) what to add/subtract to make the language more optimizable. (2) what can be added/subtracted without cost. (3) what features can share costs (given that X is in the language, it costs little or nothing to add Y). (4) whether a feature must be "paid for" all the time, or only if it is used. In addition, compiler writers make dandy devil's advocates for language specifiers. If I were designing a new language, I'd pay a tremendous amount of attention to recent and not-so-recent work in type theory and type inference. See William Cook's work, Luca Cardelli's work, and scan through the SIGPLAN PLDI proceedings back through about 1988. (Anecdotes follow for sake of concreteness -- this is based on my experience as compiler-writer-but-not-on-the-committee for the design of Modula-3.) When Modula-3 was designed, I fought hard (from the peanut gallery) for multi-dimensional open arrays, arguing that (1) this feature makes the language more useful, especially for numerical codes; (2) given reduction-in-strength and loop-invariant code motion, we can do a good job compiling it; (3) (a compromise) if we restrict our "subarrays" to the top-level only (i.e., no chance of taking a submatrix, a pity), then the one-dimensional open case works just as well as it ever did; the only question remaining is whether the multidimensional case should be illegal, or "slow" (slow relative to what?) A battle that I lost was for first-class functions and first-class methods -- my arguments in favor of them were (1) we know how to optimize these in many common cases (see the Scheme, Orbit, and S1 Common Lisp papers); (2) the language already has garbage collection, exceptions, and threads; thus, most of the run-time machinery required to support first-class functions is already present. In hindsight, one thing that I should have pushed for was the idea of unaliased (by reference or value-result) parameters (by special declaration, if necessary); this is good because it is an optimization enabler (better for dependence analysis), compiler-checked documentation, and a good tool for helping to ensure that remote execution will work. Note that the "compiler writer" contribution here is not the only reason this should have been in the language, but it is a good reason. As a devil's advocate, I pointed out that shared variables might not behave as some people expected. According to the spec (and my pathological imagination), the code WHILE shared_variable = 0 DO END; could (and would, by general-purpose optimization algorithms) be optimized at least to the form register := shared_variable; WHILE (register = 0) DO END; and could quite likely be compiled to IF shared_variable = 0 THEN LOOP (* forever *) END; END; (Note that the goodness or badness of this transformation is not the issue; rather, I am only pointing out that the spec as written permits this. If this is bad, this indicates that the spec should be changed.) This is allowed because, in the absence of the use of the Thread interface, reads from a variable written by another thread see "an implementation-dependent value of its type". Given that globals will be loaded into registers whenever possible (for efficiency) one legal value is the old one. (An implication of this is that calls to procedures must be treated as touching all global variables, since (lacking other info) a Thread routine might get called.) David Chase Sun -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Thu Sep 05 18:50:44 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: "Eric A. Anderson" Subject: Re: language design references wanted Message-ID: <91-09-010@comp.compilers> Keywords: design, question Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: "Eric A. Anderson" Organization: Compilers Central References: <91-08-149@comp.compilers> <91-09-007@comp.compilers> Date: Wed, 4 Sep 1991 16:42:51 -0400 (EDT) Approved: compilers@iecc.cambridge.ma.us > In article <91-08-149@comp.compilers> Preston Briggs writes: > 1) We do not yet have the ultimate language for any of the > language design models: imperative, functional, or declarative. Can someone send me a listing of books on declarative languages? Because I now understand what imperative and functional languages are like, but I hadn't heard about declarative ones. (Of course I hadn't heard about functional languages until I got to college) -Eric -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Thu Sep 05 18:51:43 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: henry@zoo.toronto.edu (Henry Spencer) Subject: Re: language design references wanted Message-ID: <91-09-011@comp.compilers> Keywords: design Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: henry@zoo.toronto.edu (Henry Spencer) Organization: U of Toronto Zoology References: <91-08-147@comp.compilers> <91-08-149@comp.compilers> Date: Thu, 5 Sep 1991 16:16:32 GMT Approved: compilers@iecc.cambridge.ma.us preston@helena.rice.edu (Preston Briggs) writes: >At any rate, the local lore is that compiler writers should _not_ design >languages. Instead, they should be confined to tiny cages and forced to >implement the language as specified, dammit... It is important to decide what your objectives are. If you are building a compiler for more or less an existing language, it is a mistake to get involved in redesigning the language at the same time. The folks who did PL/C, oh so many moons ago, summed it up well (approximately): "in the end we decided to implement the language unchanged, warts and all, because it became clear that otherwise we would spend all our time and effort on language design instead of implementation". Language design, although fun, is an enormous time sink. Doing it well is much harder than it looks. -- Henry Spencer @ U of Toronto Zoology henry@zoo.toronto.edu utzoo!henry -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Thu Sep 05 18:53:47 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: mike@vlsivie.tuwien.ac.at (Michael Gschwind - EECS) Subject: code generator generators? Message-ID: <91-09-012@comp.compilers> Keywords: code, design, question Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: mike@vlsivie.tuwien.ac.at (Michael Gschwind - EECS) Organization: Compilers Central Date: Thu, 5 Sep 91 13:33:09 -0700 Approved: compilers@iecc.cambridge.ma.us What's the current state of research on code generator generators? While the front end side seems to be fairly well automated by now, back end generation still seems to be an unresolved issue. There are only two systems I can think of which are (or claim to be) able to generate back ends: * MESS, a system based on high-level semantics, by Lee&Pleban (if I remember correctly). They had two articles about 3 or 4 years ago, but one of the authors said that MESS was not in a distributable state. However, he was going to write a book on this approach. - Has anybody heard of any research in that direction. * GCC, which has probably the most workable - and the only in-production use - code generator generator. (There are several tool programs gen* which generate a set of insn-*.[ch] files, which could be thought of as "the code generator generator" part.) However GCC has some drawbacks, as it is targeted at a very specific subset of machines. Also, in a way, you can think of the back end of GCC-1.* as a glorified pattern matcher. GCC-2.* seems to be much better here. (I've never actually seen the GCC-2.* source code, but I've seen some machine descriptions for it, which allow for more sophisticated scheduling decisions than gcc-1.* machine descriptions do.) What about using constraint logic programming for code generation? This should allow to cut down on the possibilities to check, while still being more flexible than a static pattern matcher. (I've read a paper by Krall&Ertl on using CLP for scheduling of pipeline constraints for the Motorola 88k, and this seems to have worked quite well.) Mike Michael Gschwind, Dept. of VLSI-Design, Vienna University of Technology mike@vlsivie.tuwien.ac.at || mike@vlsivie.uucp [Peter Lee wrote a nice book on MESS, published by MIT Press, but still said that the code was too awful to distribute. -John] -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Fri Sep 06 18:19:00 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: metzger@bach.convex.com (Robert Metzger) Subject: Compiler Patents Message-ID: <91-09-013@comp.compilers> Keywords: bibliography Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: metzger@bach.convex.com (Robert Metzger) Organization: Compilers Central Date: Fri, 6 Sep 91 08:45:51 -0500 Approved: compilers@iecc.cambridge.ma.us Here's a list of compiler patents you should know about. I do not claim this list is exhaustive or without error. Consult a patent attorney if you need to know how they impact you. Complain to your Congressperson if you think patents are not the right way to protect software as intellectual property. The alternatives are: 1) copyright the source 2) trade secret 3) no protection ------------------------------------------------------------------------------ Patent Number 4,821,181 Date of Patent Apr 11, 1989 Inventor K. Iwasawa, Y. Tanaka Assignee Hitachi, Ltd. Method for Converting a Source Program of High Level Language Statement into Object Program for a Vector Processor Patent Number 4,773,007 Date of Patent Sep 20, 1988 Inventor Y. Kanada, K. Isida Assignee Hitachi, Ltd. Compiler Code Optimization Method for a Source Program Having a First and Second Array Definition and Use Statements in a Loop Patent Number 4,833,606 Date of Patent May 23, 1989 Inventor K. Iwasawa, Y. Tanaka Assignee Hitachi, Ltd. Compiling Method for Vectorizing Multiple DO-Loops in Source Program ----- Patent Number 4,965,724 Date of Patent Oct 23, 1990 Inventor I. Utsumi, Y. Mori Assignee Oki Electric Industry, Ltd. Compiler System Using Reordering of Microoperations to Eliminate Interlocked Instructions for Pipelined Processing of Assembler Source Program ----- Patent Number 4,710,872 Date of Patent Dec 1, 1987 Inventor R.G. Scarborough Assignee International Business Machines Corporation Method for Vectorizing and Executing on an SIMD Machine Outer Loops in the Presence of Recurrent Inner Loops Patent Number 4,656,583 Date of Patent April 7, 1987 Inventor M. Auslander, J. Cocke, P. Markstein Assignee International Business Machines Corporation Method for Improving Global Common Subexpression Elimination and Code Motion in an Optimizing Compiler Patent Number 4,885,684 Date of Patent Dec 5, 1989 Inventor E. Austin, J. Robertson Assignee International Business Machines Corporation Method for Compiling a Master Task Definition Data Set for Defining the Logical Data Flow of a Distributed Processing Network Patent Number 4,656,582 Date of Patent Apr 7, 1987 Inventor G. Chaitin, M. Hopkins, P. Markstein, H. Warren, Jr. Assignee International Business Machines Corporation Generating Storage Reference Instructions in an Optimizing Compiler Patent Number 4,782,444 Date of Patent Nov 1, 1988 Inventor A. Munshi, K. Schimpf Assignee International Business Machines Corporation Compilation Using Two-Colored Pebbling Register Allocation Method Such That Spill Code Amount is Invariant With Basic Block's Textual Ordering Patent Number 4,434,753 Date of Patent Mar 6, 1984 Inventor J. Rizzi Assignee International Business Machines Corporation Register Allocation System Using Recursive Queueing During Source Code Compilation Patent Number 4,567,574 Date of Patent Jan 28, 1986 Inventor H. Saade, W. Tindall Assignee International Business Machines Corporation Optimizing COBOL Object Code Instruction Path Length with respect to PERFORM Statments ------------------------------------------------------------------------------ Robert Metzger, CONVEX Computer Corp., Richardson, Texas [Patents are available on microfilm at most large libraries, or to get paper copies you can send a check for $2/patent and a list of the numbers you want to the Commissioner of Patents, Washington DC. -John] -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Fri Sep 06 18:19:59 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: pardo@gar.cs.washington.edu (David Keppel) Subject: Re: code generator generators? Message-ID: <91-09-014@comp.compilers> Keywords: code, design, bibliography Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: pardo@gar.cs.washington.edu (David Keppel) Organization: Computer Science & Engineering, U. of Washington, Seattle References: <91-09-012@comp.compilers> Date: Fri, 6 Sep 91 17:58:16 GMT Approved: compilers@iecc.cambridge.ma.us mike@vlsivie.tuwien.ac.at (Michael Gschwind - EECS) writes: >What's the current state of research on code generator generators? >[MESS, GCC, CLP] See recent work by Fraser & Henry; TWIG (David Hanson?), etc. (Sorry, my bib won't tell me about these right now). See also code generation by partial evaluation. 5 references follow; probably the most applicable ones are the Jones, Sestoft, Sondergaard paper and the Consel and Danvy paper. There are various other papers, but I don't have handy references. ;-D on ( Code degenerator degeneration ) Pardo 5 references follow: %A Charles Consel %A Olivier Danvy %T Static and Dynamic Semantics Processing %J POPL '91 %W From Consel/Danvy Nov. 1990 %X Derive mini-Algol -> Scheme compiler from formal semantics. For trivial programs, generates code about half the speed of Pascal/C. (S1.1) [C]ompiling a program amounts to dividing the representation of its formal meaning into compile time and run time forms, and to reducing the former while emitting a representatin of the latter as object code. (S3.2) Every program is static (available at compile time) and the store is dynamic (not available until runtime). Each valuation function is static in its program argument. (The basis of compiling via PE). Addresses: compiling a program, creating an interpreted compiler, creating a compiled compiler. "Object code" is not necessarily code, can be code + data (e.g., constants). Their object code is Scheme. %A A. Haraldsson %D 1978 %T A Partial Evaluator, and Its Use for Compiling Iterative Statements in Lisp %J ACM Principles of Programming Languages (POPL) 5 %P 195-202 %X Takes the source code of an interpreter and partially evaluates it over input to produce the same result as compiling the input. The evaluation is performed as a LISP source-to-source transformation. %A Anders Haraldsson %T A Program Manipulation System Based on Partial Evaluation %R Linko\\*:ping Studies in Science and Technology Dissertations No. 14 %I Department of Mathematics, Linko\\*:ping University %C S-581 83 Linko\\*:ping, Sweden %D 1977 %A A. Haraldsson %T Experiences from a Program Manipulation System %D July 1980 %R LiTH-MAT-R-80-24 %I Linko\\*:ping University %C Linko\\*:ping, Sweden %A Neil D. Jones %A Peter Sestoft %A Harald Sondergaard %T Mix: A Self-Applicable Partial Evaluaturo for Experiments in Compiler Generation %J Lisp and Symbolic Computation %V 2 %N 9-50 %P 10 %D 1989 -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Fri Sep 06 18:21:06 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: salomon@ccu.umanitoba.ca (Dan Salomon) Subject: Re: language design references wanted Message-ID: <91-09-015@comp.compilers> Keywords: design Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: salomon@ccu.umanitoba.ca (Dan Salomon) Organization: University of Manitoba, Winnipeg, Canada References: <91-09-007@comp.compilers> <91-09-010@comp.compilers> Date: Fri, 6 Sep 91 18:51:00 GMT Approved: compilers@iecc.cambridge.ma.us In article <91-09-010@comp.compilers> "Eric A. Anderson" writes: >Can someone send me a listing of books on declarative languages? >Because I now understand what imperative and functional languages are >like, but I hadn't heard about declarative ones. The best-known declarative language is PROLOG. The principle is that you declare some information, and then ask a question. The interpreter analyzes the information to give you an answer. A declarative program does not specify how to solve a problem, it merely supplies enough information to find an answer. For an overview of declarative languages see Chapter 8 of Ghezzi & Jazayeri "Programming Language Concepts" 2nd Ed. Wiley (1982). -- Dan Salomon -- salomon@ccu.UManitoba.CA Dept. of Computer Science / University of Manitoba Winnipeg, Manitoba, Canada R3T 2N2 / (204) 275-6682 -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Fri Sep 06 18:23:21 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: fkz@cs.brown.edu (Kenneth Zadeck) Subject: Optimization book by Allen, Rosen, and Zadeck Message-ID: <91-09-016@comp.compilers> Keywords: optimize, books Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: fkz@cs.brown.edu (Kenneth Zadeck) Organization: Compilers Central References: <91-08-070@comp.compilers> Date: Fri, 6 Sep 91 10:20:24 -0400 Approved: compilers@iecc.cambridge.ma.us The book, "Optimization in Compilers," edited by Frances Allen, Barry K. Rosen, and F. Kenneth Zadeck, is currently in development. It is expected to be published sometime late in 1992 or early in 1993 as an Addison-Wesley/ACM Press book. However, no specific publication date has yet been set. Watch for future announcements in "Communications of the ACM," among other places. Kenneth Zadeck -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Sat Sep 07 18:29:50 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: rms@gnu.ai.mit.edu (Richard Stallman) Subject: Software patents Message-ID: <91-09-017@comp.compilers> Keywords: legal Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: rms@gnu.ai.mit.edu (Richard Stallman) Organization: Compilers Central References: <91-09-013@comp.compilers> Date: Sat, 7 Sep 91 01:58:33 -0400 Approved: compilers@iecc.cambridge.ma.us A recent posting contained a list of various patents on compilation techniques. I've read some IBM compiler patents, and it was interesting to see that the things they patent today are the same sort that they used to publish in journals. (For example, the original register coloring technique was published, and a recent improved version was patented instead.) The writing is on the wall: *all* compilation techniques newer than 1985 will be off limits for compiler writers to use. If you're not sure what you think about software patents, I suggest you ask the League for Programming Freedom for its position papers. The paper on software patents explains how patents are bad for business--how they make software development difficult and expensive while doing little to advance the field. To get copies of the position papers, write to league@prep.ai.mit.edu. (The League for Programming Freedom is a political organization of programmers trying bring back the freedom to write programs. Basically, to go back to the system under which we worked just a few years ago.) [RMS is the founder of the Free Software Foundation and is active in the LPF. -John] -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Sat Sep 07 18:30:45 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: pardo@gar.cs.washington.edu (David Keppel) Subject: Re: MIPSco -- compiler technology patents? Message-ID: <91-09-018@comp.compilers> Keywords: legal Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: pardo@gar.cs.washington.edu (David Keppel) Organization: Computer Science & Engineering, U. of Washington, Seattle References: <91-09-008@comp.compilers> Date: Sat, 7 Sep 91 17:33:23 GMT Approved: compilers@iecc.cambridge.ma.us mark@hubcap.clemson.edu (Mark Smotherman) writes: >[A paper ends w/ a notice of patents applied on paper's algorithms.] >[Is there a cannonical list of designs to avoid?] >[What is the relationship of the algorithm to research?] A list of things I believe today but maybe not yesterday or tomorrow, and I'm not a lawyer: * There is no list of designs to avoid. You write your code, you hope nodbody sues you. * I believe that patented devices can always be built without fee for personal use, but that patented items cannot be sold or given away without the patent owner's consent. I expect that means that patented algorithms can be examined, but the code that contains them cannot be given away. * Many companies automatically apply for patents on promising items. If the patent is issued, it can be used as a bargaining chip. Patents can also be used to hurt the competative edge of a company that is alleged to infringe; if the owner of the patent can afford to sue, they can cost the alleged infringer lots of money and/or get a restraining order. * The original goal of patents was to provide inventors enough protection that they would be encouraged to invent for the public benefit. The League for Programming Freedom has an interesting paper on patents. I highly recommend reading it. You can get a copy via anonymous ftp from `prep.ai.mit.edu' in `pub/lpf/patents.texinfo'. The texinfo file can be formatted using `TeX', provided you get the `texinfo.tex' file from the same directory. ;-D on ( The Patent Tourney ) Pardo -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Sun Sep 08 10:19:30 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: henry@zoo.toronto.edu (Henry Spencer) Subject: Re: MIPSco -- compiler technology patents? Message-ID: <91-09-019@comp.compilers> Followup-To: misc.legal Keywords: legal Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: henry@zoo.toronto.edu (Henry Spencer) Organization: U of Toronto Zoology References: <91-09-008@comp.compilers> <91-09-018@comp.compilers> Date: Sun, 8 Sep 1991 03:20:36 GMT Approved: compilers@iecc.cambridge.ma.us In article <91-09-018@comp.compilers> pardo@gar.cs.washington.edu (David Keppel) writes: >* I believe that patented devices can always be built without fee for >personal use, but that patented items cannot be sold or given away without >the patent owner's consent. I expect that means that patented algorithms >can be examined, but the code that contains them cannot be given away. It has been a while since I looked at this stuff, but my recollection is that there is *no* personal-use exemption for patents. People who suggest this are thinking of copyrights, which have different rules. Examining a patented invention is okay -- the whole idea behind patents is to give inventors an incentive to place their ideas on public view rather than keeping them secret -- but *using* it in any way whatsoever requires a license. I would guess that running an algorithm to explore its behavior would be legitimate, but employing it for a practical purpose -- e.g. recompiling your favorite utility to make it run faster -- would not. (Caution, I am not a lawyer.) Heroically resisting the temptation to wade into the fray, I would suggest that further debate on whether software patents are good or bad is best taken elsewhere, now that people have been alerted to the relevance. -- Henry Spencer @ U of Toronto Zoology henry@zoo.toronto.edu utzoo!henry [Traditionally, research use is not infringement, but software and algorithm patents are such a murky area that nobody really knows. I second Henry's suggestion that the general topic of patents is outside the purview of compilers. If you want to discuss specific patents related to compiler technology, be my guest. Note that the patents themselves are in the public domain and you can reproduce and quote them without restriction. -John] -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Sun Sep 08 21:03:43 EDT 1991 Xref: iecc comp.compilers:1851 comp.sys.intel:990 Newsgroups: comp.compilers,comp.sys.intel Path: iecc!compilers-sender From: ponamgi@cs.unc.edu (ponamgi) Subject: Cross compiler for dec 5000, remote debugger for i860 Message-ID: <91-09-020@comp.compilers> Keywords: question Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: ponamgi@cs.unc.edu (ponamgi) Organization: University of North Carolina, Chapel Hill Distribution: usa Date: 8 Sep 91 18:58:51 GMT Approved: compilers@iecc.cambridge.ma.us Does anyone have a cross compiler for the dec 5000 that generates i860 code? Also a remote debugger for i860 is also needed. If anyone has info. on either please email. thanx, krish ponamgi@cs.unc.edu -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Tue Sep 10 08:16:03 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: horst@techfak.uni-bielefeld.de (horst Hogenkamp) Subject: Re: code generator generators? Message-ID: <91-09-021@comp.compilers> Keywords: code, bibliography, design Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: horst@techfak.uni-bielefeld.de (horst Hogenkamp) Organization: Universitaet Bielefeld, Technische Fakultaet. References: <91-09-012@comp.compilers> <91-09-014@comp.compilers> Date: Mon, 09 Sep 91 09:38:24 GMT Approved: compilers@iecc.cambridge.ma.us MIMOLA code generator: ====================== Lothar Nowak: Graph Based Retargetable Microcode Compilation in the MIMOLA Design System, Proc. 20th Workshop on Microprogramming (Micro-20), Colorado Springs, Dec 1987, pp. 126-132. Lothar Nowak und Peter Marwedel: Ein retargierbarer Mikrocode-Compiler und seine Anwendung in Entwurfsverifikation und Architekturbewertung, in: R. Valk(ed.): 18. GI-Jahrestagung, Informatik-Fachberichte, Vol. 188, Springer, Heidelberg, pp. 233-245 Lothar Nowak and Peter Marwedel: Verification of Hardware Descriptions by Retargetable Code Generation, 26th Design Automation Conference, 1989, pp 441-447 BEG (back end generator): ========================= This is probably one of the best: Helmut Emmelmann: BEG - a Back End Generator - Users Manual GMD Forschungsstelle an der Universitaet Karlsruhe Vincenz-Priessnitz-Str. 1 W7500 Karlsruhe GERMANY Others: ======= - Technical Report #7913, 1979, Technical University Munich, GERMANY - IEEE-Computer, August 1980, pp. 38-49, Title? - Informatik Fachberichte #25, 1980, pp. 125-142, Springer -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Tue Sep 10 08:20:28 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: anders@diku.dk (Anders Bondorf) Subject: Scheme partial evaluator Similix ftp-available Message-ID: <91-09-022@comp.compilers> Keywords: Scheme, FTP, optimize Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: anders@diku.dk (Anders Bondorf) Organization: Department of Computer Science, U of Copenhagen Date: Mon, 9 Sep 91 13:41:28 GMT Approved: compilers@iecc.cambridge.ma.us ----------------------------------------------------- Self-applicable partial evaluator for a Scheme subset Similix available via anonymous ftp ----------------------------------------------------- The partial evaluator Similix developed at DIKU, University of Copenhagen, Denmark, is now available via anonymous ftp. Partial Evaluation ------------------ Partial evaluation has been a rapidly growing area within the last decade, as recently seen at the ACM-SIGPLAN/IFIP Symposium on Partial Evaluation and Semantics-Based Program Manipulation (Yale University, New Haven, Connecticut, June 17-19 1991), and at the Conference on Functional Programming Languages and Computer Architecture (Harvard University, Cambridge, Massachusetts, August 28-30, 1991). Partial evaluation transforms programs with incomplete input data: when given a source program p and a part of its input s, a partial evaluator mix generates a so-called residual program p_s by specializing p with respect to s. Partial evaluation is also referred to as program specialization. When applied to the remaining input d, the residual program gives the same result as the source program would when applied to the complete input: p(s,d) = p_s(d) where p_s = mix(p,s) The main point in partial evaluation is one of efficiency: running the residual program p_s can be much faster than running the source program p. Instead of running p(s,d), it may therefore be worthwhile first to generate p_s and then apply it to d. The partial evaluator knows p and s and is therefore able to perform those of p's computations that depend only on s. Program p_s is thus more efficient than program p: it need not perform the computations that depend only on s --- these have already been performed at partial evaluation time. Some partial evaluators are self-applicable: we can use the partial evaluator to optimize itself. We may thus generate p_s in an alternative and more efficient way: p_s = mix_p(s) where mix_p = mix(mix,p) mix_p is a "program generator": given a value s for p's first input, mix_p constructs program p_s (more efficiently than mix itself). We may even go one step further: we can specialize mix with respect to itself! This is done as follows: mix_mix = mix(mix,mix) We can then generate mix_p in a faster way by applying mix_mix: mix_p = mix_mix(p) Applications: ------------- A well-known particular application of partial evaluation is automatic compiler generation from interpreters: write an interpreter for a programming language L and give it as input to the program mix_mix. The result is a compiler from L to the language T that the specialized programs generated by mix are written in. Partial evaluation has been used for many other applications, for instance: -- optimizing neural networks; -- optimizing computer graphics (ray-tracing); -- optimizing numerical computations; -- generating efficient pattern matchers; -- generating parsers from grammars; -- generating DFAs from regular expressions. General Description of Similix ------------------------------ Similix is an autoprojector (self-applicable partial evaluator) for a higher order subset of the strict functional language Scheme. Similix handles programs with user defined primitive abstract data type operators which may process global variables (such as input/output operators). Similix is automatic, that is, no user annotations (such as unfolding information) are required. Similix guarantees not to duplicate nor to discard computations (discarding may change termination properties of residual programs). Because it handles higher order programs, Similix is well-suited for partially evaluating for instance interpreters that use environments represented as functions, and interpreters written in continuation passing style. And since Similix is self-applicable, stand-alone compilers can be generated from interpreters. The Similix binding time debugger (developed by Christian Mossin) gives information to the user to help rewriting source programs in order to obtain better results by partial evaluation. Such rewritings are often called "binding time improvements". The binding time debugger is thus a tool for aiding manual binding time improving. ----------------------------------------------------------------------------- The current distribution should enable you to run Similix on Chez Scheme (version 2.0.3, 3.1, or 3.2) [Cadence Research Systems, 1989] and on T (version 3.1 (13), Sun4/SPARC version) [Yale University, 1989]. T is public domain. Similix is is written in pretty much standard Scheme, so it should not be too difficult to port it to other Scheme systems (earlier versions of Similix have been ported to other Scheme systems). How to ftp Similix: ftp ftp.diku.dk login: anonymous password: binary hash cd misc get Similix.tar.Z bye To decode the file Similix.tar.Z, run uncompress < Similix.tar.Z | tar xvpf - A directory named Similix then appears. Now read the file README in the Similix directory. Best regards, Anders Bondorf DIKU, Department of Computer Science University of Copenhagen Universitetsparken 1 DK-2100 Copenhagen \O Denmark e-mail: anders@diku.dk -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Tue Sep 10 08:22:31 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: bill@hcx2.ssd.csd.harris.com (Bill Leonard) Subject: Re: code generator generators? Message-ID: <91-09-023@comp.compilers> Keywords: code, design Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: bill@hcx2.ssd.csd.harris.com (Bill Leonard) Organization: Harris Computer Systems Division, Fort Lauderdale, FL References: <91-09-012@comp.compilers> Date: 9 Sep 91 15:14:42 GMT Approved: compilers@iecc.cambridge.ma.us In article <91-09-012@comp.compilers>, mike@vlsivie.tuwien.ac.at (Michael Gschwind - EECS) writes: > What's the current state of research on code generator generators? While the > front end side seems to be fairly well automated by now, back end > generation still seems to be an unresolved issue. There are only two systems > I can think of which are (or claim to be) able to generate back ends: > > * GCC, which has probably the most workable - and the only > in-production use - code generator generator. This statement is untrue. Harris' compiler technology, which we call CCG, is a code-generator generator. Actually, it is more than this, as the entire back-end (register allocation, optimization, and code generation) is target-independent. The technology is based on the PQCC research from Carnegie-Mellon, with significant enhancements made by Harris. Our CCG technology supports Ada, C, and FORTRAN; these compilers have been retargeted to 4 widely-varying architectures, including a 24-bit machine, the Motorola M68030, and the Motorola M88100. Our technology is much more general than GCC, which concentrates mostly on the instruction selection aspects of code generation, and which also is targeted for a specific subclass of architectures. Retargeting our CCG compilers is still not a trivial task, but it can be done in a much shorter time than writing a compiler from scratch, and the resulting compiler generates much higher-quality code than one typically gets from a first-release compiler. I apologize if this sounded like a commercial, but I wanted to emphasize that this technology is both practical and in commercial use. -- Bill Leonard Harris Computer Systems Division 2101 W. Cypress Creek Road Fort Lauderdale, FL 33309 bill@ssd.csd.harris.com -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Tue Sep 10 08:26:58 EDT 1991 Xref: iecc comp.compilers:1855 comp.lang.misc:5287 Newsgroups: comp.compilers,comp.lang.misc Path: iecc!compilers-sender From: cordy@qucis.queensu.ca (Jim Cordy) Subject: TXL 5.3 Release now available Message-ID: <91-09-024@comp.compilers> Followup-To: poster Keywords: FTP, tools, code, translator Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: cordy@qucis.queensu.ca (Jim Cordy) Organization: Computing & Information Science, Queen's University Date: Mon, 9 Sep 1991 20:30:51 GMT Approved: compilers@iecc.cambridge.ma.us Release 5.3 of TXL, a rapid prototyping system for programming languages and program transformations, is now available via anonymous ftp from qusuna.qucis.queensu.ca (130.15.1.100) in the directory 'txl'. Release 5.3 fixes a number of bugs in release 5.2, in particular a bug in patterns targeted at left-recursive productions, and adds support for arbitrary comment conventions, in particular for C and C++ commenting and the % operators. TXL 5.3 is distributed in portable ANSI C source form only, and you must compile it for your particular Unix system. It has been tested on all of the VAX, Sun/3, Sun/4, NeXT, and DECstation MIPS, and meets 'gcc -ansi -pedantic' so should compile on almost anything. Full information on the details of fetching TXL can be obtained by fetching the 00README file, like so: myunix% ftp 130.15.1.100 Connected to 130.15.1.100. 220 qusuna FTP server (Version 5.56 Thu Apr 18 13:08:27 EDT 1991) ready. Name (130.15.1.100:cordy): anonymous 331 Guest login ok, send ident as password. Password: cordy@myunix 230 Guest login ok, access restrictions apply. ftp> cd txl 250 CWD command successful. ftp> get 00README 200 PORT command successful. 150 Opening ASCII mode data connection for 00README (1688 bytes). 226 Transfer complete. local: 00README remote: 00README 1731 bytes received in 0.04 seconds (42 Kbytes/s) ftp> quit 221 Goodbye. myunix% I will attempt to service any email requests from those who do not have FTP access as well, but such requests will be serviced very slowly over the next couple of months and I don't have time to try to fix any email addresses that don't work from my site directly as sent to me. For those of you who have forgotten what TXL is good for, I have reproduced the TXL 5.3 ABSTRACT file below. Jim Cordy --- Prof. James R. Cordy cordy@qucis.queensu.ca Dept. of Computing and Information Science James.R.Cordy@QueensU.CA Queen's University at Kingston cordy@qucis.bitnet Kingston, Canada K7L 3N6 utcsri!qucis!cordy ----- TXL ABSTRACT ----- Subject: TXL 5.3, a Rapid Prototyping Tool for Computer Languages Release 5.3 of TXL: Tree Transformation Language is now available via anonymous FTP from qusuna.qucis.queensu.ca (130.15.1.100). TXL 5.3, (c) 1988-1991 Queen's University at Kingston ----------------------------------------------------- Here's the language prototyping tool you've been waiting for! TXL is a generalized source-to-source translation system suitable for rapidly prototyping computer languages and langauge processors of any kind. It has been used to prototype several new programming languages as well as specification languages, command languages, and more traditional program transformation tasks such as constant folding, type inference and source optimization. TXL is NOT a compiler technology tool, rather it is a tool for use by average programmers in quickly prototyping languages and linguistic tasks. TXL takes as input an arbitrary context-free grammar in extended BNF-like notation, and a set of show-by-example transformation rules to be applied to inputs parsed using the grammar. TXL will automatically parse inputs in the language described by the grammar, no matter if ambiguous or recursive, and then successively apply the transformation rules to the parsed input until they fail, producing as output a formatted transformed source. TXL is particularly well suited to the rapid prototyping of parsers (e.g., producing a Modula 2 parser took only the half hour to type in the Modula 2 reference grammar directly from the back of Wirth's book), pretty printers (e.g., a Modula 2 paragrapher took another ten minutes to insert output formatting clues in the grammar), and custom or experimental dialects of existing programming languages (e.g., Objective Turing was prototyped by transforming to pure Turing and using the standard Turing compiler to compile the result). TXL 5.3 comes with fully portable ANSI C source automatically translated from the Turing Plus original, self-instruction scripts and a pile of examples of its use in various applications. -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Tue Sep 10 08:28:47 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: shuksan!scott@bcstec.ca.boeing.com (Scott Moody) Subject: Re: code generator generators? Message-ID: <91-09-025@comp.compilers> Summary: another reference Keywords: code, design, bibiography Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: shuksan!scott@bcstec.ca.boeing.com (Scott Moody) Organization: The Boeing Co., MMST, Seattle, Wa. References: <91-09-012@comp.compilers> Date: 9 Sep 91 21:41:21 GMT Approved: compilers@iecc.cambridge.ma.us In article <91-09-012@comp.compilers>, mike@vlsivie.tuwien.ac.at (Michael Gschwind - EECS) writes: > What's the current state of research on code generator generators? While the > front end side seems to be fairly well automated by now, back end > generation still seems to be an unresolved issue. I just xeroxed a paper from SIGPLAN'88 conference proceedings titled: "Automatic Generation of Fast Optimizing Code Generators" Christopher Fraser - AT&T Alan Wendt - U of Arizona >From the abstract: "This paper describes a system that accepts compact specifications of an intermediate code and target machine and produces program code for an intergrated code generator and peephole optimizer. A compiler for most of C uses this package. It emits code comparable to pcc1's, but it runs over five times faster on preliminary benchmarks. This compiler also runs over twice as fast as a version of pcc2 with a hand-coded, VAX-specific code generator" -- Scott Moody, scott@shuksan.boeing.com, uunet!bcstec!shuksan!scott -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Wed Sep 11 00:46:30 EDT 1991 Xref: iecc comp.arch:13815 comp.compilers:1857 comp.lang.misc:5294 Newsgroups: comp.arch,comp.compilers,comp.lang.misc Path: iecc!compilers-sender From: larus@cs.wisc.edu (James Larus) Subject: New Technical Report: "Optimally Profiling and Tracing Programs" Message-ID: <91-09-026@comp.compilers> Keywords: performance, experiment, FTP, report Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: larus@cs.wisc.edu (James Larus) Organization: University of Wisconsin CS Dept. Date: Tue, 10 Sep 1991 17:56:35 GMT Approved: compilers@iecc.cambridge.ma.us **** A postscript version of this technical report is available for anonymous ftp from primost.cs.wisc.edu in pub/opt-prof-trace.ps.Z **** Optimally Profiling and Tracing Programs Thomas Ball James R. Larus Computer Sciences Department University of Wisconsin--Madison 1210 W. Dayton St. Madison, WI 53706 USA Technical Report #1031 This paper presents two algorithms for inserting monitoring code to profile and trace programs. These algorithms greatly reduce the cost of measuring programs. Profiling, which counts the number of times each basic block in a program executes, is widely used to measure instruction set utilization of computers, identify program bottlenecks, and estimate program execution times for code optimization. Instruction traces are the basis for trace-driven simulation and analysis and are used also in trace-driven debugging. The profiling algorithm instruments a program for profiling by choosing a placement of counters that is optimized--and frequently optimal--with respect to the expected or measured execution frequency of each basic block and branch in the program. The tracing algorithm instruments a program to obtain a subsequence of the basic block trace--whose length is optimized with respect to the program's execution--from which the entire trace can be efficiently regenerated. Both algorithms have been implemented and produce a substantial improvement over previous approaches, as the performance figures in this paper show. The profiling algorithm reduces the number of counters by a factor of two and the number of counter increments by a factor of three. The tracing algorithm reduces the file size and overhead of an already highly optimized tracing system by 20-40%. [An abridged version of this paper will appear in the 19th Symposium on Principles of Programming Languages (January 19-22, 1992).] -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Wed Sep 11 18:48:56 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: Greg Wilson Subject: Wanted: Pascal Compiler Producing Interpretable Output Message-ID: <91-09-027@comp.compilers> Keywords: Pascal, interpreter, question Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: Greg Wilson Organization: Edinburgh Parallel Computing Centre Date: 11 Sep 91 10:29:03 GMT Approved: compilers@iecc.cambridge.ma.us I am looking for a public-domain Pascal compiler which produces interpretable output, rather than machine code. I need interpretable output so that I can prototype various language extensions implementing various concurrent extensions to the language. If anyone knows of, or has, such a beast, I'd be very grateful. Thanks in advance, Greg Wilson Edinburgh Parallel Computing Centre, gvw@castle.edinburgh.ac.uk [I believe a Pascal translator of some sort was posted to one of the comp.sources newsgroups. Perhaps that would be a start. -John] -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Wed Sep 11 18:50:36 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: watson@stack.urc.tue.nl (Bruce Watson) Subject: Cross compilers HP9000 -> Intel 86 wanted Message-ID: <91-09-028@comp.compilers> Keywords: C, Pascal, question, 486 Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: watson@stack.urc.tue.nl (Bruce Watson) Organization: Compilers Central Date: Wed, 11 Sep 91 13:09:43 MED Approved: compilers@iecc.cambridge.ma.us I am interested in hearing about availability or experiences with cross compilers (C and Pascal) from HP 9000 to the (target machine) of Intel x86's. I am interested in also hearing about optimizing quality and completeness of libraries etc. My first guess is that Metaware, Oasys and Green Hills may be the people. Thanks in advance, Bruce Watson -- watson@stack.urc.tue.nl Department of Computer Science Eindhoven University of Technology The Netherlands -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Wed Sep 11 18:51:14 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: Tim Budd Subject: PQCC ref Message-ID: <91-09-029@comp.compilers> Keywords: question, tools Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: Tim Budd Organization: Compilers Central Date: Wed, 11 Sep 91 12:35:10 -0700 Approved: compilers@iecc.cambridge.ma.us The other day I needed to reference the old CMU PQCC project. What is the ``classic'' reference that overviews the entire project? (couldn't find anything in the bibliographics of either aho or fischer). -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Wed Sep 11 19:03:48 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: megatest!djones@decwrl.dec.com (Dave Jones) Subject: Here 'tis: ANSI C parser Message-ID: <91-09-030@comp.compilers> Keywords: C, parse, yacc, lex, code Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: megatest!djones@decwrl.dec.com (Dave Jones) Organization: Megatest Corporation, San Jose, Ca Date: 11 Sep 91 21:45:29 GMT Approved: compilers@iecc.cambridge.ma.us Hi all, I've written a prototype ANSI C parser, which follows at the end of this posting. Look it over. Perhaps I should post it to some sources group. I'm open to suggestions. I am aware that there are other parsers floating around, but I think this one has some features which may prove useful, or at least interesting, in the area of recognizing typedef-names. At least two other parsers which have been submitted previously had some measure of typedef-name capability. One of them I have not seen, but according to the author, who was gracious enough to correspond with me, it requires that typedef-names and only typedef-names begin with capital letters. As I intend to use this as the basis of real utilities, that was obviously not sufficient. I might have used that one as a starting-point, but I was unable to obtain it via ftp, due to technical problems. I obtained the other off of the net about a year or two ago. I was unable to understand much of the code without great difficulty. Maybe the fault was all within my addled brain (synapse-rot), but there it is. I felt I could never trust the program. So I undertook to write a parser prototype that was straight-forward enough to read and understand, and which has the capacity for defining and re-defining typedef-names in a scoped name-space. You may judge whether or not I succeeded. In any case, it will require quite a bit more work to make it into anything real. If you do build something out of it, please send me a copy! It could probably be sped up by obviating a lot of calls to malloc and free, and by streamlining the name-space lookup, which currently searches a stack of hash-tables. It has no error-recovery. I may work on that at a later date, but it's really not nearly so important as it used to be when you submitted a program to a sysop and got your syntax-error messages back the next day. (Nowdays turn-around is so fast that when I get a bunch of messages from a compiler, I usually just fix the first one and then feed it back to the compiler right away without even reading the others, because fixing one thing often clears up several error-messages.) The program has not been tested very much at all. If you find mistakes, please let me know! My email address is sun!megatest!djones. Happy parsing, Dave [Works OK for me once I changed the oldspeak index and rindex into strchr and strrchr in the lexer. -John] #! /bin/sh # This is a shell archive. Remove anything before this line, then unpack # it by saving it into a file and typing "sh file". To overwrite existing # files, type "sh file -c". You can also feed this as standard input via # unshar, or by typing "sh DISCLAIMER <<'END_OF_DISCLAIMER' X XThis software may work, or it may not. Use it at your own risk. END_OF_DISCLAIMER if test 65 -ne `wc -c README <<'END_OF_README' X XThis is a bare-bones prototype for an ANSI C parser. X XIt is based on _The C Programming Language, XSecond Edition_, Kernighan and Ritchie, Printice Hall, 1988. X XThe program is relatively untested, but I think it may be instructive. XUse it at your own risk. X XI would appreciate receiving any bug-fixes or improvements you may add. XBut do me a favor: If you modify anything, please remove my name from all Xthe files. No offense intended. You understand. X XThe program is designed to take as input the output of a C-preprocessor Xsuch as cpp. That is to say, it does not handle #include, #ifdef, et cetera, Xbut it DOES handle #line directives. It eats #pragma directives, but Xdoes nothing with them. X XThis first version does not do any semantic analysis except as needed Xto recognize typedef-names. X XCHANGES TO THE GRAMMAR X XSurprisingly few changes to the published grammar were needed to accommodate Xthe recognition of typedef-names by the scanner, e.g., X X1) the terminal-symbol TYPEDEF_NAME was introduced and the production X reducing identifier to typedef_name was removed; The symbol identifier X was replace by the terminal symbol IDENTIFIER. X X2) empty-productions for scanner feedback were introduced. X X3) The non-terminal symbols "function_declarator" and X "direct_function_declarator" were added to the grammar, to replace X "declarator" and its derived rules in extern function definitions. X X4) The non-terminal symbol type-specifier was split into two parts: X X actual_type_specifier: VOID | CHAR | INT | FLOAT | DOUBLE X | TYPEDEF_NAME | struct_or_union_specifier | enum_specifier X X type_adjective: SHORT | LONG | SIGNED | UNSIGNED X X XAdditionally, there seems to be a bug in the published grammar. XClassic C compilers happily accept this file: X X foo(); X bar() { foo(); } X XTo make that work, I added the production "untyped_declaration", which Xonly applies at the global level. X XFinally, one %prec directive was introduced to silence the Xyacc warning about the well-known shift/reduce conflict on ELSE. X X X XCONCERNING TYPEDEF-NAMES AND SCANNER FEEDBACK X XThere are several kinds of name-spaces in C: a name-space for each Xstruct or union, a separate name-space for labels, et cetera. XThe scanner must be aware of the name-space which differentiates Xtypedef-names from identifiers and enumeration-constants. In order for Xthe scanner to make that distinction, a scoped symbol table is necessary. XThis first version of the parser maintains only as much info there as is Xnecessary to handle typedef-names. X XThe identifier/typedef-name distinction is only Xuseful in contexts where the name-space applies. In other Xcontexts the distinction may be inapplicable, or in cases where Xtypedef-names are not legal, a semantic-analysis phase Xmight potentially be able to generate a better error message if the parser Xdid not flag a syntax error. In those contexts, we therefore use a Xproduction that reduces TYPEDEF_NAMEs, ENUMERATION_CONSTANTS, Xand IDENTIFIERs to the non-terminal symbol "identifier". X XEven with that production, it is still necessary to disable Xrecognition of typedef-names by the scanner in some contexts. This Xrequirement could be obviated only at the expense of approximately tripling Xthe size of the grammar. X XThe scanner therefore has a boolean state-variable called "idents_only" Xwhich specifies whether the scanner should return a token of type XTYPEDEF_NAME or ENUMERATION_CONSTANT when applicable, or should only Xreturn IDENTIFIER. X XProductions which interact with the name-space routines are prefixed Xwith "NS_". X XThe production "NS_td" turns typedef-recognition on, and "NS_ntd" turns Xit off. Notice that the state-change is necessarily effective only XAFTER parsing the token which triggers it. Because original yacc uses X"lazy lookahead", the routine lex_sync() is necessary to assure that Xthe trigger-token is actually parsed before the scanner state-variable Xidents_only is toggled. X XSee routine lex_sync() in file types.c. X XThe mechanism that toggles whether the scanner recognizes typedef_names Xas such is a little convoluted. It would be nice if the "NS_td" and "NS_ntd" Xnon-terminals could occur in matched sets within single production-rules. XHowever, doing so would require that much of the grammar be duplicated. XInstead, we will turn it off when an actual type-specifier is encountered in Xa declaration, and turn it back on at the end of each production that Xincludes a type-specifier, after any declarators to which the type-specifier Xapplies. Here is the rationale: X XThe _Annotated Reference Manual_ specifies that typedef-names may be Xredefined within an inner scope in declarations which contain Xa "type-specifier" [sic]. X X typedef char T1; X typedef char T2; X X foo() { X int T1, b; /* This redefines "T1" */ X static T2; /* But this does not re-define "T2". It is X * "legal", but declares nothing. X */ X } X X T1 ch; /* This is legal. */ X XI interpret this to mean that to redefine a type-name, the declaration Xmust contain something that actually names a type; the type must not Xbe merely implied. The rationale is to be able to parse things with Xonly a one-token lookahead. Therefore I think the following should Xdeclare nothing, just as the "static T2" above declares nothing. X X typedef int T1; X X foo() { X short T1; /* declares nothing. */ X short T1 i; /* declares i */ X } X XThere are four reserved words that can derive "type-specifier" in Xthe original grammar which do not name a specific type: XSHORT, LONG, SIGNED, UNSIGNED. I changed the grammar accordingly, calling Xthose four "type-adjectives", and the others "actual-type-specifiers". X XIf I am wrong about this, somebody let me know. X XWe must turn typedef-recognition off in declarator-lists Xand such when an actual-type-specifier is found, then back on again Xafter any related declarator is finished. X XBy inspecting the grammar we find that there are five productions Xwhich can derive a type-specifier indirectly: X X o function-definition X o declaration X o parameter-declaration X o type-name X o struct-declaration X XThose derive productions containing either "declaration-specifiers" Xor "specifier-qualifier-list" which in turn derive "type-specifier". X XTypedef-recognition must be turned back on at or before the end of each of Xthese five constructs, but only after any declarators that the constructs Xapply to have been parsed. The production NS_td does the job. X XNow a note concerning the addition of the non-terminal symbol X"function_declarator". A declarator for a function introduces a Xnew scope in the name-space to accommodate its parameters. That Xscope is destroyed either at the end of the declarator, or in the Xcase of a function-definition, at the end of the compound-statement that Xis the body of the definition. To distiguish the two cases, I added Xthe non-terminal symbols "function_declarator" and X"direct_function_declarator". They open the name-space scope, but do Xnot close it as "declarator" and "direct_declarator" do. Furthermore, XI did not duplicate the productions for non-function declarators such Xas array-declarators. Therefore some illegal programs will now be flagged with Xsyntax errors, where previously detection of the error would have been Xpostponed until the semantic analysis phase. For example, X X int foo[3] { int i = 1; } X XUnder the original grammar, that was a "syntactically legal" program, Xbecause "foo[3]" constituted a declarator, and the whole thing was therefore Xa function_definition. Now, because "foo[3]" is not a function_declarator, Xit produces a syntax error. If you think it was better the other way, Xjust add the other kinds of declarators to the the rules for Xfunction-declarator. X XHave fun, and good luck. END_OF_README if test 7753 -ne `wc -c emalloc.c <<'END_OF_emalloc.c' Xextern char* malloc(); X X/* Malloc that complains and exits when memory is used up. X */ Xchar* emalloc(size) X int size; X{ X static char msg[] = "C-parser out of memory\n"; X char* retval = malloc((unsigned)size); X X if(retval == 0) { X /* fprintf might call malloc(), so... */ X write(2, msg, sizeof(msg)); X exit(-1); X } X return retval; X} END_OF_emalloc.c if test 351 -ne `wc -c gram.y <<'END_OF_gram.y' X%{ X# include "types.h" Xtypedef char* yystype_def; X# define YYSTYPE yystype_def X%} X X%token BAD_TOKEN X%token INTEGER_CONSTANT CHARACTER_CONSTANT FLOATING_CONSTANT X ENUMERATION_CONSTANT IDENTIFIER STRING X X%token SIZEOF X%token PTR_OP INC_OP DEC_OP LEFT_OP RIGHT_OP LE_OP GE_OP EQ_OP NE_OP X%token AND_OP OR_OP MUL_ASSIGN DIV_ASSIGN MOD_ASSIGN ADD_ASSIGN X%token SUB_ASSIGN LEFT_ASSIGN RIGHT_ASSIGN AND_ASSIGN X%token XOR_ASSIGN OR_ASSIGN TYPEDEF_NAME X X%token TYPEDEF EXTERN STATIC AUTO REGISTER X%token CHAR SHORT INT LONG SIGNED UNSIGNED FLOAT DOUBLE CONST VOLATILE VOID X%token STRUCT UNION ENUM ELIPSIS X X%token CASE DEFAULT IF SWITCH WHILE DO FOR GOTO CONTINUE BREAK RETURN X X%left THEN X%left ELSE X X%start translation_unit X%% X X/**************************************************************** X ********* Name-Space and scanner-feedback productions ********** X ****************************************************************/ X X/* The occurance of a type_specifier in the input turns off X * scanner-recognition of typedef-names as such, so that they can X * be re-defined within a declarator-list. The switch is called X * "name_space_types". X * X * The call to lex_sync() assures that the switch gets toggled after X * the next token is pre-fetched as a lookahead. X */ X XNS_ntd : { lex_sync(); ntd(); } X ; X X/* Once the declarators (if any) are parsed, the scanner is returned X * to the state where typedef-names are recognized. X */ XNS_td : { lex_sync(); td(); } X ; X X/* NS_scope_push creates a new scope in the id/typedef/enum-const X * name-space. New levels are created by function-declarators X * and are created and destroyed by compound-statements. X * Thus, every occurance of a function-declarator must be X * followed, at the end of the scope of that declarator, X * by an NS_scope_pop. X */ XNS_scope_push : { scope_push(); td(); } X ; XNS_scope_pop : { scope_pop(); } X ; X X/* NS_struct_push creates a new name-space for a struct or union X * NS_struct_pop finishes one. X */ XNS_struct_push : { struct_push(); td(); } X; X XNS_struct_pop: { struct_pop(); } X; X XNS_id: { new_declaration(name_space_decl); } X; X X/* Begin a new declaration of a parameter */ XNS_new_parm: { new_declaration(name_space_decl); } X; X X/* Remember that declarators while define typedef-names. */ XNS_is_typedef: { set_typedef(); } X; X X/* Finish a direct-declarator */ XNS_direct_decl: { direct_declarator(); } X; X X/* Finish a pointer-declarator */ XNS_ptr_decl: { pointer_declarator(); } X; X X/* The scanner must be aware of the name-space which X * differentiates typedef-names from identifiers. But the X * distinction is only useful within limited scopes. In other X * scopes the distinction may be invalid, or in cases where X * typedef-names are not legal, the semantic-analysis phase X * may be able to generate a better error message if the parser X * does not flag a syntax error. We therefore use the following X * production... X */ X Xidentifier X : NS_ntd TYPEDEF_NAME NS_td X | IDENTIFIER X | ENUMERATION_CONSTANT X ; X X/************************************************************ X ***************** The C grammar per se. ******************* X ************************************************************/ X X/* X * What follows is based on the gammar in _The C Programming Language_, X * Kernighan & Ritchie, Prentice Hall 1988. See the README file. X */ X Xtranslation_unit X : external_declaration X | translation_unit external_declaration X ; X Xexternal_declaration X : NS_id function_definition X | NS_id declaration X | NS_id untyped_declaration X ; X Xfunction_definition X : function_declarator X compound_statement X NS_scope_pop X X | function_declarator X declaration_list X compound_statement X NS_scope_pop X X | declaration_specifiers X function_declarator NS_td X compound_statement X NS_scope_pop X X | declaration_specifiers X function_declarator NS_td X declaration_list X compound_statement X NS_scope_pop X ; X Xdeclaration X : declaration_specifiers NS_td ';' X | declaration_specifiers init_declarator_list NS_td ';' X ; X Xuntyped_declaration X : init_declarator_list ';' X ; X Xdeclaration_list X : declaration X | declaration_list declaration X ; X Xdeclaration_specifiers X : storage_class_specifier X | storage_class_specifier declaration_specifiers X | type_specifier X | type_specifier declaration_specifiers X | type_qualifier X | type_qualifier declaration_specifiers X ; X Xstorage_class_specifier X : NS_is_typedef TYPEDEF X | EXTERN X | STATIC X | AUTO X | REGISTER X ; X X/* Once an actual type-specifier is seen, it acts as a "trigger" to X * turn typedef-recognition off while scanning declarators, etc. X */ Xtype_specifier X : NS_ntd actual_type_specifier X | type_adjective X ; X Xactual_type_specifier X : VOID X | CHAR X | INT X | FLOAT X | DOUBLE X | TYPEDEF_NAME X | struct_or_union_specifier X | enum_specifier X ; X Xtype_adjective X : SHORT X | LONG X | SIGNED X | UNSIGNED X ; X Xtype_qualifier X : CONST X | VOLATILE X ; X Xstruct_or_union_specifier X : struct_or_union NS_struct_push X '{' struct_declaration_list NS_struct_pop '}' X | struct_or_union identifier NS_struct_push X '{' struct_declaration_list NS_struct_pop '}' X | struct_or_union identifier X ; X Xstruct_or_union X : STRUCT X | UNION X ; X Xstruct_declaration_list X : struct_declaration X | struct_declaration_list struct_declaration X ; X Xinit_declarator_list X : init_declarator X | init_declarator_list ',' init_declarator X ; X Xinit_declarator X : declarator X | declarator NS_td '=' initializer NS_ntd X ; X Xstruct_declaration X : { new_declaration(struct_decl); } X specifier_qualifier_list struct_declarator_list NS_td ';' X ; X Xspecifier_qualifier_list X : type_specifier X | type_specifier specifier_qualifier_list X | type_qualifier X | type_qualifier specifier_qualifier_list X ; X Xstruct_declarator_list X : struct_declarator X | struct_declarator_list ',' struct_declarator X ; X Xstruct_declarator X : declarator X | ':' constant_expression X | declarator ':' constant_expression X ; X Xenum_specifier X : ENUM '{' enumerator_list '}' X | ENUM identifier '{' enumerator_list '}' X | ENUM identifier X ; X Xenumerator_list X : enumerator X | enumerator_list ',' enumerator X ; X Xenumerator X : IDENTIFIER X | IDENTIFIER '=' constant_expression X ; X Xdeclarator X : direct_declarator NS_direct_decl X | pointer direct_declarator NS_ptr_decl X ; X Xdirect_declarator X : IDENTIFIER { declarator_id($$); } X | '(' declarator ')' X | direct_declarator '[' ']' X | direct_declarator '[' constant_expression ']' X | direct_declarator NS_scope_push '(' parameter_type_list ')' X NS_scope_pop X | direct_declarator NS_scope_push '(' ')' NS_scope_pop X | direct_declarator NS_scope_push '(' identifier_list ')' NS_scope_pop X ; X Xfunction_declarator X : direct_function_declarator NS_direct_decl X | pointer direct_function_declarator NS_ptr_decl X ; X Xdirect_function_declarator X : direct_declarator NS_scope_push '(' parameter_type_list ')' X | direct_declarator NS_scope_push '(' ')' X | direct_declarator NS_scope_push '(' identifier_list ')' X ; X Xpointer X : '*' X | '*' type_qualifier_list X | '*' pointer X | '*' type_qualifier_list pointer X ; X Xtype_qualifier_list X : type_qualifier X | type_qualifier_list type_qualifier X ; X Xparameter_type_list X : parameter_list X | parameter_list ',' ELIPSIS X ; X Xparameter_list X : parameter_declaration X | parameter_list ',' parameter_declaration X ; X Xparameter_declaration X : NS_new_parm declaration_specifiers declarator NS_td X | NS_new_parm declaration_specifiers NS_td X | NS_new_parm declaration_specifiers abstract_declarator NS_td X ; X Xidentifier_list X : IDENTIFIER X | identifier_list ',' IDENTIFIER X ; X Xinitializer X : assignment_expression X | '{' initializer_list '}' X | '{' initializer_list ',' '}' X ; X Xinitializer_list X : initializer X | initializer_list ',' initializer X ; X Xtype_name X : specifier_qualifier_list NS_td X | specifier_qualifier_list NS_td abstract_declarator X ; X Xabstract_declarator X : pointer X | direct_abstract_declarator X | pointer direct_abstract_declarator X ; X Xdirect_abstract_declarator X : '(' abstract_declarator ')' X | '[' ']' X | '[' constant_expression ']' X | direct_abstract_declarator '[' ']' X | direct_abstract_declarator '[' constant_expression ']' X | '(' ')' X | '(' parameter_type_list ')' X | direct_abstract_declarator '(' ')' X | direct_abstract_declarator '(' parameter_type_list ')' X ; X Xstatement X : labeled_statement X | compound_statement X | expression_statement X | selection_statement X | iteration_statement X | jump_statement X ; X Xlabeled_statement X : identifier ':' statement X | CASE constant_expression ':' statement X | DEFAULT ':' statement X ; X Xexpression_statement X : ';' X | expression ';' X ; X Xcompound_statement X : NS_scope_push '{' NS_scope_pop '}' X | NS_scope_push '{' statement_list NS_scope_pop '}' X | NS_scope_push '{' declaration_list NS_scope_pop '}' X | NS_scope_push '{' declaration_list statement_list NS_scope_pop '}' X ; X Xstatement_list X : statement X | statement_list statement X ; X Xselection_statement X : IF '(' expression ')' statement %prec THEN X | IF '(' expression ')' statement ELSE statement X | SWITCH '(' expression ')' statement X ; X Xiteration_statement X : WHILE '(' expression ')' statement X | DO statement WHILE '(' expression ')' ';' X | FOR '(' ';' ';' ')' statement X | FOR '(' ';' ';' expression ')' statement X | FOR '(' ';' expression ';' ')' statement X | FOR '(' ';' expression ';' expression ')' statement X | FOR '(' expression ';' ';' ')' statement X | FOR '(' expression ';' ';' expression ')' statement X | FOR '(' expression ';' expression ';' ')' statement X | FOR '(' expression ';' expression ';' expression ')' statement X ; X Xjump_statement X : GOTO identifier ';' X | CONTINUE ';' X | BREAK ';' X | RETURN ';' X | RETURN expression ';' X ; X Xexpression X : assignment_expression X | expression ',' assignment_expression X ; X X Xassignment_expression X : conditional_expression X | unary_expression assignment_operator assignment_expression X ; X Xassignment_operator X : '=' | MUL_ASSIGN | DIV_ASSIGN | MOD_ASSIGN | ADD_ASSIGN | SUB_ASSIGN X | LEFT_ASSIGN | RIGHT_ASSIGN | AND_ASSIGN | XOR_ASSIGN | OR_ASSIGN X ; X X Xconditional_expression X : logical_or_expression X | logical_or_expression '?' expression ':' conditional_expression X ; X X Xconstant_expression X : conditional_expression X ; X X Xlogical_or_expression X : logical_and_expression X | logical_or_expression OR_OP logical_and_expression X ; X Xlogical_and_expression X : inclusive_or_expression X | logical_and_expression AND_OP inclusive_or_expression X ; X Xinclusive_or_expression X : exclusive_or_expression X | inclusive_or_expression '|' exclusive_or_expression X ; X Xexclusive_or_expression X : and_expression X | exclusive_or_expression '^' and_expression X ; X Xand_expression X : equality_expression X | and_expression '&' equality_expression X ; X Xequality_expression X : relational_expression X | equality_expression EQ_OP relational_expression X | equality_expression NE_OP relational_expression X ; X Xrelational_expression X : shift_expression X | relational_expression '<' shift_expression X | relational_expression '>' shift_expression X | relational_expression LE_OP shift_expression X | relational_expression GE_OP shift_expression X ; X Xshift_expression X : additive_expression X | shift_expression LEFT_OP additive_expression X | shift_expression RIGHT_OP additive_expression X ; X Xadditive_expression X : multiplicative_expression X | additive_expression '+' multiplicative_expression X | additive_expression '-' multiplicative_expression X ; X Xmultiplicative_expression X : cast_expression X | multiplicative_expression '*' cast_expression X | multiplicative_expression '/' cast_expression X | multiplicative_expression '%' cast_expression X ; X Xcast_expression X : unary_expression X | '(' type_name ')' cast_expression X ; X X Xunary_expression X : postfix_expression X | INC_OP unary_expression X | DEC_OP unary_expression X | unary_operator cast_expression X | SIZEOF unary_expression X | SIZEOF '(' type_name ')' X ; X X Xunary_operator X : '&' | '*' | '+' | '-' | '~' | '!' X ; X X Xpostfix_expression X : primary_expression X | postfix_expression '[' expression ']' X | postfix_expression '(' ')' X | postfix_expression '(' argument_expression_list ')' X | postfix_expression '.' identifier X | postfix_expression PTR_OP identifier X | postfix_expression INC_OP X | postfix_expression DEC_OP X ; X Xprimary_expression X : IDENTIFIER X | constant X | STRING X | '(' expression ')' X ; X Xargument_expression_list X : assignment_expression X | argument_expression_list ',' assignment_expression X ; X Xconstant X : INTEGER_CONSTANT X | CHARACTER_CONSTANT X | FLOATING_CONSTANT X | ENUMERATION_CONSTANT X ; X X X%% END_OF_gram.y if test 12878 -ne `wc -c hash.c <<'END_OF_hash.c' X/* X * These are hash-routines from a standard library, stripped down X * and specialized. The search loops look like they might spin X * forever, but they proveably terminate due to an algebraic property X * of the REHASH function. I don't want to go into it now. Trust me. X */ X X#include "types.h" X#include "hash.h" X Xextern char* emalloc(); X Xstatic str_hash(); Xstatic declaration **new_table(); Xstatic int round_up_to_pwr2(); X Xhash_init_sized(obj, initial_table_size) X hash* obj; X{ X if(initial_table_size < 4) initial_table_size = 4; X obj->size = round_up_to_pwr2(initial_table_size); X obj->num_entries = 0; X obj->max_entries = obj->size/2 - 1; X obj->mask = obj->size - 1; X obj->hash_table = new_table(obj->size); X} X Xhash_clean(obj) X hash* obj; X{ X int i; X declaration **ht = obj->hash_table; X X for(i = 0; i < obj->size; i++) { X declaration *dc = ht[i]; X if(dc) { X free((char*)dc->name); X free((char*)dc); X } X } X X free((char*)obj->hash_table); X} X X Xstatic void hash_overflow(); X X#define HASH(cont) ((str_hash(cont)) & obj->mask ) X#define REHASH(num) (((((num)+1)*3) & obj->mask) ) X X/* Put a new entry into the table. If there was previously an X * equivalent entry in the table, return it. X * If there was not, return NULL. X */ X Xdeclaration* Xhash_put(obj, entry ) X hash* obj; X declaration *entry; X{ X X int bucket_number; X declaration **bucket; X X bucket_number = HASH(entry->name); X X while(1) { X X bucket = obj->hash_table + bucket_number; X X if ( *bucket == (declaration*)0 ) { X *bucket = entry; X obj->num_entries++; X if ( obj->num_entries > obj->max_entries ) X hash_overflow(obj); X return (declaration*)0; /* <======== added new entry */ X } X X if ( strcmp( entry->name, (*bucket)->name ) != 0) { X bucket_number = REHASH(bucket_number); X continue; /* <====== search some more (collision) */ X } X X /* Found old declaration. Replace. */ X { X declaration *old = *bucket; X *bucket = entry; X return old; /* <============== replaced entry */ X } X X } X X} X X X/* Find an equivalent entry. If there is none, return NULL. X * Do not change the table. X */ X Xdeclaration* Xhash_get(obj, name) X hash* obj; X char* name; X{ X X int bucket_number; X declaration** bucket; X X bucket_number = HASH(name); X X while(1) { X bucket = obj->hash_table + bucket_number; X X if ( *bucket == (declaration*)0 ) { X return (declaration*)0; /* <====== entry not found */ X } X X if ( strcmp( name, (*bucket)->name) != 0) { X bucket_number = REHASH(bucket_number); X continue; /* <====== search some more (collision) */ X } X X return *bucket; /* <====== found old declaration */ X } X X} X X X/* private routine doubles the size of the table. X */ X Xstatic void Xhash_overflow(obj) X hash* obj; X{ X declaration** old_hash = obj->hash_table; X int old_size = obj->size; X int recno; X X obj->max_entries = obj->size - 1; X obj->size= obj->size * 2; X obj->mask= obj->size - 1; X obj->hash_table = new_table(obj->size); X X /* Take everything that was in the old table, and put it X ** into the new one. X */ X X for (recno = 0; recno < old_size; recno++) { X declaration **mem = old_hash + recno; X if ( *mem != 0 ) { X int bucket_number = HASH((*mem)->name); X while(1) { X declaration** bucket = obj->hash_table + bucket_number; X if ( *bucket == 0 ) { X *bucket = *mem; X break; /* <==== copied it */ X } X X /* search some more */ X bucket_number = REHASH(bucket_number); X X } X } X } X X free((char*)old_hash); X X} X X X X/* private routine creates new hash-table. X */ X Xstatic Xdeclaration** Xnew_table(size) X{ X X declaration** table = X (declaration**)emalloc(sizeof(declaration)*size); X declaration** cursor = table; X declaration** end = table+size; X while(cursor < end) *cursor ++ = 0; X X return table; X} X X X Xstatic int Xround_up_to_pwr2(initial_table_size) X int initial_table_size; X{ X int size = 4; /* algorithm does not work with 1 or 2 */ X X while(size < initial_table_size ) { X size*= 2; X } X return size; X} X X X Xstatic Xstr_hash(str) X char *str; X{ X int retval = 0; X while(*str) retval += retval + (unsigned char)(*str++); X return retval; X} X END_OF_hash.c if test 4337 -ne `wc -c hash.h <<'END_OF_hash.h' X Xtypedef struct X{ X declaration **hash_table; X int size; X int max_entries; X int mask; X int num_entries; X}hash; X Xdeclaration* Xhash_get(); END_OF_hash.h if test 143 -ne `wc -c main.c <<'END_OF_main.c' X#include X Xint errors = 0; X Xmain(argc, argv) X char** argv; X{ X argc--; argv++; /* skip the progam-name */ X X if(argc == 0) { X name_space_init(); X yyparse(); /* parse stdin */ X } X else /* parse all files named in the command-line */ X for(; argc; argc--, argv++) { X X FILE* fp = freopen(*argv, "r", stdin); X X if(fp == 0) { X perror(*argv); X errors++; X } X else { X name_space_init(); X yyparse(); X } X X } X X return -(errors); X} END_OF_main.c if test 496 -ne `wc -c makefile <<'END_OF_makefile' XCFLAGS = -O XLEX = flex -f X# LEX = lex XYACC = yacc -vd X XOBJS = lex.yy.o \ X y.tab.o \ X main.o \ X hash.o \ X emalloc.o \ X name-space.o X Xparse-backend: $(OBJS) X $(CC) -g $(OBJS) -o parse-backend X Xy.tab.o: y.tab.c y.tab.h X Xy.tab.c y.tab.h: gram.y X $(YACC) gram.y X Xlex.yy.o: lex.yy.c y.tab.h X Xlex.yy.c: scan.l X $(LEX) scan.l END_OF_makefile if test 319 -ne `wc -c name-space.c <<'END_OF_name-space.c' X/* X * This code deals with the C name-space that distinguishes identifiers, X * enumeration-constants, and typedef-names. X * X * It implements just enough of the name-space to distinguish X * identifiers from typedef-names. With a few more keystrokes, it could X * also identify enumeration constants, which it does not do just now. X * There is no code to determine whether a name is doubly defined within X * a scope, or whether a declaration in an old-style function definition X * names something in the parameter-list, et cetera.. In other words, X * it is a "starter kit". X */ X X#include "types.h" X#include "hash.h" X#include X#include "y.tab.h" X X X#define MAX_NUM_LEVELS 16 X#define MAX_LEVEL (MAX_NUM_LEVELS-1) X Xint scope_level = 0; /* Counts the number of scopes within the name-space */ Xint decl_level = 0; /* For nested struct-declarations */ X Xint idents_only[MAX_NUM_LEVELS]; /* If one, this name-space is not X * applicable. Always return IDENTIFIER X * in that case. X */ X Xdeclaration decls[MAX_NUM_LEVELS]; /* Declarations in progress. */ Xhash tables[MAX_NUM_LEVELS]; /* Hash tables, one for each scope */ X Xextern declaration *hash_put(); Xextern char* emalloc(); X Xname_space_init() X{ X while(scope_level > 0) { X scope_pop(); X } X X decl_level = 0; X X /* Create the name-space for level zero, with an arbitrary X * initial table size. It's kind of big, because #include-files X * usually generate a lot of names. X */ X hash_init_sized(&tables[scope_level], 512); X} X X/* X * Create a new scope in the identifier/typedef/enum-const X * name-space. X */ Xscope_push() X{ X scope_level++; X X if(scope_level > MAX_LEVEL) { X fprintf(stderr, "C-parser: Nesting is too deep.\n"); X exit(-1); X } X X /* Initial size is again arbitrary. */ X hash_init_sized(&tables[scope_level], 32 ); X X} X X/* X * Destroy an old scope in the identifier/typedef/enum-const X * name-space. X */ Xscope_pop() X{ X X hash_clean(&tables[scope_level]); X scope_level--; X} X X/* X * Create a new name-space for a structure declaration. X */ Xstruct_push() X{ X decl_level++; X} X X/* X * Finish a structure declaration X */ Xstruct_pop() X{ X decl_level--; X} X X/* X * Look for the name in the name-space, beginning with X * the outermost scope. X */ Xdeclaration* Xfind_decl(name) X char *name; X{ X int look; X X for(look = scope_level; look >= 0; look--) { X X declaration *find; X X if((find = hash_get(&tables[look], name)) != 0) X return find; X X } X X return 0; X} X X/* X * Within this name-space, each defined name has a type, X * either IDENTIFIER, ENUMERATION_CONSTANT, or TYPEDEF_NAME. X */ Xtype_of_name(name) X char* name; X{ X X declaration *find = find_decl(name); X X if(!find) X return IDENTIFIER; X else X switch(find->type) { X case enum_const: X return ENUMERATION_CONSTANT; X case typename: X return TYPEDEF_NAME; X default: X return IDENTIFIER; X } X} X X/* X * Remember the name of the declarator being defined. X */ Xdeclarator_id(name) X char* name; X{ X declaration *decl = &decls[decl_level]; X decl->name = name; X} X X/* X * Begin a new declaration with default values. X */ Xnew_declaration(type) X enum decl_type type; X{ X declaration *decl = &decls[decl_level]; X decl->decl_type = type; X decl->type = identifier; X decl->scope_level = scope_level; X decl->name = 0; X} X X/* X * Remember that this declaration defines a typename, X * not an identifier. X */ Xset_typedef() X{ X decls[decl_level].type = typename; X} X X/* X * Put a name into the current scope. X */ Xstatic Xput_name() X{ X declaration *decl = &decls[decl_level]; X declaration *copy = (declaration*)emalloc(sizeof(declaration)); X X *copy = *decl; X X if(decl->decl_type == struct_decl) { X /* Should export the decl to the structure's name-space. X * ... for now, just boot it. X */ X free((char*)copy); X return; X } X X { X declaration* prev = hash_put(&tables[scope_level], copy); X /* X * If the declaration was already there, we should do X * the right thing... for now, to heck with it. X */ X X } X} X X/* finish the declarator */ Xdirect_declarator() X{ X put_name(); X} X X/* finish the declarator */ Xpointer_declarator() X{ X put_name(); X} X X X/* X * Turn on typedef_name (and enum-constant) recognition) X */ Xtd() X{ X idents_only[decl_level] = 0; X} X X/* X * Turn it off. X */ Xntd() X{ X idents_only[decl_level] = 1; X} END_OF_name-space.c if test 4417 -ne `wc -c parse <<'END_OF_parse' X X/usr/lib/cpp $* | /u/djones/src/C-3/parse-backend END_OF_parse if test 51 -ne `wc -c scan.l <<'END_OF_scan.l' XO [0-7] XD [0-9] XL [a-zA-Z_] XH [a-fA-F0-9] XE [Ee][+-]?{D}+ XFS (f|F|l|L) XIS (u|U|l|L) XW [ \t\f]* XLIT \"(\\.|[^\\"])*\" X X%{ X#include X#include "y.tab.h" Xextern char* yylval; Xint line_num = 1; Xextern int idents_only[]; X%} X X%% X X"/*" { comment(); } X X^{W}#{W}"line"?{W}{D}+{W}{LIT}.*\n { line_directive(); } X^{W}#{W}"line"?{W}{D}+[^"]*\n { line_directive(); } X^{W}#{W}"pragma".*\n { /* ignore pragma */ } X X\n { line_num++; } X[ \t\f]+ { } X X"auto" { return(AUTO); } X"break" { return(BREAK); } X"case" { return(CASE); } X"char" { return(CHAR); } X"const" { return(CONST); } X"continue" { return(CONTINUE); } X"default" { return(DEFAULT); } X"do" { return(DO); } X"double" { return(DOUBLE); } X"else" { return(ELSE); } X"enum" { return(ENUM); } X"extern" { return(EXTERN); } X"float" { return(FLOAT); } X"for" { return(FOR); } X"goto" { return(GOTO); } X"if" { return(IF); } X"int" { return(INT); } X"long" { return(LONG); } X"register" { return(REGISTER); } X"return" { return(RETURN); } X"short" { return(SHORT); } X"signed" { return(SIGNED); } X"sizeof" { return(SIZEOF); } X"static" { return(STATIC); } X"struct" { return(STRUCT); } X"switch" { return(SWITCH); } X"typedef" { return(TYPEDEF); } X"union" { return(UNION); } X"unsigned" { return(UNSIGNED); } X"void" { return(VOID); } X"volatile" { return(VOLATILE); } X"while" { return(WHILE); } X X{L}({L}|{D})* { return(identifier_or_typedef_name()); } X X0[xX]{H}+{IS}? { return(INTEGER_CONSTANT); } X0[xX]{H}+{IS}? { return(INTEGER_CONSTANT); } X0{O}+{IS}? { return(INTEGER_CONSTANT); } X0{O}+{IS}? { return(INTEGER_CONSTANT); } X{D}+{IS}? { return(INTEGER_CONSTANT); } X{D}+{IS}? { return(INTEGER_CONSTANT); } X X'(\\.|[^\\'])+' { return(CHARACTER_CONSTANT); } X X{D}+{E}{FS}? { return(FLOATING_CONSTANT); } X{D}*"."{D}+({E})?{FS}? { return(FLOATING_CONSTANT); } X{D}+"."{D}*({E})?{FS}? { return(FLOATING_CONSTANT); } X X{LIT} { return(STRING); } X X">>=" { return(RIGHT_ASSIGN); } X"<<=" { return(LEFT_ASSIGN); } X"+=" { return(ADD_ASSIGN); } X"-=" { return(SUB_ASSIGN); } X"*=" { return(MUL_ASSIGN); } X"/=" { return(DIV_ASSIGN); } X"%=" { return(MOD_ASSIGN); } X"&=" { return(AND_ASSIGN); } X"^=" { return(XOR_ASSIGN); } X"|=" { return(OR_ASSIGN); } X">>" { return(RIGHT_OP); } X"<<" { return(LEFT_OP); } X"++" { return(INC_OP); } X"--" { return(DEC_OP); } X"->" { return(PTR_OP); } X"&&" { return(AND_OP); } X"||" { return(OR_OP); } X"<=" { return(LE_OP); } X">=" { return(GE_OP); } X"==" { return(EQ_OP); } X"!=" { return(NE_OP); } X";" { return(';'); } X"{" { return('{'); } X"}" { return('}'); } X"," { return(','); } X":" { return(':'); } X"=" { return('='); } X"(" { return('('); } X")" { return(')'); } X"[" { return('['); } X"]" { return(']'); } X"." { return('.'); } X"&" { return('&'); } X"!" { return('!'); } X"~" { return('~'); } X"-" { return('-'); } X"+" { return('+'); } X"*" { return('*'); } X"/" { return('/'); } X"%" { return('%'); } X"<" { return('<'); } X">" { return('>'); } X"^" { return('^'); } X"|" { return('|'); } X"?" { return('?'); } X X. { return BAD_TOKEN; } X X%% X Xchar *filename = 0; Xextern int yychar; Xextern int decl_level; Xextern int errors; X Xyyerror(s) Xchar *s; X{ X errors++; X X fprintf(stderr, "%s: ", s); X X if(filename) X fprintf(stderr, "file \"%s\", ", filename ); X X fprintf(stderr, "line %d, token = \"%s\"\n", X line_num, yytext); X} X X#ifndef yywrap Xyywrap() X{ X return(1); X} X#endif X Xcomment() X{ X X int splat_seen = 0; X X for(;;) { X int ch = input(); X switch (ch) { X default: X splat_seen = 0; X break; X case '*': X splat_seen = 1; X break; X case '/': X if(splat_seen) X return; X else X splat_seen = 0; X break; X case 0: { X /* This should never happen, because cpp should X * catch the error first. X */ X yychar = BAD_TOKEN; X yyerror("Unterminated comment"); X exit(-(++errors)); X } X } X X } X X} X Xextern char* strpbrk(); Xextern char* index(); Xextern char* rindex(); Xextern char* emalloc(); X Xint line_directive() X{ X /* Handle directive left by the preprocessor, i.e. X * X * # line 123 "foo.h" X * # line 125 X * # 126 "foo.h" 2 X * X * et cetera. X */ X X char *line_ptr = strpbrk(yytext, "0123456789"); X char *file_ptr = index(line_ptr, '"') + 1; /* Start of file-name */ X X line_num = atoi(line_ptr); X X if(file_ptr != 0) { X X char *file_end = rindex(file_ptr, '"'); /* end */ X int len = file_end - file_ptr; X X if(filename != 0) X free(filename); X X filename = emalloc(len + 1); X X strncpy(filename, file_ptr, len); X filename[len] = 0; X X } X} X Xint identifier_or_typedef_name() X{ X /* Make a copy and set yylval. X */ X int len = strlen(yytext); X char *name = emalloc(len+1); X strncpy(name, yytext, len); X name[len] = 0; X X yylval = name; X X /* Return the type of the token, X * IDENTIFIER, TYPEDEF_NAME, or ENUM_CONSTANT X */ X if(idents_only[decl_level]) X return IDENTIFIER; X else { X return type_of_name(name); X } X X} X X Xlex_sync() X{ X /* Probably because of its use for interactive line-interpreters X * like "dc", original yacc uses a "lazy" lookahead, that is to say, it X * does not fetch a lookahead when the only action is the default X * reduction. But our scanner-feedback must keep the lookahead in X * sync. This routine sees to it that the lookahead has been X * fetched. X * X * yychar is the yacc lookahead token. It is -1 when X * yacc is being "lazy". yylex() is allowed to return -1 (or any X * negative int) to indicate EOF, but yacc uses 0 to indicate EOF. X */ X X if(yychar == -1) X if((yychar = yylex()) < 0) X yychar = 0; X} X END_OF_scan.l if test 6118 -ne `wc -c types.h <<'END_OF_types.h' X Xenum name_type { undefined, typename, identifier, enum_const }; Xenum decl_type { name_space_decl, struct_decl }; X Xtypedef struct { X char *name; X enum name_type type; X enum decl_type decl_type; X int scope_level; X X}declaration; X X END_OF_types.h if test 241 -ne `wc -c Keywords: tools, code, bibliography Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: preston@dawn.rice.edu (Preston Briggs) Organization: Rice University, Houston References: <91-09-029@comp.compilers> Date: Thu, 12 Sep 91 01:52:35 GMT Approved: compilers@iecc.cambridge.ma.us Tim Budd writes: >The other day I needed to reference the old CMU PQCC project. >What is the ``classic'' reference that overviews the entire project? One is An Overview of the Production Quality Compiler-Compiler Project B. W. Leverett, R. G. G. Cattell, S. O. Hobbs, J. M. Newcomer, A. H. Reiner, B. R. Schatz, W. A. Wulf Tech Report CMU-CS-79-105 Carnegie-Mellon University, Comp Sci Department February 1979 It seems like I saw a version of this printed in IEEE Computer, but I can't find it right off. Preston Briggs -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Fri Sep 13 13:12:12 EDT 1991 Newsgroups: comp.compilers Path: iecc!techfak.uni-bielefeld.de!horst From: horst@techfak.uni-bielefeld.de (Horst Hogenkamp) Subject: Re: PQCC references Message-ID: <91-09-032@comp.compilers> Keywords: tools, PQCC, code, bibliography Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: horst@techfak.uni-bielefeld.de (Horst Hogenkamp) Organization: Universitaet Bielefeld, Technische Fakultaet. References: <91-09-029@comp.compilers> Date: Thu, 12 Sep 91 11:44:41 GMT Approved: compilers@iecc.cambridge.ma.us In article <91-09-029@comp.compilers>, budd@fog.CS.ORST.EDU (Tim Budd) writes: > The other day I needed to reference the old CMU PQCC project. > What is the ``classic'' reference that overviews the entire project? > (couldn't find anything in the bibliographics of either aho or fischer). sorted by date --- good luck Horst Hogenkamp :::::::::::: PQCC :::::::::::: Leverett, Cattel, Hobbs, Newcomer, Reiner, Schatz and Wulf An Overview of the Production Quality Compiler-Compiler Project Computer 13(8):38-49 August 1980 Wulf, Barbacci, Brosgol, Cattel, Conradi, Hobbs, Knueven, Leverett, Newcomer, Reiner, Schatz, Stryker and Turini Specifications for the Phases of the PQCC CMU CS Dept. September 1980 Wulf PQCC: A Machine-Relative Compiler Technology IEEE 4th International COMPSAC Conference, Chicago, pp. 24-36 Also available as CMU Tech.Report CMU-CS-80-144 October 1980 Newcomer PQCC Intermediate Machine Description Language CMU CS Dept. July 1981 Leverett Topics in Code Generation and Register Allocation CMU-CS-82-130 28 July 1982 Wulf and Nori Delayed Binding in PQCC Generated Compilers CMU-CS-82-138 4 October 1982 -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Fri Sep 13 13:14:30 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: clc5q@hemlock.cs.Virginia.EDU Subject: Re: PQCC ref In-Reply-To: <91-09-029@comp.compilers> Message-ID: <91-09-033@comp.compilers> Keywords: code, bibliography, tools Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: clc5q@hemlock.cs.Virginia.EDU Organization: University of Virginia Computer Science Department Date: Thu, 12 Sep 91 09:29:32 EDT Approved: compilers@iecc.cambridge.ma.us In article <91-09-029@comp.compilers> budd@fog.CS.ORST.EDU (Tim Budd) writes: >The other day I needed to reference the old CMU PQCC project. >What is the ``classic'' reference that overviews the entire project? >(couldn't find anything in the bibliographics of either aho or fischer). Leverett, B.W., R.G.G. Cattell, S.O. Hobbs, J.M. Newcomer, A.H. Reiner, B.R. Schatz, and W.A. Wulf: "An Overview of the Production Quality Compiler-Compiler Projects," IEEE Computer, Vol. 13, No. 8, August 1980, pp. 38-49. This is derived from the CMU Technical Report CMU-CS-79-105, published by the same authors, with the same title, in 1979. I found the reference in the final chapter of the Tremblay and Sorenson text, "The Theory and Practice of Compiler Writing," the final chapter of which is a good exposition of compiler-compiler projects. See pp. 743ff. Also, once I had the reference, I noticed that it IS in the Dragon book bibliography, page 769 of the 1986 edition, and presumably in the same place in the 1988 printing (which I don't have, unfortunately.) If you scanned for "PQCC" you wouldn't see it, however, as the abbreviation is expanded in the reference title. It isn't in the Fischer text. -- ||| clc5q@virginia.edu (Clark L. Coleman) [Art Duncan and David Lamb also sent in this reference. Thanks. -John] -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Fri Sep 13 13:16:23 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: "Clifton Royston HNL (808)625-3234" Subject: Re: code generator generators? Message-ID: <91-09-034@comp.compilers> Keywords: code, question Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: "Clifton Royston HNL (808)625-3234" Organization: VeriFone Inc., Honolulu HI References: <91-09-012@comp.compilers> Date: 12 Sep 91 12:13:10 HST Approved: compilers@iecc.cambridge.ma.us In article <91-09-012@comp.compilers>, mike@vlsivie.tuwien.ac.at (Michael Gschwind - EECS) writes: > What's the current state of research on code generator generators? While the > front end side seems to be fairly well automated by now, back end > generation still seems to be an unresolved issue. There are only two systems It depends partly on what you mean by back-end generation. I can see two alternate definitions which might seem reasonable: 1) Instead of writing specific instructions to generate machine code for each intermediate-code construct, you write a table in some special format which is "compiled" into executable code to pattern-match and generate the machine code. 2) You write a table which characterizes the instruction set of the target machine, and some tool determines how best to match those instructions to your intermediate code. The distinction here is pretty hazy, but I think there is a difference between _characterizing_ the target machine code, as in (2), and _specifying_ matches, as in (1). I would imagine most of the above described systems fall somewhere in between the two extremes. Having said this, our organization uses the Amsterdam Compiler Kit, which employs a back-end generator falling somewhere between (1) and (2). The input text file contains some sections characterizing the target machine instructions (especially in terms of registers used, side-effects, etc.) and some which specify how you want them matched to the intermediate code. The intermediate code for this system is a stack-machine p-code, so the code generation proceeds both by matching sequences of instructions and by matching the simulated stack contents (or "fake-stack".) Since I don't myself work with the code-generation part of the system, I have probably got it a little wrong and oversimplified, but thought this would be of interest. BTW, I would not claim the Amsterdam Compiler Kit is the latest word; it has been around since the early-middle '80s. -- Clifton Royston clifton_r@zon.verifone.com -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Fri Sep 13 13:35:19 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: John R. Levine Subject: 1991 Compilers book, maybe Message-ID: <91-09-035@comp.compilers> Keywords: administrivia Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: John R. Levine Organization: Compilers Central Date: Fri, 13 Sep 91 13:30:16 EDT Approved: compilers@iecc.cambridge.ma.us I am trying to decide whether to print a paper version of the 1991 compilers messages, like I did for the 1990 ones. The 1990 edition has so far sold 30 copies to book stores and 56 to individuals, which is about what I'd expected but doesn't put it on anyone's best seller list. There has been considerably more traffic in 1991 than in 1990 so a 1991 book would be longer, about 900 pages rather than 600, and cost more, probably $50 rather than $40 for direct orders, and a bookstore list price of $70 rather than $50. I'd be interested to hear from people who've bought the 1990 book, how useful you've found it and whether you plan to get the 1991 book. Anyone who still wants the 1990 book should order soon, since I only have a dozen copies left. Regards, John Levine, comp.compilers moderator johnl@iecc.cambridge.ma.us or {spdcc|ima|world}!iecc!johnl -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Fri Sep 13 23:29:40 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: Jerry Heyman Subject: Re: Language Design Reference Message-ID: <91-09-036@comp.compilers> Keywords: design Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: Jerry Heyman Organization: Compilers Central References: <91-09-007@comp.compilers> <91-09-010@comp.compilers> Date: Fri, 13 Sep 91 14:29:47 -0600 Approved: compilers@iecc.cambridge.ma.us Another book to check out is: Design of Very High-Level Computer Langaues: A User-Oriented Approach, 2nd ed Melvin Klerer McGraw-Hill, Inc. 1991 In article <91-09-027@comp.compilers> Greg Wilson writes: >I am looking for a public-domain Pascal compiler which produces >interpretable output, rather than machine code. While not PD, there is a new book (and diskette) available for a Pascal Interpreter (that also includes a symbolic debugger): Writing Compilers and Interpreters: An Applied Approach Ronald Mak John Wiley & Sons, 1991 jerry ---===--- Jerry Heyman external : jerry@dcheney.austin.ibm.com IBM PSP Dev Env Tools MS 2401 VNET : HEYMAN at AUSTIN Austin, TX 78758 internal : jerry@heyman.austin.ibm.com -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Sun Sep 15 20:15:05 EDT 1991 Xref: iecc comp.arch:13931 comp.compilers:1868 comp.sys.sun:10609 comp.sys.sgi:10729 comp.sys.mips:1829 Newsgroups: comp.arch,comp.compilers,comp.sys.sun,comp.sys.sgi,comp.sys.mips Path: iecc!compilers-sender From: larus@cs.wisc.edu (James Larus) Subject: QP (Quick Program Profiler) Release Message-ID: <91-09-037@comp.compilers> Originator: larus@primost.cs.wisc.edu Keywords: report, FTP, analysis, performance Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: larus@cs.wisc.edu (James Larus) Organization: U of Wisconsin CS Dept Date: Sun, 15 Sep 1991 20:41:51 GMT Approved: compilers@iecc.cambridge.ma.us QP: A Quick Program Profiler QP is an exact and efficient program profiler. It rewrites a program's executable file (a.out) by inserting code to record the execution frequency of every basic block (straight-line sequence of instructions). >From these counts, another program QP_STATS can calculate the execution cost of procedures in the program. Unlike the Unix tools PROF and GPROF, QP records exact execution frequency, not a statistical sample. QP operates in two modes. In "slow" mode, it places a counter in each basic block in a program--in the same manner as the MIPS tool PIXIE. In "quick" mode, QP places counters on an infrequently-executed subset of the edges in the program's control-flow graph. This placement can reduce the cost of profiling by 3-4 times. Since there is no such thing as a free lunch, quick profiling requires more program analysis and consequently slows QP and QP_STATS. The additional cost to instrument a program and report results, however, is small and is quickly gained back when profiling long-running programs. QP offers a number of advantages over existing systems: + On MIPS systems, QP typically requires less overhead than PIXIE and can profile programs that use signals. QP can also produces hierarchical profiles (like GPROF). + On SPARC-based systems, QP offers exact instruction counts, instead of a PC-histogram that is subject to quantization errors. QP also does not require recompilation of the program. QP currently runs on MIPS and SPARC-based systems. I have verified the ports on a DECstation and Sun 4 by profiling the entire SPEC benchmark suite and other programs. A port to the the Motorola 88000 is under way. QP is written to be portable--all of the machine-specific features are collected in a single file. Porting to a new machine requires approximately 1 month of effort. The table below shows the overhead cost of slow and fast QP profiling and the MIPS program PIXIE: Slow Quick Pixie SPEC Overhead Overhead Overhead Benchmark % % % gcc 224 78 169 espresso 185 98 113 spice 68 39 43 doduc 33 4 35 nasa7 8 6 3 li 136 85 157 eqntott 158 55 180 matrix30 13 13 7 fpppp 17 12 13 tomcatv 10 9 8 [Overhead measured on a DECstation 5000 with the SPEC benchmarks compiled at -O2 to permit register scavengering. Overhead for QP is slightly larger for SPEC benchmarks compiled at the standard level of -O3 or -O4.] Documentation ============= The algorithms in QP are described in a technical report: Thomas Ball and James R. Larus, "Optimally Profiling and Tracing Programs," Computer Sciences Technical Report #1031, University of Wisconsin, July 1991 (To appear POPL '92). A postscript version of the technical report is available for anonymous ftp from primost.cs.wisc.edu in the file ~ftp/pub/opt-prof-tracing.ps.Z Obtaining QP ============ QP is distributed with the full source and a small amount of documentation. QP is copyrighted by me and is distributed under license. A copy of the license is available on primost.cs.wisc.edu in ~ftp/pub/qp-license.ps.Z or it can be obtained by writing to me at the address below. Send a signed copy of the license and a check for $300.00 (US) for a tape copying charge. Please make the check payable to "Computer Sciences Fund -- University of Wisconsin Foundation." The foundation's federal taxpayer identification number is 39-074-3975. James Larus Computer Sciences Department 1210 West Dayton Street University of Wisconsin Madison, WI 53706 larus@cs.wisc.edu (608) 262-9519 -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Tue Sep 17 01:00:01 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: jourdan@minos.inria.fr (Martin Jourdan) Subject: Re: code generator generators? Message-ID: <91-09-038@comp.compilers> Keywords: code, bibliography, design Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: jourdan@minos.inria.fr (Martin Jourdan) Organization: INRIA, Rocquencourt, France References: <91-09-012@comp.compilers> <91-09-014@comp.compilers> <91-09-021@comp.compilers> Date: 16 Sep 91 12:54:16 GMT Approved: compilers@iecc.cambridge.ma.us In article <91-09-021@comp.compilers>, horst@techfak.uni-bielefeld.de (horst Hogenkamp) writes: > BEG (back end generator): > ========================= > This is probably one of the best: > > Helmut Emmelmann: BEG - a Back End Generator - Users Manual > GMD Forschungsstelle an der Universitaet Karlsruhe > Vincenz-Priessnitz-Str. 1 > W7500 Karlsruhe > GERMANY A much easier to find reference is: H. Emmelmann, F.-W Schro"er & R. Landwehr: BEG - A Generator for Efficient Back Ends SIGPLAN '89 PLDI conf., Portland, Or. SIGPLAN Notices 24, 7 (July 1989), pp. 227-237 BEG is a tool good enough for production use but, as many of its competitors, it concentrates on instruction scheduling and is weak on other issues (register allocation, instruction scheduling, peephole optimization, etc.). At INRIA we are working on Pagode, with the explicit aim of producing subprograms performing all of the above tasks from a single, easy-to-write machine description. However we're still far from our goal... For more information, get in touch with Monique Mazaud (Monique.Mazaud@inria.fr). Martin Jourdan INRIA, Rocquencourt, France. -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Tue Sep 17 01:01:12 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: mcj@zycor.lgc.com Subject: C compiler error list wanted Message-ID: <91-09-039@comp.compilers> Keywords: C, errors Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: mcj@zycor.lgc.com Organization: Compilers Central Date: Mon, 16 Sep 91 11:56:01 CDT Approved: compilers@iecc.cambridge.ma.us Howdy; Do any of you out in netland have a complete listing of error/warning messages issued by some real world C compiler? The company I work for supports a half dozen different workstations and none of their compiler reference manuals include this type of listing. I'd appreciate any help. Mike -- Michael C. Jones Landmark/Zycor mcj@zycor.lgc.com 220 Foremost Dr. Austin, Texas 78745 (512) 282-6699 [Microsoft C for MS-DOS at least used to have a complete error listing in the manual. -John] -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Tue Sep 17 01:01:46 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: napi@rangkom.MY (Mohd Hanafiah Abdullah) Subject: Strength Reduction Message-ID: <91-09-040@comp.compilers> Keywords: optimize, question Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: napi@rangkom.MY (Mohd Hanafiah Abdullah) Organization: MIMOS, Malaysia Date: 17 Sep 91 00:39:16 GMT Approved: compilers@iecc.cambridge.ma.us Hi In Induction Variable optimization, beside reducing strength of multiplication by using addition in array references, what other strength reductions could be performed, like involving division, etc? Please respond by email. Thanks. Napi -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Tue Sep 17 01:02:22 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: Jose Fortes Subject: improving weak precedence Message-ID: <91-09-041@comp.compilers> Keywords: parse, question Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: Jose Fortes Organization: Compilers Central Date: Mon, 16 Sep 91 15:21:37 GMT Approved: compilers@iecc.cambridge.ma.us The weak precedence parsing technique for context-free grammars is usually defined with the following restrictions: 1) empty rules are forbidden, and 2) somehow strong conditions are put on the similarity of right-hand parts of grammar rules. I am particularly interested in knowing about techniques that improve weak precedence's parsing power by relaxing these two restrictions. References are most welcome. Jose Fortes Laboratoire I3S Sophia Antipolis France e-mail: fortes@mimosa.unice.fr -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Wed Sep 18 23:59:45 EDT 1991 Xref: iecc comp.parallel:2181 comp.compilers:1873 Newsgroups: comp.parallel,comp.compilers Path: iecc!anaconda.cis.ohio-state.edu!gadkari From: gadkari@cis.ohio-state.edu (Sanjay Gadkari) Subject: non-imperative parallel languages Message-ID: <91-09-042@comp.compilers> Keywords: design, parallel, dataflow Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: gadkari@cis.ohio-state.edu (Sanjay Gadkari) Organization: The Ohio State University, Department of Computer and Information Science Date: Mon, 9 Sep 1991 18:06:46 GMT Approved: compilers@iecc.cambridge.ma.us I am interested in parallel (distributed) programming languages that that have moved away from the strong process + shared variable/channel/message/RPC structure, such as that exhibited by CSP, distributed OOLs, RPC based languages, parallel versions of FORTRAN etc. I have studied extensions to functional and declarative languages, Id (dataflow languages) and UNITY. Are there other language classes or designs that seem appropriate, that I have missed? Please mail responses, and I will post a summary. thanks, -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Thu Sep 19 00:01:40 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: sif@lachesis.bellcore.com (Stuart I Feldman) Subject: Call for Papers for SIGPLAN'92 (PLDI) Message-ID: <91-09-043@comp.compilers> Keywords: CFP, design Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: sif@lachesis.bellcore.com (Stuart I Feldman) Organization: Morristown Research and Engineering Date: Tue Sep 17 00:59:47 1991 Approved: compilers@iecc.cambridge.ma.us ACM SIGPLAN'92 Conference on Programming Language Design and Implementation San Francisco, California, USA June 17-19, 1992 SIGPLAN'92 continues the series of broad-based language and compiler design conferences. The conference will provide a forum for researchers and developers to learn about current practical and experimental work across the breadth of the field. The conference will emphasize experimental results and experience with the languages and techniques described. The conference seeks original papers relevant to practical issues concerning the design, development, implementation, and use of programming languages (in contrast to the annual SIGACT/SIGPLAN POPL Conference, which is oriented more toward foundations). The conference favors no particular programming paradigm or support architecture. Conference topics include: * compiler construction * interpretation * preprocessing * design and use of languages * special-purpose languages * programming environments * incremental and interactive methods * translation by program transformation * benchmarks and assessment * translator validation * implementation for non-traditional languages and/or architectures * internal representations * optimization for scalar and parallel architectures Authors should submit thirteen copies (preferably double-sided) of a technical summary of a prospective paper to the program chair; persons without access to a photocopier may submit a single copy. The first sheet of the summary (not the cover letter) must include the phone number and street and (if available) Internet addresses for the corresponding author. Summaries must not exceed 5000 words (approximately 10 pages typeset 10-point on 16-point spacing, or 15 pages if typewritten double-spaced). Excessively long summaries will be rejected immediately by the program chair. Papers awaiting acceptance by any other conference are ineligible for SIGPLAN'92; if a similar paper has been submitted else- where, the authors must notify the program chair. The summary must be organized so that it is easily understood. Clearly identify what has been accomplished, why it is significant, and how it compares with prior work. Papers will be judged on clarity, significance, relevance, correct- ness, and originality. Authors should make their papers understandable to a broad audience. The last paper in the June 1991 issue of SIGPLAN Notices offers advice to sub- mitters. Submissions must be received by November 20, 1991. Authors will be notified of acceptance or rejection by January 27, 1992. Full versions of the accepted papers must be format- ted according to ACM conventions, and camera-ready copy must be received by the program chair by April 3, 1992. Authors of accepted papers must sign an ACM copyright release form. Proceedings will be distributed at the conference and as a special issue of SIGPLAN Notices. All papers published in the proceedings are eligible for publication in refereed ACM journals at the discretion of the editor. Program Committee Randy Allen (Sun Microsystems Labs) Robert A. Ballance (University of New Mexico) Hans-J. Boehm (Xerox PARC) Saumya K. Debray (University of Arizona) Christopher W. Fraser (AT&T Bell Laboratories) Brent T. Hailpern (IBM) Samuel N. Kamin (University of Illinois) Michael Rodeh (IBM Israel Scientific Center) William M. Waite (University of Colorado) David W. Wall (DEC Western Research Laboratory) Jeannette Wing (Carnegie-Mellon University) William A. Wulf (University of Virginia) Tutorials will precede the conference on June 15-16. The conference advance program will announce the tutorial topics. Conference Chair Stuart I. Feldman Bellcore 445 South Street Morristown, NJ 07960-1910 (201)829-4305 sif@bellcore.com Program Chair: Christopher W. Fraser AT&T Bell Laboratories Room 2C-464 600 Mountain Avenue Murray Hill, NJ 07974-0636 (908)582-3583 cwf@research.att.com Local Arrangements Chair: Stan Osborne Computer Science Department San Francisco State University 1600 Holloway Avenue San Francisco, CA 94132 (415) 338-2168 stan@cs.sfsu.edu Publicity Chair Guda Venkatesh Bellcore 445 South Street Morristown, NJ 07960-1910 (201)829-5202 venky@bellcore.com -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Thu Sep 19 00:02:32 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: robichau@freedom.msfc.nasa.gov (Paul Robichaux) Subject: Re: code generator generators? Message-ID: <91-09-044@comp.compilers> Keywords: code, bibliography, design Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: robichau@freedom.msfc.nasa.gov (Paul Robichaux) Organization: NASA/MSFC References: <91-09-012@comp.compilers> <91-09-014@comp.compilers> <91-09-021@comp.compilers> <91-09-038@comp.compilers> Date: Tue, 17 Sep 1991 13:07:05 GMT Approved: compilers@iecc.cambridge.ma.us Another reference (which to my dismay got lost during moving) is Ralph Duncan, et al, and their series of papers on CGG (code generator generator.) Ralph is at CDC's Government Systems group; if you'd like to contact him, email to me and I'll forward his address. -Paul -- Paul Robichaux -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Thu Sep 19 00:03:38 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: ssimmons@convex.com (Steve Simmons) Subject: Re:strength reduction Message-ID: <91-09-045@comp.compilers> Keywords: optimize, question Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: ssimmons@convex.com (Steve Simmons) Organization: CONVEX Computer Corporation, Richardson, Tx., USA References: <91-09-040@comp.compilers> Date: Tue, 17 Sep 1991 14:49:47 GMT Approved: compilers@iecc.cambridge.ma.us Loop induction variable optimization has its biggest win by transforming an index into the array to a direct pointer to the element. Thus, the calculation of each element's address into the array is removed from the body of the loop. For example, the following pseudo code is less efficent than the later... for i=1,n *(&A + (4*i)) = 0 end Converted to loop induction variable for ptr = loc(A), loc(a)+(4*(n-1)), 4 *ptr = 0 end Notice, the address calculation has been completely optimized away. Thank you. Steve Simmons -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Thu Sep 19 00:04:55 EDT 1991 Xref: iecc comp.compilers:1877 comp.sys.m68k:1357 Newsgroups: comp.compilers,comp.sys.m68k Path: iecc!compilers-sender From: aziz@bizet.cs.colostate.edu (Khalid Aziz) Subject: Math routines for 68K Message-ID: <91-09-046@comp.compilers> Keywords: arithmetic, question, 68000 Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: aziz@bizet.cs.colostate.edu (Khalid Aziz) Organization: Colorado State Computer Science Department Distribution: usa Date: 17 Sep 91 16:22:21 GMT Approved: compilers@iecc.cambridge.ma.us Hello everyone: I need programs or algorithms to do a long division, i.e. divide a 32 bit by another 32-bit integer, and modulus operation on long integers on 68000. Both the 32-bit integers can be signed or unsigned. Since 68000 already has instructions that would divide a 32-bit integer by a 16-bit integer, signed or unsigned, I would prefer a program that takes advantage of this instruction. If you have such programs or algorithms, can you please email them to me? Thanks, Khalid ----------------------------------------------------------------------------- aziz@cs.colostate.edu Colorado State University Fort Collins, CO [The algorithms are all in Knuth, Volume 2. -John] -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Thu Sep 19 00:11:05 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: preston@dawn.rice.edu (Preston Briggs) Subject: Re: Strength Reduction Message-ID: <91-09-047@comp.compilers> Keywords: optimize, bibliography Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: preston@dawn.rice.edu (Preston Briggs) Organization: Rice University, Houston References: <91-09-040@comp.compilers> Date: Tue, 17 Sep 1991 18:11:53 GMT Approved: compilers@iecc.cambridge.ma.us napi@rangkom.MY (Mohd Hanafiah Abdullah) writes: >In Induction Variable optimization, beside reducing strength of >multiplication by using addition in array references, what other strength >reductions could be performed, like involving division, etc? Multiplication of an induction variable (IV) by a region constant (RC). Multiplication of 2 IVs. Squaring an IV. Integer division (IV / RC) Integer module (IV % RC) Exponentiation (RC ** IV) General polynomials in an IV may always be reduced to additions. Many trig functions. Further, addition may sometimes be usefully reduced. See Reduction of Operator Strength Fran Allen, John Cocke, Ken Kennedy in Program Flow Analysis Muchnick and Jones (editors) Prentice-Hall, 1981 Generally though, you need to handle multiplication. The other things are fun to watch, but not very useful. Preston Briggs -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Thu Sep 19 00:15:23 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: norman@au-bon-pain.lcs.mit.edu (Norm Rubin) Subject: RE: BEG Message-ID: <91-09-048@comp.compilers> Keywords: code, tools Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: norman@au-bon-pain.lcs.mit.edu (Norm Rubin) Organization: Compilers Central References: <91-09-021@comp.compilers> Date: Tue, 17 Sep 91 18:43:53 EDT Approved: compilers@iecc.cambridge.ma.us Does anyone know of an ftp address for the source of BEG "backend generator"? -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Thu Sep 19 00:16:23 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: dkiong@vms.discs.nus.sg (Derek Kiong) Subject: Wanted -- compilers/machine emulators for compiler course Message-ID: <91-09-049@comp.compilers> Keywords: tools, question Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: dkiong@vms.discs.nus.sg (Derek Kiong) Organization: Dept. of Information Systems and Computer Science, National University of Singapore Date: Wed, 18 Sep 1991 09:06:16 GMT Approved: compilers@iecc.cambridge.ma.us I am looking for toy compilers/interpreters ...etc that you have found helpful in teaching a compiler construction course. Please mail me your suggestions, and if there is enough response, I will summarise. Thanks in anticipation. (ps: If mail bounces off vms, please try: isckbk@nusunix1.nus.sg isckbk@nusvm.bitnet ) -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Thu Sep 19 00:17:03 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: Donald Liib Subject: backend in C or in C++ Message-ID: <91-09-050@comp.compilers> Keywords: C, C++, code, question Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: Donald Liib Organization: Compilers Central Date: Wed, 18 Sep 91 19:43:31 +0200 Approved: compilers@iecc.cambridge.ma.us Hi, which is the best publicly available tool to generate compiler back-end (from triples sequence to C or C++) with some optimizing features like explicit register usage etc. My e-mail: donald@parseq.tds.kth.se Thanks! [Probably GCC. -John] -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Sat Sep 21 10:07:32 EDT 1991 Xref: iecc comp.compilers:1882 comp.sys.m68k:1362 Newsgroups: comp.compilers,comp.sys.m68k Path: iecc!compilers-sender From: jwoehr@isis.cs.du.edu (Jack J. Woehr) Subject: Re: Math routines for 68K Message-ID: <91-09-051@comp.compilers> Keywords: arithmetic, 68000, forth Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: jwoehr@isis.cs.du.edu (Jack J. Woehr) Organization: University of Denver, Dept. of Math & Comp. Sci. References: <91-09-046@comp.compilers> Date: Thu, 19 Sep 91 22:46:29 GMT Approved: compilers@iecc.cambridge.ma.us aziz@bizet.cs.colostate.edu (Khalid Aziz) writes: >I need programs or algorithms to do a long division, i.e. divide a 32 bit >by another 32-bit integer, and modulus operation on long integers on 68000. >Both the 32-bit integers can be signed or unsigned. ... Khalid -- All the algorithms you mention are implemented (albeit somewhat inefficiently) in A4TH1.5, the entirely PD Forth system for the Amiga with complete source (in Forth BLOCK files), downloadable from the RealTime Control & Forth Board BBS (303) 278-0364, right here in Colorado. =jax= -- jax@well.{UUCP,sf.ca.us}, du!isis!koscej!jax, JAX on GEnie -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Sat Sep 21 10:28:07 EDT 1991 Xref: iecc comp.compilers:1883 comp.unix.sysv386:12559 Newsgroups: comp.compilers,comp.unix.sysv386 Path: iecc!compilers-sender From: steve@nuchat.sccsi.com (Steve Nuchia) Subject: Adding "shared" to C, need sysv386 .section syntax Message-ID: <91-09-052@comp.compilers> Keywords: C, 386, assembler Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: steve@nuchat.sccsi.com (Steve Nuchia) Organization: South Coast Computing Services, Inc. Houston Date: Thu, 19 Sep 91 14:08:38 GMT Approved: compilers@iecc.cambridge.ma.us This may be over the edge of the comp.compilers charter, but I've tried in comp.unix.sysv386 and I really want to make this work... I am trying to add a "shared" storage class to gcc for an embedded application I am working on. This is a special-purpose thing, but it is important for several reasons (but mainly aesthetics) that the shared-variable support be well integrated into the language. I know that it is easy enough to use some combination of preprocessor hackery and code extraction/generation -> sed -> as tricks to get the job done, but I would really like to be able to have what little help C gives me with type checking and scope control apply to these buggers, and adding the keyword seems to me to be a good way to do it. My plan is this: Add a keyword "shared" to the language to act as a storage class modifier (or is it a storage class? dunno yet) with two main effects. First, it gives the objects being declared persistent semantics -- like "static" inside a function. Secondly it arranges that the allocation of the variable be done in two pieces: it will write the initializer (including zeros for objects not explicitly initialized) to a section that will be linked into the (shared read only) text segment. Then it places the label for the object and a . += size type thing into a dummy segment to be relocated at an "appropriate" address. Main then allocates and attaches a sysV shared memory segment to that address and copies the initializers to it before forking (the threads all run one image, no execing). Why am I using sysV for an embedded system? Some questions are best left unanswered. Don't even think about asking me why we're using X in a hard-realtime job ... Anyway... I'd certainly appreciate any commentary or discussion on the proposal. I'll release the gcc patches if anyone is interested, but I am not proposing this as a "real" extension to C, just a clean way of doing what I need for a specific project. But the real purpose of this plea for help: I cannot find the syntax for the .section directive of the interactive (ie, nearly universal) sysv/386 "as" assembler. I know from error messages that there is such a directive, but the compiler uses only the .text, .data sort of special-case directives. This is incredibly frustrating. @#$%^&*( black-box software. Grrr. -- Steve Nuchia South Coast Computing Services (713) 880-0099 -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Sat Sep 21 10:28:53 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: kai@ifi.uio.no (Kai Ivo Quale) Subject: RE: BEG Message-ID: <91-09-053@comp.compilers> Keywords: code, tools, FTP Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: kai@ifi.uio.no (Kai Ivo Quale) Organization: Dept. of Informatics, University of Oslo, Norway References: <91-09-021@comp.compilers> <91-09-048@comp.compilers> Date: Fri, 20 Sep 1991 17:11:38 GMT Approved: compilers@iecc.cambridge.ma.us In article <91-09-048@comp.compilers>, norman@au-bon-pain.lcs.mit.edu (Norm Rubin) writes: >Does anyone know of an ftp address for the source of BEG "backend generator"? BEG isn't free: You have to pay $250 for a non-commercial license and $2500 for a commercial one. BEG is part of the GMD Toolbox. The rest of the Toolbox is ftp'able from rusmv1.rus.uni-stuttgart.de (129.69.1.12), directory: /soft/unixtools/compilerbau Kai Quale, kai@ifi.uio.no -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Sat Sep 21 10:30:09 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: bobz@truevision.com (Bob Zigon) Subject: Where can I get the GNU C compiler for DOS ? Message-ID: <91-09-054@comp.compilers> Keywords: GCC, question Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: bobz@truevision.com (Bob Zigon) Organization: Truevision Inc., Indianapolis, IN Date: Fri, 20 Sep 91 18:02:39 GMT Approved: compilers@iecc.cambridge.ma.us I'd like to play around with the GNU C Compiler under DOS. Where can I find it? bob zigon [This question comes up all the time. If someone can give me a pointer to the gnuish code for DOS, I'll put it in the FAQ. -John] -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Sun Sep 22 12:56:32 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: tm@well.sf.ca.us (Toshi Morita) Subject: Re: Where can I get the GNU C compiler for DOS ? Message-ID: <91-09-055@comp.compilers> Keywords: GCC, question Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: tm@well.sf.ca.us (Toshi Morita) Organization: Whole Earth 'Lectronic Link, Sausalito, CA References: <91-09-054@comp.compilers> Date: 22 Sep 91 00:32:08 GMT Approved: compilers@iecc.cambridge.ma.us [Forwarded from apple!ctron.COM!dj (DJ Delorie)] Use the archive-server at Clarkson. See info below. DJ -- Patch #4 has been uploaded to: grape.ecs.clarkson.edu 128.153.28.129 FTP pub/msdos/djgpp For convenience to non-FTP users, I have uploaded split versions to: sun.soe.clarkson.edu 128.153.12.3 MAIL pub/msdos/djgpp Sun.soe.clarkson.edu has an archive server that can mail you the files. To get help on the archive server, send mail to archive-server@sun.soe.clarkson.edu, with the word "help" as the message (not subject). The archive name is msdos/djgpp. --- DJGPP - G++ for MSDOS/386 --- Summary: djgpp is a port of the GNU gcc/g++ compiler to the 386/DOS platform. The compiler and programs it generates run in the 386's 32-bit mode, with full virtual memory support. Various libraries and utilities are provided also. System requirements: 80386, 512K memory Supports: 80387, Extended memory (up to 128M), XMS, VGA, SuperVGA, paging to disk (up to 128M). 1027 May 31 14:04 Index 2391625 Jul 22 10:29 djgpp.zip (grape.ecs only) 24954 Jul 22 11:12 readme 677705 Jul 22 11:13 patch4.zip 1254 Jul 22 11:13 patches4.doc 976 May 31 14:03 merge.c 6924 May 31 14:03 merge.exe 1244 May 31 14:03 split.c 7474 May 31 14:03 split.exe 294912 Jul 22 11:15 djgppzip.000 (sun.soe only) 294912 Jul 22 11:15 djgppzip.001 " 294912 Jul 22 11:15 djgppzip.002 " 294912 Jul 22 11:15 djgppzip.003 " 294912 Jul 22 11:15 djgppzip.004 " 294912 Jul 22 11:15 djgppzip.005 " 294912 Jul 22 11:15 djgppzip.006 " 294912 Jul 22 11:15 djgppzip.007 " 32329 Jul 22 11:15 djgppzip.008 " ("merge djgppzip djgpp.zip" builds the big .zip from these) Note that the split files are multiples of 16384 bytes. This is so that file transfer utilities that require multiples of some power of two will work properly with hte merge utility. A copy of patches4.doc is attached Please do not ask me to make this available anywhere other than grape.ecs or sun.soe. If you'd like it available elsewhere, contact that site's administrator and ask them to transfer it. DJ dj@ctron.com ----------------------------- patches4.doc This documents patch level 4 of djgpp New Features Bug Fixes Still to Come New Features: A unix compatible 16-bit compress is included in the samples and bin directories Make.ini for NDMake is included Profiling via gcc -pg is supported in all libraries, and gprof is included Brief documentation on gcc switches and library functions is provided Go32 handles redirecting stdout and stderr to each other or to the mono screen {A paging test program is included in samples/pagetest Bug Fixes: The ATI and Genoa drivers have been upgraded Numerous opcodes unassemble correctly in debug32 Breakpoints list as enabled when they are XMS's a20 handler is used to set and reset gateA20 Help in debug32 works properly fdopen sets the text/binary mode properly memcpy and memset return proper values getkey() and kbhit() work better GrText of characters >=128 works string I/O functions preserve the proper registers Hercules systems are better supported emu387 compares numbers correctly Still to Come: DPMI - I have the 1.0 spec, but nobody supports it, not even Windows, so it will have to wait. VCPI - Someone else has started work on it; I have a spec on the way also. -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Sun Sep 22 18:29:37 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: MM0F@ns.cc.lehigh.edu (Mary Elizabeth Rudis) Subject: Pascal P-Code, Modula M-Code Message-ID: <91-09-056@comp.compilers> Keywords: Pascal, Modula Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: MM0F@ns.cc.lehigh.edu (Mary Elizabeth Rudis) Organization: Compilers Central Date: Sun, 22 Sep 91 17:51:55 EST Approved: compilers@iecc.cambridge.ma.us Howdy all, Does anyone have/know where I can get/want to write for me *:^> the original Pascal P-Code specification, or Modula M-Code specification. I'd preferably like an FTP site, but I'll take anything at this point. Also, can anyone point me to a location where I can get the Pascal system that ran as an OpSys for the IBM PC (I read that the P-Code system was written as an operating system for the IBM when it was first released)? (YAR - Yet Another Request)->Does anyone have the address (e-mail or snail-mail) where I can write to get a version of Modula-3 for the Mac and PC. Sorry for the long request, MM0F@LEHIGH.BITNET [UCSD Pascal is now offered by an outfit called Pecan, who still support it and advertise occasionally. You can FTP a Modula 3 implementation from gatekeeper.dec.com, though I have no idea how portable it is to the Mac or PC. -John] -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Sun Sep 22 23:30:01 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: John R. Levine Subject: Comp.compilers mail server, at last Message-ID: <91-09-057@comp.compilers> Keywords: administrivia Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: John R. Levine Organization: Compilers Central Date: Sun, 22 Sep 91 23:12:49 EDT Approved: compilers@iecc.cambridge.ma.us I have finally set up a mail server to let people without FTP access retrieve back messages from comp.compilers. If you have FTP acccess, please FTP files from primost.cs.wisc.edu which will be much faster. (My machine connects only via uucp, so it can take hours for messages to turn around.) The mail server lives at compilers-server@iecc.cambridge.ma.us. Here is its help file: Welcome to the comp.compilers mail server. You can retrive any message posted to comp.compilers as well as index files to help you find what you need, and a few other compilers-related files. This is the "help" file. To request a file from the server, mail your request to compilers-server@iecc.cambridge.ma.us. It will be received by a rather dumb shell script adapted from the comp.archives KISS server. It understands the following commands: path This lets the requestor override the address that would normally be extracted from the header. help This is equivalent to the command `send help'. index This is equivalent to the command `send index'. send Send a file, see below. quit Nothing past this point is interpreted. This is provided so that the occasional lost soul whose signature contains a line that looks like a command can still use the server without getting a bogus response. The server interpets the subject line of the message. Only one file is permitted per command line, although multiple commands per message are allowed. Each message has an ID number of the form YY-MM-NNN where YY and MM are the year and month and NNN is the message number within the month. For example, send a message containing: send 91-01-003 to get the third message from January 1991. The comp.compilers message index is in a separate file for each year with the names index86, index87, etc. You can get the files via, e.g.: send index90 The message index files contain all of the Subject: lines (with "Re:" edited out) and the message ID and number of lines in lines of each message. The file "index" lists the rest of the available files. At this point, all requests are handled when received. Please be moderate in what you request. If I find that my machine overloaded with server requests (keep in mind that its connection to the world is a single modem) I will have to institute the sort of tedious flow controls that other servers have. If you want large numbers of back messages, please FTP them from primost.cs.wisc.edu if you can or else get them by modem from the Channel 1 BBS as described in the monthly posting, which you can retrieve as the file "monthly". Regards, John Levine, comp.compilers moderator -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Mon Sep 23 18:12:02 EDT 1991 Xref: iecc comp.compilers:1889 comp.parallel:2194 comp.arch:14017 Newsgroups: comp.compilers,comp.parallel,comp.arch Path: iecc!compilers-sender From: mcdowell@exlog.com (Steve McDowell) Subject: MIMD code generation? Message-ID: <91-09-058@comp.compilers> Keywords: parallel, optimize, code Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: mcdowell@exlog.com (Steve McDowell) Organization: Compilers Central Date: Thu, 19 Sep 91 16:32:46 CDT Approved: compilers@iecc.cambridge.ma.us I am looking for references to compiler technologies which generate parallel instruction streams (not simply task separation) for tightly coupled multiprocessors. Any help would be appreciated. Steve McDowell mcdowell@exloghou.exlog.com -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Mon Sep 23 18:14:40 EDT 1991 Xref: iecc comp.compilers:1890 comp.unix.sysv386:12609 Newsgroups: comp.compilers,comp.unix.sysv386 Path: iecc!compilers-sender From: pja@ralph.lafayette.la.us (Pete Alleman) Subject: Re: Adding "shared" to C, need sysv386 .section syntax Message-ID: <91-09-059@comp.compilers> Keywords: C, 386, assembler Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: pja@ralph.lafayette.la.us (Pete Alleman) Organization: Consulting References: <91-09-052@comp.compilers> Date: Mon, 23 Sep 1991 01:42:03 GMT Approved: compilers@iecc.cambridge.ma.us In article <91-09-052@comp.compilers> steve@nuchat.sccsi.com (Steve Nuchia) writes: >I am trying to add a "shared" storage class to gcc for an embedded >application I am working on. >I know that it is easy enough to use some combination of preprocessor >hackery and code extraction/generation -> sed -> as tricks to get the job >done, but I would really like to be able to have what little help C gives >me with type checking and scope control apply to these buggers, and adding >the keyword seems to me to be a good way to do it. It sounds like you're making it a lot more difficult than it should be. I have several real-time applications which run as several tasks executing with shared memory. The way I implement it: Allocate all your shared data structures in one C source file. Put nothing but the shared data allocation in that file. Now perform an incremental link on that file, supplying a link control file which allocates the memory at a hardwired absolute virtual address. Now link that shared memory object file with all tasks which are to share memory. You can reference those structures just like any other structure, they just happen to be in shared memory (after the appropriate system calls). I use this procedure for multiple task on the same processor and for multi-processor systems. It is simple, but effective. Of course it does leave the documentation up to the programmer. >Why am I using sysV for an embedded system? Hey, it works. I've been using various Unix systems for real-time applications since V6 was released to universities. Sometimes I have to make some small changes to the OS to minimize delays, but it has always done the job. It depends on your timing requirements. I had a real-time training simulator which had to execute at a solid, reliable 30Hz to keep up with the visual system. No problem with a reasonable power workstation after a little work on the OIS. I wouldn't recommend Unix for sub-millisecond real-time applications though. -- Pete Alleman pja@ralph.lafayette.la.us [Are any of these hacks appreciably faster than putting all the shared stuff in a big structure, keeping a pointer to the structure that is set from the result of shmat(), and maybe using preprocessor defines to make it look prettier? -John] -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Mon Sep 23 18:15:14 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: d37678b@kaira.hut.fi (Antsa) Subject: Re: Pascal P-Code, Modula M-Code Message-ID: <91-09-060@comp.compilers> Keywords: Pascal, Modula Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: d37678b@kaira.hut.fi (Antsa) Organization: Helsinki University of Technology, Finland References: <91-09-056@comp.compilers> Date: Mon, 23 Sep 1991 11:27:41 GMT Approved: compilers@iecc.cambridge.ma.us >Does anyone have/know where I can get/want to write for me *:^> >the original Pascal P-Code specification, or Modula M-Code >specification. I once downloaded somewhere a P-code pascal compiler that is some sort of a superset of the original P-code specification. The program is called Facilis, it is written in (old) Turbo Pascal and the documentation describes something about the P-code specification. I don't know how accurate it is or how closely it resembles to the original specs but it might be worth taking a look at. The compiler is written in Pascal but it can't compile itself, however... Antti -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Mon Sep 23 18:15:52 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: moss@cs.umass.edu Subject: Modula-3 for Mac and PC (was Pascal P-Code, Modula M-Code) Message-ID: <91-09-061@comp.compilers> Keywords: modula Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: moss@cs.umass.edu Organization: Dept of Comp and Info Sci, Univ of Mass (Amherst) References: <91-09-056@comp.compilers> Date: 23 Sep 91 13:00:10 GMT Approved: compilers@iecc.cambridge.ma.us To my knowledge there are no Modula-3 compilers for the Mac or PC. The existing compilers are "bigger than a breadbox" and mostly Unix oriented. My research group is developing a compiler based on gcc (i.e., a new front end and some modifications to the back end). Since gcc now generates code for MSDOS machines, there is some hope of seeing Modula-3 on PCs via this route eventually, but don't hold your breath -- my project is being done on a shoe string so release is not yet imminent (though we are making good progress). -- J. Eliot B. Moss, Assistant Professor Department of Computer Science Lederle Graduate Research Center University of Massachusetts Amherst, MA 01003 (413) 545-4206, 545-1249 (fax); Moss@cs.umass.edu -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Mon Sep 23 18:17:38 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: emmel@karlsruhe.gmd.de Subject: BEG - Back End Generator Message-ID: <91-09-062@comp.compilers> Keywords: code, available, bibliography Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: emmel@karlsruhe.gmd.de Organization: Compilers Central References: <91-09-048@comp.compilers> Date: Mon, 23 Sep 91 16:48:16 N Approved: compilers@iecc.cambridge.ma.us BEG - Back End Generator ================================ The BEG system builds code generators from declarative descriptions. It therefore decreases effort necessary to build code generators and increases reliability and portability of the resulting compiler. The declarative description is rule based. Code selection is done by a kind of tree pattern matching. BEG can also produce local register allocators suitable for a great variety of target machines. BEG uses an efficient implementation technique for the generated code selector. It produces hard code, so no table interpretation is necessary at compilation time. BEG has been used to produce a code generator which can replace the hand written one of the fast GMD Modula-2 compiler Mocka. The resulting compiler could translate itself. It was about 10 percent slower than the original one. Codegenerators for MIPS and SPARC have also been generated. BEG produces Modula-2 or ANSI-C code. BEG is available in object code for Sun-3, Sun-4 and DecStations, as well as in Modula-2 and C source code. It comes with a 45 pages manual. BEG is available on tape. If the user does not intend to use the system for direct commercial advantage and does not want to sell products con- taining code produced by BEG the tape can be obtained from GMD for a handling fee of DM 500. You are required to sign a lincense agreement. Please contact me to obtain a copy of the order form/license agreement. In neither case does GMD assume any responsibility for the use and reliability of the system. GMD has no obligation to maintain the system nor to provide customer support and service. Please contact: Helmut Emmelmann GMD Forschungsstelle an der Univertitaet Karlsruhe Vincenz-Priessnitz-Str. 1 W-7500 Karlsruhe 1 Germany email: emmel@karlsruhe.gmd.dbp.de Tel: 49-721-6622-15 Fax: 49-721-6622-968 References: - H.Emmelmann, F-W.Schroeer, R.Landwehr: BEG - a Generator for Efficient Back Ends, Proceedings of the Sigplan'89 Conference on Programming Language Design and Implementation Portland, Oregon, 1989, Sigplan Notices, Vol. 24, Number 7, July 1989 - BEG User Manual (available from GMD, comes with BEG in Postscript) - H.Emmelmann: Automatische Erzeugung effizienter Codegeneratoren Diplomarbeit, GMD Studie 158, Gesellschaft fuer Mathematik und Datenverarbeitung mbH - Sankt Augustin, ISBN 3-88457-158-3 (in German) -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Mon Sep 23 18:23:36 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: Yoshiyuki KONDO Subject: Cm -- A toy compiler. Message-ID: <91-09-063@comp.compilers> Keywords: C, available, experiment Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: Yoshiyuki KONDO Organization: Compilers Central Date: Mon, 23 Sep 91 23:16:17 JST Approved: compilers@iecc.cambridge.ma.us Last year I published a book on compiler writing (in Japanese and available only in Japan. Anyway this posting is not an ad for my book:-). I have written a simple one-pass toy compiler that compiles a subset of C to be used as the material in my book. The language processed by the compiler is called Cm (C minor). Cm is a `toy' language because it lacks some very important features without which it is impossible (or very difficult, at least) to write practical programs. The difference between C and Cm are as follows: * struct, union, enum are not available. (Can you imagine how *hard* to write standard libraries without them?) * typedef is not available. * initializers are not available. * storage class specifiers are not available. (All variables defined inside functions are "auto" and all variables defined outside function are "extern"). * only "char" and "int" are supported as arithmetic type. * local declaration does not nest. (Local variables can be declared only at the beginning of functions. No declaration in nested compound statement.) These features are eliminated to keep the Cm compiler as small as possible and easy to understand. In other words I do not omit any features essential to study compiler writing. (Struct/union is essential to write programs but I think it is less essential in compiler writing. Anyway I have to keep it small, so something must be eliminated.) Many aspects of compiler internals are covered in Cm. Arbitrary combinations of pointer, array, and function can be used in declarations. Short-cut operators (&&, ||) are expanded into combinations of test and conditional branch (as real compilers do). The target machine is not a stack oriented virtual machine. The target machine of Cm compiler is a `real' one -- 80x86. (It's quite *real*, isn't it? :-) The Cm compiler is written in ANSI C and Yacc, is about 4500 lines long (it's pretty small, I think:-), generates assembler source code for 80x86 to be assembled with MASM and linked with MS-LINK to get executable (.EXE) files. The Cm compiler itself can be compiled by MS-C, Turbo-C, or LSI-C (a product of my employer. Again, available only in Japan.). It operates in an MS-DOS environment and runs on any MS-DOS machines including IBM PCs or clones. I hold the copyright of Cm compiler (eg. it is not in public domain) but it is freely distributable by anyone. I have placed it in some domestic commercial BBSs but is not currently available outside Japan. If there is enough people interested in it, I will post it in an apropriate newsgroup. --- Yoshiyuki KONDO email: cond%lsi-j.co.jp@uunet.uu.net LSI Japan Co. Ltd., Tokyo, Japan cond@lsi-j.co.jp (from Japan) -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Mon Sep 23 18:24:28 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: albaugh@dms.UUCP (Mike Albaugh) Subject: Re: strength reduction Message-ID: <91-09-064@comp.compilers> Keywords: optimize Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: albaugh@dms.UUCP (Mike Albaugh) Organization: Atari Games Inc., Milpitas, CA References: <91-09-045@comp.compilers> Date: 23 Sep 91 14:27:14 GMT Approved: compilers@iecc.cambridge.ma.us >From article <91-09-045@comp.compilers>, by ssimmons@convex.com (Steve Simmons): > Loop induction variable optimization has its biggest win by > transforming an index into the array to a direct pointer to the element. A caveat: a _good_ compiler should only do this if it is a "win". If a machine supports scaled indexing and there is more than one array reference in the loop, it may be a "lose". Borrowing ssimmons's example: for i=1,n *(&A + (4*i)) = 0 *(&B + (4*i)) = 1 end Will (unfortunately) often be turned into: > Converted to loop induction variable ptrB = loc(B) for ptrA = loc(A), loc(a)+(4*(n-1)), 4 *ptrA = 0 *ptrB =1 ptrB = ptrB + 4; end This is more a problem with "strength reduction" than loop induction, in the sense that it trades an "imaginary" (effectively 0 time) multiply for two real adds. It is also a fairly common "optimization" in well-respected compilers :-) I just wanted to provide an example where the "machine independant" optimizations could benefit from a little "machine dependant" info. The layers of a compiler are no where near so cleanly separated as texbooks would have you believe. > Notice, the address calculation has been completely optimized away. A pity, if it was cheaper than two pointer adds :-) Yes, I would prefer that the actual "base of array" be in pointers, but common subexpession elimination should do that. The question I'm trying to address is the blind conversion of indexed addresses to pointers so popular in "new" compilers. I'm sure convex's compilers get this right :-) Mike | Mike Albaugh (albaugh@dms.UUCP || motcsd.mot.com!dms!albaugh) | Atari Games Corp (Arcade Games, no relation to the makers of the ST) | 675 Sycamore Dr. Milpitas, CA 95035 voice: (408)434-1709 -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Tue Sep 24 09:54:00 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: hoelzle@Neon.Stanford.EDU (Urs Hoelzle) Subject: Re: Pascal P-Code, Modula M-Code Message-ID: <91-09-065@comp.compilers> Keywords: Pascal, Modula, bibliography Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: hoelzle@Neon.Stanford.EDU (Urs Hoelzle) Organization: CS Department, Stanford University, California, USA References: <91-09-056@comp.compilers> Date: 23 Sep 91 21:09:17 GMT Approved: compilers@iecc.cambridge.ma.us MM0F@ns.cc.lehigh.edu (Mary Elizabeth Rudis) writes: >Does anyone have/know where I can get/want to write for me *:^> >the original Pascal P-Code specification, or Modula M-Code >specification. I'd preferably like an FTP site, but I'll take anything For P-Code, look in AUTHOR: Ammann, U. Eidgenoessische Technische Hochschule Zuerich (ETH). Institut fuer Informatik. Bericht 13. TITLE: ON CODE GENERATION IN A PASCAL COMPILER. 1976. NUMBER: Bericht 13. (Report Number) and AUTHOR: Eidgenoessische Technische Hochschule Zuerich (ETH). Institut fuer Informatik. Bericht 10. TITLE: THE PASCAL

COMPILER: IMPLEMENTATION NOTES. 1974. OTHER: Nori, K. V. Ammann, U. Jensen, K. Naegeli, H. H. NUMBER: Bericht 10. (Report Number) M-Code is described and defined in these two ETH publications: AUTHOR: Eidgenoessische Technische Hochschule Zuerich (ETH). Institut fuer Informatik. Bericht 40. TITLE: THE PERSONAL COMPUTER LILITH. 1981. OTHER: Wirth, N. and "Code generation and the Lilith architecture", Christian Jacobi, ETH Dissertation 7195, Zurich, 1982. One of these (I believe it is Jacobi's thesis) contains a definition of M-Code, written in Modula-2. -Urs -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Tue Sep 24 10:12:02 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: Gord Vreugdenhil Subject: GCC for DOS (FAQ list info) Message-ID: <91-09-066@comp.compilers> Keywords: GCC, FTP Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: Gord Vreugdenhil Organization: Compilers Central References: <91-09-054@comp.compilers> Date: Mon, 23 Sep 91 17:41:43 -0400 Approved: compilers@iecc.cambridge.ma.us You were asking for a pointer to a GCC implementation for DOS. Note that the following (and only one available as far as I know) is for 80386sx or better machines. The compiler generates true 32-bit code and comes with an extender. Unfortunately, this makes the current code incompatible with windows or most other products that use extended memory. The following was posted to comp.sys.ibm.pc by Keith Petersen: > WSMR-SIMTEL20.ARMY.MIL [192.88.110.20] or mirror site wuarchive.wustl.edu > > NOTE: Type B is Binary; Type A is ASCII > > Directory PD1: > Filename Type Length Date Description > ============================================== >DJGPP1.ZIP B 597579 910704 GCC/G++ C compiler for 386 (patchlevel 3) 1of4 >DJGPP2.ZIP B 478064 910704 GCC/G++ C compiler for 386 (patchlevel 3) 2of4 >DJGPP3.ZIP B 539015 910704 GCC/G++ C compiler for 386 (patchlevel 3) 3of4 >DJGPP4.ZIP B 410539 910704 GCC/G++ C compiler for 386 (patchlevel 3) 4of4 >GPPPAT1.ZIP B 87878 910704 Replacements for certain files in DJGPP pkg. >GPPPAT2.DOC A 2144 910704 Changes made to DJGPP patchlevel 2 >GPPPAT2.ZIP B 336422 910704 Replacements for certain files in DJGPP pkg. >GPPPAT3.DOC A 1066 910704 Changes made to DJGPP patchlevel 3 >GPPPAT3.ZIP B 303094 910704 Replacements for certain files in DJGPP pkg. >GPPREAD.ME A 24830 910704 Read this before unpacking DJGPP*.ZIP files >MERGE.C A 976 910704 Binary file merger source (for DJGPP) >MERGE.EXE B 6924 910704 Binary file merger executable (for DJGPP) >SPLIT.C A 1244 910704 Binary file splitter source (for DJGPP) >SPLIT.EXE B 7474 910704 Binary file splitter executable (for DJGPP) Gord Vreugdenhil gvreugdenhil@msg.uwaterloo.ca -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Tue Sep 24 14:46:42 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: "P.G.Hamer" Subject: Rparse extraction Message-ID: <91-09-067@comp.compilers> Keywords: parse, question Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: "P.G.Hamer" Organization: BNR Europe Limited, London Road, Harlow, Essex, UK Date: 24 Sep 91 12:26:40 GMT Approved: compilers@iecc.cambridge.ma.us I have read with interest about tools such as TLex and NewYacc, which provide pattern matching with parse extraction. Are any such tools readily available? Does anybody have useful experience to report? Regards, Peter -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Wed Sep 25 12:10:29 EDT 1991 Xref: iecc comp.compilers:1899 comp.unix.sysv386:12627 Newsgroups: comp.compilers,comp.unix.sysv386 Path: iecc!compilers-sender From: steve@nuchat.sccsi.com (Steve Nuchia) Subject: Re: Adding "shared" to C, need sysv386 .section syntax Message-ID: <91-09-068@comp.compilers> Keywords: C, 386, assembler Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: steve@nuchat.sccsi.com (Steve Nuchia) Organization: South Coast Computing Services, Inc. Houston References: <91-09-052@comp.compilers> <91-09-059@comp.compilers> Date: Tue, 24 Sep 91 18:26:33 GMT Approved: compilers@iecc.cambridge.ma.us In article <91-09-059@comp.compilers> pja@ralph.lafayette.la.us (Pete Alleman) writes: >The way I implement it: Allocate all your shared data structures in one C .. >Now perform an incremental link on that file, supplying a link control >file which allocates the memory at a hardwired absolute virtual address. Hmmm... yes, I see! The incremental link step fixes the addresses, then the "real" link step resolves to them, even with different images. I want a single image so that I can pass function pointers, pointers to constants, things like that around, but the idea should work. Thanks, that is simpler, at least on the back end. It does not allow me to control the scope of the objects created nor to allocate objects with private data types though. >multi-processor systems. It is simple, but effective. Of course it does >leave the documentation up to the programmer. This whole thing would be a lot easier if I had either documentation or source. Having to make do with the *ahem* manuals AT+T and Interactive put out is costing my client a lot of money. I know I should refrain from flamage on a moderated technical list, but good grief! Now that I have the syntax for the .section (thanks all) I am having a lot of grief getting the linker and the loader (ie, the exec system call) to agree on what the a.out file should look like. Of course the documentation tells me everything I could ever want to know about the *syntax* of COFF files, but nothing whatsoever about the semantics. I think I can solve this one by the trial and error method. We'll see. >>Why am I using sysV for an embedded system? >little work on the OIS. I wouldn't recommend Unix for sub-millisecond >real-time applications though. I haven't yet measured the sampling jitter, but our maximum sampling rate is 100/sec and outputs are slower than that. So jitter it the only thing I'm really worried about. That and the fact that we have neither source not adequate support for major chunks of the system. Sigh. >[Are any of these hacks appreciably faster than putting all the shared >stuff in a big structure, keeping a pointer to the structure that is set >from the result of shmat(), and maybe using preprocessor defines to make >it look prettier? -John] This isn't about performance, it is about things like type checking and information hiding. As I indicated in the first note, there are plenty of ways to skin this cat. I suppose when you get right down to it this is a science project, but the code I inherited on this project was suffering so badly from preprocessor abuse, type puns run amok, and general obfuscation that the effort seems justified. -- Steve Nuchia South Coast Computing Services (713) 880-0099 -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Wed Sep 25 12:11:52 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: AKayser@dnpap.et.tudelft.nl (Alfred Kayser) Subject: Re: GCC for DOS (FAQ list info) Message-ID: <91-09-069@comp.compilers> Keywords: GCC, FTP, MSDOS Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: AKayser@dnpap.et.tudelft.nl (Alfred Kayser) Organization: Delft University of Technology, Dept. of Electrical Engineering References: <91-09-054@comp.compilers> <91-09-066@comp.compilers> Date: Wed, 25 Sep 1991 10:11:25 GMT Approved: compilers@iecc.cambridge.ma.us gvreugdenhil@watmsg.uwaterloo.ca (Gord Vreugdenhil) writes: >You were asking for a pointer to a GCC implementation for DOS. Note that >the following (and only one available as far as I know) is for 80386sx or >better machines. The compiler generates true 32-bit code and comes with >an extender. Unfortunately, this makes the current code incompatible with >windows or most other products that use extended memory. BUT: It works with virtual memory (even vga memory can be paged) and memory will be paged to disk if space is needed. I tested this with a Scheme interpreter which allocated about 5 Megabyte of memory, while having only 4 Meg ram. It worked and reasonably fast. I'm sure this won't work this good under Windows or other extended memory managers!!! I only need one thing for now and that is a protected mode driver for the 'packet drivers'. Then I can develop a distributed object oriented system for 386 (and most other UNIX boxes) systems. When TCP/IP is ported it can be a good platform to port a X server to it. Enough hype, try it! -- -- Ir. Alfred Kayser. PACS, OS/2, TCP/IP. --- Email: AKayser@et.tudelft.nl -- -- CARDIT, Delft University of Technology ------------ Tel: (31)-15-786179 -- -- P.O.Box 5031, 2600 GA Delft, The Netherlands ------ Fax: (31)-15-784898 -- -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Wed Sep 25 12:12:52 EDT 1991 Xref: iecc comp.compilers:1901 comp.unix.sysv386:12628 Newsgroups: comp.compilers,comp.unix.sysv386 Path: iecc!compilers-sender From: pja@ralph.lafayette.la.us (Pete Alleman) Subject: Re: Adding "shared" to C, need sysv386 .section syntax Message-ID: <91-09-070@comp.compilers> Keywords: C, 386, assembler Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: pja@ralph.lafayette.la.us (Pete Alleman) Organization: Home Sweet Home, Lafayette, LA References: <91-09-052@comp.compilers> <91-09-059@comp.compilers> Date: Wed, 25 Sep 1991 00:55:06 GMT Approved: compilers@iecc.cambridge.ma.us >[Are any of these hacks appreciably faster than putting all the shared >stuff in a big structure, keeping a pointer to the structure that is set >from the result of shmat(), and maybe using preprocessor defines to make >it look prettier? -John] The speed difference is small enough that it is not much of a factor. Some advantages of using the linker to resolve the addresses: * One of my applications involves 18 processors, each with some memory, communicating and sharing data across all the memories. The shared data must be split across the 18 data spaces. It is not easy to have to worry about those addresses at source level. (This is probably a rather unusual example of Unix shared memory.) * Resolving addresses is the linker's job. * Data hiding. If I have a routine which needs some small data structure from the shared data segment, I would hate to have to include the definitions of all the data structures in shared data just to get my little structure. Also, with your suggestion, every subroutine which references shared data must be recompiled if anything is changed in the shared data structure. This can be a configuration control problem. The main disadvantage of using the linker: * Link control files tend to be rather non-portable. * The syntax of the link control file tends to be rather poorly documented. When writing small applications I used your approach. When the application grew and problems arose I solved them with the linker. As always, use the simplest approach which solves the problem satisfactorily. -- Pete Alleman pja@ralph.lafayette.la.us -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Wed Sep 25 12:13:41 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: preston@dawn.rice.edu (Preston Briggs) Subject: Re: strength reduction Message-ID: <91-09-071@comp.compilers> Keywords: optimize Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: preston@dawn.rice.edu (Preston Briggs) Organization: Rice University, Houston References: <91-09-045@comp.compilers> <91-09-064@comp.compilers> Date: Wed, 25 Sep 1991 14:19:18 GMT Approved: compilers@iecc.cambridge.ma.us In article <91-09-064@comp.compilers> albaugh@dms.UUCP (Mike Albaugh) writes: > A caveat: a _good_ compiler should only do this if it is a "win". >If a machine supports scaled indexing and there is more than one array >reference in the loop, it may be a "lose". Borrowing ssimmons's example: > > for i=1,n > *(&A + (4*i)) = 0 > *(&B + (4*i)) = 1 > end > > Will (unfortunately) often be turned into: > > ptrB = loc(B) > for ptrA = loc(A), loc(a)+(4*(n-1)), 4 > *ptrA = 0 > *ptrB =1 > ptrB = ptrB + 4; > end This isn't quit the best possible. Instead, share one index for both array accesses. for t = 4, n*4, 4 *(&A + t) = 0 *(&B + t) = 0 end This keeps us down to 1 addition (and no multiplies) per iteration. (We're assuming Reg+Offset or Reg+Reg addressing modes, as provided by many (but not all) modern architectures). Generally, all array accesses with the same stride can share the same index. Albaugh is correct in that the strength-reducer must be "aware" or the available addressing modes. And of course, scaling may be used to multiply. For a nice discussion, see The Compilation of Loop Induction Expressions Richard L. Sites TOPLAS Volume 1(1), July 1979 Preston Briggs -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Wed Sep 25 18:05:22 EDT 1991 Xref: iecc comp.compilers:1903 comp.lang.c:21789 comp.os.msdos.programmer:7532 Newsgroups: comp.compilers,comp.lang.c,comp.os.msdos.programmer Path: iecc!compilers-sender From: markus@cernvax.cern.ch (markus baertschi) Subject: Small C compiler wanted Message-ID: <91-09-072@comp.compilers> Keywords: C, MSDOS, question Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: markus@cernvax.cern.ch (markus baertschi) Organization: CERN, Geneva, Switzerland Date: 25 Sep 91 16:27:26 GMT Approved: compilers@iecc.cambridge.ma.us I'm looking for a small, but complete C compiler for MS-DOS. I'd like to run it on my HP95 palmtop. Therefore it has to be real small (50k) for a complete functional environment. I'm ready to sacrify function for size (no float, no complete library). I know about the small-c compiler. It is small, but produces assembler output what makes it impossible to use in a standalone enviroment. I was able to get my good old turbo pascal 3.0 compiler working and am actually looking for something similar but 'C'. Thanks for any hints... Markus -- Markus Baertschi | markus@cernvm.cern.ch CERN (European Particle Research Center) Geneva, Switzerland -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Wed Sep 25 18:06:44 EDT 1991 Xref: iecc comp.compilers:1904 comp.parallel:2197 comp.arch:14024 Newsgroups: comp.compilers,comp.parallel,comp.arch Path: iecc!compilers-sender From: jet@uh.edu (J Eric Townsend) Subject: Re: MIMD code generation? Message-ID: <91-09-073@comp.compilers> Keywords: parallel, optimize, code, FTP Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: jet@uh.edu (J Eric Townsend) Organization: University of Houston -- Department of Mathematics References: <91-09-058@comp.compilers> Date: Wed, 25 Sep 1991 19:54:50 GMT Approved: compilers@iecc.cambridge.ma.us In article <91-09-058@comp.compilers> mcdowell@exlog.com (Steve McDowell) writes: >I am looking for references to compiler technologies which generate parallel >instruction streams (not simply task separation) for tightly coupled >multiprocessors. You might want to look at pc (parallel C) and pf (parallel Fortran), two languages being developed here at UH. You can anonymously ftp pc from karazm.math.uh.edu:pub/Parallel/Tools/pc.1.1.1.tar.Z contact scott@uh.edu for information regarding pf. -- J. Eric Townsend - jet@uh.edu - UH Dept of Mathematics vox: (713) 749-2126 '91 CB750, DoD# 0378, TMRA# 27834 -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Wed Sep 25 21:01:49 EDT 1991 Xref: iecc comp.compilers:1905 comp.sys.m68k:1367 Newsgroups: comp.compilers,comp.sys.m68k Path: iecc!compilers-sender From: eric@zen.maths.uts.edu.au (Eric Lindsay) Subject: Re: Math routines for 68K Message-ID: <91-09-074@comp.compilers> Keywords: arithmetic, 68000, forth Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: eric@zen.maths.uts.edu.au (Eric Lindsay) Organization: Compilers Central References: <91-09-046@comp.compilers> <91-09-051@comp.compilers> Date: 26 Sep 91 14:57:45 GMT Approved: compilers@iecc.cambridge.ma.us aziz@bizet.cs.colostate.edu (Khalid Aziz) writes: >I need programs or algorithms to do a long division, i.e. divide a 32 bit >by another 32-bit integer, and modulus operation on long integers on 68000. >Both the 32-bit integers can be signed or unsigned. ... There is a single page version in 68000 assembler reprinted in King and Knight's book on the 68000. Sorry, don't have a copy handy to give the exact reference. Looked clean, and covered all size variations. I've got a copy on disk somewhere (?) as I remember using it. -- eric@zen.maths.uts.edu.au Eric Lindsay, Sch of Maths, Uni of Tech -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Thu Sep 26 16:33:27 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: dkiong@vms.discs.nus.sg (Derek Kiong) Subject: SUMMARY: Wanted -- compilers/machine emulators for compiler course Message-ID: <91-09-075@comp.compilers> Keywords: courses, summary, Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: dkiong@vms.discs.nus.sg (Derek Kiong) Organization: Dept. of Information Systems and Computer Science, National University of Singapore Date: Thu, 26 Sep 1991 04:20:22 GMT Approved: compilers@iecc.cambridge.ma.us Here is a summary of replies I received in response to my previous posting for usable material in a compiler course. Many thanks to those who responded. (I didn't think you wanted your names here.) 1) "Programming Language translation" (ISBN 0-201-18040-5) (1987) by Patrick Terry (Addison Wesley) 2) "Brinch Hansen on Pascal Compilers" by Per Brinch Hansen (Prentice-Hall, 1985) 3) Wirth has PL/0 in "Algorithms + Data structures = Programs" (Prentice Hall, 1976). He redid it in Modula-2 in a book called "Compilerbau" which is in german and dutch translations at least, not sure if it is English yet. 4) Bennett has one in C in "Introduction to compiling techniques" (McGrawHill, 1990, ISBN 0-07-707215-4). Contact jpb@maths.bath.ac.uk 5) "Crafting a Compiler" by Fisher and Leblanc. 6) We used a subset of Pascal (MiniLax, also a subset of LAX; Wait, Goos Compiler Construction Springer). 7) Samuel Kamin's book "Programming languages, An Interpreter-Based Approach", Addison-Wesley 1990. He gives interpreters for Lisp, APL, Scheme, Sasl, Clu, Smalltalk and Prolog, all written in Pascal. You can get then with anonymous ftp from uihub.cs.uiuc.edu, uiuc/kamin.distr, file distr.tar.Z 8) Tim Budd announced his C++-versions of the same interpreters ... The following posting a week ago (in comp.compilers) sounds interesting: Cm (for C minor) from Yoshiyuki KONDO I have asked the sender if we (in NUS) could use it but so far, I have not received a reply. -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Thu Sep 26 16:34:20 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: Thomas Johnsson Subject: Looking for conflict graph generators Message-ID: <91-09-076@comp.compilers> Keywords: optimize, theory Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: Thomas Johnsson Organization: Compilers Central Date: Thu, 26 Sep 91 09:29:07 +0200 Approved: compilers@iecc.cambridge.ma.us I'm looking for an algorithm, or better yet, a program, which generates conflict graphs `similar' to those obtained from a graph coloring register allocator. Anybody out there have one? The reason is that I would like to test a graph coloring register allocator without actually going to the trouble of analysing real code. Thanks in advance, -- Thomas Johnsson johnsson@cs.chalmers.se Chalmers University of Technology, G{\"o}teborg, Sweden -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Thu Sep 26 16:46:50 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: Greg Michaelson Subject: time spent in compiler phases Message-ID: <91-09-077@comp.compilers> Keywords: performance Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: Greg Michaelson Organization: Compilers Central Date: Thu, 26 Sep 91 10:41:00 BST Approved: compilers@iecc.cambridge.ma.us Does any one have figures for the proportion of total compile time spent in lexical analysis, syntax analysis, semantic analysis, code generation and optimisation? [It varies a lot by compiler. For Ken Thompson's Plan 9 C compiler, he said that the Yacc parser took as much time as everything else put together, 25% for low-level character bashing and 75% for Yacc slowness. This is quite unusual, and his is an extremely fast compiler. -John] -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Thu Sep 26 16:49:18 EDT 1991 Xref: iecc comp.compilers:1909 comp.unix.cray:213 Newsgroups: comp.compilers,comp.unix.cray Path: iecc!compilers-sender From: ghost@cs.clemson.edu (Richard Baldwin) Subject: Help: Cray compilers Message-ID: <91-09-078@comp.compilers> Keywords: question, Cray, history Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: ghost@cs.clemson.edu (Richard Baldwin) Organization: Compilers Central Date: Thu, 26 Sep 91 9:36:03 EDT Approved: compilers@iecc.cambridge.ma.us I want to do a paper on the evolution of the compiler technology of the Cray and Japanese machines (Cray architectures). I want to look at how the compilers have changed as the machines have evolved. What innovations have been included, what techniques are used to optimize the code, does the compiler do any parallelization on its own: these are the type questions I want to answer. Did the compiler motivate the hardware change or did the hardware motivate the compiler change?... Can anyone suggest some appropriate journals, texts, tech reports that might I may be overlooking? Is there anyone in the North Carolina, South Carolina, Georgia, or Chicago area that might be willing to let me read through your Cray manuals (Fujitsu and Hitachi, too)? Your experiences and/or contacts would be appreciated. Where I am looking already: Two Cray X-MP manuals, the ASPLOS proceedings, SIGPLAN, the various proceedings I used as references in my paper last spring (same machines). I think getting stuff on the Japanese computers will be my biggest hurdle. Do Cray, Fujitsu, and Hitachi have publications like the IBM Research Journal? If so, can someone give me a name/addr/... of a good person to contact? Thanks for whatever you can throw my way, Richard Baldwin ghost@cs.clemson.edu Dept of Computer Science Clemson University -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Thu Sep 26 16:52:51 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: AA409CS@opie.bgsu.edu Subject: Re: Small C compiler wanted Message-ID: <91-09-079@comp.compilers> Keywords: C, available Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: AA409CS@opie.bgsu.edu Organization: Compilers Central References: <91-09-072@comp.compilers> Date: Thu, 26 Sep 1991 11:33 EST Approved: compilers@iecc.cambridge.ma.us In Article <91-09-072@comp.compilers> Markus Baertschi (markus@cernvax.cern.ch) writes: MB> I'm looking for a small, but complete C compiler for MS-DOS. I just purchased a book A Small C Compiler (details below) which not only is a functional C compiler, but the source code is also included. While the compiler is not fully compatible with C, whatever is created using it is upward compatible to full C. The main reason I got it was for learning how to create a compiler. The source code for the compiler is included and the book is very good at describing what is found in the code and how the compiler works. Since it is based on a subset of C, one can test one's programming skills by making the compiler fully C compatible. The compiler does compile itself, which means you don't need to have anything other than the included disk to get started. Details on the book: Topics covered in the book include: 1. Generated code 2. Data structures 3. Front & Back end 4. Parsing (high and low levels) 5. Optimization techniques Author: James E. Hendrix Title: A Small C Compiler, 2nd Edition Pub.: M&T Books, a division of M&T Publishing 501 Galveston Drive Redwood City, CA 94063 ISBN 0-934375-88-7 ISBN 1-55851-007-9 (disk) ISBN 0-934375-97-6 (book & disk) QA76.73.S58H45 1988 005.13'3 88-9291 David Nebinger dnebing@opie.bgsu.edu -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Thu Sep 26 16:54:22 EDT 1991 Xref: iecc comp.compilers:1911 comp.lang.fortran:4246 Newsgroups: comp.compilers,comp.lang.fortran Path: iecc!compilers-sender From: koopman@utrcgw.utc.com (Philip Koopman) Subject: Optimizing i860 compiler for FORTRAN? Message-ID: <91-09-080@comp.compilers> Summary: Need one that optimizes COMPLEX Keywords: Fortran, optimize, question Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: koopman@utrcgw.utc.com (Philip Koopman) Organization: School of Computer Science, Carnegie Mellon Date: Thu, 26 Sep 91 16:57:29 GMT Approved: compilers@iecc.cambridge.ma.us I'm looking for a FORTRAN compiler that optimizes complex loads and stores (i.e. a pair of 32-bit complex numbers are loaded using a 64-bit load into a floating point register pair) for the i860. I've tried the Alliant FX2800 compiler, but it does complex pairs as separate 32-bit load and store instructions. Any pointers? Thanks, Phil Koopman koopman@utrcgw.utc.com United Technologies Research Center (203) 727-1624 411 Silver Lane East Hartford, CT 06108 -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Mon Sep 30 16:23:17 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: parke@star.enet.dec.com (Bill Parke) Subject: Re: Small C compiler wanted Message-ID: <91-09-081@comp.compilers> Keywords: C, assembler, linker Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: parke@star.enet.dec.com (Bill Parke) Organization: Digital Equipment Corporation, Nashua NH References: <91-09-072@comp.compilers> <91-09-079@comp.compilers> Date: 27 Sep 91 13:28:46 GMT Approved: compilers@iecc.cambridge.ma.us In article <91-09-079@comp.compilers>, AA409CS@opie.bgsu.edu writes: >Title: A Small C Compiler, 2nd Edition >QA76.73.S58H45 1988 005.13'3 88-9291 Has he published the second volume on the small assembler and linker yet ? His original single volume work included the compiler, assembler and linker together. -- Bill Parke VMS Development decwrl!star.enet.dec.com!parke Digital Equipment Corp parke@star.enet.dec.com 110 Spit Brook Road ZK03-2/Y05, Nashua NH 03063 -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Mon Sep 30 16:27:17 EDT 1991 Xref: iecc comp.compilers:1913 comp.unix.questions:19674 comp.lang.c:21974 Newsgroups: comp.compilers,comp.unix.questions,comp.lang.c Path: iecc!compilers-sender From: dcummings@trc.amoco.com (Dan L. Cummings) Subject: Wanted: Lex/yacc or equiv for ANSI C Message-ID: <91-09-082@comp.compilers> Keywords: yacc, lex, C, question Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: dcummings@trc.amoco.com (Dan L. Cummings) Organization: Amoco Production Company, Tulsa Research Date: Fri, 27 Sep 1991 13:31:41 GMT Approved: compilers@iecc.cambridge.ma.us Are there a versions/variants of lex & yacc that generate ANSI C? Dan <<<< dcummings@trc.amoco.com [Most versions of yacc and lex get all the code from a template file, generating only the contents of the tables. The flex and bison skeletons have ifdefs for an ANSI compiler. A quick look at the AT&T yacc parser suggests that it'd be easy enough to ansify it, probably without having to change yacc at all. -John] -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Mon Sep 30 16:28:24 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: Jens Hansson Subject: Easily retargetable register allocators Message-ID: <91-09-083@comp.compilers> Keywords: registers, optimize, bibliography Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: Jens Hansson Organization: Compilers Central Date: Fri, 27 Sep 1991 15:57:20 MET DST Approved: compilers@iecc.cambridge.ma.us I am working on a machine independent or easily retargetable register allocator, alternatively a register allocator generator, for my M.Sc. project. The allocator is part of a bigger project: a code generator generator, that will be used to develop new architectures, (e.g. "what will happen if we increase the number of integer registers and decrease cache size (fixed chip size)"...). I would like to have pointers to litterature. I am also interested in your experience with similar problems. Please respond only with register allocation issues (I am interested in everything, but I won't be finished with it in a lifetime :-)). This is my litterature list so far. I do not have all of it yet, I just know that they exist. Is something missing from the list? Chaitin, Auslander, Chandra, Cocke, Hopkins, Markstein, "Register Allocation via Coloring", Computer Languages 6 (1981), pp. 47 - 57. Chaitin, "Register Allocation and Spilling via Graph Coloring", ACM SIGPLAN Notices, 17, 6 (June 1982), (Proceedings of the SIGPLAN 82 Symposium on Compiler Construction), pp. 201 - 207. Bernstein, Golumbic, Manour, Pinter, Goldin, Krawczyk, Nahshon, "Spill Code Minimization Techniques for Optimizing Compilers", Proceedings of the SIGPLAN 1989 Conference on Programming Language Design and Implementation, pp. 258 - 263. Briggs, Cooper, Kennedy, Torczon,"Coloring Heuristics for Register Allocation" Proceedings of the SIGPLAN 1989 Conference on Programming Language Design and Implementation, pp. 275 - 284. Chow, Hennesy, "Register Allocation by Priority based Coloring" Proceedings of the SIGPLAN 1984 Symposium on Compiler Construction, Vol 19, Number 6, pp. 222 - 231. Larus, Hilfinger, "Register Allocation in the SPUR Lisp Compiler", Proceedings of the SIGPLAN 1986 Symposium on Compiler Construction, pp. 255 - 263. Freiburghouse, "Register Allocation Via Usage Counts", Comm. ACM 17, 11, Nov. 74. Leverett, "Register Allocation in Optimizing Compilers", Ph.D. Thesis and Technical Report CMU CS-81-103, Carnegie-Mellon University, February 1981. Sites Perkins, "Machine-Independent Register Allocation", ACM SIGPLAN Notices, Vol 14, Number 8 (August 1979), (Proceedings of the SIGPLAN 79 Symposium on Compiler Construction), pp 221 - 225 Wall, "Register Windows vs. Register Allocation", Proceedings of the ACM SIGPLAN 1988 Conference on Programming Language Design and Implementation, pp. 67 - 68. McKusic, "Register Allocation and Data Conversion in Machine Independent Code Generators", Ph.D. Thesis, UCB 1984, 121 pp (DA 8512915, Dissertion Abstracts Intl.) Flajolet, Sipala, Steyaert, "Analytic vibrations on the common subexpression problem" Conference Title: Automata, Languages and Programming. 17th International Colloquium Proceedings, p.220-34 Davidson, Fraser, "Register allocation and exhaustive peephole optimization" Journal: Software - Practice and Experience,vol.14, no.9, p.857-65 -- Jens Hansson e-mail: e86jh@efd.lth.se Phone int+46-(0)46-112295 snail-mail: Skarpskyttev 6B, S-22242 Lund, Sweden -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Mon Sep 30 16:29:18 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: steven@cwi.nl (Steven Pemberton) Subject: Re: Pascal P-Code; PD compiler; teaching compiler Message-ID: <91-09-084@comp.compilers> Keywords: Pascal, code, available Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: steven@cwi.nl (Steven Pemberton) Organization: CWI, Amsterdam References: <91-09-056@comp.compilers> <91-09-065@comp.compilers> Date: 27 Sep 91 14:26:37 GMT Approved: compilers@iecc.cambridge.ma.us This is in reply to 3 postings: 1: Asking for a PD Pascal Compiler 2: Asking for toy compilers to use for courses 3: Asking for references to P-Code. As a result of public demand, I have just posted to comp.sources.misc the Pascal P-code compiler that I used in a compiler course and documented in the book "Pascal Implementation" (details in the posting). The advantage of using this compiler was that it wasn't really a toy: it compiled roughly the whole language, so you could also treat the difficult parts that toy compilers often miss out, but was small enough (4000 lines) to study in one term. Best wishes, Steven Pemberton, CWI, Amsterdam; steven@cwi.nl -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Mon Sep 30 16:30:07 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: Anders Bondorf Subject: ftp-site for Scheme partial evaluator Similix up again Message-ID: <91-09-085@comp.compilers> Keywords: Scheme, FTP Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: Anders Bondorf Organization: Compilers Central Date: Fri, 27 Sep 91 17:37:08 +0200 Approved: compilers@iecc.cambridge.ma.us A few weeks ago the self-applicable partial evaluator Similix was announced in this newsgroup. Unfortunately our ftp-directory machine went down shortly after and was unstable for several days. The machine is now up and running. Here is how to ftp Similix: ----------------------------------------------------------------------------- ftp ftp.diku.dk login: anonymous password: binary hash cd misc get Similix.tar.Z bye ----------------------------------------------------------------------------- To decode the file Similix.tar.Z, run uncompress < Similix.tar.Z | tar xvpf - A directory named Similix then appears. Now read the file README in the Similix directory. ----------------------------------------------------------------------------- Best regards, Anders Bondorf DIKU, Department of Computer Science University of Copenhagen Universitetsparken 1 DK-2100 Copenhagen \O Denmark e-mail: anders@diku.dk -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Mon Sep 30 16:30:48 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: preston@dawn.rice.edu (Preston Briggs) Subject: Re: Looking for conflict graph generators Message-ID: <91-09-086@comp.compilers> Keywords: optimize, theory Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: preston@dawn.rice.edu (Preston Briggs) Organization: Rice University, Houston References: <91-09-076@comp.compilers> Date: Fri, 27 Sep 1991 21:47:45 GMT Approved: compilers@iecc.cambridge.ma.us Thomas Johnsson writes: >I'm looking for an algorithm, or better yet, a program, which generates >conflict graphs `similar' to those obtained from a graph coloring register >allocator. No help here. I don't even know about anyone working on the idea of `similar' (that is, I don't know about people studying what sorts of graphs arise from real code). Some people have done experimental work with random graphs. This is handy, since it's not too bad to generate random graphs of known chromatic color. Further, David Turner has shown that a k-coloring for most k-colorable graphs can be found with a simple, non-backtracking algorithm. Unfortunately, "most" is out of the (after all, very large) universe of k-colorable graphs. Further, as k becomes interesting (more than 4 or 5), the graph needs to be quite large for the algorithm to have much chance. For the purposes of register allocation, I don't much like measurements made on random graphs. Real interference graphs aren't that densely connected, but tend to require a relatively large number of colors. (Just look at the code and count the maximum liveness. You'll need at least that many colors.) Results on random graphs tend tend suggest things like "3 registers are enough to avoid spilling". Don't believe it. Preston Briggs -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Mon Sep 30 16:31:39 EDT 1991 Xref: iecc comp.arch:14154 comp.parallel:2218 comp.compilers:1918 Newsgroups: comp.arch,comp.parallel,comp.compilers Path: iecc!compilers-sender From: ds@theory.lcs.mit.edu (Denise Sergent) Subject: 1992 Brown/MIT Conference on VLSI and Parallel Systems Message-ID: <91-09-087@comp.compilers> Keywords: parallel, hardware, CFP Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: ds@theory.lcs.mit.edu (Denise Sergent) Organization: Laboratory for Computer Science, MIT Date: Fri, 27 Sep 91 21:26:27 GMT Approved: compilers@iecc.cambridge.ma.us Call for Papers 1992 Brown/MIT Conference Advanced Research in VLSI and Parallel Systems The design of highly integrated or large-scale systems involves a set of interrelated disciplines, including circuits and devices, design automation, VLSI architecture, software systems, and theory. Successful research in any of these disciplines increasingly relies on an understanding of the other areas. This conference, the 14th in a series that has been held at Caltech, MIT, UNC Chapel Hill, Stanford, and UC Santa Cruz, seeks to promote interaction among researchers in all disciplines that relate to highly integrated systems. papers are solicited in the following and related areas: CIRCUITS AND DEVICES: Innovative electrical circuits, optical computing, automated semiconductor manufacturing, wafer-scale systems. DESIGN AUTOMATION: Synthesis and silicon compilation, layout and routing, analysis and simulation, novel design methods, architectural design support, design for test. VLSI ARCHITECTURE: Highly parallel architectures, special-purpose VLSI chips and systems, novel small-scale systems, I/O and secondary storage, packaging, and fault tolerance. SOFTWARE SYSTEMS: Architecture-driven programming models, parallel languages, compiling for concurrency, operating systems, synchronization. THEORY: Parallel algorithms, VLSI theory, layout and wireability analysis, I/O complexity, interconnection networks, reliability. Keynote Speaker STEPHEN NELSON Head of massively parallel systems development at Cray Research CONTRIBUTED PAPERS: Submit five copies of a draft paper, not to exceed 15 pages, with a 500-word abstract by TUESDAY, OCTOBER 8, 1991 to: Brown/MIT VLSI Conference 545 Technology Square Cambridge, MA 02139 Please include address, phone number, and email address, if available, for the contact author. Notification of acceptances will be sent by December 3, 1991. Camera-ready copy of accepted papers is due January 7, 1992 so that the proceedings can be available at the conference. ORGANIZATION OF THE CONFERENCE: The conference is organized jointly by the Department of Computer Science, Brown University and the MIT VLSI and Parallel Systems Group. The Conference Chair is Charles E. Leiserson (MIT) and the Local Arrangements Chair is Dan Lopresti (Brown). In order to keep the conference small and informal, attendance is by invitation only. If you would like an invitation or further information about the conference, contact Denise Sergent at the above address or at (617) 253-2046 (phone) or ds@theory.lcs.mit.edu (email). PROGRAM COMMITTEE: Program committee co-chairs are John Savage (Brown) and Tom Knight (MIT). The program committee consists of Sandeep Bhatt (Yale), Gaetano Borriello (U. Washington), Rich Brown (U. Michigan), Randy Bryant (Carnegie Mellon U.), Srinivas Devadas (MIT), Gershon Kedem (Duke U.), Monica Lam (Stanford), Jack Raffel (MIT Lincoln Labs), Sartaj Sahni (U. Florida), Carlo Sequin (U.C. Berkeley), Bob Sproull (Sun Microsystems) and Jeff Vitter (Brown). -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Mon Sep 30 16:32:43 EDT 1991 Xref: iecc comp.lang.functional:864 comp.lang.scheme:2180 comp.lang.prolog:2592 comp.compilers:1919 Newsgroups: comp.lang.functional,comp.lang.scheme,comp.lang.prolog,comp.compilers Path: iecc!compilers-sender From: sestoft@diku.dk (Peter Sestoft) Subject: FTP-able bibliography on partial evaluation! Message-ID: <91-09-088@comp.compilers> Keywords: bibliography, FTP, prolog, Scheme, functional Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: sestoft@diku.dk (Peter Sestoft) Organization: Department of Computer Science, U of Copenhagen Date: 28 Sep 91 14:00:32 GMT Approved: compilers@iecc.cambridge.ma.us I keep a current bibliography on partial evaluation in Bibtex format. The bibliography has 369 entries and is updated regularly. The most recent version is available for anonymous ftp from ftp.diku.dk (Internet number 129.142.96.1) as file /pub/doc/partial-eval.bib.Z in the ftp directory. The compressed file is 62 KB. To obtain this file from DIKU, do the following from the Unix shell: (1) Type "ftp ftp.diku.dk" (2) Reply "ftp" to the prompt "Name (freja.diku.dk:...): " (3) Reply with your own e-mail address to the prompt "Password: " (4) Type "cd /pub/doc" (5) Type "binary" (6) Type "get partial-eval.bib.Z" -- and the transfer begins; (7) Type "bye" -- when completed. (8) Type "uncompress partial-eval.bib.Z" This should leave you with a Bibtex file called "partial-eval.bib". I hope that you will find it useful. Yours, Peter Sestoft -- Peter Sestoft * sestoft@diku.dk * DIKU, Department of Computer Science University of Copenhagen, Universitetsparken 1, DK-2100 Copenhagen O, Denmark Tel: +45 31 39 64 66 * Direct: +45 31 39 33 11/406 * Fax: +45 31 39 02 21 -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Mon Sep 30 17:47:26 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: haertel@euclid.uoregon.edu (Mike Haertel) Subject: time spent in compiler phases Message-ID: <91-09-089@comp.compilers> Keywords: performance, GCC Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: haertel@euclid.uoregon.edu (Mike Haertel) Organization: Compilers Central References: <91-09-077@comp.compilers> Date: Sun, 29 Sep 91 09:58:28 PDT Approved: compilers@iecc.cambridge.ma.us The GNU C compiler, given the -Q option, will print an approximate time breakdown of the time spent in its different passes. -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Mon Sep 30 17:49:20 EDT 1991 Xref: iecc comp.sys.mips:1868 comp.arch:14161 comp.compilers:1921 Newsgroups: comp.sys.mips,comp.arch,comp.compilers Path: iecc!compilers-sender From: slusher@thor.ece.uc.edu (Charles E. Slusher) Subject: MIPS R2000 interpretor Message-ID: <91-09-090@comp.compilers> Keywords: performance, interpreter Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: slusher@thor.ece.uc.edu (Charles E. Slusher) Organization: University of Cincinnati Date: Sat, 28 Sep 91 20:31:04 GMT Approved: compilers@iecc.cambridge.ma.us I am a graduate student in computer eng. and the project with which I am working has need of a MIPS R2000 interpreter (preferably written in C). Does anybody out there know of such an animal? Via ftp or any other source? %token THANKS 1 thanks: THANKS { printf("Thank You,\n"); } Charles Slusher ces@thor.ece.uc.edu -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. From compilers Mon Sep 30 23:59:06 EDT 1991 Newsgroups: comp.compilers Path: iecc!compilers-sender From: preston@dawn.rice.edu (Preston Briggs) Subject: Re: Looking for conflict graph generators Message-ID: <91-09-091@comp.compilers> Keywords: optimize, theory Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: preston@dawn.rice.edu (Preston Briggs) Organization: Rice University, Houston References: <91-09-076@comp.compilers> <91-09-086@comp.compilers> Date: Tue, 1 Oct 1991 00:54:17 GMT Approved: compilers@iecc.cambridge.ma.us I wrote: >David Turner has shown that a k-coloring for most >k-colorable graphs can be found with a simple, non-backtracking algorithm. However, it was Jonathan Turner. The reference is Almost all k-colorable graphs are easy to color Jonathan S. Turner Journal of Algorithms volume 9, 1988 Preston Briggs -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.