il.c

#include <mun/il.h>

void
instr_insert_after(instruction* instr, instruction* prev){
  instr->prev = prev;
  instr->next = prev->next;
  instr->next->prev = instr;
  instr->prev->next = instr;

  for(word i = instr->input_count(instr) - 1; i >= 0; i--){
    il_value* val = instr->input_at(instr, i);
    defn_add_input_use(val->defn, val);
  }
}

instruction*
instr_append(instruction* instr, instruction* other){
  instr_link_to(instr, other);
  for(word i = other->input_count(instr) - 1; i >= 0; i--){
    il_value* input = other->input_at(other, i);
    defn_add_input_use(input->defn, input);
  }
  return other;
}

void
instr_set_input_at(instruction* instr, word index, il_value* val){
  val->instr = instr;
  val->index = index;
  instr->raw_set_input(instr, index, val);
}

void
instr_link_to(instruction* instr, instruction* next){
  instr->next = next;
  next->prev = instr;
}

static word
def_instr_successor_count(instruction* instr){
  return 0;
}

static block_entry_instr*
def_instr_successor_at(instruction* instr, word index){
  return NULL;
}

MUN_INLINE void
instr_init(instruction* instr){
  instr->prev = NULL;
  instr->rep = kTagged;
  instr->next = NULL;

  instr->successor_at = &def_instr_successor_at;
  instr->successor_count = &def_instr_successor_count;
}

MUN_INLINE void
block_entry_init(block_entry_instr* block){
  block->preorder_num = -1;
  block->postorder_num = -1;
  block->last = NULL;
  block->offset = -1;
}

static word
def_graph_entry_successor_count(){
  return 1;
}

static block_entry_instr*
def_graph_entry_successor_at(instruction* instr, word index){
  graph_entry_instr* gei = to_graph_entry(instr);
  if(index == 0) return &gei->normal_entry->block;
  return NULL;
}

bool
defn_has_only_input_use(definition* defn, il_value* val){
  return ((defn->input_use_list == val) && (val->next == NULL));
}

void
defn_replace_uses_with(definition* defn, definition* other){
  il_value* current = NULL;
  il_value* next = defn->input_use_list;

  if(next != NULL){
    while(next != NULL){
      current = next;
      current->defn = other;
      next = current->next;
    }

    next = other->input_use_list;
    current->next = next;
    if(next != NULL) next->prev = current;
    other->input_use_list = defn->input_use_list;
    defn->input_use_list = NULL;
  }
}

graph_entry_instr*
graph_entry_new(function* func, target_entry_instr* target){
  graph_entry_instr* graph = malloc(sizeof(graph_entry_instr));
  graph->func = func;
  graph->normal_entry = target;
  graph->entry_count = 0;
  graph->spill_slot_count = 0;
  instr_init(&graph->block.instr);
  block_entry_init(&graph->block);
  graph->block.instr.successor_at = &def_graph_entry_successor_at;
  return graph;
}

static void
defn_init(definition* defn){
  defn->input_use_list = NULL;
  defn->constant_value = NULL;
  defn->ssa_temp_index = -1;
  defn->temp_index = -1;
}

static word
def_return_input_count(instruction* instr){
  return 1;
}

static il_value*
def_return_input_at(instruction* instr, word index){
  return_instr* ret = to_return(instr);
  return ret->inputs[index];
}

static void
def_return_set_input_at(instruction* instr, word index, il_value* val){
  to_return(instr)->inputs[index] = val;
}

return_instr*
return_instr_new(il_value* val){
  return_instr* ret = malloc(sizeof(return_instr));
  instr_init(&ret->defn.instr);
  defn_init(&ret->defn);
  ret->defn.instr.input_count = &def_return_input_count;
  ret->defn.instr.input_at = &def_return_input_at;
  ret->defn.instr.raw_set_input = &def_return_set_input_at;
  instr_set_input_at(&ret->defn.instr, 0, val);
  return ret;
}

static word
def_constant_input_count(instruction* instr){
  return 0;
}

static il_value*
def_constant_input_at(instruction* instr, word index){
  return NULL;
}

static void
def_constant_set_input_at(instruction* instr, word index, il_value* val){
  //Fallthrough
}

constant_instr*
constant_instr_new(instance* val){
  constant_instr* c = malloc(sizeof(constant_instr));
  instr_init(&c->defn.instr);
  defn_init(&c->defn);
  c->defn.instr.input_count = &def_constant_input_count;
  c->defn.instr.input_at = &def_constant_input_at;
  c->defn.instr.raw_set_input = &def_constant_set_input_at;
  c->value = val;
  return c;
}

