#define BLOCK_SCRATCH struct _annotation
#include "optimise.h"
#include "chains.h"
#include "block_annotate.h"
#include "blocks.h"
#include "duchain.h"
#include "collections.h"

void intraBlock3(Block b);

int (*compare2) (const void* v1, const void* v2);

char* intra() {
    flow_applyToBlocks(intraBlock3);
    // Check flowgraph is OK.
    verify(1);
    return NULL;
}

static int compareByDepth(const void* v1, const void* v2) {
    DuChain chain1 = *((DuChain*)v1);
    DuChain chain2 = *((DuChain*)v2);
    return duchain_maxDepth(chain1) - duchain_maxDepth(chain2);
}

void schedule(DuChain chain, Block b) {
    Use use, next;
    Node n;
    if (getTotalDepth(duchain_defn(chain)) > IR->x.depth)
        return;
    use = duchain_firstUse(chain);
    while(use) {
        if (getTotalDepth(duchain_useNode(use)) >= IR->x.depth)
            return;
        use = duchain_nextUse(use);
    }
    // All OK now schedule.
    n = duchain_defn(chain);
    assert(generic(n->op) == VREG);
    n->op += STACK - VREG;
    setDelve(n, getTotalDepth(n));
    use = duchain_firstUse(chain);
    next = duchain_nextUse(use);
    while (next) {
        n = duchain_useNode(use);
        assert(generic(n->op) == VREG);
        n->op += COPY - VREG;
        setDelve(n, getTotalDepth(n) + 1);
        use = next;
        next = duchain_nextUse(next);
    }
    assert(use);
    n = duchain_useNode(use);
    assert(generic(n->op) == VREG);
    n->op += STACK - VREG;
    setDelve(n, getTotalDepth(n) + 1);
    increaseDepth(duchain_defn(chain), n);
}

DuChain* getEligibleChains(Block b, int*count) {
    int i;
    ArrayList chains = duchain_getChains(b);
    BitSet live = set_clone(block_liveout(b));
    *count = list_size(chains);
    if (*count == 0)
        return NULL;
    DuChain* array = (DuChain*)list_array(chains);
    DuChain* eligible = allocate((*count) * sizeof(DuChain));
    int eligibles = 0;
    for (i = *count - 1; i >= 0; i--) {
        DuChain chain = array[i];
        if (set_contains(live, duchain_getID(chain)))
            set_remove(live, duchain_getID(chain));
        else
            eligible[eligibles++] = chain;
    }
    *count = eligibles;
    return eligible;
}

void intraBlock3(Block b) {
    int i;
    int count;
    DuChain* eligible = getEligibleChains(b, &count);
    if (count == 0)
        return;
    // Sort by urgency...
    qsort(eligible, count, sizeof(DuChain), &compareByOccurence);
    qsort(eligible, count, sizeof(DuChain), &compareByDepth);
    for (i = count - 1; i >= 0; i--) {
        schedule(eligible[i], b);
    }
}

static XStack start;
static XStack end;

static int compareByX(const void* v1, const void* v2) {
    DuChain chain1 = *((DuChain*)v1);
    DuChain chain2 = *((DuChain*)v2);
    Symbol s1 = duchain_symbol(chain1);
    Symbol s2 = duchain_symbol(chain2);
    if (xstack_contains(start, s1) || xstack_contains(end, s1)) {
        if (xstack_contains(start, s2) || xstack_contains(end, s2)) {
            return s1->ref - s2->ref;
        } else {
            return 1;    
        }
    } else {
        if (xstack_contains(start, s2)) {
            return -1;
        } else {
            return compareByOccurence(v1, v2);
        }    
    }
}

void intraBlock4(Block b) {
    int i;
    int count;
    DuChain* eligible = getEligibleChains(b, &count);
    if (count == 0)
        return;
    // Sort by urgency...
    start = block_scratch(b)->in;
    end = block_scratch(b)->out;
    qsort(eligible, count, sizeof(DuChain), &compareByDepth);
    qsort(eligible, count, sizeof(DuChain), &compareByX);
    for (i = count - 1; i >= 0; i--) {
        schedule(eligible[i], b);
    }
}

optimiser intra3 = {
    "intra3",
    "Intra block 3 - Optimises locals, allocating entire du-chains.",
    0,
    &intra
};

char* _intra4() {
    flow_applyToBlocks(intraBlock4);
    // Check flowgraph is OK.
    verify(1);
    return NULL;
}

optimiser intra4 = {
    "intra4",
    "Intra block 4 - Optimises locals, allocating entire du-chains, with reference to x-stack order.",
    0,
    &_intra4
};