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