il_value*
instr_input_at(instruction* instr, word index){
  if(instr->input_at != NULL) return instr->input_at(instr, index);
  return NULL;
}

il_value*
value_new(definition* defn){
  il_value* val = malloc(sizeof(il_value));
  val->instr = NULL;
  val->defn = defn;
  val->next = NULL;
  val->prev = NULL;
  val->index = 0;
  return val;
}

il.h

#ifndef MUN_IL_H
#define MUN_IL_H

#include "common.h"
#include "asm/core.h"
#include "object.h"

HEADER_BEGIN

#define FOR_EACH_INSTRUCTION(V) \
  V(GraphEntry) \
  V(TargetEntry) \
  V(Return) \
  V(Constant)

typedef struct _definition definition;
typedef struct _instruction instruction;
typedef struct _block_entry_instr block_entry_instr;

typedef struct _il_value {
  definition* defn;
  instruction* instr;
  struct _il_value* next;
  struct _il_value* prev;
  word index;
} il_value;

il_value* value_new(definition* defn);

MUN_INLINE bool
value_is_single_use(il_value* val) {
  return (val->next == NULL) &&
         (val->prev == NULL);
}

void value_remove_from_list(il_value* val);
void add_input_use(definition* defn, il_value* val);

MUN_INLINE void
value_bind_to(il_value* val, definition* defn){
  value_remove_from_list(val);
  val->defn = defn;
  add_input_use(defn, val);
}

MUN_INLINE void
value_add_to_list(il_value* val, il_value** list){
  il_value* next = *list;
  *list = val;
  val->next = next;
  val->prev = NULL;
  if(next != NULL) next->prev = val;
}

typedef enum{
  kUnboxedNumber,
  kBoxedNumber,
  kTagged,
  kNone
} representation;

struct _instruction{
  instruction* next;
  instruction* prev;
  representation rep;

  representation (*get_in_representation)(word index);
  definition* (*argument_at)(word index);
  void (*emit_machine_code)(asm_buff* buff);
  void (*raw_set_input)(instruction*, word index, il_value* val);
  word (*input_count)(instruction*);
  word (*successor_count)(instruction*);
  word (*argument_count)(void);
  block_entry_instr* (*successor_at)(instruction*, word index);
  block_entry_instr* (*get_block)(instruction*);
  il_value* (*input_at)(instruction*,word index);
};

void instr_set_input_at(instruction* instr, word index, il_value* val);
void instr_link_to(instruction* instr, instruction* next);
void instr_insert_after(instruction* instr, instruction* prev);

instruction* instr_append(instruction* instr, instruction* tail);

il_value* instr_input_at(instruction* instr, word index);

MUN_INLINE void
instr_insert_before(instruction* instr, instruction* next){
  instr_insert_after(next->prev, instr);
}

struct _block_entry_instr{
  instruction instr;

  word preorder_num;
  word postorder_num;
  word start_pos;
  word end_pos;
  instruction* last;
  word offset;
};

typedef struct _target_entry_instr target_entry_instr;

typedef struct{
  block_entry_instr block;

  target_entry_instr* normal_entry;
  function* func;
  word entry_count;
  word spill_slot_count;
  word fixed_slot_count;
} graph_entry_instr;

#define to_graph_entry(i) container_of(container_of(i, block_entry_instr, instr), graph_entry_instr, block)

graph_entry_instr* graph_entry_new(function* func, target_entry_instr* target);

struct _target_entry_instr{
  block_entry_instr block;
};

struct _definition{
  instruction instr;

  word temp_index;
  word ssa_temp_index;
  il_value* input_use_list;
  instance* constant_value;
};

MUN_INLINE bool
defn_has_uses(definition* defn){
  return (defn->input_use_list != NULL);
}

bool defn_has_only_input_use(definition* defn, il_value* use);

MUN_INLINE void
defn_add_input_use(definition* defn, il_value* val){
  value_add_to_list(val, &defn->input_use_list);
}

void defn_replace_uses_with(definition* defn, definition* other);

typedef struct{
  definition defn;

  il_value* inputs[1];
} return_instr;

#define to_return(i) container_of(container_of(i, definition, instr), return_instr, defn)

return_instr* return_instr_new(il_value* val);

typedef struct{
  definition defn;

  instance* value;
} constant_instr;

#define to_constant(i) container_of(container_of(i, definition, instr), constant_instr, defn)

constant_instr* constant_instr_new(instance* val);

HEADER_END

#endif