You are currently browsing the archives for the C90 tag.

The C build process

June 29th, 2012

In this article we look at the C build process – that is, how we get from C source files to executable code, programmed on the target.  It wasn’t so long ago this was common knowledge (the halcyon days of the hand-crafted make file!) but modern IDEs are making this knowledge ever-more arcane.

Compilation

The first stage of the build process is compilation.

image

The compiler is responsible for allocating memory for definitions (static and automatic) and generating opcodes from program statements. A relocatable object file (.o) is produced.  The assembler also produces .o files from assembly-language source.

The compiler works with one translation unit at a time.  A translation unit is a .c file that has passed through the pre-processor.

The compiler and assembler create relocatable object files (.o)

A Librarian facility may be used to take the object files and combine them into a library file.

Compilation stages

Compilation is a multi-stage process; each stage working with the output of the previous.  The Compiler itself is normally broken down into three parts:

  • The front end, responsible for parsing the source code
  • The middle end, responsible for optimisation
  • The back end, responsible for code generation

Front End Processing:

Pre-processing

The pre-processor parses the source code file and evaluates pre-processor directives (starting with a #) – for example #define.  A typical function of the pre-processor is to#include function / type declarations from header files.  The input to the pre-processor is known as a pre-processed translation unit; the output from the pre-processor is a post-processed translation unit.

Whitespace removal

C ignores whitespace so the first stage of processing the translation unit is to strip out all whitespace.

Tokenising

A C program is made up of tokens.  A token may be

  • a keyword (for example ‘while’)
  • an operator (for example, ‘*’)
  • an identifier; a variable name
  • a literal (for example, 10 or “my string”)
  • a comment (which is discarded at this point)

Syntax analysis

Syntax analysis ensures that tokens are organised in the correct way, according to the rules of the language.  If not, the compiler will produce a syntax error at this point.  The output of syntax analysis is a data structure known as a parse tree.

Intermediate Representation

The output from the compiler front end is a functionally equivalent program expressed in some machine-independent form known as an Intermediate Representation (IR).  The IR program is generated from the parse tree.

IR allows the compiler vendor to support multiple different languages (for example C and C++) on multiple targets without having n * m combinations of toolchain.   

There are several IRs in use, for example Gimple, used by GCC.  IRs are typically in the form of an Abstract Syntax Tree (AST) or pseudo-code.

Middle End Processing:

Semantic analysis

Semantic analysis adds further semantic information to the IR AST and performs checks on the logical structure of the program.  The type and amount of semantic analysis performed varies from compiler to compiler but most modern compilers are able to detect potential problems such as unused variables, uninitialized variables,  etc.  Any problems found at this stage are normally presented as warnings, rather than errors.

It is normally at this stage the program symbol table is constructed, and any debug information inserted.

Optimisation

Optimisation transforms the code into a functionally-equivalent, but smaller or faster form.  Optimisation is usually a multi-level process.  Common optimisations include inline expansion of functions, dead code removal, loop unrolling, register allocation, etc.

Back End Processing:

Code generation

Code generation converts the optimised IR code structure into native opcodes for the target platform.

Memory allocation

The C compiler allocates memory for code and data in Sections.  Each section contains a different type of information.  Sections may be identified by name and/or with attributes that identify the type of information contained within.  This attribute information is used by the Linker for locating sections in memory (see later).

Code

Opcodes generated by the compiler are stored in their own memory section, typically known as .code or  .text

image

Static data

The static data region is actually subdivided into two further sections:

  • one for uninitialized-definitions (int iVar1;).
  • one for initialised-definitions (int iVar2 = 10;)

So it would not be unexpected for the address of iVar1 and iVar2 to not be adjacent to each other in memory.

The uninitialized-definitions’ section is commonly known as the .bss or ZI section. The initialised-definitions’ section is commonly known as the .data or RW section. 

image

Constants

Constants may come in two forms:

  • User-defined constant objects (for example const int c;)
  • Literals (‘magic numbers’, macro definitions or strings)

The traditional C model places user-defined const objects in the .data section, along with non-const statics (so they may not be truly constant – this is why C disallows using constant integers to initialise arrays, for example)

Literals are commonly placed in the .text / .code section.  Most compilers will optimise numeric literals away and use their values directly where possible.

Many modern C toolchains support a separate .const / .rodata section specifically for constant values.  This section can be placed (in ROM) separate from the .data section.  Strictly, this is a toolchain extension.

image

Automatic variables

The majority of variables are defined within functions and classed as automatic variables. This also includes parameters and any temporary-returned-object (TRO) from a non-void function.
The default model in general programming is that the memory for these program objects is allocated from the stack. For parameters and TRO’s the memory is normally allocated by the calling function (by pushing values onto the stack), whereas for local objects, memory is allocated once the function is called. This key feature enables a function to call itself – recursion (though recursion is generally a bad idea in embedded programming as it may cause stack-overflow problems). In this model, automatic memory is reclaimed by popping the stack on function exit.

It is important to note that the compiler does NOT create a .stack segment.  Instead, opcodes are generated that access memory relative to some register, the Stack Pointer, which is configured at program start-up to point to the top of the stack segment (see below)

However, on most modern microcontrollers, especially 32-bit RISC architectures, automatics are stored in scratch registers, where possible, rather than the stack. For example the ARM Architecture Procedure Call Standard (AAPCS) defines which CPU registers are used for function call arguments into, and results from, a function and local variables.

image

Dynamic data

Memory for dynamic objects is allocated from a section known as the Heap.  As with the Stack, the Heap is not allocated by the compiler at compile time but by the Linker at link-time.

image

Object files

The compiler produces relocatable object files – .o files.
The object file contains the compiled source code – opcodes and data sections.  Note that the object file only contains the sections for static variables.  At this stage, section locations are not fixed.

The .o file is not (yet) executable because, although some items are set in concrete (for example: instruction opcodes, pc-relative addresses, “immediate” constants, etc.), static and global addresses are known only as offsets from the starts of their relevant sections. Also, addresses defined in other modules are not known at all, except by name.  The object file contains two tables -  Imports and Exports:

  • Exports contains any extern identifiers defined within this translation unit (so no statics!)
  • Imports contains any identifiers declared (and used) within the translation; but not defined within it.

Note the identifier names are in name-mangled form.

image

Linking

The Linker combines the (compiled) object files into a single executable program.  In order to do that it must perform a number of tasks.

image

Symbol resolution

The primary function of the Linker (from whence it derives its name) is to resolve references between object files – that is, to ensure each symbol defined by the program has a unique address.

If any references remain unresolved, all specified library/archive (.a) files are searched and the appropriate modules are gathered in order to resolve those references.  This is an iterative process.  If, after this, the Linker still cannot resolve a symbol it will report an ‘unresolved reference’ error.

Similarly, C specifies a ‘one-definition rule’ – that is, each symbol must have a unique and unambiguous address.  If the Linker finds the same symbol defined in two object files it will report a ‘redefinition’ error (be careful, though – some older C compilers assume that the same symbol defined in two translation units must refer to the same object!)

Section concatenation

The Linker then concatenates like-named sections from the input object files.
The combined sections (output sections) are usually given the same names as their input sections.  Program addresses are adjusted to take account of the concatenation.

Section location

To be executable code and data sections must be located at absolute addresses in memory.  Each section is given an absolute address in memory.  This can be done on a section-by-section basis but more commonly sections are concatenated from some base address.  Normally there is one base address in non-volatile memory for persistent sections (for example code) and one address in volatile memory for non-persistent sections (for example the Stack).

Data initialisation

On an embedded system any initialised data must be stored in non-volatile memory (Flash / ROM).  On startup any non-const data must be copied to RAM.  It is also very common to copy read-only sections like code to RAM to speed up execution (not shown in this example).
In order to achieve this the Linker must create extra sections to enable copying from ROM to RAM. Each section that is to be initialized by copying is divided into two, one for the ROM part (the initialisation section) and one for the RAM part (the run-time location).  The initialisation section generated by the Linker is commonly called a shadow data section – .sdata in our example (although it may have other names).

If manual initialization is not used, the linker also arranges for the startup code to perform the initialization.

The .bss section is also located in RAM but does not have a shadow copy in ROM.  A shadow copy is unnecessary, since the .bss section contains only zeroes.  This section can be initialised algorithmically as part of the startup code.

Linker control

The detailed operation of the linker can be controlled by invocation (command-line) options or by a Linker Control File (LCF). 

You may know this file by another name such as linker-script file, linker configuration file or even scatter-loading description file. The LCF file defines the physical memory layout (Flash/SRAM) and placement of the different program regions.  LCF syntax is highly compiler-dependent, so each will have its own format; although the role performed by the LCF is largely the same in all cases.

When an IDE is used, these options can usually be specified in a relatively friendly way.  The IDE then generates the necessary script and invocation options.

 image

The most important thing to control is where the final memory sections are located.  The hardware memory layout must obviously be respected – for most processors, certain things must be in specific places.

Secondly, the LCF specifies the size and location of the Stack and Heap (if dynamic memory is used). It is common practice to locate the Stack and Heap with the Heap at the lower address in RAM and the Stack at a higher address to minimise the potential for the two areas overlapping (remember, the Heap grows up the memory and the Stack grows down) and corrupting each other at run-time.

The linker configuration file shown above leads to a fairly typical memory layout shown here.

  • .cstartup – the system boot code – is explicitly located at the start of Flash.
  • .text and .rodata are located in Flash, since they need to be persistent
  • .stack and .heap are located in RAM.
  • .bss is located in RAM in this case but is (probably) empty at this point.  It will be initialised to zero at start-up.
  • The .data section is located in RAM (for run-time) but its initialisation section, .sdata, is in ROM.

image

 

The Linker will perform checks to ensure that your code and data sections will fit into the designated regions of memory.

The output from the locating process is a load file in a platform-independent format, commonly .ELF or .DWARF (although there are many others)

The ELF file is also used by the debugger when performing source-code debugging.

 

Loading

ELF or DWARF are target-independent output file formats.  In order to be loaded onto the target the ELF file must be converted into a native flash / PROM format (typically, .bin or .hex)

image

 

Key points

  • The compiler produces opcodes and data allocation from source code files to produce an object file.
  • The compiler works on a single translation unit at a time.
  • The linker concatenates object files and library files to create a program
  • The linker is responsible for allocating stack and free store sections
  • The linker operation is controlled by a configuration file, unique to the target system.
  • Linked files must be translated to a target-dependent format for loading onto the target.

Declarations and Definitions in C

January 18th, 2010

Please Note: This post is focusing on pre-C99. The reason being is that it is aimed at the embedded C programmer who tends to be working with pre-C99 based cross-compilers. Also I have split it into two as it became my larger, due to feedback, than first anticipated.

On the surface declarations and definitions in C are pretty straight-forward; but once we start introducing the concepts of scope, storage-duration, linkage and namespace life is not so simple.

Program Objects (Variables)

Let’s start with a general rule for variables:
  1. if the statement has an “=” it’s a definition?
  2. otherwise, if it has “extern” and no “=” it’s a declaration?
  3. otherwise it’s a tentative-definition that may become a declaration or a actual-definition

Object Definitions

Simply put, a definition allocates storage (memory) e.g.
int ev = 20; /* definition – reserves enough memory to hold an int */
Let’s assume from here-on that an int occupies 32-bits.

Object Declaration

A declaration gives meaning to an identifier; that is, it defines the type information of the identifier. This allows the compiler to generate correct object code to access the variable based its size (i.e. the number of bytes to read or write).

Usage

When compiling a source file, a variable must be declared before it is used or it will result in a compiler error.

int main(void)
{
   ev = 10; /* fails to compile as ev has not been declared */
   return 0;
}
int ev = 20; /* definition – allocates 32-bits */
Importantly, an object declaration does not reserve memory. e.g.
extern int ev; /* declaration – no memory reserved but defines sizeof(ev) */
int main(void)
{
   ev = 10; /* okay to use ev as declared, knows to read (say) 32-bits; k = 20 */
   return 0;
}
 int ev = 20; /* definition – memory reserved here and initialised */
Key point 1:
If no declaration is encountered before the definition, then the definition acts as an implicit declaration.
int ev = 20; /* definition and implicit-declaration: reserves memory */
int main(void) 
{
   ev = 10; /* okay to use ev as declared (implicitly) */ 
   return 0; 
}
Key point 2:
In a compiled source file there may be only one definition for an identifier, but there may be multiple declarations (as long as they agree).
extern int ev; /* 1st declaration */
extern int ev; /* 2nd declaration */
int main(void) { ev = 10; /* okay to use ev as declared */ return 0; } int ev = 20; /* definition */
In the examples so far, all definitions have included an initialisation and all declarations have used the “extern” keyword. But there is one further concept we need to examine and that is the concept of a tentative definition (this only applies to variables defined outside of functions – more on that later). Take, for example, the following program snippet:

int ev = 20; /* actual definition    */
int td;      /* tentative definition */
int main(void) { ... return 0; }
With a tentative definition, the following rule applies:

If an actual definition is found later in the source file, then the tentative definition just acts as a declaration. If the end of the source file is reached and no actual definition is found, then the tentative definition acts as an actual definition (and implicit declaration) with an initialisation of 0 (zero).

int ev; /* tentative definition becomes declaration */
int td; /* tentative definition become actual definition initialised to 0 */
int main(void)
{
   ...
   return 0;
}

int ev = 20; /* actual definition */
I’d like to address two more syntactical items before we move on. First, It is perfectly legal to write:
 extern int ev = 20; /* actual-definition */
  

I’m sure someone can (and will) tell me why this is useful, but in my 25 years of doing C I’ve never had need to use it. I my view anyone found doing this should be made to sit in the corner wearing a hat with a big ‘D’ on it!

Second, it is highly unusual (so unusual that I’ve never seen it used), but the following is also legal syntax:
 extern int(ev);
 int(ev);
 int(ev) = 20;
Before we start looking at such items as scope and linkage let’s address function declarations and definitions.

Functions

Function declarations and definitions are in many ways simpler than variables. A function definition includes the function’s body. e.g.

void f(int p) /* definition and implicit-declaration */
{
   ...
}

int main(void)
{
   f(10); /* okay to call f as declared */
   return 0;
}

A function’s declaration (typically called its prototype) makes the compiler aware there is a valid function with this identifier. e.g.

void f(int p); /* declaration */

int main(void)
{
   f(10); /* okay to call f as declared */
   return 0;
}

void f(int p) /* definition */
{
   // ...
}
On the call to the function “f” in main, the declaration enables the compiler to construct the correct call frame based on three things:
  1. the validity of the identifier
  2. the storage required to pass any parameters (by stack or register)
  3. the storage required for any return information
At the call, the names of function parameters, if any, are irrelevant (to the compiler), so can be omitted from the declaration, e.g. void f(int); /* declaration */
Also it is not illegal to have parameter names that differ from the declaration and the definition (but obviously very bad practice).

Before we move on, there are two problem areas we need to cover. First, let’s look at the following snippet:

int main()
{
   f(20); /* call f with no declaration */
   return 0;
}

void f(int i) /* definition and implicit-declaration */
{
   // ...
}

Here we are trying to call a function that hasn’t been declared. As probably expected, this code fails to compile, but not for the reason you probably assume. Earlier I stated that an identifier must be declared before being used otherwise you get a compiler error. Unfortunately this only applies to variables and not functions!

With functions, if no declaration is found before its first call, the compiler creates an implicit declaration. As it cannot determine the return type, then it assumes an int return type. So for the call
f(20);
the complier assumes a declaration of
int f();
The compiler error will actually occur at the definition of function “f” due to the implicit-declaration and definition not agreeing (as the definition is void f()). The parts being compared are officially called the function designator. As the two designators don’t match the compiler will generate an error of the form:

error: ‘f’ : redefinition; different basic types

If we change f’s return type to int, then this code will compile quite happily.

int main(void)
{
   f(20); /* call f implicit-designator of int f() */
   return 0;
}

int f(int i) /* definition’s designator matches implicit-designator */
{
   // ...
}
Why int as the return type? This is historical baggage. In the original specification of C by Kernighan & Ritche it states, regarding function return types:
If the return type is omitted, int is assumed.

This baggage is still evident today, as the following code should compile successfully:


int main()
{
   f(20); /* call f implicit-designator of int f() */
   return 0;
}

f(int i) /* definition’s designator has implicit return type of int */
{
   // ...
}
Horrible? Yes (and it’s going to get worse) but all it not lost – any modern compiler worth its salt will issue a warning similar to:

warning: 'f' undefined; assuming extern returning int

Never ignore this warning. Some compilers (such as IAR) allow a non-standard extension requiring function prototypes. Note that C++ also requires prototypes, thus closing this loophole.

Can it get worse? Oh yes, much worse.

There is a very common mistake that C programmers assume that an empty parameter list means the same as void in the parameter list. Unfortunately, in some cases it does and in others it doesn’t.

With a function definition, then empty parameter list is the same as void.

void f()       /* definition and implicit-decln of void f(void) */
{
   // ...
}

int main()
{
   f(20);       /* error as call doesn’t match decln */
   return 0;
}
However (and here it comes) for declarations this isn’t the case.
void f();      /* declaration */
void f(void);  /* prototype-declaration – not the same as above */
If a declaration has a parameter list (including void) then it becomes a prototype-declaration. The empty list in a function declarator specifies that no information about the number or types of the parameters is supplied. This has a horrible implication; take for example the following code:

void f(); /* declaration */
int main(void)
{
f(20); /* okay to call f as declared */
return 0;
}
void f(int i) /* definition */
{
// ...
}
This is perfectly legal C code, which will compile and run quite happily. The standard states that the number and types of arguments are not compared with those of the parameters in a function definition that does not include a function prototype (I know, I know, but please don’t shoot the messenger). Simply put, if there is an empty parameter list the compiler assumes that arguments to the call are correct, e.g.

void f(); /* declaration */
int main(void)
{
f(20); /* okay to call f as declared!!! */
return 0;
}
void f(void) /* definition */
{
// ...
}
So what happens above? Well the standard states that if the number of arguments does not agree with the number of parameters, the behaviour is undefined. In many cases with embedded systems, this actually won’t cause a major problem. Many modern microcontroller architectures (e.g. ARM) arguments are passed in registers. Only once the compiler starts using the stack to pass arguments will problems ensue.

Guideline: For all function always supply a function-prototype.

So hopefully that lays the groundwork of declarations and definitions we can now start addressing the concepts of scope, storage-duration, linkage and namespace.

Afternote:


void f()      /* definition and implicit-decln of void f(void) */
{
   // ...
}

int main(void)
{
   f(20);       /* error a call doesn’t match decln */
   return 0;
}
Microsoft compiler bug – this code should fail to compile. Microsoft compiles, whereas both IAR and Keil fail.
%d bloggers like this: