summaryrefslogtreecommitdiffhomepage
path: root/ir/kaps
diff options
context:
space:
mode:
authorSebastian Buchwald <Sebastian.Buchwald@kit.edu>2013-01-22 13:31:15 +0100
committerSebastian Buchwald <Sebastian.Buchwald@kit.edu>2013-01-23 13:44:32 +0100
commit9919df82486bf86fadb339eb6cb11c317b28ee6a (patch)
tree264d17b646ea8990c8b979af319f9b30b0101a6d /ir/kaps
parentdfa4f0499c3d7f7f3ed023d351171cec3789ee09 (diff)
Cleanup kaps code (using C99).
Diffstat (limited to 'ir/kaps')
-rw-r--r--ir/kaps/brute_force.c94
-rw-r--r--ir/kaps/bucket.c36
-rw-r--r--ir/kaps/heuristical.c11
-rw-r--r--ir/kaps/heuristical_co.c20
-rw-r--r--ir/kaps/heuristical_co_ld.c107
-rw-r--r--ir/kaps/html_dumper.c53
-rw-r--r--ir/kaps/kaps.c36
-rw-r--r--ir/kaps/kaps.h2
-rw-r--r--ir/kaps/matrix.c169
-rw-r--r--ir/kaps/optimal.c645
-rw-r--r--ir/kaps/pbqp_edge.c26
-rw-r--r--ir/kaps/pbqp_node.c47
-rw-r--r--ir/kaps/vector.c62
13 files changed, 499 insertions, 809 deletions
diff --git a/ir/kaps/brute_force.c b/ir/kaps/brute_force.c
index 33e36e6..612974e 100644
--- a/ir/kaps/brute_force.c
+++ b/ir/kaps/brute_force.c
@@ -11,6 +11,8 @@
*/
#include "config.h"
+#include <stdbool.h>
+
#include "assert.h"
#include "error.h"
@@ -54,25 +56,19 @@ static void apply_brute_force_reductions(pbqp_t *pbqp)
static unsigned get_minimal_alternative(pbqp_t *pbqp, pbqp_node_t *node)
{
- vector_t *node_vec;
- unsigned node_index;
- unsigned node_len;
+ vector_t *node_vec = node->costs;
+ unsigned node_len = node_vec->len;
unsigned min_index = 0;
num min = INF_COSTS;
- unsigned bucket_index;
-
- assert(pbqp);
- node_vec = node->costs;
- node_len = node_vec->len;
- bucket_index = node->bucket_index;
+ unsigned bucket_index = node->bucket_index;
- for (node_index = 0; node_index < node_len; ++node_index) {
+ for (unsigned node_index = 0; node_index < node_len; ++node_index) {
pbqp_node_bucket_t bucket_deg3;
num value;
unsigned bucket_0_length;
unsigned bucket_red_length;
- char *tmp = (char*)obstack_finish(&pbqp->obstack);
+ char *tmp = (char *)obstack_finish(&pbqp->obstack);
node_bucket_init(&bucket_deg3);
@@ -128,13 +124,8 @@ static unsigned get_minimal_alternative(pbqp_t *pbqp, pbqp_node_t *node)
static void apply_Brute_Force(pbqp_t *pbqp)
{
- pbqp_node_t *node = NULL;
- unsigned min_index = 0;
-
- assert(pbqp);
-
/* We want to reduce a node with maximum degree. */
- node = get_node_with_max_degree();
+ pbqp_node_t *node = get_node_with_max_degree();
assert(pbqp_node_get_degree(node) > 2);
#if KAPS_DUMP
@@ -150,13 +141,12 @@ static void apply_Brute_Force(pbqp_t *pbqp)
dump++;
#endif
- min_index = get_minimal_alternative(pbqp, node);
+ unsigned min_index = get_minimal_alternative(pbqp, node);
node = pbqp->nodes[node->index];
#if KAPS_DUMP
if (pbqp->dump_file) {
- fprintf(pbqp->dump_file, "node n%d is set to %d<br><br>\n",
- node->index, min_index);
+ fprintf(pbqp->dump_file, "node n%d is set to %d<br><br>\n", node->index, min_index);
}
#endif
@@ -174,22 +164,13 @@ static void apply_Brute_Force(pbqp_t *pbqp)
select_alternative(node, min_index);
}
-
-
static void back_propagate_RI(pbqp_t *pbqp, pbqp_node_t *node)
{
- pbqp_edge_t *edge;
+ pbqp_edge_t *edge = node->edges[0];
pbqp_node_t *other;
- pbqp_matrix_t *mat;
- vector_t *vec;
- int is_src;
-
- assert(pbqp);
-
- edge = node->edges[0];
- mat = edge->costs;
- is_src = edge->src == node;
- vec = node->costs;
+ pbqp_matrix_t *mat = edge->costs;
+ vector_t *vec = node->costs;
+ bool is_src = edge->src == node;
if (is_src) {
other = edge->tgt;
@@ -218,18 +199,10 @@ static void back_propagate_RII(pbqp_t *pbqp, pbqp_node_t *node)
{
pbqp_edge_t *src_edge = node->edges[0];
pbqp_edge_t *tgt_edge = node->edges[1];
- int src_is_src = src_edge->src == node;
- int tgt_is_src = tgt_edge->src == node;
- pbqp_matrix_t *src_mat;
- pbqp_matrix_t *tgt_mat;
+ bool src_is_src = src_edge->src == node;
+ bool tgt_is_src = tgt_edge->src == node;
pbqp_node_t *src_node;
pbqp_node_t *tgt_node;
- vector_t *vec;
- vector_t *node_vec;
- unsigned col_index;
- unsigned row_index;
-
- assert(pbqp);
if (src_is_src) {
src_node = src_edge->tgt;
@@ -245,14 +218,11 @@ static void back_propagate_RII(pbqp_t *pbqp, pbqp_node_t *node)
/* Swap nodes if necessary. */
if (tgt_node->index < src_node->index) {
- pbqp_node_t *tmp_node;
- pbqp_edge_t *tmp_edge;
-
- tmp_node = src_node;
+ pbqp_node_t *tmp_node = src_node;
src_node = tgt_node;
tgt_node = tmp_node;
- tmp_edge = src_edge;
+ pbqp_edge_t *tmp_edge = src_edge;
src_edge = tgt_edge;
tgt_edge = tmp_edge;
@@ -264,15 +234,12 @@ static void back_propagate_RII(pbqp_t *pbqp, pbqp_node_t *node)
src_node = pbqp->nodes[src_node->index];
tgt_node = pbqp->nodes[tgt_node->index];
- src_mat = src_edge->costs;
- tgt_mat = tgt_edge->costs;
-
- node_vec = node->costs;
-
- row_index = src_node->solution;
- col_index = tgt_node->solution;
-
- vec = vector_copy(pbqp, node_vec);
+ pbqp_matrix_t *src_mat = src_edge->costs;
+ pbqp_matrix_t *tgt_mat = tgt_edge->costs;
+ vector_t *node_vec = node->costs;
+ unsigned col_index = tgt_node->solution;
+ unsigned row_index = src_node->solution;
+ vector_t *vec = vector_copy(pbqp, node_vec);
if (src_is_src) {
vector_add_matrix_col(vec, src_mat, row_index);
@@ -299,19 +266,16 @@ static void back_propagate_RII(pbqp_t *pbqp, pbqp_node_t *node)
static void back_propagate_brute_force(pbqp_t *pbqp)
{
- unsigned node_index;
- unsigned node_len = node_bucket_get_length(reduced_bucket);
-
- assert(pbqp);
-
#if KAPS_DUMP
if (pbqp->dump_file) {
pbqp_dump_section(pbqp->dump_file, 2, "Back Propagation");
}
#endif
- for (node_index = node_len; node_index > 0; --node_index) {
- pbqp_node_t *node = reduced_bucket[node_index - 1];
+ unsigned node_len = node_bucket_get_length(reduced_bucket);
+
+ for (unsigned node_index = node_len; node_index-- != 0;) {
+ pbqp_node_t *node = reduced_bucket[node_index];
switch (pbqp_node_get_degree(node)) {
case 1:
@@ -328,6 +292,8 @@ static void back_propagate_brute_force(pbqp_t *pbqp)
void solve_pbqp_brute_force(pbqp_t *pbqp)
{
+ assert(pbqp);
+
/* Reduce nodes degree ... */
initial_simplify_edges(pbqp);
diff --git a/ir/kaps/bucket.c b/ir/kaps/bucket.c
index f3aac22..b95668b 100644
--- a/ir/kaps/bucket.c
+++ b/ir/kaps/bucket.c
@@ -48,12 +48,11 @@ void edge_bucket_insert(pbqp_edge_bucket_t *bucket, pbqp_edge_t *edge)
pbqp_edge_t *edge_bucket_pop(pbqp_edge_bucket_t *bucket)
{
- unsigned bucket_len = edge_bucket_get_length(*bucket);
- pbqp_edge_t *edge;
+ unsigned bucket_len = edge_bucket_get_length(*bucket);
assert(bucket_len > 0);
- edge = (*bucket)[bucket_len - 1];
+ pbqp_edge_t *edge = (*bucket)[bucket_len - 1];
ARR_SHRINKLEN(*bucket, (int)bucket_len - 1);
edge->bucket_index = UINT_MAX;
@@ -74,20 +73,18 @@ int node_bucket_contains(pbqp_node_bucket_t bucket, pbqp_node_t *node)
void node_bucket_copy(pbqp_node_bucket_t *dst, pbqp_node_bucket_t src)
{
- unsigned src_index;
unsigned src_length = node_bucket_get_length(src);
- for (src_index = 0; src_index < src_length; ++src_index) {
+ for (unsigned src_index = 0; src_index < src_length; ++src_index) {
node_bucket_insert(dst, src[src_index]);
}
}
void node_bucket_update(pbqp_t *pbqp, pbqp_node_bucket_t bucket)
{
- unsigned index;
unsigned length = node_bucket_get_length(bucket);
- for (index = 0; index < length; ++index) {
+ for (unsigned index = 0; index < length; ++index) {
pbqp->nodes[bucket[index]->index] = bucket[index];
}
}
@@ -116,12 +113,11 @@ void node_bucket_insert(pbqp_node_bucket_t *bucket, pbqp_node_t *node)
pbqp_node_t *node_bucket_pop(pbqp_node_bucket_t *bucket)
{
- unsigned bucket_len = node_bucket_get_length(*bucket);
- pbqp_node_t *node;
+ unsigned bucket_len = node_bucket_get_length(*bucket);
assert(bucket_len > 0);
- node = (*bucket)[bucket_len - 1];
+ pbqp_node_t *node = (*bucket)[bucket_len - 1];
ARR_SHRINKLEN(*bucket, (int)bucket_len - 1);
node->bucket_index = UINT_MAX;
@@ -131,14 +127,12 @@ pbqp_node_t *node_bucket_pop(pbqp_node_bucket_t *bucket)
void node_bucket_remove(pbqp_node_bucket_t *bucket, pbqp_node_t *node)
{
- unsigned bucket_len = node_bucket_get_length(*bucket);
- unsigned node_index;
- pbqp_node_t *other;
-
assert(node_bucket_contains(*bucket, node));
- node_index = node->bucket_index;
- other = (*bucket)[bucket_len - 1];
+ unsigned bucket_len = node_bucket_get_length(*bucket);
+ unsigned node_index = node->bucket_index;
+ pbqp_node_t *other = (*bucket)[bucket_len - 1];
+
other->bucket_index = node_index;
(*bucket)[node_index] = other;
@@ -146,15 +140,11 @@ void node_bucket_remove(pbqp_node_bucket_t *bucket, pbqp_node_t *node)
node->bucket_index = UINT_MAX;
}
-void node_bucket_deep_copy(pbqp_t *pbqp, pbqp_node_bucket_t *dst,
- pbqp_node_bucket_t src)
+void node_bucket_deep_copy(pbqp_t *pbqp, pbqp_node_bucket_t *dst, pbqp_node_bucket_t src)
{
- unsigned bucket_index;
- unsigned bucket_length;
-
- bucket_length = node_bucket_get_length(src);
+ unsigned bucket_length = node_bucket_get_length(src);
- for (bucket_index = 0; bucket_index < bucket_length; ++bucket_index) {
+ for (unsigned bucket_index = 0; bucket_index < bucket_length; ++bucket_index) {
node_bucket_insert(dst, pbqp_node_deep_copy(pbqp, *dst, src[bucket_index]));
}
}
diff --git a/ir/kaps/heuristical.c b/ir/kaps/heuristical.c
index 4e6a4e3..bfdf72e 100644
--- a/ir/kaps/heuristical.c
+++ b/ir/kaps/heuristical.c
@@ -33,13 +33,8 @@
static void apply_RN(pbqp_t *pbqp)
{
- pbqp_node_t *node = NULL;
- unsigned min_index = 0;
-
- assert(pbqp);
-
/* We want to reduce a node with maximum degree. */
- node = get_node_with_max_degree();
+ pbqp_node_t *node = get_node_with_max_degree();
assert(pbqp_node_get_degree(node) > 2);
#if KAPS_DUMP
@@ -51,7 +46,7 @@ static void apply_RN(pbqp_t *pbqp)
}
#endif
- min_index = get_local_minimal_alternative(pbqp, node);
+ unsigned min_index = get_local_minimal_alternative(pbqp, node);
#if KAPS_DUMP
if (pbqp->dump_file) {
@@ -90,6 +85,8 @@ static void apply_heuristic_reductions(pbqp_t *pbqp)
void solve_pbqp_heuristical(pbqp_t *pbqp)
{
+ assert(pbqp);
+
/* Reduce nodes degree ... */
initial_simplify_edges(pbqp);
diff --git a/ir/kaps/heuristical_co.c b/ir/kaps/heuristical_co.c
index c57e459..8786db9 100644
--- a/ir/kaps/heuristical_co.c
+++ b/ir/kaps/heuristical_co.c
@@ -34,19 +34,17 @@
static void merge_into_RN_node(pbqp_t *pbqp, plist_t *rpeo)
{
- pbqp_node_t *node = NULL;
-
- assert(pbqp);
+ pbqp_node_t *node;
/* We want to reduce the first node in reverse perfect elimination order. */
do {
/* get first element from reverse perfect elimination order */
- node = (pbqp_node_t*)plist_first(rpeo)->data;
+ node = (pbqp_node_t *)plist_first(rpeo)->data;
/* remove element from reverse perfect elimination order */
plist_erase(rpeo, plist_first(rpeo));
/* insert node at the end of rpeo so the rpeo already exits after pbqp solving */
plist_insert_back(rpeo, node);
- } while(node_is_reduced(node));
+ } while (node_is_reduced(node));
assert(pbqp_node_get_degree(node) > 2);
@@ -56,12 +54,7 @@ static void merge_into_RN_node(pbqp_t *pbqp, plist_t *rpeo)
static void apply_RN_co(pbqp_t *pbqp)
{
- pbqp_node_t *node;
- unsigned min_index;
-
- assert(pbqp);
-
- node = merged_node;
+ pbqp_node_t *node = merged_node;
merged_node = NULL;
if (node_is_reduced(node))
@@ -76,7 +69,7 @@ static void apply_RN_co(pbqp_t *pbqp)
}
#endif
- min_index = get_local_minimal_alternative(pbqp, node);
+ unsigned min_index = get_local_minimal_alternative(pbqp, node);
#if KAPS_DUMP
if (pbqp->dump_file) {
@@ -172,6 +165,9 @@ static void apply_heuristic_reductions_co(pbqp_t *pbqp, plist_t *rpeo)
void solve_pbqp_heuristical_co(pbqp_t *pbqp, plist_t *rpeo)
{
+ assert(pbqp);
+ assert(rpeo);
+
/* Reduce nodes degree ... */
initial_simplify_edges(pbqp);
diff --git a/ir/kaps/heuristical_co_ld.c b/ir/kaps/heuristical_co_ld.c
index f61da27..b0efdd1 100644
--- a/ir/kaps/heuristical_co_ld.c
+++ b/ir/kaps/heuristical_co_ld.c
@@ -4,6 +4,8 @@
*/
#include "config.h"
+#include <stdbool.h>
+
#include "adt/array.h"
#include "assert.h"
#include "error.h"
@@ -27,24 +29,18 @@
static void back_propagate_RI(pbqp_t *pbqp, pbqp_node_t *node)
{
- pbqp_edge_t *edge;
- pbqp_node_t *other;
- pbqp_matrix_t *mat;
- vector_t *vec;
- int is_src;
-
- (void) pbqp;
+ (void)pbqp;
- edge = node->edges[0];
- mat = edge->costs;
- is_src = edge->src == node;
- vec = node->costs;
+ pbqp_edge_t *edge = node->edges[0];
+ pbqp_matrix_t *mat = edge->costs;
+ bool is_src = edge->src == node;
+ vector_t *vec = node->costs;
if (is_src) {
- other = edge->tgt;
+ pbqp_node_t *other = edge->tgt;
node->solution = pbqp_matrix_get_col_min_index(mat, other->solution, vec);
} else {
- other = edge->src;
+ pbqp_node_t *other = edge->src;
node->solution = pbqp_matrix_get_row_min_index(mat, other->solution, vec);
}
@@ -59,18 +55,10 @@ static void back_propagate_RII(pbqp_t *pbqp, pbqp_node_t *node)
{
pbqp_edge_t *src_edge = node->edges[0];
pbqp_edge_t *tgt_edge = node->edges[1];
- int src_is_src = src_edge->src == node;
- int tgt_is_src = tgt_edge->src == node;
- pbqp_matrix_t *src_mat;
- pbqp_matrix_t *tgt_mat;
+ bool src_is_src = src_edge->src == node;
+ bool tgt_is_src = tgt_edge->src == node;
pbqp_node_t *src_node;
pbqp_node_t *tgt_node;
- vector_t *vec;
- vector_t *node_vec;
- unsigned col_index;
- unsigned row_index;
-
- assert(pbqp);
if (src_is_src) {
src_node = src_edge->tgt;
@@ -86,14 +74,11 @@ static void back_propagate_RII(pbqp_t *pbqp, pbqp_node_t *node)
/* Swap nodes if necessary. */
if (tgt_node->index < src_node->index) {
- pbqp_node_t *tmp_node;
- pbqp_edge_t *tmp_edge;
-
- tmp_node = src_node;
+ pbqp_node_t *tmp_node = src_node;
src_node = tgt_node;
tgt_node = tmp_node;
- tmp_edge = src_edge;
+ pbqp_edge_t *tmp_edge = src_edge;
src_edge = tgt_edge;
tgt_edge = tmp_edge;
@@ -101,15 +86,10 @@ static void back_propagate_RII(pbqp_t *pbqp, pbqp_node_t *node)
tgt_is_src = tgt_edge->src == node;
}
- src_mat = src_edge->costs;
- tgt_mat = tgt_edge->costs;
-
- node_vec = node->costs;
-
- row_index = src_node->solution;
- col_index = tgt_node->solution;
-
- vec = vector_copy(pbqp, node_vec);
+ pbqp_matrix_t *src_mat = src_edge->costs;
+ vector_t *node_vec = node->costs;
+ unsigned row_index = src_node->solution;
+ vector_t *vec = vector_copy(pbqp, node_vec);
if (src_is_src) {
vector_add_matrix_col(vec, src_mat, row_index);
@@ -117,6 +97,9 @@ static void back_propagate_RII(pbqp_t *pbqp, pbqp_node_t *node)
vector_add_matrix_row(vec, src_mat, row_index);
}
+ pbqp_matrix_t *tgt_mat = tgt_edge->costs;
+ unsigned col_index = tgt_node->solution;
+
if (tgt_is_src) {
vector_add_matrix_col(vec, tgt_mat, col_index);
} else {
@@ -136,22 +119,15 @@ static void back_propagate_RII(pbqp_t *pbqp, pbqp_node_t *node)
static void back_propagate_RN(pbqp_t *pbqp, pbqp_node_t *node)
{
- vector_t *vec = NULL;
- pbqp_node_t *neighbor = NULL;
- pbqp_edge_t *edge = NULL;
- unsigned edge_index = 0;
-
- assert(pbqp);
-
- vec = vector_copy(pbqp, node->costs);
+ vector_t *vec = vector_copy(pbqp, node->costs);
- for(edge_index = 0; edge_index < pbqp_node_get_degree(node); edge_index++) {
+ for (unsigned edge_index = 0; edge_index < pbqp_node_get_degree(node); edge_index++) {
/* get neighbor node */
- edge = node->edges[edge_index];
- neighbor = edge->src == node ? edge->tgt : edge->src;
+ pbqp_edge_t *edge = node->edges[edge_index];
+ pbqp_node_t *neighbor = edge->src == node ? edge->tgt : edge->src;
/* node is edge src node */
- if(edge->src == node)
+ if (edge->src == node)
vector_add_matrix_col(vec, edge->costs, neighbor->solution);
/* node is edge tgt node */
else
@@ -172,19 +148,16 @@ static void back_propagate_RN(pbqp_t *pbqp, pbqp_node_t *node)
static void back_propagate_ld(pbqp_t *pbqp)
{
- unsigned node_index;
- unsigned node_len = node_bucket_get_length(reduced_bucket);
-
- assert(pbqp);
-
#if KAPS_DUMP
if (pbqp->dump_file) {
pbqp_dump_section(pbqp->dump_file, 2, "Back Propagation");
}
#endif
- for (node_index = node_len; node_index > 0; --node_index) {
- pbqp_node_t *node = reduced_bucket[node_index - 1];
+ unsigned node_len = node_bucket_get_length(reduced_bucket);
+
+ for (unsigned node_index = node_len; node_index-- != 0;) {
+ pbqp_node_t *node = reduced_bucket[node_index];
switch (pbqp_node_get_degree(node)) {
case 1:
@@ -202,18 +175,16 @@ static void back_propagate_ld(pbqp_t *pbqp)
static void merge_into_RN_node(pbqp_t *pbqp, plist_t *rpeo)
{
- pbqp_node_t *node = NULL;
-
- assert(pbqp);
+ pbqp_node_t *node;
do {
/* get last element from reverse perfect elimination order */
- node = (pbqp_node_t*)plist_last(rpeo)->data;
+ node = (pbqp_node_t *)plist_last(rpeo)->data;
/* remove element from reverse perfect elimination order */
plist_erase(rpeo, plist_last(rpeo));
/* insert node at the beginning of rpeo so the rpeo already exits after pbqp solving */
plist_insert_front(rpeo, node);
- } while(node_is_reduced(node));
+ } while (node_is_reduced(node));
assert(pbqp_node_get_degree(node) > 2);
@@ -223,12 +194,9 @@ static void merge_into_RN_node(pbqp_t *pbqp, plist_t *rpeo)
static void apply_RN_co_without_selection(pbqp_t *pbqp)
{
- pbqp_node_t *node;
- unsigned edge_index;
-
- assert(pbqp);
+ (void)pbqp;
- node = merged_node;
+ pbqp_node_t *node = merged_node;
merged_node = NULL;
if (node_is_reduced(node))
@@ -244,7 +212,7 @@ static void apply_RN_co_without_selection(pbqp_t *pbqp)
#endif
/* Disconnect neighbor nodes */
- for(edge_index = 0; edge_index < pbqp_node_get_degree(node); edge_index++) {
+ for (unsigned edge_index = 0; edge_index < pbqp_node_get_degree(node); edge_index++) {
pbqp_edge_t *edge;
pbqp_node_t *neighbor;
@@ -255,7 +223,7 @@ static void apply_RN_co_without_selection(pbqp_t *pbqp)
assert(neighbor != node);
- if(!is_connected(neighbor, edge))
+ if (!is_connected(neighbor, edge))
continue;
disconnect_edge(neighbor, edge);
@@ -345,6 +313,9 @@ static void apply_heuristic_reductions_co(pbqp_t *pbqp, plist_t *rpeo)
void solve_pbqp_heuristical_co_ld(pbqp_t *pbqp, plist_t *rpeo)
{
+ assert(pbqp);
+ assert(rpeo);
+
/* Reduce nodes degree ... */
initial_simplify_edges(pbqp);
diff --git a/ir/kaps/html_dumper.c b/ir/kaps/html_dumper.c
index d66998c..9d23875 100644
--- a/ir/kaps/html_dumper.c
+++ b/ir/kaps/html_dumper.c
@@ -23,26 +23,29 @@
/* Caution: Due to static buffer use only once per statement */
static const char *cost2a(num const cost)
{
+ if (cost == INF_COSTS)
+ return "inf";
+
static char buf[10];
- if (cost == INF_COSTS) return "inf";
#if KAPS_USE_UNSIGNED
sprintf(buf, "%u", cost);
#else
sprintf(buf, "%10lld", cost);
#endif
+
return buf;
}
/* print vector */
static void dump_vector(FILE *f, vector_t *vec)
{
- unsigned index;
unsigned len = vec->len;
+ assert(len > 0);
fprintf(f, "<span class=\"vector\">( ");
- assert(len > 0);
- for (index = 0; index < len; ++index) {
+
+ for (unsigned index = 0; index < len; ++index) {
#if KAPS_ENABLE_VECTOR_NAMES
fprintf(f, "<span title=\"%s\">%s</span> ",
vec->entries[index].name, cost2a(vec->entries[index].data));
@@ -50,25 +53,29 @@ static void dump_vector(FILE *f, vector_t *vec)
fprintf(f, "%s ", cost2a(vec->entries[index].data));
#endif
}
+
fprintf(f, " )</span>\n");
}
static void dump_matrix(FILE *f, pbqp_matrix_t *mat)
{
- unsigned row, col;
- num *p = mat->entries;
-
assert(mat->cols > 0);
assert(mat->rows > 0);
+
+ num *p = mat->entries;
+
fprintf(f, "\t\\begin{pmatrix}\n");
- for (row = 0; row < mat->rows; ++row) {
+
+ for (unsigned row = 0; row < mat->rows; ++row) {
fprintf(f, "\t %s", cost2a(*p++));
- for (col = 1; col < mat->cols; ++col) {
+ for (unsigned col = 1; col < mat->cols; ++col) {
fprintf(f, "& %s", cost2a(*p++));
}
+
fprintf(f, "\\\\\n");
}
+
fprintf(f, "\t\\end{pmatrix}\n");
}
@@ -83,10 +90,9 @@ void pbqp_dump_edge(FILE *file, pbqp_edge_t *edge)
static void dump_edge_costs(pbqp_t *pbqp)
{
- unsigned src_index;
-
fputs("<p>", pbqp->dump_file);
- for (src_index = 0; src_index < pbqp->num_nodes; ++src_index) {
+
+ for (unsigned src_index = 0; src_index < pbqp->num_nodes; ++src_index) {
pbqp_node_t *src_node = get_node(pbqp, src_index);
size_t edge_index;
size_t len;
@@ -103,6 +109,7 @@ static void dump_edge_costs(pbqp_t *pbqp)
}
}
}
+
fputs("</p>", pbqp->dump_file);
}
@@ -117,13 +124,13 @@ void pbqp_dump_node(FILE *file, pbqp_node_t *node)
static void dump_node_costs(pbqp_t *pbqp)
{
- unsigned index;
-
/* dump node costs */
fputs("<p>", pbqp->dump_file);
- for (index = 0; index < pbqp->num_nodes; ++index) {
+
+ for (unsigned index = 0; index < pbqp->num_nodes; ++index) {
pbqp_dump_node(pbqp->dump_file, get_node(pbqp, index));
}
+
fputs("</p>", pbqp->dump_file);
}
@@ -134,20 +141,18 @@ void pbqp_dump_section(FILE *f, int level, const char *txt)
void pbqp_dump_graph(pbqp_t *pbqp)
{
- unsigned src_index;
-
fputs("<p>\n<graph>\n\tgraph input {\n", pbqp->dump_file);
- for (src_index = 0; src_index < pbqp->num_nodes; ++src_index) {
+
+ for (unsigned src_index = 0; src_index < pbqp->num_nodes; ++src_index) {
pbqp_node_t *node = get_node(pbqp, src_index);
+
if (node && !node_is_reduced(node)) {
fprintf(pbqp->dump_file, "\t n%u;\n", src_index);
}
}
- for (src_index = 0; src_index < pbqp->num_nodes; ++src_index) {
+ for (unsigned src_index = 0; src_index < pbqp->num_nodes; ++src_index) {
pbqp_node_t *node = get_node(pbqp, src_index);
- unsigned len;
- unsigned edge_index;
if (!node)
continue;
@@ -155,8 +160,9 @@ void pbqp_dump_graph(pbqp_t *pbqp)
if (node_is_reduced(node))
continue;
- len = ARR_LEN(node->edges);
- for (edge_index = 0; edge_index < len; ++edge_index) {
+ unsigned len = ARR_LEN(node->edges);
+
+ for (unsigned edge_index = 0; edge_index < len; ++edge_index) {
pbqp_node_t *tgt_node = node->edges[edge_index]->tgt;
unsigned tgt_index = tgt_node->index;
@@ -169,6 +175,7 @@ void pbqp_dump_graph(pbqp_t *pbqp)
}
}
}
+
fputs("\t}\n</graph>\n</p>\n", pbqp->dump_file);
}
diff --git a/ir/kaps/kaps.c b/ir/kaps/kaps.c
index 1e7008c..3252799 100644
--- a/ir/kaps/kaps.c
+++ b/ir/kaps/kaps.c
@@ -29,25 +29,21 @@ pbqp_node_t *get_node(pbqp_t *pbqp, unsigned index)
pbqp_edge_t *get_edge(pbqp_t *pbqp, unsigned src_index, unsigned tgt_index)
{
- size_t i;
- size_t len;
- pbqp_node_t *src_node;
- pbqp_node_t *tgt_node;
-
if (tgt_index < src_index) {
unsigned tmp = src_index;
src_index = tgt_index;
tgt_index = tmp;
}
- src_node = get_node(pbqp, src_index);
- tgt_node = get_node(pbqp, tgt_index);
+ pbqp_node_t *src_node = get_node(pbqp, src_index);
+ pbqp_node_t *tgt_node = get_node(pbqp, tgt_index);
assert(tgt_node);
- len = ARR_LEN(src_node->edges);
+ size_t len = ARR_LEN(src_node->edges);
- for (i = 0; i < len; ++i) {
+ for (size_t i = 0; i < len; ++i) {
pbqp_edge_t *cur_edge = src_node->edges[i];
+
if (cur_edge->tgt == tgt_node) {
return cur_edge;
}
@@ -62,20 +58,20 @@ pbqp_t *alloc_pbqp(unsigned number_nodes)
obstack_init(&pbqp->obstack);
- pbqp->solution = 0;
- pbqp->num_nodes = number_nodes;
+ pbqp->solution = 0;
+ pbqp->num_nodes = number_nodes;
#if KAPS_DUMP
- pbqp->dump_file = NULL;
+ pbqp->dump_file = NULL;
#endif
- pbqp->nodes = OALLOCNZ(&pbqp->obstack, pbqp_node_t*, number_nodes);
+ pbqp->nodes = OALLOCNZ(&pbqp->obstack, pbqp_node_t*, number_nodes);
#if KAPS_STATISTIC
- pbqp->num_bf = 0;
- pbqp->num_edges = 0;
- pbqp->num_r0 = 0;
- pbqp->num_r1 = 0;
- pbqp->num_r2 = 0;
- pbqp->num_rm = 0;
- pbqp->num_rn = 0;
+ pbqp->num_bf = 0;
+ pbqp->num_edges = 0;
+ pbqp->num_r0 = 0;
+ pbqp->num_r1 = 0;
+ pbqp->num_r2 = 0;
+ pbqp->num_rm = 0;
+ pbqp->num_rn = 0;
#endif
return pbqp;
diff --git a/ir/kaps/kaps.h b/ir/kaps/kaps.h
index 9af1623..ac6908c 100644
--- a/ir/kaps/kaps.h
+++ b/ir/kaps/kaps.h
@@ -17,7 +17,7 @@
/**
* Create an empty PBQP instance with the given number of nodes.
*/
-pbqp_t* alloc_pbqp(unsigned number_nodes);
+pbqp_t *alloc_pbqp(unsigned number_nodes);
/**
* Free the given PBQP.
diff --git a/ir/kaps/matrix.c b/ir/kaps/matrix.c
index 57bf881..38177d6 100644
--- a/ir/kaps/matrix.c
+++ b/ir/kaps/matrix.c
@@ -20,12 +20,12 @@
pbqp_matrix_t *pbqp_matrix_alloc(pbqp_t *pbqp, unsigned rows, unsigned cols)
{
- unsigned length = rows * cols;
- pbqp_matrix_t *mat = (pbqp_matrix_t*)obstack_alloc(&pbqp->obstack, sizeof(*mat) + sizeof(*mat->entries) * length);
-
assert(cols > 0);
assert(rows > 0);
+ unsigned length = rows * cols;
+ pbqp_matrix_t *mat = (pbqp_matrix_t *)obstack_alloc(&pbqp->obstack, sizeof(*mat) + sizeof(*mat->entries) * length);
+
mat->cols = cols;
mat->rows = rows;
memset(mat->entries, 0, sizeof(*mat->entries) * length);
@@ -36,7 +36,7 @@ pbqp_matrix_t *pbqp_matrix_alloc(pbqp_t *pbqp, unsigned rows, unsigned cols)
pbqp_matrix_t *pbqp_matrix_copy(pbqp_t *pbqp, pbqp_matrix_t *m)
{
unsigned len = m->rows * m->cols;
- pbqp_matrix_t *copy = (pbqp_matrix_t*)obstack_copy(&pbqp->obstack, m, sizeof(*copy) + sizeof(*copy->entries) * len);
+ pbqp_matrix_t *copy = (pbqp_matrix_t *)obstack_copy(&pbqp->obstack, m, sizeof(*copy) + sizeof(*copy->entries) * len);
assert(copy);
return copy;
@@ -44,16 +44,14 @@ pbqp_matrix_t *pbqp_matrix_copy(pbqp_t *pbqp, pbqp_matrix_t *m)
pbqp_matrix_t *pbqp_matrix_copy_and_transpose(pbqp_t *pbqp, pbqp_matrix_t *m)
{
- unsigned i;
- unsigned j;
unsigned cols = m->cols;
unsigned rows = m->rows;
unsigned len = rows * cols;
- pbqp_matrix_t *copy = (pbqp_matrix_t*)obstack_alloc(&pbqp->obstack, sizeof(*copy) + sizeof(*copy->entries) * len);
+ pbqp_matrix_t *copy = (pbqp_matrix_t *)obstack_alloc(&pbqp->obstack, sizeof(*copy) + sizeof(*copy->entries) * len);
- for (i = 0; i < rows; ++i) {
- for (j = 0; j < cols; ++j) {
- copy->entries[j*rows+i] = m->entries[i*cols+j];
+ for (unsigned i = 0; i < rows; ++i) {
+ for (unsigned j = 0; j < cols; ++j) {
+ copy->entries[j * rows + i] = m->entries[i * cols + j];
}
}
@@ -65,12 +63,8 @@ pbqp_matrix_t *pbqp_matrix_copy_and_transpose(pbqp_t *pbqp, pbqp_matrix_t *m)
void pbqp_matrix_transpose(pbqp_t *pbqp, pbqp_matrix_t *mat)
{
- unsigned len;
- pbqp_matrix_t *tmp;
-
- len = mat->rows * mat->cols;
-
- tmp = pbqp_matrix_copy_and_transpose(pbqp, mat);
+ unsigned len = mat->rows * mat->cols;
+ pbqp_matrix_t *tmp = pbqp_matrix_copy_and_transpose(pbqp, mat);
memcpy(mat, tmp, sizeof(*mat) + sizeof(*mat->entries) * len);
@@ -79,43 +73,34 @@ void pbqp_matrix_transpose(pbqp_t *pbqp, pbqp_matrix_t *mat)
void pbqp_matrix_add(pbqp_matrix_t *sum, pbqp_matrix_t *summand)
{
- int i;
- int len;
-
assert(sum->cols == summand->cols);
assert(sum->rows == summand->rows);
- len = sum->rows * sum->cols;
+ int len = sum->rows * sum->cols;
- for (i = 0; i < len; ++i) {
+ for (int i = 0; i < len; ++i) {
sum->entries[i] = pbqp_add(sum->entries[i], summand->entries[i]);
}
}
void pbqp_matrix_set_col_value(pbqp_matrix_t *mat, unsigned col, num value)
{
- unsigned row_index;
- unsigned row_len;
-
assert(col < mat->cols);
- row_len = mat->rows;
+ unsigned row_len = mat->rows;
- for (row_index = 0; row_index < row_len; ++row_index) {
+ for (unsigned row_index = 0; row_index < row_len; ++row_index) {
mat->entries[row_index * mat->cols + col] = value;
}
}
void pbqp_matrix_set_row_value(pbqp_matrix_t *mat, unsigned row, num value)
{
- unsigned col_index;
- unsigned col_len;
-
assert(row < mat->rows);
- col_len = mat->cols;
+ unsigned col_len = mat->cols;
- for (col_index = 0; col_index < col_len; ++col_index) {
+ for (unsigned col_index = 0; col_index < col_len; ++col_index) {
mat->entries[row * mat->cols + col_index] = value;
}
}
@@ -130,21 +115,17 @@ void pbqp_matrix_set(pbqp_matrix_t *mat, unsigned row, unsigned col, num value)
num pbqp_matrix_get_col_min(pbqp_matrix_t *matrix, unsigned col_index, vector_t *flags)
{
- unsigned row_index;
- num min = INF_COSTS;
-
+ num min = INF_COSTS;
unsigned col_len = matrix->cols;
unsigned row_len = matrix->rows;
- assert(matrix->rows == flags->len);
-
- for (row_index = 0; row_index < row_len; ++row_index) {
- num elem;
+ assert(row_len == flags->len);
+ for (unsigned row_index = 0; row_index < row_len; ++row_index) {
/* Ignore virtual deleted columns. */
if (flags->entries[row_index].data == INF_COSTS) continue;
- elem = matrix->entries[row_index * col_len + col_index];
+ num elem = matrix->entries[row_index * col_len + col_index];
if (elem < min) {
min = elem;
@@ -156,25 +137,21 @@ num pbqp_matrix_get_col_min(pbqp_matrix_t *matrix, unsigned col_index, vector_t
unsigned pbqp_matrix_get_col_min_index(pbqp_matrix_t *matrix, unsigned col_index, vector_t *flags)
{
- unsigned row_index;
unsigned min_index = 0;
num min = INF_COSTS;
+ unsigned col_len = matrix->cols;
+ unsigned row_len = matrix->rows;
- unsigned col_len = matrix->cols;
- unsigned row_len = matrix->rows;
-
- assert(matrix->rows == flags->len);
-
- for (row_index = 0; row_index < row_len; ++row_index) {
- num elem;
+ assert(row_len == flags->len);
+ for (unsigned row_index = 0; row_index < row_len; ++row_index) {
/* Ignore virtual deleted columns. */
if (flags->entries[row_index].data == INF_COSTS) continue;
- elem = matrix->entries[row_index * col_len + col_index];
+ num elem = matrix->entries[row_index * col_len + col_index];
if (elem < min) {
- min = elem;
+ min = elem;
min_index = row_index;
}
}
@@ -185,16 +162,12 @@ unsigned pbqp_matrix_get_col_min_index(pbqp_matrix_t *matrix, unsigned col_index
void pbqp_matrix_sub_col_value(pbqp_matrix_t *matrix, unsigned col_index,
vector_t *flags, num value)
{
- unsigned col_len;
- unsigned row_index;
- unsigned row_len;
-
- assert(matrix->rows == flags->len);
+ unsigned col_len = matrix->cols;
+ unsigned row_len = matrix->rows;
- col_len = matrix->cols;
- row_len = matrix->rows;
+ assert(row_len == flags->len);
- for (row_index = 0; row_index < row_len; ++row_index) {
+ for (unsigned row_index = 0; row_index < row_len; ++row_index) {
if (flags->entries[row_index].data == INF_COSTS) {
matrix->entries[row_index * col_len + col_index] = 0;
continue;
@@ -209,20 +182,16 @@ void pbqp_matrix_sub_col_value(pbqp_matrix_t *matrix, unsigned col_index,
num pbqp_matrix_get_row_min(pbqp_matrix_t *matrix, unsigned row_index, vector_t *flags)
{
- unsigned col_index;
- num min = INF_COSTS;
-
+ num min = INF_COSTS;
unsigned len = flags->len;
assert(matrix->cols == len);
- for (col_index = 0; col_index < len; ++col_index) {
- num elem;
-
+ for (unsigned col_index = 0; col_index < len; ++col_index) {
/* Ignore virtual deleted columns. */
if (flags->entries[col_index].data == INF_COSTS) continue;
- elem = matrix->entries[row_index * len + col_index];
+ num elem = matrix->entries[row_index * len + col_index];
if (elem < min) {
min = elem;
@@ -234,21 +203,17 @@ num pbqp_matrix_get_row_min(pbqp_matrix_t *matrix, unsigned row_index, vector_t
unsigned pbqp_matrix_get_row_min_index(pbqp_matrix_t *matrix, unsigned row_index, vector_t *flags)
{
- unsigned col_index;
unsigned min_index = 0;
num min = INF_COSTS;
-
- unsigned len = flags->len;
+ unsigned len = flags->len;
assert(matrix->cols == len);
- for (col_index = 0; col_index < len; ++col_index) {
- num elem;
-
+ for (unsigned col_index = 0; col_index < len; ++col_index) {
/* Ignore virtual deleted columns. */
if (flags->entries[col_index].data == INF_COSTS) continue;
- elem = matrix->entries[row_index * len + col_index];
+ num elem = matrix->entries[row_index * len + col_index];
if (elem < min) {
min = elem;
@@ -262,14 +227,11 @@ unsigned pbqp_matrix_get_row_min_index(pbqp_matrix_t *matrix, unsigned row_index
void pbqp_matrix_sub_row_value(pbqp_matrix_t *matrix, unsigned row_index,
vector_t *flags, num value)
{
- unsigned col_index;
- unsigned col_len;
-
- assert(matrix->cols == flags->len);
+ unsigned col_len = matrix->cols;
- col_len = matrix->cols;
+ assert(col_len == flags->len);
- for (col_index = 0; col_index < col_len; ++col_index) {
+ for (unsigned col_index = 0; col_index < col_len; ++col_index) {
if (flags->entries[col_index].data == INF_COSTS) {
matrix->entries[row_index * col_len + col_index] = 0;
continue;
@@ -284,21 +246,19 @@ void pbqp_matrix_sub_row_value(pbqp_matrix_t *matrix, unsigned row_index,
int pbqp_matrix_is_zero(pbqp_matrix_t *mat, vector_t *src_vec, vector_t *tgt_vec)
{
- unsigned col_index;
- unsigned col_len;
- unsigned row_index;
- unsigned row_len;
+ unsigned col_len = mat->cols;
+ unsigned row_len = mat->rows;
- assert(mat->cols = tgt_vec->len);
- assert(mat->rows = src_vec->len);
+ assert(col_len = tgt_vec->len);
+ assert(row_len = src_vec->len);
- col_len = mat->cols;
- row_len = mat->rows;
+ for (unsigned row_index = 0; row_index < row_len; ++row_index) {
+ if (src_vec->entries[row_index].data == INF_COSTS)
+ continue;
- for (row_index = 0; row_index < row_len; ++row_index) {
- if (src_vec->entries[row_index].data == INF_COSTS) continue;
- for (col_index = 0; col_index < col_len; ++col_index) {
- if (tgt_vec->entries[col_index].data == INF_COSTS) continue;
+ for (unsigned col_index = 0; col_index < col_len; ++col_index) {
+ if (tgt_vec->entries[col_index].data == INF_COSTS)
+ continue;
if (mat->entries[row_index * col_len + col_index] != 0) {
return 0;
@@ -311,19 +271,15 @@ int pbqp_matrix_is_zero(pbqp_matrix_t *mat, vector_t *src_vec, vector_t *tgt_vec
void pbqp_matrix_add_to_all_cols(pbqp_matrix_t *mat, vector_t *vec)
{
- unsigned col_index;
- unsigned col_len;
- unsigned row_index;
- unsigned row_len;
+ unsigned col_len = mat->cols;
+ unsigned row_len = mat->rows;
- assert(mat->rows == vec->len);
+ assert(row_len == vec->len);
- col_len = mat->cols;
- row_len = mat->rows;
-
- for (row_index = 0; row_index < row_len; ++row_index) {
+ for (unsigned row_index = 0; row_index < row_len; ++row_index) {
num value = vec->entries[row_index].data;
- for (col_index = 0; col_index < col_len; ++col_index) {
+
+ for (unsigned col_index = 0; col_index < col_len; ++col_index) {
mat->entries[row_index * col_len + col_index] = pbqp_add(
mat->entries[row_index * col_len + col_index], value);
}
@@ -332,18 +288,13 @@ void pbqp_matrix_add_to_all_cols(pbqp_matrix_t *mat, vector_t *vec)
void pbqp_matrix_add_to_all_rows(pbqp_matrix_t *mat, vector_t *vec)
{
- unsigned col_index;
- unsigned col_len;
- unsigned row_index;
- unsigned row_len;
-
- assert(mat->cols == vec->len);
+ unsigned col_len = mat->cols;
+ unsigned row_len = mat->rows;
- col_len = mat->cols;
- row_len = mat->rows;
+ assert(col_len == vec->len);
- for (row_index = 0; row_index < row_len; ++row_index) {
- for (col_index = 0; col_index < col_len; ++col_index) {
+ for (unsigned row_index = 0; row_index < row_len; ++row_index) {
+ for (unsigned col_index = 0; col_index < col_len; ++col_index) {
num value = vec->entries[col_index].data;
mat->entries[row_index * col_len + col_index] = pbqp_add(mat->entries[row_index * col_len + col_index], value);
diff --git a/ir/kaps/optimal.c b/ir/kaps/optimal.c
index e52bb33..32c0c6a 100644
--- a/ir/kaps/optimal.c
+++ b/ir/kaps/optimal.c
@@ -11,6 +11,8 @@
*/
#include "config.h"
+#include <stdbool.h>
+
#include "adt/array.h"
#include "assert.h"
#include "error.h"
@@ -60,22 +62,18 @@ static void insert_into_rm_bucket(pbqp_edge_t *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) {
+ for (int i = 0; i < 4; ++i) {
node_bucket_init(&node_buckets[i]);
}
}
void free_buckets(void)
{
- int i;
-
- for (i = 0; i < 4; ++i) {
+ for (int i = 0; i < 4; ++i) {
node_bucket_free(&node_buckets[i]);
}
@@ -88,17 +86,14 @@ void free_buckets(void)
void fill_node_buckets(pbqp_t *pbqp)
{
- unsigned node_index;
- unsigned node_len;
-
- node_len = pbqp->num_nodes;
+ unsigned node_len = pbqp->num_nodes;
#if KAPS_TIMING
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) {
+ for (unsigned node_index = 0; node_index < node_len; ++node_index) {
unsigned degree;
pbqp_node_t *node = get_node(pbqp, node_index);
@@ -124,31 +119,19 @@ void fill_node_buckets(pbqp_t *pbqp)
static void normalize_towards_source(pbqp_edge_t *edge)
{
- pbqp_matrix_t *mat;
- pbqp_node_t *src_node;
- pbqp_node_t *tgt_node;
- vector_t *src_vec;
- vector_t *tgt_vec;
- unsigned src_len;
- unsigned tgt_len;
- unsigned src_index;
- unsigned new_infinity = 0;
-
- src_node = edge->src;
- tgt_node = edge->tgt;
-
- src_vec = src_node->costs;
- tgt_vec = tgt_node->costs;
-
- src_len = src_vec->len;
- tgt_len = tgt_vec->len;
- assert(src_len > 0);
- assert(tgt_len > 0);
+ pbqp_matrix_t *mat = edge->costs;
+ pbqp_node_t *src_node = edge->src;
+ pbqp_node_t *tgt_node = edge->tgt;
+ vector_t *src_vec = src_node->costs;
+ vector_t *tgt_vec = tgt_node->costs;
+ unsigned src_len = src_vec->len;
+ unsigned new_infinity = 0;
- mat = edge->costs;
+ assert(src_len > 0);
+ assert(tgt_vec->len > 0);
/* Normalize towards source node. */
- for (src_index = 0; src_index < src_len; ++src_index) {
+ for (unsigned src_index = 0; src_index < src_len; ++src_index) {
num min = pbqp_matrix_get_row_min(mat, src_index, tgt_vec);
if (min != 0) {
@@ -168,10 +151,9 @@ static void normalize_towards_source(pbqp_edge_t *edge)
}
if (new_infinity) {
- unsigned edge_index;
unsigned edge_len = pbqp_node_get_degree(src_node);
- for (edge_index = 0; edge_index < edge_len; ++edge_index) {
+ for (unsigned edge_index = 0; edge_index < edge_len; ++edge_index) {
pbqp_edge_t *edge_candidate = src_node->edges[edge_index];
if (edge_candidate != edge) {
@@ -183,31 +165,20 @@ static void normalize_towards_source(pbqp_edge_t *edge)
static void normalize_towards_target(pbqp_edge_t *edge)
{
- pbqp_matrix_t *mat;
- pbqp_node_t *src_node;
- pbqp_node_t *tgt_node;
- vector_t *src_vec;
- vector_t *tgt_vec;
- unsigned src_len;
- unsigned tgt_len;
- unsigned tgt_index;
- unsigned new_infinity = 0;
-
- src_node = edge->src;
- tgt_node = edge->tgt;
-
- src_vec = src_node->costs;
- tgt_vec = tgt_node->costs;
-
- src_len = src_vec->len;
- tgt_len = tgt_vec->len;
- assert(src_len > 0);
+ pbqp_matrix_t *mat = edge->costs;
+ pbqp_node_t *src_node = edge->src;
+ pbqp_node_t *tgt_node = edge->tgt;
+ vector_t *src_vec = src_node->costs;
+ vector_t *tgt_vec = tgt_node->costs;
+ unsigned tgt_len = tgt_vec->len;
+ unsigned new_infinity = 0;
+
+ assert(src_vec->len > 0);
assert(tgt_len > 0);
- mat = edge->costs;
/* Normalize towards target node. */
- for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
+ for (unsigned tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
num min = pbqp_matrix_get_col_min(mat, tgt_index, src_vec);
if (min != 0) {
@@ -227,10 +198,9 @@ static void normalize_towards_target(pbqp_edge_t *edge)
}
if (new_infinity) {
- unsigned edge_index;
unsigned edge_len = pbqp_node_get_degree(tgt_node);
- for (edge_index = 0; edge_index < edge_len; ++edge_index) {
+ for (unsigned edge_index = 0; edge_index < edge_len; ++edge_index) {
pbqp_edge_t *edge_candidate = tgt_node->edges[edge_index];
if (edge_candidate != edge) {
@@ -248,44 +218,28 @@ static void normalize_towards_target(pbqp_edge_t *edge)
*/
static void merge_source_into_target(pbqp_t *pbqp, pbqp_edge_t *edge)
{
- pbqp_matrix_t *mat;
- pbqp_node_t *src_node;
- pbqp_node_t *tgt_node;
- vector_t *src_vec;
- vector_t *tgt_vec;
- unsigned *mapping;
- unsigned src_len;
- unsigned tgt_len;
- unsigned tgt_index;
- unsigned edge_index;
- unsigned edge_len;
-
- src_node = edge->src;
- tgt_node = edge->tgt;
-
- src_vec = src_node->costs;
- tgt_vec = tgt_node->costs;
-
- src_len = src_vec->len;
- tgt_len = tgt_vec->len;
+ pbqp_matrix_t *mat = edge->costs;
+ pbqp_node_t *src_node = edge->src;
+ pbqp_node_t *tgt_node = edge->tgt;
+ vector_t *src_vec = src_node->costs;
+ vector_t *tgt_vec = tgt_node->costs;
+ unsigned src_len = src_vec->len;
+ unsigned tgt_len = tgt_vec->len;
/* Matrizes are normalized. */
assert(src_len > 1);
assert(tgt_len > 1);
- mat = edge->costs;
-
- mapping = NEW_ARR_F(unsigned, tgt_len);
+ unsigned *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;
- unsigned src_index;
-
+ for (unsigned tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
if (tgt_vec->entries[tgt_index].data == INF_COSTS)
continue;
- for (src_index = 0; src_index < src_len; ++src_index) {
+ unsigned onlyOneZero = 0;
+
+ for (unsigned src_index = 0; src_index < src_len; ++src_index) {
if (src_vec->entries[src_index].data == INF_COSTS)
continue;
@@ -298,13 +252,13 @@ static void merge_source_into_target(pbqp_t *pbqp, pbqp_edge_t *edge)
return;
}
- onlyOneZero = 1;
+ onlyOneZero = 1;
mapping[tgt_index] = src_index;
}
}
/* We know that we can merge the source node into the target node. */
- edge_len = pbqp_node_get_degree(src_node);
+ unsigned edge_len = pbqp_node_get_degree(src_node);
#if KAPS_STATISTIC
pbqp->num_rm++;
@@ -319,21 +273,16 @@ static void merge_source_into_target(pbqp_t *pbqp, pbqp_edge_t *edge)
#endif
/* Reconnect the source's edges with the target node. */
- for (edge_index = 0; edge_index < edge_len; ++edge_index) {
- pbqp_edge_t *old_edge = src_node->edges[edge_index];
- pbqp_edge_t *new_edge;
- pbqp_matrix_t *old_matrix;
- pbqp_matrix_t *new_matrix;
- pbqp_node_t *other_node;
- vector_t *other_vec;
- unsigned other_len;
- unsigned other_index;
-
+ for (unsigned edge_index = 0; edge_index < edge_len; ++edge_index) {
+ pbqp_edge_t *old_edge = src_node->edges[edge_index];
assert(old_edge);
+
if (old_edge == edge)
continue;
- old_matrix = old_edge->costs;
+ pbqp_matrix_t *old_matrix = old_edge->costs;
+ pbqp_node_t *other_node;
+ unsigned other_len;
if (old_edge->tgt == src_node) {
other_node = old_edge->src;
@@ -341,46 +290,46 @@ static void merge_source_into_target(pbqp_t *pbqp, pbqp_edge_t *edge)
}
else {
other_node = old_edge->tgt;
- other_len = old_matrix->cols;
+ other_len = old_matrix->cols;
}
- other_vec = other_node->costs;
- new_matrix = pbqp_matrix_alloc(pbqp, tgt_len, other_len);
+ vector_t *other_vec = other_node->costs;
+ pbqp_matrix_t *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 src_index = mapping[tgt_index];
-
+ for (unsigned tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
if (tgt_vec->entries[tgt_index].data == INF_COSTS)
continue;
- for (other_index = 0; other_index < other_len; ++other_index) {
+ unsigned src_index = mapping[tgt_index];
+
+ for (unsigned other_index = 0; other_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[other_index*src_len+src_index];
+ 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 src_index = mapping[tgt_index];
-
+ for (unsigned tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
if (tgt_vec->entries[tgt_index].data == INF_COSTS)
continue;
- for (other_index = 0; other_index < other_len; ++other_index) {
+ unsigned src_index = mapping[tgt_index];
+
+ for (unsigned other_index = 0; other_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];
+ new_matrix->entries[tgt_index * other_len + other_index] = old_matrix->entries[src_index * other_len + other_index];
}
}
}
- new_edge = get_edge(pbqp, tgt_node->index, other_node->index);
+ pbqp_edge_t *new_edge = get_edge(pbqp, tgt_node->index, other_node->index);
add_edge_costs(pbqp, tgt_node->index, other_node->index, new_matrix);
@@ -410,44 +359,28 @@ static void merge_source_into_target(pbqp_t *pbqp, pbqp_edge_t *edge)
*/
static void merge_target_into_source(pbqp_t *pbqp, pbqp_edge_t *edge)
{
- pbqp_matrix_t *mat;
- pbqp_node_t *src_node;
- pbqp_node_t *tgt_node;
- vector_t *src_vec;
- vector_t *tgt_vec;
- unsigned *mapping;
- unsigned src_len;
- unsigned tgt_len;
- unsigned src_index;
- unsigned edge_index;
- unsigned edge_len;
-
- src_node = edge->src;
- tgt_node = edge->tgt;
-
- src_vec = src_node->costs;
- tgt_vec = tgt_node->costs;
-
- src_len = src_vec->len;
- tgt_len = tgt_vec->len;
+ pbqp_node_t *src_node = edge->src;
+ pbqp_node_t *tgt_node = edge->tgt;
+ vector_t *src_vec = src_node->costs;
+ vector_t *tgt_vec = tgt_node->costs;
+ unsigned src_len = src_vec->len;
+ unsigned tgt_len = tgt_vec->len;
/* Matrizes are normalized. */
assert(src_len > 1);
assert(tgt_len > 1);
- mat = edge->costs;
-
- mapping = NEW_ARR_F(unsigned, src_len);
+ pbqp_matrix_t *mat = edge->costs;
+ unsigned *mapping = NEW_ARR_F(unsigned, src_len);
/* Check that each row has at most one zero entry. */
- for (src_index = 0; src_index < src_len; ++src_index) {
- unsigned onlyOneZero = 0;
- unsigned tgt_index;
-
+ for (unsigned src_index = 0; src_index < src_len; ++src_index) {
if (src_vec->entries[src_index].data == INF_COSTS)
continue;
- for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
+ unsigned onlyOneZero = 0;
+
+ for (unsigned tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
if (tgt_vec->entries[tgt_index].data == INF_COSTS)
continue;
@@ -460,13 +393,13 @@ static void merge_target_into_source(pbqp_t *pbqp, pbqp_edge_t *edge)
return;
}
- onlyOneZero = 1;
+ onlyOneZero = 1;
mapping[src_index] = tgt_index;
}
}
/* We know that we can merge the target node into the source node. */
- edge_len = pbqp_node_get_degree(tgt_node);
+ unsigned edge_len = pbqp_node_get_degree(tgt_node);
#if KAPS_STATISTIC
pbqp->num_rm++;
@@ -481,22 +414,16 @@ static void merge_target_into_source(pbqp_t *pbqp, pbqp_edge_t *edge)
#endif
/* Reconnect the target's edges with the source node. */
- for (edge_index = 0; edge_index < edge_len; ++edge_index) {
- pbqp_edge_t *old_edge = tgt_node->edges[edge_index];
- pbqp_edge_t *new_edge;
- pbqp_matrix_t *old_matrix;
- pbqp_matrix_t *new_matrix;
- pbqp_node_t *other_node;
- vector_t *other_vec;
- unsigned other_len;
- unsigned other_index;
-
+ for (unsigned edge_index = 0; edge_index < edge_len; ++edge_index) {
+ pbqp_edge_t *old_edge = tgt_node->edges[edge_index];
assert(old_edge);
if (old_edge == edge)
continue;
- old_matrix = old_edge->costs;
+ pbqp_matrix_t *old_matrix = old_edge->costs;
+ pbqp_node_t *other_node;
+ unsigned other_len;
if (old_edge->tgt == tgt_node) {
other_node = old_edge->src;
@@ -504,46 +431,46 @@ static void merge_target_into_source(pbqp_t *pbqp, pbqp_edge_t *edge)
}
else {
other_node = old_edge->tgt;
- other_len = old_matrix->cols;
+ other_len = old_matrix->cols;
}
- other_vec = other_node->costs;
- new_matrix = pbqp_matrix_alloc(pbqp, src_len, other_len);
+ vector_t *other_vec = other_node->costs;
+ pbqp_matrix_t *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];
-
+ for (unsigned src_index = 0; src_index < src_len; ++src_index) {
if (src_vec->entries[src_index].data == INF_COSTS)
continue;
- for (other_index = 0; other_index < other_len; ++other_index) {
+ unsigned tgt_index = mapping[src_index];
+
+ for (unsigned 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];
+ new_matrix->entries[src_index * other_len + other_index] = old_matrix->entries[other_index * tgt_len + tgt_index];
}
}
}
/* 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];
-
+ for (unsigned src_index = 0; src_index < src_len; ++src_index) {
if (src_vec->entries[src_index].data == INF_COSTS)
continue;
- for (other_index = 0; other_index < other_len; ++other_index) {
+ unsigned tgt_index = mapping[src_index];
+
+ for (unsigned 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];
+ new_matrix->entries[src_index * other_len + other_index] = old_matrix->entries[tgt_index * other_len + other_index];
}
}
}
- new_edge = get_edge(pbqp, src_node->index, other_node->index);
+ pbqp_edge_t *new_edge = get_edge(pbqp, src_node->index, other_node->index);
add_edge_costs(pbqp, src_node->index, other_node->index, new_matrix);
@@ -570,22 +497,18 @@ static void merge_target_into_source(pbqp_t *pbqp, pbqp_edge_t *edge)
*/
void apply_RM(pbqp_t *pbqp, pbqp_node_t *node)
{
- pbqp_edge_t **edges;
- unsigned edge_index;
- unsigned edge_len;
-
- edges = node->edges;
- edge_len = pbqp_node_get_degree(node);
+ pbqp_edge_t **edges = node->edges;
+ unsigned edge_len = pbqp_node_get_degree(node);
/* Check all incident edges. */
- for (edge_index = 0; edge_index < edge_len; ++edge_index) {
+ for (unsigned edge_index = 0; edge_index < edge_len; ++edge_index) {
pbqp_edge_t *edge = edges[edge_index];
insert_into_rm_bucket(edge);
}
/* ALAP: Merge neighbors into given node. */
- while(edge_bucket_get_length(rm_bucket) > 0) {
+ while (edge_bucket_get_length(rm_bucket) > 0) {
pbqp_edge_t *edge = edge_bucket_pop(&rm_bucket);
/* If the edge is not deleted: Try a merge. */
@@ -604,10 +527,12 @@ void reorder_node_after_edge_deletion(pbqp_node_t *node)
/* Assume node lost one incident edge. */
unsigned old_degree = degree + 1;
- if (!buckets_filled) return;
+ if (!buckets_filled)
+ return;
/* Same bucket as before */
- if (degree > 2) return;
+ if (degree > 2)
+ return;
/* Delete node from old bucket... */
node_bucket_remove(&node_buckets[old_degree], node);
@@ -622,10 +547,12 @@ void reorder_node_after_edge_insertion(pbqp_node_t *node)
/* Assume node lost one incident edge. */
unsigned old_degree = degree - 1;
- if (!buckets_filled) return;
+ if (!buckets_filled)
+ return;
/* Same bucket as before */
- if (old_degree > 2) return;
+ if (old_degree > 2)
+ return;
/* Delete node from old bucket... */
node_bucket_remove(&node_buckets[old_degree], node);
@@ -636,22 +563,15 @@ void reorder_node_after_edge_insertion(pbqp_node_t *node)
void simplify_edge(pbqp_t *pbqp, pbqp_edge_t *edge)
{
+ (void)pbqp;
+
/* If edge are already deleted, we have nothing to do. */
if (is_deleted(edge))
return;
- pbqp_matrix_t *mat;
- pbqp_node_t *src_node;
- pbqp_node_t *tgt_node;
- vector_t *src_vec;
- vector_t *tgt_vec;
- int src_len;
- int tgt_len;
+ pbqp_node_t *src_node = edge->src;
+ pbqp_node_t *tgt_node = edge->tgt;
- (void) pbqp;
-
- src_node = edge->src;
- tgt_node = edge->tgt;
assert(src_node);
assert(tgt_node);
@@ -663,15 +583,10 @@ void simplify_edge(pbqp_t *pbqp, pbqp_edge_t *edge)
}
#endif
- src_vec = src_node->costs;
- tgt_vec = tgt_node->costs;
-
- src_len = src_vec->len;
- tgt_len = tgt_vec->len;
- assert(src_len > 0);
- assert(tgt_len > 0);
-
- mat = edge->costs;
+ vector_t *src_vec = src_node->costs;
+ vector_t *tgt_vec = tgt_node->costs;
+ assert(src_vec->len > 0);
+ assert(tgt_vec->len > 0);
#if KAPS_DUMP
if (pbqp->dump_file) {
@@ -690,6 +605,8 @@ void simplify_edge(pbqp_t *pbqp, pbqp_edge_t *edge)
}
#endif
+ pbqp_matrix_t *mat = edge->costs;
+
if (pbqp_matrix_is_zero(mat, src_vec, tgt_vec)) {
#if KAPS_DUMP
if (pbqp->dump_file) {
@@ -707,9 +624,6 @@ void simplify_edge(pbqp_t *pbqp, pbqp_edge_t *edge)
void initial_simplify_edges(pbqp_t *pbqp)
{
- unsigned node_index;
- unsigned node_len;
-
#if KAPS_TIMING
ir_timer_t *t_int_simpl = ir_timer_new();
ir_timer_start(t_int_simpl);
@@ -722,27 +636,26 @@ void initial_simplify_edges(pbqp_t *pbqp)
}
#endif
- node_len = pbqp->num_nodes;
+ unsigned node_len = pbqp->num_nodes;
init_buckets();
/* First simplify all edges. */
- for (node_index = 0; node_index < node_len; ++node_index) {
- unsigned edge_index;
- pbqp_node_t *node = get_node(pbqp, node_index);
- pbqp_edge_t **edges;
- unsigned edge_len;
+ for (unsigned node_index = 0; node_index < node_len; ++node_index) {
+ pbqp_node_t *node = get_node(pbqp, node_index);
- if (!node) continue;
+ if (!node)
+ continue;
- edges = node->edges;
- edge_len = pbqp_node_get_degree(node);
+ pbqp_edge_t **edges = node->edges;
+ unsigned edge_len = pbqp_node_get_degree(node);
- for (edge_index = 0; edge_index < edge_len; ++edge_index) {
+ for (unsigned edge_index = 0; edge_index < edge_len; ++edge_index) {
pbqp_edge_t *edge = edges[edge_index];
/* Simplify only once per edge. */
- if (node != edge->src) continue;
+ if (node != edge->src)
+ continue;
simplify_edge(pbqp, edge);
}
@@ -756,23 +669,15 @@ void initial_simplify_edges(pbqp_t *pbqp)
num determine_solution(pbqp_t *pbqp)
{
- unsigned node_index;
- unsigned node_len;
- num solution = 0;
+ (void)pbqp;
- #if KAPS_TIMING
- ir_timer_t *t_det_solution = ir_timer_new();
- ir_timer_reset_and_start(t_det_solution);
- #endif
-
-#if KAPS_DUMP
- FILE *file;
+#if KAPS_TIMING
+ ir_timer_t *t_det_solution = ir_timer_new();
+ ir_timer_reset_and_start(t_det_solution);
#endif
- (void) pbqp;
-
#if KAPS_DUMP
- file = pbqp->dump_file;
+ FILE *file = pbqp->dump_file;
if (file) {
pbqp_dump_section(file, 1, "4. Determine Solution/Minimum");
@@ -781,18 +686,19 @@ num determine_solution(pbqp_t *pbqp)
#endif
/* Solve trivial nodes and calculate solution. */
- node_len = node_bucket_get_length(node_buckets[0]);
+ unsigned node_len = node_bucket_get_length(node_buckets[0]);
#if KAPS_STATISTIC
pbqp->num_r0 = node_len;
#endif
- for (node_index = 0; node_index < node_len; ++node_index) {
+ num solution = 0;
+
+ for (unsigned node_index = 0; node_index < node_len; ++node_index) {
pbqp_node_t *node = node_buckets[0][node_index];
node->solution = vector_get_min_index(node->costs);
- solution = pbqp_add(solution,
- node->costs->entries[node->solution].data);
+ solution = pbqp_add(solution, node->costs->entries[node->solution].data);
#if KAPS_DUMP
if (file) {
@@ -813,33 +719,28 @@ num determine_solution(pbqp_t *pbqp)
}
#endif
- #if KAPS_TIMING
- ir_timer_stop(t_det_solution);
- printf("PBQP Determine Solution: %10.3lf msec\n", (double)ir_timer_elapsed_usec(t_det_solution) / 1000.0);
- #endif
+#if KAPS_TIMING
+ ir_timer_stop(t_det_solution);
+ printf("PBQP Determine Solution: %10.3lf msec\n", (double)ir_timer_elapsed_usec(t_det_solution) / 1000.0);
+#endif
return solution;
}
static void back_propagate_RI(pbqp_t *pbqp, pbqp_node_t *node)
{
- pbqp_edge_t *edge;
- pbqp_node_t *other;
- pbqp_matrix_t *mat;
- vector_t *vec;
- int is_src;
- (void) pbqp;
-
- edge = node->edges[0];
- mat = edge->costs;
- is_src = edge->src == node;
- vec = node->costs;
+ (void)pbqp;
+
+ pbqp_edge_t *edge = node->edges[0];
+ pbqp_matrix_t *mat = edge->costs;
+ bool is_src = edge->src == node;
+ vector_t *vec = node->costs;
if (is_src) {
- other = edge->tgt;
+ pbqp_node_t *other = edge->tgt;
node->solution = pbqp_matrix_get_col_min_index(mat, other->solution, vec);
} else {
- other = edge->src;
+ pbqp_node_t *other = edge->src;
node->solution = pbqp_matrix_get_row_min_index(mat, other->solution, vec);
}
@@ -852,18 +753,9 @@ static void back_propagate_RI(pbqp_t *pbqp, pbqp_node_t *node)
static void back_propagate_RII(pbqp_t *pbqp, pbqp_node_t *node)
{
- pbqp_edge_t *src_edge = node->edges[0];
- pbqp_edge_t *tgt_edge = node->edges[1];
- int src_is_src = src_edge->src == node;
- int tgt_is_src = tgt_edge->src == node;
- pbqp_matrix_t *src_mat;
- pbqp_matrix_t *tgt_mat;
- pbqp_node_t *src_node;
- pbqp_node_t *tgt_node;
- vector_t *vec;
- vector_t *node_vec;
- unsigned col_index;
- unsigned row_index;
+ pbqp_edge_t *src_edge = node->edges[0];
+ bool src_is_src = src_edge->src == node;
+ pbqp_node_t *src_node;
if (src_is_src) {
src_node = src_edge->tgt;
@@ -871,6 +763,10 @@ static void back_propagate_RII(pbqp_t *pbqp, pbqp_node_t *node)
src_node = src_edge->src;
}
+ pbqp_edge_t *tgt_edge = node->edges[1];
+ bool tgt_is_src = tgt_edge->src == node;
+ pbqp_node_t *tgt_node;
+
if (tgt_is_src) {
tgt_node = tgt_edge->tgt;
} else {
@@ -879,14 +775,11 @@ static void back_propagate_RII(pbqp_t *pbqp, pbqp_node_t *node)
/* Swap nodes if necessary. */
if (tgt_node->index < src_node->index) {
- pbqp_node_t *tmp_node;
- pbqp_edge_t *tmp_edge;
-
- tmp_node = src_node;
+ pbqp_node_t *tmp_node = src_node;
src_node = tgt_node;
tgt_node = tmp_node;
- tmp_edge = src_edge;
+ pbqp_edge_t *tmp_edge = src_edge;
src_edge = tgt_edge;
tgt_edge = tmp_edge;
@@ -894,15 +787,13 @@ static void back_propagate_RII(pbqp_t *pbqp, pbqp_node_t *node)
tgt_is_src = tgt_edge->src == node;
}
- src_mat = src_edge->costs;
- tgt_mat = tgt_edge->costs;
-
- node_vec = node->costs;
-
- row_index = src_node->solution;
- col_index = tgt_node->solution;
- vec = vector_copy(pbqp, node_vec);
+ pbqp_matrix_t *src_mat = src_edge->costs;
+ pbqp_matrix_t *tgt_mat = tgt_edge->costs;
+ vector_t *node_vec = node->costs;
+ unsigned row_index = src_node->solution;
+ unsigned col_index = tgt_node->solution;
+ vector_t *vec = vector_copy(pbqp, node_vec);
if (src_is_src) {
vector_add_matrix_col(vec, src_mat, row_index);
@@ -929,16 +820,15 @@ static void back_propagate_RII(pbqp_t *pbqp, pbqp_node_t *node)
void back_propagate(pbqp_t *pbqp)
{
- unsigned node_index;
- unsigned node_len = node_bucket_get_length(reduced_bucket);
-
#if KAPS_DUMP
if (pbqp->dump_file) {
pbqp_dump_section(pbqp->dump_file, 2, "Back Propagation");
}
#endif
- for (node_index = node_len; node_index > 0; --node_index) {
+ unsigned node_len = node_bucket_get_length(reduced_bucket);
+
+ for (unsigned node_index = node_len; node_index > 0; --node_index) {
pbqp_node_t *node = reduced_bucket[node_index - 1];
switch (pbqp_node_get_degree(node)) {
@@ -963,13 +853,13 @@ void apply_edge(pbqp_t *pbqp)
void apply_RI(pbqp_t *pbqp)
{
- pbqp_node_t *node = node_bucket_pop(&node_buckets[1]);
- pbqp_edge_t *edge = node->edges[0];
- pbqp_matrix_t *mat = edge->costs;
- int is_src = edge->src == node;
- pbqp_node_t *other_node;
+ (void)pbqp;
+
+ pbqp_node_t *node = node_bucket_pop(&node_buckets[1]);
+ pbqp_edge_t *edge = node->edges[0];
+ bool is_src = edge->src == node;
+ pbqp_node_t *other_node;
- (void) pbqp;
assert(pbqp_node_get_degree(node) == 1);
if (is_src) {
@@ -991,6 +881,8 @@ void apply_RI(pbqp_t *pbqp)
}
#endif
+ pbqp_matrix_t *mat = edge->costs;
+
if (is_src) {
pbqp_matrix_add_to_all_cols(mat, node->costs);
normalize_towards_target(edge);
@@ -998,6 +890,7 @@ void apply_RI(pbqp_t *pbqp)
pbqp_matrix_add_to_all_rows(mat, node->costs);
normalize_towards_source(edge);
}
+
disconnect_edge(other_node, edge);
#if KAPS_DUMP
@@ -1019,25 +912,10 @@ void apply_RI(pbqp_t *pbqp)
void apply_RII(pbqp_t *pbqp)
{
- pbqp_node_t *node = node_bucket_pop(&node_buckets[2]);
- pbqp_edge_t *src_edge = node->edges[0];
- pbqp_edge_t *tgt_edge = node->edges[1];
- int src_is_src = src_edge->src == node;
- int tgt_is_src = tgt_edge->src == node;
- pbqp_matrix_t *src_mat;
- pbqp_matrix_t *tgt_mat;
- pbqp_node_t *src_node;
- pbqp_node_t *tgt_node;
- pbqp_edge_t *edge;
- pbqp_matrix_t *mat;
- vector_t *vec;
- vector_t *node_vec;
- vector_t *src_vec;
- vector_t *tgt_vec;
- unsigned col_index;
- unsigned col_len;
- unsigned row_index;
- unsigned row_len;
+ pbqp_node_t *node = node_bucket_pop(&node_buckets[2]);
+ pbqp_edge_t *src_edge = node->edges[0];
+ bool src_is_src = src_edge->src == node;
+ pbqp_node_t *src_node;
assert(pbqp_node_get_degree(node) == 2);
@@ -1047,6 +925,10 @@ void apply_RII(pbqp_t *pbqp)
src_node = src_edge->src;
}
+ pbqp_edge_t *tgt_edge = node->edges[1];
+ bool tgt_is_src = tgt_edge->src == node;
+ pbqp_node_t *tgt_node;
+
if (tgt_is_src) {
tgt_node = tgt_edge->tgt;
} else {
@@ -1055,14 +937,11 @@ void apply_RII(pbqp_t *pbqp)
/* Swap nodes if necessary. */
if (tgt_node->index < src_node->index) {
- pbqp_node_t *tmp_node;
- pbqp_edge_t *tmp_edge;
-
- tmp_node = src_node;
+ pbqp_node_t *tmp_node = src_node;
src_node = tgt_node;
tgt_node = tmp_node;
- tmp_edge = src_edge;
+ pbqp_edge_t *tmp_edge = src_edge;
src_edge = tgt_edge;
tgt_edge = tmp_edge;
@@ -1085,21 +964,19 @@ void apply_RII(pbqp_t *pbqp)
}
#endif
- src_mat = src_edge->costs;
- tgt_mat = tgt_edge->costs;
- src_vec = src_node->costs;
- tgt_vec = tgt_node->costs;
- node_vec = node->costs;
+ pbqp_matrix_t *src_mat = src_edge->costs;
+ pbqp_matrix_t *tgt_mat = tgt_edge->costs;
+ vector_t *src_vec = src_node->costs;
+ vector_t *tgt_vec = tgt_node->costs;
+ vector_t *node_vec = node->costs;
+ unsigned col_len = tgt_vec->len;
+ unsigned row_len = src_vec->len;
+ pbqp_matrix_t *mat = pbqp_matrix_alloc(pbqp, row_len, col_len);
- row_len = src_vec->len;
- col_len = tgt_vec->len;
-
- mat = pbqp_matrix_alloc(pbqp, row_len, col_len);
-
- for (row_index = 0; row_index < row_len; ++row_index) {
- for (col_index = 0; col_index < col_len; ++col_index) {
- vec = vector_copy(pbqp, node_vec);
+ for (unsigned row_index = 0; row_index < row_len; ++row_index) {
+ for (unsigned col_index = 0; col_index < col_len; ++col_index) {
+ vector_t *vec = vector_copy(pbqp, node_vec);
if (src_is_src) {
vector_add_matrix_col(vec, src_mat, row_index);
@@ -1119,7 +996,7 @@ void apply_RII(pbqp_t *pbqp)
}
}
- edge = get_edge(pbqp, src_node->index, tgt_node->index);
+ pbqp_edge_t *edge = get_edge(pbqp, src_node->index, tgt_node->index);
/* Disconnect node. */
disconnect_edge(src_node, src_edge);
@@ -1158,46 +1035,34 @@ void apply_RII(pbqp_t *pbqp)
static void select_column(pbqp_edge_t *edge, unsigned col_index)
{
- pbqp_matrix_t *mat;
- pbqp_node_t *src_node;
- pbqp_node_t *tgt_node;
- vector_t *src_vec;
- vector_t *tgt_vec;
- unsigned src_len;
- unsigned tgt_len;
- unsigned src_index;
- unsigned new_infinity = 0;
-
- src_node = edge->src;
- tgt_node = edge->tgt;
-
- src_vec = src_node->costs;
- tgt_vec = tgt_node->costs;
-
- src_len = src_vec->len;
- tgt_len = tgt_vec->len;
+ pbqp_node_t *src_node = edge->src;
+ pbqp_node_t *tgt_node = edge->tgt;
+ vector_t *src_vec = src_node->costs;
+ vector_t *tgt_vec = tgt_node->costs;
+ unsigned src_len = src_vec->len;
+ unsigned tgt_len = tgt_vec->len;
+
assert(src_len > 0);
assert(tgt_len > 0);
- mat = edge->costs;
+ pbqp_matrix_t *mat = edge->costs;
+ unsigned new_infinity = 0;
- for (src_index = 0; src_index < src_len; ++src_index) {
+ for (unsigned src_index = 0; src_index < src_len; ++src_index) {
num elem = mat->entries[src_index * tgt_len + col_index];
if (elem != 0) {
if (elem == INF_COSTS && src_vec->entries[src_index].data != INF_COSTS)
new_infinity = 1;
- src_vec->entries[src_index].data = pbqp_add(
- src_vec->entries[src_index].data, elem);
+ src_vec->entries[src_index].data = pbqp_add(src_vec->entries[src_index].data, elem);
}
}
if (new_infinity) {
- unsigned edge_index;
unsigned edge_len = pbqp_node_get_degree(src_node);
- for (edge_index = 0; edge_index < edge_len; ++edge_index) {
+ for (unsigned edge_index = 0; edge_index < edge_len; ++edge_index) {
pbqp_edge_t *edge_candidate = src_node->edges[edge_index];
if (edge_candidate != edge) {
@@ -1211,39 +1076,29 @@ static void select_column(pbqp_edge_t *edge, unsigned col_index)
static void select_row(pbqp_edge_t *edge, unsigned row_index)
{
- pbqp_matrix_t *mat;
- pbqp_node_t *tgt_node;
- vector_t *tgt_vec;
- unsigned tgt_len;
- unsigned tgt_index;
- unsigned new_infinity = 0;
-
- tgt_node = edge->tgt;
-
- tgt_vec = tgt_node->costs;
+ pbqp_matrix_t *mat = edge->costs;
+ pbqp_node_t *tgt_node = edge->tgt;
+ vector_t *tgt_vec = tgt_node->costs;
+ unsigned tgt_len = tgt_vec->len;
+ unsigned new_infinity = 0;
- tgt_len = tgt_vec->len;
assert(tgt_len > 0);
- mat = edge->costs;
-
- for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
+ for (unsigned tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
num elem = mat->entries[row_index * tgt_len + tgt_index];
if (elem != 0) {
if (elem == INF_COSTS && tgt_vec->entries[tgt_index].data != INF_COSTS)
new_infinity = 1;
- tgt_vec->entries[tgt_index].data = pbqp_add(
- tgt_vec->entries[tgt_index].data, elem);
+ tgt_vec->entries[tgt_index].data = pbqp_add(tgt_vec->entries[tgt_index].data, elem);
}
}
if (new_infinity) {
- unsigned edge_index;
unsigned edge_len = pbqp_node_get_degree(tgt_node);
- for (edge_index = 0; edge_index < edge_len; ++edge_index) {
+ for (unsigned edge_index = 0; edge_index < edge_len; ++edge_index) {
pbqp_edge_t *edge_candidate = tgt_node->edges[edge_index];
if (edge_candidate != edge) {
@@ -1257,26 +1112,22 @@ static void select_row(pbqp_edge_t *edge, unsigned row_index)
void select_alternative(pbqp_node_t *node, unsigned selected_index)
{
- unsigned edge_index;
- unsigned node_index;
- unsigned node_len;
- vector_t *node_vec;
unsigned max_degree = pbqp_node_get_degree(node);
+ vector_t *node_vec = node->costs;
+ unsigned node_len = node_vec->len;
+ assert(selected_index < node_len);
node->solution = selected_index;
- node_vec = node->costs;
- node_len = node_vec->len;
- assert(selected_index < node_len);
/* Set all other costs to infinity. */
- for (node_index = 0; node_index < node_len; ++node_index) {
+ for (unsigned node_index = 0; node_index < node_len; ++node_index) {
if (node_index != selected_index) {
node_vec->entries[node_index].data = INF_COSTS;
}
}
/* Select corresponding row/column for incident edges. */
- for (edge_index = 0; edge_index < max_degree; ++edge_index) {
+ for (unsigned edge_index = 0; edge_index < max_degree; ++edge_index) {
pbqp_edge_t *edge = node->edges[edge_index];
if (edge->src == node)
@@ -1288,13 +1139,12 @@ void select_alternative(pbqp_node_t *node, unsigned selected_index)
pbqp_node_t *get_node_with_max_degree(void)
{
- pbqp_node_t **bucket = node_buckets[3];
- unsigned bucket_len = node_bucket_get_length(bucket);
- unsigned bucket_index;
- unsigned max_degree = 0;
- pbqp_node_t *result = NULL;
+ pbqp_node_t **bucket = node_buckets[3];
+ unsigned bucket_len = node_bucket_get_length(bucket);
+ unsigned max_degree = 0;
+ pbqp_node_t *result = NULL;
- for (bucket_index = 0; bucket_index < bucket_len; ++bucket_index) {
+ for (unsigned bucket_index = 0; bucket_index < bucket_len; ++bucket_index) {
pbqp_node_t *candidate = bucket[bucket_index];
unsigned degree = pbqp_node_get_degree(candidate);
@@ -1309,29 +1159,20 @@ pbqp_node_t *get_node_with_max_degree(void)
unsigned get_local_minimal_alternative(pbqp_t *pbqp, pbqp_node_t *node)
{
- pbqp_edge_t *edge;
- vector_t *node_vec;
- vector_t *vec;
- pbqp_matrix_t *mat;
- unsigned edge_index;
- unsigned max_degree;
- unsigned node_index;
- unsigned node_len;
- unsigned min_index = 0;
- num min = INF_COSTS;
- int is_src;
-
- node_vec = node->costs;
- node_len = node_vec->len;
- max_degree = pbqp_node_get_degree(node);
-
- for (node_index = 0; node_index < node_len; ++node_index) {
+ vector_t *node_vec = node->costs;
+ unsigned node_len = node_vec->len;
+ unsigned max_degree = pbqp_node_get_degree(node);
+ unsigned min_index = 0;
+ num min = INF_COSTS;
+
+ for (unsigned node_index = 0; node_index < node_len; ++node_index) {
num value = node_vec->entries[node_index].data;
- for (edge_index = 0; edge_index < max_degree; ++edge_index) {
- edge = node->edges[edge_index];
- mat = edge->costs;
- is_src = edge->src == node;
+ for (unsigned edge_index = 0; edge_index < max_degree; ++edge_index) {
+ pbqp_edge_t *edge = node->edges[edge_index];
+ pbqp_matrix_t *mat = edge->costs;
+ bool is_src = edge->src == node;
+ vector_t *vec;
if (is_src) {
vec = vector_copy(pbqp, edge->tgt->costs);
@@ -1357,9 +1198,11 @@ unsigned get_local_minimal_alternative(pbqp_t *pbqp, pbqp_node_t *node)
int node_is_reduced(pbqp_node_t *node)
{
- if (!reduced_bucket) return 0;
+ if (!reduced_bucket)
+ return 0;
- if (pbqp_node_get_degree(node) == 0) return 1;
+ if (pbqp_node_get_degree(node) == 0)
+ return 1;
return node_bucket_contains(reduced_bucket, node);
}
diff --git a/ir/kaps/pbqp_edge.c b/ir/kaps/pbqp_edge.c
index d016084..a1559ca 100644
--- a/ir/kaps/pbqp_edge.c
+++ b/ir/kaps/pbqp_edge.c
@@ -26,10 +26,8 @@
pbqp_edge_t *alloc_edge(pbqp_t *pbqp, int src_index, int tgt_index,
pbqp_matrix_t *costs)
{
- int transpose = 0;
- pbqp_edge_t *edge = OALLOC(&pbqp->obstack, pbqp_edge_t);
- pbqp_node_t *src_node;
- pbqp_node_t *tgt_node;
+ int transpose = 0;
+ pbqp_edge_t *edge = OALLOC(&pbqp->obstack, pbqp_edge_t);
if (tgt_index < src_index) {
int tmp = src_index;
@@ -39,9 +37,8 @@ pbqp_edge_t *alloc_edge(pbqp_t *pbqp, int src_index, int tgt_index,
transpose = 1;
}
- src_node = get_node(pbqp, src_index);
-
- tgt_node = get_node(pbqp, tgt_index);
+ pbqp_node_t *src_node = get_node(pbqp, src_index);
+ pbqp_node_t *tgt_node = get_node(pbqp, tgt_index);
if (transpose) {
edge->costs = pbqp_matrix_copy_and_transpose(pbqp, costs);
@@ -64,11 +61,8 @@ pbqp_edge_t *alloc_edge(pbqp_t *pbqp, int src_index, int tgt_index,
void delete_edge(pbqp_edge_t *edge)
{
- pbqp_node_t *src_node;
- pbqp_node_t *tgt_node;
-
- src_node = edge->src;
- tgt_node = edge->tgt;
+ pbqp_node_t *src_node = edge->src;
+ pbqp_node_t *tgt_node = edge->tgt;
disconnect_edge(src_node, edge);
disconnect_edge(tgt_node, edge);
@@ -82,20 +76,18 @@ void delete_edge(pbqp_edge_t *edge)
unsigned is_deleted(pbqp_edge_t *edge)
{
- unsigned deleted;
-
- deleted = (edge->src == NULL) && (edge-> tgt == NULL);
- return deleted;
+ return edge->src == NULL && edge->tgt == NULL;
}
pbqp_edge_t *pbqp_edge_deep_copy(pbqp_t *pbqp, pbqp_edge_t *edge,
pbqp_node_t *src_node, pbqp_node_t *tgt_node)
{
- pbqp_edge_t *copy = OALLOC(&pbqp->obstack, pbqp_edge_t);
assert(src_node);
assert(tgt_node);
+ pbqp_edge_t *copy = OALLOC(&pbqp->obstack, pbqp_edge_t);
+
copy->costs = pbqp_matrix_copy(pbqp, edge->costs);
/* Connect edge with incident nodes. */
diff --git a/ir/kaps/pbqp_node.c b/ir/kaps/pbqp_node.c
index c20178f..4276a0f 100644
--- a/ir/kaps/pbqp_node.c
+++ b/ir/kaps/pbqp_node.c
@@ -11,6 +11,8 @@
*/
#include "config.h"
+#include <stdbool.h>
+
#include "adt/array.h"
#include "assert.h"
@@ -37,18 +39,17 @@ pbqp_node_t *alloc_node(pbqp_t *pbqp, unsigned node_index, vector_t *costs)
int is_connected(pbqp_node_t *node, pbqp_edge_t *edge)
{
- pbqp_edge_t **edges;
- size_t edge_index;
- size_t edge_len;
-
assert(node);
- if (edge->src != node && edge->tgt != node) return 0;
- edges = node->edges;
- edge_len = ARR_LEN(edges);
+ if (edge->src != node && edge->tgt != node)
+ return 0;
+
+ pbqp_edge_t **edges = node->edges;
+ size_t edge_len = ARR_LEN(edges);
- for (edge_index = 0; edge_index < edge_len; ++edge_index) {
+ for (size_t edge_index = 0; edge_index < edge_len; ++edge_index) {
pbqp_edge_t *edge_candidate = edges[edge_index];
+
if (edge_candidate == edge) {
return 1;
}
@@ -59,15 +60,12 @@ int is_connected(pbqp_node_t *node, pbqp_edge_t *edge)
void disconnect_edge(pbqp_node_t *node, pbqp_edge_t *edge)
{
- pbqp_edge_t **edges;
- size_t edge_index;
- size_t edge_len;
-
- edges = node->edges;
- edge_len = ARR_LEN(edges);
+ pbqp_edge_t **edges = node->edges;
+ size_t edge_len = ARR_LEN(edges);
- for (edge_index = 0; edge_index < edge_len; ++edge_index) {
+ for (size_t edge_index = 0; edge_index < edge_len; ++edge_index) {
pbqp_edge_t *edge_candidate = edges[edge_index];
+
if (edge_candidate == edge) {
edges[edge_index] = edges[edge_len - 1];
ARR_SHRINKLEN(edges, (int)edge_len - 1);
@@ -84,19 +82,19 @@ unsigned pbqp_node_get_degree(pbqp_node_t *node)
pbqp_node_t *pbqp_node_deep_copy(pbqp_t *pbqp, pbqp_node_bucket_t new_bucket,
pbqp_node_t *node)
{
- unsigned edge_index;
unsigned edge_length = pbqp_node_get_degree(node);
pbqp_node_t *copy = OALLOC(&pbqp->obstack, pbqp_node_t);
- copy->edges = NEW_ARR_F(pbqp_edge_t *, 0);
- for (edge_index = 0; edge_index < edge_length; ++edge_index) {
+ copy->edges = NEW_ARR_F(pbqp_edge_t *, 0);
+
+ for (unsigned edge_index = 0; edge_index < edge_length; ++edge_index) {
pbqp_edge_t *edge_copy = NULL;
pbqp_edge_t *edge = node->edges[edge_index];
- int is_src = edge->src == node;
+ bool is_src = edge->src == node;
if (is_src) {
unsigned other_index = edge->tgt->bucket_index;
- unsigned is_copied = other_index < node->bucket_index;
+ bool is_copied = other_index < node->bucket_index;
if (is_copied) {
pbqp_node_t *other_copy = new_bucket[other_index];
@@ -115,14 +113,13 @@ pbqp_node_t *pbqp_node_deep_copy(pbqp_t *pbqp, pbqp_node_bucket_t new_bucket,
}
} else {
unsigned other_index = edge->src->bucket_index;
- unsigned is_copied = other_index < node->bucket_index;
+ bool is_copied = other_index < node->bucket_index;
if (is_copied) {
pbqp_node_t *other_copy = new_bucket[other_index];
unsigned degree = pbqp_node_get_degree(other_copy);
- unsigned index;
- for (index = 0; index < degree; ++index) {
+ for (unsigned index = 0; index < degree; ++index) {
if (other_copy->edges[index]->tgt == node) {
edge_copy = other_copy->edges[index];
edge_copy->tgt = copy;
@@ -133,12 +130,14 @@ pbqp_node_t *pbqp_node_deep_copy(pbqp_t *pbqp, pbqp_node_bucket_t new_bucket,
edge_copy = pbqp_edge_deep_copy(pbqp, edge, edge->src, copy);
}
}
+
ARR_APP1(pbqp_edge_t *, copy->edges, edge_copy);
}
+
copy->costs = vector_copy(pbqp, node->costs);
copy->bucket_index = node->bucket_index;
copy->solution = node->solution;
- copy->index = node->index;
+ copy->index = node->index;
return copy;
}
diff --git a/ir/kaps/vector.c b/ir/kaps/vector.c
index 2b41abe..774e40b 100644
--- a/ir/kaps/vector.c
+++ b/ir/kaps/vector.c
@@ -19,11 +19,10 @@
num pbqp_add(num x, num y)
{
- num res;
+ if (x == INF_COSTS || y == INF_COSTS)
+ return INF_COSTS;
- if (x == INF_COSTS || y == INF_COSTS) return INF_COSTS;
-
- res = x + y;
+ num res = x + y;
#if !KAPS_USE_UNSIGNED
/* No positive overflow. */
@@ -43,7 +42,7 @@ num pbqp_add(num x, num y)
vector_t *vector_alloc(pbqp_t *pbqp, unsigned length)
{
- vector_t *vec = (vector_t*)obstack_alloc(&pbqp->obstack, sizeof(*vec) + sizeof(*vec->entries) * length);
+ vector_t *vec = (vector_t *)obstack_alloc(&pbqp->obstack, sizeof(*vec) + sizeof(*vec->entries) * length);
assert(length > 0);
vec->len = length;
@@ -55,7 +54,7 @@ vector_t *vector_alloc(pbqp_t *pbqp, unsigned length)
vector_t *vector_copy(pbqp_t *pbqp, vector_t *v)
{
unsigned len = v->len;
- vector_t *copy = (vector_t*)obstack_copy(&pbqp->obstack, v, sizeof(*copy) + sizeof(*copy->entries) * len);
+ vector_t *copy = (vector_t *)obstack_copy(&pbqp->obstack, v, sizeof(*copy) + sizeof(*copy->entries) * len);
assert(copy);
return copy;
@@ -63,16 +62,12 @@ vector_t *vector_copy(pbqp_t *pbqp, vector_t *v)
void vector_add(vector_t *sum, vector_t *summand)
{
- int i;
- int len;
-
- assert(sum->len == summand->len);
+ unsigned len = sum->len;
- len = sum->len;
+ assert(len == summand->len);
- for (i = 0; i < len; ++i) {
- sum->entries[i].data = pbqp_add(sum->entries[i].data,
- summand->entries[i].data);
+ for (unsigned i = 0; i < len; ++i) {
+ sum->entries[i].data = pbqp_add(sum->entries[i].data, summand->entries[i].data);
}
}
@@ -92,57 +87,46 @@ void vector_set_description(vector_t *vec, unsigned index, const char *name)
void vector_add_value(vector_t *vec, num value)
{
- unsigned index;
- unsigned len;
+ unsigned len = vec->len;
- len = vec->len;
-
- for (index = 0; index < len; ++index) {
+ for (unsigned index = 0; index < len; ++index) {
vec->entries[index].data = pbqp_add(vec->entries[index].data, value);
}
}
void vector_add_matrix_col(vector_t *vec, pbqp_matrix_t *mat, unsigned col_index)
{
- unsigned index;
- unsigned len;
+ unsigned len = vec->len;
- assert(vec->len == mat->rows);
+ assert(len == mat->rows);
assert(col_index < mat->cols);
- len = vec->len;
-
- for (index = 0; index < len; ++index) {
+ for (unsigned index = 0; index < len; ++index) {
vec->entries[index].data = pbqp_add(vec->entries[index].data, mat->entries[index * mat->cols + col_index]);
}
}
void vector_add_matrix_row(vector_t *vec, pbqp_matrix_t *mat, unsigned row_index)
{
- unsigned index;
- unsigned len;
+ unsigned len = vec->len;
- assert(vec->len == mat->cols);
+ assert(len == mat->cols);
assert(row_index < mat->rows);
- len = vec->len;
- for (index = 0; index < len; ++index) {
- vec->entries[index].data = pbqp_add(vec->entries[index].data,
- mat->entries[row_index * mat->cols + index]);
+ for (unsigned index = 0; index < len; ++index) {
+ vec->entries[index].data = pbqp_add(vec->entries[index].data, mat->entries[row_index * mat->cols + index]);
}
}
num vector_get_min(vector_t *vec)
{
- unsigned index;
- unsigned len;
+ unsigned len = vec->len;
num min = INF_COSTS;
- len = vec->len;
assert(len > 0);
- for (index = 0; index < len; ++index) {
+ for (unsigned index = 0; index < len; ++index) {
num elem = vec->entries[index].data;
if (elem < min) {
@@ -155,15 +139,13 @@ num vector_get_min(vector_t *vec)
unsigned vector_get_min_index(vector_t *vec)
{
- unsigned index;
- unsigned len;
+ unsigned len = vec->len;
unsigned min_index = 0;
num min = INF_COSTS;
- len = vec->len;
assert(len > 0);
- for (index = 0; index < len; ++index) {
+ for (unsigned index = 0; index < len; ++index) {
num elem = vec->entries[index].data;
if (elem < min) {