6 /* Simple non-optimizing compiler.
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.
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.
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.
19 It actually does do a little bit of very simple optimization:
21 1) Tail call optimization.
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
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.
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.
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. */
39 void quotation_jit::init_quotation(cell quot)
41 elements = untag<quotation>(quot)->array;
44 bool quotation_jit::primitive_call_p(cell i, cell length)
46 return (i + 2) == length && array_nth(elements.untagged(),i + 1) == parent->special_objects[JIT_PRIMITIVE_WORD];
49 bool quotation_jit::fast_if_p(cell i, cell length)
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];
56 bool quotation_jit::fast_dip_p(cell i, cell length)
58 return (i + 2) <= length && array_nth(elements.untagged(),i + 1) == parent->special_objects[JIT_DIP_WORD];
61 bool quotation_jit::fast_2dip_p(cell i, cell length)
63 return (i + 2) <= length && array_nth(elements.untagged(),i + 1) == parent->special_objects[JIT_2DIP_WORD];
66 bool quotation_jit::fast_3dip_p(cell i, cell length)
68 return (i + 2) <= length && array_nth(elements.untagged(),i + 1) == parent->special_objects[JIT_3DIP_WORD];
71 bool quotation_jit::mega_lookup_p(cell i, cell length)
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];
79 bool quotation_jit::declare_p(cell i, cell length)
81 return (i + 2) <= length
82 && array_nth(elements.untagged(),i + 1) == parent->special_objects[JIT_DECLARE_WORD];
85 bool quotation_jit::stack_frame_p()
87 fixnum length = array_capacity(elements.untagged());
90 for(i = 0; i < length - 1; i++)
92 cell obj = array_nth(elements.untagged(),i);
93 switch(tagged<object>(obj).type())
96 if(!parent->to_boolean(untag<word>(obj)->subprimitive))
100 if(fast_dip_p(i,length) || fast_2dip_p(i,length) || fast_3dip_p(i,length))
111 bool quotation_jit::trivial_quotation_p(array *elements)
113 return array_capacity(elements) == 1 && tagged<object>(array_nth(elements,0)).type_p(WORD_TYPE);
116 void quotation_jit::emit_quot(cell quot_)
118 data_root<quotation> quot(quot_,parent);
120 array *elements = untag<array>(quot->array);
122 /* If the quotation consists of a single word, compile a direct call
124 if(trivial_quotation_p(elements))
125 literal(array_nth(elements,0));
128 if(compiling) parent->jit_compile_quot(quot.value(),relocate);
129 literal(quot.value());
133 /* Allocates memory */
134 void quotation_jit::iterate_quotation()
136 bool stack_frame = stack_frame_p();
141 emit(parent->special_objects[JIT_PROLOG]);
144 cell length = array_capacity(elements.untagged());
145 bool tail_call = false;
147 for(i = 0; i < length; i++)
151 data_root<object> obj(array_nth(elements.untagged(),i),parent);
157 if(parent->to_boolean(obj.as<word>()->subprimitive))
158 emit_subprimitive(obj.value());
159 /* The (execute) primitive is special-cased */
160 else if(obj.value() == parent->special_objects[JIT_EXECUTE_WORD])
164 if(stack_frame) emit(parent->special_objects[JIT_EPILOG]);
166 emit(parent->special_objects[JIT_EXECUTE_JUMP]);
169 emit(parent->special_objects[JIT_EXECUTE_CALL]);
171 /* Everything else */
176 if(stack_frame) emit(parent->special_objects[JIT_EPILOG]);
178 /* Inline cache misses are special-cased.
179 The calling convention for tail
180 calls stores the address of the next
181 instruction in a register. However,
182 PIC miss stubs themselves tail-call
183 the inline cache miss primitive, and
184 we don't want to clobber the saved
186 if(obj.value() == parent->special_objects[PIC_MISS_WORD]
187 || obj.value() == parent->special_objects[PIC_MISS_TAIL_WORD])
189 word_special(obj.value());
193 word_jump(obj.value());
197 word_call(obj.value());
201 push(obj.as<wrapper>()->object);
204 /* Primitive calls */
205 if(primitive_call_p(i,length))
207 literal(tag_fixnum(0));
208 literal(obj.value());
209 emit(parent->special_objects[JIT_PRIMITIVE]);
219 /* 'if' preceeded by two literal quotations (this is why if and ? are
220 mutually recursive in the library, but both still work) */
221 if(fast_if_p(i,length))
223 if(stack_frame) emit(parent->special_objects[JIT_EPILOG]);
226 emit_quot(array_nth(elements.untagged(),i));
227 emit_quot(array_nth(elements.untagged(),i + 1));
228 emit(parent->special_objects[JIT_IF]);
233 else if(fast_dip_p(i,length))
235 emit_quot(obj.value());
236 emit(parent->special_objects[JIT_DIP]);
240 else if(fast_2dip_p(i,length))
242 emit_quot(obj.value());
243 emit(parent->special_objects[JIT_2DIP]);
247 else if(fast_3dip_p(i,length))
249 emit_quot(obj.value());
250 emit(parent->special_objects[JIT_3DIP]);
257 /* Method dispatch */
258 if(mega_lookup_p(i,length))
260 emit_mega_cache_lookup(
261 array_nth(elements.untagged(),i),
262 untag_fixnum(array_nth(elements.untagged(),i + 1)),
263 array_nth(elements.untagged(),i + 2));
267 /* Non-optimizing compiler ignores declarations */
268 else if(declare_p(i,length))
281 set_position(length);
284 emit(parent->special_objects[JIT_EPILOG]);
285 emit(parent->special_objects[JIT_RETURN]);
289 void factor_vm::set_quot_xt(quotation *quot, code_block *code)
292 quot->xt = code->xt();
295 /* Allocates memory */
296 code_block *factor_vm::jit_compile_quot(cell owner_, cell quot_, bool relocating)
298 data_root<object> owner(owner_,this);
299 data_root<quotation> quot(quot_,this);
301 quotation_jit compiler(owner.value(),true,relocating,this);
302 compiler.init_quotation(quot.value());
303 compiler.iterate_quotation();
305 code_block *compiled = compiler.to_code_block();
307 if(relocating) relocate_code_block(compiled);
312 void factor_vm::jit_compile_quot(cell quot_, bool relocating)
314 data_root<quotation> quot(quot_,this);
316 if(quot->code) return;
318 code_block *compiled = jit_compile_quot(quot.value(),quot.value(),relocating);
319 set_quot_xt(quot.untagged(),compiled);
322 void factor_vm::primitive_jit_compile()
324 jit_compile_quot(dpop(),true);
327 /* push a new quotation on the stack */
328 void factor_vm::primitive_array_to_quotation()
330 quotation *quot = allot<quotation>(sizeof(quotation));
331 quot->array = dpeek();
332 quot->cached_effect = false_object;
333 quot->cache_counter = false_object;
334 quot->xt = (void *)lazy_jit_compile;
336 drepl(tag<quotation>(quot));
339 void factor_vm::primitive_quotation_xt()
341 quotation *quot = untag_check<quotation>(dpeek());
342 drepl(allot_cell((cell)quot->xt));
345 /* Compile a word definition with the non-optimizing compiler. Allocates memory */
346 void factor_vm::jit_compile_word(cell word_, cell def_, bool relocating)
348 data_root<word> word(word_,this);
349 data_root<quotation> def(def_,this);
351 code_block *compiled = jit_compile_quot(word.value(),def.value(),relocating);
352 word->code = compiled;
354 if(to_boolean(word->pic_def)) jit_compile_quot(word->pic_def,relocating);
355 if(to_boolean(word->pic_tail_def)) jit_compile_quot(word->pic_tail_def,relocating);
358 void factor_vm::compile_all_words()
360 data_root<array> words(find_all_words(),this);
363 cell length = array_capacity(words.untagged());
364 for(i = 0; i < length; i++)
366 data_root<word> word(array_nth(words.untagged(),i),this);
368 if(!word->code || !word->code->optimized_p())
369 jit_compile_word(word.value(),word->def,false);
371 update_word_xt(word.untagged());
376 /* Allocates memory */
377 fixnum factor_vm::quot_code_offset_to_scan(cell quot_, cell offset)
379 data_root<quotation> quot(quot_,this);
380 data_root<array> array(quot->array,this);
382 quotation_jit compiler(quot.value(),false,false,this);
383 compiler.init_quotation(quot.value());
384 compiler.compute_position(offset);
385 compiler.iterate_quotation();
387 return compiler.get_position();
390 cell factor_vm::lazy_jit_compile_impl(cell quot_, stack_frame *stack)
392 data_root<quotation> quot(quot_,this);
393 ctx->callstack_top = stack;
394 jit_compile_quot(quot.value(),true);
398 VM_ASM_API cell lazy_jit_compile_impl(cell quot_, stack_frame *stack, factor_vm *parent)
400 return parent->lazy_jit_compile_impl(quot_,stack);
403 void factor_vm::primitive_quot_compiled_p()
405 tagged<quotation> quot(dpop());
406 quot.untag_check(this);
407 dpush(tag_boolean(quot->code != NULL));