Symbol Table

The symbol table's fundamental role is to bind a symbolic name (e.g., a variable or function name from source code) to its associated attributes. It stores this mapping as a key-value pair. Key attributes include:

• Type: Data type (int, float, struct) or function signature.
• Scope: Lexical scope where the symbol is valid (global, function-local, block).
• Memory Location: An address or offset, which may be a virtual address for a linker or a register/stack offset for a compiler.
• Linkage: Specifies visibility to other compilation units (e.g., static, extern).

Symbol tables implement the language's scoping rules. They track the active scope during compilation or linking, allowing for:

• Nested Scopes: Managing symbols in blocks, functions, and namespaces. A new scope often creates a new nested symbol table.
• Name Resolution: Determining which declaration a name refers to when the same name is used in different scopes (shadowing).
• Scope Exit Cleanup: Removing symbols that are no longer in scope, which is critical for memory efficiency in the compiler.

During compilation, the symbol table is the authoritative source for type information. It enables the compiler to perform semantic analysis by verifying that the use of a symbol matches its declaration.

• Consistency Checking: Ensures a variable is not used as both an integer and a function.
• Function Call Validation: Checks that the number and types of arguments in a function call match the function's signature stored in the table.
• Implicit Conversion Rules: Informs the compiler about necessary type promotions or casts.

For linkers, the symbol table within object files (e.g., the .symtab section in ELF format) is essential for resolving external references.

• Undefined Symbols: The linker collects a list of symbols declared but not defined in an object file.
• Defined Symbols: It finds the corresponding definition in other object files or libraries.
• Address Assignment: Once resolved, the linker patches (relocates) all references to the symbol with its final absolute or relative address in the executable.
• Duplicate Symbol Detection: Flags errors for multiple strong definitions of the same global symbol.

Symbol tables are stripped for production but are vital for debugging. Debuggers use debug symbol tables (e.g., .debug_info in DWARF format) to map machine code back to source code.

• Source Mapping: Correlates memory addresses to function names, variable names, and line numbers.
• Variable Inspection: Allows a debugger to look up the memory location and type of a variable by its source name.
• Stack Traces: Provides human-readable function names for call stack unwinding instead of raw addresses.

Advanced compilers use symbol table information for program optimization.

• Dead Code Elimination: Identifies functions or variables that are never referenced and can be removed.
• Inline Expansion: Uses type and linkage info to decide if a function call can be replaced with the function's body.
• Interprocedural Analysis: Tracks how symbols are passed between functions to enable optimizations across function boundaries.
• Constant Propagation: If a symbol's value is known to be constant, the compiler can propagate that value throughout the code.

The Executable and Linkable Format (ELF) is the standard binary file format on Unix-like systems. It is organized into contiguous segments called sections, each holding specific data types critical for linking and execution. Key symbol-related sections include:

• .symtab: The main symbol table containing definitions and references.
• .strtab: The string table holding the actual symbol names referenced by .symtab.
• .dynsym: The dynamic symbol table for runtime linking.
• .text: Contains executable code (functions).
• .data & .bss: Hold initialized and uninitialized static/global variables. The linker uses these sections to resolve symbols and create the final executable or shared library image for the target NPU.

A linker script is a configuration file written in the linker's command language that provides explicit, low-level control over the memory layout of the final output binary. It directs the linker on:

• The memory regions available on the target NPU (e.g., SRAM, DRAM, ROM).
• Where to place specific input sections (like .text, .data, .symtab) into these regions.
• Defining symbol addresses and managing overlays.
• Setting the entry point of the program. For embedded NPU targets with constrained or non-uniform memory hierarchies, linker scripts are essential for ensuring code and data reside in optimal memory types (fast vs. slow, volatile vs. persistent) to meet performance and power constraints.

The Application Binary Interface is a low-level contract between separately compiled modules (object files, libraries) and the operating system. It defines the rules for interoperability at the machine code level. For symbol tables and linking, the ABI governs:

• Calling Convention: How functions pass arguments, return values, and manage registers/stack.
• Data Representation: Size, alignment, and layout of data types (structs).
• Symbol Mangling: How function names are encoded ("mangled") in the symbol table to represent namespaces and overloads in languages like C++.
• Dynamic Linking Semantics: How symbols are resolved at load time from shared libraries. A stable, well-defined ABI is crucial for linking vendor NPU libraries with user code, ensuring binary compatibility.

Relocation is the process performed by the linker (static relocation) or dynamic loader (runtime relocation) of patching addresses in the machine code and data sections. When a compiler generates an object file, it leaves placeholders for addresses of external symbols (e.g., calls to a function in a vendor SDK). The object file's relocation sections (e.g., .rela.text) contain records specifying:

• The location in the code/data that needs patching.
• The symbol whose address is needed.
• The type of relocation calculation (e.g., relative jump, absolute address). The linker resolves the symbol's final address from the combined symbol tables and then performs the relocation, writing the correct address into the binary. This is fundamental for creating a working executable from multiple components.

A vendor toolchain is a suite of software tools provided by a hardware vendor (e.g., NVIDIA, AMD, Intel, Qualcomm) specifically for developing applications for their accelerator, such as an NPU. It typically includes:

• A cross-compiler (often a modified GCC or LLVM/Clang) that targets the vendor's ISA.
• An assembler and linker that understand the vendor's object file formats and memory models.
• Libraries (static and dynamic) containing optimized kernels and intrinsics.
• Debuggers and profilers that can interpret the vendor-specific symbol table and debugging information. The toolchain is responsible for generating the final binary, including its symbol table, that can be executed by the vendor's runtime and driver stack on the target NPU hardware.

A cross-compiler is a compiler that runs on one system architecture (the host, e.g., x86-64) but generates executable code for a different architecture (the target, e.g., an ARM-based NPU). In the context of NPU development:

• It translates high-level code (C/C++) and vendor intrinsics into the NPU's vendor ISA.
• It generates object files containing the target's machine code and a symbol table in the target's format (e.g., ELF for the NPU).
• It is a core component of the vendor toolchain. Using a cross-compiler allows developers to build NPU binaries on powerful development machines without needing the actual NPU hardware for compilation, streamlining the development and CI/CD pipeline for embedded AI.