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