#include "flow.h" #include "collections.h" #include "blocks.h" #include <stdlib.h> /* void propagate(FlowGraph f, int root, BitSet visited); void liveness(FlowGraph f) { int i, size, notDone; size = getNodeCount(f); BitSet childless = set_new(size, FUNC); // Don't need edge sets... for (i = 0; i < size; i++) { if (set_empty(flow_children(f, i))) { set_add(childless, i); } } BitSet visited = set_new(size, FUNC); for (i = firstSetBit(childless); i >= 0; i = set_next(childless, i + 1)) { propagate(f, i, visited); } // Find all childless nodes. Start from these. Propogate from each of these. // Do recursively - need to mark nodes as visited. // Get All children of this set and add its uses to this edgesets liveness // Add liveness to uses of all parent blocks, UNLESS block contains def. // Repeat until done -- When is it finished - no more updates or possible ot do better. // Any node which would not have been marked as use by this algorithm, but has a usage in it is a final-use. // So need pass-through use as well as real use. Any node with use, but not pass-through is final. } void propagate(FlowGraph f, int root, BitSet visited) { int i; Block from, to; if (set_contains(visited, root)) { return; } set_add(visited, root); from = flow_block(f, root); BitSet parents = flow_parents(f, root); for (i = firstSetBit(parents); i >= 0; i = set_next(parents, i + 1)) { to = flow_block(f, i); propagateUse(from, to); propagate(f, i, visited); } set_remove(visited, root); } static void livenessRecursive(int node, BitSet done, BitSet visited) { int i; Block child, parent; if (set_contains(done, node)) return; if (set_contains(visited, node)) return; set_add(visited, node); BitSet children = flow_children(node); parent = flow_block(node); for (i = firstSetBit(children); i >= 0; i = set_next(children, i + 1)) { livenessRecursive(i, done, visited); } for (i = firstSetBit(children); i >= 0; i = set_next(children, i + 1)) { child = flow_block(i); propagateUse(child, parent); } set_add(done, node); set_remove(visited, node); } void liveness() { int i, size; size = getNodeCount(); BitSet done = set_new(size, FUNC); BitSet visited = set_new(size, FUNC); if (size == 1) { block_def(flow_block(0)); } else { for (i = 0; i < size; i++) { livenessRecursive(i, done, visited); } } } */