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]
93 || obj == parent->special_objects[UNWIND_NATIVE_FRAMES_WORD];
96 bool quotation_jit::word_stack_frame_p(cell obj)
98 return (to_boolean(untag<word>(obj)->subprimitive) && !special_subprimitive_p(obj))
99 || obj == parent->special_objects[JIT_PRIMITIVE_WORD];
102 bool quotation_jit::word_safepoint_p(cell obj)
104 return !special_subprimitive_p(obj);
107 bool quotation_jit::safepoint_p()
109 fixnum length = array_capacity(elements.untagged());
111 for(fixnum i = 0; i < length; i++)
113 cell obj = array_nth(elements.untagged(),i);
114 switch(tagged<object>(obj).type())
117 if(!word_safepoint_p(obj))
128 bool quotation_jit::stack_frame_p()
130 fixnum length = array_capacity(elements.untagged());
132 for(fixnum i = 0; i < length; i++)
134 cell obj = array_nth(elements.untagged(),i);
135 if (tagged<object>(obj).type() == WORD_TYPE && !word_safepoint_p(obj))
142 bool quotation_jit::trivial_quotation_p(array *elements)
144 return array_capacity(elements) == 1 && tagged<object>(array_nth(elements,0)).type_p(WORD_TYPE);
147 void quotation_jit::emit_prolog(bool safepoint, bool stack_frame)
149 if(safepoint) emit(parent->special_objects[JIT_SAFEPOINT]);
150 if(stack_frame) emit(parent->special_objects[JIT_PROLOG]);
153 void quotation_jit::emit_epilog(bool safepoint, bool stack_frame)
155 if(safepoint) emit(parent->special_objects[JIT_SAFEPOINT]);
156 if(stack_frame) emit(parent->special_objects[JIT_EPILOG]);
159 /* Allocates memory conditionally */
160 void quotation_jit::emit_quot(cell quot_)
162 data_root<quotation> quot(quot_,parent);
164 array *elements = untag<array>(quot->array);
166 /* If the quotation consists of a single word, compile a direct call
168 if(trivial_quotation_p(elements))
169 literal(array_nth(elements,0));
172 if(compiling) parent->jit_compile_quot(quot.value(),relocate);
173 literal(quot.value());
177 /* Allocates memory */
178 void quotation_jit::iterate_quotation()
180 bool safepoint = safepoint_p();
181 bool stack_frame = stack_frame_p();
185 emit_prolog(safepoint, stack_frame);
188 cell length = array_capacity(elements.untagged());
189 bool tail_call = false;
191 for(i = 0; i < length; i++)
195 data_root<object> obj(array_nth(elements.untagged(),i),parent);
201 if(to_boolean(obj.as<word>()->subprimitive))
203 tail_call = emit_subprimitive(obj.value(), /* word */
204 i == length - 1, /* tail_call_p */
205 stack_frame); /* stack_frame_p */
207 /* Everything else */
208 else if(i == length - 1)
210 emit_epilog(safepoint, stack_frame);
212 word_jump(obj.value());
215 word_call(obj.value());
218 push(obj.as<wrapper>()->object);
220 case BYTE_ARRAY_TYPE:
221 /* Primitive calls */
222 if(primitive_call_p(i,length))
224 /* On x86-64 and PowerPC, the VM pointer is stored in
225 a register; on other platforms, the RT_VM relocation
226 is used and it needs an offset parameter */
228 parameter(tag_fixnum(0));
230 parameter(obj.value());
231 parameter(false_object);
232 #ifdef FACTOR_PPC_TOC
233 parameter(obj.value());
234 parameter(false_object);
236 emit(parent->special_objects[JIT_PRIMITIVE]);
244 /* 'if' preceded by two literal quotations (this is why if and ? are
245 mutually recursive in the library, but both still work) */
246 if(fast_if_p(i,length))
248 emit_epilog(safepoint, stack_frame);
251 emit_quot(array_nth(elements.untagged(),i));
252 emit_quot(array_nth(elements.untagged(),i + 1));
253 emit(parent->special_objects[JIT_IF]);
258 else if(fast_dip_p(i,length))
260 emit_quot(obj.value());
261 emit(parent->special_objects[JIT_DIP]);
265 else if(fast_2dip_p(i,length))
267 emit_quot(obj.value());
268 emit(parent->special_objects[JIT_2DIP]);
272 else if(fast_3dip_p(i,length))
274 emit_quot(obj.value());
275 emit(parent->special_objects[JIT_3DIP]);
282 /* Method dispatch */
283 if(mega_lookup_p(i,length))
285 fixnum index = untag_fixnum(array_nth(elements.untagged(),i + 1));
286 /* Load the object from the datastack, then remove our stack frame. */
287 emit_with_literal(parent->special_objects[PIC_LOAD],tag_fixnum(-index * sizeof(cell)));
288 emit_epilog(safepoint, stack_frame);
291 emit_mega_cache_lookup(
292 array_nth(elements.untagged(),i),
294 array_nth(elements.untagged(),i + 2));
297 /* Non-optimizing compiler ignores declarations */
298 else if(declare_p(i,length))
311 set_position(length);
313 emit_epilog(safepoint, stack_frame);
314 emit(parent->special_objects[JIT_RETURN]);
318 cell quotation_jit::word_stack_frame_size(cell obj)
320 if (special_subprimitive_p(obj))
321 return SIGNAL_HANDLER_STACK_FRAME_SIZE;
323 return JIT_FRAME_SIZE;
326 /* Allocates memory */
327 code_block *factor_vm::jit_compile_quot(cell owner_, cell quot_, bool relocating)
329 data_root<object> owner(owner_,this);
330 data_root<quotation> quot(quot_,this);
332 quotation_jit compiler(owner.value(),true,relocating,this);
333 compiler.init_quotation(quot.value());
334 compiler.iterate_quotation();
336 cell frame_size = compiler.word_stack_frame_size(owner_);
338 code_block *compiled = compiler.to_code_block(frame_size);
340 if(relocating) initialize_code_block(compiled);
345 /* Allocates memory */
346 void factor_vm::jit_compile_quot(cell quot_, bool relocating)
348 data_root<quotation> quot(quot_,this);
349 if(!quot_compiled_p(quot.untagged()))
351 code_block *compiled = jit_compile_quot(quot.value(),quot.value(),relocating);
352 quot.untagged()->entry_point = compiled->entry_point();
356 /* Allocates memory */
357 void factor_vm::primitive_jit_compile()
359 jit_compile_quot(ctx->pop(),true);
362 void *factor_vm::lazy_jit_compile_entry_point()
364 return untag<word>(special_objects[LAZY_JIT_COMPILE_WORD])->entry_point;
367 /* push a new quotation on the stack */
368 /* Allocates memory */
369 void factor_vm::primitive_array_to_quotation()
371 quotation *quot = allot<quotation>(sizeof(quotation));
373 quot->array = ctx->peek();
374 quot->cached_effect = false_object;
375 quot->cache_counter = false_object;
376 quot->entry_point = lazy_jit_compile_entry_point();
378 ctx->replace(tag<quotation>(quot));
381 /* Allocates memory (from_unsigned_cell) */
382 void factor_vm::primitive_quotation_code()
384 data_root<quotation> quot(ctx->pop(),this);
386 ctx->push(from_unsigned_cell((cell)quot->entry_point));
387 ctx->push(from_unsigned_cell((cell)quot->code() + quot->code()->size()));
390 /* Allocates memory */
391 fixnum factor_vm::quot_code_offset_to_scan(cell quot_, cell offset)
393 data_root<quotation> quot(quot_,this);
394 data_root<array> array(quot->array,this);
396 quotation_jit compiler(quot.value(),false,false,this);
397 compiler.init_quotation(quot.value());
398 compiler.compute_position(offset);
399 compiler.iterate_quotation();
401 return compiler.get_position();
404 /* Allocates memory */
405 cell factor_vm::lazy_jit_compile(cell quot_)
407 data_root<quotation> quot(quot_,this);
409 FACTOR_ASSERT(!quot_compiled_p(quot.untagged()));
411 code_block *compiled = jit_compile_quot(quot.value(),quot.value(),true);
412 quot.untagged()->entry_point = compiled->entry_point();
417 /* Allocates memory */
418 VM_C_API cell lazy_jit_compile(cell quot, factor_vm *parent)
420 return parent->lazy_jit_compile(quot);
423 bool factor_vm::quot_compiled_p(quotation *quot)
425 return quot->entry_point != NULL && quot->entry_point != lazy_jit_compile_entry_point();
428 void factor_vm::primitive_quot_compiled_p()
430 tagged<quotation> quot(ctx->pop());
431 quot.untag_check(this);
432 ctx->push(tag_boolean(quot_compiled_p(quot.untagged())));
435 /* Allocates memory */
436 cell factor_vm::find_all_quotations()
438 return instances(QUOTATION_TYPE);
441 /* Allocates memory */
442 void factor_vm::initialize_all_quotations()
444 data_root<array> quotations(find_all_quotations(),this);
446 cell length = array_capacity(quotations.untagged());
447 for(cell i = 0; i < length; i++)
449 data_root<quotation> quot(array_nth(quotations.untagged(),i),this);
450 if(!quot->entry_point)
451 quot.untagged()->entry_point = lazy_jit_compile_entry_point();