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