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::special_subprimitive_p(cell obj)
87 // Subprimitives should be flagged with whether they require a stack frame.
89 return obj == parent->special_objects[SIGNAL_HANDLER_WORD]
90 || obj == parent->special_objects[LEAF_SIGNAL_HANDLER_WORD]
91 || obj == parent->special_objects[FFI_SIGNAL_HANDLER_WORD]
92 || obj == parent->special_objects[FFI_LEAF_SIGNAL_HANDLER_WORD];
95 bool quotation_jit::word_stack_frame_p(cell obj)
97 return (to_boolean(untag<word>(obj)->subprimitive) && !special_subprimitive_p(obj))
98 || obj == parent->special_objects[JIT_PRIMITIVE_WORD];
101 bool quotation_jit::word_safepoint_p(cell obj)
103 return !special_subprimitive_p(obj);
106 bool quotation_jit::safepoint_p()
108 fixnum length = array_capacity(elements.untagged());
110 for(fixnum i = 0; i < length; i++)
112 cell obj = array_nth(elements.untagged(),i);
113 switch(tagged<object>(obj).type())
116 if(!word_safepoint_p(obj))
127 bool quotation_jit::stack_frame_p()
129 fixnum length = array_capacity(elements.untagged());
131 for(fixnum i = 0; i < length; i++)
133 cell obj = array_nth(elements.untagged(),i);
134 if (tagged<object>(obj).type() == WORD_TYPE && !word_safepoint_p(obj))
141 bool quotation_jit::trivial_quotation_p(array *elements)
143 return array_capacity(elements) == 1 && tagged<object>(array_nth(elements,0)).type_p(WORD_TYPE);
146 void quotation_jit::emit_prolog(bool safepoint, bool stack_frame)
148 if(safepoint) emit(parent->special_objects[JIT_SAFEPOINT]);
149 if(stack_frame) emit(parent->special_objects[JIT_PROLOG]);
152 void quotation_jit::emit_epilog(bool safepoint, bool stack_frame)
154 if(safepoint) emit(parent->special_objects[JIT_SAFEPOINT]);
155 if(stack_frame) emit(parent->special_objects[JIT_EPILOG]);
158 void quotation_jit::emit_quot(cell quot_)
160 data_root<quotation> quot(quot_,parent);
162 array *elements = untag<array>(quot->array);
164 /* If the quotation consists of a single word, compile a direct call
166 if(trivial_quotation_p(elements))
167 literal(array_nth(elements,0));
170 if(compiling) parent->jit_compile_quot(quot.value(),relocate);
171 literal(quot.value());
175 /* Allocates memory */
176 void quotation_jit::iterate_quotation()
178 bool safepoint = safepoint_p();
179 bool stack_frame = stack_frame_p();
183 emit_prolog(safepoint, stack_frame);
186 cell length = array_capacity(elements.untagged());
187 bool tail_call = false;
189 for(i = 0; i < length; i++)
193 data_root<object> obj(array_nth(elements.untagged(),i),parent);
199 if(to_boolean(obj.as<word>()->subprimitive))
201 tail_call = emit_subprimitive(obj.value(), /* word */
202 i == length - 1, /* tail_call_p */
203 stack_frame); /* stack_frame_p */
205 /* Everything else */
206 else if(i == length - 1)
208 emit_epilog(safepoint, stack_frame);
210 word_jump(obj.value());
213 word_call(obj.value());
216 push(obj.as<wrapper>()->object);
218 case BYTE_ARRAY_TYPE:
219 /* Primitive calls */
220 if(primitive_call_p(i,length))
222 /* On x86-64 and PowerPC, the VM pointer is stored in
223 a register; on other platforms, the RT_VM relocation
224 is used and it needs an offset parameter */
226 parameter(tag_fixnum(0));
228 parameter(obj.value());
229 parameter(false_object);
230 #ifdef FACTOR_PPC_TOC
231 parameter(obj.value());
232 parameter(false_object);
234 emit(parent->special_objects[JIT_PRIMITIVE]);
242 /* 'if' preceeded by two literal quotations (this is why if and ? are
243 mutually recursive in the library, but both still work) */
244 if(fast_if_p(i,length))
246 emit_epilog(safepoint, stack_frame);
249 emit_quot(array_nth(elements.untagged(),i));
250 emit_quot(array_nth(elements.untagged(),i + 1));
251 emit(parent->special_objects[JIT_IF]);
256 else if(fast_dip_p(i,length))
258 emit_quot(obj.value());
259 emit(parent->special_objects[JIT_DIP]);
263 else if(fast_2dip_p(i,length))
265 emit_quot(obj.value());
266 emit(parent->special_objects[JIT_2DIP]);
270 else if(fast_3dip_p(i,length))
272 emit_quot(obj.value());
273 emit(parent->special_objects[JIT_3DIP]);
280 /* Method dispatch */
281 if(mega_lookup_p(i,length))
283 emit_epilog(safepoint, stack_frame);
285 emit_mega_cache_lookup(
286 array_nth(elements.untagged(),i),
287 untag_fixnum(array_nth(elements.untagged(),i + 1)),
288 array_nth(elements.untagged(),i + 2));
291 /* Non-optimizing compiler ignores declarations */
292 else if(declare_p(i,length))
305 set_position(length);
307 emit_epilog(safepoint, stack_frame);
308 emit(parent->special_objects[JIT_RETURN]);
312 cell quotation_jit::word_stack_frame_size(cell obj)
314 if (special_subprimitive_p(obj))
315 return SIGNAL_HANDLER_STACK_FRAME_SIZE;
317 return JIT_FRAME_SIZE;
320 /* Allocates memory */
321 code_block *factor_vm::jit_compile_quot(cell owner_, cell quot_, bool relocating)
323 data_root<object> owner(owner_,this);
324 data_root<quotation> quot(quot_,this);
326 quotation_jit compiler(owner.value(),true,relocating,this);
327 compiler.init_quotation(quot.value());
328 compiler.iterate_quotation();
330 cell frame_size = compiler.word_stack_frame_size(owner_);
332 code_block *compiled = compiler.to_code_block(frame_size);
334 if(relocating) initialize_code_block(compiled);
339 void factor_vm::jit_compile_quot(cell quot_, bool relocating)
341 data_root<quotation> quot(quot_,this);
342 if(!quot_compiled_p(quot.untagged()))
344 code_block *compiled = jit_compile_quot(quot.value(),quot.value(),relocating);
345 quot.untagged()->entry_point = compiled->entry_point();
349 void factor_vm::primitive_jit_compile()
351 jit_compile_quot(ctx->pop(),true);
354 void *factor_vm::lazy_jit_compile_entry_point()
356 return untag<word>(special_objects[LAZY_JIT_COMPILE_WORD])->entry_point;
359 /* push a new quotation on the stack */
360 void factor_vm::primitive_array_to_quotation()
362 quotation *quot = allot<quotation>(sizeof(quotation));
364 quot->array = ctx->peek();
365 quot->cached_effect = false_object;
366 quot->cache_counter = false_object;
367 quot->entry_point = lazy_jit_compile_entry_point();
369 ctx->replace(tag<quotation>(quot));
372 void factor_vm::primitive_quotation_code()
374 quotation *quot = untag_check<quotation>(ctx->pop());
376 ctx->push(from_unsigned_cell((cell)quot->entry_point));
377 ctx->push(from_unsigned_cell((cell)quot->code() + quot->code()->size()));
380 /* Allocates memory */
381 fixnum factor_vm::quot_code_offset_to_scan(cell quot_, cell offset)
383 data_root<quotation> quot(quot_,this);
384 data_root<array> array(quot->array,this);
386 quotation_jit compiler(quot.value(),false,false,this);
387 compiler.init_quotation(quot.value());
388 compiler.compute_position(offset);
389 compiler.iterate_quotation();
391 return compiler.get_position();
394 cell factor_vm::lazy_jit_compile(cell quot_)
396 data_root<quotation> quot(quot_,this);
398 FACTOR_ASSERT(!quot_compiled_p(quot.untagged()));
400 code_block *compiled = jit_compile_quot(quot.value(),quot.value(),true);
401 quot.untagged()->entry_point = compiled->entry_point();
406 VM_C_API cell lazy_jit_compile(cell quot, factor_vm *parent)
408 return parent->lazy_jit_compile(quot);
411 bool factor_vm::quot_compiled_p(quotation *quot)
413 return quot->entry_point != NULL && quot->entry_point != lazy_jit_compile_entry_point();
416 void factor_vm::primitive_quot_compiled_p()
418 tagged<quotation> quot(ctx->pop());
419 quot.untag_check(this);
420 ctx->push(tag_boolean(quot_compiled_p(quot.untagged())));
423 cell factor_vm::find_all_quotations()
425 return instances(QUOTATION_TYPE);
428 void factor_vm::initialize_all_quotations()
430 data_root<array> quotations(find_all_quotations(),this);
432 cell length = array_capacity(quotations.untagged());
433 for(cell i = 0; i < length; i++)
435 data_root<quotation> quot(array_nth(quotations.untagged(),i),this);
436 if(!quot->entry_point)
437 quot.untagged()->entry_point = lazy_jit_compile_entry_point();