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