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 written
   8 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 dips)
  17 are direct jumps to machine code blocks. Literals are also referenced directly
  18 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 few
  25 special words which are open-coded, see below), then no prolog/epilog is
  26 generated.
  27
  28 3) When in tail position and immediately preceded by literal arguments, the
  29 '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 and not
  35 in the VM. They are open-coded and no subroutine call is generated. This
  36 includes stack shufflers, some fixnum arithmetic words, and words such as tag,
  37 slot and eq?. A primitive call is relatively expensive (two subroutine calls)
  38 so this results in a big speedup for relatively little effort. */
  39
  40 void quotation_jit::init_quotation(cell quot) {
  41   elements = untag<quotation>(quot)->array;
  42 }
  43
  44 bool quotation_jit::fast_if_p(cell i, cell length) {
  45   return (i + 3) == length &&
  46       TAG(array_nth(elements.untagged(), i + 1)) == QUOTATION_TYPE &&
  47       array_nth(elements.untagged(), i + 2) == parent->special_objects[JIT_IF_WORD];
  48 }
  49
  50 bool quotation_jit::primitive_call_p(cell i, cell length) {
  51   cell jit_primitive_word = parent->special_objects[JIT_PRIMITIVE_WORD];
  52   return (i + 2) <= length &&
  53       array_nth(elements.untagged(), i + 1) == jit_primitive_word;
  54 }
  55
  56 bool quotation_jit::fast_dip_p(cell i, cell length) {
  57   cell jit_dip_word = parent->special_objects[JIT_DIP_WORD];
  58   return (i + 2) <= length &&
  59       array_nth(elements.untagged(), i + 1) == jit_dip_word;
  60 }
  61
  62 bool quotation_jit::fast_2dip_p(cell i, cell length) {
  63   cell jit_2dip_word = parent->special_objects[JIT_2DIP_WORD];
  64   return (i + 2) <= length &&
  65       array_nth(elements.untagged(), i + 1) == jit_2dip_word;
  66 }
  67
  68 bool quotation_jit::fast_3dip_p(cell i, cell length) {
  69   cell jit_3dip_word = parent->special_objects[JIT_3DIP_WORD];
  70   return (i + 2) <= length &&
  71       array_nth(elements.untagged(), i + 1) == jit_3dip_word;
  72 }
  73
  74 bool quotation_jit::declare_p(cell i, cell length) {
  75   cell jit_declare_word = parent->special_objects[JIT_DECLARE_WORD];
  76   return (i + 2) <= length &&
  77       array_nth(elements.untagged(), 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(array_nth(elements.untagged(), i + 1)) == FIXNUM_TYPE &&
  83       TAG(array_nth(elements.untagged(), i + 2)) == ARRAY_TYPE &&
  84       array_nth(elements.untagged(), i + 3) == parent->special_objects[MEGA_LOOKUP_WORD];
  85 }
  86
  87 bool quotation_jit::special_subprimitive_p(cell obj) {
  88   // Subprimitives should be flagged with whether they require a stack frame.
  89   // See #295.
  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 bool quotation_jit::word_safepoint_p(cell obj) {
  96   return !special_subprimitive_p(obj);
  97 }
  98
  99 /* true if there are no non-safepoint words in the quoation... */
 100 bool quotation_jit::no_non_safepoint_words_p() {
 101   cell length = array_capacity(elements.untagged());
 102   for (cell i = 0; i < length; i++) {
 103     cell obj = array_nth(elements.untagged(), i);
 104     if (TAG(obj) == WORD_TYPE && !word_safepoint_p(obj))
 105       return false;
 106   }
 107   return true;
 108 }
 109
 110 bool quotation_jit::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 no_non_safepoint_words = no_non_safepoint_words_p();
 143
 144   set_position(0);
 145
 146   if (no_non_safepoint_words) {
 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
 157     data_root<object> obj(array_nth(elements.untagged(), 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                                         no_non_safepoint_words);    /* stack_frame_p */
 166         }                                                /* Everything else */
 167         else if (i == length - 1) {
 168           emit_epilog(no_non_safepoint_words);
 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
 181    a register; on other platforms, the RT_VM relocation
 182    is used and it needs 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(no_non_safepoint_words);
 203           tail_call = true;
 204
 205           emit_quotation(array_nth(elements.untagged(), i));
 206           emit_quotation(array_nth(elements.untagged(), i + 1));
 207           emit(parent->special_objects[JIT_IF]);
 208
 209           i += 2;
 210         } /* dip */
 211         else if (fast_dip_p(i, length)) {
 212           emit_quotation(obj.value());
 213           emit(parent->special_objects[JIT_DIP]);
 214           i++;
 215         } /* 2dip */
 216         else if (fast_2dip_p(i, length)) {
 217           emit_quotation(obj.value());
 218           emit(parent->special_objects[JIT_2DIP]);
 219           i++;
 220         } /* 3dip */
 221         else if (fast_3dip_p(i, length)) {
 222           emit_quotation(obj.value());
 223           emit(parent->special_objects[JIT_3DIP]);
 224           i++;
 225         } else
 226           push(obj.value());
 227         break;
 228       case ARRAY_TYPE:
 229         /* Method dispatch */
 230         if (mega_lookup_p(i, length)) {
 231           fixnum index = untag_fixnum(array_nth(elements.untagged(), i + 1));
 232           /* Load the object from the datastack, then remove our stack frame. */
 233           emit_with_literal(parent->special_objects[PIC_LOAD],
 234                             tag_fixnum(-index * sizeof(cell)));
 235           emit_epilog(no_non_safepoint_words);
 236           tail_call = true;
 237
 238           emit_mega_cache_lookup(array_nth(elements.untagged(), i), index,
 239                                  array_nth(elements.untagged(), i + 2));
 240           i += 3;
 241         } /* Non-optimizing compiler ignores declarations */
 242         else if (declare_p(i, length))
 243           i++;
 244         else
 245           push(obj.value());
 246         break;
 247       default:
 248         push(obj.value());
 249         break;
 250     }
 251   }
 252
 253   if (!tail_call) {
 254     set_position(length);
 255     emit_epilog(no_non_safepoint_words);
 256     emit(parent->special_objects[JIT_RETURN]);
 257   }
 258 }
 259
 260 cell quotation_jit::word_stack_frame_size(cell obj) {
 261   if (special_subprimitive_p(obj))
 262     return SIGNAL_HANDLER_STACK_FRAME_SIZE;
 263   return JIT_FRAME_SIZE;
 264 }
 265
 266 /* Allocates memory */
 267 void quotation_jit::emit_mega_cache_lookup(cell methods_, fixnum index,
 268                                            cell cache_) {
 269   data_root<array> methods(methods_, parent);
 270   data_root<array> cache(cache_, parent);
 271
 272   /* The object must be on the top of the datastack at this point. */
 273
 274   /* Do a cache lookup. */
 275   emit_with_literal(parent->special_objects[MEGA_LOOKUP], cache.value());
 276
 277   /* If we end up here, the cache missed. */
 278   emit(parent->special_objects[JIT_PROLOG]);
 279
 280   /* Push index, method table and cache on the stack. */
 281   push(methods.value());
 282   push(tag_fixnum(index));
 283   push(cache.value());
 284   word_call(parent->special_objects[MEGA_MISS_WORD]);
 285
 286   /* Now the new method has been stored into the cache, and its on
 287      the stack. */
 288   emit(parent->special_objects[JIT_EPILOG]);
 289   emit(parent->special_objects[JIT_EXECUTE]);
 290 }
 291
 292 /* Allocates memory */
 293 code_block* factor_vm::jit_compile_quotation(cell owner_, cell quot_,
 294                                              bool relocating) {
 295   data_root<object> owner(owner_, this);
 296   data_root<quotation> quot(quot_, this);
 297
 298   quotation_jit compiler(owner.value(), true, relocating, this);
 299   compiler.init_quotation(quot.value());
 300   compiler.iterate_quotation();
 301
 302   cell frame_size = compiler.word_stack_frame_size(owner_);
 303
 304   code_block* compiled = compiler.to_code_block(frame_size);
 305
 306   if (relocating)
 307     initialize_code_block(compiled);
 308
 309   return compiled;
 310 }
 311
 312 /* Allocates memory */
 313 void factor_vm::jit_compile_quotation(cell quot_, bool relocating) {
 314   data_root<quotation> quot(quot_, this);
 315   if (!quotation_compiled_p(quot.untagged())) {
 316     code_block* compiled =
 317         jit_compile_quotation(quot.value(), quot.value(), relocating);
 318     quot.untagged()->entry_point = compiled->entry_point();
 319   }
 320 }
 321
 322 /* Allocates memory */
 323 void factor_vm::primitive_jit_compile() {
 324   jit_compile_quotation(ctx->pop(), true);
 325 }
 326
 327 cell factor_vm::lazy_jit_compile_entry_point() {
 328   return untag<word>(special_objects[LAZY_JIT_COMPILE_WORD])->entry_point;
 329 }
 330
 331 /* push a new quotation on the stack */
 332 /* Allocates memory */
 333 void factor_vm::primitive_array_to_quotation() {
 334   quotation* quot = allot<quotation>(sizeof(quotation));
 335
 336   quot->array = ctx->peek();
 337   quot->cached_effect = false_object;
 338   quot->cache_counter = false_object;
 339   quot->entry_point = lazy_jit_compile_entry_point();
 340
 341   ctx->replace(tag<quotation>(quot));
 342 }
 343
 344 /* Allocates memory (from_unsigned_cell) */
 345 void factor_vm::primitive_quotation_code() {
 346   data_root<quotation> quot(ctx->pop(), this);
 347
 348   ctx->push(from_unsigned_cell(quot->entry_point));
 349   ctx->push(from_unsigned_cell((cell)quot->code() + quot->code()->size()));
 350 }
 351
 352 /* Allocates memory */
 353 fixnum factor_vm::quot_code_offset_to_scan(cell quot_, cell offset) {
 354   data_root<quotation> quot(quot_, this);
 355   data_root<array> array(quot->array, this);
 356
 357   quotation_jit compiler(quot.value(), false, false, this);
 358   compiler.init_quotation(quot.value());
 359   compiler.compute_position(offset);
 360   compiler.iterate_quotation();
 361
 362   return compiler.get_position();
 363 }
 364
 365 /* Allocates memory */
 366 cell factor_vm::lazy_jit_compile(cell quot_) {
 367   data_root<quotation> quot(quot_, this);
 368
 369   FACTOR_ASSERT(!quotation_compiled_p(quot.untagged()));
 370
 371   code_block* compiled =
 372       jit_compile_quotation(quot.value(), quot.value(), true);
 373   quot.untagged()->entry_point = compiled->entry_point();
 374
 375   return quot.value();
 376 }
 377
 378 /* Allocates memory */
 379 VM_C_API cell lazy_jit_compile(cell quot, factor_vm* parent) {
 380   return parent->lazy_jit_compile(quot);
 381 }
 382
 383 bool factor_vm::quotation_compiled_p(quotation* quot) {
 384   return quot->entry_point != 0 &&
 385          quot->entry_point != lazy_jit_compile_entry_point();
 386 }
 387
 388 void factor_vm::primitive_quotation_compiled_p() {
 389   quotation* quot = untag_check<quotation>(ctx->pop());
 390   ctx->push(tag_boolean(quotation_compiled_p(quot)));
 391 }
 392
 393 }