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