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         gc_root<word> generic_word(generic_word_,parent);
  87         gc_root<array> methods(methods_,parent);
  88         gc_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,cell generic_word_,cell methods_,cell cache_entries_,bool tail_call_p)
 122 {
 123         gc_root<word> generic_word(generic_word_,this);
 124         gc_root<array> methods(methods_,this);
 125         gc_root<array> cache_entries(cache_entries_,this);
 126
 127         inline_cache_jit jit(generic_word.value(),this);
 128         jit.compile_inline_cache(index,
 129                                  generic_word.value(),
 130                                  methods.value(),
 131                                  cache_entries.value(),
 132                                  tail_call_p);
 133         code_block *code = jit.to_code_block();
 134         relocate_code_block(code);
 135         return code;
 136 }
 137
 138 /* A generic word's definition performs general method lookup. Allocates memory */
 139 void *factor_vm::megamorphic_call_stub(cell generic_word)
 140 {
 141         return untag<word>(generic_word)->xt;
 142 }
 143
 144 cell factor_vm::inline_cache_size(cell cache_entries)
 145 {
 146         return array_capacity(untag_check<array>(cache_entries)) / 2;
 147 }
 148
 149 /* Allocates memory */
 150 cell factor_vm::add_inline_cache_entry(cell cache_entries_, cell klass_, cell method_)
 151 {
 152         gc_root<array> cache_entries(cache_entries_,this);
 153         gc_root<object> klass(klass_,this);
 154         gc_root<word> method(method_,this);
 155
 156         cell pic_size = array_capacity(cache_entries.untagged());
 157         gc_root<array> new_cache_entries(reallot_array(cache_entries.untagged(),pic_size + 2),this);
 158         set_array_nth(new_cache_entries.untagged(),pic_size,klass.value());
 159         set_array_nth(new_cache_entries.untagged(),pic_size + 1,method.value());
 160         return new_cache_entries.value();
 161 }
 162
 163 void factor_vm::update_pic_transitions(cell pic_size)
 164 {
 165         if(pic_size == max_pic_size)
 166                 pic_to_mega_transitions++;
 167         else if(pic_size == 0)
 168                 cold_call_to_ic_transitions++;
 169         else if(pic_size == 1)
 170                 ic_to_pic_transitions++;
 171 }
 172
 173 /* The cache_entries parameter is either f (on cold call site) or an array (on cache miss).
 174 Called from assembly with the actual return address */
 175 void *factor_vm::inline_cache_miss(cell return_address)
 176 {
 177         check_code_pointer(return_address);
 178
 179         /* Since each PIC is only referenced from a single call site,
 180            if the old call target was a PIC, we can deallocate it immediately,
 181            instead of leaving dead PICs around until the next GC. */
 182         deallocate_inline_cache(return_address);
 183
 184         gc_root<array> cache_entries(dpop(),this);
 185         fixnum index = untag_fixnum(dpop());
 186         gc_root<array> methods(dpop(),this);
 187         gc_root<word> generic_word(dpop(),this);
 188         gc_root<object> object(((cell *)ds)[-index],this);
 189
 190         void *xt;
 191
 192         cell pic_size = inline_cache_size(cache_entries.value());
 193
 194         update_pic_transitions(pic_size);
 195
 196         if(pic_size >= max_pic_size)
 197                 xt = megamorphic_call_stub(generic_word.value());
 198         else
 199         {
 200                 cell klass = object_class(object.value());
 201                 cell method = lookup_method(object.value(),methods.value());
 202
 203                 gc_root<array> new_cache_entries(add_inline_cache_entry(
 204                                                            cache_entries.value(),
 205                                                            klass,
 206                                                            method),this);
 207                 xt = compile_inline_cache(index,
 208                                           generic_word.value(),
 209                                           methods.value(),
 210                                           new_cache_entries.value(),
 211                                           tail_call_site_p(return_address))->xt();
 212         }
 213
 214         /* Install the new stub. */
 215         set_call_target(return_address,xt);
 216
 217 #ifdef PIC_DEBUG
 218         std::cout << "Updated "
 219                 << (tail_call_site_p(return_address) ? "tail" : "non-tail")
 220                 << " call site 0x" << std::hex << return_address << std::dec
 221                 << " with " << std::hex << (cell)xt << std::dec;
 222 #endif
 223
 224         return xt;
 225 }
 226
 227 VM_C_API void *inline_cache_miss(cell return_address, factor_vm *parent)
 228 {
 229         return parent->inline_cache_miss(return_address);
 230 }
 231
 232 void factor_vm::primitive_reset_inline_cache_stats()
 233 {
 234         cold_call_to_ic_transitions = ic_to_pic_transitions = pic_to_mega_transitions = 0;
 235         pic_counts[0] = 0;
 236         pic_counts[1] = 0;
 237 }
 238
 239 void factor_vm::primitive_inline_cache_stats()
 240 {
 241         growable_array stats(this);
 242         stats.add(allot_cell(cold_call_to_ic_transitions));
 243         stats.add(allot_cell(ic_to_pic_transitions));
 244         stats.add(allot_cell(pic_to_mega_transitions));
 245         stats.add(allot_cell(pic_counts[0]));
 246         stats.add(allot_cell(pic_counts[1]));
 247         stats.trim();
 248         dpush(stats.elements.value());
 249 }
 250
 251 }