Simulating Forwarding and Pipelining Processes in MIPS and C Programming
#include
#include
#include
#include
#define MAX_LABEL_LEN 32
#define MAX_LABELS 100
#define MAX_INSTRUCTIONS 1000
#define MAX_MEMORY 32
#define MAX_OP_LINE 50
#define MAX_LINE 100
#define I_CACHE_BLOCKS 4
#define I_CACHE_BLKSIZE 8
#define D_CACHE_BLOCKS 4
#define D_CACHE_BLKSIZE 4
#define MEM_DELAY 3
#define WRITE_BUFFER_SIZE 100
enum
{
INVALID=-1, NOP=0, J, BEQ, BNE, LI,
AND, ANDI, OR, ORI, LW, SW, ADD,
ADDI, SUB, SUBI, MULT, MULTI, HLT
};
enum {
IF_ID, ID_EX1, EX1_EX2, EX2_EX3, EX3_MEM, MEM_WB, LAST
};
char *instructions[] =
{
"NOP", "J", "BEQ", "BNE", "LI", "AND", "ANDI", "OR", "ORI",
"LW", "SW", "ADD", "ADDI", "SUB", "SUBI", "MULT", "MULTI", "HLT"
};
int ninstructions = 18;
typedef struct
{
char name[MAX_LABEL_LEN];
int addr;
}label_t;
typedef struct
{
int label;
int opcode;
int rdest;
int rsrc;
int rsrc2;
int imm;
int addr;
int ex_stages;
int wb;
int mem_rd;
int mem_wr;
int mem_data;
int mem_addr;
int PC;
int rsrc_req;
int rsrc2_req;
int rsrc_val;
int rsrc2_val;
int rdest_val;
int if_cycle;
int id_cycle;
int ex_cycle;
int mem_cycle;
int wb_cycle;
int stalled;
}inst_t;
inst_t nop;
/* Label table*/
label_t labels[MAX_LABELS];
int nlabels;
/* Instruction table */
inst_t inst_table[MAX_INSTRUCTIONS];
int ninst;
/* register file */
int registers[32];
/* Data memory */
int memory[MAX_MEMORY];
int mem_size;
/* cache definitions */
typedef struct
{
int valid;
int tag;
inst_t data[I_CACHE_BLKSIZE];
}i_cache_entry_t;
typedef struct
{
int valid;
int tag;
int data[D_CACHE_BLKSIZE];
}d_cache_entry_t;
/* instruction cache */
i_cache_entry_t i_cache[I_CACHE_BLOCKS];
int i_cache_accesses = 0;
int i_cache_hits = 0;
int i_cache_reading = 0;
int i_cache_index;
int i_cache_offset;
int i_cache_mem_addr;
/* data cache */
d_cache_entry_t d_cache[D_CACHE_BLOCKS];
int d_cache_accesses = 0;
int d_cache_hits = 0;
int d_cache_reading = 0;
int d_cache_index;
int d_cache_offset;
int d_cache_mem_addr;
int d_cache_writing = 0;
int d_cache_index_w;
int d_cache_offset_w;
int d_cache_mem_addr_w;
/* Write buffer */
typedef struct
{
int addr;
int data;
}buffer_entry_t;
buffer_entry_t write_buffer[WRITE_BUFFER_SIZE];
int buffer_pos = 0;
int buffer_updating = 0;
/* Instruction statistics */
typedef struct
{
int pos;
char line[MAX_LINE];
}stats_entry_t;
stats_entry_t stats[MAX_INSTRUCTIONS];
int n_stats = 0;
/* Remove whitespace at start and end of string */
char *trim(char *str)
{
char *ptr = str, *end;
while (*ptr && isspace(*ptr))
ptr++;
if (!(*ptr))
return ptr;
end = &str[strlen(str) - 1];
while(end != ptr && isspace(*end))
end--;
end[1] = 0;
return ptr;
}
/* Convert string to uppercase */
void str_to_upper(char *str)
{
char *ptr = str;
while(*ptr)
{
*ptr = toupper(*ptr);
ptr++;
}
}
/* get the pointer to the first space after the current word, inserts a zero
at the end of the word to separate it from the next one */
char *get_next_word(char *str)
{
char *ptr = str;
while(*ptr && !isspace(*ptr))
ptr++;
if (*ptr)
*(ptr++) = 0;
return ptr;
}
/* make a first pass on the input file by loading all labels on a label table */
void first_pass(FILE *input)
{
char buffer[BUFSIZ], *line;
int nline = 0;
while (!feof(input))
{
if (fgets(buffer, BUFSIZ, input))
{
line = trim(buffer);
if (line[0])
{
get_next_word(line);
if (line[strlen(line) - 1] == ':')
{
line[strlen(line) - 1] = 0;
strcpy(labels[nlabels].name, line);
labels[nlabels].addr = nline;
nlabels++;
}
nline++;
}
}
}
}
/* parse the operands for the instruction, which are separated by commas,
returns the number of operands or -1 if they are invalid or more than 3 */
int parse_operand(char *oper, char *operands[])
{
char *token;
int ntokens = 0;
token = strtok(oper, ",");
while(token)
{
if (ntokens >= 3)
return -1;
operands[ntokens] = trim(token);
ntokens++;
token = strtok(NULL, ",");
}
return ntokens;
}
/* Search for an instruction in the instruction table and returns the opcode */
int search_instruction(char *inst)
{
int i;
int opcode = INVALID;
for (i = 0; i < ninstructions; i++)
if (!strcmp(inst, instructions[i]))
{
opcode = i;
break;
}
return opcode;
}
/* Search for a label in the label table and returns the address */
int search_label(char *label)
{
int i;
int addr = INVALID;
for (i = 0; i < nlabels; i++)
if (!strcmp(label, labels[i].name))
{
addr = i;
break;
}
return addr;
}
/* checks if the string is a valid number, returns 1 if valid, 0 otherwise */
int valid_number(char *str)
{
char *ptr = str;
if (*ptr == '-')
{
str++;
ptr++;
}
while(*ptr)
{
if (!isdigit(*ptr))
return 0;
ptr++;
}
if (ptr != str)
return 1;
else
return 0;
}
/* Validates the string by checking if it corresponds to a valid register name */
int validate_register(char *sreg)
{
int reg = INVALID;
if (sreg[0]!='R')
return INVALID;
if (!valid_number(&sreg[1]))
return INVALID;
reg = atoi(&sreg[1]);
if (reg < 0 || reg >= 32)
return INVALID;
return reg;
}
/* Parses the J instruction with given operands */
inst_t parse_J(char *operands[], int nops, int nline)
{
int addr;
inst_t instruction;
if (nops != 1)
{
fprintf(stderr, "Incorrect number of operands for J instruction in line %d\n", nline);
exit(1);
}
addr = search_label(operands[0]);
if (addr == INVALID)
{
fprintf(stderr, "Unknown label for J instruction in line %d\n", nline);
exit(1);
}
instruction.opcode = J;
instruction.addr = addr;
return instruction;
}
/* Parses the branch instruction with given operands */
inst_t parse_B(int opcode, char *operands[], int nops, int nline)
{
inst_t instruction;
if (nops != 3)
{
fprintf(stderr, "Incorrect number of operands for %s instruction in line %d\n",
instructions[opcode], nline);
exit(1);
}
instruction.opcode = opcode;
instruction.addr = search_label(operands[2]);
if (instruction.addr == INVALID)
{
fprintf(stderr, "Unknown label for %s instruction in line %d\n",
instructions[opcode], nline);
exit(1);
}
instruction.rsrc = validate_register(operands[0]);
if (instruction.rsrc == INVALID)
{
fprintf(stderr, "Invalid source register for %s instruction in line %d\n",
instructions[opcode], nline);
exit(1);
}
instruction.rsrc2 = validate_register(operands[1]);
if (instruction.rsrc2 == INVALID)
{
fprintf(stderr, "Invalid source register for %s instruction in line %d\n",
instructions[opcode], nline);
exit(1);
}
return instruction;
}
/* Parses the LI instruction with given operands */
inst_t parse_LI(char *operands[], int nops, int nline)
{
inst_t instruction;
if (nops != 2)
{
fprintf(stderr, "Incorrect number of operands for LI instruction in line %d\n", nline);
exit(1);
}
instruction.opcode = LI;
instruction.rdest = validate_register(operands[0]);
if (instruction.rdest == INVALID)
{
fprintf(stderr, "Invalid register for LI instruction in line %d\n", nline);
exit(1);
}
if (!valid_number(operands[1]))
{
fprintf(stderr, "Invalid immediate value for LI instruction in line %d\n", nline);
exit(1);
}
instruction.imm = atoi(operands[1]);
return instruction;
}
/* Parses the register arithmetic/logic instruction with given operands */
inst_t parse_R(int opcode, char *operands[], int nops, int nline)
{
inst_t instruction;
if (nops != 3)
{
fprintf(stderr, "Incorrect number of operands for %s instruction in line %d\n",
instructions[opcode], nline);
exit(1);
}
instruction.opcode = opcode;
instruction.rdest = validate_register(operands[0]);
if (instruction.rdest == INVALID)
{
fprintf(stderr, "Invalid destination register for %s instruction in line %d\n",
instructions[opcode], nline);
exit(1);
}
instruction.rsrc = validate_register(operands[1]);
if (instruction.rsrc == INVALID)
{
fprintf(stderr, "Invalid source register for %s instruction in line %d\n",
instructions[opcode], nline);
exit(1);
}
instruction.rsrc2 = validate_register(operands[2]);
if (instruction.rsrc2 == INVALID)
{
fprintf(stderr, "Invalid source register for %s instruction in line %d\n",
instructions[opcode], nline);
exit(1);
}
return instruction;
}
/* Parses the immediate arithmetic/logic instruction with given operands */
inst_t parse_I(int opcode, char *operands[], int nops, int nline)
{
inst_t instruction;
if (nops != 3)
{
fprintf(stderr, "Incorrect number of operands for %s instruction in line %d\n",
instructions[opcode], nline);
exit(1);
}
instruction.opcode = opcode;
instruction.rdest = validate_register(operands[0]);
if (instruction.rdest == INVALID)
{
fprintf(stderr, "Invalid destination register for %s instruction in line %d\n",
instructions[opcode], nline);
exit(1);
}
instruction.rsrc = validate_register(operands[1]);
if (instruction.rsrc == INVALID)
{
fprintf(stderr, "Invalid source register for %s instruction in line %d\n",
instructions[opcode], nline);
exit(1);
}
if (!valid_number(operands[2]))
{
fprintf(stderr, "Invalid immediate value for %s instruction in line %d\n",
instructions[opcode], nline);
exit(1);
}
instruction.imm = atoi(operands[2]);
return instruction;
}
/* Parses the memory instruction with given operands */
inst_t parse_M(int opcode, char *operands[], int nops, int nline)
{
int rsrc, rdest;
inst_t instruction;
char *end, *reg, *off;
if (nops != 2)
{
fprintf(stderr, "Incorrect number of operands for %s instruction in line %d\n",
instructions[opcode], nline);
exit(1);
}
instruction.opcode = opcode;
rdest = validate_register(operands[0]);
if (rdest == INVALID)
{
fprintf(stderr, "Invalid destination register for %s instruction in line %d\n",
instructions[opcode], nline);
exit(1);
}
if (opcode == LW)
instruction.rdest = rdest;
else
instruction.rsrc = rdest;
end = &operands[1][strlen(operands[1])-1];
if (*end != ')')
{
fprintf(stderr, "Invalid format for %s instruction in line %d\n",
instructions[opcode], nline);
exit(1);
}
*(end--) = 0;
while(end > operands[1] && *end != '(')
end--;
if (*end != '(' || end <= operands[1])
{
fprintf(stderr, "Invalid format for %s instruction in line %d\n",
instructions[opcode], nline);
exit(1);
}
*end = 0;
reg = trim(end + 1);
rsrc = validate_register(reg);
if (rsrc == INVALID)
{
fprintf(stderr, "Invalid base register for %s instruction in line %d\n",
instructions[opcode], nline);
exit(1);
}
if (opcode == LW)
instruction.rsrc = rsrc;
else
instruction.rsrc2 = rsrc;
off = operands[1];
if (!valid_number(off))
{
fprintf(stderr, "Invalid offset value for %s instruction in line %d\n",
instructions[opcode], nline);
exit(1);
}
instruction.imm = atoi(off);
return instruction;
}
/* Parses the HLT instruction with given operands */
inst_t parse_HLT(char *operands[], int nops, int nline)
{
inst_t instruction;
if (nops != 0)
{
fprintf(stderr, "Incorrect number of operands for HLT instruction in line %d\n", nline);
exit(1);
}
instruction.opcode = HLT;
return instruction;
}
/* Parses the instruction with the name inst and operands oper, returns a
inst_t structure with the opcode and operands of instruction */
inst_t parse_instruction(char *inst, char *oper, int nline)
{
int opcode, nops;
char *operands[3];
inst_t instruction;
opcode = search_instruction(inst);
if (opcode == INVALID)
{
fprintf(stderr, "Invalid instruction %s found in line %d\n", inst, nline);
exit(1);
}
nops = parse_operand(oper, operands);
if (nops == INVALID)
{
fprintf(stderr, "Too many operands for instruction %s in line %d\n",
instructions[opcode], nline);
exit(1);
}
switch(opcode)
{
case J:
instruction = parse_J(operands, nops, nline);
instruction.rsrc_req = 0;
instruction.rsrc2_req = 0;
break;
case BEQ:
case BNE:
instruction = parse_B(opcode, operands, nops, nline);
instruction.rsrc_req = 1;
instruction.rsrc2_req = 1;
break;
case LI:
instruction = parse_LI(operands, nops, nline);
instruction.rsrc_req = 0;
instruction.rsrc2_req = 0;
break;
case AND:
case OR:
case ADD:
case SUB:
case MULT:
instruction = parse_R(opcode, operands, nops, nline);
instruction.rsrc_req = 1;
instruction.rsrc2_req = 1;
break;
case ANDI:
case ORI:
case ADDI:
case SUBI:
case MULTI:
instruction = parse_I(opcode, operands, nops, nline);
instruction.rsrc_req = 1;
instruction.rsrc2_req = 0;
break;
case LW:
instruction = parse_M(opcode, operands, nops, nline);
instruction.rsrc_req = 1;
instruction.rsrc2_req = 0;
break;
case SW:
instruction = parse_M(opcode, operands, nops, nline);
instruction.rsrc_req = 1;
instruction.rsrc2_req = 1;
break;
case HLT:
instruction = parse_HLT(operands, nops, nline);
instruction.rsrc_req = 0;
instruction.rsrc2_req = 0;
break;
}
switch(opcode)
{
case J:
case BEQ:
case BNE:
case LI:
case HLT:
instruction.ex_stages = 0;
break;
case AND:
case OR:
case ANDI:
case ORI:
case LW:
case SW:
instruction.ex_stages = 1;
break;
case ADD:
case SUB:
case ADDI:
case SUBI:
instruction.ex_stages = 2;
break;
case MULT:
case MULTI:
instruction.ex_stages = 3;
break;
}
instruction.stalled = 0;
return instruction;
}
/* makes a second pass to parse all instructions, save them on the instruction table
translating all label references to addresses */
void second_pass(FILE *input)
{
char buffer[BUFSIZ], *line;
char *next, *inst, *oper;
int nline = 1;
inst_t instruction;
int lbl;
ninst = 0;
while (!feof(input))
{
if (fgets(buffer, BUFSIZ, input))
{
line = trim(buffer);
if (line[0])
{
str_to_upper(line);
next = get_next_word(line);
if (line[strlen(line) - 1] == ':')
{
line[strlen(line) - 1] = 0;
lbl = search_label(line);
inst = trim(next);
oper = get_next_word(inst);
}
else
{
lbl = -1;
inst = line;
oper = trim(next);
}
instruction = parse_instruction(inst, oper, nline);
instruction.label = lbl;
inst_table[ninst++] = instruction;
}
nline++;
}
}
}
/* Loads all the instructions from the given file into the instruction table */
void load_instructions(char *filename)
{
FILE *input;
input = fopen(filename, "rt");
if (input == NULL)
{
fprintf(stderr, "Unable to open instruction file \"%s\"\n", filename);
exit(1);
}
first_pass(input);
rewind(input);
second_pass(input);
fclose(input);
}
/* Loads all the memory data from the given file */
void load_memory_data(char *filename)
{
FILE *input;
char buffer[BUFSIZ], *line;
int data, bit;
input = fopen(filename, "rt");
if (input == NULL)
{
fprintf(stderr, "Unable to open memory file \"%s\"\n", filename);
exit(1);
}
while (!feof(input))
{
if (fgets(buffer, BUFSIZ, input))
{
line = trim(buffer);
if (line[0])
{
if (strlen(line)!=32)
{
fprintf(stderr, "Invalid word size found in memory file\n");
exit(1);
}
data = 0;
for (bit=0; bit<32; bit++)
{
if (line[bit] != '0' && line[bit] != '1')
{
fprintf(stderr, "Invalid bit value found in memory file\n");
exit(1);
}
data = (data << 1) | (line[bit] - '0');
}
memory[mem_size++] = data;
}
}
}
fclose(input);
}
/* save the instruction stats */
void save_instruction_stats(inst_t inst)
{
char label[MAX_LABEL_LEN + 2];
char ops[MAX_OP_LINE];
char cycles[5][MAX_OP_LINE];
stats_entry_t stat;
int i, j;
if (inst.label != INVALID)
sprintf(label, "%s:",labels[inst.label].name);
else
sprintf(label, " ");
switch(inst.opcode)
{
case J:
sprintf(ops, "%s", labels[inst.addr].name);
inst.ex_cycle = 0;
inst.mem_cycle = 0;
inst.wb_cycle = 0;
break;
case BEQ:
case BNE:
sprintf(ops, "R%d, R%d, %s", inst.rsrc, inst.rsrc2, labels[inst.addr].name);
inst.ex_cycle = 0;
inst.mem_cycle = 0;
inst.wb_cycle = 0;
break;
case LI:
sprintf(ops, "R%d, %d", inst.rdest, inst.imm);
break;
case AND:
case OR:
case ADD:
case SUB:
case MULT:
sprintf(ops, "R%d, R%d, R%d", inst.rdest, inst.rsrc, inst.rsrc2);
break;
case ANDI:
case ORI:
case ADDI:
case SUBI:
case MULTI:
sprintf(ops, "R%d, R%d, %d", inst.rdest, inst.rsrc, inst.imm);
break;
case LW:
sprintf(ops, "R%d, %d(R%d)", inst.rdest, inst.imm, inst.rsrc);
break;
case SW:
sprintf(ops, "R%d, %d(R%d)", inst.rsrc, inst.imm, inst.rsrc2);
break;
case HLT:
sprintf(ops, " ");
inst.ex_cycle = 0;
inst.mem_cycle = 0;
inst.wb_cycle = 0;
break;
}
for (i = 0; i < 5; i++)
cycles[i][0] = 0;
if (inst.if_cycle != 0)
sprintf(cycles[0], "%-6d", inst.if_cycle);
if (inst.id_cycle != 0)
sprintf(cycles[1], "%-6d", inst.id_cycle);
if (inst.ex_cycle != 0)
sprintf(cycles[2], "%-6d", inst.ex_cycle);
if (inst.mem_cycle != 0)
sprintf(cycles[3], "%-6d", inst.mem_cycle);
if (inst.wb_cycle != 0)
sprintf(cycles[4], "%-6d", inst.wb_cycle);
sprintf(stat.line, "%-8s %-8s %-20s %s %s %s %s %s", label, instructions[inst.opcode],
ops, cycles[0], cycles[1], cycles[2], cycles[3], cycles[4]);
stat.pos = inst.if_cycle;
if (n_stats == 0)
stats[n_stats++] = stat;
else
{
for (i = 0; i < n_stats; i++)
{
if (stats[i].pos > stat.pos)
break;
}
for (j = n_stats; j>i; j--)
stats[j] = stats[j - 1];
stats[i] = stat;
n_stats++;
}
}
/* Simulates one cycle of an instruction cache read */
inst_t i_cache_read(int PC)
{
int tag = PC >> 5;
int index = (PC >> 3) & 0x3;
int offset = PC & 0x7;
int i;
if (!i_cache_reading)
{
i_cache_accesses++;
if (i_cache[index].valid && i_cache[index].tag == tag)
{
i_cache_hits++;
return i_cache[index].data[offset];
}
else
{
i_cache_reading = I_CACHE_BLKSIZE*MEM_DELAY;
i_cache_index = index;
i_cache_offset = offset;
i_cache_mem_addr = (PC >> 3) << 3;
i_cache[index].tag = tag;
return nop;
}
}
else
{
i_cache_reading--;
if (i_cache_reading == 0)
{
i_cache[i_cache_index].valid = 1;
for (i = 0; i < I_CACHE_BLKSIZE; i++)
i_cache[i_cache_index].data[i] = inst_table[i_cache_mem_addr + i];
return i_cache[i_cache_index].data[i_cache_offset];
}
else
return nop;
}
}
/* Simulates one cycle of a data cache read */
int d_cache_read(int addr, int *miss)
{
int real_addr;
int tag;
int index;
int offset;
int i;
real_addr = (addr - 0x100) >> 2;
tag = real_addr >> 4;
index = (real_addr >> 2) & 0x3;
offset = real_addr & 0x3;
if (!d_cache_reading)
{
d_cache_accesses++;
if (d_cache[index].valid && d_cache[index].tag == tag)
{
d_cache_hits++;
*miss = 0;
return d_cache[index].data[offset];
}
else
{
d_cache_reading = D_CACHE_BLKSIZE*MEM_DELAY+1;
d_cache_index = index;
d_cache_offset = offset;
d_cache_mem_addr = (real_addr >> 2) << 2;
d_cache[index].tag = tag;
*miss = 1;
return 0;
}
}
else
{
if (!i_cache_reading && !d_cache_writing)
d_cache_reading--;
if (d_cache_reading == 0)
{
d_cache[d_cache_index].valid = 1;
for (i = 0; i < D_CACHE_BLKSIZE; i++)
d_cache[d_cache_index].data[i] = memory[d_cache_mem_addr + i];
*miss = 0;
return d_cache[d_cache_index].data[d_cache_offset];
}
else
{
*miss = 1;
return 0;
}
}
}
/* Simulates one cycle of a data cache write */
int d_cache_write(int val, int addr)
{
int real_addr;
int tag;
int index;
int offset;
int i;
real_addr = (addr - 0x100) >> 2;
tag = real_addr >> 4;
index = (real_addr >> 2) & 0x3;
offset = real_addr & 0x3;
if (!d_cache_writing)
{
d_cache_accesses++;
if (d_cache[index].valid && d_cache[index].tag == tag)
{
d_cache_hits++;
d_cache[index].data[offset] = val;
write_buffer[buffer_pos].data = val;
write_buffer[buffer_pos].addr = real_addr;
buffer_pos++;
return 0;
}
else
{
d_cache_writing = D_CACHE_BLKSIZE*MEM_DELAY+1;
d_cache_index_w = index;
d_cache_offset_w = offset;
d_cache_mem_addr_w = (real_addr >> 2) << 2;
d_cache[index].tag = tag;
return 1;
}
}
else
{
if (!i_cache_reading)
d_cache_writing--;
if (d_cache_writing == 0)
{
d_cache[d_cache_index_w].valid = 1;
for (i = 0; i < D_CACHE_BLKSIZE; i++)
d_cache[d_cache_index_w].data[i] = memory[d_cache_mem_addr_w + i];
d_cache[d_cache_index_w].data[d_cache_offset_w] = val;
write_buffer[buffer_pos].data = val;
write_buffer[buffer_pos].addr = d_cache_mem_addr_w;
buffer_pos++;
return 0;
}
else
return 1;
}
}
/* updates the memory using the write buffer one word at a time */
void update_memory()
{
int i;
if (!i_cache_reading && !d_cache_reading && !d_cache_writing)
{
if (!buffer_updating && buffer_pos)
buffer_updating = 3;
else
{
buffer_updating--;
if (buffer_updating == 0)
{
memory[write_buffer[0].addr] = write_buffer[0].data;
buffer_pos--;
for (i = 0; i < buffer_pos; i++)
write_buffer[i] = write_buffer[i + 1];
}
}
}
}
/* Simulates the execution of the instruction */
inst_t execute(inst_t inst)
{
inst.PC = 0;
inst.wb = 1;
inst.mem_rd = 0;
inst.mem_wr = 0;
switch (inst.opcode)
{
case J:
inst.PC = labels[inst.addr].addr;
inst.wb = 0;
break;
case BEQ:
if (inst.rsrc_val == inst.rsrc2_val)
inst.PC = labels[inst.addr].addr;
inst.wb = 0;
break;
case BNE:
if (inst.rsrc_val != inst.rsrc2_val)
inst.PC = labels[inst.addr].addr;
inst.wb = 0;
break;
case LI:
inst.rdest_val = inst.imm;
break;
case AND:
inst.rdest_val = inst.rsrc_val & inst.rsrc2_val;
break;
case OR:
inst.rdest_val = inst.rsrc_val | inst.rsrc2_val;
break;
case ADD:
inst.rdest_val = inst.rsrc_val + inst.rsrc2_val;
break;
case SUB:
inst.rdest_val = inst.rsrc_val - inst.rsrc2_val;
break;
case MULT:
inst.rdest_val = inst.rsrc_val * inst.rsrc2_val;
break;
case ANDI:
inst.rdest_val = inst.rsrc_val & inst.imm;
break;
case ORI:
inst.rdest_val = inst.rsrc_val | inst.imm;
break;
case ADDI:
inst.rdest_val = inst.rsrc_val + inst.imm;
break;
case SUBI:
inst.rdest_val = inst.rsrc_val - inst.imm;
break;
case MULTI:
inst.rdest_val = inst.rsrc_val * inst.imm;
break;
case LW:
inst.mem_rd = 1;
inst.mem_addr = inst.rsrc_val + inst.imm;
break;
case SW:
inst.wb = 0;
inst.mem_wr = 1;
inst.mem_data = inst.rsrc_val;
inst.mem_addr = inst.rsrc2_val + inst.imm;
break;
case HLT:
case NOP:
inst.wb = 0;
break;
}
return inst;
}
/* Simulate the loaded program */
void simulate()
{
int PC;
int halted, stalled;
inst_t pipeline[7];
int i, cycles = 0;
int enable_if, miss, data, slot;
nop.opcode = NOP;
nop.rdest = INVALID;
nop.rsrc = INVALID;
nop.rsrc2 = INVALID;
nop.rsrc_req = 0;
nop.rsrc2_req = 0;
nop.wb = 0;
nop.if_cycle = 0;
nop.ex_stages = 0;
nop.stalled = 0;
for(i=0; i<7; i++)
pipeline[i] = nop;
PC = 0;
halted = 0;
stalled = 0;
enable_if = 1;
while (!halted)
{
if (pipeline[ID_EX1].opcode != HLT && enable_if && !stalled)
{
pipeline[IF_ID] = i_cache_read(PC);
if (pipeline[IF_ID].opcode != NOP)
{
pipeline[IF_ID].if_cycle = cycles + 1;
pipeline[IF_ID].id_cycle = 0;
pipeline[IF_ID].ex_cycle = 0;
pipeline[IF_ID].mem_cycle = 0;
pipeline[IF_ID].wb_cycle = 0;
pipeline[IF_ID].stalled = 0;
PC++;
}
}
pipeline[ID_EX1].stalled = 0;
if (pipeline[ID_EX1].opcode == HLT)
enable_if = 0;
slot =(pipeline[ID_EX1].ex_stages == 0)? 1 : 0;
if(pipeline[ID_EX1].rsrc_req)
{
if (pipeline[ID_EX1].rsrc == pipeline[EX1_EX2].rdest)
{
if (pipeline[EX1_EX2].ex_stages <= 1 - slot && !pipeline[EX1_EX2].mem_rd)
pipeline[ID_EX1].rsrc_val = pipeline[EX1_EX2].rdest_val;
else
pipeline[ID_EX1].stalled = 1;
}
else if (pipeline[ID_EX1].rsrc == pipeline[EX2_EX3].rdest)
{
if (pipeline[EX2_EX3].ex_stages <= 2 - slot && !pipeline[EX2_EX3].mem_rd)
pipeline[ID_EX1].rsrc_val = pipeline[EX2_EX3].rdest_val;
else
pipeline[ID_EX1].stalled = 1;
}
else if (pipeline[ID_EX1].rsrc == pipeline[EX3_MEM].rdest)
{
if (!pipeline[EX3_MEM].mem_rd)
pipeline[ID_EX1].rsrc_val = pipeline[EX3_MEM].rdest_val;
else
pipeline[ID_EX1].stalled = 1;
}
else if (pipeline[ID_EX1].rsrc == pipeline[MEM_WB].rdest)
{
if (!pipeline[MEM_WB].mem_rd)
pipeline[ID_EX1].rsrc_val = pipeline[MEM_WB].rdest_val;
else
pipeline[ID_EX1].stalled = 1;
}
else if (pipeline[ID_EX1].rsrc == pipeline[LAST].rdest)
pipeline[ID_EX1].rsrc_val = pipeline[LAST].rdest_val;
else
pipeline[ID_EX1].rsrc_val = registers[pipeline[ID_EX1].rsrc];
}
if(pipeline[ID_EX1].rsrc2_req)
{
if (pipeline[ID_EX1].rsrc2 == pipeline[EX1_EX2].rdest)
{
if (pipeline[EX1_EX2].ex_stages <= 1 -slot && !pipeline[EX1_EX2].mem_rd)
pipeline[ID_EX1].rsrc2_val = pipeline[EX1_EX2].rdest_val;
else
pipeline[ID_EX1].stalled = 1;
}
else if (pipeline[ID_EX1].rsrc2 == pipeline[EX2_EX3].rdest)
{
if (pipeline[EX2_EX3].ex_stages <= 2-slot && !pipeline[EX2_EX3].mem_rd)
pipeline[ID_EX1].rsrc2_val = pipeline[EX2_EX3].rdest_val;
else
pipeline[ID_EX1].stalled = 1;
}
else if (pipeline[ID_EX1].rsrc2 == pipeline[EX3_MEM].rdest)
{
if (!pipeline[EX3_MEM].mem_rd)
pipeline[ID_EX1].rsrc2_val = pipeline[EX3_MEM].rdest_val;
else
pipeline[ID_EX1].stalled = 1;
}
else if (pipeline[ID_EX1].rsrc2 == pipeline[MEM_WB].rdest)
{
if (!pipeline[MEM_WB].mem_rd)
pipeline[ID_EX1].rsrc2_val = pipeline[MEM_WB].rdest_val;
else
pipeline[ID_EX1].stalled = 1;
}
else if (pipeline[ID_EX1].rsrc2 == pipeline[LAST].rdest)
pipeline[ID_EX1].rsrc2_val = pipeline[LAST].rdest_val;
else
pipeline[ID_EX1].rsrc2_val = registers[pipeline[ID_EX1].rsrc2];
}
if (!pipeline[ID_EX1].stalled)
{
pipeline[ID_EX1] = execute(pipeline[ID_EX1]);
if (pipeline[ID_EX1].PC)
{
PC = pipeline[ID_EX1].PC;
save_instruction_stats(pipeline[IF_ID]);
pipeline[IF_ID] = nop;
}
}
pipeline[ID_EX1].id_cycle = cycles + 1;
pipeline[EX1_EX2].stalled = 0;
pipeline[EX1_EX2].ex_cycle = cycles + 1;
pipeline[EX2_EX3].stalled = 0;
pipeline[EX2_EX3].ex_cycle = cycles + 1;
pipeline[EX3_MEM].stalled = 0;
pipeline[EX3_MEM].ex_cycle = cycles + 1;
pipeline[MEM_WB].stalled = 0;
if (pipeline[MEM_WB].mem_wr)
{
data = d_cache_write(pipeline[MEM_WB].mem_data, pipeline[MEM_WB].mem_addr);
if (miss)
pipeline[MEM_WB].stalled = 1;
}
else if (pipeline[MEM_WB].mem_rd)
{
data = d_cache_read(pipeline[MEM_WB].mem_addr, &miss);
if (!miss)
{
pipeline[MEM_WB].rdest_val = data;
pipeline[MEM_WB].mem_rd = 0;
}
else
pipeline[MEM_WB].stalled = 1;
}
pipeline[MEM_WB].mem_cycle = cycles + 1;
pipeline[LAST].stalled = 0;
if (pipeline[LAST].wb)
registers[pipeline[LAST].rdest] = pipeline[LAST].rdest_val;
pipeline[LAST].wb_cycle = cycles + 1;
if (pipeline[LAST].opcode != NOP)
{
save_instruction_stats(pipeline[LAST]);
if (pipeline[LAST].opcode == HLT)
halted = 1;
pipeline[LAST] = nop;
}
update_memory();
/* Advance pipeline */
stalled = 0;
for (i = 6; i > 0; i--)
{
if(pipeline[i].opcode == NOP)
stalled = 0;
if (!pipeline[i-1].stalled)
{
if (!stalled)
{
pipeline[i] = pipeline[i-1];
pipeline[i-1] = nop;
}
}
else
stalled = 1;
}
cycles++;
}
}
/* Print the instruction statistics on a file */
void print_results(FILE *output)
{
int i;
for (i = 0; i < n_stats; i++)
fprintf(output, "%s\n", stats[i].line);
fprintf(output, "\nTotal number of access requests for instruction cache: %d\n",
i_cache_accesses);
fprintf(output, "Number of instruction cache hits: %d\n", i_cache_hits);
fprintf(output, "\nTotal number of access requests for data cache: %d\n",
d_cache_accesses);
fprintf(output, "Number of data cache hits: %d\n", d_cache_hits);
}
int main(int argc, char **argv)
{
FILE *output;
if (argc != 4)
{
printf("Invalid number of arguments!\n");
printf("Usage:\n");
printf(" %s inst.txt data.txt output.txt\n", argv[0]);
exit(1);
}
load_instructions(argv[1]);
load_memory_data(argv[2]);
simulate();
output = fopen(argv[3], "wt");
print_results(output);
fclose(output);
print_results(stdout);
return 0;
}