Copyright: Copyright © 2020 Bob Steagall

Back to Basics: The Abstract Machine⌗

Talk: https://www.youtube.com/watch?v=ZAji7PkXaKY

PPT: back_to_basics_the_abstract_machine__bob_steagall__cppcon_2020.pdf

What is an abstract machine⌗

Abstract machines provide an intermediate language stage for compilation. They bridge the gap between the high level of a programming language and the low level of a real machine. The instructions of an abstract machine are tailored to the particular operations required to implement operations of a specific source language or class of lanquages."

Stephan Diehl, Pieter Hartel, Peter Sestoft Future Generation Computer Systems 16 2000)

“Programming language specifications (not just C and C++, all high-level programming language specifications), define the languages in terms of an abstract machine, which, in this usage, is the simplest imaginary computer capable of executing a program in the source language (or a family of languages, as in the case of the JVM).” (my emphasis)

Sergey Zubkow, www.quora.com (2015)

C++ Abstract Machines⌗

“The C++ abstract machine is a portable abstraction of your operating system, kernel and hardware. The abstract machine is the intermediary between your C++ program and the system that it is run on.”

Bryce Adelstein Lelbach, Core C++ 2019, The C++ Execution Model

Rationale⌗

We want abstraction to hide the complexity of different platforms.

The Programmer’s Concern⌗

Key takeaway: when we are writing C++ code, we are writing to the C++ Abstract Machine

Key aspects of C++ Abstract Machine⌗

The semantic descriptions in this document define a parameterized nondeterministic abstract machine. This document places no requirement on the structure of conforming implementations. In particular, they need not copy or emulate the structure of the abstract machine. Rather, conforming implementations are required to emulate (only) the observable behavior of the abstract machine as explained below.

Well-Formed, ill-formed, and IFNDR Program⌗

[defns.well.formed](3.32) C++ program constructed according to the syntax rules, diagnosable semantic rules, and the one-definition rule

for a well-formed program construct and correct data, that depends on the implementation and that each implementation documents

for a well-formed program construct and correct data, that depends on the implementation

  • Each unspecified behavior yields one result from the set of all possible valid results
  • This is the nondeterminism aspect of the abstract machine
  • eg
    • the evaluation order of arguments
    • how to store identical string literals

ill-formed program is not well-formed. ie. has syntax errors or diagnosable semantic errors

IFNDR (ill-formed, no diagnostic required) program is a program that has non-diagnosable semantic error

Structure of C++ Abstract Machine⌗

Memory⌗

  • Memory is a single flat space
  • All parts of memory are equally reachable by the abstract machine
  • There is no memory hierarchy
    • No concept of stack, registers, or cache (Although stack unwinding is mentioned several times)
    • No concept of heterogeneous memory (e.g., GPUs, co-processors)
  • Access to memory has uniform latency
  • Memory is composed of bytes
    • The standard specifies the minimum requirements for what a byte is in terms of what it must be able to represent
  • The memory available to a program consists of one or more sequences of contiguous bytes
    • Any operation in a program can potentially access any memory location in those sequences of bytes
  • Every byte has a unique location in memory - its address
    • Addresses are represented in our program by pointers

Objects⌗

  • Operations in a program create, destroy, refer to, access, and manipulate objects, which have
    • size
    • alignment
    • storage duration
    • lifetime
    • type
    • value
    • name (optional)
  • An object may have at most one memory location
  • An implementation is allowed to store two objects at the same address, or not store an object at all, if the program cannot observe the difference (the as-if rule at work!)

Expressions⌗

  • Every C++ expression has an associated type
  • Every C++ expression is a member of a value category

Threads⌗

  • What does it mean to invoke and execute a function?
    • Functions consist of statements
    • Statements consist of expressions
  • An expression is a sequence of operators and operands that specifies a computation
    • To perform that computation, the expression must be evaluated
    • Evaluating an expression can result in a value and can cause side effects
  • Evaluating an expressions that causes side effects results in changes to the program’s execution state, and possibly to observable behavior
  • The C++ standard rules governing the evaluation of expression are formulated in terms of an expression’s type and value category

BTB: structure of program⌗

Talk: https://www.youtube.com/watch?v=3KoXeegncrs

Link: back_to_basics_the_structure_of_a_program__bob_steagall__cppcon_2020.pdf

Translational Units and Phrase of Translation⌗

  1. A translation unit is defined (roughly) as
    1. A source file,
    2. Plus with all the headers and source files included via the #include directive,
    3. Minus any source lines skipped by conditional inclusion preprocessing directives (#ifdef),
    4. And all macros expanded
  2. 9 phrases 5. Preprocessing (Phrase 1 - 6) (page.22 - 27) 1. The output is the so-called translational unit 6. Compilation: syntax analysis, semantic analysis, codegen (Phrase 7 - 8) 1. The output is the translated translational unit 7. Linking: image creation

Declaration and Definition⌗

  1. Entity (These rules are about Entity)
  2. Name of the entity
    1. What surprises me is that: variable inside functions are declaration; this conforms to our big pictures in (3): the set of definition is a subset of declaration.
  3. Declaration
    1. Name of the entity is introduced by declaration
  4. Definition
    1. Every declaration is also a definition except …

Linkage⌗

  1. If names are these types of things …, then it may have linkage
  2. External Linkage: can be used by other translational unit
  3. Internal Linkage: can be used inside the entire translational unit
  4. No Linkage: can only be used within the scope it’s declared

ODR⌗

  1. A given translational unit can contain at most one definition of any …
  2. A given program must contain exactly one definition of every non-inline variable or function that is used in the program
    • multiple declarations are OK, but only one definition

For an inline variable or an inline function, a definition is required in every translation unit that uses it

  • inline was originally a suggested optimization made to the compiler
  • It has now evolved to mean “multiple definitions are permitted”
  • So, inline doesn’t necessarily make compiler create inline functions, but can also issue weak symbol that lets linker to choose one definition when linking

ABI⌗

ABI (application binary interface) is the platform-specific specification of how entities defined in one TU interact with entities defined in another TU

  • Compilers and Linkers must agree on the same ABI

For C++, this includes things like

  • Name mangling for functions
  • Name mangling for non-template types
  • Name mangling for template instantiations
  • The size, layout, and alignment of objects of any given type
  • How the bytes in an object’s binary representation are interpreted
  • Calling conventions for passing arguments to functions and receiving a returned object
  • Calling conventions for making system calls

On Linux, GCC and Clang use the Itanium ABI; On Windows, MSVC uses its own ABI

Name Mangling⌗

The C language does not provide overloading or namespaces

  • Given a C function whose declaration is void fubar (int),
  • The corresponding symbol name in object code is fubar
  • The symbol name will be the same no matter the number of parameters or their types