MIR - Add ScopeEnd statement to indicate where a value will no longer be used

15 files changed, 139 insertions, 27 deletions

diff --git a/src/hir/deserialise.cpp b/src/hir/deserialise.cpp
index 4a9b5720..19306a63 100644
--- a/src/hir/deserialise.cpp
+++ b/src/hir/deserialise.cpp
@@ -1008,6 +1008,11 @@ namespace {
                 m_in.read_bool(),
                 static_cast<unsigned int>(m_in.read_count())
                 });
+        case 4:
+            return ::MIR::Statement::make_ScopeEnd({
+                deserialise_vec<unsigned int>(),
+                deserialise_vec<unsigned int>()
+                });
         default:
             ::std::cerr << "Bad tag for a MIR Statement" << ::std::endl;
             throw "";
diff --git a/src/hir/serialise.cpp b/src/hir/serialise.cpp
index 81319c2e..e5264ae2 100644
--- a/src/hir/serialise.cpp
+++ b/src/hir/serialise.cpp
@@ -495,6 +495,11 @@ namespace {
                 m_out.write_count(e.idx);
                 m_out.write_bool(e.new_val);
                 m_out.write_count(e.other);
+                ),
+            (ScopeEnd,
+                m_out.write_tag(4);
+                serialise_vec(e.vars);
+                serialise_vec(e.tmps);
                 )
             )
         }
diff --git a/src/mir/check.cpp b/src/mir/check.cpp
index 7c8fbd13..4dbdb45f 100644
--- a/src/mir/check.cpp
+++ b/src/mir/check.cpp
@@ -457,6 +457,8 @@ void MIR_Validate_ValState(::MIR::TypeResolve& state, const ::MIR::Function& fcn
                 // Mark destination as valid
                 val_state.mark_validity( state, stmt.as_Assign().dst, true );
                 break;
+            case ::MIR::Statement::TAG_ScopeEnd:
+                break;
             }
         }
 
@@ -852,6 +854,8 @@ void MIR_Validate(const StaticTraitResolve& resolve, const ::HIR::ItemPath& path
                 case ::MIR::Statement::TAG_Drop:
                     // TODO: Anything need checking here?
                     break;
+                case ::MIR::Statement::TAG_ScopeEnd:
+                    break;
                 }
             }
 
diff --git a/src/mir/check_full.cpp b/src/mir/check_full.cpp
index 96da8a74..992db468 100644
--- a/src/mir/check_full.cpp
+++ b/src/mir/check_full.cpp
@@ -712,6 +712,9 @@ void MIR_Validate_FullValState(::MIR::TypeResolve& mir_res, const ::MIR::Functio
                         state.move_lvalue(mir_res, se.slot);
                     }
                 }
+                ),
+            (ScopeEnd,
+                // TODO: Mark all mentioned variables as invalid
                 )
             )
         }
diff --git a/src/mir/cleanup.cpp b/src/mir/cleanup.cpp
index 6516dd60..17dca948 100644
--- a/src/mir/cleanup.cpp
+++ b/src/mir/cleanup.cpp
@@ -932,6 +932,8 @@ void MIR_Cleanup(const StaticTraitResolve& resolve, const ::HIR::ItemPath& path,
                 ),
             (SetDropFlag,
                 ),
+            (ScopeEnd,
+                ),
             (Asm,
                 for(auto& v : se.inputs)
                     MIR_Cleanup_LValue(state, mutator,  v.second);
diff --git a/src/mir/dump.cpp b/src/mir/dump.cpp
index eb74dc9e..0187e8b2 100644
--- a/src/mir/dump.cpp
+++ b/src/mir/dump.cpp
@@ -99,6 +99,14 @@ namespace {
                             m_os << " IF df$" << e.flag_idx;
                         }
                         m_os << ");\n";
+                        ),
+                    (ScopeEnd,
+                        m_os << "// Scope End: ";
+                        for(auto idx : e.vars)
+                            m_os << "var$" << idx << ",";
+                        for(auto idx : e.tmps)
+                            m_os << "tmp$" << idx << ",";
+                        m_os << "\n";
                         )
                     )
                 }
