LLVM IR Interpreter Deep-Dive Focus Deep-Dive

Execution Architecture

Each OpenCL work-item is modelled by a WorkItem object that acts as a tiny single-threaded interpreter. The work-group scheduler repeatedly calls step(), which executes exactly one LLVM IR instruction per invocation:

flowchart TD
  S[WorkGroup scheduler] -->|calls| STEP[WorkItem::step]
  STEP --> CHK{hasBegun?}
  CHK -- No --> NOTIFY_BEGIN[notifyWorkItemBegin]
  NOTIFY_BEGIN --> EXEC
  CHK -- Yes --> EXEC[execute current instruction]
  EXEC --> ADV[advance currInst++]
  ADV --> BLK{nextBlock set?}
  BLK -- Yes --> MOVE[prevBlock = currBlock
currBlock = nextBlock
currInst = begin]
  BLK -- No --> RET
  MOVE --> RET{state == FINISHED?}
  RET -- Yes --> NOTIFY_END[notifyWorkItemComplete]
  RET -- No --> DONE[return m_state]
  NOTIFY_END --> DONE

WorkItem state machine

The step() / execute() Loop

WorkItem::State WorkItem::step() {
    assert(m_state == READY);
    if (!m_position->hasBegun) {
        m_position->hasBegun = true;
        m_context->notifyWorkItemBegin(this);
    }
    execute(&*m_position->currInst);

    if (++m_position->currInst == m_position->currBlock->end()
        || m_position->nextBlock) {
        if (m_position->nextBlock) {
            m_position->prevBlock = m_position->currBlock;
            m_position->currBlock = m_position->nextBlock;
            m_position->nextBlock = NULL;
            m_position->currInst  = m_position->currBlock->begin();
        }
    }
    if (m_state == FINISHED)
        m_context->notifyWorkItemComplete(this);
    return m_state;
}Copy

The execute() method wraps the opcode dispatch with result management and PHI commit logic:

void WorkItem::execute(const llvm::Instruction* instruction) {
    // 1. Allocate result storage from pool
    pair<unsigned,unsigned> sz = getValueSize(instruction);
    TypedValue result = {sz.first, sz.second, NULL};
    if (result.size)
        result.data = m_pool.alloc(result.size * result.num);

    // 2. Commit PHI temporaries accumulated from the previous block
    if (instruction->getOpcode() != llvm::Instruction::PHI
        && m_phiTemps.size() > 0) {
        for (auto& kv : m_phiTemps)
            setValue(kv.first, kv.second);
        m_phiTemps.clear();
    }

    // 3. Dispatch the actual opcode handler
    dispatch(instruction, result);

    // 4. Store the result (PHI results go to temp map)
    if (result.size) {
        if (instruction->getOpcode() != llvm::Instruction::PHI)
            setValue(instruction, result);
        else
            m_phiTemps[instruction] = result;
    }

    // 5. Notify plugins
    m_context->notifyInstructionExecuted(this, instruction, result);
}Copy

Opcode Dispatch

The dispatch() method is a large switch on instruction->getOpcode() with 45+ cases. Each case calls a dedicated handler method defined via the INSTRUCTION macro:

#define INSTRUCTION(name) \
  void WorkItem::name(const llvm::Instruction* instruction, TypedValue& result)

// dispatch() — abbreviated
void WorkItem::dispatch(const llvm::Instruction* instruction, TypedValue& result) {
    switch (instruction->getOpcode()) {
        case llvm::Instruction::Add:           add(instruction, result); break;
        case llvm::Instruction::Alloca:        alloc(instruction, result); break;
        case llvm::Instruction::Br:            br(instruction, result); break;
        case llvm::Instruction::Call:          call(instruction, result); break;
        case llvm::Instruction::GetElementPtr: gep(instruction, result); break;
        case llvm::Instruction::ICmp:          icmp(instruction, result); break;
        case llvm::Instruction::Load:          load(instruction, result); break;
        case llvm::Instruction::PHI:           phi(instruction, result); break;
        case llvm::Instruction::Ret:           ret(instruction, result); break;
        case llvm::Instruction::Store:         store(instruction, result); break;
        // ... 35+ more cases
        case llvm::Instruction::Unreachable:
            FATAL_ERROR("Encountered unreachable instruction");
        default:
            FATAL_ERROR("Unsupported instruction: %d", instruction->getOpcode());
    }
}Copy

Instruction categories

Stack Frames & Function Calls

The execution position is held in a Position struct that acts as the interpreter's call-frame stack:

struct WorkItem::Position {
    bool                               hasBegun;
    const llvm::BasicBlock*            prevBlock;    // for PHI resolution
    const llvm::BasicBlock*            currBlock;    // current basic block
    const llvm::BasicBlock*            nextBlock;    // set by br/switch
    llvm::BasicBlock::const_iterator   currInst;     // instruction pointer
    std::stack<const llvm::Instruction*> callStack;  // return addresses
    std::stack<std::list<size_t>>      allocations;  // per-frame alloca tracking
};Copy

