#include <stdlib.h>
#include <ctype.h> 
// #define NDEBUG
#include "blocks.h"
#include "collections.h"
#include "flow.h"

#define REACHABLE 1
#define PENDING 2
#define EMPTY 4

#define SENTINEL 123456789

extern void dumptree(Node tree);


struct block {
#ifndef NDEBUG
    int sentinel;
#endif
    Node first;
    Node last;
    Node firstTemp;
    int id;
    BitSet def;
    BitSet use;
    BitSet livein;
    BitSet liveout;
    EdgeSet inEdges;
    EdgeSet outEdge;
    int start_edepth;
    int start_ldepth;
    int end_edepth;
    int end_ldepth;
    BitSet reject;
    XStack inStack;
    XStack outStack;
};

void block_setStartEDepth(Block b, int depth) {
    b->start_edepth = depth;    
}

int block_getStartEDepth(Block b) {
    return b->start_edepth;
}

void block_setStartLDepth(Block b, int depth) {
    b->start_ldepth = depth;    
}

int block_getStartLDepth(Block b) {
    return b->start_ldepth;
}

void block_setEndEDepth(Block b, int depth) {
    b->end_edepth = depth;    
}

int block_getEndEDepth(Block b) {
    return b->end_edepth;
}

BitSet block_reject(Block b) {
    if (b->reject == NULL)
        b->reject =set_new(local_variable_count);
    return b->reject;   
}

XStack block_inStack(Block b) {
    return b->inStack;    
}

XStack block_outStack(Block b) {
    return b->outStack;    
}

void block_setInStack(Block b, XStack in) {
    b->inStack = in;
}

void block_setOutStack(Block b, XStack out) {
    b->outStack = out;
}

/** Sets the stack depth at the end of this block */
void block_setEndLDepth(Block b, int depth) {
    b->end_ldepth = depth;    
}

/** Returns the stack depth at the end of this block */
int block_getEndLDepth(Block b) {
    return b->end_ldepth;
}

Node block_firstNode(Block b)
{
    return b->first;    
}

Node block_lastNode(Block b)
{
    return b->last;    
}

static Block initBlock(Node first, Node last) {
    Block this = allocate(sizeof(struct block), FUNC);
    assert(this->sentinel = SENTINEL);
    this->first = first;
    this->last = last;
    assert(this->sentinel == SENTINEL);
    this->def = NULL;
    this->use = NULL;
    this->inStack = NULL;
    this->outStack = NULL;
    this->reject = NULL;
    this->id = -1;
    return this;
}

Node block_firstTemp(Block b) {
    return     b->firstTemp;
}

Node block_lastTemp(Block b) {
    Node temp;
    if (b->firstTemp) {
        for(temp = b->firstTemp; temp->x.next; temp = temp->x.next);
        return temp;
    } else {
        return NULL;    
    }
}

static Node linkTemp(Node p, Node *first, Node last) {
    Node kid;
    if (p->op == VREG + P || p->op == STACK + P || p->op == COPY + P) {
        if (last) {
            last->x.next = p;
            p->x.prev = last;
        } else if((*first) == NULL) {
           (*first) = p;
        }
        return p;
    } else {
        if((kid = p->kids[0]))
            last = linkTemp(kid, first, last);
        if ((kid = p->kids[1]))
            last = linkTemp(kid, first, last);
        return last;
     }
}

static void linkBlock(Block b) {
    Node previous, p, end, last;
    end = b->last->link;
    b->firstTemp = last = NULL;
    assert(b->first->x.prev == NULL);
    previous = NULL;
    for (p = b->first; p != end; p = p->link) {
        p->x.prev = previous;
        p->x.next = p->link;
        previous = p;
        last = linkTemp(p, &(b->firstTemp), last);
    }
    b->last->x.next = NULL;
}

Block block_new(int startDepth, int endDepth, Node first, Node last) {
    Block result;
    assert(first);
    assert(last);
    result = initBlock(first, last);
    linkBlock(result);
    result->start_edepth = startDepth;
    result->start_ldepth = 0;
    result->end_edepth = endDepth;
    result->end_ldepth = 0;
    assert(result->first->x.prev == NULL);
    assert(result->last->x.next == NULL);
    return result;
}
    
