Mercurial > octave-nkf
changeset 14948:006570a76b90
Cleanup and optimization of JIT
| author | Max Brister <max@2bass.com> |
|---|---|
| date | Sun, 10 Jun 2012 12:16:29 -0500 |
| parents | d4bbe0ef7db5 |
| children | c57cfdb37f81 |
| files | src/pt-jit.cc src/pt-jit.h |
| diffstat | 2 files changed, 415 insertions(+), 309 deletions(-) [+] |
line wrap: on
line diff
--- a/src/pt-jit.cc Sat Jun 09 14:26:15 2012 -0500 +++ b/src/pt-jit.cc Sun Jun 10 12:16:29 2012 -0500 @@ -750,17 +750,15 @@ // -------------------- jit_value -------------------- jit_value::~jit_value (void) -{ - replace_with (0); -} +{} void jit_value::replace_with (jit_value *value) { - while (use_head) + while (first_use ()) { - jit_instruction *user = use_head->user (); - size_t idx = use_head->index (); + jit_instruction *user = first_use ()->user (); + size_t idx = first_use ()->index (); user->stash_argument (idx, value); } } @@ -805,13 +803,28 @@ } // -------------------- jit_block -------------------- +void +jit_block::replace_with (jit_value *value) +{ + assert (isa<jit_block> (value)); + jit_block *block = static_cast<jit_block *> (value); + + jit_value::replace_with (block); + + while (ILIST_T::first_use ()) + { + jit_phi_incomming *incomming = ILIST_T::first_use (); + incomming->stash_value (block); + } +} + jit_block * jit_block::maybe_merge () { - if (succ_count () == 1 && succ (0) != this - && (succ (0)->pred_count () == 1 || instructions.size () == 1)) + if (successor_count () == 1 && successor (0) != this + && (successor (0)->use_count () == 1 || instructions.size () == 1)) { - jit_block *to_merge = succ (0); + jit_block *to_merge = successor (0); merge (*to_merge); return to_merge; } @@ -825,11 +838,7 @@ // the merge block will contain a new terminator jit_terminator *old_term = terminator (); if (old_term) - { - old_term->remove (); - for (size_t i = 0; i < old_term->argument_count (); ++i) - old_term->stash_argument (i, 0); - } + old_term->remove (); bool was_empty = end () == begin (); iterator merge_begin = end (); @@ -851,7 +860,6 @@ } block.replace_with (this); - block.mark_dead (); } jit_instruction * @@ -906,6 +914,7 @@ jit_terminator * jit_block::terminator (void) const { + assert (this); if (instructions.empty ()) return 0; @@ -913,76 +922,36 @@ return dynamic_cast<jit_terminator *> (last); } -jit_block * -jit_block::pred (size_t idx) const -{ - // FIXME: Make this O(1) - assert (idx < use_count ()); - jit_use *use; - size_t i; - for (use = first_use (), i = 0; use && i < idx; ++i, use = use->next ()); - return use->user_parent (); -} - bool jit_block::branch_alive (jit_block *asucc) const { return terminator ()->alive (asucc); } -size_t -jit_block::pred_index (jit_block *apred) const -{ - for (size_t i = 0; i < pred_count (); ++i) - if (pred (i) == apred) - return i; - - fail ("No such predecessor"); -} - -void -jit_block::create_merge (llvm::Function *inside, jit_block *apred) -{ - mpred_llvm.resize (pred_count ()); - - size_t pred_idx = pred_index (apred); - if (! mpred_llvm[pred_idx] && apred->pred_count () > 1) - { - llvm::BasicBlock *amerge; - amerge = llvm::BasicBlock::Create (context, "phi_merge", inside, - to_llvm ()); - - // fix the predecessor jump if it has been created - jit_terminator *jterm = pred_terminator (pred_idx); - if (jterm->has_llvm ()) - { - llvm::Value *term = jterm->to_llvm (); - llvm::TerminatorInst *branch = llvm::cast<llvm::TerminatorInst> (term); - for (size_t i = 0; i < branch->getNumSuccessors (); ++i) - { - if (branch->getSuccessor (i) == to_llvm ()) - branch->setSuccessor (i, amerge); - } - } - - llvm::IRBuilder<> temp (amerge); - temp.CreateBr (to_llvm ()); - mpred_llvm[pred_idx] = amerge; - } -} - jit_block * -jit_block::succ (size_t i) const +jit_block::successor (size_t i) const { jit_terminator *term = terminator (); - return term->sucessor (i); + return term->successor (i); } size_t -jit_block::succ_count (void) const +jit_block::successor_count (void) const { jit_terminator *term = terminator (); - return term ? term->sucessor_count () : 0; + return term ? term->successor_count () : 0; +} + +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 * @@ -997,14 +966,14 @@ short_print (os); os << ":\n"; os << " mid: " << mid << std::endl; - os << " pred: "; - for (size_t i = 0; i < pred_count (); ++i) - os << *pred (i) << " "; + os << " predecessors: "; + for (jit_use *use = first_use (); use; use = use->next ()) + os << *use->user_parent () << " "; os << std::endl; - os << " succ: "; - for (size_t i = 0; i < succ_count (); ++i) - os << *succ (i) << " "; + os << " successors: "; + for (size_t i = 0; i < successor_count (); ++i) + os << *successor (i) << " "; os << std::endl; os << " idom: "; @@ -1032,11 +1001,11 @@ return; ++mvisit_count; - if (pred_count () >= 2) + if (use_count () >= 2) { - for (size_t i = 0; i < pred_count (); ++i) + for (jit_use *use = first_use (); use; use = use->next ()) { - jit_block *runner = pred (i); + jit_block *runner = use->user_parent (); while (runner != idom) { runner->mdf.insert (this); @@ -1045,8 +1014,8 @@ } } - for (size_t i = 0; i < succ_count (); ++i) - succ (i)->compute_df (visit_count); + for (size_t i = 0; i < successor_count (); ++i) + successor (i)->compute_df (visit_count); } bool @@ -1056,17 +1025,24 @@ return false; ++mvisit_count; - if (! pred_count ()) + if (! use_count ()) return false; bool changed = false; - for (size_t i = 0; i < pred_count (); ++i) - changed = pred (i)->update_idom (visit_count) || changed; - - jit_block *new_idom = pred (0); - for (size_t i = 1; i < pred_count (); ++i) + for (jit_use *use = first_use (); use; use = use->next ()) { - jit_block *pidom = pred (i)->idom; + jit_block *pred = use->user_parent (); + changed = pred->update_idom (visit_count) || changed; + } + + jit_use *use = first_use (); + jit_block *new_idom = use->user_parent (); + use = use->next (); + + for (; use; use = use->next ()) + { + jit_block *pred = use->user_parent (); + jit_block *pidom = pred->idom; if (pidom) new_idom = pidom->idom_intersect (new_idom); } @@ -1100,8 +1076,8 @@ if (idom != this) idom->dom_succ.push_back (this); - for (size_t i = 0; i < succ_count (); ++i) - succ (i)->create_dom_tree (visit_count); + for (size_t i = 0; i < successor_count (); ++i) + successor (i)->create_dom_tree (visit_count); } jit_block * @@ -1128,15 +1104,20 @@ { jit_block *p = parent (); size_t new_idx = 0; + jit_value *unique = argument (1); + for (size_t i = 0; i < argument_count (); ++i) { jit_block *inc = incomming (i); if (inc->branch_alive (p)) { + if (unique != argument (i)) + unique = 0; + if (new_idx != i) { stash_argument (new_idx, argument (i)); - mincomming[new_idx] = mincomming[i]; + mincomming[new_idx].stash_value (inc); } ++new_idx; @@ -1150,9 +1131,9 @@ } assert (argument_count () > 0); - if (argument_count () == 1) + if (unique) { - replace_with (argument (0)); + replace_with (unique); return true; } @@ -1169,7 +1150,7 @@ jit_type *infered = 0; for (size_t i = 0; i < argument_count (); ++i) { - jit_block *inc = mincomming[i]; + jit_block *inc = incomming (i); if (inc->branch_alive (p)) infered = jit_typeinfo::join (infered, argument_type (i)); } @@ -1184,17 +1165,42 @@ } // -------------------- jit_terminator -------------------- -bool -jit_terminator::alive (const jit_block *asucessor) const +size_t +jit_terminator::successor_index (const jit_block *asuccessor) const { - size_t scount = sucessor_count (); + size_t scount = successor_count (); for (size_t i = 0; i < scount; ++i) - if (sucessor (i) == asucessor) - return malive[i]; + if (successor (i) == asuccessor) + return i; 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) { @@ -1207,12 +1213,18 @@ { changed = true; malive[i] = true; - sucessor (i)->mark_alive (); + successor (i)->mark_alive (); } return changed; } +llvm::TerminatorInst * +jit_terminator::to_llvm (void) const +{ + return llvm::cast<llvm::TerminatorInst> (jit_value::to_llvm ()); +} + // -------------------- jit_call -------------------- bool jit_call::infer (void) @@ -1251,7 +1263,7 @@ entry_block = create<jit_block> ("body"); final_block = create<jit_block> ("final"); - blocks.push_back (entry_block); + add_block (entry_block); entry_block->mark_alive (); block = entry_block; visit (tee); @@ -1262,7 +1274,7 @@ assert (continues.empty ()); block->append (create<jit_break> (final_block)); - blocks.push_back (final_block); + add_block (final_block); for (vmap_t::iterator iter = vmap.begin (); iter != vmap.end (); ++iter) @@ -1363,7 +1375,7 @@ jit_block *normal = create<jit_block> (block->name ()); block->append (create<jit_check_error> (call, normal, final_block)); - blocks.push_back (normal); + add_block (normal); block = normal; result = call; } @@ -1454,7 +1466,7 @@ vmap[iter_name] = iterator; jit_block *body = create<jit_block> ("for_body"); - blocks.push_back (body); + add_block (body); jit_block *tail = create<jit_block> ("for_tail"); @@ -1483,14 +1495,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); - blocks.push_back (tail); + add_block (tail); block = tail; return; } // check our condition, continues jump to this block jit_block *check_block = create<jit_block> ("for_check"); - blocks.push_back (check_block); + add_block (check_block); if (! breaking) block->append (create<jit_break> (check_block)); @@ -1507,7 +1519,7 @@ block->append (create<jit_cond_break> (check, body, tail)); // breaks will go to our tail - blocks.push_back (tail); + add_block (tail); finish_breaks (tail, breaks); block = tail; } @@ -1608,7 +1620,7 @@ assert (block); if (i) // the first block is prev_block, so it has already been added - blocks.push_back (entry_blocks[i]); + add_block (entry_blocks[i]); if (! tic->is_else_clause ()) { @@ -1618,12 +1630,12 @@ block->append (check); jit_block *next = create<jit_block> (block->name ()); - blocks.push_back (next); + add_block (next); block->append (create<jit_check_error> (check, next, final_block)); block = next; jit_block *body = create<jit_block> (i == 0 ? "if_body" : "ifelse_body"); - blocks.push_back (body); + add_block (body); jit_instruction *br = create<jit_cond_break> (check, body, entry_blocks[i + 1]); @@ -1646,7 +1658,7 @@ if (num_incomming || ! last_else) { - blocks.push_back (tail); + add_block (tail); block = tail; } else @@ -1898,11 +1910,11 @@ void jit_convert::append_users_term (jit_terminator *term) { - for (size_t i = 0; i < term->sucessor_count (); ++i) + for (size_t i = 0; i < term->successor_count (); ++i) { if (term->alive (i)) { - jit_block *succ = term->sucessor (i); + jit_block *succ = term->successor (i); for (jit_block::iterator iter = succ->begin (); iter != succ->end () && isa<jit_phi> (*iter); ++iter) push_worklist (*iter); @@ -1917,27 +1929,27 @@ void jit_convert::merge_blocks (void) { + std::vector<jit_block *> dead; for (block_list::iterator iter = blocks.begin (); iter != blocks.end (); ++iter) { jit_block *b = *iter; jit_block *merged = b->maybe_merge (); - if (merged == final_block) - final_block = b; - - if (merged == entry_block) - entry_block = b; + if (merged) + { + if (merged == final_block) + final_block = b; + + if (merged == entry_block) + entry_block = b; + + dead.push_back (merged); + } } - for (block_list::iterator iter = blocks.begin (); iter != blocks.end ();) - { - jit_block *b = *iter; - if (b->dead ()) - iter = blocks.erase (iter); - else - ++iter; - } + for (size_t i = 0; i < dead.size (); ++i) + blocks.erase (dead[i]->location ()); } void @@ -1969,7 +1981,7 @@ if (! added_phi.count (dblock)) { jit_phi *phi = create<jit_phi> (iter->second, - dblock->pred_count ()); + dblock->use_count ()); dblock->prepend (phi); added_phi.insert (dblock); } @@ -2008,15 +2020,15 @@ instr->push_variable (); } - // finish phi nodes of sucessors - for (size_t i = 0; i < block.succ_count (); ++i) + // finish phi nodes of successors + for (size_t i = 0; i < block.successor_count (); ++i) { - jit_block *finish = block.succ (i); + jit_block *finish = block.successor (i); for (jit_block::iterator iter = finish->begin (); iter != finish->end () && isa<jit_phi> (*iter);) { - jit_phi *phi = dynamic_cast<jit_phi *> (*iter); + jit_phi *phi = static_cast<jit_phi *> (*iter); jit_variable *var = phi->dest (); if (var->has_top ()) { @@ -2063,9 +2075,9 @@ // FIXME: A special case for jit_check_error, if we generalize to // we will need to change! jit_terminator *term = b->terminator (); - if (term && term->sucessor_count () == 2 && ! term->alive (1)) + if (term && term->successor_count () == 2 && ! term->alive (0)) { - jit_block *succ = term->sucessor (0); + jit_block *succ = term->successor (1); term->remove (); jit_break *abreak = b->append (create<jit_break> (succ)); abreak->infer (); @@ -2074,7 +2086,12 @@ ++biter; } else - biter = blocks.erase (biter); + { + jit_terminator *term = b->terminator (); + if (term) + term->remove (); + biter = blocks.erase (biter); + } } } @@ -2335,7 +2352,7 @@ void jit_convert::convert_llvm::visit (jit_break& b) { - b.stash_llvm (builder.CreateBr (b.sucessor_llvm ())); + b.stash_llvm (builder.CreateBr (b.successor_llvm ())); } void @@ -2343,7 +2360,7 @@ { llvm::Value *cond = cb.cond_llvm (); llvm::Value *br; - br = builder.CreateCondBr (cond, cb.sucessor_llvm (0), cb.sucessor_llvm (1)); + br = builder.CreateCondBr (cond, cb.successor_llvm (0), cb.successor_llvm (1)); cb.stash_llvm (br); } @@ -2398,10 +2415,14 @@ builder.Insert (node); phi.stash_llvm (node); - jit_block *parent = phi.parent (); + jit_block *pblock = phi.parent (); for (size_t i = 0; i < phi.argument_count (); ++i) if (phi.argument_type (i) != phi.type ()) - parent->create_merge (function, phi.incomming (i)); + { + jit_block *inc = phi.incomming (i); + jit_terminator *term = inc->terminator (); + term->create_merge (function, pblock); + } } void @@ -2414,8 +2435,8 @@ jit_convert::convert_llvm::visit (jit_check_error& check) { llvm::Value *cond = jit_typeinfo::insert_error_check (); - llvm::Value *br = builder.CreateCondBr (cond, check.sucessor_llvm (1), - check.sucessor_llvm (0)); + llvm::Value *br = builder.CreateCondBr (cond, check.successor_llvm (0), + check.successor_llvm (1)); check.stash_llvm (br); }
--- a/src/pt-jit.h Sat Jun 09 14:26:15 2012 -0500 +++ b/src/pt-jit.h Sun Jun 10 12:16:29 2012 -0500 @@ -85,12 +85,111 @@ class Type; class Twine; class GlobalVariable; + class TerminatorInst; } class octave_base_value; class octave_value; class tree; +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> @@ -592,12 +691,10 @@ class jit_use; class -jit_value +jit_value : public jit_internal_list<jit_value, jit_use> { - friend class jit_use; public: - jit_value (void) : llvm_value (0), ty (0), use_head (0), use_tail (0), - myuse_count (0), mlast_use (0), + jit_value (void) : llvm_value (0), ty (0), mlast_use (0), min_worklist (false) {} virtual ~jit_value (void); @@ -613,7 +710,7 @@ } // replace all uses with - void replace_with (jit_value *value); + virtual void replace_with (jit_value *value); jit_type *type (void) const { return ty; } @@ -629,10 +726,6 @@ void stash_type (jit_type *new_ty) { ty = new_ty; } - jit_use *first_use (void) const { return use_head; } - - size_t use_count (void) const { return myuse_count; } - std::string print_string (void) { std::stringstream ss; @@ -681,9 +774,6 @@ llvm::Value *llvm_value; private: jit_type *ty; - jit_use *use_head; - jit_use *use_tail; - size_t myuse_count; jit_instruction *mlast_use; bool min_worklist; }; @@ -691,28 +781,23 @@ std::ostream& operator<< (std::ostream& os, const jit_value& value); class -jit_use +jit_use : public jit_internal_node<jit_value, jit_use> { public: - jit_use (void) : mvalue (0), mnext (0), mprev (0), muser (0), mindex (0) {} + 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) : mvalue (0), mnext (0), mprev (0), muser (0), - mindex (0) + jit_use (const jit_use& use) : muser (0), mindex (0) { *this = use; } - ~jit_use (void) { remove (); } - jit_use& operator= (const jit_use& use) { stash_value (use.value (), use.user (), use.index ()); return *this; } - jit_value *value (void) const { return mvalue; } - size_t index (void) const { return mindex; } jit_instruction *user (void) const { return muser; } @@ -724,57 +809,11 @@ void stash_value (jit_value *avalue, jit_instruction *auser = 0, size_t aindex = -1) { - remove (); - - mvalue = avalue; - - if (mvalue) - { - if (mvalue->use_head) - { - mvalue->use_tail->mnext = this; - mprev = mvalue->use_tail; - } - else - mvalue->use_head = this; - - mvalue->use_tail = this; - ++mvalue->myuse_count; - } - + jit_internal_node::stash_value (avalue); mindex = aindex; muser = auser; } - - jit_use *next (void) const { return mnext; } - - jit_use *prev (void) const { return mprev; } private: - void remove (void) - { - if (mvalue) - { - if (this == mvalue->use_head) - mvalue->use_head = mnext; - - if (this == mvalue->use_tail) - mvalue->use_tail = mprev; - - if (mprev) - mprev->mnext = mnext; - - if (mnext) - mnext->mprev = mprev; - - mnext = mprev = 0; - --mvalue->myuse_count; - mvalue = 0; - } - } - - jit_value *mvalue; - jit_use *mnext; - jit_use *mprev; jit_instruction *muser; size_t mindex; }; @@ -787,13 +826,11 @@ jit_instruction (void) : mid (next_id ()), mparent (0) {} - jit_instruction (size_t nargs, jit_value *adefault = 0) - : already_infered (nargs, reinterpret_cast<jit_type *>(0)), arguments (nargs), - mid (next_id ()), mparent (0) + jit_instruction (size_t nargs) + : already_infered (nargs, reinterpret_cast<jit_type *>(0)), + mid (next_id ()), mparent (0) { - if (adefault) - for (size_t i = 0; i < nargs; ++i) - stash_argument (i, adefault); + arguments.reserve (nargs); } jit_instruction (jit_value *arg0) @@ -871,6 +908,13 @@ arguments[i].stash_value (arg, this, i); } + void push_argument (jit_value *arg) + { + arguments.push_back (jit_use ()); + stash_argument (arguments.size () - 1, arg); + already_infered.push_back (0); + } + size_t argument_count (void) const { return arguments.size (); @@ -880,6 +924,7 @@ { size_t old = arguments.size (); arguments.resize (acount); + already_infered.resize (acount); if (adefault) for (size_t i = old; i < acount; ++i) @@ -972,9 +1017,12 @@ T mvalue; }; +class jit_phi_incomming; + class -jit_block : public jit_value +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; @@ -984,21 +1032,22 @@ typedef df_set::const_iterator df_iterator; jit_block (const std::string& aname) : mvisit_count (0), mid (NO_ID), idom (0), - mname (aname), mdead (false), - malive (false) + mname (aname), malive (false) {} + virtual void replace_with (jit_value *value); + + // 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; } - // dead blocks have already been removed from the CFG - bool dead (void) const { return mdead; } - - void mark_dead (void) { mdead = true; } - - // If we can merge with a sucessor, do so and return the now empty block + // 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 @@ -1031,45 +1080,16 @@ jit_terminator *terminator (void) const; - jit_block *pred (size_t idx) const; - - jit_terminator *pred_terminator (size_t idx) const - { - return pred (idx)->terminator (); - } - // is the jump from pred alive? bool branch_alive (jit_block *asucc) const; - std::ostream& print_pred (std::ostream& os, size_t idx) const - { - return pred (idx)->short_print (os); - } - - // takes into account for the addition of phi merges - llvm::BasicBlock *pred_llvm (size_t idx) const - { - if (mpred_llvm.size () < pred_count ()) - mpred_llvm.resize (pred_count ()); - - return mpred_llvm[idx] ? mpred_llvm[idx] : pred (idx)->to_llvm (); - } - - llvm::BasicBlock *pred_llvm (jit_block *apred) const - { - return pred_llvm (pred_index (apred)); - } - - size_t pred_index (jit_block *apred) const; - - // create llvm phi merge blocks for all predecessors (if required) - void create_merge (llvm::Function *inside, jit_block *apred); - - size_t pred_count (void) const { return use_count (); } - - jit_block *succ (size_t i) const; - - size_t succ_count (void) 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; iterator begin (void) { return instructions.begin (); } @@ -1108,8 +1128,11 @@ return; ++mvisit_count; - for (size_t i = 0; i < pred_count (); ++i) - pred (i)->label (visit_count, number); + for (jit_use *use = first_use (); use; use = use->next ()) + { + jit_block *pred = use->user_parent (); + pred->label (visit_count, number); + } mid = number++; } @@ -1153,10 +1176,11 @@ { print_indent (os, indent); short_print (os) << ": %pred = "; - for (size_t i = 0; i < pred_count (); ++i) + for (jit_use *use = first_use (); use; use = use->next ()) { - print_pred (os, i); - if (i + 1 < pred_count ()) + jit_block *pred = use->user_parent (); + os << *pred; + if (use->next ()) os << ", "; } os << std::endl; @@ -1182,7 +1206,13 @@ llvm::BasicBlock *to_llvm (void) const; - JIT_VALUE_ACCEPT (block) + std::list<jit_block *>::iterator location (void) const + { return mlocation; } + + void stash_location (std::list<jit_block *>::iterator alocation) + { mlocation = alocation; } + + JIT_VALUE_ACCEPT (block); private: void internal_append (jit_instruction *instr); @@ -1205,9 +1235,31 @@ std::vector<jit_block *> dom_succ; std::string mname; instruction_list instructions; - mutable std::vector<llvm::BasicBlock *> mpred_llvm; - bool mdead; bool malive; + std::list<jit_block *>::iterator mlocation; + + jit_phi_incomming *use_head; + jit_phi_incomming *use_tail; + size_t myuse_count; +}; + +// 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) {} + + 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 ()); + return *this; + } }; // allow regular function pointers as well as pointers to members @@ -1383,7 +1435,8 @@ jit_phi : public jit_assign_base { public: - jit_phi (jit_variable *adest, size_t npred) : jit_assign_base (adest, npred) + jit_phi (jit_variable *adest, size_t npred) + : jit_assign_base (adest, npred) { mincomming.reserve (npred); } @@ -1393,20 +1446,20 @@ void add_incomming (jit_block *from, jit_value *value) { - stash_argument (mincomming.size (), value); - mincomming.push_back (from); + push_argument (value); + mincomming.push_back (jit_phi_incomming ()); + mincomming[mincomming.size () - 1].stash_value (from); } jit_block *incomming (size_t i) const { - return mincomming[i]; + return mincomming[i].value (); } llvm::BasicBlock *incomming_llvm (size_t i) const { jit_block *inc = incomming (i); - jit_block *p = parent (); - return p->pred_llvm (inc); + return inc->branch_llvm (parent ()); } virtual bool infer (void); @@ -1420,15 +1473,14 @@ std::string indent_str (ss_str.size (), ' '); os << ss_str; - jit_block *pblock = parent (); for (size_t i = 0; i < argument_count (); ++i) { if (i > 0) os << indent_str; os << "| "; - pblock->print_pred (os, i) << " -> "; - print_argument (os, i); + os << *incomming (i) << " -> "; + os << *argument (i); if (i + 1 < argument_count ()) os << std::endl; @@ -1448,60 +1500,87 @@ JIT_VALUE_ACCEPT (phi); private: - std::vector<jit_block *> mincomming; + std::vector<jit_phi_incomming> mincomming; }; class jit_terminator : public jit_instruction { public: - jit_terminator (size_t asucessor_count, jit_value *arg0) - : jit_instruction (arg0), malive (asucessor_count, false) {} - - jit_terminator (size_t asucessor_count, jit_value *arg0, jit_value *arg1) - : jit_instruction (arg0, arg1), malive (asucessor_count, false) {} - - jit_terminator (size_t asucessor_count, jit_value *arg0, jit_value *arg1, + jit_terminator (size_t asuccessor_count, jit_value *arg0) + : jit_instruction (arg0), malive (asuccessor_count, false), + mbranch_llvm (asuccessor_count, 0) {} + + jit_terminator (size_t asuccessor_count, jit_value *arg0, jit_value *arg1) + : jit_instruction (arg0, arg1), malive (asuccessor_count, false), + mbranch_llvm (asuccessor_count, 0) {} + + jit_terminator (size_t asuccessor_count, jit_value *arg0, jit_value *arg1, jit_value *arg2) - : jit_instruction (arg0, arg1, arg2), malive (asucessor_count, false) {} - - jit_block *sucessor (size_t idx = 0) const + : jit_instruction (arg0, arg1, arg2), malive (asuccessor_count, false), + mbranch_llvm (asuccessor_count, 0) {} + + jit_block *successor (size_t idx = 0) const { return static_cast<jit_block *> (argument (idx)); } - // return either our sucessors block directly, or the phi merge block - // between us and our sucessor - llvm::BasicBlock *sucessor_llvm (size_t idx = 0) const + // the llvm block between our parent and the given successor + llvm::BasicBlock *branch_llvm (size_t idx = 0) const + { + return mbranch_llvm[idx] ? mbranch_llvm[idx] : parent ()->to_llvm (); + } + + llvm::BasicBlock *branch_llvm (int idx) const + { + return branch_llvm (static_cast<size_t> (idx)); + } + + llvm::BasicBlock *branch_llvm (const jit_block *asuccessor) const { - jit_block *succ = sucessor (idx); - llvm::BasicBlock *pllvm = parent_llvm (); - llvm::BasicBlock *spred_llvm = succ->pred_llvm (parent ()); - llvm::BasicBlock *succ_llvm = succ->to_llvm (); - return pllvm == spred_llvm ? succ_llvm : spred_llvm; + return branch_llvm (successor_index (asuccessor)); + } + + llvm::BasicBlock *successor_llvm (size_t idx = 0) const + { + return mbranch_llvm[idx] ? mbranch_llvm[idx] : successor (idx)->to_llvm (); } - std::ostream& print_sucessor (std::ostream& os, size_t idx = 0) const + 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)) os << "[live] "; else os << "[dead] "; - return sucessor (idx)->short_print (os); + return successor (idx)->short_print (os); } - // Check if the jump to sucessor is live - bool alive (const jit_block *asucessor) const; + // 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]; } - size_t sucessor_count (void) const { return malive.size (); } + 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; + std::vector<llvm::BasicBlock *> mbranch_llvm; }; class @@ -1510,12 +1589,12 @@ public: jit_break (jit_block *succ) : jit_terminator (1, succ) {} - virtual size_t sucessor_count (void) const { return 1; } + 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) << "break: "; - return print_sucessor (os); + return print_successor (os); } JIT_VALUE_ACCEPT (break) @@ -1540,14 +1619,14 @@ return cond ()->to_llvm (); } - virtual size_t sucessor_count (void) const { return 2; } + 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_break: "; print_cond (os) << ", "; - print_sucessor (os, 0) << ", "; - return print_sucessor (os, 1); + print_successor (os, 0) << ", "; + return print_successor (os, 1); } JIT_VALUE_ACCEPT (cond_break) @@ -1625,7 +1704,7 @@ { public: jit_check_error (jit_call *acheck_for, jit_block *normal, jit_block *error) - : jit_terminator (2, normal, error, acheck_for) {} + : jit_terminator (2, error, normal, acheck_for) {} jit_call *check_for (void) const { @@ -1635,15 +1714,15 @@ virtual std::ostream& print (std::ostream& os, size_t indent = 0) const { print_indent (os, indent) << "error_check " << *check_for () << ", "; - print_sucessor (os, 0) << ", "; - return print_sucessor (os, 1); + print_successor (os, 1) << ", "; + return print_successor (os, 0); } JIT_VALUE_ACCEPT (jit_check_error) protected: virtual bool check_alive (size_t idx) const { - return idx == 0 ? true : check_for ()->can_error (); + return idx == 1 ? true : check_for ()->can_error (); } }; @@ -1931,6 +2010,12 @@ 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_variable *get_variable (const std::string& vname); jit_value *do_assign (const std::string& lhs, jit_value *rhs, bool print);