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