CS4:COMP LN6 USEFUL SUPPORT ROUTINES You will need a selection of support routines and it is best if these are in a set of external routines linked with the rest of your compiler. It will help your schedule if you draft these routines over the Xmas vacation. Message Routines ---------------- You will need at least two message routines to output a warning and an error message. The text of error messages is often kept in a sophisticated packet format although a simple %const %string %array will suffice at a pinch. Your warning and error routines will need to substitute actual names or other test into the stored messages - probably using marker characters. ie. if there is a "#" in a message the second parameter is a number to be substituted. If there is a "%" then the second paramater is dictionary reference; extract the text of the name from the dictionary and insert it. Warnings are normally output to the listing only but errors go also to the error message stream so you will have to use the information provided by Compile. List Processing Package ----------------------- Algol in general has no limits - "fors" may be nested to any depths as may other constructs. The compiler must cope with the exceptional without penalising the simple by allocating vast areas which cause excessive paging. The solution is to allocate part of th workfile to a list processing area and hold the data in lists not arrays or records. You will probably want doubly linked lists:- ^ | _____________________________________ ! ! ! ! ! Data ! Blink ! Flink ! !_________________!_________!_______! | V If you use a %record %array for the list structure the links are subscripts not addresses and 2 16 bit fields are sufficient. The data field should be about four or five integers wide. A "list id" or head cell can be an integer where the top 16 bits indentify the bottom cell and the bottom 16 bits identify the top cell. One of the main purposes of this package is to hold details of names evicted from the dictionary by redeclaration in an inner block, you should keep this in mind when designing the package. The data should be provided or removed from the routines by %record %name parameters although record value and record function can also be used. Restricting everything to a single format (with alternatives) of record enables the package to be amended for longer or smaller data fields as the compiler develops. You will need at least the following:- INIT ASL to obtain space from the work file and map on the record array. Also formats the initial free list. NEWCELL, to obtain and return cells from the free RETURNCELL list. PUSH, POP, to push and pop cells from the top (bottom) BPUSH,BPOP of list. INSERTAFTER, to insert (remove) cells from the middle INSERTBEFORE, of a list. REMOVE FROMLIST, to obtain (replace) data from (in) a REPLACE cell without touching the linking. DISCARDLIST return a complete list to the free cells list. PRINTLIST, useful for debugging. CHECKLIST MORESPACE obtains more space from the workfile if possible - called when new cell finds no free cells. Register Allocation ------------------- Register allocation is vital to compiler performance, the routines need to be fast and sensible, minimising the dumping of registers. The need to use even/odd register pairs and the anomolous status of register GR0 all complicate the program. The routines operate on an array of register descriptor records from 0:19 for 16 general and 4 floating registers. Each descripter record will contain at least the fillowing fields:- STATUS May take the values:- free - nothing in the register used - has useful contents which don't need preserving on reuse. dumpable - the contents, ususlly an arithmetic result, must be dumped if the register is to be reused. locked - can not be dumped. USE/INF Details of the contents for register tracking. It is certainly worth tracking small constants and local scalars. COUNT The number of times the contents must be used before the register reverts to "free". ID The value to be inserted in an instruction - needed for FRs in particular. TRIPPTR A (record) pointer to the triple which generated this value. The search routines concentrate on funding the register that can be obtained at lowest cost - one might assign costs as follows. free - 0 used - 4 dumpable - 8 count locked - infinite It is advisable to increment the cost by a bit if the other member of the even-odd pair is free; this avoids clobbering pairs unnecessarily. It is also advisable to increase the cost if the result is due to be used in the current triple - this avoids an immediate reload. The search routines make a pass through the relevant routines assigning costs and exiting at once on zero cost. Otherwise the minimum cost register is selected and dumped as necessary. You will need the following:- claim gr0 Any general register 0-15. claim gr1 Any general register bar zero. claim fr Any floating register. claim gr pair Any even odd pair. claim safe gr Any Gr from 4-14 that is preserved across a call. reg used To decrement the use count and reset status when count reaches zero. free gr Restore a register to free status. forget gr Forget the use/inf fields of one (all) forget all registers. Needed when passing a user label etc. print regs For diagnostic purposes. dump reg To dump the contents - can't be coded yet. find use Look for a register with use/inf as specified. set use Set the use/inf fields without changing status. pre call Checks the registers not preserved at procedure call and dumps them as necessary. Work File Utilisation -------------------- Good paging performance depends on keeping data in the work file as compact as possible. Try to use it from both ends leaving a hole in the middle - either area can then expand. I use the following scheme. 1. Allocate list processing space in top 20%; format 1 page worth only. 2. Lexically scan into the bottom of the file and then parse building the tree on top of the scanned text. 3. If it parses O.K. move the tree to the bottom and copy the dictionary after it. Build the intermediate form on the back of the dictionary which will not expand further. 4. I then increase the list space and I-F tables as necessary until they meet. Small programs only ever access top page and bottom 1 or 2 pages of the file!