#include "optimise.h"
#include "blocks.h"
#include "flow.h"
#include "nodes.h"
#define DEPTH (IR->x.depth)

void popAll(Block b, int* temps, int count) {
    BitSet defd, _block_use, livein;
    int i;
    if (count == 0)
        return;
    defd = block_def(b);
    _block_use = block_use(b);
    livein = block_livein(b);
    for (i = 0; i < count; i++) {
//        set_remove(livein, temps[i]);
//        set_add(defd, temps[i]);
//        set_remove(_block_use, temps[i]);
        popTemp(localVariableSymbol(temps[i]), b);
    }
}

void pushAll(Block b, int* temps, int count) {
//    verify(b);
    Node forest, last;
    int i;
    BitSet liveout;
    if (count == 0)
        return;
    forest = last = NULL;
    liveout = block_liveout(b);
    for (i = 0; i < count; i++) {
        set_remove(liveout, temps[i]);
        pushTemp(localVariableSymbol(temps[i]), b);
    }
}

static int getDepthFirst(Block b, Symbol temp) {
    Node p;
    for (p = block_firstTemp(b); p; p = p->x.next) {
        if (p->syms[0] == temp) {
            return DEPTH - getEDepth(p);
        }
    }
    return DEPTH;
}

static int getDepthLast(Block b, Symbol temp) {
    Node p;
    for (p = block_lastTemp(b); p; p = p->x.prev) {
        if (p->syms[0] == temp) {
            return DEPTH - getEDepth(p);
        }
    }
    return DEPTH;
}

static int cmp(const void* v1, const void* v2) {
    Symbol* s1 = (Symbol*)v1;
    Symbol* s2 = (Symbol*)v2;
    return (*s1)->x.scratch - (*s2)->x.scratch;
}

static int scheduleTemps(EdgeSet edges, BitSet live, int* substack) {
    /* For each variable in live set, get max allowable depth, and annotate Symbol with that depth. */
    int i, j, count = 0;
    Symbol* symbols = allocate(sizeof(Symbol) * set_size(live), FUNC);
    BitSet children = edgeset_children(edges);
    BitSet parents = edgeset_parents(edges);
    FOR_EACH(i, live) {
        Symbol temp = localVariableSymbol(i);
        int min_depth = DEPTH;
        FOR_EACH(j, parents) {
            int depth = getDepthLast(flow_block(j), temp);
            if (depth < min_depth)
                min_depth = depth;
        }
        FOR_EACH(j, children) {
            int depth = getDepthFirst(flow_block(j), temp);
            if (depth < min_depth)
                min_depth = depth;
        }
        if (min_depth > 0) {
            temp->x.scratch = min_depth;
            symbols[count++] = temp;    
        }
    }
    /* Sort temps by max_depth */
    qsort(symbols, count, sizeof(Symbol), &cmp);
    /* Eliminate impossible temps */
    for(i = 0; i < count; i++) {
        if (symbols[i]->x.scratch <= i) {
            count--;
            for (j = i; j < count; j++) {
                symbols[j] = symbols[j+1];
            }
            i--;
        }
    }
    for(i = 0; i < count; i++) {
        substack[i] = symbols[i]->x.uniqueID;
//        fprintf(stderr, "substack[%d] = %s\n", i, symbols[i]->name);
    }
    return count;
}

static BitSet liveIntersection(EdgeSet set) {
    /* This is the set_intersection of all union(def, use) of parents
     * and use of children
    - As opposed to the union of live-in/out in other algorithms */
    BitSet children, parents, live;
    int i;
    Block b;
    children = edgeset_children(set);
    parents = edgeset_parents(set);
    i = FIRST_IN(children);
    b = flow_block(i);
    live = set_clone(block_use(b));
    for (; i >= 0; i = set_next(children, i+1)) {
        b = flow_block(i);
        live = set_intersection(live, block_use(b));
    }
    FOR_EACH(i, parents) {
        BitSet def_use;
        b = flow_block(i);
        def_use = set_union(block_def(b), block_use(b));
        live = set_intersection(live, def_use);
    }
    return live;
}

static BitSet liveUnion(EdgeSet set) {
    /* This is the set_intersection of all union(def, use) of parents
     * and use of children
    - As opposed to the union of live-in/out in other algorithms */
    BitSet children, parents, live;
    int i;
    Block b;
    children = edgeset_children(set);
    parents = edgeset_parents(set);
    i = FIRST_IN(children);
    b = flow_block(i);
    live = set_clone(block_use(b));
    for (; i >= 0; i = set_next(children, i+1)) {
        b = flow_block(i);
        live = set_union(live, block_use(b));
    }
    FOR_EACH(i, parents) {
        BitSet def_use;
        b = flow_block(i);
        live = set_intersection(live, block_liveout(b));
    }
    return live;
}

static void schedule(EdgeSet edges, BitSet (*func)(EdgeSet edges)) {
    int i, count, *substack;
    BitSet children, parents;
    BitSet live = func(edges);
    if (!set_empty(live)) {
        substack = allocate(sizeof(int) * set_size(live), FUNC);
        count = scheduleTemps(edges, live, substack);
        children = edgeset_children(edges);
        FOR_EACH(i, children) {
            popAll(flow_block(i), substack, count);
        }
        parents = edgeset_parents(edges);
        FOR_EACH(i, parents) {
            pushAll(flow_block(i), substack, count);
        }
    }
}

static char* xxxx(void) {
    /* Boundary Mapping
    -- All information is already present */
    ArrayList edge_sets = flow_edgeSets();
    int i, size = list_size(edge_sets);
    for(i = 0; i < size; i++) {
        schedule((EdgeSet)list_get(edge_sets, i), liveIntersection);
    }
    return NULL;
}

optimiser bailey = {
    "bailey",
    "Chris Bailey's intra-boundary algorithm [Bailey 00e]",
    0,
    &xxxx
};

static char* xxxx_p(void) {
    ArrayList edge_sets = flow_edgeSets();
    int i, size = list_size(edge_sets);
    for(i = 0; i < size; i++) {
        schedule((EdgeSet)list_get(edge_sets, i), liveUnion);
    }
    return NULL;
}

optimiser bailey_plus = {
    "bailey+",
    "Chris Bailey's algorithm with union rather than intersection",
    0,
    &xxxx_p
};