The Fifth Laboratory

The "C" Lab.


You will submit this lab by electronic mail as usual, the details are found here as usual.

Setup

The start-up script has created the directory smd137/lab5 and placed the MIPS model mips_pipe.xml and the Makefile there. Compile the file by running "make lab5".

General information on lab 5.

You will turn in two parts. The first is a C source code file, which implements something very similar to your Lab One code:
       DT_LABNUMMER     5
       DT_LABDEL        1
This will be processed by the compiler "MIPS SDE lite" with the same Makefile as given to you below which will produce an assembler code file for the MIPS simulator. The compilation must succeed, and the program must execute correctly in "mips_pipe.xml".

The second part is a text file you will create,

       DT_LABNUMMER     5
       DT_LABDEL        2
containing some summary information, and a code analysis.

You will start from the skelleton c-source file "lab5.c" (also placed in the directory smd137/lab5/).

Fill in the size of your byte array from lab1 in the specified place in lab5.c. Also copy the "abc" and "coded" word arrays from your lab1 into lab5.c where it's specified (in the beginning of the file). It should look something like this:
__asm__(".data
        .global plain
# fill in the size of your 'plain' byte array
plain:	.space 100

# your 'abc' word array goes here:

abc:    .word	0x90237dfc	# string 'abc', encoded
        .word	0x7df689a7
	.word	0x56e7af08
	.word	    0

# your 'coded' word array goes here:

coded:	.word	0xc2fb596e	# the real encoded data
	.word	0x2ea59607
		.
		.
		.
	.word	    0

	.text
"
);
Notice that if you don't change or remove the string "abc" from the comment when you copy your abc word array from lab1 the compiler will complain. In the example below the comment have been changed from:
# string "abc", encoded
to
# string 'abc', encoded

Compile by:
        >make lab5

What the Lab is About.

The "C" programming language is especially popular among people who have been exposed to assembly programming, because they understand what is happening at the instruction set level. "C" is a compromise that lets these people access most of the low-level mechanisms of the machine, yet still work at a slightly higher abstraction level than all the way down at the assembler level. "C" has a much lower abstraction level than Java for example, but keeping in mind what kind of people usually use "C", it is not surprising that "C" is used to write operating systems, compilers, hardware diagnostics, and many other applications which operate very close to real, physical hardware.

The idea of this lab is, mainly, the difference between parameters by value vs. reference in "C", and how pointers are generated, passed, and used.

The "c-source file" contains almost everything you need, except for the executable statements inside of "decode", "codgen" and one little patch in "main" (a critical patch: make sure you understand it !!). All global variables, local variables, and formal parameters have been declared and are in place. Here is pretty much all the "C" you need to know:

CONSTANTS:
  'A'                  the 8-bit value for one character
  "ABC"                byte string: FOUR characters
                       (last byte has value zero)
  0xff132              integer constant in hex
  0177                 integer constant in octal
  177                  integer constant in decimal


DECLARATIONS:
  int  a;              "a" is 32-bit signed integer
  char b;              "b" is 8-bit (signed) byte
  int *c;              "c" is a pointer to an integer;
  char *d;             obvious
  int  e[20];          integer array, 20 elements
  char f[20];          byte array, 20 elements

STATEMENTS:

  while ( blaj ) {     while-loop
    do this;
    then do this;
  }

  if ( blaj ) {        if-then-else
     do this;
  } else {
     do this;
  }

  if ( blaj ) {        if-then
     do this;
  }

  a = 1;                assignment

  - a                   negation

  ~ a                   bit inversion

  (a == b)              compare for equality. CAREFUL !!
  (a >= b)              remember:  SIGNED 
  (a <= b)               
  
  (a >> 3)              arithmetic shift right

  a + b
  a - 0x00003fff        obvious enough
  (a & 0x00003fff)      logical and
  (a | 0x00003fff)      logical or
  (a ^ 0x00003fff)      logical xor
  & a                   address of variable "a"

                        (where "a" is a pointer):
  * a                   fetch the item pointed to by "a"
NO there is no "rotate" operator in "C", but you know how to accomplish the same thing, don't you ? The MIPS doesn't have this either: it is a assembly pseudo-operation. So you must go in and study how "rotate" was actually implemented, and do that same thing yourself by hand.

What to Code

Take the "c-source file," and hack until it decodes the big string. The string will be located in the .data segment. Then you can request a Dump Segment of the .data segment from the menu in the Data Memory. This will produce a file named dumpFile_0 located in the same directory as the jar-file.

Analysis of Generated Code

In the file mips_program.objdump, identify that part of the code which corresponds to the subroutine "codgen" and copy that into a separate file (which will become your "Part Two" for this lab). What we want now is for you to explain each and every instruction you see: why did the compiler generate this ? From what you can see, where did the compiler "decide" to place the local variables ? Where are the formal parameters ?

Do NOT assume that we have your source program at hand, when we read your Part Two. Part Two should be completely self-contained. Begin with a copy of the source code for "codgen", and then document the assembler code by copying each line from that source code and placing it near to the instructions which implement it.

We expect a detailed explanation, take each instruction or maybe very small groups (two or three instructions) and explain how the compiler has used every variable, every register, every opcode, why you think it didn't use certain "more obvious" opcodes. The compiler may have moved things around in very strange ways: explain why the compiler decided that it was alright to do that move, or reordering, or optimization. In some cases it had to perform some strange reordering. Why ?

And you will see many places where the compiler could have done a much better job. Yes, you should say "the compiler could have saved x instructions by doing y" everywhere you discover such things.

By the time you have finished doing this analysis, you will have gained tremendous insight into how compilers actually work.

Now it is time to play with the optimization flags. The flag is given to sde-gcc in the Makefile like this:
-O0
The possible choices of optimizations are:
-O0 -O1 -O2 -O3 -O4
Your task is to try the different flags and explain what the compiler does to your code. You should also run the program and see how it affects the number of cycles the program takes. Also check your decoded string to see if something differs between the different runs and in the case the decoding fails, try to find and explain the error. This analysis should be appended to part two.

What Should Turn In:

Part One is your completed "C" program (the source file), which successfully compiles with the makefile given in this lab and which successfully prints out the decoded string to memory.

Part Two is a file which you create yourself, and should contain the following information:

Do NOT erase your lab after you turn it in !

Last modified 2005-12-12 by pln