From b709c4160edb945f57d3b10960728badb1781185 Mon Sep 17 00:00:00 2001 From: Nick Gasson Date: Mon, 31 Oct 2022 15:27:51 +0000 Subject: [PATCH] Dynamically resize CFG edge list --- src/jit/jit-core.c | 4 +++- src/jit/jit-llvm.c | 26 ++++++++++++++++++-------- src/jit/jit-optim.c | 37 ++++++++++++++++++++++++++++++------- src/jit/jit-priv.h | 6 +++++- test/test_jit.c | 16 ++++++++-------- 5 files changed, 64 insertions(+), 25 deletions(-) diff --git a/src/jit/jit-core.c b/src/jit/jit-core.c index 5a6b078f..900845f5 100644 --- a/src/jit/jit-core.c +++ b/src/jit/jit-core.c @@ -408,11 +408,13 @@ static void jit_interp_trace(diag_t *d) assert(a->irpos < a->func->nirs); const loc_t *loc = NULL; for (jit_ir_t *ir = &(a->func->irbuf[a->irpos]); - ir >= a->func->irbuf && !ir->target; ir--) { + ir >= a->func->irbuf; ir--) { if (ir->op == J_DEBUG) { loc = &ir->arg1.loc; break; } + else if (ir->target) + break; } jit_emit_trace(d, loc ?: tree_loc(enclosing), enclosing, symbol); diff --git a/src/jit/jit-llvm.c b/src/jit/jit-llvm.c index f2b64cde..30fb2bad 100644 --- a/src/jit/jit-llvm.c +++ b/src/jit/jit-llvm.c @@ -651,6 +651,15 @@ static void cgen_zext_result(cgen_req_t *req, cgen_block_t *cgb, jit_ir_t *ir, } } +static void cgen_sync_irpos(cgen_req_t *req, jit_ir_t *ir) +{ + const unsigned irpos = ir - req->func->irbuf; + LLVMValueRef irpos_ptr = LLVMBuildStructGEP2(req->builder, + req->types[LLVM_ANCHOR], + req->anchor, 2, ""); + LLVMBuildStore(req->builder, llvm_int32(req, irpos), irpos_ptr); +} + static void cgen_op_recv(cgen_req_t *req, cgen_block_t *cgb, jit_ir_t *ir) { assert(ir->arg1.kind == JIT_VALUE_INT64); @@ -969,18 +978,21 @@ static void cgen_op_jump(cgen_req_t *req, cgen_block_t *cgb, jit_ir_t *ir) { if (ir->cc == JIT_CC_NONE) { assert(cgb->source->out.count == 1); - LLVMBasicBlockRef dest = req->blocks[cgb->source->out.edges[0]].bbref; + LLVMBasicBlockRef dest = + req->blocks[jit_get_edge(&(cgb->source->out), 0)].bbref; LLVMBuildBr(req->builder, dest); } else if (ir->cc == JIT_CC_T) { assert(cgb->source->out.count == 2); - LLVMBasicBlockRef dest_t = req->blocks[cgb->source->out.edges[1]].bbref; + LLVMBasicBlockRef dest_t = + req->blocks[jit_get_edge(&(cgb->source->out), 1)].bbref; LLVMBasicBlockRef dest_f = (cgb + 1)->bbref; LLVMBuildCondBr(req->builder, cgb->outflags, dest_t, dest_f); } else if (ir->cc == JIT_CC_F) { assert(cgb->source->out.count == 2); - LLVMBasicBlockRef dest_t = req->blocks[cgb->source->out.edges[1]].bbref; + LLVMBasicBlockRef dest_t = + req->blocks[jit_get_edge(&(cgb->source->out), 1)].bbref; LLVMBasicBlockRef dest_f = (cgb + 1)->bbref; LLVMBuildCondBr(req->builder, cgb->outflags, dest_f, dest_t); } @@ -1051,6 +1063,8 @@ static void cgen_op_csel(cgen_req_t *req, cgen_block_t *cgb, jit_ir_t *ir) static void cgen_op_call(cgen_req_t *req, cgen_block_t *cgb, jit_ir_t *ir) { + cgen_sync_irpos(req, ir); + jit_func_t *callee = jit_get_func(req->func->jit, ir->arg1.handle); const char *name = cgen_istr(req, callee->name); LLVMValueRef global = LLVMGetNamedGlobal(req->module, name); @@ -1157,11 +1171,7 @@ static void cgen_macro_bzero(cgen_req_t *req, cgen_block_t *cgb, jit_ir_t *ir) static void cgen_macro_exit(cgen_req_t *req, cgen_block_t *cgb, jit_ir_t *ir) { - const unsigned irpos = ir - req->func->irbuf; - LLVMValueRef irpos_ptr = LLVMBuildStructGEP2(req->builder, - req->types[LLVM_ANCHOR], - req->anchor, 2, ""); - LLVMBuildStore(req->builder, llvm_int32(req, irpos), irpos_ptr); + cgen_sync_irpos(req, ir); LLVMValueRef which = cgen_get_value(req, cgb, ir->arg1); LLVMValueRef fn = cgen_get_fn(req, LLVM_DO_EXIT); diff --git a/src/jit/jit-optim.c b/src/jit/jit-optim.c index 947a46d7..413e80ee 100644 --- a/src/jit/jit-optim.c +++ b/src/jit/jit-optim.c @@ -20,6 +20,7 @@ #include #include +#include //////////////////////////////////////////////////////////////////////////////// // Control flow graph construction @@ -46,13 +47,32 @@ static bool cfg_will_abort(jit_ir_t *ir) return ir->op == J_TRAP; } -static void cfg_add_edge(jit_cfg_t *cfg, jit_block_t *from, jit_block_t *to) +static void cfg_add_one_edge(jit_edge_list_t *list, unsigned edge) { - assert(from->out.count < 4); - assert(to->in.count < 4); + if (list->count < 4) + list->u.edges[list->count++] = edge; + else if (list->count == 4) { + unsigned *ptr = xmalloc_array(16, sizeof(unsigned)); + memcpy(ptr, list->u.edges, 4 * sizeof(unsigned)); + + list->max = 16; + list->u.external = ptr; + list->u.external[list->count++] = edge; + } + else if (list->count == list->max) { + list->max *= 2; + list->u.external = + xrealloc_array(list->u.external, list->max, sizeof(unsigned)); + list->u.external[list->count++] = edge; + } + else + list->u.external[list->count++] = edge; +} - from->out.edges[from->out.count++] = to - cfg->blocks; - to->in.edges[to->in.count++] = from - cfg->blocks; +static void cfg_add_edge(jit_cfg_t *cfg, jit_block_t *from, jit_block_t *to) +{ + cfg_add_one_edge(&(from->out), to - cfg->blocks); + cfg_add_one_edge(&(to->in), from - cfg->blocks); } static jit_reg_t cfg_get_reg(jit_value_t value) @@ -216,6 +236,9 @@ jit_block_t *jit_block_for(jit_cfg_t *cfg, int pos) int jit_get_edge(jit_edge_list_t *list, int nth) { - assert(nth < 4); - return list->edges[nth]; + assert(nth < list->count); + if (list->max <= 4) + return list->u.edges[nth]; + else + return list->u.external[nth]; } diff --git a/src/jit/jit-priv.h b/src/jit/jit-priv.h index a0b08344..abc75b2e 100644 --- a/src/jit/jit-priv.h +++ b/src/jit/jit-priv.h @@ -204,7 +204,11 @@ typedef void (*jit_entry_fn_t)(jit_func_t *, jit_anchor_t *, jit_scalar_t *); typedef struct { unsigned count; - unsigned edges[4]; + unsigned max; + union { + unsigned edges[4]; + unsigned *external; + } u; } jit_edge_list_t; typedef struct _jit_block { diff --git a/test/test_jit.c b/test/test_jit.c index 4a9191fb..8f78c45e 100644 --- a/test/test_jit.c +++ b/test/test_jit.c @@ -1242,7 +1242,7 @@ START_TEST(test_cfg1) ck_assert_int_eq(cfg->blocks[0].aborts, 0); ck_assert_int_eq(cfg->blocks[0].in.count, 0); ck_assert_int_eq(cfg->blocks[0].out.count, 1); - ck_assert_int_eq(cfg->blocks[0].out.edges[0], 1); + ck_assert_int_eq(jit_get_edge(&cfg->blocks[0].out, 0), 1); ck_assert_int_eq(cfg->blocks[0].livein.size, 2); ck_assert_int_eq(cfg->blocks[0].livein.bits, 0); ck_assert_int_eq(cfg->blocks[0].liveout.size, 2); @@ -1251,26 +1251,26 @@ START_TEST(test_cfg1) ck_assert_int_eq(cfg->blocks[0].varkill.bits, 0x3); ck_assert_int_eq(cfg->blocks[1].in.count, 2); - ck_assert_int_eq(cfg->blocks[1].in.edges[0], 0); - ck_assert_int_eq(cfg->blocks[1].in.edges[1], 2); + ck_assert_int_eq(jit_get_edge(&cfg->blocks[1].in, 0), 0); + ck_assert_int_eq(jit_get_edge(&cfg->blocks[1].in, 1), 2); ck_assert_int_eq(cfg->blocks[1].out.count, 2); - ck_assert_int_eq(cfg->blocks[1].out.edges[0], 2); - ck_assert_int_eq(cfg->blocks[1].out.edges[1], 3); + ck_assert_int_eq(jit_get_edge(&cfg->blocks[1].out, 0), 2); + ck_assert_int_eq(jit_get_edge(&cfg->blocks[1].out, 1), 3); ck_assert_int_eq(cfg->blocks[1].livein.bits, 0x3); ck_assert_int_eq(cfg->blocks[1].liveout.bits, 0x3); ck_assert_int_eq(cfg->blocks[1].varkill.bits, 0); ck_assert_int_eq(cfg->blocks[2].in.count, 1); - ck_assert_int_eq(cfg->blocks[2].in.edges[0], 1); + ck_assert_int_eq(jit_get_edge(&cfg->blocks[2].in, 0), 1); ck_assert_int_eq(cfg->blocks[2].out.count, 1); - ck_assert_int_eq(cfg->blocks[2].out.edges[0], 1); + ck_assert_int_eq(jit_get_edge(&cfg->blocks[2].out, 0), 1); ck_assert_int_eq(cfg->blocks[2].livein.bits, 0x3); ck_assert_int_eq(cfg->blocks[2].liveout.bits, 0x3); ck_assert_int_eq(cfg->blocks[2].varkill.bits, 0x3); ck_assert_int_eq(cfg->blocks[3].returns, 1); ck_assert_int_eq(cfg->blocks[3].in.count, 1); - ck_assert_int_eq(cfg->blocks[3].in.edges[0], 1); + ck_assert_int_eq(jit_get_edge(&cfg->blocks[3].in, 0), 1); ck_assert_int_eq(cfg->blocks[3].out.count, 0); ck_assert_int_eq(cfg->blocks[3].livein.bits, 0x2); ck_assert_int_eq(cfg->blocks[3].liveout.bits, 0); -- 2.39.2