IL Tree Walking

The IL tree walking framework is the backbone of every operation that must visit the complete IL graph: debug display, device code marking, IL serialization, and IL copying for template instantiation. The framework lives in il_walk.c (with entry-kind dispatch logic auto-generated from walk_entry.h). It provides a generic, callback-driven traversal engine consisting of two core functions: walk_file_scope_il (sub_60E4F0), which orchestrates the top-level iteration over all global entry-kind lists, and walk_entry_and_subtree (sub_604170), which recursively descends into a single entry's children according to the IL schema. Five global function-pointer slots allow each client to customize the walk's behavior without modifying the walker itself.

The framework follows a strict separation of traversal and action. The walker knows how to navigate the IL graph; the callbacks decide what to do at each node. This design enables the same walker to serve four fundamentally different purposes: pretty-printing, transitive-closure marking, pointer remapping during copy, and entry filtering during serialization.

Key Facts

Callback Slot Architecture

The five callback slots are stored as global function pointers. Before any walk, the caller saves all five values, installs its own set, and restores the originals on exit. This save/restore discipline makes walks re-entrant -- a callback can itself trigger a nested walk with different callbacks.

The pre_walk_check slot is the only one whose return value controls flow: nonzero means "already handled, skip this subtree." The keep-in-il pass uses this to avoid revisiting already-marked entries (preventing infinite recursion on cyclic references). The entry_replace slot is used during IL copy operations to translate pointers from the source IL region to the destination region.

Walk State Globals

In addition to the five callback slots, four state variables track the walker's context:

All four are saved and restored alongside the callback slots, making the entire walk context atomically swappable.

walk_file_scope_il (sub_60E4F0)

This is the central traversal entry point. Every operation that needs to visit the entire file-scope IL calls this function with its desired callbacks. It takes six arguments:

void walk_file_scope_il(
    entry_callback_t   a1,   // entry visitor (qword_126FB88)
    string_callback_t  a2,   // string visitor (qword_126FB80)
    entry_replace_t    a3,   // pointer remapper (qword_126FB70)
    entry_filter_t     a4,   // list filter (qword_126FB68)
    pre_walk_check_t   a5,   // pre-visit gate (qword_126FB78)
    int                a6    // walk_mode_flags (dword_126FB60)
);

Initialization

The function begins by saving all five callback slots and all four walk state variables, then installs the caller's values:

// Save current state
saved_entry_cb      = qword_126FB88;
saved_string_cb     = qword_126FB80;
saved_pre_walk      = qword_126FB78;
saved_entry_replace = qword_126FB70;
saved_entry_filter  = qword_126FB68;
saved_is_file_scope = dword_126FB5C;
saved_is_secondary  = dword_126FB58;
saved_il_region     = dword_106B644;
saved_mode_flags    = dword_126FB60;

// Install new callbacks
qword_126FB88 = a1;
qword_126FB80 = a2;
qword_126FB70 = a3;
qword_126FB68 = a4;
qword_126FB78 = a5;
dword_126FB60 = a6;
dword_126FB5C = 1;  // mark as file-scope walk

An assertion fires if pre_walk_check is NULL and the primary scope is in secondary IL (bit 1 of flags byte set):

if (!a5 && is_secondary)
    assert_fail("il_walk.c", 270, "walk_file_scope_il");

This prevents unguarded walks into secondary IL regions, which would produce incorrect results because secondary entries need canonical-entry delegation.

Walk Order

The function visits IL entries in a fixed, deterministic order. This order is significant for serialization (the IL binary format expects entries in this exact sequence) and for display (the --dump_il output follows this structure).

Phase 1: Primary scope (kind 23)

primary_scope = xmmword_126EB60[1];  // second qword of IL header

// If entry_replace callback exists, remap the scope pointer first
if (entry_replace)
    primary_scope = entry_replace(primary_scope, 23);

// Determine IL region flags from the scope's prefix byte
is_secondary_il = (*(primary_scope - 8) & 0x02) != 0;
current_il_region = ((*(primary_scope - 8) >> 2) ^ 1) & 1;

walk_entry_and_subtree(primary_scope, 23);

The scope entry (kind 23) is walked first because it is the root of the scope tree. Walking the scope recursively visits all nested scopes and their member lists.

