From c9cf69c1f258297ea9ab86391808d288970cc480 Mon Sep 17 00:00:00 2001 From: Rhys Weatherley Date: Fri, 11 Jun 2004 01:39:00 +0000 Subject: [PATCH] Implement tail calls from a function to itself. --- ChangeLog | 9 ++ doc/libjit.texi | 47 +++++- jit/jit-insn.c | 314 ++++++++++++++++++++++++++++++++++++----- jit/jit-internal.h | 10 ++ jit/jit-reg-alloc.c | 17 +++ jit/jit-rules-arm.c | 2 +- jit/jit-rules-arm.sel | 1 + jit/jit-rules-interp.c | 4 +- jit/jit-rules-x86.c | 2 +- jit/jit-rules-x86.sel | 2 + jit/jit-rules.h | 2 +- jit/jit-value.c | 16 +++ tutorial/Makefile.am | 6 +- tutorial/t2.c | 2 - tutorial/t5.c | 106 ++++++++++++++ 15 files changed, 493 insertions(+), 47 deletions(-) create mode 100644 tutorial/t5.c diff --git a/ChangeLog b/ChangeLog index 7ef2e89..bdd5019 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,4 +1,13 @@ +2004-06-11 Rhys Weatherley + + * doc/libjit.texi, jit/jit-insn.c, jit/jit-internal.h, + jit/jit-reg-alloc.c, jit/jit-rules-arm.c, jit/jit-rules-arm.sel, + jit/jit-rules-interp.c, jit/jit-rules-x86.c, jit/jit-rules-x86.sel, + jit/jit-rules.h, jit/jit-value.c, tutorial/Makefile.am, + tutorial/t2.c, tutorial/t5.c: implement tail calls from a + function to itself. + 2004-06-10 Rhys Weatherley * jit/jit-apply-arm.c, jit/jit-gen-arm.c, jit/jit-gen-arm.h, diff --git a/doc/libjit.texi b/doc/libjit.texi index 34b91f3..537c023 100644 --- a/doc/libjit.texi +++ b/doc/libjit.texi @@ -213,6 +213,7 @@ but a real program would be expected to handle such errors. * Tutorial 2:: Tutorial 2 - gcd * Tutorial 3:: Tutorial 3 - compiling on-demand * Tutorial 4:: Tutorial 4 - mul_add, C++ version +* Tutorial 5:: Tutorial 5 - gcd, with tail calls * Dynamic Pascal:: Dynamic Pascal - A full JIT example @end menu @@ -641,7 +642,7 @@ heuristics. @c ----------------------------------------------------------------------- -@node Tutorial 4, Dynamic Pascal, Tutorial 3, Tutorials +@node Tutorial 4, Tutorial 5, Tutorial 3, Tutorials @section Tutorial 4 - mul_add, C++ version @cindex mul_add C++ tutorial @@ -756,7 +757,49 @@ library. @c ----------------------------------------------------------------------- -@node Dynamic Pascal, Initialization, Tutorial 4, Tutorials +@node Tutorial 5, Dynamic Pascal, Tutorial 4, Tutorials +@section Tutorial 5 - gcd, with tail calls +@cindex gcd with tail calls + +Astute readers would have noticed that Tutorial 2 included two instances +of "tail calls". That is, calls to the same function that are immediately +followed by a @code{return} instruction. + +Libjit can optimize tail calls if you provide the @code{JIT_CALL_TAIL} +flag to @code{jit_insn_call}. Previously, we used the following code +to call @code{gcd} recursively: + +@example +temp3 = jit_insn_call + (function, "gcd", function, 0, temp_args, 2, 0); +jit_insn_return(function, temp3); +@end example + +@noindent +In Tutorial 5, this is modified to the following: + +@example +jit_insn_call(function, "gcd", function, 0, temp_args, 2, JIT_CALL_TAIL); +@end example + +There is no need for the @code{jit_insn_return}, because the call +will never return to that point in the code. Behind the scenes, +@code{libjit} will convert the call into a jump back to the head +of the function. + +Tail calls can only be used in certain circumstances. The source +and destination of the call must have the same function signatures. +None of the parameters should point to local variables in the current +stack frame. And tail calls cannot be used from any source function +that uses @code{try} or @code{alloca} statements. + +Because it can be difficult for @code{libjit} to determine when these +conditions have been met, it relies upon the caller to supply the +@code{JIT_CALL_TAIL} flag when it is appropriate to use a tail call. + +@c ----------------------------------------------------------------------- + +@node Dynamic Pascal, Initialization, Tutorial 5, Tutorials @section Dynamic Pascal - A full JIT example @cindex Dynamic Pascal diff --git a/jit/jit-insn.c b/jit/jit-insn.c index 19f56ba..11826e5 100644 --- a/jit/jit-insn.c +++ b/jit/jit-insn.c @@ -4950,6 +4950,142 @@ static int restore_eh_frame_after_call(jit_function_t func, int flags) #endif } +/* + * Determine if two signatures are identical for the purpose of tail calls. + */ +static int signature_identical(jit_type_t type1, jit_type_t type2) +{ + unsigned int param; + + /* Handle the easy case first */ + if(type1 == type2) + { + return 1; + } + + /* Remove the tags and then bail out if either type is invalid */ + type1 = jit_type_remove_tags(type1); + type2 = jit_type_remove_tags(type2); + if(!type1 || !type2) + { + return 0; + } + + /* Normalize pointer types, but leave signature types as-is */ + if(type1->kind == JIT_TYPE_PTR) + { + type1 = jit_type_normalize(type1); + } + if(type2->kind == JIT_TYPE_PTR) + { + type2 = jit_type_normalize(type2); + } + +#ifdef JIT_NFLOAT_IS_DOUBLE + /* "double" and "nfloat" are identical on this platform */ + if((type1->kind == JIT_TYPE_FLOAT64 || type1->kind == JIT_TYPE_NFLOAT) && + (type2->kind == JIT_TYPE_FLOAT64 || type2->kind == JIT_TYPE_NFLOAT)) + { + return 1; + } +#endif + + /* If the kinds are not the same now, then we don't have a match */ + if(type1->kind != type2->kind) + { + return 0; + } + + /* Structure and union types must have the same size and alignment */ + if(type1->kind == JIT_TYPE_STRUCT || type1->kind == JIT_TYPE_UNION) + { + return (jit_type_get_size(type1) == jit_type_get_size(type2) && + jit_type_get_alignment(type1) == jit_type_get_alignment(type2)); + } + + /* Signature types must be compared component-by-component */ + if(type1->kind == JIT_TYPE_SIGNATURE) + { + if(type1->abi != type2->abi) + { + return 0; + } + if(!signature_identical(type1->sub_type, type2->sub_type)) + { + return 0; + } + if(type1->num_components != type2->num_components) + { + return 0; + } + for(param = 0; param < type1->num_components; ++param) + { + if(!signature_identical(type1->components[param].type, + type2->components[param].type)) + { + return 0; + } + } + } + + /* If we get here, then the types are compatible */ + return 1; +} + +/* + * Create call setup instructions, taking tail calls into effect. + */ +static int create_call_setup_insns + (jit_function_t func, jit_function_t callee, jit_type_t signature, + jit_value_t *args, unsigned int num_args, + int is_nested, int nesting_level, jit_value_t *struct_return, int flags) +{ + jit_value_t *new_args; + jit_value_t value; + unsigned int arg_num; + + /* If we are performing a tail call, then duplicate the argument + values so that we don't accidentally destroy parameters in + situations like func(x, y) -> func(y, x) */ + if((flags & JIT_CALL_TAIL) != 0 && num_args > 0) + { + new_args = (jit_value_t *)alloca(sizeof(jit_value_t) * num_args); + for(arg_num = 0; arg_num < num_args; ++arg_num) + { + value = args[arg_num]; + if(value && value->is_parameter) + { + value = jit_insn_dup(func, value); + if(!value) + { + return 0; + } + } + new_args[arg_num] = value; + } + args = new_args; + } + + /* If we are calling ourselves, then store back to our own parameters */ + if((flags & JIT_CALL_TAIL) != 0 && func == callee) + { + for(arg_num = 0; arg_num < num_args; ++arg_num) + { + if(!jit_insn_store(func, jit_value_get_param(func, arg_num), + args[arg_num])) + { + return 0; + } + } + return 1; + } + + /* Let the back end do the work */ + return _jit_create_call_setup_insns + (func, signature, args, num_args, + is_nested, nesting_level, struct_return, flags); +} + /*@ * @deftypefun jit_value_t jit_insn_call (jit_function_t func, {const char *} name, jit_function_t jit_func, jit_type_t signature, {jit_value_t *} args, {unsigned int} num_args, int flags) * Call the function @code{jit_func}, which may or may not be translated yet. @@ -4998,6 +5134,8 @@ jit_value_t jit_insn_call jit_value_t *new_args; jit_value_t return_value; jit_insn_t insn; + jit_label_t entry_point; + jit_label_t label_end; /* Bail out if there is something wrong with the parameters */ if(!_jit_function_ensure_builder(func) || !jit_func) @@ -5011,6 +5149,21 @@ jit_value_t jit_insn_call signature = jit_func->signature; } + /* Verify that tail calls are possible to the destination */ + if((flags & JIT_CALL_TAIL) != 0) + { + if(func->nested_parent || jit_func->nested_parent) + { + /* Cannot use tail calls with nested function calls */ + flags &= ~JIT_CALL_TAIL; + } + else if(!signature_identical(signature, func->signature)) + { + /* The signatures are not the same, so tail calls not allowed */ + flags &= ~JIT_CALL_TAIL; + } + } + /* Determine the nesting relationship with the current function */ if(jit_func->nested_parent) { @@ -5074,35 +5227,70 @@ jit_value_t jit_insn_call } /* Create the instructions to push the parameters onto the stack */ - if(!_jit_create_call_setup_insns - (func, signature, new_args, num_args, - is_nested, nesting_level, &return_value)) + if(!create_call_setup_insns + (func, jit_func, signature, new_args, num_args, + is_nested, nesting_level, &return_value, flags)) { return 0; } - /* Functions that call out are not leaves */ - func->builder->non_leaf = 1; - /* Start a new block and output the "call" instruction */ - if(!jit_insn_new_block(func)) + if((flags & JIT_CALL_TAIL) != 0 && func == jit_func) { - return 0; + /* We are performing a tail call to ourselves, which we can + turn into an unconditional branch back to our entry point */ + entry_point = jit_label_undefined; + label_end = jit_label_undefined; + if(!jit_insn_branch(func, &entry_point)) + { + return 0; + } + if(!jit_insn_label(func, &entry_point)) + { + return 0; + } + if(!jit_insn_label(func, &label_end)) + { + return 0; + } + if(!jit_insn_move_blocks_to_start(func, entry_point, label_end)) + { + return 0; + } } - insn = _jit_block_add_insn(func->builder->current_block); - if(!insn) + else { - return 0; + /* Functions that call out are not leaves */ + func->builder->non_leaf = 1; + + /* Performing a regular call, or a tail call to someone else */ + if(!jit_insn_new_block(func)) + { + return 0; + } + insn = _jit_block_add_insn(func->builder->current_block); + if(!insn) + { + return 0; + } + if((flags & JIT_CALL_TAIL) != 0) + { + func->builder->has_tail_call = 1; + insn->opcode = JIT_OP_CALL_TAIL; + } + else + { + insn->opcode = JIT_OP_CALL; + } + insn->flags = JIT_INSN_DEST_IS_FUNCTION | JIT_INSN_VALUE1_IS_NAME; + insn->dest = (jit_value_t)jit_func; + insn->value1 = (jit_value_t)name; } - insn->opcode = JIT_OP_CALL; - insn->flags = JIT_INSN_DEST_IS_FUNCTION | JIT_INSN_VALUE1_IS_NAME; - insn->dest = (jit_value_t)jit_func; - insn->value1 = (jit_value_t)name; /* If the function does not return, then end the current block. The next block does not have "entered_via_top" set so that it will be eliminated during later code generation */ - if((flags & JIT_CALL_NORETURN) != 0) + if((flags & (JIT_CALL_NORETURN | JIT_CALL_TAIL)) != 0) { func->builder->current_block->ends_in_dead = 1; if(!jit_insn_new_block(func)) @@ -5122,10 +5310,13 @@ jit_value_t jit_insn_call } /* Create the instructions necessary to move the return value into place */ - if(!_jit_create_call_return_insns - (func, signature, new_args, num_args, return_value, is_nested)) + if((flags & JIT_CALL_TAIL) == 0) { - return 0; + if(!_jit_create_call_return_insns + (func, signature, new_args, num_args, return_value, is_nested)) + { + return 0; + } } /* Restore exception frame information after the call */ @@ -5157,6 +5348,19 @@ jit_value_t jit_insn_call_indirect return 0; } + /* Verify that tail calls are possible to the destination */ + if((flags & JIT_CALL_TAIL) != 0) + { + if(func->nested_parent) + { + flags &= ~JIT_CALL_TAIL; + } + else if(!signature_identical(signature, func->signature)) + { + flags &= ~JIT_CALL_TAIL; + } + } + /* Convert the arguments to the actual parameter types */ if(num_args > 0) { @@ -5178,8 +5382,8 @@ jit_value_t jit_insn_call_indirect } /* Create the instructions to push the parameters onto the stack */ - if(!_jit_create_call_setup_insns - (func, signature, new_args, num_args, 0, 0, &return_value)) + if(!create_call_setup_insns + (func, 0, signature, new_args, num_args, 0, 0, &return_value, flags)) { return 0; } @@ -5212,7 +5416,7 @@ jit_value_t jit_insn_call_indirect /* If the function does not return, then end the current block. The next block does not have "entered_via_top" set so that it will be eliminated during later code generation */ - if((flags & JIT_CALL_NORETURN) != 0) + if((flags & (JIT_CALL_NORETURN | JIT_CALL_TAIL)) != 0) { func->builder->current_block->ends_in_dead = 1; if(!jit_insn_new_block(func)) @@ -5232,10 +5436,13 @@ jit_value_t jit_insn_call_indirect } /* Create the instructions necessary to move the return value into place */ - if(!_jit_create_call_return_insns - (func, signature, new_args, num_args, return_value, 0)) + if((flags & JIT_CALL_TAIL) == 0) { - return 0; + if(!_jit_create_call_return_insns + (func, signature, new_args, num_args, return_value, 0)) + { + return 0; + } } /* Restore exception frame information after the call */ @@ -5271,6 +5478,19 @@ jit_value_t jit_insn_call_indirect_vtable return 0; } + /* Verify that tail calls are possible to the destination */ + if((flags & JIT_CALL_TAIL) != 0) + { + if(func->nested_parent) + { + flags &= ~JIT_CALL_TAIL; + } + else if(!signature_identical(signature, func->signature)) + { + flags &= ~JIT_CALL_TAIL; + } + } + /* Convert the arguments to the actual parameter types */ if(num_args > 0) { @@ -5292,8 +5512,8 @@ jit_value_t jit_insn_call_indirect_vtable } /* Create the instructions to push the parameters onto the stack */ - if(!_jit_create_call_setup_insns - (func, signature, new_args, num_args, 0, 0, &return_value)) + if(!create_call_setup_insns + (func, 0, signature, new_args, num_args, 0, 0, &return_value, flags)) { return 0; } @@ -5324,7 +5544,7 @@ jit_value_t jit_insn_call_indirect_vtable /* If the function does not return, then end the current block. The next block does not have "entered_via_top" set so that it will be eliminated during later code generation */ - if((flags & JIT_CALL_NORETURN) != 0) + if((flags & (JIT_CALL_NORETURN | JIT_CALL_TAIL)) != 0) { func->builder->current_block->ends_in_dead = 1; if(!jit_insn_new_block(func)) @@ -5344,10 +5564,13 @@ jit_value_t jit_insn_call_indirect_vtable } /* Create the instructions necessary to move the return value into place */ - if(!_jit_create_call_return_insns - (func, signature, new_args, num_args, return_value, 0)) + if((flags & JIT_CALL_TAIL) == 0) { - return 0; + if(!_jit_create_call_return_insns + (func, signature, new_args, num_args, return_value, 0)) + { + return 0; + } } /* Restore exception frame information after the call */ @@ -5380,6 +5603,19 @@ jit_value_t jit_insn_call_native return 0; } + /* Verify that tail calls are possible to the destination */ + if((flags & JIT_CALL_TAIL) != 0) + { + if(func->nested_parent) + { + flags &= ~JIT_CALL_TAIL; + } + else if(!signature_identical(signature, func->signature)) + { + flags &= ~JIT_CALL_TAIL; + } + } + /* Convert the arguments to the actual parameter types */ if(num_args > 0) { @@ -5401,8 +5637,8 @@ jit_value_t jit_insn_call_native } /* Create the instructions to push the parameters onto the stack */ - if(!_jit_create_call_setup_insns - (func, signature, new_args, num_args, 0, 0, &return_value)) + if(!create_call_setup_insns + (func, 0, signature, new_args, num_args, 0, 0, &return_value, flags)) { return 0; } @@ -5432,7 +5668,7 @@ jit_value_t jit_insn_call_native /* If the function does not return, then end the current block. The next block does not have "entered_via_top" set so that it will be eliminated during later code generation */ - if((flags & JIT_CALL_NORETURN) != 0) + if((flags & (JIT_CALL_NORETURN | JIT_CALL_TAIL)) != 0) { func->builder->current_block->ends_in_dead = 1; if(!jit_insn_new_block(func)) @@ -5452,10 +5688,13 @@ jit_value_t jit_insn_call_native } /* Create the instructions necessary to move the return value into place */ - if(!_jit_create_call_return_insns - (func, signature, new_args, num_args, return_value, 0)) + if((flags & JIT_CALL_TAIL) == 0) { - return 0; + if(!_jit_create_call_return_insns + (func, signature, new_args, num_args, return_value, 0)) + { + return 0; + } } /* Restore exception frame information after the call */ @@ -7277,6 +7516,7 @@ int jit_insn_move_blocks_to_start { if(func->builder->init_insn <= init_block->last_insn) { + _jit_value_ref_params(func); block = _jit_block_create(func, 0); if(!block) { diff --git a/jit/jit-internal.h b/jit/jit-internal.h index 8ec50ca..a249e04 100644 --- a/jit/jit-internal.h +++ b/jit/jit-internal.h @@ -226,6 +226,13 @@ struct _jit_value */ void _jit_value_free(void *value); +/* + * Add references to all of the parameter values in a function. + * This is used when the initialization block is split during a + * "jit_insn_move_blocks_to_start" instruction. + */ +void _jit_value_ref_params(jit_function_t func); + /* * Internal structure of an instruction. */ @@ -305,6 +312,9 @@ struct _jit_builder /* Flag that indicates if the function has an ordinary return */ int ordinary_return : 1; + /* Flag that indicates that the current function contains a tail call */ + int has_tail_call : 1; + /* List of all instructions in this function */ jit_insn_t *insns; int num_insns; diff --git a/jit/jit-reg-alloc.c b/jit/jit-reg-alloc.c index 1ae3d06..39ea14b 100644 --- a/jit/jit-reg-alloc.c +++ b/jit/jit-reg-alloc.c @@ -1457,6 +1457,23 @@ void _jit_regs_alloc_global(jit_gencode_t gen, jit_function_t func) return; } + /* If the current function involves a tail call, then we don't do + global register allocation and we also prevent the code generator + from using any of the callee-saved registers. This simplifies + tail calls, which don't have to worry about restoring such registers */ + if(func->builder->has_tail_call) + { + for(reg = 0; reg < JIT_NUM_REGS; ++reg) + { + if((_jit_reg_info[reg].flags & + (JIT_REG_FIXED | JIT_REG_CALL_USED)) == 0) + { + jit_reg_set_used(gen->permanent, reg); + } + } + return; + } + /* Scan all values within the function, looking for the most used. We will replace this with a better allocation strategy later */ block = func->builder->value_pool.blocks; diff --git a/jit/jit-rules-arm.c b/jit/jit-rules-arm.c index b937d58..61a08aa 100644 --- a/jit/jit-rules-arm.c +++ b/jit/jit-rules-arm.c @@ -551,7 +551,7 @@ int _jit_create_entry_insns(jit_function_t func) int _jit_create_call_setup_insns (jit_function_t func, jit_type_t signature, jit_value_t *args, unsigned int num_args, - int is_nested, int nesting_level, jit_value_t *struct_return) + int is_nested, int nesting_level, jit_value_t *struct_return, int flags) { jit_type_t type = jit_type_get_return(signature); jit_value_t value; diff --git a/jit/jit-rules-arm.sel b/jit/jit-rules-arm.sel index db3a6b5..f25973e 100644 --- a/jit/jit-rules-arm.sel +++ b/jit/jit-rules-arm.sel @@ -563,6 +563,7 @@ JIT_OP_CALL: JIT_OP_CALL_TAIL: [] -> { jit_function_t func = (jit_function_t)(insn->dest); + arm_pop_frame_tail(inst, 0); arm_jump(inst, func->closure_entry); } diff --git a/jit/jit-rules-interp.c b/jit/jit-rules-interp.c index 4d7b81f..75162c9 100644 --- a/jit/jit-rules-interp.c +++ b/jit/jit-rules-interp.c @@ -355,7 +355,7 @@ int _jit_create_entry_insns(jit_function_t func) } /*@ - * @deftypefun int _jit_create_call_setup_insns (jit_function_t func, jit_type_t signature, {jit_value_t *} args, {unsigned int} num_args, int is_nested, int nested_level, jit_value_t *struct_return) + * @deftypefun int _jit_create_call_setup_insns (jit_function_t func, jit_type_t signature, {jit_value_t *} args, {unsigned int} num_args, int is_nested, int nested_level, jit_value_t *struct_return, int flags) * Create instructions within @code{func} necessary to set up for a * function call to a function with the specified @code{signature}. * Use @code{jit_insn_push} to push values onto the system stack, @@ -376,7 +376,7 @@ int _jit_create_entry_insns(jit_function_t func) int _jit_create_call_setup_insns (jit_function_t func, jit_type_t signature, jit_value_t *args, unsigned int num_args, - int is_nested, int nested_level, jit_value_t *struct_return) + int is_nested, int nested_level, jit_value_t *struct_return, int flags) { jit_type_t type; jit_type_t vtype; diff --git a/jit/jit-rules-x86.c b/jit/jit-rules-x86.c index 3a09e83..bc683db 100644 --- a/jit/jit-rules-x86.c +++ b/jit/jit-rules-x86.c @@ -335,7 +335,7 @@ int _jit_create_entry_insns(jit_function_t func) int _jit_create_call_setup_insns (jit_function_t func, jit_type_t signature, jit_value_t *args, unsigned int num_args, - int is_nested, int nesting_level, jit_value_t *struct_return) + int is_nested, int nesting_level, jit_value_t *struct_return, int flags) { jit_type_t type = jit_type_get_return(signature); jit_value_t value; diff --git a/jit/jit-rules-x86.sel b/jit/jit-rules-x86.sel index 253e913..3da10d6 100644 --- a/jit/jit-rules-x86.sel +++ b/jit/jit-rules-x86.sel @@ -1439,6 +1439,8 @@ JIT_OP_CALL: JIT_OP_CALL_TAIL: [] -> { jit_function_t func = (jit_function_t)(insn->dest); + x86_mov_reg_reg(inst, X86_ESP, X86_EBP, sizeof(void *)); + x86_pop_reg(inst, X86_EBP); x86_jump_code(inst, func->closure_entry); } diff --git a/jit/jit-rules.h b/jit/jit-rules.h index f73ab04..43b604f 100644 --- a/jit/jit-rules.h +++ b/jit/jit-rules.h @@ -170,7 +170,7 @@ int _jit_create_entry_insns(jit_function_t func); int _jit_create_call_setup_insns (jit_function_t func, jit_type_t signature, jit_value_t *args, unsigned int num_args, - int is_nested, int nesting_level, jit_value_t *struct_return); + int is_nested, int nesting_level, jit_value_t *struct_return, int flags); int _jit_setup_indirect_pointer(jit_function_t func, jit_value_t value); int _jit_create_call_return_insns (jit_function_t func, jit_type_t signature, diff --git a/jit/jit-value.c b/jit/jit-value.c index f5c1d86..4141d1d 100644 --- a/jit/jit-value.c +++ b/jit/jit-value.c @@ -655,6 +655,22 @@ void jit_value_ref(jit_function_t func, jit_value_t value) } } +void _jit_value_ref_params(jit_function_t func) +{ + unsigned int num_params; + unsigned int param; + if(func->builder->param_values) + { + num_params = jit_type_num_params(func->signature); + for(param = 0; param < num_params; ++param) + { + jit_value_ref(func, func->builder->param_values[param]); + } + } + jit_value_ref(func, func->builder->struct_return); + jit_value_ref(func, func->builder->parent_frame); +} + /*@ * @deftypefun void jit_value_set_volatile (jit_value_t value) * Set a flag on a value to indicate that it is volatile. The contents diff --git a/tutorial/Makefile.am b/tutorial/Makefile.am index 33e244a..83b5148 100644 --- a/tutorial/Makefile.am +++ b/tutorial/Makefile.am @@ -1,5 +1,5 @@ -noinst_PROGRAMS = t1 t2 t3 t4 +noinst_PROGRAMS = t1 t2 t3 t4 t5 t1_SOURCES = t1.c t1_LDADD = $(top_builddir)/jit/libjit.la @@ -18,5 +18,9 @@ t4_LDADD = $(top_builddir)/jitplus/libjitplus.la $(top_builddir)/jit/libjit.la t4_DEPENDENCIES = $(top_builddir)/jitplus/libjitplus.la \ $(top_builddir)/jit/libjit.la +t5_SOURCES = t5.c +t5_LDADD = $(top_builddir)/jit/libjit.la +t5_DEPENDENCIES = $(top_builddir)/jit/libjit.la + AM_CFLAGS = -I$(top_srcdir)/include -I$(top_builddir)/include -I. -I$(srcdir) AM_CXXFLAGS = -I$(top_srcdir)/include -I$(top_builddir)/include -I. -I$(srcdir) diff --git a/tutorial/t2.c b/tutorial/t2.c index a4d67a2..1160e2b 100644 --- a/tutorial/t2.c +++ b/tutorial/t2.c @@ -90,9 +90,7 @@ int main(int argc, char **argv) jit_insn_return(function, temp4); /* Compile the function */ - jit_dump_function(stdout, function, "gcd"); jit_function_compile(function); - jit_dump_function(stdout, function, "gcd"); /* Unlock the context */ jit_context_build_end(context); diff --git a/tutorial/t5.c b/tutorial/t5.c new file mode 100644 index 0000000..7bac8a5 --- /dev/null +++ b/tutorial/t5.c @@ -0,0 +1,106 @@ +/* + +Tutorial 5 - gcd, with tail call optimization + +Builds and compiles the following function: + +unsigned int gcd(unsigned int x, unsigned int y) +{ + if(x == y) + { + return x; + } + else if(x < y) + { + return gcd(x, y - x); + } + else + { + return gcd(x - y, y); + } +} + +*/ + +#include +#include + +int main(int argc, char **argv) +{ + jit_context_t context; + jit_type_t params[2]; + jit_type_t signature; + jit_function_t function; + jit_value_t x, y; + jit_value_t temp1, temp2; + jit_value_t temp_args[2]; + jit_label_t label1 = jit_label_undefined; + jit_label_t label2 = jit_label_undefined; + jit_uint arg1, arg2; + void *args[2]; + jit_uint result; + + /* Create a context to hold the JIT's primary state */ + context = jit_context_create(); + + /* Lock the context while we build and compile the function */ + jit_context_build_start(context); + + /* Build the function signature */ + params[0] = jit_type_uint; + params[1] = jit_type_uint; + signature = jit_type_create_signature + (jit_abi_cdecl, jit_type_uint, params, 2, 1); + + /* Create the function object */ + function = jit_function_create(context, signature); + + /* Check the condition "if(x == y)" */ + x = jit_value_get_param(function, 0); + y = jit_value_get_param(function, 1); + temp1 = jit_insn_eq(function, x, y); + jit_insn_branch_if_not(function, temp1, &label1); + + /* Implement "return x" */ + jit_insn_return(function, x); + + /* Set "label1" at this position */ + jit_insn_label(function, &label1); + + /* Check the condition "if(x < y)" */ + temp2 = jit_insn_lt(function, x, y); + jit_insn_branch_if_not(function, temp2, &label2); + + /* Implement "return gcd(x, y - x)" */ + temp_args[0] = x; + temp_args[1] = jit_insn_sub(function, y, x); + jit_insn_call(function, "gcd", function, 0, temp_args, 2, JIT_CALL_TAIL); + + /* Set "label2" at this position */ + jit_insn_label(function, &label2); + + /* Implement "return gcd(x - y, y)" */ + temp_args[0] = jit_insn_sub(function, x, y); + temp_args[1] = y; + jit_insn_call(function, "gcd", function, 0, temp_args, 2, JIT_CALL_TAIL); + + /* Compile the function */ + jit_function_compile(function); + + /* Unlock the context */ + jit_context_build_end(context); + + /* Execute the function and print the result */ + arg1 = 27; + arg2 = 14; + args[0] = &arg1; + args[1] = &arg2; + jit_function_apply(function, args, &result); + printf("gcd(27, 14) = %u\n", (unsigned int)result); + + /* Clean up */ + jit_context_destroy(context); + + /* Finished */ + return 0; +} -- 2.47.3