https://git.ruby-lang.org/ruby.git/commit/?id=0cc73ca2a9

From 0cc73ca2a9a2aa5276cd022be9891475a15ecee3 Mon Sep 17 00:00:00 2001
From: Maxime Chevalier-Boisvert <maximechevalierb@g...>
Date: Mon, 19 Apr 2021 17:07:27 -0400
Subject: Malloc branch entries (#112)

* Malloc branch entries

* Add ASM comment for stack overflow check

* WIP

* Fix branch GC code. Add rb_darray_remove_unordered().

* Fix block end_pos after branch rewriting. Remove dst_patched bits.
---
 darray.h       |  10 +++
 yjit_codegen.c |   9 ++
 yjit_core.c    | 259 +++++++++++++++++++++++++++------------------------------
 yjit_core.h    |  21 +++--
 yjit_iface.c   |  29 +++++--
 5 files changed, 176 insertions(+), 152 deletions(-)

diff --git a/darray.h b/darray.h
index 71e2d7e6ce..b613d08489 100644
--- a/darray.h
+++ b/darray.h
@@ -51,10 +51,20 @@ https://github.com/ruby/ruby/blob/trunk/darray.h#L51
         1                                         \
     ) : 0)
 
+// Last element of the array
+//
+#define rb_darray_back(ary) ((ary)->data[(ary)->meta.size - 1])
+
 // Remove the last element of the array.
 //
 #define rb_darray_pop_back(ary) ((ary)->meta.size--)
 
+// Remove element at idx and replace it by the last element
+#define rb_darray_remove_unordered(ary, idx) do {   \
+    rb_darray_set(ary, idx, rb_darray_back(ary));   \
+    rb_darray_pop_back(ary);                        \
+} while (0);
+
 // Iterate over items of the array in a for loop
 //
 #define rb_darray_foreach(ary, idx_name, elem_ptr_var) \
diff --git a/yjit_codegen.c b/yjit_codegen.c
index 8d4cd02677..8cc3d5c8c8 100644
--- a/yjit_codegen.c
+++ b/yjit_codegen.c
@@ -301,6 +301,7 @@ jit_jump_to_next_insn(jitstate_t *jit, const ctx_t *current_context) https://github.com/ruby/ruby/blob/trunk/yjit_codegen.c#L301
 
     // Generate the jump instruction
     gen_direct_jump(
+        jit->block,
         &reset_depth,
         jump_block
     );
