1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408 |
- .nr PS 11
- .nr VS 13p
- .EQ
- delim @@
- .EN
- .EQ
- gfont R
- .EN
- .ND
- .RP
- .TL
- A back end table for the Motorola MC68000, MC68010 and MC68020 microprocessors
- .AU
- Frank Doodeman
- .AB
- A back end table is part of the Amsterdam Compiler Kit (ACK). It is used
- to produce the actual back end, a program that translates the intermediate
- language family EM to assembly language for some target machine. The table
- discussed here can be used for two back ends, suitable for in total three
- machines: the MC68000 and MC68010 (the difference between these two is
- so small that one back end table can be used for either one), or
- for the MC68020.
- .AE
- .NH
- Introduction
- .PP
- To simplify the task of producing portable (cross) compilers and interpreters
- the Vrije Universiteit designed an integrated collection of programs, the
- Amsterdam Compiler Kit (ACK) [2]. It is based on the old UNCOL idea [1] which
- attempts to solve the problem of how to make a compiler for each of @ N @
- languages on @ M @ different machines without having to write @ N times M @
- programs.
- .PP
- The UNCOL approach is to write @ N @
- .I
- front ends,
- .R
- which translate the
- source language into a common intermediate language UNCOL (Universal Computer
- Oriented Language), and @ M @
- .I
- back ends,
- .R
- each of which translates programs in
- UNCOL into a specific machine language. Under these conditions only @ M + N @
- programs must be written to provide all @ N @ languages on all @ M @
- machines, instead of @ M times N @ programs.
- .PP
- The intermediate language for the Amsterdam Compiler Kit is the machine language
- for a simple stack machine called EM (Encoding Machine) [3]. So a back end for
- the MC68020 translates EM code into MC68020 assembly language. Writing such a
- table [4] suffices to get the back end.
- .PP
- The back end is a single program that is driven by a machine dependent driving
- table. This table, the back end table, defines the mapping of EM code to
- the MC68000, MC68010 or MC68020 assembly language.
- .NH
- The MC68000 and MC68020 micro processors
- .PP
- In this document the name MC68000 will be used for both the MC68000 and the
- MC68010 micro processors, because as far as the back end table is concerned
- there is no difference between them. For a complete and detailed description
- of the MC68020 one is referred to [5]; for the MC68000 one might also use [6].
- In this section some relevant parts will be handled.
- .NH 2
- Registers
- .PP
- Both the MC68000 and the MC68020 have eight 32-bit data registers (@ D sub 0 @-@ D sub 7 @) that can
- be used for byte (8-bit), word (16-bit) and long word (32-bit) data operations.
- They also have seven 32-bit address registers (@ A sub 0 @-@ A sub 6 @) that may be used as
- software stack pointers and base address registers; address register @ A sub 7 @ is
- used as the system stack pointer. Address registers may also be used for
- word and long word address operations.
- .NH 2
- Addressing modes
- .PP
- First the MC68000 addressing modes will be discussed. Since the MC68020's
- set of addressing modes is an extension of the MC68000's set, of course this
- section also applies to the MC68020.
- .PP
- In the description we use:
- .IP @ A sub n @
- for address register;
- .IP @ D sub n @
- for data register;
- .IP @ R sub n @
- for address or data register;
- .IP @ X sub n @
- for index register (either data or address register);
- .IP @ PC @
- for program counter;
- .IP @ d sub 8 @
- for 8 bit displacement integer;
- .IP @ d sub 16 @
- for 16 bit displacement integer;
- .IP @ bd @
- for base displacement (may be null, word or long);
- .IP @ od @
- for outer displacement (may be null, word or long).
- .NH 3
- General addressing modes
- .NH 4
- Register Direct Addressing
- .IP Syntax: 8
- @ R sub n @
- .PP
- This addressing mode (it can be used with either a data register or an address
- register) specifies that the operand is in one of
- the 16 multifunction registers.
- .NH 4
- Address Register Indirect
- .IP Syntax: 8
- @ ( A sub n ) @
- .PP
- The address of the operand is in the address register specified.
- .NH 4
- Address Register Indirect With Postincrement
- .IP Syntax: 8
- @ ( A sub n )+ @
- .PP
- The address of the operand is in the address register specified. After the
- operand address is used, the address register is incremented by one, two or
- four depending upon whether the size of the operand is byte, word or long.
- If the address register is the stack pointer and the operand size is byte, the
- address register is incremented by two rather than one to keep the stack pointer
- on a word boundary.
- .NH 4
- Address Register Indirect With Predecrement
- .IP Syntax: 8
- @ -( A sub n ) @
- .PP
- The address of the operand is in the address register specified. Before the
- operand address is used, the address register is decremented by one, two or
- four depending upon whether the size of the operand is byte, word or long.
- If the address register is the stack pointer and the operand size is byte, the
- address register is decremented by two rather than one to keep the stack pointer
- on a word boundary.
- .NH 4
- Address Register Indirect With Displacement
- .IP Syntax: 8
- @ d sub 16 ( A sub n ) @ for the MC68000, @ ( d sub 16 , A sub n ) @ for the MC68020
- .PP
- This address mode requires one word of extension. The address of the operand is
- the sum of the contents of the address register and the sign extended 16-bit
- integer in the extension word.
- .NH 4
- Address Register Indirect With Index
- .IP Syntax: 8
- @ d sub 8 ( A sub n , X sub n .size) @ for the MC68000, @ ( d sub 8 , A sub n , X sub n .size) @ for the MC68020
- .PP
- This address mode requires one word of extension according to a certain format,
- which specifies
- .IP 1.
- which register to use as index register;
- .IP 2.
- a flag that indicates whether the index register is a data register or an
- address register;
- .IP 3.
- a flag that indicates the index size; this is
- .I word
- when the low order part of the index register is to be used, and
- .I long
- when the whole long value in the register is to be used as index;
- .IP 4.
- an 8-bit displacement integer (the low order byte of the extension word).
- .PP
- The address of the operand is the sum of the contents of the address register,
- the possibly sign extended contents of index register and the sign
- extended 8-bit displacement.
- .NH 4
- Absolute Data Addressing
- .IP Syntax: 8
- @ address @ for the MC68000, @ ( address ) @ for the MC68020
- .PP
- Two different kinds of this mode are available:
- .IP 1.
- Absolute Short Address; this mode requires one word of extension. The address of
- the operand is the sign extended 16-bit extension word.
- .IP 2.
- Absolute Long Address; this mode requires two words of extension. The address of
- the operand is developed by concatenation of the two extension words; the high
- order part of the address is the first extension word, the low order part is
- the second.
- .NH 4
- Program Counter With Displacement.
- .IP Syntax: 8
- @ d sub 16 ( PC ) @ for the MC68000, @ ( d sub 16 , PC ) @ for the MC68020
- .PP
- This mode requires one word of extension. The address of the operand is the sum
- of the address in the program counter and the sign extended 16-bit displacement
- integer in the extension word. The value in the program counter is the
- address of the extension word.
- .NH 4
- Program Counter With Index
- .IP Syntax: 8
- @ d sub 8 ( PC , X sub n .size ) @ for the MC68000, @ ( d sub 8 , PC, X sub n .size ) @ for the MC68020
- .PP
- This mode requires one word of extension as described under
- .I
- Address Register Indirect With Index.
- .R
- The address of the operand is the sum of the value in the
- program counter, the possibly sign extended index register and the sign
- extended 8-bit displacement integer in the extension word.
- The value in the program counter is the address of the extension word.
- .NH 4
- Immediate Data
- .IP Syntax: 8
- @ "\#data" @
- .PP
- This addressing mode requires either one or two words of extension, depending
- on the size of the operation;
- .IP
- byte operation - the operand is in the low order byte of extension word;
- .IP
- word operation - the operand is in the extension word;
- .IP
- long operation - the operand is in the two extension words, the high order
- 16-bits are in the first extension word, the low order 16-bits in the second.
- .NH 3
- Extra MC68020 addressing modes
- .PP
- The MC68020 has three more addressing modes. These modes all use a displacement
- (some even two), an address register and an index register. Instead of the
- address register one may also use the program counter. Any of these
- may be omitted. If all addends are omitted the processor creates an
- effective address of zero. All of these three modes require at least one
- extension word, the
- .I
- Full Format Extension Word,
- .R
- which specifies:
- .IP 1.
- the index register number (0-7);
- .IP 2.
- the index register type (address or data register);
- .IP 3.
- the size of the index (only low order part or the whole register)
- .IP 4.
- a scale factor. This is a number from 0 to 3 which specifies how many bits
- the contents of the index register is to be shifted to the left before being
- used as an index;
- .IP 5.
- a flag that specifies whether the base (address) register is to be added or
- to be suppressed;
- .IP 6.
- a flag that specifies whether to add or suppress the index operand;
- .IP 7.
- two bits that specify the size of the base displacement (null, word or long);
- .IP 8.
- three bits that in combination with (6) above specify which of the three
- addressing modes (described below) to use and, if used, the size of the
- outer displacement (null, word or long).
- .IP N.B.
- All modes mentioned above for the MC68000
- that use an index register may have this register
- scaled (only when using the MC68020).
- .PP
- The three extra addressing modes are:
- .NH 4
- Address Register Indirect With Index (Base Displacement)
- .IP Syntax: 8
- @ ( bd , A sub n , X sub n .size*scale ) @ (MC68020 only)
- .PP
- The address of the operand is the sum of the contents of the address register,
- the scaled contents of the possibly scaled index register and the possibly
- sign extended base displacement. When the program counter is used instead
- of the address register, the value in the program counter is the address
- of the full format extension word. This mode requires one or two more extension
- words when the size of the base displacement is word or long respectively.
- .PP
- Note that without the index operand, this mode is an extension of the
- .I
- Address Register Indirect With Displacement
- .R
- mode; when using the MC68020 one is no longer limited to a 16-bit displacement.
- Also note that with the index operand added, this mode is an extension
- of the
- .I
- Address Register Indirect With Index
- .R
- mode; when using the MC68020 one is no longer limited to an 8-bit displacement.
- .NH 4
- Memory Indirect Post-Indexed
- .IP Syntax: 8
- @ ( [ bd , A sub n ] , X sub n .size*scale , od ) @ (MC68020 only)
- .PP
- This mode may use an outer displacement. First an intermediate memory
- address is calculated by adding the contents of the address register and
- the possibly sign extended base displacement. This address is used
- for in indirect memory access of a long word, followed by adding
- the index operand (scaled and possibly signed extended). Finally the
- outer displacement is added to yield the address of the operand.
- When the program counter is used, the value in the program counter is the
- address of the full format extension word.
- .NH 4
- Memory Indirect Pre-Indexed
- .IP Syntax: 8
- @ ( [ bd , A sub n , X sub n .size*scale ] , od ) @ (MC68020 only)
- .PP
- This mode may use an outer displacement. First an intermediate memory
- address is calculated by adding the contents of the address register,
- the scaled contents of the possibly sign extended index register and
- the possibly sign extended base displacement. This address is used
- for an indirect memory access of a long word, followed by adding
- the outer displacement to yield the address of the operand.
- When the program counter is used, the value in the program counter is the
- address of the full format extension word.
- .NH 3
- Addressing modes used in the table
- .PP
- Not all addressing modes mentioned above are used in code generation. It is
- clear that none of the modes that use the program counter PC can be used,
- since at code generation time nothing is known about the value in PC.
- Also some of the possibilities of the three MC68020 addressing modes are not
- used; e.g. it is possible to use a
- .I
- Data Register Indirect
- .R
- mode, which actually is the
- .I
- Address Register Indirect With Index
- .R
- mode, with the address register and the displacement left out. However
- such a mode would require two extra bytes for the full format extension word,
- and it would also be much slower than using
- .I
- Address Register Indirect.
- .R
- For this kind of reasons several possible addressing modes are not used in the
- generation of code.
- In the table address registers are only used for holding addresses, and
- for index registers only data registers are used.
- .NH
- The M68000 and MC68020 back end table
- .PP
- The table itself has to be run through the C preprocessor
- before it can be used to generate
- the back end (called
- .I
- code generator
- .R
- or
- .I cg
- for short). When no flags are given to
- the preprocessor an MC68020 code generator is produced; for the MC68000
- code generator one has to run the table through the preprocessor using the
- .I -Dm68k4
- flag.
- .PP
- The table is designed as described in [4]. For the overall design of a back
- end table one is referred to this document. This section only deals
- with problems encountered in writing the table and other things worth noting.
- .NH 2
- Constant Definitions
- .PP
- Wordsize and pointersize (EM_WSIZE and EM_PSIZE respectively) are defined
- as four (bytes). EM_BSIZE, the hole between AB (the parameter base) and
- LB (the local base), is eight bytes: only
- the return address and the localbase are saved.
- .NH 2
- Properties
- .PP
- Since Hans van Staveren in his document [4] clearly states that
- .I cg
- execution time is negatively influenced by the number of properties, only
- four different properties have been defined. Besides, since the registers
- really are multifunctional, these four are really all that are needed.
- .NH 2
- Registers
- .PP
- The table uses register variables: @ D sub 3 @ - @ D sub 7 @ are used as general register
- variables, and address registers @ A sub 2 @ - @ A sub 5 @ are used as pointer register
- variables. @ A sub 6 @ is reserved for the localbase.
- .NH 2
- Tokens
- .PP
- At first glance one might wonder about the amount of tokens, especially
- for the MC68020, considering the small amount of different addressing modes.
- However, the last three addressing modes mentioned for the MC68020 may
- omit any of the addends, and this leads to a large amount of different tokens.
- I did consider the possibility of enlarging the number of tokens and sets
- even further, because there might be assemblers that don't handle displacements
- of zero optimally (they might generate a 2 byte extension word holding zero).
- The small profit in bytes in the generated code
- however does not justify the increase
- in size of the token section, the set section and the patterns section,
- so this idea was not developed any further.
- .PP
- The timing cost of the tokens may be incorrect for some MC68000 tokens.
- This is because the MC68000 uses a 16-bit data bus which causes the need
- of two separate memory accesses for getting 32-bit operands.
- .NH 3
- Token names
- .PP
- The amount of tokens and the limited capability of the authors imagination
- might have caused the names of some tokens not to be very clarifying.
- Some information about the names may be in place here.
- .PP
- Whenever part of a token name is in capitals that part is memory indirected
- (i.e. in square brackets). In token names
- .I OFF
- and
- .I off
- mean an offsetted address register, so an address register with a displacement
- (either base displacement or outer displacement).
- .I
- IND, ind
- .R
- and
- .I index
- stand for indexed, or index register.
- .I ABS
- and
- .I abs
- stand for absolute, which actually is just a displacement (base or outer).
- These `rules' only apply to names of tokens that represent actual operands.
- There are also tokens that represent addresses of operands. These
- (with a few exceptions) contain
- .I
- regA, regX
- .R
- and
- .I con
- as parts of there names, which stand for address register, index register and
- displacement (always base displacement) respectively. If the address to which
- the token refers uses memory indirection, that part of the name comes first
- (in small letters), followed by an underscore. The memory indirection part
- follows the `rules' for operand token names.
- .PP
- Of course there are exceptions to these `rules' but in those cases the names
- are self explanatory.
- .PP
- Two special cases:
- .I ext_regX
- is the name of the token that represents the
- address of an absolute indexed operand, syntax @ ( bd , X sub n .size*scale ) @;
- .I regX
- does not represent any real mode, but is used with EM array instructions and
- pointer arithmetic.
- .NH 3
- Special tokens for the MC68000
- .PP
- The MC68000 requires two extra tokens, which are called
- .I t_regAcon
- and
- .I
- t_regAregXcon.
- .R
- They are necessary because
- .I regAcon
- can only have a 16-bit displacement on the MC68000, and
- .I regAregXcon
- uses only 8 bits for its displacement. To prevent these addressing modes to
- be used with displacements that are too large, the extra tokens are needed.
- Whenever the displacements become too large and they need
- to be used in the generation
- of assembly code, these tokens are transformed into other tokens.
- To prevent the table from becoming too messy I defined
- .I t_regAcon
- and
- .I t_regAregXcon
- to be identical to
- .I regAcon
- and
- .I regAregXcon
- respectively for the MC68020.
- .NH 2
- Sets
- .PP
- Most set names used in the table are self explanatory, especially to the reader
- who is familiar with the four addressing categories as mentioned in [5]:
- .I
- data, memory, alterable
- .R
- and
- .I
- control.
- .R
- In the sets definition part some sets are defined that are not used elsewhere in
- the table, but are only used to be part of the definition of
- some other set. This keeps the
- set definition part from getting too unreadable.
- .PP
- The sets called
- .I imm_cmp
- consist of all tokens that can be used to compare with a constant.
- .NH 2
- Instructions
- .PP
- Only the instructions that are used in code generation are listed here.
- The first few instructions are meant especially for the use with register
- variables. The operand LOCAL used here refers to a register variable.
- The reader may not conclude that these operations are also allowed on
- ordinary locals. The space and timing cost of these instructions have been
- adapted, but the use of the word LOCAL for register variables causes these cost
- to be inaccurate anyway.
- .PP
- The
- .I killreg
- instruction, which generates a comment in the assembly language output and
- which is meant to let
- .I cg
- know that the data register operand has its contents destroyed,
- needs some explaining but this explanation is better in place
- in the discussion of groups 3 and 4 of the section about patterns.
- .PP
- The timing cost of the instructions are probably not very accurate for the
- MC68020 because the MC68020 uses an instruction cache and prefetch. The
- cost used in the table are the `worst case cost' as mentioned in section 9
- of [5].
- .NH 2
- Moves
- .PP
- These are all pretty straightforward, except perhaps when
- .I t_regAcon
- and
- .I t_regAregXcon
- are used. In these cases the size of the displacement has to be checked
- before moving. This also applies to the stacking rules and the coercions.
- .NH 2
- Tests
- .PP
- These three tests (one fore each operation size) could not be more
- straightforward than they are now.
- .NH 2
- Stackingrules
- .PP
- The only peculiar stackingrule is the one for
- .I
- regX.
- .R
- This token is only used with EM array instructions and
- with pointer arithmetic. Whenever it is put
- on the fake stack, some EM instructions are left in the instruction stream
- to remove this token. Consequently it should never have to be stacked. However
- the
- .I
- code generator generator
- .R
- (or
- .I cgg
- for short)
- complained about not having a stackingrule for this token, so it had to
- be added nevertheless.
- .NH 2
- Coercions
- .PP
- These are all straightforward. There are no splitting coercions since
- the fake stack never contains any tokens that can be split.
- There are only two unstacking coercions.
- The rest are all transforming coercions. Almost all coercions transform
- tokens into either a data register or an address register, except in the
- MC68000 part of the table the
- .I t_regAcon
- and
- .I t_regAregXcon
- tokens are transformed into real
- .I regAcon
- and
- .I regAregXcon
- tokens with displacements that are properly sized.
- .NH 2
- Patterns
- .PP
- This is the largest part of the table. It is subdivided into 17 groups.
- We will take a closer look at the more interesting groups.
- .NH 3
- Group 0: rules for register variables
- .PP
- This group makes sure that EM instructions using register variables are
- handled efficiently. This group includes: local loads and
- stores; arithmetic, shifts and logical operations on locals and indirect locals
- and pointer handling, where C expressions like
- .I
- *cp++
- .R
- are handled. For such an expression there are several EM instruction
- sequences the front end might generate. For an integer pointer e.g.:
- .DS
- .B
- lol lol adp stl loi $1==$2 && $1==$4 && $3==4 && $5==4
- .I
- .DE
- or
- .DS
- .B
- lol loi lol adp stl $1==$3 && $3==$5 && $2==4 && $5==4
- .I
- .DE
- or perhaps even
- .DS
- .B
- lil lol adp stl $1==$2 && $2==$4 && $3==4
- .I
- .DE
- Each of these is included, since which one is generated is is up to the front
- end. If the front end is consistent this will mean that some of these patterns
- will never be used in code generation. This might seem a waist, but anyone
- who thinks that will certainly change his mind when his new C front end
- generates a different EM instruction sequence.
- .NH 3
- Groups 1 and 2: load and store instructions
- .PP
- In these groups
- .B lof
- and
- .B stf
- ,
- .B loi
- and
- .B sti
- ,
- .B ldf
- and
- .B sdf
- are the important instructions.
- These are the large parts in this group, especially the
- .B loi
- and
- .B sti
- instructions, because they come in three basic sizes (byte, word and long).
- Note that with these instructions in the MC68000 part the
- .I exact
- is omitted in front of
- .I regAcon
- and
- .I
- regAregXcon.
- .R
- This makes sure that
- .I t_regAcon
- and
- .I t_regAregXcon
- are transformed into proper tokens before they are used as addresses.
- .PP
- Also note that the
- .I regAregXcon
- token is completely left out from the
- \fBlof\fR, \fBstf\fR, \fBldf\fR and \fBsdf\fR
- instruction handling. This is because the sum of the token displacement
- and the offset provided in the instruction cannot be checked and is likely
- to exceed 8 bits. Unfortunately
- .I cgg
- does not allow the inspection of subregisters of tokens that are on the
- fake stack. This same problem might also occur with the
- .I regAcon
- token, but this is less likely because it
- uses 16-bit displacements. Besides if it would have been left out the
- \fBlof\fR, \fBstf\fR, \fBldf\fR and \fBsdf\fR
- instructions would have been handled considerably less efficient.
- .NH 3
- Groups 3 and 4: integer and unsigned arithmetic
- .PP
- EM instruction
- .B sbi
- also works with address registers, because the
- .B cmp
- instruction in group 12 is replaced by \fBsbi 4\fR.
- .PP
- For the MC68000 \fBmli\fR, \fBmlu\fR, \fBdvi\fR, \fBdvu\fR, \fBrmi\fR
- and \fBrmu\fR are handled
- by library routines. This is because the MC68000 has only 16-bit multiplications
- and divisions.
- .PP
- The MC68020 does have 32-bit multiplications and divisions, but for the
- .B rmi
- and
- .B rmu
- EM instructions peculiar things happen anyway: they generate the
- .I killreg
- instruction. This is necessary because the data register that
- first held the dividend now holds the quotient; the original contents are
- destroyed without
- .I cg
- knowing about it (the destruction of the two registers that make up the
- .I DREG_pair
- token couldn't be noted in the instructions part of the table).
- To let
- .I cg
- know that these contents are destroyed, we have to use this `pseudo instruction'
- from lack of a better solution.
- .NH 3
- Group 5: floating point arithmetic
- .PP
- Since floating point arithmetic is not implemented traps will be generated here.
- .NH 3
- Group 6: pointer arithmetic
- .PP
- This also is a very important group, along with groups 1 and 2. The MC68020
- has many different addressing modes and if possible they should be used in
- the generation of assembly language.
- .PP
- The
- .I regX
- token is generated here too. It is meant to make efficient use of the
- MC68020 possibility of scaling index registers.
- .PP
- Note that I would have liked one extra pattern to handle C-statements
- like
- .DS
- .I
- pointer += expr ? constant1 : constant2;
- .R
- .DE
- efficiently. This pattern would have looked like:
- .DS
- pat ads
- with const
- leaving adp %1.num
- .DE
- but when
- .I cg
- is coming to the EM replacement part, the constant has already been removed
- from the fake stack, causing
- .I %1.num
- to have a wrong value.
- .NH 3
- Group 9: logical instructions
- .PP
- The EM instructions \fBand\fR,
- .B ior
- and
- .B xor
- are so much alike that procedures can be used here, except for the
- .B
- xor $1==4
- .R
- instruction, because the MC68000
- .I eor
- instruction does not allow as many kinds of operands as
- .I and
- and
- .I
- or.
- .R
- .NH 3
- Group 11: arrays
- .PP
- This group also tries to make efficient use of the available addressing modes,
- but it leaves the actual work to group 6 mentioned above.
- .PP
- The
- .I regX
- token is also generated here. In this group this token is very useful for
- handling array instructions for arrays with one, two, four or eight byte
- elements; the array index goes into the index register, which can then
- be scaled appropriately. An offset is used when the
- first array element has an index other than zero.
- .PP
- I would have liked some extra patterns here too but they won't work
- for the same reasons as explained in the discussion of group 6.
- .NH 3
- Group 14: procedure calls instructions
- .PP
- The function return area consists of registers @ D sub 0 @ and @ D sub 1 @.
- .NH 3
- Group 15: miscellaneous instructions
- .PP
- In many cases here library routines are called. These will be discussed
- later.
- .PP
- Two special EM instructions are included here: \fBdch\fR, and \fBlpb\fR.
- I don't know when they are generated by a front end, but these
- instructions were also in the back end table for the PDP. In the PDP table
- these instructions were replaced by
- .B
- loi 4
- .R
- and
- .B
- adp 8
- .R
- respectively. I included them both, since they couldn't do any harm.
- .NH 3
- Extra group: optimalization
- .PP
- This group is handling EM patterns with more than one instruction. This group
- is not absolutely necessary but it makes the generation of code
- more efficient. Among the things that are handled here are: arithmetic and
- logical operations on locals, externals and indirect locals; shifting
- of locals, externals and indirect locals by one; some pointer arithmetic; tests
- in combination with logical and's and or's or with branches. Finally
- there are sixteen patterns about divisions that could be handled more
- efficiently by right shifts and which I think should be handled by the
- peephole optimizer (since it also handles
- the same patterns with multiplication).
- .NH
- The library routines
- .PP
- The table is supplied with two separate libraries: one for the MC68000 and one
- for the MC68020. The MC68000 uses a couple more routines than the MC68020
- because it doesn't have 32-bit division and multiplication.
- .PP
- The routines that need to pop their operands first store their return address.
- Routines that need other register besides @ D sub 0 @-@ D sub 2 @ and @ A sub 0 @-@ A sub 1 @ first store
- the original contents of those registers. @ D sub 0 @-@ D sub 2 @ and @ A sub 0 @-@ A sub 1 @ do not have
- to be saved because if they contain anything useful, their contents
- are pushed on the stack before the routine is called.
- .PP
- The
- .I .trp
- routine just prints a message stating the trap number and exits (except
- of course when that particular trap number is masked). Usually higher
- level languages use their own trap handling routines.
- .PP
- The
- .I .mon
- routine doesn't do anything useful at all. It just prints a message stating that
- the specified system call is not implemented and then exits. Front ends
- usually generate calls to special routines rather than the EM
- instruction \fBmon\fR.
- These routines have to be supplied in another library. They
- may be system dependent (e.g. the MC68000 machine this table was tested on
- first moves the parameters to registers, then moves the system call number
- to @ D sub 0 @ and then executes
- .I
- trap #0,
- .R
- whereas the MC68020 machine this table was tested on required the parameters
- to be on the stack rather than in registers). Therefor this library is not
- discussed here.
- .PP
- The
- .I .printf
- routine is included for EM diagnostic messages. It can print strings using %s,
- 16-bit decimal numbers using %d and 32-bit hexadecimal numbers using %x.
- .PP
- The
- .I .strhp
- routine stores a new EM heap pointer, and sometimes it needs to allocate more
- heap space. This is done by calling the system call routine \fI_brk\fR.
- Chunks of 1K bytes are allocated, but this can easily be changed into
- larger or smaller chunks.
- .PP
- The MC68000 library also contains a routine to handle the EM instruction \fBrck\fR.
- The MC68020 has an instruction
- .I cmp2
- that is specially meant for range checking so the MC68020 library can do without
- that routine.
- .PP
- The MC68000 library has two multiplication routines, one for unsigned and the other
- for signed multiplication. The one for signed multiplication
- first tests the sizes of the operands, to see if it can perform
- the 16 bit machine instruction instead of the routine. If not, it considers
- it's two operands being two digit numbers in a 65535-radix system. It
- uses the 16-bit unsigned multiply instruction
- .I mulu
- three times (it does not calculate the high order result),
- and adds up the intermediary results the proper way. The signed
- multiplication routine calculates the sign of the result, calculates
- the result as it it were an unsigned multiplication, and
- adjusts the sign of the result. Here testing
- the operands for there sizes would be less simple, because the operands
- are signeds; so that is not done here.
- .PP
- The MC68000 library also has two division routines. The routine for unsigned
- division uses the popular algorithm, where the divisor is shifted out and
- the quotient shifted in. The signed division routine calculates the sign of
- both the quotient and the remainder, calls the unsigned division routine
- and adjusts the signs for the quotient and the remainder.
- .PP
- The
- .I .nop
- routine is included for testing purposes. This routine prints the line
- number and the value in the stack pointer. Calls to this routine
- are generated by the EM instruction \fBnop\fR, which is ordinarily
- left out by the peephole optimizer.
- .NH
- Testing the table
- .PP
- There are special test programs available for testing back end tables.
- First there is the EM test set, which tests most EM instructions, making
- good use of the
- .B nop
- instruction. Then there are the Pascal and C test programs. The Pascal
- test programs report errors, which makes it relatively easy
- to find out what was wrong in the table. The C test programs just
- generate some output, which then has to be compared to the expected
- output. Differences are
- not only caused by errors but also e.g. by the use of four
- byte integers and unsigneds (which this table does),
- the use of signed characters
- instead of unsigned characters (the C front end I used generated signed
- characters) or because the back end
- does not support floating point.
- These differences have to be `filtered out' to reveal
- the differences caused by actual errors in the back end table.
- These errors then have to be found out by examining the assembly code, for
- no proper diagnostic messages are generated.
- .PP
- After these three basic tests there still remain a number of patterns that
- haven't been tested yet. Fortunately
- .I cgg
- offers the possibility of generating a special
- .I cg
- that can print a list of patterns that haven't been used in
- code generation yet.
- For these patterns the table writer has to write his own test programs.
- This may complicate things a bit because errors may now be caused by
- errors in the back end table as well as errors in the test programs.
- The latter happened quite often to me, because I found EM
- to be an uncomfortable programming language (of course it isn't meant to
- be a programming language, but an intermediary language).
- .PP
- There still remain a couple of patterns in this table that haven't been tested
- yet. However these patterns all have very similar cases that have been
- tested (an example of this is mentioned in the section on group 0
- of the patterns section of the table). Some patterns have to
- do with floating point numbers. These EM instructions all generate
- traps, so they didn't all have to be tested. The two instructions
- .B dch
- and
- .B lpb
- haven't been tested in this table, but since they only use EM replacement
- and they have been tested in the PDP back end table, these two should
- be all right.
- .NH
- Performance of the back end
- .PP
- To test the performance of the back end I gathered a couple of
- C programs and compiled them on the machines I used to test the back ends on.
- I compiled them using the C compiler that was available there and
- I also compiled them using the back end. I then compared the sizes
- of the text segments in the object files.
- The final results of these comparisons are in fig. 1 and fig. 2.
- .KF
- .TS
- center box;
- cfI s s s s s
- c s s s s s
- c c | c s | c s
- c c | c s | c s
- c | c | c c | c c
- l | n | n n | n n.
- Differences in text segment sizes for the MC68000
- parts of the back end compiled by itself
- _
- original old m68k4 new MC68000
- compiler (100%) back end back end
- _
- name size size perc. size perc.
- _
- codegen.c 13892 16224 116.7% 12860 92.5%
- compute.c 4340 4502 103.7% 4530 104.3%
- equiv.c 680 662 97.3% 598 87.9%
- fillem.c 8016 7304 91.1% 6880 85.8%
- gencode.c 1356 1194 88.0% 1130 83.3%
- glosym.c 224 202 90.1% 190 84.8%
- main.c 732 672 91.8% 634 86.6%
- move.c 1876 1526 81.3% 1410 75.1%
- nextem.c 1288 1594 123.7% 1192 92.5%
- reg.c 1076 1014 94.2% 916 85.1%
- regvar.c 1352 1188 87.8% 1150 85.0%
- salloc.c 1240 1100 88.7% 1024 82.5%
- state.c 628 600 95.5% 532 84.7%
- subr.c 6948 6382 91.8% 5680 81.7%
- =
- averages 2939 3155 95.8% 2766 86.6%
- .TE
- .DS C
- fig 1.
- .DE
- .KE
- .KF
- .TS
- center box;
- cfI s s s
- cfI s s s
- c s s s
- c s s s
- c c | c s
- c c | c s
- c | c | c c
- l | n | n n.
- Differences in text segment sizes
- for the MC68020
- parts of the back end
- compiled by itself
- _
- original MC68020
- compiler (100%) back end
- _
- name size size perc.
- _
- codegen.c 12608 12134 96.2%
- compute.c 4624 4416 95.5%
- equiv.c 572 504 88.1%
- fillem.c 7780 6976 89.6%
- gencode.c 1320 1086 82.2%
- glosym.c 228 182 79.8%
- main.c 736 596 80.9%
- move.c 1392 1280 91.9%
- nextem.c 1176 1066 90.6%
- reg.c 1052 836 79.4%
- regvar.c 1196 968 80.9%
- salloc.c 1200 932 77.6%
- state.c 580 528 91.0%
- subr.c 6136 5268 85.8%
- =
- averages 2900 2627 86.4%
- .TE
- .DS C
- fig 2.
- .DE
- .KE
- Fig. 1 also includes results of an old m68k4 back end (a back end
- for the MC68000 with four byte word and pointersize). The table for
- this back end was given to me as an example, but I thought it didn't make
- good use of the MC68000's addressing capabilities, it hardly did any
- optimalization, and it sometimes even
- generated code that the assembler would not swallow.
- This was sufficient reason for me to write a completely new table.
- .PP
- The results from the table may not be taken too seriously. The sizes measured
- are the sizes of the text segments of the user programs, i.e. without the
- inclusion of library routines. Of course these segments do contain calls
- to these routines. Another thing is that the
- .I rom
- segment may be included in the text segment (this is why the
- results for the MC68000 for
- .I compute.c
- look so bad).
- .PP
- Some other things must be said about these results.
- The quality of EM code
- generated by the C front end is certainly not optimal. The front end
- uses temporary locals (extra locals that are used to evaluate expressions)
- far too quickly: for a simple C expression like
- .DS
- .I
- *(pointer) += constant
- .R
- .DE
- where
- .I pointer
- is a register variable, the C front end generates (for obscure reasons)
- a temporary local that holds the contents of \fIpointer\fR. This way
- the pattern for
- .DS
- .B
- loc lil adi sil $2==$4 && $3==4
- .R
- .DE
- for register variables is not used and longer, less efficient
- code is generated. But even in spite of this, the back end seems to
- generate rather compact code.
- .NH
- Some timing results
- .PP
- In order to measure the performance of the code generated by the back end
- some timing tests were done. The reason I chose these particular tests is
- that they were also done for many other back ends; the reader can compare
- the results if he so wishes (of course comparing the results only
- show a global difference in speed of the various machines; it doesn't
- show whether some back end generates relatively better code than another).
- .PP
- On the MC68000 machine the statements were executed one million times.
- On the MC68020 machine the statements had to be executed four million times
- because this machine was so fast that timing results would be very
- unreliable if the statements were executed only one million times.
- .PP
- For testing I used the following C test program:
- .DS
- .I
- main()
- {
- int i, j, ...
- ...
- for (i=0; i<1000; i++)
- for (j=0; j<1000; j++)
- STATEMENT;
- }
- .R
- .DE
- where
- .I STATEMENT
- is any of the test statements or the empty statement. For the MC68020
- tests I used 2000 instead of 1000.
- The results of the test with the empty statement were used to calculate
- the execution times of the other test statements.
- .PP
- Figures 3 and 4 show many results. For each machine actually two tests were
- done: one with register variables, and the other without them.
- I noticed that the original C compilers on both machines did not generate
- the use of register variables, unless specifically requested. The
- back end uses register variables when and where they are profitable, even
- if the user did not ask for them.
- .KF
- .TS
- center box;
- cfI s s s s
- c s s s s
- c | c s | c s
- cw(1.5i) | c c | c c
- c | c c | c c
- lp-2fI | n n | n n.
- timing results for the MC68000
- times in @ mu @seconds
- _
- test statement without register variables with register variables
- _
- original new MC68000 original new MC68000
- C compiler back end C compiler back end
- _
- int1=0; 2.8 2.7 0.5 0.5
- int1=int2-1; 4.1 4.1 1.3 1.3
- int1=int1+1; 4.1 4.1 1.3 1.3
- int1=int2*int3; 40.0 40.5 36.2 36.8
- T{
- int1=(int2<0);
- \/*true*/
- T} 5.5 7.3 2.0 4.5
- T{
- int1=(int2<0);
- \/*false*/
- T} 4.7 8.5 2.8 5.6
- T{
- int1=(int2<3);
- \/*true*/
- T} 6.2 7.7 2.6 5.4
- T{
- int1=(int2<3);
- \/*false*/
- T} 5.4 8.9 3.6 6.5
- T{
- .na
- int1=((int2>3)||(int2<3));
- \/* true || false */
- T} 6.0 7.8 3.4 5.4
- T{
- .na
- int1=((int2>3)||(int2<3));
- \/* false || true */
- T} 9.1 10.2 5.7 7.1
- T{
- .na
- switch (int1) {
- case 1: int1=0; break;
- case 2: int1=1; break;
- }
- T} 6.3 17.8 5.3 14.0
- T{
- .na
- if (int1=0) int2=3;
- \/*true*/
- T} 5.1 4.7 1.3 1.3
- T{
- .na
- if (int1=0) int2=3;
- \/*false*/
- T} 2.2 2.1 1.9 1.1
- while (int1>0) int1=int1-1; 2.2 2.1 1.1 1.1
- int1=a[int2]; 6.8 6.7 4.0 3.1
- p3(int1); 14.3 11.1 13.4 10.0
- int1=f(int2); 17.7 14.5 14.8 11.7
- s.overhead=5400; 2.8 2.7 2.9 2.7
- .TE
- .DS C
- Fig. 3
- .DE
- .KE
- .KF
- .TS
- center box;
- cfI s s s s
- c s s s s
- c | c s | c s
- cw(1.5i) | c c | c c
- c | c c | c c
- lp-2fI | n n | n n.
- timing results for the MC68020
- times in @ mu @seconds
- _
- test statement without register variables with register variables
- _
- original new MC68020 original new MC68020
- C compiler back end C compiler back end
- _
- int1=0; .25 .25 .15 .15
- int1=int2-1; 1.3 1.3 .38 .38
- int1=int1+1; 1.2 .90 .38 .15
- int1=int2*int3; 4.4 4.2 3.0 3.1
- T{
- int1=(int2<0);
- \/*true*/
- T} 1.6 2.7 1.1 2.3
- T{
- int1=(int2<0);
- \/*false*/
- T} 1.9 2.9 .80 2.1
- T{
- int1=(int2<3);
- \/*true*/
- T} 1.7 2.8 1.2 2.6
- T{
- int1=(int2<3);
- \/*false*/
- T} 2.1 3.0 .85 2.3
- T{
- .na
- int1=((int2>3)||(int2<3));
- \/* true || false */
- T} 2.1 3.1 1.2 2.5
- T{
- .na
- int1=((int2>3)||(int2<3));
- \/* false || true */
- T} 3.4 4.2 1.8 3.2
- T{
- .na
- switch (int1) {
- case 1: int1=0; break;
- case 2: int1=1; break;
- }
- T} 2.7 8.0 2.0 6.9
- T{
- .na
- if (int1=0) int2=3;
- \/*true*/
- T} 1.2 1.3 .63 .63
- T{
- .na
- if (int1=0) int2=3;
- \/*false*/
- T} 1.7 1.6 .50 .53
- while (int1>0) int1=int1-1; 1.2 1.3 .55 .53
- int1=a[int2]; 1.8 1.8 1.0 1.0
- p3(int1); 14.8 5.5 14.1 5.0
- int1=f(int2); 16.3 6.6 15.2 5.9
- s.overhead=5400; .48 .48 .50 .50
- .TE
- .DS C
- Fig. 4
- .DE
- .KE
- .PP
- The reader may have noticed that on both machines the back end seems
- to generate considerably slower code for tests where a `condition' is
- used in the rhs of an assignment statement. This is in fact not true: it is
- the front end that generates bad code. Two examples: for the C statement
- .DS
- .I
- int1 = (int2 < 0);
- .R
- .DE
- the front end generates the following code for the rhs (I
- used arbitrary labels):
- .DS
- .B
- lol -16
- zlt *10
- loc 0
- bra *11
- 10
- loc 1
- 11
- .R
- .DE
- while in this case (to my opinion) it should have generated
- .DS
- .B
- lol -16
- tlt
- .R
- .DE
- which is much shorter. Another example: for the C statement
- .DS
- .I
- int1 = (int2 < 3);
- .B
- .DE
- the front end generates for the rhs
- .DS
- .B
- lol -16
- loc 3
- blt *10
- loc 0
- bra *11
- 10
- loc 1
- 11
- .R
- .DE
- while a much better translation would be
- .DS
- .B
- lol -16
- loc 3
- cmi 4
- tlt
- .R
- .DE
- .PP
- Another statement that the back end seems to generate slower code for is
- the C switch statement. This is true, but it is also caused by
- the way these things are done in EM. EM uses the
- .B csa
- or
- .B csb
- instruction, and for these two I had to use library routines. On larger
- switch statements the
- .I .csa
- routine will perform relatively better.
- .PP
- The back end generates considerably faster code for procedure and function
- calls, especially in the MC68020 case, and also for the C statement
- .DS
- .I
- int1 = int1 + 1;
- .R
- .DE
- The original C compilers use the same method for this instruction
- as for
- .DS
- .I
- int1 = int2 - 1;
- .R
- .DE
- they perform the addition in a scratch register, and then store the
- result. For the former C statement this is not necessary, because
- the MC68000 and MC68020 have an instruction that can add constants
- to almost anything (in this case: to locals). The MC68000 and MC68020
- back ends do use this instruction.
- .NH
- Some final remarks
- .PP
- As mentioned a few times before, the C front end compiler does not
- generate optimal code and as a consequence of this the
- back end does not always generate optimal code. This is especially
- the case with temporary locals, which the front end generates much
- too quickly, and also with conditional expressions that are
- used in the rhs of an assignment statement (fortunately this is not
- needed so much).
- .PP
- If
- .I cgg
- would have been able to accept operands separated by any character
- instead of just by commas (in the instruction definitions part),
- I wouldn't have had the need of the
- .I killreg
- pseudo instruction. It would also be handy to have
- .I cgg
- accept all normal C operators. At the moment
- .I cgg
- does not accept binary ands, ors and exors, even though in [4]
- it is stated that
- .I cgg
- does accept all normal C operators. As it happens I did not need the
- binary operators, but at some time in developing the table I thought
- I did.
- .PP
- I would also like
- .I cg
- to do more with the condition codes information that is supplied with
- each instruction in the instruction definitions section of the table.
- Sometimes
- .I cg
- generates test instructions which actually were not necessary. This
- of course causes the generated
- programs to be slightly larger and slightly slower.
- .PP
- In spite of the few minor shortcomings mentioned above I found
- .I cgg
- a very comfortable tool to use.
- .SH
- References
- .PP
- .IP [1]
- T. B. Steel Jr.,
- .I
- UNCOL: The myth and the Fact,
- .R
- in Ann. Rev. Auto. Prog.,
- R. Goodman (ed.), Vol. 2 (1969), pp 325 - 344
- .IP [2]
- A. S. Tanenbaum, H. van Staveren, E. G. Keizer, J. W. Stevenson,
- .I
- A practical toolkit for making portable compilers,
- .R
- Informatica Report 74, Vrije Universiteit, Amsterdam, 1983
- .IP [3]
- A. S. Tanenbaum, H. van Staveren, E. G. Keizer, J. W. Stevenson,
- .I
- Description of an experimental machine architecture for use with
- block structured languages,
- .R
- Informatica Report 81, Vrije Universiteit, Amsterdam, 1983
- .IP [4]
- H. van Staveren
- .I
- The table driven code generator from the Amsterdam Compiler Kit,
- Second Revised Edition,
- .R
- Vrije Universiteit, Amsterdam
- .IP [5]
- .I
- MC68020 32-bit Microprocessor User's Manual,
- .R
- Second Edition,
- Motorola Inc., 1985, 1984
- .IP [6]
- .I
- MC68000 16-bit Microprocessor User's Manual,
- Preliminary,
- .R
- Motorola Inc., 1979
|