vm/quotations.cpp

   1 #include "master.hpp"
   2
   3 namespace factor
   4 {
   5
   6 /* Simple non-optimizing compiler.
   7
   8 This is one of the two compilers implementing Factor; the second one is written
   9 in Factor and performs advanced optimizations. See basis/compiler/compiler.factor.
  10
  11 The non-optimizing compiler compiles a quotation at a time by concatenating
  12 machine code chunks; prolog, epilog, call word, jump to word, etc. These machine
  13 code chunks are generated from Factor code in basis/cpu/.../bootstrap.factor.
  14
  15 Calls to words and constant quotations (referenced by conditionals and dips)
  16 are direct jumps to machine code blocks. Literals are also referenced directly
  17 without going through the literal table.
  18
  19 It actually does do a little bit of very simple optimization:
  20
  21 1) Tail call optimization.
  22
  23 2) If a quotation is determined to not call any other words (except for a few
  24 special words which are open-coded, see below), then no prolog/epilog is
  25 generated.
  26
  27 3) When in tail position and immediately preceded by literal arguments, the
  28 'if' is generated inline, instead of as a call to the 'if' word.
  29
  30 4) When preceded by a quotation, calls to 'dip', '2dip' and '3dip' are
  31 open-coded as retain stack manipulation surrounding a subroutine call.
  32
  33 5) Sub-primitives are primitive words which are implemented in assembly and not
  34 in the VM. They are open-coded and no subroutine call is generated. This
  35 includes stack shufflers, some fixnum arithmetic words, and words such as tag,
  36 slot and eq?. A primitive call is relatively expensive (two subroutine calls)
  37 so this results in a big speedup for relatively little effort. */
  38
  39 void quotation_jit::init_quotation(cell quot)
  40 {
  41         elements = untag<quotation>(quot)->array;
  42 }
  43
  44 bool quotation_jit::primitive_call_p(cell i, cell length)
  45 {
  46         return (i + 2) <= length && array_nth(elements.untagged(),i + 1) == parent->special_objects[JIT_PRIMITIVE_WORD];
  47 }
  48
  49 bool quotation_jit::fast_if_p(cell i, cell length)
  50 {
  51         return (i + 3) == length
  52                 && tagged<object>(array_nth(elements.untagged(),i + 1)).type_p(QUOTATION_TYPE)
  53                 && array_nth(elements.untagged(),i + 2) == parent->special_objects[JIT_IF_WORD];
  54 }
  55
  56 bool quotation_jit::fast_dip_p(cell i, cell length)
  57 {
  58         return (i + 2) <= length && array_nth(elements.untagged(),i + 1) == parent->special_objects[JIT_DIP_WORD];
  59 }
  60
  61 bool quotation_jit::fast_2dip_p(cell i, cell length)
  62 {
  63         return (i + 2) <= length && array_nth(elements.untagged(),i + 1) == parent->special_objects[JIT_2DIP_WORD];
  64 }
  65
  66 bool quotation_jit::fast_3dip_p(cell i, cell length)
  67 {
  68         return (i + 2) <= length && array_nth(elements.untagged(),i + 1) == parent->special_objects[JIT_3DIP_WORD];
  69 }
  70
  71 bool quotation_jit::mega_lookup_p(cell i, cell length)
  72 {
  73         return (i + 4) <= length
  74                 && tagged<object>(array_nth(elements.untagged(),i + 1)).type_p(FIXNUM_TYPE)
  75                 && tagged<object>(array_nth(elements.untagged(),i + 2)).type_p(ARRAY_TYPE)
  76                 && array_nth(elements.untagged(),i + 3) == parent->special_objects[MEGA_LOOKUP_WORD];
  77 }
  78
  79 bool quotation_jit::declare_p(cell i, cell length)
  80 {
  81         return (i + 2) <= length
  82                 && array_nth(elements.untagged(),i + 1) == parent->special_objects[JIT_DECLARE_WORD];
  83 }
  84
  85 bool quotation_jit::special_subprimitive_p(cell obj)
  86 {
  87         // Subprimitives should be flagged with whether they require a stack frame.
  88         // See #295.
  89         return obj == parent->special_objects[SIGNAL_HANDLER_WORD]
  90                 || obj == parent->special_objects[LEAF_SIGNAL_HANDLER_WORD]
  91                 || obj == parent->special_objects[FFI_SIGNAL_HANDLER_WORD]
  92                 || obj == parent->special_objects[FFI_LEAF_SIGNAL_HANDLER_WORD]
  93                 || obj == parent->special_objects[UNWIND_NATIVE_FRAMES_WORD];
  94 }
  95
  96 bool quotation_jit::word_stack_frame_p(cell obj)
  97 {
  98         return (to_boolean(untag<word>(obj)->subprimitive) && !special_subprimitive_p(obj))
  99                 || obj == parent->special_objects[JIT_PRIMITIVE_WORD];
 100 }
 101
 102 bool quotation_jit::word_safepoint_p(cell obj)
 103 {
 104         return !special_subprimitive_p(obj);
 105 }
 106
 107 bool quotation_jit::safepoint_p()
 108 {
 109         fixnum length = array_capacity(elements.untagged());
 110
 111         for(fixnum i = 0; i < length; i++)
 112         {
 113                 cell obj = array_nth(elements.untagged(),i);
 114                 switch(tagged<object>(obj).type())
 115                 {
 116                 case WORD_TYPE:
 117                         if(!word_safepoint_p(obj))
 118                                 return false;
 119                         break;
 120                 default:
 121                         break;
 122                 }
 123         }
 124
 125         return true;
 126 }
 127
 128 bool quotation_jit::stack_frame_p()
 129 {
 130         fixnum length = array_capacity(elements.untagged());
 131
 132         for(fixnum i = 0; i < length; i++)
 133         {
 134                 cell obj = array_nth(elements.untagged(),i);
 135                 if (tagged<object>(obj).type() == WORD_TYPE && !word_safepoint_p(obj))
 136                         return false;
 137         }
 138
 139         return true;
 140 }
 141
 142 bool quotation_jit::trivial_quotation_p(array *elements)
 143 {
 144         return array_capacity(elements) == 1 && tagged<object>(array_nth(elements,0)).type_p(WORD_TYPE);
 145 }
 146
 147 void quotation_jit::emit_prolog(bool safepoint, bool stack_frame)
 148 {
 149         if(safepoint) emit(parent->special_objects[JIT_SAFEPOINT]);
 150         if(stack_frame) emit(parent->special_objects[JIT_PROLOG]);
 151 }
 152
 153 void quotation_jit::emit_epilog(bool safepoint, bool stack_frame)
 154 {
 155         if(safepoint) emit(parent->special_objects[JIT_SAFEPOINT]);
 156         if(stack_frame) emit(parent->special_objects[JIT_EPILOG]);
 157 }
 158
 159 void quotation_jit::emit_quot(cell quot_)
 160 {
 161         data_root<quotation> quot(quot_,parent);
 162
 163         array *elements = untag<array>(quot->array);
 164
 165         /* If the quotation consists of a single word, compile a direct call
 166         to the word. */
 167         if(trivial_quotation_p(elements))
 168                 literal(array_nth(elements,0));
 169         else
 170         {
 171                 if(compiling) parent->jit_compile_quot(quot.value(),relocate);
 172                 literal(quot.value());
 173         }
 174 }
 175
 176 /* Allocates memory */
 177 void quotation_jit::iterate_quotation()
 178 {
 179         bool safepoint = safepoint_p();
 180         bool stack_frame = stack_frame_p();
 181
 182         set_position(0);
 183
 184         emit_prolog(safepoint, stack_frame);
 185
 186         cell i;
 187         cell length = array_capacity(elements.untagged());
 188         bool tail_call = false;
 189
 190         for(i = 0; i < length; i++)
 191         {
 192                 set_position(i);
 193
 194                 data_root<object> obj(array_nth(elements.untagged(),i),parent);
 195
 196                 switch(obj.type())
 197                 {
 198                 case WORD_TYPE:
 199                         /* Sub-primitives */
 200                         if(to_boolean(obj.as<word>()->subprimitive))
 201                         {
 202                                 tail_call = emit_subprimitive(obj.value(), /* word */
 203                                         i == length - 1, /* tail_call_p */
 204                                         stack_frame); /* stack_frame_p */
 205                         }
 206                         /* Everything else */
 207                         else if(i == length - 1)
 208                         {
 209                                 emit_epilog(safepoint, stack_frame);
 210                                 tail_call = true;
 211                                 word_jump(obj.value());
 212                         }
 213                         else
 214                                 word_call(obj.value());
 215                         break;
 216                 case WRAPPER_TYPE:
 217                         push(obj.as<wrapper>()->object);
 218                         break;
 219                 case BYTE_ARRAY_TYPE:
 220                         /* Primitive calls */
 221                         if(primitive_call_p(i,length))
 222                         {
 223                                 /* On x86-64 and PowerPC, the VM pointer is stored in
 224                                 a register; on other platforms, the RT_VM relocation
 225                                 is used and it needs an offset parameter */
 226 #ifdef FACTOR_X86
 227                                 parameter(tag_fixnum(0));
 228 #endif
 229                                 parameter(obj.value());
 230                                 parameter(false_object);
 231 #ifdef FACTOR_PPC_TOC
 232                                 parameter(obj.value());
 233                                 parameter(false_object);
 234 #endif
 235                                 emit(parent->special_objects[JIT_PRIMITIVE]);
 236
 237                                 i++;
 238                         }
 239                         else
 240                                 push(obj.value());
 241                         break;
 242                 case QUOTATION_TYPE:
 243                         /* 'if' preceeded by two literal quotations (this is why if and ? are
 244                            mutually recursive in the library, but both still work) */
 245                         if(fast_if_p(i,length))
 246                         {
 247                                 emit_epilog(safepoint, stack_frame);
 248                                 tail_call = true;
 249
 250                                 emit_quot(array_nth(elements.untagged(),i));
 251                                 emit_quot(array_nth(elements.untagged(),i + 1));
 252                                 emit(parent->special_objects[JIT_IF]);
 253
 254                                 i += 2;
 255                         }
 256                         /* dip */
 257                         else if(fast_dip_p(i,length))
 258                         {
 259                                 emit_quot(obj.value());
 260                                 emit(parent->special_objects[JIT_DIP]);
 261                                 i++;
 262                         }
 263                         /* 2dip */
 264                         else if(fast_2dip_p(i,length))
 265                         {
 266                                 emit_quot(obj.value());
 267                                 emit(parent->special_objects[JIT_2DIP]);
 268                                 i++;
 269                         }
 270                         /* 3dip */
 271                         else if(fast_3dip_p(i,length))
 272                         {
 273                                 emit_quot(obj.value());
 274                                 emit(parent->special_objects[JIT_3DIP]);
 275                                 i++;
 276                         }
 277                         else
 278                                 push(obj.value());
 279                         break;
 280                 case ARRAY_TYPE:
 281                         /* Method dispatch */
 282                         if(mega_lookup_p(i,length))
 283                         {
 284                                 fixnum index = untag_fixnum(array_nth(elements.untagged(),i + 1));
 285                                 /* Load the object from the datastack, then remove our stack frame. */
 286                                 emit_with_literal(parent->special_objects[PIC_LOAD],tag_fixnum(-index * sizeof(cell)));
 287                                 emit_epilog(safepoint, stack_frame);
 288                                 tail_call = true;
 289
 290                                 emit_mega_cache_lookup(
 291                                         array_nth(elements.untagged(),i),
 292                                         index,
 293                                         array_nth(elements.untagged(),i + 2));
 294                                 i += 3;
 295                         }
 296                         /* Non-optimizing compiler ignores declarations */
 297                         else if(declare_p(i,length))
 298                                 i++;
 299                         else
 300                                 push(obj.value());
 301                         break;
 302                 default:
 303                         push(obj.value());
 304                         break;
 305                 }
 306         }
 307
 308         if(!tail_call)
 309         {
 310                 set_position(length);
 311
 312                 emit_epilog(safepoint, stack_frame);
 313                 emit(parent->special_objects[JIT_RETURN]);
 314         }
 315 }
 316
 317 cell quotation_jit::word_stack_frame_size(cell obj)
 318 {
 319         if (special_subprimitive_p(obj))
 320                 return SIGNAL_HANDLER_STACK_FRAME_SIZE;
 321         else
 322                 return JIT_FRAME_SIZE;
 323 }
 324
 325 /* Allocates memory */
 326 code_block *factor_vm::jit_compile_quot(cell owner_, cell quot_, bool relocating)
 327 {
 328         data_root<object> owner(owner_,this);
 329         data_root<quotation> quot(quot_,this);
 330
 331         quotation_jit compiler(owner.value(),true,relocating,this);
 332         compiler.init_quotation(quot.value());
 333         compiler.iterate_quotation();
 334
 335         cell frame_size = compiler.word_stack_frame_size(owner_);
 336
 337         code_block *compiled = compiler.to_code_block(frame_size);
 338
 339         if(relocating) initialize_code_block(compiled);
 340
 341         return compiled;
 342 }
 343
 344 void factor_vm::jit_compile_quot(cell quot_, bool relocating)
 345 {
 346         data_root<quotation> quot(quot_,this);
 347         if(!quot_compiled_p(quot.untagged()))
 348         {
 349                 code_block *compiled = jit_compile_quot(quot.value(),quot.value(),relocating);
 350                 quot.untagged()->entry_point = compiled->entry_point();
 351         }
 352 }
 353
 354 void factor_vm::primitive_jit_compile()
 355 {
 356         jit_compile_quot(ctx->pop(),true);
 357 }
 358
 359 void *factor_vm::lazy_jit_compile_entry_point()
 360 {
 361         return untag<word>(special_objects[LAZY_JIT_COMPILE_WORD])->entry_point;
 362 }
 363
 364 /* push a new quotation on the stack */
 365 void factor_vm::primitive_array_to_quotation()
 366 {
 367         quotation *quot = allot<quotation>(sizeof(quotation));
 368
 369         quot->array = ctx->peek();
 370         quot->cached_effect = false_object;
 371         quot->cache_counter = false_object;
 372         quot->entry_point = lazy_jit_compile_entry_point();
 373
 374         ctx->replace(tag<quotation>(quot));
 375 }
 376
 377 void factor_vm::primitive_quotation_code()
 378 {
 379         quotation *quot = untag_check<quotation>(ctx->pop());
 380
 381         ctx->push(from_unsigned_cell((cell)quot->entry_point));
 382         ctx->push(from_unsigned_cell((cell)quot->code() + quot->code()->size()));
 383 }
 384
 385 /* Allocates memory */
 386 fixnum factor_vm::quot_code_offset_to_scan(cell quot_, cell offset)
 387 {
 388         data_root<quotation> quot(quot_,this);
 389         data_root<array> array(quot->array,this);
 390
 391         quotation_jit compiler(quot.value(),false,false,this);
 392         compiler.init_quotation(quot.value());
 393         compiler.compute_position(offset);
 394         compiler.iterate_quotation();
 395
 396         return compiler.get_position();
 397 }
 398
 399 cell factor_vm::lazy_jit_compile(cell quot_)
 400 {
 401         data_root<quotation> quot(quot_,this);
 402
 403         FACTOR_ASSERT(!quot_compiled_p(quot.untagged()));
 404
 405         code_block *compiled = jit_compile_quot(quot.value(),quot.value(),true);
 406         quot.untagged()->entry_point = compiled->entry_point();
 407
 408         return quot.value();
 409 }
 410
 411 VM_C_API cell lazy_jit_compile(cell quot, factor_vm *parent)
 412 {
 413         return parent->lazy_jit_compile(quot);
 414 }
 415
 416 bool factor_vm::quot_compiled_p(quotation *quot)
 417 {
 418         return quot->entry_point != NULL && quot->entry_point != lazy_jit_compile_entry_point();
 419 }
 420
 421 void factor_vm::primitive_quot_compiled_p()
 422 {
 423         tagged<quotation> quot(ctx->pop());
 424         quot.untag_check(this);
 425         ctx->push(tag_boolean(quot_compiled_p(quot.untagged())));
 426 }
 427
 428 cell factor_vm::find_all_quotations()
 429 {
 430         return instances(QUOTATION_TYPE);
 431 }
 432
 433 void factor_vm::initialize_all_quotations()
 434 {
 435         data_root<array> quotations(find_all_quotations(),this);
 436
 437         cell length = array_capacity(quotations.untagged());
 438         for(cell i = 0; i < length; i++)
 439         {
 440                 data_root<quotation> quot(array_nth(quotations.untagged(),i),this);
 441                 if(!quot->entry_point)
 442                         quot.untagged()->entry_point = lazy_jit_compile_entry_point();
 443         }
 444 }
 445
 446 }