D1 From C Code to Binary Program

You have already learned and used C in the E stage, and you have also run C programs that you compiled yourself on a processor. After becoming familiar with C development in Linux, you already know that a program can run only after C code is turned into a binary executable file. So how does a compiler turn C code into an executable file? What is the relationship between an executable file and the instructions executed on a processor? To answer these questions, we will use some Linux tools to further understand the steps in this process.

Preprocessing

Preprocessing is a step before actual compilation, and its essence is text processing. Preprocessing mainly includes the following tasks:

• Including header files
• Macro substitution
• Removing comments
• Joining strings split by line-continuation characters (\ at the end of a line)
• Handling conditional compilation #ifdef/#else/#endif
• Handling the stringification operator #
• Handling the token-pasting operator ##

For example, consider the following C code:

// a.c
#include <stdio.h>
#define MSG "Hello \
World!\n"
#define _str(x) #x
#define _concat(a, b) a##b
int main() {
  printf(MSG /* "hi!\n" */);
#ifdef __riscv
  printf("Hello RISC-V!\n");
#endif
  _concat(pr, intf)(_str(RISC-V));
  return 0;
}

You can preprocess the C code above with:

gcc -E a.c

Observe the Preprocessing Result

Try running the gcc command above, then compare the preprocessing result with the source file.

One question worth discussing is: how does gcc find header files? To answer this question, we can read the tool's logs and the relevant manuals.

How to Find Header Files

1. Try running gcc -E a.c --verbose > /dev/null, and look for header-file-related content in the output.
2. Search for and read the description of the -I option in man gcc.

After understanding this, try creating some stdio.h files, then use the -I option to make gcc include the stdio.h you created instead of the one in the standard library. Use the -E option to check whether the preprocessing result matches your expectation.

Observe the Preprocessing Result (2)

Try preprocessing with gcc for the RISC-V architecture:

riscv64-linux-gnu-gcc -E a.c

Check the preprocessing result at this point. What new changes do you notice?

The macro __riscv in the C code above is special: it is predefined by riscv64-linux-gnu-gcc. Therefore, even though it is not directly defined in the C code, riscv64-linux-gnu-gcc still treats it as defined. You can view all predefined macros with the following command:

echo | gcc -dM -E - | sort

This command makes gcc preprocess an empty file, then print all macros defined during this process and sort them.

Compare the Predefined Macros of gcc and riscv64-linux-gnu-gcc

Try comparing the predefined macros of gcc and riscv64-linux-gnu-gcc to understand their differences during preprocessing. You only need a rough understanding of these differences; there is no need to dig deeply into the specific meaning of every macro.

Hint:

• Using diff or related commands can help you quickly find differences between two files.
• If you want to understand the meaning of some macros, refer to the gcc manual.

Compilation

In a broad sense, compilation is the process of converting one language into another. For a C compiler, compilation is the process of converting C into a target language. This target language is related to the ISA and usually refers to the assembly language of the target ISA. For example, on a computer with an x86 architecture, gcc converts C into x86 assembly; while riscv64-linux-gnu-gcc converts C into riscv64 assembly.

This process involves many details, and we will not dig into how every step is implemented here. Instead, we will use suitable tools to understand what each step does and build a basic understanding of the compilation process. For this, you need to install clang, which is functionally equivalent to gcc and is also a C compiler.

apt-get install clang

We will use the following program to observe the steps in the compilation process:

// a.c
#include <stdio.h>
int main() { // compute 10 + 20
  int x = 10, y = 20;
  int z = x + y;
  printf("z = %d\n", z);
  return 0;
}

Understand the Compilation Process

Try reading man clang, especially the introduction to compilation stages, to gain a general understanding of the compilation process.

Lexical Analysis

Lexical analysis recognizes and records every token in the source file, including identifiers, keywords, constants, strings, operators, braces, semicolons, and so on. If an illegal token such as @ is encountered, an error is reported. You can view the lexical analysis result with:

clang -fsyntax-only -Xclang -dump-tokens a.c

You can see that the lexical analysis result also records the position of every token in the format filename:line number:column number.

In fact, a C source file is essentially a text file, so it can also be viewed as a string, and the lexical analysis tool can be viewed as a string-matching program.

Lexical Analysis and Syntax Highlighting

You have probably used syntax highlighting in an editor. In fact, this feature is not hard to implement: according to the definitions in the C standard, you can write a simple lexical analysis tool to recognize some keywords in C code and output them in different colors. If you want to output to a terminal, you can use the color feature of ANSI escape codes.

Syntax Analysis

Syntax analysis organizes the recognized tokens into a tree structure according to the syntax of C, thereby clarifying the hierarchical structure of the source program, from files and functions to statements, expressions, variables, and so on. If a syntax error is encountered, such as a missing semicolon, an error is reported. The result of syntax analysis is usually presented as an Abstract Syntax Tree (AST). You can view the syntax analysis result with:

clang -fsyntax-only -Xclang -ast-dump a.c

Semantic Analysis

Semantic analysis determines the type of each expression in the AST according to the semantics of C. During this process, compatible types are converted according to the C standard, such as arithmetic type promotion. Cases that do not conform to the semantics are reported as errors. Some cases that are syntactically correct but semantically incorrect include undefined references, mismatched operand types for operators, such as struct mytype a; int b = a + 1;, and mismatches in the type or number of function-call arguments.

For clang, expression types are already included when the AST is output. In fact, most compilers do not strictly separate syntax analysis and semantic analysis.

An important application of semantic analysis is static program analysis, which analyzes source code without running the program. Its essence is analyzing semantic information in the AST. Analysis perspectives include code style and conventions, potential software defects, security vulnerabilities, performance issues, and so on. For example, consider the following program:

// a.c
#include <stdlib.h>
int main() {
  int *p = malloc(sizeof(*p) * 10);
  free(p);
  *p = 0;
  return 0;
}

