Make

A make file consists of a set of make rules. Each rule has three parts: a target, a set of zero or more dependencies, and a list of zero or more commands.

target: dependencies
(tab) command1
(tab) command2

Make is invoked by specifying a target on the command line. If no target is given, then the first target in the file is taken as the default. To compete a target, all dependencies are evaluated first. If a dependency is another target in the makefile, then those dependent targets are evaluated. If the dependency is not a target in the makefile, then the file system is checked for the existence of a file with the name of the dependency. If the file has been modified more recently than the file matching the target, then the commands for that target are run.

Consider the files:

main.c:
  #include "bar.h"
  void main() {
    bar();
  }
bar.c:
  #include "bar.h"
  void bar() {
  }
bar.h:
  void bar();

The corresponding naive makefile would be:

main.exe: main.o bar.o
(tab) gcc main.o bar.o -o main.exe

main.o: main.c bar.h
(tab) gcc -c man.c

bar.o: bar.c bar.h
(tab) gcc -c bar.c

clean:
(tab) rm *.o main.exe

Note: the "-o" flag specifies the name of the output file. The "-c" flag tells the compiler to stop after the "compile" stage and before the "link" stage, generating an object file as the output.

Typing "make" on the command line would build this project and produce an executable named "main.exe". Typing "make" again would do nothing since all of the dependencies would evaluate to false since none of the source files had changed. Changing any of the source files and then typing "make" would cause only the required segments of the project to be recompiled. The make utility knows what files need to be rebuilt based on the dependencies that we have given it, so it is important that these dependencies are correct.

See also: GNU make documentation.

C: Declaration vs Definition

In computer science, there is a subtle but important distinction between a declaration and a definition.

A declaration is a statement that something exists and what its characteristics are (name, and type). A definition is saying what that thing is.

A function declaration in C looks like this: void foo();. Note the semicolon. If we were to create a variable like that (int i;) we would declare that the variable exists without assigning it a value. When we declare a method without giving it a body, was are saying that this method exists somewhere, but we are not saying what it is. [Note: the variable in the example would still be "defined" since it was allocated space.] In C, these are referred to as function prototypes. In Java, they are called method signatures. They are functionally and conceptually the same.

To define a function, we must give it a body: void foo() {...}. This is saying what the function is and is a shorthand for the concept of saying: void foo() = {...}.

You can think of all of the symbols in a program as entries in a dictionary. The declarations are listing all of the words, and the definitions are assigning them meanings. Because programs must be unambiguous (so that they can be machine executed), each word that we declare must have exactly one definition. It would be ambiguous to have words with no definition (no meaning) or multiple definitions (multiple meanings) -- the machine would not know what to do.

Declarations can be used by the compiler to verify that function calls and function definitions match the exposed prototypes. C can use the function declarations (separated from their definitions) to achieve seperate compilation.

Separate compilation allows the differing functional units of a program to be compiled independently. If the function "foo" calls the function "bar," the two of them can be compiled separately if they both know the prototype for the "bar" method. Bar does not have to know anything about foo, and foo only has to know the declaration for bar. The linker can link the definition of bar to the call to bar in the method foo.

Separate compilation allows for large projects to be compiled without having to recompile every function every time a change is made. In the previous example, a change to foo would not require bar to be recompiled, and a change to bar would not require foo to be recompiled. A change to the declaration of bar would require both foo and bar to be recompiled though.

See also: Variable Definition vs Declaration

Stages of Compilation

Compilation in C has two major stages. The first stage, "compiling" consists of preprocessing, lexical, syntactic, and semantic analysis, followed by optimization and code generation. All of the compile errors that you are familiar with in Java come from this first stage.

The input to the first stage is your .c and .h source files, and the output is a .o object file. The object file consists of two parts, the machine code equivalent of the source file, and a symbol table which lists all of the symbols (functions, variable, and a few other things) that this object files provides and requires.

The second stage of C compilation is "linking." A linker takes in a set of object files and "links" the symbols in the symbol tables together. If one symbol table requires a "bar" function, the linker connects it to the object file that provides it. The output from the linker is an executable file.

In Java, there is very little static linking -- most is done dynamically at run-time, so this will be a new source of errors for you. Fortunately, the errors generated by the linker are usually very straightforward.

There are two major sources of errors from the linker. The first occurs when a symbol is required by one object file, but not provided by any other. In this case, the linker cannot make a required link, so it will generate a "symbol not defined" error. [The closest equivalent in Java is a "NoClassDefFoundError," a "NoSuchFieldError," and a "NoSuchMethodError" at runtime.] The other kind of error comes when a symbol has been provided by more than one object file. In this case, the linker does not know which symbol to link to, so it will generate a "multiply defined symbol" error.

