DenseMap, Symbol Table, and EDG Frontend Structures

The EDG 6.6 frontend layered on LLVM's DenseMap maintains its own declaration nodes, type nodes, and scope stack for C/C++/CUDA semantic analysis. This page documents the EDG-level structures that ride on top of the DenseMap. For the DenseMap implementation itself -- layout, hash function, probing, sentinel values, and growth policy -- see Hash Table and Collection Infrastructure.

The EDG symbol tables in this subsystem use the NVVM-layer sentinel pair (-8 / -16) and the pointer hash (ptr >> 9) ^ (ptr >> 4). See the sentinel reference table for other subsystems.

EDG Declaration Node Layout

The EDG 6.6 frontend represents every C/C++ declaration as a variable-length structure. The canonical declaration node layout was recovered from the top-level declarator parser sub_662DE0 and the declaration-specifier resolver sub_7C0F00.

Declaration Node (a_decl_node) -- 456+ bytes

decl_flags (+8) Bit Definitions

state_flags (+126) Bit Definitions

entity_kind (+80) Dispatch Values

Used by sub_860B80 and sub_7C0F00 phase 3:

Declaration Node Allocation

sub_84DCB0 allocates 152-byte declaration entries from a free-list at qword_4D03C68, with fallback to the global allocator sub_823970(152). The full node size table at qword_4B6D500 provides per-tag sizes for all 87 IL node types; the declaration tag (6) indexes into this table for memcpy during template instantiation.

EDG Type Node Layout

Type nodes are the central representation for C/C++ types throughout the EDG frontend. Two distinct layouts exist: the IL-level type node used by the tree walker (sub_7506E0) and the semantic type node used by the type comparison engine (sub_7386E0). The type translation system (sub_91AED0) bridges between these and LLVM types.

IL-Level Type Node (from sub_7506E0 tree walker)

The IL tree walker addresses fields as a1[N] (8-byte indexed), with byte-level sub-kind tags at specific offsets:

Semantic Type Node (from sub_7386E0 comparison engine)

EDG-to-LLVM Type Translation Node (from sub_918E50)

The type translation system reads a third view of the type node with offsets optimized for LLVM type construction:

type_kind Enumeration (semantic type comparison)

The full enumeration recovered from sub_7386E0:

EDG-to-LLVM Type Kind Encoding (byte at node+16)

Qualifier Word Values (node+18 & 0x7FFF)

Type Canonicalization -- sub_72EC50

Before any type comparison, both sides are canonicalized by stripping non-template typedef aliases:

fn edg_canonicalize_type(type) -> type:
    while type.type_kind == 2:               // tk_elaborated
        scope = type.payload_at_56
        if scope.elaborate_kind != 12:       // not typedef_name
            break
        if scope.elaborate_sub_kind != 1:    // not single-member typedef
            break
        if scope.class_flags & 0x10:         // has template specialization
            break
        type = sub_72E9A0(type)              // unwrap one layer
    return type

This peels through chains like typedef int MyInt; typedef MyInt YourInt; down to the fundamental type. Template specialization aliases are never unwrapped.

EDG Scope Stack

The scope stack is a global array of 776-byte entries, indexed by a scope depth counter. It represents the C++ scope nesting at parse time (file scope -> namespace -> class -> function -> block).

Global State

Scope Stack Entry Layout (776 bytes)

Each entry at qword_4F04C68[0] + 776 * index:

scope_kind Values

Push / Pop Operations

sub_854590(0)   // push_scope -- increments dword_4F04C64, initializes new entry
sub_854430()    // pop_scope  -- decrements dword_4F04C64, restores parent
sub_854AB0(...) // pop_declarator_scope (context-specific cleanup)
sub_854B40()    // push_declarator_scope (declarator-specific init)

The scope depth counter at qword_4F061C8 + 64 is bumped independently for declarator nesting depth tracking. Class scope depth lives at qword_4F061C8 + 81.

Scope Chain Traversal Algorithm

The declaration-specifier resolver sub_7C0F00 performs scope chain traversal to resolve qualified names. The algorithm was recovered from Phase 4 (lines 1197-1600) of that function.

Unqualified Name Lookup

fn lookup_unqualified(name, scope_index) -> entity:
    // Phase 2 of sub_7C0F00
    // Try each lookup strategy in priority order:

    result = sub_7D5DD0(name)                    // unqualified lookup in current scope
    if result:
        return result

    result = sub_7D2AC0(name, flags)             // lookup with specific flags
    if result:
        return result

    result = sub_7ACA80(name)                    // ADL / ambiguity resolution
    return result

