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);
182 /* Primitive calls */
183 if(primitive_call_p(i,length))
185 parameter(tag_fixnum(0));
186 parameter(obj.value());
187 emit(parent->special_objects[JIT_PRIMITIVE]);
195 /* 'if' preceeded by two literal quotations (this is why if and ? are
196 mutually recursive in the library, but both still work) */
197 if(fast_if_p(i,length))
199 if(stack_frame) emit(parent->special_objects[JIT_EPILOG]);
202 emit_quot(array_nth(elements.untagged(),i));
203 emit_quot(array_nth(elements.untagged(),i + 1));
204 emit(parent->special_objects[JIT_IF]);
209 else if(fast_dip_p(i,length))
211 emit_quot(obj.value());
212 emit(parent->special_objects[JIT_DIP]);
216 else if(fast_2dip_p(i,length))
218 emit_quot(obj.value());
219 emit(parent->special_objects[JIT_2DIP]);
223 else if(fast_3dip_p(i,length))
225 emit_quot(obj.value());
226 emit(parent->special_objects[JIT_3DIP]);
233 /* Method dispatch */
234 if(mega_lookup_p(i,length))
236 if(stack_frame) emit(parent->special_objects[JIT_EPILOG]);
238 emit_mega_cache_lookup(
239 array_nth(elements.untagged(),i),
240 untag_fixnum(array_nth(elements.untagged(),i + 1)),
241 array_nth(elements.untagged(),i + 2));
244 /* Non-optimizing compiler ignores declarations */
245 else if(declare_p(i,length))
258 set_position(length);
260 if(stack_frame) emit(parent->special_objects[JIT_EPILOG]);
261 emit(parent->special_objects[JIT_RETURN]);
265 void factor_vm::set_quot_xt(quotation *quot, code_block *code)
268 quot->xt = code->xt();
271 /* Allocates memory */
272 code_block *factor_vm::jit_compile_quot(cell owner_, cell quot_, bool relocating)
274 data_root<object> owner(owner_,this);
275 data_root<quotation> quot(quot_,this);
277 quotation_jit compiler(owner.value(),true,relocating,this);
278 compiler.init_quotation(quot.value());
279 compiler.iterate_quotation();
281 code_block *compiled = compiler.to_code_block();
283 if(relocating) initialize_code_block(compiled);
288 void factor_vm::jit_compile_quot(cell quot_, bool relocating)
290 data_root<quotation> quot(quot_,this);
292 if(quot->code) return;
294 code_block *compiled = jit_compile_quot(quot.value(),quot.value(),relocating);
295 set_quot_xt(quot.untagged(),compiled);
298 void factor_vm::primitive_jit_compile()
300 jit_compile_quot(ctx->pop(),true);
303 /* push a new quotation on the stack */
304 void factor_vm::primitive_array_to_quotation()
306 quotation *quot = allot<quotation>(sizeof(quotation));
307 quot->array = ctx->peek();
308 quot->cached_effect = false_object;
309 quot->cache_counter = false_object;
310 quot->xt = (void *)lazy_jit_compile;
312 ctx->replace(tag<quotation>(quot));
315 void factor_vm::primitive_quotation_xt()
317 quotation *quot = untag_check<quotation>(ctx->peek());
318 ctx->replace(allot_cell((cell)quot->xt));
321 /* Allocates memory */
322 fixnum factor_vm::quot_code_offset_to_scan(cell quot_, cell offset)
324 data_root<quotation> quot(quot_,this);
325 data_root<array> array(quot->array,this);
327 quotation_jit compiler(quot.value(),false,false,this);
328 compiler.init_quotation(quot.value());
329 compiler.compute_position(offset);
330 compiler.iterate_quotation();
332 return compiler.get_position();
335 cell factor_vm::lazy_jit_compile_impl(cell quot_)
337 data_root<quotation> quot(quot_,this);
338 jit_compile_quot(quot.value(),true);
342 VM_C_API cell lazy_jit_compile_impl(cell quot, factor_vm *parent)
344 return parent->lazy_jit_compile_impl(quot);
347 void factor_vm::primitive_quot_compiled_p()
349 tagged<quotation> quot(ctx->pop());
350 quot.untag_check(this);
351 ctx->push(tag_boolean(quot->code != NULL));