This program conforms to C syntax, and each statement viewed individually also conforms to C semantics. Compiling it directly with gcc a.c reports no error, and the compiled program may even run successfully. However, if the compilation option -Wall is added, gcc performs more code checks and emits a warning that the code has a use-after-free issue, meaning memory is still accessed after being freed. Tools that report potential problems in code through static program analysis are called lint tools.

Similarly, you can invoke clang's lint tool to analyze the program above:

clang a.c --analyze -Xanalyzer -analyzer-output=text

Take Lint Tools Seriously

Some beginners feel that asking the compiler to report more warnings creates extra programming work. In fact, using lint tools costs developers almost nothing, yet helps them discover many potential problems. Once these problems enter the runtime phase, developers pay a much higher price to debug them. Especially in large projects, problems caused by code like the example above can be hard to detect, and the software may suddenly crash after running for a long time, making debugging very difficult. Therefore, large projects usually make full use of lint tools to improve project quality as much as possible.

Intermediate Code Generation

Intermediate code is an ISA defined by the compiler for compilation scenarios. It is also called Intermediate Representation (IR) or Intermediate Language. You can view the intermediate code generated by clang with:

clang -S -emit-llvm a.c
cat a.ll

Recall the state machine model: the main task of compilation is to translate the state machine of a C program into the state machine of an ISA, that is, to translate C variables into registers or memory, and C statements into instruction sequences. Since intermediate code can also be viewed as an ISA, we can understand intermediate code generation from the state-machine perspective: translate C variables into intermediate-code variables, such as %1, %2, %3; translate C statements into intermediate-code instructions, such as alloca, store, load, add, call, and ret. Of course, the translation process needs to rely on the semantics analyzed from the AST, so that the behavior of the translated intermediate code is equivalent to that of the input C program.

Why not translate directly to the target language, namely the processor-related ISA? On one hand, there are many processor-related ISAs. If we translated directly to each processor-related ISA and also needed to optimize programs, every optimization technique would have to be implemented separately for different ISAs, increasing compiler maintenance cost. If we first translate to intermediate code and then to the processor-related ISA, optimization techniques only need to be implemented on the intermediate code.

On the other hand, intermediate code can serve as a bridge between many source languages, such as C, Fortran, and Haskell, and many target languages, such as x86, ARM, and RISC-V. Suppose there are source languages and target languages. Direct translation to target languages would require implementing translation modules. If intermediate code is introduced and the compiler flow is divided into a frontend and backend with intermediate code as the boundary, only translation modules are needed: the frontend modules translate the source languages into intermediate code, and the backend modules translate intermediate code into the target languages.

             frontend                              backend
           +----------+                        +------------+
      C -> |  Clang   | -+                 +-> |  llvm-x86  | -> x86
           +----------+  |                 |   +------------+
           +----------+  +-> +----------+ -+   +------------+
Fortran -> | llvm-gcc | ---> | llvm-opt | ---> |  llvm-arm  | -> ARM
           +----------+  +-> +----------+ -+   +------------+
           +----------+  |                 |   +------------+
Haskell -> |    GHC   | -+                 +-> | llvm-riscv | -> RISC-V
           +----------+  LLVM IR      LLVM IR  +------------+

Different compilers may use different intermediate code. For example, the intermediate code used by clang is called LLVM IR, while the intermediate code used by gcc is called GIMPLE. However, we do not need to understand the specific details of intermediate code. A rough understanding of intermediate code generation from the perspective of the state machine model is enough.

Compilation Optimization

Compilation optimization is an important step in modern software construction. With compilation optimization, developers can focus on program business logic and do not need to think too much about program performance during development; compilers usually provide a decent lower bound for performance. Real-world projects commonly use compilation optimization techniques, and in the future, you will also run many optimized programs on processors you design yourself. Therefore, understanding some common optimization techniques and why compilers generate certain instruction sequences will help with future debugging and architecture optimization work.

Definition of Compilation Optimization Correctness

We can understand compilation optimization from the perspective of program behavior: if two programs are "consistent" in some sense, the "simple" one can replace the "complex" one. The behavior of executing statements one by one according to the C standard is called "strict execution". Using "strict execution" as the baseline, the C standard rigorously defines the "consistency" above: the optimized program should satisfy consistency in "program observable behavior" (C99 standard, Section 5.1.2.3, item 6), which specifically includes:

1. Accesses to variables qualified by volatile must be executed strictly.
2. At program termination, data written to files must be consistent with strict execution.
3. Input and output of interactive devices (stdio.h) must be consistent with strict execution.

"Observable behavior" describes the effect of a C program on the outside world from an external perspective. For example, the second point requires external operations without real-time requirements to "look consistent" at the end, while the third point requires external operations with real-time requirements to "look consistent" during execution. The first point constrains the internal behavior of a C program, and is actually related to "memory-mapped I/O" mentioned in the F stage. We will not elaborate on it here; we will continue discussing related content in the D stage.

Therefore, as long as the optimized program still satisfies consistency of observable behavior, the optimization is "correct". Under this condition, if the optimized program has fewer variables or fewer statements, we can expect better performance.

Examples of Compilation Optimization Techniques

Below are some common compilation optimization techniques. Note that optimization techniques are not directly applied to C code in the compilation flow, but for ease of understanding, we use C code to present the semantics before and after optimization.

• Constant propagation - If the value of a variable is a constant, that value can be substituted at its use sites. If substitution forms a constant expression, the value of that expression can be computed directly. In the following example, the value of a is a constant, so a + 2 is also a constant, making b a constant as well. Furthermore, b * 3 is also a constant. The compiler can compute these constant expressions directly and replace them with the computed results, so it does not need to generate corresponding instructions, such as addition and multiplication instructions, to compute these expressions at runtime.

//          Before             |            After
  int a = 1;                   |    int a = 1;
  int b = a + 2;               |    int b = 3;
  printf("%d\n", b * 3);       |    printf("%d\n", 9);

• Dead code elimination - Unreachable code or variables that are no longer used can be removed. In the following example, the DEBUG macro is defined as 0, so the code inside the if block will never execute and can be removed. After removing the code in the if block, variable a is unused and can be further removed.

