text:
<file_sep>%\chapter{Obsah CD}
%\chapter{Manual}
%\chapter{Konfigrační soubor}
%\chapter{RelaxNG Schéma konfiguračního soboru}
%\chapter{Plakat}
\chapter{CD Contents}

The attached CD contains the source code, with SDCC included, the tests and installation and compilation scripts.

\chapter{Installation and Usage}

SDCC lists the following dependencies: Boost, Yacc, Bison.

To compile the \texttt{pblaze} port, you have to use a C++ compiler that supports the ISO/IEC 14882:2011 (C++11) standard.

The port can be built against any recent snapshot of SDCC and version 3.4.0. It is possible to compile it against SDCC 3.3.0, too but on some machines, \texttt{configure} does not generate the required \texttt{Makefile}. The CD includes version 3.3.0 with the \texttt{Makefile} already generated.

If you compile the project from new source directly, please follow the steps listed in Section \ref{compilation} now.

To run the compiled binary (especially on \texttt{merlin.fit.vutbr.cz}), you need to link against the correct \texttt{libstdc++} on runtime.
To do so on \texttt{merlin}, add the following path to your \texttt{LD\_LIBRARY\_PATH}:

\begin{center}\verb|/pub/tmp/gcc/gcc-4.9.0/.x86_64-linux/x86_64-linux/libstdc++-v3/src/.libs|\end{center}

\section{Usage}

To use the \texttt{pblaze} port, specify the \texttt{-mpblaze} command line option to the \texttt{sdcc} binary.

To change the size of the function arguments to be passed via registers, use the \texttt{--argreg=N} option, specifying the count of the registers.

\chapter{PicoBlaze-6 Instruction Set}\label{instrset}
\begin{table}[H]
\centering
r - register, p - address in register, cX - constant, size, l - label
\begin{tabular}{| r | c | c | l |}\hline

\verb|LOAD|&\verb|r|&\verb|r|& Moves contents of registers\\ \hline
\verb|LOAD|&\verb|r|&\verb|c|& Moves contents of registers\\ \hline
\verb|STAR|&\verb|r|&\verb|r|& Moves contents of registers between banks\\ \hline

\verb|AND|&\verb|r|&\verb|r|& Binary and\\ \hline
\verb|AND|&\verb|r|&\verb|c|& Binary and\\ \hline
\verb|OR|&\verb|r|&\verb|r|& Binary or\\ \hline
\verb|OR|&\verb|r|&\verb|c|& Binary or\\ \hline
\verb|XOR|&\verb|r|&\verb|r|& Binary xor\\ \hline
\verb|XOR|&\verb|r|&\verb|c|& Binary xor\\ \hline

\verb|ADD|&\verb|r|&\verb|r|& Addition\\ \hline
\verb|ADD|&\verb|r|&\verb|c|& Addition\\ \hline
\verb|ADDCY|&\verb|r|&\verb|r|& Addition, reuses carry\\ \hline
\verb|ADDCY|&\verb|r|&\verb|c|& Addition, reuses carry\\ \hline
\verb|SUB|&\verb|r|&\verb|r|& Subtraction\\ \hline
\verb|SUB|&\verb|r|&\verb|c|& Subtraction\\ \hline
\verb|SUBCY|&\verb|r|&\verb|r|& Subtraction, reuses carry\\ \hline
\verb|SUBCY|&\verb|r|&\verb|c|& Subtraction, reuses carry\\ \hline

\verb|TEST|&\verb|r|&\verb|r|& Binary and without result storage\\ \hline
\verb|TEST|&\verb|r|&\verb|c|& Binary and without result storage\\ \hline
\verb|TESTCY|&\verb|r|&\verb|r|& Binary and without result storage, reuses carry\\ \hline
\verb|TESTCY|&\verb|r|&\verb|c|& Binary and without result storage, reuses carry\\ \hline
\verb|COMPARE|&\verb|r|&\verb|r|& Operand comparison\\ \hline
\verb|COMPARE|&\verb|r|&\verb|c|& Operand comparison\\ \hline
\verb|COMPARECY|&\verb|r|&\verb|r|& Operand comparison, reuses carry\\ \hline
\verb|COMPARECY|&\verb|r|&\verb|c|& Operand comparison, reuses carry\\ \hline

\verb|SL0|&\verb|r|&\verb||& Shift left, fill 0 \\ \hline
\verb|SL1|&\verb|r|&\verb||& Shift left, fill 1 \\ \hline
\verb|SLX|&\verb|r|&\verb||& Shift left, fill LSB \\ \hline
\verb|SLA|&\verb|r|&\verb||& Shift left, fill carry \\ \hline
\verb|RL|&\verb|r|&\verb||& Rotate left \\ \hline
\end{tabular}
\end{table}

\begin{table}[H]
\centering
r - register, p - address in register, cX - constant, size, l - label
\begin{tabular}{| r | c | c | l |}\hline
\verb|SR0|&\verb|r|&\verb||& Shift right, fill 0 \\ \hline
\verb|SR1|&\verb|r|&\verb||& Shift right, fill 1 \\ \hline
\verb|SRX|&\verb|r|&\verb||& Shift right, fill LSB \\ \hline
\verb|SRA|&\verb|r|&\verb||& Shift right, fill carry \\ \hline
\verb|RR|&\verb|r|&\verb||& Rotate right \\ \hline

\verb|REGBANK|&\verb|A|&\verb||& Select bank A \\ \hline
\verb|REGBANK|&\verb|B|&\verb||& Select bank B \\ \hline

\verb|INPUT|&\verb|r|&\verb|p|& Read data from a port \\ \hline
\verb|INPUT|&\verb|r|&\verb|c8|& Read data from a port \\ \hline
\verb|OUTPUT|&\verb|r|&\verb|p|& Write data to a port \\ \hline
\verb|OUTPUT|&\verb|r|&\verb|c8|& Write data to a port \\ \hline
\verb|OUTPUTK|&\verb|r|&\verb|p|& Write constant data to a specific port\\ \hline

\verb|STORE|&\verb|r|&\verb|p|& Write data to scratchpad memory \\ \hline
\verb|STORE|&\verb|r|&\verb|c8|& Write data to scratchpad memory \\ \hline
\verb|FETCH|&\verb|r|&\verb|p|& Read data from scratchpad memory \\ \hline
\verb|FETCH|&\verb|r|&\verb|c8|& Read data from scratchpad memory \\ \hline

\verb|DISABLE INTERRUPT|&\verb||&\verb||& Disable interrupt \\ \hline
\verb|ENABLE INTERRUPT|&\verb||&\verb||& Enable interrupt \\ \hline
\verb|RETURNI DISABLE|&\verb||&\verb||& Disable return from interrupt handler \\ \hline
\verb|RETURNI ENABLE|&\verb||&\verb||& Enable return from interrupt handler \\ \hline

\verb|JUMP|&\verb|l|&\verb||& Jump to label \\ \hline
\verb|JUMP|&\verb|Z|&\verb|l|& Jump to label if zero \\ \hline
\verb|JUMP|&\verb|NZ|&\verb|l|& Jump to label if not zero \\ \hline
\verb|JUMP|&\verb|C|&\verb|l|& Jump to label if carry \\ \hline
\verb|JUMP|&\verb|NC|&\verb|l|& Jump to label if not carry \\ \hline
\verb|JUMP@|&\verb|p|&\verb|p|& Jump to label pointer\\ \hline

\verb|CALL|&\verb|l|&\verb||& Call label \\ \hline
\verb|CALL|&\verb|Z|&\verb|l|& Call label if zero \\ \hline
\verb|CALL|&\verb|NZ|&\verb|l|& Call label if not zero \\ \hline
\verb|CALL|&\verb|C|&\verb|l|& Call label if carry \\ \hline
\verb|CALL|&\verb|NC|&\verb|l|& Call label if not carry \\ \hline
\verb|CALL@|&\verb|p|&\verb|p|& Call label pointer \\ \hline

\verb|RETURN|&\verb||&\verb||& Return from call \\ \hline
\verb|RETURN|&\verb|Z|&\verb||& Return if zero \\ \hline
\verb|RETURN|&\verb|NZ|&\verb||& Return if not zero  \\ \hline
\verb|RETURN|&\verb|C|&\verb||& Return if carry \\ \hline
\verb|RETURN|&\verb|NC|&\verb||& Return if not carry \\ \hline

\verb|LOAD&RETURN|&\verb|r|&\verb|c|& Load a constant and return \\ \hline

\verb|HWBUILD|&\verb|r|&\verb||& Get harware information\\ \hline
\end{tabular}
\end{table}

<file_sep>Text part of my bachelor thesis - C Language Compiler Back-End for PicoBlaze-6

