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 FIXNUM_TYPE:
 182                         /* Primitive calls */
 183                         if(primitive_call_p(i,length))
 184                         {
 185                                 parameter(tag_fixnum(0));
 186                                 parameter(obj.value());
 187                                 emit(parent->special_objects[JIT_PRIMITIVE]);
 188
 189                                 i++;
 190                         }
 191                         else
 192                                 push(obj.value());
 193                         break;
 194                 case QUOTATION_TYPE:
 195                         /* 'if' preceeded by two literal quotations (this is why if and ? are
 196                            mutually recursive in the library, but both still work) */
 197                         if(fast_if_p(i,length))
 198                         {
 199                                 if(stack_frame) emit(parent->special_objects[JIT_EPILOG]);
 200                                 tail_call = true;
 201
 202                                 emit_quot(array_nth(elements.untagged(),i));
 203                                 emit_quot(array_nth(elements.untagged(),i + 1));
 204                                 emit(parent->special_objects[JIT_IF]);
 205
 206                                 i += 2;
 207                         }
 208                         /* dip */
 209                         else if(fast_dip_p(i,length))
 210                         {
 211                                 emit_quot(obj.value());
 212                                 emit(parent->special_objects[JIT_DIP]);
 213                                 i++;
 214                         }
 215                         /* 2dip */
 216                         else if(fast_2dip_p(i,length))
 217                         {
 218                                 emit_quot(obj.value());
 219                                 emit(parent->special_objects[JIT_2DIP]);
 220                                 i++;
 221                         }
 222                         /* 3dip */
 223                         else if(fast_3dip_p(i,length))
 224                         {
 225                                 emit_quot(obj.value());
 226                                 emit(parent->special_objects[JIT_3DIP]);
 227                                 i++;
 228                         }
 229                         else
 230                                 push(obj.value());
 231                         break;
 232                 case ARRAY_TYPE:
 233                         /* Method dispatch */
 234                         if(mega_lookup_p(i,length))
 235                         {
 236                                 if(stack_frame) emit(parent->special_objects[JIT_EPILOG]);
 237                                 tail_call = true;
 238                                 emit_mega_cache_lookup(
 239                                         array_nth(elements.untagged(),i),
 240                                         untag_fixnum(array_nth(elements.untagged(),i + 1)),
 241                                         array_nth(elements.untagged(),i + 2));
 242                                 i += 3;
 243                         }
 244                         /* Non-optimizing compiler ignores declarations */
 245                         else if(declare_p(i,length))
 246                                 i++;
 247                         else
 248                                 push(obj.value());
 249                         break;
 250                 default:
 251                         push(obj.value());
 252                         break;
 253                 }
 254         }
 255
 256         if(!tail_call)
 257         {
 258                 set_position(length);
 259
 260                 if(stack_frame) emit(parent->special_objects[JIT_EPILOG]);
 261                 emit(parent->special_objects[JIT_RETURN]);
 262         }
 263 }
 264
 265 void factor_vm::set_quot_xt(quotation *quot, code_block *code)
 266 {
 267         quot->code = code;
 268         quot->xt = code->xt();
 269 }
 270
 271 /* Allocates memory */
 272 code_block *factor_vm::jit_compile_quot(cell owner_, cell quot_, bool relocating)
 273 {
 274         data_root<object> owner(owner_,this);
 275         data_root<quotation> quot(quot_,this);
 276
 277         quotation_jit compiler(owner.value(),true,relocating,this);
 278         compiler.init_quotation(quot.value());
 279         compiler.iterate_quotation();
 280
 281         code_block *compiled = compiler.to_code_block();
 282
 283         if(relocating) initialize_code_block(compiled);
 284
 285         return compiled;
 286 }
 287
 288 void factor_vm::jit_compile_quot(cell quot_, bool relocating)
 289 {
 290         data_root<quotation> quot(quot_,this);
 291
 292         if(quot->code) return;
 293
 294         code_block *compiled = jit_compile_quot(quot.value(),quot.value(),relocating);
 295         set_quot_xt(quot.untagged(),compiled);
 296 }
 297
 298 void factor_vm::primitive_jit_compile()
 299 {
 300         jit_compile_quot(ctx->pop(),true);
 301 }
 302
 303 /* push a new quotation on the stack */
 304 void factor_vm::primitive_array_to_quotation()
 305 {
 306         quotation *quot = allot<quotation>(sizeof(quotation));
 307         quot->array = ctx->peek();
 308         quot->cached_effect = false_object;
 309         quot->cache_counter = false_object;
 310         quot->xt = (void *)lazy_jit_compile;
 311         quot->code = NULL;
 312         ctx->replace(tag<quotation>(quot));
 313 }
 314
 315 void factor_vm::primitive_quotation_xt()
 316 {
 317         quotation *quot = untag_check<quotation>(ctx->peek());
 318         ctx->replace(allot_cell((cell)quot->xt));
 319 }
 320
 321 /* Allocates memory */
 322 fixnum factor_vm::quot_code_offset_to_scan(cell quot_, cell offset)
 323 {
 324         data_root<quotation> quot(quot_,this);
 325         data_root<array> array(quot->array,this);
 326
 327         quotation_jit compiler(quot.value(),false,false,this);
 328         compiler.init_quotation(quot.value());
 329         compiler.compute_position(offset);
 330         compiler.iterate_quotation();
 331
 332         return compiler.get_position();
 333 }
 334
 335 cell factor_vm::lazy_jit_compile_impl(cell quot_)
 336 {
 337         data_root<quotation> quot(quot_,this);
 338         jit_compile_quot(quot.value(),true);
 339         return quot.value();
 340 }
 341
 342 VM_C_API cell lazy_jit_compile_impl(cell quot, factor_vm *parent)
 343 {
 344         return parent->lazy_jit_compile_impl(quot);
 345 }
 346
 347 void factor_vm::primitive_quot_compiled_p()
 348 {
 349         tagged<quotation> quot(ctx->pop());
 350         quot.untag_check(this);
 351         ctx->push(tag_boolean(quot->code != NULL));
 352 }
 353
 354 }