//          Before             |            After
  #define DEBUG 0              |    #define DEBUG 0
  int fun(int x) {             |    int fun(int x) {
    int a = x + 3;             |      return x / 2;
    if (DEBUG) {               |    }
      printf("a = %d\n", a);   |
    }                          |
    return x / 2;              |
  }                            |

• Redundant operation elimination - Assignments that are overwritten before being read can be removed. In the following example, the assignment a = 3 will be overwritten by a = f(), so the former can be removed. Similarly, the assignments a = f() and a = 7 can also be removed.

//          Before             |            After
  int a;                       |    int a;
  a = 3;                       |    f();
  a = f();                     |    a = 10;
  a = 7;                       |
  a = 10;                      |

Can It Be Further Optimized?

The optimized result above keeps the function call f(). Can f() be removed further? Why?

• Code strength reduction - Replace complex operations with simpler ones. In the following example, i * 4 and i << 2 have the same semantics when their behavior is defined. But on most computers, multiplication instructions are more expensive than shift instructions. Replacing the former with the latter can improve program performance.

//          Before             |            After
  int x = a[i * 4];            |    int x = a[i << 2];

• Common subexpression elimination - For subexpressions computed multiple times, an intermediate variable can store the result and later code can directly reference it without repeated computation. In the following example, a * b appears twice. Introducing temp to store the result of a * b can reduce one multiplication and improve performance.

//          Before             |            After
  int x = a * b - 1;           |    int temp = a * b;
  int y = a * b * 2;           |    int x = temp - 1;
                               |    int y = temp * 2;

• Loop-invariant code motion - Code whose result is the same in every loop iteration can be moved before the loop and computed once. In the following example, the expression a + 2 has the same result in every iteration, so it can be moved before the loop and computed once, avoiding repeated computation in every iteration.

//          Before             |            After
  int a = f1();                |    int x = f1() + 2;
  for (i = 0; i < 10; i ++) {  |    for (i = 0; i < 10; i ++) {
    int x = a + 2;             |      int y = f2(x);
    int y = f2(x);             |      sum += y + i;
    sum += y + i;              |    }
  }                            |

Can It Be Further Optimized? (2)

In the optimized result above, f2(x) is still inside the loop. Can f2(x) be moved before the loop and computed there? Why?

• Function inlining - For smaller functions, expand them at the call site to save the overhead of function calls. In the following example, f1(x, 3) inside f2() can be directly expanded to compute x + 3, avoiding the function call and return process and improving performance.

//          Before             |            After
  int f1(int x, int y) {       |    int f1(int x, int y) {
    return x + y;              |      return x + y;
  }                            |    }
  int f2(int x) {              |    int f2(int x) {
    return f1(x, 3);           |      return x + 3;
  }                            |    }

Can It Be Further Optimized? (3)

In the example above, suppose f1(x, 3) is the only call to f1() in this source file. Can dead code elimination be applied to remove f1() from the optimized result? Why?

Besides the techniques introduced above, there are many other compilation optimization techniques, such as induction variable analysis, loop unrolling, software pipelining, automatic parallelization, alias and pointer analysis, and so on. We will not expand on them here. Interested students can consult relevant materials.

Enabling Compilation Optimization

You can pass the -O1 option to clang to enable more compilation optimization work:

clang -S -emit-llvm -O1 a.c
cat a.ll

Compare Compilation Optimization Results

Try comparing the intermediate code generated before and after adding -O1. What differences do you notice after adding -O1?

Compare Compilation Optimization Results (2)

Try adding the volatile keyword before int x = 10, y = 20;, then regenerate the -O1 intermediate code. Compared with the previously generated intermediate code, what differences do you notice now?

Compilers usually provide different optimization levels, allowing developers to choose among program performance, code size, compilation time, and other metrics. For example, in gcc, optimization levels for program performance are: -Ofast > -O3 > -O2 > -O1 > -Og > -O0 (default). The higher the optimization level, the higher the performance of the generated program, but the longer the compilation time. Most software projects compiled with gcc or clang usually use -O2, which allows software to run with good performance. For -O3, gcc also tries to obtain higher performance by generating more code. -Ofast is more aggressive: it may even use optimization strategies that violate language standards in exchange for higher performance. -Og uses only debugging-friendly optimization strategies. Compared with -O0, it can improve program performance while preserving the original structure of the program, such as loops and function calls, so that the generated instruction sequence corresponds well to the C code and is convenient for developers to debug.

Besides program performance, gcc also provides optimization levels aimed at code size: -Oz > -Os > -O1 > -O0 (default). For clang, the optimization options above also apply.

An optimization level usually includes many optimization techniques. For gcc, you can use -Q --help=optimizers to view the optimization techniques enabled by a corresponding optimization level. For example:

gcc -Q --help=optimizers -O1

This shows which optimization techniques are enabled by -O1. For clang, you can use -ftime-report to view the substeps, or passes, in the compilation process:

clang -S -emit-llvm -O1 a.c -ftime-report

Of course, we do not require you to understand the specific details of every optimization technique. If you are interested, you can consult the relevant manuals.

Target Code Generation

Target code generation translates optimized intermediate code into target code, namely the processor-related ISA. Similarly, we can understand target code generation from the state-machine perspective: translate intermediate-code variables into processor ISA variables, that is, translate %1, %2, %3, and so on into registers or memory addresses; translate intermediate-code instructions into processor ISA instructions, that is, translate instructions such as alloca, store, load, add, call, and ret into processor ISA instructions. You can view the target code generated by clang with:

clang -S a.c
cat a.s

The clang command above generates assembly code for the same ISA as the local environment by default, such as x86. You can also pass the compilation option --target=xxx to clang to generate corresponding assembly code. For example, --target=riscv64-linux-gnu makes clang generate riscv64 assembly:

clang -S a.c --target=riscv64-linux-gnu

This compilation process of generating assembly code for an ISA different from the local environment is called cross-compilation.

Using riscv64 as an Example

Because the system lacks a riscv32 runtime environment, it cannot generate riscv32 code using the system's default configuration, and subsequent steps also cannot generate a riscv32 executable.

