htf@sari.edinburgh.ac.uk (H T Fallside) (12/06/90)
I'm after a preprocessor that will do in-line expansion of procedure
calls IN SOURCE for C to produce one lovely long main() procedure,
something capable of dealing intelligently with parameters and local
variables. Anyone out there got any ideas before I start writing ?
hamish
---------------------
htf@uk.ac.ed.castle
[GCC has an "inline" keyword which expands procedures in line, but I haven't
seen any source-to-source converters. What do you plan to do about
directly or indirectly recursive routines? -John]
--
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.markhall@pyrps5.pyramid.com (Mark Hall) (12/12/90)
In article <10767.9012051639@subnode.sari.ed.ac.uk> H T Fallside <htf@sari.edinburgh.ac.uk> writes: >I'm after a preprocessor that will do in-line expansion of procedure >calls IN SOURCE for C to produce one lovely long main() procedure, >something capable of dealing intelligently with parameters and local >variables. Anyone out there got any ideas before I start writing ? Since the one true answer has yet to be posted, allow me: A Study of a C Function Inliner Jack W. Davidson and Anne M. Holler University of Virginia Heaven knows where I got this paper, probably heard they were working on it through the grapevine. I got a copy of the INLINER program from them for a small fee and one UNIX(tm) proof-of-purchase seal. You can get a copy by contacting Jack Davidson using either of: jwd@virginia.edu uunet!virginia!jwd (804)924-7605 Two years ago, when I first used it, it did a fine job. Since then Anne Holler has been improving it. By now I'm sure it'll be more than adequate for you needs. -Mark Hall (smart mailer): markhall@pyrps5.pyramid.com (uucp paths): {ames|decwrl|sun|seismo}!pyramid!markhall -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.
djones@decwrl.dec.com (Dave Jones) (12/14/90)
> I'm after a preprocessor that will do in-line expansion of procedure > calls IN SOURCE for C to produce one lovely long main() procedure, > something capable of dealing intelligently with parameters and local > variables. Anyone out there got any ideas before I start writing ? You might look for inspiration in "cfront" or some other C++ to C compiler that does in-line procedure expansion. Look at the C code that it produces for in-line calls and you'll get the flavor of it. Now then, please tell us why in the world you would want to make an entire program into one procedure. That will certainly make the resulting object code slower. For one thing, on most machines, the procedure call/return is an efficient way to save and restore registers. For another, unless the program is a rather simple one with most procedures being called from only one place, the program will be larger. On machines that do paging, larger usually means slower, sometimes much slower. If you are trying to get around some system limitation, tell us what it is and maybe someone will come up with an alterative method. I will leave you with one last word: "recursion". You will have to reinvent procedure calls to handle recursion. -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.
pardo@cs.washington.edu (David Keppel) (12/17/90)
>>[I want to create one huge main()] megatest!djones@decwrl.dec.com (Dave Jones) writes: >[Why? It will certainly make the resulting object code slower.] >[For example, call/return is an efficient way to save/restore > registers; the program will be larger unless procedures have only > one call site; a larger program is usually slower; you will have to > reinvent procedure calls to handle recursion.] Um, er, ah, well, uh... I'm not the original author so I can't comment on why s/he wanted to do it. It does seem to me, though, that you're imagining a particular model for how things get expanded. I don't see any particular reason why ANY of the problems mentioned above are ``problems''. * Call/return as an efficient way to save/restore registers The VAX and Tahoes are optimized to save and restore registers in call/return, but also have an explict register save with mask instruction that does the same thing without the overhead of setting up the argument/frame pointer(s), etc. The 680x0 family has a similar instruction. On many RISCy machines -- and on a number of CISCy machines -- register save/restore is left almost entirely up to the programmer, the major exceptions being CISCy machines that dedicate the program counter and the stack pointer. * The program will be larger unless procedures have only one call site. That's assuming that you have a function inlined everywhere that they appear. An alternative is to take each function |x| and produce a label |x| and a set of ``calling conventions'' for transferring control to that label. You do wind up reinventing the procedure call, it is true, but you also wind up with equivalent-size code. * A larger program will generally be slower That depends in great detail on things like caching behavior. Strictly inling long squences is almost always a lose, but shorter sequences can profitably be replicated at a substantial increase in ojbect code size if, say, the larger code improves prefetching. * You have to reinvent procedure calls to handle recursion. Excluding the case of tail calling, yes, you do have to reinvent procedure calls. However, you might get more freedom about designing custom calling conventions. In summary, aggressive compilers such as the MIPS compiler generally try to create one large procedure out of a program. They generally don't inline recursive calls unless they are tail-recursive. The major difference is that they reserve ``squashing everything in to one big function'' for e.g., link time. Yeah, well, I'd like to squash C source, too, but for my needs it's the best programming language I have avaialable. ;-D on ( But working on it anyway ) Pardo -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.
htf@castle.ed.ac.uk (H T Fallside) (12/17/90)
In article <14662@goofy.megatest.UUCP> megatest!djones@decwrl.dec.com (Dave Jones) writes: First thanks to those people writing to tell me about Jack Davidson's and Ann Holler's inliner (see 1254) which sounds like being just the thing I need. >Now then, please tell us why in the world you would want to make an entire >program into one procedure. I'm looking at doing some silicon compilation on dsp algorithms written in C. It's much easier to analyse the allocation requirements, loop nesting depth and any parallelism when the code is non-procedural. I'm not concerned at this stage about size or speed issues on host machines just whether the code remains compilable after i've been playing around with it :-) >I will leave you with one last word: "recursion". I was under the impression that any recursive procedure could be exchanged for an iterative one (and vice versa) am i wrong ? thanks again hamish ---------- htf@uk.ac.ed.castle [It's true, recursion and iteration are equivalent, but the translation can be ugly, particularly in the presence of things like indirect recursion via function pointers. -John] -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.
leland@cs.columbia.edu (Lee Woodbury) (12/18/90)
In article <10767.9012051639@subnode.sari.ed.ac.uk> H T Fallside <htf@sari.edinburgh.ac.uk> writes: >I'm after a preprocessor that will do in-line expansion of procedure >calls IN SOURCE for C to produce one lovely long main() procedure, >something capable of dealing intelligently with parameters and local >variables. Anyone out there got any ideas before I start writing ? In late 1987, this fellow Steven McGeady 3714 SE 26th Ave. Portland, OR 97202 (503) 235-2462 (503) 696-4393 tektronix!ogcvax!omepd!mcg intelca!omepd!mcg posted source to comp.sources.unix for a program called 'inline' which did just what you wanted. I got it, saved it, and still have it, but have never used it, so I can't tell you how good it is. The package contained a copyright notice that prevents me from simply sending it to you, but I have enclosed the message that accompanied the original posting, the copyright notice, and the manual page (which the copyright notice specifically allows me to distribute). The source itself should still be in the comp.sources.unix archives (Volume 11, Issue 39, Archive-name: inline/Part01...Part04); there was also a patch (Volume 11, Issue 43, Archive-name: inline/Patch1). You may also want to consider trying to reach the author to see if he has a more recent version. Good luck. I would be interested to hear how useful this code is. Leland Woodbury ARPANET/INTERNET: leland@cs.columbia.edu USENET: ...!columbia!cs.columbia.edu!leland BITNET: leland%cs.columbia.edu@cuvmb USMAIL: Columbia Univ., 457 CS, 500 W. 120 St., NYC 10027-6699 TELEPHONE: 212-854-8109 FAX: 212-666-0140 ----------------------------------------------------------------------- : This is a shar archive. Extract with sh, not csh. : The rest of this file will extract: : : NN-HEADER : COPYRIGHT : inline.1 : echo x - NN-HEADER sed 's/^X//' > NN-HEADER << '//go.sysin dd *' XFrom columbia!rutgers!ukma!uunet!rs Thu Sep 24 13:11:15 EDT 1987 X>From: rs@uunet.UU.NET (Rich Salz) XNewsgroups: comp.sources.unix XSubject: v11i039: Inline code expander for C, Part01/04 XMessage-ID: <1582@uunet.UU.NET> XDate: 16 Sep 87 03:57:56 GMT XOrganization: UUNET Communications Services, Arlington, VA XLines: 852 XApproved: rs@uunet.UU.NET X XSubmitted-by: omepd!mcg@uunet.UU.NET XPosting-number: Volume 11, Issue 39 XArchive-name: inline/Part01 X X[ Please note The copyright restrictions; if you have problems with them, X calm reasoned e-mail to Mr. McGeady will probably be most effective. X Don't send ME mail, as I don't care enough. --r$ ] X XI have a submission for comp.sources.unix, my inline code substituter, X'inline'. It has been in beta-test for over a month now, and I believe Xthat it is stable enough to be released. The next four messages will Xcontain the four shar files with the source, documentation, test files, Xand design notes. X XA word about the copyright. I have chosen to copyright the source to Xthe program, but place the binaries in the public domain. This is Xpredominantly to retain control over modifications to the source and Xover what people might do with it. The copyright notice file COPYRIGHT Xcontains explicit permission for distribution over comp.sources, and Xvia the archive server, but disallows other distribution. If there is Xa problem with this, please let me know. X XThank you for your help. X XS. McGeady Xtektronix!ogcvax!omepd!mcg Xintelca!mipos3!omepd!mcg X(503) 696-4393 X //go.sysin dd * echo x - COPYRIGHT sed 's/^X//' > COPYRIGHT << '//go.sysin dd *' X XThe source code to this program ('inline') is copyrighted, and all rights Xare reserved by the author. The copyrighted files include the C source files Xand header files (all these files have copyright notices on them). XRedistribution of this source code requires explicit permission from the Xauthor. The author explicit grants permission to the comp.sources Xmoderators to redistribute the source code to end-users. Other persons Xwishing to redistribute this code must have permission from the author. (*) X XPermission is hereby granted to distribute the binary object code for this Xprogram without explicit permission from the author, so long as such Xdistribution is not for profit. X XThe Manual page for this program is hereby placed in the public domain. X X4/30/87 X XSteven McGeady X3714 SE 26th Ave. XPortland, OR 97202 X(503) 235-2462 X(503) 696-4393 Xtektronix!ogcvax!omepd!mcg Xintelca!omepd!mcg X X(*) I am taking the position that the posting of "diffs", including Xreasonable context diffs, is "fair use", and is permitted (or at least XI won't complain about it). However, I would prefer if all modifications Xwere sent to me first. X X //go.sysin dd * echo x - inline.1 sed 's/^X//' > inline.1 << '//go.sysin dd *' X.TH INLINE 1 X.\" $Header: inline.1,v 1.8 87/06/24 13:21:28 mcg Rel $ X.SH NAME Xinline \- C preprocessor for inline functions X.SH SYNOPSIS X.B inline X[ X.B \-w X] [ X.B \-e X] [ X.B \-s X] [ X.B \-n X] [ X.B \-d X] [ X.B \-2 X] [ X.B \-S [ em X] X] X[ infile ] [ outfile ] X.SH DESCRIPTION X.I Inline Xis a Xpreprocessor that accepts C language programs Xcontaining the additional storage-class keyword X\fBinline\fR applied to function declarations, and Xgenerates identical C programs that (usually) have the Xfunctions so marked expanded where they are called. XInput code lacking the X.B inline Xkeyword is output unchanged. XThus X.I inline Xallows C programmers a feature similar to that provided Xby the C++ language. XHowever, while the specifications are the same, the X.I inline Xprogram works substantially differently from currently Ximplemented C++ compilers. XCurrent C++ compilers rewrite Xinline functions into expressions, thus prohibiting loops in them, but Xallowing their use in contexts such as control statements of looping Xconstructs. X.I Inline Xnormally Xreformats Xinline functions into code concealed in local blocks, adds Xvariables for parameter and return values, and changes X.B return Xstatements into X.BR goto s. XThis allows use of all normal C constructs within inlines. XThis rewriting is appropriate in all contexts except when Xinline functions are called in the control parts of X.B for Xand X.B while Xloops, and in a few other cases. XIn these cases, the C++ style expansion is used, and the procedures are Xrewritten as expressions when Xpossible (that is, when they lack loops, switches, and goto's). X.PP X.I Inline Xemits X.B extern X(or, optionally, X.BR static ) Xpredeclarations for Xinline functions, so that unexpanded instances are compiled correctly, Xand can be supplied externally. XAdditionally, options are provided to emit the bodies of any unexpanded Xfunctions as static procedures at the end of a module, or to emit Xthe bodies of all inline functions alone, allowing inline functions to Xbe collected into a library. X.PP XIn normal operation, X.I inline Xfunctions must be declared before they are used (like C++). XThe \-2 (two-pass) option relaxes this requirement, at a 30% penalty in Xprocessing time. X.PP XThe following options are provided: X.IP \-w Xsupress warning messages about unexpandable instances of inline functions. X.IP \-e Xemit predeclarations as X.BR extern s, Xand do not dump bodies of unexpanded functions (default). X.IP \-s Xemit predeclarations as X.BR static s, Xand dump bodies of unexpanded functions. X.IP \-n Xemit no predeclarations at all, and do not Xdump bodies of unexpanded functions. XThis allows the gathering of X.B inline Xfunctions into a library, to resolve unexpanded Xreferences and any instances where the address Xof an X.B inline Xwas taken. X.IP \-d Xdo not emit the main program, only dump the Xbodies of all inlines (incompatible with \-e, \-s, and \-n). X.IP \-2 Xprocess the file in two passes. This allows inline functions to be Xdeclared after their use. For this option, standard input is not Xaccepted. X.IP \-S Xemit (on the standard error output) statistics Xabout the expansion process. X.IP \-Se Xemit extended statistics, giving expansion statistics Xfor each X.BR inline . X.IP \-Sm Xemit statistics about the memory usage of the program (if the program is Xcompiled to collect these statistics). X.PP XIf no input file is specified, the standard input is assumed, Xand likewise for the standard output. X.SH BUGS/CAVEATS X.I Inline Xdoes not perform predictably when given incorrect C programs. XIt is easy to test a program that contains inlines with the Xcommand: X.sp X.nf X.na X cc -c -Dinline=static file.c X.fi X.ad X.PP XWhen multiple inline functions are present in a single expression, Xthe order in which the functions are executed in the inline code Xis sometimes different from the order in which they would have been Xcalled had they not been expanded. XIn particular, all functions in the expression will be evaluated, Xleft-to-right, before the operations in the expression are performed. XThis is correct for most C operators, X.I except Xthe comma, boolean-or (||), and boolean-and (&&) operators. XInline handles all but the comma operator correctly, expressionizing Xcalls on the right side of the conditional operators. X.PP XWhile X.I inline Xattempts to pass preprocessor defines through without change, Xit is strongly suggested that X.I inline Xbe executed Xon code that has already been processed by Xthe C preprocessor /lib/cpp. X.PP X.I Inline Xdoes not recognize certain degenerate cases of function declarations Xand calls, in particular: X.sp X.nf X.na X (foo)(arg); X.fi X.ad X.I Inline Xalso does not correctly handle inline functions which take the address of Xlabels, or which use labels other than in \fBgoto\fR statements, both Xextremely distasteful (and probably illegal) practices. X.SH "SEE ALSO" Xcc(1), cpp(1) X.SH NOTE X.I Inline Xsource code Xis Copyright, 1986, 1987 by S. McGeady, all rights reserved. X.br XThe binaries for the VAX version of this program and this manual page are Xin the public domain. X.SH AUTHOR XS. McGeady X.br X3714 SE 26th Ave. X.br XPortland, OR 97202 X.br X(503) 235-2462 //go.sysin dd * exit -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.
Olivier.Levillain@cl.bull.fr (Olivier Levillain) (12/18/90)
In article <14662@goofy.megatest.UUCP>, megatest!djones@decwrl.dec.com (Dave Jones) writes: |>Now then, please tell us why in the world you would want to make an entire |>program into one procedure. That will certainly make the resulting object |>code slower. For one thing, on most machines, the procedure call/return is |>an efficient way to save and restore registers. For another, unless the |>program is a rather simple one with most procedures being called from only |>one place, the program will be larger. On machines that do paging, larger |>usually means slower, sometimes much slower. I don't agree with these arguments. |> For one thing, on most machines, the procedure call/return is |>an efficient way to save and restore registers. Saving and restoring registers even if it is efficient, can be expensive especially on CISC machine. On our machine (BULL DPS7), it uses 50 cycles + 1 cycle by register to save/restore. |> For another, unless the |>program is a rather simple one with most procedures being called from only |>one place, the program will be larger. I wrote myself an inliner for a common code generator which generates code for several front-ends (C, Fortran, PL1). Inlining is done on an intermediary language and takes place before local and global optimization. So that the optimizers can work on larger sequences of linear code. Big parts in and around call of inlined functions disappear in the optimizers because their context is more completely defined. If you write: f (x) int x; { switch (x) { case 1: return 1;break; case 2: return 0;break; case 3: return 1;break; case 4; return 2;break; } } main () { int y; ... y=2; ... if (f(y)) ... else <stat1>; ... Without an inliner, the whole code will be generated. If you "inline" f, generated code will look as if you wrote: main () { int y; ... y=2; ... <stat1>; ... because, after f has been inlined, optimizer can compute at compile-time that f(y) will return 0. So that, the final size of generated code is not necessarily very much bigger. |>On machines that do paging, larger |>usually means slower, sometimes much slower. If the procedure you call is not in the same page that the page from where you call this procedure, OS will also have a missing page exception to handle. |>I will leave you with one last word: "recursion". You will have to |>reinvent procedure calls to handle recursion. Inlining procedure does not mean that you don't call a procedure any longer. You can just inline a call to a (directly or not) recursive procedure and leave the really recursive call in place. As a conclusion, just one thing: we have an improvement of 30% on dhrystone1.1 benchmark when using the inliner. Olivier LEVILLAIN --- Bull S.A. BSS7-LANG-LSLI e-mail: Olivier.Levillain@cl.bull.fr Rue Jean-Jaures, F6/1D/10, BP 53 tel: (33-1) 34-80-65-52 78340 Les Clayes-sous-Bois, France Fax: (33-1) 34-80-79-50 -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.