Mercurial > hg > octave-lyh
changeset 14963:709f50069722
Change algorithm for placing releases and simplify PHIs in low level Octave IR
* src/pt-jit.cc (octave_jit_compute_nelem): Fix whitepsace issue.
(octave_jit_gindex_range): Remove debug print.
(jit_block::replace_in_phi, jit_block::maybe_split,
jit_block::jit_phi_incomming, jit_phi::to_llvm, jit_convert::append,
jit_convert::insert_before, jit_convert::insert_after,
jit_convert::simplify_phi): New function.
(jit_block::branch_llvm, jit_terminator::create_merge): Removed function.
(jit_convert::jit_convert): Replace add_block with append and simplify phi.
(jit_convert::visit_simple_for_command, jit_convert::visit_if_command_list):
Replace add_block with append.
(jit_convert::place_releases): Use compute_temp instead of release_placer.
(jit_convert::compute_temp): New class.
(jit_convert::release_placer): Removed class.
(jit_convert::convert_llvm::finish_phi): Do not check phi argument types.
(jit_convert::convert_llvm::visit): Do not create merge blocks.
* src/pt-jit.h (jit_block::NO_ID): Made public.
(jit_block::jit_block): Add visit_count argument.
(jit_block::replace_in_phi, jit_block::maybe_split, jit_phi::to_llvm,
jit_convert::simplify_phi): New declaration.
(jit_block::branch_llvm, jit_terminator::create_merge): Remove declaration.
(jit_block::jit_phi_incomming): Keep track of phi user.
(jit_block::jit_block::callback<int>): New template specialization.
(jit_assign::src): Do not cast src to jit_instruction.
(jit_phi::add_incomming): Keep track of this.
(jit_phi::incomming_llvm): Access incomming llvm directly.
(jit_call::needs_release): New function.
(jit_convert::add_block): Renamed to jit_convert::append.
(jit_convert::create_checked_impl): Use append instead of add_block.
(jit_convert::release_placer): Removed class.
(jit_convert::compute_temp): New class.
(jit_convert::finish_phi): Change declaration to take a jit_phi as argument.
author | Max Brister <max@2bass.com> |
---|---|
date | Thu, 21 Jun 2012 15:08:06 -0500 |
parents | 90a7a2af2cd5 |
children | 434ffa574c78 |
files | src/pt-jit.cc src/pt-jit.h |
diffstat | 2 files changed, 290 insertions(+), 179 deletions(-) [+] |
line wrap: on
line diff
--- a/src/pt-jit.cc +++ b/src/pt-jit.cc @@ -137,7 +137,7 @@ octave_jit_compute_nelem (double base, double limit, double inc) { Range rng = Range (base, limit, inc); - return rng.nelem (); + return rng.nelem (); } extern "C" void @@ -222,7 +222,6 @@ octave_jit_gindex_range (int nd, int dim, octave_idx_type iext, octave_idx_type ext) { - std::cout << "gindex_range\n"; try { gripe_index_out_of_range (nd, dim, iext, ext); @@ -1074,6 +1073,20 @@ } } +void +jit_block::replace_in_phi (jit_block *ablock, jit_block *with) +{ + jit_phi_incomming *node = ILIST_T::first_use (); + while (node) + { + jit_phi_incomming *prev = node; + node = node->next (); + + if (prev->user_parent () == ablock) + prev->stash_value (with); + } +} + jit_block * jit_block::maybe_merge () { @@ -1199,18 +1212,6 @@ } llvm::BasicBlock * -jit_block::branch_llvm (size_t idx) const -{ - return terminator ()->branch_llvm (idx); -} - -llvm::BasicBlock * -jit_block::branch_llvm (jit_block *succ) const -{ - return terminator ()->branch_llvm (succ); -} - -llvm::BasicBlock * jit_block::to_llvm (void) const { return llvm::cast<llvm::BasicBlock> (llvm_value); @@ -1322,6 +1323,27 @@ } } +jit_block * +jit_block::maybe_split (jit_convert& convert, jit_block *asuccessor) +{ + if (successor_count () > 1) + { + jit_terminator *term = terminator (); + size_t idx = term->successor_index (asuccessor); + jit_block *split = convert.create<jit_block> ("phi_split", mvisit_count); + + convert.insert_after (this, split); + term->stash_argument (idx, split); + jit_branch *br = split->append (convert.create<jit_branch> (asuccessor)); + replace_in_phi (asuccessor, split); + br->infer (); + + return split; + } + + return this; +} + void jit_block::create_dom_tree (size_t visit_count) { @@ -1354,6 +1376,12 @@ return i; } +// -------------------- jit_phi_incomming -------------------- + +jit_block * +jit_phi_incomming::user_parent (void) const +{ return muser->parent (); } + // -------------------- jit_phi -------------------- bool jit_phi::prune (void) @@ -1420,6 +1448,12 @@ return false; } +llvm::PHINode * +jit_phi::to_llvm (void) const +{ + return llvm::cast<llvm::PHINode> (jit_value::to_llvm ()); +} + // -------------------- jit_terminator -------------------- size_t jit_terminator::successor_index (const jit_block *asuccessor) const @@ -1432,31 +1466,6 @@ panic_impossible (); } -void -jit_terminator::create_merge (llvm::Function *function, jit_block *asuccessor) -{ - size_t idx = successor_index (asuccessor); - if (! mbranch_llvm[idx] && successor_count () > 1) - { - assert (parent ()); - assert (parent_llvm ()); - llvm::BasicBlock *merge = llvm::BasicBlock::Create (context, "phi_merge", - function, - parent_llvm ()); - - // fix the predecessor jump if it has been created - if (has_llvm ()) - { - llvm::TerminatorInst *branch = to_llvm (); - branch->setSuccessor (idx, merge); - } - - llvm::IRBuilder<> temp (merge); - temp.CreateBr (successor_llvm (idx)); - mbranch_llvm[idx] = merge; - } -} - bool jit_terminator::infer (void) { @@ -1519,7 +1528,7 @@ entry_block = create<jit_block> ("body"); final_block = create<jit_block> ("final"); - add_block (entry_block); + append (entry_block); entry_block->mark_alive (); block = entry_block; visit (tee); @@ -1530,7 +1539,7 @@ assert (continues.empty ()); block->append (create<jit_branch> (final_block)); - add_block (final_block); + append (final_block); for (vmap_t::iterator iter = vmap.begin (); iter != vmap.end (); ++iter) { @@ -1566,6 +1575,8 @@ remove_dead (); merge_blocks (); + simplify_phi (); + final_block->label (); place_releases (); #ifdef OCTAVE_JIT_DEBUG @@ -1715,7 +1726,7 @@ vmap[iter_name] = iterator; jit_block *body = create<jit_block> ("for_body"); - add_block (body); + append (body); jit_block *tail = create<jit_block> ("for_tail"); @@ -1744,14 +1755,14 @@ // WTF are you doing user? Every branch was a continue, why did you have // a loop??? Users are silly people... finish_breaks (tail, breaks); - add_block (tail); + append (tail); block = tail; return; } // check our condition, continues jump to this block jit_block *check_block = create<jit_block> ("for_check"); - add_block (check_block); + append (check_block); if (! breaking) block->append (create<jit_branch> (check_block)); @@ -1768,7 +1779,7 @@ block->append (create<jit_cond_branch> (check, body, tail)); // breaks will go to our tail - add_block (tail); + append (tail); finish_breaks (tail, breaks); block = tail; } @@ -1867,7 +1878,7 @@ assert (block); if (i) // the first block is prev_block, so it has already been added - add_block (entry_blocks[i]); + append (entry_blocks[i]); if (! tic->is_else_clause ()) { @@ -1879,7 +1890,7 @@ jit_block *body = create<jit_block> (i == 0 ? "if_body" : "ifelse_body"); - add_block (body); + append (body); jit_instruction *br = create<jit_cond_branch> (check, body, entry_blocks[i + 1]); @@ -1902,7 +1913,7 @@ if (num_incomming || ! last_else) { - add_block (tail); + append (tail); block = tail; } else @@ -2129,6 +2140,27 @@ fail (); } +void +jit_convert::append (jit_block *ablock) +{ + blocks.push_back (ablock); + ablock->stash_location (--blocks.end ()); +} + +void +jit_convert::insert_before (block_iterator iter, jit_block *ablock) +{ + iter = blocks.insert (iter, ablock); + ablock->stash_location (iter); +} + +void +jit_convert::insert_after (block_iterator iter, jit_block *ablock) +{ + ++iter; + insert_before (iter, ablock); +} + jit_variable * jit_convert::get_variable (const std::string& vname) { @@ -2356,8 +2388,46 @@ void jit_convert::place_releases (void) { - release_placer placer (*this); - entry_block->visit_dom (placer, &jit_block::pop_all); + compute_temp tinfo (*this); +} + +void +jit_convert::simplify_phi (void) +{ + for (block_list::iterator biter = blocks.begin (); biter != blocks.end (); + ++biter) + { + jit_block &ablock = **biter; + for (jit_block::iterator iter = ablock.begin (); iter != ablock.end () + && isa<jit_phi> (*iter); ++iter) + simplify_phi (*static_cast<jit_phi *> (*iter)); + } +} + +void +jit_convert::simplify_phi (jit_phi& phi) +{ + jit_block& pblock = *phi.parent (); + const jit_function& cast_fn = jit_typeinfo::cast (phi.type ()); + jit_variable *dest = phi.dest (); + for (size_t i = 0; i < phi.argument_count (); ++i) + { + jit_value *arg = phi.argument (i); + if (arg->type () != phi.type ()) + { + jit_block *pred = phi.incomming (i); + jit_block *split = pred->maybe_split (*this, pblock); + jit_terminator *term = split->terminator (); + jit_instruction *cast = create<jit_call> (cast_fn, arg); + jit_assign *assign = create<jit_assign> (dest, cast); + + split->insert_before (term, cast); + split->insert_before (term, assign); + cast->infer (); + assign->infer (); + phi.stash_argument (i, assign); + } + } } void @@ -2371,38 +2441,76 @@ } } -// -------------------- jit_convert::release_placer -------------------- -void -jit_convert::release_placer::operator() (jit_block& block) +// -------------------- jit_convert::compute_temp -------------------- +jit_convert::compute_temp::compute_temp (jit_convert& aconvert) + : convert (aconvert), mtemp_out (aconvert.final_block->id () + 1) { - for (jit_block::iterator iter = block.begin (); iter != block.end (); ++iter) + block_list& blocks = convert.blocks; + + // initialze mtemp_out + for (block_list::iterator biter = blocks.begin (); biter != blocks.end (); + ++biter) { - jit_instruction *instr = *iter; - instr->stash_last_use (instr); - - for (size_t i = 0; i < instr->argument_count (); ++i) + jit_block& block = **biter; + instr_set& tout = temp_out (block); + for (jit_block::iterator iter = block.begin (); iter != block.end (); + ++iter) { - jit_value *arg = instr->argument (i); - assert (arg); - arg->stash_last_use (instr); + jit_instruction *instr = *iter; + + // check for temporaries that require release and live across + // multiple blocks + if (instr->needs_release () + && instr->use_count () == 1 + && instr->first_use ()->user_parent () != &block) + tout.insert (instr); + + if (isa<jit_call> (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_call> (&jit_typeinfo::release, + arg); + release->infer (); + block.insert_after (iter, release); + ++iter; + } + } + } } - - jit_assign *assign = dynamic_cast<jit_assign *> (instr); - if (assign && assign->dest ()->has_top ()) + } + + 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_variable *var = assign->dest (); - jit_instruction *last_use = var->last_use (); - jit_call *release = convert.create<jit_call> (jit_typeinfo::release, - var->top ()); - release->infer (); - if (last_use && last_use->parent () == &block - && ! isa<jit_phi> (last_use)) - block.insert_after (last_use->location (), release); - else - block.prepend_after_phi (release); + 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; } - - instr->push_variable (); } } @@ -2467,7 +2575,7 @@ piter != block.end () && isa<jit_phi> (*piter); ++piter) { jit_instruction *phi = *piter; - finish_phi (phi); + finish_phi (static_cast<jit_phi *> (phi)); } } @@ -2484,72 +2592,13 @@ } void -jit_convert::convert_llvm::finish_phi (jit_instruction *aphi) +jit_convert::convert_llvm::finish_phi (jit_phi *phi) { - jit_phi *phi = static_cast<jit_phi *> (aphi); - llvm::PHINode *llvm_phi = llvm::cast<llvm::PHINode> (phi->to_llvm ()); - - bool can_remove = ! phi->use_count (); - if (! can_remove && llvm_phi->hasOneUse () && phi->use_count () == 1) - { - jit_instruction *user = phi->first_use ()->user (); - can_remove = isa<jit_call> (user); // must be a remove - } - - if (can_remove) + llvm::PHINode *llvm_phi = phi->to_llvm (); + for (size_t i = 0; i < phi->argument_count (); ++i) { - // replace with releases along each incomming branch - while (! llvm_phi->use_empty ()) - { - llvm::Instruction *llvm_instr; - llvm_instr = llvm::cast<llvm::Instruction> (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 = phi->incomming_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 ()); - } - - create_call (ol, phi->argument (i)); - } - } - } - else - { - for (size_t i = 0; i < phi->argument_count (); ++i) - { - llvm::BasicBlock *pred = phi->incomming_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)); - - llvm::Value *casted = create_call (ol, phi->argument (i)); - llvm_phi->addIncoming (casted, pred); - } - } + llvm::BasicBlock *pred = phi->incomming_llvm (i); + llvm_phi->addIncoming (phi->argument_llvm (i), pred); } } @@ -2651,15 +2700,6 @@ phi.argument_count ()); builder.Insert (node); phi.stash_llvm (node); - - jit_block *pblock = phi.parent (); - for (size_t i = 0; i < phi.argument_count (); ++i) - if (phi.argument_type (i) != phi.type ()) - { - jit_block *inc = phi.incomming (i); - jit_terminator *term = inc->terminator (); - term->create_merge (function, pblock); - } } void
--- a/src/pt-jit.h +++ b/src/pt-jit.h @@ -87,6 +87,7 @@ class Twine; class GlobalVariable; class TerminatorInst; + class PHINode; } class octave_base_value; @@ -732,6 +733,8 @@ #undef JIT_METH +class jit_convert; + // ABCs which aren't included in JIT_VISIT_IR_ALL class jit_instruction; class jit_terminator; @@ -801,6 +804,8 @@ 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 @@ -1124,12 +1129,17 @@ typedef std::set<jit_block *> df_set; typedef df_set::const_iterator df_iterator; - jit_block (const std::string& aname) : mvisit_count (0), mid (NO_ID), - idom (0), mname (aname), malive (false) + 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 (); } @@ -1161,8 +1171,18 @@ 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; @@ -1176,10 +1196,6 @@ // is the jump from pred alive? bool branch_alive (jit_block *asucc) const; - llvm::BasicBlock *branch_llvm (size_t idx) const; - - llvm::BasicBlock *branch_llvm (jit_block *succ) const; - jit_block *successor (size_t i) const; size_t successor_count (void) const; @@ -1286,6 +1302,14 @@ 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; @@ -1321,7 +1345,6 @@ void do_visit_dom (size_t visit_count, func_type0 inorder, func_type1 postorder); - static const size_t NO_ID = static_cast<size_t> (-1); size_t mvisit_count; size_t mid; jit_block *idom; @@ -1338,7 +1361,9 @@ jit_phi_incomming : public jit_internal_node<jit_block, jit_phi_incomming> { public: - jit_phi_incomming (void) {} + 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 () { @@ -1348,8 +1373,15 @@ 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; }; // allow regular function pointers as well as pointers to members @@ -1368,6 +1400,16 @@ }; template <> +class jit_block_callback<int> +{ +public: + jit_block_callback (int) {} + + void operator() (jit_block&) + {} +}; + +template <> class jit_block_callback<void (jit_block::*)(void)> { public: @@ -1511,9 +1553,9 @@ jit_assign (jit_variable *adest, jit_value *asrc) : jit_assign_base (adest, asrc) {} - jit_instruction *src (void) const + jit_value *src (void) const { - return static_cast<jit_instruction *> (argument (0)); + return argument (0); } virtual bool infer (void) @@ -1552,7 +1594,7 @@ void add_incomming (jit_block *from, jit_value *value) { push_argument (value); - mincomming.push_back (jit_phi_incomming ()); + mincomming.push_back (jit_phi_incomming (this)); mincomming[mincomming.size () - 1].stash_value (from); } @@ -1563,8 +1605,7 @@ llvm::BasicBlock *incomming_llvm (size_t i) const { - jit_block *inc = incomming (i); - return inc->branch_llvm (parent ()); + return incomming (i)->to_llvm (); } virtual void construct_ssa (void) {} @@ -1596,6 +1637,8 @@ return os; } + llvm::PHINode *to_llvm (void) const; + JIT_VALUE_ACCEPT; private: std::vector<jit_phi_incomming> mincomming; @@ -1646,9 +1689,6 @@ size_t successor_index (const jit_block *asuccessor) const; - // create a merge block along the given edge - void create_merge (llvm::Function *function, jit_block *asuccessor); - std::ostream& print_successor (std::ostream& os, size_t idx = 0) const { if (alive (idx)) @@ -1771,6 +1811,11 @@ return mfunction.get_overload (argument_types ()); } + virtual bool needs_release (void) const + { + return type () && jit_typeinfo::get_release (type ()).function; + } + virtual std::ostream& print (std::ostream& os, size_t indent = 0) const { print_indent (os, indent); @@ -2093,10 +2138,26 @@ jit_call *ret = create<jit_call> (arg0, arg1, arg2); return create_checked_impl (ret); } -private: + typedef std::list<jit_block *> block_list; typedef block_list::iterator block_iterator; + void append (jit_block *ablock); + + void insert_before (block_iterator iter, jit_block *ablock); + + void insert_before (jit_block *loc, jit_block *ablock) + { + insert_before (loc->location (), ablock); + } + + void insert_after (block_iterator iter, jit_block *ablock); + + void insert_after (jit_block *loc, jit_block *ablock) + { + insert_after (loc->location (), ablock); + } +private: std::vector<std::pair<std::string, bool> > arguments; type_bound_vector bounds; @@ -2124,19 +2185,13 @@ typedef std::map<std::string, jit_variable *> vmap_t; vmap_t vmap; - void add_block (jit_block *ablock) - { - blocks.push_back (ablock); - ablock->stash_location (--blocks.end ()); - } - jit_call *create_checked_impl (jit_call *ret) { block->append (ret); jit_block *normal = create<jit_block> (block->name ()); block->append (create<jit_error_check> (ret, normal, final_block)); - add_block (normal); + append (normal); block = normal; return ret; @@ -2185,6 +2240,10 @@ void place_releases (void); + void simplify_phi (void); + + void simplify_phi (jit_phi& phi); + void print_blocks (const std::string& header) { std::cout << "-------------------- " << header << " --------------------\n"; @@ -2215,13 +2274,25 @@ void finish_breaks (jit_block *dest, const block_list& lst); - struct release_placer + typedef std::set<jit_instruction *> instr_set; + + // compute per block information about temporaries + class + compute_temp { - release_placer (jit_convert& aconvert) : convert (aconvert) {} - - jit_convert& convert; + 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<instr_set> mtemp_out; + bool changed; }; // this case is much simpler, just convert from the jit ir to llvm @@ -2246,7 +2317,7 @@ // name -> llvm argument std::map<std::string, llvm::Value *> arguments; - void finish_phi (jit_instruction *phi); + void finish_phi (jit_phi *phi); void visit (jit_value *jvalue) {