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 cell length = array_capacity(elements.untagged());
109 for (cell 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 cell length = array_capacity(elements.untagged());
127 for (cell 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 /* Allocates memory (emit) */
142 void quotation_jit::emit_prolog(bool safepoint, bool stack_frame) {
144 emit(parent->special_objects[JIT_SAFEPOINT]);
146 emit(parent->special_objects[JIT_PROLOG]);
149 /* Allocates memory (emit) */
150 void quotation_jit::emit_epilog(bool safepoint, bool stack_frame) {
152 emit(parent->special_objects[JIT_SAFEPOINT]);
154 emit(parent->special_objects[JIT_EPILOG]);
157 /* Allocates memory conditionally */
158 void quotation_jit::emit_quot(cell quot_) {
159 data_root<quotation> quot(quot_, parent);
161 array* elements = untag<array>(quot->array);
163 /* If the quotation consists of a single word, compile a direct call
165 if (trivial_quotation_p(elements))
166 literal(array_nth(elements, 0));
169 parent->jit_compile_quot(quot.value(), relocate);
170 literal(quot.value());
174 /* Allocates memory (parameter(), literal(), emit_prolog, emit_with_literal)*/
175 void quotation_jit::iterate_quotation() {
176 bool safepoint = safepoint_p();
177 bool stack_frame = stack_frame_p();
181 emit_prolog(safepoint, stack_frame);
184 cell length = array_capacity(elements.untagged());
185 bool tail_call = false;
187 for (i = 0; i < length; i++) {
190 data_root<object> obj(array_nth(elements.untagged(), i), parent);
192 switch (obj.type()) {
195 if (to_boolean(obj.as<word>()->subprimitive)) {
196 tail_call = emit_subprimitive(obj.value(), /* word */
197 i == length - 1, /* tail_call_p */
198 stack_frame); /* stack_frame_p */
199 } /* Everything else */
200 else if (i == length - 1) {
201 emit_epilog(safepoint, stack_frame);
203 word_jump(obj.value());
205 word_call(obj.value());
208 push(obj.as<wrapper>()->object);
210 case BYTE_ARRAY_TYPE:
211 /* Primitive calls */
212 if (primitive_call_p(i, length)) {
213 /* On x86-64 and PowerPC, the VM pointer is stored in
214 a register; on other platforms, the RT_VM relocation
215 is used and it needs an offset parameter */
217 parameter(tag_fixnum(0));
219 parameter(obj.value());
220 parameter(false_object);
221 #ifdef FACTOR_PPC_TOC
222 parameter(obj.value());
223 parameter(false_object);
225 emit(parent->special_objects[JIT_PRIMITIVE]);
232 /* 'if' preceded by two literal quotations (this is why if and ? are
233 mutually recursive in the library, but both still work) */
234 if (fast_if_p(i, length)) {
235 emit_epilog(safepoint, stack_frame);
238 emit_quot(array_nth(elements.untagged(), i));
239 emit_quot(array_nth(elements.untagged(), i + 1));
240 emit(parent->special_objects[JIT_IF]);
244 else if (fast_dip_p(i, length)) {
245 emit_quot(obj.value());
246 emit(parent->special_objects[JIT_DIP]);
249 else if (fast_2dip_p(i, length)) {
250 emit_quot(obj.value());
251 emit(parent->special_objects[JIT_2DIP]);
254 else if (fast_3dip_p(i, length)) {
255 emit_quot(obj.value());
256 emit(parent->special_objects[JIT_3DIP]);
262 /* Method dispatch */
263 if (mega_lookup_p(i, length)) {
264 fixnum index = untag_fixnum(array_nth(elements.untagged(), i + 1));
265 /* Load the object from the datastack, then remove our stack frame. */
266 emit_with_literal(parent->special_objects[PIC_LOAD],
267 tag_fixnum(-index * sizeof(cell)));
268 emit_epilog(safepoint, stack_frame);
271 emit_mega_cache_lookup(array_nth(elements.untagged(), i), index,
272 array_nth(elements.untagged(), i + 2));
274 } /* Non-optimizing compiler ignores declarations */
275 else if (declare_p(i, length))
287 set_position(length);
289 emit_epilog(safepoint, stack_frame);
290 emit(parent->special_objects[JIT_RETURN]);
294 cell quotation_jit::word_stack_frame_size(cell obj) {
295 if (special_subprimitive_p(obj))
296 return SIGNAL_HANDLER_STACK_FRAME_SIZE;
298 return JIT_FRAME_SIZE;
301 /* Allocates memory */
302 code_block* factor_vm::jit_compile_quot(cell owner_, cell quot_,
304 data_root<object> owner(owner_, this);
305 data_root<quotation> quot(quot_, this);
307 quotation_jit compiler(owner.value(), true, relocating, this);
308 compiler.init_quotation(quot.value());
309 compiler.iterate_quotation();
311 cell frame_size = compiler.word_stack_frame_size(owner_);
313 code_block* compiled = compiler.to_code_block(frame_size);
316 initialize_code_block(compiled);
321 /* Allocates memory */
322 void factor_vm::jit_compile_quot(cell quot_, bool relocating) {
323 data_root<quotation> quot(quot_, this);
324 if (!quot_compiled_p(quot.untagged())) {
325 code_block* compiled =
326 jit_compile_quot(quot.value(), quot.value(), relocating);
327 quot.untagged()->entry_point = compiled->entry_point();
331 /* Allocates memory */
332 void factor_vm::primitive_jit_compile() { jit_compile_quot(ctx->pop(), true); }
334 cell factor_vm::lazy_jit_compile_entry_point() {
335 return untag<word>(special_objects[LAZY_JIT_COMPILE_WORD])->entry_point;
338 /* push a new quotation on the stack */
339 /* Allocates memory */
340 void factor_vm::primitive_array_to_quotation() {
341 quotation* quot = allot<quotation>(sizeof(quotation));
343 quot->array = ctx->peek();
344 quot->cached_effect = false_object;
345 quot->cache_counter = false_object;
346 quot->entry_point = lazy_jit_compile_entry_point();
348 ctx->replace(tag<quotation>(quot));
351 /* Allocates memory (from_unsigned_cell) */
352 void factor_vm::primitive_quotation_code() {
353 data_root<quotation> quot(ctx->pop(), this);
355 ctx->push(from_unsigned_cell(quot->entry_point));
356 ctx->push(from_unsigned_cell((cell)quot->code() + quot->code()->size()));
359 /* Allocates memory */
360 fixnum factor_vm::quot_code_offset_to_scan(cell quot_, cell offset) {
361 data_root<quotation> quot(quot_, this);
362 data_root<array> array(quot->array, this);
364 quotation_jit compiler(quot.value(), false, false, this);
365 compiler.init_quotation(quot.value());
366 compiler.compute_position(offset);
367 compiler.iterate_quotation();
369 return compiler.get_position();
372 /* Allocates memory */
373 cell factor_vm::lazy_jit_compile(cell quot_) {
374 data_root<quotation> quot(quot_, this);
376 FACTOR_ASSERT(!quot_compiled_p(quot.untagged()));
378 code_block* compiled = jit_compile_quot(quot.value(), quot.value(), true);
379 quot.untagged()->entry_point = compiled->entry_point();
384 /* Allocates memory */
385 VM_C_API cell lazy_jit_compile(cell quot, factor_vm* parent) {
386 return parent->lazy_jit_compile(quot);
389 bool factor_vm::quot_compiled_p(quotation* quot) {
390 return quot->entry_point != 0 &&
391 quot->entry_point != lazy_jit_compile_entry_point();
394 void factor_vm::primitive_quot_compiled_p() {
395 tagged<quotation> quot(ctx->pop());
396 quot.untag_check(this);
397 ctx->push(tag_boolean(quot_compiled_p(quot.untagged())));
400 /* Allocates memory */
401 cell factor_vm::find_all_quotations() { return instances(QUOTATION_TYPE); }
403 /* Allocates memory */
404 void factor_vm::initialize_all_quotations() {
405 data_root<array> quotations(find_all_quotations(), this);
407 cell length = array_capacity(quotations.untagged());
408 for (cell i = 0; i < length; i++) {
409 data_root<quotation> quot(array_nth(quotations.untagged(), i), this);
410 if (!quot->entry_point)
411 quot.untagged()->entry_point = lazy_jit_compile_entry_point();