Trình biên dịch biến mã nguồn thành chỉ thị máy như thế nào

Compiler không dịch trực tiếp từng dòng source thành một dòng assembly. Nó liên tục đổi representation của chương trình. Mỗi representation loại bỏ chi tiết thừa và giúp trả lời câu hỏi mới: ký tự nào tạo token? Identifier trỏ tới khai báo nào? Phép cộng có hợp lệ không? Giá trị nào là constant? CPU instruction nào thực hiện operation này? Temporary value nên nằm ở đâu?

Xét expression nhỏ let total: i32 = price * 4 + 2. Cách viết quan trọng với lexer, hình dạng cây quan trọng với parser, kiểu khai báo quan trọng với semantic analysis, còn dependency số học quan trọng với optimizer. Khi backend phát instruction, những cái tên như total có thể đã biến mất. Thứ còn lại là graph của value, effect, branch và storage location.

Bài viết theo dõi quá trình đó bằng compiler TypeScript thu nhỏ có integer literal, variable, let, phép cộng và phép nhân. Phạm vi nhỏ nhưng các ranh giới đều có thật trong compiler production.

Front end biến văn bản thành ý nghĩa #

Lexing gom ký tự thành token, bỏ whitespace nhưng giữ category và source position. Input price * 4 + 2 trở thành identifier(price), star, integer(4), plus và integer(2). Giữ offset là thiết yếu: phase sau phải báo unknown name hay type mismatch tại source ban đầu, không phải tại instruction được sinh ra.

Parsing tiếp tục nhận diện cấu trúc grammar. Precedence khiến phép nhân kết dính chặt hơn phép cộng, do đó expression trở thành Add(Mul(Name("price"), Int(4)), Int(2)). Abstract syntax tree này bỏ dấu câu sau khi chúng hoàn thành vai trò. Ngược lại, concrete syntax tree dành cho formatter và công cụ refactor thường giữ comment, whitespace và delimiter.

Front end dưới đây giữ riêng expression grammar. Regular expression nhận diện token class, còn precedence climbing làm * bind chặt hơn +:

type Expr =
  | { kind: 'int'; value: number; offset: number }
  | { kind: 'name'; name: string; offset: number }
  | { kind: 'binary'; op: '+' | '*'; left: Expr; right: Expr; offset: number };

type Token = { kind: 'int' | 'name' | 'plus' | 'star' | 'eof'; text: string; offset: number };

function lex(source: string): Token[] {
  const pattern = /\s+|\d+|[A-Za-z_]\w*|[+*]/gy;
  const tokens: Token[] = [];
  while (pattern.lastIndex < source.length) {
    const offset = pattern.lastIndex;
    const match = pattern.exec(source);
    if (!match) throw new SyntaxError(`unexpected input at ${offset}`);
    const text = match[0];
    if (/^\s+$/.test(text)) continue;
    const kind = /^\d+$/.test(text) ? 'int'
      : /^\w+$/.test(text) ? 'name'
      : text === '+' ? 'plus' : 'star';
    tokens.push({ kind, text, offset });
  }
  return [...tokens, { kind: 'eof', text: '', offset: source.length }];
}

class Parser {
  private cursor = 0;
  constructor(private readonly tokens: Token[]) {}

  parseExpression(minPrecedence = 0): Expr {
    const token = this.tokens[this.cursor++]!;
    let left: Expr;
    if (token.kind === 'int') left = { kind: 'int', value: Number(token.text), offset: token.offset };
    else if (token.kind === 'name') left = { kind: 'name', name: token.text, offset: token.offset };
    else throw new SyntaxError(`expected expression at ${token.offset}`);

    const precedence = { plus: 1, star: 2 } as const;
    while (true) {
      const operator = this.tokens[this.cursor]!;
      const level = operator.kind === 'plus' || operator.kind === 'star' ? precedence[operator.kind] : -1;
      if (level < minPrecedence) break;
      this.cursor++;
      const right = this.parseExpression(level + 1);
      left = { kind: 'binary', op: operator.kind === 'plus' ? '+' : '*', left, right, offset: operator.offset };
    }
    return left;
  }
}

Parser thực tế còn phải phục hồi sau error và xử lý grammar mơ hồ. Contract vẫn vậy: parsing tạo structure chứ chưa quyết định meaning.

Semantic analysis phân giải name và type #

AST có thể đúng grammar nhưng vẫn vô nghĩa. price * missing tham chiếu variable chưa khai báo. Một language có string có thể parse được price + "four", rồi từ chối vì không có phép cộng phù hợp. Semantic analysis dựng scope, bind mỗi lần dùng name với một declaration, kiểm tra visibility và mutability, infer hoặc xác minh type, đồng thời thường annotate tree bằng symbol và conversion.

