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