Qualified Name Lookup (A::B::C)

The scope iteration loop at LABEL_282/283/285/288 walks the scope chain:

fn lookup_qualified(base_entity, remaining_name) -> entity:
    current = base_entity
    while true:
        // Check if "::" follows the current entity
        if current_token != TK_SCOPE_RESOLUTION:  // token 37
            return current

        consume_token()  // sub_7B8B50

        // Classify the current entity
        kind = current.entity_kind  // byte at +80
        switch kind:
            case 6:   // namespace
                result = sub_7D4A40(current, remaining_name)  // namespace lookup
            case 3:   // class
            case 19:  // class template
                result = sub_7D2AC0(current, remaining_name, MEMBER_FLAG)
            case 17:  // template
                result = sub_830940(current, remaining_name)  // class template lookup
            default:
                result = sub_7D4600(current, remaining_name)  // generic qualified lookup

        if !result:
            // Error: member not found in scope
            sub_6851C0(error_code, context)
            return null

        current = result

        // Check member access, visibility, redeclaration
        sub_8841F0(current, scope_entry)  // access check for C++ members

Self-Recursive Qualified Resolution

When the declaration-specifier resolver encounters a :: after resolving a name, it recurses into itself at sub_7C0F00(20, a2) where flags=20 decodes as:

• bit 2 (0x04) = nested declarator sub-parse context
• bit 4 (0x10) = restrict parse to type-specifiers only

This handles arbitrarily deep qualified names like A::B::C::D. Recursion depth is bounded by the nesting depth of the qualified name.

Scope Chain Walking for Declaration Resolution

sub_868D90 (ADL / instantiation lookup) walks the scope chain upward:

fn walk_scope_chain(start_index) -> entity:
    index = start_index
    while index >= 0:
        entry = scope_table_base + 776 * index
        // Check if this scope contains the target declaration
        // ... name lookup within the scope's name list ...

        // Move to parent scope
        index = entry.parent_scope_index  // at offset +552

Type Comparison Engine

sub_7386E0 implements structural type comparison for the EDG frontend. It performs a parallel tree walk over two type nodes, comparing them field-by-field with mode-dependent strictness.

Calling Convention

sub_7386E0(packed_pair: __int128, flags: int) -> bool
    packed_pair.low  = type_A pointer
    packed_pair.high = type_B pointer
    flags bits:
        0-1: cv_compare_mode (0=strict, 1=relaxed, 2=overload)
        2:   template_matching_mode
        5:   anonymous_class_structural_compare

Comparison Algorithm

fn compare_types(type_A, type_B, flags) -> bool:
    // 1. Null handling
    if both null: return true
    if either null: return false

    // 2. Canonicalize (strip non-template typedefs)
    type_A = sub_72EC50(type_A)
    type_B = sub_72EC50(type_B)

    // 3. Quick-reject on header bytes
    if type_A.type_kind != type_B.type_kind: return false
    if (type_A.cv_quals ^ type_B.cv_quals) & 0x43: return false  // const/volatile/restrict
    if (type_A.flags_1 ^ type_B.flags_1) & 0x04: return false

    // 4. Type-specific structural comparison
    switch type_A.type_kind:
        case 3 (class):
            if type_A.scope == type_B.scope: return true     // identity shortcut
            if unique_id_enabled:
                if scope_A.unique_id == scope_B.unique_id: return true
            if template_mode:
                return sub_89BAF0(...)  // template arg list compare
            if anonymous_mode && both_anonymous:
                return sub_739430(member_list_A, member_list_B)

        case 7 (member_pointer):
            // Compare: flags, class ptr, scope ptr, return type,
            // params, exception spec -- 6 sub-comparisons

        case 33 (using_decl) in overload mode:
            // Hash table lookup at qword_4D03BF8 for base class lists
            // Element-by-element comparison of 24-byte triples

        // ... 35 other cases ...

    // 5. Post-switch: declaration pointer compare
    if type_A.decl != type_B.decl:
        if !sub_8D97D0(type_A.decl, type_B.decl): return false
    return true

Helper Functions

Key Global: dword_4F07588 -- unique_id optimization

