summaryrefslogtreecommitdiff
path: root/src/mir/optimise.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/mir/optimise.cpp')
-rw-r--r--src/mir/optimise.cpp442
1 files changed, 4 insertions, 438 deletions
diff --git a/src/mir/optimise.cpp b/src/mir/optimise.cpp
index 2e823821..390bd1d6 100644
--- a/src/mir/optimise.cpp
+++ b/src/mir/optimise.cpp
@@ -1006,6 +1006,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 +1037,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=*/false);
+ //::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;
generated by cgit v1.2.3 (git 2.39.1) at 2025-06-14 22:04:38 +0000