vm/inline_cache.cpp

   1 #include "master.hpp"
   2
   3 namespace factor {
   4
   5 void factor_vm::deallocate_inline_cache(cell return_address) {
   6   // Find the call target.
   7   void* old_entry_point = get_call_target(return_address);
   8   code_block* old_block = (code_block*)old_entry_point - 1;
   9
  10   // Free the old PIC since we know its unreachable
  11   if (old_block->pic_p())
  12     code->free(old_block);
  13 }
  14
  15 // Figure out what kind of type check the PIC needs based on the methods
  16 // it contains
  17 static cell determine_inline_cache_type(array* cache_entries) {
  18   for (cell i = 0; i < array_capacity(cache_entries); i += 2) {
  19     // Is it a tuple layout?
  20     if (TAG(array_nth(cache_entries, i)) == ARRAY_TYPE) {
  21       return PIC_TUPLE;
  22     }
  23   }
  24   return PIC_TAG;
  25 }
  26
  27 void factor_vm::update_pic_count(cell type) {
  28   if (type == PIC_TAG)
  29     dispatch_stats.pic_tag_count++;
  30   else
  31     dispatch_stats.pic_tuple_count++;
  32 }
  33
  34 struct inline_cache_jit : public jit {
  35   inline_cache_jit(cell generic_word, factor_vm* vm)
  36       : jit(code_block_pic, generic_word, vm) {}
  37
  38   void emit_check_and_jump(cell ic_type, cell i, cell klass, cell method);
  39   void emit_inline_cache(fixnum index, cell generic_word_, cell methods_,
  40                          cell cache_entries_, bool tail_call_p);
  41 };
  42
  43 void inline_cache_jit::emit_check_and_jump(cell ic_type, cell i,
  44                                            cell klass, cell method) {
  45   // Class equal?
  46   cell check_type = PIC_CHECK_TAG;
  47   if (TAG(klass) != FIXNUM_TYPE)
  48       check_type = PIC_CHECK_TUPLE;
  49
  50   // The tag check can be skipped if it is the first one and we are
  51   // checking for the fixnum type which is 0. That is because the
  52   // AND instruction in the PIC_TAG template already sets the zero
  53   // flag.
  54   if (!(i == 0 && ic_type == PIC_TAG && klass == 0)) {
  55     emit_with_literal(parent->special_objects[check_type], klass);
  56   }
  57
  58   // Yes? Jump to method
  59   emit_with_literal(parent->special_objects[PIC_HIT], method);
  60 }
  61
  62 // index: 0 = top of stack, 1 = item underneath, etc
  63 // cache_entries: array of class/method pairs
  64 // Allocates memory
  65 void inline_cache_jit::emit_inline_cache(fixnum index, cell generic_word_,
  66                                          cell methods_, cell cache_entries_,
  67                                          bool tail_call_p) {
  68   data_root<word> generic_word(generic_word_, parent);
  69   data_root<array> methods(methods_, parent);
  70   data_root<array> cache_entries(cache_entries_, parent);
  71
  72   cell ic_type = determine_inline_cache_type(cache_entries.untagged());
  73   parent->update_pic_count(ic_type);
  74
  75   // Generate machine code to determine the object's class.
  76   emit_with_literal(parent->special_objects[PIC_LOAD],
  77                     tag_fixnum(-index * sizeof(cell)));
  78
  79   // Put the tag of the object, or class of the tuple in a register.
  80   emit(parent->special_objects[ic_type]);
  81
  82   // Generate machine code to check, in turn, if the class is one of the cached
  83   // entries.
  84   for (cell i = 0; i < array_capacity(cache_entries.untagged()); i += 2) {
  85     cell klass = array_nth(cache_entries.untagged(), i);
  86     cell method = array_nth(cache_entries.untagged(), i + 1);
  87
  88     emit_check_and_jump(ic_type, i, klass, 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.emit_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 }