From 5df14088b5a473ceddb01a0c2180a06e12abc161 Mon Sep 17 00:00:00 2001 From: "yu.dongliang" Date: Thu, 20 Oct 2022 17:59:07 +0800 Subject: [PATCH] DAG optimize basic block for pointer dereference --- core/scf_3ac.c | 7 +++++ core/scf_basic_block.c | 4 +-- core/scf_operator_dag.c | 29 +++++++++++++++++- core/scf_optimizer_basic_block.c | 52 +++++++++++++++++--------------- 4 files changed, 65 insertions(+), 27 deletions(-) diff --git a/core/scf_3ac.c b/core/scf_3ac.c index 1d8f807..d9f0e4a 100644 --- a/core/scf_3ac.c +++ b/core/scf_3ac.c @@ -788,6 +788,9 @@ int scf_3ac_code_to_dag(scf_3ac_code_t* c, scf_list_t* dag) if (c->srcs) { scf_3ac_operand_t* src; + scf_dag_node_t* dn_return = scf_dag_node_alloc(c->op->type, NULL, NULL); + + scf_list_add_tail(dag, &dn_return->list); int i; for (i = 0; i < c->srcs->size; i++) { @@ -796,6 +799,10 @@ int scf_3ac_code_to_dag(scf_3ac_code_t* c, scf_list_t* dag) ret = scf_dag_get_node(dag, src->node, &src->dag_node); if (ret < 0) return ret; + + ret = scf_dag_node_add_child(dn_return, src->dag_node); + if (ret < 0) + return ret; } } } else if (scf_type_is_jmp(c->op->type)) { diff --git a/core/scf_basic_block.c b/core/scf_basic_block.c index 323fa13..92766c8 100644 --- a/core/scf_basic_block.c +++ b/core/scf_basic_block.c @@ -243,8 +243,8 @@ void scf_basic_block_print_list(scf_list_t* h) scf_basic_block_t* bb = scf_list_data(l, scf_basic_block_t, list); - printf("\033[33mbasic_block: %p, index: %d, dfo_normal: %d, cmp_flag: %d, group: %d, loop: %d, dereference_flag: %d\033[0m\n", - bb, bb->index, bb->dfo_normal, bb->cmp_flag, bb->group_flag, bb->loop_flag, bb->dereference_flag); + printf("\033[33mbasic_block: %p, index: %d, dfo_normal: %d, cmp_flag: %d, group: %d, loop: %d, dereference_flag: %d, ret_flag: %d\033[0m\n", + bb, bb->index, bb->dfo_normal, bb->cmp_flag, bb->group_flag, bb->loop_flag, bb->dereference_flag, bb->ret_flag); scf_basic_block_print(bb, sentinel); diff --git a/core/scf_operator_dag.c b/core/scf_operator_dag.c index 9a7abd2..def6838 100644 --- a/core/scf_operator_dag.c +++ b/core/scf_operator_dag.c @@ -281,6 +281,19 @@ 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); +SCF_DAG_ASSIGN_DEREFERENCE(add_assign, ADD_ASSIGN); +SCF_DAG_ASSIGN_DEREFERENCE(sub_assign, SUB_ASSIGN); +SCF_DAG_ASSIGN_DEREFERENCE(and_assign, AND_ASSIGN); +SCF_DAG_ASSIGN_DEREFERENCE(or_assign, OR_ASSIGN); +SCF_DAG_ASSIGN_DEREFERENCE(inc, INC); +SCF_DAG_ASSIGN_DEREFERENCE(dec, DEC); + static int _scf_dag_op_assign_array_index(scf_list_t* h, scf_dag_node_t* parent, scf_dag_node_t** nodes, int nb_nodes) { assert(4 == nb_nodes); @@ -298,6 +311,11 @@ SCF_DAG_ASSIGN_POINTER(sub_assign, SUB_ASSIGN); SCF_DAG_ASSIGN_POINTER(and_assign, AND_ASSIGN); SCF_DAG_ASSIGN_POINTER(or_assign, OR_ASSIGN); +static int _scf_dag_op_return(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_RETURN, NULL, nodes, nb_nodes); +} + static int _scf_dag_op_cmp(scf_list_t* h, scf_dag_node_t* parent, scf_dag_node_t** nodes, int nb_nodes) { assert(2 == nb_nodes); @@ -367,6 +385,7 @@ scf_dag_operator_t dag_operators[] = {SCF_OP_GT, SCF_OP_ASSOCIATIVITY_LEFT, _scf_dag_op_gt}, {SCF_OP_LT, SCF_OP_ASSOCIATIVITY_LEFT, _scf_dag_op_lt}, + {SCF_OP_RETURN, SCF_OP_ASSOCIATIVITY_LEFT, _scf_dag_op_return}, {SCF_OP_3AC_CMP, SCF_OP_ASSOCIATIVITY_LEFT, _scf_dag_op_cmp}, {SCF_OP_3AC_TEQ, SCF_OP_ASSOCIATIVITY_LEFT, _scf_dag_op_teq}, @@ -398,6 +417,14 @@ scf_dag_operator_t dag_operators[] = {SCF_OP_3AC_SUB_ASSIGN_POINTER, SCF_OP_ASSOCIATIVITY_RIGHT, _scf_dag_op_sub_assign_pointer}, {SCF_OP_3AC_AND_ASSIGN_POINTER, SCF_OP_ASSOCIATIVITY_RIGHT, _scf_dag_op_and_assign_pointer}, {SCF_OP_3AC_OR_ASSIGN_POINTER, SCF_OP_ASSOCIATIVITY_RIGHT, _scf_dag_op_or_assign_pointer}, + + {SCF_OP_3AC_ASSIGN_DEREFERENCE, SCF_OP_ASSOCIATIVITY_RIGHT, _scf_dag_op_assign_dereference}, + {SCF_OP_3AC_ADD_ASSIGN_DEREFERENCE, SCF_OP_ASSOCIATIVITY_RIGHT, _scf_dag_op_add_assign_dereference}, + {SCF_OP_3AC_SUB_ASSIGN_DEREFERENCE, SCF_OP_ASSOCIATIVITY_RIGHT, _scf_dag_op_sub_assign_dereference}, + {SCF_OP_3AC_AND_ASSIGN_DEREFERENCE, SCF_OP_ASSOCIATIVITY_RIGHT, _scf_dag_op_and_assign_dereference}, + {SCF_OP_3AC_OR_ASSIGN_DEREFERENCE, SCF_OP_ASSOCIATIVITY_RIGHT, _scf_dag_op_or_assign_dereference}, + {SCF_OP_3AC_INC_DEREFERENCE, SCF_OP_ASSOCIATIVITY_RIGHT, _scf_dag_op_inc_dereference}, + {SCF_OP_3AC_DEC_DEREFERENCE, SCF_OP_ASSOCIATIVITY_RIGHT, _scf_dag_op_dec_dereference}, }; scf_dag_operator_t* scf_dag_operator_find(int type) @@ -441,7 +468,7 @@ int scf_dag_expr_calculate(scf_list_t* h, scf_dag_node_t* node) #endif scf_dag_operator_t* op = scf_dag_operator_find(node->type); if (!op) { - scf_loge("node->type: %d, SCF_OP_3AC_ASSIGN_POINTER: %d\n", node->type, SCF_OP_3AC_ASSIGN_POINTER); + scf_loge("node->type: %d, %d\n", node->type, SCF_OP_3AC_ADD_ASSIGN_DEREFERENCE); if (node->var && node->var->w) scf_loge("node->var: %s\n", node->var->w->text->data); return -1; diff --git a/core/scf_optimizer_basic_block.c b/core/scf_optimizer_basic_block.c index 81a1d07..a591b09 100644 --- a/core/scf_optimizer_basic_block.c +++ b/core/scf_optimizer_basic_block.c @@ -55,7 +55,7 @@ static int _bb_dag_update(scf_basic_block_t* bb, scf_vector_t* dag, scf_list_t* if (scf_type_is_assign_array_index(dn->type)) continue; - if (scf_type_is_assign_dereference(dn->type) || SCF_OP_DEREFERENCE == dn->type) + if (scf_type_is_assign_dereference(dn->type)) continue; if (scf_type_is_assign_pointer(dn->type)) continue; @@ -66,7 +66,8 @@ static int _bb_dag_update(scf_basic_block_t* bb, scf_vector_t* dag, scf_list_t* || SCF_OP_3AC_SETZ == dn->type || SCF_OP_3AC_SETNZ == dn->type || SCF_OP_3AC_SETLT == dn->type || SCF_OP_3AC_SETLE == dn->type || SCF_OP_3AC_SETGT == dn->type || SCF_OP_3AC_SETGE == dn->type - || SCF_OP_ADDRESS_OF == dn->type) { + || SCF_OP_ADDRESS_OF == dn->type + || SCF_OP_DEREFERENCE == dn->type) { if (!dn->childs) { scf_list_del(&dn->list); @@ -78,36 +79,39 @@ static int _bb_dag_update(scf_basic_block_t* bb, scf_vector_t* dag, scf_list_t* } assert(1 == dn->childs->size || 2 == dn->childs->size); + dn_bb = dn->childs->data[0]; - dn_bb = dn->childs->data[0]; + if (SCF_OP_ADDRESS_OF == dn->type || SCF_OP_DEREFERENCE == dn->type) { - dn_func = _func_dag_find_dn(dag, dn_bb, f_dag); - if (!dn_func) { - scf_loge("\n"); - return -1; - } - - if (SCF_OP_ADDRESS_OF != dn->type) { - - if (scf_vector_find(bb->dn_saves, dn_func) - || scf_vector_find(bb->dn_resaves, dn_func)) - continue; + dn_func = _func_dag_find_dn(dag, dn, f_dag); + } else { assert(dn_bb->parents && dn_bb->parents->size > 0); if (dn != dn_bb->parents->data[dn_bb->parents->size - 1]) continue; - if (2 == dn->childs->size) { - dn_bb2 = dn->childs->data[1]; + dn_func = _func_dag_find_dn(dag, dn_bb, f_dag); + } - assert(0 == scf_vector_del(dn->childs, dn_bb2)); - assert(0 == scf_vector_del(dn_bb2->parents, dn)); + if (!dn_func) { + scf_loge("\n"); + return -1; + } + + if (scf_vector_find(bb->dn_saves, dn_func) + || scf_vector_find(bb->dn_resaves, dn_func)) + continue; + + if (2 == dn->childs->size) { + dn_bb2 = dn->childs->data[1]; - if (0 == dn_bb2->parents->size) { - scf_vector_free(dn_bb2->parents); - dn_bb2->parents = NULL; - } + assert(0 == scf_vector_del(dn->childs, dn_bb2)); + assert(0 == scf_vector_del(dn_bb2->parents, dn)); + + if (0 == dn_bb2->parents->size) { + scf_vector_free(dn_bb2->parents); + dn_bb2->parents = NULL; } } @@ -352,13 +356,14 @@ static int _optimize_basic_block(scf_ast_t* ast, scf_function_t* f, scf_list_t* int ret; int i; +// scf_basic_block_print_list(bb_list_head); + 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->ret_flag || bb->end_flag || bb->call_flag || bb->varg_flag) { @@ -375,7 +380,6 @@ static int _optimize_basic_block(scf_ast_t* ast, scf_function_t* f, scf_list_t* } } -// scf_basic_block_print_list(bb_list_head); return 0; } -- 2.25.1