Computer programs as we know them today derive from a model proposed by John Von Neumann, considered to be one of the smartest people of the 20th Century. This is impressive, since that is the century that gave us airplanes, rocketships, nuclear power, and the electric guitar. Speaking of nuclear power, von Neumann worked on the Manhattan Project, where he first became interested in computers.

Wait, let's back up a moment. The earliest computers were either built to perform specific calculations, or were programmed in hardware, using patch cords or other mechanical connections. Alan Turing, another wicked smart 20th Century mathematician, came up with idea of a universal computer that could store its program internally and read it like data. Von Neumann -- and two colleagues who were out to lunch when the paper was written -- realized this idea with a program architecture sharing data and code in a single address space.

Let's look at an example that computes the average of two numbers.

#include <stdio.h>

int main()
{
        int x = 3;
        int y = 4;
        float z = 0;
        z = z + y;
        z = z / 2;
        printf("z is %f\n", z);
        return 0;
}

It's not a very efficient way to write this code, but it will give us the answer. (Question: why did we declare z as a float instead of an int?) Here is an excerpt from the assembly code generated by the GNU C++ compiler.

        .file   "strpgm01.c"
        .section        .rodata
.LC2:                           DATA (VARIABLES) ARE STORED WITH INSTRUCTIONS
        .string "z is %f\n"     THIS STRING IS NOT NAMED IN THE PROGRAM
        .text
        .globl  main
        .type   main, @function
main:
.LFB0:
        .cfi_startproc      INSTRUCTIONS START HERE
        pushq   %rbp
        movq    %rsp, %rbp

...

.LC1:
        .long   1073741824
        .ident  "GCC: (Ubuntu 5.4.0-6ubuntu1~16.04.10) 5.4.0 20160609"
        .section        .note.GNU-stack,"",@progbits

All of the symbols beginning with a period (.) are instructions to the compiler. The left-aligned symbols with the trailing colon (:) are labels marking branch targets in the program. The only label in this program is main:, the entry point of our program.

We will look at the assembly instructions another time. What we want to notice here is that the data and instructions are stored together in the program. The unnamed string from the printf statement appears before the main function begins. The long near the end will hold the return value.

Combining code and data in a program allowed a number of innovations, including the development of operating systems.

But where are our x,y, and z variables? Shouldn't they be in our program as well? Actually, they are. They are just in a structure we cannot see called the runtime stack. To understand how this works we need to look at two of the big innovations in programming languages over the last half-century or so: procedure calls and dynamic memory allocation.

The earliest programming languages -- like COBOL and FORTRAN -- originally lacked any concept of separate functions -- also known as subroutines, procedures, and most recently methods. If programmer had a special purpose segement of code they wished to run, they would explicitly branch to it using a line number or label (like main: in our example above). This inserted the branch target address into the Program Counter in the CPU. It was the programmer's responsibility to branch back to the correct location. There was no concept of parameters, local variables or return values.

This early model presented a number of challenges for programmers. It was often difficult to predict how much large to make data structures. Without local variables, programs quickly became complex and error prone. And without the concept of subroutines, large programs were extremely difficult to maintain. FORTRAN II added support for subroutines with return values and pass by reference parameters, but they were little more than structured GOTO statements. Modern programming would require two innovations in memory management -- dynamic memory allocation and the runtime stack.

In early programming languages, if I wanted to create a list, stack, or other data structure, I was obliged to know in advance how many elements my structure could hold and what size each element would be. The compiler then allocated the space for the structure in the data segment of my code.

Dynamic memory allocation allows programmers to allocate memory at runtime, based (for example) on the number of data elements a program is required to process. Among other innovations, dynamic memory allocation enabled the development of object-oriented languages. Efficient polymorphism requires runtime creation of objects. (Why?)

C was one of the first languages to explicity support dynamic allocation. The memory allocation API comprises 4 functions:

• malloc()  Allocates a single block of memory
• calloc()   Allocates sized and initialized blocks of memory
• free()   Frees allocated memory
• realloc() Changes (increases) allocation of previously allocated memory

Each function (except free) returns the address of the beginning of the created block. Dynamic memory creation in OO languages like Java uses a class prototype to guide memory allocation, most often using the new keyword. Deallocation of memory that is no longer used is accomplished through a process known as garbage collection. One notable exception to the last rule is C++, which typically requires developers to deallocate unneeded objects.

Memory allocated for a program is divided into three segments. The first is the static segment, containing the machine instructions and static data of the program. Since the size of compiled code does not change, the size of this segment is constant. The second segment is known as the heap. The heap segment is reserved for dynamically allocated memory (e.g. objects). The heap segment usually begins at the end of the static segment and grows up (addresses increase) as memory is allocated.

The third segment is called the runtime stack, or often just the stack.The stack is used to manage data storage and retrieval for calling and returning from functions. The stack typically starts at the top of the program's allocated memory and grows down (i.e. addresses decrease as the stack grows).

When a subroutine is called, several things need to happen:

• Executing code is ‘suspended’
• Parameters are placed where the called procedure can access them
• Control branches to subroutine code
• Subroutine acquires the storage needed for its execution
• Subroutine is executed
• Result is placed where the calling program can acces it
• Control returns to the statement after the subroutine call

The data used to manage this process is called an activation record or stack frame. As illustrated in the figure, it contains space for arguments, local variables, compiler-generated temporary variables, a few important addresses, and values from registers that were in use by the calling program. Managing the stack frame is primarily the responsibility of the calling routine or program. This happens primarily in two code segments that bracket the subroutine code.

The prolog is placed before the body of the function by the compiler and performs the following operations:

• Pushes the value of the link register (LR) onto the stack.
• Pushes the value of the frame pointer (FP) onto the stack.
• Sets the FP (register) to the value of the stack pointer (SP). (Lets the debugger find previous stack frames.)
• Pushes the values of the registers that must be preserved onto the stack.
• Allocates space in the stack frame for local storage.

After the body of the function, the compiler places an epilog to restore the process to the state it was prior to the subroutine call.

• Deallocates the space used for local storage in the stack.
• Restores the preserved register values saved on the stack by the prolog.
• Restores the value of the frame pointer (FP).
• Returns by popping the saved link register (LR) into the program counter (PC).

Resources:

Assembly cheatsheet

Introduction to X86-64 Assembly for Compiler Writers

GNU Assembler Examples