Understanding C Language-2: Instruction Execution 中文版

Introduction

Last post describes how to model data by variables in C programming. When variables are ready, it’s time to design handy tools to use them.

Imperative Programming

Tell machines “how to” step by step is the core idea of imperative programming. People like to imagine this as a recipe(in fact, the famous tool GNU make just names build steps of one specific target recipe):

1
2
3
4
Peel the skin of tomatoes off and slice them
Beat the eggs together with the salt, and set aside.
Heat half of the oil in a wok over medium-high heat, pour in the egg.
Stir in the tomatoes with 1 teaspoon of sugar. Continue cooking uncovered 2 minutes.

They are similar to the following statements in main function of C:

1
2
3
4
5
6
int main() {
int tomato = 1;
int egg = 2;
int dish = a + b;
return dish;
}

Ok, let’s go on to design elements to express these operations.

Operand & Expression

Here is your first quest: how can you give computers the order to do the computation “1+2”?
Maybe you will answer immediately: “write down 1+2 directly!”.

Bingo! This is almost the simplest expression, just abstract and model from it.
It’s easy to tell “1” and “2” are the same type of element, “+” is the other type. We can name them as operand and operator respectively. “1+2” combines them and called expression.

Nature of Operators

We can divide the operators into categories, e.g. arithmetic, relational calculus, assignment. Operators usually map to corresponding assembly instructions since they describe specific machine operations. For example:

Assembly Instruction C Operator
add +(add)
sub - (Sub)
and &&(Logical OR)
mov =(Assigment)
lea &(Fetch address)

To summarize, each operator models a specific operation.

Nature of Expression

Expression model evaluation. It combines operands(maybe by omitted) to be evaluated in a specific order.

Here are some points:

  • The simplest case
    A literal or variable is the simplest expression and the value is itself(e.g. 12 or variable a).
  • Nesting
    An operand can be expression itself, which can complicate expression.
  • Evaluation Order
    How to evaluate one expression depend on priority and associativity(take effect when priorities are equal) of the operator. Use parenthesizes to change the default evaluation order.

For one thing:
Expression 1+2*3 describes the computation of ‘multiply 2 by 3, then add 1 to it’. To do the addition firstly, you have to introduce parenthesizes: (1+2)*3. To simplify this expression with no parenthesizes, rewrite it in RPN(Reverse Polish notation, also known as postfix notation) form.

Infix Notation Postfix Notation
1+2*3 1 2 3 * +
(1+2)*3 1 2 + 3 *

Interpreters often use RPN inside for it is convenient to evaluate when scanned from left to right with data structure stack. On the other side, infix notation is widely used in writing programs since it is adapted for human read/write.

Use binary-tree to transform infix notation expression into postfix notation(Unary operator or multi-purpose operator can both be converted to Binocular operator).

Statement

The recipe mentioned above consists of multiple steps with one specific execution order. Programs are just the same. We introduce statements to model this kind of control flow.

C language defines ‘;’ as the delimiter to recognize single statements.

Control Flow

The four types of common control flow are listed as below:

  • Ordinal
    Wrap multiple statements with ‘{}’ claims the ordered execution sequence naturally. This group of statements is also called a compound statement.
  • Conditional
    Execute conditionally depend on the bool value of an expression.
  • Loop
    Execute repeatedly depend on the bool value of an expression.
  • Direct Jump
    Jump to specific statement unconditional(e.g. goto/continue/break/return).
    Be aware that the target label of goto must be in the referencing environment(details in the next section) like variables.

In assembly language, the foundation of control flow is autoincrementing of register RIP and opcode like jmp:

1
jmp addr // change ip to addr

All control flow described above except ordinal can be converted into assembly instructions contains jmp.

Referencing Environment

One statement can refer to variables that have been declared. So each statement has its own set of visible variables, called referencing environment.

I prefer to call the referencing environment context as it likes natural language:

You and I are friends。

Context is needed to adjust who is ‘You’ in this sentence.

Context is the same concept as the variable scope mentions in previous post: Variable scope is from variable perspective meanwhile context is from statement perspective.

So how to determine context binding to a specific statement in C? The answer is lex scope(or static scope).

In c, each compound statement wrapped within ‘{}’ makes a scope, which means functions/loops/condition statements all have their scopes.
Context can be nested. The variable search follows the path from inner to outer. The inner variable will cover the outer variable with the same name.

For example:

1
2
3
4
5
6
7
8
9
int main() {
int a = 1;
int b = 2;
if (a == 1) {
int a = 2;
a == b;
}
}

corresponding assembly code:

1
2
3
4
5
6
7
8
9
push %rbp
mov %rsp,%rbp
movl $0x1,-0x4(%rbp) ; set a = 1
movl $0x2,-0x8(%rbp) ; set b = 2
cmpl $0x1,-0x4(%rbp) ; a == 1?
jne 40050c <main+0x1f>
movl $0x2,-0xc(%rbp) ; inner a = 2
pop %rbp
retq

The key point here is context can be determined during the compile stage through a static scope, which helps to find out potential mistaken references.
Relatively, languages employ dynamic scope to determine context by runtime call chain instead of static code.

Introduction of Function

You have all the basic tools to direct computers at this time. You can order computers to do any computation by writing statements to operate on variables.

