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