#include "blocks.h"
#include "collections.h"

typedef struct _chain *Chain;
ArrayList getChains(Block b);
extern int getTotalDepth(Node n);


struct _chain {
    Symbol s;         // Variable for this chain
    Node defn;        // Definition for this chain - If NULL - means s is live on entry to block.
    Node first;       // First use in this chain
    Node last;        // Last use in this chain
    int max_depth;    
    signed char liveout;    // 1 chain is live-out of the block. -1 chain contains last use or defn of variable s in block. 0 otherwise.
    char allocated;
};

Symbol chain_symbol(const Chain chain) {
    return chain->s;
}

Node chain_first(const Chain chain) {
    return chain->first;    
}

Node chain_defn(const Chain chain) {
    return chain->defn;
}

int chain_empty(Chain chain) {
    return !(chain->defn || chain->first);
}

/** Returns 1 for accept, 0 for don't care and -1 for reject */
int mockAllocate(Chain chain, Block b) {
    Node n, start, end;
    if (chain_empty(chain)) {
        LOG(("Chain ignored: %s %d %d\n", chain->s->name, (chain->defn == NULL), chain->liveout));
        return 0;
    }
    if (chain->defn && (chain->defn->x.scratch > IR->x.depth)) {
        LOG(("Chain not OK: %s %d %d\n", chain->s->name, (chain->defn == NULL), chain->liveout));
        return -1;
    }
    n = chain->first;
    while(n) {
        if (n->x.scratch >= IR->x.depth) {
            LOG(("Chain not OK: %s %d %d\n", chain->s->name, (chain->defn == NULL), chain->liveout));
            return -1;
        }    
        n = n->x.nextUse;
    } 
    LOG(("Chain OK: %s %d %d\n", chain->s->name, (chain->defn == NULL), chain->liveout));
    start = chain->defn ? chain->defn : block_firstTemp(b);
    end = chain->liveout ? block_lastTemp(b) : chain->last;
    if (start && end) {
        for(n = start; n != end->x.next; n = n->x.next)
            n->x.scratch++;      
    }
    return 1;
}

int chain_livein(const Chain chain) {
    return chain->defn == NULL;    
}

int chain_liveout(const Chain chain) {
    return chain->liveout;    
}

static Chain chain_new(Node defn, Symbol s) {
    Chain chain = allocate(sizeof(struct _chain), FUNC);
    chain->defn = defn;
    chain->s = s;
    chain->first = NULL;
    chain->last = NULL;
    chain->liveout = 0;
    chain->allocated = 0;
    chain->max_depth = 0;
    return chain;
}

static void chain_addUse(Chain chain, Node use) {
    assert(generic(use->op) == VREG);
    assert(chain->s == use->syms[0]);
    if (chain->first == NULL) {
        chain->first = use;
    } else {
        chain->last->x.nextUse = use;
    }
    chain->last = use;
    use->x.nextUse = NULL;
    if(use && (getEDepth(use) > chain->max_depth))
        chain->max_depth = getEDepth(use);
}

/** Allocates this chain within its Block.
    Ie. Converts VREGP nodes to STACKP and COPYP nodes. */
int chain_allocate(Chain chain, Block b, ArrayList lstack1, ArrayList lstack2) {
    Node n, start, end;
    assert(!(chain->allocated));
    if (chain->defn && getTotalDepth(chain->defn) > IR->x.depth) {
        LOG(("%s %d %d not allocated\n", chain->s->name, (chain->defn == NULL), chain->liveout));
        return 0;
    }
    n = chain->first;
    while(n) {
        int depth = getTotalDepth(n);
        assert(n->op == VREG + P);
        if (depth >= IR->x.depth) {
            LOG(("%s %d %d not allocated\n", chain->s->name, (chain->defn == NULL), chain->liveout));
            return 0;
        }
        n = n->x.nextUse;
    }
    n = chain->defn;
    if (n) {
        n->op = STACK + P;
        setDelve(n, getTotalDepth(n));
        n = n->x.nextUse;
    }
    n = chain->first;
    while(n) {
        if ((n == chain->last) && (chain->liveout <= 0)) {
            n->op = STACK + P;
        } else {
            n->op = COPY + P;
        }
        setDelve(n, getTotalDepth(n) + 1);
        n = n->x.nextUse;
    }
    if (chain->defn == NULL) {
        start = block_firstTemp(b);
        list_add(lstack1, chain->s);
    } else {
        start = chain->defn;
    }
    if (chain->liveout > 0) {
        end = block_lastTemp(b);
        list_add(lstack2, chain->s);
    } else {
        end = chain->last;
    }
    if (start && end)
        increaseLDepth(start, end);
    chain->allocated = 1;
    LOG(("%s %d %d allocated\n", chain->s->name, (chain->defn == NULL), chain->liveout));
    return 1;
}

static void findUse(Node p, Chain* indexedChains) {
    if (p->kids[0]) {
        if (generic(p->kids[0]->op) == VREG) {
            Chain chain = indexedChains[getTempIndex(p->kids[0])];
            if (chain)
                chain_addUse(chain, p->kids[0]);
        } else {
            findUse(p->kids[0], indexedChains);
            if (p->kids[1])
                findUse(p->kids[1], indexedChains);
        }
    }
}

/** Returns a list of chains for this Block */
ArrayList generateChains(Block b) {
    int i;
    Node p, end, kid;
    ArrayList chains = list_new(16);
    BitSet livein, liveout;
    Chain* indexedChains;
    if (local_variable_count == 0)
        return chains;
    livein = block_livein(b);
    indexedChains = allocate(sizeof(Chain) * local_variable_count, FUNC);
    LOG(("Generating chains for block %d\n", block_id(b)));
    for (i = 0; i < local_variable_count; i++) {
        if (set_contains(livein, i))
            indexedChains[i] = chain_new(NULL, localVariableSymbol(i));
        else    
            indexedChains[i] = NULL;
    }
    end = block_lastNode(b)->x.next;
    for (p = block_firstNode(b); p != end; p = p->x.next) {
        if (generic(p->op) == ASGN) {
            kid = p->kids[0];
            findUse(kid, indexedChains);
            kid = p->kids[1];
            if (generic(kid->op) == VREG) {
                Chain completed = indexedChains[getTempIndex(kid)];
                if (completed != NULL && completed->first != NULL) {
                    list_add(chains, completed);
                    LOG(("Created chain %s %d %d\n", completed->s->name, (completed->defn == NULL), completed->liveout));
                }
                indexedChains[getTempIndex(kid)] = chain_new(kid, kid->syms[0]);
            } else {
                findUse(kid, indexedChains);
            }
        } else {
            findUse(p, indexedChains);
        }
    }
    liveout = block_liveout(b);
    for (i = 0; i < local_variable_count; i++) {
        if (indexedChains[i] != NULL && (!(localVariableSymbol(i)->x.branchTemp))) {
            if (set_contains(liveout, i)) {
                indexedChains[i]->liveout = 1;
                list_add(chains, indexedChains[i]);
                LOG(("Created chain %s %d %d\n", indexedChains[i]->s->name, (indexedChains[i]->defn == NULL), indexedChains[i]->liveout));
            } else if (indexedChains[i]->first != NULL) {
                indexedChains[i]->liveout = -1;
                list_add(chains, indexedChains[i]);
                LOG(("Created chain %s %d %d\n", indexedChains[i]->s->name, (indexedChains[i]->defn == NULL), indexedChains[i]->liveout));
            } 
        }
     }
    return chains;
}

void chain_makelastliveout(Chain chain, Symbol var) {
    if (chain->liveout < 0 && chain->s == var)
        chain->liveout = 1;
}