SelectionDAG Node Structure

The SelectionDAG (SDNode) is the central data structure in cicc's code generation backend. Nodes represent operations in the target-independent DAG before instruction selection lowers them to machine instructions. The DAG builder (sub_2081F00, 267KB) converts LLVM IR into an initial DAG by visiting each IR instruction through a dispatch chain rooted at sub_2065D30. Nodes are deduplicated via a CSE hash table (sub_F4CEE0, 41KB) and allocated from a bump allocator embedded in the builder context object. The complete SelectionDAG pipeline then runs type legalization, operation legalization, DAG combining, and instruction selection over this graph before emitting PTX machine instructions.

SDNode Layout (104 Bytes, Two Views)

Every SDNode is allocated as exactly 104 bytes, hardcoded in sub_163D530. After allocation, all fields are zeroed. Two complementary views of the layout have been recovered: the "allocator view" from the zeroing pattern in sub_163D530, and the "accessor view" from field access patterns across the combiner (sub_F20C20), legalization (sub_1FFB890), and known-bits engine (sub_33D4EF0).

Allocator View (from sub_163D530)

The raw 104 bytes are zeroed via a combination of qword and dword stores:

qw[0..5] = 0, dw[6] = 0, qw[8..10] = 0, dw[11] = 0, byte[96] = 0

The statistics counter at context offset +96 is incremented by 104 for every allocation: *(_QWORD *)(v4 + 96) += 104LL.

Accessor View (Composite from Combiner, Legalizer, KnownBits)

The following table reconciles field accesses across sub_F20C20 (DAG combiner visitor), sub_1FFB890 (LegalizeOp), sub_33D4EF0 (computeKnownBits, 114KB), and sub_1FCE100 (LegalizeOp dispatcher):

Note on dual access patterns. The combiner accesses opcodes at N+24 as a 4-byte field with flags, while the legalizer reads *(uint16_t*)(node+24) for a clean 16-bit opcode. The KnownBits engine (sub_33D4EF0) accesses fields at offsets up to +112, confirming that ConstantSDNode and MemSDNode subclasses extend beyond the base 104-byte allocation. These extended nodes are allocated via sub_BD2DA0 (80 bytes for lightweight variants) or sub_22077B0 (128 bytes for MemSDNode), while the base SDNode remains 104 bytes.

Operand Storage

Operands are stored in a contiguous array of SDUse structures. Two storage modes exist:

Mode A -- backward inline (common for small operand counts). Operands are stored before the node in memory, growing toward lower addresses:

operand[i] = *(qword*)(N + 32*(i - NumOps))
// or equivalently: N - 32*NumOps = first operand address

This 32-byte operand stride is confirmed across sub_F3D570, sub_F20C20, and sub_F5A610.

Mode B -- indirect pointer (when node_flags_byte bit 6 is set). An 8-byte pointer at N-8 points to a separately allocated operand array:

if (*(byte*)(N+7) & 0x40):
    operand_base = *(qword*)(N - 8)

The SDUse structure (each operand slot) has a 40-byte stride in the legalizer view (sub_1FFB890) and a 32-byte stride in the combiner view. The 40-byte stride includes use-chain forward/backward pointers:

Use-list traversal functions: sub_B43C20 (add to use list), sub_B43D60 (remove from use list).

SDValue

An SDValue is a lightweight {SDNode*, unsigned ResNo} pair identifying a specific result of a specific DAG node. In the decompiled code, SDValues appear as 16-byte pairs at various points:

struct SDValue {
    SDNode *Node;     // +0: pointer to the defining node
    uint32_t ResNo;   // +8: which result of that node (0-based)
};

SDValues are passed by value in registers (packed into __m128i in many decompiled signatures) and stored in operand arrays. The SDUse structure wraps an SDValue with use-chain linkage for the def-use graph.

SelectionDAG Builder Context

The builder context is the a1/v4 parameter to sub_163D530. It holds the function being compiled, target information, the bump allocator state, and several DenseMaps for node deduplication.

Embedded DenseMaps

Three DenseMap/DenseSet instances are embedded inline in the context for node deduplication and worklist tracking. All use the standard DenseMap infrastructure with NVVM-layer sentinels (-8 / -16); see Hash Table and Collection Infrastructure for the hash function, probing strategy, and growth policy.

Map A (CSE node mapping) at offsets +120..+148:

Map B (secondary set) at offsets +152..+176, same layout.

Set C (worklist) at offsets +184..+208, same layout.

Total minimum context size: 212 bytes.

Map A uses 16-byte bucket stride (key + value pairs), confirmed by the decompiled access pattern:

v30 = (_QWORD *)(v28 + 16LL * v29);   // 16-byte stride
*v30 = v11;                             // key
v30[1] = v19;                           // value

DAG Builder Algorithm (SelectionDAGBuilder)

The SelectionDAGBuilder converts LLVM IR to an initial SelectionDAG. The main entry is sub_2081F00 (267KB, ~9,000 lines), with the visit dispatcher at sub_2065D30 (25KB). The builder processes one basic block at a time, walking the IR instruction list and emitting corresponding SDNode subgraphs.