Phase 2: Source file entries (kind 1)

for (entry = xmmword_126EB60[0]; entry; entry = entry->child_file) {
    if (entry_filter && !entry_filter(entry, 1))
        continue;  // filtered out
    walk_entry_and_subtree(entry, 1);
}

Source file entries form a linked list via offset +56 (child_file). Each entry holds the file name, full path, and name_as_written strings.

Phase 3: main_routine pointer and string entries

Before walking strings, the function remaps the main_routine pointer from the IL header:

// main_routine (qword_126EB70, IL header + 0x10)
if (entry_replace) {
    il_header.main_routine = entry_replace(il_header.main_routine, 11);
    // Also remap compiler_version through entry_replace
    compiler_version = entry_replace(compiler_version, 26);
}

Then two string entries from the IL header are walked as "other text" (kind 26):

// compiler_version (qword_126EB78, IL header + 0x18)
if (compiler_version) {
    if (trace_verbosity > 4)
        fprintf(s, "Walking IL tree, string entry kind = %s\n", "other text");
    if (string_callback)
        string_callback(compiler_version, 26, strlen(compiler_version) + 1);
}

// time_of_compilation (qword_126EB80, IL header + 0x20) -- same pattern
if (entry_replace)
    time_of_compilation = entry_replace(time_of_compilation, 26);
if (time_of_compilation) {
    if (string_callback)
        string_callback(time_of_compilation, 26, strlen(time_of_compilation) + 1);
}

Strings are walked with kind 26 (other_text) and the string callback receives the raw character pointer, the kind, and the length including the null terminator.

Phase 4: Orphaned entities list (kind 55)

for (entry = qword_126EBA0; entry; entry = entry->next) {
    if (entry_filter && !entry_filter(entry, 55))
        continue;
    walk_entry_and_subtree(entry, 55);
}

Kind 55 entries are orphaned entities -- declarations that lost their parent scope (e.g., after template instantiation cleanup). They are stored in a separate linked list headed at qword_126EBA0.

Phase 5: Global entry-kind lists (kinds 1--72)

The bulk of the walk iterates 45 global linked lists, one per entry kind. Each list head is stored at a fixed address in the 0x126E610--0x126EA80 range, with 16-byte spacing. The complete walk order, verified from the decompiled sub_60E4F0:

Note the gaps in the walk order: kinds 24-26 (base_class, string_text, other_text), 31-32 (local_static_variable_init, vla_dimension), 43-45 (asm_operand, asm_clobber, reserved), and 49-58 (element_position through hidden_name) are skipped. These entry kinds are either embedded inline within parent entries, accessed only through the recursive descent of walk_entry_and_subtree, or have no file-scope lists. Also note that kinds 59 and 61 appear out-of-order (61 before 59) -- this is verified in the binary.

For each non-empty list, the walk applies the entry_replace callback (if present) to each entry before descending, and follows the next pointer (at offset -16 in the raw allocation, which is the next_in_list link in the entry prefix).

Phase 6: Special trailing lists

Three additional lists are walked after the main kind-indexed sequence:

// seq_number_lookup entries (kind 64) at qword_126EBE8
for (entry = qword_126EBE8; entry; entry = entry->next) {
    if (entry_filter) ...
    walk_entry_and_subtree(entry, 64);
}

// External declarations (kind 6) at qword_126EBE0
// -- uses entry_filter with kind 6 and follows offset +104 links

// Kind 83 entries at qword_126EC00
for (entry = qword_126EC00; entry; entry = entry->next) {
    if (entry_filter) ...
    walk_entry_and_subtree(entry, 83);
}

Cleanup

After all phases complete, the function restores all saved state:

dword_126FB5C = saved_is_file_scope;
dword_126FB58 = saved_is_secondary;
dword_106B644 = saved_il_region;
dword_126FB60 = saved_mode_flags;
qword_126FB88 = saved_entry_cb;
qword_126FB80 = saved_string_cb;
qword_126FB78 = saved_pre_walk;
qword_126FB70 = saved_entry_replace;
qword_126FB68 = saved_entry_filter;

If tracing is active (dword_126EFC8), the function emits trace-leave via sub_48AFD0.

walk_entry_and_subtree (sub_604170)

