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