Entry and Dispatch

sub_2081F00(SelectionDAGBuilder *this, BasicBlock *BB):
    // this+552 = SelectionDAG pointer
    // this+560 = DataLayout pointer
    // Walk BB instruction list via linked list at BB+40/+48
    for each instruction I in BB:
        sub_2065D30(this, I)     // main visit dispatch

The visit dispatcher (sub_2065D30) contains a DenseMap for node deduplication (hash function: (key >> 9) ^ (key >> 4)). It switches on the IR opcode and delegates to per-instruction visitors:

Chain Management

Every memory-touching SDNode carries a chain operand (token type) that enforces memory ordering. The chain is a linked sequence of token-typed SDValues threading through all memory operations in program order.

Chain creation. The builder maintains a "current chain" (PendingChain) that is updated after every memory operation. When a load or store is emitted, the current chain becomes its chain input, and the node's token result becomes the new current chain.

TokenFactor merging. When multiple independent memory operations can be reordered (e.g., independent loads), the builder creates a TokenFactor (opcode 2/55 depending on context) node that merges multiple chains into one:

// sub_F429C0: merge node creation
TokenFactor = getNode(ISD::TokenFactor, dl, MVT::Other, chains[])

Chain handling utilities in the builder:

• sub_20993A0 (11KB) -- chain/token helper for load/store sequences
• sub_2098400 -- chain token node creator
• sub_20989A0 -- memory scheduling chain builder
• sub_F6C1B0 (16KB) -- chain management in combining, uses sub_B46970 (isTokenFactor)

Glue (flag) chains. Certain node pairs must be scheduled adjacently (e.g., CopyToReg + CALL). These use a "glue" value type (MVT::Glue) as an additional operand/result. The call lowering in sub_3040BF0 threads glue through the entire call sequence: CallSeqBegin -> DeclareParam* -> Store* -> CallProto -> CallStart -> LoadRetParam* -> CallSeqEnd.

Per-Node Analysis Structure

During DAG construction, sub_163D530 creates per-node analysis objects (accessed via v381) with the following layout:

Operations: sub_163BE40(v381, ptr) inserts into the +8 array; sub_163BBF0(context, key) looks up the analysis structure for a node in the context's DenseMap.

CSE (Common Subexpression Elimination) Hash Table

The getNode() family of functions deduplicates SDNodes via a CSE hash table. The primary implementation is sub_F4CEE0 (41KB):

sub_F4CEE0(SelectionDAG *DAG, unsigned Opcode, SDVTList VTs, SDValue *Ops, unsigned NumOps):
    // 1. Compute profile hash via sub_F4B360 (SDNode::Profile)
    //    Hash combines: opcode, VTs, all operand node pointers
    // 2. Lookup in CSE hash table:
    //    hash = ((profile >> 4) ^ (profile >> 9)) & (capacity - 1)
    //    Quadratic probing: step 1, 2, 3, ...
    //    Sentinels: -4096 (empty), -8192 (tombstone)
    // 3. If found: return existing node
    // 4. If not found:
    //    Allocate via sub_BD2C40 (bump allocator)
    //    Initialize via sub_B44260 (SDNode constructor)
    //    Insert into hash table
    //    Add to AllNodes list (global sentinel: qword_4F81430)
    //    Return new node

Node builder variants handle different operand counts:

• sub_F49030 (38KB) -- complex node construction with operand/result type setup
• sub_F429C0 (34KB) -- merge/TokenFactor/indexed node creation
• sub_F44160 (22KB) -- CSE rebuild after modification
• sub_F40FD0 (16KB) -- node construction with chain initialization

The AllNodes list (qword_4F81430) is a doubly-linked intrusive list of all SDNodes in the current DAG, used for iteration during combining and legalization passes.

NVPTX-Specific Node Types (NVPTXISD)

NVPTX target-specific ISD opcodes begin at ISD::BUILTIN_OP_END = 0x1DC9 (confirmed by sub_2095B00 delegation threshold for getTargetNodeName()). In the decompiled code, target opcodes are referenced by small integers (the NVPTXISD enum value minus BUILTIN_OP_END). The following table consolidates all NVPTXISD opcodes discovered across sub_3040BF0, sub_32E3060, sub_33B0210, and the legalization infrastructure:

Call ABI Nodes

Memory / Vector Nodes

Math / Rounding-Mode Nodes

Address Space / Miscellaneous Nodes

Atomic Opcodes (from sub_20BED60)

DAG Legalization Flow

After the initial DAG is built, three legalization phases transform it into a form the NVPTX backend can select:

Phase 1: Type Legalization (sub_20019C0, 348KB)

The DAGTypeLegalizer iterates to fixpoint. For each node, it reads the result/operand types and checks the legality table at TLI + 259 * VT + opcode + 2422. If illegal, it applies one of: promote, expand, soften, scalarize, or split-vector. The worklist iterates until no node has an illegal type.

NVPTX legal vector types are extremely limited (only v2f16, v2bf16, v2i16, v4i8 -- all packing into 32-bit registers via Int32HalfRegs). This means virtually all LLVM-IR vector operations pass through the split/scalarize paths.