This is the recursive engine -- the second-largest function in the entire cudafe++ binary at 7763 lines / 42KB of decompiled code. It takes an entry pointer and its kind, then recursively walks every child entry according to the IL schema.

Entry Protocol

Before descending into any entry, the function executes a two-path check:

while (true) {
    if (pre_walk_check != NULL) {
        // Callback path: delegate decision to the callback
        if (pre_walk_check(entry, entry_kind))
            return;  // callback says skip
    } else {
        // Default path: check flags
        flags = *(entry - 8);

        // If not file-scope walk and entry has file-scope bit: skip
        if (!is_file_scope_walk && (flags & 0x01))
            return;

        // If entry's il_region bit matches current_il_region: skip
        if (((flags & 0x04) != 0) == current_il_region)
            return;

        // Stamp the entry's il_region bit to match current region
        *(entry - 8) = (4 * (current_il_region & 1)) | (flags & 0xFB);
    }

    // Trace output at verbosity > 4
    if (trace_verbosity > 4)
        fprintf(s, "Walking IL tree, entry kind = %s\n",
                il_entry_kind_names[entry_kind]);

    // Dispatch on entry kind
    switch ((char)entry_kind) { ... }
}

The while(true) loop structure exists because certain cases (particularly linked-list tails) use continue to re-enter the check with a new entry, avoiding redundant function-call overhead for tail chains.

The default-path flags check serves two purposes:

1. Scope isolation: File-scope entries encountered during a routine-scope walk are skipped (they belong to the outer walk).
2. Region tracking: The current_il_region toggle prevents visiting the same entry twice within a single walk -- once stamped, an entry's bit 2 matches current_il_region, and the equality check causes the walker to skip it.

Entry Kind Dispatch

The giant switch covers all 85 entry kinds. Each case knows the exact layout of that entry type and recursively calls walk_entry_and_subtree on every child pointer. The three callbacks are invoked at appropriate points:

• entry_replace: Called on each child pointer before recursion, potentially replacing it with a remapped pointer.
• string_callback: Called on string fields (file names, identifier text), receiving the string pointer, kind 26, and byte length including null terminator.
• entry_filter: Called on linked-list head pointers, returning NULL to remove the entry from the list.

Coverage by Entry Kind

The following table shows the major entry kinds and what the walker visits for each:

Constant Entry Sub-Switch (Case 2)

The constant entry handler is one of the most complex cases. After walking two type references ([14], [15] as kind 6) and one expression ([16] as kind 13), it dispatches on the constant_kind byte at entry + 148:

// Walk shared fields first
walk(a1[14], 6);   // type
walk(a1[15], 6);   // declared_type
walk(a1[16], 13);  // associated expression

// Strip template info if walk_mode_flags set
if (walk_mode_flags)
    a1[17] = 0;

switch (constant_kind) {
    case 0:  /* ck_error */
    case 1:  /* ck_integer */
    case 3:  /* ck_float */
    case 5:  /* ck_imaginary */
    case 14: /* ck_void */
        break;  // leaf constants, no children

    case 2:  /* ck_string */
        // Walk string data at [20] as string_text (kind 25)
        // Length comes from [19] (not strlen -- may have embedded NULs)
        if (string_callback)
            string_callback(a1[20], 25, a1[19]);
        break;

    case 4:  /* ck_complex */
        walk(a1[19], 27);   // template_parameter (real/imaginary parts)
        break;

    case 6:  /* ck_address -- 7 sub-kinds at entry+152 */
        switch (address_sub_kind) {
            case 0: entry_replace(a1[20], 11);  break;  // routine
            case 1: entry_replace(a1[20], 7);   break;  // variable
            case 2: case 3:
                walk(a1[20], 2);                break;  // constant (recurse)
            case 4: entry_replace(a1[20], 6);   break;  // type (typeid)
            case 5: walk(a1[20], 6);            break;  // type (uuidof, recurse)
            case 6: entry_replace(a1[20], 12);  break;  // label
            default: error("bad address const kind");
        }
        // Then walk subobject_path list at [22] (kind 80)
        break;

    case 7:  /* ck_ptr_to_member */
        entry_replace(a1[19], 36);   // derivation_path
        walk(a1[20], 62);            // name_reference
        // Conditional: if a1[21] & 2, replace [22] as routine(11)
        //             else replace [22] as field(8)
        break;

    case 8:  /* ck_label_difference */
        walk(a1[20], 2);             // constant (recurse)
        break;

    case 9:  /* ck_dynamic_init */
        walk(a1[19], 30);            // dynamic_init entry
        break;

    case 10: /* ck_aggregate */
        // Linked list of constants at [19], each via offset +104
        for each constant in list: walk(entry, 2);
        entry_replace(a1[20], 2);    // tail constant
        break;

    case 11: /* ck_init_repeat */
        walk(a1[19], 2);            // repeated constant
        break;

    case 12: /* ck_template_param -- 15 sub-kinds at entry+152 */
        // Another sub-switch with cases 0-13 + default error
        break;

    case 13: /* ck_designator */
        walk(a1[20], 2);            // constant value
        break;

    case 15: /* ck_reflection */
        // Walk [20] with kind from entry+152 byte
        break;
}

