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