Instruction Selection

Instruction selection is fundamentally a pattern matching problem. The compiler's intermediate representation (IR) nodes are matched against a library of known patterns, where each pattern corresponds to a sequence of one or more target machine instructions.

• Tree/DAG Patterns: Operations are often represented as expression trees or directed acyclic graphs (DAGs). The selector finds the lowest-cost covering of the IR graph using patterns from the instruction set architecture (ISA).
• Cost Model: Each pattern has an associated cost (e.g., latency, code size). The selector aims for a minimum-cost cover, optimizing for performance or size.
• Declarative Specifications: Patterns are typically defined in a declarative language (like LLVM's TableGen), separating hardware description from compiler logic.

The process is intrinsically tied to the target NPU's microarchitecture. It translates generic operations into instructions that leverage specific hardware features.

• Intrinsic Functions: Maps high-level functions (e.g., a matrix multiplication) directly to vendor-provided, highly optimized hardware intrinsics or accelerator instructions.
• Exploiting Special Units: Identifies opportunities to use specialized functional units (e.g., tensor cores, vector ALUs, systolic arrays) instead of generic scalar operations.
• Legalization: Converts IR operations that have no direct hardware equivalent into a legal sequence of supported instructions (e.g., emulating a 64-bit integer multiply on a 32-bit unit).

Instruction selection is deeply interwoven with instruction scheduling and register allocation—often referred to as the backend triad. Decisions in one phase constrain the others.

• Integrated Approaches: Some compilers use integrated instruction selection and scheduling to make globally optimal decisions, evaluating the impact of pattern choices on pipeline stalls and register pressure.
• Virtual Registers: Selection typically operates on a representation using an unlimited number of virtual registers. The actual mapping to physical registers happens later.
• Peephole Optimization: After initial selection, a peephole optimization pass may further refine short instruction sequences, a form of localized, post-selection pattern matching.

Selecting instructions for Neural Processing Units presents unique challenges compared to general-purpose CPUs.

• Complex, Compound Instructions: NPU ISAs often include very complex, domain-specific instructions (e.g., a fused convolution-ReLU-batch norm). The selector must recognize large, composite IR subgraphs.
• Data Layout Constraints: Instructions may require data in specific memory layouts (e.g., NHWC vs. NCHW). Selection may need to trigger layout transformation passes.
• Mixed-Precision Support: Must correctly map to instructions that operate on FP32, FP16, BF16, INT8, or INT4 data types, inserting precision conversion ops where necessary.

Different algorithmic strategies are employed to solve the pattern matching and covering problem efficiently.

• Tree Parsing: For expression trees, efficient dynamic programming algorithms (like BURS) can find an optimal cover in linear time.
• DAG Covering: For DAGs, the problem is NP-complete, requiring heuristic approaches (e.g., greedy algorithms) or integer linear programming for small, critical sections.
• Retargetability: Frameworks like LLVM use a declarative TableGen backend description to generate the selector, making the compiler retargetable to new ISAs.

Instruction selection interacts directly with graph fusion strategies. What can be fused at a high level must ultimately be mappable to a single, efficient hardware instruction or kernel.

• Fusion Boundary Decision: The feasibility of fusing a group of operators may depend on whether the resulting compound operation has a direct, efficient instruction pattern. If not, it may be better to keep them separate.
• Vendor Library Calls: Often, the best 'instruction' for a fused pattern (like a fused attention block) is a call to a hand-optimized vendor library (e.g., cuDNN, TensorRT). The selector must recognize these large patterns.
• Custom Kernel Generation: For unsupported fused patterns, the selector's output feeds into a kernel code generator that produces custom CUDA/OpenCL/Metal code.

The core mechanism of instruction selection is pattern matching on a Directed Acyclic Graph (DAG) representation of the computation. The compiler's instruction set architecture (ISA) defines a library of patterns, each mapping a subgraph of IR operations to a sequence of target instructions (e.g., a fused multiply-add). The compiler searches for the optimal covering of the entire computation DAG with these patterns, minimizing a cost model (e.g., latency, power). This is often formalized as a tree parsing or graph covering problem.

Selecting the 'best' instruction sequence requires a cost model. For NPUs, this model evaluates alternatives based on:

• Cycle count and latency.
• Power consumption per operation.
• Register pressure and memory bandwidth usage.
• Utilization of specialized hardware units (e.g., tensor cores). Algorithms like dynamic programming (for tree-structured IR) or integer linear programming are used to find the optimal pattern cover. In practice, heuristics are often employed for large graphs.

Modern NPUs expose features that instruction selection must explicitly leverage:

• Fused Operations: Selecting a single FMA (Fused Multiply-Add) instruction over separate MUL and ADD instructions.
• SIMD/VLIW: Packing multiple scalar operations into a Single Instruction, Multiple Data (SIMD) or Very Long Instruction Word (VLIW) instruction.
• Specialized Units: Mapping matrix multiplications to tensor cores or transcendental functions (e.g., GELU) to dedicated non-linear function units.
• Memory Access Patterns: Selecting instructions with specific addressing modes or prefetch hints.

In the ML compiler pipeline (e.g., TVM, MLIR, XLA), instruction selection occurs after high-level graph optimizations (fusion, layout transforms) and before register allocation and instruction scheduling. It interacts closely with:

• Legalization: Converting unsupported high-level ops to a lower-level IR that the instruction selector can process.
• Intrinsic Mapping: Mapping compiler IR operations directly to vendor-provided hardware intrinsics (e.g., @llvm.npu.mma).
• Lowering: The final step of producing machine code from the selected instruction patterns.

Consider a matmul operation lowering for an NPU with a tensor core.

1. High-Level IR: %C = linalg.matmul ins(%A, %B) outs(%C)
2. Legalized/Lowered IR: A loop nest with load, store, and vector.contract operations.
3. Instruction Selection:
   • Pattern A: Cover the inner vector.contract with a sequence of standard SIMD mul and add instructions.
   • Pattern B: Cover the same subgraph with a single wmma (Warp Matrix Multiply-Accumulate) tensor core instruction.
4. Decision: The cost model selects Pattern B due to significantly higher throughput and lower energy per operation, generating the corresponding machine instruction.

Key challenges in NPU instruction selection include:

• Irregular ISAs: NPU ISAs are often proprietary, non-orthogonal, and densely packed, complicating pattern definition.
• Multi-Level Selection: Selection may happen at multiple IR levels (e.g., in MLIR, moving from linalg dialect to vector dialect to npu dialect).
• Retargetability: Using compiler generators like LLVM TableGen or MLIR's declarative rewrite rules to describe the ISA and generate the selector for new hardware.
• Profile-Guided Selection: Using runtime profiling data to choose between multiple valid instruction sequences for variable-latency operations.

The compiler phase that determines the execution order of selected machine instructions to maximize hardware utilization. It reorders instructions to hide pipeline latencies, manage functional unit contention, and respect data dependencies.

• Key Goal: Minimize pipeline stalls and bubbles.
• NPU Relevance: Critical for deeply pipelined and multi-issue NPU architectures where instruction-level parallelism (ILP) is a primary performance lever.
• Interaction with Selection: Scheduling occurs after or interleaved with selection; a poor schedule can negate the benefits of optimal instruction choice.

The process of mapping an unlimited number of virtual registers (from the IR) to a finite set of physical registers available on the target hardware. Its goal is to minimize costly spills to slower memory.

• Spill Code: Instructions generated to save/restore register values to/from memory when physical registers are exhausted.
• NPU Challenge: NPUs often have complex, hierarchical, or partitioned register files (e.g., vector vs. scalar registers). Allocation must be aware of these constraints.
• Co-design with Selection: The choice of instructions (e.g., a 3-operand vs. a 2-operand format) directly impacts register pressure and allocation complexity.

A low-level, local optimization pass that examines short sequences of already-selected machine instructions (a 'peephole') and replaces them with faster or shorter sequences.

• Scope: Works on the final instruction stream, often catching inefficiencies missed by higher-level passes.
• Common Examples:
  • Removing redundant moves (MOV R1, R1).
  • Using an increment instruction (INC) instead of add immediate (ADD ..., 1).
  • Fusing a compare-and-branch sequence into a single conditional branch instruction.
• Post-Selection Role: Acts as a final cleanup pass after instruction selection and scheduling.

A low-level intermediate representation that is instruction-set specific but still abstract (not yet binary). It represents the program using the target architecture's instructions, registers, and addressing modes, but before final binary encoding.

• Purpose: Serves as the input to the final code emission phase. Enables machine-specific optimizations (like peephole) in a structured way.
• Contrast with IR: While the compiler's main IR (e.g., LLVM IR, MLIR) is machine-independent, the Machine IR is tied to a specific NPU ISA (e.g., ARM SVE, NVIDIA PTX, custom NPU ISA).
• Output of Selection: The instruction selection phase typically produces the initial Machine IR.

The core algorithmic approach for instruction selection, often modeled as covering a Directed Acyclic Graph (DAG) representing the IR computation with patterns from the target instruction set.

• DAG Representation: IR operations form nodes, dataflow forms edges. This exposes common subexpressions naturally.
• Pattern Library: A declarative description of target machine instructions (e.g., in TD files for LLVM). Each pattern maps a subgraph of IR operations to a sequence of machine instructions.
• Algorithms: Use dynamic programming (e.g., tree parsing) or heuristic search to find the optimal/lowest-cost covering of the DAG with machine instruction patterns.

The process of mapping high-level IR operations to vendor-provided primitives—intrinsics (compiler-known functions) or SDK library calls—that map directly to highly optimized NPU hardware features.

• Hardware-Specific Functions: Examples include special activation functions (e.g., __sigmoid_fast), tensor core operations, or DMA copy engines.
• Compiler Support: The instruction selector must recognize IR patterns that correspond to these intrinsics and emit the appropriate call or intrinsic instruction.
• Performance Critical: Using these mapped calls is often far more efficient than emitting a sequence of generic instructions to achieve the same function.