IR Language Experiments

ir.js

// Source code:
//
// int a = 25
// int b = 20
// int c = 0;
//
// if (a + b > 40) {
//   c = 1;
// } else {
//   c = 0;
// }
//
// return c
//
//
// IR with annotations:
// 
//   %0 = alloca
//   %1 = alloca
//   %2 = alloca
//   store %0 25
//   store %1 25
//   store %2 0
//   %3 = add %0 %1
//   %4 = cmp sgt %3 40
//   br %4 .L0 .L1
// .L0
//   store %2 1
//   br .L2
// .L1
//   store %2 0
//   br .L2
// .L2
//   %5 = load %2
//   ret %5
//

class IRNode {};

class IRBasicBlock extends IRNode {
  constructor(id) {
    super();
    this.id = id;
    this.instructions = [];
  }
};

class IRLiteral extends IRNode {
  constructor(value) {
    super();
    this.value = value;
  }
};

class IRReference extends IRNode {
  constructor(id) {
    super();
    this.id = id;
  }
};

class IRLabel extends IRNode {
  constructor(symbol) {
    super();
    this.symbol = symbol;
  }
};

class IRAlloc extends IRNode {};

class IRStore extends IRNode {
  constructor(target, source) {
    super();
    this.target = target;
    this.source = source;
  }
};

class IRAdd extends IRNode {
  constructor(left, right) {
    super();
    this.left = left;
    this.right = right;
  }
};

class IRCmp extends IRNode {
  constructor(method, left, right) {
    super();
    this.method = method;
    this.left = left;
    this.right = right;
  }
};

class IRBr extends IRNode {
  constructor(condition, then_block, else_block) {
    super();
    this.condition = condition;
    this.then_block = then_block;
    this.else_block = else_block;
  }
};

class IRJmp extends IRNode {
  constructor(block) {
    super();
    this.block = block;
  }
};

class IRLoad extends IRNode {
  constructor(source) {
    super();
    this.source = source;
  }
};

class IRRet extends IRNode {
  constructor(source) {
    super();
    this.source = source;
  }
};

class IRBuilder {
  constructor() {
    this.symbols = {};
    this.symbol_counter = 0;

    this.blocks = {};
    this.current_block = undefined;
  }

  get_symbol() {
    return new IRReference(this.symbol_counter++);
  }

  append_to_block(node) {
    this.active_block().instructions.push(node);
  }

  append_to_block_with_symbol(node) {
    this.append_to_block(node);
    const symbol = this.get_symbol();
    this.assign_symbol(symbol, node);
    return symbol;
  }

  create_new_block() {
    const symbol = this.get_symbol();
    const block = new IRBasicBlock(symbol.id);
    this.blocks[symbol.id] = block;
    return new IRLabel(symbol);
  }

  set_current_block(symbol) {
    this.current_block = symbol;
  }

  assign_symbol(symbol, node) {
    this.symbols[symbol.id] = node;
  }

  lookup_symbol(symbol) {
    return this.symbols[symbol.id];
  }

  lookup_block(label) {
    return this.blocks[label.symbol.id];
  }

  active_block() {
    return this.lookup_block(this.current_block);
  }
};

const builder = new IRBuilder();
const mainBB = builder.create_new_block();
builder.set_current_block(mainBB);

const sym_a = builder.append_to_block_with_symbol(new IRAlloc());
const sym_b = builder.append_to_block_with_symbol(new IRAlloc());
const sym_c = builder.append_to_block_with_symbol(new IRAlloc());

builder.append_to_block(new IRStore(sym_a, new IRLiteral(25)));
builder.append_to_block(new IRStore(sym_b, new IRLiteral(20)));
builder.append_to_block(new IRStore(sym_c, new IRLiteral(0)));

const left_block = builder.create_new_block();
const right_block = builder.create_new_block();
const exit_block = builder.create_new_block();

const sym_addition = builder.append_to_block_with_symbol(new IRAdd(sym_a, sym_b));
const sym_comparison = builder.append_to_block_with_symbol(new IRCmp("sgt", sym_addition, new IRLiteral(40)));
builder.append_to_block(new IRBr(sym_comparison, left_block, right_block));

builder.set_current_block(left_block);
builder.append_to_block(new IRStore(sym_c, new IRLiteral(1)));
builder.append_to_block(new IRJmp(exit_block));

builder.set_current_block(right_block);
builder.append_to_block(new IRStore(sym_c, new IRLiteral(0)));
builder.append_to_block(new IRJmp(exit_block));

builder.set_current_block(exit_block);
const value_c = builder.append_to_block_with_symbol(new IRLoad(sym_c));
builder.append_to_block(new IRRet(value_c));

console.dir(builder, { depth: null });

IRBuilder {
  symbols: 
   { '1': IRAlloc {},
     '2': IRAlloc {},
     '3': IRAlloc {},
     '7': IRAdd { left: IRReference { id: 1 }, right: IRReference { id: 2 } },
     '8': 
      IRCmp {
        method: 'sgt',
        left: IRReference { id: 7 },
        right: IRLiteral { value: 40 } },
     '9': IRLoad { source: IRReference { id: 3 } } },
  symbol_counter: 10,
  blocks: 
   { '0': 
      IRBasicBlock {
        id: 0,
        instructions: 
         [ IRAlloc {},
           IRAlloc {},
           IRAlloc {},
           IRStore {
             target: IRReference { id: 1 },
             source: IRLiteral { value: 25 } },
           IRStore {
             target: IRReference { id: 2 },
             source: IRLiteral { value: 20 } },
           IRStore {
             target: IRReference { id: 3 },
             source: IRLiteral { value: 0 } },
           IRAdd { left: IRReference { id: 1 }, right: IRReference { id: 2 } },
           IRCmp {
             method: 'sgt',
             left: IRReference { id: 7 },
             right: IRLiteral { value: 40 } },
           IRBr {
             condition: IRReference { id: 8 },
             then_block: IRLabel { symbol: IRReference { id: 4 } },
             else_block: IRLabel { symbol: IRReference { id: 5 } } } ] },
     '4': 
      IRBasicBlock {
        id: 4,
        instructions: 
         [ IRStore {
             target: IRReference { id: 3 },
             source: IRLiteral { value: 1 } },
           IRJmp { block: IRLabel { symbol: IRReference { id: 6 } } } ] },
     '5': 
      IRBasicBlock {
        id: 5,
        instructions: 
         [ IRStore {
             target: IRReference { id: 3 },
             source: IRLiteral { value: 0 } },
           IRJmp { block: IRLabel { symbol: IRReference { id: 6 } } } ] },
     '6': 
      IRBasicBlock {
        id: 6,
        instructions: 
         [ IRLoad { source: IRReference { id: 3 } },
           IRRet { source: IRReference { id: 9 } } ] } },
  current_block: IRLabel { symbol: IRReference { id: 6 } } }