vm/dispatch.cpp

   1 #include "master.hpp"
   2
   3 namespace factor
   4 {
   5
   6 cell megamorphic_cache_hits;
   7 cell megamorphic_cache_misses;
   8
   9 static cell search_lookup_alist(cell table, cell klass)
  10 {
  11         array *elements = untag<array>(table);
  12         fixnum index = array_capacity(elements) - 2;
  13         while(index >= 0)
  14         {
  15                 if(array_nth(elements,index) == klass)
  16                         return array_nth(elements,index + 1);
  17                 else
  18                         index -= 2;
  19         }
  20
  21         return F;
  22 }
  23
  24 static cell search_lookup_hash(cell table, cell klass, cell hashcode)
  25 {
  26         array *buckets = untag<array>(table);
  27         cell bucket = array_nth(buckets,hashcode & (array_capacity(buckets) - 1));
  28         if(tagged<object>(bucket).type_p(WORD_TYPE) || bucket == F)
  29                 return bucket;
  30         else
  31                 return search_lookup_alist(bucket,klass);
  32 }
  33
  34 static cell nth_superclass(tuple_layout *layout, fixnum echelon)
  35 {
  36         cell *ptr = (cell *)(layout + 1);
  37         return ptr[echelon * 2];
  38 }
  39
  40 static cell nth_hashcode(tuple_layout *layout, fixnum echelon)
  41 {
  42         cell *ptr = (cell *)(layout + 1);
  43         return ptr[echelon * 2 + 1];
  44 }
  45
  46 static cell lookup_tuple_method(cell obj, cell methods)
  47 {
  48         tuple_layout *layout = untag<tuple_layout>(untag<tuple>(obj)->layout);
  49
  50         array *echelons = untag<array>(methods);
  51
  52         fixnum echelon = untag_fixnum(layout->echelon);
  53         fixnum max_echelon = array_capacity(echelons) - 1;
  54         if(echelon > max_echelon) echelon = max_echelon;
  55
  56         while(echelon >= 0)
  57         {
  58                 cell echelon_methods = array_nth(echelons,echelon);
  59
  60                 if(tagged<object>(echelon_methods).type_p(WORD_TYPE))
  61                         return echelon_methods;
  62                 else if(echelon_methods != F)
  63                 {
  64                         cell klass = nth_superclass(layout,echelon);
  65                         cell hashcode = untag_fixnum(nth_hashcode(layout,echelon));
  66                         cell result = search_lookup_hash(echelon_methods,klass,hashcode);
  67                         if(result != F)
  68                                 return result;
  69                 }
  70
  71                 echelon--;
  72         }
  73
  74         critical_error("Cannot find tuple method",methods);
  75         return F;
  76 }
  77
  78 static cell lookup_hi_tag_method(cell obj, cell methods)
  79 {
  80         array *hi_tag_methods = untag<array>(methods);
  81         cell tag = untag<object>(obj)->h.hi_tag() - HEADER_TYPE;
  82 #ifdef FACTOR_DEBUG
  83         assert(tag < TYPE_COUNT - HEADER_TYPE);
  84 #endif
  85         return array_nth(hi_tag_methods,tag);
  86 }
  87
  88 static cell lookup_hairy_method(cell obj, cell methods)
  89 {
  90         cell method = array_nth(untag<array>(methods),TAG(obj));
  91         if(tagged<object>(method).type_p(WORD_TYPE))
  92                 return method;
  93         else
  94         {
  95                 switch(TAG(obj))
  96                 {
  97                 case TUPLE_TYPE:
  98                         return lookup_tuple_method(obj,method);
  99                         break;
 100                 case OBJECT_TYPE:
 101                         return lookup_hi_tag_method(obj,method);
 102                         break;
 103                 default:
 104                         critical_error("Bad methods array",methods);
 105                         return 0;
 106                 }
 107         }
 108 }
 109
 110 cell lookup_method(cell obj, cell methods)
 111 {
 112         cell tag = TAG(obj);
 113         if(tag == TUPLE_TYPE || tag == OBJECT_TYPE)
 114                 return lookup_hairy_method(obj,methods);
 115         else
 116                 return array_nth(untag<array>(methods),TAG(obj));
 117 }
 118
 119 PRIMITIVE(lookup_method)
 120 {
 121         cell methods = dpop();
 122         cell obj = dpop();
 123         dpush(lookup_method(obj,methods));
 124 }
 125
 126 cell object_class(cell obj)
 127 {
 128         switch(TAG(obj))
 129         {
 130         case TUPLE_TYPE:
 131                 return untag<tuple>(obj)->layout;
 132         case OBJECT_TYPE:
 133                 return untag<object>(obj)->h.value;
 134         default:
 135                 return tag_fixnum(TAG(obj));
 136         }
 137 }
 138
 139 static cell method_cache_hashcode(cell klass, array *array)
 140 {
 141         cell capacity = (array_capacity(array) >> 1) - 1;
 142         return ((klass >> TAG_BITS) & capacity) << 1;
 143 }
 144
 145 static void update_method_cache(cell cache, cell klass, cell method)
 146 {
 147         array *cache_elements = untag<array>(cache);
 148         cell hashcode = method_cache_hashcode(klass,cache_elements);
 149         set_array_nth(cache_elements,hashcode,klass);
 150         set_array_nth(cache_elements,hashcode + 1,method);
 151 }
 152
 153 PRIMITIVE(mega_cache_miss)
 154 {
 155         megamorphic_cache_misses++;
 156
 157         cell cache = dpop();
 158         fixnum index = untag_fixnum(dpop());
 159         cell methods = dpop();
 160
 161         cell object = ((cell *)ds)[-index];
 162         cell klass = object_class(object);
 163         cell method = lookup_method(object,methods);
 164
 165         update_method_cache(cache,klass,method);
 166
 167         dpush(method);
 168 }
 169
 170 PRIMITIVE(reset_dispatch_stats)
 171 {
 172         megamorphic_cache_hits = megamorphic_cache_misses = 0;
 173 }
 174
 175 PRIMITIVE(dispatch_stats)
 176 {
 177         growable_array stats;
 178         stats.add(allot_cell(megamorphic_cache_hits));
 179         stats.add(allot_cell(megamorphic_cache_misses));
 180         stats.trim();
 181         dpush(stats.elements.value());
 182 }
 183
 184 void quotation_jit::emit_mega_cache_lookup(cell methods_, fixnum index, cell cache_)
 185 {
 186         gc_root<array> methods(methods_);
 187         gc_root<array> cache(cache_);
 188
 189         /* Generate machine code to determine the object's class. */
 190         emit_class_lookup(index,PIC_HI_TAG_TUPLE);
 191
 192         /* Do a cache lookup. */
 193         emit_with(userenv[MEGA_LOOKUP],cache.value());
 194
 195         /* If we end up here, the cache missed. */
 196         emit(userenv[JIT_PROLOG]);
 197
 198         /* Push index, method table and cache on the stack. */
 199         push(methods.value());
 200         push(tag_fixnum(index));
 201         push(cache.value());
 202         word_call(userenv[MEGA_MISS_WORD]);
 203
 204         /* Now the new method has been stored into the cache, and its on
 205            the stack. */
 206         emit(userenv[JIT_EPILOG]);
 207         emit(userenv[JIT_EXECUTE_JUMP]);
 208 }
 209
 210 }