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                                 emit(parent->special_objects[JIT_PRIMITIVE]);
 194
 195                                 i++;
 196                         }
 197                         else
 198                                 push(obj.value());
 199                         break;
 200                 case QUOTATION_TYPE:
 201                         /* 'if' preceeded by two literal quotations (this is why if and ? are
 202                            mutually recursive in the library, but both still work) */
 203                         if(fast_if_p(i,length))
 204                         {
 205                                 if(stack_frame) emit(parent->special_objects[JIT_EPILOG]);
 206                                 tail_call = true;
 207
 208                                 emit_quot(array_nth(elements.untagged(),i));
 209                                 emit_quot(array_nth(elements.untagged(),i + 1));
 210                                 emit(parent->special_objects[JIT_IF]);
 211
 212                                 i += 2;
 213                         }
 214                         /* dip */
 215                         else if(fast_dip_p(i,length))
 216                         {
 217                                 emit_quot(obj.value());
 218                                 emit(parent->special_objects[JIT_DIP]);
 219                                 i++;
 220                         }
 221                         /* 2dip */
 222                         else if(fast_2dip_p(i,length))
 223                         {
 224                                 emit_quot(obj.value());
 225                                 emit(parent->special_objects[JIT_2DIP]);
 226                                 i++;
 227                         }
 228                         /* 3dip */
 229                         else if(fast_3dip_p(i,length))
 230                         {
 231                                 emit_quot(obj.value());
 232                                 emit(parent->special_objects[JIT_3DIP]);
 233                                 i++;
 234                         }
 235                         else
 236                                 push(obj.value());
 237                         break;
 238                 case ARRAY_TYPE:
 239                         /* Method dispatch */
 240                         if(mega_lookup_p(i,length))
 241                         {
 242                                 if(stack_frame) emit(parent->special_objects[JIT_EPILOG]);
 243                                 tail_call = true;
 244                                 emit_mega_cache_lookup(
 245                                         array_nth(elements.untagged(),i),
 246                                         untag_fixnum(array_nth(elements.untagged(),i + 1)),
 247                                         array_nth(elements.untagged(),i + 2));
 248                                 i += 3;
 249                         }
 250                         /* Non-optimizing compiler ignores declarations */
 251                         else if(declare_p(i,length))
 252                                 i++;
 253                         else
 254                                 push(obj.value());
 255                         break;
 256                 default:
 257                         push(obj.value());
 258                         break;
 259                 }
 260         }
 261
 262         if(!tail_call)
 263         {
 264                 set_position(length);
 265
 266                 if(stack_frame) emit(parent->special_objects[JIT_EPILOG]);
 267                 emit(parent->special_objects[JIT_RETURN]);
 268         }
 269 }
 270
 271 void factor_vm::set_quot_entry_point(quotation *quot, code_block *code)
 272 {
 273         quot->code = code;
 274         quot->entry_point = code->entry_point();
 275 }
 276
 277 /* Allocates memory */
 278 code_block *factor_vm::jit_compile_quot(cell owner_, cell quot_, bool relocating)
 279 {
 280         data_root<object> owner(owner_,this);
 281         data_root<quotation> quot(quot_,this);
 282
 283         quotation_jit compiler(owner.value(),true,relocating,this);
 284         compiler.init_quotation(quot.value());
 285         compiler.iterate_quotation();
 286
 287         code_block *compiled = compiler.to_code_block();
 288
 289         if(relocating) initialize_code_block(compiled);
 290
 291         return compiled;
 292 }
 293
 294 void factor_vm::jit_compile_quot(cell quot_, bool relocating)
 295 {
 296         data_root<quotation> quot(quot_,this);
 297         if(!quot_compiled_p(quot.untagged()))
 298         {
 299                 code_block *compiled = jit_compile_quot(quot.value(),quot.value(),relocating);
 300                 set_quot_entry_point(quot.untagged(),compiled);
 301         }
 302 }
 303
 304 void factor_vm::primitive_jit_compile()
 305 {
 306         jit_compile_quot(ctx->pop(),true);
 307 }
 308
 309 code_block *factor_vm::lazy_jit_compile_block()
 310 {
 311         return untag<word>(special_objects[LAZY_JIT_COMPILE_WORD])->code;
 312 }
 313
 314 /* push a new quotation on the stack */
 315 void factor_vm::primitive_array_to_quotation()
 316 {
 317         quotation *quot = allot<quotation>(sizeof(quotation));
 318
 319         quot->array = ctx->peek();
 320         quot->cached_effect = false_object;
 321         quot->cache_counter = false_object;
 322         set_quot_entry_point(quot,lazy_jit_compile_block());
 323
 324         ctx->replace(tag<quotation>(quot));
 325 }
 326
 327 void factor_vm::primitive_quotation_code()
 328 {
 329         quotation *quot = untag_check<quotation>(ctx->pop());
 330
 331         ctx->push(from_unsigned_cell((cell)quot->code->entry_point()));
 332         ctx->push(from_unsigned_cell((cell)quot->code + quot->code->size()));
 333 }
 334
 335 /* Allocates memory */
 336 fixnum factor_vm::quot_code_offset_to_scan(cell quot_, cell offset)
 337 {
 338         data_root<quotation> quot(quot_,this);
 339         data_root<array> array(quot->array,this);
 340
 341         quotation_jit compiler(quot.value(),false,false,this);
 342         compiler.init_quotation(quot.value());
 343         compiler.compute_position(offset);
 344         compiler.iterate_quotation();
 345
 346         return compiler.get_position();
 347 }
 348
 349 cell factor_vm::lazy_jit_compile(cell quot_)
 350 {
 351         data_root<quotation> quot(quot_,this);
 352
 353         assert(!quot_compiled_p(quot.untagged()));
 354
 355         code_block *compiled = jit_compile_quot(quot.value(),quot.value(),true);
 356         set_quot_entry_point(quot.untagged(),compiled);
 357
 358         return quot.value();
 359 }
 360
 361 VM_C_API cell lazy_jit_compile(cell quot, factor_vm *parent)
 362 {
 363         return parent->lazy_jit_compile(quot);
 364 }
 365
 366 bool factor_vm::quot_compiled_p(quotation *quot)
 367 {
 368         return quot->code != NULL && quot->code != lazy_jit_compile_block();
 369 }
 370
 371 void factor_vm::primitive_quot_compiled_p()
 372 {
 373         tagged<quotation> quot(ctx->pop());
 374         quot.untag_check(this);
 375         ctx->push(tag_boolean(quot_compiled_p(quot.untagged())));
 376 }
 377
 378 cell factor_vm::find_all_quotations()
 379 {
 380         return instances(QUOTATION_TYPE);
 381 }
 382
 383 void factor_vm::initialize_all_quotations()
 384 {
 385         data_root<array> quotations(find_all_quotations(),this);
 386
 387         cell length = array_capacity(quotations.untagged());
 388         for(cell i = 0; i < length; i++)
 389         {
 390                 data_root<quotation> quot(array_nth(quotations.untagged(),i),this);
 391                 if(!quot->code)
 392                         set_quot_entry_point(quot.untagged(),lazy_jit_compile_block());
 393         }
 394 }
 395
 396 }