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