@@ -722,6 +723,7 @@ jit_chain_guard(enum jcc_kinds jcc, jitstate_t *jit, const ctx_t *ctx, uint8_t d https://github.com/ruby/ruby/blob/trunk/yjit_codegen.c#L723
         deeper.chain_depth++;
 
         gen_branch(
+            jit->block,
             ctx,
             (blockid_t) { jit->iseq, jit->insn_idx },
             &deeper,
@@ -1334,6 +1336,7 @@ gen_branchif(jitstate_t* jit, ctx_t* ctx) https://github.com/ruby/ruby/blob/trunk/yjit_codegen.c#L1336
 
     // Generate the branch instructions
     gen_branch(
+        jit->block,
         ctx,
         jump_block,
         ctx,
@@ -1387,6 +1390,7 @@ gen_branchunless(jitstate_t* jit, ctx_t* ctx) https://github.com/ruby/ruby/blob/trunk/yjit_codegen.c#L1390
 
     // Generate the branch instructions
     gen_branch(
+        jit->block,
         ctx,
         jump_block,
         ctx,
@@ -1412,6 +1416,7 @@ gen_jump(jitstate_t* jit, ctx_t* ctx) https://github.com/ruby/ruby/blob/trunk/yjit_codegen.c#L1416
 
     // Generate the jump instruction
     gen_direct_jump(
+        jit->block,
         ctx,
         jump_block
     );
@@ -1726,6 +1731,7 @@ gen_oswb_iseq(jitstate_t *jit, ctx_t *ctx, const struct rb_callinfo *ci, const r https://github.com/ruby/ruby/blob/trunk/yjit_codegen.c#L1731
 
     // Stack overflow check
     // #define CHECK_VM_STACK_OVERFLOW0(cfp, sp, margin)
+    ADD_COMMENT(cb, "stack overflow check");
     lea(cb, REG0, ctx_sp_opnd(ctx, sizeof(VALUE) * (num_locals + iseq->body->stack_max) + sizeof(rb_control_frame_t)));
     cmp(cb, REG_CFP, REG0);
     jle_ptr(cb, COUNTED_EXIT(side_exit, oswb_se_cf_overflow));
@@ -1802,6 +1808,7 @@ gen_oswb_iseq(jitstate_t *jit, ctx_t *ctx, const struct rb_callinfo *ci, const r https://github.com/ruby/ruby/blob/trunk/yjit_codegen.c#L1808
 
     // Write the JIT return address on the callee frame
     gen_branch(
+        jit->block,
         ctx,
         return_block,
         &return_ctx,
@@ -1818,6 +1825,7 @@ gen_oswb_iseq(jitstate_t *jit, ctx_t *ctx, const struct rb_callinfo *ci, const r https://github.com/ruby/ruby/blob/trunk/yjit_codegen.c#L1825
 
     // Directly jump to the entry point of the callee
     gen_direct_jump(
+        jit->block,
         &callee_ctx,
         (blockid_t){ iseq, 0 }
     );
@@ -2049,6 +2057,7 @@ gen_opt_getinlinecache(jitstate_t *jit, ctx_t *ctx) https://github.com/ruby/ruby/blob/trunk/yjit_codegen.c#L2057
     // Jump over the code for filling the cache
     uint32_t jump_idx = jit_next_insn_idx(jit) + (int32_t)jump_offset;
     gen_direct_jump(
+        jit->block,
         ctx,
         (blockid_t){ .iseq = jit->iseq, .idx = jump_idx }
     );
diff --git a/yjit_core.c b/yjit_core.c
index 2584714f7a..56450840cd 100644
--- a/yjit_core.c
+++ b/yjit_core.c
@@ -12,13 +12,6 @@ https://github.com/ruby/ruby/blob/trunk/yjit_core.c#L12
 // Maximum number of versions per block
 #define MAX_VERSIONS 4
 
-// Maximum number of branch instructions we can track
-#define MAX_BRANCHES 250000
-
-// Registered branch entries
-branch_t branch_entries[MAX_BRANCHES];
-uint32_t num_branches = 0;
-
 /*
 Get an operand for the adjusted stack pointer address
 */
@@ -385,6 +378,26 @@ add_block_version(blockid_t blockid, block_t* block) https://github.com/ruby/ruby/blob/trunk/yjit_core.c#L378
     }
 }
 
+// Create a new outgoing branch entry for a block
+static branch_t*
+make_branch_entry(block_t* block, const ctx_t* src_ctx, branchgen_fn gen_fn)
+{
+    RUBY_ASSERT(block != NULL);
+
+    // Allocate and zero-initialize
+    branch_t* branch = calloc(1, sizeof(branch_t));
+
+    branch->block = block;
+    branch->src_ctx = *src_ctx;
+    branch->gen_fn = gen_fn;
+    branch->shape = SHAPE_DEFAULT;
+
+    // Add to the list of outgoing branches for the block
+    rb_darray_append(&block->outgoing, branch);
+
+    return branch;
+}
+
 // Retrieve a basic block version for an (iseq, idx) tuple
 block_t* find_block_version(blockid_t blockid, const ctx_t* ctx)
 {
@@ -410,15 +423,6 @@ block_t* find_block_version(blockid_t blockid, const ctx_t* ctx) https://github.com/ruby/ruby/blob/trunk/yjit_core.c#L423
     return best_version;
 }
 
-void
-yjit_branches_update_references(void)
-{
-    for (uint32_t i = 0; i < num_branches; i++) {
-        branch_entries[i].targets[0].iseq = (const void *)rb_gc_location((VALUE)branch_entries[i].targets[0].iseq);
-        branch_entries[i].targets[1].iseq = (const void *)rb_gc_location((VALUE)branch_entries[i].targets[1].iseq);
-    }
-}
-
 // Compile a new block version immediately
 block_t* gen_block_version(blockid_t blockid, const ctx_t* start_ctx, rb_execution_context_t* ec)
 {
@@ -442,14 +446,13 @@ block_t* gen_block_version(blockid_t blockid, const ctx_t* start_ctx, rb_executi https://github.com/ruby/ruby/blob/trunk/yjit_core.c#L446
 
     // For each successor block to compile
     for (;;) {
-        // If no branches were generated, stop
-        if (num_branches == 0) {
+        // If the previous block compiled doesn't have outgoing branches, stop
+        if (rb_darray_size(block->outgoing) == 0) {
             break;
         }
 
-        // Get the last branch entry
-        uint32_t branch_idx = num_branches - 1;
-        branch_t* last_branch = &branch_entries[num_branches - 1];
+        // Get the last outgoing branch from the previous block
+        branch_t* last_branch = rb_darray_back(block->outgoing);
 
         // If there is no next block to compile, stop
         if (last_branch->dst_addrs[0] || last_branch->dst_addrs[1]) {
@@ -476,7 +479,8 @@ block_t* gen_block_version(blockid_t blockid, const ctx_t* start_ctx, rb_executi https://github.com/ruby/ruby/blob/trunk/yjit_core.c#L479
 
         // Patch the last branch address
         last_branch->dst_addrs[0] = cb_get_ptr(cb, block->start_pos);
-        rb_darray_append(&block->incoming, branch_idx);
+        rb_darray_append(&block->incoming, last_branch);
+        last_branch->blocks[0] = block;
 
         RUBY_ASSERT(block->start_pos == last_branch->end_pos);
     }
@@ -508,7 +512,7 @@ uint8_t* gen_entry_point(const rb_iseq_t *iseq, uint32_t insn_idx, rb_execution_ https://github.com/ruby/ruby/blob/trunk/yjit_core.c#L512
 // Called by the generated code when a branch stub is executed
 // Triggers compilation of branches and code patching
 static uint8_t *
-branch_stub_hit(const uint32_t branch_idx, const uint32_t target_idx, rb_execution_context_t* ec)
+branch_stub_hit(branch_t* branch, const uint32_t target_idx, rb_execution_context_t* ec)
 {
     uint8_t* dst_addr;
     ctx_t generic_ctx;
@@ -518,20 +522,19 @@ branch_stub_hit(const uint32_t branch_idx, const uint32_t target_idx, rb_executi https://github.com/ruby/ruby/blob/trunk/yjit_core.c#L522
     RB_VM_LOCK_ENTER();
     rb_vm_barrier();
 
-    RUBY_ASSERT(branch_idx < num_branches);
+    RUBY_ASSERT(branch != NULL);
     RUBY_ASSERT(target_idx < 2);
-    branch_t *branch = &branch_entries[branch_idx];
     blockid_t target = branch->targets[target_idx];
     const ctx_t* target_ctx = &branch->target_ctxs[target_idx];
 
     // If this branch has already been patched, return the dst address
     // Note: ractors can cause the same stub to be hit multiple times
-    if (branch->dst_patched & (1 << target_idx)) {
-        dst_addr =  branch->dst_addrs[target_idx];
+    if (branch->blocks[target_idx]) {
+        dst_addr = branch->dst_addrs[target_idx];
     }
     else
     {
-        //fprintf(stderr, "\nstub hit, branch idx: %d, target idx: %d\n", branch_idx, target_idx);
+        //fprintf(stderr, "\nstub hit, branch: %p, target idx: %d\n", branch, target_idx);
         //fprintf(stderr, "blockid.iseq=%p, blockid.idx=%d\n", target.iseq, target.idx);
         //fprintf(stderr, "chain_depth=%d\n", target_ctx->chain_depth);
 
@@ -566,6 +569,9 @@ branch_stub_hit(const uint32_t branch_idx, const uint32_t target_idx, rb_executi https://github.com/ruby/ruby/blob/trunk/yjit_core.c#L569
 
             // If the new block can be generated right after the branch (at cb->write_pos)
             if (cb->write_pos == branch->end_pos) {
+                // This branch should be terminating its block
+                RUBY_ (... truncated)

--
ML: ruby-changes@q...
Info: http://www.atdot.net/~ko1/quickml/