Environment ánh xạ source name sang symbol ID ổn định. ID phân biệt hai variable cùng tên trong nested scope và cho phép phase sau quên cách viết ở source.

type SymbolId = number;
type TypedExpr =
  | { kind: 'const'; value: number; type: 'i32' }
  | { kind: 'load'; symbol: SymbolId; type: 'i32' }
  | { kind: 'binary'; op: '+' | '*'; left: TypedExpr; right: TypedExpr; type: 'i32' };

function checkExpression(expression: Expr, scope: Map<string, SymbolId>): TypedExpr {
  switch (expression.kind) {
    case 'int':
      if (!Number.isInteger(expression.value) || expression.value > 2_147_483_647) {
        throw new TypeError(`i32 literal out of range at ${expression.offset}`);
      }
      return { kind: 'const', value: expression.value, type: 'i32' };
    case 'name': {
      const symbol = scope.get(expression.name);
      if (symbol === undefined) throw new ReferenceError(`unknown name '${expression.name}' at ${expression.offset}`);
      return { kind: 'load', symbol, type: 'i32' };
    }
    case 'binary':
      return {
        kind: 'binary',
        op: expression.op,
        left: checkExpression(expression.left, scope),
        right: checkExpression(expression.right, scope),
        type: 'i32',
      };
  }
}

Type checking không chỉ ngăn crash. Nó chọn operation. So sánh signed và unsigned dùng machine instruction khác nhau; cộng integer và floating point tuân theo quy tắc overflow và rounding khác nhau; generic call có thể cần specialization. Vì vậy type system cung cấp fact để lowering và optimization dựa vào.

IR và SSA làm lộ data flow #

Compiler lower typed AST xuống intermediate representation (IR). AST phản ánh source nesting; IR làm rõ control flow và data dependency. Compiler thường có typed IR, mid-level control-flow IR và machine IR gần target.

Static single assignment hay SSA cho mỗi value đúng một definition. Thay vì gán lại x nhiều lần, compiler tạo x0, x1 và các version tiếp theo. Tại điểm merge của control flow, phi node chọn value tương ứng với predecessor vừa chạy. Property này làm use-definition chain trở nên trực tiếp và mở đường cho sparse analysis.

Với expression chạy thẳng, virtual register cung cấp property quan trọng kiểu SSA:

v0 = load symbol0       ; price
v1 = const 4
v2 = mul.i32 v0, v1
v3 = const 2
v4 = add.i32 v2, v3
store symbol1, v4       ; total

Optimization không phải một bước thần kỳ. Nó là chuỗi analysis và rewrite giữ nguyên behavior quan sát được.

Thứ tự pass quan trọng: inlining làm lộ constant, folding khiến branch unreachable, rồi xóa branch làm lộ dead value. Optimizer lặp pass nhưng phải giới hạn compile time và code growth.

Backend chọn instruction và cấp phát register #

Instruction selection ánh xạ IR sang target pattern. Nhân bốn có thể dùng imul hoặc shift; phép cộng dùng ngay làm address có thể fold vào addressing mode. Selection còn phải xét operand constraint, flag, calling convention và CPU cost.

Target ban đầu dùng vô hạn virtual register, nhưng hardware có register file nhỏ. Register allocation tính liveness, cho live range không interfere dùng chung physical register và spill phần dư xuống stack. Graph coloring thường tốt; linear scan nhanh và phổ biến trong JIT. Calling convention quy định argument, return value và register phải bảo toàn.

Backend tập trung dưới đây nhận stack-shaped IR, fold constant, tính lần dùng cuối, tái sử dụng register đã chết và phát assembly giống x64:

type Ir =
  | { op: 'const'; out: number; value: number }
  | { op: 'load'; out: number; stackOffset: number }
  | { op: 'add' | 'mul'; out: number; left: number; right: number }
  | { op: 'store'; value: number; stackOffset: number };

function foldConstants(instructions: Ir[]): Ir[] {
  const constants = new Map<number, number>();
  return instructions.map((instruction) => {
    if (instruction.op === 'const') constants.set(instruction.out, instruction.value);
    if (instruction.op !== 'add' && instruction.op !== 'mul') return instruction;
    const left = constants.get(instruction.left);
    const right = constants.get(instruction.right);
    if (left === undefined || right === undefined) return instruction;
    const value = instruction.op === 'add' ? (left + right) | 0 : Math.imul(left, right);
    constants.set(instruction.out, value);
    return { op: 'const', out: instruction.out, value };
  });
}

