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