From e8d877cdf28f72f7c44232db18c97ce79bcc53ae Mon Sep 17 00:00:00 2001 From: "yu.dongliang" <18588496441@163.com> Date: Tue, 8 Oct 2024 21:26:36 +0800 Subject: [PATCH] optimize common sub-expr after call() analysis --- core/scf_basic_block.c | 30 +++++++ core/scf_basic_block.h | 1 + core/scf_dag.h | 15 ++-- core/scf_operator_dag.c | 28 +++++- core/scf_optimizer.c | 4 + core/scf_optimizer_basic_block.c | 148 ++++++++++++++++++------------- core/scf_optimizer_common_expr.c | 139 +++++++++++++++++++++++++++++ core/scf_variable.c | 39 ++++---- elf/scf_elf_link.c | 2 +- examples/common_expr.c | 17 ++++ native/x64/scf_x64_reg.c | 30 ++++--- parse/Makefile | 1 + util/scf_list.h | 11 +++ 13 files changed, 361 insertions(+), 104 deletions(-) create mode 100644 core/scf_optimizer_common_expr.c create mode 100644 examples/common_expr.c diff --git a/core/scf_basic_block.c b/core/scf_basic_block.c index b207148..fddd9f5 100644 --- a/core/scf_basic_block.c +++ b/core/scf_basic_block.c @@ -617,6 +617,36 @@ int scf_basic_block_dag2(scf_basic_block_t* bb, scf_list_t* dag_list_head) return 0; } +int scf_basic_block_vars(scf_basic_block_t* bb, scf_list_t* bb_list_head) +{ + scf_list_t* l; + scf_3ac_code_t* c; + + int ret = _bb_vars(bb); + if (ret < 0) { + scf_loge("\n"); + return ret; + } + + for (l = scf_list_head(&bb->code_list_head); l != scf_list_sentinel(&bb->code_list_head); l = scf_list_next(l)) { + c = scf_list_data(l, scf_3ac_code_t, list); + + if (c->active_vars) + scf_vector_clear(c->active_vars, (void (*)(void*))scf_dn_status_free); + else { + c->active_vars = scf_vector_alloc(); + if (!c->active_vars) + return -ENOMEM; + } + + ret = _copy_to_active_vars(c->active_vars, bb->var_dag_nodes); + if (ret < 0) + return ret; + } + + return scf_basic_block_inited_vars(bb, bb_list_head); +} + int scf_basic_block_dag(scf_basic_block_t* bb, scf_list_t* bb_list_head, scf_list_t* dag_list_head) { scf_list_t* l; diff --git a/core/scf_basic_block.h b/core/scf_basic_block.h index 8ae5247..356d9b7 100644 --- a/core/scf_basic_block.h +++ b/core/scf_basic_block.h @@ -122,6 +122,7 @@ void scf_bb_loop_print (scf_bb_group_t* loop); void scf_basic_block_print(scf_basic_block_t* bb, scf_list_t* sentinel); void scf_basic_block_print_list(scf_list_t* h); +int scf_basic_block_vars(scf_basic_block_t* bb, scf_list_t* bb_list_head); int scf_basic_block_dag (scf_basic_block_t* bb, scf_list_t* bb_list_head, scf_list_t* dag_list_head); int scf_basic_block_dag2(scf_basic_block_t* bb, scf_list_t* dag_list_head); diff --git a/core/scf_dag.h b/core/scf_dag.h index c2674a8..12fa974 100644 --- a/core/scf_dag.h +++ b/core/scf_dag.h @@ -19,17 +19,20 @@ enum scf_dn_alias_type SCF_DN_ALIAS_ALLOC, }; -struct scf_dag_node_s { - scf_list_t list; // for dag node list in scope +struct scf_dag_node_s +{ + scf_list_t list; // for dag node list in scope - int type; // node type + int type; // node type - scf_variable_t* var; + scf_variable_t* var; scf_dag_node_t* old; scf_node_t* node; - scf_vector_t* parents; - scf_vector_t* childs; + scf_vector_t* parents; + scf_vector_t* childs; + + scf_dag_node_t* direct; void* rabi; void* rabi2; diff --git a/core/scf_operator_dag.c b/core/scf_operator_dag.c index 68bb4bc..fbe81cc 100644 --- a/core/scf_operator_dag.c +++ b/core/scf_operator_dag.c @@ -260,6 +260,33 @@ SCF_DAG_BINARY(mul, MUL) SCF_DAG_BINARY(div, DIV) SCF_DAG_BINARY(mod, MOD) +static int _scf_dag_op_assign(scf_list_t* h, scf_dag_node_t* parent, scf_dag_node_t** nodes, int nb_nodes) +{ + assert(2 == nb_nodes); + + scf_3ac_operand_t* dst; + scf_3ac_code_t* c; + scf_list_t* l; + + if (!parent->direct) + return _scf_3ac_code_2(h, SCF_OP_ASSIGN, nodes[0], nodes[1]); + + if (!nodes[1]->direct) { + nodes [1]->direct = nodes[0]; + + l = scf_list_tail(h); + c = scf_list_data(l, scf_3ac_code_t, list); + + assert(1 == c->dsts->size); + dst = c->dsts->data[0]; + + dst->node = nodes[0]->node; + dst->dag_node = nodes[0]; + return 0; + } + + return _scf_3ac_code_2(h, SCF_OP_ASSIGN, nodes[0], nodes[1]->direct); +} #define SCF_DAG_BINARY_ASSIGN(name, op) \ static int _scf_dag_op_##name(scf_list_t* h, scf_dag_node_t* parent, scf_dag_node_t** nodes, int nb_nodes) \ @@ -267,7 +294,6 @@ static int _scf_dag_op_##name(scf_list_t* h, scf_dag_node_t* parent, scf_dag_nod assert(2 == nb_nodes); \ return _scf_3ac_code_2(h, SCF_OP_##op, nodes[0], nodes[1]); \ } -SCF_DAG_BINARY_ASSIGN(assign, ASSIGN) SCF_DAG_BINARY_ASSIGN(add_assign, ADD_ASSIGN) SCF_DAG_BINARY_ASSIGN(sub_assign, SUB_ASSIGN) diff --git a/core/scf_optimizer.c b/core/scf_optimizer.c index 45e04e8..d0ee2ce 100644 --- a/core/scf_optimizer.c +++ b/core/scf_optimizer.c @@ -5,6 +5,8 @@ extern scf_optimizer_t scf_optimizer_inline; extern scf_optimizer_t scf_optimizer_dag; extern scf_optimizer_t scf_optimizer_call; +extern scf_optimizer_t scf_optimizer_common_expr; + extern scf_optimizer_t scf_optimizer_pointer_alias; extern scf_optimizer_t scf_optimizer_active_vars; @@ -31,6 +33,8 @@ static scf_optimizer_t* scf_optimizers[] = &scf_optimizer_dag, &scf_optimizer_call, + &scf_optimizer_common_expr, + &scf_optimizer_pointer_alias, &scf_optimizer_active_vars, diff --git a/core/scf_optimizer_basic_block.c b/core/scf_optimizer_basic_block.c index 3e36fb7..a3ceb87 100644 --- a/core/scf_optimizer_basic_block.c +++ b/core/scf_optimizer_basic_block.c @@ -1,11 +1,64 @@ #include"scf_optimizer.h" +void __use_function_dag(scf_list_t* h, scf_basic_block_t* bb); + +static void __optimize_assign(scf_dag_node_t* assign) +{ + scf_dag_node_t* parent; + scf_dag_node_t* dst; + scf_dag_node_t* src; + int i; + + assert(2 == assign->childs->size); + + dst = assign->childs->data[0]; + src = assign->childs->data[1]; + + if (SCF_OP_ADD == src->type + || SCF_OP_SUB == src->type + || SCF_OP_MUL == src->type + || SCF_OP_DIV == src->type + || SCF_OP_MOD == src->type + || SCF_OP_ADDRESS_OF == src->type) { + + for (i = src->parents->size - 1; i >= 0; i--) { + parent = src->parents->data[i]; + + if (parent == assign) + break; + } + + for (--i; i >= 0; i--) { + parent = src->parents->data[i]; + + if (SCF_OP_ASSIGN == parent->type) + continue; + + if (SCF_OP_ADD == parent->type + || SCF_OP_SUB == parent->type + || SCF_OP_MUL == parent->type + || SCF_OP_DIV == parent->type + || SCF_OP_MOD == parent->type + || SCF_OP_ADDRESS_OF == parent->type) { + + if (dst != parent->childs->data[0] && dst != parent->childs->data[1]) + continue; + } + break; + } + + if (i < 0) + assign->direct = dst; + } +} + static int _bb_dag_update(scf_basic_block_t* bb) { scf_dag_node_t* dn; scf_dag_node_t* dn_bb; scf_dag_node_t* dn_bb2; scf_dag_node_t* dn_func; + scf_dag_node_t* parent; scf_list_t* l; int i; @@ -58,8 +111,12 @@ static int _bb_dag_update(scf_basic_block_t* bb) } else { assert(dn_bb->parents && dn_bb->parents->size > 0); - if (dn != dn_bb->parents->data[dn_bb->parents->size - 1]) + if (dn != dn_bb->parents->data[dn_bb->parents->size - 1]) { + + if (SCF_OP_ASSIGN == dn->type) + __optimize_assign(dn); continue; + } dn_func = dn_bb->old; } @@ -70,8 +127,12 @@ static int _bb_dag_update(scf_basic_block_t* bb) } if (scf_vector_find(bb->dn_saves, dn_func) - || scf_vector_find(bb->dn_resaves, dn_func)) + || scf_vector_find(bb->dn_resaves, dn_func)) { + + if (SCF_OP_ASSIGN == dn->type) + __optimize_assign(dn); continue; + } for (i = 0; i < dn->childs->size; ) { dn_bb = dn->childs->data[i]; @@ -105,8 +166,8 @@ static int _bb_dag_update(scf_basic_block_t* bb) return -1; } - if (scf_vector_find(bb->dn_saves, dn_func) - || scf_vector_find(bb->dn_resaves, dn_func)) + if (scf_vector_find(bb->dn_saves, dn_func) + || scf_vector_find(bb->dn_resaves, dn_func)) continue; for (i = 0; i < dn->childs->size; i++) { @@ -137,92 +198,57 @@ static int _bb_dag_update(scf_basic_block_t* bb) static int __optimize_basic_block(scf_basic_block_t* bb, scf_function_t* f) { - scf_3ac_operand_t* src; - scf_3ac_operand_t* dst; - scf_dag_node_t* dn; - scf_3ac_code_t* c; - scf_vector_t* roots; - scf_list_t* l; - scf_list_t h; + scf_dag_node_t* dn; + scf_vector_t* roots; + scf_list_t h; int ret; int i; scf_list_init(&h); + roots = scf_vector_alloc(); + if (!roots) + return -ENOMEM; + ret = scf_basic_block_dag2(bb, &bb->dag_list_head); if (ret < 0) - return ret; + goto error; ret = _bb_dag_update(bb); - if (ret < 0) { - scf_loge("\n"); - return ret; - } - - roots = scf_vector_alloc(); - if (!roots) - return -ENOMEM; + if (ret < 0) + goto error; ret = scf_dag_find_roots(&bb->dag_list_head, roots); - if (ret < 0) { - scf_vector_free(roots); - return ret; - } + if (ret < 0) + goto error; + scf_logd("bb: %p, roots->size: %d\n", bb, roots->size); for (i = 0; i < roots->size; i++) { dn = roots->data[i]; - if (!dn) - continue; - ret = scf_dag_expr_calculate(&h, dn); if (ret < 0) { scf_loge("\n"); - return ret; + scf_list_clear(&h, scf_3ac_code_t, list, scf_3ac_code_free); + goto error; } } scf_list_clear(&bb->code_list_head, scf_3ac_code_t, list, scf_3ac_code_free); - for (l = scf_list_head(&h); l != scf_list_sentinel(&h); ) { - c = scf_list_data(l, scf_3ac_code_t, list); + scf_list_mov2(&bb->code_list_head, &h); - if (c->dsts) { - dst = c->dsts->data[0]; - dn = dst->dag_node->old; - - dst->dag_node = dn; - } - - if (c->srcs) { - for (i = 0; i < c->srcs->size; i++) { - src = c->srcs->data[i]; - - dn = src->dag_node->old; - - src->dag_node = dn; - } - } - - l = scf_list_next(l); - - scf_list_del(&c->list); - scf_list_add_tail(&bb->code_list_head, &c->list); - - c->basic_block = bb; - } - - ret = scf_basic_block_active_vars(bb); - if (ret < 0) { - scf_loge("\n"); - return ret; - } +error: + __use_function_dag(&bb->code_list_head, bb); scf_dag_node_free_list(&bb->dag_list_head); scf_vector_free(roots); - return 0; + + if (ret >= 0) + ret = scf_basic_block_active_vars(bb); + return ret; } static int _optimize_basic_block(scf_ast_t* ast, scf_function_t* f, scf_vector_t* functions) diff --git a/core/scf_optimizer_common_expr.c b/core/scf_optimizer_common_expr.c new file mode 100644 index 0000000..5eaaa3c --- /dev/null +++ b/core/scf_optimizer_common_expr.c @@ -0,0 +1,139 @@ +#include"scf_optimizer.h" + +void __use_function_dag(scf_list_t* h, scf_basic_block_t* bb) +{ + scf_3ac_operand_t* src; + scf_3ac_operand_t* dst; + scf_3ac_code_t* c; + scf_dag_node_t* dn; + scf_list_t* l; + + int i; + + for (l = scf_list_head(h); l != scf_list_sentinel(h); l = scf_list_next(l)) { + c = scf_list_data(l, scf_3ac_code_t, list); + + if (c->dsts) { + dst = c->dsts->data[0]; + dn = dst->dag_node->old; + + dst->node = dn->node; + dst->dag_node = dn; + } + + if (c->srcs) { + for (i = 0; i < c->srcs->size; i++) { + src = c->srcs->data[i]; + + dn = src->dag_node->old; + + src->node = dn->node; + src->dag_node = dn; + } + } + + c->basic_block = bb; + } +} + +int __optimize_common_expr(scf_basic_block_t* bb, scf_function_t* f) +{ + scf_dag_node_t* dn; + scf_vector_t* roots; + scf_list_t* l; + scf_list_t h; + + int ret; + int i; + + scf_list_init(&h); + + roots = scf_vector_alloc(); + if (!roots) + return -ENOMEM; + + ret = scf_basic_block_dag2(bb, &bb->dag_list_head); + if (ret < 0) + goto error; + + ret = scf_dag_find_roots(&bb->dag_list_head, roots); + if (ret < 0) + goto error; + + for (i = 0; i < roots->size; i++) { + dn = roots->data[i]; + + ret = scf_dag_expr_calculate(&h, dn); + if (ret < 0) { + scf_loge("\n"); + scf_list_clear(&h, scf_3ac_code_t, list, scf_3ac_code_free); + goto error; + } + } + + scf_list_clear(&bb->code_list_head, scf_3ac_code_t, list, scf_3ac_code_free); + + scf_list_mov2(&bb->code_list_head, &h); + + ret = 0; +error: + __use_function_dag(&bb->code_list_head, bb); + + scf_dag_node_free_list(&bb->dag_list_head); + scf_vector_free(roots); + return ret; +} + +static int _optimize_common_expr(scf_ast_t* ast, scf_function_t* f, scf_vector_t* functions) +{ + if (!f) + return -EINVAL; + + scf_basic_block_t* bb; + scf_list_t* l; + scf_list_t* bb_list_head = &f->basic_block_list_head; + + if (scf_list_empty(bb_list_head)) + return 0; + + scf_logd("------- %s() ------\n", f->node.w->text->data); + + for (l = scf_list_head(bb_list_head); l != scf_list_sentinel(bb_list_head); l = scf_list_next(l)) { + + bb = scf_list_data(l, scf_basic_block_t, list); + + if (bb->jmp_flag + || bb->end_flag + || bb->call_flag + || bb->varg_flag) { + scf_logd("bb: %p, jmp:%d,ret:%d, end: %d, call:%d, varg:%d, dereference_flag: %d\n", + bb, bb->jmp_flag, bb->ret_flag, bb->end_flag, bb->call_flag, bb->dereference_flag, + bb->varg_flag); + continue; + } + + int ret = __optimize_common_expr(bb, f); + if (ret < 0) { + scf_loge("\n"); + return ret; + } + + ret = scf_basic_block_vars(bb, bb_list_head); + if (ret < 0) + return ret; + } + + scf_loge("-------------------------\n"); + scf_basic_block_print_list(bb_list_head); + scf_loge("-------------------------\n"); + return 0; +} + +scf_optimizer_t scf_optimizer_common_expr = +{ + .name = "common_expr", + + .optimize = _optimize_common_expr, + + .flags = SCF_OPTIMIZER_LOCAL, +}; diff --git a/core/scf_variable.c b/core/scf_variable.c index 9ef8d2c..2738784 100644 --- a/core/scf_variable.c +++ b/core/scf_variable.c @@ -242,35 +242,32 @@ scf_variable_t* scf_variable_clone(scf_variable_t* v) return v2; } -scf_variable_t* scf_variable_ref(scf_variable_t* var) +scf_variable_t* scf_variable_ref(scf_variable_t* v) { - var->refs++; - return var; + v->refs++; + return v; } -void scf_variable_free(scf_variable_t* var) +void scf_variable_free(scf_variable_t* v) { - assert(var); + if (v) { + if (--v->refs > 0) + return; - var->refs--; - if (var->refs > 0) { - return; - } else if (var->refs < 0) { - assert(0); // BUGS - } + assert(0 == v->refs); - if (var->w) { - scf_lex_word_free(var->w); - var->w = NULL; - } + if (v->w) { + scf_lex_word_free(v->w); + v->w = NULL; + } - if (var->signature) { - scf_string_free(var->signature); - var->signature = NULL; - } + if (v->signature) { + scf_string_free(v->signature); + v->signature = NULL; + } - free(var); - var = NULL; + free(v); + } } void scf_variable_add_array_dimention(scf_variable_t* var, int dimention_size) diff --git a/elf/scf_elf_link.c b/elf/scf_elf_link.c index 311982f..095fc99 100644 --- a/elf/scf_elf_link.c +++ b/elf/scf_elf_link.c @@ -835,7 +835,7 @@ static int _find_so_sym(scf_elf_file_t** pso, scf_vector_t* dlls, scf_elf_sym_t* } if (j == dlls->size) { - scf_loge("\n"); + scf_loge("linker don't find symbel '%s'\n", sym->name); return -1; } diff --git a/examples/common_expr.c b/examples/common_expr.c new file mode 100644 index 0000000..fd2df05 --- /dev/null +++ b/examples/common_expr.c @@ -0,0 +1,17 @@ +int printf(const char* fmt, ...); + +int main() +{ + int a[4] = {1, 2, 3, 4}; + + int* p = a; + + p += 2; + + int b = *p; + int c = *p; + int d = *p; + + printf("b: %d, c: %d, d: %d\n", b, c, d); + return 0; +} diff --git a/native/x64/scf_x64_reg.c b/native/x64/scf_x64_reg.c index 9cde470..a82d242 100644 --- a/native/x64/scf_x64_reg.c +++ b/native/x64/scf_x64_reg.c @@ -633,7 +633,7 @@ int x64_overflow_reg2(scf_register_t* r, scf_dag_node_t* dn, scf_3ac_code_t* c, continue; for (j = 0; j < r2->dag_nodes->size; ) { - dn2 = r2->dag_nodes->data[j]; + dn2 = r2->dag_nodes->data[j]; if (dn2 == dn) { j++; @@ -652,7 +652,9 @@ int x64_overflow_reg2(scf_register_t* r, scf_dag_node_t* dn, scf_3ac_code_t* c, static int _x64_overflow_reg3(scf_register_t* r, scf_dag_node_t* dn, scf_3ac_code_t* c, scf_function_t* f) { - scf_register_t* r2; + scf_variable_t* v; + scf_variable_t* v2; + scf_register_t* r2; scf_dn_status_t* ds2; scf_dag_node_t* dn2; @@ -678,27 +680,27 @@ static int _x64_overflow_reg3(scf_register_t* r, scf_dag_node_t* dn, scf_3ac_cod } ds2 = scf_vector_find_cmp(c->active_vars, dn2, scf_dn_status_cmp); - if (!ds2) { - j++; - continue; - } - if (!ds2->active) { + if (!ds2 || !ds2->active) { + assert(0 == scf_vector_del(r2->dag_nodes, dn2)); +#if 1 + v2 = dn2->var; + if (v2->w) + scf_logw("drop inactive v2_%d_%d/%s, bp_offset: %d\n", v2->w->line, v2->w->pos, v2->w->text->data, v2->bp_offset); + else + scf_logw("drop inactive v2_%#lx, bp_offset: %d\n", 0xffff & (uintptr_t)v2, v2->bp_offset); +#endif + dn2->loaded = 0; + dn2->color = -1; j++; continue; } #if 0 - scf_variable_t* v = dn->var; - scf_variable_t* v2 = dn2->var; + v = dn->var; if (v->w) scf_logi("v_%d_%d/%s, bp_offset: %d\n", v->w->line, v->w->pos, v->w->text->data, v->bp_offset); else scf_logi("v_%#lx, bp_offset: %d\n", 0xffff & (uintptr_t)v, v->bp_offset); - - if (v2->w) - scf_logi("v2_%d_%d/%s, bp_offset: %d\n", v2->w->line, v2->w->pos, v2->w->text->data, v2->bp_offset); - else - scf_logi("v2_%#lx, bp_offset: %d\n", 0xffff & (uintptr_t)v2, v2->bp_offset); #endif int ret = x64_save_var(dn2, c, f); if (ret < 0) diff --git a/parse/Makefile b/parse/Makefile index e3ca067..5750f47 100644 --- a/parse/Makefile +++ b/parse/Makefile @@ -103,6 +103,7 @@ CFILES += ../core/scf_optimizer.c CFILES += ../core/scf_optimizer_dag.c CFILES += ../core/scf_optimizer_inline.c CFILES += ../core/scf_optimizer_call.c +CFILES += ../core/scf_optimizer_common_expr.c CFILES += ../core/scf_optimizer_pointer_alias.c CFILES += ../core/scf_optimizer_active_vars.c CFILES += ../core/scf_optimizer_pointer_aliases.c diff --git a/util/scf_list.h b/util/scf_list.h index b5fac89..e08644f 100644 --- a/util/scf_list.h +++ b/util/scf_list.h @@ -42,6 +42,17 @@ static inline void scf_list_add_front(scf_list_t* h, scf_list_t* n) h->next = n; } +static inline void scf_list_mov2(scf_list_t* h0, scf_list_t* h1) +{ + if (h1->next == h1) + return; + + h0->prev->next = h1->next; + h1->next->prev = h0->prev; + h1->prev->next = h0; + h0->prev = h1->prev; +} + #define SCF_LIST_INIT(h) {&h, &h} #define scf_list_data(l, type, member) ((type*)((char*)l - offsetof(type, member))) -- 2.25.1