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