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::word_stack_frame_p(cell obj)
87 return to_boolean(untag<word>(obj)->subprimitive)
88 || obj == parent->special_objects[JIT_PRIMITIVE_WORD];
91 bool quotation_jit::stack_frame_p()
93 fixnum length = array_capacity(elements.untagged());
95 for(fixnum i = 0; i < length; i++)
97 cell obj = array_nth(elements.untagged(),i);
98 switch(tagged<object>(obj).type())
101 if(i != length - 1 || word_stack_frame_p(obj))
105 if(fast_dip_p(i,length) || fast_2dip_p(i,length) || fast_3dip_p(i,length))
116 bool quotation_jit::trivial_quotation_p(array *elements)
118 return array_capacity(elements) == 1 && tagged<object>(array_nth(elements,0)).type_p(WORD_TYPE);
121 void quotation_jit::emit_quot(cell quot_)
123 data_root<quotation> quot(quot_,parent);
125 array *elements = untag<array>(quot->array);
127 /* If the quotation consists of a single word, compile a direct call
129 if(trivial_quotation_p(elements))
130 literal(array_nth(elements,0));
133 if(compiling) parent->jit_compile_quot(quot.value(),relocate);
134 literal(quot.value());
138 /* Allocates memory */
139 void quotation_jit::iterate_quotation()
141 bool stack_frame = stack_frame_p();
146 emit(parent->special_objects[JIT_PROLOG]);
149 cell length = array_capacity(elements.untagged());
150 bool tail_call = false;
152 for(i = 0; i < length; i++)
156 data_root<object> obj(array_nth(elements.untagged(),i),parent);
162 if(to_boolean(obj.as<word>()->subprimitive))
164 tail_call = emit_subprimitive(obj.value(), /* word */
165 i == length - 1, /* tail_call_p */
166 stack_frame); /* stack_frame_p */
168 /* Everything else */
169 else if(i == length - 1)
171 if(stack_frame) emit(parent->special_objects[JIT_EPILOG]);
173 word_jump(obj.value());
176 word_call(obj.value());
179 push(obj.as<wrapper>()->object);
181 case BYTE_ARRAY_TYPE:
182 /* Primitive calls */
183 if(primitive_call_p(i,length))
185 /* On x86-64 and PowerPC, the VM pointer is stored in
186 a register; on other platforms, the RT_VM relocation
187 is used and it needs an offset parameter */
189 parameter(tag_fixnum(0));
191 parameter(obj.value());
192 parameter(false_object);
193 #ifdef FACTOR_PPC_TOC
194 parameter(obj.value());
195 parameter(false_object);
197 emit(parent->special_objects[JIT_PRIMITIVE]);
205 /* 'if' preceeded by two literal quotations (this is why if and ? are
206 mutually recursive in the library, but both still work) */
207 if(fast_if_p(i,length))
209 if(stack_frame) emit(parent->special_objects[JIT_EPILOG]);
212 emit_quot(array_nth(elements.untagged(),i));
213 emit_quot(array_nth(elements.untagged(),i + 1));
214 emit(parent->special_objects[JIT_IF]);
219 else if(fast_dip_p(i,length))
221 emit_quot(obj.value());
222 emit(parent->special_objects[JIT_DIP]);
226 else if(fast_2dip_p(i,length))
228 emit_quot(obj.value());
229 emit(parent->special_objects[JIT_2DIP]);
233 else if(fast_3dip_p(i,length))
235 emit_quot(obj.value());
236 emit(parent->special_objects[JIT_3DIP]);
243 /* Method dispatch */
244 if(mega_lookup_p(i,length))
246 if(stack_frame) emit(parent->special_objects[JIT_EPILOG]);
248 emit_mega_cache_lookup(
249 array_nth(elements.untagged(),i),
250 untag_fixnum(array_nth(elements.untagged(),i + 1)),
251 array_nth(elements.untagged(),i + 2));
254 /* Non-optimizing compiler ignores declarations */
255 else if(declare_p(i,length))
268 set_position(length);
270 if(stack_frame) emit(parent->special_objects[JIT_EPILOG]);
271 emit(parent->special_objects[JIT_RETURN]);
275 void factor_vm::set_quot_entry_point(quotation *quot, code_block *code)
278 quot->entry_point = code->entry_point();
281 /* Allocates memory */
282 code_block *factor_vm::jit_compile_quot(cell owner_, cell quot_, bool relocating)
284 data_root<object> owner(owner_,this);
285 data_root<quotation> quot(quot_,this);
287 quotation_jit compiler(owner.value(),true,relocating,this);
288 compiler.init_quotation(quot.value());
289 compiler.iterate_quotation();
291 code_block *compiled = compiler.to_code_block();
293 if(relocating) initialize_code_block(compiled);
298 void factor_vm::jit_compile_quot(cell quot_, bool relocating)
300 data_root<quotation> quot(quot_,this);
301 if(!quot_compiled_p(quot.untagged()))
303 code_block *compiled = jit_compile_quot(quot.value(),quot.value(),relocating);
304 set_quot_entry_point(quot.untagged(),compiled);
308 void factor_vm::primitive_jit_compile()
310 jit_compile_quot(ctx->pop(),true);
313 code_block *factor_vm::lazy_jit_compile_block()
315 return untag<word>(special_objects[LAZY_JIT_COMPILE_WORD])->code;
318 /* push a new quotation on the stack */
319 void factor_vm::primitive_array_to_quotation()
321 quotation *quot = allot<quotation>(sizeof(quotation));
323 quot->array = ctx->peek();
324 quot->cached_effect = false_object;
325 quot->cache_counter = false_object;
326 set_quot_entry_point(quot,lazy_jit_compile_block());
328 ctx->replace(tag<quotation>(quot));
331 void factor_vm::primitive_quotation_code()
333 quotation *quot = untag_check<quotation>(ctx->pop());
335 ctx->push(from_unsigned_cell((cell)quot->code->entry_point()));
336 ctx->push(from_unsigned_cell((cell)quot->code + quot->code->size()));
339 /* Allocates memory */
340 fixnum factor_vm::quot_code_offset_to_scan(cell quot_, cell offset)
342 data_root<quotation> quot(quot_,this);
343 data_root<array> array(quot->array,this);
345 quotation_jit compiler(quot.value(),false,false,this);
346 compiler.init_quotation(quot.value());
347 compiler.compute_position(offset);
348 compiler.iterate_quotation();
350 return compiler.get_position();
353 cell factor_vm::lazy_jit_compile(cell quot_)
355 data_root<quotation> quot(quot_,this);
357 assert(!quot_compiled_p(quot.untagged()));
359 code_block *compiled = jit_compile_quot(quot.value(),quot.value(),true);
360 set_quot_entry_point(quot.untagged(),compiled);
365 VM_C_API cell lazy_jit_compile(cell quot, factor_vm *parent)
367 return parent->lazy_jit_compile(quot);
370 bool factor_vm::quot_compiled_p(quotation *quot)
372 return quot->code != NULL && quot->code != lazy_jit_compile_block();
375 void factor_vm::primitive_quot_compiled_p()
377 tagged<quotation> quot(ctx->pop());
378 quot.untag_check(this);
379 ctx->push(tag_boolean(quot_compiled_p(quot.untagged())));
382 cell factor_vm::find_all_quotations()
384 return instances(QUOTATION_TYPE);
387 void factor_vm::initialize_all_quotations()
389 data_root<array> quotations(find_all_quotations(),this);
391 cell length = array_capacity(quotations.untagged());
392 for(cell i = 0; i < length; i++)
394 data_root<quotation> quot(array_nth(quotations.untagged(),i),this);
396 set_quot_entry_point(quot.untagged(),lazy_jit_compile_block());