vm/inline_cache.cpp

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