#include "c.h" #include "collections.h" #include "x_stack.h" struct x_stack { int size; BitSet set; Symbol items[1]; // item 0 is TOS... }; int xstack_size(XStack x) { return x->size; } int compareVirtuals(Symbol s1, Symbol s2) { int dif = (s2->ref - s1->ref) * 8; if (dif) return dif; else return s1 > s2 ? 1 : s1 == s2 ? 0 : -1; // strcmp(s2->name, s1->name); } int cmpRefCount(const void* v1, const void* v2) { Symbol s1 = *((Symbol*)v1); Symbol s2 = *((Symbol*)v2); return compareVirtuals(s1, s2); } Symbol xstack_item(XStack x, int index) { return x->items[index]; } void xstack_print(XStack stack, FILE* out) { int i; if (stack == NULL) { fprintf(out, "None"); return; } fprintf(out, " ~ "); if (stack->size) { for (i = xstack_size(stack) - 1; i >= 1; i--) { fprintf(out, "%s, ", stack->items[i]->name); } fprintf(out, "%s ", stack->items[0]->name); } } void xstack_remove(XStack x, int index) { int i; Symbol s; assert(index >= 0); assert(index < x->size); s = x->items[index]; set_remove(x->set, s->x.uniqueID); for (i = index + 1; i < x->size; i++) { x->items[i-1] = x->items[i]; } --x->size; } int xstack_contains(XStack x, Symbol s) { int id = s->x.uniqueID; return set_contains(x->set, id); } XStack xstack_new(BitSet set) { int i, index, size; XStack new; assert(set); size = set_size(set); new = allocate(sizeof(Symbol) * (size - 1) + sizeof(struct x_stack), FUNC); new->size = size; new->set = set; index = 0; FOR_EACH(i, set) { new->items[index++] = localVariableSymbol(i); } qsort(new->items, index, sizeof(Symbol), &cmpRefCount); return new; } void xstack_ensureReachable(XStack x, BitSet variables, int delve) { int i, excess; if (x->size <= delve) return; do { int candidate = -1; int lowest = -1; excess = 0; for (i = x->size - 1; i >= 0; --i) { if (set_contains(variables, x->items[i]->x.uniqueID)) { if (i >= delve) excess = 1; if (lowest < 0) lowest = i; } else { if (candidate < 0 && i < delve) candidate = i; } } if (excess) { if (candidate >= 0) xstack_remove(x, candidate); else if (lowest >= 0) xstack_remove(x, lowest); } } while (excess); } ArrayList xstack_top(XStack x, int count) { int i; ArrayList result = list_new(count); assert(x->size >= count); for(i = 0; i < count; i++) list_add(result, x->items[i]); return result; }