int block_id(Block b) {
    assert(b->id >= 0);
    return b->id;
}
    
void block_setID(Block b, int id) {
    assert(id >= 0);
    assert(b->id < 0); 
    b->id = id;
}

static void useTree(Block b, Node tree) {
    if (tree->kids[0]) {
        useTree(b, tree->kids[0]);
        if (tree->kids[1])
            useTree(b, tree->kids[1]);
    } else if (generic(tree->op) == VREG) {
        int temp = getTempIndex(tree);
        if (!set_contains(b->def, temp))
            set_add(b->use, temp);
    }
}

static void defUse(Block b) {
    Node p, kid, end;
    b->def = set_new(local_variable_count);
    assert(set_empty(b->def));
    b->use = set_new(local_variable_count);
    assert(set_empty(b->use));
    end = b->last->x.next;
    for (p = b->first; p != end; p = p->x.next) {
        switch (generic(p->op)) {
        case ASGN:
            kid = p->kids[0];
            useTree(b, kid);
            kid = p->kids[1];
            if (generic(kid->op) == VREG) {
                int temp = getTempIndex(kid);
                kid->x.defn = 1;
                if (!set_contains(b->use, temp))
                    set_add(b->def, temp);
            } else {
                useTree(b, kid);
            }
            break;
        case EQ: case NE: case LT: case LE: case GT: case GE:
            useTree(b, p->kids[0]);
            useTree(b, p->kids[1]);
            break;
        case CALL:
            if (p->kids[1])
                useTree(b, p->kids[1]);
        case ARG: case JUMP:
            useTree(b, p->kids[0]);
            break;
        case RET:
            if (p->kids[0])
                useTree(b, p->kids[0]);
            break;    
        }    
    }
    b->livein = set_clone(b->use);
    b->liveout = set_new(local_variable_count);
}

void block_initDefUse(Block b) {
    if (b->def == NULL) 
        defUse(b);
}

BitSet block_def(Block b) {
    if(!b->def)
        defUse(b);
    return b->def;     
}

BitSet block_use(Block b) {
    if(!b->def)
        defUse(b);
    return b->use;    
}

BitSet block_livein(Block b) {
    assert(b->livein);
    return b->livein;    
}

BitSet block_liveout(Block b) {
    assert(b->liveout);
    return b->liveout;    
}

Block block_merge(Block b1, Block b2) {
    Node temp;
    Block new;
    assert(b1->first->x.prev == NULL);
    assert(b2->first->x.prev == NULL);
    new = initBlock(b1->first, b2->last);
    b1->last->x.next = b2->first;
    b2->first->x.prev = b1->last;
    new->start_edepth = b1->start_edepth;
    new->start_ldepth = b1->start_ldepth;
    new->end_edepth = b2->end_edepth;
    new->end_ldepth = b2->end_ldepth;
    assert(b2->start_edepth == b1->end_edepth);
     assert(b2->start_ldepth == b1->end_ldepth);
    if(b1->firstTemp) {
        new->firstTemp = b1->firstTemp;
        if (b2->firstTemp) {
            temp = block_lastTemp(b1);
            b2->firstTemp->x.prev = temp;
            temp->x.next = b2->firstTemp;
        }
    } else {
        if (b2->firstTemp) {
            new->firstTemp = b2->firstTemp;
        } else {
            new->firstTemp = NULL;
        }
    }
    return new;
}

void block_deleteVariable(Block b, Node temp) {
    assert(temp->op == STACK + P || temp->op == VREG + P || temp->op == COPY + P); 
    if (temp->x.prev) { 
        temp->x.prev->x.next = temp->x.next;
    } else {
        assert(b->firstTemp == temp);
        b->firstTemp = temp->x.next;
    }
    if (temp->x.next) 
        temp->x.next->x.prev = temp->x.prev;
}

