il5 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446
  1. .NH 2
  2. Implementation
  3. .PP
  4. A major factor in the implementation
  5. of Inline Substitution is the requirement
  6. not to use an excessive amount of memory.
  7. IL essentially analyzes the entire program;
  8. it makes decisions based on which procedure calls
  9. appear in the whole program.
  10. Yet, because of the memory restriction, it is
  11. not feasible to read the entire program
  12. in main memory.
  13. To solve this problem, the IL phase has been
  14. split up into three subphases that are executed sequentially:
  15. .IP 1.
  16. analyze every procedure; see how it accesses its parameters;
  17. simultaneously collect all calls
  18. appearing in the whole program an put them
  19. in a \fIcall-list\fR.
  20. .IP 2.
  21. use the call-list and decide which calls will be substituted
  22. in line.
  23. .IP 3.
  24. take the decisions of subphase 2 and modify the
  25. program accordingly.
  26. .LP
  27. Subphases 1 and 3 scan the input program; only
  28. subphase 3 modifies it.
  29. It is essential that the decisions can be made
  30. in subphase 2
  31. without using the input program,
  32. provided that subphase 1 puts enough information
  33. in the call-list.
  34. Subphase 2 keeps the entire call-list in main memory
  35. and repeatedly scans it, to
  36. find the next best candidate for expansion.
  37. .PP
  38. We will specify the
  39. data structures used by IL before
  40. describing the subphases.
  41. .NH 3
  42. Data structures
  43. .NH 4
  44. The procedure table
  45. .PP
  46. In subphase 1 information is gathered about every procedure
  47. and added to the procedure table.
  48. This information is used by the heuristic rules.
  49. A proctable entry for procedure p has
  50. the following extra information:
  51. .IP -
  52. is it allowed to substitute an invocation of p in line?
  53. .IP -
  54. is it allowed to put any parameter of such a call in line?
  55. .IP -
  56. the size of p (number of EM instructions)
  57. .IP -
  58. does p 'fall through'?
  59. .IP -
  60. a description of the formal parameters that p accesses; this information
  61. is obtained by looking at the code of p. For every parameter f,
  62. we record:
  63. .RS
  64. .IP -
  65. the offset of f
  66. .IP -
  67. the type of f (word, double word, pointer)
  68. .IP -
  69. may the corresponding actual parameter be put in line?
  70. .IP -
  71. is f ever accessed indirectly?
  72. .IP -
  73. if f used: never, once or more than once?
  74. .RE
  75. .IP -
  76. the number of times p is called (see below)
  77. .IP -
  78. the file address of its call-count information (see below).
  79. .LP
  80. .NH 4
  81. Call-count information
  82. .PP
  83. As a result of Inline Substitution, some procedures may
  84. become useless, because all their invocations have been
  85. substituted in line.
  86. One of the tasks of IL is to keep track which
  87. procedures are no longer called.
  88. Note that IL is especially keen on procedures that are
  89. called only once
  90. (possibly as a result of expanding all other calls to it).
  91. So we want to know how many times a procedure
  92. is called \fIduring\fR Inline Substitution.
  93. It is not good enough to compute this
  94. information afterwards.
  95. The task is rather complex, because
  96. the number of times a procedure is called
  97. varies during the entire process:
  98. .IP 1.
  99. If a call to p is substituted in line,
  100. the number of calls to p gets decremented by 1.
  101. .IP 2.
  102. If a call to p is substituted in line,
  103. and p contains n calls to q, then the number of calls to q
  104. gets incremented by n.
  105. .IP 3.
  106. If a procedure p is removed (because it is no
  107. longer called) and p contains n calls to q,
  108. then the number of calls to q gets decremented by n.
  109. .LP
  110. (Note that p may be the same as q, if p is recursive).
  111. .sp 0
  112. So we actually want to have the following information:
  113. .DS
  114. NRCALL(p,q) = number of call to q appearing in p,
  115. for all procedures p and q that may be put in line.
  116. .DE
  117. This information, called \fIcall-count information\fR is
  118. computed by the first subphase.
  119. It is stored in a file.
  120. It is represented as a number of lists, rather than as
  121. a (very sparse) matrix.
  122. Every procedure has a list of (proc,count) pairs,
  123. telling which procedures it calls, and how many times.
  124. The file address of its call-count list is stored
  125. in its proctable entry.
  126. Whenever this information is needed, it is fetched from
  127. the file, using direct access.
  128. The proctable entry also contains the number of times
  129. a procedure is called, at any moment.
  130. .NH 4
  131. The call-list
  132. .PP
  133. The call-list is the major data structure use by IL.
  134. Every item of the list describes one procedure call.
  135. It contains the following attributes:
  136. .IP -
  137. the calling procedure (caller)
  138. .IP -
  139. the called procedure (callee)
  140. .IP -
  141. identification of the CAL instruction (sequence number)
  142. .IP -
  143. the loop nesting level; our heuristic rules appreciate
  144. calls inside a loop (or even inside a loop nested inside
  145. another loop, etc.) more than other calls
  146. .IP -
  147. the actual parameter expressions involved in the call;
  148. for every actual, we record:
  149. .RS
  150. .IP -
  151. the EM code of the expression
  152. .IP -
  153. the number of bytes of its result (size)
  154. .IP -
  155. an indication if the actual may be put in line
  156. .RE
  157. .LP
  158. The structure of the call-list is rather complex.
  159. Whenever a call is expanded in line, new calls
  160. will suddenly appear in the program,
  161. that were not contained in the original body
  162. of the calling subroutine.
  163. These calls are inherited from the called procedure.
  164. We will refer to these invocations as \fInested calls\fR
  165. (see Fig. 5.1).
  166. .DS
  167. .TS
  168. lw(2.5i) l.
  169. procedure p is
  170. begin .
  171. a(); .
  172. b(); .
  173. end;
  174. .TE
  175. .TS
  176. lw(2.5i) l.
  177. procedure r is procedure r is
  178. begin begin
  179. x(); x();
  180. p(); -- in line a(); -- nested call
  181. y(); b(); -- nested call
  182. end; y();
  183. end;
  184. .TE
  185. Fig. 5.1 Example of nested procedure calls
  186. .DE
  187. Nested calls may subsequently be put in line too
  188. (probably resulting in a yet deeper nesting level, etc.).
  189. So the call-list does not always reflect the source program,
  190. but changes dynamically, as decisions are made.
  191. If a call to p is expanded, all calls appearing in p
  192. will be added to the call-list.
  193. .sp 0
  194. A convenient and elegant way to represent
  195. the call-list is to use a LISP-like list.
  196. .[
  197. poel lisp trac
  198. .]
  199. Calls that appear at the same level
  200. are linked in the CDR direction. If a call C
  201. to a procedure p is expanded,
  202. all calls appearing in p are put in a sub-list
  203. of C, i.e. in its CAR.
  204. In the example above, before the decision
  205. to expand the call to p is made, the
  206. call-list of procedure r looks like:
  207. .DS
  208. (call-to-x, call-to-p, call-to-y)
  209. .DE
  210. After the decision, it looks like:
  211. .DS
  212. (call-to-x, (call-to-p*, call-to-a, call-to-b), call-to-y)
  213. .DE
  214. The call to p is marked, because it has been
  215. substituted.
  216. Whenever IL wants to traverse the call-list of some procedure,
  217. it uses the well-known LISP technique of
  218. recursion in the CAR direction and
  219. iteration in the CDR direction
  220. (see page 1.19-2 of
  221. .[
  222. poel lisp trac
  223. .]
  224. ).
  225. All list traversals look like:
  226. .DS
  227. traverse(list)
  228. {
  229. for (c = first(list); c != 0; c = CDR(c)) {
  230. if (c is marked) {
  231. traverse(CAR(c));
  232. } else {
  233. do something with c
  234. }
  235. }
  236. }
  237. .DE
  238. The entire call-list consists of a number of LISP-like lists,
  239. one for every procedure.
  240. The proctable entry of a procedure contains a pointer
  241. to the beginning of the list.
  242. .NH 3
  243. The first subphase: procedure analysis
  244. .PP
  245. The tasks of the first subphase are to determine
  246. several attributes of every procedure
  247. and to construct the basic call-list,
  248. i.e. without nested calls.
  249. The size of a procedure is determined
  250. by simply counting its EM instructions.
  251. Pseudo instructions are skipped.
  252. A procedure does not 'fall through' if its CFG
  253. contains a basic block
  254. that is not the last block of the CFG and
  255. that ends on a RET instruction.
  256. The formal parameters of a procedure are determined
  257. by inspection of
  258. its code.
  259. .PP
  260. The call-list in constructed by looking at all CAL instructions
  261. appearing in the program.
  262. The call-list should only contain calls to procedures
  263. that may be put in line.
  264. This fact is only known if the procedure was
  265. analyzed earlier.
  266. If a call to a procedure p appears in the program
  267. before the body of p,
  268. the call will always be put in the call-list.
  269. If p is later found to be unsuitable,
  270. the call will be removed from the list by the
  271. second subphase.
  272. .PP
  273. An important issue is the recognition
  274. of the actual parameter expressions of the call.
  275. The front ends produces messages telling how many
  276. bytes of formal parameters every procedure accesses.
  277. (If there is no such message for a procedure, it
  278. cannot be put in line).
  279. The actual parameters together must account for
  280. the same number of bytes.A recursive descent parser is used
  281. to parse side-effect free EM expressions.
  282. It uses a table and some
  283. auxiliary routines to determine
  284. how many bytes every EM instruction pops from the stack
  285. and how many bytes it pushes onto the stack.
  286. These numbers depend on the EM instruction, its argument,
  287. and the wordsize and pointersize of the target machine.
  288. Initially, the parser has to recognize the
  289. number of bytes specified in the formals-message,
  290. say N.
  291. Assume the first instruction before the CAL pops S bytes
  292. and pushes R bytes.
  293. If R > N, too many bytes are recognized
  294. and the parser fails.
  295. Else, it calls itself recursively to recognize the
  296. S bytes used as operand of the instruction.
  297. If it succeeds in doing so, it continues with the next instruction,
  298. i.e. the first instruction before the code recognized by
  299. the recursive call, to recognize N-R more bytes.
  300. The result is a number of EM instructions that collectively push N bytes.
  301. If an instruction is come across that has side-effects
  302. (e.g. a store or a procedure call) or of which R and S cannot
  303. be computed statically (e.g. a LOS), it fails.
  304. .sp 0
  305. Note that the parser traverses the code backwards.
  306. As EM code is essentially postfix code, the parser works top down.
  307. .PP
  308. If the parser fails to recognize the parameters, the call will not
  309. be substituted in line.
  310. If the parameters can be determined, they still have to
  311. match the formal parameters of the called procedure.
  312. This check is performed by the second subphase; it cannot be
  313. done here, because it is possible that the called
  314. procedure has not been analyzed yet.
  315. .PP
  316. The entire call-list is written to a file,
  317. to be processed by the second subphase.
  318. .NH 3
  319. The second subphase: making decisions
  320. .PP
  321. The task of the second subphase is quite easy
  322. to understand.
  323. It reads the call-list file,
  324. builds an incore call-list and deletes every
  325. call that may not be expanded in line (either because the called
  326. procedure may not be put in line, or because the actual parameters
  327. of the call do not match the formal parameters of the called procedure).
  328. It assigns a \fIpay-off\fR to every call,
  329. indicating how desirable it is to expand it.
  330. .PP
  331. The subphase repeatedly scans the call-list and takes
  332. the call with the highest ratio.
  333. The chosen one gets marked,
  334. and the call-list is extended with the nested calls,
  335. as described above.
  336. These nested calls are also assigned a ratio,
  337. and will be considered too during the next scans.
  338. .sp 0
  339. After every decision the number of times
  340. every procedure is called is updated, using
  341. the call-count information.
  342. Meanwhile, the subphase keeps track of the amount of space left
  343. available.
  344. If all space is used, or if there are no more calls left to
  345. be expanded, it exits this loop.
  346. Finally, calls to procedures that are called only
  347. once are also chosen.
  348. .PP
  349. The actual parameters of a call are only needed by
  350. this subphase to assign a ratio to a call.
  351. To save some space, these actuals are not kept in main memory.
  352. They are removed after the call has been read and a ratio
  353. has been assigned to it.
  354. So this subphase works with \fIabstracts\fR of calls.
  355. After all work has been done,
  356. the actual parameters of the chosen calls are retrieved
  357. from a file,
  358. as they are needed by the transformation subphase.
  359. .NH 3
  360. The third subphase: doing transformations
  361. .PP
  362. The third subphase makes the actual modifications to
  363. the EM text.
  364. It is directed by the decisions made in the previous subphase,
  365. as expressed via the call-list.
  366. The call-list read by this subphase contains
  367. only calls that were selected for expansion.
  368. The list is ordered in the same way as the EM text,
  369. i.e. if a call C1 appears before a call C2 in the call-list,
  370. C1 also appears before C2 in the EM text.
  371. So the EM text is traversed linearly,
  372. the calls that have to be substituted are determined
  373. and the modifications are made.
  374. If a procedure is come across that is no longer needed,
  375. it is simply not written to the output EM file.
  376. The substitution of a call takes place in distinct steps:
  377. .IP "change the calling sequence" 7
  378. .sp 0
  379. The actual parameter expressions are changed.
  380. Parameters that are put in line are removed.
  381. All remaining ones must store their result in a
  382. temporary local variable, rather than
  383. push it on the stack.
  384. The CAL instruction and any ASP (to pop actual parameters)
  385. or LFR (to fetch the result of a function)
  386. are deleted.
  387. .IP "fetch the text of the called procedure"
  388. .sp 0
  389. Direct disk access is used to to read the text of the
  390. called procedure.
  391. The file offset is obtained from the proctable entry.
  392. .IP "allocate bytes for locals and temporaries"
  393. .sp 0
  394. The local variables of the called procedure will be put in the
  395. stack frame of the calling procedure.
  396. The same applies to any temporary variables
  397. that hold the result of parameters
  398. that were not put in line.
  399. The proctable entry of the caller is updated.
  400. .IP "put a label after the CAL"
  401. .sp 0
  402. If the called procedure contains a RET (return) instruction
  403. somewhere in the middle of its text (i.e. it does
  404. not fall through), the RET must be changed into
  405. a BRA (branch), to jump over the
  406. remainder of the text.
  407. This label is not needed if the called
  408. procedure falls through.
  409. .IP "copy the text of the called procedure and modify it"
  410. .sp 0
  411. References to local variables of the called routine
  412. and to parameters that are not put in line
  413. are changed to refer to the
  414. new local of the caller.
  415. References to in line parameters are replaced
  416. by the actual parameter expression.
  417. Returns (RETs) are either deleted or
  418. replaced by a BRA.
  419. Messages containing information about local
  420. variables or parameters are changed.
  421. Global data declarations and the PRO and END pseudos
  422. are removed.
  423. Instruction labels and references to them are
  424. changed to make sure they do not have the
  425. same identifying number as
  426. labels in the calling procedure.
  427. .IP "insert the modified text"
  428. .sp 0
  429. The pseudos of the called procedure are put after the pseudos
  430. of the calling procedure.
  431. The real text of the callee is put at
  432. the place where the CAL was.
  433. .IP "take care of nested substitutions"
  434. .sp 0
  435. The expanded procedure may contain calls that
  436. have to be expanded too (nested calls).
  437. If the descriptor of this call contains actual
  438. parameter expressions,
  439. the code of the expressions has to be changed
  440. the same way as the code of the callee was changed.
  441. Next, the entire process of finding CALs and doing
  442. the substitutions is repeated recursively.
  443. .LP