#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "s3inst.h"
#include "functions.h"

extern inst_t instList;
extern int count;

usedef_t *table;

int firstInstruction() {

    int index;
    inst_t current = instList;

    while (!(current->label))
        current = current->next;

    index = current->count;

    return index;
}

void unionArrays(int *destArray, int *srcArray, int numRegs) {

    int i;

    for (i = 0; i < numRegs; i++) {
        if (srcArray[i] == 1)
            destArray[i] = 1;
    }

    return;
}

int compareArrays(int *firstArray, int *secondArray, int numRegs) {

    int i;

    for (i = 0; i < numRegs; i++) {
        if (secondArray[i] != firstArray[i])
            return 1;
    }
    return 0;
}

void copyArray(int *firstArray, int *secondArray, int numRegs) {

    int i;

    for (i = 0; i < numRegs; i++) {
        secondArray[i] = firstArray[i];
    }

    return;
}

void genUseDef() {
    inst_t current = instList;

    while (current != NULL) {
        if (current->op == OP_BR) {
            if (current->ops[0].t == op_reg)
                table[current->count].use0 = current->ops[0].reg;
        } else if (current->op == OP_STR) {
            if (current->ops[0].t == op_reg)
                table[current->count].use0 = current->ops[0].reg;
            if (current->ops[1].t == op_reg)
                table[current->count].use1 = current->ops[1].reg;
        } else if (current->op == OP_IN) {
            table[current->count].def = 0;
        } else if (current->op == OP_OUT) {
            table[current->count].use0 = 0;
        } else if (current->op == OP_SET) {
            table[current->count].def = current->ops[0].reg;
        } else if (current->op != OP_BRA && current->op != OP_RET) {
            if (current->ops[0].t == op_reg)
                table[current->count].def = current->ops[0].reg;
            if (current->ops[1].t == op_reg)
                table[current->count].use0 = current->ops[1].reg;
            if (current->ops[2].t == op_reg)
                table[current->count].use1 = current->ops[2].reg;
        }

        current = current->next;
    }
}

void successors(block_array *cfg) {

    block *node = cfg->label_list[0];
    int curr_index = 0;
    int i;

    while (node != NULL) {

        if (node->instruction->label) {
            for (i = 0; i < cfg->num_of_labels; i++) {
                if (strcmp(cfg->label_list[i]->instruction->label, node->instruction->label) == 0) {
                    curr_index = i;
                    break;
                }
            }
        }

        if (node->instruction->op == OP_BR) {
            table[node->instruction->count].succ0 = node->left->instruction->count;
            table[node->instruction->count].succ1 = node->right->instruction->count;
            node = node->right;
        } else if (node->instruction->op == OP_RET) {
            table[node->instruction->count].succ0 = -1;
            table[node->instruction->count].succ1 = -1;
            break;
        } else if (node->instruction->op == OP_BRA) {
            table[node->instruction->count].succ0 = node->left->instruction->count;
            table[node->instruction->count].succ1 = -1;
            node = cfg->label_list[curr_index + 1];
        } else {
            table[node->instruction->count].succ0 = node->left->instruction->count;
            table[node->instruction->count].succ1 = -1;
            node = node->left;
        }
    }

    return;
}

void liveness() {
    int i, j;
    int changed = 1;
    int numRegs = number_of_registers();
    int firstIndex = firstInstruction();

    int **liveInArray, **liveOutArray;
    int *temp;

    instr_set* liveIn;
    instr_set* liveOut;

    liveIn = (instr_set*) malloc(count * sizeof (instr_set));
    liveOut = (instr_set*) malloc(count * sizeof (instr_set));

    liveInArray = (int**) malloc(count * sizeof (int*));
    liveOutArray = (int**) malloc(count * sizeof (int*));
    temp = (int*) calloc(numRegs, sizeof (int));

    for (i = 0; i < count; i++) {
        liveInArray[i] = (int*) calloc(numRegs, sizeof (int));
        liveOutArray[i] = (int*) calloc(numRegs, sizeof (int));
    }


    while (changed == 1) // iterate while no changes made
    {
        changed = 0;

        // calc live ins
        for (i = firstIndex; i < count; i++) // iterate through all instructions
        {
            copyArray(liveOutArray[i], temp, numRegs); // make temp array

            temp[table[i].def] = 0;

            if (table[i].use0 != -1)
                temp[table[i].use0] = 1;
            if (table[i].use1 != -1)
                temp[table[i].use1] = 1;

            changed = compareArrays(liveOutArray[i], temp, numRegs);

            copyArray(temp, liveInArray[i], numRegs);
        }

        // calc live outs
        for (i = firstIndex; i < count; i++) // iterate through all instructions
        {
            for (j = 0; j < numRegs; j++) // clear array
                temp[j] = 0;

            if (table[i].succ0 != -1)
                unionArrays(temp, liveInArray[table[i].succ0], numRegs);
            if (table[i].succ1 != -1)
                unionArrays(temp, liveInArray[table[i].succ1], numRegs);

            if (compareArrays(liveOutArray[i], temp, numRegs) == 1)
                changed = 1;

            copyArray(temp, liveOutArray[i], numRegs);
        }
    }

}

void calcLiveness(block_array* cfg) {
    int i;

    table = (usedef_t*) malloc(count * sizeof (usedef_t));

    for (i = 0; i < count; i++) {
        table[i].use0 = -1;
        table[i].use1 = -1;
        table[i].def = -1;
        table[i].succ0 = -1;
        table[i].succ1 = -1;
    }

    genUseDef();
    successors(cfg);

    liveness();

    for (i = 3; i < count; i++) {
        printf("%03d: use0: %02d use1: %02d def: %02d succ0: %02d succ1: %02d\n",
                i, table[i].use0, table[i].use1, table[i].def, table[i].succ0, table[i].succ1);
    }
}