% Combined i186/Z80 design\documentclass{article}% Too long to type :)\newcommand{\tosh}{Toshiba TLCS-900H}\begin{document}\title{Combined i186/Z80 backend design}\author{Michael Hope michaelh@earthling.net.nz}\date{\today}\maketitle\begin{abstract}There is much similarity between the Zilog Z80, Nintendo GBZ80, Inteli186, and \tosh processors.  This document describes the design of abackend consisting of a register allocator and set of extendable codegenerators for SDCC which can target all of these processors.\end{abstract}\section{Motivation}The primary motivation is to add a i186 backend to SDCC, and in theprocess come to understand register allocation.  The secondary goal isto attempt to combine the common parts from the Z80 and i186 backendsto make both easier to maintain.  In the 'would be nice' category isadding support for the \tosh.\section{Processor descriptions}\subsection{Zilog Z80}\begin{tabular}{l|l|l}	Name	& Parts	& Notes \\ \hline	AF	& A	& Accumulator and flags.  Unusable as a pair. \\ \hline	BC	& B, C	& \\ \hline	DE	& D, E	& \\ \hline	HL	& H, L	& \\ \hline	IX	& None	& Index register. \\ \hline	IY	& None	& Index register. \\\end{tabular}The Z80 also has a switchable alternate register set AF', BC', DE',and HL' which are not accessible directly.  It is assumed that it istoo hard to track these to make it worthwhile.  IX and IY can be splitat the byte level by using undocumented instructions.  While thiswould make them more usable as general purpose registers, it isignored for compatibility.\subsection{Nintendo GBZ80}The GBZ80 is basically a Z80 less the index registers and thealternate register set. \\\begin{tabular}{l|l|l}	Name	& Parts	& Notes \\ \hline	AF	& A	& Accumulator and flags.  Unusable as a pair. \\ \hline	BC	& B, C	& \\ \hline	DE	& D, E	& \\ \hline	HL	& H, L	& \\\end{tabular}\subsection{Intel i186}\begin{tabular}{l|l|l}	Name	& Parts		& Notes \\ \hline	AX	& AH, AL	& Accumulator. \\ \hline	BX	& BH, BL	& \\ \hline	CX	& CH, CL	& \\ \hline	DX	& DH, DL	& \\ \hline	DI	& None		& Destination Index. \\ \hline	SI	& None		& Source Index. \\ \hline	BP	& None		& Base pointer. \\\end{tabular}Note that the segment registers CS, DS, ES, and SS are not listed.For simplicity only tiny mode is supported.  Tiny mode is where boththe data and code exist in one segment, such that CS = DS.  Thisallows constant data stored in the code segment to be accessed in thesame method as data.  This may cause trouble later if far mode isneeded.\subsection{\tosh}The 900H seems to be inspired by the Z80.  It is listed as a 16 bitdevice, but most of the registers are 32 bits wide. \\\begin{tabular}{l|l|l}	Name	& Parts		& Notes \\ \hline	XWA	& WA, W, A	& Accumulator \\ \hline	XBC	& BC, B, C	& \\ \hline	XDE	& DE, D, E	& \\ \hline	XHL	& HL, H, L	& \\ \hline	XIX	& IX		& \\ \hline	XIY	& IY		& \\ \hline	XIZ	& IZ		& \\\end{tabular}All registers can act as either an index base or an index offset.  Theoffset is limited to sixteen bits.  Apparently XIX, XIY, and XIZ canbe split at the byte level.  For simplicity this is ignored.\section{Common features}\subsection{Stack}The stack grows downwards.  All push operations are pre-decrement.All but the GBZ80 have a base pointer register that can be used alongwith an offset to access local variables and parameters.  The GBZ80 andZ80 both have problems with more than 127 bytes of local variables dueto their offset being a INT8.\subsection{Registers}All contain a reasonable but small number of registers.  All have somespecial purpose registers which can either be handled separately orignored.  All general purpose registers can be split at the byte andword level, but doing so may make the rest of the registerunavailable.\subsection{Memory}All have a 64k address space.  However this should not be assumed to makefar support easier later.\section{Design}\subsection{Basics}The design is mainly stack based, such that all local variables andparameters go onto the stack.  Compare with the mcs51 backend whichoverlays variables onto a shared static area.All stack access goes through the base pointer register (BP).  Thestack frame consists of the parameters pushed right to left, thereturn context, and then local variables.  SP points to the base ofthe local variables.  BP points to the bottom of the return contextand hence to just above the top of the local variables.  Note that asthe stack grows down the parameters appear with the left mostparameter at the lowest address.A scratch register will be available for any sub operation to use andwill be valid only within that sub operation.  The accumulator is alsounavailable.  Return values are normally returned in the scratchregister and accumulator.\begin{tabular}{l|l|l|l|l}	Name		& i186	  & Z80	    & GBZ80  & 900H 	\\ \hline	Base pointer 	& BP	  & IX	    & HL     & XIX 	\\ \hline	Scratch		& BX	  & HL	    & DE     & XHL	\\ \hline	Return		& BX, AX  & HL, IY  & DE, HL & XHL	\\ \hline	Available	& CX, DX  & BC, DE  & BC     & XBC, XDE	\\ \hline	Ignored		& SI, DI  & IY	    & None   & XIY, XIZ	\\\end{tabular}\subsection{Register allocator}The current Z80 and mcs51 register allocators perform these steps:\begin{enumerate}	\item Pack each basic block by removing straight assignments and markingremat. iTemps.	\item Set the number of registers required for each live range based onthe type and size of the live range.	\item Assign registers to each segment by deassigning registers and stacklocations for any just expired iTemps, skipping any instructions which don't needregisters, and spilling and assigning registers to the result of this tuple.	\item Create the register mask for this segment.\end{enumerate}Optimisations include assigning into the accumulator or the scratchregister where possible.  This requires knowledge of what the codegenerator touches for a given instruction.The first generation register allocator will only pack assignments and markremat. variables.  Only the register management is processor specific.  Theallocator may ask for a given size register or if a given size register isavailable.  Note that only whole registers may be returned.  For example, allocation will fail if a sixteen bit register is requested and no pairis available, even two eight bit registers are available.  Note that onthe Z80, GBZ80, and i186 a request for a 32 bit register will always fail.\subsection{Code generator}The possible operations are:\begin{itemize}	\item NOT - Logical not.  0 -> 1, others -> 0.	\item CPL - Bitwise complement.	\item UMINUS - Unary minus.  result = 0 - left.	\item IPUSH - Push immediate onto the stack.	\item CALL - Call a function.	\item PCALL - Call via pointer.	\item FUNCTION - Emit the function prelude.	\item ENDFUNCTION - Emit the function prologue.	\item RET - Load the return value and jump to end of function.	\item LABEL - Generate a local label.	\item GOTO - Jump to a local label.	\item Arithmitic - +, -, *, /, \%.	\item Comparison - LT, GT, LEQ, GEQ, !=, =.	\item Logical - \&\&, ||	\item Binary - AND, OR, XOR.	\item Shift - RRC, RLC, LSR, LSL.	\item Pointer - Set and Get.	\item Assign.	\item IF jump.	\item Misc - Jump table, cast, address of.\end{itemize}\end{document}