The fly in the ointment is that some pieces of code exist repeatedly. These codes usually do the same thing with different data. It annoys you to enter the same statements again and again. We, programmers, are the laziest people in the world. We should fix it.

C introduce functions to resolve this problem(named routines formally, the function is one realization of it): Define invariable code fragment as function body and define variable data as parameters. Invoke functions with different arguments leads to the corresponding result.

Calling Convention

Since calling a function within a function(e.g. A calls B, B calls C) has FILO(First In Last Out) feature, it is easy to organize data about invoked functions as frames(also known as Active Record) and save them in the calling stack.
Platforms publish Calling conventions to define interactive details(e.g. frame layout) between calling and called functions. The convention covers:

  • How to pass arguments to called function& the order of arguments
  • How to pass back the result
  • Which registers should be saved by the called function
  • Which function is on duty to clean the stack after return

According to official document from GNU GCC, GCC follows convention sysv_abi on x86 platform. Fig.1 shows the memory layout in this convention:

Fig.1 Memory Layout of Stack
Fig.1 Memory Layout of Stack

We can find that the calling stack grows downward with elements pushed as follows:

  • The return address of calling function(rip)
  • Stack bottom address of the called function(bsp)
  • Reserved space for local auto variables of called function
  • Reserved space of parameters of called function

Here is one illustration:

1
2
3
4
5
6
7
8
9
10
11
int callee(int a, int b) {
int c = 1;
return c;
}
int main() {
int a = 1;
int b = 2;
return callee(a, b);
}

Compile it on amd64 platform and we get the following assembly code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// callee
push %rbp ; save frame base (8bytes)
mov %rsp,%rbp ; create new frame base
mov %edi,-0x14(%rbp) ; get argument a (4 bytes)
mov %esi,-0x18(%rbp) ; get argument b (4 bytes)
movl $0x1,-0x4(%rbp) ; set local var c = 1 (4 bytess)
mov -0x4(%rbp),%eax ; set return value
pop %rbp
retq
// main
push %rbp ; save old frame base (8 bytes)
mov %rsp,%rbp ; create new frame base
sub $0x10,%rsp ; allocate space for local vars (16 bytes)
movl $0x1,-0x4(%rbp) ; set local var a = 1 (4 bytes)
movl $0x2,-0x8(%rbp) ; set local var b = 2 (4 bytes)
mov -0x8(%rbp),%edx
mov -0x4(%rbp),%eax
mov %edx,%esi ; pass argument b
mov %eax,%edi ; pass argumnet a
callq 4004ed <callee> ; call will push rip (8 bytes) to stack
leaveq ; set rsp = rbp then pop rbp (clean up)
retq

The convention defines:

  1. Arguments are passed by registers from right to left(RTL) according to predefined priorities(Pass by stack is available in some conditions, details in manual)
  2. Pass return value by register eax
  3. Reserved space for local variables is aligned by 16 bytes
  4. It is calling function’s duty to clean up its stack(leaveq in main)

Two additional points:

  1. It creates a calling chain by saving bsp(base pointer) of the last frame in each frame, which is used to search visible variables in dynamic-scope languages
  2. One additional pointer referring to parent function in static code is needed in language support nested functions(Not C) to complete the referencing environment.

Declaration of Function

New ANSI C standard demands function declaration(function prototype) before usage like variables to provide necessary type info about parameters and return value.
Compile the following C code:

1
2
3
4
5
6
7
int func(int a);
int main() {
int d[5];
d = func(1);
return 1;
}

will produce errors:

extern_func_decl.c: In function ‘main’:
extern_func_decl.c:5:7: error: incompatible types when assigning to type ‘int5’ from type ‘int’

Function prototypes make programs more robust.

Memory Layout of Function

Compilers put function bodies in the text segment as they are executable and record function names as one entry in the symbol table.

Conclusion

This post talks about blocks of control flow in C programming: operator, expression, statement, and function. It also shows how to employ stack to support nested function calling.
Here are two additional points:

Stack

Stack saves the calling chain, so we need multiple stacks if we are developing a multi-thread application(one stack for each thread).
Even if no concurrency needed, OS like Linux distinguishes between kernel stack and user stack to provide different execute permission.

Coroutine

A normal function has only one entry. Multi-entry(execution can be suspended and resumed) leads to coroutine. Switch between coroutines occurs in user mode triggered by explicit instructions meanwhile Switch between threads occurs in kernel mode triggered by the scheduler.
Many methods can implement coroutines. The primary principle is to save the calling frame(execution state) in heap and resume in the future.

References

  1. C Grammar
  2. Description about Calling Convention from GNU gcc
  3. List of x86 Calling_Conventions
  4. Michael Matz, Jan Hubička, Andreas Jaeger, Mark Mitchell, Milind Girkar, Hongjiu Lu, David Kreitzer, Vyacheslav Zakharin, eds. (2018-01-28). “System V Application Binary Interface: AMD64 Architecture Processor Supplement (With LP64 and ILP32 Programming Models) Version 1.0”
  5. Robert W. Sebesta, (2016). Concepts of Programming Languages
  6. The GNU C Library Manual

Series

  1. Understanding C Language-1: Memory Object