diff options
Diffstat (limited to 'src/mir/optimise.cpp')
| -rw-r--r-- | src/mir/optimise.cpp | 663 |
1 files changed, 188 insertions, 475 deletions
diff --git a/src/mir/optimise.cpp b/src/mir/optimise.cpp index 2e823821..81574afd 100644 --- a/src/mir/optimise.cpp +++ b/src/mir/optimise.cpp @@ -17,6 +17,13 @@ #include <iomanip> #include <trans/target.hpp> +#define DUMP_BEFORE_ALL 0 +#define DUMP_BEFORE_CONSTPROPAGATE 0 +#define CHECK_AFTER_PASS 0 + +#define DUMP_AFTER_DONE 0 +#define CHECK_AFTER_DONE 1 + namespace { ::MIR::BasicBlockId get_new_target(const ::MIR::TypeResolve& state, ::MIR::BasicBlockId bb) { @@ -185,6 +192,8 @@ namespace { (Drop, // Well, it mutates... rv |= visit_mir_lvalue_mut(e.slot, ValUsage::Write, cb); + ), + (ScopeEnd, ) ) return rv; @@ -436,26 +445,32 @@ void MIR_Optimise(const StaticTraitResolve& resolve, const ::HIR::ItemPath& path // >> Combine Duplicate Blocks change_happened |= MIR_Optimise_UnifyBlocks(state, fcn); - #if 0 if( change_happened ) { - //MIR_Dump_Fcn(::std::cout, fcn); + #if DUMP_AFTER_PASS + if( debug_enabled() ) { + MIR_Dump_Fcn(::std::cout, fcn); + } + #endif + #if CHECK_AFTER_PASS MIR_Validate(resolve, path, fcn, args, ret_type); + #endif } - #endif MIR_Optimise_GarbageCollect_Partial(state, fcn); pass_num += 1; } while( change_happened ); - #if 1 + #if DUMP_AFTER_DONE if( debug_enabled() ) { MIR_Dump_Fcn(::std::cout, fcn); } #endif + #if CHECK_AFTER_DONE // DEFENCE: Run validation _before_ GC (so validation errors refer to the pre-gc numbers) MIR_Validate(resolve, path, fcn, args, ret_type); + #endif // GC pass on blocks and variables // - Find unused blocks, then delete and rewrite all references. MIR_Optimise_GarbageCollect(state, fcn); @@ -469,6 +484,31 @@ bool MIR_Optimise_BlockSimplify(::MIR::TypeResolve& state, ::MIR::Function& fcn) // >> Replace targets that point to a block that is just a goto for(auto& block : fcn.blocks) { + // Unify sequential ScopeEnd statements + if( block.statements.size() > 1 ) + { + for(auto it = block.statements.begin() + 1; it != block.statements.end(); ) + { + if( (it-1)->is_ScopeEnd() && it->is_ScopeEnd() ) + { + auto& dst = (it-1)->as_ScopeEnd(); + const auto& src = it->as_ScopeEnd(); + DEBUG("Unify " << *(it-1) << " and " << *it); + for(auto v : src.vars) + dst.vars.push_back(v); + for(auto v : src.tmps) + dst.tmps.push_back(v); + ::std::sort(dst.vars.begin(), dst.vars.end()); + ::std::sort(dst.tmps.begin(), dst.tmps.end()); + it = block.statements.erase(it); + } + else + { + ++ it; + } + } + } + TU_MATCHA( (block.terminator), (e), (Incomplete, ), @@ -589,7 +629,7 @@ bool MIR_Optimise_BlockSimplify(::MIR::TypeResolve& state, ::MIR::Function& fcn) bool MIR_Optimise_Inlining(::MIR::TypeResolve& state, ::MIR::Function& fcn) { TRACE_FUNCTION; - + struct H { static bool can_inline(const ::HIR::Path& path, const ::MIR::Function& fcn) @@ -686,22 +726,21 @@ bool MIR_Optimise_Inlining(::MIR::TypeResolve& state, ::MIR::Function& fcn) return rv; } - ::MIR::BasicBlock clone_bb(const ::MIR::BasicBlock& src) const + ::MIR::BasicBlock clone_bb(const ::MIR::BasicBlock& src, unsigned src_idx, unsigned new_idx) const { ::MIR::BasicBlock rv; rv.statements.reserve( src.statements.size() ); for(const auto& stmt : src.statements) { + DEBUG("BB" << src_idx << "->BB" << new_idx << "/" << rv.statements.size() << ": " << stmt); TU_MATCHA( (stmt), (se), (Assign, - DEBUG(se.dst << " = " << se.src); rv.statements.push_back( ::MIR::Statement::make_Assign({ this->clone_lval(se.dst), this->clone_rval(se.src) }) ); ), (Asm, - DEBUG("asm!"); rv.statements.push_back( ::MIR::Statement::make_Asm({ se.tpl, this->clone_name_lval_vec(se.outputs), @@ -711,7 +750,6 @@ bool MIR_Optimise_Inlining(::MIR::TypeResolve& state, ::MIR::Function& fcn) }) ); ), (SetDropFlag, - DEBUG("df" << se.idx << " = "); rv.statements.push_back( ::MIR::Statement::make_SetDropFlag({ this->df_base + se.idx, se.new_val, @@ -719,17 +757,27 @@ bool MIR_Optimise_Inlining(::MIR::TypeResolve& state, ::MIR::Function& fcn) }) ); ), (Drop, - DEBUG("drop " << se.slot); rv.statements.push_back( ::MIR::Statement::make_Drop({ se.kind, this->clone_lval(se.slot), se.flag_idx == ~0u ? ~0u : this->df_base + se.flag_idx }) ); + ), + (ScopeEnd, + ::MIR::Statement::Data_ScopeEnd new_se; + new_se.vars.reserve(se.vars.size()); + for(auto idx : se.vars) + new_se.vars.push_back(this->var_base + idx); + new_se.tmps.reserve(se.tmps.size()); + for(auto idx : se.tmps) + new_se.tmps.push_back(this->tmp_base + idx); + rv.statements.push_back(::MIR::Statement( mv$(new_se) )); ) ) } - DEBUG(src.terminator); + DEBUG("BB" << src_idx << "->BB" << new_idx << "/" << rv.statements.size() << ": " << src.terminator); rv.terminator = this->clone_term(src.terminator); + DEBUG("-> " << rv.terminator); return rv; } ::MIR::Terminator clone_term(const ::MIR::Terminator& src) const @@ -981,7 +1029,7 @@ bool MIR_Optimise_Inlining(::MIR::TypeResolve& state, ::MIR::Function& fcn) new_blocks.reserve( called_mir->blocks.size() ); for(const auto& bb : called_mir->blocks) { - new_blocks.push_back( cloner.clone_bb(bb) ); + new_blocks.push_back( cloner.clone_bb(bb, (&bb - called_mir->blocks.data()), fcn.blocks.size() + new_blocks.size()) ); } // > Append new temporaries for(auto& val : cloner.const_assignments) @@ -1006,6 +1054,7 @@ bool MIR_Optimise_Inlining(::MIR::TypeResolve& state, ::MIR::Function& fcn) return inline_happened; } + // -------------------------------------------------------------------- // If two temporaries don't overlap in lifetime (blocks in which they're valid), unify the two // -------------------------------------------------------------------- @@ -1036,444 +1085,9 @@ bool MIR_Optimise_UnifyTemporaries(::MIR::TypeResolve& state, ::MIR::Function& f return false; } - class VarLifetime - { - ::std::vector<bool> statements; - - public: - VarLifetime(::std::vector<bool> stmts): - statements( mv$(stmts) ) - {} - - // true if this value is used at any point - bool is_used() const { - for(auto v : statements) - if( v ) - return true; - return false; - } - bool overlaps(const VarLifetime& x) const { - assert(statements.size() == x.statements.size()); - for(unsigned int i = 0; i < statements.size(); i ++) - { - if( statements[i] && x.statements[i] ) - return true; - } - return false; - } - void unify(const VarLifetime& x) { - assert(statements.size() == x.statements.size()); - for(unsigned int i = 0; i < statements.size(); i ++) - { - if( x.statements[i] ) - statements[i] = true; - } - } - }; - //::std::vector<VarLifetime> var_lifetimes; - ::std::vector<VarLifetime> tmp_lifetimes; - - - // New algorithm notes: - // --- - // The lifetime of a value starts when it is written, and ends the last time it is read - // - When a variable is read, end any existing lifetime and start a new one. - // - When the value is read, update the end of its lifetime. - // --- - // A lifetime is a range in the call graph (with a start and end, including list of blocks) - // - Representation: Bitmap with a bit per statement. - // - Record the current block path in general state, along with known active lifetimes - - // TODO: Move all this code to a helper to other passes can use it. - { - // Scan through all possible paths in the graph (with loopback detection using a memory of the path) - // - If a loop is detected, determine if there were changes to the lifetime set during that pass - // > Changes are noticed by recording in the state structure when it triggers a change in the lifetime - // map. - struct Position - { - size_t path_index = 0; // index into the block path. - unsigned int stmt_idx = 0; - - bool operator==(const Position& x) const { - return path_index == x.path_index && stmt_idx == x.stmt_idx; - } - }; - struct ProtoLifetime - { - Position start; - Position end; - - bool is_empty() const { - return start == end; - } - }; - static unsigned NEXT_INDEX = 0; - struct State - { - unsigned int index = 0; - ::std::vector<unsigned int> block_path; - ::std::vector<unsigned int> block_change_idx; - unsigned int cur_change_idx = 0; - - // if read, update. If set, save and update - ::std::vector<ProtoLifetime> tmp_ends; - //::std::vector<Position> var_ends; - - State clone() const { - auto rv = *this; - rv.index = ++NEXT_INDEX; - return rv; - } - }; - NEXT_INDEX = 0; - - struct ValueLifetime - { - ::std::vector<bool> stmt_bitmap; - ValueLifetime(size_t stmt_count): - stmt_bitmap(stmt_count) - {} - }; - - size_t statement_count = 0; - ::std::vector<size_t> block_offsets; - block_offsets.reserve( fcn.blocks.size() ); - for(const auto& bb : fcn.blocks) - { - block_offsets.push_back(statement_count); - statement_count += bb.statements.size() + 1; // +1 for the terminator - } - - ::std::vector<ValueLifetime> temporary_lifetimes( fcn.temporaries.size(), ValueLifetime(statement_count) ); - - struct BlockSeenLifetimes { - const ::std::vector<size_t>& block_offsets; - ::std::vector< ::std::vector<unsigned int> > tmp; - - BlockSeenLifetimes(const ::std::vector<size_t>& block_offsets, const ::MIR::Function& fcn): - block_offsets( block_offsets ), - tmp( fcn.temporaries.size() ) - {} - - bool has_state() const - { - return ::std::any_of(tmp.begin(), tmp.end(), [&](const auto& x){ return !x.empty(); }); - } - - bool try_merge(const State& val_state) const - { - for(size_t i = 0; i < val_state.tmp_ends.size(); i++) - { - const auto& lft = val_state.tmp_ends[i]; - const auto& seen = this->tmp[i]; - if(lft.is_empty()) continue ; - auto end_idx = block_offsets.at( val_state.block_path.at(lft.end.path_index) ) + lft.end.stmt_idx; - - auto it = ::std::find(seen.begin(), seen.end(), end_idx); - if( it == seen.end() ) - { - return true; - } - } - return false; - } - bool merge(const State& val_state) - { - bool rv = false; - for(size_t i = 0; i < val_state.tmp_ends.size(); i++) - { - const auto& lft = val_state.tmp_ends[i]; - auto& seen = this->tmp[i]; - if(lft.is_empty()) continue ; - auto end_idx = block_offsets.at( val_state.block_path.at(lft.end.path_index) ) + lft.end.stmt_idx; - - auto it = ::std::find(seen.begin(), seen.end(), end_idx); - if( it == seen.end() ) - { - rv = true; - seen.push_back( end_idx ); - } - } - return rv; - } - }; - ::std::vector<BlockSeenLifetimes> block_seen_lifetimes( fcn.blocks.size(), BlockSeenLifetimes(block_offsets, fcn) ); - - State init_state; - init_state.tmp_ends.resize( fcn.temporaries.size(), ProtoLifetime() ); - - ::std::vector<::std::pair<unsigned int, State>> todo_queue; - todo_queue.push_back(::std::make_pair( 0, mv$(init_state) )); - - while(!todo_queue.empty()) - { - auto bb_idx = todo_queue.back().first; - auto val_state = mv$(todo_queue.back().second); - todo_queue.pop_back(); - state.set_cur_stmt(bb_idx, 0); - - // Fill alive time in the bitmap - // TODO: Maybe also store the range (as a sequence of {block,start,end}) - auto add_lifetime_s = [&](State& val_state, const ::MIR::LValue& lv, const Position& start, const Position& end) { - assert(start.path_index <= end.path_index); - assert(start.path_index < end.path_index || start.stmt_idx <= end.stmt_idx); - if(start.path_index == end.path_index && start.stmt_idx == end.stmt_idx) - return; - //DEBUG("[add_lifetime] " << lv << " (" << start.path_index << "," << start.stmt_idx << ") -- (" << end.path_index << "," << end.stmt_idx << ")"); - ValueLifetime* lft; - if(const auto* e = lv.opt_Temporary()) - { - lft = &temporary_lifetimes[e->idx]; - } - else - { - MIR_TODO(state, "[add_lifetime] " << lv); - return; - } - - // Fill lifetime map for this temporary in the indicated range - bool did_set = false; - unsigned int j = start.stmt_idx; - unsigned int i = start.path_index; - while( i <= end.path_index ) - { - auto bb_idx = val_state.block_path.at(i); - const auto& bb = fcn.blocks[bb_idx]; - MIR_ASSERT(state, j <= bb.statements.size(), ""); - MIR_ASSERT(state, bb_idx < block_offsets.size(), ""); - - auto block_base = block_offsets.at(bb_idx); - auto idx = block_base + j; - if( !lft->stmt_bitmap.at(idx) ) - { - lft->stmt_bitmap[idx] = true; - did_set = true; - } - - if( i == end.path_index && j == end.stmt_idx ) - break; - - // If the current index is the terminator (one after the size) - if(j == bb.statements.size()) - { - j = 0; - i++; - } - else - { - j ++; - } - } - - // - If the above set a new bit, increment `val_state.cur_change_idx` - if( did_set ) - { - DEBUG("[add_lifetime] " << lv << " (" << start.path_index << "," << start.stmt_idx << ") -- (" << end.path_index << "," << end.stmt_idx << ") - New information"); - val_state.cur_change_idx += 1; - } - }; - auto add_lifetime = [&](const ::MIR::LValue& lv, const Position& start, const Position& end) { - add_lifetime_s(val_state, lv, start, end); - }; - - auto apply_state = [&](State& state) { - // Apply all changes in this state, just in case there was new information - for(unsigned i = 0; i < fcn.temporaries.size(); i++) - add_lifetime_s( state, ::MIR::LValue::make_Temporary({i}), state.tmp_ends[i].start, state.tmp_ends[i].end ); - }; - auto add_to_visit = [&](unsigned int new_bb_idx, State new_state) { - auto& bb_memory_ent = block_seen_lifetimes[new_bb_idx]; - /*if( !bb_memory_ent.has_state() ) - { - // No recorded state, needs to be visited - DEBUG(state << " " << new_state.index << " -> bb" << new_bb_idx << " (no existing state)"); - } - else*/ if( bb_memory_ent.try_merge(new_state) ) - { - // This state has new information, needs to be visited - DEBUG(state << " " << new_state.index << " -> bb" << new_bb_idx << " (new info)"); - } - else - { - // Skip - DEBUG(state << " " << new_state.index << " No new state before push (to bb" << new_bb_idx << "), applying"); - apply_state(new_state); - return ; - } - todo_queue.push_back(::std::make_pair( new_bb_idx, mv$(new_state) )); - }; - - // Compare this state to a composite list of lifetimes seen in this block - // - Just compares the end of each proto lifetime - { - auto& bb_memory_ent = block_seen_lifetimes[bb_idx]; - bool has_new = bb_memory_ent.merge(val_state); - - if( !has_new && bb_memory_ent.has_state() ) - { - DEBUG(state << " " << val_state.index << " No new entry state"); - apply_state(val_state); - - continue ; - } - } - - // Check if this state has visited this block before, and if anything changed since last time - { - auto it = ::std::find(val_state.block_path.rbegin(), val_state.block_path.rend(), bb_idx); - if( it != val_state.block_path.rend() ) - { - auto idx = &*it - &val_state.block_path.front(); - if( val_state.block_change_idx[idx] == val_state.cur_change_idx ) - { - DEBUG(state << " " << val_state.index << " Loop and no change"); - continue ; - } - else - { - assert( val_state.block_change_idx[idx] < val_state.cur_change_idx ); - DEBUG(state << " " << val_state.index << " --- Loop, " << val_state.cur_change_idx - val_state.block_change_idx[idx] << " changes"); - } - } - else - { - DEBUG(state << " " << val_state.index << " ---"); - } - val_state.block_path.push_back(bb_idx); - val_state.block_change_idx.push_back( val_state.cur_change_idx ); - } - - Position cur_pos; - cur_pos.path_index = val_state.block_path.size() - 1; - cur_pos.stmt_idx = 0; - auto lvalue_read = [&](const ::MIR::LValue& lv) { - if(const auto* e = lv.opt_Temporary()) - { - // Update the last read location - val_state.tmp_ends.at(e->idx).end = cur_pos; - } - }; - auto lvalue_set = [&](const ::MIR::LValue& lv) { - if(const auto* e = lv.opt_Temporary()) - { - // End whatever value was originally there, and insert this new one - val_state.tmp_ends.at(e->idx).end = cur_pos; - add_lifetime(lv, val_state.tmp_ends.at(e->idx).start, val_state.tmp_ends.at(e->idx).end); - val_state.tmp_ends.at(e->idx).start = cur_pos; - } - }; - - // Run statements - for(const auto& stmt : fcn.blocks[bb_idx].statements) - { - auto stmt_idx = &stmt - &fcn.blocks[bb_idx].statements.front(); - cur_pos.stmt_idx = stmt_idx; - state.set_cur_stmt(bb_idx, stmt_idx); - DEBUG(state << " " << stmt); - - if( const auto* e = stmt.opt_Drop() ) - { - visit_mir_lvalues(stmt, [&](const auto& lv, ValUsage vu)->bool{ - if(vu == ValUsage::Read) - lvalue_read(lv); - return false; - }); - lvalue_read(e->slot); - lvalue_set(e->slot); - } - else - { - visit_mir_lvalues(stmt, [&](const auto& lv, ValUsage vu)->bool{ - if(vu == ValUsage::Read) - lvalue_read(lv); - if(vu == ValUsage::Write) - lvalue_set(lv); - return false; - }); - } - } - cur_pos.stmt_idx = fcn.blocks[bb_idx].statements.size(); - - state.set_cur_stmt_term(bb_idx); - DEBUG(state << "TERM " << fcn.blocks[bb_idx].terminator); - TU_MATCH(::MIR::Terminator, (fcn.blocks[bb_idx].terminator), (e), - (Incomplete, - // Should be impossible here. - ), - (Return, - // End all active lifetimes at their previous location. - apply_state(val_state); - ), - (Diverge, - apply_state(val_state); - ), - (Goto, - add_to_visit(e, mv$(val_state)); - ), - (Panic, - // What should be done here? - ), - (If, - lvalue_read(e.cond); - - // Push blocks - add_to_visit(e.bb0, val_state.clone()); - add_to_visit(e.bb1, mv$(val_state)); - ), - (Switch, - lvalue_read(e.val); - ::std::set<unsigned int> tgts; - for(const auto& tgt : e.targets) - tgts.insert(tgt); - - for(const auto& tgt : tgts) - { - auto vs = (tgt == *tgts.rbegin() ? mv$(val_state) : val_state.clone()); - add_to_visit(tgt, mv$(vs)); - } - ), - (Call, - if( const auto* f = e.fcn.opt_Value() ) - lvalue_read(*f); - for(const auto& arg : e.args) - if( const auto* e = arg.opt_LValue() ) - lvalue_read(*e); - - // Push blocks (with return valid only in one) - add_to_visit(e.panic_block, val_state.clone()); - - // TODO: If the function returns !, don't follow the ret_block - lvalue_set(e.ret_val); - add_to_visit(e.ret_block, mv$(val_state)); - ) - ) - } - - // Dump out variable lifetimes. -#if 0 - for(unsigned int i = 0; i < temporary_lifetimes.size(); i ++) - { - const auto& lft = temporary_lifetimes[i]; - auto name = FMT("tmp$" << i); - while(name.size() < 3+1+3) - name += " "; - DEBUG(name << " : " << FMT_CB(os, - for(unsigned int j = 0; j < lft.stmt_bitmap.size(); j++) - { - if(j != 0 && ::std::find(block_offsets.begin(), block_offsets.end(), j) != block_offsets.end()) - os << "|"; - os << (lft.stmt_bitmap[j] ? "X" : " "); - } - )); - } -#endif - - // Move lifetime bitmaps into the variable for the below code - tmp_lifetimes.reserve( temporary_lifetimes.size() ); - for(auto& lft : temporary_lifetimes) - tmp_lifetimes.push_back( VarLifetime(mv$(lft.stmt_bitmap)) ); - } + auto lifetimes = MIR_Helper_GetLifetimes(state, fcn, /*dump_debug=*/true); + //::std::vector<::MIR::ValueLifetime> var_lifetimes = mv$(lifetimes.m_variables); + ::std::vector<::MIR::ValueLifetime> tmp_lifetimes = mv$(lifetimes.m_temporaries); // 2. Unify variables of the same type with distinct non-overlapping lifetimes ::std::map<unsigned int, unsigned int> replacements; @@ -1520,6 +1134,8 @@ bool MIR_Optimise_UnifyTemporaries(::MIR::TypeResolve& state, ::MIR::Function& f } return false; }); + + // TODO: Replace in ScopeEnd too? } return replacement_needed; @@ -1572,6 +1188,12 @@ bool MIR_Optimise_UnifyBlocks(::MIR::TypeResolve& state, ::MIR::Function& fcn) return false; if( ae.slot != be.slot ) return false; + ), + (ScopeEnd, + if( ae.vars != be.vars ) + return false; + if( ae.tmps == be.tmps ) + return false; ) ) } @@ -1664,7 +1286,7 @@ bool MIR_Optimise_UnifyBlocks(::MIR::TypeResolve& state, ::MIR::Function& fcn) if( ! replacements.empty() ) { //MIR_TODO(state, "Unify blocks - " << replacements); - DEBUG("Unify blocks - " << replacements); + DEBUG("Unify blocks (old: new) - " << replacements); auto patch_tgt = [&replacements](::MIR::BasicBlockId& tgt) { auto it = replacements.find(tgt); if( it != replacements.end() ) @@ -1726,6 +1348,9 @@ bool MIR_Optimise_UnifyBlocks(::MIR::TypeResolve& state, ::MIR::Function& fcn) // -------------------------------------------------------------------- bool MIR_Optimise_ConstPropagte(::MIR::TypeResolve& state, ::MIR::Function& fcn) { +#if DUMP_BEFORE_ALL || DUMP_BEFORE_CONSTPROPAGATE + if( debug_enabled() ) MIR_Dump_Fcn(::std::cout, fcn); +#endif bool changed = false; TRACE_FUNCTION_FR("", changed); @@ -1760,8 +1385,8 @@ bool MIR_Optimise_ConstPropagte(::MIR::TypeResolve& state, ::MIR::Function& fcn) changed = true; } } - // NOTE: Quick special-case for bswap<u8> (a no-op) - else if( tef.name == "bswap" && tef.params.m_types.at(0) == ::HIR::CoreType::U8 ) + // NOTE: Quick special-case for bswap<u8/i8> (a no-op) + else if( tef.name == "bswap" && (tef.params.m_types.at(0) == ::HIR::CoreType::U8 || tef.params.m_types.at(0) == ::HIR::CoreType::I8) ) { DEBUG("bswap<u8> is a no-op"); if( auto* e = te.args.at(0).opt_LValue() ) @@ -1771,12 +1396,14 @@ bool MIR_Optimise_ConstPropagte(::MIR::TypeResolve& state, ::MIR::Function& fcn) bb.terminator = ::MIR::Terminator::make_Goto(te.ret_block); changed = true; } - //else if( tef.name == "get_dst_meta_slice" ) - //{ - // MIR_ASSERT(state, te.args.at(0).is_LValue(), "Argument to `get_dst_meta` must be a lvalue"); - // auto& e = te.args.at(0).as_LValue(); - // bb.statements.push_back(::MIR::Statement::make_Assign({ mv$(te.ret_val), ::MIR::RValue::make_DstMeta({ mv$(*e) }) })); - //} + else if( tef.name == "mrustc_slice_len" ) + { + MIR_ASSERT(state, te.args.at(0).is_LValue(), "Argument to `get_dst_meta` must be a lvalue"); + auto& e = te.args.at(0).as_LValue(); + bb.statements.push_back(::MIR::Statement::make_Assign({ mv$(te.ret_val), ::MIR::RValue::make_DstMeta({ mv$(e) }) })); + bb.terminator = ::MIR::Terminator::make_Goto(te.ret_block); + changed = true; + } else { // Ignore any other intrinsics @@ -1801,6 +1428,7 @@ bool MIR_Optimise_ConstPropagte(::MIR::TypeResolve& state, ::MIR::Function& fcn) auto it = known_values.find(*pe); if( it != known_values.end() ) { + DEBUG(state << "Value " << *pe << " known to be " << it->second); p = it->second.clone(); } } @@ -1821,6 +1449,7 @@ bool MIR_Optimise_ConstPropagte(::MIR::TypeResolve& state, ::MIR::Function& fcn) auto it = known_values.find(se); if( it != known_values.end() ) { + DEBUG(state << "Value " << se << " known to be" << it->second); e->src = it->second.clone(); } ), @@ -1840,7 +1469,41 @@ bool MIR_Optimise_ConstPropagte(::MIR::TypeResolve& state, ::MIR::Function& fcn) if( se.val_l.is_Constant() && se.val_r.is_Constant() ) { - // TODO: Evaluate BinOp + const auto& val_l = se.val_l.as_Constant(); + const auto& val_r = se.val_r.as_Constant(); + + ::MIR::Constant new_value; + bool replace = false; + switch(se.op) + { + case ::MIR::eBinOp::EQ: + if( val_l.is_Const() ) + ; + else + { + replace = true; + new_value = ::MIR::Constant::make_Bool({val_l == val_r}); + } + break; + case ::MIR::eBinOp::NE: + if( val_l.is_Const() ) + ; + else + { + replace = true; + new_value = ::MIR::Constant::make_Bool({val_l != val_r}); + } + break; + // TODO: Other binary operations + default: + break; + } + + if( replace ) + { + DEBUG(state << " " << e->src << " = " << new_value); + e->src = mv$(new_value); + } } ), (UniOp, @@ -1848,6 +1511,8 @@ bool MIR_Optimise_ConstPropagte(::MIR::TypeResolve& state, ::MIR::Function& fcn) if( it != known_values.end() ) { const auto& val = it->second; + ::MIR::Constant new_value; + bool replace = false; // TODO: Evaluate UniOp switch( se.op ) { @@ -1874,7 +1539,8 @@ bool MIR_Optimise_ConstPropagte(::MIR::TypeResolve& state, ::MIR::Function& fcn) // Invalid type for Uint literal break; } - e->src = ::MIR::Constant::make_Uint({ val, ve.t }); + new_value = ::MIR::Constant::make_Uint({ val, ve.t }); + replace = true; ), (Int, // Is ! valid on Int? @@ -1883,7 +1549,8 @@ bool MIR_Optimise_ConstPropagte(::MIR::TypeResolve& state, ::MIR::Function& fcn) // Not valid? ), (Bool, - e->src = ::MIR::Constant::make_Bool({ !ve.v }); + new_value = ::MIR::Constant::make_Bool({ !ve.v }); + replace = true; ), (Bytes, ), (StaticString, ), @@ -1900,10 +1567,12 @@ bool MIR_Optimise_ConstPropagte(::MIR::TypeResolve& state, ::MIR::Function& fcn) // Not valid? ), (Int, - e->src = ::MIR::Constant::make_Int({ -ve.v, ve.t }); + new_value = ::MIR::Constant::make_Int({ -ve.v, ve.t }); + replace = true; ), (Float, - e->src = ::MIR::Constant::make_Float({ -ve.v, ve.t }); + new_value = ::MIR::Constant::make_Float({ -ve.v, ve.t }); + replace = true; ), (Bool, // Not valid? @@ -1918,6 +1587,11 @@ bool MIR_Optimise_ConstPropagte(::MIR::TypeResolve& state, ::MIR::Function& fcn) ) break; } + if( replace ) + { + DEBUG(state << " " << e->src << " = " << new_value); + e->src = mv$(new_value); + } } ), (DstMeta, @@ -1948,18 +1622,19 @@ bool MIR_Optimise_ConstPropagte(::MIR::TypeResolve& state, ::MIR::Function& fcn) // - If a known temporary is borrowed mutably or mutated somehow, clear its knowledge visit_mir_lvalues(stmt, [&known_values](const ::MIR::LValue& lv, ValUsage vu)->bool { if( vu == ValUsage::Write ) { - auto it = known_values.find(lv); - if(it != known_values.end()) - known_values.erase(it); + known_values.erase(lv); } return false; }); // - Locate `temp = SOME_CONST` and record value if( const auto* e = stmt.opt_Assign() ) { - if( e->dst.is_Temporary() && e->src.is_Constant() ) + if( e->dst.is_Temporary() || e->dst.is_Variable() ) { - known_values.insert(::std::make_pair( e->dst.clone(), e->src.as_Constant().clone() )); + if( const auto* ce = e->src.opt_Constant() ) + { + known_values.insert(::std::make_pair( e->dst.clone(), ce->clone() )); + } } } } @@ -2000,12 +1675,15 @@ bool MIR_Optimise_ConstPropagte(::MIR::TypeResolve& state, ::MIR::Function& fcn) if( se.dst != te.cond ) continue; - if( !se.src.is_Constant() ) - continue; - if( !se.src.as_Constant().is_Bool() ) - continue; - val_known = true; - known_val = se.src.as_Constant().as_Bool().v; + if( se.src.is_Constant() && se.src.as_Constant().is_Bool() ) + { + val_known = true; + known_val = se.src.as_Constant().as_Bool().v; + } + else + { + val_known = false; + } break; } else @@ -2673,6 +2351,9 @@ bool MIR_Optimise_GarbageCollect(::MIR::TypeResolve& state, ::MIR::Function& fcn DEBUG("GC Temporary(" << i << ")"); fcn.temporaries.erase(fcn.temporaries.begin() + j); } + else { + DEBUG("tmp$" << i << " => tmp$" << j); + } temp_rewrite_table.push_back( used_temps[i] ? j ++ : ~0u ); } ::std::vector<unsigned int> var_rewrite_table; @@ -2684,6 +2365,9 @@ bool MIR_Optimise_GarbageCollect(::MIR::TypeResolve& state, ::MIR::Function& fcn DEBUG("GC Variable(" << i << ")"); fcn.named_variables.erase(fcn.named_variables.begin() + j); } + else { + DEBUG("var$" << i << " => var$" << j); + } var_rewrite_table.push_back( used_vars[i] ? j ++ : ~0u ); } ::std::vector<unsigned int> df_rewrite_table; @@ -2745,6 +2429,35 @@ bool MIR_Optimise_GarbageCollect(::MIR::TypeResolve& state, ::MIR::Function& fcn if( se->other != ~0u ) se->other = df_rewrite_table[se->other]; } + else if( auto* se = stmt_it->opt_ScopeEnd() ) + { + for(auto it = se->vars.begin(); it != se->vars.end(); ) + { + if( var_rewrite_table.at(*it) == ~0u ) { + it = se->vars.erase(it); + } + else { + *it = var_rewrite_table.at(*it); + ++ it; + } + } + for(auto it = se->tmps.begin(); it != se->tmps.end(); ) + { + if( temp_rewrite_table.at(*it) == ~0u ) { + it = se->tmps.erase(it); + } + else { + *it = temp_rewrite_table.at(*it); + ++ it; + } + } + + if( se->vars.empty() && se->tmps.empty() ) { + DEBUG("- Delete ScopeEnd (now empty)"); + stmt_it = it->statements.erase(stmt_it); + -- stmt_it; + } + } } state.set_cur_stmt_term(i); // Rewrite and advance |