#include "optimise.h" #include "blocks.h" #include "flow.h" #include "nodes.h" #define DEPTH (IR->x.depth) void popAll(Block b, int* temps, int count) { BitSet defd, _block_use, livein; int i; if (count == 0) return; defd = block_def(b); _block_use = block_use(b); livein = block_livein(b); for (i = 0; i < count; i++) { // set_remove(livein, temps[i]); // set_add(defd, temps[i]); // set_remove(_block_use, temps[i]); popTemp(localVariableSymbol(temps[i]), b); } } void pushAll(Block b, int* temps, int count) { // verify(b); Node forest, last; int i; BitSet liveout; if (count == 0) return; forest = last = NULL; liveout = block_liveout(b); for (i = 0; i < count; i++) { set_remove(liveout, temps[i]); pushTemp(localVariableSymbol(temps[i]), b); } } static int getDepthFirst(Block b, Symbol temp) { Node p; for (p = block_firstTemp(b); p; p = p->x.next) { if (p->syms[0] == temp) { return DEPTH - getEDepth(p); } } return DEPTH; } static int getDepthLast(Block b, Symbol temp) { Node p; for (p = block_lastTemp(b); p; p = p->x.prev) { if (p->syms[0] == temp) { return DEPTH - getEDepth(p); } } return DEPTH; } static int cmp(const void* v1, const void* v2) { Symbol* s1 = (Symbol*)v1; Symbol* s2 = (Symbol*)v2; return (*s1)->x.scratch - (*s2)->x.scratch; } static int scheduleTemps(EdgeSet edges, BitSet live, int* substack) { /* For each variable in live set, get max allowable depth, and annotate Symbol with that depth. */ int i, j, count = 0; Symbol* symbols = allocate(sizeof(Symbol) * set_size(live), FUNC); BitSet children = edgeset_children(edges); BitSet parents = edgeset_parents(edges); FOR_EACH(i, live) { Symbol temp = localVariableSymbol(i); int min_depth = DEPTH; FOR_EACH(j, parents) { int depth = getDepthLast(flow_block(j), temp); if (depth < min_depth) min_depth = depth; } FOR_EACH(j, children) { int depth = getDepthFirst(flow_block(j), temp); if (depth < min_depth) min_depth = depth; } if (min_depth > 0) { temp->x.scratch = min_depth; symbols[count++] = temp; } } /* Sort temps by max_depth */ qsort(symbols, count, sizeof(Symbol), &cmp); /* Eliminate impossible temps */ for(i = 0; i < count; i++) { if (symbols[i]->x.scratch <= i) { count--; for (j = i; j < count; j++) { symbols[j] = symbols[j+1]; } i--; } } for(i = 0; i < count; i++) { substack[i] = symbols[i]->x.uniqueID; // fprintf(stderr, "substack[%d] = %s\n", i, symbols[i]->name); } return count; } static BitSet liveIntersection(EdgeSet set) { /* This is the set_intersection of all union(def, use) of parents * and use of children - As opposed to the union of live-in/out in other algorithms */ BitSet children, parents, live; int i; Block b; children = edgeset_children(set); parents = edgeset_parents(set); i = FIRST_IN(children); b = flow_block(i); live = set_clone(block_use(b)); for (; i >= 0; i = set_next(children, i+1)) { b = flow_block(i); live = set_intersection(live, block_use(b)); } FOR_EACH(i, parents) { BitSet def_use; b = flow_block(i); def_use = set_union(block_def(b), block_use(b)); live = set_intersection(live, def_use); } return live; } static BitSet liveUnion(EdgeSet set) { /* This is the set_intersection of all union(def, use) of parents * and use of children - As opposed to the union of live-in/out in other algorithms */ BitSet children, parents, live; int i; Block b; children = edgeset_children(set); parents = edgeset_parents(set); i = FIRST_IN(children); b = flow_block(i); live = set_clone(block_use(b)); for (; i >= 0; i = set_next(children, i+1)) { b = flow_block(i); live = set_union(live, block_use(b)); } FOR_EACH(i, parents) { BitSet def_use; b = flow_block(i); live = set_intersection(live, block_liveout(b)); } return live; } static void schedule(EdgeSet edges, BitSet (*func)(EdgeSet edges)) { int i, count, *substack; BitSet children, parents; BitSet live = func(edges); if (!set_empty(live)) { substack = allocate(sizeof(int) * set_size(live), FUNC); count = scheduleTemps(edges, live, substack); children = edgeset_children(edges); FOR_EACH(i, children) { popAll(flow_block(i), substack, count); } parents = edgeset_parents(edges); FOR_EACH(i, parents) { pushAll(flow_block(i), substack, count); } } } static char* xxxx(void) { /* Boundary Mapping -- All information is already present */ ArrayList edge_sets = flow_edgeSets(); int i, size = list_size(edge_sets); for(i = 0; i < size; i++) { schedule((EdgeSet)list_get(edge_sets, i), liveIntersection); } return NULL; } optimiser bailey = { "bailey", "Chris Bailey's intra-boundary algorithm [Bailey 00e]", 0, &xxxx }; static char* xxxx_p(void) { ArrayList edge_sets = flow_edgeSets(); int i, size = list_size(edge_sets); for(i = 0; i < size; i++) { schedule((EdgeSet)list_get(edge_sets, i), liveUnion); } return NULL; } optimiser bailey_plus = { "bailey+", "Chris Bailey's algorithm with union rather than intersection", 0, &xxxx_p };