From d2bf7702e710c054fe2f5f356d7a9d79007fb8cf Mon Sep 17 00:00:00 2001 From: David Given Date: Sat, 17 Dec 2016 10:18:51 +0100 Subject: [PATCH] Bigraph now uses hash tables to hold edges inside vertices, rather than linked lists. --- mach/proto/mcg/pass_nonlocalphis.c | 4 +- mach/proto/mcg/pass_registerallocator.c | 1 + mach/proto/mcg/pass_removedeadphis.c | 2 +- modules/src/data/bigraph.c | 177 ++++++++++-------------- modules/src/data/bigraph.h | 5 +- modules/src/data/hashtable.c | 14 +- modules/src/data/hashtable.h | 3 +- modules/src/data/set.c | 6 +- modules/src/data/set.h | 4 +- 9 files changed, 89 insertions(+), 127 deletions(-) diff --git a/mach/proto/mcg/pass_nonlocalphis.c b/mach/proto/mcg/pass_nonlocalphis.c index 8f0fdc732..52387c76e 100644 --- a/mach/proto/mcg/pass_nonlocalphis.c +++ b/mach/proto/mcg/pass_nonlocalphis.c @@ -48,7 +48,7 @@ static void recursively_move_children_to_confirmed(struct basicblock* bb) { struct basicblock* candidate = bb->nexts.item[i]; - if (set_contains(&pending, candidate)) + if (set_get(&pending, candidate)) { tracef('I', "I: encompassing %s\n", candidate->name); set_remove(&pending, candidate); @@ -142,7 +142,7 @@ static void import_ir(struct ir* phi) if (bb == current_src) pmap_add(&phi->u.phivalue, bb, current_ir); - else if (set_contains(&confirmed, bb) && !already_importing(bb)) + else if (set_get(&confirmed, bb) && !already_importing(bb)) { struct ir* newphi = insert_phi_to_prev(bb, current_ir->size, current_ir); pmap_add(&phi->u.phivalue, bb, newphi); diff --git a/mach/proto/mcg/pass_registerallocator.c b/mach/proto/mcg/pass_registerallocator.c index a906be3bf..4a0c4ea03 100644 --- a/mach/proto/mcg/pass_registerallocator.c +++ b/mach/proto/mcg/pass_registerallocator.c @@ -1189,6 +1189,7 @@ void pass_register_allocator(void) tracef('R', "R: generating interference and preference graphs\n"); hop_walk(build_interference_graph_cb, NULL); +exit(0); tracef('R', "R: before purge, interference=%d nodes, preference=%d nodes\n", interferenceg.vertices.size, preferenceg.vertices.size); diff --git a/mach/proto/mcg/pass_removedeadphis.c b/mach/proto/mcg/pass_removedeadphis.c index fb53f751d..3aa0fe954 100644 --- a/mach/proto/mcg/pass_removedeadphis.c +++ b/mach/proto/mcg/pass_removedeadphis.c @@ -53,7 +53,7 @@ static void purge_unused_phis(struct basicblock* bb) for (i=0; iirs.count; i++) { struct ir* ir = bb->irs.item[i]; - if ((ir->opcode == IR_PHI) && (set_contains(&phis, ir))) + if ((ir->opcode == IR_PHI) && set_get(&phis, ir)) { array_remove(&bb->irs, ir); i--; diff --git a/modules/src/data/bigraph.c b/modules/src/data/bigraph.c index 4499563d6..7f24c9468 100644 --- a/modules/src/data/bigraph.c +++ b/modules/src/data/bigraph.c @@ -3,41 +3,41 @@ #include #include #include "bigraph.h" +#include "set.h" -struct edgenode +struct edge { - struct edgenode* next; - struct vertex* this; - struct vertex* other; + struct vertex* v1; + struct vertex* v2; }; struct vertex { void* data; - struct edgenode* connections; int degree; + struct set edges; }; static uint32_t edge_hash_function(void* key) { - struct edgenode* en = key; + struct edge* edge = key; /* This will always return the same value, even if the two endpoints are swapped. */ - return standard_pointer_hash_function(en->this) ^ standard_pointer_hash_function(en->other); + return standard_pointer_hash_function(edge->v1) ^ standard_pointer_hash_function(edge->v2); } static bool edge_comparison_function(void* key1, void* key2) { - struct edgenode* en1 = key1; - struct edgenode* en2 = key2; + struct edge* edge1 = key1; + struct edge* edge2 = key2; - return ((en1->this == en2->this) && (en1->other == en2->other)) - || ((en1->this == en2->other) && (en1->other == en2->this)); + return ((edge1->v1 == edge2->v1) && (edge1->v2 == edge2->v2)) + || ((edge1->v1 == edge2->v2) && (edge1->v2 == edge2->v1)); } static void lazy_init(struct graph* g) { - g->edges.hashfunction = edge_hash_function; - g->edges.cmpfunction = edge_comparison_function; + g->edges.table.hashfunction = edge_hash_function; + g->edges.table.cmpfunction = edge_comparison_function; } void graph_reset(struct graph* g) @@ -50,22 +50,22 @@ void graph_reset(struct graph* g) if (!vertex) return; - while (vertex->connections) - { - struct edgenode* next = vertex->connections->next; - free(vertex->connections); - vertex->connections = next; - } - + set_reset(&vertex->edges); free(vertex); } + + for (;;) + { + struct edge* edge = set_pop(&g->edges); + free(edge); + } } bool graph_contains_vertex(struct graph* g, void* data) { lazy_init(g); - return hashtable_contains(&g->vertices, data); + return !!hashtable_get(&g->vertices, data); } static struct vertex* find_or_add_vertex(struct graph* g, void* data) @@ -85,101 +85,58 @@ static struct vertex* find_or_add_vertex(struct graph* g, void* data) return vertex; } -static struct edgenode** find_edgep(struct vertex* v1, struct vertex* v2) -{ - struct edgenode** ep = &v1->connections; - - while (*ep) - { - if ((*ep)->other == v2) - return ep; - ep = &(*ep)->next; - } - - return ep; -} - bool graph_contains_edge(struct graph* g, void* data1, void* data2) { - struct vertex* v1 = find_or_add_vertex(g, data1); - struct vertex* v2 = find_or_add_vertex(g, data2); - - if (!v1 || !v2) - return false; + struct edge template; - return *find_edgep(v1, v2) || *find_edgep(v2, v1); -} - -static struct edgenode* add_edge(struct vertex* v1, struct vertex* v2) -{ - struct edgenode** ep = find_edgep(v1, v2); - if (!*ep) - { - *ep = calloc(1, sizeof(struct edgenode)); - (*ep)->this = v1; - (*ep)->other = v2; - v1->degree++; - } + template.v1 = find_or_add_vertex(g, data1); + template.v2 = find_or_add_vertex(g, data2); + if (!template.v1 || !template.v2) + return false; - return *ep; + return !!set_get(&g->edges, &template); } void graph_add_edge(struct graph* g, void* data1, void* data2) { - struct vertex* v1 = find_or_add_vertex(g, data1); - struct vertex* v2 = find_or_add_vertex(g, data2); - struct edgenode* e; - struct edgenode template; + struct edge template; + struct edge* e; - if (v1 == v2) + template.v1 = find_or_add_vertex(g, data1); + template.v2 = find_or_add_vertex(g, data2); + if (template.v1 == template.v2) return; - template.this = v1; - template.other = v2; - if (hashtable_contains(&g->edges, &template)) + if (set_get(&g->edges, &template)) return; - add_edge(v1, v2); - e = add_edge(v2, v1); + e = calloc(1, sizeof(struct edge)); + *e = template; - hashtable_put(&g->edges, e, e); -} - -static struct edgenode* remove_edge(struct vertex* v1, struct vertex* v2) -{ - struct edgenode** ep = find_edgep(v1, v2); - - if (*ep) - { - struct edgenode* old = *ep; - *ep = (*ep)->next; - v1->degree--; - return old; - } - - return NULL; + set_add(&g->edges, e); + set_add(&template.v1->edges, e); + set_add(&template.v2->edges, e); + template.v1->degree++; + template.v2->degree++; } void graph_remove_edge(struct graph* g, void* data1, void* data2) { + struct edge template; struct vertex* v1 = find_or_add_vertex(g, data1); struct vertex* v2 = find_or_add_vertex(g, data2); - struct edgenode* e1 = remove_edge(v1, v2); - struct edgenode* e2 = remove_edge(v2, v1); - assert(!e1 == !e2); + template.v1 = find_or_add_vertex(g, data1); + template.v2 = find_or_add_vertex(g, data2); + if (template.v1 == template.v2) + return; - if (e1) - { - /* e1 is a template; the actual object in the hashtable might actually - * be e2 (as they compare the same). So, remove from the hashtable - * before freeing anything. */ - hashtable_remove(&g->edges, e1); - free(e1); - } - if (e2) - free(e2); + set_remove(&template.v1->edges, &template); + set_remove(&template.v2->edges, &template); + free(set_remove(&g->edges, &template)); + template.v1->degree--; + template.v2->degree--; } void graph_add_vertex(struct graph* g, void* data) @@ -196,17 +153,25 @@ void graph_remove_vertex(struct graph* g, void* data) if (!vertex) return; - while (vertex->connections) - { - struct edgenode* next = vertex->connections->next; - struct edgenode* e = remove_edge(vertex->connections->other, vertex); - hashtable_remove(&g->edges, vertex->connections); - free(e); - free(vertex->connections); - vertex->connections = next; - } - + for (;;) + { + struct vertex* other; + struct edge* e = set_pop(&vertex->edges); + if (!e) + break; + + other = e->v1; + if (other == vertex) + other = e->v2; + + set_remove(&other->edges, e); + other->degree--; + free(set_remove(&g->edges, e)); + } + + set_reset(&vertex->edges); hashtable_remove(&g->vertices, data); + free(vertex); } int graph_get_vertex_degree(struct graph* g, void* data) @@ -233,11 +198,11 @@ void* graph_next_vertex(struct graph* g, struct vertex_iterator* it) bool graph_next_edge(struct graph* g, struct edge_iterator* it) { - struct edgenode* e = hashtable_next(&g->edges, &it->hit); + struct edge* e = set_next(&g->edges, &it->sit); if (e) { - it->left = e->this->data; - it->right = e->other->data; + it->left = e->v1->data; + it->right = e->v2->data; return true; } else diff --git a/modules/src/data/bigraph.h b/modules/src/data/bigraph.h index 673d4364f..e33762bce 100644 --- a/modules/src/data/bigraph.h +++ b/modules/src/data/bigraph.h @@ -2,13 +2,14 @@ #define BIGRAPH_H #include "hashtable.h" +#include "set.h" /* A bidirectional graph with node addition and removal capabilities. */ struct graph { struct hashtable vertices; - struct hashtable edges; + struct set edges; }; struct vertex_iterator @@ -27,7 +28,7 @@ struct edge_iterator void* right; /* Private */ - struct hashtable_iterator hit; + struct set_iterator sit; }; extern void graph_reset(struct graph* g); diff --git a/modules/src/data/hashtable.c b/modules/src/data/hashtable.c index 35dfe5ae1..8e43d9e8c 100644 --- a/modules/src/data/hashtable.c +++ b/modules/src/data/hashtable.c @@ -25,7 +25,7 @@ bool standard_pointer_comparison_function(void* key1, void* key2) static void lazy_init(struct hashtable* ht) { if (!ht->num_buckets) - ht->num_buckets = 37; + ht->num_buckets = 7; if (!ht->hashfunction) ht->hashfunction = standard_pointer_hash_function; @@ -120,24 +120,20 @@ void* hashtable_get(struct hashtable* ht, void* key) return NULL; } -bool hashtable_contains(struct hashtable* ht, void* key) -{ - return *findnodep(ht, key); -} - -bool hashtable_remove(struct hashtable* ht, void* key) +void* hashtable_remove(struct hashtable* ht, void* key) { struct hashnode** hnp = findnodep(ht, key); if (*hnp) { struct hashnode* hn = *hnp; + void* value = hn->value; *hnp = hn->next; free(hn); ht->size--; - return true; + return value; } - return false; + return NULL; } void* hashtable_pop(struct hashtable* ht) diff --git a/modules/src/data/hashtable.h b/modules/src/data/hashtable.h index 2838d81b1..47304110e 100644 --- a/modules/src/data/hashtable.h +++ b/modules/src/data/hashtable.h @@ -35,8 +35,7 @@ extern void hashtable_rebucket(struct hashtable* ht, unsigned int num_buckets); extern void* hashtable_put(struct hashtable* ht, void* key, void* data); extern void* hashtable_get(struct hashtable* ht, void* key); -extern bool hashtable_contains(struct hashtable* ht, void* key); -extern bool hashtable_remove(struct hashtable* ht, void* key); +extern void* hashtable_remove(struct hashtable* ht, void* key); extern void* hashtable_pop(struct hashtable* ht); extern void* hashtable_next(struct hashtable* ht, struct hashtable_iterator* it); diff --git a/modules/src/data/set.c b/modules/src/data/set.c index fd0ab9aac..5c3cb5aaa 100644 --- a/modules/src/data/set.c +++ b/modules/src/data/set.c @@ -18,14 +18,14 @@ bool set_add(struct set* s, void* item) return hashtable_put(&s->table, item, item); } -bool set_remove(struct set* s, void* item) +void* set_remove(struct set* s, void* item) { return hashtable_remove(&s->table, item); } -bool set_contains(struct set* s, void* item) +void* set_get(struct set* s, void* item) { - return hashtable_contains(&s->table, item); + return hashtable_get(&s->table, item); } void* set_pop(struct set* s) diff --git a/modules/src/data/set.h b/modules/src/data/set.h index 97956811e..5069ca0f1 100644 --- a/modules/src/data/set.h +++ b/modules/src/data/set.h @@ -14,8 +14,8 @@ extern void set_empty(struct set* s); extern void set_reset(struct set* s); extern bool set_add(struct set* s, void* item); -extern bool set_remove(struct set* s, void* item); -extern bool set_contains(struct set* s, void* item); +extern void* set_remove(struct set* s, void* item); +extern void* set_get(struct set* s, void* item); extern void* set_pop(struct set* s); struct set_iterator -- 2.34.1