Mercurial > octave-nkf
diff src/pt-jit.h @ 15016:005cb78e1dd1
Split pt-jit into multiple files.
* src/Makefile: Add jit-util.h, jit-typeinfo.h, jit-ir.h, jit-util.cc,
jit-typeinfo.cc, and jit-ir.cc.
* src/jit-ir.cc: New file.
* src/jit-ir.h: New file.
* src/jit-typeinfo.cc: New file.
* src/jit-typeinfo.h: New file.
* src/jit-util.h: New file.
* src/jit-util.cc: New file.
* src/pt-jit.cc: (jit_fail_exception): Move to jit-ir.h.
(fail): Removed function.
(jit_print, jit_use, jit_value, jit_instruction, jit_block, jit_phi_incomming,
jit_phi, jit_terminator, jit_call): Moved to jit-ir.cc.
(octave_jit_print_any, octave_jit_print_double, octave_jit_binary_any_any,
octave_jit_compute_nelem, octave_jit_release_any, octave_jit_release_matrix,
octave_jit_grab_any, octave_jit_grab_matrix, octave_jit_cast_any_matrix,
octave_jit_cast_matrix_any, octave_jit_cast_scalar_any,
octave_jit_cast_any_scalar, octave_jit_cast_complex_any,
octave_jit_cast_any_complex, octave_jit_gripe_nan_to_logical_conversion,
octave_jit_ginvalid_index, octave_jit_gindex_range,
octave_jit_paren_subsasgn_impl, octave_jit_paren_subsasgn_matrix_range,
octave_jit_complex_div, octave_jit_pow_scalar_scalar,
octave_jit_pow_complex_complex, octave_jit_pow_scalar_scalar,
octave_jit_pow_complex_scalar, octave_jit_pow_scalar_scalar,
octave_jit_pow_scalar_complex, octave_jit_pow_scalar_scalar,
octave_jit_print_matrix, octave_jit_call, jit_type, jit_function,
jit_operation, jit_typeinfo): Moved to jit-typeinfo.cc
* src/pt-jit.h (jit_print, jit_use, jit_value, jit_instruction, jit_block,
jit_phi_incomming, jit_phi, jit_terminator, jit_call): Moved to jit-ir.h.
(jit_internal_list, jit_internal_node, jit_range, jit_array): Moved to
jit-util.h.
(jit_type, jit_function, jit_operation, jit_typeinfo): Moved to jit-typeinfo.h
author | Max Brister <max@2bass.com> |
---|---|
date | Wed, 25 Jul 2012 21:12:47 -0500 |
parents | 094bc0a145a1 |
children | 75d1bc2fd6d2 |
line wrap: on
line diff
--- a/src/pt-jit.h Wed Jul 25 16:30:39 2012 -0700 +++ b/src/pt-jit.h Wed Jul 25 21:12:47 2012 -0500 @@ -25,15 +25,8 @@ #ifdef HAVE_LLVM -#include <list> -#include <map> -#include <set> -#include <stdexcept> -#include <vector> -#include <stack> +#include "jit-ir.h" -#include "Array.h" -#include "Range.h" #include "pt-walk.h" // -------------------- Current status -------------------- @@ -61,1957 +54,6 @@ // 3. ... // --------------------------------------------------------- - -// we don't want to include llvm headers here, as they require -// __STDC_LIMIT_MACROS and __STDC_CONSTANT_MACROS be defined in the entire -// compilation unit -namespace llvm -{ - class Value; - class Module; - class FunctionPassManager; - class PassManager; - class ExecutionEngine; - class Function; - class BasicBlock; - class LLVMContext; - class Type; - class StructType; - class Twine; - class GlobalVariable; - class TerminatorInst; - class PHINode; -} - -// llvm doesn't provide this, and it's really useful for debugging -std::ostream& operator<< (std::ostream& os, const llvm::Value& v); - -class octave_base_value; -class octave_builtin; -class octave_value; -class tree; -class tree_expression; - -template <typename HOLDER_T, typename SUB_T> -class jit_internal_node; - -// jit_internal_list and jit_internal_node implement generic embedded doubly -// linked lists. List items extend from jit_internal_list, and can be placed -// in nodes of type jit_internal_node. We use CRTP twice. -template <typename LIST_T, typename NODE_T> -class -jit_internal_list -{ - friend class jit_internal_node<LIST_T, NODE_T>; -public: - jit_internal_list (void) : use_head (0), use_tail (0), muse_count (0) {} - - virtual ~jit_internal_list (void) - { - while (use_head) - use_head->stash_value (0); - } - - NODE_T *first_use (void) const { return use_head; } - - size_t use_count (void) const { return muse_count; } -private: - NODE_T *use_head; - NODE_T *use_tail; - size_t muse_count; -}; - -// a node for internal linked lists -template <typename LIST_T, typename NODE_T> -class -jit_internal_node -{ -public: - typedef jit_internal_list<LIST_T, NODE_T> jit_ilist; - - jit_internal_node (void) : mvalue (0), mnext (0), mprev (0) {} - - ~jit_internal_node (void) { remove (); } - - LIST_T *value (void) const { return mvalue; } - - void stash_value (LIST_T *avalue) - { - remove (); - - mvalue = avalue; - - if (mvalue) - { - jit_ilist *ilist = mvalue; - NODE_T *sthis = static_cast<NODE_T *> (this); - if (ilist->use_head) - { - ilist->use_tail->mnext = sthis; - mprev = ilist->use_tail; - } - else - ilist->use_head = sthis; - - ilist->use_tail = sthis; - ++ilist->muse_count; - } - } - - NODE_T *next (void) const { return mnext; } - - NODE_T *prev (void) const { return mprev; } -private: - void remove () - { - if (mvalue) - { - jit_ilist *ilist = mvalue; - if (mprev) - mprev->mnext = mnext; - else - // we are the use_head - ilist->use_head = mnext; - - if (mnext) - mnext->mprev = mprev; - else - // we are the use tail - ilist->use_tail = mprev; - - mnext = mprev = 0; - --ilist->muse_count; - mvalue = 0; - } - } - - LIST_T *mvalue; - NODE_T *mnext; - NODE_T *mprev; -}; - -// Use like: isa<jit_phi> (value) -// basically just a short cut type typing dyanmic_cast. -template <typename T, typename U> -bool isa (U *value) -{ - return dynamic_cast<T *> (value); -} - -// jit_range is compatable with the llvm range structure -struct -jit_range -{ - jit_range (const Range& from) : base (from.base ()), limit (from.limit ()), - inc (from.inc ()), nelem (from.nelem ()) - {} - - operator Range () const - { - return Range (base, limit, inc); - } - - bool all_elements_are_ints () const; - - double base; - double limit; - double inc; - octave_idx_type nelem; -}; - -std::ostream& operator<< (std::ostream& os, const jit_range& rng); - -// jit_array is compatable with the llvm array/matrix structures -template <typename T, typename U> -struct -jit_array -{ - jit_array (T& from) : array (new T (from)) - { - update (); - } - - void update (void) - { - ref_count = array->jit_ref_count (); - slice_data = array->jit_slice_data () - 1; - slice_len = array->capacity (); - dimensions = array->jit_dimensions (); - } - - void update (T *aarray) - { - array = aarray; - update (); - } - - operator T () const - { - return *array; - } - - int *ref_count; - - U *slice_data; - octave_idx_type slice_len; - octave_idx_type *dimensions; - - T *array; -}; - -typedef jit_array<NDArray, double> jit_matrix; - -std::ostream& operator<< (std::ostream& os, const jit_matrix& mat); - -class jit_type; -class jit_value; - -// calling convention -namespace -jit_convention -{ - enum - type - { - // internal to jit - internal, - - // an external C call - external, - - length - }; -} - -// Used to keep track of estimated (infered) types during JIT. This is a -// hierarchical type system which includes both concrete and abstract types. -// -// Current, we only support any and scalar types. If we can't figure out what -// type a variable is, we assign it the any type. This allows us to generate -// code even for the case of poor type inference. -class -jit_type -{ -public: - typedef llvm::Value *(*convert_fn) (llvm::Value *); - - jit_type (const std::string& aname, jit_type *aparent, llvm::Type *allvm_type, - int aid); - - // a user readable type name - const std::string& name (void) const { return mname; } - - // a unique id for the type - int type_id (void) const { return mid; } - - // An abstract base type, may be null - jit_type *parent (void) const { return mparent; } - - // convert to an llvm type - llvm::Type *to_llvm (void) const { return llvm_type; } - - // how this type gets passed as a function argument - llvm::Type *to_llvm_arg (void) const; - - size_t depth (void) const { return mdepth; } - - bool sret (jit_convention::type cc) const { return msret[cc]; } - - void mark_sret (jit_convention::type cc = jit_convention::external) - { msret[cc] = true; } - - bool pointer_arg (jit_convention::type cc) const { return mpointer_arg[cc]; } - - void mark_pointer_arg (jit_convention::type cc = jit_convention::external) - { mpointer_arg[cc] = true; } - - convert_fn pack (jit_convention::type cc) { return mpack[cc]; } - - void set_pack (jit_convention::type cc, convert_fn fn) { mpack[cc] = fn; } - - convert_fn unpack (jit_convention::type cc) { return munpack[cc]; } - - void set_unpack (jit_convention::type cc, convert_fn fn) - { munpack[cc] = fn; } - - llvm::Type *packed_type (jit_convention::type cc) - { return mpacked_type[cc]; } - - void set_packed_type (jit_convention::type cc, llvm::Type *ty) - { mpacked_type[cc] = ty; } -private: - std::string mname; - jit_type *mparent; - llvm::Type *llvm_type; - int mid; - size_t mdepth; - - bool msret[jit_convention::length]; - bool mpointer_arg[jit_convention::length]; - - convert_fn mpack[jit_convention::length]; - convert_fn munpack[jit_convention::length]; - - llvm::Type *mpacked_type[jit_convention::length]; -}; - -// seperate print function to allow easy printing if type is null -std::ostream& jit_print (std::ostream& os, jit_type *atype); - -#define ASSIGN_ARG(i) the_args[i] = arg ## i; -#define JIT_EXPAND(ret, fname, type, isconst, N) \ - ret fname (JIT_PARAM_ARGS OCT_MAKE_DECL_LIST (type, arg, N)) isconst \ - { \ - std::vector<type> the_args (N); \ - OCT_ITERATE_MACRO (ASSIGN_ARG, N); \ - return fname (JIT_PARAMS the_args); \ - } - -// provides a mechanism for calling -class -jit_function -{ - friend std::ostream& operator<< (std::ostream& os, const jit_function& fn); -public: - jit_function (); - - jit_function (llvm::Module *amodule, jit_convention::type acall_conv, - const llvm::Twine& aname, jit_type *aresult, - const std::vector<jit_type *>& aargs); - - jit_function (const jit_function& fn, jit_type *aresult, - const std::vector<jit_type *>& aargs); - - jit_function (const jit_function& fn); - - bool valid (void) const { return llvm_function; } - - std::string name (void) const; - - llvm::BasicBlock *new_block (const std::string& aname = "body", - llvm::BasicBlock *insert_before = 0); - - llvm::Value *call (const std::vector<jit_value *>& in_args) const; - - llvm::Value *call (const std::vector<llvm::Value *>& in_args) const; - -#define JIT_PARAM_ARGS -#define JIT_PARAMS -#define JIT_CALL(N) JIT_EXPAND (llvm::Value *, call, llvm::Value *, const, N) - - JIT_CALL (0); - JIT_CALL (1); - JIT_CALL (2); - JIT_CALL (3); - JIT_CALL (4); - JIT_CALL (5); - -#undef JIT_CALL - -#define JIT_CALL(N) JIT_EXPAND (llvm::Value *, call, jit_value *, const, N) - - JIT_CALL (1); - JIT_CALL (2); - -#undef JIT_CALL -#undef JIT_PARAMS -#undef JIT_PARAM_ARGS - - llvm::Value *argument (size_t idx) const; - - void do_return (llvm::Value *rval = 0); - - llvm::Function *to_llvm (void) const { return llvm_function; } - - // If true, then the return value is passed as a pointer in the first argument - bool sret (void) const { return mresult && mresult->sret (call_conv); } - - bool can_error (void) const { return mcan_error; } - - void mark_can_error (void) { mcan_error = true; } - - jit_type *result (void) const { return mresult; } - - jit_type *argument_type (size_t idx) const - { - assert (idx < args.size ()); - return args[idx]; - } - - const std::vector<jit_type *>& arguments (void) const { return args; } -private: - llvm::Module *module; - llvm::Function *llvm_function; - jit_type *mresult; - std::vector<jit_type *> args; - jit_convention::type call_conv; - bool mcan_error; -}; - -std::ostream& operator<< (std::ostream& os, const jit_function& fn); - - -// Keeps track of overloads for a builtin function. Used for both type inference -// and code generation. -class -jit_operation -{ -public: - void add_overload (const jit_function& func) - { - add_overload (func, func.arguments ()); - } - - void add_overload (const jit_function& func, - const std::vector<jit_type*>& args); - - const jit_function& overload (const std::vector<jit_type *>& types) const; - - jit_type *result (const std::vector<jit_type *>& types) const - { - const jit_function& temp = overload (types); - return temp.result (); - } - -#define JIT_PARAMS -#define JIT_PARAM_ARGS -#define JIT_OVERLOAD(N) \ - JIT_EXPAND (const jit_function&, overload, jit_type *, const, N) \ - JIT_EXPAND (jit_type *, result, jit_type *, const, N) - - JIT_OVERLOAD (1); - JIT_OVERLOAD (2); - JIT_OVERLOAD (3); - -#undef JIT_PARAMS -#undef JIT_PARAM_ARGS - - const std::string& name (void) const { return mname; } - - void stash_name (const std::string& aname) { mname = aname; } -private: - Array<octave_idx_type> to_idx (const std::vector<jit_type*>& types) const; - - std::vector<Array<jit_function> > overloads; - - std::string mname; -}; - -// Get information and manipulate jit types. -class -jit_typeinfo -{ -public: - static void initialize (llvm::Module *m, llvm::ExecutionEngine *e); - - static jit_type *join (jit_type *lhs, jit_type *rhs) - { - return instance->do_join (lhs, rhs); - } - - static jit_type *get_any (void) { return instance->any; } - - static jit_type *get_matrix (void) { return instance->matrix; } - - static jit_type *get_scalar (void) { return instance->scalar; } - - static llvm::Type *get_scalar_llvm (void) - { return instance->scalar->to_llvm (); } - - static jit_type *get_range (void) { return instance->range; } - - static jit_type *get_string (void) { return instance->string; } - - static jit_type *get_bool (void) { return instance->boolean; } - - static jit_type *get_index (void) { return instance->index; } - - static llvm::Type *get_index_llvm (void) - { return instance->index->to_llvm (); } - - static jit_type *get_complex (void) { return instance->complex; } - - static jit_type *type_of (const octave_value& ov) - { - return instance->do_type_of (ov); - } - - static const jit_operation& binary_op (int op) - { - return instance->do_binary_op (op); - } - - static const jit_operation& grab (void) { return instance->grab_fn; } - - static const jit_function& get_grab (jit_type *type) - { - return instance->grab_fn.overload (type); - } - - static const jit_operation& release (void) - { - return instance->release_fn; - } - - static const jit_function& get_release (jit_type *type) - { - return instance->release_fn.overload (type); - } - - static const jit_operation& print_value (void) - { - return instance->print_fn; - } - - static const jit_operation& for_init (void) - { - return instance->for_init_fn; - } - - static const jit_operation& for_check (void) - { - return instance->for_check_fn; - } - - static const jit_operation& for_index (void) - { - return instance->for_index_fn; - } - - static const jit_operation& make_range (void) - { - return instance->make_range_fn; - } - - static const jit_operation& paren_subsref (void) - { - return instance->paren_subsref_fn; - } - - static const jit_operation& paren_subsasgn (void) - { - return instance->paren_subsasgn_fn; - } - - static const jit_operation& logically_true (void) - { - return instance->logically_true_fn; - } - - static const jit_operation& cast (jit_type *result) - { - return instance->do_cast (result); - } - - static const jit_function& cast (jit_type *to, jit_type *from) - { - return instance->do_cast (to, from); - } - - static llvm::Value *insert_error_check (void) - { - return instance->do_insert_error_check (); - } -private: - jit_typeinfo (llvm::Module *m, llvm::ExecutionEngine *e); - - // FIXME: Do these methods really need to be in jit_typeinfo? - jit_type *do_join (jit_type *lhs, jit_type *rhs) - { - // empty case - if (! lhs) - return rhs; - - if (! rhs) - return lhs; - - // check for a shared parent - while (lhs != rhs) - { - if (lhs->depth () > rhs->depth ()) - lhs = lhs->parent (); - else if (lhs->depth () < rhs->depth ()) - rhs = rhs->parent (); - else - { - // we MUST have depth > 0 as any is the base type of everything - do - { - lhs = lhs->parent (); - rhs = rhs->parent (); - } - while (lhs != rhs); - } - } - - return lhs; - } - - jit_type *do_difference (jit_type *lhs, jit_type *) - { - // FIXME: Maybe we can do something smarter? - return lhs; - } - - jit_type *do_type_of (const octave_value &ov) const; - - const jit_operation& do_binary_op (int op) const - { - assert (static_cast<size_t>(op) < binary_ops.size ()); - return binary_ops[op]; - } - - const jit_operation& do_cast (jit_type *to) - { - static jit_operation null_function; - if (! to) - return null_function; - - size_t id = to->type_id (); - if (id >= casts.size ()) - return null_function; - return casts[id]; - } - - const jit_function& do_cast (jit_type *to, jit_type *from) - { - return do_cast (to).overload (from); - } - - jit_type *new_type (const std::string& name, jit_type *parent, - llvm::Type *llvm_type); - - - void add_print (jit_type *ty); - - void add_binary_op (jit_type *ty, int op, int llvm_op); - - void add_binary_icmp (jit_type *ty, int op, int llvm_op); - - void add_binary_fcmp (jit_type *ty, int op, int llvm_op); - - jit_function create_function (jit_convention::type cc, - const llvm::Twine& name, jit_type *ret, - const std::vector<jit_type *>& args - = std::vector<jit_type *> ()); - -#define JIT_PARAM_ARGS jit_convention::type cc, const llvm::Twine& name, \ - jit_type *ret, -#define JIT_PARAMS cc, name, ret, -#define CREATE_FUNCTION(N) JIT_EXPAND(jit_function, create_function, \ - jit_type *, /* empty */, N) - - CREATE_FUNCTION(1); - CREATE_FUNCTION(2); - CREATE_FUNCTION(3); - CREATE_FUNCTION(4); - -#undef JIT_PARAM_ARGS -#undef JIT_PARAMS -#undef CREATE_FUNCTION - - jit_function create_identity (jit_type *type); - - llvm::Value *do_insert_error_check (void); - - void add_builtin (const std::string& name); - - void register_intrinsic (const std::string& name, size_t id, - jit_type *result, jit_type *arg0) - { - std::vector<jit_type *> args (1, arg0); - register_intrinsic (name, id, result, args); - } - - void register_intrinsic (const std::string& name, size_t id, jit_type *result, - const std::vector<jit_type *>& args); - - void register_generic (const std::string& name, jit_type *result, - jit_type *arg0) - { - std::vector<jit_type *> args (1, arg0); - register_generic (name, result, args); - } - - void register_generic (const std::string& name, jit_type *result, - const std::vector<jit_type *>& args); - - octave_builtin *find_builtin (const std::string& name); - - jit_function mirror_binary (const jit_function& fn); - - llvm::Function *wrap_complex (llvm::Function *wrap); - - static llvm::Value *pack_complex (llvm::Value *cplx); - - static llvm::Value *unpack_complex (llvm::Value *result); - - llvm::Value *complex_real (llvm::Value *cx); - - llvm::Value *complex_real (llvm::Value *cx, llvm::Value *real); - - llvm::Value *complex_imag (llvm::Value *cx); - - llvm::Value *complex_imag (llvm::Value *cx, llvm::Value *imag); - - llvm::Value *complex_new (llvm::Value *real, llvm::Value *imag); - - void create_int (size_t nbits); - - jit_type *intN (size_t nbits) const; - - static jit_typeinfo *instance; - - llvm::Module *module; - llvm::ExecutionEngine *engine; - int next_id; - - llvm::GlobalVariable *lerror_state; - - std::vector<jit_type*> id_to_type; - jit_type *any; - jit_type *matrix; - jit_type *scalar; - jit_type *range; - jit_type *string; - jit_type *boolean; - jit_type *index; - jit_type *complex; - jit_type *unknown_function; - std::map<size_t, jit_type *> ints; - std::map<std::string, jit_type *> builtins; - - llvm::StructType *complex_ret; - - std::vector<jit_operation> binary_ops; - jit_operation grab_fn; - jit_operation release_fn; - jit_operation print_fn; - jit_operation for_init_fn; - jit_operation for_check_fn; - jit_operation for_index_fn; - jit_operation logically_true_fn; - jit_operation make_range_fn; - jit_operation paren_subsref_fn; - jit_operation paren_subsasgn_fn; - - // type id -> cast function TO that type - std::vector<jit_operation> casts; - - // type id -> identity function - std::vector<jit_function> identities; -}; - -// The low level octave jit ir -// this ir is close to llvm, but contains information for doing type inference. -// We convert the octave parse tree to this IR directly. - -#define JIT_VISIT_IR_NOTEMPLATE \ - JIT_METH(block); \ - JIT_METH(branch); \ - JIT_METH(cond_branch); \ - JIT_METH(call); \ - JIT_METH(extract_argument); \ - JIT_METH(store_argument); \ - JIT_METH(phi); \ - JIT_METH(variable); \ - JIT_METH(error_check); \ - JIT_METH(assign) \ - JIT_METH(argument) - -#define JIT_VISIT_IR_CONST \ - JIT_METH(const_bool); \ - JIT_METH(const_scalar); \ - JIT_METH(const_complex); \ - JIT_METH(const_index); \ - JIT_METH(const_string); \ - JIT_METH(const_range) - -#define JIT_VISIT_IR_CLASSES \ - JIT_VISIT_IR_NOTEMPLATE \ - JIT_VISIT_IR_CONST - -// forward declare all ir classes -#define JIT_METH(cname) \ - class jit_ ## cname; - -JIT_VISIT_IR_NOTEMPLATE - -#undef JIT_METH - -class jit_convert; - -// ABCs which aren't included in JIT_VISIT_IR_ALL -class jit_instruction; -class jit_terminator; - -template <typename T, jit_type *(*EXTRACT_T)(void), typename PASS_T = T, - bool QUOTE=false> -class jit_const; - -typedef jit_const<bool, jit_typeinfo::get_bool> jit_const_bool; -typedef jit_const<double, jit_typeinfo::get_scalar> jit_const_scalar; -typedef jit_const<Complex, jit_typeinfo::get_complex> jit_const_complex; -typedef jit_const<octave_idx_type, jit_typeinfo::get_index> jit_const_index; - -typedef jit_const<std::string, jit_typeinfo::get_string, const std::string&, - true> jit_const_string; -typedef jit_const<jit_range, jit_typeinfo::get_range, const jit_range&> -jit_const_range; - -class jit_ir_walker; -class jit_use; - -class -jit_value : public jit_internal_list<jit_value, jit_use> -{ -public: - jit_value (void) : llvm_value (0), ty (0), mlast_use (0), - min_worklist (false) {} - - virtual ~jit_value (void); - - bool in_worklist (void) const - { - return min_worklist; - } - - void stash_in_worklist (bool ain_worklist) - { - min_worklist = ain_worklist; - } - - // The block of the first use which is not a jit_error_check - // So this is not necessarily first_use ()->parent (). - jit_block *first_use_block (void); - - // replace all uses with - virtual void replace_with (jit_value *value); - - jit_type *type (void) const { return ty; } - - llvm::Type *type_llvm (void) const - { - return ty ? ty->to_llvm () : 0; - } - - const std::string& type_name (void) const - { - return ty->name (); - } - - void stash_type (jit_type *new_ty) { ty = new_ty; } - - std::string print_string (void) - { - std::stringstream ss; - print (ss); - return ss.str (); - } - - jit_instruction *last_use (void) const { return mlast_use; } - - void stash_last_use (jit_instruction *alast_use) - { - mlast_use = alast_use; - } - - virtual bool needs_release (void) const { return false; } - - virtual std::ostream& print (std::ostream& os, size_t indent = 0) const = 0; - - virtual std::ostream& short_print (std::ostream& os) const - { return print (os); } - - virtual void accept (jit_ir_walker& walker) = 0; - - bool has_llvm (void) const - { - return llvm_value; - } - - llvm::Value *to_llvm (void) const - { - assert (llvm_value); - return llvm_value; - } - - void stash_llvm (llvm::Value *compiled) - { - llvm_value = compiled; - } - -protected: - std::ostream& print_indent (std::ostream& os, size_t indent = 0) const - { - for (size_t i = 0; i < indent * 8; ++i) - os << " "; - return os; - } - - llvm::Value *llvm_value; -private: - jit_type *ty; - jit_instruction *mlast_use; - bool min_worklist; -}; - -std::ostream& operator<< (std::ostream& os, const jit_value& value); -std::ostream& jit_print (std::ostream& os, jit_value *avalue); - -class -jit_use : public jit_internal_node<jit_value, jit_use> -{ -public: - jit_use (void) : muser (0), mindex (0) {} - - // we should really have a move operator, but not until c++11 :( - jit_use (const jit_use& use) : muser (0), mindex (0) - { - *this = use; - } - - jit_use& operator= (const jit_use& use) - { - stash_value (use.value (), use.user (), use.index ()); - return *this; - } - - size_t index (void) const { return mindex; } - - jit_instruction *user (void) const { return muser; } - - jit_block *user_parent (void) const; - - std::list<jit_block *> user_parent_location (void) const; - - void stash_value (jit_value *avalue, jit_instruction *auser = 0, - size_t aindex = -1) - { - jit_internal_node::stash_value (avalue); - mindex = aindex; - muser = auser; - } -private: - jit_instruction *muser; - size_t mindex; -}; - -class -jit_instruction : public jit_value -{ -public: - // FIXME: this code could be so much pretier with varadic templates... - jit_instruction (void) : mid (next_id ()), mparent (0) - {} - - jit_instruction (size_t nargs) : mid (next_id ()), mparent (0) - { - already_infered.reserve (nargs); - marguments.reserve (nargs); - } - -#define STASH_ARG(i) stash_argument (i, arg ## i); -#define JIT_INSTRUCTION_CTOR(N) \ - jit_instruction (OCT_MAKE_DECL_LIST (jit_value *, arg, N)) \ - : already_infered (N), marguments (N), mid (next_id ()), mparent (0) \ - { \ - OCT_ITERATE_MACRO (STASH_ARG, N); \ - } - - JIT_INSTRUCTION_CTOR(1) - JIT_INSTRUCTION_CTOR(2) - JIT_INSTRUCTION_CTOR(3) - JIT_INSTRUCTION_CTOR(4) - -#undef STASH_ARG -#undef JIT_INSTRUCTION_CTOR - - static void reset_ids (void) - { - next_id (true); - } - - jit_value *argument (size_t i) const - { - return marguments[i].value (); - } - - llvm::Value *argument_llvm (size_t i) const - { - assert (argument (i)); - return argument (i)->to_llvm (); - } - - jit_type *argument_type (size_t i) const - { - return argument (i)->type (); - } - - llvm::Type *argument_type_llvm (size_t i) const - { - assert (argument (i)); - return argument_type (i)->to_llvm (); - } - - std::ostream& print_argument (std::ostream& os, size_t i) const - { - if (argument (i)) - return argument (i)->short_print (os); - else - return os << "NULL"; - } - - void stash_argument (size_t i, jit_value *arg) - { - marguments[i].stash_value (arg, this, i); - } - - void push_argument (jit_value *arg) - { - marguments.push_back (jit_use ()); - stash_argument (marguments.size () - 1, arg); - already_infered.push_back (0); - } - - size_t argument_count (void) const - { - return marguments.size (); - } - - void resize_arguments (size_t acount, jit_value *adefault = 0) - { - size_t old = marguments.size (); - marguments.resize (acount); - already_infered.resize (acount); - - if (adefault) - for (size_t i = old; i < acount; ++i) - stash_argument (i, adefault); - } - - const std::vector<jit_use>& arguments (void) const { return marguments; } - - // argument types which have been infered already - const std::vector<jit_type *>& argument_types (void) const - { return already_infered; } - - virtual void push_variable (void) {} - - virtual void pop_variable (void) {} - - virtual void construct_ssa (void) - { - do_construct_ssa (0, argument_count ()); - } - - virtual bool infer (void) { return false; } - - void remove (void); - - virtual std::ostream& short_print (std::ostream& os) const; - - jit_block *parent (void) const { return mparent; } - - std::list<jit_instruction *>::iterator location (void) const - { - return mlocation; - } - - llvm::BasicBlock *parent_llvm (void) const; - - void stash_parent (jit_block *aparent, - std::list<jit_instruction *>::iterator alocation) - { - mparent = aparent; - mlocation = alocation; - } - - size_t id (void) const { return mid; } -protected: - - // Do SSA replacement on arguments in [start, end) - void do_construct_ssa (size_t start, size_t end); - - std::vector<jit_type *> already_infered; -private: - static size_t next_id (bool reset = false) - { - static size_t ret = 0; - if (reset) - return ret = 0; - - return ret++; - } - - std::vector<jit_use> marguments; - - size_t mid; - jit_block *mparent; - std::list<jit_instruction *>::iterator mlocation; -}; - -// defnie accept methods for subclasses -#define JIT_VALUE_ACCEPT \ - virtual void accept (jit_ir_walker& walker); - -// for use as a dummy argument during conversion to LLVM -class -jit_argument : public jit_value -{ -public: - jit_argument (jit_type *atype, llvm::Value *avalue) - { - stash_type (atype); - stash_llvm (avalue); - } - - virtual std::ostream& print (std::ostream& os, size_t indent = 0) const - { - print_indent (os, indent); - return jit_print (os, type ()) << ": DUMMY"; - } - - JIT_VALUE_ACCEPT; -}; - -template <typename T, jit_type *(*EXTRACT_T)(void), typename PASS_T, - bool QUOTE> -class -jit_const : public jit_value -{ -public: - typedef PASS_T pass_t; - - jit_const (PASS_T avalue) : mvalue (avalue) - { - stash_type (EXTRACT_T ()); - } - - PASS_T value (void) const { return mvalue; } - - virtual std::ostream& print (std::ostream& os, size_t indent = 0) const - { - print_indent (os, indent); - jit_print (os, type ()) << ": "; - if (QUOTE) - os << "\""; - os << mvalue; - if (QUOTE) - os << "\""; - return os; - } - - JIT_VALUE_ACCEPT; -private: - T mvalue; -}; - -class jit_phi_incomming; - -class -jit_block : public jit_value, public jit_internal_list<jit_block, - jit_phi_incomming> -{ - typedef jit_internal_list<jit_block, jit_phi_incomming> ILIST_T; -public: - typedef std::list<jit_instruction *> instruction_list; - typedef instruction_list::iterator iterator; - typedef instruction_list::const_iterator const_iterator; - - typedef std::set<jit_block *> df_set; - typedef df_set::const_iterator df_iterator; - - static const size_t NO_ID = static_cast<size_t> (-1); - - jit_block (const std::string& aname, size_t avisit_count = 0) - : mvisit_count (avisit_count), mid (NO_ID), idom (0), mname (aname), - malive (false) - {} - - virtual void replace_with (jit_value *value); - - void replace_in_phi (jit_block *ablock, jit_block *with); - - // we have a new internal list, but we want to stay compatable with jit_value - jit_use *first_use (void) const { return jit_value::first_use (); } - - size_t use_count (void) const { return jit_value::use_count (); } - - // if a block is alive, then it might be visited during execution - bool alive (void) const { return malive; } - - void mark_alive (void) { malive = true; } - - // If we can merge with a successor, do so and return the now empty block - jit_block *maybe_merge (); - - // merge another block into this block, leaving the merge block empty - void merge (jit_block& merge); - - const std::string& name (void) const { return mname; } - - jit_instruction *prepend (jit_instruction *instr); - - jit_instruction *prepend_after_phi (jit_instruction *instr); - - template <typename T> - T *append (T *instr) - { - internal_append (instr); - return instr; - } - - jit_instruction *insert_before (iterator loc, jit_instruction *instr); - - jit_instruction *insert_before (jit_instruction *loc, jit_instruction *instr) - { - return insert_before (loc->location (), instr); - } - - jit_instruction *insert_after (iterator loc, jit_instruction *instr); - - jit_instruction *insert_after (jit_instruction *loc, jit_instruction *instr) - { - return insert_after (loc->location (), instr); - } - - iterator remove (iterator iter) - { - jit_instruction *instr = *iter; - iter = instructions.erase (iter); - instr->stash_parent (0, instructions.end ()); - return iter; - } - - jit_terminator *terminator (void) const; - - // is the jump from pred alive? - bool branch_alive (jit_block *asucc) const; - - jit_block *successor (size_t i) const; - - size_t successor_count (void) const; - - iterator begin (void) { return instructions.begin (); } - - const_iterator begin (void) const { return instructions.begin (); } - - iterator end (void) { return instructions.end (); } - - const_iterator end (void) const { return instructions.end (); } - - iterator phi_begin (void); - - iterator phi_end (void); - - iterator nonphi_begin (void); - - // must label before id is valid - size_t id (void) const { return mid; } - - // dominance frontier - const df_set& df (void) const { return mdf; } - - df_iterator df_begin (void) const { return mdf.begin (); } - - df_iterator df_end (void) const { return mdf.end (); } - - // label with a RPO walk - void label (void) - { - size_t number = 0; - label (mvisit_count, number); - } - - void label (size_t avisit_count, size_t& number) - { - if (visited (avisit_count)) - return; - - for (jit_use *use = first_use (); use; use = use->next ()) - { - jit_block *pred = use->user_parent (); - pred->label (avisit_count, number); - } - - mid = number++; - } - - // See for idom computation algorithm - // Cooper, Keith D.; Harvey, Timothy J; and Kennedy, Ken (2001). - // "A Simple, Fast Dominance Algorithm" - void compute_idom (jit_block *entry_block) - { - bool changed; - entry_block->idom = entry_block; - do - changed = update_idom (mvisit_count); - while (changed); - } - - // compute dominance frontier - void compute_df (void) - { - compute_df (mvisit_count); - } - - void create_dom_tree (void) - { - create_dom_tree (mvisit_count); - } - - jit_block *dom_successor (size_t idx) const - { - return dom_succ[idx]; - } - - size_t dom_successor_count (void) const - { - return dom_succ.size (); - } - - // call pop_varaible on all instructions - void pop_all (void); - - virtual std::ostream& print (std::ostream& os, size_t indent = 0) const - { - print_indent (os, indent); - short_print (os) << ": %pred = "; - for (jit_use *use = first_use (); use; use = use->next ()) - { - jit_block *pred = use->user_parent (); - os << *pred; - if (use->next ()) - os << ", "; - } - os << std::endl; - - for (const_iterator iter = begin (); iter != end (); ++iter) - { - jit_instruction *instr = *iter; - instr->print (os, indent + 1) << std::endl; - } - return os; - } - - // ... - jit_block *maybe_split (jit_convert& convert, jit_block *asuccessor); - - jit_block *maybe_split (jit_convert& convert, jit_block& asuccessor) - { - return maybe_split (convert, &asuccessor); - } - - // print dominator infomration - std::ostream& print_dom (std::ostream& os) const; - - virtual std::ostream& short_print (std::ostream& os) const - { - os << mname; - if (mid != NO_ID) - os << mid; - return os; - } - - llvm::BasicBlock *to_llvm (void) const; - - std::list<jit_block *>::iterator location (void) const - { return mlocation; } - - void stash_location (std::list<jit_block *>::iterator alocation) - { mlocation = alocation; } - - // used to prevent visiting the same node twice in the graph - size_t visit_count (void) const { return mvisit_count; } - - // check if this node has been visited yet at the given visit count. If we - // have not been visited yet, mark us as visited. - bool visited (size_t avisit_count) - { - if (mvisit_count <= avisit_count) - { - mvisit_count = avisit_count + 1; - return false; - } - - return true; - } - - JIT_VALUE_ACCEPT; -private: - void internal_append (jit_instruction *instr); - - void compute_df (size_t avisit_count); - - bool update_idom (size_t avisit_count); - - void create_dom_tree (size_t avisit_count); - - static jit_block *idom_intersect (jit_block *i, jit_block *j); - - size_t mvisit_count; - size_t mid; - jit_block *idom; - df_set mdf; - std::vector<jit_block *> dom_succ; - std::string mname; - instruction_list instructions; - bool malive; - std::list<jit_block *>::iterator mlocation; -}; - -// keeps track of phi functions that use a block on incomming edges -class -jit_phi_incomming : public jit_internal_node<jit_block, jit_phi_incomming> -{ -public: - jit_phi_incomming (void) : muser (0) {} - - jit_phi_incomming (jit_phi *auser) : muser (auser) {} - - jit_phi_incomming (const jit_phi_incomming& use) : jit_internal_node () - { - *this = use; - } - - jit_phi_incomming& operator= (const jit_phi_incomming& use) - { - stash_value (use.value ()); - muser = use.muser; - return *this; - } - - jit_phi *user (void) const { return muser; } - - jit_block *user_parent (void) const; -private: - jit_phi *muser; -}; - -// A non-ssa variable -class -jit_variable : public jit_value -{ -public: - jit_variable (const std::string& aname) : mname (aname), mlast_use (0) {} - - const std::string &name (void) const { return mname; } - - // manipulate the value_stack, for use during SSA construction. The top of the - // value stack represents the current value for this variable - bool has_top (void) const - { - return ! value_stack.empty (); - } - - jit_value *top (void) const - { - return value_stack.top (); - } - - void push (jit_instruction *v) - { - value_stack.push (v); - mlast_use = v; - } - - void pop (void) - { - value_stack.pop (); - } - - jit_instruction *last_use (void) const - { - return mlast_use; - } - - void stash_last_use (jit_instruction *instr) - { - mlast_use = instr; - } - - // blocks in which we are used - void use_blocks (jit_block::df_set& result) - { - jit_use *use = first_use (); - while (use) - { - result.insert (use->user_parent ()); - use = use->next (); - } - } - - virtual std::ostream& print (std::ostream& os, size_t indent = 0) const - { - return print_indent (os, indent) << mname; - } - - JIT_VALUE_ACCEPT; -private: - std::string mname; - std::stack<jit_value *> value_stack; - jit_instruction *mlast_use; -}; - -class -jit_assign_base : public jit_instruction -{ -public: - jit_assign_base (jit_variable *adest) : jit_instruction (), mdest (adest) {} - - jit_assign_base (jit_variable *adest, size_t npred) : jit_instruction (npred), - mdest (adest) {} - - jit_assign_base (jit_variable *adest, jit_value *arg0, jit_value *arg1) - : jit_instruction (arg0, arg1), mdest (adest) {} - - jit_variable *dest (void) const { return mdest; } - - virtual void push_variable (void) - { - mdest->push (this); - } - - virtual void pop_variable (void) - { - mdest->pop (); - } - - virtual std::ostream& short_print (std::ostream& os) const - { - if (type ()) - jit_print (os, type ()) << ": "; - - dest ()->short_print (os); - return os << "#" << id (); - } -private: - jit_variable *mdest; -}; - -class -jit_assign : public jit_assign_base -{ -public: - jit_assign (jit_variable *adest, jit_value *asrc) - : jit_assign_base (adest, adest, asrc), martificial (false) {} - - jit_value *overwrite (void) const - { - return argument (0); - } - - jit_value *src (void) const - { - return argument (1); - } - - // variables don't get modified in an SSA, but COW requires we modify - // variables. An artificial assign is for when a variable gets modified. We - // need an assign in the SSA, but the reference counts shouldn't be updated. - bool artificial (void) const { return martificial; } - - void mark_artificial (void) { martificial = true; } - - virtual bool infer (void) - { - jit_type *stype = src ()->type (); - if (stype != type()) - { - stash_type (stype); - return true; - } - - return false; - } - - virtual std::ostream& print (std::ostream& os, size_t indent = 0) const - { - print_indent (os, indent) << *this << " = " << *src (); - - if (artificial ()) - os << " [artificial]"; - - return os; - } - - JIT_VALUE_ACCEPT; -private: - bool martificial; -}; - -class -jit_phi : public jit_assign_base -{ -public: - jit_phi (jit_variable *adest, size_t npred) - : jit_assign_base (adest, npred) - { - mincomming.reserve (npred); - } - - // removes arguments form dead incomming jumps - bool prune (void); - - void add_incomming (jit_block *from, jit_value *value) - { - push_argument (value); - mincomming.push_back (jit_phi_incomming (this)); - mincomming[mincomming.size () - 1].stash_value (from); - } - - jit_block *incomming (size_t i) const - { - return mincomming[i].value (); - } - - llvm::BasicBlock *incomming_llvm (size_t i) const - { - return incomming (i)->to_llvm (); - } - - virtual void construct_ssa (void) {} - - virtual bool infer (void); - - virtual std::ostream& print (std::ostream& os, size_t indent = 0) const - { - std::stringstream ss; - print_indent (ss, indent); - short_print (ss) << " phi "; - std::string ss_str = ss.str (); - std::string indent_str (ss_str.size (), ' '); - os << ss_str; - - for (size_t i = 0; i < argument_count (); ++i) - { - if (i > 0) - os << indent_str; - os << "| "; - - os << *incomming (i) << " -> "; - os << *argument (i); - - if (i + 1 < argument_count ()) - os << std::endl; - } - - return os; - } - - llvm::PHINode *to_llvm (void) const; - - JIT_VALUE_ACCEPT; -private: - std::vector<jit_phi_incomming> mincomming; -}; - -class -jit_terminator : public jit_instruction -{ -public: -#define JIT_TERMINATOR_CONST(N) \ - jit_terminator (size_t asuccessor_count, \ - OCT_MAKE_DECL_LIST (jit_value *, arg, N)) \ - : jit_instruction (OCT_MAKE_ARG_LIST (arg, N)), \ - malive (asuccessor_count, false) {} - - JIT_TERMINATOR_CONST (1) - JIT_TERMINATOR_CONST (2) - JIT_TERMINATOR_CONST (3) - -#undef JIT_TERMINATOR_CONST - - jit_block *successor (size_t idx = 0) const - { - return static_cast<jit_block *> (argument (idx)); - } - - llvm::BasicBlock *successor_llvm (size_t idx = 0) const - { - return successor (idx)->to_llvm (); - } - - size_t successor_index (const jit_block *asuccessor) const; - - std::ostream& print_successor (std::ostream& os, size_t idx = 0) const - { - if (alive (idx)) - os << "[live] "; - else - os << "[dead] "; - - return successor (idx)->short_print (os); - } - - // Check if the jump to successor is live - bool alive (const jit_block *asuccessor) const - { - return alive (successor_index (asuccessor)); - } - - bool alive (size_t idx) const { return malive[idx]; } - - bool alive (int idx) const { return malive[idx]; } - - size_t successor_count (void) const { return malive.size (); } - - virtual bool infer (void); - - llvm::TerminatorInst *to_llvm (void) const; -protected: - virtual bool check_alive (size_t) const { return true; } -private: - std::vector<bool> malive; -}; - -class -jit_branch : public jit_terminator -{ -public: - jit_branch (jit_block *succ) : jit_terminator (1, succ) {} - - virtual size_t successor_count (void) const { return 1; } - - virtual std::ostream& print (std::ostream& os, size_t indent = 0) const - { - print_indent (os, indent) << "branch: "; - return print_successor (os); - } - - JIT_VALUE_ACCEPT; -}; - -class -jit_cond_branch : public jit_terminator -{ -public: - jit_cond_branch (jit_value *c, jit_block *ctrue, jit_block *cfalse) - : jit_terminator (2, ctrue, cfalse, c) {} - - jit_value *cond (void) const { return argument (2); } - - std::ostream& print_cond (std::ostream& os) const - { - return cond ()->short_print (os); - } - - llvm::Value *cond_llvm (void) const - { - return cond ()->to_llvm (); - } - - virtual size_t successor_count (void) const { return 2; } - - virtual std::ostream& print (std::ostream& os, size_t indent = 0) const - { - print_indent (os, indent) << "cond_branch: "; - print_cond (os) << ", "; - print_successor (os, 0) << ", "; - return print_successor (os, 1); - } - - JIT_VALUE_ACCEPT; -}; - -class -jit_call : public jit_instruction -{ -public: -#define JIT_CALL_CONST(N) \ - jit_call (const jit_operation& aoperation, \ - OCT_MAKE_DECL_LIST (jit_value *, arg, N)) \ - : jit_instruction (OCT_MAKE_ARG_LIST (arg, N)), moperation (aoperation) {} \ - \ - jit_call (const jit_operation& (*aoperation) (void), \ - OCT_MAKE_DECL_LIST (jit_value *, arg, N)) \ - : jit_instruction (OCT_MAKE_ARG_LIST (arg, N)), moperation (aoperation ()) \ - {} - - JIT_CALL_CONST (1) - JIT_CALL_CONST (2) - JIT_CALL_CONST (3) - JIT_CALL_CONST (4) - -#undef JIT_CALL_CONST - - - const jit_operation& operation (void) const { return moperation; } - - bool can_error (void) const - { - return overload ().can_error (); - } - - const jit_function& overload (void) const - { - return moperation.overload (argument_types ()); - } - - virtual bool needs_release (void) const - { - return type () && jit_typeinfo::get_release (type ()).valid (); - } - - virtual std::ostream& print (std::ostream& os, size_t indent = 0) const - { - print_indent (os, indent); - - if (use_count ()) - short_print (os) << " = "; - os << "call " << moperation.name () << " ("; - - for (size_t i = 0; i < argument_count (); ++i) - { - print_argument (os, i); - if (i + 1 < argument_count ()) - os << ", "; - } - return os << ")"; - } - - virtual bool infer (void); - - JIT_VALUE_ACCEPT; -private: - const jit_operation& moperation; -}; - -// FIXME: This is just ugly... -// checks error_state, if error_state is false then goto the normal branche, -// otherwise goto the error branch -class -jit_error_check : public jit_terminator -{ -public: - jit_error_check (jit_call *acheck_for, jit_block *normal, jit_block *error) - : jit_terminator (2, error, normal, acheck_for) {} - - jit_call *check_for (void) const - { - return static_cast<jit_call *> (argument (2)); - } - - virtual std::ostream& print (std::ostream& os, size_t indent = 0) const - { - print_indent (os, indent) << "error_check " << *check_for () << ", "; - print_successor (os, 1) << ", "; - return print_successor (os, 0); - } - - JIT_VALUE_ACCEPT; -protected: - virtual bool check_alive (size_t idx) const - { - return idx == 1 ? true : check_for ()->can_error (); - } -}; - -class -jit_extract_argument : public jit_assign_base -{ -public: - jit_extract_argument (jit_type *atype, jit_variable *adest) - : jit_assign_base (adest) - { - stash_type (atype); - } - - const std::string& name (void) const - { - return dest ()->name (); - } - - const jit_function& overload (void) const - { - return jit_typeinfo::cast (type (), jit_typeinfo::get_any ()); - } - - virtual std::ostream& print (std::ostream& os, size_t indent = 0) const - { - print_indent (os, indent); - - return short_print (os) << " = extract " << name (); - } - - JIT_VALUE_ACCEPT; -}; - -class -jit_store_argument : public jit_instruction -{ -public: - jit_store_argument (jit_variable *var) - : jit_instruction (var), dest (var) - {} - - const std::string& name (void) const - { - return dest->name (); - } - - const jit_function& overload (void) const - { - return jit_typeinfo::cast (jit_typeinfo::get_any (), result_type ()); - } - - jit_value *result (void) const - { - return argument (0); - } - - jit_type *result_type (void) const - { - return result ()->type (); - } - - llvm::Value *result_llvm (void) const - { - return result ()->to_llvm (); - } - - virtual std::ostream& print (std::ostream& os, size_t indent = 0) const - { - jit_value *res = result (); - print_indent (os, indent) << "store "; - dest->short_print (os); - - if (! isa<jit_variable> (res)) - { - os << " = "; - res->short_print (os); - } - - return os; - } - - JIT_VALUE_ACCEPT; -private: - jit_variable *dest; -}; - -class -jit_ir_walker -{ -public: - virtual ~jit_ir_walker () {} - -#define JIT_METH(clname) \ - virtual void visit (jit_ ## clname&) = 0; - - JIT_VISIT_IR_CLASSES; - -#undef JIT_METH -}; - -template <typename T, jit_type *(*EXTRACT_T)(void), typename PASS_T, bool QUOTE> -void -jit_const<T, EXTRACT_T, PASS_T, QUOTE>::accept (jit_ir_walker& walker) -{ - walker.visit (*this); -} - // convert between IRs // FIXME: Class relationships are messy from here on down. They need to be // cleaned up. @@ -2404,12 +446,5 @@ type_bound_vector bounds; }; -// some #defines we use in the header, but not the cc file -#undef JIT_VISIT_IR_CLASSES -#undef JIT_VISIT_IR_CONST -#undef JIT_VALUE_ACCEPT -#undef ASSIGN_ARG -#undef JIT_EXPAND - #endif #endif