Linking errors for methods come about because of the distinction between method declaration and method definition in C, which is the subject of the next post.

Branches (While Loop - !0)

Consider the code block:

int x = 0;

while(x <= 10) {
  x++;

}
x += 4;

while(x > 10) {
  x--;
}
x -= 4;  

When we have a loop condition that involves a non-zero argument, we need to re-express that condition in terms of a zero argument. The code block above translates to:

int x = 0;

while(x -10 <= 0) {         // or [ 0 <= 10 - x]
  x++;
}
x += 4;

while(x -10 > 0) {          // or [ 0 > 10 - x]
  x--;
}
x -= 4;  

Converting to assembly gives:

0:   ld $0x0000, r0       # x = 0

# first loop, false conditional at top
2:   ld $0xfffffff6, r1   # r1 = -10
8:   mov r0, r2            
     add r1, r2           # r2 = x - 10
     bgt r2, 0x0012       # if x-10 > 0, x > 10, !(x <= 10) goto +3

     inc r0               # x++
     br 0x0008            # goto -4

12:  add $4, r0           # x += 4

# second loop, true conditional at bottom
14:  ld $0xfffffff6, r1   # r1 = -10
1a:  br 0x0022            # goto +4
1c:  dec r0               # x--;

     mov r0, r2
     add r1, r2           # r2 = x - 10;
22:  bgt r2, 0x001c       # if x-10 > 0, x > 10 goto -3

     add $-4, r0          # x -= 4  

Note: the condition being evaluated in each case is identical, it is just treated differently. In one block, it is used as a condition to exit the loop; in the other, it is used as a condition to continue the loop.

Bonus: Advanced Branching (Switch Statement)

Consider a switch statement:

switch(r0) {
  case 0: ~~~0;
          break;
  case 1: ~~~1;
          break;
  ...
  case 0xf: ~~~f;
            break;
  default:
            ~~~default;
}
~~~done

If / Else Naive Implementation

  0: rr move r1, r0     # r1 = r0
     beq r1, 0x??0      # goto "0" case
     dec r1             # r1 = r0 - 1
     beq r1, 0x??1      # goto "1" case
     ...
     dec r1             # r1 = r0 - f
     beq r1, 0x??f      # goto "f" case
     ~~~default         # execute "default" case
     br 0x???           # exit
??0: ~~~0               # execute "0" case
     br 0x???           # exit
??1: ~~~1               # execute "1" case
     br 0x???           # exit
...
??f: ~~~f               # execute "f" case
???: ~~~done            # outside the switch

Case     # conditions evaluated      # branches taken
  0                 1                      2
  1                 2                      2
 ..
  e                15                      2
  f                16                      1
 <0                17                      1
 >f                17                      1
Sum:              170                     31

Every additional case adds progressively more and more to the number of conditions evaluated. The number of branches taken remains constant for each execution path.

Switch / Jump Table Implementation

   0:  move r1, r0          # r1 = r0
       dec r1               
       bgt r1 0x08          # ensure >=0 (in range)
       br "def"             # if not, goto "default" case
   8:  move r1, r0          # r1 = r0
       ld $0xFFFFFFF1, r2   # r2 = -f
       add r2, r1           # r1 = r0 - f
       bgt r1 "def"         # goto "default" case if > f
       move r1, r0          # r1 = r0 (and r1 is in range)
       ld $0x00001000, r2   # r2 = & jump table
       jmp *(4*r1, r2)      # jump to the right case
"c0":  ~~~0                 # case "0"
       br "done"            # exit
"c1":  ~~~1                 # case "1"
       br "done"            # exit
...
"cf":  ~~~f                 # case "f"
       br "done"            # exit
"def": ~~~~default         # "default" case
"done" ~~~~done            # outside the switch
...
1000:  &"c0"    # jump table, filled with addresses of cases
       &"c1"
       ...
       &"cf"

Case     # conditions evaluated      # branches taken
  0                 3                      3
  1                 3                      3
 ..
  e                 3                      3
  f                 3                      3
 <0                 1                      1
 >f                 2                      1
Sum:               48                     47

More cases do not grow the number of conditions evaluated per path, and the number of branches taken per path remains constant.

Special Note: the number of branches taken in the above example is higher than that of the if/else example due to the branch on the ">0" case. This branch can be eliminated by reversing the test:

   0:  move r1, r0          # r1 = r0
       not r1               # 
       inc r1               # r1 = -r0
       bgt r1 "def"         # goto "default" if <0
   8:  move r1, r0
       ld $0xFFFFFFF1, r2   # r2 = -f
       add r2, r1           # r1 = r0 - f
       bgt r1 "def"         # goto "default" case if > f
       move r1, r0          # r1 = r0 (and r1 is in range)
       ld $0x00001000, r2   # r2 = & jump table
       jmp *(4*r1, r2)      # jump to the right case