For convenience, we use riscv64 here to demonstrate the RISC-V compilation flow. Compared with riscv32, riscv64 only adds several instructions. However, to understand the general correspondence between C code and assembly code, you do not need to deeply understand the specific semantics of every instruction at this point.

Understand the Relationship between C Code and riscv Instruction Sequences

Read the riscv64 assembly code obtained by cross-compiling with clang, and try to point out which segment of assembly code is compiled from which segment of C code.

Understand the Relationship between C Code and riscv Instruction Sequences (2)

Add -O1 and recompile to obtain riscv64 assembly code. What differences do you notice in the generated assembly code? How does it correspond to the C code?

As the last step of compilation, target code generation can also be performed with gcc:

gcc -S a.c  # compile to local ISA
riscv64-linux-gnu-gcc -S a.c  # cross-compile to riscv64

During target code generation, the compiler also performs optimizations related to the target ISA. For example, when translating intermediate-code variables into ISA registers or memory, the compiler tries to put frequently used variables in registers and less frequently used variables in memory. In modern computers, processors access registers much more efficiently than memory, so putting commonly used variables in registers can improve overall program performance. For instruction translation, the compiler also tries to generate instruction sequences with fewer instructions, which can also improve performance. These strategies have certain theoretical support; we will not expand on them here. Interested students can consider consulting materials on compiler principles.

Generation and Execution of Binary Files

Assembly

The result of compilation is assembly code. We already know that assembly language is the symbolic representation of instructions, so assembly code is essentially readable text. But processor circuits cannot understand text, so assembly code still needs to be converted into the binary encoding of instructions. This is the job of the assembly step, and the tool that performs this job is called an assembler.

The assembler works in a straightforward way: in general, it consults the ISA manual and translates text instructions in the assembly code one by one into the corresponding binary encodings, producing an object file. You can make clang generate an assembled object file with:

clang -c a.c
ls a.o

However, the contents of an object file are no longer text, so opening it with a text editor produces unreadable content. To view the contents of an object file, we need binary-file parsing tools to parse the binary contents into readable text. For example, we can use objdump from the binutils (Binary Utilities) package to parse the object file:

objdump -d a.o

The process of parsing assembly code back from an object file is called disassembly. The command above produces x86 disassembly, which is similar to the assembly file generated by the compiler. In fact, when you manually decoded binary sISA instructions in the F stage, you were doing something similar to disassembly!

To obtain a riscv64 object file, we need cross-compilation:

clang -c a.c --target=riscv64-linux-gnu
riscv64-linux-gnu-objdump -d a.o

Similarly, we can use gcc to generate object files:

gcc -c a.c
riscv64-linux-gnu-gcc -c a.c

Alternatively, use the LLVM toolchain for disassembly. It can automatically recognize the ISA architecture corresponding to the object file, which is more convenient:

llvm-objdump -d a.o  # supports both x86 and RISC-V object files

View the Disassembly Result of a riscv64 Object File

Based on the commands above, view the disassembly result of a riscv64 object file and compare it with the assembly file generated by the compiler.

Linking

Linking merges multiple object files into the final executable file. You can make clang generate a linked executable with:

clang a.c
ls a.out

Executable files can also be disassembled with objdump.

However, you will find that compared with the object file before linking (a.o), the linked executable contains much more content. To further understand where this content comes from, we can view the log of the clang command:

clang a.c --verbose

At the end of the log, you can see the command related to linking. This command also contains several object files named like crt*.o. Here, crt is short for C runtime, meaning the runtime environment of C programs. In other words, the linking process merges the object file obtained after compiling and assembling a.c with existing object files related to the C runtime environment, finally generating an executable file. It is predictable that executable files include these runtime-environment-related object files in order to provide necessary support for executing the executable.

Similarly, we can use gcc to generate an executable:

gcc a.c

We can also generate a riscv64 executable through cross-compilation:

clang a.c --target=riscv64-linux-gnu
riscv64-linux-gnu-gcc a.c

View the Disassembly Result of a riscv64 Executable File

Try generating a riscv64 executable, view its disassembly result, and compare it with the object file before linking.

The linking process involves many details. You do not need to dig into them now; we will introduce them in the C stage.

Execution

For x86, after compiling an executable, run it with:

./a.out

You are already familiar with the processor's instruction execution process: fetch, decode, execute, and update PC. As long as the program's instruction sequence is placed in memory and PC points to the first instruction, the processor will automatically execute the program.

Compare Performance before and after Compilation Optimization

We introduced various compilation optimization options earlier. Now you can experience the power of these options. Using the series summation program as an example, you can measure program runtime under different compilation optimization levels and understand the effect of different optimization levels on program performance.

To make performance differences easier to measure, you need to adjust the final term of the series to increase its execution time. If the final term is large, you can also change the type of the sum variable to long long. You can use the time command to measure the execution time of a command. For example, time ls reports the execution time of ls.

After adjusting the final term of the series, compile and measure runtime under -O0, -O1, and -O2.

If you are interested, you can also use disassembly to view the corresponding assembly code, and try to understand from the assembly code: why was the corresponding performance improvement obtained? What compilation optimization techniques might the compiler have applied? To answer these questions, you may need to RTFM or STFW to learn the functions of some assembly instructions.

However, the compiled executable file is stored in external storage such as a disk or SSD. How is it placed into memory? Recall the processor implemented in Logisim: we directly connected the instruction sequence to the circuit as constants. For a processor developed in RTL, we used the simulation environment to read the instruction sequence into memory connected to the processor. The essence of both methods is that we manually completed the work of "placing the program's instruction sequence in memory". But in the ./a.out command above, we did not manually complete this work.

When we execute ./a.out, who exactly completes the work of "placing the program's instruction sequence in memory" so that the processor can fetch it from memory and execute it? In fact, modern operating systems have a special program called a loader. Its job is to read, or load, other executable files from external storage into memory and jump to the corresponding program entry to execute instructions.

