# HG changeset patch # User Max Brister # Date 1338833444 18000 # Node ID 5801e031a3b5eff3c1b8889e04269a224e3602a5 # Parent 4ec5f49cdfe4fef56ad1204f4a7ad285c4d89321 Place releases after last use and generalize dom visiting diff --git a/src/pt-jit.cc b/src/pt-jit.cc --- a/src/pt-jit.cc +++ b/src/pt-jit.cc @@ -339,30 +339,30 @@ fn = create_function ("octave_jit_grab_any", any, any); engine->addGlobalMapping (fn, reinterpret_cast(&octave_jit_grab_any)); - grab_fn.add_overload (fn, false, any, any); + grab_fn.add_overload (fn, false, false, any, any); grab_fn.stash_name ("grab"); // grab scalar fn = create_identity (scalar); - grab_fn.add_overload (fn, false, scalar, scalar); + grab_fn.add_overload (fn, false, false, scalar, scalar); // grab index fn = create_identity (index); - grab_fn.add_overload (fn, false, index, index); + grab_fn.add_overload (fn, false, false, index, index); // release any fn = create_function ("octave_jit_release_any", void_t, any->to_llvm ()); engine->addGlobalMapping (fn, reinterpret_cast(&octave_jit_release_any)); - release_fn.add_overload (fn, false, 0, any); + release_fn.add_overload (fn, false, false, 0, any); release_fn.stash_name ("release"); // release scalar fn = create_identity (scalar); - release_fn.add_overload (fn, false, 0, scalar); + release_fn.add_overload (fn, false, false, 0, scalar); // release index fn = create_identity (index); - release_fn.add_overload (fn, false, 0, index); + release_fn.add_overload (fn, false, false, 0, index); // now for binary scalar operations // FIXME: Finish all operations @@ -401,7 +401,7 @@ builder.CreateRet (zero); } llvm::verifyFunction (*fn); - for_init_fn.add_overload (fn, false, index, range); + for_init_fn.add_overload (fn, false, false, index, range); // bounds check for for loop for_check_fn.stash_name ("for_check"); @@ -417,7 +417,7 @@ builder.CreateRet (ret); } llvm::verifyFunction (*fn); - for_check_fn.add_overload (fn, false, boolean, range, index); + for_check_fn.add_overload (fn, false, false, boolean, range, index); // index variabe for for loop for_index_fn.stash_name ("for_index"); @@ -437,7 +437,7 @@ builder.CreateRet (ret); } llvm::verifyFunction (*fn); - for_index_fn.add_overload (fn, false, scalar, range, index); + for_index_fn.add_overload (fn, false, false, scalar, range, index); // logically true // FIXME: Check for NaN @@ -450,14 +450,14 @@ builder.CreateRet (ret); } llvm::verifyFunction (*fn); - logically_true.add_overload (fn, true, boolean, scalar); + logically_true.add_overload (fn, true, false, boolean, scalar); fn = create_function ("octave_logically_true_bool", boolean, boolean); body = llvm::BasicBlock::Create (context, "body", fn); builder.SetInsertPoint (body); builder.CreateRet (fn->arg_begin ()); llvm::verifyFunction (*fn); - logically_true.add_overload (fn, false, boolean, boolean); + logically_true.add_overload (fn, false, false, boolean, boolean); logically_true.stash_name ("logically_true"); casts[any->type_id ()].stash_name ("(any)"); @@ -466,20 +466,20 @@ // cast any <- scalar fn = create_function ("octave_jit_cast_any_scalar", any, scalar); engine->addGlobalMapping (fn, reinterpret_cast (&octave_jit_cast_any_scalar)); - casts[any->type_id ()].add_overload (fn, false, any, scalar); + casts[any->type_id ()].add_overload (fn, false, false, any, scalar); // cast scalar <- any fn = create_function ("octave_jit_cast_scalar_any", scalar, any); engine->addGlobalMapping (fn, reinterpret_cast (&octave_jit_cast_scalar_any)); - casts[scalar->type_id ()].add_overload (fn, false, scalar, any); + casts[scalar->type_id ()].add_overload (fn, false, false, scalar, any); // cast any <- any fn = create_identity (any); - casts[any->type_id ()].add_overload (fn, false, any, any); + casts[any->type_id ()].add_overload (fn, false, false, any, any); // cast scalar <- scalar fn = create_identity (scalar); - casts[scalar->type_id ()].add_overload (fn, false, scalar, scalar); + casts[scalar->type_id ()].add_overload (fn, false, false, scalar, scalar); } void @@ -494,7 +494,7 @@ ty->to_llvm ()); engine->addGlobalMapping (fn, call); - jit_function::overload ol (fn, false, 0, string, ty); + jit_function::overload ol (fn, false, true, 0, string, ty); print_fn.add_overload (ol); } @@ -517,7 +517,7 @@ builder.CreateRet (ret); llvm::verifyFunction (*fn); - jit_function::overload ol(fn, false, ty, ty, ty); + jit_function::overload ol(fn, false, false, ty, ty, ty); binary_ops[op].add_overload (ol); } @@ -539,7 +539,7 @@ builder.CreateRet (ret); llvm::verifyFunction (*fn); - jit_function::overload ol (fn, false, boolean, ty, ty); + jit_function::overload ol (fn, false, false, boolean, ty, ty); binary_ops[op].add_overload (ol); } @@ -561,7 +561,7 @@ builder.CreateRet (ret); llvm::verifyFunction (*fn); - jit_function::overload ol (fn, false, boolean, ty, ty); + jit_function::overload ol (fn, false, false, boolean, ty, ty); binary_ops[op].add_overload (ol); } @@ -666,6 +666,13 @@ // -------------------- jit_instruction -------------------- void +jit_instruction::remove (void) +{ + if (mparent) + mparent->remove (mlocation); +} + +void jit_instruction::push_variable (void) { if (tag ()) @@ -715,23 +722,40 @@ jit_block::prepend (jit_instruction *instr) { instructions.push_front (instr); - instr->stash_parent (this); + instr->stash_parent (this, instructions.begin ()); return instr; } jit_instruction * +jit_block::prepend_after_phi (jit_instruction *instr) +{ + // FIXME: Make this O(1) + for (iterator iter = begin (); iter != end (); ++iter) + { + jit_instruction *temp = *iter; + if (! temp->is_phi ()) + { + insert_before (iter, instr); + return instr; + } + } + + return append (instr); +} + +jit_instruction * jit_block::append (jit_instruction *instr) { instructions.push_back (instr); - instr->stash_parent (this); + instr->stash_parent (this, --instructions.end ()); return instr; } jit_instruction * jit_block::insert_before (iterator loc, jit_instruction *instr) { - instructions.insert (loc, instr); - instr->stash_parent (this); + iterator iloc = instructions.insert (loc, instr); + instr->stash_parent (this, iloc); return instr; } @@ -739,8 +763,8 @@ jit_block::insert_after (iterator loc, jit_instruction *instr) { ++loc; - instructions.insert (loc, instr); - instr->stash_parent (this); + iterator iloc = instructions.insert (loc, instr); + instr->stash_parent (this, iloc); return instr; } @@ -751,7 +775,7 @@ return 0; jit_instruction *last = instructions.back (); - return dynamic_cast (last); + return last->to_terminator (); } jit_block * @@ -925,61 +949,8 @@ } void -jit_block::finish_phi (jit_block *apred) -{ - size_t pred_idx = pred_index (apred); - for (iterator iter = begin (); iter != end () - && dynamic_cast (*iter); ++iter) - { - jit_instruction *phi = *iter; - jit_variable *var = phi->tag (); - phi->stash_argument (pred_idx, var->top ()); - } -} - -void -jit_block::do_construct_ssa (jit_convert& convert, size_t visit_count) +jit_block::pop_all (void) { - if (mvisit_count > visit_count) - return; - ++mvisit_count; - - for (iterator iter = begin (); iter != end (); ++iter) - { - jit_instruction *instr = *iter; - bool isphi = dynamic_cast (instr); - - if (! isphi) - { - for (size_t i = 0; i < instr->argument_count (); ++i) - { - jit_variable *var; - var = dynamic_cast (instr->argument (i)); - if (var) - instr->stash_argument (i, var->top ()); - } - - // FIXME: Remove need for jit_store_argument dynamic cast - jit_variable *tag = instr->tag (); - if (tag && tag->has_top () - && ! dynamic_cast (instr)) - { - jit_call *rel = convert.create (jit_typeinfo::release, - tag->top ()); - insert_after (iter, rel); - ++iter; - } - } - - instr->push_variable (); - } - - for (size_t i = 0; i < succ_count (); ++i) - succ (i)->finish_phi (this); - - for (size_t i = 0; i < dom_succ.size (); ++i) - dom_succ[i]->do_construct_ssa (convert, visit_count); - for (iterator iter = begin (); iter != end (); ++iter) { jit_instruction *instr = *iter; @@ -1021,6 +992,18 @@ // -------------------- jit_call -------------------- bool +jit_call::dead (void) const +{ + return ! has_side_effects () && use_count () == 0; +} + +bool +jit_call::almost_dead (void) const +{ + return ! has_side_effects () && use_count () <= 1; +} + +bool jit_call::infer (void) { // FIXME: explain algorithm @@ -1082,10 +1065,6 @@ iter != constants.end (); ++iter) append_users (*iter); -#ifdef OCTAVE_JIT_DEBUG - print_blocks ("octave jit ir"); -#endif - // FIXME: Describe algorithm here while (worklist.size ()) { @@ -1096,6 +1075,8 @@ append_users (next); } + place_releases (); + #ifdef OCTAVE_JIT_DEBUG std::cout << "-------------------- Compiling tree --------------------\n"; std::cout << tee.str_print_code () << std::endl; @@ -1107,7 +1088,7 @@ for (jit_block::iterator iter = entry_block->begin (); iter != entry_block->end (); ++iter) { - if (jit_extract_argument *extract = dynamic_cast (*iter)) + if (jit_extract_argument *extract = (*iter)->to_extract_argument ()) arguments.push_back (std::make_pair (extract->name (), true)); } @@ -1714,7 +1695,7 @@ entry_block->compute_df (); entry_block->create_dom_tree (); - // insert phi nodes where needed + // insert phi nodes where needed, this is done on a per variable basis for (vmap_t::iterator iter = vmap.begin (); iter != vmap.end (); ++iter) { jit_block::df_set visited, added_phi; @@ -1748,13 +1729,59 @@ } } - entry_block->construct_ssa (*this); + entry_block->visit_dom (&jit_convert::do_construct_ssa, &jit_block::pop_all); } void -jit_convert::finish_breaks (jit_block *dest, const break_list& lst) +jit_convert::do_construct_ssa (jit_block& block) { - for (break_list::const_iterator iter = lst.begin (); iter != lst.end (); + // replace variables with their current SSA value + for (jit_block::iterator iter = block.begin (); iter != block.end (); ++iter) + { + jit_instruction *instr = *iter; + if (! instr->is_phi ()) + { + for (size_t i = 0; i < instr->argument_count (); ++i) + { + jit_variable *var; + var = instr->argument_variable (i); + assert (var == instr->argument (i)->to_variable ()); + assert (var == dynamic_cast (instr->argument (i))); + if (var) + instr->stash_argument (i, var->top ()); + } + } + + instr->push_variable (); + } + + // finish phi nodes of sucessors + for (size_t i = 0; i < block.succ_count (); ++i) + { + jit_block *finish = block.succ (i); + size_t pred_idx = finish->pred_index (&block); + + for (jit_block::iterator iter = finish->begin (); iter != finish->end () + && (*iter)->is_phi (); ++iter) + { + jit_instruction *phi = *iter; + jit_variable *var = phi->tag (); + phi->stash_argument (pred_idx, var->top ()); + } + } +} + +void +jit_convert::place_releases (void) +{ + jit_convert::release_placer placer (*this); + entry_block->visit_dom (placer, &jit_block::pop_all); +} + +void +jit_convert::finish_breaks (jit_block *dest, const block_list& lst) +{ + for (block_list::const_iterator iter = lst.begin (); iter != lst.end (); ++iter) { jit_block *b = *iter; @@ -1762,6 +1789,42 @@ } } +// -------------------- jit_convert::release_placer -------------------- +void +jit_convert::release_placer::operator() (jit_block& block) +{ + for (jit_block::iterator iter = block.begin (); iter != block.end (); ++iter) + { + jit_instruction *instr = *iter; + for (size_t i = 0; i < instr->argument_count (); ++i) + { + jit_instruction *arg = instr->argument_instruction (i); + if (arg && arg->tag ()) + { + jit_variable *tag = arg->tag (); + tag->stash_last_use (instr); + } + } + + jit_variable *tag = instr->tag (); + if (tag && ! (instr->is_phi () || instr->is_store_argument ()) + && tag->has_top ()) + { + jit_instruction *last_use = tag->last_use (); + jit_call *release = convert.create (jit_typeinfo::release, + tag->top ()); + release->infer (); + if (last_use && last_use->parent () == &block + && ! last_use->is_phi ()) + block.insert_after (last_use->location (), release); + else + block.prepend_after_phi (release); + } + + instr->push_variable (); + } +} + // -------------------- jit_convert::convert_llvm -------------------- llvm::Function * jit_convert::convert_llvm::convert (llvm::Module *module, @@ -1812,42 +1875,10 @@ { jit_block& block = **biter; for (jit_block::iterator piter = block.begin (); - piter != block.end () && dynamic_cast (*piter); ++piter) + piter != block.end () && (*piter)->is_phi (); ++piter) { - // our phi nodes don't have to have the same incomming type, - // so we do casts here jit_instruction *phi = *piter; - jit_block *pblock = phi->parent (); - llvm::PHINode *llvm_phi = llvm::cast (phi->to_llvm ()); - for (size_t i = 0; i < phi->argument_count (); ++i) - { - llvm::BasicBlock *pred = pblock->pred_llvm (i); - if (phi->argument_type_llvm (i) == phi->type_llvm ()) - { - llvm_phi->addIncoming (phi->argument_llvm (i), pred); - } - else - { - // add cast right before pred terminator - builder.SetInsertPoint (--pred->end ()); - - const jit_function::overload& ol - = jit_typeinfo::cast (phi->type (), - phi->argument_type (i)); - if (! ol.function) - { - std::stringstream ss; - ss << "No cast for phi(" << i << "): "; - phi->print (ss); - fail (ss.str ()); - } - - llvm::Value *casted; - casted = builder.CreateCall (ol.function, - phi->argument_llvm (i)); - llvm_phi->addIncoming (casted, pred); - } - } + finish_phi (phi); } } @@ -1864,6 +1895,87 @@ } void +jit_convert::convert_llvm::finish_phi (jit_instruction *phi) +{ + jit_block *pblock = phi->parent (); + llvm::PHINode *llvm_phi = llvm::cast (phi->to_llvm ()); + + bool can_remove = llvm_phi->use_empty (); + if (! can_remove && llvm_phi->hasOneUse () && phi->use_count () == 1) + { + jit_instruction *user = phi->first_use ()->user (); + can_remove = user->is_call (); // must be a remove + } + + if (can_remove) + { + // replace with releases along each incomming branch + while (! llvm_phi->use_empty ()) + { + llvm::Instruction *llvm_instr; + llvm_instr = llvm::cast (llvm_phi->use_back ()); + llvm_instr->eraseFromParent (); + } + + llvm_phi->eraseFromParent (); + phi->stash_llvm (0); + + for (size_t i = 0; i < phi->argument_count (); ++i) + { + jit_value *arg = phi->argument (i); + if (arg->has_llvm () && phi->argument_type (i) != phi->type ()) + { + llvm::BasicBlock *pred = pblock->pred_llvm (i); + builder.SetInsertPoint (--pred->end ()); + const jit_function::overload& ol + = jit_typeinfo::get_release (phi->argument_type (i)); + if (! ol.function) + { + std::stringstream ss; + ss << "No release for phi(" << i << "): "; + phi->print (ss); + fail (ss.str ()); + } + + builder.CreateCall (ol.function, phi->argument_llvm (i)); + } + } + } + else + { + for (size_t i = 0; i < phi->argument_count (); ++i) + { + llvm::BasicBlock *pred = pblock->pred_llvm (i); + if (phi->argument_type (i) == phi->type ()) + { + llvm_phi->addIncoming (phi->argument_llvm (i), pred); + } + else + { + // add cast right before pred terminator + builder.SetInsertPoint (--pred->end ()); + + const jit_function::overload& ol + = jit_typeinfo::cast (phi->type (), + phi->argument_type (i)); + if (! ol.function) + { + std::stringstream ss; + ss << "No cast for phi(" << i << "): "; + phi->print (ss); + fail (ss.str ()); + } + + llvm::Value *casted; + casted = builder.CreateCall (ol.function, + phi->argument_llvm (i)); + llvm_phi->addIncoming (casted, pred); + } + } + } +} + +void jit_convert::convert_llvm::visit (jit_const_string& cs) { cs.stash_llvm (builder.CreateGlobalStringPtr (cs.value ())); diff --git a/src/pt-jit.h b/src/pt-jit.h --- a/src/pt-jit.h +++ b/src/pt-jit.h @@ -163,19 +163,20 @@ jit_function { public: - struct overload + struct + overload { overload (void) : function (0), can_error (true), result (0) {} - overload (llvm::Function *f, bool e, jit_type *r, jit_type *arg0) : - function (f), can_error (e), result (r), arguments (1) + overload (llvm::Function *f, bool e, bool s, jit_type *r, jit_type *arg0) : + function (f), can_error (e), side_effects (s), result (r), arguments (1) { arguments[0] = arg0; } - overload (llvm::Function *f, bool e, jit_type *r, jit_type *arg0, - jit_type *arg1) : function (f), can_error (e), result (r), - arguments (2) + overload (llvm::Function *f, bool e, bool s, jit_type *r, jit_type *arg0, + jit_type *arg1) : function (f), can_error (e), side_effects (s), + result (r), arguments (2) { arguments[0] = arg0; arguments[1] = arg1; @@ -183,6 +184,7 @@ llvm::Function *function; bool can_error; + bool side_effects; jit_type *result; std::vector arguments; }; @@ -192,16 +194,16 @@ add_overload (func, func.arguments); } - void add_overload (llvm::Function *f, bool e, jit_type *r, jit_type *arg0) + void add_overload (llvm::Function *f, bool e, bool s, jit_type *r, jit_type *arg0) { - overload ol (f, e, r, arg0); + overload ol (f, e, s, r, arg0); add_overload (ol); } - void add_overload (llvm::Function *f, bool e, jit_type *r, jit_type *arg0, + void add_overload (llvm::Function *f, bool e, bool s, jit_type *r, jit_type *arg0, jit_type *arg1) { - overload ol (f, e, r, arg0, arg1); + overload ol (f, e, s, r, arg0, arg1); add_overload (ol); } @@ -293,6 +295,11 @@ return instance->release_fn; } + static const jit_function::overload& get_release (jit_type *type) + { + return instance->release_fn.get_overload (type); + } + static const jit_function& print_value (void) { return instance->print_fn; @@ -490,19 +497,54 @@ // We convert the octave parse tree to this IR directly. #define JIT_VISIT_IR_NOTEMPLATE \ - JIT_METH(block); \ - JIT_METH(break); \ - JIT_METH(cond_break); \ - JIT_METH(call); \ - JIT_METH(extract_argument); \ - JIT_METH(store_argument); \ - JIT_METH(phi); \ + JIT_METH(block) \ + JIT_METH(break) \ + JIT_METH(cond_break) \ + JIT_METH(call) \ + JIT_METH(extract_argument) \ + JIT_METH(store_argument) \ + JIT_METH(phi) \ JIT_METH(variable) +#define JIT_VISIT_IR_CONST \ + JIT_METH(const_scalar) \ + JIT_METH(const_index) \ + JIT_METH(const_string) \ + JIT_METH(const_range) + +#define JIT_VISIT_IR_ABSTRACT \ + JIT_METH(instruction) \ + JIT_METH(terminator) + #define JIT_VISIT_IR_CLASSES \ - JIT_VISIT_IR_NOTEMPLATE; \ + JIT_VISIT_IR_NOTEMPLATE \ JIT_VISIT_IR_CONST +#define JIT_VISIT_IR_ALL \ + JIT_VISIT_IR_CLASSES \ + JIT_VISIT_IR_ABSTRACT + +// forward declare all ir classes +#define JIT_METH(cname) \ + class jit_ ## cname; + +JIT_VISIT_IR_ABSTRACT +JIT_VISIT_IR_NOTEMPLATE + +#undef JIT_METH + +// constants are typedefs from jit_const +template +class jit_const; + +typedef jit_const jit_const_scalar; +typedef jit_const jit_const_index; + +typedef jit_const +jit_const_string; +typedef jit_const +jit_const_range; class jit_ir_walker; class jit_use; @@ -566,6 +608,22 @@ { llvm_value = compiled; } + +#define JIT_METH(cname) \ + virtual bool is_ ## cname (void) const \ + { return false; } \ + \ + virtual jit_ ## cname *to_ ## cname (void) \ + { return 0; } \ + \ + virtual const jit_ ## cname *to_ ## cname (void) const \ + { return 0; } + +JIT_VISIT_IR_NOTEMPLATE +JIT_VISIT_IR_ABSTRACT + +#undef JIT_METH + protected: std::ostream& print_indent (std::ostream& os, size_t indent) const { @@ -583,8 +641,15 @@ std::ostream& operator<< (std::ostream& os, const jit_value& value); -class jit_instruction; -class jit_block; +#define JIT_GEN_CASTS(cname) \ + virtual bool is_ ## cname (void) const \ + { return true; } \ + \ + virtual jit_ ## cname *to_ ## cname (void) \ + { return this; } \ + \ + virtual const jit_ ## cname *to_ ## cname (void) const \ + { return this; } class jit_use @@ -615,6 +680,8 @@ jit_block *user_parent (void) const; + std::list user_parent_location (void) const; + void stash_value (jit_value *avalue, jit_instruction *auser = 0, size_t aindex = -1) { @@ -668,8 +735,6 @@ size_t mindex; }; -class jit_variable; - class jit_instruction : public jit_value { @@ -738,6 +803,20 @@ return argument_type (i)->to_llvm (); } + // generate functions of form argument_type where type is any subclass of + // jit_value +#define JIT_METH(cname) \ + jit_ ## cname *argument_ ## cname (size_t i) const \ + { \ + jit_value *arg = argument (i); \ + return arg ? arg->to_ ## cname () : 0; \ + } + +JIT_VISIT_IR_ABSTRACT +JIT_VISIT_IR_NOTEMPLATE + +#undef JIT_METH + std::ostream& print_argument (std::ostream& os, size_t i) const { if (argument (i)) @@ -770,8 +849,14 @@ const std::vector& argument_types (void) const { return already_infered; } + virtual bool dead (void) const { return false; } + + virtual bool almost_dead (void) const { return false; } + virtual bool infer (void) { return false; } + void remove (void); + void push_variable (void); void pop_variable (void); @@ -780,17 +865,25 @@ jit_block *parent (void) const { return mparent; } + std::list::iterator location (void) const + { + return mlocation; + } + llvm::BasicBlock *parent_llvm (void) const; - void stash_parent (jit_block *aparent) + void stash_parent (jit_block *aparent, + std::list::iterator alocation) { - assert (! mparent); mparent = aparent; + mlocation = alocation; } jit_variable *tag (void) const; void stash_tag (jit_variable *atag); + + JIT_GEN_CASTS (instruction) protected: std::vector already_infered; private: @@ -809,14 +902,15 @@ size_t id; jit_block *mparent; + std::list::iterator mlocation; }; // defnie accept methods for subclasses #define JIT_VALUE_ACCEPT(clname) \ virtual void accept (jit_ir_walker& walker); -template +template class jit_const : public jit_instruction { @@ -847,24 +941,6 @@ T mvalue; }; -typedef jit_const jit_const_scalar; -typedef jit_const jit_const_index; - -typedef jit_const -jit_const_string; -typedef jit_const -jit_const_range; - -#define JIT_VISIT_IR_CONST \ - JIT_METH(const_scalar); \ - JIT_METH(const_index); \ - JIT_METH(const_string); \ - JIT_METH(const_range) - -class jit_terminator; -class jit_phi; -class jit_convert; - class jit_block : public jit_value { @@ -884,6 +960,8 @@ jit_instruction *prepend (jit_instruction *instr); + jit_instruction *prepend_after_phi (jit_instruction *instr); + jit_instruction *append (jit_instruction *instr); jit_instruction *insert_before (iterator loc, jit_instruction *instr); @@ -892,7 +970,9 @@ void remove (jit_block::iterator iter) { + jit_instruction *instr = *iter; instructions.erase (iter); + instr->stash_parent (0, instructions.end ()); } jit_terminator *terminator (void) const; @@ -1001,11 +1081,18 @@ create_dom_tree (mvisit_count); } - void construct_ssa (jit_convert& convert) + // visit blocks in the order of the dominator tree + // inorder - Run on the root first, then children + // postorder - Run on children first, then the root + template + void visit_dom (func_type0 inorder, func_type1 postorder) { - do_construct_ssa (convert, mvisit_count); + do_visit_dom (mvisit_count, inorder, postorder); } + // call pop_varaible on all instructions + void pop_all (void); + virtual std::ostream& print (std::ostream& os, size_t indent) const { print_indent (os, indent) << mname << ": %pred = "; @@ -1036,19 +1123,19 @@ llvm::BasicBlock *to_llvm (void) const; JIT_VALUE_ACCEPT (block) + JIT_GEN_CASTS (block) private: void compute_df (size_t visit_count); bool update_idom (size_t visit_count); - void finish_phi (jit_block *pred); - - void do_construct_ssa (jit_convert& convert, size_t visit_count); - void create_dom_tree (size_t visit_count); jit_block *idom_intersect (jit_block *b); + template + void do_visit_dom (size_t visit_count, func_type0 inorder, func_type1 postorder); + static const size_t NO_ID = static_cast (-1); size_t mvisit_count; size_t mid; @@ -1060,6 +1147,54 @@ mutable std::vector mpred_llvm; }; +// allow regular function pointers as well as pointers to members +template +class jit_block_callback +{ +public: + jit_block_callback (func_type afunction) : function (afunction) {} + + void operator() (jit_block& block) + { + function (block); + } +private: + func_type function; +}; + +template <> +class jit_block_callback +{ +public: + typedef void (jit_block::*func_type)(void); + + jit_block_callback (func_type afunction) : function (afunction) {} + + void operator() (jit_block& ablock) + { + (ablock.*function) (); + } +private: + func_type function; +}; + +template +void +jit_block::do_visit_dom (size_t visit_count, func_type0 inorder, func_type1 postorder) +{ + if (mvisit_count > visit_count) + return; + mvisit_count = visit_count + 1; + + jit_block_callback inorder_cb (inorder); + inorder_cb (*this); + + for (size_t i = 0; i < dom_succ.size (); ++i) + dom_succ[i]->do_visit_dom (visit_count, inorder, postorder); + + jit_block_callback postorder_cb (postorder); + postorder_cb (*this); +} // A non-ssa variable @@ -1067,7 +1202,7 @@ jit_variable : public jit_value { public: - jit_variable (const std::string& aname) : mname (aname) {} + jit_variable (const std::string& aname) : mname (aname), mlast_use (0) {} const std::string &name (void) const { return mname; } @@ -1083,9 +1218,10 @@ return value_stack.top (); } - void push (jit_value *v) + void push (jit_instruction *v) { value_stack.push (v); + mlast_use = v; } void pop (void) @@ -1093,6 +1229,16 @@ 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) { @@ -1110,9 +1256,11 @@ } JIT_VALUE_ACCEPT (variable) + JIT_GEN_CASTS (variable) private: std::string mname; std::stack value_stack; + jit_instruction *mlast_use; }; class @@ -1125,6 +1273,16 @@ stash_tag (avariable); } + virtual bool dead (void) const + { + return use_count () == 0; + } + + virtual bool almost_dead (void) const + { + return use_count () <= 1; + } + virtual bool infer (void) { jit_type *infered = 0; @@ -1167,6 +1325,7 @@ } JIT_VALUE_ACCEPT (phi); + JIT_GEN_CASTS (phi) }; class @@ -1197,6 +1356,8 @@ } virtual size_t sucessor_count (void) const = 0; + + JIT_GEN_CASTS (terminator) }; class @@ -1220,6 +1381,7 @@ } JIT_VALUE_ACCEPT (break) + JIT_GEN_CASTS (break) }; class @@ -1258,6 +1420,7 @@ } JIT_VALUE_ACCEPT (cond_break) + JIT_GEN_CASTS (cond_break) }; class @@ -1280,6 +1443,11 @@ const jit_function& function (void) const { return mfunction; } + bool has_side_effects (void) const + { + return overload ().side_effects; + } + const jit_function::overload& overload (void) const { return mfunction.get_overload (argument_types ()); @@ -1302,9 +1470,14 @@ return os << ")"; } + virtual bool dead (void) const; + + virtual bool almost_dead (void) const; + virtual bool infer (void); JIT_VALUE_ACCEPT (call) + JIT_GEN_CASTS (call) private: const jit_function& mfunction; }; @@ -1339,6 +1512,7 @@ } JIT_VALUE_ACCEPT (extract_argument) + JIT_GEN_CASTS (extract_argument) }; class @@ -1385,6 +1559,7 @@ } JIT_VALUE_ACCEPT (store_argument) + JIT_GEN_CASTS (store_argument) }; class @@ -1394,7 +1569,7 @@ virtual ~jit_ir_walker () {} #define JIT_METH(clname) \ - virtual void visit (jit_ ## clname&) = 0 + virtual void visit (jit_ ## clname&) = 0; JIT_VISIT_IR_CLASSES; @@ -1548,6 +1723,9 @@ return ret; } private: + typedef std::list block_list; + typedef block_list::iterator block_iterator; + std::vector > arguments; type_bound_vector bounds; @@ -1597,6 +1775,10 @@ void construct_ssa (jit_block *final_block); + static void do_construct_ssa (jit_block& block); + + void place_releases (void); + void print_blocks (const std::string& header) { std::cout << "-------------------- " << header << " --------------------\n"; @@ -1621,13 +1803,20 @@ std::cout << std::endl; } - typedef std::list break_list; + bool breaking; // true if we are breaking OR continuing + block_list breaks; + block_list continues; + + void finish_breaks (jit_block *dest, const block_list& lst); - bool breaking; // true if we are breaking OR continuing - break_list breaks; - break_list continues; + struct release_placer + { + release_placer (jit_convert& aconvert) : convert (aconvert) {} - void finish_breaks (jit_block *dest, const break_list& lst); + jit_convert& convert; + + void operator() (jit_block& block); + }; // this case is much simpler, just convert from the jit ir to llvm class @@ -1648,6 +1837,7 @@ // name -> llvm argument std::map arguments; + void finish_phi (jit_instruction *phi); void visit (jit_value *jvalue) {