From 041ce32dfd069b9befa4f51a7f57fbb5987621ce Mon Sep 17 00:00:00 2001 From: "yu.dongliang" <18588496441@163.com> Date: Thu, 9 Jul 2026 20:08:43 +0800 Subject: [PATCH] optimize to decrease the binary X64 instuctions of '../examples/strcpy.c', and fix parse failed when init array. --- core/scf_3ac.c | 78 +++++++++--- core/scf_operator_dag.c | 71 ++++++++++- core/scf_operator_handler_3ac.c | 44 +++++-- core/scf_optimizer.c | 4 +- core/scf_optimizer_pointer_alias.c | 74 ++++++----- core/scf_pointer_alias.c | 24 ++-- examples/inc_post.c | 9 ++ examples/strcpy.c | 20 +++ native/scf_instruction.h | 9 ++ native/x64/scf_x64_inst.c | 21 +-- native/x64/scf_x64_peephole.c | 198 ++++++++++++++++++++--------- native/x64/scf_x64_reg_util.h | 16 +++ parse/scf_dfa_init_data.c | 3 + 13 files changed, 421 insertions(+), 150 deletions(-) create mode 100644 examples/inc_post.c create mode 100644 examples/strcpy.c diff --git a/core/scf_3ac.c b/core/scf_3ac.c index 07401bb..1331e92 100644 --- a/core/scf_3ac.c +++ b/core/scf_3ac.c @@ -624,35 +624,39 @@ int scf_3ac_code_to_dag(scf_3ac_code_t* c, scf_list_t* dag) if (SCF_OP_ASSIGN == c->op->type && src->dag_node == dst->dag_node) return 0; - scf_dag_node_t* dn_src; - scf_dag_node_t* dn_parent; - scf_dag_node_t* dn_assign; - scf_variable_t* v_assign = NULL; + scf_dag_node_t* assign; + scf_variable_t* v = NULL; if (dst->node->parent) - v_assign = _scf_operand_get(dst->node->parent); + v = _scf_operand_get(dst->node->parent); - dn_assign = scf_dag_node_alloc(c->op->type, v_assign, NULL); + assign = scf_dag_node_alloc(c->op->type, v, NULL); - scf_list_add_tail(dag, &dn_assign->list); + scf_list_add_tail(dag, &assign->list); - dn_src = src->dag_node; + scf_dag_node_t* parent; + scf_dag_node_t* old; + scf_dag_node_t* cur = src->dag_node; - if (dn_src->parents && dn_src->parents->size > 0 && !scf_variable_may_malloced(dn_src->var)) { - dn_parent = dn_src->parents->data[dn_src->parents->size - 1]; + if (cur->parents && cur->parents->size > 0 && !scf_variable_may_malloced(cur->var)) { + parent = cur->parents->data[cur->parents->size - 1]; - if (SCF_OP_ASSIGN == dn_parent->type) { + if (SCF_OP_ASSIGN == parent->type) { + assert(2 == parent->childs->size); + old = parent->childs->data[1]; - assert(2 == dn_parent->childs->size); - dn_src = dn_parent->childs->data[1]; + if (old->parents + && old->parents->size > 0 + && old->parents->data[old->parents->size - 1] == parent) + cur = old; } } - ret = scf_dag_node_add_child(dn_assign, dst->dag_node); + ret = scf_dag_node_add_child(assign, dst->dag_node); if (ret < 0) return ret; - return scf_dag_node_add_child(dn_assign, dn_src); + return scf_dag_node_add_child(assign, cur); } else if (scf_type_is_assign_array_index(c->op->type) || scf_type_is_assign_dereference(c->op->type) @@ -1250,8 +1254,41 @@ void scf_3ac_list_print(scf_list_t* h) } } +static void _3ac_filter_unary_post(scf_list_t* h, scf_3ac_code_t* c, scf_node_t* obj) +{ + scf_3ac_operand_t* src; + scf_3ac_code_t* c2; + scf_3ac_code_t* post; + scf_list_t* l; + + assert(1 == obj->nb_nodes); + do { + obj = obj->nodes[0]; + + } while (SCF_OP_EXPR == obj->type); + + if (!scf_type_is_var(obj->type)) + return; + + for (l = scf_list_prev(&c->list); l != scf_list_sentinel(h); l = scf_list_prev(l)) { + c2 = scf_list_data(l, scf_3ac_code_t, list); + + if (SCF_OP_3AC_INC != c2->op->type && SCF_OP_3AC_DEC != c2->op->type) + continue; + + src = c2->srcs->data[0]; + + if (src->node == obj) { + scf_list_del(&c->list); + scf_list_add_tail(&c2->list, &c->list); + break; + } + } +} + static int _3ac_find_basic_block_start(scf_list_t* h) { + scf_3ac_operand_t* src; scf_3ac_operand_t* dst; scf_3ac_code_t* c; scf_3ac_code_t* c2; @@ -1261,14 +1298,23 @@ static int _3ac_find_basic_block_start(scf_list_t* h) int start = 0; - for (l = scf_list_head(h); l != scf_list_sentinel(h); l = scf_list_next(l)) { + for (l = scf_list_head(h); l != scf_list_sentinel(h); ) { c = scf_list_data(l, scf_3ac_code_t, list); + l = scf_list_next(l); if (!start) { c->basic_block_start = 1; start = 1; } + + if (SCF_OP_3AC_ASSIGN_DEREFERENCE == c->op->type + || SCF_OP_DEREFERENCE == c->op->type) { + src = c->srcs->data[0]; + + if (SCF_OP_INC_POST == src->node->type || SCF_OP_DEC_POST == src->node->type) + _3ac_filter_unary_post(h, c, src->node); + } #if 1 if (SCF_OP_ASSIGN == c->op->type) { dst = c->dsts->data[0]; diff --git a/core/scf_operator_dag.c b/core/scf_operator_dag.c index a3142e8..0e5f0c8 100644 --- a/core/scf_operator_dag.c +++ b/core/scf_operator_dag.c @@ -175,6 +175,12 @@ static int _scf_dag_op_pointer(scf_list_t* h, scf_dag_node_t* parent, scf_dag_no return _scf_3ac_code_N(h, SCF_OP_POINTER, parent, nodes, nb_nodes); } +static int _scf_dag_op_va_arg(scf_list_t* h, scf_dag_node_t* parent, scf_dag_node_t** nodes, int nb_nodes) +{ + assert(3 == nb_nodes); + return _scf_3ac_code_N(h, SCF_OP_VA_ARG, parent, nodes, nb_nodes); +} + static int _scf_dag_op_neg(scf_list_t* h, scf_dag_node_t* parent, scf_dag_node_t** nodes, int nb_nodes) { assert(1 == nb_nodes); @@ -209,13 +215,70 @@ static int _scf_dag_op_address_of(scf_list_t* h, scf_dag_node_t* parent, scf_dag return -1; } +static scf_dag_node_t* _scf_dag_inc_dec(scf_dag_node_t* parent, const scf_dag_node_t* node) +{ + scf_dag_node_t* dn; + int i; + + switch (node->type) + { + case SCF_OP_INC: + case SCF_OP_INC_POST: + case SCF_OP_DEC_POST: + case SCF_OP_DEC: + + for (i = node->parents->size - 1; i >= 0; i--) { + dn = node->parents->data[i]; + + if (dn == parent) + break; + } + + for (--i; i >= 0; i--) { + dn = node->parents->data[i]; + + if (SCF_OP_ASSIGN != dn->type) + continue; + + assert(2 == dn->childs->size); + + if (node == dn->childs->data[0]) + return dn->childs->data[1]; + } + break; + }; + + return NULL; +} + static int _scf_dag_op_dereference(scf_list_t* h, scf_dag_node_t* parent, scf_dag_node_t** nodes, int nb_nodes) { assert(1 == nb_nodes); + scf_dag_node_t* src = _scf_dag_inc_dec(parent, nodes[0]); + if (src) + return _scf_3ac_code_2(h, SCF_OP_DEREFERENCE, parent, src); + return _scf_3ac_code_2(h, SCF_OP_DEREFERENCE, parent, nodes[0]); } +static int _scf_dag_op_assign_dereference(scf_list_t* h, scf_dag_node_t* parent, scf_dag_node_t** nodes, int nb_nodes) +{ + scf_dag_node_t* src = _scf_dag_inc_dec(parent, nodes[0]); + if (src) { + scf_dag_node_t* tmp = nodes[0]; + + nodes[0] = src; + + int ret = _scf_3ac_code_N(h, SCF_OP_3AC_ASSIGN_DEREFERENCE, NULL, nodes, nb_nodes); + + nodes[0] = tmp; + return ret; + } + + return _scf_3ac_code_N(h, SCF_OP_3AC_ASSIGN_DEREFERENCE, NULL, nodes, nb_nodes); +} + static int _scf_dag_op_type_cast(scf_list_t* h, scf_dag_node_t* parent, scf_dag_node_t** nodes, int nb_nodes) { assert(1 == nb_nodes); @@ -307,13 +370,6 @@ SCF_DAG_BINARY_ASSIGN(shr_assign, SHR_ASSIGN) SCF_DAG_BINARY_ASSIGN(and_assign, AND_ASSIGN) SCF_DAG_BINARY_ASSIGN(or_assign, OR_ASSIGN) -#define SCF_DAG_ASSIGN_DEREFERENCE(name, op) \ -static int _scf_dag_op_##name##_dereference(scf_list_t* h, scf_dag_node_t* parent, scf_dag_node_t** nodes, int nb_nodes) \ -{ \ - return _scf_3ac_code_N(h, SCF_OP_3AC_##op##_DEREFERENCE, NULL, nodes, nb_nodes); \ -} -SCF_DAG_ASSIGN_DEREFERENCE(assign, ASSIGN); - #define SCF_DAG_ASSIGN_ARRAY_INDEX(name, op) \ static int _scf_dag_op_##name##_array_index(scf_list_t* h, scf_dag_node_t* parent, scf_dag_node_t** nodes, int nb_nodes) \ { \ @@ -383,6 +439,7 @@ scf_dag_operator_t dag_operators[] = { {SCF_OP_ARRAY_INDEX, SCF_OP_ASSOCIATIVITY_LEFT, _scf_dag_op_array_index}, {SCF_OP_POINTER, SCF_OP_ASSOCIATIVITY_LEFT, _scf_dag_op_pointer}, + {SCF_OP_VA_ARG, SCF_OP_ASSOCIATIVITY_LEFT, _scf_dag_op_va_arg}, {SCF_OP_BIT_NOT, SCF_OP_ASSOCIATIVITY_LEFT, _scf_dag_op_bit_not}, {SCF_OP_LOGIC_NOT, SCF_OP_ASSOCIATIVITY_RIGHT, _scf_dag_op_logic_not}, diff --git a/core/scf_operator_handler_3ac.c b/core/scf_operator_handler_3ac.c index ac81c08..a2b048e 100644 --- a/core/scf_operator_handler_3ac.c +++ b/core/scf_operator_handler_3ac.c @@ -1055,6 +1055,26 @@ static int _scf_op_end_loop(scf_list_t* start_prev, scf_list_t* continue_prev, s return 0; } +static void __scf_loop_entry_clear(scf_list_t* start_prev, scf_3ac_code_t* jmp_end) +{ + scf_3ac_code_t* c; + scf_list_t* l; + + for (l = scf_list_next(start_prev); l != &jmp_end->list; ) { + + c = scf_list_data(l, scf_3ac_code_t, list); + l = scf_list_next(l); + + scf_list_del(&c->list); + scf_3ac_code_free(c); + c = NULL; + } + + scf_list_del(&jmp_end->list); + scf_3ac_code_free(jmp_end); + jmp_end = NULL; +} + static int _scf_op_do(scf_ast_t* ast, scf_node_t** nodes, int nb_nodes, void* data) { assert(2 == nb_nodes); @@ -1099,19 +1119,7 @@ static int _scf_op_do(scf_ast_t* ast, scf_node_t** nodes, int nb_nodes, void* da // delete 'cond check' at 'start of loop' scf_vector_del(d->branch_ops->_breaks, jmp_end); - for (l = scf_list_next(start_prev); l != &jmp_end->list; ) { - c = scf_list_data(l, scf_3ac_code_t, list); - l = scf_list_next(l); - - scf_list_del(&c->list); - scf_3ac_code_free(c); - c = NULL; - } - - scf_list_del(&jmp_end->list); - scf_3ac_code_free(jmp_end); - jmp_end = NULL; - + __scf_loop_entry_clear(start_prev, jmp_end); return 0; } @@ -1149,6 +1157,8 @@ static int _scf_op_while(scf_ast_t* ast, scf_node_t** nodes, int nb_nodes, void* } } + scf_list_t* body_end = scf_list_tail(d->_3ac_list_head); + if (_scf_op_end_loop(start_prev, NULL, jmp_end, up_branch_ops, d) < 0) { scf_loge("\n"); return -1; @@ -1157,6 +1167,14 @@ static int _scf_op_while(scf_ast_t* ast, scf_node_t** nodes, int nb_nodes, void* d->branch_ops = up_branch_ops; scf_branch_ops_free(local_branch_ops); local_branch_ops = NULL; + + if (body_end == &jmp_end->list) { + + scf_vector_del(d->branch_ops->_breaks, jmp_end); + + __scf_loop_entry_clear(start_prev, jmp_end); + } + return 0; } diff --git a/core/scf_optimizer.c b/core/scf_optimizer.c index d69fa20..1b84c12 100644 --- a/core/scf_optimizer.c +++ b/core/scf_optimizer.c @@ -109,8 +109,8 @@ int scf_optimize(scf_ast_t* ast, scf_vector_t* functions) if (!f->node.define_flag) continue; - if (strcmp(f->node.w->text->data, "main")) - continue; +// if (strcmp(f->node.w->text->data, "main")) +// continue; printf("\n"); scf_logi("------- %s() ------\n", f->node.w->text->data); diff --git a/core/scf_optimizer_pointer_alias.c b/core/scf_optimizer_pointer_alias.c index d974d30..7a1802a 100644 --- a/core/scf_optimizer_pointer_alias.c +++ b/core/scf_optimizer_pointer_alias.c @@ -22,14 +22,13 @@ static int _filter_3ac_by_pointer_alias(scf_3ac_operand_t* pointer, scf_list_t* l3 = prev; for (l2 = scf_list_tail(&h); l2 != scf_list_sentinel(&h); ) { - c2 = scf_list_data(l2, scf_3ac_code_t, list); for ( ; l3 != scf_list_sentinel(&bb->code_list_head); ) { - - c3 = scf_list_data(l3, scf_3ac_code_t, list); + c3 = scf_list_data(l3, scf_3ac_code_t, list); if (scf_3ac_code_same(c2, c3)) { + l3 = scf_list_prev(l3); l2 = scf_list_prev(l2); @@ -104,10 +103,8 @@ static int _3ac_pointer_alias(scf_dag_node_t* alias, scf_3ac_code_t* c, scf_basi pointer = c->srcs->data[0]; ret = scf_vector_del(c->srcs, pointer); - if (ret < 0) { - scf_loge("\n"); + if (ret < 0) return ret; - } #if 1 ret = _filter_3ac_by_pointer_alias(pointer, scf_list_prev(&c->list), bb, bb_list_head); @@ -243,7 +240,7 @@ static int _alias_dereference(scf_vector_t** paliases, scf_dag_node_t* dn_pointe static int _alias_assign_dereference(scf_vector_t** paliases, scf_dag_node_t* dn_pointer, scf_3ac_code_t* c, scf_basic_block_t* bb, scf_list_t* bb_list_head) { - scf_dn_status_t* status; + scf_dn_status_t* ds; scf_vector_t* aliases; int ret; @@ -259,18 +256,24 @@ static int _alias_assign_dereference(scf_vector_t** paliases, scf_dag_node_t* dn scf_logd("aliases->size: %d\n", aliases->size); if (1 == aliases->size) { - status = aliases->data[0]; + ds = aliases->data[0]; - if (SCF_DN_ALIAS_VAR == status->alias_type && !scf_variable_const_integer(status->alias->var)) { + if (SCF_DN_ALIAS_VAR == ds->alias_type && !scf_variable_const_integer(ds->alias->var)) { - ret = _3ac_pointer_alias(status->alias, c, bb, bb_list_head); + int nb_pointers0 = scf_variable_nb_pointers(dn_pointer->var); + int nb_pointers1 = scf_variable_nb_pointers(ds->alias->var); - scf_vector_free(aliases); - aliases = NULL; + if (nb_pointers0 > nb_pointers1) { - if (ret < 0) - return ret; - return scf_basic_block_inited_vars(bb, bb_list_head); + ret = _3ac_pointer_alias(ds->alias, c, bb, bb_list_head); + + scf_vector_free(aliases); + aliases = NULL; + + if (ret < 0) + return ret; + return scf_basic_block_inited_vars(bb, bb_list_head); + } } } @@ -309,30 +312,36 @@ static int __optimize_alias_dereference(scf_3ac_operand_t* pointer, scf_3ac_code if (SCF_DN_ALIAS_VAR == ds->alias_type) { - l = scf_list_prev(&c->list); + int nb_pointers0 = scf_variable_nb_pointers(dn_pointer->var); + int nb_pointers1 = scf_variable_nb_pointers(ds->alias->var); - if (l == scf_list_sentinel(&bb->code_list_head)) { - l = scf_list_prev(&bb->list); + if (nb_pointers0 > nb_pointers1) { - assert(l != scf_list_sentinel(bb_list_head)); + l = scf_list_prev(&c->list); - bb2 = scf_list_data(l, scf_basic_block_t, list); - l = scf_list_tail(&bb2->code_list_head); - } else { - bb2 = bb; - l = scf_list_prev(&c->list); - } + if (l == scf_list_sentinel(&bb->code_list_head)) { + l = scf_list_prev(&bb->list); - scf_vector_free(aliases); - aliases = NULL; + assert(l != scf_list_sentinel(bb_list_head)); - ret = _filter_3ac_by_pointer_alias(pointer, l, bb2, bb_list_head); - if (ret < 0) - return ret; + bb2 = scf_list_data(l, scf_basic_block_t, list); + l = scf_list_tail(&bb2->code_list_head); + } else { + bb2 = bb; + l = scf_list_prev(&c->list); + } - pointer->dag_node = ds->alias; + scf_vector_free(aliases); + aliases = NULL; - return scf_basic_block_inited_vars(bb, bb_list_head); + ret = _filter_3ac_by_pointer_alias(pointer, l, bb2, bb_list_head); + if (ret < 0) + return ret; + + pointer->dag_node = ds->alias; + + return scf_basic_block_inited_vars(bb, bb_list_head); + } } } @@ -546,7 +555,6 @@ static int _optimize_pointer_alias(scf_ast_t* ast, scf_function_t* f, scf_vector return ret; } -// scf_basic_block_print_list(bb_list_head); return 0; } diff --git a/core/scf_pointer_alias.c b/core/scf_pointer_alias.c index 710d764..91b104b 100644 --- a/core/scf_pointer_alias.c +++ b/core/scf_pointer_alias.c @@ -1176,17 +1176,17 @@ static int _pointer_alias_add(scf_vector_t* aliases, scf_dag_node_t* dn, scf_3ac } di = scf_dn_index_alloc(); - if (!di) { - scf_dn_status_free(ds2); + if (!di) return -ENOMEM; - } if (scf_variable_nb_pointers(dn0->var) > 0) { ds2 = NULL; int ret = scf_ds_for_dn(&ds2, dn0); - if (ret < 0) + if (ret < 0) { + scf_dn_index_free(di); return ret; + } if (scf_variable_const(dn1->var)) di->index = dn1->var->data.i64; @@ -1197,8 +1197,10 @@ static int _pointer_alias_add(scf_vector_t* aliases, scf_dag_node_t* dn, scf_3ac ds2 = NULL; int ret = scf_ds_for_dn(&ds2, dn1); - if (ret < 0) + if (ret < 0) { + scf_dn_index_free(di); return ret; + } if (scf_variable_const(dn0->var)) di->index = dn0->var->data.i64; @@ -1208,7 +1210,7 @@ static int _pointer_alias_add(scf_vector_t* aliases, scf_dag_node_t* dn, scf_3ac scf_loge("dn0->nb_pointers: %d\n", dn0->var->nb_pointers); scf_loge("dn1->nb_pointers: %d\n", dn1->var->nb_pointers); - scf_dn_status_free(ds2); + scf_dn_index_free(di); return -1; } @@ -1509,11 +1511,15 @@ int scf_pointer_alias(scf_vector_t* aliases, scf_dag_node_t* dn_alias, scf_3ac_c } int ret; - if (scf_type_is_var(dn_alias->type)) + if (scf_type_is_var(dn_alias->type) + || SCF_OP_INC == dn_alias->type + || SCF_OP_DEC == dn_alias->type + || SCF_OP_INC_POST == dn_alias->type + || SCF_OP_DEC_POST == dn_alias->type) return _pointer_alias_var(aliases, dn_alias, c, bb, bb_list_head); - switch (dn_alias->type) { - + switch (dn_alias->type) + { case SCF_OP_ADDRESS_OF: ret = _pointer_alias_address_of(aliases, dn_alias); return ret; diff --git a/examples/inc_post.c b/examples/inc_post.c new file mode 100644 index 0000000..08acaa8 --- /dev/null +++ b/examples/inc_post.c @@ -0,0 +1,9 @@ +int printf(const char* fmt, ...); + +int main(int j) +{ + int i = j++; + + printf("i: %d\n", i); + return 0; +} diff --git a/examples/strcpy.c b/examples/strcpy.c new file mode 100644 index 0000000..83bb84c --- /dev/null +++ b/examples/strcpy.c @@ -0,0 +1,20 @@ +int printf(const char* fmt, ...); + +int scf_strcpy(char* dst, const char* src) +{ + char* p = dst; + + while (*dst++ = *src++); + + return (int)(dst - p); +} + +int main() +{ + char buf[128]; + + int n = scf_strcpy(buf, "hello"); + + printf("n: %d, %s\n", n, buf); + return 0; +} diff --git a/native/scf_instruction.h b/native/scf_instruction.h index 004018e..8fd1716 100644 --- a/native/scf_instruction.h +++ b/native/scf_instruction.h @@ -96,6 +96,15 @@ static inline int scf_inst_data_empty(scf_inst_data_t* id) return !(id->mem_flag || id->base || id->imm_size); } +static inline int scf_inst_data_use_reg(scf_inst_data_t* id, scf_register_t* r) +{ + if (id->base && SCF_COLOR_CONFLICT(id->base->color, r->color)) + return 1; + if (id->index && SCF_COLOR_CONFLICT(id->index->color, r->color)) + return 1; + return 0; +} + static inline int scf_inst_data_same(scf_inst_data_t* id0, scf_inst_data_t* id1) { // global var, are considered as different. diff --git a/native/x64/scf_x64_inst.c b/native/x64/scf_x64_inst.c index c66cd26..e10d024 100644 --- a/native/x64/scf_x64_inst.c +++ b/native/x64/scf_x64_inst.c @@ -868,17 +868,14 @@ static int _x64_inst_inc(scf_native_t* ctx, scf_3ac_code_t* c, int INC, int ADD) if (v->data_size > 0xff) imm_size = 4; - if (v->nb_pointers > 0) - OpCode = x64_find_OpCode(ADD, imm_size, v->size, SCF_X64_I2E); - else - OpCode = x64_find_OpCode(INC, v->size, v->size, SCF_X64_E); + if (v->nb_pointers > 0 && v->data_size > 1) { - if (!OpCode) { - scf_loge("v->size: %d, imm_size: %d\n", v->size, imm_size); - return -EINVAL; - } + OpCode = x64_find_OpCode(ADD, imm_size, v->size, SCF_X64_I2E); + if (!OpCode) { + scf_loge("v->size: %d, imm_size: %d\n", v->size, imm_size); + return -EINVAL; + } - if (v->nb_pointers > 0) { if (src->dag_node->color > 0) { X64_SELECT_REG_CHECK(&rs, src->dag_node, c, f, 1); inst = x64_make_inst_I2E(OpCode, rs, (uint8_t*)&v->data_size, imm_size); @@ -892,6 +889,12 @@ static int _x64_inst_inc(scf_native_t* ctx, scf_3ac_code_t* c, int INC, int ADD) } } else { + OpCode = x64_find_OpCode(INC, v->size, v->size, SCF_X64_E); + if (!OpCode) { + scf_loge("v->size: %d, imm_size: %d\n", v->size, imm_size); + return -EINVAL; + } + if (src->dag_node->color > 0) { X64_SELECT_REG_CHECK(&rs, src->dag_node, c, f, 1); inst = x64_make_inst_E(OpCode, rs); diff --git a/native/x64/scf_x64_peephole.c b/native/x64/scf_x64_peephole.c index cb3d512..394e96a 100644 --- a/native/x64/scf_x64_peephole.c +++ b/native/x64/scf_x64_peephole.c @@ -3,6 +3,12 @@ #include"scf_basic_block.h" #include"scf_3ac.h" +typedef struct { + scf_instruction_t* inst; + + int lea_flag; +} x64_peep_ctx_t; + static int __x64_peep_mov_by_lea(scf_instruction_t* mov, scf_instruction_t* lea) { scf_instruction_t* inst; @@ -36,11 +42,13 @@ static int __x64_peep_src_was_mem(scf_instruction_t* inst, scf_inst_data_t* src) scf_instruction_t* tmp; scf_x64_OpCode_t* OpCode; - if (src->base) - tmp = x64_make_inst_E2G((scf_x64_OpCode_t*)inst->OpCode, inst->dst.base, src->base); - else { - int bytes = inst->dst.base->bytes; + int bytes = inst->dst.base->bytes; + if (src->base) { + OpCode = x64_find_OpCode(inst->OpCode->type, bytes, bytes, SCF_X64_E2G); + + tmp = x64_make_inst_E2G(OpCode, inst->dst.base, src->base); + } else { if (src->imm_size < bytes) src->imm = scf_zero_extend(src->imm, src->imm_size); @@ -61,6 +69,7 @@ static int __x64_peep_src_was_mem(scf_instruction_t* inst, scf_inst_data_t* src) memcpy(inst->code, tmp->code, tmp->len); inst->len = tmp->len; + inst->OpCode = tmp->OpCode; inst->src.base = src->base; inst->src.index = NULL; inst->src.scale = 0; @@ -124,6 +133,48 @@ static int __x64_peep_mov_to_mem(scf_instruction_t* mov, scf_inst_data_t* src) return 0; } +static int _x64_peephole_lea(scf_vector_t* save_insts, scf_vector_t* peep_insts, scf_instruction_t* inst) +{ + scf_3ac_code_t* c = inst->c; + scf_basic_block_t* bb = c->basic_block; + scf_instruction_t* std; + + assert(x64_inst_data_is_reg(&inst->dst)); + + int j; + for (j = peep_insts->size - 1; j >= 0; j--) { + std = peep_insts->data[j]; + + if (scf_inst_data_use_reg(&std->src, inst->dst.base) + || scf_inst_data_use_reg(&std->dst, inst->dst.base)) { + + assert(0 == scf_vector_del(peep_insts, std)); + } + } + + return scf_vector_add_unique(peep_insts, inst); +} + +static int _x64_peephole_inc_dec(scf_vector_t* save_insts, scf_vector_t* peep_insts, scf_instruction_t* inst) +{ + scf_3ac_code_t* c = inst->c; + scf_basic_block_t* bb = c->basic_block; + scf_instruction_t* std; + + int j; + for (j = peep_insts->size - 1; j >= 0; j--) { + std = peep_insts->data[j]; + + if (x64_inst_data_affect(&std->src, &inst->dst) + || x64_inst_data_affect(&std->dst, &inst->dst)) { + + assert(0 == scf_vector_del(peep_insts, std)); + } + } + + return scf_vector_add_unique(peep_insts, inst); +} + static int _x64_peephole_mov(scf_vector_t* save_insts, scf_vector_t* peep_insts, scf_instruction_t* inst) { scf_3ac_code_t* c = inst->c; @@ -141,13 +192,27 @@ static int _x64_peephole_mov(scf_vector_t* save_insts, scf_vector_t* peep_insts, if (SCF_X64_LEA == std->OpCode->type) { - if (scf_inst_data_same(&std->dst, &inst->src) - && x64_inst_data_is_reg(&inst->dst) - && x64_inst_data_is_local(&std->src)) { + if (!x64_inst_data_is_local(&std->src)) + break; - __x64_peep_mov_by_lea(inst, std); - } - break; + if (scf_inst_data_same(&std->dst, &inst->src)) { + + if (x64_inst_data_is_reg(&inst->dst)) + __x64_peep_mov_by_lea(inst, std); + break; + + } else if (scf_inst_data_same(&std->src, &inst->src)) + break; + else if (scf_inst_data_same(&std->src, &inst->dst)) + break; + } + + if (SCF_X64_INC == std->OpCode->type || SCF_X64_DEC == std->OpCode->type) { + + if (x64_inst_data_affect(&inst->src, &std->dst) + || x64_inst_data_affect(&inst->dst, &std->dst)) + break; + continue; } if (scf_inst_data_same(&std->dst, &inst->dst)) { @@ -207,7 +272,12 @@ static int _x64_peephole_mov(scf_vector_t* save_insts, scf_vector_t* peep_insts, __x64_peep_mov_to_mem(inst, &std->src); continue; } + + } else if (!std->src.mem_flag) { + __x64_peep_src_was_mem(inst, &std->src); + continue; } + } else if (scf_inst_data_same(&std->src, &inst->dst)) { assert(0 == scf_vector_del(peep_insts, std)); @@ -224,10 +294,8 @@ static int _x64_peephole_mov(scf_vector_t* save_insts, scf_vector_t* peep_insts, } else if (x64_inst_data_is_reg(&std->dst)) { - if (inst->src.base == std->dst.base - || inst->src.index == std->dst.base - || inst->dst.base == std->dst.base - || inst->dst.index == std->dst.base) + if (scf_inst_data_use_reg(&inst->src, std->dst.base) + || scf_inst_data_use_reg(&inst->dst, std->dst.base)) std->nb_used++; } } @@ -262,6 +330,14 @@ static int _x64_peephole_cmp(scf_vector_t* save_insts, scf_vector_t* peep_insts, if (SCF_X64_LEA == std->OpCode->type) break; + if (SCF_X64_INC == std->OpCode->type || SCF_X64_DEC == std->OpCode->type) { + + if (x64_inst_data_affect(&inst->src, &std->dst) + || x64_inst_data_affect(&inst->dst, &std->dst)) + break; + continue; + } + int ret = 0; if (inst->src.mem_flag) { if (scf_inst_data_same(&inst->src, &std->src)) @@ -293,10 +369,8 @@ static int _x64_peephole_cmp(scf_vector_t* save_insts, scf_vector_t* peep_insts, check: if (x64_inst_data_is_reg(&std->dst)) { - if (inst->src.base == std->dst.base - || inst->src.index == std->dst.base - || inst->dst.index == std->dst.base - || inst->dst.base == std->dst.base) + if (scf_inst_data_use_reg(&inst->src, std->dst.base) + || scf_inst_data_use_reg(&inst->dst, std->dst.base)) std->nb_used++; } @@ -308,8 +382,10 @@ check: return 0; } -static int x64_inst_is_useful(scf_instruction_t* inst, scf_instruction_t* std) +static int x64_inst_is_useful(x64_peep_ctx_t* ctx, scf_instruction_t* std) { + scf_instruction_t* inst = ctx->inst; + if (scf_inst_data_same(&inst->dst, &std->src)) return 1; @@ -329,25 +405,9 @@ static int x64_inst_is_useful(scf_instruction_t* inst, scf_instruction_t* std) return 1; } else { - r1 = std->src.base; - if (x64_inst_data_is_reg(&std->src)) { - if (X64_COLOR_CONFLICT(r0->color, r1->color)) - return 1; - } - - if (r1 && X64_COLOR_CONFLICT(r1->color, r0->color)) - return 1; - - r1 = std->src.index; - if (r1 && X64_COLOR_CONFLICT(r1->color, r0->color)) - return 1; - - r1 = std->dst.index; - if (r1 && X64_COLOR_CONFLICT(r1->color, r0->color)) + if (scf_inst_data_use_reg(&std->src, r0)) return 1; - - r1 = std->dst.base; - if (r1 && X64_COLOR_CONFLICT(r1->color, r0->color)) + if (scf_inst_data_use_reg(&std->dst, r0)) return 1; } @@ -364,8 +424,10 @@ static int x64_inst_is_useful(scf_instruction_t* inst, scf_instruction_t* std) || SCF_OP_VA_END == inst->c->op->type) return 1; - if (x64_inst_data_is_pointer(&std->dst) || x64_inst_data_is_pointer(&std->src)) - return 1; + if (ctx->lea_flag) { + if (x64_inst_data_is_pointer(&std->dst) || x64_inst_data_is_pointer(&std->src)) + return 1; + } switch (std->OpCode->type) { @@ -377,8 +439,14 @@ static int x64_inst_is_useful(scf_instruction_t* inst, scf_instruction_t* std) case SCF_X64_MOV: case SCF_X64_LEA: - if (std->src.base == inst->dst.base) // maybe array member - return 1; + if (std->src.base == inst->dst.base) { // maybe array member + + if (ctx->lea_flag) + return 1; + + if (x64_find_register("rbp") != std->src.base) + return 1; + } break; default: break; @@ -387,16 +455,16 @@ static int x64_inst_is_useful(scf_instruction_t* inst, scf_instruction_t* std) return 0; } -static int x64_inst_useful_3ac(scf_instruction_t* inst, scf_3ac_code_t* c) +static int x64_inst_useful_3ac(x64_peep_ctx_t* ctx, scf_3ac_code_t* c) { scf_instruction_t* inst2; int j = 0; - if (inst->c == c) { + if (ctx->inst->c == c) { for ( ; j < c->instructions->size; j++) { inst2 = c->instructions->data[j]; - if (inst2 == inst) + if (inst2 == ctx->inst) break; } @@ -408,40 +476,39 @@ static int x64_inst_useful_3ac(scf_instruction_t* inst, scf_3ac_code_t* c) for ( ; j < c->instructions->size; j++) { inst2 = c->instructions->data[j]; - if (x64_inst_is_useful(inst, inst2)) + if (x64_inst_is_useful(ctx, inst2)) return 1; } } return 0; } -static int x64_inst_useful_bb(scf_instruction_t* inst, scf_basic_block_t* bb) +static int x64_inst_useful_bb(x64_peep_ctx_t* ctx, scf_basic_block_t* bb) { scf_3ac_code_t* c; scf_list_t* l; - if (bb == inst->c->basic_block) - l = &inst->c->list; + if (bb == ctx->inst->c->basic_block) + l = &ctx->inst->c->list; else l = scf_list_head(&bb->code_list_head); for ( ; l != scf_list_sentinel(&bb->code_list_head); l = scf_list_next(l)) { c = scf_list_data(l, scf_3ac_code_t, list); - if (x64_inst_useful_3ac(inst, c)) + if (x64_inst_useful_3ac(ctx, c)) return 1; } return 0; } -static int __x64_inst_useful_bb_next(scf_basic_block_t* bb, void* data, scf_vector_t* queue) +static int __x64_inst_useful_bb_next(scf_basic_block_t* bb, void* ctx, scf_vector_t* queue) { - scf_instruction_t* inst = data; scf_basic_block_t* bb2; int j; - if (x64_inst_useful_bb(inst, bb)) + if (x64_inst_useful_bb(ctx, bb)) return 1; for (j = 0; j < bb->nexts->size; j++) { @@ -455,13 +522,16 @@ static int __x64_inst_useful_bb_next(scf_basic_block_t* bb, void* data, scf_vect return 0; } -static int _x64_peephole_function(scf_vector_t* save_insts, scf_function_t* f) +static int _x64_peephole_function(scf_vector_t* save_insts, scf_function_t* f, int lea_flag) { scf_instruction_t* inst; scf_basic_block_t* bb; scf_3ac_code_t* c; + x64_peep_ctx_t ctx; int i; + ctx.lea_flag = lea_flag; + for (i = save_insts->size - 1; i >= 0; i--) { inst = save_insts->data[i]; @@ -479,7 +549,9 @@ static int _x64_peephole_function(scf_vector_t* save_insts, scf_function_t* f) c = inst->c; bb = c->basic_block; - int ret = scf_basic_block_search_bfs(bb, __x64_inst_useful_bb_next, inst); + ctx.inst = inst; + + int ret = scf_basic_block_search_bfs(bb, __x64_inst_useful_bb_next, &ctx); if (ret < 0) return ret; @@ -507,7 +579,7 @@ static int _x64_peephole_function(scf_vector_t* save_insts, scf_function_t* f) else f->bp_used_flag = 0; - scf_logw("%s(), f->bp_used_flag: %d\n", f->node.w->text->data, f->bp_used_flag); + scf_logw("%s(), f->bp_used_flag: %d, lea_flag: %d\n", f->node.w->text->data, f->bp_used_flag, lea_flag); return 0; } @@ -533,7 +605,7 @@ int x64_optimize_peephole(scf_native_t* ctx, scf_function_t* f) return -ENOMEM; } - int jmp_back_flag = 0; + int lea_flag = 0; int ret = 0; int i; @@ -552,9 +624,6 @@ int x64_optimize_peephole(scf_native_t* ctx, scf_function_t* f) assert(1 == c->dsts->size); dst = c->dsts->data[0]; - - if (dst->bb->index < bb->index) - jmp_back_flag = 1; continue; } @@ -590,7 +659,14 @@ int x64_optimize_peephole(scf_native_t* ctx, scf_function_t* f) break; case SCF_X64_LEA: - ret = scf_vector_add_unique(peep_insts, inst); + lea_flag = 1; + + ret = _x64_peephole_lea(save_insts, peep_insts, inst); + break; + + case SCF_X64_INC: + case SCF_X64_DEC: + ret = _x64_peephole_inc_dec(save_insts, peep_insts, inst); break; case SCF_X64_MOVSS: @@ -615,7 +691,7 @@ int x64_optimize_peephole(scf_native_t* ctx, scf_function_t* f) } } - ret = _x64_peephole_function(save_insts, f); + ret = _x64_peephole_function(save_insts, f, lea_flag); error: scf_vector_free(save_insts); scf_vector_free(peep_insts); diff --git a/native/x64/scf_x64_reg_util.h b/native/x64/scf_x64_reg_util.h index c05dd14..f727920 100644 --- a/native/x64/scf_x64_reg_util.h +++ b/native/x64/scf_x64_reg_util.h @@ -82,4 +82,20 @@ static inline int x64_inst_data_is_pointer(scf_inst_data_t* id) return 0; } +static inline int x64_inst_data_affect(scf_inst_data_t* y, scf_inst_data_t* x) +{ + if (x64_inst_data_is_reg(x)) { + + if (scf_inst_data_use_reg(y, x->base)) + return 1; + + } else if (x64_inst_data_is_local(x)) { + + if (scf_inst_data_same(y, x)) + return 1; + } else + return 1; + return 0; +} + #endif diff --git a/parse/scf_dfa_init_data.c b/parse/scf_dfa_init_data.c index 2453874..b67c1af 100644 --- a/parse/scf_dfa_init_data.c +++ b/parse/scf_dfa_init_data.c @@ -151,6 +151,9 @@ static int _data_action_comma(scf_dfa_t* dfa, scf_vector_t* words, void* data) SCF_DFA_PUSH_HOOK(scf_dfa_find_node(dfa, "init_data_comma"), SCF_DFA_HOOK_POST); + md->nb_lss = 0; + md->nb_rss = 0; + return SCF_DFA_SWITCH_TO; } -- 2.25.1