From a5329f816b57b0550e072a586027ed29bc2d90ac Mon Sep 17 00:00:00 2001 From: "yu.dongliang" <18588496441@163.com> Date: Sun, 12 Jul 2026 14:52:16 +0800 Subject: [PATCH] split code of x64 peephole to 2 files. --- core/scf_basic_block.h | 1 + native/x64/scf_x64.c | 2 +- native/x64/scf_x64.h | 8 +- native/x64/scf_x64_optimize.c | 332 ++++++++++++++++++++++++++++++++++ native/x64/scf_x64_peephole.c | 240 +----------------------- parse/Makefile | 4 +- 6 files changed, 345 insertions(+), 242 deletions(-) create mode 100644 native/x64/scf_x64_optimize.c diff --git a/core/scf_basic_block.h b/core/scf_basic_block.h index f823032..218a03c 100644 --- a/core/scf_basic_block.h +++ b/core/scf_basic_block.h @@ -107,6 +107,7 @@ struct scf_basic_block_s uint32_t loop_flag :1; uint32_t group_flag :1; uint32_t visit_flag :1; + uint32_t block_flag :1; uint32_t native_flag :1; scf_basic_block_t* vla_free; diff --git a/native/x64/scf_x64.c b/native/x64/scf_x64.c index 7877bda..94b2b89 100644 --- a/native/x64/scf_x64.c +++ b/native/x64/scf_x64.c @@ -1104,7 +1104,7 @@ int _scf_x64_select_inst(scf_native_t* ctx) } } #if 1 - if (x64_optimize_peephole(ctx, f) < 0) { + if (x64_optimize(f) < 0) { scf_loge("\n"); return -1; } diff --git a/native/x64/scf_x64.h b/native/x64/scf_x64.h index 54c6821..47e13c8 100644 --- a/native/x64/scf_x64.h +++ b/native/x64/scf_x64.h @@ -8,8 +8,10 @@ #include"scf_graph.h" #include"scf_elf.h" -#define X64_PEEPHOLE_DEL 1 -#define X64_PEEPHOLE_OK 0 +#define X64_PEEPHOLE_OK 0 +#define X64_PEEPHOLE_DEL 1 +#define X64_PEEPHOLE_USE 2 +#define X64_PEEPHOLE_BLOCK 4 typedef struct { @@ -37,7 +39,7 @@ int scf_x64_open (scf_native_t* ctx, const char* arch); int scf_x64_close (scf_native_t* ctx); int scf_x64_select(scf_native_t* ctx); -int x64_optimize_peephole(scf_native_t* ctx, scf_function_t* f); +int x64_optimize(scf_function_t* f); int scf_x64_graph_kcolor(scf_graph_t* graph, int k, scf_vector_t* colors); diff --git a/native/x64/scf_x64_optimize.c b/native/x64/scf_x64_optimize.c new file mode 100644 index 0000000..0753af8 --- /dev/null +++ b/native/x64/scf_x64_optimize.c @@ -0,0 +1,332 @@ +#include"scf_x64.h" +#include"scf_elf.h" +#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_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 X64_PEEPHOLE_USE; + + if (x64_inst_data_is_reg(&inst->dst)) { + + scf_register_t* r0 = inst->dst.base; + scf_register_t* r1; + + if (SCF_X64_CALL == std->OpCode->type) { + + if (X64_COLOR_CONFLICT(r0->color, X64_COLOR(0, SCF_X64_REG_RDI, 0xff)) + || X64_COLOR_CONFLICT(r0->color, X64_COLOR(0, SCF_X64_REG_RSI, 0xff)) + || X64_COLOR_CONFLICT(r0->color, X64_COLOR(0, SCF_X64_REG_RDX, 0xff)) + || X64_COLOR_CONFLICT(r0->color, X64_COLOR(0, SCF_X64_REG_RCX, 0xff)) + || X64_COLOR_CONFLICT(r0->color, X64_COLOR(0, SCF_X64_REG_R8, 0xff)) + || X64_COLOR_CONFLICT(r0->color, X64_COLOR(0, SCF_X64_REG_R9, 0xff)) + || X64_COLOR_CONFLICT(r0->color, X64_COLOR(0, SCF_X64_REG_RAX, 0xff)) + + || X64_COLOR_CONFLICT(r0->color, X64_COLOR(1, SCF_X64_REG_XMM0, 0xff)) + || X64_COLOR_CONFLICT(r0->color, X64_COLOR(1, SCF_X64_REG_XMM1, 0xff)) + || X64_COLOR_CONFLICT(r0->color, X64_COLOR(1, SCF_X64_REG_XMM2, 0xff)) + || X64_COLOR_CONFLICT(r0->color, X64_COLOR(1, SCF_X64_REG_XMM3, 0xff)) + || X64_COLOR_CONFLICT(r0->color, X64_COLOR(1, SCF_X64_REG_XMM4, 0xff)) + || X64_COLOR_CONFLICT(r0->color, X64_COLOR(1, SCF_X64_REG_XMM5, 0xff)) + || X64_COLOR_CONFLICT(r0->color, X64_COLOR(1, SCF_X64_REG_XMM6, 0xff)) + || X64_COLOR_CONFLICT(r0->color, X64_COLOR(1, SCF_X64_REG_XMM7, 0xff))) + return X64_PEEPHOLE_USE; + + } else { + if (scf_inst_data_use_reg(&std->src, r0)) + return X64_PEEPHOLE_USE; + + switch (std->OpCode->type) + { + case SCF_X64_MUL: + case SCF_X64_DIV: + + if (X64_COLOR_CONFLICT(r0->color, X64_COLOR(0, SCF_X64_REG_RAX, 0xff)) + || X64_COLOR_CONFLICT(r0->color, X64_COLOR(0, SCF_X64_REG_RDX, 0xff))) + return X64_PEEPHOLE_USE; + break; + + case SCF_X64_SHL: + case SCF_X64_SHR: + case SCF_X64_SAR: + if (X64_COLOR_CONFLICT(r0->color, X64_COLOR(0, SCF_X64_REG_RCX, 0xff))) + return X64_PEEPHOLE_USE; + break; + }; +#if 1 + if (SCF_X64_MOV == std->OpCode->type + && x64_inst_data_is_reg(&std->dst) + && X64_COLOR_CONFLICT(std->dst.base->color, r0->color)) + return X64_PEEPHOLE_BLOCK; +#endif + if (scf_inst_data_use_reg(&std->dst, r0)) + return X64_PEEPHOLE_USE; + } + + } else if (x64_inst_data_is_local(&inst->dst)) { + + if (scf_inst_data_same(&inst->dst, &std->src)) + return X64_PEEPHOLE_USE; + + if (X64_COLOR_CONFLICT(inst->dst.base->color, X64_COLOR(0, SCF_X64_REG_RSP, 0xff))) + return X64_PEEPHOLE_USE; + + if (SCF_OP_VA_START == inst->c->op->type + || SCF_OP_VA_ARG == inst->c->op->type + || SCF_OP_VA_END == inst->c->op->type) + return X64_PEEPHOLE_USE; + + if (ctx->lea_flag) { + if (x64_inst_data_is_pointer(&std->dst) || x64_inst_data_is_pointer(&std->src)) + return X64_PEEPHOLE_USE; + } + + switch (std->OpCode->type) + { + case SCF_X64_CMP: + case SCF_X64_TEST: + if (scf_inst_data_same(&inst->dst, &std->dst)) + return X64_PEEPHOLE_USE; + break; + + case SCF_X64_MOV: + case SCF_X64_LEA: + if (std->src.base == inst->dst.base) { // maybe array member + + if (ctx->lea_flag) + return X64_PEEPHOLE_USE; + + if (!X64_COLOR_CONFLICT(std->src.base->color, X64_COLOR(0, SCF_X64_REG_RBP, 0xff))) + return X64_PEEPHOLE_USE; + } + break; + default: + break; + }; + } + return 0; +} + +static int x64_inst_useful_3ac(x64_peep_ctx_t* ctx, scf_3ac_code_t* c) +{ + scf_instruction_t* inst2; + int j = 0; + + if (ctx->inst->c == c) { + for ( ; j < c->instructions->size; j++) { + inst2 = c->instructions->data[j]; + + if (inst2 == ctx->inst) + break; + } + + assert(j < c->instructions->size); + ++j; + } + + if (c->instructions) { + for ( ; j < c->instructions->size; j++) { + inst2 = c->instructions->data[j]; + + int ret = x64_inst_is_useful(ctx, inst2); + if (ret > 0) + return ret; + } + } + return 0; +} + +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 == 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); + + int ret = x64_inst_useful_3ac(ctx, c); + if (ret > 0) + return ret; + } + + return 0; +} + +static int __x64_inst_useful_dfs_next(scf_basic_block_t* cur, x64_peep_ctx_t* ctx) +{ + cur->visit_flag = 1; + + int ret = x64_inst_useful_bb(ctx, cur); + if (ret > 0) + return ret; + + scf_basic_block_t* bb; + int j; + int flag = 0; + + for (j = 0; j < cur->nexts->size; j++) { + bb = cur->nexts->data[j]; + + if (bb->visit_flag) + continue; + + ret = __x64_inst_useful_dfs_next(bb, ctx); + + if (X64_PEEPHOLE_USE == ret) + return X64_PEEPHOLE_USE; + + else if (X64_PEEPHOLE_BLOCK == ret) { + flag = X64_PEEPHOLE_BLOCK; + + bb->block_flag = 1; + } + } + + return flag; +} + +static int __x64_dfs_next_block(scf_basic_block_t* cur, scf_basic_block_t* end) +{ + if (cur == end) + return 1; + + if (cur->block_flag) + return 0; + cur->block_flag = 1; + + scf_basic_block_t* bb; + int j; + + for (j = 0; j < cur->nexts->size; j++) { + bb = cur->nexts->data[j]; + + if (bb == end) + return 1; + + if (bb->block_flag) + continue; + + if (__x64_dfs_next_block(bb, end)) + return 1; + } + + return 0; +} + +static int _x64_inst_useful_dfs_next(scf_function_t* f, scf_basic_block_t* cur, x64_peep_ctx_t* ctx) +{ + scf_list_t* l = scf_list_tail(&f->basic_block_list_head); + scf_basic_block_t* end = scf_list_data(l, scf_basic_block_t, list); + scf_basic_block_t* bb; + + for (l = scf_list_head(&f->basic_block_list_head); l != scf_list_sentinel(&f->basic_block_list_head); l = scf_list_next(l)) { + bb = scf_list_data(l, scf_basic_block_t, list); + + bb->visit_flag = 0; + bb->block_flag = 0; + } + + int ret = __x64_inst_useful_dfs_next(cur, ctx); + + if (X64_PEEPHOLE_BLOCK == ret) { + if (__x64_dfs_next_block(cur, end)) + return X64_PEEPHOLE_USE; + } + + return ret; +} + +static int _x64_peephole_function(scf_vector_t* save_insts, scf_function_t* f, int lea_flag) +{ + scf_basic_block_t* bb; + scf_instruction_t* inst; + 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]; + + if (SCF_X64_MOV != inst->OpCode->type) + continue; + + if (!x64_inst_data_is_reg(&inst->dst) && !x64_inst_data_is_local(&inst->dst)) + continue; + + c = inst->c; + bb = c->basic_block; + + ctx.inst = inst; + + int ret = _x64_inst_useful_dfs_next(f, bb, &ctx); + if (ret < 0) + return ret; + + if (X64_PEEPHOLE_USE == ret) + continue; + else if (X64_PEEPHOLE_BLOCK != ret + && x64_inst_data_is_reg(&inst->dst) + && x64_reg_is_retval(inst->dst.base)) + continue; + + assert(0 == scf_vector_del(c->instructions, inst)); + assert(0 == scf_vector_del(save_insts, inst)); + + free(inst); + inst = NULL; + } + + int n_locals = 0; + + for (i = 0; i < save_insts->size; i++) { + inst = save_insts->data[i]; + + if (x64_inst_data_is_local(&inst->src) || x64_inst_data_is_local(&inst->dst)) + n_locals++; + } + + if (n_locals > 0) + f->bp_used_flag = 1; + else + f->bp_used_flag = 0; + + 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; +} + +int x64_peephole(scf_vector_t* save_insts, scf_function_t* f, int* lea_flag); + +int x64_optimize(scf_function_t* f) +{ + scf_vector_t* save_insts = scf_vector_alloc(); + if (!save_insts) + return -ENOMEM; + + int lea_flag = 0; + + int ret = x64_peephole(save_insts, f, &lea_flag); + if (ret < 0) + goto error; + + ret = _x64_peephole_function(save_insts, f, lea_flag); +error: + scf_vector_free(save_insts); + return ret; +} diff --git a/native/x64/scf_x64_peephole.c b/native/x64/scf_x64_peephole.c index 75baa7b..8c90a38 100644 --- a/native/x64/scf_x64_peephole.c +++ b/native/x64/scf_x64_peephole.c @@ -3,12 +3,6 @@ #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; @@ -382,242 +376,21 @@ check: return 0; } -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; - - if (x64_inst_data_is_reg(&inst->dst)) { - - scf_register_t* r0 = inst->dst.base; - scf_register_t* r1; - - if (SCF_X64_CALL == std->OpCode->type) { - - if (X64_COLOR_CONFLICT(r0->color, x64_find_register("rdi")->color) - || X64_COLOR_CONFLICT(r0->color, x64_find_register("rsi")->color) - || X64_COLOR_CONFLICT(r0->color, x64_find_register("rdx")->color) - || X64_COLOR_CONFLICT(r0->color, x64_find_register("rcx")->color) - || X64_COLOR_CONFLICT(r0->color, x64_find_register("r8")->color) - || X64_COLOR_CONFLICT(r0->color, x64_find_register("r9")->color) - || X64_COLOR_CONFLICT(r0->color, x64_find_register("xmm0")->color) - || X64_COLOR_CONFLICT(r0->color, x64_find_register("xmm1")->color) - || X64_COLOR_CONFLICT(r0->color, x64_find_register("xmm2")->color) - || X64_COLOR_CONFLICT(r0->color, x64_find_register("xmm3")->color) - || X64_COLOR_CONFLICT(r0->color, x64_find_register("xmm4")->color) - || X64_COLOR_CONFLICT(r0->color, x64_find_register("xmm5")->color) - || X64_COLOR_CONFLICT(r0->color, x64_find_register("xmm6")->color) - || X64_COLOR_CONFLICT(r0->color, x64_find_register("xmm7")->color)) - return 1; - - } else { - if (scf_inst_data_use_reg(&std->src, r0)) - return 1; - if (scf_inst_data_use_reg(&std->dst, r0)) - return 1; - } - - } else if (x64_inst_data_is_local(&inst->dst)) { - - if (scf_inst_data_same(&inst->dst, &std->src)) - return 1; - - if (x64_find_register("rsp") == inst->dst.base) - return 1; - - if (SCF_OP_VA_START == inst->c->op->type - || SCF_OP_VA_ARG == inst->c->op->type - || SCF_OP_VA_END == inst->c->op->type) - 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) - { - case SCF_X64_CMP: - case SCF_X64_TEST: - if (scf_inst_data_same(&inst->dst, &std->dst)) - return 1; - break; - - case SCF_X64_MOV: - case SCF_X64_LEA: - 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; - }; - } - return 0; -} - -static int x64_inst_useful_3ac(x64_peep_ctx_t* ctx, scf_3ac_code_t* c) -{ - scf_instruction_t* inst2; - int j = 0; - - if (ctx->inst->c == c) { - for ( ; j < c->instructions->size; j++) { - inst2 = c->instructions->data[j]; - - if (inst2 == ctx->inst) - break; - } - - assert(j < c->instructions->size); - ++j; - } - - if (c->instructions) { - for ( ; j < c->instructions->size; j++) { - inst2 = c->instructions->data[j]; - - if (x64_inst_is_useful(ctx, inst2)) - return 1; - } - } - return 0; -} - -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 == 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(ctx, c)) - return 1; - } - - return 0; -} - -static int __x64_inst_useful_bb_next(scf_basic_block_t* bb, void* ctx, scf_vector_t* queue) -{ - scf_basic_block_t* bb2; - int j; - - if (x64_inst_useful_bb(ctx, bb)) - return 1; - - for (j = 0; j < bb->nexts->size; j++) { - bb2 = bb->nexts->data[j]; - - int ret = scf_vector_add(queue, bb2); - if (ret < 0) - return ret; - } - - return 0; -} - -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]; - - if (SCF_X64_MOV != inst->OpCode->type) - continue; - - if (x64_inst_data_is_reg(&inst->dst)) { - - if (x64_reg_is_retval(inst->dst.base)) - continue; - - } else if (!x64_inst_data_is_local(&inst->dst)) - continue; - - c = inst->c; - bb = c->basic_block; - - ctx.inst = inst; - - int ret = scf_basic_block_search_bfs(bb, __x64_inst_useful_bb_next, &ctx); - if (ret < 0) - return ret; - - if (ret > 0) - continue; - - assert(0 == scf_vector_del(c->instructions, inst)); - assert(0 == scf_vector_del(save_insts, inst)); - - free(inst); - inst = NULL; - } - - int n_locals = 0; - - for (i = 0; i < save_insts->size; i++) { - inst = save_insts->data[i]; - - if (x64_inst_data_is_local(&inst->src) || x64_inst_data_is_local(&inst->dst)) - n_locals++; - } - - if (n_locals > 0) - f->bp_used_flag = 1; - else - f->bp_used_flag = 0; - - 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; -} - -int x64_optimize_peephole(scf_native_t* ctx, scf_function_t* f) +int x64_peephole(scf_vector_t* save_insts, scf_function_t* f, int* lea_flag) { scf_instruction_t* inst; scf_basic_block_t* bb; - scf_3ac_operand_t* dst; scf_3ac_code_t* c; scf_list_t* l; scf_list_t* l2; - scf_vector_t* peep_insts; - scf_vector_t* save_insts; peep_insts = scf_vector_alloc(); if (!peep_insts) return -ENOMEM; - save_insts = scf_vector_alloc(); - if (!save_insts) { - scf_vector_free(save_insts); - return -ENOMEM; - } - - int lea_flag = 0; - int ret = 0; int i; - int j; for (l = scf_list_head(&f->basic_block_list_head); l != scf_list_sentinel(&f->basic_block_list_head); l = scf_list_next(l)) { @@ -626,12 +399,6 @@ int x64_optimize_peephole(scf_native_t* ctx, scf_function_t* f) if (bb->jmp_flag) { scf_vector_clear(peep_insts, NULL); - - l2 = scf_list_head(&bb->code_list_head); - c = scf_list_data(l2, scf_3ac_code_t, list); - - assert(1 == c->dsts->size); - dst = c->dsts->data[0]; continue; } @@ -667,7 +434,7 @@ int x64_optimize_peephole(scf_native_t* ctx, scf_function_t* f) break; case SCF_X64_LEA: - lea_flag = 1; + *lea_flag = 1; ret = _x64_peephole_lea(save_insts, peep_insts, inst); break; @@ -699,9 +466,8 @@ int x64_optimize_peephole(scf_native_t* ctx, scf_function_t* f) } } - ret = _x64_peephole_function(save_insts, f, lea_flag); + ret = 0; error: - scf_vector_free(save_insts); scf_vector_free(peep_insts); return ret; } diff --git a/parse/Makefile b/parse/Makefile index 01bfcca..1f588d0 100644 --- a/parse/Makefile +++ b/parse/Makefile @@ -30,9 +30,11 @@ CFILES += ../native/x64/scf_x64_rcg.c CFILES += ../native/x64/scf_x64_graph.c CFILES += ../native/x64/scf_x64_reg.c CFILES += ../native/x64/scf_x64_opcode.c -CFILES += ../native/x64/scf_x64_peephole.c CFILES += ../native/x64/scf_x64_bb_color.c +CFILES += ../native/x64/scf_x64_peephole.c +CFILES += ../native/x64/scf_x64_optimize.c + CFILES += ../native/risc/scf_risc_bb_color.c CFILES += ../native/risc/scf_risc.c CFILES += ../native/risc/scf_risc_graph.c -- 2.25.1