diff --git a/src/mir/from_hir.hpp b/src/mir/from_hir.hpp
index 5b0b8904..e124770c 100644
--- a/src/mir/from_hir.hpp
+++ b/src/mir/from_hir.hpp
@@ -199,6 +199,8 @@ public:
     void push_stmt_set_dropflag_val(const Span& sp, unsigned int index, bool value);
     void push_stmt_set_dropflag_other(const Span& sp, unsigned int index, unsigned int other);
 
+    void push_stmt(const Span& sp, ::MIR::Statement stmt);
+
     // - Block management
     bool block_active() const {
         return m_block_active;
diff --git a/src/mir/helpers.cpp b/src/mir/helpers.cpp
index e0e646fa..21e16116 100644
--- a/src/mir/helpers.cpp
+++ b/src/mir/helpers.cpp
@@ -402,6 +402,8 @@ namespace {
         (Drop,
             // Well, it mutates...
             rv |= visit_mir_lvalue(e.slot, ValUsage::Write, cb);
+            ),
+        (ScopeEnd,
             )
         )
         return rv;
diff --git a/src/mir/mir.cpp b/src/mir/mir.cpp
index 3c16af37..9edc925b 100644
--- a/src/mir/mir.cpp
+++ b/src/mir/mir.cpp
@@ -483,6 +483,14 @@ namespace MIR {
             if(e.flag_idx != ~0u)
                 os << "IF df$" << e.flag_idx;
             os << ")";
+            ),
+        (ScopeEnd,
+            os << "ScopeEnd(";
+            for(auto idx : e.vars)
+                os << "var$" << idx << ",";
+            for(auto idx : e.tmps)
+                os << "tmp$" << idx << ",";
+            os << ")";
             )
         )
         return os;
diff --git a/src/mir/mir.hpp b/src/mir/mir.hpp
index 93a430ff..dc33d673 100644
--- a/src/mir/mir.hpp
+++ b/src/mir/mir.hpp
@@ -272,6 +272,10 @@ TAGGED_UNION(Statement, Assign,
         eDropKind   kind;   // NOTE: For the `box` primitive
         LValue  slot;
         unsigned int flag_idx;  // Valid if != ~0u
+        }),
+    (ScopeEnd, struct {
+        ::std::vector<unsigned> vars;
+        ::std::vector<unsigned> tmps;
         })
     );
 extern ::std::ostream& operator<<(::std::ostream& os, const Statement& x);
