vm/inline_cache.cpp

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