vm/inline_cache.cpp

   1 #include "master.hpp"
   2
   3 namespace factor {
   4
   5 void factor_vm::init_inline_caching(int max_size) { max_pic_size = max_size; }
   6
   7 void factor_vm::deallocate_inline_cache(cell return_address) {
   8   /* Find the call target. */
   9   void* old_entry_point = get_call_target(return_address);
  10   code_block* old_block = (code_block*)old_entry_point - 1;
  11
  12   /* Free the old PIC since we know its unreachable */
  13   if (old_block->pic_p())
  14     code->free(old_block);
  15 }
  16
  17 /* Figure out what kind of type check the PIC needs based on the methods
  18    it contains */
  19 cell factor_vm::determine_inline_cache_type(array* cache_entries) {
  20   bool seen_tuple = false;
  21
  22   cell i;
  23   for (i = 0; i < array_capacity(cache_entries); i += 2) {
  24     /* Is it a tuple layout? */
  25     if (TAG(array_nth(cache_entries, i)) == ARRAY_TYPE) {
  26       seen_tuple = true;
  27       break;
  28     }
  29   }
  30
  31   return seen_tuple ? PIC_TUPLE : PIC_TAG;
  32 }
  33
  34 void factor_vm::update_pic_count(cell type) {
  35   if (type == PIC_TAG)
  36     dispatch_stats.pic_tag_count++;
  37   else
  38     dispatch_stats.pic_tuple_count++;
  39 }
  40
  41 struct inline_cache_jit : public jit {
  42   fixnum index;
  43
  44   inline_cache_jit(cell generic_word, factor_vm* vm)
  45       : jit(code_block_pic, generic_word, vm) {}
  46   ;
  47
  48   void emit_check(cell klass);
  49   void compile_inline_cache(fixnum index, cell generic_word_, cell methods_,
  50                             cell cache_entries_, bool tail_call_p);
  51 };
  52
  53 /* Allocates memory */
  54 void inline_cache_jit::emit_check(cell klass) {
  55   cell code_template;
  56   if (TAG(klass) == FIXNUM_TYPE)
  57     code_template = parent->special_objects[PIC_CHECK_TAG];
  58   else
  59     code_template = parent->special_objects[PIC_CHECK_TUPLE];
  60
  61   emit_with_literal(code_template, klass);
  62 }
  63
  64 /* index: 0 = top of stack, 1 = item underneath, etc
  65    cache_entries: array of class/method pairs */
  66 /* Allocates memory */
  67 void inline_cache_jit::compile_inline_cache(fixnum index, cell generic_word_,
  68                                             cell methods_, cell cache_entries_,
  69                                             bool tail_call_p) {
  70   data_root<word> generic_word(generic_word_, parent);
  71   data_root<array> methods(methods_, parent);
  72   data_root<array> cache_entries(cache_entries_, parent);
  73
  74   cell inline_cache_type =
  75       parent->determine_inline_cache_type(cache_entries.untagged());
  76   parent->update_pic_count(inline_cache_type);
  77
  78   /* Generate machine code to determine the object's class. */
  79   emit_with_literal(parent->special_objects[PIC_LOAD],
  80                     tag_fixnum(-index * sizeof(cell)));
  81   emit(parent->special_objects[inline_cache_type]);
  82
  83   /* Generate machine code to check, in turn, if the class is one of the cached
  84    * entries. */
  85   cell i;
  86   for (i = 0; i < array_capacity(cache_entries.untagged()); i += 2) {
  87     /* Class equal? */
  88     cell klass = array_nth(cache_entries.untagged(), i);
  89     emit_check(klass);
  90
  91     /* Yes? Jump to method */
  92     cell method = array_nth(cache_entries.untagged(), i + 1);
  93     emit_with_literal(parent->special_objects[PIC_HIT], method);
  94   }
  95
  96   /* If none of the above conditionals tested true, then execution "falls
  97      through" to here. */
  98
  99   /* A stack frame is set up, since the inline-cache-miss sub-primitive
 100      makes a subroutine call to the VM. */
 101   emit(parent->special_objects[JIT_PROLOG]);
 102
 103   /* The inline-cache-miss sub-primitive call receives enough information to
 104      reconstruct the PIC with the new entry. */
 105   push(generic_word.value());
 106   push(methods.value());
 107   push(tag_fixnum(index));
 108   push(cache_entries.value());
 109
 110   emit_subprimitive(
 111       parent->special_objects[tail_call_p ? PIC_MISS_TAIL_WORD : PIC_MISS_WORD],
 112       true,  /* tail_call_p */
 113       true); /* stack_frame_p */
 114 }
 115
 116 /* Allocates memory */
 117 code_block* factor_vm::compile_inline_cache(fixnum index, cell generic_word_,
 118                                             cell methods_, cell cache_entries_,
 119                                             bool tail_call_p) {
 120   data_root<word> generic_word(generic_word_, this);
 121   data_root<array> methods(methods_, this);
 122   data_root<array> cache_entries(cache_entries_, this);
 123
 124   inline_cache_jit jit(generic_word.value(), this);
 125   jit.compile_inline_cache(index, generic_word.value(), methods.value(),
 126                            cache_entries.value(), tail_call_p);
 127   code_block* code = jit.to_code_block(JIT_FRAME_SIZE);
 128   initialize_code_block(code);
 129   return code;
 130 }
 131
 132 cell factor_vm::inline_cache_size(cell cache_entries) {
 133   return array_capacity(untag_check<array>(cache_entries)) / 2;
 134 }
 135
 136 /* Allocates memory */
 137 cell factor_vm::add_inline_cache_entry(cell cache_entries_, cell klass_,
 138                                        cell method_) {
 139   data_root<array> cache_entries(cache_entries_, this);
 140   data_root<object> klass(klass_, this);
 141   data_root<word> method(method_, this);
 142
 143   cell pic_size = array_capacity(cache_entries.untagged());
 144   data_root<array> new_cache_entries(
 145       reallot_array(cache_entries.untagged(), pic_size + 2), this);
 146   set_array_nth(new_cache_entries.untagged(), pic_size, klass.value());
 147   set_array_nth(new_cache_entries.untagged(), pic_size + 1, method.value());
 148   return new_cache_entries.value();
 149 }
 150
 151 void factor_vm::update_pic_transitions(cell pic_size) {
 152   if (pic_size == max_pic_size)
 153     dispatch_stats.pic_to_mega_transitions++;
 154   else if (pic_size == 0)
 155     dispatch_stats.cold_call_to_ic_transitions++;
 156   else if (pic_size == 1)
 157     dispatch_stats.ic_to_pic_transitions++;
 158 }
 159
 160 /* The cache_entries parameter is empty (on cold call site) or has entries
 161    (on cache miss). Called from assembly with the actual return address.
 162    Compilation of the inline cache may trigger a GC, which may trigger a
 163    compaction;
 164    also, the block containing the return address may now be dead. Use a
 165    code_root to take care of the details. */
 166 /* Allocates memory */
 167 cell factor_vm::inline_cache_miss(cell return_address_) {
 168   code_root return_address(return_address_, this);
 169   bool tail_call_site = tail_call_site_p(return_address.value);
 170
 171 #ifdef PIC_DEBUG
 172   FACTOR_PRINT("Inline cache miss at "
 173                << (tail_call_site ? "tail" : "non-tail")
 174                << " call site 0x" << std::hex << return_address.value
 175                << std::dec);
 176   print_callstack();
 177 #endif
 178
 179   data_root<array> cache_entries(ctx->pop(), this);
 180   fixnum index = untag_fixnum(ctx->pop());
 181   data_root<array> methods(ctx->pop(), this);
 182   data_root<word> generic_word(ctx->pop(), this);
 183   data_root<object> object(((cell*)ctx->datastack)[-index], this);
 184
 185   cell pic_size = inline_cache_size(cache_entries.value());
 186
 187   update_pic_transitions(pic_size);
 188
 189   cell xt;
 190
 191   if (pic_size >= max_pic_size)
 192     xt = generic_word->entry_point;
 193   else {
 194     cell klass = object_class(object.value());
 195     cell method = lookup_method(object.value(), methods.value());
 196
 197     data_root<array> new_cache_entries(
 198         add_inline_cache_entry(cache_entries.value(), klass, method), this);
 199
 200     xt = compile_inline_cache(index, generic_word.value(), methods.value(),
 201                               new_cache_entries.value(), tail_call_site)
 202         ->entry_point();
 203   }
 204
 205   /* Install the new stub. */
 206   if (return_address.valid) {
 207     /* Since each PIC is only referenced from a single call site,
 208        if the old call target was a PIC, we can deallocate it immediately,
 209        instead of leaving dead PICs around until the next GC. */
 210     deallocate_inline_cache(return_address.value);
 211     set_call_target(return_address.value, xt);
 212
 213 #ifdef PIC_DEBUG
 214     FACTOR_PRINT("Updated " << (tail_call_site ? "tail" : "non-tail")
 215                  << " call site 0x" << std::hex << return_address.value << std::dec
 216                  << " with 0x" << std::hex << (cell)xt << std::dec);
 217     print_callstack();
 218 #endif
 219   }
 220
 221   return xt;
 222 }
 223
 224 /* Allocates memory */
 225 VM_C_API cell inline_cache_miss(cell return_address, factor_vm* parent) {
 226   return parent->inline_cache_miss(return_address);
 227 }
 228
 229 }