From 7de8ce4efcfd23515d4e4b6a6f80e142438df758 Mon Sep 17 00:00:00 2001 From: Alan Wu Date: Thu, 4 Mar 2021 15:31:37 -0500 Subject: YJIT: Use 2D array to group block versions For deferred compilation, we sometimes want to care about the order of the block versions. Use an array instead of a linked list to do that. --- darray.h | 5 +++++ ujit_core.c | 45 +++++++++++++++++++-------------------------- ujit_iface.c | 42 ++++++++++++++++++++++++------------------ 3 files changed, 48 insertions(+), 44 deletions(-) diff --git a/darray.h b/darray.h index d3ffc88131..a86132d59a 100644 --- a/darray.h +++ b/darray.h @@ -60,6 +60,11 @@ #define rb_darray_foreach(ary, idx_name, elem_ptr_var) \ for (int idx_name = 0; idx_name < rb_darray_size(ary) && ((elem_ptr_var) = rb_darray_ref(ary, idx_name)); ++idx_name) +// Iterate over valid indicies in the array in a for loop +// +#define rb_darray_for(ary, idx_name) \ + for (int idx_name = 0; idx_name < rb_darray_size(ary); ++idx_name) + // Make a dynamic array of a certain size. All bytes backing the elements are set to zero. // Return 1 on success and 0 on failure. // diff --git a/ujit_core.c b/ujit_core.c index c4db19de70..651046cc55 100644 --- a/ujit_core.c +++ b/ujit_core.c @@ -144,6 +144,7 @@ int ctx_diff(const ctx_t* src, const ctx_t* dst) return diff; } +// Get all blocks for a particular place in an iseq. static rb_ujit_block_array_t get_version_array(const rb_iseq_t *iseq, unsigned idx) { @@ -189,19 +190,14 @@ add_block_version(blockid_t blockid, block_t* block) #endif } - block_t *first_version = get_first_version(iseq, blockid.idx); + RUBY_ASSERT((int32_t)blockid.idx < rb_darray_size(body->ujit_blocks)); + rb_ujit_block_array_t *block_array_ref = rb_darray_ref(body->ujit_blocks, blockid.idx); - // If there exists a version for this block id - if (first_version != NULL) { - // Link to the next version in a linked list - RUBY_ASSERT(block->next == NULL); - block->next = first_version; + // Add the new block + if (!rb_darray_append(block_array_ref, block)) { + rb_bug("allocation failed"); } - // Make new block the first version - rb_darray_set(body->ujit_blocks, blockid.idx, block); - RUBY_ASSERT(find_block_version(blockid, &block->ctx) != NULL); - { // By writing the new block to the iseq, the iseq now // contains new references to Ruby objects. Run write barriers. @@ -225,17 +221,16 @@ add_block_version(blockid_t blockid, block_t* block) // Retrieve a basic block version for an (iseq, idx) tuple block_t* find_block_version(blockid_t blockid, const ctx_t* ctx) { - rb_ujit_block_array_t versions = get_version_array(iseq, block->blockid.idx); + rb_ujit_block_array_t versions = get_version_array(blockid.iseq, blockid.idx); // Best match found block_t* best_version = NULL; int best_diff = INT_MAX; // For each version matching the blockid - block_t **element; - rb_darray_foreach(versions, idx, element) { - block_t *version = *element; - int diff = ctx_diff(ctx, version->ctx); + rb_darray_for(versions, idx) { + block_t *version = rb_darray_get(versions, idx); + int diff = ctx_diff(ctx, &version->ctx); // Note that we always prefer the first matching // version because of inline-cache chains @@ -649,21 +644,20 @@ ujit_free_block(block_t *block) static bool block_array_remove(rb_ujit_block_array_t block_array, block_t *block) { + bool after_target = false; block_t **element; - bool shifting = false; rb_darray_foreach(block_array, idx, element) { - if (*element == block) { - shifting = true; - } - else if (shifting) { + if (after_target) { rb_darray_set(block_array, idx - 1, *element); } + else if (*element == block) { + after_target = true; + } } - if (shifting) { - rb_darray_pop(block_array); - } - return shifting; + if (after_target) rb_darray_pop_back(block_array); + + return after_target; } // Invalidate one specific block version @@ -677,7 +671,6 @@ invalidate_block_version(block_t* block) // 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); @@ -736,7 +729,7 @@ invalidate_block_version(block_t* block) // Should check how it's used in exit and side-exit const void * const *handler_table = rb_vm_get_insns_address_table(); void* handler_addr = (void*)handler_table[entry_opcode]; - iseq->body->iseq_encoded[idx] = (VALUE)handler_addr; + iseq->body->iseq_encoded[idx] = (VALUE)handler_addr; // TODO: // May want to recompile a new entry point (for interpreter entry blocks) diff --git a/ujit_iface.c b/ujit_iface.c index 0d4e6c0fc9..54e8897d3b 100644 --- a/ujit_iface.c +++ b/ujit_iface.c @@ -381,11 +381,13 @@ ujit_blocks_for(VALUE mod, VALUE rb_iseq) const rb_iseq_t *iseq = rb_iseqw_to_iseq(rb_iseq); 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_darray_for(iseq->body->ujit_blocks, version_array_idx) { + rb_ujit_block_array_t versions = rb_darray_get(iseq->body->ujit_blocks, version_array_idx); + + rb_darray_for(versions, block_idx) { + block_t *block = rb_darray_get(versions, block_idx); + + VALUE rb_block = TypedData_Wrap_Struct(cUjitBlock, &ujit_block_type, block); rb_ary_push(all_versions, rb_block); } } @@ -678,12 +680,12 @@ print_ujit_stats(void) void rb_ujit_iseq_mark(const struct rb_iseq_constant_body *body) { - block_t **element; - rb_darray_foreach(body->ujit_blocks, idx, element) { + rb_darray_for(body->ujit_blocks, version_array_idx) { + rb_ujit_block_array_t version_array = rb_darray_get(body->ujit_blocks, version_array_idx); + rb_darray_for(version_array, block_idx) { + block_t *block = rb_darray_get(version_array, block_idx); - - 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); @@ -706,9 +708,12 @@ rb_ujit_iseq_mark(const struct rb_iseq_constant_body *body) void rb_ujit_iseq_update_references(const struct rb_iseq_constant_body *body) { - block_t **element; - rb_darray_foreach(body->ujit_blocks, idx, element) { - for (block_t *block = *element; block; block = block->next) { + rb_darray_for(body->ujit_blocks, version_array_idx) { + rb_ujit_block_array_t version_array = rb_darray_get(body->ujit_blocks, version_array_idx); + + rb_darray_for(version_array, block_idx) { + block_t *block = rb_darray_get(version_array, block_idx); + block->blockid.iseq = (const rb_iseq_t *)rb_gc_location((VALUE)block->blockid.iseq); block->dependencies.cc = rb_gc_location(block->dependencies.cc); @@ -736,14 +741,15 @@ rb_ujit_iseq_update_references(const struct rb_iseq_constant_body *body) void rb_ujit_iseq_free(const struct rb_iseq_constant_body *body) { - block_t **element; - rb_darray_foreach(body->ujit_blocks, idx, element) { - block_t *block = *element; - while (block) { - block_t *next = block->next; + rb_darray_for(body->ujit_blocks, version_array_idx) { + rb_ujit_block_array_t version_array = rb_darray_get(body->ujit_blocks, version_array_idx); + + rb_darray_for(version_array, block_idx) { + block_t *block = rb_darray_get(version_array, block_idx); ujit_free_block(block); - block = next; } + + rb_darray_free(version_array); } rb_darray_free(body->ujit_blocks); -- cgit v1.2.1