Type legalization workers:

• sub_201E5F0 (81KB) -- promote/expand secondary dispatch (441 case labels, 6 switches)
• sub_201BB90 (75KB) -- ExpandIntegerResult (632 case labels)
• sub_2029C10 -- SplitVectorResult dispatcher (reads opcode at node+24)
• sub_202E5A0 -- SplitVectorOperand dispatcher
• sub_2036110 -- ScalarizeVectorResult
• sub_2035F80 -- ScalarizeVectorOperand

Phase 2: Operation Legalization (sub_1FFB890, 169KB)

After types are legal, the operation legalizer checks whether each operation at its now-legal type is supported. The action lookup:

action = *(uint8_t*)(TLI + 259*VT + opcode + 2422)

Actions dispatch through a five-way switch:

Custom lowering invokes NVPTXTargetLowering::LowerOperation() (sub_32E3060, 111KB) through the vtable. This is where all NVPTX-specific operation lowering happens: BUILD_VECTOR splat detection, VECTOR_SHUFFLE three-level lowering, EXTRACT_VECTOR_ELT three-path dispatch, and the .param-space calling convention.

Additional action tables:

• Second table at TLI + opcode + 2681 -- for BSWAP/CTLZ/CTTZ/BITREVERSE (opcodes 43--45, 199)
• Third table at TLI + opcode + 3976 -- for FSINCOS (opcode 211)
• Fourth table at TLI + 18112 -- packed nibble format for FP_TO_SINT/FP_TO_UINT/SELECT_CC, indexed by (VT_id >> 3) + 15 * condcode_type

Phase 3: DAG Combining (Three Passes)

DAG combining runs after each legalization phase. The orchestrator (sub_F681E0, 65KB) manages a worklist of SDNodes and calls the per-node visitor (sub_F20C20, 64KB) for each. The visitor implements a six-phase combine algorithm:

1. Opcode-specific combine via sub_100E380 -- target-independent pattern matching
2. Known-bits narrowing -- for constants, calls sub_11A3F30 (computeKnownBits/SimplifyDemandedBits) and narrows if fewer bits demanded
3. Operand type-narrowing loop -- walks all operands, promotes/truncates to legal types, creates SIGN_EXTEND/TRUNCATE casts
4. All-constant-operand fold -- 4x-unrolled check via sub_1028510 (ConstantFold)
5. Division-by-constant strength reduction -- shift+mask replacement for power-of-2 divisors
6. Vector stride / reassociation -- sub_F15770 (shift-fold), sub_F17ED0 (stride patterns)

NVPTX-specific combines run as a post-legalize pass:

• sub_33C0CA0 (62KB) -- PerformDAGCombine, the NVPTX target hook
• sub_32EC4F0 (92KB) -- post-legalize combine
• sub_3425710 (142KB) -- the NVIDIA DAGCombiner with internal "COVERED"/"INCLUDED" debug tracing strings (not present in upstream LLVM)

The worklist uses the same DenseMap infrastructure as the builder context, with the hash at DAG+2072 (capacity at DAG+2088, count at DAG+2080). Node replacement goes through sub_F162A0 (CombineTo/ReplaceAllUsesWith), which walks the use-list, hashes each user into the worklist map, then calls sub_BD84D0 for the actual use-chain splice.

Bump Allocator

The builder context uses a slab-based bump allocator identical to the one used for NVVM IR nodes:

• Slab growth: 4096 << (slab_index >> 7) -- exponential, capped at 4TB.
• Alignment: 8 bytes.
• No per-node free: entire slabs are released when the DAG is destroyed.
• Overflow: allocates a new slab via malloc().

Since every base SDNode is exactly 104 bytes (13 qwords), a single 4096-byte initial slab holds approximately 39 nodes before overflow triggers slab growth. Extended node types (ConstantSDNode, MemSDNode) may be larger and are allocated via separate paths:

• sub_BD2C40 -- standard SDNode allocation (bump allocator)
• sub_BD2DA0 -- SDNode allocation variant (80 bytes, for lightweight nodes)
• sub_22077B0 -- operator new[] (128 bytes, for MemSDNode with chain/alignment fields)

Basic Block Iteration

The builder iterates over the function's basic blocks via a linked list rooted at a2 + 72 (the function parameter). Each list node embeds the data pointer at offset -24 from the node:

bb_data = node_ptr - 24

Within each basic block, instructions are iterated via an inner list:

• Inner list sentinel at bb_data + 40
• Inner list head at bb_data + 48

This matches the LLVM ilist intrusive linked list pattern where the list hook is embedded at a fixed offset within the contained object.

Differences from Upstream LLVM

Function Map

Cross-References

• SelectionDAG & Instruction Selection -- pipeline overview, NVPTX lowering, combine detail
• Type Legalization -- 348KB type legalizer deep-dive
• ISel Patterns -- instruction selection pattern database
• Register Classes -- NVPTX register class constraints
• Address Spaces -- address space encoding
• Hash Infrastructure -- universal DenseMap documentation
• IR Node Structure -- NVVM IR node layout (pre-SelectionDAG)
• Pattern Database -- ISel pattern constraint classes