From 1d5aba32f02abeb7bc0d5e5d9ce71a157be899f6 Mon Sep 17 00:00:00 2001 From: "yu.dongliang" <18588496441@163.com> Date: Tue, 28 Nov 2023 18:14:09 +0800 Subject: [PATCH] fix: some bugs in pointer analysis --- core/scf_basic_block.c | 73 +++++++++++++++++++++++------- core/scf_basic_block.h | 2 + core/scf_optimizer_basic_block.c | 25 ++++------ core/scf_optimizer_dag.c | 2 +- core/scf_optimizer_pointer_alias.c | 20 +++++--- core/scf_pointer_alias.c | 38 ++++++++++------ examples/array_pointer_opt.c | 24 ++++++++++ examples/struct_pointer_opt.c | 24 ++++++++++ 8 files changed, 154 insertions(+), 54 deletions(-) create mode 100644 examples/array_pointer_opt.c create mode 100644 examples/struct_pointer_opt.c diff --git a/core/scf_basic_block.c b/core/scf_basic_block.c index 36e76a7..dca0be5 100644 --- a/core/scf_basic_block.c +++ b/core/scf_basic_block.c @@ -265,22 +265,21 @@ void scf_basic_block_print_list(scf_list_t* h) } } #if 0 - if (bb->dominators) { - for (i = 0; i < bb->dominators->size; i++) - printf("dominator: %p\n", bb->dominators->data[i]); + if (bb->dominators_normal) { + for (i = 0; i < bb->dominators_normal->size; i++) + printf("dominator: %p\n", bb->dominators_normal->data[i]); } +#endif if (bb->dn_status_initeds) { + printf("inited: \n"); for (i = 0; i < bb->dn_status_initeds->size; i++) { - scf_dn_status_t* av = bb->dn_status_initeds->data[i]; - scf_dag_node_t* dn = av->dag_node; - scf_variable_t* v = dn->var; + scf_dn_status_t* ds = bb->dn_status_initeds->data[i]; - if (v && v->w) - printf("inited: v_%d_%d/%s\n", v->w->line, v->w->pos, v->w->text->data); + scf_dn_status_print(ds); } + printf("\n"); } -#endif #if 1 if (bb->ds_malloced) { scf_dn_status_t* ds; @@ -816,15 +815,12 @@ static int _bb_init_array_index(scf_3ac_code_t* c, scf_basic_block_t* bb, scf_li int scf_basic_block_inited_vars(scf_basic_block_t* bb, scf_list_t* bb_list_head) { - int ret = 0; - int i; - - scf_list_t* l; + scf_3ac_operand_t* dst; scf_3ac_code_t* c; scf_dag_node_t* dn; - scf_dn_status_t* status; - scf_dn_status_t* status2; - scf_3ac_operand_t* dst; + scf_list_t* l; + + int ret = 0; for (l = scf_list_head(&bb->code_list_head); l != scf_list_sentinel(&bb->code_list_head); l = scf_list_next(l)) { @@ -868,6 +864,51 @@ int scf_basic_block_inited_vars(scf_basic_block_t* bb, scf_list_t* bb_list_head) return 0; } +int scf_basic_block_inited_by3ac(scf_basic_block_t* bb) +{ + scf_dn_status_t* ds; + scf_dn_status_t* ds2; + scf_3ac_code_t* c; + scf_list_t* l; + + int i; + + if (bb->dn_status_initeds) + scf_vector_clear(bb->dn_status_initeds, ( void (*)(void*) )scf_dn_status_free); + else { + bb->dn_status_initeds = scf_vector_alloc(); + if (!bb->dn_status_initeds) + return -ENOMEM; + } + + 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->dn_status_initeds) + continue; + + for (i = 0; i < c->dn_status_initeds->size; i++) { + ds = c->dn_status_initeds->data[i]; + + ds2 = scf_vector_find_cmp(bb->dn_status_initeds, ds, scf_dn_status_cmp_same_dn_indexes); + if (ds2) + scf_vector_del(bb->dn_status_initeds, ds2); + + ds2 = scf_dn_status_clone(ds); + if (!ds2) + return -ENOMEM; + + if (scf_vector_add(bb->dn_status_initeds, ds2) < 0) { + scf_dn_status_free(ds2); + return -ENOMEM; + } + } + } + + return 0; +} + int scf_basic_block_active_vars(scf_basic_block_t* bb) { scf_list_t* l; diff --git a/core/scf_basic_block.h b/core/scf_basic_block.h index 0c932eb..c9d4e39 100644 --- a/core/scf_basic_block.h +++ b/core/scf_basic_block.h @@ -134,5 +134,7 @@ int scf_basic_block_split(scf_basic_block_t* bb_parent, scf_basi void scf_basic_block_mov_code(scf_list_t* start, scf_basic_block_t* bb_dst, scf_basic_block_t* bb_src); +int scf_basic_block_inited_by3ac(scf_basic_block_t* bb); + #endif diff --git a/core/scf_optimizer_basic_block.c b/core/scf_optimizer_basic_block.c index a46b3e4..df9cf5c 100644 --- a/core/scf_optimizer_basic_block.c +++ b/core/scf_optimizer_basic_block.c @@ -48,7 +48,7 @@ static int _bb_dag_update(scf_basic_block_t* bb) continue; } - assert(1 == dn->childs->size || 2 == dn->childs->size); + assert(1 <= dn->childs->size && dn->childs->size <= 3); dn_bb = dn->childs->data[0]; if (SCF_OP_ADDRESS_OF == dn->type || SCF_OP_DEREFERENCE == dn->type) { @@ -73,26 +73,18 @@ static int _bb_dag_update(scf_basic_block_t* bb) || scf_vector_find(bb->dn_resaves, dn_func)) continue; - if (2 == dn->childs->size) { - dn_bb2 = dn->childs->data[1]; + for (i = 0; i < dn->childs->size; ) { + dn_bb = dn->childs->data[i]; - assert(0 == scf_vector_del(dn->childs, dn_bb2)); - assert(0 == scf_vector_del(dn_bb2->parents, dn)); + assert(0 == scf_vector_del(dn->childs, dn_bb)); + assert(0 == scf_vector_del(dn_bb->parents, dn)); - if (0 == dn_bb2->parents->size) { - scf_vector_free(dn_bb2->parents); - dn_bb2->parents = NULL; + if (0 == dn_bb->parents->size) { + scf_vector_free(dn_bb->parents); + dn_bb->parents = NULL; } } - assert(0 == scf_vector_del(dn->childs, dn_bb)); - assert(0 == scf_vector_del(dn_bb->parents, dn)); - - if (0 == dn_bb->parents->size) { - scf_vector_free(dn_bb->parents); - dn_bb->parents = NULL; - } - assert(0 == dn->childs->size); scf_list_del(&dn->list); scf_dag_node_free(dn); @@ -285,6 +277,7 @@ static int _optimize_basic_block(scf_ast_t* ast, scf_function_t* f, scf_list_t* int ret; int i; +// scf_logi("------- %s() ------\n", f->node.w->text->data); // scf_basic_block_print_list(bb_list_head); #if 1 for (l = scf_list_head(bb_list_head); l != scf_list_sentinel(bb_list_head); diff --git a/core/scf_optimizer_dag.c b/core/scf_optimizer_dag.c index ec74b4c..cdcf0d5 100644 --- a/core/scf_optimizer_dag.c +++ b/core/scf_optimizer_dag.c @@ -31,7 +31,7 @@ static int _optimize_dag(scf_ast_t* ast, scf_function_t* f, scf_list_t* bb_list_ } } -// scf_basic_block_print_list(bb_list_head); + scf_basic_block_print_list(bb_list_head); return 0; } diff --git a/core/scf_optimizer_pointer_alias.c b/core/scf_optimizer_pointer_alias.c index 02244d3..b228c6c 100644 --- a/core/scf_optimizer_pointer_alias.c +++ b/core/scf_optimizer_pointer_alias.c @@ -525,20 +525,26 @@ static int _optimize_alias_bb(scf_basic_block_t* bb, scf_list_t* bb_list_head) if (scf_list_next(end) == scf_list_sentinel(&bb->code_list_head)) break; - scf_basic_block_t* bb_child = NULL; + scf_basic_block_t* bb2 = NULL; - int ret = scf_basic_block_split(bb, &bb_child); + int ret = scf_basic_block_split(bb, &bb2); if (ret < 0) return ret; - bb_child->dereference_flag = 0; - bb_child->array_index_flag = bb->array_index_flag; + bb2->ret_flag = bb->ret_flag; + bb ->ret_flag = 0; - scf_basic_block_mov_code(scf_list_next(end), bb_child, bb); + bb2->dereference_flag = 0; + bb2->array_index_flag = bb->array_index_flag; - scf_list_add_front(&bb->list, &bb_child->list); + scf_basic_block_mov_code(scf_list_next(end), bb2, bb); - bb = bb_child; +// SCF_XCHG(bb2->dn_status_initeds, bb->dn_status_initeds); +// scf_basic_block_inited_by3ac(bb); + + scf_list_add_front(&bb->list, &bb2->list); + + bb = bb2; } while (1); return 0; diff --git a/core/scf_pointer_alias.c b/core/scf_pointer_alias.c index 0417374..1dcdc21 100644 --- a/core/scf_pointer_alias.c +++ b/core/scf_pointer_alias.c @@ -173,26 +173,35 @@ static int _bb_pointer_initeds(scf_vector_t* initeds, scf_list_t* bb_list_head, } if (ds->dn_indexes && ds->dn_indexes->size > 0) { + dn = ds->dag_node; + v = dn->var; - scf_dn_status_t* base; - scf_vector_t* tmp; + if (!v->arg_flag + && !v->global_flag + && v->nb_dimentions <= 0 + && v->nb_pointers > 0 + && !scf_variable_const(v) && !scf_variable_const_string(v)) { - base = scf_dn_status_alloc(ds->dag_node); - if (!base) - return -ENOMEM; + scf_dn_status_t* base; + scf_vector_t* tmp; - tmp = scf_vector_alloc(); - if (!tmp) { - scf_dn_status_free(base); - return -ENOMEM; - } + base = scf_dn_status_alloc(ds->dag_node); + if (!base) + return -ENOMEM; - ret = _bb_pointer_initeds(tmp, bb_list_head, bb, base); + tmp = scf_vector_alloc(); + if (!tmp) { + scf_dn_status_free(base); + return -ENOMEM; + } - scf_vector_free(tmp); - scf_dn_status_free(base); + ret = _bb_pointer_initeds(tmp, bb_list_head, bb, base); - return ret; + scf_vector_free(tmp); + scf_dn_status_free(base); + + return ret; + } } scf_loge("initeds->size: %d\n", initeds->size); @@ -763,6 +772,7 @@ int _dn_status_alias_dereference(scf_vector_t* aliases, scf_dn_status_t* ds_poin continue; ds = scf_vector_find_cmp(c2->dn_status_initeds, ds_pointer, scf_dn_status_cmp_like_dn_indexes); + if (ds && ds->alias) { if (scf_vector_find(aliases, ds)) diff --git a/examples/array_pointer_opt.c b/examples/array_pointer_opt.c new file mode 100644 index 0000000..5017e1f --- /dev/null +++ b/examples/array_pointer_opt.c @@ -0,0 +1,24 @@ +int printf(const char* fmt, ...); + +int f() +{ + int a = 1; + int b = 2; + + int* pa[2] = {&a, &b}; + + int** pp = &pa[0]; + + **pp += 3; + return a; +} + +int main() +{ + int i = 1; + int a = 2; + int b = 3; + + printf("%d\n", f()); + return 0; +} diff --git a/examples/struct_pointer_opt.c b/examples/struct_pointer_opt.c new file mode 100644 index 0000000..da1fdbc --- /dev/null +++ b/examples/struct_pointer_opt.c @@ -0,0 +1,24 @@ +int printf(const char* fmt, ...); + +struct S { + int* p0; + int* p1; +}; + +int f() +{ + int a = 1; + int b = 2; + S s = {&a, &b}; + + int** pp = &s->p0; + + **pp += 3; + return a; +} + +int main() +{ + printf("%d\n", f()); + return 0; +} -- 2.25.1