But a processor can only execute instructions conforming to its ISA specification. For example, most students use computers equipped with x86 processors, so they can only execute x86 executables and cannot execute RISC-V executables. If an x86 processor is forcibly made to execute a RISC-V instruction sequence, it may recognize RISC-V instructions as x86 instructions with other behaviors during decoding, or even as illegal instructions, so the processor cannot execute them according to the original RISC-V semantics and the program result will not match expectations. Therefore, during program loading, the loader checks which ISA the program's instruction sequence belongs to. If it is inconsistent with the ISA of the current processor, the loader stops loading and reports an error.

Loading a program is a necessary step before the program runs, so the loader is part of the runtime environment. The crtxxx.o object files mentioned above contain part of the loader's functionality. The runtime environment also contains other functionality. For example, during the execution of ./a.out, the role of the runtime environment is also reflected in the following:

• Before program execution starts, it prepares various initialization tasks. When you learned C before, you may have thought that a program starts from main(). But if that were true, how would the program arguments we enter on the command line be passed to argc and argv of main()? In fact, this work is also done by the runtime environment: only after completing a series of preparations such as loading the program and preparing arguments does the runtime environment call main().

Does a Program Really Start from main()?

Try using strace or gdb to verify your idea.

Hint: in gdb, you can use the starti command to pause the program at its first instruction.

• During program execution, it provides support for library functions such as printf(). The example code above directly calls printf() without writing the code for printf(), but when executing ./a.out, it indeed successfully outputs information through printf(). Therefore, we have reason to guess that the crtxxx.o object files provide a way to execute printf() directly or indirectly. In fact, library functions are indeed part of the runtime environment.
• After program execution ends, it provides functionality for program exit. When you learned C before, you may have thought that a program exits directly after returning from main(). But if you understand that the runtime environment does a lot of preparation before executing main(), it is easy to guess that after returning from main(), control should return to the runtime environment, which then performs cleanup before program exit.

Does a Program Really End after Returning from main()?

Try using strace or gdb to verify your idea.

In general, a program alone is not enough for it to run. In a broad sense, all functionality that supports program execution belongs to the runtime environment.

Manual Behavior and Coding Standards

Just as the ISA manual defines instruction semantics, C semantics are also defined by a corresponding manual. After C appeared in the 1970s, it was widely used because of its efficiency, flexibility, and portability, but variants and extensions of C across different compilers created compatibility problems. To solve this challenge, ANSI established a committee in 1983 to standardize C. After many years of development, the C standard evolved into various versions, including C90, C99, C11, C17, and C23. These versions are usually named after the year when the standard was released; for example, C11 was released around 2011. In "One Student One Chip", we use C99 as an example to understand some definitions and concepts in the C standard, thereby building a more comprehensive understanding of C program behavior.

Implementation of Standard Specifications

The essence of a standard specification is a set of definitions and conventions, usually presented as a manual. To put a standard specification into practice, it must be implemented in some form; such a form is called an implementation of the standard specification. For example, an ISA is essentially a standard specification, and a processor that implements this specification with digital circuits is an implementation of the ISA. Obviously, processor behavior must conform to the ISA specification.

Similarly, the C standard also has corresponding implementations. Section 3.12 of the C99 manual defines what an "implementation" is:

particular set of software, running in a particular translation environment
under particular control options, that performs translation of programs for,
and supports execution of functions in a particular execution environment

In other words, an implementation of the C standard is a particular set of software running in a particular translation environment, used to translate programs into a particular execution environment and support execution of functions in that environment. Using concepts we are familiar with, an implementation of the C standard is the compiler, used for program translation, and the runtime environment, used to support program execution. Here "compiler" is meant broadly and includes the assembler and linker. Similarly, the compiler and runtime environment must conform to the C standard.

Standard specifications define many details, including various things that "should" or "should not" happen. These are clearly defined behaviors, and the corresponding behavior of a concrete implementation must follow the standard specification. But standard specifications cannot clearly define behavior in every situation. We will continue discussing this below.

Semantics of Program Execution

Recall the state machine model of computer systems: the process of executing a C program is the process of changing program state through C statements. This understanding is based on the state machine model. Now let's see how the C standard defines "program execution"; this will help us further understand the details of program execution.

Section 5.1.2.3 of the C99 manual defines "program execution". We explain these definitions one by one:

1 The semantic descriptions in this International Standard describe the behavior of
an abstract machine in which issues of optimization are irrelevant.

In the manual, the semantic descriptions of program execution are for an abstract machine and do not involve optimization. Here, the concept of an abstract machine is similar to the model machine we discussed when introducing ISAs: it discusses only its functions and behavior, not its concrete implementation.

2 Accessing a volatile object, modifying an object, modifying a file, or calling a
function that does any of those operations are all side effects, which are changes
in the state of the execution environment. Evaluation of an expression in general
includes both value computations and initiation of side effects. Value computation
for an lvalue expression includes determining the identity of the designated object.

Accessing a volatile object, modifying an object, modifying a file, or calling a function that performs any of these operations are all called side effects, meaning changes to the state of the execution environment. Evaluating an expression generally includes both value computation and initiation of side effects. Computing an lvalue expression also includes determining the identity of the designated object.

The concepts of "access" and "modify" are both defined in Chapter 3 of the manual, Terms, definitions, and symbols. Specifically, "access" means reading or modifying the value of an object, and "modify" includes the case where the new value to be stored is the same as the old value.

3 Sequenced before is an asymmetric, transitive, pair-wise relation between
evaluations executed by a single thread, which induces a partial order among those
evaluations. Given any two evaluations A and B, if A is sequenced before B, then the
execution of A shall precede the execution of B. (Conversely, if A is sequenced
before B, then B is sequenced after A.) If A is not sequenced before or after B,
then A and B are unsequenced. Evaluations A and B are indeterminately sequenced when
A is sequenced either before or after B, but it is unspecified which. The presence
of a sequence point between the evaluation of expressions A and B implies that every
value computation and side effect associated with A is sequenced before every value
computation and side effect associated with B. (A summary of the sequence points is
given in annex C.)

