X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=optimal.c;h=01c8fe193ec92fdde3f0125b33ae06e5963f5350;hb=b53f0ce545ee17c6af98601216f1591e5db3c5cb;hp=a1a97f4a68881f945d3b37ae5080018ad74c92ad;hpb=0e06345406059230d8894f55062eb6ea04a195e6;p=libfirm diff --git a/optimal.c b/optimal.c index a1a97f4a6..01c8fe193 100644 --- a/optimal.c +++ b/optimal.c @@ -47,6 +47,7 @@ #include "timing.h" pbqp_edge **edge_bucket; +pbqp_edge **rm_bucket; pbqp_node **node_buckets[4]; pbqp_node **reduced_bucket = NULL; static int buckets_filled = 0; @@ -61,11 +62,22 @@ static void insert_into_edge_bucket(pbqp_edge *edge) edge_bucket_insert(&edge_bucket, edge); } +static void insert_into_rm_bucket(pbqp_edge *edge) +{ + if (edge_bucket_contains(rm_bucket, edge)) { + /* Edge is already inserted. */ + return; + } + + edge_bucket_insert(&rm_bucket, edge); +} + static void init_buckets(void) { int i; edge_bucket_init(&edge_bucket); + edge_bucket_init(&rm_bucket); node_bucket_init(&reduced_bucket); for (i = 0; i < 4; ++i) { @@ -82,6 +94,7 @@ void free_buckets(void) } edge_bucket_free(&edge_bucket); + edge_bucket_free(&rm_bucket); node_bucket_free(&reduced_bucket); buckets_filled = 0; @@ -96,8 +109,8 @@ void fill_node_buckets(pbqp *pbqp) node_len = pbqp->num_nodes; #if KAPS_TIMING - ir_timer_t *t_fill_buckets = ir_timer_register("be_pbqp_fill_buckets", "PBQP Fill Nodes into buckets"); - ir_timer_reset_and_start(t_fill_buckets); + ir_timer_t *t_fill_buckets = ir_timer_new(); + ir_timer_start(t_fill_buckets); #endif for (node_index = 0; node_index < node_len; ++node_index) { @@ -120,7 +133,7 @@ void fill_node_buckets(pbqp *pbqp) #if KAPS_TIMING ir_timer_stop(t_fill_buckets); - printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_fill_buckets), (double)ir_timer_elapsed_usec(t_fill_buckets) / 1000.0); + printf("PBQP Fill Nodes into buckets: %8.3lf msec\n", (double)ir_timer_elapsed_usec(t_fill_buckets) / 1000.0); #endif } @@ -285,11 +298,12 @@ static void merge_source_into_target(pbqp *pbqp, pbqp_edge *edge) mat = edge->costs; assert(mat); - mapping = NEW_ARR_F(unsigned, src_len); + mapping = NEW_ARR_F(unsigned, tgt_len); /* Check that each column has at most one zero entry. */ for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) { unsigned onlyOneZero = 0; + if (tgt_vec->entries[tgt_index].data == INF_COSTS) continue; @@ -321,9 +335,11 @@ static void merge_source_into_target(pbqp *pbqp, pbqp_edge *edge) /* Reconnect the source's edges with the target node. */ for (edge_index = 0; edge_index < edge_len; ++edge_index) { pbqp_edge *old_edge = src_node->edges[edge_index]; + pbqp_edge *new_edge; pbqp_matrix *old_matrix; pbqp_matrix *new_matrix; pbqp_node *other_node; + vector *other_vec; unsigned other_len; unsigned other_index; unsigned tgt_index; @@ -337,83 +353,85 @@ static void merge_source_into_target(pbqp *pbqp, pbqp_edge *edge) assert(old_matrix); if (old_edge->tgt == src_node) { - other_node = edge->src; + other_node = old_edge->src; other_len = old_matrix->rows; } else { - other_node = edge->tgt; + other_node = old_edge->tgt; other_len = old_matrix->cols; } assert(other_node); + other_vec = other_node->costs; new_matrix = pbqp_matrix_alloc(pbqp, tgt_len, other_len); /* Source node selects the column of the old_matrix. */ if (old_edge->tgt == src_node) { for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) { - unsigned old_index = mapping[tgt_index]; + unsigned src_index = mapping[tgt_index]; + + if (tgt_vec->entries[tgt_index].data == INF_COSTS) + continue; + for (other_index = 0; other_index < other_len; ++other_index) { - new_matrix->entries[tgt_index*other_len+other_index] = old_matrix->entries[other_index*src_len+old_index]; + if (other_vec->entries[other_index].data == INF_COSTS) + continue; + + new_matrix->entries[tgt_index*other_len+other_index] = old_matrix->entries[other_index*src_len+src_index]; } } } /* Source node selects the row of the old_matrix. */ else { for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) { - unsigned old_index = mapping[tgt_index]; + unsigned src_index = mapping[tgt_index]; + + if (tgt_vec->entries[tgt_index].data == INF_COSTS) + continue; + for (other_index = 0; other_index < other_len; ++other_index) { - new_matrix->entries[tgt_index*other_len+other_index] = old_matrix->entries[old_index*other_len+other_index]; + if (other_vec->entries[other_index].data == INF_COSTS) + continue; + + new_matrix->entries[tgt_index*other_len+other_index] = old_matrix->entries[src_index*other_len+other_index]; } } } add_edge_costs(pbqp, tgt_node->index, other_node->index, new_matrix); - disconnect_edge(src_node, old_edge); - disconnect_edge(other_node, old_edge); + delete_edge(old_edge); + reorder_node(src_node); + reorder_node(other_node); + + new_edge = get_edge(pbqp, tgt_node->index, other_node->index); + insert_into_rm_bucket(new_edge); } /* Reduce the remaining source node via RI. */ apply_RI(pbqp); } - -void reorder_node(pbqp_node *node) -{ - unsigned degree = pbqp_node_get_degree(node); - /* Assume node lost one incident edge. */ - unsigned old_degree = degree + 1; - - if (!buckets_filled) return; - - /* Same bucket as before */ - if (degree > 2) return; - - if (!node_bucket_contains(node_buckets[old_degree], node)) { - /* Old arity is new arity, so we have nothing to do. */ - assert(node_bucket_contains(node_buckets[degree], node)); - return; - } - - /* Delete node from old bucket... */ - node_bucket_remove(&node_buckets[old_degree], node); - - /* ..and add to new one. */ - node_bucket_insert(&node_buckets[degree], node); -} - -#if KAPS_STATISTIC -void check_melting_possibility(pbqp *pbqp, pbqp_edge *edge) +/** + * Tries to apply RM for the target node of the given edge. + * + * Checks whether the target node of edge can be merged into the source node of + * edge, and performs the merge, if possible. + */ +static void merge_target_into_source(pbqp *pbqp, pbqp_edge *edge) { pbqp_matrix *mat; pbqp_node *src_node; pbqp_node *tgt_node; vector *src_vec; vector *tgt_vec; - int src_len; - int tgt_len; - int src_index; - int tgt_index; + unsigned *mapping; + unsigned src_len; + unsigned tgt_len; + unsigned src_index; + unsigned tgt_index; + unsigned edge_index; + unsigned edge_len; assert(pbqp); assert(edge); @@ -430,77 +448,185 @@ void check_melting_possibility(pbqp *pbqp, pbqp_edge *edge) src_len = src_vec->len; tgt_len = tgt_vec->len; - assert(src_len > 0); - assert(tgt_len > 0); + + /* Matrizes are normalized. */ + assert(src_len > 1); + assert(tgt_len > 1); mat = edge->costs; assert(mat); - if (src_len == 1 && tgt_len == 1) { - //panic("Something is wrong"); - } + mapping = NEW_ARR_F(unsigned, src_len); - int allRowsOk = 1; + /* Check that each row has at most one zero entry. */ for (src_index = 0; src_index < src_len; ++src_index) { - int onlyOneZero = 0; - if (src_vec->entries[src_index].data == INF_COSTS) { + unsigned onlyOneZero = 0; + + if (src_vec->entries[src_index].data == INF_COSTS) continue; - } + for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) { - if (tgt_vec->entries[tgt_index].data == INF_COSTS) { + if (tgt_vec->entries[tgt_index].data == INF_COSTS) continue; - } - if (mat->entries[src_index * tgt_len + tgt_index] == 0) { - if (onlyOneZero) { - onlyOneZero = 0; - break; - } else { - onlyOneZero = 1; - continue; - } - } - if (mat->entries[src_index * tgt_len + tgt_index] == INF_COSTS) { + + if (mat->entries[src_index * tgt_len + tgt_index] == INF_COSTS) continue; + + /* Matrix entry is finite. */ + if (onlyOneZero) { + DEL_ARR_F(mapping); + return; } - onlyOneZero = 0; - break; + + onlyOneZero = 1; + mapping[src_index] = tgt_index; } - allRowsOk &= onlyOneZero; } - int allColsOk = 1; - for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) { - int onlyOneZero = 0; - if (tgt_vec->entries[tgt_index].data == INF_COSTS) { + /* We know that we can merge the target node into the source node. */ + edge_len = pbqp_node_get_degree(tgt_node); + +#if KAPS_STATISTIC + pbqp->num_rm++; +#endif + + /* Reconnect the target's edges with the source node. */ + for (edge_index = 0; edge_index < edge_len; ++edge_index) { + pbqp_edge *old_edge = tgt_node->edges[edge_index]; + pbqp_edge *new_edge; + pbqp_matrix *old_matrix; + pbqp_matrix *new_matrix; + pbqp_node *other_node; + vector *other_vec; + unsigned other_len; + unsigned other_index; + unsigned src_index; + + assert(old_edge); + + if (old_edge == edge) continue; + + old_matrix = old_edge->costs; + assert(old_matrix); + + if (old_edge->tgt == tgt_node) { + other_node = old_edge->src; + other_len = old_matrix->rows; } - for (src_index = 0; src_index < src_len; ++src_index) { - if (src_vec->entries[src_index].data == INF_COSTS) { - continue; - } - if (mat->entries[src_index * tgt_len + tgt_index] == 0) { - if (onlyOneZero) { - onlyOneZero = 0; - break; - } else { - onlyOneZero = 1; + else { + other_node = old_edge->tgt; + other_len = old_matrix->cols; + } + assert(other_node); + other_vec = other_node->costs; + + new_matrix = pbqp_matrix_alloc(pbqp, src_len, other_len); + + /* Target node selects the column of the old_matrix. */ + if (old_edge->tgt == tgt_node) { + for (src_index = 0; src_index < src_len; ++src_index) { + unsigned tgt_index = mapping[src_index]; + + if (src_vec->entries[src_index].data == INF_COSTS) continue; + + for (other_index = 0; other_index < other_len; ++other_index) { + if (other_vec->entries[other_index].data == INF_COSTS) + continue; + + new_matrix->entries[src_index*other_len+other_index] = old_matrix->entries[other_index*tgt_len+tgt_index]; } } - if (mat->entries[src_index * tgt_len + tgt_index] == INF_COSTS) { - continue; + } + /* Source node selects the row of the old_matrix. */ + else { + for (src_index = 0; src_index < src_len; ++src_index) { + unsigned tgt_index = mapping[src_index]; + + if (src_vec->entries[src_index].data == INF_COSTS) + continue; + + for (other_index = 0; other_index < other_len; ++other_index) { + if (other_vec->entries[other_index].data == INF_COSTS) + continue; + + new_matrix->entries[src_index*other_len+other_index] = old_matrix->entries[tgt_index*other_len+other_index]; + } } - onlyOneZero = 0; - break; } - allColsOk &= onlyOneZero; + + add_edge_costs(pbqp, src_node->index, other_node->index, new_matrix); + + delete_edge(old_edge); + reorder_node(tgt_node); + reorder_node(other_node); + + new_edge = get_edge(pbqp, src_node->index, other_node->index); + insert_into_rm_bucket(new_edge); + } + + /* Reduce the remaining source node via RI. */ + apply_RI(pbqp); +} + +/** + * Merge neighbors into the given node. + */ +void apply_RM(pbqp *pbqp, pbqp_node *node) +{ + pbqp_edge **edges; + unsigned edge_index; + unsigned edge_len; + + assert(node); + assert(pbqp); + + edges = node->edges; + edge_len = pbqp_node_get_degree(node); + + /* Check all incident edges. */ + for (edge_index = 0; edge_index < edge_len; ++edge_index) { + pbqp_edge *edge = edges[edge_index]; + + insert_into_rm_bucket(edge); } - if (allRowsOk || allColsOk) { - pbqp->num_rm++; + /* ALAP: Merge neighbors into given node. */ + while(edge_bucket_get_length(rm_bucket) > 0) { + pbqp_edge *edge = edge_bucket_pop(&rm_bucket); + assert(edge); + + if (edge->src == node) + merge_target_into_source(pbqp, edge); + else + merge_source_into_target(pbqp, edge); } } -#endif + +void reorder_node(pbqp_node *node) +{ + unsigned degree = pbqp_node_get_degree(node); + /* Assume node lost one incident edge. */ + unsigned old_degree = degree + 1; + + if (!buckets_filled) return; + + /* Same bucket as before */ + if (degree > 2) return; + + if (!node_bucket_contains(node_buckets[old_degree], node)) { + /* Old arity is new arity, so we have nothing to do. */ + assert(node_bucket_contains(node_buckets[degree], node)); + return; + } + + /* Delete node from old bucket... */ + node_bucket_remove(&node_buckets[old_degree], node); + + /* ..and add to new one. */ + node_bucket_insert(&node_buckets[degree], node); +} void simplify_edge(pbqp *pbqp, pbqp_edge *edge) { @@ -587,8 +713,8 @@ void initial_simplify_edges(pbqp *pbqp) assert(pbqp); #if KAPS_TIMING - ir_timer_t *t_int_simpl = ir_timer_register("be_pbqp_init_simp", "PBQP Initial simplify edges"); - ir_timer_reset_and_start(t_int_simpl); + ir_timer_t *t_int_simpl = ir_timer_new(); + ir_timer_start(t_int_simpl); #endif #if KAPS_DUMP @@ -626,7 +752,7 @@ void initial_simplify_edges(pbqp *pbqp) #if KAPS_TIMING ir_timer_stop(t_int_simpl); - printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_int_simpl), (double)ir_timer_elapsed_usec(t_int_simpl) / 1000.0); + printf("PBQP Initial simplify edges: %8.3lf msec\n", (double)ir_timer_elapsed_usec(t_int_simpl) / 1000.0); #endif } @@ -637,7 +763,7 @@ num determine_solution(pbqp *pbqp) num solution = 0; #if KAPS_TIMING - ir_timer_t *t_det_solution = ir_timer_register("be_det_solution", "PBQP Determine Solution"); + ir_timer_t *t_det_solution = ir_timer_new(); ir_timer_reset_and_start(t_det_solution); #endif @@ -692,7 +818,7 @@ num determine_solution(pbqp *pbqp) #if KAPS_TIMING ir_timer_stop(t_det_solution); - printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_det_solution), (double)ir_timer_elapsed_usec(t_det_solution) / 1000.0); + printf("PBQP Determine Solution: %8.3lf msec\n", (double)ir_timer_elapsed_usec(t_det_solution) / 1000.0); #endif return solution;