home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / altsrcs / 3 / 3256 < prev    next >
Encoding:
Internet Message Format  |  1991-04-30  |  9.3 KB
  1. From: eliot@cs.qmw.ac.uk (Eliot Miranda)
  2. Newsgroups: comp.compilers,gnu.gcc.bug,alt.sources
  3. Subject: re: Threaded Code
  4. Message-ID: <3520@sequent.cs.qmw.ac.uk>
  5. Date: 5 Apr 91 11:43:51 GMT
  6. Approved: compilers@iecc.cambridge.ma.us
  7.  
  8. I recently posted articles to comp.compilers & alt.sources on how
  9. to write threaded code machines in C.  I received the following questions
  10. from Simon Peyton Jones at Glasgow.  They are specific to GCC.
  11. Since they have non-obvious answers & since the answers suggest
  12. augmentation of the GCC compiler I'm posting my response to Simon.
  13.  
  14. >From: Simon L Peyton Jones <simonpj@cs.gla.ac.uk>
  15. >
  16. >I saw your article about threaded code.  Like you and others, we are
  17. >using C as an assembler, only for a pure functional language, Haskell.
  18. >I have some brief questions.
  19. >
  20. >1. By telling GCC not to use a frame pointer, one can eliminate
  21. >the prolog entirely, can't one?  So why edit it out?
  22.  
  23. No, registers local to the procedure will still be saved & stack space
  24. allocated for automatic variables. This IS a problem since the
  25. threaded-code jump at the end of the procedure will miss the register
  26. restores before the epilogue.  Consequently the stack will grow unless
  27. these register saves & stack-space allocations are removed.  Also
  28. GCC can not always eliminate the frame pointer.
  29.  
  30. >I guess the answer is going to be local variables, allocated once for
  31. >all by the StartTCMachine routine.  Still, it seems quite a pain.  I guess
  32. >one could sacrifice some (perhaps slight) speed by using a bunch of
  33. >globals instead.
  34. For certain routines, not using register variables will be expensive
  35. (e.g. a simple integer arithmetic primitive).
  36.  
  37. >2. You edit out the epilogue for tidiness only, I take it.  It doesn't
  38. >cause any problems if you leave it in, does it?
  39. No, but given that the prologue has to be removed & removing the epilogue
  40. is as easy (& given finite memory :-) one might as well remove it.
  41. >
  42. >3. Why do you use no-defer-pop (with the associated bug)?
  43. OK. This is again to avoid stack growth.  On conventional stack architectures
  44. gcc will try & combine the argument popping code of a sequence of procedure calls.
  45. e.g.
  46. extern long a, b, c;
  47. void doit() {
  48.     foo(a); bar(b); baz(c);
  49. }
  50.  
  51. with -O -no-defer-pop one might expect gcc to generate
  52.  
  53.     link %a6,#0
  54.     movel a,%sp@-
  55.     jbsr foo
  56.     addqw #4,%sp
  57.     movel b,%sp@-
  58.     jbsr bar
  59.     addqw #4,%sp
  60.     movel c,%sp@-
  61.     jbsr baz
  62.     addqw #4,%sp
  63.     unlk %a6
  64.     rts
  65.  
  66. but because gcc knows that the unlk instruction will roll back the stack
  67. in fact gcc generates:
  68.  
  69.     link %a6,#0
  70.     movel a,%sp@-
  71.     jbsr foo
  72.     addqw #4,%sp
  73.     movel b,%sp@-
  74.     jbsr bar
  75.     addqw #4,%sp
  76.     movel c,%sp@-
  77.     jbsr baz
  78.     unlk %a6
  79.     rts
  80.  
  81. With -O -fdefer-pop gcc optimizes out the pops completely & generates:
  82.  
  83.     link %a6,#0
  84.     movel a,%sp@-
  85.     jbsr foo
  86.     movel b,%sp@-
  87.     jbsr bar
  88.     movel c,%sp@-
  89.     jbsr baz
  90.     unlk %a6
  91.     rts
  92.  
  93. with -O -fomit-frame-pointer -fdefer-pop gcc generates:
  94.  
  95.     movel a,%sp@-
  96.     jbsr foo
  97.     movel b,%sp@-
  98.     jbsr bar
  99.     movel c,%sp@-
  100.     jbsr baz
  101.     addw #12,%sp
  102.     rts
  103.  
  104. & with -O -fomit-frame-pointer -fno-defer-pop gcc generates:
  105.  
  106.     movel a,%sp@-
  107.     jbsr foo
  108.     addqw #4,%sp
  109.     movel b,%sp@-
  110.     jbsr bar
  111.     addqw #4,%sp
  112.     movel c,%sp@-
  113.     jbsr baz
  114.     addqw #4,%sp
  115.     rts
  116.  
  117. All the above cases are as one would wish.  The elimination of all
  118. defered pops in the unlk instruction is especially clever.
  119.  
  120. However, in the presence of the threaded-code jump the waters darken!
  121. Consider what gcc generates for:
  122.  
  123.     register void (**tcip)() asm("%a5");
  124.  
  125.     #define JUMPNEXT do{asm("movl %a5@+,%a0; jmp %a0@");return;}while(0)
  126.  
  127.     extern long a, b;
  128.     void doit() {
  129.         foo(a); bar(b); JUMPNEXT;
  130.     }
  131. with -O -fdefer-pop gcc generates
  132.  
  133. doit:
  134.     link %a6,#0
  135.     movel a,%sp@-
  136.     jbsr foo
  137.     movel b,%sp@-
  138.     jbsr bar
  139. #APP
  140.     movl %a5@+,%a0; jmp %a0@
  141. #NO_APP
  142.     unlk %a6
  143.     rts
  144.  
  145. This is clearly no good because the arguments to both foo & bar
  146. will never be popped. Every time doit() is executed the stack will grow
  147. by 8 bytes.  Soon your program will dump core with a very large stack
  148. segment!
  149.  
  150. with -O -fno-defer-pop gcc generates:
  151.  
  152.     link %a6,#0
  153.     movel a,%sp@-
  154.     jbsr foo
  155.     addqw #4,%sp
  156.     movel b,%sp@-
  157.     jbsr bar
  158. #APP
  159.     movl %a5@+,%a0; jmp %a0@
  160. #NO_APP
  161.     unlk %a6
  162.     rts
  163.  
  164. Again useless because bar's pop has been folded into the unlk
  165. which won't be executed.
  166.  
  167. with -O -fdefer-pop -fomit-frame-pointer gcc generates
  168.  
  169.     movel a,%sp@-
  170.     jbsr foo
  171.     movel b,%sp@-
  172.     jbsr bar
  173.     addqw #8,%sp
  174. #APP
  175.     movl %a5@+,%a0; jmp %a0@
  176. #NO_APP
  177.     rts
  178.  
  179. This is great. However, not all functions are susceptible to
  180. the omit-frame-pointer optimization (i.e. functions
  181. with local variables).  E.g. the code generated for:
  182.  
  183.     register void (**tcip)() asm("%a5");
  184.  
  185.     #define JUMPNEXT do{asm("movl %a5@+,%a0; jmp %a0@");return;}while(0)
  186.  
  187.     extern long a, b;
  188.     void doit() {
  189.         char    large[1024];
  190.         foo(a,large); bar(b); JUMPNEXT;
  191.     }
  192.  
  193. with -O -fomit-frame-pointer -fdefer-pop is:
  194.  
  195.     link %a6,#-1024
  196.     pea %a6@(-1024)
  197.     movel a,%sp@-
  198.     jbsr foo
  199.     movel b,%sp@-
  200.     jbsr bar
  201. #APP
  202.     movl %a5@+,%a0; jmp %a0@
  203. #NO_APP
  204.     unlk %a6
  205.     rts
  206.  
  207. so in general one can't rely on -fomit-frame-pointer.
  208. For the above example both
  209.     -O -fomit-frame-pointer -fno-defer-pop
  210. and
  211.     -O -fno-defer-pop
  212. generate:
  213.  
  214. doit:
  215.     link %a6,#-1024
  216.     pea %a6@(-1024)
  217.     movel a,%sp@-
  218.     jbsr foo
  219.     addqw #8,%sp
  220.     movel b,%sp@-
  221.     jbsr bar
  222. #APP
  223.     movl %a5@+,%a0; jmp %a0@
  224. #NO_APP
  225.     unlk %a6
  226.     rts
  227.  
  228. This is also useless because bar's argument pop has been folded away.  The
  229. problem is that gcc will always fold away the last call's argument pop if
  230. the function has a frame pointer, and -fomit-frame-pointer can't allways
  231. get rid of the frame pointer.  In fact, in the presence of variable sized
  232. automatic variables or calls on alloca it would be very hard (impossible
  233. for recursive functions?) to do.
  234.  
  235. The neatest solution I've come up with is to use -fno-defer-pop and a
  236. dummy function call between the threaded-code jump and the return:
  237.  
  238.     register void (**tcip)() asm("%a5");
  239.  
  240.     #define JUMPNEXT do{asm("movl %a5@+,%a0; jmp %a0@");SBD();return;}while(0)
  241.  
  242.     extern long a, b;
  243.     void doit() {
  244.         foo(a); bar(b); JUMPNEXT;
  245.     }
  246. with -O -fno-defer-pop gcc generates:
  247.  
  248.     link %a6,#0
  249.     movel a,%sp@-
  250.     jbsr foo
  251.     addqw #4,%sp
  252.     movel b,%sp@-
  253.     jbsr bar
  254.     addqw #4,%sp
  255. #APP
  256.     movl %a5@+,%a0; jmp %a0@
  257. #NO_APP
  258.     jbsr SBD
  259.     unlk %a6
  260.     rts
  261.  
  262. Now bar's argument pop is not folded because its no longer the last
  263. call in the routine, SBD is.
  264. So the call to SBD
  265.     a) prevents gcc's 'last call argument pop fold into unlk' optimization
  266.        which prevents uncontrolled stack growth.
  267.     b) doesn't get executed because of the jump
  268.     c) is trivial to remove from the assembler with a sed-script
  269.  
  270.  
  271. One an try to use -fcaller-saves, but this surrounds calls with unnecessary
  272. register saves & restores that for the code to be optimal have to be edited out.
  273.  
  274. >4. Why does JUMPNEXT have a loop?  Surely the jump leaves the loop right
  275. >away.  Presumably you are tricking the compiler somehow.
  276.  
  277. This is old C lore.  The problem is
  278.     'How do you write a macro that is a sequence of statements
  279.      that can be used wherever a single statement can?'
  280.  
  281. take the following definition of JUMPNEXT:
  282. #define JUMPNEXT asm("movl %a5@+,%a0; jmp %a0@");return;
  283.  
  284. Now invoke it here:
  285.     if (its_time_to_jump)
  286.         JUMPNEXT;
  287.     do_something_else();
  288.  
  289. This expands to:
  290.     if (its_time_to_jump)
  291.         asm("movl %a5@+,%a0; jmp %a0@");
  292.     return;
  293.     do_something_else();
  294.  
  295. Not at all whats intended!
  296.  
  297. There are two tricks I know of (the first I saw in Berkely Smalltalk,
  298. the second in Richard Stallman's gcc manual. I expect they're both
  299. quite old).
  300. The first is to surround your statements with
  301. if (TRUE){statements}else
  302. i.e.
  303. #define JUMPNEXT if(1){asm("movl %a5@+,%a0; jmp %a0@");return;}else
  304. So now we get:
  305.     if (its_time_to_jump)
  306.         if (1){
  307.             asm("movl %a5@+,%a0; jmp %a0@");
  308.             return;
  309.         else;
  310.     do_something_else();
  311.  
  312. which works because C binds elses innermost first. However, some
  313. compilers will whine about dangling elses.  The second scheme is
  314. more elegant (-:
  315.  
  316. Surround your statements with
  317. do{statements}while(FALSE);
  318. which will execute statements precisely once (its NOT a loop).
  319. i.e.
  320. #define JUMPNEXT do{asm("movl %a5@+,%a0; jmp %a0@");SBD();return;}while(0)
  321. expands to
  322.  
  323.     if (its_time_to_jump)
  324.         do {
  325.             asm("movl %a5@+,%a0; jmp %a0@");
  326.             return;
  327.         while(0);
  328.     do_something_else();
  329.  
  330. which does what's wanted and doesn't incur compiler whines.
  331.  
  332.  
  333. >Thanks
  334. >
  335. >Simon L Peyton Jones, Glasgow University
  336.  
  337. More and more people are taking the 'use C as an assembler' route, and
  338. more and more people are using GCC to do it (because its code quality is
  339. good, it had global register variables, and it has an excellent asm
  340. facility).  The threaded-code in C idea is also becomming more popular.
  341. But as the code above demonstrates, one does have to side-step
  342. optimizations and develop system-specific assembler editing scripts.
  343.  
  344. I'd like to ask Richard Stallman & the GCC development team for
  345.     -fno-prolog -fno-epilog
  346. flags that instruct gcc to generate
  347.     a) no register saves or restores
  348.     b) no automatic variable allocation
  349.     c) no procedure linkage/frame creation
  350.  
  351. Then the optimal 'Threaded-Code Machine in GCC C' can be compiled without
  352. any assembler editing scripts at all.
  353.  
  354. Also nice would be a way of telling GCC that an asm statement
  355. changed the flow of control so GCC could
  356.     a) warn about not-reached code
  357.     b) eliminate unnecessary code (do more code folding)
  358. -- 
  359. Eliot Miranda            email:    eliot@cs.qmw.ac.uk
  360. Dept of Computer Science    Tel:    071 975 5229 (+44 71 975 5229)
  361. Queen Mary Westfield College    ARPA:    eliot%cs.qmw.ac.uk@nsf.ac.uk    
  362. Mile End Road            UUCP:    eliot@qmw-cs.uucp
  363. LONDON E1 4NS
  364. -- 
  365. Send compilers articles to compilers@iecc.cambridge.ma.us or
  366. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  367.