CS61C Spring 1999
Section 23 TA: Gek Siong Low (cs61c-tb)
Week 2 Discussion notes
Big and Little Endians
The professor mentioned Big and Little Endians in class, so I'll just elaborate here on what they mean and their implications.
Basically, endian means "which end comes first?" Recall the diagram for big/little endians:
3 2 1 0 <- Little Endian Architectures: Intel, DEC Alpha
-----------------
msb | | | | | lsb
-----------------
0 1 2 3 <- Big Endian Architectures: HP PA, Sparc, PowerPC
When you address a (4-byte) word, the pointer is pointing to byte 0. So on a Little Endian machine, the bytes are in reverse order:
-----------------
lsb | | | | | msb
-----------------
0 1 2 3 <- Little Endian (with bytes going from 0 to 3, left to right)
This should look familiar to those who have hacked the save files of PC games before, e.g. to get some special item for an RPG game. In a hex editor, you'll notice that the numbers you are searching for are in reverse byte-order, so to hack your character's money from 500 (01F4 in hex) to 65535 (FFFF in hex), you have to search for the bytes F401 instead. By the way, games nowadays have become so complicated and "hack-proof" that this simple search technique no longer works. This example is simply an illustration.
How do Endian-ness affect you? Not for game-hacking of course. Endian-ness generally is not an inssue if you are writing software for one platform/machine, but they have to be considered when your applications must share data across architectures. For example, numerical data written directly to a file on a Big Endian machine as integers/floats cannot be read correctly by a Little Endian machine without conversion. In networks, when Big Endian machines communicate with Little machines, they must convert from one Endian to the other. Special routines are provided for these tasks in the network libraries. You'll see more of this if you take EECS122.
Registers and Spilling
There are 32 registers in MIPS, and although you can (in theory) use all 32 registers whichever way you want, conventions do exist to make life easier (it's true) for programmers and you should follow them when writing MIPS programs. The OS expects that you follow these conventions too.
The professor mentioned spilling in lecture, so I'll elaborate on that here. When compiling a program, the compiler will decide on the best way to allocate the registers for each section of code. We want the variables to be in registers as much as possible because registers are the fastest memory in the computer. It may be that 32 registers are not enough to store all variables, and therefore the compiler will spill some variables. It simply means that these variables will be stored in main memory and fetched when they are needed. Of course, that would be much slower because of the overhead in fetching to and from main memory.
There is no standard or 100% efficient way to decide which variables should be spilled. Compilers tend to use certain heuristics to decide. One common heuristic is to find out which variables are least frequently referenced and spill those variables, but it is no guarantee that there is no more efficient way. Register allocation is studied in detail in CS164. For this class, I guess you simply need to know what spilling is and why we do it.
Some notes on memory addressing
Every MIPS program has a data segment and a text segment. Your program is in the text segment and static data is in the data segment. When you do a lw or sw, the address in the register is usually the address of some label you've declared in the data segment (it can also be on the heap, but that's for later).
Example:
.data
message: .asciiz "Hello world!"
i: .word 100
j: .word 200
k: .word 300
Note that lw and sw uses byte-addressing. That is, the address is in bytes. But words stored in memory have to be word-aligned for efficiency (it's a hardware design issue), and thus the byte addresses must be multiples of 4.
Branches, however, use word-addressing, because all instructions are 4-bytes long, and therefore the additional 2 bits (we'll do binary numbers later) at the end are implicit. This may be a point of confusion for some, so I'll just mention it here so you'll be prepared. The fact that all instructions are exactly 4-bytes is one of the beauties of RISC (Reduced Instruction Set Computing). It makes hardware design so much simpler - register references, opcodes, etc are always in the same place. Compare this with CISC (C for "Complex") where instructions can be any length and it is very difficult to design hardware that can deal with variable lengths. So here's one reason why Intel chips have so many bugs! :-)
C to MIPS
It is fairly straightforward to convert from C to MIPS. Going the other way is not so trivial, because there are so many ways to write an equivalent MIPS program. Compilers usually translate C code to assembly and then perform optimization before writing out machine code, so if you disassemble a piece of compiled C code it may not be possible to match it with your C source. Optimization can be turned off with the gcc compiler. You'll see a lot of these in CS164.
Here are some simple ways to write MIPS code for C decision blocks, presented as diagrams for easy understanding (as few actual MIPS code as possible). You simply "fill in the blanks".
1. if pred then A else B
MIPS:
test pred and branch -----.
----------------- |
| | |
| code for B | |
| | |
----------------- |
j exit |
True: ----------------- <--------.
| |
| code for A |
| |
-----------------
Exit:
2. while pred { body } do { body } while pred
MIPS: MIPS:
Loop: test pred and branch ------. Loop: -------------------
-------------------- | | |
| | | | code for body |
| code for body | | | |
| | | -------------------
-------------------- | test pred and branch ---.
j Loop | j Loop |
Exit: <----------. Exit: <---------------.
Note that these are not the only way to write the MIPS code, sometimes you can eliminate one or two instructions here and there. Be very careful with your branch conditions - do you need to test the complement (negative) condition instead?
Remember that labels should be unique. Don't go around writing True labels everywhere.
Jump Address Table
The case statement can be written as one huge if-then-else or using the jumptable. Here's a diagram of what a jumptable actually looks like in memory:
Memory:
---------------
base_addr --> | --+---> pointers to some code section -------------.
|-------------| |
| --+------------------------------------------. |
+ |-------------| | |
| | | |
an index |-------------| | |
| | | |
k | |-------------| | |
| | | | |
| | | | |
V | | | |
| | | |
| | | |
--------------- | |
| |
| |
MIPS code: | |
.data (this is how the jumptable may be declared) | |
jumptable: | |
.word L1 | |
.word L2 | |
.word L3 | |
| |
.text | |
| |
la $t0 jumptable # this is the base_addr | |
test if k is out-of-range | |
calculate 4*k, store in some register, say $t1 | |
add $t0 to $t1 # now $t1 points to an entry in the jumptable | |
lw $t1, 0($t1) # now $t1 has the contents of that entry, | |
# which points to some code | |
jr $t1 # jump to that code | |
| |
L1: -------- <-----------------------------------------------------. |
| | |
| code | |
| | |
-------- |
j Exit |
L2: -------- <-----------------------------------------------------------.
| |
| code |
| |
--------
j Exit
.
.
.
Exit:
I hope this diagram would clarify the concept somewhat.
Example C to MIPS translation
This is one way to implement the strcpy() function:
C code:
int strcpy(char *out, char *in) {
int i;
char c;
i=0;
do {
c=in[i];
out[i]=c;
i++;
} while (c!='\0');
return i-1;
}
MIPS code:
.data
inbuf: .asciiz "Hello World!"
outbuf: .byte 0:100 # reserves 100 bytes of zeros
.text
__start:
la $a0, outbuf # these are our parameters
la $a1, inbuf
add $t1, $t1, $zero # i=0
loop:
add $t2, $a1, $t1 # addr of in[i]
lb $t3, 0($t2) # c=in[i]
add $t2, $a0, $t1 # addr of out[i]
sb $t3, 0($t2) # out[i]=c
addi $t1, $t1, 1 # i++
bne $t3, $zero, loop # while (c!='\')
addi $t1, $t1, -1 # i-1
add $v0, $t1, $zero # return i-1
done
Note that this is not a proper MIPS procedure (not yet) following the register conventions. I plucked this example off my old lecure notes. You can try writing out a proper MIPS procedure as an exercise.
The C code above is not the only way to write the strcpy() function, though. Here's another way:
int strcpy(char *out, char *in) {
char *p=in;
while (*out++=*p++);
return p-in;
}
Try to figure out how it works and write the corresponding MIPS code for it. This example illustrates why C is so hard to learn!
Written by : Gek Siong Low (cs61c-tb), Spring 1999