#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 **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=3;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=3;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);
	}
}