Go Programming Language

When objects must exist outside the garbage-collected heap (e.g., part of the memory manager or when a P is unavailable), use one of these mechanisms:

• sysAlloc: Obtains memory directly from the OS in multiples of the system page size. Use sysFree to release it.
• persistentalloc: Combines small allocations into a single sysAlloc to reduce fragmentation. Note: These objects cannot be freed.
• fixalloc: A SLAB-style allocator for fixed-size objects. Memory can be freed but only reused by the same fixalloc pool for objects of the same type.

Safety Rules for Unmanaged Memory:

1. Mark types as not in heap by embedding internal/runtime/sys.NotInHeap.
2. If unmanaged memory contains heap pointers, they must be garbage collection roots (accessible via a global variable or added via runtime.markroot).
3. If memory is reused, heap pointers must be zero-initialized before becoming visible to the GC to avoid stale pointers.

The SSA (Static Single Assignment) backend is a core component of the Go compiler. It represents the program in a form where every value is defined exactly once, making it easier to perform optimizations like dead code elimination or nil check elimination.

Key abstractions include:

• Values: The basic building blocks. Each value has a unique ID, an operator (Op), a type, and arguments. Operators define the operation (e.g., OpAdd8 for 8-bit integer addition).
• Memory types: The memory type represents the global memory state. SSA uses this to ensure memory operations (like Store) are kept in the correct order by making subsequent operations depend on the previous memory state.
• Blocks: Represent basic blocks in the control flow graph. They contain a list of values and define how control flows (e.g., plain blocks, exit blocks, or if blocks with two successors).
• Functions: Represent a function declaration and its body, consisting of a name, a signature, and a list of blocks starting from an entry block.

// Example SSA representation of: var c uint8 = a + b
v4 = Add8 <uint8> v2 v3

// Example of memory dependency to prevent reordering:
v10 = Store <mem> {int} v6 v8 v1
v14 = Store <mem> {int} v7 v8 v10

Go defines the layout of composite types as a sequence of fields. The layout is determined by the size and alignment of each field, using the following logic:

• Field Offset: The offset of field $i$ is the alignment of the current field relative to the end of the previous field: offset(S, i) = align(offset(S, i-1) + sizeof(t_{i-1}), alignof(t_i)).
• Sequence Alignment: The alignment of a sequence is the maximum alignment of any of its fields.
• Sequence Size: The total size is the offset of the last field plus its size, rounded up to the sequence's alignment.

Specific Composite Type Layouts

• interface{} (Empty Interface): A sequence of 1. a pointer to the runtime type description and 2. an unsafe.Pointer data field.
• Other Interfaces: A sequence of 1. a pointer to the runtime "itab" (containing method pointers and data type) and 2. an unsafe.Pointer data field. Interfaces can be direct (value stored in data field) or indirect (pointer to value stored in data field). A direct interface is only possible if the value is a single pointer word.
• Array [N]T: A sequence of $N$ fields of type $T$.
• Slice []T: A sequence of:
  1. A *[cap]T pointer to the backing store.
  2. An int for len.
  3. An int for cap.
• String: A sequence of:
  1. A *[len]byte pointer to the backing store.
  2. An int for len.
• Struct: A sequence of its fields $t_1, ext{...}, t_M$, followed by a padding byte $t_P$ if sizeof(t_M) == 0 and any other field has a non-zero size. This prevents creating past-the-end pointers.

Best Practice for Assembly: User-written assembly should avoid manual layout calculations and instead use constants defined in go_asm.h.

The Go compiler (gc) operates in several logical phases, which can be broadly categorized into front-end, middle-end, and back-end:

1. Parsing: Tokenizes source code and constructs a syntax tree (cmd/compile/internal/syntax).
2. Type checking: Performs type analysis using the syntax tree (cmd/compile/internal/types2).
3. IR construction ("noding"): Converts syntax and type representations into the compiler's internal AST and types (cmd/compile/internal/ir, cmd/compile/internal/types, cmd/compile/internal/noder). This uses Unified IR.
4. Middle end: Performs optimizations on the IR, including dead code elimination, devirtualization, function inlining, and escape analysis (cmd/compile/internal/inline, cmd/compile/internal/devirtualize, cmd/compile/internal/escape).
5. Walk: Decomposes complex statements into simpler ones and desugars high-level constructs (like switch or map/channel operations) into primitive ones (cmd/compile/internal/walk).
6. Generic SSA: Converts IR into Static Single Assignment (SSA) form. This phase applies machine-independent optimizations like unneeded nil check removal and constant folding (cmd/compile/internal/ssa, cmd/compile/internal/ssagen).
7. Generating machine code: Lowers generic SSA values into machine-specific variants, performs final optimizations (register allocation, stack frame layout), and invokes the assembler to produce object files (cmd/compile/internal/ssa, cmd/internal/obj).

Go uses a register-based internal ABI where function calls pass arguments and results using a combination of machine registers and the stack.

Key Principles

• Preference for Registers: Arguments and results are preferentially passed in registers because they are faster than stack access.
• Stack Fallback: An argument or result is passed on the stack if:
  • It contains a non-trivial array (length > 1).
  • It does not fit entirely in the remaining available registers.
• Atomicity: Each argument or result is passed either entirely in registers or entirely on the stack; they are never split between the two.
• Spill Space: For arguments passed in registers, the caller reserves uninitialized "spill space" on the stack. This allows the callee to grow the stack or take the address of a register-based argument without complex reconstruction.

Stack Frame Layout

When using both registers and the stack, the stack frame (from lower to higher addresses) follows this order:

1. Stack-assigned receiver
2. Stack-assigned arguments
3. Pointer-alignment field
4. Stack-assigned results
5. Pointer-alignment field
6. Spill space for each register-assigned argument
7. Pointer-alignment field

// Example of a function signature and its assignment logic:
// func f(a1 uint8, a2 [2]uintptr, a3 uint8) (r1 struct { x uintptr; y [2]uintptr }, r2 string)
// 
// On a 64-bit architecture with registers R0-R9:
// - a1: Register R0
// - a2: Stack-assigned (due to array length > 1)
// - a3: Register R1
// - r1: Stack-assigned (due to struct containing array)
// - r2: Register-assigned (r2.base -> R0, r2.len -> R1)

The math/big package relies on several internal thresholds to switch between different algorithmic implementations for performance optimization. While these are internal to the package, understanding them helps explain how the package scales with input size:

• karatsubaThreshold: The input length $N$ at which the package switches from the $O(N^2)$ grade school multiplication algorithm to the $O(N^{1.58})$ Karatsuba algorithm.
• basicSqrThreshold: The threshold for squaring a number (z.Mul(x, x)). Below this, it uses grade school multiplication; above it, it uses a customized quadratic algorithm that avoids half the word-by-word multiplies.
• karatsubaSqrThreshold: The threshold beyond which a customized Karatsuba squaring algorithm (using three half-sized squarings) is used instead of standard Karatsuba multiplication.
• divRecursiveThreshold: The threshold determining when to switch from a recursive divide-and-conquer division algorithm to a traditional grade-school trial-and-error division.