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