The walk_mode_flags field zeroing (a1[17] = 0) strips template parameter constant info during IL binary output. This is the template-stripping behavior controlled by argument a6 of walk_file_scope_il.

String Entry Handling

String fields within entries are walked with three distinct string kind values:

The string_text kind (25) is special: its length comes from the enclosing constant entry's [19] field rather than strlen, because C/C++ string literals may contain embedded null bytes. All other string kinds use strlen(str) + 1.

Error Strings

The function contains diagnostic strings from walk_entry.h that fire on unexpected sub-kind values:

All three errors reference walk_entry.h as the source file and walk_entry_and_subtree as the function name, confirming the dispatch code is generated from the header file.

walk_routine_scope_il (sub_610200)

The routine-scope counterpart of walk_file_scope_il. It takes a routine index and walks that routine's scope chain:

void walk_routine_scope_il(int routine_index, ...) {
    // Same 5-callback + 4-state save/restore pattern
    // Trace: "walk_routine_scope_il"
    // Assert: il_walk.c, line 376

    dword_126FB5C = 0;  // NOT file-scope walk

    scope = qword_126EB90[routine_index];  // routine_scope_array
    while (scope) {
        walk_entry_and_subtree(scope, 23);
        if (entry_replace)
            scope = entry_replace(scope, 23);
        scope = scope->next;
    }
}

The key difference from walk_file_scope_il is that is_file_scope_walk is set to 0, which changes the entry protocol in walk_entry_and_subtree: entries with the file-scope bit set in their flags byte are skipped, because they belong to the file-scope IL and should not be processed during a routine-scope walk.

Callers and Use Cases

The walk framework serves four distinct purposes. Each caller installs a different callback configuration.

IL Display

The --dump_il debug output uses the walk framework with display_il_entry (sub_5F4930) as the entry callback:

// sub_5F76B0 (display_il_header)
walk_file_scope_il(
    display_il_entry,    // a1: entry callback = sub_5F4930
    NULL,                // a2: no string callback
    NULL,                // a3: no replace
    NULL,                // a4: no filter
    NULL,                // a5: no pre-walk check
    0                    // a6: no special flags
);

With all callbacks NULL except entry_callback, the walker visits every entry in walk order and calls display_il_entry on each, which dispatches on entry kind to print formatted field dumps. The pre_walk_check is NULL, so the default flags-based skip logic applies -- the current_il_region toggle prevents double-visiting.

Keep-in-IL Marking

The device code selection pass (mark_to_keep_in_il, sub_610420) installs the prune callback as pre_walk_check and NULL for everything else:

// sub_610420 (mark_to_keep_in_il)
qword_126FB88 = NULL;                    // no entry callback
qword_126FB80 = NULL;                    // no string callback
qword_126FB78 = prune_keep_in_il_walk;   // sub_617310
qword_126FB70 = NULL;                    // no replace
qword_126FB68 = NULL;                    // no filter

The prune_keep_in_il_walk callback (sub_617310) sets bit 7 (0x80) of each entry's flags byte and returns 1 for already-marked entries (preventing infinite recursion). The actual subtree walk is handled by a specialized copy of walk_entry_and_subtree (sub_6115E0, walk_tree_and_set_keep_in_il, 4649 lines) that directly sets the keep bit on every reachable child rather than using callbacks. See Keep-in-IL for the full mechanism.

