home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / mitsch75.zip / scheme-7_5_17-src.zip / scheme-7.5.17 / src / compiler / documentation / TASKS < prev    next >
Text File  |  1993-10-29  |  10KB  |  235 lines
  1. -*-Text-*-
  2.  
  3. Task list for compiler.  The list is seperated into classes of
  4. decreasing priority.  Add new entries at the end of the appropriate
  5. class.
  6.  
  7. Each entry should start with an open/close bracket.  "Claim" a
  8. particular task by putting your uname in the brackets.  When the task
  9. is done, put DONE in the brackets.
  10.  
  11.  
  12. ---- Class 1 (required for release) ----
  13.  
  14. [DONE] Fix keyword bug in pattern matcher.
  15.  
  16. [DONE] Open code computed vector operations.
  17.  
  18. [DONE] Open code computed string, and bit-string operations.  (1-2
  19. days)
  20.  
  21. [DONE] Open code generic arithmetic.  (1 week)
  22.  
  23. [DONE] Open code flonum arithmetic.  (6 weeks)
  24.  
  25. [Partly done] Fix dataflow analyzer explosion on takr.
  26. Handled by compiling by procedures.  Not really taken care of, but
  27. solves the problem in practice.
  28.  
  29. [] Stack overflow checks.  
  30. This can be done accurately or heuristically:
  31. To do it accurately we must compute the maximum number of pushes for a
  32. procedure (not transitively) and (if not zero) check at entry whether
  33. that much space is available.
  34. To do it heuristically we only need to find those procedures that can
  35. call themselves (indirectly) in subproblem position and check whether
  36. we've exceeded the buffer at entry.  The other procedures will push an
  37. arbitrarily large, but finite amount.  Given a sufficiently large
  38. overpush buffer, the heuristic test should be sufficient.
  39.  
  40. [] New closure/trampoline implementation to alleviate cacheing
  41. problems:
  42.   Closures can be pre-allocated in chunks at HeapTop and growing
  43. towards Free.  The closures have fixed instructions to jump to a
  44. simple assembly language routine that grabs the real entry point from
  45. the closure and invokes it through a register.  In this way the
  46. instructions are never modified and the cache need only be flushed
  47. rarely.  For example, the pre-allocated closures at the top of memory
  48. would look like
  49.  
  50. <header>
  51. jsr n(a6)
  52. <entry point of code>
  53. <pointer to closure's variable area>
  54.  
  55. and n(a6) would be
  56.  
  57. mov.l    (sp),a0
  58. subq.l    &4,(sp)        ; bump back to closure
  59. ori.b    &tc_compiled_entry,(sp)
  60. mov.l    (a0),a0        ; get real entry point
  61. jmp    (a0)        ; go to closure
  62.  
  63.  
  64. ---- Class 2 (highly desirable or good cost/payoff ratio) ----
  65.  
  66. [DONE] Reorder arguments in tail recursive calls and push the minimum
  67. number of temporaries.  (3 weeks)
  68.  
  69. [] Reduce the number of interrupt checks and move them to continuation
  70. invocation rather than continuation entry.  The call graph is already
  71. computed.  There is no need for an entry gc check if the procedure
  72. does not call itself.  There is no need for a continuation check if
  73. the continuation cannot ultimately return to itself.  We may want to
  74. add gc checks anyway if we are consing more than a small fixed amount.
  75. A different problem is determining when to gc check in the middle of a
  76. basic block.  AAB's code probably generates humongous basic blocks
  77. which may require interruptability. (3 weeks)
  78.  
  79. [DONE] Self consistent closing.  This includes dropping parent frame
  80. for open externals (and maybe static links) when the procedure does
  81. not need them.  Effective closures.  (3 weeks)
  82.  
  83. [Partly done] Open code compiler apply.  (3 days)
  84. The 68K version has quick handlers for common arities.
  85.  
  86. [] Open code or provide special handlers for common "unsafe"
  87. primitives such as apply, force, eval, with-interrupt-mask, etc.  (3
  88. days)
  89.  
  90. [DONE] Teach the uuo linker about entities so it can do a direct jump. (3
  91. days).
  92.  
  93. [] Speed up some bit string operations.  (3 days?)
  94.  
  95. [] Cache compatible compiled versions of procedures in loops, and
  96. invoke them cheaply, using a computed jump.  (Use declarations, 1
  97. week.)
  98.  
  99. [] Optimize I/O procedures (e.g. read, write) by supplying correct
  100. default port argument.  Perhaps call lower-level operation which does
  101. no defaulting.  (3 days)
  102.  
  103.  
  104. ---- Class 3 (less desirable but cheap) ----
  105.  
  106. [] Better linearization in loops.  (3-4 days)
  107.  
  108. [OBSOLETE] Make top level (constant) definitions be handled by the
  109. linker to eliminate code space.  (2 weeks?)  Compilation by procedures
  110. obsoletes this.  The top level code, which performs the definitions,
  111. is not purified, so it is GCd.
  112.  
  113. [] Assignments should do better.  No need to cellify if the variable
  114. is never closed over either by a procedure or by a continuation.
  115. Currently we can easily tell the procedure story, but can't tell the
  116. continuation story since the closing analysis is asymmetric.  Maybe do
  117. the analysis on continuations as well only for this job.  Lvalues
  118. already have a field to determine whether they are "closed over".  We
  119. may need a notion of a continuation "ultimately exported".  (10 days)
  120.  
  121. [] Add an fg optimization phase that reduces the strength of the
  122. continuation types: After simapp and outer previously unknown-type
  123. continuations may have known types and some of the work can be avoided
  124. if the type is effect or predicate.  (2 weeks)
  125.  
  126. [] Better code generation for many cases of computed jump: Many of
  127. them turn into
  128.     <test>
  129.     pea    entry
  130.     move.b    &tc_entry,(sp)
  131.     bra    merge
  132.     ...  merge
  133.     clr.b    (sp)
  134.     rts
  135.  
  136. which can obviously be improved to
  137.     
  138.     <test>
  139.     bra    entry
  140.  
  141. and merge may not be necessary at all.  (1 week)
  142.  
  143. [DONE] Teach the UUO linker about primitives.  In this way, users who
  144. don't know about declarations may get a little better performance when
  145. their code references CAR (etc) freely.  This requires making "unsafe"
  146. primitives back out correctly when invoked from compiled code.  1 week.
  147.  
  148.  
  149. ---- Class 4 (expensive or long term) ----
  150.  
  151. [] Register variables in tight loops.  (summer)
  152.  
  153. [] Loop unrolling in tight loops.  (2 weeks)
  154.  
  155. [] Remove type codes from continuation via microcode stack parser.  A
  156. different possibility is to have a hybrid high/low tag approach where
  157. fixnums and compiled entries differ only in the low tags.  Through
  158. alignment constraints the code could always be tagged automatically.
  159. (summer)
  160.  
  161. [] Redo the variable cache stuff to avoid or simplify trap tests.
  162. Right now the main obstacle to this is "unassigned".  Assignments
  163. could become expensive (because unassigning a variable would be
  164. expensive), or we could make assignment never be able to unassign a
  165. variable.  (3 weeks)
  166.  
  167. [DONE] Improve optional arguments by bypassing apply in some cases where
  168. the frame needs to be reformatted by inserting optionals.  (3 days)
  169.  
  170. [DONE] Rewrite the back end.  Currently it behaves quadratically on the
  171. length of the input.  It should be linear!  (4 weeks)
  172. It was a bug in the symbol table stuff by which many labels hashed to
  173. the same bucket and searches became linear rather than constant time.
  174.  
  175. [DONE] Multi closing: Divide closures into non-overlapping sets which can
  176. share the structure of the closure.  In many cases, procedures are
  177. closed by contagion, and their free variables could be added to the
  178. closure who caused them to be closed.  Many of these don't even need
  179. code pointers.  (6 weeks)
  180.  
  181. [] Write a recognizer for downward funargs and for cps-like code to
  182. avoid closing non passed-out procedures passed as arguments.  This
  183. would make cps-style multiple values generate pretty good code.  (6
  184. weeks)
  185.  
  186. [] Improve the closure analyzer to close less often for compatibility:
  187. if all the possible operators have their closing limits in a linear
  188. chain, we can always leave all the stuff around that the innermost
  189. possible operator needs, and dynamically pop the appropriate amount of
  190. stuff if the operator is not the innermost one.  (4 weeks)
  191.  
  192.  
  193. ---- Class 5 (very long term) ----
  194.  
  195. [DONE] Side effect analysis.  Remove extraneous calls.
  196.  
  197. [DONE] Value analysis.  Remove busy noops (cdr-loops, etc).
  198.  
  199. [] Make a triviality analyzer that tells the code generator to inline
  200. code simple procedures even if used in more than one place.  As a
  201. special case of this, add a piece of code that decides when eta
  202. conversion is beneficial and propagates the results through the value
  203. graph.  This is important for some versions of the Y operator.  { A
  204. very simple version of this already done in the value analysis. }
  205.  
  206. [] Reverse the order of arguments on the stack.  In this way
  207. listifying and defaulting optionals becomes much simpler since there
  208. is never a need to open a gap.
  209.  
  210. [OBSOLETE] Write a static linker which when given multiple code
  211. objects to be loaded in the same environment, produces a new code
  212. object to be loaded in that environment but in which all
  213. cross-references have been linked.  This needs definitions to be
  214. written in a "parseable" format.  If an option that would produce code
  215. for creation of the environment and initialization of the program was
  216. provided, and the runtime system was restructured into a library from
  217. which the linker could selectively link, the compiler would become
  218. stand-alone.  (summer) 
  219.     There is a better way to get a stand-alone compiler, with no
  220. changes to the compiler!  A modified fasload can be written that
  221. `nulls' the environment object from compiled code blocks and the cache
  222. lists kept around for incremental definition.  The dumped code will
  223. only have those procedures needed (or modules needed if not compiled
  224. by procedures), and will not share environment structure with the
  225. load-time environment.  The primitives referenced by the code will be
  226. the only ones needed for the stand-alone version.
  227.  
  228.  
  229. ---- Class 6 (idle thoughts) ----
  230.  
  231. [] When handling disjunctions in the front end, if the predicate
  232. expression is something known to return a boolean value (such as
  233. `eq?'), then there is no need to generate a variable to hold the
  234. value.
  235.