How can memory addresses be compile-time constants?

Question

In C the memory address of a statically allocated object or a function is considered compile-time constant. For example this is valid code:

static int x;
static int *const p = &x;
static const char *const s = "The address of this string will not necessarily be the same across executions";

But since there is no way all implementations can guarantee that the actual address of even statically allocated objects can be known at compile time, how can they be treated as compile-time constants and used in places where a constant expression is required such as an initializer for other statically allocated objects? But they are more similar to runtime constants. What techniques do compilers use to initialize statically allocated pointers to addresses of other statically allocated objects?

Answer 1

What techniques do compilers use to initialize statically allocated pointers to addresses of other statically allocated objects?

Broadly speaking it is not much different from a function call or access to a global variable. The compiler will insert a symbolic reference and the exact memory location will be filled in later.

Logically a program goes through a number of steps between source code and execution.

• Compilation.
• Assembly (optional, the compilation process may generate object files directly)
• Linking
• Loading/Dynamic linking (optional, the code may be burned into a rom).

At some stage in the process, the symbolic references in the code must be resolved to become actual addresses. There are broadly two stages where this can happen, if the code is built targetting a fixed address, then the linker can complete the resolution process. If the code is built to be relocatable at load time then the resolution process must be completed by the loader/dynamic linker.

I'm going to use the following code for my tests, it is similar to yours but I have removed the "static", this means that the compiler will not be able to optimise the unused variables away. I'm going to use arm32 as it's the platform whose assembler I find easy to read, and linux as the target OS. That said, the assembler I'm going to present isn't going to contain any actual code.

int x;
int *const p = &x;
const char *const s = "The address of this string will not necessarily be the same across executions";

On most linux ports* linux we can control whether the code is built to be relocatable or not with the -fPIC switch.

When looking at godbolt be aware that the output is heavily filtered by default. We need to turn off some of the filtering here or we will miss important stuff. I have manually skipped some stuff that is not relavent to the question.

First lets build it with no compiler flags. In this configuration the compiler will produce code that can be relocated at link time but cannot be relocated during the loading process.

        .global x
        .bss
        .align  2
        .type   x, %object
        .size   x, 4
x:
        .space  4

x is not initialised, so it is placed in the bss section and no initial valid is provides.

        .global p
        .section        .rodata
        .align  2
        .type   p, %object
        .size   p, 4
p:
        .word   x

x declared const, so it's placed in the rodata section. However the compiler does not provide a numeric value but merely a symbolic reference. The linker will fill in that symbolic reference later.

        .global s
        .align  2
.LC0:
        .ascii  "The address of this string will not necessarily be "
        .ascii  "the same across executions\000"
        .align  2
        .type   s, %object
        .size   s, 4
s:
        .word   .LC0

The compiler has put both the string literal and the constant s in the rodata section and like it has used a symbolic reference to allow s to refer to the string constant. The section is not explicitly selected in this block of code because it was already set to .rodata from the previous block.

So now lets try adding -fPIC how does the code change.

        .bss
        .align  2
        .type   x, %object
        .size   x, 4
x:
        .space  4

No change here, x is still an uninitialised variable in the bss section.

        .global p
        .section        .data.rel.ro,"aw"
        .align  2
        .type   p, %object
        .size   p, 4
p:
        .word   x

However, this has changed. Rather than being placed in the normal rodata section this has now been placed in a "data.rel.ro" section. This is a special area of memory that is writeable during the relocation phase of dynamic loading, but will become read-only once loading is complete.

        .global s
        .section        .rodata
        .align  2
.LC0:
        .ascii  "The address of this string will not necessarily be "
        .ascii  "the same across executions\000"
        .section        .data.rel.ro.local,"aw"
        .align  2
        .type   s, %object
        .size   s, 4
s:
        .word   .LC0

The string literal is still placed in the regular rodata section, since it doesn't refer to any memory locations, but the pointer to it is once-again placed in a special section.

