From cc61141c8a3ab54e92f0dab3a2122ccd8cafe6ed Mon Sep 17 00:00:00 2001 From: "yu.dongliang" <18588496441@163.com> Date: Sun, 5 Jul 2026 12:38:37 +0800 Subject: [PATCH] delete some un-used code for native graph K-color --- native/risc/scf_risc.c | 32 ++-- native/risc/scf_risc.h | 7 +- native/risc/scf_risc_graph.c | 64 +++---- native/risc/scf_risc_rcg.c | 41 ++--- native/risc/scf_risc_reg_arm32.c | 8 +- native/risc/scf_risc_reg_arm64.c | 8 +- native/risc/scf_risc_reg_naja.c | 6 +- native/x64/scf_x64.c | 30 +-- native/x64/scf_x64.h | 9 +- native/x64/scf_x64_graph.c | 68 +++---- native/x64/scf_x64_rcg.c | 71 ++++---- native/x64/scf_x64_reg.c | 6 +- util/scf_graph.c | 302 +++---------------------------- util/scf_graph.h | 19 +- 14 files changed, 197 insertions(+), 474 deletions(-) diff --git a/native/risc/scf_risc.c b/native/risc/scf_risc.c index b38529e..4e915b0 100644 --- a/native/risc/scf_risc.c +++ b/native/risc/scf_risc.c @@ -252,13 +252,13 @@ static int _risc_function_finish(scf_native_t* ctx, scf_function_t* f) static void _risc_rcg_node_printf(risc_rcg_node_t* rn, scf_function_t* f) { - if (rn->dag_node) { - scf_variable_t* v = rn->dag_node->var; + if (rn->dn) { + scf_variable_t* v = rn->dn->var; if (v->w) { scf_logw("v_%d_%d/%s, %p,%p, ", v->w->line, v->w->pos, v->w->text->data, - v, rn->dag_node); + v, rn->dn); if (v->bp_offset < 0) printf("bp_offset: -%#x, ", -v->bp_offset); @@ -266,22 +266,22 @@ static void _risc_rcg_node_printf(risc_rcg_node_t* rn, scf_function_t* f) printf("bp_offset: %#x, ", v->bp_offset); printf("color: %ld, type: %ld, id: %ld, mask: %ld", - rn->dag_node->color, - RISC_COLOR_TYPE(rn->dag_node->color), - RISC_COLOR_ID(rn->dag_node->color), - RISC_COLOR_MASK(rn->dag_node->color)); + rn->dn->color, + RISC_COLOR_TYPE(rn->dn->color), + RISC_COLOR_ID(rn->dn->color), + RISC_COLOR_MASK(rn->dn->color)); } else { scf_logw("v_%#lx, %p,%p, color: %ld, type: %ld, id: %ld, mask: %ld", - (uintptr_t)v & 0xffff, v, rn->dag_node, - rn->dag_node->color, - RISC_COLOR_TYPE(rn->dag_node->color), - RISC_COLOR_ID(rn->dag_node->color), - RISC_COLOR_MASK(rn->dag_node->color)); + (uintptr_t)v & 0xffff, v, rn->dn, + rn->dn->color, + RISC_COLOR_TYPE(rn->dn->color), + RISC_COLOR_ID(rn->dn->color), + RISC_COLOR_MASK(rn->dn->color)); } - if (rn->dag_node->color > 0) { - scf_register_t* r = f->rops->find_register_color(rn->dag_node->color); + if (rn->dn->color > 0) { + scf_register_t* r = f->rops->find_register_color(rn->dn->color); printf(", reg: %s\n", r->name); } else { printf("\n"); @@ -469,8 +469,8 @@ static int _risc_bb_regs_from_graph(scf_basic_block_t* bb, scf_graph_t* g, scf_f int i; for (i = 0; i < g->nodes->size; i++) { scf_graph_node_t* gn = g->nodes->data[i]; - risc_rcg_node_t* rn = gn->data; - scf_dag_node_t* dn = rn->dag_node; + risc_rcg_node_t* rn = gn->data; + scf_dag_node_t* dn = rn->dn; scf_dn_status_t* ds; if (!dn) { diff --git a/native/risc/scf_risc.h b/native/risc/scf_risc.h index 41847cb..5bb7423 100644 --- a/native/risc/scf_risc.h +++ b/native/risc/scf_risc.h @@ -18,11 +18,8 @@ typedef struct { } scf_risc_context_t; typedef struct { - scf_dag_node_t* dag_node; - - scf_register_t* reg; - - scf_risc_OpCode_t* OpCode; + scf_dag_node_t* dn; + scf_register_t* reg; } risc_rcg_node_t; diff --git a/native/risc/scf_risc_graph.c b/native/risc/scf_risc_graph.c index aa2f63c..c83bf2e 100644 --- a/native/risc/scf_risc_graph.c +++ b/native/risc/scf_risc_graph.c @@ -5,7 +5,7 @@ static intptr_t _risc_color_select(scf_graph_node_t* node, scf_vector_t* colors, { risc_rcg_node_t* rn = node->data; - if (!rn->dag_node) { + if (!rn->dn) { assert(rn->reg); return rn->reg->color; } @@ -16,8 +16,8 @@ static intptr_t _risc_color_select(scf_graph_node_t* node, scf_vector_t* colors, int bytes = RISC_COLOR_BYTES(c); uint32_t type = RISC_COLOR_TYPE(c); - if (bytes == f->rops->variable_size (rn->dag_node->var) - && type == scf_variable_float(rn->dag_node->var)) + if (bytes == f->rops->variable_size (rn->dn->var) + && type == scf_variable_float(rn->dn->var)) return c; } @@ -76,7 +76,7 @@ static int _risc_kcolor_delete(scf_graph_t* graph, int k, scf_vector_t* deleted_ scf_logd("graph->nodes->size: %d, neighbors: %d, k: %d, node: %p, rn->reg: %p\n", graph->nodes->size, node->neighbors->size, k, node, rn->reg); - if (!rn->dag_node) { + if (!rn->dn) { assert(rn->reg); assert(node->color > 0); i++; @@ -91,13 +91,13 @@ static int _risc_kcolor_delete(scf_graph_t* graph, int k, scf_vector_t* deleted_ scf_logd("graph->nodes->size: %d, neighbors: %d, k: %d, node: %p, rn->reg: %p\n", graph->nodes->size, node->neighbors->size, k, node, rn->reg); - if (0 != scf_graph_delete_node(graph, node)) { - scf_loge("scf_graph_delete_node\n"); + if (0 != scf_graph_del_node(graph, node)) { + scf_loge("scf_graph_del_node\n"); return -1; } if (0 != scf_vector_add(deleted_nodes, node)) { - scf_loge("scf_graph_delete_node\n"); + scf_loge("scf_graph_del_node\n"); return -1; } nb_deleted++; @@ -119,7 +119,7 @@ static int _risc_kcolor_fill(scf_graph_t* graph, int k, scf_vector_t* colors, scf_vector_t* colors2 = NULL; for (i = deleted_nodes->size - 1; i >= 0; i--) { - scf_graph_node_t* node = deleted_nodes->data[i]; + scf_graph_node_t* node = deleted_nodes->data[i]; risc_rcg_node_t* rn = node->data; if (node->neighbors->size >= k) @@ -141,9 +141,9 @@ static int _risc_kcolor_fill(scf_graph_t* graph, int k, scf_vector_t* colors, if (f->rops->color_conflict(node->color, neighbor->color)) { scf_logd("node: %p, neighbor: %p, color: %#lx:%#lx\n", node, neighbor, node->color, neighbor->color); - scf_logd("node: %p, dn: %p, reg: %p\n", node, rn->dag_node, rn->reg); + scf_logd("node: %p, dn: %p, reg: %p\n", node, rn->dn, rn->reg); //assert(!rn->reg); - assert(rn->dag_node); + assert(rn->dn); node->color = 0; } } @@ -195,7 +195,7 @@ static int _risc_kcolor_find_not_neighbor(scf_graph_t* graph, int k, scf_graph_n node0 = graph->nodes->data[i]; rn0 = node0->data; - dn0 = rn0->dag_node; + dn0 = rn0->dn; if (!dn0) { assert(rn0->reg); @@ -216,7 +216,7 @@ static int _risc_kcolor_find_not_neighbor(scf_graph_t* graph, int k, scf_graph_n node1 = graph->nodes->data[j]; rn1 = node1->data; - dn1 = rn1->dag_node; + dn1 = rn1->dn; if (!dn1) { assert(rn1->reg); @@ -253,7 +253,7 @@ static scf_graph_node_t* _risc_max_neighbors(scf_graph_t* graph) int max = 0; int i; for (i = 0; i < graph->nodes->size; i++) { - scf_graph_node_t* node = graph->nodes->data[i]; + scf_graph_node_t* node = graph->nodes->data[i]; risc_rcg_node_t* rn = node->data; if (rn->reg) { @@ -269,10 +269,10 @@ static scf_graph_node_t* _risc_max_neighbors(scf_graph_t* graph) risc_rcg_node_t* rn = node_max->data; - if (rn->dag_node->var->w) - scf_logi("max_neighbors: %d, %s\n", max, rn->dag_node->var->w->text->data); + if (rn->dn->var->w) + scf_logi("max_neighbors: %d, %s\n", max, rn->dn->var->w->text->data); else - scf_logi("max_neighbors: %d, v_%p\n", max, rn->dag_node->var); + scf_logi("max_neighbors: %d, v_%p\n", max, rn->dn->var); return node_max; } @@ -285,50 +285,46 @@ static void _risc_kcolor_process_conflict(scf_graph_t* graph, scf_function_t* f) for (i = 0; i < graph->nodes->size - 1; i++) { - scf_graph_node_t* gn0 = graph->nodes->data[i]; + scf_graph_node_t* gn0 = graph->nodes->data[i]; risc_rcg_node_t* rn0 = gn0->data; - scf_logd("i: %d, rn0->dag_node: %p, rn0->reg: %p\n", i, rn0->dag_node, rn0->reg); + scf_logd("i: %d, rn0->dn: %p, rn0->reg: %p\n", i, rn0->dn, rn0->reg); if (0 == gn0->color) continue; for (j = i + 1; j < graph->nodes->size; j++) { - scf_graph_node_t* gn1 = graph->nodes->data[j]; + scf_graph_node_t* gn1 = graph->nodes->data[j]; risc_rcg_node_t* rn1 = gn1->data; - scf_logd("j: %d, rn1->dag_node: %p, rn1->reg: %p\n", j, rn1->dag_node, rn1->reg); + scf_logd("j: %d, rn1->dn: %p, rn1->reg: %p\n", j, rn1->dn, rn1->reg); if (0 == gn1->color) continue; if (!f->rops->color_conflict(gn0->color, gn1->color)) continue; - if (!rn0->dag_node) { - if (!rn1->dag_node) { + if (!rn0->dn) { + if (!rn1->dn) { continue; } rn1->reg = NULL; - rn1->OpCode = NULL; gn1->color = 0; - } else if (!rn1->dag_node) { + } else if (!rn1->dn) { rn0->reg = NULL; - rn0->OpCode = NULL; gn0->color = 0; } else { - int nb_parents0 = rn0->dag_node->parents ? rn0->dag_node->parents->size : 0; - int nb_parents1 = rn1->dag_node->parents ? rn1->dag_node->parents->size : 0; + int nb_parents0 = rn0->dn->parents ? rn0->dn->parents->size : 0; + int nb_parents1 = rn1->dn->parents ? rn1->dn->parents->size : 0; if (nb_parents0 > nb_parents1) { rn1->reg = NULL; - rn1->OpCode = NULL; gn1->color = 0; } else { rn0->reg = NULL; - rn0->OpCode = NULL; gn0->color = 0; } } @@ -386,8 +382,8 @@ static int _risc_graph_kcolor(scf_graph_t* graph, int k, scf_vector_t* colors, s goto error; } - int reg_size0 = f->rops->variable_size(rn0->dag_node->var); - int reg_size1 = f->rops->variable_size(rn1->dag_node->var); + int reg_size0 = f->rops->variable_size(rn0->dn->var); + int reg_size1 = f->rops->variable_size(rn1->dn->var); if (reg_size0 > reg_size1) { @@ -428,11 +424,11 @@ static int _risc_graph_kcolor(scf_graph_t* graph, int k, scf_vector_t* colors, s assert(!scf_vector_find(colors2, (void*)node0->color)); } - ret = scf_graph_delete_node(graph, node0); + ret = scf_graph_del_node(graph, node0); if (ret < 0) goto error; - ret = scf_graph_delete_node(graph, node1); + ret = scf_graph_del_node(graph, node1); if (ret < 0) goto error; @@ -455,7 +451,7 @@ overflow: node_max = _risc_max_neighbors(graph); assert(node_max); - ret = scf_graph_delete_node(graph, node_max); + ret = scf_graph_del_node(graph, node_max); if (ret < 0) goto error; node_max->color = -1; diff --git a/native/risc/scf_risc_rcg.c b/native/risc/scf_risc_rcg.c index 072f9db..7560702 100644 --- a/native/risc/scf_risc_rcg.c +++ b/native/risc/scf_risc_rcg.c @@ -3,28 +3,23 @@ static int _risc_rcg_node_cmp(const void* v0, const void* v1) { const scf_graph_node_t* gn1 = v1; - const risc_rcg_node_t* rn1 = gn1->data; - const risc_rcg_node_t* rn0 = v0; + const risc_rcg_node_t* rn1 = gn1->data; + const risc_rcg_node_t* rn0 = v0; - if (rn0->dag_node || rn1->dag_node) - return rn0->dag_node != rn1->dag_node; + if (rn0->dn || rn1->dn) + return rn0->dn != rn1->dn; return rn0->reg != rn1->reg; } int risc_rcg_find_node(scf_graph_node_t** pp, scf_graph_t* g, scf_dag_node_t* dn, scf_register_t* reg) { - risc_rcg_node_t* rn = calloc(1, sizeof(risc_rcg_node_t)); - if (!rn) - return -ENOMEM; - - rn->dag_node = dn; - rn->reg = reg; + risc_rcg_node_t tmp; - scf_graph_node_t* gn = scf_vector_find_cmp(g->nodes, rn, _risc_rcg_node_cmp); - free(rn); - rn = NULL; + tmp.dn = dn; + tmp.reg = reg; + scf_graph_node_t* gn = scf_vector_find_cmp(g->nodes, &tmp, _risc_rcg_node_cmp); if (!gn) return -1; @@ -34,16 +29,17 @@ int risc_rcg_find_node(scf_graph_node_t** pp, scf_graph_t* g, scf_dag_node_t* dn int _risc_rcg_make_node(scf_graph_node_t** pp, scf_graph_t* g, scf_dag_node_t* dn, scf_register_t* reg) { - risc_rcg_node_t* rn = calloc(1, sizeof(risc_rcg_node_t)); - if (!rn) - return -ENOMEM; + risc_rcg_node_t* rn; + risc_rcg_node_t tmp; - rn->dag_node = dn; - rn->reg = reg; - rn->OpCode = NULL; + tmp.dn = dn; + tmp.reg = reg; - scf_graph_node_t* gn = scf_vector_find_cmp(g->nodes, rn, _risc_rcg_node_cmp); + scf_graph_node_t* gn = scf_vector_find_cmp(g->nodes, &tmp, _risc_rcg_node_cmp); if (!gn) { + rn = calloc(1, sizeof(risc_rcg_node_t)); + if (!rn) + return -ENOMEM; gn = scf_graph_node_alloc(); if (!gn) { @@ -51,6 +47,8 @@ int _risc_rcg_make_node(scf_graph_node_t** pp, scf_graph_t* g, scf_dag_node_t* d return -ENOMEM; } + rn->dn = dn; + rn->reg = reg; gn->data = rn; if (reg) @@ -65,9 +63,6 @@ int _risc_rcg_make_node(scf_graph_node_t** pp, scf_graph_t* g, scf_dag_node_t* d } else { if (reg) gn->color = reg->color; - - free(rn); - rn = NULL; } *pp = gn; diff --git a/native/risc/scf_risc_reg_arm32.c b/native/risc/scf_risc_reg_arm32.c index d7499ec..d60b2e8 100644 --- a/native/risc/scf_risc_reg_arm32.c +++ b/native/risc/scf_risc_reg_arm32.c @@ -802,13 +802,13 @@ scf_register_t* arm32_select_overflowed_reg(scf_dag_node_t* dn, scf_3ac_code_t* for (j = 0; j < neighbors->size; j++) { scf_graph_node_t* neighbor = neighbors->data[j]; - risc_rcg_node_t* rn = neighbor->data; + risc_rcg_node_t* rn = neighbor->data; - if (rn->dag_node) { - if (rn->dag_node->color <= 0) + if (rn->dn) { + if (rn->dn->color <= 0) continue; - if (arm32_color_conflict(r->color, rn->dag_node->color)) + if (arm32_color_conflict(r->color, rn->dn->color)) break; } else { assert(rn->reg); diff --git a/native/risc/scf_risc_reg_arm64.c b/native/risc/scf_risc_reg_arm64.c index 6fa6d9d..8e2578b 100644 --- a/native/risc/scf_risc_reg_arm64.c +++ b/native/risc/scf_risc_reg_arm64.c @@ -892,13 +892,13 @@ scf_register_t* arm64_select_overflowed_reg(scf_dag_node_t* dn, scf_3ac_code_t* for (j = 0; j < neighbors->size; j++) { scf_graph_node_t* neighbor = neighbors->data[j]; - risc_rcg_node_t* rn = neighbor->data; + risc_rcg_node_t* rn = neighbor->data; - if (rn->dag_node) { - if (rn->dag_node->color <= 0) + if (rn->dn) { + if (rn->dn->color <= 0) continue; - if (arm64_color_conflict(r->color, rn->dag_node->color)) + if (arm64_color_conflict(r->color, rn->dn->color)) break; } else { assert(rn->reg); diff --git a/native/risc/scf_risc_reg_naja.c b/native/risc/scf_risc_reg_naja.c index fa795a5..4fac36e 100644 --- a/native/risc/scf_risc_reg_naja.c +++ b/native/risc/scf_risc_reg_naja.c @@ -521,11 +521,11 @@ scf_register_t* naja_select_overflowed_reg(scf_dag_node_t* dn, scf_3ac_code_t* c scf_graph_node_t* neighbor = neighbors->data[j]; risc_rcg_node_t* rn = neighbor->data; - if (rn->dag_node) { - if (rn->dag_node->color <= 0) + if (rn->dn) { + if (rn->dn->color <= 0) continue; - if (naja_color_conflict(r->color, rn->dag_node->color)) + if (naja_color_conflict(r->color, rn->dn->color)) break; } else { assert(rn->reg); diff --git a/native/x64/scf_x64.c b/native/x64/scf_x64.c index 903fa68..7877bda 100644 --- a/native/x64/scf_x64.c +++ b/native/x64/scf_x64.c @@ -298,8 +298,8 @@ static int _x64_function_finish(scf_function_t* f) static void _x64_rcg_node_printf(x64_rcg_node_t* rn) { - if (rn->dag_node) { - scf_variable_t* v = rn->dag_node->var; + if (rn->dn) { + scf_variable_t* v = rn->dn->var; if (v->w) { scf_logw("v_%d_%d/%s, ", @@ -311,22 +311,22 @@ static void _x64_rcg_node_printf(x64_rcg_node_t* rn) printf("bp_offset: %#x, ", v->bp_offset); printf("color: %ld, type: %ld, id: %ld, mask: %ld", - rn->dag_node->color, - X64_COLOR_TYPE(rn->dag_node->color), - X64_COLOR_ID(rn->dag_node->color), - X64_COLOR_MASK(rn->dag_node->color)); + rn->dn->color, + X64_COLOR_TYPE(rn->dn->color), + X64_COLOR_ID(rn->dn->color), + X64_COLOR_MASK(rn->dn->color)); } else { scf_logw("v_%#lx, %p,%p, color: %ld, type: %ld, id: %ld, mask: %ld", - (uintptr_t)v & 0xffff, v, rn->dag_node, - rn->dag_node->color, - X64_COLOR_TYPE(rn->dag_node->color), - X64_COLOR_ID(rn->dag_node->color), - X64_COLOR_MASK(rn->dag_node->color)); + (uintptr_t)v & 0xffff, v, rn->dn, + rn->dn->color, + X64_COLOR_TYPE(rn->dn->color), + X64_COLOR_ID(rn->dn->color), + X64_COLOR_MASK(rn->dn->color)); } - if (rn->dag_node->color > 0) { - scf_register_t* r = x64_find_register_color(rn->dag_node->color); + if (rn->dn->color > 0) { + scf_register_t* r = x64_find_register_color(rn->dn->color); printf(", reg: %s\n", r->name); } else { printf("\n"); @@ -381,7 +381,7 @@ static int _x64_argv_prepare(scf_graph_t* g, scf_basic_block_t* bb, scf_function if (l == scf_list_sentinel(&f->dag_list_head)) continue; - int ret = _x64_rcg_make_node(&gn, g, dn, v->rabi, NULL); + int ret = _x64_rcg_make_node(&gn, g, dn, v->rabi); if (ret < 0) return ret; @@ -516,7 +516,7 @@ static int _x64_bb_regs_from_graph(scf_basic_block_t* bb, scf_graph_t* g) for (i = 0; i < g->nodes->size; i++) { scf_graph_node_t* gn = g->nodes->data[i]; x64_rcg_node_t* rn = gn->data; - scf_dag_node_t* dn = rn->dag_node; + scf_dag_node_t* dn = rn->dn; scf_dn_status_t* ds; if (!dn) { diff --git a/native/x64/scf_x64.h b/native/x64/scf_x64.h index e30405c..54c6821 100644 --- a/native/x64/scf_x64.h +++ b/native/x64/scf_x64.h @@ -18,12 +18,9 @@ typedef struct { } scf_x64_context_t; typedef struct { - scf_dag_node_t* dag_node; - + scf_dag_node_t* dn; scf_register_t* reg; - scf_x64_OpCode_t* OpCode; - } x64_rcg_node_t; @@ -33,8 +30,8 @@ typedef int (*x64_inst_handler_pt)(scf_native_t* ctx, scf_3ac_code_t* c); x64_rcg_handler_pt scf_x64_find_rcg_handler (const int op_type); x64_inst_handler_pt scf_x64_find_inst_handler(const int op_type); -int x64_rcg_find_node(scf_graph_node_t** pp, scf_graph_t* g, scf_dag_node_t* dn, scf_register_t* reg); -int _x64_rcg_make_node(scf_graph_node_t** pp, scf_graph_t* g, scf_dag_node_t* dn, scf_register_t* reg, scf_x64_OpCode_t* OpCode); +int x64_rcg_find_node(scf_graph_node_t** pp, scf_graph_t* g, scf_dag_node_t* dn, scf_register_t* reg); +int _x64_rcg_make_node(scf_graph_node_t** pp, scf_graph_t* g, scf_dag_node_t* dn, scf_register_t* reg); int scf_x64_open (scf_native_t* ctx, const char* arch); int scf_x64_close (scf_native_t* ctx); diff --git a/native/x64/scf_x64_graph.c b/native/x64/scf_x64_graph.c index aebd3cd..6df3f14 100644 --- a/native/x64/scf_x64_graph.c +++ b/native/x64/scf_x64_graph.c @@ -5,7 +5,7 @@ static intptr_t _x64_color_select(scf_graph_node_t* node, scf_vector_t* colors) { x64_rcg_node_t* rn = node->data; - if (!rn->dag_node) { + if (!rn->dn) { assert(rn->reg); return rn->reg->color; } @@ -16,8 +16,8 @@ static intptr_t _x64_color_select(scf_graph_node_t* node, scf_vector_t* colors) int bytes = X64_COLOR_BYTES(c); uint32_t type = X64_COLOR_TYPE(c); - if (bytes == x64_variable_size(rn->dag_node->var) - && type == scf_variable_float(rn->dag_node->var)) + if (bytes == x64_variable_size(rn->dn->var) + && type == scf_variable_float(rn->dn->var)) return c; } @@ -76,7 +76,7 @@ static int _x64_kcolor_delete(scf_graph_t* graph, int k, scf_vector_t* deleted_n scf_logd("graph->nodes->size: %d, neighbors: %d, k: %d, node: %p, rn->reg: %p\n", graph->nodes->size, node->neighbors->size, k, node, rn->reg); - if (!rn->dag_node) { + if (!rn->dn) { assert(rn->reg); assert(node->color > 0); i++; @@ -91,13 +91,13 @@ static int _x64_kcolor_delete(scf_graph_t* graph, int k, scf_vector_t* deleted_n scf_logd("graph->nodes->size: %d, neighbors: %d, k: %d, node: %p, rn->reg: %p\n", graph->nodes->size, node->neighbors->size, k, node, rn->reg); - if (0 != scf_graph_delete_node(graph, node)) { - scf_loge("scf_graph_delete_node\n"); + if (0 != scf_graph_del_node(graph, node)) { + scf_loge("scf_graph_del_node\n"); return -1; } if (0 != scf_vector_add(deleted_nodes, node)) { - scf_loge("scf_graph_delete_node\n"); + scf_loge("scf_graph_del_node\n"); return -1; } nb_deleted++; @@ -141,9 +141,9 @@ static int _x64_kcolor_fill(scf_graph_t* graph, int k, scf_vector_t* colors, if (X64_COLOR_CONFLICT(node->color, neighbor->color)) { scf_logd("node: %p, neighbor: %p, color: %#lx:%#lx\n", node, neighbor, node->color, neighbor->color); - scf_logd("node: %p, dn: %p, reg: %p\n", node, rn->dag_node, rn->reg); + scf_logd("node: %p, dn: %p, reg: %p\n", node, rn->dn, rn->reg); //assert(!rn->reg); - assert(rn->dag_node); + assert(rn->dn); node->color = 0; } } @@ -195,7 +195,7 @@ static int _x64_kcolor_find_not_neighbor(scf_graph_t* graph, int k, scf_graph_no node0 = graph->nodes->data[i]; rn0 = node0->data; - dn0 = rn0->dag_node; + dn0 = rn0->dn; if (!dn0) { assert(rn0->reg); @@ -216,7 +216,7 @@ static int _x64_kcolor_find_not_neighbor(scf_graph_t* graph, int k, scf_graph_no node1 = graph->nodes->data[j]; rn1 = node1->data; - dn1 = rn1->dag_node; + dn1 = rn1->dn; if (!dn1) { assert(rn1->reg); @@ -249,12 +249,16 @@ static int _x64_kcolor_find_not_neighbor(scf_graph_t* graph, int k, scf_graph_no static scf_graph_node_t* _x64_max_neighbors(scf_graph_t* graph) { - scf_graph_node_t* node_max = NULL; + scf_graph_node_t* node_max = NULL; + scf_graph_node_t* node; + x64_rcg_node_t* rn; + int max = 0; int i; + for (i = 0; i < graph->nodes->size; i++) { - scf_graph_node_t* node = graph->nodes->data[i]; - x64_rcg_node_t* rn = node->data; + node = graph->nodes->data[i]; + rn = node->data; if (rn->reg) { assert(node->color > 0); @@ -267,12 +271,12 @@ static scf_graph_node_t* _x64_max_neighbors(scf_graph_t* graph) } } - x64_rcg_node_t* rn = node_max->data; + rn = node_max->data; - if (rn->dag_node->var->w) - scf_logd("max_neighbors: %d, %s\n", max, rn->dag_node->var->w->text->data); + if (rn->dn->var->w) + scf_logd("max_neighbors: %d, %s\n", max, rn->dn->var->w->text->data); else - scf_logd("max_neighbors: %d, v_%p\n", max, rn->dag_node->var); + scf_logd("max_neighbors: %d, v_%p\n", max, rn->dn->var); return node_max; } @@ -288,7 +292,7 @@ static void _x64_kcolor_process_conflict(scf_graph_t* graph) scf_graph_node_t* gn0 = graph->nodes->data[i]; x64_rcg_node_t* rn0 = gn0->data; - scf_logd("i: %d, rn0->dag_node: %p, rn0->reg: %p\n", i, rn0->dag_node, rn0->reg); + scf_logd("i: %d, rn0->dn: %p, rn0->reg: %p\n", i, rn0->dn, rn0->reg); if (0 == gn0->color) continue; @@ -297,38 +301,34 @@ static void _x64_kcolor_process_conflict(scf_graph_t* graph) scf_graph_node_t* gn1 = graph->nodes->data[j]; x64_rcg_node_t* rn1 = gn1->data; - scf_logd("j: %d, rn1->dag_node: %p, rn1->reg: %p\n", j, rn1->dag_node, rn1->reg); + scf_logd("j: %d, rn1->dn: %p, rn1->reg: %p\n", j, rn1->dn, rn1->reg); if (0 == gn1->color) continue; if (!X64_COLOR_CONFLICT(gn0->color, gn1->color)) continue; - if (!rn0->dag_node) { - if (!rn1->dag_node) { + if (!rn0->dn) { + if (!rn1->dn) { continue; } rn1->reg = NULL; - rn1->OpCode = NULL; gn1->color = 0; - } else if (!rn1->dag_node) { + } else if (!rn1->dn) { rn0->reg = NULL; - rn0->OpCode = NULL; gn0->color = 0; } else { - int nb_parents0 = rn0->dag_node->parents ? rn0->dag_node->parents->size : 0; - int nb_parents1 = rn1->dag_node->parents ? rn1->dag_node->parents->size : 0; + int nb_parents0 = rn0->dn->parents ? rn0->dn->parents->size : 0; + int nb_parents1 = rn1->dn->parents ? rn1->dn->parents->size : 0; if (nb_parents0 > nb_parents1) { rn1->reg = NULL; - rn1->OpCode = NULL; gn1->color = 0; } else { rn0->reg = NULL; - rn0->OpCode = NULL; gn0->color = 0; } } @@ -386,8 +386,8 @@ static int _x64_graph_kcolor(scf_graph_t* graph, int k, scf_vector_t* colors) goto error; } - int reg_size0 = x64_variable_size(rn0->dag_node->var); - int reg_size1 = x64_variable_size(rn1->dag_node->var); + int reg_size0 = x64_variable_size(rn0->dn->var); + int reg_size1 = x64_variable_size(rn1->dn->var); if (reg_size0 > reg_size1) { @@ -428,11 +428,11 @@ static int _x64_graph_kcolor(scf_graph_t* graph, int k, scf_vector_t* colors) assert(!scf_vector_find(colors2, (void*)node0->color)); } - ret = scf_graph_delete_node(graph, node0); + ret = scf_graph_del_node(graph, node0); if (ret < 0) goto error; - ret = scf_graph_delete_node(graph, node1); + ret = scf_graph_del_node(graph, node1); if (ret < 0) goto error; @@ -455,7 +455,7 @@ overflow: node_max = _x64_max_neighbors(graph); assert(node_max); - ret = scf_graph_delete_node(graph, node_max); + ret = scf_graph_del_node(graph, node_max); if (ret < 0) goto error; node_max->color = -1; diff --git a/native/x64/scf_x64_rcg.c b/native/x64/scf_x64_rcg.c index 79059a8..58f7344 100644 --- a/native/x64/scf_x64_rcg.c +++ b/native/x64/scf_x64_rcg.c @@ -6,25 +6,20 @@ static int _x64_rcg_node_cmp(const void* v0, const void* v1) const x64_rcg_node_t* rn1 = gn1->data; const x64_rcg_node_t* rn0 = v0; - if (rn0->dag_node || rn1->dag_node) - return rn0->dag_node != rn1->dag_node; + if (rn0->dn || rn1->dn) + return rn0->dn != rn1->dn; return rn0->reg != rn1->reg; } int x64_rcg_find_node(scf_graph_node_t** pp, scf_graph_t* g, scf_dag_node_t* dn, scf_register_t* reg) { - x64_rcg_node_t* rn = calloc(1, sizeof(x64_rcg_node_t)); - if (!rn) - return -ENOMEM; - - rn->dag_node = dn; - rn->reg = reg; + x64_rcg_node_t tmp; - scf_graph_node_t* gn = scf_vector_find_cmp(g->nodes, rn, _x64_rcg_node_cmp); - free(rn); - rn = NULL; + tmp.dn = dn; + tmp.reg = reg; + scf_graph_node_t* gn = scf_vector_find_cmp(g->nodes, &tmp, _x64_rcg_node_cmp); if (!gn) return -1; @@ -32,18 +27,19 @@ int x64_rcg_find_node(scf_graph_node_t** pp, scf_graph_t* g, scf_dag_node_t* dn, return 0; } -int _x64_rcg_make_node(scf_graph_node_t** pp, scf_graph_t* g, scf_dag_node_t* dn, scf_register_t* reg, scf_x64_OpCode_t* OpCode) +int _x64_rcg_make_node(scf_graph_node_t** pp, scf_graph_t* g, scf_dag_node_t* dn, scf_register_t* reg) { - x64_rcg_node_t* rn = calloc(1, sizeof(x64_rcg_node_t)); - if (!rn) - return -ENOMEM; + x64_rcg_node_t* rn; + x64_rcg_node_t tmp; - rn->dag_node = dn; - rn->reg = reg; - rn->OpCode = OpCode; + tmp.dn = dn; + tmp.reg = reg; - scf_graph_node_t* gn = scf_vector_find_cmp(g->nodes, rn, _x64_rcg_node_cmp); + scf_graph_node_t* gn = scf_vector_find_cmp(g->nodes, &tmp, _x64_rcg_node_cmp); if (!gn) { + rn = calloc(1, sizeof(x64_rcg_node_t)); + if (!rn) + return -ENOMEM; gn = scf_graph_node_alloc(); if (!gn) { @@ -51,6 +47,8 @@ int _x64_rcg_make_node(scf_graph_node_t** pp, scf_graph_t* g, scf_dag_node_t* dn return -ENOMEM; } + rn->dn = dn; + rn->reg = reg; gn->data = rn; if (reg) @@ -65,9 +63,6 @@ int _x64_rcg_make_node(scf_graph_node_t** pp, scf_graph_t* g, scf_dag_node_t* dn } else { if (reg) gn->color = reg->color; - - free(rn); - rn = NULL; } *pp = gn; @@ -119,7 +114,7 @@ static int _x64_rcg_active_vars(scf_graph_t* g, scf_vector_t* active_vars) if (!ds0->active) continue; - ret = _x64_rcg_make_node(&gn0, g, dn0, NULL, NULL); + ret = _x64_rcg_make_node(&gn0, g, dn0, NULL); if (ret < 0) return ret; @@ -131,7 +126,7 @@ static int _x64_rcg_active_vars(scf_graph_t* g, scf_vector_t* active_vars) if (!ds1->active) continue; - ret = _x64_rcg_make_node(&gn1, g, dn1, NULL, NULL); + ret = _x64_rcg_make_node(&gn1, g, dn1, NULL); if (ret < 0) return ret; @@ -168,7 +163,7 @@ static int _x64_rcg_operands(scf_graph_t* g, scf_vector_t* operands) if (scf_variable_const(dn0->var)) continue; - int ret = _x64_rcg_make_node(&gn0, g, dn0, NULL, NULL); + int ret = _x64_rcg_make_node(&gn0, g, dn0, NULL); if (ret < 0) return ret; @@ -180,7 +175,7 @@ static int _x64_rcg_operands(scf_graph_t* g, scf_vector_t* operands) if (scf_variable_const(dn1->var)) continue; - ret = _x64_rcg_make_node(&gn1, g, dn1, NULL, NULL); + ret = _x64_rcg_make_node(&gn1, g, dn1, NULL); if (ret < 0) return ret; @@ -213,7 +208,7 @@ static int _x64_rcg_to_active_vars(scf_graph_t* g, scf_graph_node_t* gn0, scf_ve if (!ds1->active) continue; - ret = _x64_rcg_make_node(&gn1, g, dn1, NULL, NULL); + ret = _x64_rcg_make_node(&gn1, g, dn1, NULL); if (ret < 0) return ret; @@ -240,7 +235,7 @@ static int _x64_rcg_make(scf_3ac_code_t* c, scf_graph_t* g, scf_dag_node_t* dn, int i; if (dn || reg) { - ret = _x64_rcg_make_node(&gn0, g, dn, reg, OpCode); + ret = _x64_rcg_make_node(&gn0, g, dn, reg); if (ret < 0) { scf_loge("\n"); return ret; @@ -333,7 +328,7 @@ static int _x64_rcg_call(scf_native_t* ctx, scf_3ac_code_t* c, scf_graph_t* g) r = NULL; gn = NULL; - ret = _x64_rcg_make_node(&gn, g, dn, r, NULL); + ret = _x64_rcg_make_node(&gn, g, dn, r); if (ret < 0) { scf_loge("\n"); return ret; @@ -360,7 +355,7 @@ static int _x64_rcg_call(scf_native_t* ctx, scf_3ac_code_t* c, scf_graph_t* g) continue; gn = NULL; - ret = _x64_rcg_make_node(&gn, g, dn, dn->rabi2, NULL); + ret = _x64_rcg_make_node(&gn, g, dn, dn->rabi2); if (ret < 0) { scf_loge("\n"); return ret; @@ -373,7 +368,7 @@ static int _x64_rcg_call(scf_native_t* ctx, scf_3ac_code_t* c, scf_graph_t* g) if (!dn_pf->var->const_literal_flag) { - ret = _x64_rcg_make_node(&gn_pf, g, dn_pf, NULL, NULL); + ret = _x64_rcg_make_node(&gn_pf, g, dn_pf, NULL); if (ret < 0) { scf_loge("\n"); return ret; @@ -386,7 +381,7 @@ static int _x64_rcg_call(scf_native_t* ctx, scf_3ac_code_t* c, scf_graph_t* g) rabi = x64_find_register_type_id_bytes(0, x64_abi_regs[i], dn_pf->var->size); - ret = _x64_rcg_make_node(&gn_rabi, g, NULL, rabi, NULL); + ret = _x64_rcg_make_node(&gn_rabi, g, NULL, rabi); if (ret < 0) { scf_loge("\n"); return ret; @@ -674,7 +669,7 @@ static int _x64_rcg_shift(scf_native_t* ctx, scf_3ac_code_t* c, scf_graph_t* g) if (scf_variable_const(count->dag_node->var)) return _x64_rcg_make(c, g, dn, NULL, NULL); - int ret = _x64_rcg_make_node(&gn, g, count->dag_node, cl, NULL); + int ret = _x64_rcg_make_node(&gn, g, count->dag_node, cl); if (ret < 0) return ret; @@ -682,12 +677,12 @@ static int _x64_rcg_shift(scf_native_t* ctx, scf_3ac_code_t* c, scf_graph_t* g) if (ret < 0) return ret; - ret = _x64_rcg_make_node(&gn_cl, g, NULL, cl, NULL); + ret = _x64_rcg_make_node(&gn_cl, g, NULL, cl); if (ret < 0) return ret; if (dn) { - ret = _x64_rcg_make_node(&gn, g, dn, NULL, NULL); + ret = _x64_rcg_make_node(&gn, g, dn, NULL); if (ret < 0) return ret; @@ -701,7 +696,7 @@ static int _x64_rcg_shift(scf_native_t* ctx, scf_3ac_code_t* c, scf_graph_t* g) scf_3ac_operand_t* src = c->srcs->data[i]; scf_graph_node_t* gn_src = NULL; - ret = _x64_rcg_make_node(&gn_src, g, src->dag_node, NULL, NULL); + ret = _x64_rcg_make_node(&gn_src, g, src->dag_node, NULL); if (ret < 0) return ret; @@ -959,7 +954,7 @@ static int _x64_rcg_return_handler(scf_native_t* ctx, scf_3ac_code_t* c, scf_gra } else r = x64_find_register_type_id_bytes(is_float, x64_abi_ret_regs[i], size); - ret = _x64_rcg_make_node(&gn, g, dn, r, NULL); + ret = _x64_rcg_make_node(&gn, g, dn, r); if (ret < 0) return ret; } @@ -1005,7 +1000,7 @@ static int _x64_rcg_memset_handler(scf_native_t* ctx, scf_3ac_code_t* c, scf_gra else return -EINVAL; - ret = _x64_rcg_make_node(&gn, g, dn, r, NULL); + ret = _x64_rcg_make_node(&gn, g, dn, r); if (ret < 0) return ret; } diff --git a/native/x64/scf_x64_reg.c b/native/x64/scf_x64_reg.c index 38505ce..d017fab 100644 --- a/native/x64/scf_x64_reg.c +++ b/native/x64/scf_x64_reg.c @@ -618,11 +618,11 @@ scf_register_t* x64_select_overflowed_reg(scf_dag_node_t* dn, scf_3ac_code_t* c) scf_graph_node_t* neighbor = neighbors->data[j]; x64_rcg_node_t* rn = neighbor->data; - if (rn->dag_node) { - if (rn->dag_node->color <= 0) + if (rn->dn) { + if (rn->dn->color <= 0) continue; - if (X64_COLOR_CONFLICT(r->color, rn->dag_node->color)) + if (X64_COLOR_CONFLICT(r->color, rn->dn->color)) break; } else { assert(rn->reg); diff --git a/util/scf_graph.c b/util/scf_graph.c index e64a351..ba97b42 100644 --- a/util/scf_graph.c +++ b/util/scf_graph.c @@ -9,26 +9,18 @@ scf_graph_t* scf_graph_alloc() graph->nodes = scf_vector_alloc(); if (!graph->nodes) { free(graph); - graph = NULL; return NULL; } + return graph; } void scf_graph_free(scf_graph_t* graph) { if (graph) { - int i; - for (i = 0; i < graph->nodes->size; i++) { - - scf_graph_node_t* node = graph->nodes->data[i]; - - scf_graph_node_free(node); - } - - scf_vector_free(graph->nodes); + scf_vector_clear(graph->nodes, ( void (*)(void*) )scf_graph_node_free); + scf_vector_free (graph->nodes); free(graph); - graph = NULL; } } @@ -41,9 +33,9 @@ scf_graph_node_t* scf_graph_node_alloc() node->neighbors = scf_vector_alloc(); if (!node->neighbors) { free(node); - node = NULL; return NULL; } + return node; } @@ -52,7 +44,6 @@ void scf_graph_node_free(scf_graph_node_t* node) if (node) { scf_vector_free(node->neighbors); free(node); - node = NULL; } } @@ -60,11 +51,16 @@ void scf_graph_node_print(scf_graph_node_t* node) { if (node) { printf("node: %p, color: %d\n", node, (int)node->color); + + scf_graph_node_t* neighbor; int j; + for (j = 0; j < node->neighbors->size; j++) { - scf_graph_node_t* neighbor = node->neighbors->data[j]; + neighbor = node->neighbors->data[j]; + printf("neighbor: %p, color: %d\n", neighbor, (int)neighbor->color); } + printf("\n"); } } @@ -77,296 +73,44 @@ int scf_graph_make_edge(scf_graph_node_t* node1, scf_graph_node_t* node2) return scf_vector_add(node1->neighbors, node2); } -int scf_graph_delete_node(scf_graph_t* graph, scf_graph_node_t* node) +int scf_graph_del_node(scf_graph_t* graph, scf_graph_node_t* node) { if (!graph || !node) return -EINVAL; - scf_graph_node_t* neighbor; + scf_graph_node_t* neighbor; int j; for (j = 0; j < node->neighbors->size; j++) { neighbor = node->neighbors->data[j]; - scf_logd("node %p, neighbor: %p, %d\n", node, neighbor, neighbor->neighbors->size); - // it may be not 2 side graph scf_vector_del(neighbor->neighbors, node); } - if (0 != scf_vector_del(graph->nodes, node)) - return -1; - return 0; + return scf_vector_del(graph->nodes, node); } int scf_graph_add_node(scf_graph_t* graph, scf_graph_node_t* node) { + scf_graph_node_t* neighbor; int j; - for (j = 0; j < node->neighbors->size; j++) { - - scf_graph_node_t* neighbor = node->neighbors->data[j]; - - if (scf_vector_find(graph->nodes, neighbor)) { - - if (!scf_vector_find(neighbor->neighbors, node)) { - - if (0 != scf_vector_add(neighbor->neighbors, node)) - return -1; - } else - scf_logw("node %p already in neighbor: %p\n", node, neighbor); - } else - scf_logw("neighbor: %p of node: %p not in graph\n", neighbor, node); - } - - if (0 != scf_vector_add(graph->nodes, node)) - return -1; - return 0; -} - -static int _kcolor_delete(scf_graph_t* graph, int k, scf_vector_t* deleted_nodes) -{ - while (graph->nodes->size > 0) { - - int nb_deleted = 0; - int i = 0; - while (i < graph->nodes->size) { - - scf_graph_node_t* node = graph->nodes->data[i]; - - if (node->neighbors->size >= k) { - i++; - continue; - } - - if (0 != scf_graph_delete_node(graph, node)) { - scf_loge("scf_graph_delete_node\n"); - return -1; - } - - if (0 != scf_vector_add(deleted_nodes, node)) { - scf_loge("scf_graph_delete_node\n"); - return -1; - } - nb_deleted++; - } - - if (0 == nb_deleted) - break; - } - return 0; -} - -static int _kcolor_fill(scf_graph_t* graph, scf_vector_t* colors, scf_vector_t* deleted_nodes) -{ - int k = colors->size; - int i; - int j; - scf_vector_t* colors2 = NULL; - - for (i = deleted_nodes->size - 1; i >= 0; i--) { - scf_graph_node_t* node = deleted_nodes->data[i]; - - assert(node->neighbors->size < k); - - colors2 = scf_vector_clone(colors); - if (!colors2) - return -ENOMEM; - - scf_logd("node: %p, neighbor: %d, k: %d\n", node, node->neighbors->size, k); - - for (j = 0; j < node->neighbors->size; j++) { - scf_graph_node_t* neighbor = node->neighbors->data[j]; - - if (neighbor->color > 0) - scf_vector_del(colors2, (void*)neighbor->color); - - if (0 != scf_vector_add(neighbor->neighbors, node)) - goto error; - } - - assert(colors2->size >= 0); - if (0 == colors2->size) - goto error; - - node->color = (intptr_t)(colors2->data[0]); - if (0 != scf_vector_add(graph->nodes, node)) - goto error; - - scf_vector_free(colors2); - colors2 = NULL; - } - - return 0; - -error: - scf_vector_free(colors2); - colors2 = NULL; - return -1; -} - -static int _kcolor_find_not_neighbor(scf_graph_t* graph, int k, scf_graph_node_t** pp0, scf_graph_node_t** pp1) -{ - assert(graph->nodes->size >= k); - - int i; - for (i = 0; i < graph->nodes->size; i++) { - scf_graph_node_t* node0 = graph->nodes->data[i]; + for (j = 0; j < node->neighbors->size; j++) { + neighbor = node->neighbors->data[j]; - if (node0->neighbors->size > k) + if (!scf_vector_find(graph->nodes, neighbor)) { + scf_logd("neighbor: %p of node: %p not in graph\n", neighbor, node); continue; - - scf_graph_node_t* node1 = NULL; - int j; - for (j = i + 1; j < graph->nodes->size; j++) { - node1 = graph->nodes->data[j]; - - if (!scf_vector_find(node0->neighbors, node1)) { - assert(!scf_vector_find(node1->neighbors, node0)); - break; - } - - node1 = NULL; - } - - if (node1) { - *pp0 = node0; - *pp1 = node1; - return 0; - } - } - return -1; -} - -static scf_graph_node_t* _max_neighbors(scf_graph_t* graph) -{ - scf_graph_node_t* node_max = NULL; - int max = 0; - int i; - for (i = 0; i < graph->nodes->size; i++) { - scf_graph_node_t* node = graph->nodes->data[i]; - - if (!node_max || max < node->neighbors->size) { - node_max = node; - max = node->neighbors->size; - } - } - - scf_logi("max_neighbors: %d\n", max); - - return node_max; -} - -int scf_graph_kcolor(scf_graph_t* graph, scf_vector_t* colors) -{ - if (!graph || !colors || 0 == colors->size) - return -EINVAL; - - int k = colors->size; - int ret = -1; - - scf_vector_t* colors2 = NULL; - scf_vector_t* deleted_nodes = scf_vector_alloc(); - if (!deleted_nodes) - return -ENOMEM; - - scf_logd("graph->nodes->size: %d, k: %d\n", graph->nodes->size, k); - - ret = _kcolor_delete(graph, k, deleted_nodes); - if (ret < 0) - goto error; - - if (0 == graph->nodes->size) { - ret = _kcolor_fill(graph, colors, deleted_nodes); - if (ret < 0) - goto error; - - scf_vector_free(deleted_nodes); - deleted_nodes = NULL; - - scf_logd("graph->nodes->size: %d\n", graph->nodes->size); - return 0; - } - - assert(graph->nodes->size > 0); - assert(graph->nodes->size >= k); - - scf_graph_node_t* node0 = NULL; - scf_graph_node_t* node1 = NULL; - - if (0 == _kcolor_find_not_neighbor(graph, k, &node0, &node1)) { - assert(node0); - assert(node1); - - node0->color = (intptr_t)(colors->data[0]); - node1->color = node0->color; - - ret = scf_graph_delete_node(graph, node0); - if (ret < 0) - goto error; - - ret = scf_graph_delete_node(graph, node1); - if (ret < 0) - goto error; - - assert(!colors2); - colors2 = scf_vector_clone(colors); - if (!colors2) { - ret = -ENOMEM; - goto error; } - ret = scf_vector_del(colors2, (void*)node0->color); - if (ret < 0) - goto error; - - ret = scf_graph_kcolor(graph, colors2); - if (ret < 0) - goto error; - - ret = scf_graph_add_node(graph, node0); - if (ret < 0) - goto error; - - ret = scf_graph_add_node(graph, node1); - if (ret < 0) - goto error; - - scf_vector_free(colors2); - colors2 = NULL; - } else { - scf_graph_node_t* node_max = _max_neighbors(graph); - assert(node_max); - - ret = scf_graph_delete_node(graph, node_max); - if (ret < 0) - goto error; - node_max->color = -1; - - ret = scf_graph_kcolor(graph, colors); - if (ret < 0) - goto error; + if (scf_vector_find(neighbor->neighbors, node)) + continue; - ret = scf_graph_add_node(graph, node_max); + int ret = scf_vector_add(neighbor->neighbors, node); if (ret < 0) - goto error; + return ret; } - ret = _kcolor_fill(graph, colors, deleted_nodes); - if (ret < 0) - goto error; - - scf_vector_free(deleted_nodes); - deleted_nodes = NULL; - - scf_logd("graph->nodes->size: %d\n", graph->nodes->size); - return 0; - -error: - if (colors2) - scf_vector_free(colors2); - - scf_vector_free(deleted_nodes); - return ret; + return scf_vector_add(graph->nodes, node); } - diff --git a/util/scf_graph.h b/util/scf_graph.h index 6137d05..3a09dfd 100644 --- a/util/scf_graph.h +++ b/util/scf_graph.h @@ -4,28 +4,28 @@ #include"scf_vector.h" typedef struct { - scf_vector_t* neighbors; + scf_vector_t* neighbors; intptr_t color; - void* data; + void* data; } scf_graph_node_t; typedef struct { - scf_vector_t* nodes; + scf_vector_t* nodes; } scf_graph_t; -scf_graph_t* scf_graph_alloc(); -void scf_graph_free(scf_graph_t* graph); +scf_graph_t* scf_graph_alloc(); +void scf_graph_free(scf_graph_t* graph); -scf_graph_node_t* scf_graph_node_alloc(); -void scf_graph_node_free(scf_graph_node_t* node); -void scf_graph_node_print(scf_graph_node_t* node); +scf_graph_node_t* scf_graph_node_alloc(); +void scf_graph_node_free (scf_graph_node_t* node); +void scf_graph_node_print(scf_graph_node_t* node); int scf_graph_make_edge(scf_graph_node_t* node1, scf_graph_node_t* node2); -int scf_graph_delete_node(scf_graph_t* graph, scf_graph_node_t* node); +int scf_graph_del_node(scf_graph_t* graph, scf_graph_node_t* node); int scf_graph_add_node(scf_graph_t* graph, scf_graph_node_t* node); // color = 0, not colored @@ -34,4 +34,3 @@ int scf_graph_add_node(scf_graph_t* graph, scf_graph_node_t* nod int scf_graph_kcolor(scf_graph_t* graph, scf_vector_t* colors); #endif - -- 2.25.1