How LLVM Target-Independent Code Generation Works: SelectionDAG vs GlobalISel

LLVM transforms architecture-neutral LLVM-IR into machine code through two complementary pipelines: the legacy SelectionDAG framework, which builds and legalizes a directed acyclic graph of SDNode objects, and the modern GlobalISel infrastructure, which operates on SSA-based Machine IR using a TableGen-driven selector.

LLVM's code generation strategy in the llvm/llvm-project repository decouples target-specific instruction selection from high-level optimization. This target-independent approach allows backend developers to support new architectures without rewriting the entire compilation pipeline. The system achieves this abstraction through two distinct but coexisting infrastructures: the mature SelectionDAG and the newer GlobalISel.

Overview of LLVM Code Generation Pipelines

LLVM provides two primary paths from IR to machine code:

• SelectionDAG (Legacy): Constructs a graph-based representation (SelectionDAG) of the program using generic ISD::* opcodes. The DAG undergoes type legalization, DAG combining, instruction selection, and scheduling before emission.
• GlobalISel (Modern): Translates LLVM-IR directly into generic Machine IR (MIR) using G_* opcodes. A legalizer rewrites illegal operations, and a match-table selector replaces generic instructions with target-specific opcodes.

Both pipelines rely on target-specific hooks—TargetLowering and TargetInstrInfo—to determine legality and selection rules, ensuring that architecture-specific details remain encapsulated while the core algorithm stays generic.

The SelectionDAG Pipeline (Legacy)

The SelectionDAG infrastructure represents the classic LLVM code generation path. According to the source code in llvm/lib/CodeGen/SelectionDAG/, this pipeline processes functions through six distinct phases.

DAG Construction with SelectionDAGBuilder

The process begins in SelectionDAGBuilder.cpp, where the SelectionDAGBuilder class traverses LLVM-IR basic blocks. For each instruction, it creates SDNode objects and assembles them into a SelectionDAG—a directed acyclic graph where edges represent data flow through SDValue objects.

// Conceptual flow in SelectionDAGBuilder.cpp
llvm::SelectionDAGBuilder Builder(DAG, ...);
Builder.buildFunction(MF.getFunction());

This builder emits only target-independent opcodes (the ISD::* namespace), ensuring that subsequent phases operate without target-specific knowledge.

Legalization and Type Conversion

Once constructed, the DAG often contains operations or types illegal for the target architecture. In SelectionDAGISel.cpp (lines 10000-10700), the LegalizeTypes() and LegalizeVectors() methods transform these nodes into legal equivalents. For example, a 64-bit integer on a 32-bit target becomes a pair of 32-bit values with appropriate extension or truncation nodes (G_ANYEXT, G_TRUNC).

DAG Combining Optimizations

Before and after legalization, the pipeline runs several DAG combiner passes to simplify the graph. The source code around lines 84000-84200 in SelectionDAGISel.cpp shows calls to Combine methods that perform pattern-matching optimizations. These passes shrink the graph, expose additional instruction selection opportunities, and eliminate redundant operations without target-specific knowledge.

Instruction Selection

The core transformation occurs in DoInstructionSelection(), implemented around lines 13000-13300 in SelectionDAGISel.cpp. This method walks the DAG in topological order using a while (ISelPosition != CurDAG->allnodes_begin()) loop, replacing each generic SDNode with one or more target-specific MachineInstr objects. The selection logic queries TargetLowering hooks to determine the appropriate machine opcode for each generic operation.

Scheduling and Emission

After selection, the pipeline creates a scheduler via CreateScheduler() (line 16200 in SelectionDAGISel.cpp). The ScheduleDAGSDNodes implementation orders instructions while respecting data dependencies, register pressure limits, and target-specific heuristics. Finally, the scheduled instruction list populates the MachineFunction, completing the target-independent transformation.

SelectionDAG Implementation Example

The following code illustrates how a custom backend pass might invoke the SelectionDAG pipeline:

// ExamplePass.cpp – MachineFunctionPass running the legacy DAG
struct ExamplePass : public llvm::MachineFunctionPass {
  static char ID;
  ExamplePass() : MachineFunctionPass(ID) {}

