CSE 351, section 2: Translating C to Machine Instructions

1. Getting Familiar with a Simple C Function

I started section with a quick review of what the class has covered over the last week and a half, and a discussion of some of the differences between Java and C. One of the important differences is that in C, functions (methods) have to be declared before they are used.

To make sure that all functions are declared before any code runs, C programmers use a header file with a ".h" suffix to declare all the functions that they will then fully define in their code file (with a ".c" suffix). [We did not discuss how the header file gets included with the rest of the code using the #include directive.] The function declaration in the header file resembles an abstract method declaration in Java: the function header followed by a semicolon instead of curly braces with the function body.

I wrote out a simple value-swapping C function called exchange, that takes an int pointer and an integer:

	int exchange (int* px, int y)
	{
	    int z = *px;
	    *px = y;
	    return z; 
	}

The function declaration (in the header file) would look like this:

	int exchange (int* px, int y);

And to illustrate how we would call the exchange function and what it would do, I wrote a snippet of code that might call exchange from main:

	int a = 4;
	int b = 3;
	b = exchange(&a, b);
	printf("a == %d, b == %d", a, b); 

We walked through the code, noting that &a provides a pointer to the int (3) stored in a (i.e., the address of a), which is passed to exchange as px; and *px yields the value stored at the address of a (dereferencing the pointer px), which is 3. We can also assign a value to *px, which is what the second line does—it sets a (the value at the address pointed to by px) to 4.

2. What Can the CPU Do?

Registers and Memory

I asked the class to think about the hardware elements that comprise the computer that is going to run our C program. In particular, we have two main components: the CPU and main memory. We are going to imagine an extremely simplified CPU that contains a few key elements:

• a register file, with eight 32-bit (4-byte, 1-word) registers;
• some module for doing arithmetic and logical operations; and
• a program counter (PC) to keep track of where the computer "is" in the code.

A Simple Instruction Set Architecture

The class helped to suggest simple register-focused actions that the CPU could do (starting with the simplest of all—nothing or "no operation", and the equally straightforward "halt" instruction). The result was this list:

• put a value into a register;
• copy one register to another register;
• do an arithmetic or logical operation on two registers (add, subtract, and, xor)
• copy a word from main memory into a register; or
• copy a word from a register into main memory.

Addressing Memory: Base and Displacement

We took a look at main memory, and realized that we can view it as a big array. That means we can use the tricks we have learned about array indexing in C—and pointer arithmetic—when we want to address memory. In particular, we've seen that the expression array[3] is equivalent to *(array + 3); but that also means it is equivalent to 3[array]! That looks weird at first, but it turns out that we access memory using very similar notation, which we call "base and displacement". The base is the "array" address, a 32-bit word (a pointer) in one of the registers. The displacement is another 32-bit word (often a smaller number) that is written out, like the "3".

One Machine Instruction

I demonstrated how the pseudo-assembly-language instruction "copy a word from a register into main memory" is represented for the CPU. The necessary elements are:

1. the instruction itself;
2. the source register;
3. the base address register; and
4. the displacement value.

In the y86 instruction set (described in Chapter 4 of the Bryant & O'Hallaron textbook, a simplified version of the x86 instruction set), the form of this instruction is:

	mrmovl rA, D(rB)

	Ox 40 26 0C 00 00 00  

There is a machine representation for each of the basic instructions that the CPU can accomplish: a binary string that the processor can decode.

3. Connecting the Dots: Turning Software into Hardware-Executable Instructions

We then wrote the C exchange function in terms of our pseudo-machine-language instructions. In order to get the parameter values, I declared that px was in memory 8 bytes above the address in register 5, and y was 12 bytes above the address in register 5. I also explained that register 0 has a special use: at the end of a function, register 0 should contain its return value. We ended up with the following pseudo-assembly code:

	mem-->reg 8(r5), r1    # put px into register 1
	mem-->reg 12(r5), r2   # put y into register 2
	mem-->reg 0(r1), r0    # put *px into register 0 (ready to be the return value)
	reg-->mem r2, 0(r1)    # *px = y

Summing an array

To finish off the section, I asked the class to collectively provide the pseudo-assembly code to sum the elements of a three-integer array in memory at location 0x1000, putting the sum into register 0 and then halting.

Here is the code that the class came up with:

	value-->reg 0x1000, r1   # put the array's base address into register 1
	mem-->reg   0(r1), r0    # put the first int into register 0
	mem-->reg   4(r1), r2    # put the second int into register 2
	add         r2, r0       # add the first and second ints in register 0
	mem-->reg   8(r1), r2    # put the third int into register 2
	add         r2, r0       # add the third int to the sum in register 0
	halt

So in the course of fifty minutes we gained some more familiarity with C, got introduced to the idea of an instruction set that provides a connection between software and hardware, and learned how it is possible to translate from high-level programs down to machine-readable bits!