• "Sequenced before" is an asymmetric and transitive pairwise relation defined for evaluations executed in a single thread; it induces a partial order among those evaluations.
• Given any two evaluations A and B, if A is sequenced before B, then the execution of A occurs before the execution of B.
• Conversely, if A is sequenced before B, then B is sequenced after A.
• If A is neither sequenced before nor sequenced after B, then A and B are unsequenced.
• If A is sequenced before B or A is sequenced after B, but which one is not specified, then A and B are indeterminately sequenced.
• If a sequence point exists between the evaluations of expressions A and B, then all value computations and side effects associated with A are sequenced before all value computations and side effects associated with B.
• Annex C gives a summary of sequence points.

Item 3 strictly defines legal order relations among different evaluations through sequence points. Combined with the side effects defined in item 2, it strictly defines the semantics of the whole program execution. For example, consider the following program:

a = 1;
b = a + 2;

According to the summary of sequence points in Annex C, there is a sequence point between the expression evaluations of expression statements. According to the definition of sequence points, this means all value computations and side effects related to the expression a = 1 must occur and take effect before evaluating b = a + 2. Therefore, when evaluating b = a + 2, the value of a has already been modified to 1, so the program reads 1 from variable a at that moment.

You may feel that this does not seem very useful. Let's look at the following example. What does this program output?

#include <stdio.h>
int f() { printf("in f()\n"); return 1; }
int g() { printf("in g()\n"); return 2; }
int h() { printf("in h()\n"); return 3; }
int main () {
  int result = f() + g() * h();
  return 0;
}

In fact, this program may output any order of function calls, because multiple function calls in the same expression statement are indeterminately sequenced, so they may be called in any order. If the program behavior depends on a particular call order, the execution result may not match expectations.

4 In the abstract machine, all expressions are evaluated as specified by the
semantics. An actual implementation need not evaluate part of an expression if it
can deduce that its value is not used and that no needed side effects are produced
(including any caused by calling a function or accessing a volatile object).

In the abstract machine, all expressions are evaluated according to the corresponding semantics. In a concrete implementation, if the value of part of an expression is not used and no needed side effects are produced, including side effects caused by function calls or accesses to volatile objects, then this part of the expression does not need to be evaluated.

Item 4 actually indicates optimization opportunities in expression evaluation.

5 When the processing of the abstract machine is interrupted by receipt of a signal,
the values of objects that are neither lock-free atomic objects nor of type volatile
sig_atomic_t are unspecified, as is the state of the floating-point environment. The
value of any object modified by the handler that is neither a lock-free atomic
object nor of type volatile sig_atomic_t becomes indeterminate when the handler
exits, as does the state of the floating-point environment if it is modified by the
handler and not restored to its original state.

Item 5 is related to the signal mechanism and is beyond the current learning scope, so we will not expand on it here.

6 The least requirements on a conforming implementation are:
- Accesses to volatile objects are evaluated strictly according to the rules of the
  abstract machine.
- At program termination, all data written into files shall be identical to the
  result that execution of the program according to the abstract semantics would
  have produced.
- The input and output dynamics of interactive devices shall take place as specified
  in 7.21.3. The intent of these requirements is that unbuffered or line-buffered
  output appear as soon as possible, to ensure that prompting messages actually
  appear prior to a program waiting for input.
This is the observable behavior of the program.

A conforming implementation must satisfy at least three requirements. This is the "consistency of program observable behavior" discussed earlier in compilation optimization.

7 What constitutes an interactive device is implementation-defined.

What exactly counts as an interactive device is defined by the implementation.

8 More stringent correspondences between abstract and actual semantics may be
defined by each implementation.

Each implementation may further define stricter correspondences between abstract semantics and actual semantics.

Earlier we mentioned that "standard specifications cannot clearly define behavior in every situation". Understanding how concrete implementations handle these behaviors will help us understand how computer systems work and guide us to write more standard-conforming code that avoids these behaviors.

Using C99 as an example, behaviors that cannot be clearly defined fall into the following categories. Their concepts are all defined in Chapter 3 of the manual, Terms, definitions, and symbols.

Unspecified Behavior

The C99 manual defines Unspecified Behavior as follows:

use of an unspecified value, or other behavior where this International
Standard provides two or more possibilities and imposes no further requirements
on which is chosen in any instance

In other words, for the result of this kind of behavior, the C standard provides multiple choices but does not specify which one to choose. The concrete implementation may choose one of them.

The C99 manual gives the following example:

An example of unspecified behavior is the order in which the arguments to a
function are evaluated

That is, the order in which function-call arguments are evaluated is unspecified. We can verify this with the following program:

// a.c
#include <stdio.h>
void f(int x, int y) {
  printf("x = %d, y = %d\n", x, y);
}
int main() {
  int i = 1;
  f(i ++, i ++);
  return 0;
}

On yzh's system, compiling and running the program with gcc and clang respectively gives the following results:

$ gcc a.c && ./a.out
x = 2, y = 1
$ clang a.c && ./a.out
x = 1, y = 2

As you can see, even for the same program code, using different compilers to compile it can produce different runtime results.

Experience Unspecified Behavior

Try compiling and running the program above on your system and observe the result.

If you try compiling and running the program above on your own system, the result may differ from yzh's. If so, this means that even the same compiler may produce different runtime results for this program when different versions are used, but this still conforms to the C standard. More extremely, a compiler could randomly decide the evaluation order of function-call arguments, and this would still conform to the C standard!

if (rand() & 1) { evaluate from left to right; }
else            { evaluate from right to left; }

Since neither the C standard nor its implementation is wrong, the problem can only be the program. In fact, the behavior of the program above depends on unspecified behavior in the C standard, causing the program to behave differently under different compilers. If we do not want this result, we should write code that is not affected by unspecified behavior. For example, rewrite the code above as follows:

  int i = 1;
  int x = i ++;
  int y = i ++;
  f(x, y);

Then, regardless of the evaluation order used by f(x, y), the program behavior always outputs x = 1, y = 2, and is therefore not affected by unspecified behavior.

