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) == 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) == 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) == 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) == 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) == 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) == 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(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(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));
 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() == userenv[JIT_EXECUTE_WORD])
 138                         {
 139                                 if(i == length - 1)
 140                                 {
 141                                         if(stack_frame) emit(userenv[JIT_EPILOG]);
 142                                         tail_call = true;
 143                                         emit(userenv[JIT_EXECUTE_JUMP]);
 144                                 }
 145                                 else
 146                                         emit(userenv[JIT_EXECUTE_CALL]);
 147                         }
 148                         /* Everything else */
 149                         else
 150                         {
 151                                 if(i == length - 1)
 152                                 {
 153                                         if(stack_frame) emit(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() == userenv[PIC_MISS_WORD]
 164                                            || obj.value() == 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(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(userenv[JIT_EPILOG]);
 197                                 tail_call = true;
 198
 199                                 if(compiling)
 200                                 {
 201                                         jit_compile(array_nth(elements.untagged(),i),relocate);
 202                                         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(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                                         jit_compile(obj.value(),relocate);
 218                                 emit_with(userenv[JIT_DIP],obj.value());
 219                                 i++;
 220                                 break;
 221                         }
 222                         /* 2dip */
 223                         else if(fast_2dip_p(i))
 224                         {
 225                                 if(compiling)
 226                                         jit_compile(obj.value(),relocate);
 227                                 emit_with(userenv[JIT_2DIP],obj.value());
 228                                 i++;
 229                                 break;
 230                         }
 231                         /* 3dip */
 232                         else if(fast_3dip_p(i))
 233                         {
 234                                 if(compiling)
 235                                         jit_compile(obj.value(),relocate);
 236                                 emit_with(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(userenv[JIT_EPILOG]);
 264                 emit(userenv[JIT_RETURN]);
 265         }
 266 }
 267
 268 void 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 jit_compile(cell quot_, bool relocating)
 279 {
 280         gc_root<quotation> quot(quot_);
 281         if(quot->code) return;
 282
 283         quotation_jit compiler(quot.value(),true,relocating);
 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 PRIMITIVE(jit_compile)
 293 {
 294         jit_compile(dpop(),true);
 295 }
 296
 297 /* push a new quotation on the stack */
 298 PRIMITIVE(array_to_quotation)
 299 {
 300         quotation *quot = allot<quotation>(sizeof(quotation));
 301         quot->array = dpeek();
 302         quot->cached_effect = F;
 303         quot->cache_counter = F;
 304         quot->xt = (void *)lazy_jit_compile;
 305         quot->code = NULL;
 306         drepl(tag<quotation>(quot));
 307 }
 308
 309 PRIMITIVE(quotation_xt)
 310 {
 311         quotation *quot = untag_check<quotation>(dpeek());
 312         drepl(allot_cell((cell)quot->xt));
 313 }
 314
 315 void compile_all_words()
 316 {
 317         gc_root<array> words(find_all_words());
 318
 319         cell i;
 320         cell length = array_capacity(words.untagged());
 321         for(i = 0; i < length; i++)
 322         {
 323                 gc_root<word> word(array_nth(words.untagged(),i));
 324
 325                 if(!word->code || !word_optimized_p(word.untagged()))
 326                         jit_compile_word(word.value(),word->def,false);
 327
 328                 update_word_xt(word.value());
 329
 330         }
 331
 332         iterate_code_heap(relocate_code_block);
 333 }
 334
 335 /* Allocates memory */
 336 fixnum quot_code_offset_to_scan(cell quot_, cell offset)
 337 {
 338         gc_root<quotation> quot(quot_);
 339         gc_root<array> array(quot->array);
 340
 341         quotation_jit compiler(quot.value(),false,false);
 342         compiler.compute_position(offset);
 343         compiler.iterate_quotation();
 344
 345         return compiler.get_position();
 346 }
 347
 348 VM_ASM_API cell lazy_jit_compile_impl(cell quot_, stack_frame *stack)
 349 {
 350         gc_root<quotation> quot(quot_);
 351         stack_chain->callstack_top = stack;
 352         jit_compile(quot.value(),true);
 353         return quot.value();
 354 }
 355
 356 PRIMITIVE(quot_compiled_p)
 357 {
 358         tagged<quotation> quot(dpop());
 359         quot.untag_check();
 360         dpush(tag_boolean(quot->code != NULL));
 361 }
 362
 363 }