  bool runOnMachineFunction(llvm::MachineFunction &MF) override {
    llvm::TargetMachine &TM = *MF.getTarget();
    llvm::SelectionDAG DAG(TM, llvm::CodeGenOptLevel::Default);
    llvm::SelectionDAGBuilder Builder(DAG, /*FuncInfo=*/nullptr,
                                      /*SwiftError=*/nullptr,
                                      llvm::CodeGenOptLevel::Default);
    Builder.init(/*GFI=*/nullptr, /*AA=*/nullptr, /*AC=*/nullptr,
                 /*LibInfo=*/nullptr, /*TTI=*/nullptr,
                 /*UA=*/nullptr, /*PSI=*/nullptr, /*BFI=*/nullptr,
                 /*MMI=*/nullptr, /*FnVarLocs=*/nullptr);
    Builder.buildFunction(MF.getFunction());

    // Run DAG pipeline: legalize, combine, select, schedule
    llvm::SelectionDAGISel ISel(TM, llvm::CodeGenOptLevel::Default);
    ISel.setMF(&MF);
    ISel.runOnMachineFunction(MF);
    return true;
  }
};

The GlobalISel Pipeline (Modern)

GlobalISel replaces the heavyweight DAG with a lighter, SSA-based representation that targets find easier to implement and debug. The pipeline lives in llvm/lib/CodeGen/GlobalISel/ and operates on Machine IR rather than a custom graph structure.

MIR Generation and Generic Opcodes

The front-end lowers LLVM-IR to generic MIR using MachineIRBuilder helpers. This representation uses G_* opcodes (such as G_ADD or G_LOAD) that are target-independent but operate on MIR registers rather than LLVM values.

The Legalizer and LegalizerHelper

The LegalizerHelper class, defined in LegalizerHelper.h (line 95 entry point legalizeInstrStep()), examines each generic instruction. If an operation or its type is illegal for the current target, the helper rewrites it into legal forms—widening scalars, splitting vectors, or emitting library calls. Targets provide *LegalizerInfo subclasses (e.g., X86LegalizerInfo.h) that define transformation rules via tables.

TableGen-Driven Instruction Selection

After legalization, the InstructionSelector class (defined in InstructionSelector.h at line 28) processes the MIR. Unlike SelectionDAG's C++ selection logic, GlobalISel uses match-tables generated from TableGen definitions (*.td files). The abstract select() method iterates through these tables to replace generic G_* opcodes with target-specific TargetOpcode::* values.

Target-Specific Implementation

Targets subclass InstructionSelector to provide custom logic beyond generated tables. For example, X86InstructionSelector.cpp implements fallback patterns for X86-specific optimizations that cannot be expressed declaratively in TableGen.

GlobalISel Implementation Examples

Custom Instruction Selector:

// X86InstructionSelector.cpp – target-specific selector
class X86InstructionSelector : public llvm::InstructionSelector {
public:
  bool select(llvm::MachineInstr &MI) override {
    // Generated match table handles standard cases
    if (InstructionSelector::select(MI))
      return true;

    // Custom fallback for non-TableGen patterns
    if (MI.getOpcode() == llvm::TargetOpcode::G_ADD) {
      llvm::MachineInstrBuilder MIB = llvm::BuildMI(
          *MI.getParent(), MI, MI.getDebugLoc(),
          getX86InstrInfo()->get(llvm::X86::ADD));
      MIB.addReg(MI.getOperand(0).getReg())
         .addReg(MI.getOperand(1).getReg());
      MI.eraseFromParent();
      return true;
    }
    return false;
  }
};

Standalone Legalizer Pass:

// LegalizePass.cpp – invoking the GlobalISel legalizer
struct LegalizePass : public llvm::MachineFunctionPass {
  static char ID;
  LegalizePass() : MachineFunctionPass(ID) {}