When set, enables O(1) identity comparison via the unique_id field at scope+32. This avoids recursive structural comparison for named classes and enums. The field is compared as a non-null integer; matching non-null values prove the two types refer to the same entity.

IL Tree Walker and Copier

Tree Walker -- sub_7506E0 (190KB, 7283 lines)

The generic IL tree walker visits every node in the EDG intermediate representation. It dispatches on 83 node kinds (1-86 with gaps at 24-26) using a massive switch statement.

Callback table at .bss 0x4F08014..0x4F08040:

Visit-mark protocol: Each node has a flag byte at node[-8]. Bit 2 tracks "visited in current pass" with polarity toggled per walk pass via dword_4D03B64. This avoids clearing visited marks between walks.

Linked-list traversal pattern (60+ lists walked):

for cursor = node.field; cursor; cursor = cursor.next:
    if list_node_rewrite_fn:
        cursor = list_node_rewrite_fn(cursor, child_kind)
    if cursor:
        walk_il_node(cursor, child_kind)
        cursor = node.field  // re-read (rewrite may have changed it)

Next-pointer stride varies by node kind: +0, +16, +24, +32, +56, +112, +120 bytes.

Tree Copier -- sub_766570 (148KB, 5187 lines)

The copier is driven by template instantiation (sub_8C5CD0 -> sub_8C4EC0 -> sub_8C2C50 -> sub_766570). It uses the walker's callback infrastructure:

• sub_8C38E0 = copy_ref callback: resolves pending copy destinations
• sub_8C3810 = copy_scope callback: resolves scope-level copies
• Node sizes from qword_4B6D500[tag] (87+ entries, one per IL node type)

Copy protocol using flag bits at node[-8]:

Copy destination stored at *(node - 24). When both bits 0 and 1 are set, sub_8C3650 forces the copy by allocating qword_4B6D500[tag] bytes and performing memcpy followed by pointer rewriting.

EDG-to-LLVM Type Translation System

Entry: sub_91AED0 -> sub_91AB30. Uses a worklist-driven fixed-point iteration.

Translation Context Object (at a1+160)

Fixed-Point Algorithm

fn translate_all_types(ctx, module):
    // Phase 1: iterate module members
    for member in module.member_list:
        sub_AA3700(member)  // gather initial flags

    // Phase 2: fixed-point iteration
    do:
        ordering = sub_919CD0(module)        // topological sort (10-level BFS)
        for type in ordering.reverse():
            sub_913880(ctx, type)            // invalidate stale cache entries
        for type in ordering.reverse():
            changed |= sub_9197C0(ctx, type) // process single declaration
    while changed

    // Phase 3: optional late fixup (byte_3C35480-gated)
    if optimization_enabled:
        do:
            changed = sub_917E30(ctx)
        while changed

    // Phase 4: cleanup
    sub_909590(ctx)

Bitmask for Scope-Tracking Types

The expression 0x100000100003FF >> (kind - 25) selects which type kinds in the range [25..78] require scope tracking during translation. This covers compound types, pointer types, and dependent types that carry CUDA address-space qualifiers.

Usage Across the Compiler

DenseMap instances appear at these known locations:

• NVVM context object: 8+ tables for IR node uniquing (opcodes 0x10..0x1F), plus sub-function tables for opcodes 0x04..0x15.
• SelectionDAG builder context: Map A (+120), Map B (+152), Set C (+184) for node deduplication and worklist.
• Per-node analysis: embedded DenseSet at +72 inside analysis structures created during DAG construction.
• Instruction constraint table: the global word_3F3E6C0 array is a flat table rather than a DenseMap, but the constraint emission functions use DenseMaps for lookup caching.
• EDG type translation: 5 distinct caches -- visited set, type cache, type-value map, scope table, and type index table.
• Base class comparison: qword_4D03BF8 hash table for overload-resolution base class triple lookup.

The consistency of the hash function, sentinel values, and growth policy across all instances is documented in Hash Table and Collection Infrastructure.

Cross-References

• IR Node Layout -- NVVM IR node structure and operand access
• DAG Node -- SelectionDAG builder that consumes DenseMap instances
• Pattern Database -- instruction selection patterns indexed by DenseMap
• Address Spaces -- CUDA memory space qualifier values
• Hash Infrastructure -- comprehensive DenseMap documentation
• EDG Frontend -- EDG tokenizer and keyword dispatch
• IRGen Types -- EDG-to-LLVM type translation detail

Function Map