sim.c

#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>

typedef struct {
    bool has_value;
    int value;
} maybe_int;

typedef struct {
    unsigned count;
    maybe_int value;
} rc_maybe_int;

typedef struct {
    rc_maybe_int* ptr;
} future_int;

// Create a new future int which will be filled at some point
future_int make_future_int() {
    future_int fut;
    fut.ptr = malloc(sizeof(rc_maybe_int));
    fut.ptr->count = 1;
    fut.ptr->value.has_value = false;
    fut.ptr->value.value = -42;
    return fut;
}

// Create a new future int which is already filled with the given value
future_int make_now_int(int val) {
    future_int fut;
    fut.ptr = malloc(sizeof(rc_maybe_int));
    fut.ptr->count = 1;
    fut.ptr->value.has_value = true;
    fut.ptr->value.value = val;
    return fut;
}

// Anticipate the value of a future in, i.e. copy it
future_int anticipate(future_int f) {
    f.ptr->count++;
    return f;
}

// Check if the future int has had it's value filled or not
bool is_ready(future_int f) {
    return f.ptr->value.has_value;
}

// Return the value of a filled future int
int get_value(future_int f) {
    return f.ptr->value.value;
}

// Fulil a future by giving it a value
void put_value(future_int f, int val) {
    f.ptr->value.has_value = true;
    f.ptr->value.value = val;
}

// Release a future
void release(future_int* f) {
    f->ptr->count--;
    if(f->ptr->count == 0) {
        free(f->ptr);
    }
    f->ptr = 0;
}

// Architectural registers
typedef enum { REG_G0, REG_G1, REG_G2, REG_G3, REG_G4, REG_G5, REG_SIZE } REG;

// Operand for a not-yet-issued (aka static) instruction
typedef struct {
    bool is_immediate;
    union {
        REG src;
        int value;
    };
} statik_op;
statik_op imm(int val) {
    statik_op op;
    op.is_immediate = true;
    op.value = val;
    return op;
}
statik_op reg(REG r) {
    statik_op op;
    op.is_immediate = false;
    op.src = r;
    return op;
}

typedef enum { OC_ADD, OC_MUL } OC;

// A not yet issued instruction
typedef struct {
    OC opcode;
    REG dst;
    statik_op lhs;
    statik_op rhs;
} statik_insn;

// An issued instruction
typedef struct {
    OC opcode;
    future_int result;
    future_int lhs;
    future_int rhs;
} issued_insn;

// Reorder buffer entry
typedef struct {
    future_int value;
    REG dst;
} writeback;

// Commitment register file
int crf[REG_SIZE];
// Register alias table
future_int rat[REG_SIZE];
// Instruction window
statik_insn insn_wnd[4];
// Reservation station
issued_insn res_stn[4];
// Reorder buffer
writeback rob[4];

// Resolve a static operand to a future by reading the register alias table
future_int resolve_statik(statik_op op) {
    if (op.is_immediate) {
        return make_now_int(op.value);
    } else {
        return anticipate(rat[op.src]);
    }
}

void initialize() {
    printf("Enter single character seed: ");
    srand(getc(stdin));
    for(unsigned i = 0; i < REG_SIZE; i++) {
        crf[i] = i;
        rat[i] = make_now_int(i);
    }
}

// issue instruction at index i from the instruction window
void issue(unsigned i) {
    // Fill reservation station
    res_stn[i] = (issued_insn) {
        .opcode = insn_wnd[i].opcode,
        .result = make_future_int(),
        .lhs = resolve_statik(insn_wnd[i].lhs),
        .rhs = resolve_statik(insn_wnd[i].rhs)
    };
    //
    release(&rat[insn_wnd[i].dst]);
    rat[insn_wnd[i].dst] = anticipate(res_stn[i].result);
    rob[i] = (writeback) {
        .value = anticipate(res_stn[i].result),
        .dst = insn_wnd[i].dst
    };
}

// execute instruction at index i in the resevation station
void execute(unsigned i) {
    if (is_ready(res_stn[i].lhs)
     && is_ready(res_stn[i].rhs)) {
        switch(res_stn[i].opcode) {
        case OC_ADD:
            put_value(res_stn[i].result,
                get_value(res_stn[i].lhs)
              + get_value(res_stn[i].rhs)
            );
            break;
        case OC_MUL:
            put_value(res_stn[i].result,
                get_value(res_stn[i].lhs)
              * get_value(res_stn[i].rhs)
            );
            break;
        }
    }
}

// Commit the writeback at index i of the reorder buffer
void commit(unsigned i) {
    crf[rob[i].dst] = get_value(rob[i].value);
}

// [min, max]
int random(int min, int max){
   return min + rand() / (RAND_MAX / (max - min + 1) + 1);
}

int main() {
    initialize();
    insn_wnd[0] = (statik_insn) {.opcode = OC_MUL, .lhs = imm(42),     .rhs = reg(REG_G2), .dst = REG_G0}; // g0 <- 42 * 2
    insn_wnd[1] = (statik_insn) {.opcode = OC_ADD, .lhs = reg(REG_G0), .rhs = reg(REG_G3), .dst = REG_G4}; // g4 <- 84 + 3
    insn_wnd[2] = (statik_insn) {.opcode = OC_MUL, .lhs = reg(REG_G4), .rhs = reg(REG_G2), .dst = REG_G1}; // g1 <- 87 * 2
    insn_wnd[3] = (statik_insn) {.opcode = OC_ADD, .lhs = reg(REG_G1), .rhs = reg(REG_G1), .dst = REG_G1}; // g1 <- 174 + 174
    
    // Issue in-order
    issue(0);
    issue(1);
    issue(2);
    issue(3);

    bool all_finished = true;
    do {
        // Execute in random order
        unsigned to_exe = random(0, 3);
        execute(to_exe);
        printf("Executing insn#%d\n", to_exe);
        
        all_finished = true;
        for(unsigned i = 0; i < 4; i++) {
            all_finished &= is_ready(res_stn[i].result);
        }
    } while (!all_finished);

    // Commit in-order
    commit(0);
    commit(1);
    commit(2);
    commit(3);

    // Print results
    for(unsigned i = 0; i < REG_SIZE; i++) {
        printf("g%d = %d\n", i, crf[i]);
    }
    return 0;
}