ruby-changes:68710
From: Maxime <ko1@a...>
Date: Thu, 21 Oct 2021 08:12:31 +0900 (JST)
Subject: [ruby-changes:68710] 187435c117 (master): Complete refactoring to eliminate recursion in ujit's compilation
https://git.ruby-lang.org/ruby.git/commit/?id=187435c117 From 187435c11757748af37c59ced54d4ee04f442ffe Mon Sep 17 00:00:00 2001 From: Maxime Chevalier-Boisvert <maxime.chevalierboisvert@s...> Date: Mon, 18 Jan 2021 17:03:04 -0500 Subject: Complete refactoring to eliminate recursion in ujit's compilation --- ujit_codegen.c | 54 ++++++++----------- ujit_codegen.h | 4 +- ujit_core.c | 162 +++++++++++++++++++++++++++++++++------------------------ ujit_core.h | 7 ++- 4 files changed, 121 insertions(+), 106 deletions(-) diff --git a/ujit_codegen.c b/ujit_codegen.c index 006d64fe0f..bc91a9ad3b 100644 --- a/ujit_codegen.c +++ b/ujit_codegen.c @@ -81,6 +81,9 @@ ujit_side_exit(jitstate_t* jit, ctx_t* ctx) https://github.com/ruby/ruby/blob/trunk/ujit_codegen.c#L81 // Table mapping opcodes to interpreter handlers const void * const *handler_table = rb_vm_get_insns_address_table(); + // FIXME: rewriting the old instruction is only necessary if we're + // exiting right at an interpreter entry point + // Write back the old instruction at the exit PC // Otherwise the interpreter may jump right back to the // JITted code we're trying to exit @@ -102,7 +105,7 @@ Compile an interpreter entry block to be inserted into an iseq https://github.com/ruby/ruby/blob/trunk/ujit_codegen.c#L105 Returns `NULL` if compilation fails. */ uint8_t* -ujit_gen_entry(block_t* block) +ujit_entry_prologue() { assert (cb != NULL); @@ -121,28 +124,17 @@ ujit_gen_entry(block_t* block) https://github.com/ruby/ruby/blob/trunk/ujit_codegen.c#L124 // Load the current SP from the CFP into REG_SP mov(cb, REG_SP, member_opnd(REG_CFP, rb_control_frame_t, sp)); - // Compile the block starting at this instruction - uint32_t num_instrs = ujit_gen_code(block); - - // If no instructions were compiled - if (num_instrs == 0) { - return NULL; - } - return code_ptr; } /* Compile a sequence of bytecode instructions for a given basic block version */ -uint32_t -ujit_gen_code(block_t* block) +void +ujit_gen_block(ctx_t* ctx, block_t* block) { assert (cb != NULL); - - // Copy the block's context to avoid mutating it - ctx_t ctx_copy = block->ctx; - ctx_t* ctx = &ctx_copy; + assert (block != NULL); const rb_iseq_t *iseq = block->blockid.iseq; uint32_t insn_idx = block->blockid.idx; @@ -158,16 +150,19 @@ ujit_gen_code(block_t* block) https://github.com/ruby/ruby/blob/trunk/ujit_codegen.c#L150 rb_bug("out of executable memory (outlined block)"); } - // Last operation that was successfully compiled - opdesc_t* p_last_op = NULL; - - // Initialize JIT state object + // Initialize a JIT state object jitstate_t jit = { block, - iseq + block->blockid.iseq, + 0, + 0 }; - uint32_t num_instrs = 0; + // Last operation that was successfully compiled + opdesc_t* p_last_op = NULL; + + // Mark the start position of the block + block->start_pos = cb->write_pos; // For each instruction to compile for (;;) { @@ -191,7 +186,7 @@ ujit_gen_code(block_t* block) https://github.com/ruby/ruby/blob/trunk/ujit_codegen.c#L186 opdesc_t* p_desc = (opdesc_t*)st_op_desc; bool success = p_desc->gen_fn(&jit, ctx); - // If we can't compile this instruction + // If we can't compile this instruction, stop if (!success) { break; } @@ -199,7 +194,6 @@ ujit_gen_code(block_t* block) https://github.com/ruby/ruby/blob/trunk/ujit_codegen.c#L194 // Move to the next instruction p_last_op = p_desc; insn_idx += insn_len(opcode); - num_instrs++; // If this instruction terminates this block if (p_desc->is_branch) { @@ -207,15 +201,18 @@ ujit_gen_code(block_t* block) https://github.com/ruby/ruby/blob/trunk/ujit_codegen.c#L201 } } - // Store the index of the last instruction in the block - block->end_idx = insn_idx; - // If the last instruction compiled did not terminate the block // Generate code to exit to the interpreter if (!p_last_op || !p_last_op->is_branch) { ujit_gen_exit(&jit, ctx, cb, &encoded[insn_idx]); } + // Mark the end position of the block + block->end_pos = cb->write_pos; + + // Store the index of the last instruction in the block + block->end_idx = insn_idx; + if (UJIT_DUMP_MODE >= 2) { // Dump list of compiled instrutions fprintf(stderr, "Compiled the following for iseq=%p:\n", (void *)iseq); @@ -227,8 +224,6 @@ ujit_gen_code(block_t* block) https://github.com/ruby/ruby/blob/trunk/ujit_codegen.c#L224 pc += insn_len(opcode); } } - - return num_instrs; } static bool @@ -683,7 +678,6 @@ gen_branchunless(jitstate_t* jit, ctx_t* ctx) https://github.com/ruby/ruby/blob/trunk/ujit_codegen.c#L678 // Generate the branch instructions gen_branch( - jit->block, ctx, jump_block, ctx, @@ -727,7 +721,6 @@ gen_jump(jitstate_t* jit, ctx_t* ctx) https://github.com/ruby/ruby/blob/trunk/ujit_codegen.c#L721 // Generate the jump instruction gen_branch( - jit->block, ctx, jump_block, ctx, @@ -986,7 +979,6 @@ gen_opt_send_without_block(jitstate_t* jit, ctx_t* ctx) https://github.com/ruby/ruby/blob/trunk/ujit_codegen.c#L979 // We do this to end the current block after the call blockid_t cont_block = { jit->iseq, jit_next_idx(jit) }; gen_branch( - jit->block, ctx, cont_block, ctx, diff --git a/ujit_codegen.h b/ujit_codegen.h index 192cf29d61..26b97bbc2a 100644 --- a/ujit_codegen.h +++ b/ujit_codegen.h @@ -40,9 +40,9 @@ typedef struct OpDesc https://github.com/ruby/ruby/blob/trunk/ujit_codegen.h#L40 } opdesc_t; -uint8_t* ujit_gen_entry(block_t* block); +uint8_t* ujit_entry_prologue(); -uint32_t ujit_gen_code(block_t* block); +void ujit_gen_block(ctx_t* ctx, block_t* block); void ujit_init_codegen(void); diff --git a/ujit_core.c b/ujit_core.c index 70306ce86b..332e356860 100644 --- a/ujit_core.c +++ b/ujit_core.c @@ -69,6 +69,17 @@ ctx_stack_opnd(ctx_t* ctx, int32_t idx) https://github.com/ruby/ruby/blob/trunk/ujit_core.c#L69 return opnd; } +// Add an incoming branch for a given block version +static void add_incoming(block_t* p_block, uint32_t branch_idx) +{ + // Add this branch to the list of incoming branches for the target + uint32_t* new_list = malloc(sizeof(uint32_t) * p_block->num_incoming + 1); + memcpy(new_list, p_block->incoming, p_block->num_incoming); + new_list[p_block->num_incoming] = branch_idx; + p_block->incoming = new_list; + p_block->num_incoming += 1; +} + // Retrieve a basic block version for an (iseq, idx) tuple block_t* find_block_version(blockid_t blockid, const ctx_t* ctx) { @@ -79,87 +90,94 @@ block_t* find_block_version(blockid_t blockid, const ctx_t* ctx) https://github.com/ruby/ruby/blob/trunk/ujit_core.c#L90 } // - // TODO: use the ctx parameter to search available versions + // TODO: use the ctx parameter to search existing versions for a match // return NULL; } // Compile a new block version immediately -block_t* gen_block_version(blockid_t blockid, const ctx_t* ctx) +block_t* gen_block_version(blockid_t blockid, const ctx_t* start_ctx) { - // Allocate a version object - block_t* p_block = malloc(sizeof(block_t)); - memcpy(&p_block->blockid, &blockid, sizeof(blockid_t)); - memcpy(&p_block->ctx, ctx, sizeof(ctx_t)); - p_block->incoming = NULL; - p_block->num_incoming = 0; - p_block->end_pos = 0; + // Copy the context to avoid mutating it + ctx_t ctx_copy = *start_ctx; + ctx_t* ctx = &ctx_copy; - // The block starts at the current position - p_block->start_pos = cb->write_pos; + // Allocate a new block version object + block_t* first_block = calloc(1, sizeof(block_t)); + first_block->blockid = blockid; + memcpy(&first_block->ctx, ctx, sizeof(ctx_t)); - // Compile the block version - ujit_gen_code(p_block); + // Block that is currently being compiled + block_t* block = first_block; - // The block may have been terminated in gen_branch - if (p_block->end_pos == 0) - p_block->end_pos = cb->write_pos; + // Generate code for the first block + ujit_gen_block(ctx, block); // Keep track of the new block version - st_insert(version_tbl, (st_data_t)&p_block->blockid, (st_data_t)p_block); + st_insert(version_tbl, (st_data_t)&block->blockid, (st_data_t)block); + + // For each successor block to compile + for (;;) { + // If no branches were generated, stop + if (num_branches == 0) { + break; + } + + // Get the last branch entry + uint32_t branch_idx = num_branches - 1; + branch_t* last_branch = &branch_entries[num_branches - 1]; + + // If there is no next block to compile, stop + if (last_branch->dst_addrs[0] || last_branch->dst_addrs[1]) { + break; + } + + if (last_branch->targets[0].iseq == NULL) { + rb_bug("invalid target for last branch"); + } + + // Allocate a new block version object + block = calloc(1, sizeof(block_t)); + block->blockid = last_branch->targets[0]; + memcpy(&block->ctx, ctx, sizeof(ctx_t)); + + // Generate code for the current block + ujit_gen_block(ctx, block); + + // Keep track of the new block version + st_insert(version_tbl, (st_data_t)&block->blockid, (st_data_t)block); + + // Patch the last branch address + last_branch->dst_addrs[0] = cb_get_ptr(cb, block->start_pos); + add_incoming(block, branch_idx); + assert (block->start_pos == last_branch->end_pos); + } - return p_block; + return first_block; } // Generate a block version that is an entry point in (... truncated) -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/