#include #include #include "flow.h" #include "collections.h" #include "x_stack.h" /** Most of the functions here are wrappers around the generic graph functions, casting pointers to their correct types. Other function provide some flow-graph specific functionality such as determining liveness and edge-sets .*/ Graph flow_graph; struct edge_set { BitSet parents; BitSet children; XStack x_stack; int depth; }; int edgeset_depth(EdgeSet edges) { return edges->depth; } BitSet edgeset_parents(EdgeSet edges) { return edges->parents; } BitSet edgeset_children(EdgeSet edges) { return edges->children; } void flow_applyToBlocks(void (* func)(Block nodeData)) { int i; for(i = 0; i < flow_size(); i++) { func((Block)graph_node(flow_graph, i)); } } int flow_addBlock(Block block) { return graph_addNode(flow_graph, block); } void addEdge(int from, int to) { graph_addEdge(flow_graph, from, to); } static void* wrapper(void* b1, void* b2) { return block_merge((Block)b1, (Block)b2); } /** Closes the flow graph, see graph_close for effect. Also sets ids of all blocks as contiguous numbers from 0 upwards. */ void flow_close() { int i, size; graph_close(flow_graph, wrapper); //Set IDs. size = flow_size(); for(i = 0; i < size; i++) { block_setID((Block)graph_node(flow_graph, i), i); } write_log("Flow graph closed, size %d\n", size); } Block flow_block(int index) { return graph_node(flow_graph, index); } EdgeSet createEdgeSet() { EdgeSet set = allocate(sizeof(struct edge_set), FUNC); set->children = graph_newNodeSet(flow_graph, FUNC); set->parents = graph_newNodeSet(flow_graph, FUNC); return set; } /** Builds the edge set which contains the predecessor edges to block with id of initialChild */ static EdgeSet buildEdgeSet(int initialChild) { BitSet newChildren, newParents; EdgeSet set; int next; if (set_empty(flow_parents(initialChild))) return NULL; newChildren = graph_newNodeSet(flow_graph, FUNC); newParents = graph_newNodeSet(flow_graph, FUNC); set = createEdgeSet(); set_add(set->children, initialChild); set->depth = block_getStartEDepth(flow_block(initialChild)); set_add(newChildren, initialChild); while (FIRST_IN(newChildren) >= 0) { while ((next = FIRST_IN(newChildren)) >= 0) { set_remove(newChildren, next); set_addSet(newParents, flow_parents(next)); } set_removeSet(newParents, set->parents); set_addSet(set->parents, newParents); set_clear(newChildren); while ((next = FIRST_IN(newParents)) >= 0) { set_remove(newParents, next); set_addSet(newChildren, flow_children(next)); } set_removeSet(newChildren, set->children); set_addSet(set->children, newChildren); set_clear(newParents); } return set; } /** Generates complete list of edge-sets for the flow graph */ ArrayList flow_edgeSets() { int i, next; ArrayList list = list_new(flow_size() / 2); // Visit each edge in turn and add to one edge set or other... BitSet children = graph_newNodeSet(flow_graph, FUNC); int size = flow_size(); for(i = 0; i < size; i++) set_add(children, i); while ((next = FIRST_IN(children)) >= 0) { EdgeSet set = buildEdgeSet(next); if (set == NULL) { set_remove(children, next); } else { list_add(list, set); set_removeSet(children, set->children); } } return list; } void flow_print(char* filename) { int i, size = flow_size(); FILE* out = fopen(filename, "w"); ArrayList edge_sets; if (out == NULL) { write_log("Unable to open %s, so no graph dump\n", filename); return; } for (i = 0; i < size; i++) { flow_printNode(i, out); } fprintf(out, "\n"); edge_sets = flow_edgeSets(); size = list_size(edge_sets); fprintf(out, "%d Edge sets\n", size); for(i = 0; i < size; i++) { edgeset_print((EdgeSet)list_get(edge_sets, i), out); } fclose(out); } void printTemps(FILE* out, BitSet set) { if (set) { int i; FOR_EACH(i, set) { fprintf(out, "%s ", localVariableSymbol(i)->name); } } } void flow_printNode(int i, FILE* out) { Block block = flow_block(i); fprintf(out, "Block %d\n", i); fprintf(out, "Parents "); set_print(out, graph_parents(flow_graph, i)); fprintf(out, "\nLive in "); printTemps(out, block_livein(block)); fprintf(out, "\nStart e-depth "); fprintf(out, "%d", block_getStartEDepth(block)); fprintf(out, "\nStart l-depth "); fprintf(out, "%d", block_getStartLDepth(block)); fprintf(out, "\nXStack in:"); xstack_print(block_inStack(block), out); fprintf(out, "\nDefined "); printTemps(out, block_def(block)); fprintf(out, "\nUsed "); printTemps(out, block_use(block)); fprintf(out, "\nRejects "); printTemps(out, block_reject(block)); fprintf(out, "\n"); block_print(block, out); fprintf(out, "\nLive out "); printTemps(out, block_liveout(block)); fprintf(out, "\nEnd l-depth "); fprintf(out, "%d", block_getEndLDepth(block)); fprintf(out, "\nEnd e-depth "); fprintf(out, "%d", block_getEndEDepth(block)); fprintf(out, "\nXStack out:"); xstack_print(block_outStack(block), out); fprintf(out, "\nChildren "); set_print(out, graph_children(flow_graph, i)); fprintf(out, "\n\n"); } void edgeset_print(EdgeSet set, FILE* out) { fprintf(out, "\nParents "); set_print(out, set->parents); fprintf(out, "\nChildren "); set_print(out, set->children); fprintf(out, "\n"); } /** Liveness - from Dragon Book (algorithm 10.4) */ void liveness() { int i, j, size, changed; BitSet livein; size = flow_size(); for (i = 0; i < size; i++) { block_initDefUse(flow_block(i)); } livein = set_clone(block_liveout(flow_block(0))); do { changed = 0; // Go backwards, so changes propagate faster. for (i = size -1; i >= 0; i--) { Block b = flow_block(i); BitSet liveout = block_liveout(b); BitSet children = flow_children(i); FOR_EACH(j, children) { set_addSet(liveout, block_livein(flow_block(j))); } set_clear(livein); set_addSet(livein, liveout); set_removeSet(livein, block_def(b)); set_addSet(livein, block_use(b)); if (!set_equals(livein, block_livein(b))) { changed = 1; set_addSet(block_livein(b), livein); } } } while (changed); }