The program part can be found on https://github.com/krivka/pbccv3<file_sep>
\begin{center}
\textbf{\huge Bachelor's Thesis Assignment}

\Large Unofficial Translation
\end{center}

\subsection*{Student}
<NAME>

\subsection*{Specialisation}
Information Technology

\subsection*{Topic}
\textbf{C Compiler Back-End for PicoBlaze-6}

\subsection*{Category}
Compilers

\subsection*{Instructions}
\begin{enumerate}
	\item Study the standard of C programming language and the specification of the version 6 of the 8-bit softcore processor PicoBlaze by Xilinx.
	\item Examine the existing compilers for 8-bit processors (e.g. PCCOMP, PBCCv2) and identify their fundamental flaws and problems.
	\item According to your supervisor's instructions select an appropriate subset of C language and choose an existing C compiler front-end (e.g. SDCC or LLVM) for the implementation. Then, design the back-end for the chosen front-end to translate the subset of C language to the assembly language of PicoBlaze-6 target platform.
	\item Implement the design.
	\item Test the resulting compiler using at least 10 non-trivial examples and evaluate its pros and cons compared to the other examined alternatives. In the conclusion, propose some improvements of the compiler.
\end{enumerate}

\subsection*{Supervisor}
\textbf{<NAME>, Ing., Ph.D.}, UIFS FIT VUT

<file_sep>%=========================================================================
% (c) <NAME>, <NAME>, 2008
%emitter priklad

\definecolor{gray}{gray}{0.5}
\newcommand{\todo}[1]{\textcolor{red}{TODO\:} \textcolor{gray}{#1}}

\chapter{Introduction}\label{introduction}

Subject of this thesis project is constructing a C programming language compiler back-end for the soft-core processor PicoBlaze-6. The 8-bit processor is quite simple but after the recent update, it provides an interesting set of features to use in C programs.

However, Currently, there is no other C compiler designed especially for the PicoBlaze-6 processor, therefore a new compiler utilizing the new features is a welcome addition to the existing toolchain.

    \section{The C Programming Language}

    The C programming language was created in the 1970s by <NAME> and <NAME>. In this project, I focused mainly on implementing its two latest standards, ISO/IEC 9899:1999 \cite{C99} and partially ISO/IEC 9899:2011 \cite{C11}.

    \section{The Previous Project}
    Similar thesis topic was elaborated by <NAME> as his Master thesis in 2011. This project is discussed in Section \ref{prev_pbcc}.

    While he was writing the thesis, a new version of the target processor was released (see Chapter~\ref{processor}). The resulting application is discussed in Section~\ref{prev_pbcc}.

    \section{Structure of the Document}

    After the introduction to PicoBlaze in Chapter \ref{processor} and explaining the basic principles of compiler design in Chapter \ref{theory}, the available existing and open source C language compiler front-ends are enumerated in Chapter \ref{compiler}.

    Next, the previous projects implementing a compiler for the older releases of the PicoBlaze processor, are listed in Chapter \ref{existing}.

    And finally, Chapter \ref{design} explains the principles that the final application builds upon and its functionality is tested and evaluated in Chapter \ref{evaluation}. Chapter \ref{features} contains the summary of the compiler features and their description.

\chapter{The PicoBlaze Processor}\label{processor}

\emph{PicoBlaze} is a 8-bit processor created by Xilinx Inc. for their Spartan and Virtex FPGA\footnote{Field-Programmable Gate Array} series as an embeddable circuit to implement sequential programming in the parallel FPGA architecture. This means the processor is not meant to be physically manufactured, yet it would be possible \cite{PicoBlazeWeb}.

    \section{History}

    Historically, the name of the design was \texttt{KCPSM}, for Ken Chapman's Programmable State Machine and then Constant Coded Programmable State Machine. This term is now still used in the FPGA design - the \emph{VHDL}\footnote{\emph{VHSIC} (Very High Speed Integrated Circuit) Hardware Description Language} and Verilog components are still caled \texttt{kcpsmX} where \texttt{X} stands for the version of the processor \cite{DSPwFPGA}.

        \subsection{PicoBlaze}

        The first version of PicoBlaze was released in May 1999.

        The initial PicoBlaze was very simple, especially compared to the current one. There was only space for 256 instructions in the program memory and there was no RAM. Only 16 8-bit registers were available to be used for storage. However, it is possible to connect an external memory through the 256 I/O pins.

        The multi-byte arithmetic instructions (\texttt{ADDCY} and \texttt{SUBCY}) were included since the very beginning.

        There was no dedicated instruction for value comparison but both the zero and carry flags were already present \cite{PicoBlaze}.

        \subsection{PicoBlaze-2}

        The second version of the processor was initially released in December 2002.

        The program could consist of 1024 instructions at most and there was no scratchpad memory for runtime variables. The instructions were able to operate only with the 32 8-bit registers and constant values.

        The PicoBlaze instruction set remained the same in this revision.\cite{PicoBlaze2}.

        \subsection{PicoBlaze-3}

        First release of the previous version, 3, of PicoBlaze was released in May 2003. Its last revision, was released in August 2004.

        The register count was reduced to 16 while their size has been kept the same. The main addition in this version is the 64 byte large scratchpad memory, that eliminates the need of an external memory connected through the I/O ports.

        Instruction set changes in this version include the addition of comparison, testing and parity counting instructions \cite{PicoBlaze3}.

        \subsection{PicoBlaze-6}

        The PicoBlaze-6 was initially released on 28th October 2010. Since then, a total of 7 newer revisions of this versions were released.

        The most recent one, PicoBlaze-6 release 8, was released on 31th March 2014 \cite{PicoBlaze6}.

        The differences and new features compared to PicoBlaze-3 are discussed in Section~\ref{kcpsm6cmp}. The main features, regardless of history, are listed in Section~\ref{mainfeatures}.

    \section{Main Features}\label{mainfeatures}

    PicoBlaze is a \emph{RISC}\footnote{Reduced Instruction Set Computing}, Harvard architecture\footnote{The program code and the data memory are stored in separate locations} processor. Every instruction is executed in 2 clock cycles \cite{PicoBlaze6}.

    \begin{table}[H]
    \centering
    \begin{tabular}{ @{\extracolsep{\fill} } r | l }
        Program memory & Up to 4096 instructions \\

        Scratchpad RAM & Up to 256 bytes \\

        2 Register banks & Containing 16 8-bit registers each\\

        Input/Output & 256 8-bit ports \\

        8-bit Arithmetic-Logic Unit & Supports shifting, adding and subtracting \\
                                    & Provides AND, OR and XOR operations \\
                                    & Compares and tests \\
                                    & Implements carry and zero flags \\

        FPGA design & Can be included directly in the hardware code \\
                    & No other equipment or code needed \\
    \end{tabular}
    \caption{PicoBlaze-6 features \cite{PicoBlazeWeb}}
    \end{table}

    \section{Practical usage}

    A sequential processor, in comparison to parallel hardware design, is much more feasible for implementing state machines and computational cycles.

    It is suitable to used to control simple devices and to communicate over serial interfaces. The use-cases presented by the manufacturer are LCD drivers, SPI communication, controlling devices such as A/D controller.

    Time-based operations as pulse width modulation are possible with the processor, as well as display of real time clock or frequency measuring \cite{PicoBlazeExamples}.

    \section{New features and properties of PicoBlaze-6}\label{kcpsm6cmp}

    Compared to the previous version, there were major changes in PicoBlaze design after the upgrade to the sixth version, which is still backwards-compatible.

    The most important ones are covered in this section in descending order according to their impact on programming in C and the compiler itself \cite{PicoBlaze6}.

        \subsubsection{New \texttt{JUMP@} and \texttt{CALL@} Instructions}\label{jumpat}

        Indirect jumps and calls, provided the address of the function or label, are possible in the new version.

        This improves compatibility with sophisticated C programs greatly as it allows the implementation of function pointers and their calling.

        It also means there had to a new addressing mode introduced - the whole program memory cannot be covered with only an 8-bit value, so the code's section is stored in the lower four bytes of the first register and the rest of the address in the second one.

        \subsubsection{New \texttt{REGBANK} and \texttt{STAR} Instructions}

        The new version of the processor now provides two sets of 16 general purpose registers that are switchable using the \texttt{REGBANK} instruction - this means only one of the sets can be accessed at a time.

        To store values in the inactive bank, the \texttt{STAR} instruction is provided - it is used to store a value from the active bank register in another register that is in the inactive bank.

        \subsubsection{\texttt{ADDCY} and \texttt{SUBCY} Instruction Changes}

        The previous version of these instructions modified the zero flag only according to their own result. Now they add the previous zero to the current one.

        \subsubsection{New \texttt{COMPARECY} and \texttt{TESTCY} Instructions}

        Instructions added to make comparing multi-byte types easier. They store the flags (carry and zero) and propagate them according to the progress through the single bytes.

        \subsubsection{Program Memory Changes}

        Due to the two newly added memory addressing pins, it is possible to address four times more program memory (now up to 4096), increasing the possible program size and complexity.

        \subsubsection{RAM Changes}

        The amount of RAM addressable by the program was increased to up to 256 bytes from 64, yet it depends on the target device the processor will be implemented on.

        This was achieved by modifying the opcodes of instructions of the processor, not the internals.

        \subsubsection{Call stack}

        Only 30 levels of function call depth are now available compared to 31 of PicoBlaze-3.

        \subsubsection{New \texttt{LOAD\&RETURN} Instruction and \texttt{STRING} Directive}

        The user (or compiler) can now specify a byte string location in the memory using the \texttt{STRING} directive in the assembly.

        Then, using the \texttt{LOAD\&RETURN} instruction, it is possible to load a constant value into a specified register and unconditionally return from a subroutine, making these very useful in conjunction to generate text strings to be presented to the user.

        \subsubsection{New \texttt{OUTPUTK} Instruction}

        This instruction allows the program to output a constant instead of loading it into a register and outputting it using the regular \texttt{OUTPUT}.

    \section{PacoBlaze}

    \emph{PacoBlaze} is an open-source (under the BSD license) clone of the PicoBlaze processor written in Verilog.

    Its main advantage is the possibility to be used with hardware not provided by Xilinx and modifiability and configurability.

    Due to the higher versatility, \emph{PacoBlaze} is not as efficient (resource-wise) as the original implementation but it enables the user to remove unneeded parts from the processor and use its smallest required subset, therefore reducing FPGA space use as the result.

    The latest version is 2.2 (released in 2007) so it cannot possibly implement the new instructions of PicoBlaze-6 that this project tries to use as much as possible \cite{PacoBlaze}.

    \section{PicoBlaze Assemblers}

        Compilation to the machine code directly is not feasible because it prevents further modifications of the resulting code. It's also not absolutely necessary as there already are complete assemblers, with features, implementing which would reduce the time available for writing the C compiling part of the toolchain.

        \subsection{pBlazASM}\label{pblazasm}

        PBlazASM is an open source assembler created by Mediatronix to be used for compiling the machine code source files directly to machine code in several formats. It can also create a representation (\texttt{.lst} files) that is then used in the pBlazSIM simulator (that is distributed in the same repository, see Section \ref{pblazsim}) \cite{PblazAsm}.

        However, the program itself is bug infested and crashes quite often. There were some trivial bugs that were possible to be fixed quickly, such as calling \texttt{free} on a pointer that was not returned by \texttt{malloc}.

    \section{PicoBlaze Simulators}

        As the debugging capabilities of the processor are limited, making debugging of the programs on real hardware too complicated, possibility of usage a simulator of the target processor is more than welcome.

        \subsection{pBlazSIM}\label{pblazsim}

        One of the most recent ones, pBlazSIM, was created by Mediatronix, too. It is actually hosted in the same repository tree as pBlazASM (see Section \ref{pblazasm}), along with some other tools \cite{PblazSim}. \cite{PblazAsmRepo}

        Hosted under the GPLv2 open source license, it is written in C++ and Qt, so its use is not limited only to one platform. Mediatronix distributes only the Windows binary form, though.

            \subsubsection{Running Under Linux}

            First attempts to run the simulator in \emph{Wine}\footnote{WINE is not an Emulator - an open source Windows API implementation} were quite unsuccessful as it was only capable to simulate the code which was included in the distributed binary package and no other.

            Attempts to compile the simulator from the source provided were also unsuccessful at first. Some changes to the distributed files were required.

            The needed steps to finish the compilation successfully are fixing the \texttt{qmake} project file to include all needed source files and adding one missing icon for the GUI\footnote{Graphical User Interface} (for example by copying the existing ones in different colors).

            The hand-compiled version is able to run the assembly files generated by pBlazASM (see Section \ref{pblazasm}) well. All features in the GUI are working, too.

            I contacted the upstream developer responsible for the changes that introduced the invalid constructions to fix them. The code was fixed by the developer in two days.

            \subsubsection{Command Line Simulator}

            A simple simulator without any user interface was introduced to the code-base recently. The officially provided build system information does not handle its compilation but due to the relative simplicity of the project, it is easy to compile this executable by hand by using the object files of the pBlaze.cpp module.

            The simplest way possible (provided you use a C++ compiler that is able to link directly) to compile this binary is by using the following command:

            \begin{center}
                \texttt{\$\{CXX\} pBlaze.cpp pBlazSIMcl.cpp -o \$\{SIM\_BINARY\}}
            \end{center}

        \subsection{PBSim}\label{pbsim}

        A project that is being developed on the University, started as a Master's project in year 2012 \cite{PbsimProj}.

        Bound to SDCC (see Section \ref{sdcc}) and tightly related to Eclipse, it is possible to use it as a part of its UI.

        It is hosted under the GPLv2 license on Github \cite{PbsimRepo} but there are no instruction to compile the project. In comparison to pBlazSIM (see Section \ref{pblazsim}), it's not active at all.

\chapter{Programming language compiler}\label{theory}

Most of the modern computer processors are programmed using a fairly complicated binary instruction set. To make writing more complex and powerful applications more pleasant and comprehensible, we are now using programming languages that are translated (\emph{compiled}) into the low level binary form executable by the processor.

In this chapter, the most vital parts and terms in construction of a compiler are discussed, with focus on C language \cite{DragonBook}.

    \section{Compiler Structure}

    A typical programming language compiler consists of two to four main parts:

    First part is an optional preprocessor which prepares the source code for the front-end, for example by removing comments or expanding macro definitions.

    A language front-end, which transforms the code from a programming language to its simple intermediate and internal representation.

    An intermediate code optimizer searches the representation for patterns that can be changed to more efficient, smaller or faster equivalents. This part is optional, too.

    And finally, the back-end, that generates the target code for the processor itself, be it assembly code, virtual machine code or a processor-native code \cite{DragonBook}.

    \begin{figure}[H]
    \centering
    \begin{tikzpicture}
        \tikzstyle{block} = [draw, rectangle, minimum width=14.5em, minimum height=2.2em]
        \node (Program) {\emph{Source Program}};
        \node[block,right=of Program,thick] (Preprocessor) {Preprocessor};
        \node[block,below=of Preprocessor,thick] (Front) {Front-End};
        \node[block,below=of Front,thick] (IMO) {Intermediate Code Optimizer};
        \node[block,below=of IMO,thick] (Back) {Back-End};
        \node[right=of Back,font=\bf,thick] (Target) {\emph{Target Code}};

        \draw[->, thick] (Program) edge (Preprocessor);
        \draw[->,thick] (Preprocessor) edge node[auto] {\emph{Stripped Source Code}} (Front.north);
        \draw[->,thick] (Front) edge node[auto] {\emph{Intermediate Code}} (IMO);
        \draw[->,thick] (IMO) edge node[auto] {\emph{Optimized Intermediate Code}} (Back);
        \draw[->,thick] (Back) edge (Target);
    \end{tikzpicture}
    \caption{Structure of a compiler front-end} \label{fig:compiler}
    \end{figure}

    \section{Preprocessor}

    Preprocessor performs a simple task of removing or replacing text in the input source code according to some pre-set rules.

    The most common task is removing comments to leave only language defined tokens for the further stages of compilation.

    In the C programming language, there are preprocessor macros, too. These serve a purpose of replacing and inserting text. However, describing the entirety of the C preprocessor is a task beyond limits of this thesis, only few directives are listed, along with their simplified descriptions \cite{GnuCppWeb}.

    \begin{table}[H]
    \begin{tabular}{r|l}
        \verb|#include "file"| or \verb|<file>| & Behaves as if the whole contents of \verb|file| were inserted \\
        & instead of it.\\
        \verb|#define MACRO ...| & Every occurrence of \verb|NAME| in the code is replaced with \\
        & what is substituted with \verb|...| (until the end of line).\\
        \verb|#if cond| & The following lines until \verb|#endif| are pasted if \verb|cond| is\\
        & met. \verb|cond| supports C expression syntax.\\
        \verb|#ifdef MACRO| & Equivalent to \verb|#if defined(MACRO)|. True if \verb|MACRO| was\\
        & defined.
    \end{tabular}
    \caption{Basic C preprocessor macros}
    \end{table}

    \section{Front-end}

        The central and most important part of the compiler, it does a whole set of operations over the source code to produce its independent representation.

        It is a language-specific part, that also checks the correctness of the input code.

        Large compiler projects even aim to its complete and clear replaceability (see Sections \ref{gcc} and \ref{llvm} for examples) to benefit from the optimization in the following stages of compilation.

        \begin{figure}[H]
        \centering
        \begin{tikzpicture}
            \tikzstyle{block} = [draw, rectangle, minimum width=10em, minimum height=2.2em]
            \node (Program) {\emph{Source Program}};
            \node[block,right=of Program,thick] (Lex) {Lexical Analyzer};
            \node[block,right=of Lex,thick] (Parser) {Parser};
            \node[block,below=of Lex,thick] (SymTab) {Symbol Table};
            \node[block,right=of SymTab,thick] (CodeGen) {Code Generator};
            \node[below=of CodeGen,font=\bf,thick] (IM) {\emph{Intermediate Code}};

            \draw[->,thick] (Program) -- (Lex);
            \draw[transform canvas={yshift=0.5ex},->,thick] (Lex) -- (Parser);
            \draw[transform canvas={yshift=-0.5ex},<-,thick] (Lex) -- (Parser);
            \draw[transform canvas={xshift=0.5ex},->,thick] (CodeGen) -- (Parser);
            \draw[transform canvas={xshift=-0.5ex},<-,thick] (CodeGen) -- (Parser);
            \draw[<->,thick] (Lex) -- (SymTab);
            \draw[<->,thick] (SymTab) -- (CodeGen);
            \draw[->,thick] (CodeGen) -- (IM);
        \end{tikzpicture}
        \caption{Structure of a compiler front-end} \label{fig:frontend}
        \end{figure}

        \subsection{Lexical analysis}

            \emph{Lexical analyzer} comes into contact with the raw source code.

            Reading the input stream character by character, it breaks it down to segments called \emph{tokens}, according to rules that are set by the language standard.

            For example, there can be a token representing a \emph{keyword} (like \texttt{if} or \texttt{for}), a literal value (\texttt{42} or \verb'"string"',...) or a type or symbol name (\texttt{foo}, \texttt{main},...) \cite{DragonBook}.

            A token of the \texttt{if} keyword will be always represented with the same string - \texttt{if}. However, a variable name in C can take form of any string that matches the following regular expression \cite{C99}.

            \begin{center}\texttt{[A-Za-z\_][A-Za-z\_0-9]*}\end{center}

            These names and values are then stored in the symbol table, which will be discussed in the next section.

        \subsection{Symbol Table}

            A \emph{symbol table} is a container storing names of all symbols that the lexical analyzer has detected \cite{DragonBook}.

            The values here are used further in the compilation, either to resolve the identity of tokens, or to actually assign the literal values and use them in the program itself.

        \subsection{Parser}

            \emph{Parser} then takes the stream of tokens and arranges them into a tree-like structure. This process is called \emph{syntactic analysis}. It consists not only of arranging the tree but as a side-effect, correct syntax of the input code is being checked.

            Consider the following expression for demonstration of processes taking place in the parser:

            \begin{listing}
            \centering
            \texttt{1 * foo + 5 * bar}
            \caption{Example expression}\label{lst:expr}
            \end{listing}

            The tree, as a result of the syntactic analysis, would take the form represented in the next diagram \cite{CompilerDesignInC}.

            Note the operator precedence is honored in the same way as in regular mathematical expressions.

            \begin{figure}[H]
            \centering
            \begin{tikzpicture}[node distance=1.5cm]
                \node (add) {+};
                \node (mulL) [below left of=add,xshift=-33] {*};
                \node (mulR) [below right of=add,xshift=33] {*};
                \node (1) [below left of=mulL] {\emph{value}(1)};
                \node (foo) [below right of=mulL] {\emph{identifier}(\texttt{foo})};
                \node (5) [below left of=mulR] {\emph{value}(5)};
                \node (bar) [below right of=mulR] {\emph{identifier}(\texttt{bar})};
                \coordinate (mulM) at ($(mulL)!0.5!(mulR)$);

                \draw (add) -- (mulL);
                \draw (add) -- (mulR);
                \draw (mulL) -- (1);
                \draw (mulL) -- (foo);
                \draw (mulR) -- (5);
                \draw (mulR) -- (bar);
            \end{tikzpicture}
            \caption{Syntactic tree} \label{fig:syntactic}
            \end{figure}

            There is also other information about the tokens in this expression, like types in case of variables. It is necessary to check if they are used in the right context, like if functions are used like functions and not variables or if defined operations are being used upon them. This process is called \emph{semantic analysis} \cite{DragonBook}.

            \begin{figure}[H]
            \centering
            \begin{tikzpicture}[node distance=1.5cm]
                \node (add) {+};
                \node (mulL) [below left of=add,xshift=-33] {*};
                \node (mulR) [below right of=add,xshift=33] {*};
                \node (1) [below left of=mulL] {\texttt{\textless int\textgreater} 1};
                \node (foo) [below right of=mulL] {\texttt{\textless float\textgreater foo}};
                \node (5) [below left of=mulR] {\texttt{\textless int\textgreater} 5};
                \node (bar) [below right of=mulR] {\texttt{\textless int\textgreater bar}};
                \coordinate (mulM) at ($(mulL)!0.5!(mulR)$);

                \draw (add) -- (mulL);
                \draw (add) -- (mulR);
                \draw (mulL) -- (1);
                \draw (mulL) -- (foo);
                \draw (mulR) -- (5);
                \draw (mulR) -- (bar);
            \end{tikzpicture}
            \caption{Operator and operand relation in semantic analysis} \label{fig:semantic}
            \end{figure}

            If \texttt{foo} was not a \texttt{float} but for example a \texttt{bool} variable the semantic analysis of the expression would fail because the operation of multiplication is not be defined between these two types.

            The result types of expressions, are deduced as well. In this case, in C language, the whole expression's result would take form of a \texttt{float}.

        \subsection{Code Generator}

            While the trees are being constructed and checked, the intermediate code is created as well.

            The \emph{parser} feeds the completed subtrees and their nodes into the code generator that flattens the structure into a series of instructions, similar to the assembly language of a computer processor \cite{DragonBook}.

            Only one kind of resemblance of the previous code will be left - the links in code branches for both conditional and unconditional jumps - this is required to make creating the links in the resulting code easier.

            In case the compiler does not use any kind of intermediate code, directly the target language is being emitted in this section, making the code generator serve the purpose of a back-end (described in Section \ref{desc_backend}), too.

    \section{Intermediate Code}\label{immediate}

            As mentioned in the previous section, the intermediate code resembles assembly. The difference between the two is still quite big though. Intermediate code contains a lot more information, like variable names, information about liveness of the variables, type information and much more.

            Popular form of such output is called \emph{three address code}. Every instruction in this simple language takes a maximum of three operands, first marks where the result will be stored and the other to are the source operands \cite{DragonBook}.

            Consider the example we already used, defined in Listing \ref{lst:expr}.

            The expression will be transformed to the following (simplified) series of instructions in three address code:

            \begin{listing}\centering\begin{tabular}{l}
            \verb|mul    temp1,       1,     foo|\\
            \verb|mul    temp2,       5,     bar|\\
            \verb|add    temp1,   temp1,   temp2|
            \end{tabular}
            \caption{Example of a three address code}\label{lst:tac}
            \end{listing}

            The instructions in the code can be limited to take only two operands. The first operand will be both the result and the first argument in this case. This code is equivalent to the previous, only printed in two-operand notation:

            \begin{listing}\centering\begin{tabular}{l}
            \verb|assign  temp1,      1|\\
            \verb|mul     temp1,    foo|\\
            \verb|assign  temp2,      5|\\
            \verb|mul     temp2,    bar|\\
            \verb|add     temp1,  temp2|\\
            \end{tabular}
            \caption{Example of a two-operand intermediate code}\label{lst:2ic}
            \end{listing}

            Three address code as intermediate language is very common in compilers. This puts them close to some processor architectures, such as ARM, that uses a form of three address code as its assembly language. \cite{ARM} In contrary, other architectures, like x86 \cite{x86}, or, PicoBlaze \cite{PicoBlaze6}, that this thesis targets, use only two operands in their assembly.

        \subsection{The Intermediate Code Optimizer}

            Optimizing the code during the compilation is not absolutely vital for the whole process. However, it is a welcome part, especially by the end-users of the tool.

            The optimizer looks for patterns that can be reordered, changed for their faster equivalents or completely removed, while maintaining the same functionality as before.

            To demonstrate on the three address code from Listing \ref{lst:tac}, consider this instruction:

            \begin{center}\verb|mul    temp1,       1,     foo|\end{center}

            Multiplying anything with 1 is redundant. After removing this unnecessary operation and changing the order to preserve the same result, the example would look like this:

            \begin{listing}\centering\begin{tabular}{l}
            \verb|mul    temp1,       5,     bar|\\
            \verb|add    temp1,   temp1,     foo|\\
            \end{tabular}
            \caption{Optimized three address code from Listing \ref{lst:tac}}\label{lst:opttac}
            \end{listing}

            One whole instruction was saved in this case.

            There are many more techniques that can be applied on any amount of code. One of the simplest ones is \emph{dead code} and \emph{dead variable detection}. When a variable is not used or a conditional branch cannot be entered at any time when the program will be executed, the optimizer can completely remove it \cite{OptimizingCompiler}.

    \section{Back-end}\label{desc_backend}

        The target specific part of the compiler, generating the sought code, is the \emph{back-end}.

        For each instruction of the immediate code, it matches its equivalent, be it single instruction, or a whole function, in the target language.

        Aside from this its main task is to allocate registers for each target instruction, as the immediate code does not use any. Because the number of the registers is finite, it also needs to handle management of other data storage forms, such as the stack \cite{DragonBook}.

        More complex compilers are usually aiming to be \emph{retargetable} - that means they are equipped to support multiple back-ends for different compilation targets. There is a list of some of them in Chapter \ref{compiler}.

        Writing a compiler back-end is the goal of this thesis.

\chapter{Compiler Front-End Choice}\label{compiler}

As starting a new compiler from scratch would not be possible in the limited time frame of a bachelor thesis, I had to choose an existing front-end and provide a corresponding back-end part for the target platform.

This basically rules out all of the proprietary compilers and the selection limited to those from the world of free and open source software. In the end, the choice consisted of the following three.

    \section{GNU Compiler Collection}\label{gcc}

    The GNU Compiler Collection, more known as \texttt{GCC}, was started as a simple C compiler in 1985 by <NAME>. It is now one of the most widely used compiler suites not only in open source systems \cite{GccWeb}.

    Due to its huge history and background, its code base is stable and mature but it also is very hard to read due to historical reasons and the fact basically everything is wrapped in several layers of macros.

    The documentation of the inner functionality is hard to find and it is not very well arranged. Because of its heritage, the structure does not seem very transparent.

    Free Software Foundation and the GNU Project are holding governance over the development and are prohibiting major changes to the architecture or code style which drives many new developers away.\footnote{\url{http://gcc.gnu.org/ml/gcc/2014-01/msg00176.html}}

    \section{Low Level Virtual Machine}\label{llvm}

    LLVM is a modern project with a gaining popularity in past years for implementing the features very fast and providing of interesting and useful tools, like static analyzer.

    Its C and C++ front-end, Clang, is adding the latest features of the new language standards and their drafts sooner than the competitors.

    Compared to GCC, LLVM is a really young project. It was founded in 2005. The codebase is dynamically changing, written in C++ with heavy use of templates and automatically generated code \cite{LlvmWeb}.

    Its development is sponsored by companies like Google, for example to provide ability to run native applications in the browser (NaCl project, or especially its part PNaCl) or Apple, which utilizes the ecosystem in the official development toolkit provided for their products \cite{LlvmApple} \cite{LlvmNacl}.

    LLVM provides a very well documented intermediate representation of the compiled source code. Its documentation is publicly visible on their wiki page, every necessary detail is described and the community provides several easy ways to be approached.

        \subsection{Architecture}

        LLVM is strictly separated into front and back ends, divided by the LLVM intermediate code that is heavily optimized and is executable directly in a virtual machine (hence the name Low Level \emph{Virtual Machine})

    \section{Small Device C Compiler}\label{sdcc}

    SDCC is a simple (compared to the previous two) compiler aimed to be easily retargetable and provide a quality background for creating compilers for 8bit processors \cite{SdccWeb}.

    It is not a very large project (especially when compared to GCC and LLVM) and it uses parts (for example, the preprocessor) of GCC.

    It optimizes the compiled source code with focusing on issues appearing on small devices.

    The intermediate code is not documented very well (there is a list of all the iCodes on the project's wiki) but is simple enough to be understandable.

\chapter{Existing Solutions}\label{existing}

The idea of writing C compilers for PicoBlaze is not new. There has been a few projects implementing C compilers directly, or compilers of languages based on C. The most exposed ones are covered in this chapter.

    \section{PCComp}\label{pccomp}

    PicoBlaze C Compiler, the project of <NAME>, has its own page on SourceForge\footnote{\url{http://sourceforge.net/projects/pccomp/}},
    yet there are no files to download or source code in the repository and the only relevant activity visible is a question where to actually download the compiler.

    I managed to find a Windows binary in version 1.8.4 in a web archive and a user manual describing the compiler's features, both created in 2005 or 2006.

    However, the limitations of the compiler are vast. It generates stack-based code. This is unfortunate because PicoBlaze lacks any stack \cite{pccompman}.

        \subsection{Features}

        The compiler is not strictly following the C standard and implements only its small subset.

        The supported cores are PicoBlaze, PicoBlaze-2 and PicoBlaze-3.

        Only the support for byte and word (1 and 2 bytes) types was implemented.

        One-dimensional arrays without any pointer arithmetic are supported by the compiler.

        \subsection{Limitations}

        Type conversions are missing, as are variable modifiers (e.g. \texttt{volatile}).

        The compiler does not support any kind of resulting code optimization, except dead branch detection.

        The compiled assembly is often buggy or even nonfunctional and the probability of getting broken code is increasing with the complexity of the input source code and the arithmetic expressions in particular.

    \section{PBCC by <NAME>}\label{not_quite_c}

    This bachelor thesis was written on Faculty of Electrical Engineering of Czech Technical University in Prague in  2008 when only PCComp (Section \ref{pccomp}) existed.

    A compiler was written as a goal of the thesis, resulting in a small application able to compile a limited subset of the C programming language \cite{PbccNovacek}.

    Also, the source code is not to be found anywhere on the Internet, only the text part of the thesis was made public.

        \subsection{Features}

        The compiler only allows the user to compile a small subset of the actual ISO/IEC 9899:1999 standard.

        Processor support is limited to PicoBlaze-3.

        The types supported are \texttt{void}, \texttt{char} and \texttt{int}, again sized only 1 and 2 bytes.

        Only one-dimensional arrays are available to the user.

        Despite the simplicity of the compiler, there are some optimization methods implemented. For example, constant expressions are replaced by values directly.

        \subsection{Limitations}

        There is no support for any user-defined type, whether it is only an enumeration, a \texttt{typedef} type or a complex type (\texttt{struct} or \texttt{union}). This effectively limits the user to use only the basic types that are in this case integers sized one and two bytes.

        There is no expression conditions, strings and multidimensional arrays.

        These limitations are caused by the fact the author decided to write the compiler
        from scratch without use of any framework or front-end. The time needed to finish a complete C compiler is far beyond the time-frame of a bachelor thesis.

    \section{PBCC by <NAME>orník}\label{prev_pbcc}

    PicoBlaze C Compiler is a project sponsored by Virtuální laboratoř aplikovaných mikroprocesorů
    realized on the Faculty of Information Technology, Brno University of Technology.

    It was written in years 2010 - 2011 by <NAME> as a part of his master's thesis and is now maintained by <NAME>, supervisor of this thesis \cite{PbccProjekt}.

    The compiler is based on the Small Device C Compiler (SDCC) modified to provide support for the processor so it offers a subset of features of SDCC in version 3.0 \cite{PbccHornik}.

        \subsection{Features}

        There is support for adding further optimization methods provided by SDCC, additionally to its own optimization procedures
        that are ran during the compilation process on the intermediate code.

        Data types supported are integers large from 1 to 4 bytes, there is also no problem with converting them.

        Use of arrays (even multidimensional) and pointers is implemented, including their use as function parameters.

        PicoBlaze-6 was released only a few months after the inception of the thesis that was targeting the previous one, PicoBlaze-3. This topic is discussed in Chapter \ref{processor}. The main focus of the thesis was the older iteration of the processor, therefore function pointers and all other new features were left unimplemented.

        \subsection{Limitations}

        There is a list of known problems and limits list in the official documentation. To name a few, there is no support for getting or setting values on a memory address and limited support for global variables and interrupt vectors.

        The main reason to rewrite the compiler from scratch is to avoid carrying all the legacy instructions and features and to focus on the cleanest possible implementation of the current revision of the processor.

        The author also suggests allocating the registers by coloring them and using the information for better results when memory access frequency is taken in question.

        Unclear code copied over from other ports that is not very comprehensible is the reason why I wrote the whole program again while using just a few parts from the original code.

\chapter{Implementation Design}\label{design}

In this chapter, the technical details of the project are discussed.

The port itself is written in C++ with a layer wrapping the C internals of SDCC.

    \section{New Port Addition}\label{compilation}

        As this process is not documented anywhere in the SDCC documentation and doing it properly would require deep and good understanding of the GNU autotools toolchain, the following procedure was used to add the new port to the SDCC source:

        \begin{enumerate}

        \item Create a port source directory in \texttt{src/}, in this case, I was calling it \texttt{pblaze}.

        \item Add the basic source files in the port directory, for example \texttt{main.c} and \texttt{main.h}. \texttt{main.c} has to contain an instance of \texttt{PORT} structure containing information about the port specifications and pointers to functions that will be called during the compilation.

        \item A new (unique) port ID needs to be inserted into \texttt{src/port.h}:

        \texttt{\#define TARGET\_ID\_PBLAZE    16}

        \item And create an \texttt{extern} reference to the \texttt{PORT} instance from \texttt{src/pblaze/main.c}, for example:

            \begin{verbatim}#if !OPT_DISABLE_PBLAZE
            extern PORT pblaze_port;
            #endif\end{verbatim}

        \item In \texttt{src/SDCCmain.c}, insert a reference to the structure defined in \texttt{src/pblaze/main.c}.

        \end{enumerate}

            \subsection{Automation of new port addition}

            These tasks are automated in the included \texttt{glue.sh} script. When it is executed in  Bash\footnote{Bourne Again Shell, \url{http://www.gnu.org/software/bash/}} with the \texttt{SDCC\_HOME} environment variable set to point to the directory with both PBCC and SDCC source code, it completes all the necessary tasks.

        \section{Compilation}

        After the port was added, SDCC can be compiled. The steps to achieve successful compilation are:

        \begin{enumerate}
        \item \texttt{autoconf} creates a \texttt{configure} script to configure the components and compiler options of the final binary
        \item \texttt{./configure} is a script that compiles a Makefile for the compilation itself. It is possible, for example, to modify the optimization of the compiler binary or disable compilation of ports of architectures we will not need.
        \item \texttt{make} is the compilation script itself. You can speed the whole process by using the \texttt{-jX} argument specifying that \texttt{X} compiler processes should run at the same time.
        \end{enumerate}

    \section{SDCC Internals Wrapper}

    Using pure C library calls and macros in a C++ project would be a waste of potential of the language, therefore the project is built upon a wrapper library for the SDCC internals instead of using them directly.

    The whole wrapper library is included in the \texttt{wrap} modules.

        \subsection{Approach}

            Every SDCC structure that is vital for the process is wrapped in its own class. These classes are \texttt{Set}, \texttt{EbbIndex}, \texttt{EbBlock}, \texttt{SymLink}, \texttt{Symbol}, \texttt{Value}, \texttt{Operand} and \texttt{ICode}. Their SDCC counterparts are named the same, except they have lower-case initials.

            To provide the ability of implicit up-cast, the classes are directly inheriting the structures themselves.

            Each of the classes has its methods derived from the functions and macros that are operating over them in the SDCC internal library. The methods are partially hand-written and partially generated from the definitions in the header files.

            Aside from the methods, nothing was added to the classes. None of the methods is virtual. That means the memory footprint and binary compatibility with original structures is kept.

    \section{Utilities}

    The \texttt{util} module contains code for making the code in other parts of the projects easier to read and understand.

        \subsection{Emitter}\label{emitter}

        Every target code output in the C++ part of the port is handled using this class.

        It implements a \texttt{std::ostream}-like\footnote{Output stream class in the C++ Standard Template Library} (left shift operator overloading) API to be easy to spot in the code.

        There is one static instance of the class that is used to output from all other modules. The constructor was left open in case another separate output was needed. This option was left unused so far though.

        The class also provides a static member variable \texttt{i} for iterating when an instruction is being output. This allows the \texttt{Instruction} class that is being handled to be able to check the byte position in the multi-byte operands. This makes changing instruction forms (for example between \texttt{ADD} and \texttt{ADDCY}) possible. It is also used in the overloaded left shift operator for operands, to get their current needed byte.

        \subsection{Function}

        \texttt{Function} is a class containing public static members only. It provides information about the current function the compiler is processing such as parameter count and their sizes.

        Its main purpose is to compute which function parameters will need to be stored on the stack and which parameters will be passed through registers.

        The processing method is called every time the \texttt{FUNCTION} iCode is reached.

    \section{Register and Memory management}

    The code providing the functionality described in Section \ref{immediate} is located in the \texttt{ralloc} module.

    The entry point is the \texttt{Allocator} class, precisely its static method \texttt{assignRegisters} that takes the basic block index as its parameter.

        \subsection{Type support}

        PicoBlaze-6 supports one byte integer operations only, some with possibility to reuse the carry bit (see Appendix \ref{instrset} for the list of available instructions).

        Implementing floating point operations on such a simple device is neither feasible, nor actually usable. Emulating hardware support for any standard defining the format would result in huge memory use and each operation would take huge amounts of processor power.

        Advised usage in this case is to connect a hardware FP circuit over the I/O pins.

        \begin{table}[H]
        \centering
        \begin{tabularx}{0.9\textwidth}{*{7}{Y}}
        \texttt{char} & \texttt{short} & \texttt{int} & \texttt{long} & \texttt{long~long}& \texttt{void*} & \texttt{void(*)()}\\
        \hline
        1             &         2      &        2     &         4     &         4          &        1        &          2 \\
        \end{tabularx}
        \caption{Basic types supported by the compiler}
        \end{table}

        \subsection{Register Allocation}

        The register management is handled in the \texttt{Register} class. Two sets of \texttt{Register} instances are aggregated each in one \texttt{Bank} instance to provide the ability to switch the banks and pass operands between them.

        When there is no free register available, the LRU\footnote{Least Recently Used} algorithm is applied to find the one that is to be freed and stored in the scratchpad memory until the next use.

        \subsection{Stack Management}\label{stack}

        The stack is growing up, starting at the zero address. All stores and operations on both function entry and leave are processed in the \texttt{Stack} class which implements all necessary moves on the stack pointer (SP).

        Each of the stored variables has an instance of \texttt{StackCell} class assigned, containing the information about the offset from the pointer and the start of the variable.

        All variables are stored in big endian order, consecutively.

        The stack pointer is stored in the \texttt{sF} register, in both banks. On bank switch, it is propagated to contain the changes done to it.

        \subsection{Static Memory}

        Static memory, used for storage of global variables, is implemented in the \texttt{Memory} class.

        In most aspects, including the implemented interface, it is similar to the \texttt{Stack} (see Section \ref{stack}). The most important difference is no necessity to do anything on function calls and different implementation using only position in memory.

        It grows in the opposite direction to the stack, from the highest possible address in the memory - address \texttt{0xFF}.

        As in the case of \texttt{Stack}, the variables are stored consecutively in big endian order.

    \section{Code Generator}

    To avoid as much code duplication as possible, every instruction is being emitted using iteration over the \texttt{Emitter::i} variable in the manner displayed in the following code snippet.

    \begin{listing}
    \centering
    \begin{verbatim}for (Emitter::i = 0; Emitter::i < left->getType()->getSize(); Emitter::i++)
    emit << I::Xor(result, right);\end{verbatim}
    \caption{\texttt{Emitter} and \texttt{Instruction} example use}
    \end{listing}

    All instruction classes inherit from the generic \texttt{I} class that also acts as their parent and enclosing class both. It defines the \texttt{toString} virtual method that the children implement. This method is used in the overloaded left shift operator of \texttt{Emitter} (see Section \ref{emitter}) and \texttt{I} to obtain the whole string representation of the operation and write it into the output file.

        \subsection{Calling Conventions}\label{callconv}

        The calling conventions were designed to utilize as much of the variables as possible because of the limited capabilities of the processor.

        \emph{Caller saves} strategy is implemented by the compiler. That means the registers are saved to the function stack by the caller, not the callee function. Variable liveness is considered, dead variables are omitted.

        The arguments are stored consecutively in little-endian order\footnote{The least significant byte is stored first, the most significant one last} in the registers.

        By default, the first 8 registers are used for passing the arguments directly and the rest is stored on the stack of the callee. Their count can be modified by the compiler command line argument \texttt{--argregs=N}, with the maximum value of \texttt{N} being 13.

        For example, consider the following function:

        \begin{listing}
        \centering
        \texttt{int function(int l, long r);}
        \caption{Called function prototype}\label{lst:func}
        \end{listing}

        Its initial register utilization would be as follows:

        \begin{listing}
        \centering
        \begin{tabular}{ | c | c | c | c | c | c | c | c | }
            \hline
            \texttt{s0} & \texttt{s1} & \texttt{s2} & \texttt{s3} & \texttt{s4} & \texttt{s5} & \texttt{s6} & \texttt{s7} \\
            \hline
            \texttt{l[0]} & \texttt{l[1]} & \texttt{r[0]} & \texttt{r[1]} & \texttt{r[2]} & \texttt{r[3]} & free & free \\
            \hline
            \hline
            \texttt{s8} & \texttt{s9} & \texttt{sA} & \texttt{sB} & \texttt{sC} & \texttt{sD} & \texttt{sE} & \texttt{sF} \\
            \hline
            free & free & free & free & free & free & free & \texttt{SP} \\
            \hline
        \end{tabular}
        \caption{Register bank state when function from Listing \ref{lst:func} is called}\label{lst:regs}
        \end{listing}

        The returned value is stored in the first registers in the same way as the parameters were stored. Little-endian order limits the register use in the caller to the bare minimum. Returning structure values is not supported, pointer use is necessarry in this case.

        After the function has returned, caller (according to the caller saves strategy) restores its variables back into registers.

        \subsection{Function Pointers}

        As mentioned in new feature overview (this particular change is discussed in Section \ref{kcpsm6cmp}), the processor now supports jumping to labels and calling functions that have their address loaded on run-time.

        To make use of the new specification as much as possible, the compiler supports calling function pointers using the \texttt{CALL@} instruction.

        Prior to the instruction invocation itself, the function pointer is stored in the \texttt{sD} and \texttt{sE} registers. As the address of a function is larger than the size of one register, it has to be stored in two of them - \texttt{sD} contains the upper 4 bits of the address and \texttt{sE} the lower 8 bits.

        \subsection{Register Bank Utilization}\label{rbank}

        From the perspective of register banks, there are two types of functions (as there are two banks).

        The first type is either function \texttt{main} or a state when the program has not entered \texttt{main} yet - on initialization of global and static variables. This code has access only to variables stored in registers in Bank A.

        The other types are all other functions. These have access to registers in Bank B.

        The bank selection is handled from the code of the first type. This makes the other functions able to call any other function including itself. Any kind of recursion including \texttt{main} is not supported though.

        Before and after the call, bank has to be switched to the appropriate one. Also, if the function returned any value, it has to be transferred from the other bank to the current one before the bank is switched.

        In effect, this makes having most of the program logic in the \texttt{main} function, as it does not have to store most of its registers before calling a function, thus reducing the number of necessary \texttt{FETCH} and \texttt{STORE} instructions to move the local variables in the stack memory.

        \subsection{Assignment Generation}

        There are different cases we have to handle on assignment in the compiler.

            \subsubsection{Function Call Parameters}

            The compiler detects when the assignment is done in a function call. This means the available operand registers are already full, so the following arguments need to be stored on stack.

            These assignments are done preemptively, the variables go on stack directly. The stack pointer in the function will handle these as if they were saved there in the function body directly.

            \subsubsection{Dereferenced Pointer Assignment}

            The PicoBlaze-6 has only 256 bytes of scratchpad RAM (see Section \ref{mainfeatures}). This means the pointers to variables take only one byte of memory.

            Assignment to these variables is done using the \texttt{STORE} instruction. However, \texttt{STORE} cannot take a literal as its source data argument. Therefore, a temporary operand is allocated and used for temporary storage of the data being stored.

            \subsubsection{Temporary Variable on the Right Side}

            This case occurs when a temporary variable with a live scope that does not reach beyond the sequence number of the iCode containing this assignment. This usually occurs on an immediate computation in an complex expression.

            Instead of moving the variable, the registers are only reassigned to the result operand.

            \subsubsection{Other Cases}

            The other cases cover assignments with regular variables and literal values as operands. The temporary variables with longer life scope are included, too.

            There is nothing special on this case - the values are moved using the \texttt{LOAD} instruction. A \texttt{FETCH} is used first if the variable has been saved to memory.

        \subsection{Stack and Variable Storage}

        Local variables of the program are initially created in the registers. Only once there is not enough room for any other variable needed for an operation in future, it is freed from the register and stored (\emph{spilled}) on the stack.

        Stack pointer is stored only in register \texttt{sF} only in Bank B. Stack pointer is not tracked in the \texttt{main} function. As does register bank selection, this also makes recursive calls to \texttt{main} impossible.

        \subsection{Arithmetic Operations}

        Only basic arithmetic supported by the processor is implemented. More specifically, there is no basic support for neither multiplication nor division of the variables.

        The multiplication functions can be extracted from the previous PBCC (see Section \ref{prev_pbcc}) and inserted as inline assembly in a separate function, according to the calling conventions.

        The other arithmetic and logic operations of the C language are implemented, with focus on utilizing the new and improved instructions of PicoBlaze-6 to save computational cycles.

    \section{Compiled Assembly Properties}

    The compiler is producing commented assembly to be given to an assembler which then in turn produces its various binary equivalents or other formats, for example suitable for simulation.

    In this section, the vital properties, required for getting grasp of the code (for its further modification by hand or integrating hand tuned assembly code, for example), are discussed.

        \subsection{Comments in the Code}

        To improve the readability and comprehensiveness of the code, there are explanatory comments included in the compiled assembly.

            \subsubsection{Instruction Comments}

            Lines of most of the instructions contain a short comment explaining the instruction and its operands. This covers moves and arithmetic operations especially.

            To demonstrate, when the following code snippet is compiled:

            \begin{listing}
            \centering
            \texttt{int baz = 42 + foo - bar;}
            \caption{Example assignment}\label{lst:assign}
            \end{listing}

            Then, assuming the variable was not loaded in the registers beforehand and the other variables were already used (\texttt{foo} is in \texttt{s0} and \texttt{s1} and \texttt{bar} is in \texttt{s2} and \texttt{s3}), the resulting assembly will take the following form:

            \begin{listing}
            \centering
            \begin{verbatim}
            load    s4,     s0              ; iTemp0[0]=foo[0]
            load    s5,     s1              ; iTemp0[1]=foo[0]
            add     s4,     0x2a            ; iTemp0[0]+=42[0]
            addcy   s5,     0x0             ; iTemp0[1]+=42[1]
                                            ; iTemp1=iTemp0
            sub     s4,     s2              ; iTemp1[0]-=bar[0]
            subcy   s5,     s3              ; iTemp1[1]-=bar[1]
                                            ; baz=iTemp1
            \end{verbatim}
            \caption{Assembly output compiled from code in Listing \ref{lst:assign}}\label{lst:assignasm}
            \end{listing}

            Each byte in the operation is covered by the regular C-style array notation.

            Moves on temporary variables to next variables in a more complex expressions are optimized out, too. They are marked in the assembly to point out that another variable now resides in the particular registers.

            \subsubsection{Function Comments}

            Every function is prepended with a comment that states its name with a list of its arguments. Every argument's name is written in the list along with the registers it is stored in, in case it is not stored on stack directly.

            Demonstrated on an example:

            \begin{listing}
            \centering
            \texttt{char func(long arg1, int arg2, char arg3);}
            \caption{Example function to be compiled}\label{functocomment}
            \end{listing}

            \begin{listing}
            \centering
            \texttt{; Function func, arguments: [arg1:\{s0,s1,s2,s3,\},arg2:\{s4,s5,\},arg3:\{s6,\},]}
            \caption{Explanatory assembly comment before the label generated for Listing \ref{functocomment}}
            \end{listing}

\chapter{Port Features}\label{features}

    \section{Code Clarity}

    The extensibility and readability of this port is not comparable to any other port. The code generation itself takes only about 5 lines of code for each \texttt{ICode}, compared to tens to hundreds in PBCCv2(see Section \ref{prev_pbcc}).

    Providing a C++ API also helps by providing more syntax sugar for anybody who wants to further modify the compiler. Using class methods instead of macros and functions also adds the possibility to use an IDE\footnote{Integrated Development Environment} with method suggestion.

    \section{PicoBlaze-6 Support}

    There is no other C compiler designed to produce code exclusively for the newest revision of the PicoBlaze processor.

    The most modern ones support only PicoBlaze-3 so they miss the opportunity to save not only the program space (meaning less CPU cycles for the same program) but also the scratchpad memory and registers (which means the program will utilize less CPU cycles again).

    One of the cases when this is true is multi-byte variable comparison - equality check had to be done using many jumps and storing intermediate results, the new \texttt{COMPARECY} reuses the carry and zero values that are already in the flags.

    \section{Built-in Functions}

    The necessity to communicate with connected peripherals is satisfied by using the \texttt{char port\_in(char port)} and \texttt{void port\_out(char port, char value)} built-in functions.

    They are compiled into \texttt{OUTPUT}, \texttt{OUTPUTK} and \texttt{INPUT} instructions, respectively. \texttt{OUTPUTK} is used when it is possible. That is, when both operands are constant and the port is in the range \texttt{0x0} - \texttt{0xF}.

    As they are not really functions, when compiled to the assembly, there is no need to use the registers designated for function calling. The first available registers are used instead of \texttt{s0} and \texttt{s1} (as specified in Section \ref{callconv}).

\chapter{Testing and Evaluation}\label{evaluation}

It is necessary to evaluate the overall success of a compiler project by testing it and comparing it to the alternatives. In this section, the testing and comparison methods are described.

    \section{Testing}\label{testing}

    Several example source files were compiled and ran in a simulator to prove the resulting assembly corresponds to the input source code.

        \subsection{Tools and the Testing Process}

        \texttt{PBlazSIM} (described in Section \ref{pblazsim}) was chosen to simulate the resulting code due to its simplicity, maturity and liveliness of the upstream developers.

            \subsubsection{Obtaining the Simulation Result}

                The simplicity of \texttt{PBlazSIM} cleared the way for modifying of the (small) codebase and including it as a part of the test-suite in this project.

                The only modification done is as follows: When the simulation ends because of an error or reaches the correct final state of the simulation (this happens once it  the \texttt{BREAK} internal opcode is processed), it prints the state of the processor to the standard output.

                The output is formatted for easy parsing and use in the attached test suite.

            \subsubsection{Assembler}

                The input to \texttt{PBlazSIM} are rich assembly language files enhanced with binary representation of the code it is about to simulate. This format is compiled using \texttt{PBlazASM} (see Section \ref{pblazasm}) using the \texttt{\-l} flag and results in a file with \texttt{.LST} extension.

                There were no special modifications required to get the needed results except the ones mentioned in Section \ref{pblazasm}.
\newpage
        \subsection{The Framework}

        All scripts are ran recursively for each \texttt{.c} and \texttt{.tst} file in the \texttt{test} directory in the root of the code tree.

        Every \texttt{.c} file has to have its \texttt{.tst} counter-part with the same base name to be considered a valid test.

        It tests the memory and the registers for presence of any value given (with the exception of omitted zero values, considering major part of the memory will be free in most cases), be it on a specifically given position or anywhere.

        It is also possible to test \texttt{ZERO} and \texttt{CARRY} flags of the processor.

            \subsubsection{Test File Format}

            The \texttt{.tst} file format requires every such file to include declaration of every of the following variables:

            \begin{center}
            \begin{tabular}{ r | l }
                \texttt{stored\_somewhere} & Array, bounds undefined. \\
                & Each value contained in it is looked for in the memory and \\
                & register dump. The value can be contained anywhere. \\

                \texttt{stored\_there} & Array of 256 values. \\
                & If there is a value X on position Y, the memory has to contain \\
                & value X on position Y too. \\

                \texttt{bankA} & Array of 16 values. \\
                & Contains a value for each of the registers in the bank. \\

                \texttt{bankB} & Analogic to \texttt{bankA}, for bank B.

            \end{tabular}
            \end{center}

            The variables are declared and defined in pseudo-C style (without the type specification), that means: enumerations take a brace-enclosed list as their initializer and Boolean values can be either \texttt{true} or \texttt{false}.

            Every definition has to be ended with a semicolon. Double definitions will result in a failing test.

            For example, the following declaration will check all memory locations to contain the values 1, 2 and 3:

            \begin{center}
                \texttt{stored\_somewhere = \{1, 002, 0x3\};}
            \end{center}

            And the following declaration says register \texttt{s2} has to contain value \texttt{0xFF} - other registers are omitted (because they are equal to zero).

            \begin{center}
                \texttt{bankA = \{0, 0, 0xFF, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0\}};
            \end{center}
\newpage
        \subsection{Test Cases}

            This is the list of the included and applied test cases that were also ran and checked in the simulator.

            \begin{center}
            \begin{tabular}{ r | l }
                \texttt{null} & Does not compute anything, tests if the whole stack works \\
                \texttt{basic} & Basic variable assignment \\
                \texttt{arithmetics} & Addition and subtraction \\
                \texttt{array} & Array (pointer) data assignment and reading \\
                \texttt{bitoper} & Binary operations on the variables \\
                \texttt{cond\_simple} & Simple condition evaluation \\
                \texttt{cond\_complex} & Complicated condition and cycle evaluation \\
                \texttt{func\_simple} & Basic function calling \\
                \texttt{func\_recursive} & Recursive function calling \\
                \texttt{func\_ptr} & Function pointer calling - functionally equivalent to \texttt{func\_recursive} \\
                \texttt{struct} & Structure operations \\
            \end{tabular}
            \end{center}

            The code of the tests is completely synthetic, with no real world purpose. Some variables had to be defined as \texttt{volatile}, to avoid their optimization which would remove some of them completely, defeating the purpose of testing the mentioned features.

    \section{Evaluation}

    Due to the fact neither the source code of PBCC by <NAME> nor PCComp is publicly available, also considering the simplicity of the other compilers, only the previous PBCC projekt by <NAME> was used in comparison (see Chapter \ref{existing} for more details).

    The same test cases were used as in the functionality testing (described in Section \ref{testing}).

    The tests were designed to be compileable in all other compilers, except the cases when an unavailable feature is being tested.

    The quality metric (in case the program compiles and is valid) was chosen to be the count of used instructions.

    \begin{table}[H]
    \definecolor{lightlightgray}{gray}{0.95}
    \rowcolors{1}{lightlightgray}{}
    \centering
    \begin{tabularx}{0.8\textwidth}{r *{2}{Y}}
\hline
test case          & PBCCv3 (this project) &     PBCCv2 (Horník)     \\
\hline
\verb|basic|       &\checkmark(\textbf{23})&\checkmark(62)           \\
\verb|arithmetics| &\checkmark(\textbf{19})&\checkmark(26)           \\
\verb|array|       &\checkmark(\textbf{70})&$\times$(internal error) \\
\verb|bitoper|     &\checkmark(\textbf{29})&\checkmark(49)           \\
\verb|cond_simple| &\checkmark(\textbf{56})&\checkmark(87)           \\
\verb|cond_complex|&\checkmark(\textbf{33})&\checkmark(53)           \\
\verb|func_simple| &\checkmark(\textbf{35})&\checkmark(51)           \\
\verb|func_recurs| &\checkmark(\textbf{44})&$\times$(infinite recursion)\\
\verb|func_ptr|    &\checkmark(\textbf{51})&$\times$(no support)     \\
\verb|struct|      &\checkmark(55)         &\checkmark(\textbf{52})           \\
\hline

    \end{tabularx}

    \emph{\checkmark(instruction count)} for succeeded cases, \emph{$\times$(reason)} for failed cases
    \caption{Test results}
    \end{table}

    PBCCv3 gives shorter code for most test cases, except the cases when PBCCv2 fails. In PBCCv2, cases \texttt{array} and \texttt{func\_ptr} failed in the compilation phase and no output was produced. The test case \texttt{func\_recurs} compiled fine. However, when simulated, the processor got stuck in an infinite call loop and stopped eventually.

    The only case when PBCCv2 gives shorter code is for the \texttt{struct} test case. This is caused by the slight overhead needed for calling a function between register banks (explained in Section \ref{rbank}).

\chapter{Conclusion}\label{conclusion}

The back-end project was started from scratch except for some output wrapper code, therefore the expected functionality was not a complete C compiler. The implemented subset is able to compile a wide range of test applications.

Considering the produced code quality, the compiler is better, compared to the alternatives. On the applied test set, the produced code is on average 33\% shorter than the code compiled with the previous PBCC. It is also more understandable by the extensive usage of generated explanatory comments.

If taken as an exercise and exploration of the limits of the processor, the project succeeded, too. Function pointers are really usable and testing applications utilizing them work correctly. There is also basic support for pointer assignment which is then utilized in array and structure usage.

\section{Future Development}

The compiler was tested on synthetic cases only. Real world complex applications are needed to be tested with the compiler to have potential issues or inefficiencies fixed.

Some features lack at this moment, too, such as an implementation of integer division and multiplication or interrupt table generation.

The back-end was also designed to be partially portable to other front-ends. It could be used with LLVM, for example, to achieve the ability to compile programs written in other languages. too.

%=========================================================================

languages: Markdown TeX

repo_name: MartinBriza/bcThesis


text:
<file_sep>## Alveo
Alveo is a real-time trading application for charting and performing technical analysis of the markets.

To download the platform: https://apiaryfund.com/software

To request features & report bugs: https://apiaryfund.com/develop

## Setting Up Visual Studio for Alveo Development
<!--TODO:Insert screenshots-->
1. Open the Visual Studio Solution from the repository
2. Locate the dll's
  *  The dll's can be found in the Alveo folder under C:\\Program Files\\Alveo
  *  **You may need to show hidden files in windows explorer to view the dll files**
3. Reference the dlls in the Visual Studio solution
  *  In the UserCode Solution Right click on References and select *Add Reference*
  *  Click *Browse* and navigate to the location of the dll files
  *  Select the dll files and press *Add*

## Creating an Indicator
Look at an [example](https://github.com/marlais/Alveo/blob/master/Code/Indicators/Aroon.cs) indicator.
<!--TODO: Explain basic indicator creation-->

Look at the [Wiki](https://github.com/marlais/Alveo/wiki) for additional information on creating an indicator

## Using Custom Indicators
<!--TODO: Add screenshots-->
Custom indicators can be used in Alveo
1.  Open Alveo
2.  Select *Code*
3.  Select *Editor*
4.  Paste the code for the indicator into the editor and press the green *build* button
5.  Select the indicator from the indicators list

branch_name: refs/heads/master

repo_language: Markdown


text:
<repo_name>lsamano/yarn-farm-app<file_sep>/app/models/item.rb
class Item < ApplicationRecord
  has_many :cart_items
  has_many :orders, through: :cart_items
  # has_many :users, through: :orders
end
<file_sep>/app/models/user.rb
class User < ApplicationRecord
  has_secure_password
  has_many :orders

  def cart
    #grabs most recent cart (ex. the only open order)
    open_cart = self.orders.last
    # OrderSerializer.new(open_cart)
    {
      id: open_cart.id,
      items_in_cart: open_cart.items_in_cart
    }
  end
end
<file_sep>/app/serializers/cart_item_serializer.rb
class CartItemSerializer
  include FastJsonapi::ObjectSerializer
  # attributes
  belongs_to :item
end
<file_sep>/app/models/order.rb
class Order < ApplicationRecord
  belongs_to :user
  has_many :cart_items
  has_many :items, through: :cart_items

  def items_in_cart
    self.cart_items.map do |cart_item|
      item = cart_item.item
      {
        id: cart_item.id,
        item_id: item.id,
        name: item.name,
        price: item.price,
        quantity: cart_item.quantity
      }
    end
  end
end
<file_sep>/app/serializers/order_serializer.rb
class OrderSerializer
  include FastJsonapi::ObjectSerializer
  has_many :cart_items
end
<file_sep>/app/controllers/api/v1/orders_controller.rb
class Api::V1::OrdersController < ApplicationController
  def checkout
    @order = current_user.cart
    # checkout logic
    Order.create(user: current_user)
  end
end
<file_sep>/db/seeds.rb
# This file should contain all the record creation needed to seed the database with its default values.
# The data can then be loaded with the rails db:seed command (or created alongside the database with db:setup).
#
# Examples:
#
#   movies = Movie.create([{ name: 'Star Wars' }, { name: 'Lord of the Rings' }])
#   Character.create(name: 'Luke', movie: movies.first)
CartItem.destroy_all
Item.destroy_all
Order.destroy_all
User.destroy_all

user = User.create(
  username: "Eme",
  password: "eme"
)

order = Order.create(user_id: user.id)

item1 = Item.create(
  name: "Bernat Maker Home Dec Yarn",
  price: 9.99
)

item2 = Item.create(
  name: "La Mia 100% Merino Wool Yarn",
  price: 20.99
)

  CartItem.create(
    order_id: order.id,
    item_id: item1.id,
    quantity: 2
  )

  CartItem.create(
    order_id: order.id,
    item_id: item2.id,
    quantity: 1
  )

puts "Seeded."
<file_sep>/app/controllers/api/v1/users_controller.rb
class Api::V1::UsersController < ApplicationController
  skip_before_action :authorized, only: [:create, :index, :show]
  before_action :find_user, only: [:show, :update, :destroy]

  # TODO: This is just for dev purposes
  def index
    render json: UserSerializer.new(User.all)
  end

  # TODO: This is just for dev purposes
  def show
    render json: UserSerializer.new(@user)
  end

  def profile
    render json: { user: UserSerializer.new(current_user) }, status: :accepted
  end

  def create
    @user = User.create(user_params)
    if @user.valid?
      # make JWT
      @token = encode_token({ user_id: @user.id })
      # make empty cart/order
      Order.create(user_id: @user.id)
      render json: { user: UserSerializer.new(@user), jwt: @token }, status: :created
    else
      render json: { error: 'failed to create user' }, status: :not_acceptable
    end
  end

  def update
    @user.update_attributes(user_params)
    if @user.save
      render json: UserSerializer.new(@user)
    else
      render json: { error: 'failed to update user' }, status: :not_acceptable
    end
  end

  def destroy
    @user.destroy
    render json: { success: true, message: 'user deleted' }
  end

  private

  def find_user
    @user = User.find(params[:id])
  end

  def user_params
    params.require(:user).permit(:username, :password, :bio, :avatar)
  end
end

repo_language: Ruby

repo_name: lsamano/yarn-farm-app