5 /* Simple non-optimizing compiler.
7 This is one of the two compilers implementing Factor; the second one is written
8 in Factor and performs advanced optimizations. See
9 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) {
40 elements = untag<quotation>(quot)->array;
43 bool quotation_jit::primitive_call_p(cell i, cell length) {
44 return (i + 2) <= length && array_nth(elements.untagged(), i + 1) ==
45 parent->special_objects[JIT_PRIMITIVE_WORD];
48 bool quotation_jit::fast_if_p(cell i, cell length) {
49 return (i + 3) == length &&
50 tagged<object>(array_nth(elements.untagged(), i + 1))
51 .type_p(QUOTATION_TYPE) &&
52 array_nth(elements.untagged(), i + 2) ==
53 parent->special_objects[JIT_IF_WORD];
56 bool quotation_jit::fast_dip_p(cell i, cell length) {
57 return (i + 2) <= length && array_nth(elements.untagged(), i + 1) ==
58 parent->special_objects[JIT_DIP_WORD];
61 bool quotation_jit::fast_2dip_p(cell i, cell length) {
62 return (i + 2) <= length && array_nth(elements.untagged(), i + 1) ==
63 parent->special_objects[JIT_2DIP_WORD];
66 bool quotation_jit::fast_3dip_p(cell i, cell length) {
67 return (i + 2) <= length && array_nth(elements.untagged(), i + 1) ==
68 parent->special_objects[JIT_3DIP_WORD];
71 bool quotation_jit::mega_lookup_p(cell i, cell length) {
72 return (i + 4) <= length &&
73 tagged<object>(array_nth(elements.untagged(), i + 1))
74 .type_p(FIXNUM_TYPE) &&
75 tagged<object>(array_nth(elements.untagged(), i + 2))
76 .type_p(ARRAY_TYPE) &&
77 array_nth(elements.untagged(), i + 3) ==
78 parent->special_objects[MEGA_LOOKUP_WORD];
81 bool quotation_jit::declare_p(cell i, cell length) {
82 return (i + 2) <= length && array_nth(elements.untagged(), i + 1) ==
83 parent->special_objects[JIT_DECLARE_WORD];
86 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) {
97 return (to_boolean(untag<word>(obj)->subprimitive) &&
98 !special_subprimitive_p(obj)) ||
99 obj == parent->special_objects[JIT_PRIMITIVE_WORD];
102 bool quotation_jit::word_safepoint_p(cell obj) {
103 return !special_subprimitive_p(obj);
106 bool quotation_jit::safepoint_p() {
107 fixnum length = array_capacity(elements.untagged());
109 for (fixnum i = 0; i < length; i++) {
110 cell obj = array_nth(elements.untagged(), i);
111 switch (tagged<object>(obj).type()) {
113 if (!word_safepoint_p(obj))
124 bool quotation_jit::stack_frame_p() {
125 fixnum length = array_capacity(elements.untagged());
127 for (fixnum i = 0; i < length; i++) {
128 cell obj = array_nth(elements.untagged(), i);
129 if (tagged<object>(obj).type() == WORD_TYPE && !word_safepoint_p(obj))
136 bool quotation_jit::trivial_quotation_p(array* elements) {
137 return array_capacity(elements) == 1 &&
138 tagged<object>(array_nth(elements, 0)).type_p(WORD_TYPE);
141 void quotation_jit::emit_prolog(bool safepoint, bool stack_frame) {
143 emit(parent->special_objects[JIT_SAFEPOINT]);
145 emit(parent->special_objects[JIT_PROLOG]);
148 void quotation_jit::emit_epilog(bool safepoint, bool stack_frame) {
150 emit(parent->special_objects[JIT_SAFEPOINT]);
152 emit(parent->special_objects[JIT_EPILOG]);
155 /* Allocates memory conditionally */
156 void quotation_jit::emit_quot(cell quot_) {
157 data_root<quotation> quot(quot_, parent);
159 array* elements = untag<array>(quot->array);
161 /* If the quotation consists of a single word, compile a direct call
163 if (trivial_quotation_p(elements))
164 literal(array_nth(elements, 0));
167 parent->jit_compile_quot(quot.value(), relocate);
168 literal(quot.value());
172 /* Allocates memory */
173 void quotation_jit::iterate_quotation() {
174 bool safepoint = safepoint_p();
175 bool stack_frame = stack_frame_p();
179 emit_prolog(safepoint, stack_frame);
182 cell length = array_capacity(elements.untagged());
183 bool tail_call = false;
185 for (i = 0; i < length; i++) {
188 data_root<object> obj(array_nth(elements.untagged(), i), parent);
190 switch (obj.type()) {
193 if (to_boolean(obj.as<word>()->subprimitive)) {
194 tail_call = emit_subprimitive(obj.value(), /* word */
195 i == length - 1, /* tail_call_p */
196 stack_frame); /* stack_frame_p */
197 } /* Everything else */
198 else if (i == length - 1) {
199 emit_epilog(safepoint, stack_frame);
201 word_jump(obj.value());
203 word_call(obj.value());
206 push(obj.as<wrapper>()->object);
208 case BYTE_ARRAY_TYPE:
209 /* Primitive calls */
210 if (primitive_call_p(i, length)) {
211 /* On x86-64 and PowerPC, the VM pointer is stored in
212 a register; on other platforms, the RT_VM relocation
213 is used and it needs an offset parameter */
215 parameter(tag_fixnum(0));
217 parameter(obj.value());
218 parameter(false_object);
219 #ifdef FACTOR_PPC_TOC
220 parameter(obj.value());
221 parameter(false_object);
223 emit(parent->special_objects[JIT_PRIMITIVE]);
230 /* 'if' preceded by two literal quotations (this is why if and ? are
231 mutually recursive in the library, but both still work) */
232 if (fast_if_p(i, length)) {
233 emit_epilog(safepoint, stack_frame);
236 emit_quot(array_nth(elements.untagged(), i));
237 emit_quot(array_nth(elements.untagged(), i + 1));
238 emit(parent->special_objects[JIT_IF]);
242 else if (fast_dip_p(i, length)) {
243 emit_quot(obj.value());
244 emit(parent->special_objects[JIT_DIP]);
247 else if (fast_2dip_p(i, length)) {
248 emit_quot(obj.value());
249 emit(parent->special_objects[JIT_2DIP]);
252 else if (fast_3dip_p(i, length)) {
253 emit_quot(obj.value());
254 emit(parent->special_objects[JIT_3DIP]);
260 /* Method dispatch */
261 if (mega_lookup_p(i, length)) {
262 fixnum index = untag_fixnum(array_nth(elements.untagged(), i + 1));
263 /* Load the object from the datastack, then remove our stack frame. */
264 emit_with_literal(parent->special_objects[PIC_LOAD],
265 tag_fixnum(-index * sizeof(cell)));
266 emit_epilog(safepoint, stack_frame);
269 emit_mega_cache_lookup(array_nth(elements.untagged(), i), index,
270 array_nth(elements.untagged(), i + 2));
272 } /* Non-optimizing compiler ignores declarations */
273 else if (declare_p(i, length))
285 set_position(length);
287 emit_epilog(safepoint, stack_frame);
288 emit(parent->special_objects[JIT_RETURN]);
292 cell quotation_jit::word_stack_frame_size(cell obj) {
293 if (special_subprimitive_p(obj))
294 return SIGNAL_HANDLER_STACK_FRAME_SIZE;
296 return JIT_FRAME_SIZE;
299 /* Allocates memory */
300 code_block* factor_vm::jit_compile_quot(cell owner_, cell quot_,
302 data_root<object> owner(owner_, this);
303 data_root<quotation> quot(quot_, this);
305 quotation_jit compiler(owner.value(), true, relocating, this);
306 compiler.init_quotation(quot.value());
307 compiler.iterate_quotation();
309 cell frame_size = compiler.word_stack_frame_size(owner_);
311 code_block* compiled = compiler.to_code_block(frame_size);
314 initialize_code_block(compiled);
319 /* Allocates memory */
320 void factor_vm::jit_compile_quot(cell quot_, bool relocating) {
321 data_root<quotation> quot(quot_, this);
322 if (!quot_compiled_p(quot.untagged())) {
323 code_block* compiled =
324 jit_compile_quot(quot.value(), quot.value(), relocating);
325 quot.untagged()->entry_point = compiled->entry_point();
329 /* Allocates memory */
330 void factor_vm::primitive_jit_compile() { jit_compile_quot(ctx->pop(), true); }
332 void* factor_vm::lazy_jit_compile_entry_point() {
333 return untag<word>(special_objects[LAZY_JIT_COMPILE_WORD])->entry_point;
336 /* push a new quotation on the stack */
337 /* Allocates memory */
338 void factor_vm::primitive_array_to_quotation() {
339 quotation* quot = allot<quotation>(sizeof(quotation));
341 quot->array = ctx->peek();
342 quot->cached_effect = false_object;
343 quot->cache_counter = false_object;
344 quot->entry_point = lazy_jit_compile_entry_point();
346 ctx->replace(tag<quotation>(quot));
349 /* Allocates memory (from_unsigned_cell) */
350 void factor_vm::primitive_quotation_code() {
351 data_root<quotation> quot(ctx->pop(), this);
353 ctx->push(from_unsigned_cell((cell) quot->entry_point));
354 ctx->push(from_unsigned_cell((cell) quot->code() + quot->code()->size()));
357 /* Allocates memory */
358 fixnum factor_vm::quot_code_offset_to_scan(cell quot_, cell offset) {
359 data_root<quotation> quot(quot_, this);
360 data_root<array> array(quot->array, this);
362 quotation_jit compiler(quot.value(), false, false, this);
363 compiler.init_quotation(quot.value());
364 compiler.compute_position(offset);
365 compiler.iterate_quotation();
367 return compiler.get_position();
370 /* Allocates memory */
371 cell factor_vm::lazy_jit_compile(cell quot_) {
372 data_root<quotation> quot(quot_, this);
374 FACTOR_ASSERT(!quot_compiled_p(quot.untagged()));
376 code_block* compiled = jit_compile_quot(quot.value(), quot.value(), true);
377 quot.untagged()->entry_point = compiled->entry_point();
382 /* Allocates memory */
383 VM_C_API cell lazy_jit_compile(cell quot, factor_vm* parent) {
384 return parent->lazy_jit_compile(quot);
387 bool factor_vm::quot_compiled_p(quotation* quot) {
388 return quot->entry_point != NULL &&
389 quot->entry_point != lazy_jit_compile_entry_point();
392 void factor_vm::primitive_quot_compiled_p() {
393 tagged<quotation> quot(ctx->pop());
394 quot.untag_check(this);
395 ctx->push(tag_boolean(quot_compiled_p(quot.untagged())));
398 /* Allocates memory */
399 cell factor_vm::find_all_quotations() { return instances(QUOTATION_TYPE); }
401 /* Allocates memory */
402 void factor_vm::initialize_all_quotations() {
403 data_root<array> quotations(find_all_quotations(), this);
405 cell length = array_capacity(quotations.untagged());
406 for (cell i = 0; i < length; i++) {
407 data_root<quotation> quot(array_nth(quotations.untagged(), i), this);
408 if (!quot->entry_point)
409 quot.untagged()->entry_point = lazy_jit_compile_entry_point();