  bool runOnMachineFunction(llvm::MachineFunction &MF) override {
    llvm::GISelChangeObserver Observer;
    llvm::MachineIRBuilder MIRBuilder(MF);
    llvm::LegalizerHelper Helper(MF, Observer, MIRBuilder,
                                 &MF.getSubtarget().getLegalizerInfo());

    for (auto &MBB : MF) {
      for (auto &MI : llvm::make_early_inc_range(MBB)) {
        if (Helper.legalizeInstrStep(MI, /*LocObserver=*/nullptr) !=
            LegalizerHelper::AlreadyLegal) {
          // Instruction was rewritten to legal form
        }
      }
    }
    return true;
  }
};

Key Source Files and Components

The following files define the core infrastructure for LLVM target-independent code generation:

Component	File Path	Description
DAG Builder	llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp	Walks LLVM-IR and constructs the initial SelectionDAG
DAG Core	llvm/include/llvm/CodeGen/SelectionDAG.h	Defines SDNode and SDValue graph structures
Legacy Pipeline	llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp	Implements legalization, combining, selection, and scheduling
Scheduler Interface	llvm/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.h	Abstract scheduler used by the DAG pipeline
Selector Base	llvm/include/llvm/CodeGen/GlobalISel/InstructionSelector.h	Abstract select() method for GlobalISel
Legalizer	llvm/include/llvm/CodeGen/GlobalISel/LegalizerHelper.h	legalizeInstrStep() and operation rewriting logic
MIR Builder	llvm/include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h	Helper for emitting generic Machine IR
X86 LegalizerInfo	llvm/lib/Target/X86/GISel/X86LegalizerInfo.h	Target-specific legality tables
X86 Selector	llvm/lib/Target/X86/GISel/X86InstructionSelector.cpp	X86-specific selection implementation

Summary

• SelectionDAG builds a graph of SDNode objects from LLVM-IR, then legalizes types, combines nodes, selects instructions, and schedules them using target-independent algorithms driven by TargetLowering hooks.
• GlobalISel operates on SSA-based Machine IR with generic G_* opcodes, using LegalizerHelper for type legalization and InstructionSelector with TableGen-generated match tables for opcode replacement.
• Both pipelines share the TargetInstrInfo and TargetLowering interfaces, allowing targets to migrate gradually from the legacy DAG infrastructure to the modern GlobalISel framework.
• Key implementation files include SelectionDAGISel.cpp (legacy pipeline orchestration), LegalizerHelper.h (GlobalISel legalization), and target-specific subclasses like X86InstructionSelector.cpp.

Frequently Asked Questions

What is the primary difference between SelectionDAG and GlobalISel?

SelectionDAG constructs a custom directed acyclic graph representation (SelectionDAG) using SDNode objects and requires explicit graph traversal for legalization and selection. GlobalISel works directly on Machine IR (MIR)—an SSA-based representation closer to the final machine code—making it easier to debug and extend. While SelectionDAG uses C++-based selection logic, GlobalISel leverages TableGen-generated match tables for most instruction selection decisions.

How does LLVM ensure target independence during instruction selection?

Both pipelines rely on abstract target interfaces rather than hardcoded architecture knowledge. SelectionDAG uses TargetLowering to query operation legality and selection rules, while GlobalISel uses LegalizerInfo tables and InstructionSelector subclasses. The core algorithms in SelectionDAGISel.cpp and InstructionSelector.h operate on generic opcodes (ISD::* and G_* respectively), deferring target-specific decisions to virtual method calls implemented by each backend.

Can a target use both SelectionDAG and GlobalISel simultaneously?

Yes, targets can support both pipelines and select between them via compiler flags or function attributes. For example, AArch64 supports both infrastructures, allowing developers to compare code quality or gradually migrate optimization passes from the legacy DAG to GlobalISel. The MachineFunction format serves as the common output format for both pipelines, ensuring compatibility with subsequent passes like register allocation and machine code emission.

Where does type legalization occur in each pipeline?

In SelectionDAG, type legalization occurs in SelectionDAGISel.cpp through the LegalizeTypes() and LegalizeVectors() methods (around lines 10000-10700), which insert conversion nodes to eliminate illegal types before instruction selection. In GlobalISel, the LegalizerHelper class performs this role via the legalizeInstrStep() method, examining each generic instruction and rewriting it according to target-specific LegalizerInfo tables that define widening, narrowing, or splitting strategies for unsupported types.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}