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 inline cell quotation_jit::nth(cell index) {
  41   return array_nth(elements.untagged(), index);
  42 }
  43
  44 void quotation_jit::init_quotation(cell quot) {
  45   elements = untag<quotation>(quot)->array;
  46 }
  47
  48 bool quotation_jit::fast_if_p(cell i, cell length) {
  49   return (i + 3) == length &&
  50       TAG(nth(i + 1)) == QUOTATION_TYPE &&
  51       nth(i + 2) == parent->special_objects[JIT_IF_WORD];
  52 }
  53
  54 bool quotation_jit::primitive_call_p(cell i, cell length) {
  55   cell jit_primitive_word = parent->special_objects[JIT_PRIMITIVE_WORD];
  56   return (i + 2) <= length && nth(i + 1) == jit_primitive_word;
  57 }
  58
  59 bool quotation_jit::fast_dip_p(cell i, cell length) {
  60   cell jit_dip_word = parent->special_objects[JIT_DIP_WORD];
  61   return (i + 2) <= length && nth(i + 1) == jit_dip_word;
  62 }
  63
  64 bool quotation_jit::fast_2dip_p(cell i, cell length) {
  65   cell jit_2dip_word = parent->special_objects[JIT_2DIP_WORD];
  66   return (i + 2) <= length && nth(i + 1) == jit_2dip_word;
  67 }
  68
  69 bool quotation_jit::fast_3dip_p(cell i, cell length) {
  70   cell jit_3dip_word = parent->special_objects[JIT_3DIP_WORD];
  71   return (i + 2) <= length && nth(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 && nth(i + 1) == jit_declare_word;
  77 }
  78
  79 bool quotation_jit::mega_lookup_p(cell i, cell length) {
  80   return (i + 4) <= length &&
  81       TAG(nth(i + 1)) == FIXNUM_TYPE &&
  82       TAG(nth(i + 2)) == ARRAY_TYPE &&
  83       nth(i + 3) == parent->special_objects[MEGA_LOOKUP_WORD];
  84 }
  85
  86 /* Subprimitives should be flagged with whether they require a stack frame.
  87    See #295. */
  88 bool quotation_jit::special_subprimitive_p(cell obj) {
  89   return obj == parent->special_objects[SIGNAL_HANDLER_WORD] ||
  90          obj == parent->special_objects[LEAF_SIGNAL_HANDLER_WORD] ||
  91          obj == parent->special_objects[UNWIND_NATIVE_FRAMES_WORD];
  92 }
  93
  94 /* All quotations wants a stack frame, except if they contain:
  95
  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
 180    a register; on other platforms, the RT_VM relocation
 181    is used and it needs 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(frame_size);
 297
 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 }