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