MIR - Fixed optimisation and scopring issues

7 files changed, 203 insertions, 74 deletions

diff --git a/src/common.hpp b/src/common.hpp
index d3aca257..1971faa9 100644
--- a/src/common.hpp
+++ b/src/common.hpp
@@ -348,4 +348,52 @@ auto end (reversion_wrapper<T> w) { return w.iterable.rend(); }
 template <typename T>
 reversion_wrapper<T> reverse (T&& iterable) { return { iterable }; }
 
+
+template<typename T>
+struct RunIterable {
+    const ::std::vector<T>& list;
+    unsigned int ofs;
+    ::std::pair<size_t,size_t> cur;
+    RunIterable(const ::std::vector<T>& list):
+        list(list), ofs(0)
+    {
+        advance();
+    }
+    void advance() {
+        if( ofs < list.size() )
+        {
+            auto start = ofs;
+            while(ofs < list.size() && list[ofs] == list[start])
+                ofs ++;
+            cur = ::std::make_pair(start, ofs-1);
+        }
+        else
+        {
+            ofs = list.size()+1;
+        }
+    }
+    RunIterable<T> begin() { return *this; }
+    RunIterable<T> end() { auto rv = *this; rv.ofs = list.size()+1; return rv; }
+    bool operator==(const RunIterable<T>& x) {
+        return x.ofs == ofs;
+    }
+    bool operator!=(const RunIterable<T>& x) {
+        return !(*this == x);
+    }
+    void operator++() {
+        advance();
+    }
+    const ::std::pair<size_t,size_t>& operator*() const {
+        return this->cur;
+    }
+    const ::std::pair<size_t,size_t>* operator->() const {
+        return &this->cur;
+    }
+};
+template<typename T>
+RunIterable<T> runs(const ::std::vector<T>& x) {
+    return RunIterable<T>(x);
+}
+
+
 #endif
diff --git a/src/mir/check.cpp b/src/mir/check.cpp
index 8e933508..54b831df 100644
--- a/src/mir/check.cpp
+++ b/src/mir/check.cpp
@@ -84,53 +84,6 @@ namespace {
     }
 }
 
-namespace {
-    template<typename T>
-    struct RunIterable {
-        const ::std::vector<T>& list;
-        unsigned int ofs;
-        ::std::pair<size_t,size_t> cur;
-        RunIterable(const ::std::vector<T>& list):
-            list(list), ofs(0)
-        {
-            advance();
-        }
-        void advance() {
-            if( ofs < list.size() )
-            {
-                auto start = ofs;
-                while(ofs < list.size() && list[ofs] == list[start])
-                    ofs ++;
-                cur = ::std::make_pair(start, ofs-1);
-            }
-            else
-            {
-                ofs = list.size()+1;
-            }
-        }
-        RunIterable<T> begin() { return *this; }
-        RunIterable<T> end() { auto rv = *this; rv.ofs = list.size()+1; return rv; }
-        bool operator==(const RunIterable<T>& x) {
-            return x.ofs == ofs;
-        }
-        bool operator!=(const RunIterable<T>& x) {
-            return !(*this == x);
-        }
-        void operator++() {
-            advance();
-        }
-        const ::std::pair<size_t,size_t>& operator*() const {
-            return this->cur;
-        }
-        const ::std::pair<size_t,size_t>* operator->() const {
-            return &this->cur;
-        }
-    };
-    template<typename T>
-    RunIterable<T> runs(const ::std::vector<T>& x) {
-        return RunIterable<T>(x);
-    }
-}
 //template<typename T>
 //::std::ostream& operator<<(::std::ostream& os, const T& v) {
 //    v.fmt(os);
diff --git a/src/mir/check_full.cpp b/src/mir/check_full.cpp
index 1f527ff2..b697e01f 100644
--- a/src/mir/check_full.cpp
+++ b/src/mir/check_full.cpp
@@ -177,8 +177,33 @@ namespace
 
             ::HIR::TypeRef  tmp;
             bool is_copy = mir_res.m_resolve.type_is_copy( mir_res.sp, mir_res.get_lvalue_type(tmp, root_lv) );
-
             size_t cur_stmt = mir_res.get_cur_stmt_ofs();
