#include "optimise.h"
#include "flow.h"

static void decrementTreeDepth(Node n) {
    Node kid;
    int gop = generic(n->op);
//    assert(gop == VREG);
    assert(gop != COPY);
    if (gop == STACK) {
        assert(getDelve(n) > 1);
        assert(getEDepth(n) > 0);
        setDelve(n, getDelve(n) - 1);
        n->x.e_depth--;
    } else {
        if (kid = n->kids[0]) {
            decrementTreeDepth(kid);
            if (kid = n->kids[1]) {
                decrementTreeDepth(kid);
            }
        }    
    }
}

/** Need to go through this carefully... */
/**  If remove VREGP - Need to spot STACKPs that need spilling... */
static Node killTree(Block b, Node tree) {
    int op = generic(tree->op);
    if (op == CALL || op == TUCK) {
        return tree;    
    }
    if (op == INDIR) {
        int kidop = generic(tree->kids[0]->op);
        if (kidop == STACK)
            return tree;
        else if (kidop == VREG || kidop == COPY) {
            block_deleteVariable(b, tree->kids[0]);
            return NULL;
        }
    }
    if (tree->kids[1]) {
        Node lhs, rhs;
        lhs = killTree(b, tree->kids[0]);
        rhs = killTree(b, tree->kids[1]);
        if (lhs) {
            if (rhs) {
                tree->kids[0] = lhs;
                tree->kids[1] = rhs;
                return tree;
            } else {
                return lhs;
            }
        } else {
            if (rhs) {
                decrementTreeDepth(rhs);
                return rhs; 
            } else {
            //    fprintf(stderr, "Tree is totally dead!\n");
            //    prettytree(tree);
                return NULL;
            }
        }
    } else if (tree->kids[0]) {
        return killTree(b, tree->kids[0]);
    } else {
        return NULL;    
    }
}

static void removeDeadTree(Block b, Node tree) {
    Node asgn, rhs;
    assert(generic(tree->op) == ASGN);
    asgn = tree->kids[1];
    rhs = killTree(b, tree->kids[0]);
    LOG(("Removing store to %s\n", tree->kids[1]->syms[0]->x.name));
    block_deleteVariable(b, asgn);
    if (rhs) {
        // Promote rhs to the top node.
        // Copy the node into place.
        tree->op = rhs->op;
        tree->syms[0] = rhs->syms[0];
        tree->syms[1] = rhs->syms[1];
        tree->syms[2] = rhs->syms[2];
        tree->kids[0] = rhs->kids[0];
        tree->kids[1] = rhs->kids[1];
    } else {
        tree->op = NOOP;
        tree->kids[0] = NULL;
        tree->kids[1] = NULL;
    } 
    // verify();
}

static void removeDeadStores(Block b) {
    // A dead store is a store with no subsequent uses of a temp is that is not live-out.    
    Node p, end;
    BitSet live = set_clone(block_liveout(b));
    LOG(("Dead store removal for block %d\n", block_id(b)));
    // Work backwards
    for (p = block_lastTemp(b); p; p = p->x.prev) {
        assert(p->op == VREG + P || p->op == STACK + P || p->op == COPY + P); 
        p->x.dead = 0;
        if (p->op == VREG + P) {
            int index = getTempIndex(p);
            if (p->x.defn) {
                if (set_contains(live, index)) {
                    set_remove(live, index);
                } else {
                    p->x.dead = 1;
                }
            } else {
                set_add(live, index);
            }
        }
    }
    end = block_lastNode(b)->x.next;
    for (p = block_firstNode(b); p != end; p = p->x.next) {
        if (generic(p->op) == ASGN) {
            if (p->kids[1]->op == VREG + P && p->kids[1]->x.dead) {
                removeDeadTree(b, p);
            }
        }
    }
}


static char* dead() {
    flow_applyToBlocks(removeDeadStores);
    // Check flowgraph is OK.
    // verify();
    return NULL;
}

optimiser deadstore = {
    "deadstore",
    "Remove dead stores",
    14,
    &dead
};