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