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