Try Understanding Argument Evaluation Order from Sequence Points

Look up the relevant content about argument evaluation in the C99 manual. How does the manual describe argument evaluation order from the perspective of sequence points?

Implementation-defined Behavior

The C99 manual defines Implementation-defined Behavior as follows:

unspecified behavior where each implementation documents how the choice is made

In other words, this kind of behavior is a special kind of unspecified behavior, but the concrete implementation must document how it makes the choice. Unlike ordinary unspecified behavior, once the concrete implementation documents its choice for implementation-defined behavior, it cannot change it arbitrarily. The concrete implementation must follow not only the C standard, but also its own documentation. Therefore, programs containing this kind of behavior can still produce the same result when compiled and run multiple times in a specific environment, including a compiler and runtime environment.

A common example is the length of integer types. In fact, the C standard has never defined how long each integer type is. Section 5.2.4.2 of the C99 manual states the following about integer type lengths:

An implementation is required to document all the limits specified in this
subclause, which are specified in the headers <limits.h> and <float.h>.
Additional limits are specified in <stdint.h>.

Regarding the lengths of integer types, Section 5.2.4.2.1 of the C99 manual states:

The values given below shall be replaced by constant expressions suitable for
use in #if preprocessing directives. Moreover, except for CHAR_BIT and
MB_LEN_MAX, the following shall be replaced by expressions that have the same
type as would an expression that is an object of the corresponding type
converted according to the integer promotions. Their implementation-defined
values shall be equal or greater in magnitude (absolute value) to those shown,
with the same sign.

Here we list some of the values mentioned as the values given below:

	Value	Description
SCHAR_MIN		Minimum value of signed char
SCHAR_MAX		Maximum value of signed char
UCHAR_MAX		Maximum value of unsigned char
SHRT_MIN		Minimum value of short int
SHRT_MAX		Maximum value of short int
USHRT_MAX		Maximum value of unsigned short int
INT_MIN		Minimum value of int
INT_MAX		Maximum value of int
UINT_MAX		Maximum value of unsigned int
LONG_MIN		Minimum value of long int
LONG_MAX		Maximum value of long int
ULONG_MAX		Maximum value of unsigned long int
LLONG_MIN		Minimum value of long long int
LLONG_MAX		Maximum value of long long int
ULLONG_MAX		Maximum value of unsigned long long int

As you can see, the C standard only defines the minimum range of values for each integer type. Concrete implementations may define larger ranges for each integer type, but cannot define ranges smaller than the minimum ranges defined by the C standard.

Why does the C standard make such rules? We can learn the purpose of the C standard from the abstract of the C99 manual:

This International Standard specifies the form and establishes the
interpretation of programs expressed in the programming language C. Its purpose
is to promote portability, reliability, maintainability, and efficient
execution of C language programs on a variety of computing systems.

To maximize compatibility with various computer systems, the C standard must consider:

• Supporting past computer systems, so many rules cannot be too rigid. Careful readers may have noticed that in the C standard, the greatest lower bound for the minimum value of signed char is , but the minimum number representable by 8-bit two's complement is . This is because the C standard considers that some past computers used sign-magnitude or ones' complement representation, where an 8-bit signed number can represent a minimum value of . If the C standard defined the greatest lower bound for the minimum value of signed char as , it would not be compatible with those computers.

How Long Is One Byte?

You might answer "8 bits" without thinking. But in fact, Section 3.6 of the C standard says that the number of bits in one byte is implementation-defined:

A byte is composed of a contiguous sequence of bits, the number of which
is implementation-defined

This is clearly for compatibility with past computer systems: historically, the length of one byte has been defined as different numbers of bits on different computers, ranging from 1 bit to 48 bits. Therefore, the C standard cannot directly define 1 byte as 8 bits; it leaves this to the concrete implementation.

Careful readers may also have noticed that the C standard content quoted above indirectly describes integer type lengths using value ranges instead of direct descriptions such as 4 bytes. This is also to avoid using the concept of byte, which is ambiguous across different implementations.

• Supporting future computer systems, so many rules must also be compatible with the future. The C standard defines only the minimum range of values for each integer type precisely to leave room for the future. Take the int type as an example. In some environments from the 1990s, such as Turbo C, which some old textbooks used as a development environment, int is 16 bits. In 32-bit systems, such as Windows VC 6.0 or GCC on Linux, int is 32 bits. In modern 64-bit systems, int is still 32 bits.

View the Range of Integer Types in Linux

The Linux runtime environment is also part of a concrete implementation of the C standard. You can view /usr/include/limits.h to understand the range of integer types in this concrete implementation.

In summary, programs containing implementation-defined behavior can produce the same result when compiled and run multiple times in a specific environment. But if the program is ported to another environment, you need to consider how implementation-defined behavior differs between the new environment and the old one. For example, if a 32-bit program is ported to a 16-bit environment, although this requirement is now very rare, one issue to consider is that data of type int may overflow. One solution is to change it to long, because the C standard requires long to have a value range of at least to , which can contain the value range of int in a 32-bit environment.

Locale-specific Behavior

The C99 manual defines Locale-specific Behavior as follows:

behavior that depends on local conventions of nationality, culture, and
language that each implementation documents

In other words, the result of this behavior depends on local conventions of country or region, culture, and language. The concrete implementation must document the result of the behavior. It is a special kind of implementation-defined behavior.

One example is the extended character set. Which characters are included in the extended character set is locale-specific behavior. Consider the following program:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

#define 主函数 main
#define 返回 return

char* 字符串拼接(char *串1, char *串2) {
  char *新串 = malloc(strlen(串1) + strlen(串2) + 1);
  assert(新串);
  strcpy(新串, 串1);
  strcat(新串, 串2);
  返回 新串;
}

int 主函数() {
  char *信息 = 字符串拼接("一生一芯", "很简单");
  printf("%s\n", 信息);
  free(信息);
  返回 0;
}

The program above uses strings and identifiers containing Chinese characters. In a concrete implementation that supports Chinese characters, this program can compile and run successfully; in a concrete implementation that only supports the basic character set, namely ASCII, this program cannot compile.

