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