static Node lastTempInTree(Node n) {
    Node kid, x;
    int gop = generic(n->op);
    if (gop == STACK || gop == VREG) 
        return n;
    if ((kid = n->kids[1])) {
        x = lastTempInTree(kid);
        if (x)
            return x;
    } 
    if ((kid = n->kids[0])) {
        return lastTempInTree(kid);    
    } else {
        return NULL;
    }
}

static void insertAfter(Block b, Node n, Node forest) {
    Node firstTemp, lastTemp, p, previousTemp, tree;
    assert(n);
    assert(forest);
    lastTemp = firstTemp = NULL;
    // Link forest internally.
    for (p = forest; p->link; p = p->link) {
        p->x.next = p->link;
        p->x.next->x.prev = p;
        lastTemp = linkTemp(p, &firstTemp, lastTemp);
    }
    lastTemp = linkTemp(p, &firstTemp, lastTemp);
    // Link roots
    p->link = n->link;
    n->link = forest;
    if (b->last == n) 
        b->last = p;
    else
        n->x.next->x.prev = p;
    p->x.next = n->x.next;
    n->x.next = forest;
    forest->x.prev = n;
    // Link temps
    if (firstTemp == NULL)
        return;
    if (b->firstTemp == NULL) {
        b->firstTemp = firstTemp;
        return;
    }
    previousTemp = NULL;
    tree = n;
    do {
        previousTemp = lastTempInTree(tree);
        tree = tree->x.prev;
    } while ((tree != NULL) && (previousTemp == NULL));
    if (previousTemp) {
        if (previousTemp->x.next)
            previousTemp->x.next->x.prev = lastTemp;
        lastTemp->x.next = previousTemp->x.next;
        previousTemp->x.next = firstTemp;
        firstTemp->x.prev = previousTemp;
    } else {
        lastTemp->x.next = b->firstTemp;
        b->firstTemp->x.prev = lastTemp;
        b->firstTemp = firstTemp;
    }
}

void block_print(Block b, FILE* out) {
    Node p, end;
    end = block_lastNode(b)->x.next;
    for (p = block_firstNode(b); p != end; p = p->x.next)
        printTree(p, out);
}

int block_length(Block b) {
    int count = 0;
    Node p, end;
    end = block_lastNode(b)->x.next;
    for (p = block_firstNode(b); p != end; p = p->x.next)
        count++;
    return count;
}

static void noopHead(Block b) {
    Node first = b->first;
    Node second = newnode(first->op, first->kids[0], first->kids[1], first->syms[0]);
    second->syms[1] = first->syms[1];
    first->op = NOOP;
    first->kids[0] = NULL;
    first->kids[1] = NULL;
    first->syms[0] = NULL;
    first->syms[1] = NULL;
    second->x.prev = first;
    second->link = first->link;
    first->link = second;
    if (first->x.next) {
        first->x.next->x.prev = second;
    } else {
        b->last = second;
    }
    second->x.next = first->x.next;
    first->x.next = second;
}

void block_insertAtHead(Block b, Node forest) {
    Node first = b->first;
    assert(forest);
    if (first->op != NOOP && first->op != LABEL + V)
        noopHead(b);
    assert(first->x.prev == NULL);
    insertAfter(b, first, forest);
}

void block_insertAtTail(Block b, Node forest) {
    assert(forest);
    switch(generic(b->last->op)) {
    case LT: case JUMP: case NE: case EQ: case GT: case LE: case GE:
        if (b->last == b->first) {
            block_insertAtHead(b, forest);
        } else {
            insertAfter(b, b->last->x.prev, forest);
        }
        break;
    default:
        insertAfter(b, b->last, forest);
    }
}

void increaseLDepth(Node from, Node to) {
    Node n;
    int generic = generic(from->op);
    assert(generic == VREG || generic == STACK || generic == COPY);
    assert(from->kids[0] == NULL);
    generic = generic(to->op);
    assert(generic == VREG || generic == STACK || generic == COPY);
    assert(to->kids[0] == NULL);
    for (n = from; n != to->x.next; n = n->x.next) {
        assert(n->x.next || to->x.next == NULL);
        n->x.l_depth++;
    }
}