#include <stdlib.h>
#include <ctype.h> 
#include "flow.h"
#include "collections.h"
#include "x_stack.h"

/** Most of the functions here are wrappers around the 
generic graph functions, casting pointers to their correct types.
Other function provide some flow-graph specific functionality
such as determining liveness and edge-sets .*/

Graph flow_graph;

struct edge_set {
    BitSet parents;
    BitSet children;
    XStack x_stack;
    int depth;
};

int edgeset_depth(EdgeSet edges) {
    return edges->depth;
}

BitSet edgeset_parents(EdgeSet edges) {
    return edges->parents;
}

BitSet edgeset_children(EdgeSet edges) {
    return edges->children;
}

void flow_applyToBlocks(void (* func)(Block nodeData)) {
    int i;
    for(i = 0; i < flow_size(); i++) {
        func((Block)graph_node(flow_graph, i));
    }
}  

int flow_addBlock(Block block) {
    return graph_addNode(flow_graph, block);
}

void addEdge(int from, int to) {
    graph_addEdge(flow_graph, from, to);
}    

static void* wrapper(void* b1, void* b2) {
    return block_merge((Block)b1, (Block)b2);    
}

/** Closes the flow graph, see graph_close for effect.
Also sets ids of all blocks as contiguous numbers from 0 upwards. */
void flow_close() {
    int i, size;
    graph_close(flow_graph, wrapper);
    //Set IDs.
    size = flow_size();
    for(i = 0; i < size; i++) {
        block_setID((Block)graph_node(flow_graph, i), i);
    }
    write_log("Flow graph closed, size %d\n", size);
}

Block flow_block(int index) {
    return graph_node(flow_graph, index);
}

EdgeSet createEdgeSet() {
    EdgeSet set = allocate(sizeof(struct edge_set), FUNC);
    set->children = graph_newNodeSet(flow_graph, FUNC);
    set->parents = graph_newNodeSet(flow_graph, FUNC);
     return set;
}

/** Builds the edge set which contains the predecessor
edges to block with id of initialChild */
static EdgeSet buildEdgeSet(int initialChild) {
    BitSet newChildren, newParents;
    EdgeSet set;
    int next;
    if (set_empty(flow_parents(initialChild)))
        return NULL;
    newChildren = graph_newNodeSet(flow_graph, FUNC);
    newParents = graph_newNodeSet(flow_graph, FUNC);
    set = createEdgeSet();
    set_add(set->children, initialChild);
    set->depth = block_getStartEDepth(flow_block(initialChild));
    set_add(newChildren, initialChild);
    while (FIRST_IN(newChildren) >= 0) {
        while ((next = FIRST_IN(newChildren)) >= 0) {
            set_remove(newChildren, next);
            set_addSet(newParents, flow_parents(next));
        }
        set_removeSet(newParents, set->parents);
        set_addSet(set->parents, newParents);
        set_clear(newChildren);
        while ((next = FIRST_IN(newParents)) >= 0) {
            set_remove(newParents, next);
            set_addSet(newChildren, flow_children(next));
        }
        set_removeSet(newChildren, set->children);
        set_addSet(set->children, newChildren);
        set_clear(newParents);
    }
    return set;
}

/** Generates complete list of edge-sets for the flow graph */
ArrayList flow_edgeSets() {    
    int i, next;
    ArrayList list = list_new(flow_size() / 2);
    // Visit each edge in turn and add to one edge set or other...
    BitSet children = graph_newNodeSet(flow_graph, FUNC);
    int size = flow_size();
    for(i = 0; i < size; i++)
        set_add(children, i);
    while ((next = FIRST_IN(children)) >= 0) {
        EdgeSet set = buildEdgeSet(next);
        if (set == NULL) {
            set_remove(children, next);
        } else {
            list_add(list, set);
            set_removeSet(children, set->children);
        }
    }
    return list;
}

void flow_print(char* filename) {
    int i, size = flow_size();
    FILE* out = fopen(filename, "w");
    ArrayList edge_sets;
    if (out == NULL) {
        write_log("Unable to open %s, so no graph dump\n", filename);
        return;
    }
    for (i = 0; i < size; i++) {
        flow_printNode(i, out);
    }
    fprintf(out, "\n");
    edge_sets = flow_edgeSets();
    size = list_size(edge_sets);
    fprintf(out, "%d Edge sets\n", size);
    for(i = 0; i < size; i++) {
        edgeset_print((EdgeSet)list_get(edge_sets, i), out);
    }
    fclose(out);
}

void printTemps(FILE* out, BitSet set) {
    if (set) {
        int i;
        FOR_EACH(i, set) {
            fprintf(out, "%s ", localVariableSymbol(i)->name);
        }
    }
}

void flow_printNode(int i, FILE* out) {
    Block block = flow_block(i);
    fprintf(out, "Block %d\n", i);
    fprintf(out, "Parents ");
    set_print(out, graph_parents(flow_graph, i));
    fprintf(out, "\nLive in ");
    printTemps(out, block_livein(block));
    fprintf(out, "\nStart e-depth ");
    fprintf(out, "%d", block_getStartEDepth(block));
    fprintf(out, "\nStart l-depth ");
    fprintf(out, "%d", block_getStartLDepth(block));
    fprintf(out, "\nXStack in:");
    xstack_print(block_inStack(block), out);
    fprintf(out, "\nDefined ");
    printTemps(out, block_def(block));
    fprintf(out, "\nUsed ");
    printTemps(out, block_use(block));
    fprintf(out, "\nRejects ");
    printTemps(out, block_reject(block));
    fprintf(out, "\n");
    block_print(block, out);
    fprintf(out, "\nLive out ");
    printTemps(out, block_liveout(block));
    fprintf(out, "\nEnd l-depth ");
    fprintf(out, "%d", block_getEndLDepth(block));
    fprintf(out, "\nEnd e-depth ");
    fprintf(out, "%d", block_getEndEDepth(block));
    fprintf(out, "\nXStack out:");
    xstack_print(block_outStack(block), out);
    fprintf(out, "\nChildren ");
    set_print(out, graph_children(flow_graph, i));
    fprintf(out, "\n\n");
}

void edgeset_print(EdgeSet set, FILE* out) {
    fprintf(out, "\nParents ");
    set_print(out, set->parents);
    fprintf(out, "\nChildren ");
    set_print(out, set->children);
    fprintf(out, "\n");
}

/** Liveness - from Dragon Book (algorithm 10.4) */
void liveness() {
    int i, j, size, changed;
    BitSet livein;
    size = flow_size();
    for (i = 0; i < size; i++) {
        block_initDefUse(flow_block(i));
    }
    livein = set_clone(block_liveout(flow_block(0)));
    do {
        changed = 0;
        // Go backwards, so changes propagate faster.
        for (i = size -1; i >= 0; i--) {
            Block b = flow_block(i);
            BitSet liveout = block_liveout(b);
            BitSet children = flow_children(i);
            FOR_EACH(j, children) {
                set_addSet(liveout, block_livein(flow_block(j)));
            }
            set_clear(livein);
            set_addSet(livein, liveout);
            set_removeSet(livein, block_def(b));
            set_addSet(livein, block_use(b));
            if (!set_equals(livein, block_livein(b))) {
                changed = 1;
                set_addSet(block_livein(b), livein);
            }
        }
    } while (changed);
}