ruby-changes:68821
From: Maxime <ko1@a...>
Date: Thu, 21 Oct 2021 08:14:05 +0900 (JST)
Subject: [ruby-changes:68821] abc016ad2c (master): WIP refactor block lists to use darray
https://git.ruby-lang.org/ruby.git/commit/?id=abc016ad2c From abc016ad2c85a15ad6a512be57f47d893bc81e27 Mon Sep 17 00:00:00 2001 From: Maxime Chevalier-Boisvert <maxime.chevalierboisvert@s...> Date: Thu, 4 Mar 2021 12:05:18 -0500 Subject: WIP refactor block lists to use darray --- ujit_codegen.c | 19 ++++++++++- ujit_core.c | 100 +++++++++++++++++++++++++++------------------------------ ujit_core.h | 6 ---- ujit_iface.c | 15 +++++---- vm_core.h | 4 ++- 5 files changed, 78 insertions(+), 66 deletions(-) diff --git a/ujit_codegen.c b/ujit_codegen.c index db8b48a2e8..41662a8b2d 100644 --- a/ujit_codegen.c +++ b/ujit_codegen.c @@ -576,13 +576,27 @@ gen_getinstancevariable(jitstate_t* jit, ctx_t* ctx) https://github.com/ruby/ruby/blob/trunk/ujit_codegen.c#L576 + /* + num_versions = count_block_versions(this_instruction); + if (num_versions > N) + return JIT_CANT_COMPILE; - /* + if (defer_compilation(this_instruction, ctx)) return JIT_END_BLOCK; + VALUE top_val = jit_peek_at_stack(); + + + + + class = get_ruby_class(top_val); + + + + guard_object_class(class, current_instr); */ @@ -593,6 +607,9 @@ gen_getinstancevariable(jitstate_t* jit, ctx_t* ctx) https://github.com/ruby/ruby/blob/trunk/ujit_codegen.c#L607 + + + // If the class uses the default allocator, instances should all be T_OBJECT // NOTE: This assumes nobody changes the allocator of the class after allocation. // Eventually, we can encode whether an object is T_OBJECT or not diff --git a/ujit_core.c b/ujit_core.c index b07d8450ad..c4db19de70 100644 --- a/ujit_core.c +++ b/ujit_core.c @@ -144,17 +144,25 @@ int ctx_diff(const ctx_t* src, const ctx_t* dst) https://github.com/ruby/ruby/blob/trunk/ujit_core.c#L144 return diff; } -static block_t * -get_first_version(const rb_iseq_t *iseq, unsigned idx) +static rb_ujit_block_array_t +get_version_array(const rb_iseq_t *iseq, unsigned idx) { struct rb_iseq_constant_body *body = iseq->body; + if (rb_darray_size(body->ujit_blocks) == 0) { return NULL; } + RUBY_ASSERT((unsigned)rb_darray_size(body->ujit_blocks) == body->iseq_size); return rb_darray_get(body->ujit_blocks, idx); } +// Count the number of block versions matching a given blockid +static size_t get_num_versions(blockid_t blockid) +{ + return rb_darray_size(get_version_array(blockid.iseq, blockid.idx)); +} + // Keep track of a block version. Block should be fully constructed. static void add_block_version(blockid_t blockid, block_t* block) @@ -214,50 +222,29 @@ add_block_version(blockid_t blockid, block_t* block) https://github.com/ruby/ruby/blob/trunk/ujit_core.c#L222 } } -// Count the number of block versions matching a given blockid -static size_t count_block_versions(blockid_t blockid) -{ - size_t count = 0; - block_t *first_version = get_first_version(blockid.iseq, blockid.idx); - - // For each version matching the blockid - for (block_t *version = first_version; version != NULL; version = version->next) - { - count += 1; - } - - return count; -} - // Retrieve a basic block version for an (iseq, idx) tuple block_t* find_block_version(blockid_t blockid, const ctx_t* ctx) { - block_t *first_version = get_first_version(blockid.iseq, blockid.idx); - - // If there exists a version for this block id - if (!first_version) return NULL; + rb_ujit_block_array_t versions = get_version_array(iseq, block->blockid.idx); // Best match found block_t* best_version = NULL; int best_diff = INT_MAX; // For each version matching the blockid - for (block_t* version = first_version; version != NULL; version = version->next) - { - int diff = ctx_diff(ctx, &version->ctx); - - if (diff < best_diff) - { + block_t **element; + rb_darray_foreach(versions, idx, element) { + block_t *version = *element; + int diff = ctx_diff(ctx, version->ctx); + + // Note that we always prefer the first matching + // version because of inline-cache chains + if (diff < best_diff) { best_version = version; best_diff = diff; } } - if (best_version == NULL) - { - return NULL; - } - return best_version; } @@ -393,7 +380,7 @@ uint8_t* branch_stub_hit(uint32_t branch_idx, uint32_t target_idx, rb_execution_ https://github.com/ruby/ruby/blob/trunk/ujit_core.c#L380 ctx_t generic_ctx = DEFAULT_CTX; generic_ctx.stack_size = target_ctx->stack_size; generic_ctx.sp_offset = target_ctx->sp_offset; - if (count_block_versions(target) >= MAX_VERSIONS - 1) + if (get_num_versions(target) >= MAX_VERSIONS - 1) { fprintf(stderr, "version limit hit in branch_stub_hit\n"); target_ctx = &generic_ctx; @@ -559,7 +546,7 @@ void gen_direct_jump( https://github.com/ruby/ruby/blob/trunk/ujit_core.c#L546 ctx_t generic_ctx = DEFAULT_CTX; generic_ctx.stack_size = ctx->stack_size; generic_ctx.sp_offset = ctx->sp_offset; - if (count_block_versions(target0) >= MAX_VERSIONS - 1) + if (get_num_versions(target0) >= MAX_VERSIONS - 1) { fprintf(stderr, "version limit hit in gen_direct_jump\n"); ctx = &generic_ctx; @@ -658,6 +645,27 @@ ujit_free_block(block_t *block) https://github.com/ruby/ruby/blob/trunk/ujit_core.c#L645 free(block); } +// Remove a block version without reordering the version array +static bool +block_array_remove(rb_ujit_block_array_t block_array, block_t *block) +{ + block_t **element; + bool shifting = false; + rb_darray_foreach(block_array, idx, element) { + if (*element == block) { + shifting = true; + } + else if (shifting) { + rb_darray_set(block_array, idx - 1, *element); + } + } + + if (shifting) { + rb_darray_pop(block_array); + } + return shifting; +} + // Invalidate one specific block version void invalidate_block_version(block_t* block) @@ -667,24 +675,12 @@ invalidate_block_version(block_t* block) https://github.com/ruby/ruby/blob/trunk/ujit_core.c#L675 // fprintf(stderr, "invalidating block (%p, %d)\n", block->blockid.iseq, block->blockid.idx); // fprintf(stderr, "block=%p\n", block); - block_t *first_block = get_first_version(iseq, block->blockid.idx); - RUBY_ASSERT(first_block != NULL); - - // Remove references to this block - if (first_block == block) { - // Make the next block the new first version - rb_darray_set(iseq->body->ujit_blocks, block->blockid.idx, block->next); - } - else { - bool deleted = false; - for (block_t* cur = first_block; cur != NULL; cur = cur->next) { - if (cur->next == block) { - cur->next = cur->next->next; - break; - } - } - RUBY_ASSERT(deleted); - } + // Remove this block from the version array + rb_ujit_block_array_t versions = get_version_array(iseq, block->blockid.idx); + RUBY_ASSERT(rb_darray_size(versions) > 0); + RB_UNUSED_VAR(bool removed); + removed = block_array_remove(versions, block); + RUBY_ASSERT(removed); // Get a pointer to the generated code for this block uint8_t* code_ptr = cb_get_ptr(cb, block->start_pos); diff --git a/ujit_core.h b/ujit_core.h index bfd44b145e..ac7d02ae12 100644 --- a/ujit_core.h +++ b/ujit_core.h @@ -121,12 +121,6 @@ typedef struct ujit_block_version https://github.com/ruby/ruby/blob/trunk/ujit_core.h#L121 // Offsets for GC managed objects in the mainline code block int32_array_t gc_object_offsets; - // Next block version for this blockid (singly-linked list) - struct ujit_block_version *next; - - // Offsets for GC managed objects in the mainline code block - offset_array_t gc_object_offsets; - // GC managed objects that this block depend on struct { VALUE cc; diff --git a/ujit_iface.c b/ujit_iface.c index 2030501637..0d4e6c0fc9 100644 --- a/ujit_iface.c +++ b/ujit_iface.c @@ -379,12 +379,13 @@ ujit_blocks_for(VALUE mod, VALUE rb_iseq) https://github.com/ruby/ruby/blob/trunk/ujit_iface.c#L379 } const rb_iseq_t *iseq = rb_iseqw_to_iseq(rb_iseq); - block_t **element; - VALUE all_versions = rb_ary_new(); - rb_darray_foreach(iseq->body->ujit_blocks, idx, element) { - for (block_t *version = *element; version; version = version->next) { - VALUE rb_block = TypedData_Wrap_Struct(cUjitBlock, &ujit_block_type, version); + VALUE all_versions = rb_ary_new(); + rb_ujit_block_array_t *versions; + rb_darray_foreach(iseq->body->ujit_blocks, idx, versions) { + block_t **block; + rb_darray_foreach(*versions, idx, block) { + VALUE rb_block = TypedData_Wrap_Struct(cUjitBlock, &ujit_block_type, *block); rb_ary_push(all_versions, rb_block); } } @@ -679,9 +680,11 @@ rb_ujit_iseq_mark(const struct rb_iseq_constant_body *body) https://github.com/ruby/ruby/blob/trunk/ujit_iface.c#L680 { block_t **element; rb_darray_foreach(body->ujit_blocks, idx, element) { + + + for (block_t *block = *element; block; block = block->next) { rb_gc_mark_movable((VALUE)block->blockid.iseq); - rb_gc_mark_movable(block->dependencies.cc); rb_gc_mark_movable(block->dependencies.cme); rb_gc_mark_movable(block->dependencies.iseq); diff --git a/vm_core.h b/vm_core.h index e984be781e..184cc764c5 100644 --- a/vm_core.h +++ b/vm_core.h @@ -312,7 +312,9 @@ pathobj_realpath(VALUE pathobj) https://github.com/ruby/ruby/blob/trunk/vm_core.h#L312 /* Forward declarations */ struct rb_mjit_unit; +// List of YJIT block versions typedef rb_darray(struct ujit_block_version *) rb_ujit_block_array_t; +typedef rb_darray(rb_ujit_block_array_t) rb_ujit_block_array_array_t; struct rb_iseq_constant_body { enum iseq_type { @@ -45 (... truncated) -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/