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 void quotation_jit::emit_prolog(bool safepoint, bool stack_frame) {
 142   if (safepoint)
 143     emit(parent->special_objects[JIT_SAFEPOINT]);
 144   if (stack_frame)
 145     emit(parent->special_objects[JIT_PROLOG]);
 146 }
 147
 148 void quotation_jit::emit_epilog(bool safepoint, bool stack_frame) {
 149   if (safepoint)
 150     emit(parent->special_objects[JIT_SAFEPOINT]);
 151   if (stack_frame)
 152     emit(parent->special_objects[JIT_EPILOG]);
 153 }
 154
 155 /* Allocates memory conditionally */
 156 void quotation_jit::emit_quot(cell quot_) {
 157   data_root<quotation> quot(quot_, parent);
 158
 159   array* elements = untag<array>(quot->array);
 160
 161   /* If the quotation consists of a single word, compile a direct call
 162      to the word. */
 163   if (trivial_quotation_p(elements))
 164     literal(array_nth(elements, 0));
 165   else {
 166     if (compiling)
 167       parent->jit_compile_quot(quot.value(), relocate);
 168     literal(quot.value());
 169   }
 170 }
 171
 172 /* Allocates memory */
 173 void quotation_jit::iterate_quotation() {
 174   bool safepoint = safepoint_p();
 175   bool stack_frame = stack_frame_p();
 176
 177   set_position(0);
 178
 179   emit_prolog(safepoint, stack_frame);
 180
 181   cell i;
 182   cell length = array_capacity(elements.untagged());
 183   bool tail_call = false;
 184
 185   for (i = 0; i < length; i++) {
 186     set_position(i);
 187
 188     data_root<object> obj(array_nth(elements.untagged(), i), parent);
 189
 190     switch (obj.type()) {
 191       case WORD_TYPE:
 192         /* Sub-primitives */
 193         if (to_boolean(obj.as<word>()->subprimitive)) {
 194           tail_call = emit_subprimitive(obj.value(),     /* word */
 195                                         i == length - 1, /* tail_call_p */
 196                                         stack_frame);    /* stack_frame_p */
 197         }                                                /* Everything else */
 198             else if (i == length - 1) {
 199           emit_epilog(safepoint, stack_frame);
 200           tail_call = true;
 201           word_jump(obj.value());
 202         } else
 203           word_call(obj.value());
 204         break;
 205       case WRAPPER_TYPE:
 206         push(obj.as<wrapper>()->object);
 207         break;
 208       case BYTE_ARRAY_TYPE:
 209         /* Primitive calls */
 210         if (primitive_call_p(i, length)) {
 211 /* On x86-64 and PowerPC, the VM pointer is stored in
 212    a register; on other platforms, the RT_VM relocation
 213    is used and it needs an offset parameter */
 214 #ifdef FACTOR_X86
 215           parameter(tag_fixnum(0));
 216 #endif
 217           parameter(obj.value());
 218           parameter(false_object);
 219 #ifdef FACTOR_PPC_TOC
 220           parameter(obj.value());
 221           parameter(false_object);
 222 #endif
 223           emit(parent->special_objects[JIT_PRIMITIVE]);
 224
 225           i++;
 226         } else
 227           push(obj.value());
 228         break;
 229       case QUOTATION_TYPE:
 230         /* 'if' preceded by two literal quotations (this is why if and ? are
 231            mutually recursive in the library, but both still work) */
 232         if (fast_if_p(i, length)) {
 233           emit_epilog(safepoint, stack_frame);
 234           tail_call = true;
 235
 236           emit_quot(array_nth(elements.untagged(), i));
 237           emit_quot(array_nth(elements.untagged(), i + 1));
 238           emit(parent->special_objects[JIT_IF]);
 239
 240           i += 2;
 241         } /* dip */
 242             else if (fast_dip_p(i, length)) {
 243           emit_quot(obj.value());
 244           emit(parent->special_objects[JIT_DIP]);
 245           i++;
 246         } /* 2dip */
 247             else if (fast_2dip_p(i, length)) {
 248           emit_quot(obj.value());
 249           emit(parent->special_objects[JIT_2DIP]);
 250           i++;
 251         } /* 3dip */
 252             else if (fast_3dip_p(i, length)) {
 253           emit_quot(obj.value());
 254           emit(parent->special_objects[JIT_3DIP]);
 255           i++;
 256         } else
 257           push(obj.value());
 258         break;
 259       case ARRAY_TYPE:
 260         /* Method dispatch */
 261         if (mega_lookup_p(i, length)) {
 262           fixnum index = untag_fixnum(array_nth(elements.untagged(), i + 1));
 263           /* Load the object from the datastack, then remove our stack frame. */
 264           emit_with_literal(parent->special_objects[PIC_LOAD],
 265                             tag_fixnum(-index * sizeof(cell)));
 266           emit_epilog(safepoint, stack_frame);
 267           tail_call = true;
 268
 269           emit_mega_cache_lookup(array_nth(elements.untagged(), i), index,
 270                                  array_nth(elements.untagged(), i + 2));
 271           i += 3;
 272         } /* Non-optimizing compiler ignores declarations */
 273             else if (declare_p(i, length))
 274           i++;
 275         else
 276           push(obj.value());
 277         break;
 278       default:
 279         push(obj.value());
 280         break;
 281     }
 282   }
 283
 284   if (!tail_call) {
 285     set_position(length);
 286
 287     emit_epilog(safepoint, stack_frame);
 288     emit(parent->special_objects[JIT_RETURN]);
 289   }
 290 }
 291
 292 cell quotation_jit::word_stack_frame_size(cell obj) {
 293   if (special_subprimitive_p(obj))
 294     return SIGNAL_HANDLER_STACK_FRAME_SIZE;
 295   else
 296     return JIT_FRAME_SIZE;
 297 }
 298
 299 /* Allocates memory */
 300 code_block* factor_vm::jit_compile_quot(cell owner_, cell quot_,
 301                                         bool relocating) {
 302   data_root<object> owner(owner_, this);
 303   data_root<quotation> quot(quot_, this);
 304
 305   quotation_jit compiler(owner.value(), true, relocating, this);
 306   compiler.init_quotation(quot.value());
 307   compiler.iterate_quotation();
 308
 309   cell frame_size = compiler.word_stack_frame_size(owner_);
 310
 311   code_block* compiled = compiler.to_code_block(frame_size);
 312
 313   if (relocating)
 314     initialize_code_block(compiled);
 315
 316   return compiled;
 317 }
 318
 319 /* Allocates memory */
 320 void factor_vm::jit_compile_quot(cell quot_, bool relocating) {
 321   data_root<quotation> quot(quot_, this);
 322   if (!quot_compiled_p(quot.untagged())) {
 323     code_block* compiled =
 324         jit_compile_quot(quot.value(), quot.value(), relocating);
 325     quot.untagged()->entry_point = compiled->entry_point();
 326   }
 327 }
 328
 329 /* Allocates memory */
 330 void factor_vm::primitive_jit_compile() { jit_compile_quot(ctx->pop(), true); }
 331
 332 void* factor_vm::lazy_jit_compile_entry_point() {
 333   return untag<word>(special_objects[LAZY_JIT_COMPILE_WORD])->entry_point;
 334 }
 335
 336 /* push a new quotation on the stack */
 337 /* Allocates memory */
 338 void factor_vm::primitive_array_to_quotation() {
 339   quotation* quot = allot<quotation>(sizeof(quotation));
 340
 341   quot->array = ctx->peek();
 342   quot->cached_effect = false_object;
 343   quot->cache_counter = false_object;
 344   quot->entry_point = lazy_jit_compile_entry_point();
 345
 346   ctx->replace(tag<quotation>(quot));
 347 }
 348
 349 /* Allocates memory (from_unsigned_cell) */
 350 void factor_vm::primitive_quotation_code() {
 351   data_root<quotation> quot(ctx->pop(), this);
 352
 353   ctx->push(from_unsigned_cell((cell)quot->entry_point));
 354   ctx->push(from_unsigned_cell((cell)quot->code() + quot->code()->size()));
 355 }
 356
 357 /* Allocates memory */
 358 fixnum factor_vm::quot_code_offset_to_scan(cell quot_, cell offset) {
 359   data_root<quotation> quot(quot_, this);
 360   data_root<array> array(quot->array, this);
 361
 362   quotation_jit compiler(quot.value(), false, false, this);
 363   compiler.init_quotation(quot.value());
 364   compiler.compute_position(offset);
 365   compiler.iterate_quotation();
 366
 367   return compiler.get_position();
 368 }
 369
 370 /* Allocates memory */
 371 cell factor_vm::lazy_jit_compile(cell quot_) {
 372   data_root<quotation> quot(quot_, this);
 373
 374   FACTOR_ASSERT(!quot_compiled_p(quot.untagged()));
 375
 376   code_block* compiled = jit_compile_quot(quot.value(), quot.value(), true);
 377   quot.untagged()->entry_point = compiled->entry_point();
 378
 379   return quot.value();
 380 }
 381
 382 /* Allocates memory */
 383 VM_C_API cell lazy_jit_compile(cell quot, factor_vm* parent) {
 384   return parent->lazy_jit_compile(quot);
 385 }
 386
 387 bool factor_vm::quot_compiled_p(quotation* quot) {
 388   return quot->entry_point != NULL &&
 389          quot->entry_point != lazy_jit_compile_entry_point();
 390 }
 391
 392 void factor_vm::primitive_quot_compiled_p() {
 393   tagged<quotation> quot(ctx->pop());
 394   quot.untag_check(this);
 395   ctx->push(tag_boolean(quot_compiled_p(quot.untagged())));
 396 }
 397
 398 /* Allocates memory */
 399 cell factor_vm::find_all_quotations() { return instances(QUOTATION_TYPE); }
 400
 401 /* Allocates memory */
 402 void factor_vm::initialize_all_quotations() {
 403   data_root<array> quotations(find_all_quotations(), this);
 404
 405   cell length = array_capacity(quotations.untagged());
 406   for (cell i = 0; i < length; i++) {
 407     data_root<quotation> quot(array_nth(quotations.untagged(), i), this);
 408     if (!quot->entry_point)
 409       quot.untagged()->entry_point = lazy_jit_compile_entry_point();
 410   }
 411 }
 412
 413 }