vm/quotations.cpp

   1 #include "master.hpp"
   2
   3 namespace factor {
   4
   5 // Simple non-optimizing compiler.
   6
   7 // This is one of the two compilers implementing Factor; the second one is
   8 // written in Factor and performs advanced optimizations. See
   9 // basis/compiler/compiler.factor.
  10
  11 // The non-optimizing compiler compiles a quotation at a time by
  12 // concatenating machine code chunks; prolog, epilog, call word, jump to
  13 // word, etc. These machine code chunks are generated from Factor code in
  14 // basis/bootstrap/assembler/.
  15
  16 // Calls to words and constant quotations (referenced by conditionals and
  17 // dips) are direct jumps to machine code blocks. Literals are also
  18 // referenced directly without going through the literal table.
  19
  20 // It actually does do a little bit of very simple optimization:
  21
  22 // 1) Tail call optimization.
  23
  24 // 2) If a quotation is determined to not call any other words (except for a
  25 // few special words which are open-coded, see below), then no prolog/epilog
  26 // is generated.
  27
  28 // 3) When in tail position and immediately preceded by literal arguments,
  29 // the 'if' is generated inline, instead of as a call to the 'if' word.
  30
  31 // 4) When preceded by a quotation, calls to 'dip', '2dip' and '3dip' are
  32 // open-coded as retain stack manipulation surrounding a subroutine call.
  33
  34 // 5) Sub-primitives are primitive words which are implemented in assembly
  35 // and not in the VM. They are open-coded and no subroutine call is generated.
  36 // This includes stack shufflers, some fixnum arithmetic words, and words
  37 // such as tag, slot and eq?. A primitive call is relatively expensive
  38 // (two subroutine calls) so this results in a big speedup for relatively
  39 // little effort.
  40
  41 inline cell quotation_jit::nth(cell index) {
  42   return array_nth(elements.untagged(), index);
  43 }
  44
  45 void quotation_jit::init_quotation(cell quot) {
  46   elements.set_value(untag<quotation>(quot)->array);
  47 }
  48
  49 bool quotation_jit::fast_if_p(cell i, cell length) {
  50   return (i + 3) == length &&
  51       TAG(nth(i + 1)) == QUOTATION_TYPE &&
  52       nth(i + 2) == parent->special_objects[JIT_IF_WORD];
  53 }
  54
  55 bool quotation_jit::primitive_call_p(cell i, cell length) {
  56   cell jit_primitive_word = parent->special_objects[JIT_PRIMITIVE_WORD];
  57   return (i + 2) <= length && nth(i + 1) == jit_primitive_word;
  58 }
  59
  60 bool quotation_jit::fast_dip_p(cell i, cell length) {
  61   cell jit_dip_word = parent->special_objects[JIT_DIP_WORD];
  62   return (i + 2) <= length && nth(i + 1) == jit_dip_word;
  63 }
  64
  65 bool quotation_jit::fast_2dip_p(cell i, cell length) {
  66   cell jit_2dip_word = parent->special_objects[JIT_2DIP_WORD];
  67   return (i + 2) <= length && nth(i + 1) == jit_2dip_word;
  68 }
  69
  70 bool quotation_jit::fast_3dip_p(cell i, cell length) {
  71   cell jit_3dip_word = parent->special_objects[JIT_3DIP_WORD];
  72   return (i + 2) <= length && nth(i + 1) == jit_3dip_word;
  73 }
  74
  75 bool quotation_jit::declare_p(cell i, cell length) {
  76   cell jit_declare_word = parent->special_objects[JIT_DECLARE_WORD];
  77   return (i + 2) <= length && nth(i + 1) == jit_declare_word;
  78 }
  79
  80 bool quotation_jit::mega_lookup_p(cell i, cell length) {
  81   return (i + 4) <= length &&
  82       TAG(nth(i + 1)) == FIXNUM_TYPE &&
  83       TAG(nth(i + 2)) == ARRAY_TYPE &&
  84       nth(i + 3) == parent->special_objects[MEGA_LOOKUP_WORD];
  85 }
  86
  87 // Subprimitives should be flagged with whether they require a stack frame.
  88 // See #295.
  89 bool quotation_jit::special_subprimitive_p(cell obj) {
  90   return obj == parent->special_objects[SIGNAL_HANDLER_WORD] ||
  91          obj == parent->special_objects[LEAF_SIGNAL_HANDLER_WORD] ||
  92          obj == parent->special_objects[UNWIND_NATIVE_FRAMES_WORD];
  93 }
  94
  95 // All quotations want a stack frame, except if they contain:
  96 //   1) calls to the special subprimitives, see #295.
  97 //   2) mega cache lookups, see #651
  98 bool quotation_jit::stack_frame_p() {
  99   cell length = array_capacity(elements.untagged());
 100   for (cell i = 0; i < length; i++) {
 101     cell obj = nth(i);
 102     cell tag = TAG(obj);
 103     if ((tag == WORD_TYPE && special_subprimitive_p(obj)) ||
 104         (tag == ARRAY_TYPE && mega_lookup_p(i, length)))
 105       return false;
 106   }
 107   return true;
 108 }
 109
 110 static bool trivial_quotation_p(array* elements) {
 111   return array_capacity(elements) == 1 &&
 112       TAG(array_nth(elements, 0)) == WORD_TYPE;
 113 }
 114
 115 // Allocates memory (emit)
 116 void quotation_jit::emit_epilog(bool needed) {
 117   if (needed) {
 118     emit(parent->special_objects[JIT_SAFEPOINT]);
 119     emit(parent->special_objects[JIT_EPILOG]);
 120   }
 121 }
 122
 123 // Allocates memory conditionally
 124 void quotation_jit::emit_quotation(cell quot_) {
 125   data_root<quotation> quot(quot_, parent);
 126
 127   array* elements = untag<array>(quot->array);
 128
 129   // If the quotation consists of a single word, compile a direct call
 130   // to the word.
 131   if (trivial_quotation_p(elements))
 132     literal(array_nth(elements, 0));
 133   else {
 134     if (compiling)
 135       parent->jit_compile_quotation(quot.value(), relocate);
 136     literal(quot.value());
 137   }
 138 }
 139
 140 // Allocates memory (parameter(), literal(), emit_epilog, emit_with_literal)
 141 void quotation_jit::iterate_quotation() {
 142   bool stack_frame = stack_frame_p();
 143
 144   set_position(0);
 145
 146   if (stack_frame) {
 147     emit(parent->special_objects[JIT_SAFEPOINT]);
 148     emit(parent->special_objects[JIT_PROLOG]);
 149   }
 150
 151   cell length = array_capacity(elements.untagged());
 152   bool tail_call = false;
 153
 154   for (cell i = 0; i < length; i++) {
 155     set_position(i);
 156     data_root<object> obj(nth(i), parent);
 157
 158     switch (obj.type()) {
 159       case WORD_TYPE:
 160         // Sub-primitives
 161         if (to_boolean(obj.as<word>()->subprimitive)) {
 162           tail_call = emit_subprimitive(obj.value(),     // word
 163                                         i == length - 1, // tail_call_p
 164                                         stack_frame);    // stack_frame_p
 165         }                                                // Everything else
 166         else if (i == length - 1) {
 167           emit_epilog(stack_frame);
 168           tail_call = true;
 169           word_jump(obj.value());
 170         } else
 171           word_call(obj.value());
 172         break;
 173       case WRAPPER_TYPE:
 174         push(obj.as<wrapper>()->object);
 175         break;
 176       case BYTE_ARRAY_TYPE:
 177         // Primitive calls
 178         if (primitive_call_p(i, length)) {
 179 // On x86-64 and PowerPC, the VM pointer is stored in a register;
 180 // on other platforms, the RT_VM relocation is used and it needs
 181 // an offset parameter
 182 #ifdef FACTOR_X86
 183           parameter(tag_fixnum(0));
 184 #endif
 185           parameter(obj.value());
 186           parameter(false_object);
 187 #ifdef FACTOR_PPC_TOC
 188           parameter(obj.value());
 189           parameter(false_object);
 190 #endif
 191           emit(parent->special_objects[JIT_PRIMITIVE]);
 192
 193           i++;
 194         } else
 195           push(obj.value());
 196         break;
 197       case QUOTATION_TYPE:
 198         // 'if' preceded by two literal quotations (this is why if and ? are
 199         // mutually recursive in the library, but both still work)
 200         if (fast_if_p(i, length)) {
 201           emit_epilog(stack_frame);
 202           tail_call = true;
 203           emit_quotation(nth(i));
 204           emit_quotation(nth(i + 1));
 205           emit(parent->special_objects[JIT_IF]);
 206           i += 2;
 207         } // dip
 208         else if (fast_dip_p(i, length)) {
 209           emit_quotation(obj.value());
 210           emit(parent->special_objects[JIT_DIP]);
 211           i++;
 212         } // 2dip
 213         else if (fast_2dip_p(i, length)) {
 214           emit_quotation(obj.value());
 215           emit(parent->special_objects[JIT_2DIP]);
 216           i++;
 217         } // 3dip
 218         else if (fast_3dip_p(i, length)) {
 219           emit_quotation(obj.value());
 220           emit(parent->special_objects[JIT_3DIP]);
 221           i++;
 222         } else
 223           push(obj.value());
 224         break;
 225       case ARRAY_TYPE:
 226         // Method dispatch
 227         if (mega_lookup_p(i, length)) {
 228           tail_call = true;
 229           emit_mega_cache_lookup(nth(i), untag_fixnum(nth(i + 1)), nth(i + 2));
 230           i += 3;
 231         } // Non-optimizing compiler ignores declarations
 232         else if (declare_p(i, length))
 233           i++;
 234         else
 235           push(obj.value());
 236         break;
 237       default:
 238         push(obj.value());
 239         break;
 240     }
 241   }
 242
 243   if (!tail_call) {
 244     set_position(length);
 245     emit_epilog(stack_frame);
 246     emit(parent->special_objects[JIT_RETURN]);
 247   }
 248 }
 249
 250 cell quotation_jit::word_stack_frame_size(cell obj) {
 251   if (special_subprimitive_p(obj))
 252     return SIGNAL_HANDLER_STACK_FRAME_SIZE;
 253   return JIT_FRAME_SIZE;
 254 }
 255
 256 // Allocates memory
 257 void quotation_jit::emit_mega_cache_lookup(cell methods_, fixnum index,
 258                                            cell cache_) {
 259   data_root<array> methods(methods_, parent);
 260   data_root<array> cache(cache_, parent);
 261
 262   // Load the object from the datastack.
 263   emit_with_literal(parent->special_objects[PIC_LOAD],
 264                     tag_fixnum(-index * sizeof(cell)));
 265
 266   // Do a cache lookup.
 267   emit_with_literal(parent->special_objects[MEGA_LOOKUP], cache.value());
 268
 269   // If we end up here, the cache missed.
 270   emit(parent->special_objects[JIT_PROLOG]);
 271
 272   // Push index, method table and cache on the stack.
 273   push(methods.value());
 274   push(tag_fixnum(index));
 275   push(cache.value());
 276   word_call(parent->special_objects[MEGA_MISS_WORD]);
 277
 278   // Now the new method has been stored into the cache, and its on
 279   // the stack.
 280   emit(parent->special_objects[JIT_EPILOG]);
 281   emit(parent->special_objects[JIT_EXECUTE]);
 282 }
 283
 284 // Allocates memory
 285 code_block* factor_vm::jit_compile_quotation(cell owner_, cell quot_,
 286                                              bool relocating) {
 287   data_root<object> owner(owner_, this);
 288   data_root<quotation> quot(quot_, this);
 289
 290   quotation_jit compiler(owner.value(), true, relocating, this);
 291   compiler.init_quotation(quot.value());
 292   compiler.iterate_quotation();
 293
 294   cell frame_size = compiler.word_stack_frame_size(owner_);
 295
 296   code_block* compiled = compiler.to_code_block(CODE_BLOCK_UNOPTIMIZED,
 297                                                 frame_size);
 298   if (relocating)
 299     initialize_code_block(compiled);
 300
 301   return compiled;
 302 }
 303
 304 // Allocates memory
 305 void factor_vm::jit_compile_quotation(cell quot_, bool relocating) {
 306   data_root<quotation> quot(quot_, this);
 307   if (!quotation_compiled_p(quot.untagged())) {
 308     code_block* compiled =
 309         jit_compile_quotation(quot.value(), quot.value(), relocating);
 310     quot.untagged()->entry_point = compiled->entry_point();
 311   }
 312 }
 313
 314 // Allocates memory
 315 void factor_vm::primitive_jit_compile() {
 316   jit_compile_quotation(ctx->pop(), true);
 317 }
 318
 319 cell factor_vm::lazy_jit_compile_entry_point() {
 320   return untag<word>(special_objects[LAZY_JIT_COMPILE_WORD])->entry_point;
 321 }
 322
 323 // push a new quotation on the stack
 324 // Allocates memory
 325 void factor_vm::primitive_array_to_quotation() {
 326   quotation* quot = allot<quotation>(sizeof(quotation));
 327
 328   quot->array = ctx->peek();
 329   quot->cached_effect = false_object;
 330   quot->cache_counter = false_object;
 331   quot->entry_point = lazy_jit_compile_entry_point();
 332
 333   ctx->replace(tag<quotation>(quot));
 334 }
 335
 336 // Allocates memory (from_unsigned_cell)
 337 void factor_vm::primitive_quotation_code() {
 338   data_root<quotation> quot(ctx->pop(), this);
 339
 340   ctx->push(from_unsigned_cell(quot->entry_point));
 341   ctx->push(from_unsigned_cell((cell)quot->code() + quot->code()->size()));
 342 }
 343
 344 // Allocates memory
 345 fixnum factor_vm::quot_code_offset_to_scan(cell quot_, cell offset) {
 346   data_root<quotation> quot(quot_, this);
 347   data_root<array> array(quot->array, this);
 348
 349   quotation_jit compiler(quot.value(), false, false, this);
 350   compiler.init_quotation(quot.value());
 351   compiler.compute_position(offset);
 352   compiler.iterate_quotation();
 353
 354   return compiler.get_position();
 355 }
 356
 357 // Allocates memory
 358 cell factor_vm::lazy_jit_compile(cell quot_) {
 359   data_root<quotation> quot(quot_, this);
 360
 361   FACTOR_ASSERT(!quotation_compiled_p(quot.untagged()));
 362
 363   code_block* compiled =
 364       jit_compile_quotation(quot.value(), quot.value(), true);
 365   quot.untagged()->entry_point = compiled->entry_point();
 366
 367   return quot.value();
 368 }
 369
 370 // Allocates memory
 371 VM_C_API cell lazy_jit_compile(cell quot, factor_vm* parent) {
 372   return parent->lazy_jit_compile(quot);
 373 }
 374
 375 bool factor_vm::quotation_compiled_p(quotation* quot) {
 376   return quot->entry_point != 0 &&
 377          quot->entry_point != lazy_jit_compile_entry_point();
 378 }
 379
 380 void factor_vm::primitive_quotation_compiled_p() {
 381   quotation* quot = untag_check<quotation>(ctx->pop());
 382   ctx->push(tag_boolean(quotation_compiled_p(quot)));
 383 }
 384
 385 }