...

Case     # conditions evaluated      # branches taken
  0                 3                      2
  1                 3                      2
 ..
  e                 3                      2
  f                 3                      2
 <0                 1                      1
 >f                 2                      1
Sum:               48                     32

For more information, see Implementing Common Control Structures in Assembly Language and/or C to Assembly Translation III.

Branches (While Loop - false)

while(x != 0 ) {
  ~~~i
  ~~~i
  ~~~i
}
~~~o

Address	Machine	Assembly	Notes
	assume r0 = x
0:	9005	beq r0, 0x10	branch to exit
2:	~~~i		true case
	~~~i
	~~~i
8:	80FC	br 0x00	loop
10:	~~~o		exited loop

Note 1: 2 branches total, 1 branch taken on critical path.

Note 2: conditional at top.

Branches (While Loop - true)

while( x == 0 ) {
 ~~i
 ~~i
 ~~i
}
~~ o

Naive / Literal

Address	Machine	Assembly	Notes
	assume r0 = x
0:	9002	beq r0, 0x04	conditional
2:	8005	br 0x0c	exit
4:	~~~i		true case
	~~~i
	~~~i
a:	80FB	br 0x00	loop
c:	~~~o		exited loop

Note: 3 branches total, 2 branches in critical path.

Preferred

Address	Machine	Assembly	Notes
	assume r0 = x
0:	8004	br 0x08	prime (need to check condition)
2:	~~~i		true case
	~~~i
	~~~i
8:	90FD	beq r0, 0x02	loop conditional
	~~~o		exited loop

Note 1: 2 branches total, 1 branch in critical path.

Note 2: conditional at bottom.

Branches (If Statements)

If without Else

if( x == 0 ) {
  x = 1;
}
x++;

Address	Machine	Assembly	Notes
	assume r0 = x
0:	9002	beq r0, 0x0004	if true, skip false
2:	8004	br 0x000a	false case, skip true
4:	0000 0000 0001	ld $0x0001, r0	true case
a:	6300	inc r0	after if block

Note: the false case comes first since we branch somewhere else when true.

If with Else

if( x == 0 ) {
  x = 1;
} else {
  x = 2;
}
x++;

Address	Machine	Assembly	Notes
	assume r0 = x
0:	9005	beq r0, 0x000a	if true, skip false
2:	0000 0000 0002	ld $0x0002, r0	false case
8:	8004	br 0x0010	skip true
a:	0000 0000 0001	ld $0x0001, r0	true case
10:	6300	inc r0	after if block

Structures in Machine Memory

typedef struct {
  int a;
  int b;
} T;

T foo;
T bar[2];
T* h = (T*) malloc( 3* sizeof(T) );  // reserve heap space

address	value	offset	c name	region
0:	~~~~~			program
	...
1000:	???? ????	00	foo.a	global variables
	???? ????	01	foo.b
1008:	???? ????	00	bar[0].a
	???? ????	01	bar[0].b
	???? ????	02	bar[1].a
	???? ????	03	bar[1].b
1018:	0000 2000	00	h
	...
2000:	???? ????	00	h[0].a	heap
	???? ????	01	h[0].b
	???? ????	02	h[1].a
	???? ????	03	h[1].b
	???? ????	04	h[2].a
	???? ????	05	h[2].b

Gold Machine's Branching Instructions

opcode	format	semantics	example	example assembly (RISC)
branch	8-oo	pc = pc-2 + 2*o	1000: 8006	br 0x100c
branch if equal	9roo	if r[r] == 0, pc = pc-2 + 2*o	1000: 9206	beq r2, 0x100c
branch if greater	aroo	if r[r] > 0, pc = pc-2 + 2*o	1000: a206	bgt r2, 0x100c
jump	b--- aaaaaaaa	pc = a	1000: b000 00008000	jmp 0x8000
get pc	6f-d	r[d] = pc-2	6f01	gpc r1
jump indirect	croo	pc = r[r] + 2*o	c103	jmp 0x3(r1)
jump indirect, b+o	droo	pc = m[ r[r] + 4*o ]	d103	jmp *0x3(r1)
jump indirect, index	eir-	pc = m r[r] + 4*r[i] ]	e120	jmp *(4*r1,r2)

Note 1: All "branch" machine language instructions are relative to the current PC (though their assembly versions are absolute). All "jump" instructions are absolute.

Note 2: the semantics for each branch instruction include a -2. This is to undo the +2 increment to PC during the fetch stage.

Corollary to Note 2: a branch of "0" should make the branch instruction branch to itself. So if you ever branch by 0, you will enter an infinite loop. This simplifies branching forwards and backwards.