+
+            // Dump all statements
+            if(true)
+            {
+                for(size_t i = 0; i < this->bb_path.size()-1; i++)
+                {
+                    size_t bb_idx = this->bb_path[i];
+                    const auto& bb = mir_res.m_fcn.blocks.at(bb_idx);
+
+                    for(size_t stmt_idx = 0; stmt_idx < bb.statements.size(); stmt_idx++)
+                    {
+                        DEBUG("BB" << bb_idx << "/" << stmt_idx << " - " << bb.statements[stmt_idx]);
+                    }
+                    DEBUG("BB" << bb_idx << "/TERM - " << bb.terminator);
+                }
+
+                {
+                    size_t bb_idx = this->bb_path.back();
+                    const auto& bb = mir_res.m_fcn.blocks.at(bb_idx);
+                    for(size_t stmt_idx = 0; stmt_idx < cur_stmt; stmt_idx ++)
+                    {
+                        DEBUG("BB" << bb_idx << "/" << stmt_idx << " - " << bb.statements[stmt_idx]);
+                    }
+                }
+            }
+
             if( !is_copy )
             {
                 // Walk backwards through the BBs and find where it's used by value
@@ -629,6 +654,9 @@ namespace std {
             print_val(FMT_CB(ss, ss << ",_" << i;), x.vars[i]);
         for(unsigned int i = 0; i < x.temporaries.size(); i ++)
             print_val(FMT_CB(ss, ss << ",t" << i;), x.temporaries[i]);
+        for(unsigned int i = 0; i < x.drop_flags.size(); i++)
+            if(x.drop_flags[i])
+                os << ",df" << i;
         os << ")";
         return os;
     }
@@ -638,6 +666,9 @@ namespace std {
 // "Executes" the function, keeping track of drop flags and variable validities
 void MIR_Validate_FullValState(::MIR::TypeResolve& mir_res, const ::MIR::Function& fcn)
 {
+    // TODO: Use a timer to check elapsed CPU time in this function, and check on each iteration
+    // - If more than `n` (10?) seconds passes on one function, warn and abort
+    //ElapsedTimeCounter    timer;
     ::std::vector<StateSet> block_entry_states( fcn.blocks.size() );
 
     // Determine value lifetimes (BBs in which Copy values are valid)
@@ -719,9 +750,10 @@ void MIR_Validate_FullValState(::MIR::TypeResolve& mir_res, const ::MIR::Functio
         {
             mir_res.set_cur_stmt(cur_block, i);
 
+            DEBUG(mir_res << blk.statements[i]);
+
             TU_MATCHA( (blk.statements[i]), (se),
             (Assign,
-                DEBUG(mir_res << " " << se.dst << " = " << se.src);
                 TU_MATCHA( (se.src), (ve),
                 (Use,
                     state.move_lvalue(mir_res, ve);
diff --git a/src/mir/from_hir.cpp b/src/mir/from_hir.cpp
index 808c16b6..246e2317 100644
--- a/src/mir/from_hir.cpp
+++ b/src/mir/from_hir.cpp
@@ -631,7 +631,7 @@ namespace {
         {
             TRACE_FUNCTION_FR("_Match", "_Match");
             auto _ = save_and_edit(m_borrow_raise_target, nullptr);
-            auto stmt_scope = m_builder.new_scope_temp(node.span());
+            //auto stmt_scope = m_builder.new_scope_temp(node.span());
             this->visit_node_ptr(node.m_value);
             auto match_val = m_builder.get_result_in_lvalue(node.m_value->span(), node.m_value->m_res_type);
 
@@ -680,13 +680,13 @@ namespace {
                 const auto& sp = node.span();
 
                 auto res = m_builder.get_result(sp);
-                m_builder.raise_variables(sp, res, stmt_scope, /*to_above=*/true);
+                //m_builder.raise_variables(sp, res, stmt_scope, /*to_above=*/true);
                 m_builder.set_result(sp, mv$(res));
 
-                m_builder.terminate_scope( node.span(), mv$(stmt_scope) );
+                //m_builder.terminate_scope( node.span(), mv$(stmt_scope) );
             }
             else {
-                m_builder.terminate_scope( node.span(), mv$(stmt_scope), false );
+                //m_builder.terminate_scope( node.span(), mv$(stmt_scope), false );
             }
         } // ExprNode_Match
 
diff --git a/src/mir/mir_builder.cpp b/src/mir/mir_builder.cpp
index 35fc2fa4..eb50e9f7 100644
--- a/src/mir/mir_builder.cpp
+++ b/src/mir/mir_builder.cpp
@@ -611,14 +611,17 @@ void MirBuilder::raise_variables(const Span& sp, const ::MIR::LValue& val, const
                 DEBUG("Crossing split with no existing end state");
             }
 
+            // TODO: This should update the outer state to unset.
             auto& arm = sd_split->arms.back();
             if( const auto* ve = val.opt_Variable() )
             {
                 arm.var_states.insert(::std::make_pair( *ve, get_variable_state(sp, *ve).clone() ));
+                m_variable_states.at(*ve) = VarState(InvalidType::Uninit);
             }
             else if( const auto* ve = val.opt_Temporary() )
             {
                 arm.tmp_states.insert(::std::make_pair( ve->idx, get_temp_state(sp, ve->idx).clone() ));
+                m_temporary_states.at(ve->idx) = VarState(InvalidType::Uninit);
             }
             else
             {
@@ -865,20 +868,23 @@ void MirBuilder::raise_all(const Span& sp, ScopeHandle source, const ScopeHandle
             if(sd_loop->exit_state_valid)
             {
                 DEBUG("Crossing loop with existing end state");
-                // Insert these values as Invalid
+                // Insert these values as Invalid, both in the existing exit state, and in the changed list
                 for(auto idx : src_list)
                 {
                     auto v = sd_loop->exit_state.tmp_states.insert(::std::make_pair( idx, VarState(InvalidType::Uninit) ));
                     ASSERT_BUG(sp, v.second, "");
-
-                    auto v2 = sd_loop->changed_tmps.insert(::std::make_pair( idx, VarState(InvalidType::Uninit) ));
-                    ASSERT_BUG(sp, v2.second, "");
                 }
             }
             else
             {
                 DEBUG("Crossing loop with no end state");
             }
+
+            for(auto idx : src_list)
+            {
+                auto v2 = sd_loop->changed_tmps.insert(::std::make_pair( idx, VarState(InvalidType::Uninit) ));
+                ASSERT_BUG(sp, v2.second, "");
+            }
         }
         else if(auto* sd_split = scope_def.data.opt_Split())
         {
diff --git a/src/mir/operations.hpp b/src/mir/operations.hpp
index cdc9c00b..1c06bc8c 100644
--- a/src/mir/operations.hpp
+++ b/src/mir/operations.hpp
@@ -10,6 +10,8 @@
 
 // Check that the MIR is well-formed
 extern void MIR_Validate(const StaticTraitResolve& resolve, const ::HIR::ItemPath& path, const ::MIR::Function& fcn, const ::HIR::Function::args_t& args, const ::HIR::TypeRef& ret_type);
+// -
+extern void MIR_Validate_Full(const StaticTraitResolve& resolve, const ::HIR::ItemPath& path, const ::MIR::Function& fcn, const ::HIR::Function::args_t& args, const ::HIR::TypeRef& ret_type);
 // Perform needed changes to the generated MIR (virtualisation, Unsize/CoerceUnsize, ...)
 extern void MIR_Cleanup(const StaticTraitResolve& resolve, const ::HIR::ItemPath& path, ::MIR::Function& fcn, const ::HIR::Function::args_t& args, const ::HIR::TypeRef& ret_type);
 // Optimise the MIR
diff --git a/src/mir/optimise.cpp b/src/mir/optimise.cpp
index 81574afd..d7379526 100644
--- a/src/mir/optimise.cpp
+++ b/src/mir/optimise.cpp
@@ -474,6 +474,9 @@ void MIR_Optimise(const StaticTraitResolve& resolve, const ::HIR::ItemPath& path
     // GC pass on blocks and variables
     // - Find unused blocks, then delete and rewrite all references.
     MIR_Optimise_GarbageCollect(state, fcn);
+
+    //MIR_Validate(resolve, path, fcn, args, ret_type);
+    //MIR_Validate_Full(resolve, path, fcn, args, ret_type);
 }
 
 // --------------------------------------------------------------------
@@ -1422,6 +1425,7 @@ bool MIR_Optimise_ConstPropagte(::MIR::TypeResolve& state, ::MIR::Function& fcn)
         auto bbidx = &bb - &fcn.blocks.front();
 
         ::std::map< ::MIR::LValue, ::MIR::Constant >    known_values;
+        ::std::map< unsigned, bool >    known_drop_flags;
 
         auto check_param = [&](::MIR::Param& p) {
             if(const auto* pe = p.opt_LValue()) {
@@ -1619,6 +1623,38 @@ bool MIR_Optimise_ConstPropagte(::MIR::TypeResolve& state, ::MIR::Function& fcn)
                     )
                 )
             }
+            else if( const auto* se = stmt.opt_SetDropFlag() )
+            {
+                if( se->other == ~0u )
+                {
+                    known_drop_flags.insert(::std::make_pair( se->idx, se->new_val ));
+                }
+                else
+                {
+                    auto it = known_drop_flags.find(se->other);
+                    if( it != known_drop_flags.end() )
+                    {
+                        known_drop_flags.insert(::std::make_pair( se->idx, se->new_val ^ it->second ));
+                    }
+                }
+            }
+            else if( auto* se = stmt.opt_Drop() )
+            {
+                if( se->flag_idx != ~0u )
+                {
+                    auto it = known_drop_flags.find(se->flag_idx);
+                    if( it != known_drop_flags.end() )
+                    {
+                        if( it->second ) {
+                            se->flag_idx = ~0u;
+                        }
+                        else {
+                            // TODO: Delete drop
+                            stmt = ::MIR::Statement::make_ScopeEnd({ });
+                        }
+                    }
+                }
+            }
             // - 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 ) {
@@ -2285,11 +2321,11 @@ bool MIR_Optimise_GarbageCollect(::MIR::TypeResolve& state, ::MIR::Function& fcn
             TU_IFLET( ::MIR::Statement, stmt, Assign, e,
                 assigned_lval(e.dst);
             )
-            else if( const auto* e = stmt.opt_Drop() )
-            {
-                if( e->flag_idx != ~0u )
-                    used_dfs.at(e->flag_idx) = true;
-            }
+            //else if( const auto* e = stmt.opt_Drop() )
+            //{
+            //    //if( e->flag_idx != ~0u )
+            //    //    used_dfs.at(e->flag_idx) = true;
+            //}
             else if( const auto* e = stmt.opt_Asm() )
             {
                 for(const auto& val : e->outputs)
@@ -2299,6 +2335,7 @@ bool MIR_Optimise_GarbageCollect(::MIR::TypeResolve& state, ::MIR::Function& fcn
             {
                 if( e->other != ~0u )
                     used_dfs.at(e->other) = true;
+                used_dfs.at(e->idx) = true;
             }
         }
 
@@ -2348,7 +2385,6 @@ bool MIR_Optimise_GarbageCollect(::MIR::TypeResolve& state, ::MIR::Function& fcn
     {
         if( !used_temps[i] )
         {
-            DEBUG("GC Temporary(" << i << ")");
             fcn.temporaries.erase(fcn.temporaries.begin() + j);
         }
         else {
@@ -2356,6 +2392,15 @@ bool MIR_Optimise_GarbageCollect(::MIR::TypeResolve& state, ::MIR::Function& fcn
         }
         temp_rewrite_table.push_back( used_temps[i] ? j ++ : ~0u );
     }
+    DEBUG("Deleted Temporaries:" << FMT_CB(ss,
+                for(auto run : runs(used_temps))
+                    if( !used_temps[run.first] )
+                    {
+                        ss << " " << run.first;
+                        if(run.second != run.first)
+                            ss << "-" << run.second;
+                    }
+                ));
     ::std::vector<unsigned int> var_rewrite_table;
     unsigned int n_var = fcn.named_variables.size();
     for(unsigned int i = 0, j = 0; i < n_var; i ++)
@@ -2377,7 +2422,7 @@ bool MIR_Optimise_GarbageCollect(::MIR::TypeResolve& state, ::MIR::Function& fcn
         if( !used_dfs[i] )
         {
             DEBUG("GC df" << i);
-            fcn.drop_flags.erase(fcn.drop_flags.begin() + j);
+            // NOTE: Not erased until after rewriting
         }
         df_rewrite_table.push_back( used_dfs[i] ? j ++ : ~0u );
     }
@@ -2408,28 +2453,47 @@ bool MIR_Optimise_GarbageCollect(::MIR::TypeResolve& state, ::MIR::Function& fcn
                 }
                 return false;
                 };
-            for(auto stmt_it = it->statements.begin(); stmt_it != it->statements.end(); ++ stmt_it)
+            ::std::vector<bool> to_remove_statements(it->statements.size());
+            for(auto& stmt : it->statements)
             {
-                state.set_cur_stmt(i, stmt_it - it->statements.begin());
-                visit_mir_lvalues_mut(*stmt_it, lvalue_cb);
-                if( auto* se = stmt_it->opt_Drop() )
+                auto stmt_idx = &stmt - &it->statements.front();
+                state.set_cur_stmt(i, stmt_idx);
+                if( auto* se = stmt.opt_Drop() )
+                {
+                    // If the drop flag was unset, either remove the drop or remove the drop flag reference
+                    if( se->flag_idx != ~0u && df_rewrite_table[se->flag_idx] == ~0u)
+                    {
+                        if( fcn.drop_flags.at(se->flag_idx) ) {
+                            DEBUG(state << "Remove flag from " << stmt);
+                            se->flag_idx = ~0u;
+                        }
+                        else {
+                            DEBUG(state << "Remove " << stmt);
+                            to_remove_statements[stmt_idx] = true;
+                            continue ;
+                        }
+                    }
+                }
+
+                visit_mir_lvalues_mut(stmt, lvalue_cb);
+                if( auto* se = stmt.opt_Drop() )
                 {
                     // Rewrite drop flag indexes
                     if( se->flag_idx != ~0u )
                         se->flag_idx = df_rewrite_table[se->flag_idx];
                 }
-                else if( auto* se = stmt_it->opt_SetDropFlag() )
+                else if( auto* se = stmt.opt_SetDropFlag() )
                 {
                     // Rewrite drop flag indexes OR delete
                     if( df_rewrite_table[se->idx] == ~0u ) {
-                        stmt_it = it->statements.erase(stmt_it)-1;
+                        to_remove_statements[stmt_idx] = true;
                         continue ;
                     }
                     se->idx = df_rewrite_table[se->idx];
                     if( se->other != ~0u )
                         se->other = df_rewrite_table[se->other];
                 }
-                else if( auto* se = stmt_it->opt_ScopeEnd() )
+                else if( auto* se = stmt.opt_ScopeEnd() )
                 {
                     for(auto it = se->vars.begin(); it != se->vars.end(); )
                     {
@@ -2453,9 +2517,9 @@ bool MIR_Optimise_GarbageCollect(::MIR::TypeResolve& state, ::MIR::Function& fcn
                     }
 
                     if( se->vars.empty() && se->tmps.empty() ) {
-                        DEBUG("- Delete ScopeEnd (now empty)");
-                        stmt_it = it->statements.erase(stmt_it);
-                        -- stmt_it;
+                        DEBUG(state << "Delete ScopeEnd (now empty)");
+                        to_remove_statements[stmt_idx] = true;
+                        continue ;
                     }
                 }
             }
@@ -2495,10 +2559,34 @@ bool MIR_Optimise_GarbageCollect(::MIR::TypeResolve& state, ::MIR::Function& fcn
                 )
             )
 
+            // Delete all statements flagged in a bitmap for deletion
+            auto stmt_it = it->statements.begin();
+            for(auto flag : to_remove_statements)
+            {
+                if(flag) {
+                    stmt_it = it->statements.erase(stmt_it);
+                }
+                else {
+                    ++ stmt_it;
+                }
+            }
+
             ++it;
         }
     }
 
+    for(unsigned int i = 0, j = 0; i < n_df; i ++)
+    {
+        if( !used_dfs[i] )
+        {
+            fcn.drop_flags.erase(fcn.drop_flags.begin() + j);
+        }
+        else
+        {
+            j ++;
+        }
+    }
+
     // TODO: Detect if any optimisations happened, and return true in that case
     return false;
 }