IL Serialization

IL binary output (when IL_SHOULD_BE_WRITTEN_TO_FILE would be enabled, or for device IL output) uses all five callback slots:

• entry_callback: Records each entry's position in the output stream
• string_callback: Serializes string data with length prefix
• entry_replace: Translates IL pointers to output-stream offsets
• entry_filter: Skips entries that should not appear in the output (e.g., entries without keep_in_il for device IL)
• pre_walk_check: Prevents re-serializing entries already written

IL Copy (Template Instantiation)

When EDG instantiates a template, it copies the template's IL subtree into a new region. The copy operation uses entry_replace to remap all pointers from the source region to the destination:

• entry_replace: For each child pointer, allocates a new entry in the destination region, copies the source entry's contents, and returns the new pointer
• string_callback: Copies string data into the destination region
• pre_walk_check: Tracks which entries have already been copied (using the visited-set hash table at qword_126FB50)

Hash Table for Visited Set

The walk framework includes a visited-set hash table for cycles and deduplication:

The hash table is reset by sub_603B30 (clear_walk_hash_table) before each walk operation. It uses open addressing and is primarily employed during IL copy operations to map source entry pointers to their destination counterparts.

Helper Functions

Several helper functions support the walk framework:

Keep-in-IL Specialized Walkers

The keep-in-il pass uses parallel implementations of the walk framework that bypass the callback mechanism for performance:

These specialized walkers are structurally identical to walk_entry_and_subtree but replace callback invocations with direct *(entry - 8) |= 0x80 operations. They exist as separate functions rather than callback-based walks because the keep-in-il marking is performance-critical -- it runs on every CUDA compilation, and eliminating the function-pointer indirection across ~330 recursive calls provides measurable speedup.

Global Entry-Kind List Layout

The per-kind linked lists are stored in a contiguous global array starting at 0x126E600, with 16-byte stride. The formula 0x126E600 + kind * 0x10 gives the list head for most entry kinds up to kind 72. The complete walk order with all 51 lists (45 from Phase 5, 3 from Phase 6, plus orphaned entities, source files, and seq_number_lookup) is documented in the Phase 5 table above.

The three trailing lists (Phase 6) are stored outside the contiguous array at separate addresses in the IL header/footer region:

The external declarations list (qword_126EBE0) is notable: it walks entries as kind 6 (type) but uses a different linked-list strategy (offset +104 rather than the standard prefix next pointer). This is because the external declarations list is a secondary index over type entries that are also present in the main type list at qword_126E660.

Walk Order Diagram

walk_file_scope_il(callbacks...)
  |
  +-- [save 5 callbacks + 4 state vars]
  +-- [install caller's callbacks]
  |
  +-- Phase 1: walk_entry_and_subtree(primary_scope, 23)
  |     |
  |     +-- Recursively visits all nested scopes,
  |         their member lists (vars, routines, types),
  |         and all subtrees
  |
  +-- Phase 2: source_file list (kind 1)
  |     +-- for each file: walk(file, 1)
  |         +-- walks file_name, full_name, child files
  |
  +-- Phase 3: main_routine + string entries
  |     +-- entry_replace(main_routine, 11)
  |     +-- string_callback(compiler_version, 26, len)
  |     +-- string_callback(time_of_compilation, 26, len)
  |
  +-- Phase 4: orphaned_entities list (kind 55)
  |     +-- for each orphan: walk(orphan, 55)
  |
  +-- Phase 5: global lists (kinds 1, 2, 3, ..., 72)
  |     +-- for each kind:
  |           for each entry in list:
  |             entry_replace(entry, kind)
  |             walk(entry, kind)
  |
  +-- Phase 6: trailing lists (kinds 64, 6-ext, 83)
  |
  +-- [restore saved state]

Diagnostic Strings

Function Map

Cross-References

• IL Overview -- entry kind table, IL header structure
• IL Allocation -- entry prefix layout, flags byte definition
• Keep-in-IL -- device code marking pass using this framework
• IL Display -- display_il_entry callback
• Pipeline Overview -- when walks are triggered
• Device/Host Separation -- higher-level context