@@ -286,6 +290,7 @@ struct BasicBlock
 class Function
 {
 public:
+    // TODO: Unify Variables, Temporaries, and Arguments
     ::std::vector< ::HIR::TypeRef>  named_variables;
     ::std::vector< ::HIR::TypeRef>  temporaries;
     ::std::vector<bool> drop_flags;
diff --git a/src/mir/mir_builder.cpp b/src/mir/mir_builder.cpp
index 686df677..c023b797 100644
--- a/src/mir/mir_builder.cpp
+++ b/src/mir/mir_builder.cpp
@@ -304,7 +304,7 @@ void MirBuilder::push_stmt_assign(const Span& sp, ::MIR::LValue dst, ::MIR::RVal
 
     // Drop target if populated
     mark_value_assigned(sp, dst);
-    m_output.blocks.at(m_current_block).statements.push_back( ::MIR::Statement::make_Assign({ mv$(dst), mv$(val) }) );
+    this->push_stmt( sp, ::MIR::Statement::make_Assign({ mv$(dst), mv$(val) }) );
 }
 void MirBuilder::push_stmt_drop(const Span& sp, ::MIR::LValue val, unsigned int flag/*=~0u*/)
 {
@@ -316,9 +316,7 @@ void MirBuilder::push_stmt_drop(const Span& sp, ::MIR::LValue val, unsigned int
         return ;
     }
 
-    auto stmt = ::MIR::Statement::make_Drop({ ::MIR::eDropKind::DEEP, mv$(val), flag });
-    DEBUG(stmt);
-    m_output.blocks.at(m_current_block).statements.push_back( mv$(stmt) );
+    this->push_stmt(sp, ::MIR::Statement::make_Drop({ ::MIR::eDropKind::DEEP, mv$(val), flag }));
 
     if( flag != ~0u )
     {
@@ -333,9 +331,7 @@ void MirBuilder::push_stmt_drop_shallow(const Span& sp, ::MIR::LValue val, unsig
 
     // TODO: Ensure that the type is a Box?
 
-    auto stmt = ::MIR::Statement::make_Drop({ ::MIR::eDropKind::SHALLOW, mv$(val), flag });
-    DEBUG(stmt);
-    m_output.blocks.at(m_current_block).statements.push_back( mv$(stmt) );
+    this->push_stmt(sp, ::MIR::Statement::make_Drop({ ::MIR::eDropKind::SHALLOW, mv$(val), flag }));
 
     if( flag != ~0u )
     {
@@ -352,21 +348,19 @@ void MirBuilder::push_stmt_asm(const Span& sp, ::MIR::Statement::Data_Asm data)
         mark_value_assigned(sp, v.second);
 
     // 2. Push
-    auto stmt = ::MIR::Statement::make_Asm( mv$(data) );
-    DEBUG(stmt);
-    m_output.blocks.at(m_current_block).statements.push_back( mv$(stmt) );
+    this->push_stmt(sp, ::MIR::Statement::make_Asm( mv$(data) ));
 }
 void MirBuilder::push_stmt_set_dropflag_val(const Span& sp, unsigned int idx, bool value)
 {
-    ASSERT_BUG(sp, m_block_active, "Pushing statement with no active block");
-    auto stmt = ::MIR::Statement::make_SetDropFlag({ idx, value });
-    DEBUG(stmt);
-    m_output.blocks.at(m_current_block).statements.push_back( mv$(stmt) );
+    this->push_stmt(sp, ::MIR::Statement::make_SetDropFlag({ idx, value }));
 }
 void MirBuilder::push_stmt_set_dropflag_other(const Span& sp, unsigned int idx, unsigned int other)
 {
+    this->push_stmt(sp, ::MIR::Statement::make_SetDropFlag({ idx, false, other }));
+}
+void MirBuilder::push_stmt(const Span& sp, ::MIR::Statement stmt)
+{
     ASSERT_BUG(sp, m_block_active, "Pushing statement with no active block");
-    auto stmt = ::MIR::Statement::make_SetDropFlag({ idx, false, other });
     DEBUG(stmt);
     m_output.blocks.at(m_current_block).statements.push_back( mv$(stmt) );
 }
@@ -777,6 +771,21 @@ void MirBuilder::terminate_scope(const Span& sp, ScopeHandle scope, bool emit_cl
     {
         // 2. Emit drops for all non-moved variables (share with below)
         drop_scope_values(scope_def);
+
+        // Emit ScopeEnd for all controlled values
+        ::MIR::Statement::Data_ScopeEnd se;
+        if(const auto* e = scope_def.data.opt_Variables() ) {
+            se.vars = e->vars;
+        }
+        else if(const auto* e = scope_def.data.opt_Temporaries()) {
+            se.tmps = e->temporaries;
+        }
+        else {
+        }
+        // Only push the ScopeEnd if there were variables to end
+        if( !se.vars.empty() || !se.tmps.empty() ) {
+            this->push_stmt(sp, ::MIR::Statement( mv$(se) ));
+        }
     }
 
     // 3. Pop scope (last because `drop_scope_values` uses the stack)
diff --git a/src/mir/optimise.cpp b/src/mir/optimise.cpp
index 390bd1d6..063e5fe3 100644
--- a/src/mir/optimise.cpp
+++ b/src/mir/optimise.cpp
@@ -185,6 +185,8 @@ namespace {
         (Drop,
             // Well, it mutates...
             rv |= visit_mir_lvalue_mut(e.slot, ValUsage::Write, cb);
+            ),
+        (ScopeEnd,
             )
         )
         return rv;
@@ -686,22 +688,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 +712,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 +719,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 +991,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)
@@ -1138,6 +1148,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;
                     )
                 )
             }
@@ -1230,7 +1246,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() )
@@ -1326,8 +1342,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() )
@@ -2311,6 +2327,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
diff --git a/src/trans/codegen_c.cpp b/src/trans/codegen_c.cpp
index 983bdfd4..c3532073 100644
--- a/src/trans/codegen_c.cpp
+++ b/src/trans/codegen_c.cpp
@@ -1315,6 +1315,9 @@ namespace {
                     switch( stmt.tag() )
                     {
                     case ::MIR::Statement::TAGDEAD: throw "";
+                    case ::MIR::Statement::TAG_ScopeEnd:
+                        m_of << "// " << stmt << "\n";
+                        break;
                     case ::MIR::Statement::TAG_SetDropFlag: {
                         const auto& e = stmt.as_SetDropFlag();
                         m_of << "\tdf" << e.idx << " = ";
@@ -1330,7 +1333,7 @@ namespace {
                         const auto& ty = mir_res.get_lvalue_type(tmp, e.slot);
 
                         if( e.flag_idx != ~0u )
-                            m_of << "if( df" << e.flag_idx << " ) {\n";
+                            m_of << "\tif( df" << e.flag_idx << " ) {\n";
 
                         switch( e.kind )
                         {
@@ -1353,7 +1356,7 @@ namespace {
                             break;
                         }
                         if( e.flag_idx != ~0u )
-                            m_of << "}\n";
+                            m_of << "\t}\n";
                         break; }
                     case ::MIR::Statement::TAG_Asm: {
                         const auto& e = stmt.as_Asm();
@@ -2720,7 +2723,11 @@ namespace {
                     if( ' ' <= v && v < 0x7F && v != '"' && v != '\\' )
                         m_of << v;
                     else
+                    {
                         m_of << "\\" << ((unsigned int)v & 0xFF);
+                        if( isdigit( *(&v+1) ) )
+                            m_of << "\"\"";
+                    }
                 }
                 m_of << "\"" << ::std::dec;
                 m_of << ";\n\t";
diff --git a/src/trans/enumerate.cpp b/src/trans/enumerate.cpp
index 481b275b..02116d18 100644
--- a/src/trans/enumerate.cpp
+++ b/src/trans/enumerate.cpp
@@ -875,6 +875,8 @@ void Trans_Enumerate_Types(EnumState& state)
                             for(const auto& v : se.inputs)
                                 H::visit_lvalue(tv,pp,fcn, v.second);
                             ),
+                        (ScopeEnd,
+                            ),
                         (Assign,
                             H::visit_lvalue(tv,pp,fcn, se.dst);
                             TU_MATCHA( (se.src), (re),
@@ -1461,6 +1463,8 @@ void Trans_Enumerate_FillFrom_MIR(EnumState& state, const ::MIR::Function& code,
                 ),
             (SetDropFlag,
                 ),
+            (ScopeEnd,
+                ),
             (Drop,
                 DEBUG("- DROP " << se.slot);
                 Trans_Enumerate_FillFrom_MIR_LValue(state, se.slot, pp);
diff --git a/src/trans/monomorphise.cpp b/src/trans/monomorphise.cpp
index 1688a8f5..1a7d8e79 100644
--- a/src/trans/monomorphise.cpp
+++ b/src/trans/monomorphise.cpp
@@ -150,6 +150,9 @@ namespace {
             case ::MIR::Statement::TAG_SetDropFlag:
                 statements.push_back( ::MIR::Statement( stmt.as_SetDropFlag() ) );
                 break;
+            case ::MIR::Statement::TAG_ScopeEnd:
+                statements.push_back( ::MIR::Statement( stmt.as_ScopeEnd() ) );
+                break;
             case ::MIR::Statement::TAG_Drop: {
                 const auto& e = stmt.as_Drop();
                 DEBUG("- DROP " << e.slot);