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