Usually, locale-specific behavior needs to be considered when developing internationalized software, or i18n. Besides character sets, locale-specific behavior includes decimal-point characters, currency symbols, time and date formats, and so on. However, "One Student One Chip" does not involve this kind of software, so you do not need to study it deeply.

Undefined Behavior

The C99 manual defines Undefined Behavior as follows:

behavior, upon use of a nonportable or erroneous program construct or of
erroneous data, for which this International Standard imposes no requirements

This is a kind of erroneous behavior where the program or data does not conform to the standard, but the C standard imposes no constraints on the result of this behavior. In other words, any result conforms to the C standard. Informally, "anything can happen". The C99 manual lists some possible results:

Possible undefined behavior ranges from ignoring the situation completely with
unpredictable results, to behaving during translation or program execution in a
documented manner characteristic of the environment (with or without the
issuance of a diagnostic message), to terminating a translation or execution
(with the issuance of a diagnostic message).

These results include:

• Reporting an error and exiting during compilation or execution
• Handling it according to the documentation of the concrete implementation, possibly without warning
• Completely unpredictable results

One example of undefined behavior is buffer overflow. Consider the following program:

// a.c
#include <stdio.h>
int main() {
  int a[10] = {0};
  printf("a[10] = %d\n", a[10]);
  return 0;
}

Experience Undefined Behavior

Try compiling and running the program above multiple times on your system, and observe the results.

The program above references a[10] when calling printf(), accessing an element beyond the boundary of the array. According to the C standard, the value of a[10] is undefined. Therefore, whether the compiler reports an error, the program reports an error during execution, or the program outputs 0 or a garbage value, all of these behaviors conform to the C standard.

Programs containing undefined behavior are very likely unable to produce correct results even after being compiled and run multiple times. If your program produces different results across multiple runs, after ruling out external sources of randomness, you can suspect that your program contains undefined behavior.

Why RTFM?

We quoted the original text from the C standard above because we hope everyone sees the precise definitions of certain concepts in the C standard. You are unlikely to see similar concepts and definitions in most other materials. For example, even if you have taken a C course or learned C through other materials, this may be the first time you have heard of concepts such as "undefined behavior" and "sequence point".

This shows that the C textbooks and learning materials you have encountered are not the entirety of C. In fact, the C standard precisely defines every detail of C, and we have reason to believe that the authors of the C standard understand C more deeply than authors of books and blogs.

Of course, different people learn C for different purposes. If the goal is to write some simple programs in C or pass exams, most textbooks and learning materials are already sufficient. On that basis, if you want to study C more deeply, understand the basic principles of how computer systems work, or even build your own computer system, reading the C standard manual is the best choice.

The goal of "One Student One Chip" is the latter. Unlike other chips, a processor chip is designed to run software programs. Therefore, we view processor chip design from the perspective of computer systems: you not only need to learn how to design a processor chip, but also need to learn how to run programs on that chip, so you can check whether programs run correctly and well.

As your learning deepens, you will gradually encounter problems that books and blogs cannot explain clearly. At that time, you need to realize that you have started entering the domain of professionals. Learning to read manuals is a pass to becoming a professional.

However, manuals contain a great deal of content. When we suggest reading manuals, we do not expect you to master everything in a short time. More importantly, we want you to develop the awareness of reading manuals: when you want to thoroughly understand a problem, you should think of reading the relevant manual content; even if you can find related answers on the Internet, you should still think of checking what the manual says, unless those answers explicitly quote the manual, which makes them excellent answers. If you can build this awareness and put it into practice, your understanding of C is already in the top 1% of the industry.

Reference List for the Behaviors Above

Annex J of the C99 manual lists all instances of the four behavior categories above in the C standard. Consult it when needed.

Application Binary Interface

We already know that a concrete implementation of the C standard is a set of software, mainly a compiler and runtime environment. The compiler is responsible for generating the program's binary executable, and the runtime environment is responsible for supporting program execution. On one hand, a program's binary executable is related to the ISA, and the program executes on a processor of the corresponding ISA. On the other hand, the runtime environment includes library functions and part of the operating system's functionality, and the program needs to interact with them before, during, and after running.

Therefore, the concepts of program, compiler, operating system, library functions, and ISA are related to each other as a whole computer system. This relationship is generally presented through conventions and specifications. This is the Application Binary Interface, abbreviated ABI. That is, the ABI is the interface specification between a program and the concepts above at the binary level.

Because the C standard needs to be compatible with all kinds of computer systems, it cannot precisely define the results of many behaviors. But for a specific computer system, many conditions are fixed. As the binary-level convention of this computer system, the ABI can be viewed as documentation for a concrete implementation of the C standard. Therefore, many choices for implementation-defined behavior at the C standard level are written into the ABI.

For example, for a specific ISA, the widths of bytes and general-purpose registers are fixed. Based on this, the ABI can determine the value ranges of C integer types. The whole computer system follows the ABI's consistent understanding of integer type ranges, thereby jointly supporting program execution.

As a specification, ABI content includes:

• The processor instruction set, register structure, stack organization, memory access types, and so on
• The size, layout, and alignment of basic data types directly accessible by the processor
• Calling conventions, which specify how function arguments are passed and how return values are obtained
• How applications initiate system calls to the operating system
• Object file formats, supported runtime libraries, and so on

Once again, we see that the result of running a program on a specific computer system is related to the source code, compiler, runtime environment, ISA, hardware, and more. The ABI is also an important manifestation of computer-system software and hardware cooperating to support program execution. For now, you only need a basic understanding of ABI. We will use RISC-V as an example in the D stage to introduce concrete ABI content.

RTFM

Of course, besides the C standard manual, we also recommend reading other manuals in your spare time, including the RISC-V manual, Verilog manual, and RISC-V ABI manual, among others. They can provide the most comprehensive and authoritative help for understanding related details. If you find them very difficult to read, do not worry. As you accumulate more foundational knowledge while learning, returning to these manuals will become smoother and smoother.

yyz