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 core/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 core/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 bool quotation_jit::primitive_call_p(cell i)
  40 {
  41         return (i + 2) == array_capacity(elements.untagged())
  42                 && tagged<object>(array_nth(elements.untagged(),i)).type_p(FIXNUM_TYPE)
  43                 && array_nth(elements.untagged(),i + 1) == parent_vm->userenv[JIT_PRIMITIVE_WORD];
  44 }
  45
  46 bool quotation_jit::fast_if_p(cell i)
  47 {
  48         return (i + 3) == array_capacity(elements.untagged())
  49                 && tagged<object>(array_nth(elements.untagged(),i)).type_p(QUOTATION_TYPE)
  50                 && tagged<object>(array_nth(elements.untagged(),i + 1)).type_p(QUOTATION_TYPE)
  51                 && array_nth(elements.untagged(),i + 2) == parent_vm->userenv[JIT_IF_WORD];
  52 }
  53
  54 bool quotation_jit::fast_dip_p(cell i)
  55 {
  56         return (i + 2) <= array_capacity(elements.untagged())
  57                 && tagged<object>(array_nth(elements.untagged(),i)).type_p(QUOTATION_TYPE)
  58                 && array_nth(elements.untagged(),i + 1) == parent_vm->userenv[JIT_DIP_WORD];
  59 }
  60
  61 bool quotation_jit::fast_2dip_p(cell i)
  62 {
  63         return (i + 2) <= array_capacity(elements.untagged())
  64                 && tagged<object>(array_nth(elements.untagged(),i)).type_p(QUOTATION_TYPE)
  65                 && array_nth(elements.untagged(),i + 1) == parent_vm->userenv[JIT_2DIP_WORD];
  66 }
  67
  68 bool quotation_jit::fast_3dip_p(cell i)
  69 {
  70         return (i + 2) <= array_capacity(elements.untagged())
  71                 && tagged<object>(array_nth(elements.untagged(),i)).type_p(QUOTATION_TYPE)
  72                 && array_nth(elements.untagged(),i + 1) == parent_vm->userenv[JIT_3DIP_WORD];
  73 }
  74
  75 bool quotation_jit::mega_lookup_p(cell i)
  76 {
  77         return (i + 3) < array_capacity(elements.untagged())
  78                 && tagged<object>(array_nth(elements.untagged(),i)).type_p(ARRAY_TYPE)
  79                 && tagged<object>(array_nth(elements.untagged(),i + 1)).type_p(FIXNUM_TYPE)
  80                 && tagged<object>(array_nth(elements.untagged(),i + 2)).type_p(ARRAY_TYPE)
  81                 && array_nth(elements.untagged(),i + 3) == parent_vm->userenv[MEGA_LOOKUP_WORD];
  82 }
  83
  84 bool quotation_jit::stack_frame_p()
  85 {
  86         fixnum length = array_capacity(elements.untagged());
  87         fixnum i;
  88
  89         for(i = 0; i < length - 1; i++)
  90         {
  91                 cell obj = array_nth(elements.untagged(),i);
  92                 switch(tagged<object>(obj).type())
  93                 {
  94                 case WORD_TYPE:
  95                         if(parent_vm->untag<word>(obj)->subprimitive == F)
  96                                 return true;
  97                         break;
  98                 case QUOTATION_TYPE:
  99                         if(fast_dip_p(i) || fast_2dip_p(i) || fast_3dip_p(i))
 100                                 return true;
 101                         break;
 102                 default:
 103                         break;
 104                 }
 105         }
 106
 107         return false;
 108 }
 109
 110 /* Allocates memory */
 111 void quotation_jit::iterate_quotation()
 112 {
 113         bool stack_frame = stack_frame_p();
 114
 115         set_position(0);
 116
 117         if(stack_frame)
 118                 emit(parent_vm->userenv[JIT_PROLOG]);
 119
 120         cell i;
 121         cell length = array_capacity(elements.untagged());
 122         bool tail_call = false;
 123
 124         for(i = 0; i < length; i++)
 125         {
 126                 set_position(i);
 127
 128                 gc_root<object> obj(array_nth(elements.untagged(),i),parent_vm);
 129
 130                 switch(obj.type())
 131                 {
 132                 case WORD_TYPE:
 133                         /* Intrinsics */
 134                         if(obj.as<word>()->subprimitive != F)
 135                                 emit_subprimitive(obj.value());
 136                         /* The (execute) primitive is special-cased */
 137                         else if(obj.value() == parent_vm->userenv[JIT_EXECUTE_WORD])
 138                         {
 139                                 if(i == length - 1)
 140                                 {
 141                                         if(stack_frame) emit(parent_vm->userenv[JIT_EPILOG]);
 142                                         tail_call = true;
 143                                         emit(parent_vm->userenv[JIT_EXECUTE_JUMP]);
 144                                 }
 145                                 else
 146                                         emit(parent_vm->userenv[JIT_EXECUTE_CALL]);
 147                         }
 148                         /* Everything else */
 149                         else
 150                         {
 151                                 if(i == length - 1)
 152                                 {
 153                                         if(stack_frame) emit(parent_vm->userenv[JIT_EPILOG]);
 154                                         tail_call = true;
 155                                         /* Inline cache misses are special-cased.
 156                                            The calling convention for tail
 157                                            calls stores the address of the next
 158                                            instruction in a register. However,
 159                                            PIC miss stubs themselves tail-call
 160                                            the inline cache miss primitive, and
 161                                            we don't want to clobber the saved
 162                                            address. */
 163                                         if(obj.value() == parent_vm->userenv[PIC_MISS_WORD]
 164                                            || obj.value() == parent_vm->userenv[PIC_MISS_TAIL_WORD])
 165                                         {
 166                                                 word_special(obj.value());
 167                                         }
 168                                         else
 169                                         {
 170                                                 word_jump(obj.value());
 171                                         }
 172                                 }
 173                                 else
 174                                         word_call(obj.value());
 175                         }
 176                         break;
 177                 case WRAPPER_TYPE:
 178                         push(obj.as<wrapper>()->object);
 179                         break;
 180                 case FIXNUM_TYPE:
 181                         /* Primitive calls */
 182                         if(primitive_call_p(i))
 183                         {
 184                                 emit_with(parent_vm->userenv[JIT_PRIMITIVE],obj.value());
 185
 186                                 i++;
 187
 188                                 tail_call = true;
 189                                 break;
 190                         }
 191                 case QUOTATION_TYPE:
 192                         /* 'if' preceeded by two literal quotations (this is why if and ? are
 193                            mutually recursive in the library, but both still work) */
 194                         if(fast_if_p(i))
 195                         {
 196                                 if(stack_frame) emit(parent_vm->userenv[JIT_EPILOG]);
 197                                 tail_call = true;
 198
 199                                 if(compiling)
 200                                 {
 201                                         parent_vm->jit_compile(array_nth(elements.untagged(),i),relocate);
 202                                         parent_vm->jit_compile(array_nth(elements.untagged(),i + 1),relocate);
 203                                 }
 204
 205                                 literal(array_nth(elements.untagged(),i));
 206                                 literal(array_nth(elements.untagged(),i + 1));
 207                                 emit(parent_vm->userenv[JIT_IF]);
 208
 209                                 i += 2;
 210
 211                                 break;
 212                         }
 213                         /* dip */
 214                         else if(fast_dip_p(i))
 215                         {
 216                                 if(compiling)
 217                                         parent_vm->jit_compile(obj.value(),relocate);
 218                                 emit_with(parent_vm->userenv[JIT_DIP],obj.value());
 219                                 i++;
 220                                 break;
 221                         }
 222                         /* 2dip */
 223                         else if(fast_2dip_p(i))
 224                         {
 225                                 if(compiling)
 226                                         parent_vm->jit_compile(obj.value(),relocate);
 227                                 emit_with(parent_vm->userenv[JIT_2DIP],obj.value());
 228                                 i++;
 229                                 break;
 230                         }
 231                         /* 3dip */
 232                         else if(fast_3dip_p(i))
 233                         {
 234                                 if(compiling)
 235                                         parent_vm->jit_compile(obj.value(),relocate);
 236                                 emit_with(parent_vm->userenv[JIT_3DIP],obj.value());
 237                                 i++;
 238                                 break;
 239                         }
 240                 case ARRAY_TYPE:
 241                         /* Method dispatch */
 242                         if(mega_lookup_p(i))
 243                         {
 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                                 tail_call = true;
 250                                 break;
 251                         }
 252                 default:
 253                         push(obj.value());
 254                         break;
 255                 }
 256         }
 257
 258         if(!tail_call)
 259         {
 260                 set_position(length);
 261
 262                 if(stack_frame)
 263                         emit(parent_vm->userenv[JIT_EPILOG]);
 264                 emit(parent_vm->userenv[JIT_RETURN]);
 265         }
 266 }
 267
 268 void factor_vm::set_quot_xt(quotation *quot, code_block *code)
 269 {
 270         if(code->type != QUOTATION_TYPE)
 271                 critical_error("Bad param to set_quot_xt",(cell)code);
 272
 273         quot->code = code;
 274         quot->xt = code->xt();
 275 }
 276
 277 /* Allocates memory */
 278 void factor_vm::jit_compile(cell quot_, bool relocating)
 279 {
 280         gc_root<quotation> quot(quot_,this);
 281         if(quot->code) return;
 282
 283         quotation_jit compiler(quot.value(),true,relocating,this);
 284         compiler.iterate_quotation();
 285
 286         code_block *compiled = compiler.to_code_block();
 287         set_quot_xt(quot.untagged(),compiled);
 288
 289         if(relocating) relocate_code_block(compiled);
 290 }
 291
 292 inline void factor_vm::primitive_jit_compile()
 293 {
 294         jit_compile(dpop(),true);
 295 }
 296
 297 PRIMITIVE(jit_compile)
 298 {
 299         PRIMITIVE_GETVM()->primitive_jit_compile();
 300 }
 301
 302 /* push a new quotation on the stack */
 303 inline void factor_vm::primitive_array_to_quotation()
 304 {
 305         quotation *quot = allot<quotation>(sizeof(quotation));
 306         quot->array = dpeek();
 307         quot->cached_effect = F;
 308         quot->cache_counter = F;
 309         quot->xt = (void *)lazy_jit_compile;
 310         quot->code = NULL;
 311         drepl(tag<quotation>(quot));
 312 }
 313
 314 PRIMITIVE(array_to_quotation)
 315 {
 316         PRIMITIVE_GETVM()->primitive_array_to_quotation();
 317 }
 318
 319 inline void factor_vm::primitive_quotation_xt()
 320 {
 321         quotation *quot = untag_check<quotation>(dpeek());
 322         drepl(allot_cell((cell)quot->xt));
 323 }
 324
 325 PRIMITIVE(quotation_xt)
 326 {
 327         PRIMITIVE_GETVM()->primitive_quotation_xt();
 328 }
 329
 330 void factor_vm::compile_all_words()
 331 {
 332         gc_root<array> words(find_all_words(),this);
 333
 334         cell i;
 335         cell length = array_capacity(words.untagged());
 336         for(i = 0; i < length; i++)
 337         {
 338                 gc_root<word> word(array_nth(words.untagged(),i),this);
 339
 340                 if(!word->code || !word_optimized_p(word.untagged()))
 341                         jit_compile_word(word.value(),word->def,false);
 342
 343                 update_word_xt(word.value());
 344
 345         }
 346
 347         iterate_code_heap(factor::relocate_code_block);
 348 }
 349
 350 /* Allocates memory */
 351 fixnum factor_vm::quot_code_offset_to_scan(cell quot_, cell offset)
 352 {
 353         gc_root<quotation> quot(quot_,this);
 354         gc_root<array> array(quot->array,this);
 355
 356         quotation_jit compiler(quot.value(),false,false,this);
 357         compiler.compute_position(offset);
 358         compiler.iterate_quotation();
 359
 360         return compiler.get_position();
 361 }
 362
 363 cell factor_vm::lazy_jit_compile_impl(cell quot_, stack_frame *stack)
 364 {
 365         gc_root<quotation> quot(quot_,this);
 366         stack_chain->callstack_top = stack;
 367         jit_compile(quot.value(),true);
 368         return quot.value();
 369 }
 370
 371 VM_ASM_API cell lazy_jit_compile_impl(cell quot_, stack_frame *stack, factor_vm *myvm)
 372 {
 373         ASSERTVM();
 374         return VM_PTR->lazy_jit_compile_impl(quot_,stack);
 375 }
 376
 377 inline void factor_vm::primitive_quot_compiled_p()
 378 {
 379         tagged<quotation> quot(dpop());
 380         quot.untag_check(this);
 381         dpush(tag_boolean(quot->code != NULL));
 382 }
 383
 384 PRIMITIVE(quot_compiled_p)
 385 {
 386         PRIMITIVE_GETVM()->primitive_quot_compiled_p();
 387 }
 388
 389 }