sequenceDiagram
  participant Sched as WorkGroup
  participant WI as WorkItem
  participant Pos as Position
  participant Mem as Private Memory

  Sched->>WI: step()
  WI->>WI: execute(call instruction)
  WI->>Pos: push currInst onto callStack
  WI->>Pos: push new allocation list
  WI->>Pos: nextBlock = callee entry block
  Note over Pos: IP now points into callee

  loop callee body
    Sched->>WI: step()
  end

  WI->>WI: execute(ret instruction)
  WI->>Pos: pop callStack → restore IP
  WI->>Mem: deallocateBuffer for each alloca
  WI->>Pos: pop allocation list
  Note over Pos: IP restored to caller

Call instruction handler

INSTRUCTION(call) {
    const llvm::CallInst* callInst = (const llvm::CallInst*)instruction;
    const llvm::Function* function = callInst->getCalledFunction();

    // Resolve indirect calls
    if (!function) {
        const llvm::Value* v = callInst->getCalledOperand();
        function = (const llvm::Function*)((const llvm::User*)v)->getOperand(0);
    }

    if (!function->isDeclaration()) {
        // User-defined function: push stack frame
        m_position->callStack.push(&*m_position->currInst);
        m_position->allocations.push(std::list<size_t>());
        m_position->nextBlock = &*function->begin();

        // Bind arguments (handle byval copies)
        for (auto arg = function->arg_begin(); arg != function->arg_end(); arg++) {
            TypedValue value = getOperand(callInst->getArgOperand(arg->getArgNo()));
            if (arg->hasByValAttr()) {
                size_t sz  = getTypeSize(arg->getParamByValType());
                void*  src = m_privateMemory->getPointer(value.getPointer());
                size_t ptr = m_privateMemory->allocateBuffer(sz, 0, (uint8_t*)src);
                m_position->allocations.top().push_back(ptr);
                TypedValue addr = {sizeof(size_t), 1, m_pool.alloc(sizeof(size_t))};
                addr.setPointer(ptr);
                setValue(&*arg, addr);
            } else {
                setValue(&*arg, m_pool.clone(value));
            }
        }
        return;
    }

    // External / builtin function
    InterpreterCache::Builtin builtin = m_cache->getBuiltin(function);
    builtin.function.func(this, callInst, builtin.name,
                          builtin.overload, result, builtin.function.op);
}Copy

Branch Handling & PHI Nodes

Conditional and unconditional branches

INSTRUCTION(br) {
    if (instruction->getNumOperands() == 1) {
        // Unconditional
        m_position->nextBlock =
            (const llvm::BasicBlock*)instruction->getOperand(0);
    } else {
        // Conditional: operand 0 = i1 predicate
        bool pred = getOperand(instruction->getOperand(0)).getUInt();
        m_position->nextBlock = (const llvm::BasicBlock*)
            (pred ? instruction->getOperand(2)    // true dest
                  : instruction->getOperand(1));  // false dest
    }
}

INSTRUCTION(phi) {
    const llvm::PHINode* phiNode = (const llvm::PHINode*)instruction;
    const llvm::Value* incoming =
        phiNode->getIncomingValueForBlock(m_position->prevBlock);
    memcpy(result.data, getOperand(incoming).data, result.size * result.num);
}Copy

Builtin Function System

When call encounters a function that is a declaration (no body in the IR), the InterpreterCache resolves it to a builtin entry:

struct BuiltinFunction {
    void (*func)(WorkItem*, const llvm::CallInst*,
                 const std::string& name, const std::string& overload,
                 TypedValue& result, void* op);
    void* op;   // optional function pointer for generic wrappers
};

// Registration maps
extern BuiltinFunctionMap        workItemBuiltins;       // exact name match
extern BuiltinFunctionPrefixList workItemPrefixBuiltins; // prefix matchCopy

Generic vector wrappers

Math builtins are registered via generic wrappers that apply a C function element-wise across vector operands:

// Apply a 1-arg double function to each vector element
static void f1arg(WorkItem* wi, const llvm::CallInst* ci,
                  const string& name, const string& overload,
                  TypedValue& result, double (*func)(double)) {
    for (unsigned i = 0; i < result.num; i++)
        result.setFloat(func(FARGV(0, i)), i);
}

// Registration example (conceptual):
//   workItemBuiltins["sin"]  = {f1arg, (void*)sin};
//   workItemBuiltins["cos"]  = {f1arg, (void*)cos};
//   workItemBuiltins["sqrt"] = {f1arg, (void*)sqrt};Copy

Builtin categories

Operand Resolution

getOperand() resolves any LLVM Value to a TypedValue:

• Arguments, instructions, globals → looked up in the value store via getValue()
• Constant expressions → recursively dispatched through the interpreter
• Constant data → fetched from the InterpreterCache

flowchart LR
  V[llvm::Value*] --> A{Argument or Instruction?}
  A -- Yes --> VS[getValue from m_values]
  A -- No --> B{ConstantExpr?}
  B -- Yes --> D[dispatch as instruction]
  B -- No --> C{ConstantData?}
  C -- Yes --> IC[InterpreterCache::getConstant]
  C -- No --> ERR[fatal error]