home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / arch / 12023 < prev    next >
Encoding:
Text File  |  1993-01-01  |  2.2 KB  |  55 lines
  1. Newsgroups: comp.arch
  2. Path: sparky!uunet!newsgate.watson.ibm.com!yktnews!admin!yktnews!prener
  3. From: prener@watson.ibm.com (Dan Prener)
  4. Subject: Re: No Last Call Optimization on Sparc and DECstation
  5. Sender: news@watson.ibm.com (NNTP News Poster)
  6. Message-ID: <PRENER.93Jan1202639@prener.watson.ibm.com>
  7. In-Reply-To: bmtong@cs.cuhk.hk's message of Wed, 30 Dec 1992 09:43:52 GMT
  8. Date: Sat, 2 Jan 1993 01:26:39 GMT
  9. Disclaimer: This posting represents the poster's views, not necessarily those of IBM
  10. References: <1992Dec30.094352.4243@cucs5.cs.cuhk.hk>
  11. Nntp-Posting-Host: prener.watson.ibm.com
  12. Organization: IBM T.J. Watson Research Center, Hawthorne, New York
  13. Lines: 40
  14.  
  15. In article <1992Dec30.094352.4243@cucs5.cs.cuhk.hk> bmtong@cs.cuhk.hk (Tong Bo-Ming) writes:
  16.  
  17. > In the field of Logic Programming, we have a kind of optimization
  18. > technique called the Last Call Optimization.  The idea is simple.
  19.  
  20. >     p(a,b,c)
  21. >     {    x(a);
  22. >         y(b);
  23. >         z(c);
  24. >     }
  25.  
  26. > In the above procedure, we may discard the current stack frame (or reg
  27. > window in Sparc) before calling z.  We then replace the call z
  28. > instruction by a jump instruction.
  29.  
  30. >     p(a)
  31. >     {    x(a);
  32. >     }
  33.  
  34. > In the above kind of procedure where there is only one call, no stack
  35. > frame is necessary.  It can be optimized as if it were a leaf procedure.
  36.  
  37. > It is a sad thing to notice that such a nice optimization is not
  38. > implemented in languages other than Prolog and on RISC architectures.
  39.  
  40. IBM's compilers for the RS/6000 do this, when possible.  There are a few
  41. things one must watch out for.  The linkage conventions of the RS/6000
  42. dictate that a procedure that must save and restore registers does so
  43. using a save area in the caller's stack frame.  That means that, in your
  44. second example, one cannot always regard p() as a leaf procedure unless
  45. x() is a leaf procedure.  The differences between the conventional linkage
  46. semantics of C and FORTRAN (multiple procedures in a FORTRAN 77 file are
  47. regarded as if they came from multiple files, i.e., some may be replaced
  48. at link time) mean, in practice, that this optimization can be done in
  49. C but not in FORTRAN.
  50.  
  51. And, of course, this optimization eliminates tail recursion as an instance
  52. of the more general phenomenon.
  53. --
  54.                                    Dan Prener (prener@watson.ibm.com)
  55.