# 2. Processor instruction set

## Exercise outline

1. introduction and familiarise with MIPS architecture simulator QtMips
2. test program for simple addition
3. following tasks extending the program
4. the 1. homework assignment (on the page https://dcenet.felk.cvut.cz/apo/

## What should I repeat before the exercise

1. Purpose and mnemonic of the basic instructions of the processor
2. Familiarize with MIPS architecture simulator QtMips and simulation of execution of a simple program
3. Notice the 1. homework (https://dcenet.felk.cvut.cz/apo/)

## What shall we do

Gain an understanding of how are the machine instructions executed/processed by a simple processor.

The simplicity, straightforwardness, and orthogonality of the instruction encoding is an essential reason why most textbooks choose as a model architecture MIPS processor. The processor reads instructions encoded in binary form. PC-class personal computers do not allow us to execute MIPS-based machine code directly on their processor (architecture X86), but there exist many simulators of this architecture. The simulator QtMips was developed to support the practical experience of this course.

### Part 1 - Basic instruction - description and use

Detailed description:

Instruction Instruction Syntax Operation Description
add add \$d, \$s, \$t \$d = \$s + \$t; Add: Add together values in two registers (\$s + \$t) and stores the result in register \$d. addi addi \$t, \$s, C \$t = \$s + C; Add immediate: Adds a value in \$s and a signed constant (immediate value) and stores the result in \$t. sub sub \$d,\$s,\$t \$d = \$s - \$t Subtract: Subtracts a value in register \$t from value of \$s and stores result in \$d.
bne bne \$s, \$t, offset if \$s != \$t go to PC+4+4*offset; else go to PC+4 Branch on not equal: (conditional) jump if value in \$s is not equal to a value in \$t.
beq beq \$s, \$t, offset if \$s == \$t go to PC+4+4*offset; else go to PC+4 Branch on equal: (conditional) jump if value in \$s is equal to a value in \$t.
jump j C PC = (PC ∧ 0xf0000000) ∨ 4*C Jump: Unconditional jump to label C.
lw lw \$t,C(\$s) \$t = Memory[\$s + C] Load word: Loads a word from address in memory and stores it in register \$t. sw sw \$t,C(\$s) Memory[\$s + C] = \$t Store word: Stores a value in register \$t to given address in memory.
lui lui \$t,C \$t = C << 16 Load upper immediate: Stores given immediate value (constant) C to upper part of register \$t. Register is 32 bits long and C is 16 bits. la la \$at, LabelAddr lui \$at, LabelAddr[31:16]; ori \$at,\$at, LabelAddr[15:0] Load Address: stores a 32 bit (address of) label and stores it to register \$at. This is a pseudo-instruction - it is translated into sequence of actual instructions.

A more detailed description of the instructions can be found at Wikipedia https://en.wikipedia.org/wiki/MIPS_architecture.

Autoritative description of architecture https://www.mips.com/:

### Translation of assembler source code to machine code

There is no restriction to use any plain text editor for writing assembler source code. In the laboratory, there are installed more text editors and development environments. For example vim, Emacs, etc. We suggest to select Geany for those who have no personal preference.

Open a text editor and prepare simple assembler source file named simple-lw-sw.S. The suffix capital “.S” is crucial. This suffix is assigned by standard development tools for the source files/code in assembler language and compiler decides according to the suffix how to process the file. Other recognized suffixes are .c for C language source files. .cc or .cpp for C++, .o for object files (files which content is already translated source code into target machine native instructions but there is not defined to which address will be these code fragments located). Library files suffix .a (archive) is used for functions libraries, which are included in final executable according to their requirements/use by other files. A final executable file (program) is stored without extension on Unix class systems..

.globl _start
.set noat
.set noreorder

.text

_start:
lw     $2, 0x2000($0)
// store the word to absolute address
sw     $2, 0x2004($0)

loop:
// stop execution wait for debugger/user
break
// ensure that continuation does not
// interpret random data
beq    $0,$0, loop
nop

.data

src_val:
.word  0x12345678
dst_val:


Assembly code source file consists of

• instruction mnemonics which represent an abbreviation of operation (lw - load word, sw - save word, add, sub - subtract), the operands can follow after operation mnemonics. Operands are usually numbers or another specification of registers and immediate numeric constant operands. Operands are separated by comma.
• labels (followed by a colon). It is possible to reference these labels from some instruction operands and directives to store raw words or other data into memory. The address to the memory location following the label (instruction or data) is stored in the instruction field or other memory location in the place from which is the label referenced.
• control directives (pseudo-instructions) for assembly compiler, they usually start by a dot .
• comments, source files designated by capital .S suffix are preprocessed before actual translation to machine code/object files. The rules for preprocessing are the same as for the C compiler, and the same format of comments can be used.

The following directives are used in the provided sample code

• .globl - symbols identifiers following the directive are visible/accessible even outside actual compilation unit. The symbol _start or _ _start specifies program entry point by the convention.
• .set noat - disallow use of temporary assembler register which is used for the realization of some higher level instructions translated by the assembler to the sequence of machine instructions. For example la (load address), which is macro instruction translated by assembler to the sequence of lui and ori instructions.
• .set noreorder - forbid instructions reordering by assembler. Assembler is able to optimize ordering of some instructions which allows to fill delay-slots (these are not used by initial simulator setup for simplicity), reordering is not desirable for our code
• .ent jméno - the mark for start of a function
• .end jméno - the mark for end of a function
• .text - switch to fill .text section which is used to store actual program machine instructions
• .data - switch to fill .data sections which holds initialized data/variables/arrays
• .word - the directive to store into actually filed section value specified after the directive

The complete manual for GNU assembler and all its directives can be found at GNU assembleru.

The compilation is performed by cross-compiler mips-elf-gcc (cross-compiler means that compiler host system, PC in our case, is different than compilation target system with MIPS architecture).

mips-elf-gcc -Wl,-Ttext,0x1000 -Wl,-Tdata,0x2000 -nostdlib -nodefaultlibs -nostartfiles -o simple-lw-sw simple-lw-sw.S

The invocation requires multiple parameters, because standard programs in C language require linking of initialization sequences and library functions. But our actual goal is to describe the lowest level without this automatization the first which allows understanding how it is extended and equipped by automatic initialization sequences and constructs which allows comfortable code writing of programs at a higher level and in higher level languages. Parameters -Wl, are passed to the linker program and specify to which address is located .text section with program instructions and to where starts .data section with initialized variables. Following parameters in the order of their appearance disable automatic addition of startup and initialization sequence (-nostartfiles) and disable use of standard libraries. The file name after switch -o specifies the name of the final executable file (output). File names of one or more source files follow.

The simple-lw-sw project with appropriate Makefile can be found in /opt/apo/qtmips-semstart directory.

On Windows, complete MSys with make utility can be installed or plain compiler mips-elf-gcc-i686-mingw32 can be called from following batch file.

PATH=%PATH%;c:\path\to\mips-elf-gcc-i686-mingw32\bin
mips-elf-gcc -Wl,-Ttext,0x1000 -Wl,-Tdata,0x2000 -nostdlib -nodefaultlibs -nostartfiles -o simple-lw-sw test.S

QtMips simulator is used to execute the program. Select the most simple variant of simulated processor “No pipeline no cache”. Button “Browse” is used to select executable file name (simple-lw-sw without suffix in our case) for field “Elf executable”.

Select tab Core next and disable checkbox Delay slot. This configuration makes simulator to diverge from real MIPS architecture, but it is more straightforward for initial experiments. The program is written in the mode set .noreorder is translated 1:1 to the instruction sequence for this setup and branch instruction execution would be more intuitive - they are processed immediately. We return to this topic later with full reasons for real processor behavior.

The diagram with the processor is opened. Use double-click on program counter register (PC) opens program listing with actual instructions. Double click on registers blocks opens a view with the list of architectural registers. Double click on data memory shows memory content. The windows layout shown on the next picture is the appropriate and intuitive starting point

Select “Follow fetch” option in the “Program” listing window which highlights instruction/line actually fetched by the processor for execution. The start of listing in “Memory” windows should be set to the address 0x2000 on which data value 0x12345678 was placed. The program can be stepped through by “Machine” → “Step” menu entry or by the corresponding button on the toolbar. The value is loaded to the register first, and then it is stored to the following memory cell.

Change the program to process a load-store sequence in the loop. Instruction break has to be removed from the loop because its purpose is to stop program execution when reached. Test that edited value at address 0x2000 is always copied to the address 0x2004. Modify the program to add two input values on 0x2000 and 0x2004 address and stored the result at address 0x2008.

Next step is to modify the program to add two vectors with a length of four words. Use assembler macroinstruction la vect_a (load address) to set registers to point to the start of the vectors.

    ...
.data

vect_a:
.word  0x12345678
.word  0x12345678
.word  0x12345678
.word  0x12345678
vect_b:
.word  0x12345678
...

Continue with implementation of the program to compute an average value from eight numbers.

### Automate program compilation by use of Makefile

The compiler invocation is desirable to document at least and better automate. The one way is to use a script with the sequence of commands required for compilation. Such script can be written directly for shell - command line interpreter (BASH or DASH on GNU/Linux usually). But it is not practical to translate all compilation units of a larger project when only small change modifies only one or a small subset of source files. More different systems have been developed to automate exactly these tasks. Some examples are Make, Ant, qmake, Cmake, meson, etc.

#### Makefile

Make is the tool which allows to automate compilation of source codes, description of the compilation process is described in Makefile.

Makefile template for the compilation of source files written in assembly language or C language for MIPS simulator environment:

ARCH=mips-elf

CC=$(ARCH)-gcc AS=$(ARCH)-as
LD=$(ARCH)-ld OBJCOPY=$(ARCH)-objcopy

CFLAGS  += -ggdb -O1
AFLAGS  += -ggdb
LDFLAGS += -ggdb
LDFLAGS += -nostdlib -nodefaultlibs -nostartfiles
LDFLAGS += -Wl,-Ttext,0x1000 -Wl,-Tdata,0x2000

all:default

.PHONY:clean

%.srec:%
$(OBJCOPY) -O srec$< $@ %.o:%.S$(CC) -D__ASSEMBLY__ $(AFLAGS) -c$< -o $@ %.s:%.c$(CC) $(CFLAGS)$(CPPFLAGS) -S $< -o$@

%.o:%.c
$(CC)$(CFLAGS) $(CPPFLAGS) -c$< -o $@ # default output default:change_me.srec # executable file:object file.o change_me:change_me.o$(CC) $(LDFLAGS)$^ -o \$@

# all generated that would be cleaned
clean:
rm -f change_me change_me.o change_me.out change_me.srec

tab character has to be used to indent of commands in the Makefile. Makefile does not recognize indent by spaces.

Makefile consists from definitions (assignment of values to variables) and rules. The rules start by a line which defines dependency of rule target(s) on the dependencies listed after the colon. The dependencies are names of files or abstracts commands which as to be (make) available before the commands following the first rule line can create required results. File names can be complete names or their base part can be substituted by character “%” which allows specifying rule for a whole class of transformations from one compilation stage to another. Even more complete template for the compilation of assembler and C source files to MIPS target platform with an automatic building of dependencies on header files can be found in directory /opt/apo/qtmips_template on the computers in the laboratory.

#### Compilation

A compilation is invoked by a command make (the make has to be invoked in the directory where Makefile and program source code are located). Make generates multiple output files. The file without an extension is used for execution in QtMips environment. The process of compilation translated the compilation unit (one source wile together with includes header files for a simple case) into object files (.o) in relocatable form. Object files are then collected by the linker which resolves address references between compilation units and locates code to the final addresses. It is necessary to equip the actual sequences of machine instructions by the envelope which specifies where to fill references during .o files linking during the final placement on the specified addresses. Even instruction and data in the final executable form usually require some information for operating systems where they should be loaded/mapped in the memory or process address-space. The ELF (Executable and Linkable Format) is used to store these metadata in our case and generally on most of the modern systems.

#### Determine variable addresses and correspondence of source code and final ELF executable

Next command can be used to find addresses of the final location of variables and data entries after linking

mips-elf-nm program

The list of sections and their locations can be listed by

mips-elf-objdump --headers program

List final machine code after translation with corresponding source lines

mips-elf-objdump --source program

1. learn how to use compiler and simulator
2. change program to run memory read and write in a loop (try to modify program directly in the simulator, change break to nop)
3. computation with vector - return to the source and define vectors vec_a, vec_b, vec_c - four word elements each and use lw, sw and add instructions to compute vec_c[0] = vec_a[0] + vec_b[0]
4. extend program to compute sum for each vec_c element in introduced the inner loop
5. implementation of program to compute n-th member of Fibonacci series
6. start of the work on bubble-sort algorithm
• GNU MIPS-ELF corss-compiler - compiler of C language and assemblr, packages for Debian GNU/Linux x86_64, i586 and Windows, configuration and build of compiler form its source code
• gcc-binutils-newlib-mips-elf_4.4.4-1_mingw32.zip - MIPS-ELF GCC 4.4.4 compiled for MinGW32 (Windows) - it requires to use switches -lm -lgcc -lc for larger programs, for simple programs in assembler without libraries, next options are required -nostdlib -nodefaultlibs -nostartfiles
• MIPS processor description - including instruction set
• Missouri State University - Nice simulator in Java language
• It requires assembly without macro-definitions (preprocessed).

gcc -E assembler.S -o preprocessed-pro-mips.s can be used for preprocessing.