home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / compiler / 1290 < prev    next >
Encoding:
Text File  |  1992-07-30  |  3.6 KB  |  92 lines
  1. Newsgroups: comp.compilers
  2. Path: sparky!uunet!think.com!spdcc!iecc!compilers-sender
  3. From: boehm@parc.xerox.com (Hans Boehm)
  4. Subject: Re: Pros and cons of high-level intermediate languages
  5. Reply-To: boehm@parc.xerox.com (Hans Boehm)
  6. Organization: Xerox PARC
  7. Date: Thu, 30 Jul 1992 01:02:05 GMT
  8. Approved: compilers@iecc.cambridge.ma.us
  9. Message-ID: <92-07-111@comp.compilers>
  10. References: <92-07-064@comp.compilers> <92-07-089@comp.compilers>
  11. Keywords: translator, design
  12. Sender: compilers-sender@iecc.cambridge.ma.us
  13. Lines: 77
  14.  
  15. graham@maths.su.oz.au (Graham Matthews) writes:
  16.  
  17. >(Hans Boehm) writes:
  18. >>But the C standard does not guarantee that C compiler 
  19. >>optimizations are safe in the presence of such a collector. 
  20.  
  21. >I am not sure I understand what you are talking about here Hans.  As far
  22. >as I can see if the C code you produce is not safe in the presence of
  23. >garbage collection then you are generating incorrect C code. There is
  24. >nothing in C that makes it "garbage collection unsafe" even with a
  25. >non-conservative garbage collection.
  26.  
  27. Here's a quick example of the problem.  Assume a conservative garbage
  28. collector that finds automatic variables by scanning the stack a word at a
  29. time.  (Also assume that registers are found somehow, usually either by
  30. using _setjmp, or with assembly code.)  Assume further that I write a loop
  31. traversing a list made up of nodes:
  32.  
  33. struct a {
  34.     char junk[40000];
  35.     struct a * next;
  36. }
  37.  
  38. Assume further that this loop is the last access to any of the nodes in
  39. the list, and that x is the last pointer to anywhere in the list.
  40. Somewhere in the loop is the statement
  41.  
  42. x = x -> next;
  43.  
  44. On machines like the RS/6000 that allow 16 bit signed displacements in a
  45. load instruction, this is likely to be compiled as:
  46.  
  47. x += 65536;    (An "add immediate upper" instruction)
  48. x = x[-25536];  (This is intended as a byte displacement; not correct C)
  49.  
  50. If a garbage collection occurs between the two instructions, I'm sunk.
  51. (This can happen in the presence of signals or preemptive threads.  If I
  52. have neither, pretend there was an allocation call before this statement,
  53. and the compiler moved the first statement to before the function call.
  54. If x is a local register variable, this is otherwise legitimate.  There
  55. are other examples where it's easy to insert a function call at the
  56. inopportune point.)
  57.  
  58. Note that this is easily remedied by using a different register for the
  59. intermediate value.
  60.  
  61. The problem is that the C compiler is allowed to disguise local pointer
  62. variables any way it wants to, in the interest of optimization.  As far as
  63. it's concerned, the garbage collector is not a legitimate since it
  64. examine's its callers' stack frames.
  65.  
  66. There are ways to avoid this by explicitly recording values of local
  67. variables to be traced by the collector someplace else or by forcing the
  68. variables themselves into memory.  (Edelson and others have done work
  69. along these lines.)  But on modern machines, inhibiting register
  70. allocation of local variables is a major performance problem.
  71.  
  72. The problem can be fixed in current compilers of which I am aware by
  73. judicious insertion of code to keep variables live sufficiently long.  If
  74. LIVE(x) forces x to be live (in some cheap, probably compiler dependent
  75. way), then 
  76.  
  77. x = x -> next;
  78.  
  79. should be rewritten as (automatically one hopes)
  80.  
  81. x = x -> next; LIVE(x);
  82.  
  83. The reader can verify that this indeed works for the above example, under
  84. some reasonable assumptions about the compiler.  It does not suffice for
  85. an arbitrary ANSI compiler.  (Again, more details by email on request.)
  86.  
  87. Hans-J. Boehm
  88. (boehm@parc.xerox.com)
  89. -- 
  90. Send compilers articles to compilers@iecc.cambridge.ma.us or
  91. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  92.