* for historic reasons the situation is a bit different on x86-32.

Answer 2

One easy solution, used in C++ for instance, is to restrict the set of available compile-time operations on addresses. For instance, in C++ addresses generally can only be compared for equality, arrays being the exception (the addresses of array elements are ordered by position in the array).

So given two distinct symbols a and b, the compiler knows that &a != &b, and also knows that &a < &b is an invalid comparison.

The question seems to assume that the compiler needs a numerical value for addresses at compile time, but this is not actually required.

Answer 3

But since there is no way all implementations can guarantee that the actual address of even statically allocated objects can be known at compile time

(Emphasis mine.)

It's important to note that in C particularly, code is not necessarily portable. That is, code which works on one C compiler, for one target architecture, will not necessarily work when a different compiler is used, or when it is compiled for a different architecture. There are a few reasons for this:

• C should be able to target many different architectures, including very low-resource embedded architectures. In those contexts, statically-allocated memory with compile-time constant addresses makes sense, and dynamic allocation of memory might be infeasible.
• C leaves a lot of things as "unspecified behaviour", so that each compiler is free to define those behaviours how they wish; consequently, programmers are free to rely on that compiler's promised behaviour even where it goes beyond the C specification.
• C is supposed to be "close to the metal", allowing the programmer to take advantage of platform-specific optimisations if they want to. Loading from a constant address is presumably a bit faster (on some platforms) than loading and dereferencing a pointer, so C wants to make this available as an option for platforms where it makes sense. (There's also the basic fact that integer types in C have platform-dependent sizes.)

So in summary, C has features which don't necessarily work everywhere, because a lot of C code is written without the intention of it working everywhere, and because offering only a lowest-common-denominator set of features common to all target architectures would mean not being able to offer the performance that C programmers demand.

So "all implementations" don't need to guarantee this for it to be a feature in the language.

Answer 4

In C the memory address of a statically allocated object or a function is considered compile-time ... But since there is no way all implementations can guarantee that the actual address of even statically allocated objects can be known at compile time, how can they be treated as compile-time constants?

Fundamentally, the object code contains an expression capture mechanisms.  These mechanisms allow delaying computations involving unresolved symbols until their address information is known.  These expressions can be forwarded from object code (built directly from source) to be resolved during linking, or delayed even longer to be resolved during program loading.

The mechanism of relocations allows for such expression to be conveyed from source code to object code to executable, and these are know as to be resolved during final program construction, or even delayed to program loading.  Any such computations that can be resolved prior to the actual start of program execution are considered as constants, since any two such computations will yield the same values for the same symbols.

There are address computations that cannot be computed at compile time or even build or load time, and these go to the addresses of local variables that are placed onto the runtime stack, since there's no way at build time to know what the stack pointer value might be during any activation of a function (and that as recursion is supported, multiple copies of variables may be in multiple activations)   While the addresses of these variables can only be computed during runtime, some computations about them may be possible during build (e.g. subtraction of one address from another that is in the same array).  The compiler will switch strategies for constants known at compile time vs. runtime computed addresses.

Answer 5

There's no concept of "compile-time constants" in C. There is a concept of "constant expressions" and more specifically "address constants", which are the only kind of addresses that are allowed as initializers of static variables (const or not). Presumably they restricted initializers in that way so that implementations could initialize all static-duration objects at compile time rather than runtime, but that's only an optimization. An implementation that doesn't (or for technical reasons can't) do that can still comply with the standard.

In many execution environments, including modern desktop and phone operating systems with dynamic linking and ASLR, the values of address constants are not really decided until run time, so you can reasonably argue that they aren't compile-time constants—although it's operating-system code, not application code generated by the compiler, that calculates the runtime values. In environments without OS support for relocation, the compiler may generate code to do it, again at run time. The C standard doesn't forbid that, or, as far as I know, discuss it at all.

Answer 6

These addresses could be set to not be known at compile time (although one of the pointers is known to point to the static variable x), but they are constant (not changing).