vm/inline_cache.cpp

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