function emitX64(instructions: Ir[]): string[] {
  const registers = ['eax', 'ecx', 'edx'];
  const location = new Map<number, string>();
  const lastUse = new Map<number, number>();
  const assembly: string[] = [];

  instructions.forEach((instruction, index) => {
    if (instruction.op === 'add' || instruction.op === 'mul') {
      lastUse.set(instruction.left, index);
      lastUse.set(instruction.right, index);
    } else if (instruction.op === 'store') lastUse.set(instruction.value, index);
  });

  const acquire = (index: number): string => {
    for (const [value, register] of location) {
      if ((lastUse.get(value) ?? -1) < index) location.delete(value);
      else if (register.startsWith('spill')) continue;
    }
    const used = new Set(location.values());
    const free = registers.find((register) => !used.has(register));
    if (!free) throw new Error('spill required: allocate a stack slot');
    return free;
  };

  instructions.forEach((instruction, index) => {
    if (instruction.op === 'const') {
      const target = acquire(index);
      location.set(instruction.out, target);
      assembly.push(`mov ${target}, ${instruction.value}`);
    } else if (instruction.op === 'load') {
      const target = acquire(index);
      location.set(instruction.out, target);
      assembly.push(`mov ${target}, DWORD PTR [rbp${instruction.stackOffset}]`);
    } else if (instruction.op === 'add' || instruction.op === 'mul') {
      const left = location.get(instruction.left)!;
      const right = location.get(instruction.right)!;
      location.delete(instruction.left);
      const target = left;
      location.set(instruction.out, target);
      assembly.push(`${instruction.op === 'add' ? 'add' : 'imul'} ${target}, ${right}`);
    } else {
      assembly.push(`mov DWORD PTR [rbp${instruction.stackOffset}], ${location.get(instruction.value)!}`);
    }
  });
  return assembly;
}

Allocator này cố ý báo khi cần spill thay vì che phần khó. Allocator hoàn chỉnh chèn store và reload, split live range, xử lý instruction bắt buộc dùng register cố định và có thể chạy allocation lại sau rewrite. Sau allocation, assembler encode instruction thành byte, chọn độ rộng immediate và ghi lại location chưa thể resolve.

Object file, linking, JIT và tính đúng đắn #

Object file chứa machine code, section dữ liệu, symbol table và relocation. Call tới function ngoài file chưa biết final address, nên assembler phát placeholder và relocation. Linker ghép object/library, resolve symbol, layout section và tạo executable hoặc shared library; OS loader map image rồi hoàn tất dynamic relocation.

Debug information giữ đường quay lại source. DWARF hoặc PDB map instruction range tới line, mô tả scope/type và vị trí variable. Với optimization, function inline không có frame thường, variable di chuyển giữa register và stack, còn dead code không có address. “Optimized out” đôi khi là câu trả lời trung thực.

Ahead-of-time và just-in-time compiler dùng nhiều phase giống nhau nhưng tối ưu cho constraint khác nhau:

JIT có thể quan sát phép cộng JavaScript từ trước tới giờ chỉ nhận small integer, rồi phát fast integer sequence được bảo vệ bởi type check. Nếu sau đó xuất hiện string, deoptimization metadata dựng lại interpreter state và tiếp tục bằng generic code. Tiered runtime bắt đầu bằng interpret hoặc compile nhanh, thu profile, rồi chỉ tốn nhiều optimization effort cho hot function. AOT compiler có thể mô phỏng phần nào kiến thức đó bằng profile-guided optimization, nhưng profile cũ có thể không khớp deployment tiếp theo.

Correctness không thể thương lượng. Mỗi pass phải giữ exception, memory ordering, volatile access, overflow và floating-point corner case. Đội compiler dùng unit/conformance test, IR verifier, differential testing, fuzzing và translation validation. Mỗi optimization thực chất là một proof obligation.

Điều cần ghi nhớ #

• Compilation là chuỗi representation, không phải phép thay trực tiếp source text bằng assembly.
• Token và AST phục hồi syntax; name resolution và type checking thiết lập ý nghĩa đồng thời giữ source diagnostic.
• IR dạng SSA làm lộ quan hệ use-definition và control flow để optimization trở nên khả thi.
• Instruction selection, calling convention, liveness, register allocation và spilling thích nghi vô hạn IR value với hardware hữu hạn.
• Assembler tạo machine code cùng relocation record; linker resolve chương trình cuối, còn debug metadata ánh xạ instruction đã optimize về source.
• AOT compiler chi thời gian trước execution; JIT dùng live profile và guarded specialization, sau đó deoptimize khi assumption không còn đúng.
• Mọi optimization bị giới hạn bởi semantics của source language. Code sai chạy nhanh hơn vẫn là compiler bug, không phải optimization.

Source variable total trở thành token, AST declaration, typed symbol, virtual value, physical register, encoded byte và cuối cùng là address trong process. Compiler chia một phép dịch khó thành chuỗi quyết định nhỏ, có thể kiểm tra.