Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

The portability of BCPL to the MC68000 via the intermediate language SLIM Ranger, Eric Alfrey 1982

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

Item Metadata

Download

Media
831-UBC_1982_A6_7 R36.pdf [ 2.78MB ]
Metadata
JSON: 831-1.0051818.json
JSON-LD: 831-1.0051818-ld.json
RDF/XML (Pretty): 831-1.0051818-rdf.xml
RDF/JSON: 831-1.0051818-rdf.json
Turtle: 831-1.0051818-turtle.txt
N-Triples: 831-1.0051818-rdf-ntriples.txt
Original Record: 831-1.0051818-source.json
Full Text
831-1.0051818-fulltext.txt
Citation
831-1.0051818.ris

Full Text

THE PORTABILITY OF BCPL TO THE MC68000 VIA THE INTERMEDIATE LANGUAGE SLIM by ERIC ALFREY THIRD RANGER B.Sc, The University of B r i t i s h Columbia, 1980 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in THE FACULTY OF GRADUATE STUDIES THE DEPARTMENT OF COMPUTER SCIENCE We accept t h i s thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA A p r i l 1982 1982 In presenting t h i s thesis i n p a r t i a l f u l f i l m e n t of the requirements for an advanced degree at the University of B r i t i s h Columbia, I agree that the Library s h a l l make i t f r e e l y available for reference and study. I further agree that permission for extensive copying of t h i s thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. I t i s understood that copying or publication of t h i s thesis for f i n a n c i a l gain s h a l l not be allowed without my written permission. Department of Computer S c i e n c e The University of B r i t i s h Columbia 1956 Main Mall Vancouver, Canada V6T 1Y3 D a t e ?7 April 19R? DE-6 (3/81) i i A b s t r a c t T h i s t h e s i s d e s c r i b e s t h e d e s i g n o f a s y s t e m t h a t c o n v e r t s t h e i n t e r m e d i a t e l a n g u a g e SLIM, i n t o a s s e m b l e r code f o r t h e M o t o r o l a MC68000. T h i s i s t h e n a s s e m b l e d and l o a d e d o n t o a MC68000 s i m u l a t o r where i t s u c c e s s f u l l y r u n s . The s u i t a b i l i t y o f SLIM as an i n t e r m e d i a t e l a n g u a g e i s a l s o s t u d i e d , w i t h a t r e a t m e n t on code o p t i m i z a t i o n . i i i Table of Contents Abstract i i Table of Contents i i i L i s t of Figures v Acknowledgements v i 1 . Introduction 1 1.1 Area of research 1 1.2 Summary of work 4 2. SLIM and the MC68000 6 2.1 The SLIM Machine 6 2.1.1 The Registers 7 2.1.2 The Modifiers 8 2.1.3 A Summary of the Operations . . . . . . . . 1 1 2.2 The Motorola MC68000 . . 13 2.2.1 The Registers 13 2.2.2 The Addressing Schemes 14 2.3 Is the MC68000 suitable for SLIM? 16 3. The Mapping of SLIM to the MC68000 19 3.1 The Instruction Mappings 19 3.1.1 Loading and Storing 19 3.1.2 Sequencing 23 3.1.3 The Arithmetic and Logical Operations . . 29 3.1.4 The Miscellaneous Instructions 33 3.1.5 Pseudo Directives 34 3.2 Mapping Problems 35 3.3 Optimizations 38 3.4 The Runtime Support 40 i v 4. E v a l u t a t i o n 42 5. C o n c l u s i o n s and F u r t h e r R e s e a r c h 48 B i b l i o g r a p h y 52 I . The S o f t w a r e 54 I I . P r i n t Out H i 56 I I I . Towers of H a n o i 58 IV. The SLIM P a r s e r 60 V. O p t i m i z i n g Example 63 V I . The CALL R o u t i n e 66 V L i s t of Figures Figure 1. The SLIM Instructions . . .. . 12 Figure 2. The C a l l i n g Mechanism 25 v i Acknowledgements I would l i k e to thank the department of Computer Science for i t s support on t h i s project. This extends p a r t i c u l a r l y to my supervisor John Peck, for his summer research position that got me started, and his unending support throughout. I also thank Harvey Abramson for reading this thesis, and for the BCPL version of the C a l l , upon which this implementation is based. For the time I spent outside of the university, I thank Deborah. Her support saw me through the writing of t h i s thesi s. 1 Chapter 1 Introduct ion The purpose of t h i s endeavour i s to study the f e a s i b i l i t y of transporting the language BCPL to the Motorola MC68000 computer. This i s to be accomplished through the intermediate language c a l l e d SLIM, the assembly language for an ideal computer. This allows a look at the concept of intermediate languages and their usefulness in the task of transporting languages. It s p e c i f i c a l l y looks at the question of the use of SLIM for this purpose, as SLIM has been designed as an ideal computer for compiling BCPL programs into. BCPL was chosen as i t i s a t y p i c a l language in the f i e l d of computer science today. It is used for writing system software and user programs (Richards 69). 1.1 Area of research The f i e l d in question deals with the idea of transporting languages to di f f e r e n t computers by the use of an intermediate language. The use of an intermediate language gives the compiler writer greater freedom in code generation. This i s because of the fact that there is one common standard, the intermediate language. 2 When a compiler writer i s faced with the problem of code generation, there are two main options available to him. F i r s t , he may generate code that i s highly dependent on the part i c u l a r computer that he i s using. Secondly, he may generate code that i s for some ideal computer, and then worry about the s p e c i f i c problem of his actual computer. Intermediate languages are also used in the area of transporting languages. Given a group of researchers on d i f f e r i n g systems, three options are available for transferring programs. The usual method i s to transport programs at the source l e v e l . This i s simple, fast, and guarantees that the program w i l l work, assuming that the code has nothing that is machine dependent. The main problem i s , what happens i f researcher one has language X, and researcher two has language Y? This means that the code w i l l have to be rewritten from X to Y. This can induce errors; for example, the o r i g i n a l program may involve coding techniques that are unsupported in the second language. The second method is the use of cross assemblers or cross compilers. This i s having a program that translates the assembler language of machine X into that of machine Y. But again there are problems. The biggest i s the overhead in writing these programs in the f i r s t place. There must be changes made at a l l of the i n s t a l l a t i o n s i f one of them 3 changes. Also there i s a serious problem in the area of detecting bad translations. If my translation works in a l l but the case of the largest negative number, for example, I may never find t h i s situation except after many runs of the program. The last route that has been taken, is to define an intermediate language. This i s usually the assembler language for some simple computer. The idea is that i f I have t h i s simple computer as hardware, then I can run any code that you send me in i t s assembly language. This can be accomplished by writing a cross assembler, or translator, that assembles this language into your native computer's assembler, or d i r e c t l y to code. The fact that I now have only one translation to worry about at my i n s t a l l a t i o n has cut down the amount of code I must maintain, and i t makes testing of the translation easier and safer. When I wish to transfer code to another i n s t a l l a t i o n , I only have to generate i t for this intermediate assembler, move the source, and know that the code i s correct for any of the systems. 4 1.2 Summary of work The work that has been done can be summarized as follows: -translate a BCPL program into SLIM, -translate SLIM into Motorola MC68000 assembly code, -assemble the code producing a Motorola S-module, -load the S-module into a Motorola MC68000 simulator. BCPL can be examined in several of the references. For an introduction, see "BCPL - The Language And Its Compiler" by Richards and Whitby-Strevens. SLIM and the Motorola MC68000 w i l l both be discussed in the next chapter. The Motorola was chosen to be looked at as i t is a t y p i c a l modern micro computer, with a large set of instructions for use. The translation of BCPL into SLIM i s provided as one of the optional codes produced by the MTS/BCPL SLIM compiler.. The MC68000 assembler and simulator are programs supplied by Motorola for developmental work. The area that I am involved in is the translation of SLIM into the Motorola assembler. This e n t a i l s several areas that have to be looked at. F i r s t l y , is SLIM simple enough to be e a s i l y moved to a real computer? Secondly, is the MC68000 powerful enough to implement SLIM with any degree of e f f i c i e n c y ? And t h i r d l y , what mapping is necessary to equate the two computers? 5 The t a s k i s c o m p l i c a t e d by t h e f a c t t h a t t h e M o t o r o l a s o f t w a r e i s w r i t t e n f o r an IBM-360. T h i s i s a c c e p t a b l e a s UBC r u n s an Ahmdal-470, a 360 l o o k - a l i k e , b u t UBC a l s o has an a c c o u n t i n g s y s t e m where e v e r y a c c o u n t i s b u d g e t e d . The M o t o r o l a s o f t w a r e i s e x t r e m e l y e x p e n s i v e t o r u n , and b u d g e t i n g has been f o u n d t o be t h e b i g g e s t p r o b l e m . T h e r e f o r e , i t was d e c i d e d t h a t t h e d e v e l o p m e n t a l work would be done on a TI-990 c o m p u t e r , and once r u n n i n g , c r e a t e t h e f i n a l v e r s i o n on t h e 470. The TI s y s t e m s u p p o r t s z e d , a l a n g u a g e t h a t r e s e m b l e s C ( C h e r i t o n & S t e e v e s 7 9 ) . The t r a n s l a t o r was w r i t t e n and debugged i n t h i s , t h e n i t was t r a n s l a t e d i n t o a BCPL v e r s i o n f o r MTS. The s a v i n g s t a k e n by t h i s method, made t h e d i f f e r e n c e between g e t t i n g t h e i m p l e m e n t a t i o n w o r k i n g o r n o t . T h e r e c a n be a s t r o n g c a s e made f o r not u s i n g s i m u l a t o r s , but r a t h e r t h e r e a l h a r d w a r e . C h a p t e r 2 SLIM and t h e MC68000 6 T h i s c h a p t e r has two p u r p o s e s . I t i s . t o g i v e a d e s c r i p t i o n of t h e SLIM and MC68000 c o m p u t e r s . I t i s t h e n t o show t h a t a mapping o f SLIM t o MC68000 i s f e a s i b l e . I t s h o u l d be n o t e d t h a t t h e mapping i s r e l a t i v e l y s i m p l e and s t r a i g h t f o r w a r d . T h e r e a r e , however, two major p r o b l e m s p r e s e n t . The f i r s t o c c u r s i n r e s o l v i n g t h e BCPL c e l l v e r s u s t h e M o t o r o l a word a d d r e s s i n g schemes, whereby, M o t o r o l a means t h a t a word a d d r e s s must be a 16 b i t r e f e r e n c e , o c c u r r i n g on an even a d d r e s s b o u n d a r y . The o t h e r i s t h a t o f r e s o l v i n g SLIM's upwards w i t h t h e MC68000's downward g r o w i n g s t a c k s . T h e s e a r e d i s c u s s e d below. 2.1 The SLIM M a c h i n e SLIM i s a s i m p l e , one a c c u m u l a t o r , s t a c k o r i e n t e d c o m p u t e r , w h i c h o r i g i n a t e d w i t h t h e work of Mark Fox (Fox 7 8 ) . I t has s i n c e u n d e r g o n e s e v e r a l c h a n g e s . The b i g g e s t c h a nge, i s t h a t of c o m p a c t i n g t h e n o t a t i o n (Abramson e t a l 8 0 ) . T h i s c a n be seen by e x a m i n i n g Mark F o x ' s t h e s i s ' s n o t a t i o n w i t h t h e modern f o r m . In t h e o r i g i n a l , a l l of t h e i n s t r u c t i o n s had a n o t a t i o n s i m i l a r t o most a s s e m b l y l a n g u a g e s . Now e a c h i n s t r u c t i o n . h a s a one o r 7 two character notation, thus leading to a smaller number of bytes necessary to transmit source code from one i n s t a l l a t i o n to another. For example, the sequence that was LD P7 STKLD 0 PUSH i s now represented as LIE7 PLO P. Another main area of change has been in the c a l l and return mechanisms. O r i g i n a l l y , the routine that was to do the c a l l , had to reserve s u f f i c i e n t space on the stack for the environment. Now the c a l l instruction handles that job as well. The tradeoff made was one of fewer instructions but with a more complicated c a l l . 2.1 .1 The Registers SLIM i s designed to work with a runtime evaluation stack. To accomplish t h i s , there are two registers used for stack maintenance. The f i r s t i s c a l l e d E and i s used to define the environment. A l l of the runtime linkage, parameter, and l o c a l variables are accessed as offs e t s from E. An offset is defined in the BCPL sense, as the number of c e l l s , not the number of words or bytes. The second register used with the stack i s H. This i s the top of stack marker (also known as the high point in BCPL l i t e r a t u r e ) and is used for pushing and popping values 8 to and from the stack. It can be dynamically changed during execution, thus allowing blocks of c e l l s to be allocated or removed from the stack in addition to 'one at a time' access. For computation, there i s an accumulator c e l l c a l l e d A. A l l arithmetic and l o g i c a l operations take place using A. By convention, this i s also used for holding the value returned by a function. The l a s t two registers are G and C. The concept of the BCPL global vector i s ca r r i e d through to SLIM with G. It points to the start of the global area. At the present time this i s set by the program i n i t i a l i z a t i o n , and i s not altera b l e at runtime. SLIM's program counter i s C. 2.1.2 The Modifiers In the SLIM computer, many of the operations take a possibly modified operand. This may be thought of as a value that i s used in some way by that operation. It should be noted, however, that there are operations that do not take an operand, and that there are several forms of modi f i e r s . If an operation, say L, uses a modifier, the value that L uses i s computed before any action is taken by L. This 9 value, after modification, i s c a l l e d W. W may be thought of as another register, one that i s set to a value immediately after the next instruction has been fetched. It i s W that the operation then uses. Every operand is either a signed or unsigned number, a character constant (this i s stored as an integer value), or a l a b e l . One of these forms must be present i f the operation takes an operator. The notation for a number i s just a numerical.value, preceded by a '-' sign i f negative. For a character constant, the character ' is placed immediately in front of the character that i s the operand. For a label the modifier '@' i s used. This i s followed by the label number. One of the above forms i s always the l a s t in an instruction that takes an operand. The number (character, label) may be immediately preceded by either an 'E' or a 'G'. They may not be both present in one i n s t r u c t i o n . The 'E' means that the current value of the E register i s to be added to the operand producing the modified value, thus implementing a mechanism to give displacements in the runtime environment stack. S i m i l a r l y , 'G' means to add to the operand the value of the G r e g i s t e r . This gives an offset into the global area. At present, G's value never changes, but is assumed to be set to an area that represents the globals. 10 At this point, W has a number. This is just a value, but there must be a mechanism to get at the value stored in some location. This could be accomplished by having an instruction that does th i s task; load from location. This was not the chosen route. It was decided that any instruction should have th i s a b i l i t y , not only to handle values, but values in locations. This i s represented by following the instruction opcode with an optional ' I ' . If there, i t means that there i s to be one l e v e l of indi r e c t i o n taken on W at this point. As an example, take the instruction LIE-5. F i r s t , W is loaded with the value -5. Then the current value of the E register i s added to that. What you now have is a pointer to the runtime environment, -5 c e l l s from the current environment pointed to by E. The 'I' next indicates that you should treat t h i s as an address and fetch the value at that location. So W is now loaded with the contents of the c e l l that is pointed to -5 c e l l s from the current location of E. F i n a l l y , i t is t h i s value that is used by the instr u c t i o n , L (load the accumulator with W). There is a t o t a l l y d i f f e r e n t operand that may be used. It i s represented by the character 'H'. It may not be used with any of the others already mentioned. What i t w i l l do is to take the present value of the H register, use i t as an address, load W with the value that H points to, and then decrement H. This is the action of popping a value off of 11 t h e r u n t i m e e v a l u a t i o n s t a c k . N ote t h a t t h e f a c t t h a t W i s s e t b e f o r e any a c t i o n of an i n s t r u c t i o n must be t a k e n i n t o a c c o u n t w i t h t h i s m o d i f i e r . Some i n s t r u c t i o n s e x p e c t a m o d i f i e d v a l u e and an a d d i t i o n a l v a l u e f r o m t h e s t a c k , so o r d e r i n g i s c r i t i c a l . 2.1.3 A Summary of t h e O p e r a t i o n s The o p e r a t i o n s s u p p o r t e d by SLIM, f a l l i n t o a number of c a t e g o r i e s . The f i r s t i s t h a t of l o a d i n g and s t o r i n g . T h e s e a r e a l w a y s t o and f r o m t h e a c c u m u l a t o r , t h u s s e t t i n g up a r i t h m e t i c s e q u e n c e s and s t o r i n g a n s w e r s , and f o r moving d a t a f r o m one a r e a t o a n o t h e r , as when s e t t i n g up t h e p a r a m e t e r s f o r a p r o c e d u r e c a l l . A n o t h e r i n s t r u c t i o n t y p e i s t h a t of s e q u e n c i n g . T h e r e a r e b a s i c a l l y t h e jump ( c o n d i t i o n a l and u n c o n d i t i o n a l ) , and t h e c a l l and r e t u r n mechanism i n t h i s c a t e g o r y , but a l s o i n c l u d e s e q u e n t i a l s w i t c h i n g c o n t r o l s . N e x t , f a l l t h e a r i t h m e t i c and l o g i c a l o p e r a t i o n s . Most of t h e s e t a k e a m o d i f i e r ; a l l a f f e c t t h e a c c u m u l a t o r . F i n a l l y t h e r e a r e a number of m i s c e l l a n e o u s i n s t r u c t i o n s . A summary of t h e i n s t r u c t i o n s of SLIM i s p r o v i d e d . 12 The SLIM Instructions Instruction Mnemonic Microcode Note: D = data @ = label Load c e l l LW A : = W Store c e l l SW !W := A Load c e l l subscripted L!W A := A!W Store c e l l subscripted S!W LET V = !H; H -:= 1; A!W : = V Load byte L%W A := A%W Store byte S%W LET V = !H; H.-:= 1; A%W : = V Load f i e l d *** L:W A := W of A Store f i e l d *** S:W LET V = !H; H-:= 1 ; W OF A > — t Load device *** L$r A := A!r Store device *** S$r LET V = !H; H -:= 1; A! r : = V Push and load c e l l PLW H +:= 1; !H := A; A := W Jump JW C := W True jump TW IF A = TRUE THEN C : = W False jump FW IF A = FALSE THEN C := W Modify high point MW H +:= W <op> **** <op>W A := A <op> W Ca l l ** CW Return ** R Push P H + : = 1 ; ! H : = A Exchange X W := H!(-1); H!(-1) := A; A • Complement —I A : = ""A Negate — A := -A Absolute 1 A := ABS A Originate *** 0 Void *** V no operation Switchon sequential * ?S D@default Dc1 D@1 Dc2 D@2 ... Den D@n Switchon indexed * ?I D@default Dlo Dhi D@1 D@2 D@n * See "The Essence Of Portable Programming" (Abramson et a l 80) for the microcode ** See "Yet Another C a l l And Return together with Revised Remember and Transfer" (Abramson 81) for the BCPL version of the code *** Not implemented **** <op> codes are: + - * / / * < < = > > = = -• = » « == /\ -/ Figure 1 The SLIM Instructions 1 3 2.2 The M o t o r o l a MC68000 The M o t o r o l a MC68000 i s one o f t h e new g e n e r a t i o n o f m i c r o c o m p u t e r s . I t has an i n t e r n a l d a t a s i z e o f 16 b i t s , w i t h a 23 b i t a d d r e s s s p a c e (word a d d r e s s a b l e ) . The i n s t r u c t i o n s e t i s v e r y f u l l f o r a r i t h m e t i c and c o n t r o l o p e r a t i o n s . 2.2.1 The R e g i s t e r s T h e r e a r e 8 d a t a , and 8 a d d r e s s r e g i s t e r s . E a c h o f t h e s e i s 32 b i t s i n s i z e . The machine s u p p o r t s o p e r a t i o n s i n b y t e (8 b i t ) , word (16 b i t ) , and l o n g word (32 b i t ) f o r t h e d a t a r e g i s t e r s . The a d d r e s s r e g i s t e r s may o n l y be us e d i n word and l o n g word s i z e . When d e a l i n g w i t h b y t e s i z e , t h e low o r d e r ( r i g h t hand) 8 b i t s a r e t h e ones t h a t a r e a f f e c t e d . The same i s t r u e w i t h t h e word s i z e . I t i s t h e low o r d e r 16 b i t s t h a t a r e a f f e c t e d . When l o n g word i s c h o s e n , a l l 32 b i t s a r e a f f e c t e d . Any of t h e d a t a r e g i s t e r s may be u s e d i n c o m p u t a t i o n . T h e r e i s no d e f a u l t r e g i s t e r , t h e programmer has c o m p l e t e c o n t r o l . T h i s i s a l s o t r u e f o r t h e a d d r e s s r e g i s t e r s , e x c e p t f o r t h e a c t i o n of a p r o c e d u r e c a l l . A d d r e s s r e g i s t e r 7, A7, i s u s e d f o r t h i s p u r p o s e . I t a c t u a l l y i s two 1 4 d i f f e r e n t registers, determined by the mode of the machine. In user mode, A7 i s the user stack pointer. The MC68000 also supports a system mode, however. When the computer is in t h i s mode, A7 i s the supervisor stack pointer. This project does not consider the use of the supervisor mode of operation, so any procedure c a l l w i l l use the user stack pointer. 2.2.2 The Addressing Schemes The MC68000 supports addressing schemes that reassemble those of the PDP-11 series. There are twelve dif f e r e n t addressing schemes. Some of the instructions have i m p l i c i t register references. The c a l l and return is an example of t h i s . A l i s t of the various schemes i s : -data register d i r e c t -address register d i r e c t -address register indirect treat the value in an address register as an address 1 5 -address register i n d i r e c t with postincrement the value of the increment i s adjusted according to the size of the argument (1, 2, or 4) -address register i n d i r e c t with predecrement the value is again adjusted according to the size -address register with displacement add a displacement value to the contents of the regi ster -address register with index-in addition to a displacement, add another register's value into the address c a l c u l a t i o n -absolute short the address is contained in the next word -absolute long the address is contained in the next two words -program counter with displacement as with address register with displacement -program counter with index 16 as w i t h a d d r e s s r e g i s t e r w i t h i n d e x - i m m e d i a t e t h e d a t a i s i n t h e i n s t r u c t i o n , f o r b y t e and word s i z e t h e n e x t word c o n t a i n s t h e v a l u e , f o r l o n g word, a s e c o n d word i s u s e d 2.3 I s t h e MC68000 s u i t a b l e f o r SLIM? The p o i n t t o c o n s i d e r i s whether o r not t h e two m a c h i n e s a r e s i m i l a r enough t o t r y t o make a mapping. The p h i l o s o p h y of SLIM i s one of s i m p l i c i t y , so t h a t mapping t o any r e a l c omputer i s p o s s i b l e . The mapping i s f e a s i b l e , and i s r e l a t i v e l y s i m p l e . I w i l l now show t h a t SLIM c a n be mapped t o t h e MC68000. The SLIM a c c u m u l a t o r , A, i s h a n d l e d by t h e d a t a r e g i s t e r DO. The program c o u n t e r C i s h a n d l e d by t h e MC68000's own pr o g r a m c o u n t e r . The a d d r e s s r e g i s t e r s 0 and 1 a r e u s e d f o r H and E r e s p e c t i v e l y . R e g i s t e r A4 i s us e d f o r G, a l t h o u g h f o r t h i s i m p l e m e n t a t i o n , i t i s s e t t o 0. G i v e n t h a t t h e MC68000 s u p p o r t s 16 b i t o p e r a t i o n s e a s i l y on d a t a , 16 b i t s was c h o s e n t o be t h e c e l l s i z e . T h i s means t h a t t h e maximum a d d r e s s a b i l i t y i s o n l y 16 b i t s , t h u s c u t t i n g down on t h e a c t u a l l y a v a i l a b l e number, but t h e 1 7 simulator used to test the system only allowed addresses in the range of 0-7FFF hex. This meant that a c e l l could contain the address of any addressable word in the simulator. The main reason for a 16 b i t c e l l , was that the hardware e a s i l y supports t h i s for the arithmetic and l o g i c a l operations. A major problem i s that the MC68000 only uses the low order 23 b i t s for addressing. This would imply that a 23 b i t c e l l would be the largest that could be supported, as BCPL (and SLIM) state that a c e l l must contain an address. Motorola has plans to expand the computer to a f u l l 32 b i t address space in the future, so a 32 b i t c e l l i s possible for future implementations. At the present time, A4 i s i n i t i a l i z e d to 0. This places the global vector at that location. The maximum number of globals that has been implemented is 25. The address of the startup routine is placed at location 0 (that i s , at global 0), the default address that the simulator starts at. For communication, the program uses two simulator supplied functions, INCON and OUTCON. These are input from console, and output to console, respectively. They deal with a record at a time, so the BCPL routines, RDCH and WRCH are defined in terms of these. This makes li n e by l i n e I/O simple. 18 W i t h t h e above, i t has been seen t h a t e v e r y component i n SLIM c a n be e q u a t e d t o t h e MC68000. The mapping w i l l t h e r e f o r e be c o m p l e t e i f t h e i n s t r u c t i o n s c a n a l s o be mapped. T h i s i s t h e t o p i c o f t h e n e x t c h a p t e r . 19 C h a p t e r 3 The Mapping of SLIM t o t h e MC68000 G i v e n t h a t the_ s t r u c t u r e of SLIM has been mapped t o . t h e MC68000, t h e r e a r e t h r e e t h i n g s t h a t must be s e e n . The f i r s t a r e t h e i n s t r u c t i o n s t h a t w i l l do t h e mapping from SLIM t o t h e MC68000. The o t h e r two i n v o l v e p r o b l e m s w i t h t h a t mapping. The f i r s t of t h e s e i s t o r e s o l v e t h e p r o b l e m of SLIM's use of an a d d r e s s as a c e l l a d d r e s s w i t h t h a t of t h e MC68000's use as a word a d d r e s s . L a s t l y , SLIM's s t a c k s a r e d e f i n e d t o grow upwards. T h i s i s i n c o n s i s t e n t w i t h t h e MC68000, whose s t a c k s grow more c o n v e n i e n t l y downwards. 3.1 The I n s t r u c t i o n M a p p i n g s T h i s s e c t i o n l o o k s a t e a c h i n s t r u c t i o n g r o u p i n t u r n . T h i s a l l o w s one t o c o n c e n t r a t e on t h e s p e c i f i c s o f a p a r t i c u l a r s e t of i n s t r u c t i o n s . 3.1.1 L o a d i n g and S t o r i n g SLIM s u p p o r t s 5 d i f f e r e n t l o a d and s t o r e i n s t r u c t i o n p a i r s . They a l w a y s l o a d o r s t o r e i n o r out of t h e a c c u m u l a t o r . The v a r i o u s i n s t r u c t i o n s a r e : 20 LW SW c e l l L!W S!W c e l l subscripted L%W S%W byte L:W S:W f i e l d L$r S$r device " Given that the load and store device has not been f i n a l i z e d in the design of SLIM, and that loading and storing a f i e l d can be accomplished by l o g i c a l operations, i t was decided not to do these. It should be noted that loading and storing are not consistent in their interpretation of W. For loading, W represents the value that is to be loaded into A. But for storing, W represents the address that A's value i s to be placed i n . This corresponds to the inconsistent actions, of the l e f t and right hand side of an assignment statement in most programming languages. For simple loading and storing, just the value is needed for A. To handle c e l l s , an index is needed. A problem occurs for loading bytes. That is the fact that loading a byte into a data register in the MC68000, w i l l only a l t e r the low order 8 b i t s . This means that for a BCPL/SLIM sense, the other byte of the low order word of A must be cleared. The upper two bytes are not affected, as they are only used for addresses. 21 The next area that must be looked at is how to handle the various modifier options. The method chosen, was to have the code as orthogonal as possible, taking advantage of the various addressing schemes supported by the machine, rather than emphasizing d i f f e r e n t instruction sequences. To handle no modifier i s just to supply the data as being of an immediate nature. If the modifier i s E or G, the SLIM address in those registers must be supplied. There i s a s l i g h t complication though, the addresses stored in the E and G registers (on the MC68000) are stored as word addresses, thus allowing indexing to take place e a s i l y . This means that to get the c e l l address, i t i s necessary to make an adjustment. This i s accomplished by taking the value and s h i f t i n g that right by 1 b i t . The only place where th i s s h i f t i n g must not be done, i s in the global loading sequence, because i f an address i s in the global vector, i t must be a word address, not a c e l l address. For the IE and IG modifiers, a l l that i s needed i s to convert the c e l l address into a word displacement. This is just twice the c e l l value, taking appropriate action for the dir e c t i o n of stack growth. If the modifier i s H, the operand is just popped off of the stack. A label has i t s address loaded, s h i f t i n g to a c e l l address i f necessary. An indirect label is handled with the program counter with displacement mode. F i n a l l y , for a character, the machine 22 dependent form i s loaded into the low order byte. For storing, the scheme is similar, except that the address i s taken one l e v e l sooner; that i s , i t handles the inconsistent nature of storing. This is apparent in examining E and IE. For the E modifier, t h i s i s a location that i s some displacement from the E value. But for IE, the value at that location must be loaded, and then use that for the address to place A. . Examples: L-456 MOVE.W #-456,.DO Load a constant LE3 MOVE A1,D0 LSR.W #1,D0 SUBQ.W #3,DO Load a c e l l address Note the correction for the address LH MOVE.W (A0)+,D0 Pop the stack SE2 MOVE.W DO,-4(A1) Store at a location SH MOVEA.W (A0)+,A2 MOVE.W DO,(A2) Store with top of stack i n d i r e c t i o n L!4 MOVE.W D0,A2 MOVE.W -8(A2,A2),D0 Load with a c e l l subscr ipted L%IE6 LSL.W #1,D0 MOVEA.W -12(A1),A2 MOVE.B 0(A2 , D 0 ) , D 0 ANDI.W #$FF,D0 Load a byte The upper order byte of the accumulator is cleared 23 S%IG3 LSL.W #1,D0 MOVEA.W 6(A4),A2 MOVE.W (A0)+,D2 MOVE.B D2,0(A2,D0) LSR.W #1,D0 S t o r e a b y t e The v a l u e i n DO must be made i n t o a word a d d r e s s and t h e n back t o a c e l l a d d r e s s A l s o t o c o n s i d e r i n t h i s g r o u p , a r e t h e a c t i o n s o f P and PL. They r e p r e s e n t p u s h i n g o n t o t h e e v a l u a t i o n s t a c k . F o r th e PL i n s t r u c t i o n , t h e r e i s t h e a d d i t i o n a l a c t i o n - of l o a d i n g A a f t e r t h e pu s h has o c c u r r e d . The c o d e f o r b o t h i s : MOVE.W DO,-(AO) T h i s i s f o l l o w e d by t h e s t a n d a r d l o a d s e q u e n c e f o r PL. 3.1.2 S e q u e n c i n g T h e r e a r e t h r e e methods of se q u e n c e c o n t r o l i n SLIM. They a r e b r a n c h i n g , t h e c a l l i n g a nd r e t u r n i n g p a i r , and t h e s w i t c h o n c o n s t r u c t s . SLIM s u p p o r t s b o t h u n c o n d i t i o n a l and c o n d i t i o n a l b r a n c h i n g . F o r u n c o n d i t i o n a l , a jump t o t h e l a b e l i s p r o v i d e d . F o r c o n d i t i o n a l , a t e s t i s made w i t h A. D e p e n d i n g on t h e outcome, a b r a n c h may o c c u r . F o r an i n d i r e c t l a b e l , t h e v a l u e a t t h e s p e c i f i e d l o c a t i o n i s l o a d e d i n t o an a d d r e s s r e g i s t e r , t h e n t h a t i s use d a s t h e 24 address. SLIM uses the BCPL/MTS sense of true and f a l s e . True i s represented by negative 1. False i s represented by 0. SLIM does not state what happens i f A has a value of other than true or fals e , and a T or F instruction i s executed. With t h i s implementation, you may not branch with the T, whereas you would with the F, and vice versa. To see t h i s , suppose that A has value -2. If you have the series T@4 J@5, the T instruction w i l l compare -2 with true. Since -2 i s not equal to true, the instruction w i l l not jump, therefore causing the J@5 to be executed. However, i f you have the series F@5 J@4 (which l o g i c a l l y should branch to the same label as the previous s e r i e s ) , -2 is not equal to false so the branch w i l l be to label 4. To see how c a l l and return work, the structure of the runtime stack i s necessary (see figure 2). Basic a l l y i t consists of 3 c e l l s that contain in order, the old top of stack pointer, the old environment pointer, and the return address. For a c a l l to occur, a l l of the parameters, except the l a s t to the routine, are loaded on the stack. The last i s loaded in A. The c a l l instruction treats W as the address of the routine. 25 The C a l l In Action E ( c a l l e r ) H(caller) I I - + + + V + + V-- + |parms| H | E | C |locals|working| _+ + + + + + + <stack link> Before•the c a l l + < + EH(callee) I I . + + + + + + y_ + + _ _ + v + |parms| H | E | C |locals|working|parms| * | * | r | - + + + A + + + + + - I - + + <stack link> (old) <stack link> (new) After the c a l l Figure 2 The C a l l i n g Mechanism 26 To handle the case of d i f f e r i n g numbers of formal and actual parameters, t h i s information i s e x p l i c i t l y coded into SLIM. A c a l l of C@3 D4, i s a c a l l to the routine at label 3, with 4 actual parameters. Then elsewhere may be @3:D6, meaning that this routine expected 6 formal parameters. The purpose of thi s information i s so that the environment can be set up in accordance with the compiled o f f s e t s , as these can not be determined at run time. The return i n s t r u c t i o n , R, restores H, E, and C from the 3 c e l l s currently being pointed to by E. Because of the complexities of c a l l i n g a routine, the C and D instruction pair was made into a runtime support procedure. The address of the routine to c a l l i s loaded into A2, with the number of parameters passed, loaded into Dl . Switchons have two forms, sequential, and indexed. These were both considered too complex to generate the code for d i r e c t l y , so they are implemented as runtime routines. The code sequences for these are as defined in SLIM. There i s the instruction to jump to the runtime support routine, followed by the. various data declarations. These declarations are not handled in any special way, but are just translated as they are. 27 The runtime support for SLIM's c a l l i n s t r u c t i o n , must have the address of the c a l l loaded into A2, with the number of parameters passed loaded into D l . The routine w i l l then look at the SLIM routine's number of expected arguments, and w i l l construct a new environment. It w i l l then pass control to that routine. The return instruction w i l l simply restore the old E and H pointers, and transfer control to the return address. Examples: (assume the f i r s t section) C@3 LEA L3S1,A2 D3 MOVEQ #3,D1 JSR CALL CI@4 MOVEA L4S1,A2 D2 MOVEQ #2,D1 JSR CALL CH MOVEA.W (A0)+,A2 DO MOVEQ #0,D1 JSR CALL R MOVEA.W A1,A3 MOVEM.W (A3)+,A2/A1/A0 JMP (A2) For an unconditional branch, a jump to the label i s a l l that i s needed. If i t i s a conditional branch, however, a test with the accumulator i s needed f i r s t . This w i l l consist of either looking for -1 or 0 (true, false) and jumping i f the test succeeds. 28 Examples: (assume the f i r s t section) J@1 0 JMP L10S1 JI@1 0 MOVEA.W L10S1,A2 JMP (A2) T@1 CMPI.W #-1,D0 BEQ L1S1 F@2 TST.W DO BEQ L2S1 The two switchon instructions are implemented as runtime support routines. The mechanism for translation i s simply to place a jump to subroutine, JSR, instruction to the appropriate routine. The SLIM data following i t i s simply translated as normal. Examples: (assume the f i r s t section) ?S D@1 D1 D@2 D1 0 D@3 DI 00 D@4 JSR SSW DC.W L1S1 DC.W 1 DC.W L2S1 DC.W 10 DC.W L3S1 DC.W 100 DC.W L4S1 ?I D@1 D1 0 D1 2 D@2 D(53 D@4 JSR ISW DC.W L1S1 DC.W 10 DC.W 12 DC.W L2S1 DC.W L3S1 DC.W L4S1 29 3.1.3 The Arithmetic and Logical Operations The chief reason for choosing a c e l l size of 16 b i t s was because of thi s group of instructions. The MC68000 supports the concept of a 16 b i t data size for the arithmetic instructions. Simple arithmetic, such as addition and subtraction, i s possible at a size of 32 b i t s , but mu l t i p l i c a t i o n and d i v i s i o n are not. For ease of programming, these two were programmed using the machine's own multiply and divide. SLIM does not state what happens on overflow, underflow, or on divide by zero. The results of these occurrences are undefined and s t r i c t l y dependent on the pa r t i c u l a r computer that SLIM i s implemented on. For thi s implementation, there is no detection done, so runtime errors w i l l r e s u l t . The arithmetic operations that are supported are addition, subtraction, m u l t i p l i c a t i o n , d i v i s i o n , and modulus (in the BCPL sense for signs). A l l of the above are for integer arithmetic only, as currently there are no fl o a t i n g point numbers implemented in SLIM. The r e l a t i o n a l operators set the value of A, after doing a s p e c i f i c comparison of A to some value. Those supported' are less than, less than or equal to, greater than, greater than or equal to, equal, not equal. The value of A w i l l be set to negative 1 i f the comparison is true, 0 i f i t is 30 f a l s e . There is also the operations of s h i f t i n g . Left and right are both supported. The b i t that i s shifted in is value 0. Note that SLIM does not have a rotate operator. The accumulator may also be used for b i t manipulation, not just comparison. The operations supported are equivalent, not equivalent, l o g i c a l and, and, l o g i c a l or. The b i t pattern formed by the current value of A applied to W i s l e f t in A. There are a number of operations that do not take a modifier. These are b i t wise complement, negate, and absolute value. A l l of these a f f e c t the accumulator. A l l of the above operations have a machine hardware equivalent, with the exception of absolute value. This was handled as a stand alone runtime routine. For addition and subtraction, the value i s taken and applied to DO d i r e c t l y . It should be noted that there is no checking for underflow or overflow. This i s in agreement with what SLIM states. For d i v i s i o n and remainder, the machine's own hardware divide i s used. It expects a 32 bit number, to be divided by a 16 b i t number, and w i l l return the signed integer 31 d i v i s i o n and the remainder. To generate the 32 b i t dividend, a sign extension is performed. For a /* inst r u c t i o n , the d i v i s i o n i s performed, then the remainder is swapped into the low order word. Examples: (with an unmodified operand) +1 ADDI,W #1,DO -2 SUBI.W #2,DO *3 MULS #3,DO /4 EXT.L DO DIVS #4,DO /*5 EXT.L DO DIVS #5,DO SWAP DO For r e l a t i o n a l operators, the comparison i s made with the value to be tested against. At th i s point, the MC68000's condition register i s set. Now the set instruction i s used. It w i l l set the byte destination s p e c i f i e d i f the given condition i s true, otherwise, clear i t . To make thi s a SLIM true or fals e , a sign extension is then done. Sh i f t i n g i s done using one of two forms. The f i r s t i s for s h i f t s of from 1 to 8 b i t s i n c l u s i v e . The other is for bigger s h i f t s , this one requiring that a second data register contain the number of b i t s to s h i f t . 32 Bitwise comparisons are handled as expected, using the MC68000's own hardware instructions. The only complication of"those instructions that have no operand, is with absolute value. This i s not a hardware instruction for the MC68000. So i t must be done in software. The complication is that the assembler does not support a reference to the current location. This means that i f a test for being negative is done, a branch around a negate instruction cannot be done. The ABS routine was therefore created. Examples: (with an unmodified operand) <6 CMPI.W #6,DO SLT DO EXT.W DO > = 7 CMPI.W #7,D0 SGE DO EXT.W DO » 8 LSR.W #8,DO « 9 MOVEQ #9,D1 LSL D1,D0 = =10 EORI.W #10,DO EORI.W #11,D0 NOT.W DO /\12 ANDI.W #12,DO NOT.W DO 33 NEG.W DO | JSR ABS 3.1.4 The Miscellaneous Instructions As mentioned e a r l i e r , SLIM can modify the H register dynamically, not just when pushing or popping the stack. This i s by the M inst r u c t i o n . The value of W i s d i r e c t l y added to H, in a c e l l addressing sense. One instruction i s provided for easing the job of the compiler writer. This i s the top of stack exchange, X. The action of thi s i s to exchange the accumulator, with the contents of the c e l l that i s one down from the top of the evaluation stack. So i f A has value 1, the top of stack 2, and the c e l l below the top of stack 3, after executing X, A w i l l be 3, the top of stack 2, and the other c e l l 1. This operation requires 5 instructions on the machine, but occurs so infrequently that i t i s l e f t as a straight in code inse r t i o n , not a runtime routine. Examples: M5 SUBA.W #10,AO MIE-2 SUBA.W 4(A1),A0 SUBA.W 4(A1),D0 34 MH MOVE.W (A0)+,D1 SUBA.W D1,A0 SUBA.W D1,A0 X ADDA.W #2,AO MOVE.W (A0),D1 MOVE.W DO,(AO) MOVE.W D1,D0 SUBA.W #2,AO 3.1.5 Pseudo Directives There are a number of pseudo d i r e c t i v e s that SLIM has. These are used for storing constants, defining labels, defining the start of procedures and sections, and t e l l i n g when a global load sequence s t a r t s . A l l of these are handled by using similar pseudo d i r e c t i v e s of the Motorola assembler. A point to note i s that i t i s the $$ d i r e c t i v e that d i r e c t s the status of sh i f t i n g or not for adjusting for c e l l addresses. SLIM generates label numbers star t i n g at 1 for each section, thus having labels unique for each section. The Motorola assembler does not support mixing of assemblies. The method chosen for making the labels unique, was to append an additional 'S' followed by a number that represented the section number. So SLIM's @10 in the f i r s t section w i l l translate to L10S1, and in the fourth section to L10S4. This makes the labels unique for the assembler. 35 Examples: (assume the f i r s t section) @2: L2S1: D1 DC.W 1 D@5 DC.W L5S1 D'C DC.W <Character representation of C> $"START" ' ***** START $ * procedure end. These 3 give directions to the translator: $$"FIRST" ***** Section: FIRST $$ <start of global load sequence> <end of section> 3.2 Mapping Problems As mentioned before, there are two main problems facing the mapping. The f i r s t of these is the fact that SLIM uses a c e l l address and the MC68000 uses a word address (which i s twice that of the c e l l address). The second is that of configuring the translation to f i t SLIM's upwards growing stack, with the MC68000's downward growing stack. 36 In BCPL, i f I say X :• = @Y, I w i l l have the c e l l address of Y loaded in X. This concept i s carried over to the SLIM machine, so that i f the accumulator has an address loaded into i t , i t w i l l be the c e l l address. This means that for any other instruction that uses this value as an address, i t must double that value before use. If i t does not replace the accumulator's value, i t must in addition reset that value back to a c e l l address, in case the next operation uses the accumulator again with a c e l l interpretation. This may occur, for example, i f there are two store c e l l s in a row. The only time when you do not want to do t h i s , i s in the global load sequence. This can be shown i f you were to load global 15 with @1. Now the compiler generated code w i l l reference t h i s in the manner of an indirect c a l l through global 15. A t y p i c a l c a l l might be, CIG15 DO, so the value address. On the other hand, i f I need to do some arithmetic to a variable that has an address, i t must be at the c e l l l e v e l so that i t conforms with the BCPL/SLIM sense. This can be seen by examining the code for Writef. In this routine, you have a variable in which you decrement by 1 after each use, thus giving you a c e l l address. The other problem of the stack growth is r e l a t i v e l y easy to handle. The MC68000 does handle stack growth in both d i r e c t i o n s , but i s simpler in the downward d i r e c t i o n . This 37 fact can be seen by remembering that the addressing schemes are predecrement, and postincrement. This means that for forward growing stacks, you would be pointing one word beyond your top of stack word. The choice was made to u t i l i z e the more natural (for the MC68000) downward stacks. This made the problem transparent to SLIM except for the instructions that have an address and use a SLIM displacement from that. An example of this i s L!3. This t e l l s SLIM to take the value in A, treat i t as a c e l l address, and get the c e l l that is 3 locations up the stack from t h i s . Handling the c e l l address has been discused above, but for the 3 locations beyond that, you have to treat t h i s as a c e l l displacement and double i t . F i n a l l y , a look at vectors, strings, and addresses i s required. The vectors are handled in the compilation of the SLIM code as a compiler option. For upward growing stacks, the c e l l pointing to the vector is made to point to the f i r s t c e l l of that vector. This means that the c e l l indexed by v!n i s n c e l l s up from @v. This would not work for downward growing stacks, however, as v!1 i s 1 c e l l down in the runtime stack. To solve t h i s , the c e l l pointing to the vector i s made to point to the l a s t c e l l of the vector. This w i l l cause the vector to grow 'upwards' in the runtime stack, so v!n is n c e l l s 'down' the stack, but i s n c e l l s into the vector. In effect, the d i r e c t i o n a l sense of the vector has been reversed. Strings are stored in the code 38 generated, which grows upwards, so they are not a problem as they go the correct d i r e c t i o n already. As for addresses, since the MC68000 uses downward stacks, a l l references to the 'next' BCPL or SLIM c e l l must use -1 as the increment. For example, i f X has the address of some parameter, to get the address of the next parameter, you would write X -:= 1. 3.3 Optimizations SLIM i s described as a simple, one accumulator, stack oriented computer. The s i m p l i c i t y can best be seen by how the BCPL code for X := X + 1 would t y p i c a l l y be generated. It would look l i k e : LIE3 +1 SE3. From th i s i t should be apparent that at least as far as incrementing or decrementing goes, SLIM uses three instructions where one would do. But this would also be true for any updating type assignment, for example, X := X + Y, which would give LIE3 +IE4 SE3. The reasoning i s to keep the number of SLIM instructions to a minimum. The above would have to have a dyadic operation. This p r o l i f e r a t i o n of additional operators would defeat the purpose in having a simple computer. The above i s just part of the picture, however. The problem shows up in another example. 39 The code f o r L I E 3 = 4 T@5, w ould c r e a t e 6 MC68000 a s s e m b l e r i n s t r u c t i o n s , where 3 would do. The p r o b l e m c a n b e s t be seen i n t h a t t h e i n d i v i d u a l SLIM i n s t r u c t i o n s c a r r y no i n f o r m a t i o n t o t h e n e x t i n s t r u c t i o n . T h i s would a l l e v i a t e s u c h p r o b l e m s a s t h e c o n d i t i o n a l b r a n c h example. I f s u c h i n f o r m a t i o n i s a l l o w e d t o be c a r r i e d a c r o s s more t h a n one SLIM i n s t r u c t i o n , t h e n p a r t i c u l a r l y e f f i c i e n t i n s t r u c t i o n s f o r y o u r machine may be t a k e n a d v a n t a g e o f . T h i s was r e c o g n i z e d and d e a l t w i t h i n t h i s i m p l e m e n t a t i o n . The way t o do t h i s i s t o see t h a t i n s t r u c t i o n 1 f o l l o w e d by i n s t r u c t i o n 2, can b e s t be done, not n e c e s s a r i l y by d i r e c t l y t r a n s l a t i n g them i n t u r n , but p o s s i b l y by t r a n s f o r m i n g them i n t o a d i f f e r e n t p a i r o f i n s t r u c t i o n s . The way t o a c c o m p l i s h t h i s , f o r t h e p a r t i c u l a r example of l o a d i n g a s e r i e s o f p a r a m e t e r s t o t h e s t a c k b e f o r e c a l l i n g , was t o i n v e n t a new i n s t r u c t i o n ; l o a d t o s t a c k , LS. To see t h i s , c o n s i d e r t h e BCPL s t a t e m e n t f o o ( l , 2 , 3 ) . T h i s w i l l g e n e r a t e t h e SLIM code L1 PL2 PL3 CI§3 D3, where you have @3:D<label of foo>. The l o a d i n g s e r i e s w i l l g e n e r a t e 5 a s s e m e b l e r i n s t r u c t i o n s . W i t h t h e o p t i m i z a t i o n t h i s w i l l be seen by t h e code g e n e r a t o r as LS1 LS2 L3 CI@3 D3. A s i n g l e LSn w i l l t a k e o n l y one a s s e m b l e r i n s t r u c t i o n , so t h e l o a d i n g s e r i e s w i l l t a k e o n l y 3 a s s e m b l e r i n s t r u c t i o n s . So t y p i c a l l y , you w i l l go f r o m 2 * ( n - l ) + 1 (n 40 is the number of parameters passed), to n instructions. This i s a considerable savings no matter how you measure e f f i c i e n c y . The fundamental conclusion in experimenting with optimizing the code generation, i s that the implementor must choose a fixed number of SLIM instructions to look at and then p o t e n t i a l l y transform these into a new set of instructions that take advantage of the p a r t i c u l a r computer. ' 3.4 The Runtime Support For any computer system to run, there must be some runtime support. For t h i s system, i t consists of a l i b r a r y of BCPL functions, and some primitives to perform certain SLIM instructions. The format of the primitives, is just to load any control information that they require, and then generate a jump to subroutine instruction, JSR. The most frequently used primitive, i s the CALL routine. This i s for implementing SLIM c a l l s . It functions by taking an address, and the number of actual parameters, and w i l l then set up the runtime environment (depending, on the actual number and the formal number of parameters), and then transfer control to the code. 41 An example of the functions available in the l i b r a r y i s RDCH. This w i l l return with the next character from the current input l i n e . If there is no character, i t w i l l get the next l i n e . Note that for t h i s implementation, there i s a newline character, *N, at the end of every l i n e . The last area that can be included as runtime support, i s that of the loading phase. For this system, th i s is a s t a t i c phase, as the global area and l i b r a r y are preassembled, and start at a fixed location (0). The program starts assembling at the next available location beyond the l i b r a r y . The code of the program is automatically assembled with a sequence of instructions that load the address from global 1, and begin execution there. This i s followed by a series that t e l l the user that the program execution i s finished, and ask for termination. 42 C h a p t e r 4 E v a l u t a t i o n When c o n s i d e r i n g a p r o j e c t o f t h i s t y p e , t h e f i r s t q u e s t i o n t h a t c an be a s k e d i s , d o e s i t work? T h e r e a r e o t h e r f a c t o r s t h a n t h i s , however. Q u e s t i o n s s u c h as t h e s i z e o f cod e p r o d u c e d , and t h e s p e e d a t w h i c h t h a t code w i l l run may be j u s t as i m p o r t a n t . To answer t h e f i r s t q u e s t i o n , does i t work, one o n l y has t o l o o k a t t h e r e s u l t s o f some r u n s ( s e e a p p e n d i c e s ) . The answer i s y e s i t r u n s . A BCPL program can be t a k e n and c o m p i l e d t o SLIM. The SLIM c a n be t r a n s l a t e d t o M o t o r o l a MC68000 a s s e m b l e r and s u c c e s s f u l l y a s s e m b l e d p r o d u c i n g a M o t o r o l a S-module ( t h i s i s t h e t e r m f o r a l o a d a b l e module t o th e M o t o r o l a d e v e l o p m e n t a l s y s t e m , of wh i c h t h e s i m u l a t o r u s e d i n t h i s p r o j e c t i s a p a r t ) . T h i s S-module can be l o a d e d and r u n . One of t h e o t h e r f a c t o r s i s t h e s i z e of t h e code t h a t i s p r o d u c e d . I t may mean t h e d i f f e r e n c e between a p r o g r a m t h a t w i l l f i t on t h e machine and run and one t h a t won't. F o r t h e p r e s e n t s i m u l a t o r , t h e t o t a l of t h e program c o d e , t h e r u n t i m e l i b r a r y , t h e g l o b a l a r e a , and t h e r u n t i m e s t a c k must be l e s s t h a n 8000 hex words. T h i s i s not an o v e r l y g e n e r o u s amount o f memory i f one w i s h e s t o implement a c o m p i l e r , b u t t h i s i s s u f f i c i e n t f o r s m a l l t o moderate p r o g r a m s . 43 If you have a system in which you want to implement a larger program, there are four routes that are available. The f i r s t i s the easiest and is to purchase a real machine with s u f f i c i e n t memory to f i t the program you have in mind. To do t h i s you must remember that the code generator must be reworked to handle the fact that there w i l l be sign extension when dealing with addresses for the M C 6 8 0 0 0 . The usual route i s to hardwire the address lines from the CPU to low, thus ignoring the problem. The second i s to implement the large program in pieces that are of manageable size ( w i l l f i t ) , and have multiple passes. With th i s scheme each pass must have a representation of i t s data that w i l l be storable on the mass storage device. This may not be too p r a c t i c a l for some structures; for example, the expression tree that i s produced by the BCPL compiler. This i s not impossible to represent on a disk, but i s easier to handle i f i t i s a l l i n t e r n a l l y stored. A l t e r n a t l y , the software may page the data structures to and from the mass storage device. But again, a representation of the data must be chosen that makes this, f e a s i b l e . The l a s t method i s the most expensive of the four in terms of hardware costs, but i s the most f l e x i b l e . It is to combine the f i r s t two, and add the memory management unit 44 that Motorola manufactures. This w i l l allow you to implement a v i r t u a l memory system. This would a l l e v i a t e the problem of i n s u f f i c i e n t memory and allow the software not to have to do the paging. As far as execution speed i s concerned, this project cannot make an empirical measurement, as there is no access to a real MC68000, only to a simulator. The simulator w i l l not execute in real time, given that i t is on a time sharing system. One can not even make a good guess at the real time, as the system load w i l l be s h i f t i n g over time. The only way to measure, i s to use the simulator's a b i l i t y to set break traps. This w i l l allow you to see the number of machine (simulated) cycles that a program takes. This i s i l l u s t r a t e d in the appendices. The biggest problem with t h i s system, i s that the code produced is not the most compact form that i s possible. This i s caused by the fact that SLIM's p r i n c i p l e of being a simple computer does not take into account the fact that the newer micro computers have powerful new features. An example of this i s the link mechanism for the MC68000. This instruction w i l l set up a stack l i n k , reserve a given number of words and store the old link pointer, thus allowing the machine to keep i t s own form of an environment, at the instruction l e v e l . Unfortunately, t h i s i s 45 incompatible with the design of SLIM, because SLIM also needs to keep the top of stack marker along with the environment pointer. This results in the route that was taken, a l i b r a r y primitive that does the actions of the SLIM c a l l . The code that i s produced must work in the general case, therefore, i t does things that i t sometimes does not need to. An example of this is in handling the c e l l to word address problem. Many times, the value in the accumulator i s shifted l e f t by 1 b i t , thereby making i t a word address. After t h i s interpretation has been finished, the accumulator's contents are then shifted right by 1 b i t , thereby maintaining i t s c e l l address form. This i s the general case, as mentioned. The problem is that frequently the accumulator i s then immediately used for some other purpose, overwriting the value that was just corrected. An optimization would be to notice that the value in the accumulator is to be overwritten and not make the s h i f t . This problem of not producing the most compactful code was most noticed when the l i b r a r y was hand optimized. The primitive l i b r a r y can be (and is) defined in BCPL, with the exceptions of Rdch, and Wrch. This was compiled producing a SLIM'ed version of the routines. This was then translated to form the assembler•code. The assembler was not d i r e c t l y 46 assembled, however. At t h i s point, the assembly code was taken and modified. The f i r s t thing that was done was to take the code and i n s t a l l into i t , the area that was for the global vector. At location 0, that i s , global 0, a single word form of a branch was i n s t a l l e d to the Startup code. This i s the section of code that sets up the machine's stack, the SLIM stack, i n i t i a l i z e s the registers used for I/O, and then branches to the standard s t a r t i n g address. Once this step had been taken and found to be working, the individual routines were taken, one at a time, and were examined and hand optimized, to reduce the space they occupied and their execution speed. The non-optimiz;ed versions worked, but the tradeoff of the manual e f f o r t for the improved performance was deemed v a l i d . The underlying conclusion of t h i s is that there must be another pass made over the code, one that does some data flow analysis (possibly having to make a tree, in addition to the o r i g i n a l expression tree that was made to produce the SLIM in the f i r s t place). The results of hand optimizing the code, show that the code produced is correct, but that i t is not near to optimal. This can be seen to be a f a u l t , not of the code generator, but rather of the lack of s p e c i a l i z a t i o n in the d e f i n i t i o n of SLIM. The SLIM philosophy does not preach 47 compact n a t i v e c o d e , i t j u s t s t a t e s s i m p l i c i t y of machine d e s i g n , and e a s e o f i m p l e m e n t i n g . B o t h o f t h e s e p o i n t s have been shown t o be t r u e by t h e r e s u l t s of t h i s p r o j e c t . The work a l s o shows t h a t f o r a p a r t i c u l a r i m p l e m e n t a t i o n , a l o c a l c o m p i l e r w r i t e r may have two v e r s i o n s of h i s c o m p i l e r . The f i r s t i s f o r t h e o r i g i n a l p r o b l e m of t r a n s p o r t i n g code t o a d i f f e r e n t i n s t a l l a t i o n . F o r t h i s , a w e l l d e f i n e d common d e s i g n i s needed. F o r o t h e r work, however, he may w e l l want t o have a SLIM p r i m e machine d e f i n e d f o r h i s c o m p u t e r . T h i n k of t h e SLIM p r i m e as a SLIM c o m p u t e r , but w i t h e x t r a s a d d e d t h a t t a k e a d v a n t a g e o f i n f o r m a t i o n he knows t h a t he w i l l be a b l e t o use a t code g e n e r a t i o n t i m e . I t would be a c o m b i n a t i o n of t h i s and t h e t r a n s l a t i o n of SLIM s e q u e n c e s t o d i f f e r i n g s e q u e n c e s , t h a t w o u l d make f o r much b e t t e r c o d e . A s p e c i f i c example was made w i t h t h e MC68000. The l o a d t o s t a c k i n s t r u c t i o n , LS, as p r e v i o u s l y m e n t i o n e d , was c r e a t e d . I t s p u r p o s e i s t o t a k e a d v a n t a g e o f t h e f a c t t h a t t h e MC68000 can move d a t a d i r e c t l y t o t h e r u n t i m e s t a c k , I t d o e s n o t need t o l o a d a r e g i s t e r and t h e n push t h e r e g i s t e r ' s v a l u e . 48 C h a p t e r 5 C o n c l u s i o n s and F u r t h e r R e s e a r c h The i n t e n t i o n o f t h e p r o j e c t was t o see whether SLIM c o u l d be a s u i t a b l e v e h i c l e f o r t h e t r a n s p o r t i n g o f BCPL pro g r a m s t o t h e M o t o r o l a MC68000. To t h i s end, t h e p r o j e c t i s a s u c c e s s . The code e x i s t s w h i c h w i l l t a k e SLIM code and p r o d u c e M o t o r o l a a s s e m b l e r w h i c h w i l l l o a d and e x e c u t e on th e M o t o r o l a s u p p l i e d s i m u l a t o r . T h e r e a r e p r o b l e m s as t h i n g s s t a n d , t h o u g h . The f i r s t and. f o r e m o s t i s t h a t t h i s i s u s i n g a s i m u l a t o r , n o t a r e a l m a c h i n e . T h i s was c a u s e d by s e v e r a l f a c t o r s , p r i n c i p a l l y t h a t t h e u n i v e r s i t y does not y e t own a MC68000. The s e c o n d f a c t o r , i s t h a t even t h o u g h t h e u n i v e r s i t y has p u r c h a s e d a MC68000, i t w i l l n o t be a v a i l a b l e i n t h e n e a r f u t u r e . T h i s d o e s not i n v a l i d a t e t h e p r o j e c t , i t j u s t would have been n i c e r t o see t h e cod e e x e c u t i n g on a r e a l m a c h i n e . A t o p i c t h a t must be l o o k e d a t b e f o r e r e s e a r c h on SLIM can p r o c e e d , i s whether or not i t s h o u l d be r e d e s i g n e d t o t a k e a d v a n t a g e of new f e a t u r e s o f r e a l m i c r o c o m p u t e r s . T h i s i s a d e b a t a b l e t o p i c . T h e r e i s t h e argument t h a t t h e e f f i c i e n c y t h a t t h i s would buy i s w e l l w o r t h t h e e f f o r t and c o m p l i c a t i o n s t h a t t h i s would a d d . T h i s would be r e f l e c t e d i n b e t t e r code g e n e r a t i o n ( o r a t l e a s t no needed c o d e o p t i m i z a t i o n ) , and i n s m a l l e r s o u r c e code programs ( t h e y 49 would be more compact). Of course, the argument against this i s that SLIM must be simple, so that anybody has a chance of implementing i t . This i s the argument that I tend to support. The simpler the simulated computer, the easier my i n i t i a l job i s . This leads to a better chance of my getting a system that w i l l run. At many i n s t a l l a t i o n s , code size and execution speed are c r i t i c a l issues. These may be caused by memory size l i m i t a t i o n s , non-mapped memory (a no v i r t u a l memory system), and real time applications. Even with these problems, however, i t i s better to get a translator which works before handling writing an e f f i c i e n t t r a nslator. Given that an implementor i s functioning from within a community of users, someone may already have written an e f f i c i e n t translator for his p a r t i c u l a r machine. If t h i s is so, he need only have a simple minded translator running to get the e f f i c i e n t one. He can get the person with the e f f i c i e n t translator to SLIM i t , and send the SLIM'ed code to him. He then runs the SLIM'ed e f f i c i e n t translator through his not so e f f i c i e n t one. Then he runs the SLIM through the code that was produced, giving him a native machine version of the e f f i c i e n t translator. 50 If an e f f i c i e n t translator does not exi s t , and he writes one, then i t i s available in the community of users. Thus, i f someone has the same machine as he does, the above actions are reversed. Another person writes a simple minded translator, and then i s sent a SLIM'ed version of the e f f i c i e n t one. Even i f other users may not be able to use the e f f i c i e n t translator for their machines, i t may provide some methods that they can use themselves. In e f f e c t , what an e f f i c i e n t translator for a p a r t i c u l a r machine can do, i s to provide a framework on which another can be b u i l t . This may take the form, for example, of a new instruction (for the MC68000, the LS i s an example) which another machine can use. If the route followed i s to keep SLIM as simple as i t i s , then an implementor must have a method for the optimization, as mentioned above. This can be done by combining two methods, optimize a series of SLIM instructions into a d i f f e r e n t series producing assembler code followed by optimizing that assembler code, before the actual assembly. It i s t h i s combination that must be looked at for future machines. The question of what is a good instruction to invent for one machine, for example the LS (load to stack) for the MC68000, may well be asked on another machine. 51 The LS instruction was designed for the MC68000 to take advantage of i t s stack nature. The same instruction would probably be used on a PDP-11, as the MC68000's addressing schemes are based on the PDP's. This would indicate to an implementor, that i f his machine i s stack oriented, he may well be able to make use of LS. After this comes the question of how to take advantage of the fact that most modern computers have instructions that contain two memory references, so operations l i k e incrementing, do not have to do a load, add, store sequence, but only 1 ins t r u c t i o n . Looking at this closer, a t y p i c a l SLIM sequence i s : LIE5 +3 SE5. This would produce the code: MOVE.W - 10(A1),D0 ADDI.W #3,DO MOVE.W D0,-10(A1) These three instructions can be reduced to one having the same e f f e c t : ADDI.W#3,-10(A1) 52 Bibliography 1. Abramson, H. Three BCPL Machines , UBC Technical Report 79-11, 1979 2. Abramson, H. Yet another C a l l and Return ! together with Revised Remember and Transfer , UBC SLIM note, 1981 3. Abramson, H., Fox, M., Gorlick, M., Manis, V. & Peck, J. The Pica-B Computer, An Abstract Target Machine For A Transportable Single-User Operating System , UBC Technical Report 79-12, 1979 4. Abramson, H., Peck, J. & Dyment, J. The Essence Of  Portable Programming , UBC Preliminary Draft, 1980 5. Agarwal, R. & Chanson, S. A Space-efficient Code  Generation Scheme For BCPL , Software Practice And Review, Vol 10 No 2, pp 77 - 95, 1980 6. Cheriton, D. & Murphy, W. Verex System Programmer's Manual , UBC Technical Manual 79-1, 1979 7. Cheriton, D. & Steeves, P. Zed Language Reference  Manual , UBC Technical Report 79-2, 1979 8. Fox, M. Machine Archtitecture And The Programming  Language BCPL , UBC Thesis, 1978 9. Hecht, M. Flow Analysis Of Computer Programs , Elsevier North-Holland, 1977 10. MC68000, 16-Bit Microprocessor , Motorola, 1980 11. M68000 Simulator Reference Manual , Motorola, 1980 12. Richards, M. BCPL: A Tool For Compiler Writing And  System Programming Proc. of the AFIPS 1969 SJCC, Vol 34, AFIPS press, pp 557 - 566 13. Richards, M. , Edited by Peck,. J. & Manis, V. The BCPL  Programming:Manual , UBC Technical Manual 75-77, 1977 53 14. Richards, M. & Whitby-Strevens, C. BCPL - The Language  And Its Compiler , Cambridge University Press, 1979 54 Appendix I The Software This i s a description of the software involved with t h i s system. This includes the BCPL to SLIM compiler, the SLIM to Motorola translator, the MC68000 assembler, and the MC68000 simulator. The BCPL to SLIM compiler i s a program that originated at Cambridge. It has since been modified at UBC to run under MTS. This i s part of the ongoing SLIM project. BCPL has been successfully compiled on several d i f f e r e n t computers. The route taken has been one that t h i s thesis has done, convert BCPL into SLIM and then write a SLIM to native computer translator. To f a c i l t a t e the fact that some computers have a downward growing stack ( l i k e the MC68000), the compiler has an option that w i l l c o r r e c t l y handle VEC's, a BCPL one dimensional array construct, to take t h i s into account. The translator w i l l accept SLIM code and produce Motorola MC68000 assembly code. Each instruction i s parsed, to get the instruction, the modifier, and the operand. The operator i s then used to switch into a large SWITCHON statement, which then in turn, uses the modifier ( i f necessary) in another SWITCHON. The code i s then generated by the f i n a l state that is found. The program also uses the 55 simple optimization of examining two consecutive SLIM instructions, and replacing them with a d i f f e r e n t pair, i f they are found to be a known pairing. The Motorola assembler and simulator are programs supplied from Motorola. The assembler w i l l generate a text f i l e that is acceptable by the simulator. These f i l e s are c a l l e d S-modules, as every l i n e starts with an S. A l l of the above software can be seen running in the following appendices. This i s a l i s t of the programs: -To generate SLIM code: $RUN JELP:SLIM SCARDS=BCPL.source SPUNCH=slim PAR=BN -To translate t h i s into assembler: $RUN RNGR:PROJ.O+CS:BCPLLIB SCARDS=slim SPUNCH=asmb -This is then given to the assembler: $RUN VERX:M68K.ASM SCARDS=asmb SPRINT=-P SPUNCH=s.module -This i s then run on the simulator: $RUN VERX:M68K.SIM 1=s.module+RNGR:PROJ.LIB Appendix II Print Out Hi # com This i s an edited version of the programs # com running under MTS # # l i s t t1.s > 1 // test WRCH > 2 get. "rngr:header" > 3 l e t s t a r t O be > 4 $( Wrch('H'); WrchCi*); Wrch('*N') $) # com Now compile this into SLIM # run j e l p r s l i m scards=t1.s spunch=t1.sl par=bn UBC - BCPL/MTS version 7 (81-09-20) PAR=BN (s) l i s t i n g = FALSE (T) tree = FALSE (n) code option = (B) backvec = TRUE (L) lex trace = FALSE (0) overlay = FALSE (N) naming = FALSE (K) mark = FALSE ( + ) tree space = 12000 Tree size = 426(000652) 0 BCPL errors detected # l i s t t 1 . s i > 1 J@2 > 2 $"START" > 3 @1:D0 L'H CIG2 D1 L ' i CIG2 D1 L'*N CIG2 > 4 D1 R $: $ > 5 @2:@3:$$ L@1 SG1 . > 6 # com Now translate this into Motorola assembler # # run proj.o+cs:bcpllib scards=t1.sl spunch=t1.a Motorola instructions = 21(000025) # l i s t t1.a@-ic > 1 $CONTINUE WITH RNGR:PROJ.HD.S RETURN > 2 JMP L2S1 > 3 ***** START > 4 L1S1: DC.W 0 > 5 MOVEQ #72,DO > 6 MOVEA.W 4(A4),A2 > 7 MOVEQ #1,D1 > 8 JSR CALL > 9 MOVEQ #105,DO > 10 MOVEA.W 4(A4),A2 > 11 MOVEQ #1,D1 > 12 JSR CALL > 13 MOVEQ #10,DO > 14 MOVEA.W 4(A4),A2 > 15 MOVEQ #1,D1 57 > 16 JSR CALL > 17 MOVEA.W A1,A3 > 18 MOVEM.W (A3)+,A2/A1/A0 > 19 JMP (A2) > 20 * p r o c e d u r e end > 21 * p r o c e d u r e end > 22 L2S1: DS.W 0 > 23 L3S1: LEA L1S1,A2 > 24 MOVE.W A2,D0 > 25 MOVE.W D0,2(A4) > 26 $CONTINUE WITH RNGR:PROJ.TL.S RETURN # com T h i s i s now a s s e m b l e d , p r o d u c i n g an S-module # run verx:m68k.asm s c a r d s = t 1 . a s p r i n t = - p spunch=t1.68 MC68000 ASM REV: 1.4 - COPYRIGHT MOTOROLA 1978 ****** TOTAL ERRORS: 0 — TOTAL LINES: 49 # l i s t t 1 . 6 8 > 1 S00600004844521B > 2 S11305324EFA003000007048346C000472014EB868 > 3 S1130542004E7069346C000472014EB8004E700A99 > 4 S1130552346C000472014EB8004E36494C9B0700BD > 5 S10505624ED273 > 6 S113056445FAFFD0300A39400002346C00027200AC > 7 S11305744EB8004E700A45F8007272014EB8004E2F > 8 S11305844E7200004BFA00184DED001B4EB90001E9 > 9 S113059400024EB9000100004EB900010000202AF7 > 10 . S11305A42A2A20454E44204F462052554E202A2ABA > 11 S10D05B42A2048495420454F4620F0 > 12 S9030000FC # com Now t h i s l o a d module and t h e l i b r a r y # com a r e l o a d e d i n t o t h e s i m u l a t o r # r u n verx:m68k.sim 1 = t 1 . 6 8 + p r o j . l i b MACSS SIMULATOR - REL 1.9 ? IM ? SD T ? R Hi PRIVILEDGED INSTRUCTION TRAP ADDRESS IS ZERO. T=3C6 end of f i l e # com Note t h a t t h e r e were 3C6 Hex c y c l e s t a k e n 58 Appendix III Towers of Hanoi # com This i s a simple example that w i l l # com demonstrate recursion and # com multiple sections # # l i s t t15.s > 1 section, " f i r s t section, just has s t a r t " > 2 get. "rngr:header" > 3 global $( hanoi : 15 $) > 4 l e t start() be > 5 •$( l e t n = readnO > 6 i f n = 0 then return > 7 writef("Towers of Hanoi n=%N*N", n) > 9 hanoi(n, 'A', 'B', 'C') > 10 $) repeat > 11 > 1 2 . > 13 section, "second section" > 14 get. "rngr:header" > 15 global $( hanoi : 15 $) > 16 let hanoi(n, s, i , d) be > 17 $( i f n <= 0 then return > 18 hanoi(n-1, s, d, i) > 19 writef("Move %N from %C to %C*N", n, s, d) > 21 hanoi(n-1, i , s, d) > 22 . $) > 23 # run j e l p r s l i m scards=tl5.s spunch=t15.si par=bn UBC - BCPL/MTS version 7 (81-09-20) PAR= = BN ( s ) l i s t i n g = FALSE (T) tree = FALSE (n) code option = (B) backvec = TRUE (L) lex trace = FALSE (0) overlay FALSE (N) naming = FALSE (K) mark = FALSE ( + ) tree space = 12000 SECTION f i r s t section, just has start Tree size = 479(000761) 0 BCPL errors detected SECTION second section Tree size = 525(001015) 0 BCPL errors detected # l i s t t15.sl > 2 $ $ " f i r s t section, just has st a r t " J@2 > 3 $"START" > 4 @1:D0 > 5 @3:CIG8 DO P =0 F@4 R > 6 . @4:L@5 PLIE1 CIG-5 D2 LIE1 PL'A PL'B PL'C CIG15 59 > 7 D4 M-1 J@3 $: > 8 @5:D"Towers of Hanoi n=%N*N" $ > 9 @2:@6:$$ L@1 SG1 . > 10 > 1 1 $$"second section" J@2 > 1 2 $"HANOI" > 1 3 @1:D4 LIE-6 <=0 F@3 R > 1 4 @3:LIE-6 -1 PLIE-5 PLIE-3 PLIE-4 CIG1 5 > 1 5 PLIE-6 > 16 PLIE-5 PLIE-3 CIG5 D4 LIE-6 -1 PLIE-4 > 17 PLIE-3 CIG15 > 18 D4 R $: > 19 @4:D"Move %N from %C to %C*N" $ > 20 @2:@5:$$ L@1 SG15 . > 21 # run proj .o+cs:bcpllib scards=t15.si spunch= 11 5.a D4 L@4 PLIE-5 Motorola instructions = 46(000056) Motorola instructions = 64(000100) # run verx:m68k,asm scards=t1.a sprint=-p spunch=t15.68 MC68000 ASM REV: 1.4 - COPYRIGHT MOTOROLA 1978 ****** TOTAL ERRORS: 0 — TOTAL LINES: 132 #• run verx :m68k . sim 1 =t 1 5 . 68+pro j . 1 ib MACSS SIMULATOR - REL 1.9 ? IM ? SD T ? R 3 Towers of Hanoi n=3 Move 1 from A to C Move 2 from A to B Move 1 from C to B Move 3 from A to C Move 1 from B to A Move 2 from B to C Move 1 from A to C 1 Towers of Hanoi n=1 Move 1 from A to C 0 PRIVILEDGED INSTRUCTION TRAP ADDRESS IS ZERO. T=1123E end of f i l e # com Note the number of cycles Appendix IV The SLIM Parser # com This example takes the # com SLIM parser (modified) # com from the program # # com It is then run on the SLIM # com that writes out 'Hi' # com (see appendix 2) # # run jelp: s l i m scards=eg.s spunch=eg.sl par=bn UBC - BCPL/MTS version 7 (81-09-20) PAR=BN (S) l i s t i n g = FALSE (T) tree = FALSE (n) code option = (B) backvec = TRUE (L) lex trace = FALSE (0) overlay = FALSE (N) naming = FALSE (K) mark = FALSE (+) tree space = 12000 Tree size = 2855(005447) 0 BCPL errors detected # run proj.o+cs:bcpllib scards=eg.sl spunch=eg.a Motorola instructions = 877(001555) # run verx:m68k.asm scards=eg.a sprint=-p spunch=eg, MC68000 ASM REV: 1.4 - COPYRIGHT MOTOROLA 1978 ****** TOTAL ERRORS: 0 ~ TOTAL LINES: # run verx:m68k.sim 1=eg.68+proj.lib 930 MACSS SIMULATOR -? IM ? SD 1 ? R $continue with t1 code=1 62,7,2 code=1 79,12,16243 code=1 66,9, 1 code=1 52,9,0 code=1 65,11,72 code=1 51,4,2 code=1 52,9,1 code=1 65,11,105 code=1 51,4,2 code=1 52,9,1 code=1 65,11,10 code=1 51,4,2 code=1 52,9,1 code=1 82,13,0 code=1 79,13,0 code=1 79,13,0 61 code=l66,9,2 code=l66,9,3 code=1,13,0 code=165,7,1 code=183,3,1 PRIVILEDGED INSTRUCTION TRAP ADDRESS IS ZERO. T=3460D end of f i l e # com You can now compare th i s with the # com manifest values for the instructions # l i s t eg.header > 1 MANIFEST $( cell_bsz = 2; endstreamch = -1 $) > 2 /* The tree header. */ > 3 MANIFEST > 4 $( s_section = 1 > 5 s_neg = 2 > 6 s_not = 3 > 7 s_mult = 5 > 8 s_div = 6 > 9 s_rem = 7 > 10 s_plus = 8 > 11 s_minus = 9 > 12 s_eq = 10 > 13 s_ne = 1 1 > 14 s _ l t = 12 > 15- s_ge = 13 > 16 s_gt = 14 > 17 s_le = 15 > 18 s_shl = 16 > 19 s_shr = 17 > 20 s_logand = 18 > 21 s_logor = 19 > 22 s_neqv = 20 > 2 3 s_eqv = 24 > 24 s_abs = 36 > 25 s_c = 151 > 26 s_d = 152 > 27 s_end = 153 > 28 s_ent_def = 154 > 29 s_error = 156 > 30 s_ext_def = 157 > 31 s_f = 158 > 32 s_isw = 161 > 33 s_j = 162 > 34 s _ l = 165 > 35 s_lab_def = 166 > 36 s_load_byte = 168 > 37 s_load_cell = 169 > 38 s_m = 173 > 39 s_p = 177 > 40 s_pl = 178 > 41 s_proc_nm = 179 > 42 s_q = 181 > 43 s_r = 182 > 44 s_s = 183 > 45 s ssw = 185 62 > 46 s _ s t o r e _ c e l l = 1 8 6 -> 47 s _ s t o r e _ b y t e = 187 > 48 s _ t = 188 > 49 s x = 189 > 50 $T > 51 > 52 MANIFEST > 53 /* T h e s e a r e c o n s t a n t s f o r SLIM m o d i f i e r s . * / > 54 $( m_e = 1; m_ie = 2; m_g = 3; m_ig = 4 > 55 m_h = 5; m_ih = 6; m_l = 7; m _ i l = 8 > 56 m_n = 9; m_in = 10; m_c = 11; m_s = 12 > 57 m _ n u l l = 13; m_colon:14; m_en_def = 16; > 57.5 m_ex_def = 17 > 58 m_nop = 18 > 59 /* S t a t e s f o r e a c h e x t e r n a l */ > 60 e x t _ d e c l a r e d = 1; e x t _ d e f i n e d = 2; > 60.5 e x t _ a p p l i e d = 3 $) > 61 > 62 GLOBAL $( s e c t i o n _ n u m : 15 $) > 63 63 Appendix V Optimizing Example This example w i l l show that though the code produced works, i t could be improved by having another pass over i t . This pass could do simple data flow analysis, for instance, i t could determine i f the accumulator is to be loaded with a new value in the next i n s t r u c t i o n . If so, then i t i s free to be bypassed in a load sequence. This i s seen i f you consider that a t y p i c a l SLIM sequence is to load the A with a value, then store i t somewhere, then load another value. This could instead be accomplished by just using an instruction that w i l l move the f i r s t data item to where i t is needed, and then loading in the next value. This i s the code produced by the program for Writes, the standard BCPL routine for writing strings. This i s one of the l i b r a r y routines that i s supplied. ***** WRITES L3S1: DC.W 1 MOVE.W #1,-(A0) MOVE.W 6(A1),D0 MOVEA.W D0,A2 CLR.W DO MOVE.B 0(A2,A2),D0 MOVE.W DO,-(AO) JMP L24S1 L25S1: MOVE.W 6(A1),D0 LSL.W #1,D0 MOVEA.W -2(A1),A2 MOVE.B 0(A2,D0),D0 ANDI,W #$FF,D0 64 MOVEA.W 4(A4),A2 MOVEQ #1,D1 JSR CALL MOVE.W -2(A1),D0 ADDI.W #1,D0 MOVE.W DO,-2(A1) L24S1: MOVE.W -2(A1),D0 CMP.W -4(A1),D0 SLE DO EXT.W DO CMPI.W #-1,D0 BEQ L25S1 MOVEA A1 ,A3 MOVEM.W (A3)+,A2/A1/A0 JMP (A2) * procedure end * procedure end This code was then taken and hand optimized. This was done for space and time e f f i c i e n c y in the l i b r a r y routine. ***** WRITES Writes: DC.W 1 MOVE.W #1,-(A0) MOVEA.W 6(A1),A2 CLR.W DO MOVE.B 0(A2,A2),D0 MOVE.W DO,-(AO) BRA.S L24S1 L25S1: MOVE.W 6(A1),D0 LSL.W #1,D0 MOVEA.W -2(A1),A2 MOVE.B 0(A2,D0),D0 ANDI.W #$FF,D0 MOVEA.W 4(A4),A2 MOVEQ #1,D1 JSR CALL ADDQ #1,-2(A1) L24A1: MOVE.W -2(A1),D0 CMP.W -4(A1),D0 BLE L25S1 MOVEA.W A1,A3 MOVEM.W (A3)+,A2/A1/A0 JMP (A2) * procedure end * procedure end 65 The non-optimized version has 27 instructions and one constant. The other has 21 and a constant. Even th i s simple example shows that the code can be compressed. . T h i s optimization might be done by reading the assembler instructions in order, looking for a time that the accumulator (DO in thi s system) i s loaded with a value. The scan then continues to the following i n s t r u c t i o n . If that instruction i s to store DO, the next instruction i s examined. If th i s one is to load DO, then the previous two can be changed from the load DO, store DO, into move a value. This can be seen by examining: MOVE.W #2,DO MOVE.W DO,2(A1) MOVE.W -6(A1),D0 MOVE.W D0,8(A4) MOVE.W -4(A1),D0 JMP L1S1 This can be changed into: MOVE.W # 2,2(A1) MOVE.W -6(A1),8(A4) MOVE.W -4(A1),D0 JMP L1S1 v. 66 Appendix VI The CALL Routine This i s the CALL routine, as i t i s in the runtime support l i b r a r y . It is based, on the BCPL routine in "Yet another C a l l and Return ! together with Revised Remember and Transfer" (Abramson 81). This BCPL version was run through the SLIM compiler, hand assembled from the SLIM produced, and f i n a l l y , hand optimized. This is the most compact code that I can see for the routine. CALL: MOVE.W (A2),D2, \ BEQ.S CALL 1 \ MOVE.W DO,-(AO) \ CALL 1: MOVE.W D2,D4 \ BLT.S CALL2 \ SUB.W D1,D4 \ LSL.W #1,D4 SUBA D4,A0 MOVE.W D2,D1 CALL2: LSL.W #1,D1 \ MOVE.W A0,D2 ADD.W D1,D2 MOVEA.L (A7)+,A3 \ MOVEM.W D2/A1/A3,-(A0) \ MOVEA.L A0,A1 \ ADDQ #2,A2 \ JMP (A2) \ get number expected i f -•= 0 then push last argument i f i n d e f i n i t e number then skip t h i s : compute new_h(Shortfall) adjust H get return address make stack environment E := H skip over number expected c e l l start executing the routine 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            data-media="{[{embed.selectedMedia}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0051818/manifest

Comment

Related Items