# HG changeset patch # User Max Brister # Date 1340659560 18000 # Node ID b23a98ca0e436d89be9b7ad79be19a38eafdcaf6 # Parent 0f156affb036037bda38c89de140c9132d6253cd Remove jit_block::visit_dom and simplify release placement * src/pt-jit.cc (octave_jit_paren_subsasgn_impl): Remove debug print. (jit_value::first_use_block): New function. (jit_block::compute_df, jit_block::update_idom, jit_block::create_dom_tree): Use visited function. (jit_convert::construct_ssa): Call do_construct_ssa with visit count. (jit_convert::do_construct_ssa): Use dominator graph directly. (jit_convert::place_releases, jit_convert::release_temp): Track temporaries instead of using compute_temp. (jit_convert::compute_temp::compute_temp, jit_convert::compute_temp::operator ()): Removed function. * src/pt-jit.cc (jit_value::fire_use_block): New declaration. (jit_block::label): Use visited function. (jit_block::dom_successor, jit_block::dom_successor_count, jit_block::visited, jit_block::visit_count): New functions. (jit_block::visit_dom, jit_block::do_visit_dom): Removed function. (jit_block_callback): Removed class. (jit_convert::do_construct_ssa, jit_convert::rleease_temp): Change function signature. (jit_convert::instr_set): Remove typedef. (jit_convert::compute_temp): Remove class declaration. diff -r 0f156affb036 -r b23a98ca0e43 src/pt-jit.cc --- a/src/pt-jit.cc Mon Jun 25 14:40:21 2012 -0500 +++ b/src/pt-jit.cc Mon Jun 25 16:26:00 2012 -0500 @@ -240,7 +240,6 @@ octave_jit_paren_subsasgn_impl (jit_matrix *mat, octave_idx_type index, double value) { - std::cout << "impl\n"; NDArray *array = mat->array; if (array->nelem () < index) array->resize1 (index); @@ -1057,6 +1056,21 @@ jit_value::~jit_value (void) {} +jit_block * +jit_value::first_use_block (void) +{ + jit_use *use = first_use (); + while (use) + { + if (! isa (use->user ())) + return use->user_parent (); + + use = use->next (); + } + + return 0; +} + void jit_value::replace_with (jit_value *value) { @@ -1322,11 +1336,10 @@ } void -jit_block::compute_df (size_t visit_count) +jit_block::compute_df (size_t avisit_count) { - if (mvisit_count > visit_count) + if (visited (avisit_count)) return; - ++mvisit_count; if (use_count () >= 2) { @@ -1342,24 +1355,20 @@ } for (size_t i = 0; i < successor_count (); ++i) - successor (i)->compute_df (visit_count); + successor (i)->compute_df (avisit_count); } bool -jit_block::update_idom (size_t visit_count) +jit_block::update_idom (size_t avisit_count) { - if (mvisit_count > visit_count) - return false; - ++mvisit_count; - - if (! use_count ()) + if (visited (avisit_count) || ! use_count ()) return false; bool changed = false; for (jit_use *use = first_use (); use; use = use->next ()) { jit_block *pred = use->user_parent (); - changed = pred->update_idom (visit_count) || changed; + changed = pred->update_idom (avisit_count) || changed; } jit_use *use = first_use (); @@ -1425,17 +1434,16 @@ } void -jit_block::create_dom_tree (size_t visit_count) +jit_block::create_dom_tree (size_t avisit_count) { - if (mvisit_count > visit_count) + if (visited (avisit_count)) return; - ++mvisit_count; if (idom != this) idom->dom_succ.push_back (this); for (size_t i = 0; i < successor_count (); ++i) - successor (i)->create_dom_tree (visit_count); + successor (i)->create_dom_tree (avisit_count); } jit_block * @@ -2405,14 +2413,17 @@ } } - entry_block->visit_dom (&jit_convert::do_construct_ssa, &jit_block::pop_all); + do_construct_ssa (*entry_block, entry_block->visit_count ()); } void -jit_convert::do_construct_ssa (jit_block& block) +jit_convert::do_construct_ssa (jit_block& ablock, size_t avisit_count) { + if (ablock.visited (avisit_count)) + return; + // replace variables with their current SSA value - for (jit_block::iterator iter = block.begin (); iter != block.end (); ++iter) + for (jit_block::iterator iter = ablock.begin (); iter != ablock.end (); ++iter) { jit_instruction *instr = *iter; instr->construct_ssa (); @@ -2420,9 +2431,9 @@ } // finish phi nodes of successors - for (size_t i = 0; i < block.successor_count (); ++i) + for (size_t i = 0; i < ablock.successor_count (); ++i) { - jit_block *finish = block.successor (i); + jit_block *finish = ablock.successor (i); for (jit_block::iterator iter = finish->begin (); iter != finish->end () && isa (*iter);) @@ -2431,7 +2442,7 @@ jit_variable *var = phi->dest (); if (var->has_top ()) { - phi->add_incomming (&block, var->top ()); + phi->add_incomming (&ablock, var->top ()); ++iter; } else @@ -2443,6 +2454,11 @@ } } } + + for (size_t i = 0; i < ablock.dom_successor_count (); ++i) + do_construct_ssa (*ablock.dom_successor (i), avisit_count); + + ablock.pop_all (); } void @@ -2497,34 +2513,67 @@ void jit_convert::place_releases (void) { - compute_temp tinfo (*this); - + std::set temporaries; for (block_list::iterator iter = blocks.begin (); iter != blocks.end (); ++iter) { jit_block& ablock = **iter; if (ablock.id () != jit_block::NO_ID) { - release_temp (ablock, tinfo.temp_out (ablock)); + release_temp (ablock, temporaries); release_dead_phi (ablock); } } - } void -jit_convert::release_temp (jit_block& ablock, const instr_set& temp) +jit_convert::release_temp (jit_block& ablock, std::set& temp) { - if (! temp.size ()) - return; - - jit_block *split = ablock.maybe_split (*this, final_block); - jit_terminator *term = split->terminator (); - for (instr_set::const_iterator iter = temp.begin (); iter != temp.end (); + for (jit_block::iterator iter = ablock.begin (); iter != ablock.end (); ++iter) { jit_instruction *instr = *iter; - jit_call *release = create (&jit_typeinfo::release, instr); + + // check for temporaries that require release and live across + // multiple blocks + if (instr->needs_release ()) + { + jit_block *fu_block = instr->first_use_block (); + if (fu_block && fu_block != &ablock) + temp.insert (instr); + } + + if (isa (instr)) + { + // place releases for temporary arguments + for (size_t i = 0; i < instr->argument_count (); ++i) + { + jit_value *arg = instr->argument (i); + if (arg->needs_release ()) + { + jit_call *release = create (&jit_typeinfo::release, + arg); + release->infer (); + ablock.insert_after (iter, release); + ++iter; + temp.erase (arg); + } + } + } + } + + if (! temp.size () || ! isa (ablock.terminator ())) + return; + + // FIXME: If we support try/catch or unwind_protect final_block may not be the + // destination + jit_block *split = ablock.maybe_split (*this, final_block); + jit_terminator *term = split->terminator (); + for (std::set::const_iterator iter = temp.begin (); + iter != temp.end (); ++iter) + { + jit_value *value = *iter; + jit_call *release = create (&jit_typeinfo::release, value); split->insert_before (term, release); release->infer (); } @@ -2611,96 +2660,6 @@ } } -// -------------------- jit_convert::compute_temp -------------------- -jit_convert::compute_temp::compute_temp (jit_convert& aconvert) - : convert (aconvert), mtemp_out (aconvert.final_block->id () + 1) -{ - block_list& blocks = convert.blocks; - - // initialze mtemp_out - for (block_list::iterator biter = blocks.begin (); biter != blocks.end (); - ++biter) - { - jit_block& block = **biter; - instr_set& tout = temp_out (block); - for (jit_block::iterator iter = block.begin (); iter != block.end (); - ++iter) - { - jit_instruction *instr = *iter; - - // check for temporaries that require release and live across - // multiple blocks - if (instr->needs_release () - && instr->use_count () >= 1) - { - bool parent_in_block = false; - jit_use *use = instr->first_use (); - while (use) - { - // skip error checks, as they do not release their use - if (! isa (use->user ()) - && use->user_parent () == &block) - { - parent_in_block = true; - break; - } - - use = use->next (); - } - - if (! parent_in_block) - tout.insert (instr); - } - - if (isa (instr)) - { - // place releases for temporary arguments - for (size_t i = 0; i < instr->argument_count (); ++i) - { - jit_value *arg = instr->argument (i); - if (arg->needs_release ()) - { - jit_call *release - = convert.create (&jit_typeinfo::release, - arg); - release->infer (); - block.insert_after (iter, release); - ++iter; - } - } - } - } - } - - do - { - changed = false; - convert.entry_block->visit_dom (*this, 0); - } - while (changed); -} - -void -jit_convert::compute_temp::operator() (jit_block& block) -{ - instr_set& tout = temp_out (block); - for (jit_use *use = block.first_use (); use; use = use->next ()) - { - jit_block& pred = *use->user_parent (); - instr_set& pred_tout = temp_out (pred); - for (instr_set::iterator iter = pred_tout.begin (); - iter != pred_tout.end (); ++ iter) - { - jit_instruction *instr = *iter; - jit_block *use_in = instr->parent (); - - // FIXME: Only valid until we support try/catch or unwind_protect - if (use_in != &block && &block != convert.final_block) - changed = changed || tout.insert (instr).second; - } - } -} - // -------------------- jit_convert::convert_llvm -------------------- llvm::Function * jit_convert::convert_llvm::convert (llvm::Module *module, diff -r 0f156affb036 -r b23a98ca0e43 src/pt-jit.h --- a/src/pt-jit.h Mon Jun 25 14:40:21 2012 -0500 +++ b/src/pt-jit.h Mon Jun 25 16:26:00 2012 -0500 @@ -776,6 +776,10 @@ 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); @@ -1235,16 +1239,15 @@ label (mvisit_count, number); } - void label (size_t visit_count, size_t& number) + void label (size_t avisit_count, size_t& number) { - if (mvisit_count > visit_count) + if (visited (avisit_count)) return; - ++mvisit_count; for (jit_use *use = first_use (); use; use = use->next ()) { jit_block *pred = use->user_parent (); - pred->label (visit_count, number); + pred->label (avisit_count, number); } mid = number++; @@ -1273,13 +1276,14 @@ create_dom_tree (mvisit_count); } - // 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) + jit_block *dom_successor (size_t idx) const { - do_visit_dom (mvisit_count, inorder, postorder); + return dom_succ[idx]; + } + + size_t dom_successor_count (void) const + { + return dom_succ.size (); } // call pop_varaible on all instructions @@ -1333,22 +1337,34 @@ void stash_location (std::list::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 visit_count); - - bool update_idom (size_t visit_count); - - void create_dom_tree (size_t visit_count); + void compute_df (size_t avisit_count); + + bool update_idom (size_t avisit_count); + + void create_dom_tree (size_t avisit_count); jit_block *idom_intersect (jit_block *b); - template - void do_visit_dom (size_t visit_count, func_type0 inorder, - func_type1 postorder); - size_t mvisit_count; size_t mid; jit_block *idom; @@ -1388,67 +1404,6 @@ jit_phi *muser; }; -// 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: - jit_block_callback (int) {} - - void operator() (jit_block&) - {} -}; - -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 class jit_variable : public jit_value @@ -2276,15 +2231,13 @@ void construct_ssa (void); - static void do_construct_ssa (jit_block& block); + void do_construct_ssa (jit_block& block, size_t avisit_count); void remove_dead (); - typedef std::set instr_set; - void place_releases (void); - void release_temp (jit_block& ablock, const instr_set& temp); + void release_temp (jit_block& ablock, std::set& temp); void release_dead_phi (jit_block& ablock); @@ -2322,25 +2275,6 @@ void finish_breaks (jit_block *dest, const block_list& lst); - // compute per block information about temporaries - class - compute_temp - { - public: - compute_temp (jit_convert& aconvert); - - void operator() (jit_block& block); - - instr_set &temp_out (jit_block& b) - { - return mtemp_out[b.id ()]; - } - private: - jit_convert& convert; - std::vector mtemp_out; - bool changed; - }; - // this case is much simpler, just convert from the jit ir to llvm class convert_llvm : public jit_ir_walker