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
12 concatenating machine code chunks; prolog, epilog, call word, jump to
13 word, etc. These machine code chunks are generated from Factor code in
14 basis/bootstrap/assembler/.
16 Calls to words and constant quotations (referenced by conditionals and dips)
17 are direct jumps to machine code blocks. Literals are also referenced directly
18 without going through the literal table.
20 It actually does do a little bit of very simple optimization:
22 1) Tail call optimization.
24 2) If a quotation is determined to not call any other words (except for a few
25 special words which are open-coded, see below), then no prolog/epilog is
28 3) When in tail position and immediately preceded by literal arguments, the
29 'if' is generated inline, instead of as a call to the 'if' word.
31 4) When preceded by a quotation, calls to 'dip', '2dip' and '3dip' are
32 open-coded as retain stack manipulation surrounding a subroutine call.
34 5) Sub-primitives are primitive words which are implemented in assembly and not
35 in the VM. They are open-coded and no subroutine call is generated. This
36 includes stack shufflers, some fixnum arithmetic words, and words such as tag,
37 slot and eq?. A primitive call is relatively expensive (two subroutine calls)
38 so this results in a big speedup for relatively little effort. */
40 void quotation_jit::init_quotation(cell quot) {
41 elements = untag<quotation>(quot)->array;
44 bool quotation_jit::fast_if_p(cell i, cell length) {
45 return (i + 3) == length &&
46 TAG(array_nth(elements.untagged(), i + 1)) == QUOTATION_TYPE &&
47 array_nth(elements.untagged(), i + 2) == parent->special_objects[JIT_IF_WORD];
50 bool quotation_jit::primitive_call_p(cell i, cell length) {
51 cell jit_primitive_word = parent->special_objects[JIT_PRIMITIVE_WORD];
52 return (i + 2) <= length &&
53 array_nth(elements.untagged(), i + 1) == jit_primitive_word;
56 bool quotation_jit::fast_dip_p(cell i, cell length) {
57 cell jit_dip_word = parent->special_objects[JIT_DIP_WORD];
58 return (i + 2) <= length &&
59 array_nth(elements.untagged(), i + 1) == jit_dip_word;
62 bool quotation_jit::fast_2dip_p(cell i, cell length) {
63 cell jit_2dip_word = parent->special_objects[JIT_2DIP_WORD];
64 return (i + 2) <= length &&
65 array_nth(elements.untagged(), i + 1) == jit_2dip_word;
68 bool quotation_jit::fast_3dip_p(cell i, cell length) {
69 cell jit_3dip_word = parent->special_objects[JIT_3DIP_WORD];
70 return (i + 2) <= length &&
71 array_nth(elements.untagged(), i + 1) == jit_3dip_word;
74 bool quotation_jit::declare_p(cell i, cell length) {
75 cell jit_declare_word = parent->special_objects[JIT_DECLARE_WORD];
76 return (i + 2) <= length &&
77 array_nth(elements.untagged(), i + 1) == jit_declare_word;
80 bool quotation_jit::mega_lookup_p(cell i, cell length) {
81 return (i + 4) <= length &&
82 TAG(array_nth(elements.untagged(), i + 1)) == FIXNUM_TYPE &&
83 TAG(array_nth(elements.untagged(), i + 2)) == ARRAY_TYPE &&
84 array_nth(elements.untagged(), i + 3) == parent->special_objects[MEGA_LOOKUP_WORD];
87 bool quotation_jit::special_subprimitive_p(cell obj) {
88 // Subprimitives should be flagged with whether they require a stack frame.
90 return obj == parent->special_objects[SIGNAL_HANDLER_WORD] ||
91 obj == parent->special_objects[LEAF_SIGNAL_HANDLER_WORD] ||
92 obj == parent->special_objects[UNWIND_NATIVE_FRAMES_WORD];
95 bool quotation_jit::word_safepoint_p(cell obj) {
96 return !special_subprimitive_p(obj);
99 /* true if there are no non-safepoint words in the quoation... */
100 bool quotation_jit::no_non_safepoint_words_p() {
101 cell length = array_capacity(elements.untagged());
102 for (cell i = 0; i < length; i++) {
103 cell obj = array_nth(elements.untagged(), i);
104 if (TAG(obj) == WORD_TYPE && !word_safepoint_p(obj))
110 bool quotation_jit::trivial_quotation_p(array* elements) {
111 return array_capacity(elements) == 1 &&
112 TAG(array_nth(elements, 0)) == WORD_TYPE;
115 /* Allocates memory (emit) */
116 void quotation_jit::emit_epilog(bool needed) {
118 emit(parent->special_objects[JIT_SAFEPOINT]);
119 emit(parent->special_objects[JIT_EPILOG]);
123 /* Allocates memory conditionally */
124 void quotation_jit::emit_quotation(cell quot_) {
125 data_root<quotation> quot(quot_, parent);
127 array* elements = untag<array>(quot->array);
129 /* If the quotation consists of a single word, compile a direct call
131 if (trivial_quotation_p(elements))
132 literal(array_nth(elements, 0));
135 parent->jit_compile_quotation(quot.value(), relocate);
136 literal(quot.value());
140 /* Allocates memory (parameter(), literal(), emit_epilog, emit_with_literal)*/
141 void quotation_jit::iterate_quotation() {
142 bool no_non_safepoint_words = no_non_safepoint_words_p();
146 if (no_non_safepoint_words) {
147 emit(parent->special_objects[JIT_SAFEPOINT]);
148 emit(parent->special_objects[JIT_PROLOG]);
151 cell length = array_capacity(elements.untagged());
152 bool tail_call = false;
154 for (cell i = 0; i < length; i++) {
157 data_root<object> obj(array_nth(elements.untagged(), i), parent);
159 switch (obj.type()) {
162 if (to_boolean(obj.as<word>()->subprimitive)) {
163 tail_call = emit_subprimitive(obj.value(), /* word */
164 i == length - 1, /* tail_call_p */
165 no_non_safepoint_words); /* stack_frame_p */
166 } /* Everything else */
167 else if (i == length - 1) {
168 emit_epilog(no_non_safepoint_words);
170 word_jump(obj.value());
172 word_call(obj.value());
175 push(obj.as<wrapper>()->object);
177 case BYTE_ARRAY_TYPE:
178 /* Primitive calls */
179 if (primitive_call_p(i, length)) {
180 /* On x86-64 and PowerPC, the VM pointer is stored in
181 a register; on other platforms, the RT_VM relocation
182 is used and it needs an offset parameter */
184 parameter(tag_fixnum(0));
186 parameter(obj.value());
187 parameter(false_object);
188 #ifdef FACTOR_PPC_TOC
189 parameter(obj.value());
190 parameter(false_object);
192 emit(parent->special_objects[JIT_PRIMITIVE]);
199 /* 'if' preceded by two literal quotations (this is why if and ? are
200 mutually recursive in the library, but both still work) */
201 if (fast_if_p(i, length)) {
202 emit_epilog(no_non_safepoint_words);
205 emit_quotation(array_nth(elements.untagged(), i));
206 emit_quotation(array_nth(elements.untagged(), i + 1));
207 emit(parent->special_objects[JIT_IF]);
211 else if (fast_dip_p(i, length)) {
212 emit_quotation(obj.value());
213 emit(parent->special_objects[JIT_DIP]);
216 else if (fast_2dip_p(i, length)) {
217 emit_quotation(obj.value());
218 emit(parent->special_objects[JIT_2DIP]);
221 else if (fast_3dip_p(i, length)) {
222 emit_quotation(obj.value());
223 emit(parent->special_objects[JIT_3DIP]);
229 /* Method dispatch */
230 if (mega_lookup_p(i, length)) {
231 fixnum index = untag_fixnum(array_nth(elements.untagged(), i + 1));
232 /* Load the object from the datastack, then remove our stack frame. */
233 emit_with_literal(parent->special_objects[PIC_LOAD],
234 tag_fixnum(-index * sizeof(cell)));
235 emit_epilog(no_non_safepoint_words);
238 emit_mega_cache_lookup(array_nth(elements.untagged(), i), index,
239 array_nth(elements.untagged(), i + 2));
241 } /* Non-optimizing compiler ignores declarations */
242 else if (declare_p(i, length))
254 set_position(length);
255 emit_epilog(no_non_safepoint_words);
256 emit(parent->special_objects[JIT_RETURN]);
260 cell quotation_jit::word_stack_frame_size(cell obj) {
261 if (special_subprimitive_p(obj))
262 return SIGNAL_HANDLER_STACK_FRAME_SIZE;
263 return JIT_FRAME_SIZE;
266 /* Allocates memory */
267 code_block* factor_vm::jit_compile_quotation(cell owner_, cell quot_,
269 data_root<object> owner(owner_, this);
270 data_root<quotation> quot(quot_, this);
272 quotation_jit compiler(owner.value(), true, relocating, this);
273 compiler.init_quotation(quot.value());
274 compiler.iterate_quotation();
276 cell frame_size = compiler.word_stack_frame_size(owner_);
278 code_block* compiled = compiler.to_code_block(frame_size);
281 initialize_code_block(compiled);
286 /* Allocates memory */
287 void factor_vm::jit_compile_quotation(cell quot_, bool relocating) {
288 data_root<quotation> quot(quot_, this);
289 if (!quotation_compiled_p(quot.untagged())) {
290 code_block* compiled =
291 jit_compile_quotation(quot.value(), quot.value(), relocating);
292 quot.untagged()->entry_point = compiled->entry_point();
296 /* Allocates memory */
297 void factor_vm::primitive_jit_compile() {
298 jit_compile_quotation(ctx->pop(), true);
301 cell factor_vm::lazy_jit_compile_entry_point() {
302 return untag<word>(special_objects[LAZY_JIT_COMPILE_WORD])->entry_point;
305 /* push a new quotation on the stack */
306 /* Allocates memory */
307 void factor_vm::primitive_array_to_quotation() {
308 quotation* quot = allot<quotation>(sizeof(quotation));
310 quot->array = ctx->peek();
311 quot->cached_effect = false_object;
312 quot->cache_counter = false_object;
313 quot->entry_point = lazy_jit_compile_entry_point();
315 ctx->replace(tag<quotation>(quot));
318 /* Allocates memory (from_unsigned_cell) */
319 void factor_vm::primitive_quotation_code() {
320 data_root<quotation> quot(ctx->pop(), this);
322 ctx->push(from_unsigned_cell(quot->entry_point));
323 ctx->push(from_unsigned_cell((cell)quot->code() + quot->code()->size()));
326 /* Allocates memory */
327 fixnum factor_vm::quot_code_offset_to_scan(cell quot_, cell offset) {
328 data_root<quotation> quot(quot_, this);
329 data_root<array> array(quot->array, this);
331 quotation_jit compiler(quot.value(), false, false, this);
332 compiler.init_quotation(quot.value());
333 compiler.compute_position(offset);
334 compiler.iterate_quotation();
336 return compiler.get_position();
339 /* Allocates memory */
340 cell factor_vm::lazy_jit_compile(cell quot_) {
341 data_root<quotation> quot(quot_, this);
343 FACTOR_ASSERT(!quotation_compiled_p(quot.untagged()));
345 code_block* compiled =
346 jit_compile_quotation(quot.value(), quot.value(), true);
347 quot.untagged()->entry_point = compiled->entry_point();
352 /* Allocates memory */
353 VM_C_API cell lazy_jit_compile(cell quot, factor_vm* parent) {
354 return parent->lazy_jit_compile(quot);
357 bool factor_vm::quotation_compiled_p(quotation* quot) {
358 return quot->entry_point != 0 &&
359 quot->entry_point != lazy_jit_compile_entry_point();
362 void factor_vm::primitive_quotation_compiled_p() {
363 quotation* quot = untag_check<quotation>(ctx->pop());
364 ctx->push(tag_boolean(quotation_compiled_p(quot)));
367 /* Allocates memory */
368 void factor_vm::initialize_all_quotations() {
369 cell all_quots = instances(QUOTATION_TYPE);
370 data_root<array> quotations(all_quots, this);
372 cell length = array_capacity(quotations.untagged());
373 for (cell i = 0; i < length; i++) {
374 data_root<quotation> quot(array_nth(quotations.untagged(), i), this);
375 if (!quot->entry_point)
376 quot.untagged()->entry_point = lazy_jit_compile_entry_point();