#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; }