MIR - Add rough optimisations

5 files changed, 225 insertions, 0 deletions

diff --git a/src/mir/cleanup.cpp b/src/mir/cleanup.cpp
index 7297f402..f921d655 100644
--- a/src/mir/cleanup.cpp
+++ b/src/mir/cleanup.cpp
@@ -14,6 +14,7 @@
 #include <hir/visitor.hpp>
 #include <hir_typeck/static.hpp>
 #include <mir/helpers.hpp>
+#include <mir/operations.hpp>
 
 struct MirMutator
 {
@@ -700,6 +701,34 @@ void MIR_Cleanup(const StaticTraitResolve& resolve, const ::HIR::ItemPath& path,
         }
         
         state.set_cur_stmt_term( mutator.cur_block );
+        
+        TU_MATCHA( (block.terminator), (e),
+        (Incomplete,
+            ),
+        (Return,
+            ),
+        (Diverge,
+            ),
+        (Goto,
+            ),
+        (Panic,
+            ),
+        (If,
+            MIR_Cleanup_LValue(state, mutator, e.cond);
+            ),
+        (Switch,
+            MIR_Cleanup_LValue(state, mutator, e.val);
+            ),
+        (Call,
+            MIR_Cleanup_LValue(state, mutator, e.ret_val);
+            if( e.fcn.is_Value() ) {
+                MIR_Cleanup_LValue(state, mutator, e.fcn.as_Value());
+            }
+            for(auto& lv : e.args)
+                MIR_Cleanup_LValue(state, mutator, lv);
+            )
+        )
+        
         TU_IFLET( ::MIR::Terminator, block.terminator, Call, e,
             
             TU_IFLET( ::MIR::CallTarget, e.fcn, Path, path,
@@ -729,5 +758,9 @@ void MIR_Cleanup(const StaticTraitResolve& resolve, const ::HIR::ItemPath& path,
         mutator.cur_block += 1;
         mutator.cur_stmt = 0;
     }
+    
+    
+    // TODO: Make this configurable once the optimisations become expensive
+    MIR_Optimise(resolve, path, fcn, args, ret_type);
 }
 
diff --git a/src/mir/helpers.cpp b/src/mir/helpers.cpp
index 6842ab72..e2272f31 100644
--- a/src/mir/helpers.cpp
+++ b/src/mir/helpers.cpp
@@ -27,6 +27,12 @@ void ::MIR::TypeResolve::print_msg(const char* tag, ::std::function<void(::std::
     throw CheckFailure {};
 }
 
+const ::MIR::BasicBlock& ::MIR::TypeResolve::get_block(::MIR::BasicBlockId id) const
+{
+    MIR_ASSERT(*this, id < m_fcn.blocks.size(), "Block ID " << id << " out of range");
+    return m_fcn.blocks[id];
+}
+
 const ::HIR::TypeRef& ::MIR::TypeResolve::get_lvalue_type(::HIR::TypeRef& tmp, const ::MIR::LValue& val) const
 {
     TU_MATCH(::MIR::LValue, (val), (e),
diff --git a/src/mir/helpers.hpp b/src/mir/helpers.hpp
index aef012a7..6382dbed 100644
--- a/src/mir/helpers.hpp
+++ b/src/mir/helpers.hpp
@@ -21,6 +21,9 @@ namespace MIR {
 
 class Function;
 class LValue;
+class BasicBlock;
+
+typedef unsigned int    BasicBlockId;
 
 struct CheckFailure:
     public ::std::exception
@@ -84,6 +87,8 @@ public:
     }
     void print_msg(const char* tag, ::std::function<void(::std::ostream& os)> cb) const;
     
+    const ::MIR::BasicBlock& get_block(::MIR::BasicBlockId id) const;
+    
     const ::HIR::TypeRef& get_lvalue_type(::HIR::TypeRef& tmp, const ::MIR::LValue& val) const;
     
     const ::HIR::TypeRef* is_type_owned_box(const ::HIR::TypeRef& ty) const;
diff --git a/src/mir/operations.hpp b/src/mir/operations.hpp
index a32531e9..deef8830 100644
--- a/src/mir/operations.hpp
+++ b/src/mir/operations.hpp
@@ -8,5 +8,9 @@
 #include <hir_typeck/static.hpp>
 #include <hir/item_path.hpp>
 
+// 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);
+// 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
+extern void MIR_Optimise(const StaticTraitResolve& resolve, const ::HIR::ItemPath& path, ::MIR::Function& fcn, const ::HIR::Function::args_t& args, const ::HIR::TypeRef& ret_type);
diff --git a/src/mir/optimise.cpp b/src/mir/optimise.cpp
new file mode 100644
index 00000000..72651dd3
--- /dev/null
+++ b/src/mir/optimise.cpp
@@ -0,0 +1,177 @@
+/*
+ * MRustC - Rust Compiler
+ * - By John Hodge (Mutabah/thePowersGang)
+ *
+ * mir/optimise.cpp
+ * - MIR Optimisations
+ *
+ */
+#include "main_bindings.hpp"
+#include "mir.hpp"
+#include <hir/visitor.hpp>
+#include <hir_typeck/static.hpp>
+#include <mir/helpers.hpp>
+#include <mir/operations.hpp>
+
+namespace {
+    ::MIR::BasicBlockId get_new_target(const ::MIR::TypeResolve& state, ::MIR::BasicBlockId bb)
+    {
+        const auto& target = state.get_block(bb);
+        if( target.statements.size() != 0 )
+        {
+            return bb;
+        }
+        else if( !target.terminator.is_Goto() )
+        {
+            return bb;
+        }
+        else
+        {
+            // Make sure we don't infinite loop
+            if( bb == target.terminator.as_Goto() )
+                return bb;
+            
+            auto rv = get_new_target(state, target.terminator.as_Goto());
+            DEBUG(bb << " => " << rv);
+            return rv;
+        }
+    }
+}
+
+void MIR_Optimise(const StaticTraitResolve& resolve, const ::HIR::ItemPath& path, ::MIR::Function& fcn, const ::HIR::Function::args_t& args, const ::HIR::TypeRef& ret_type)
+{
+    static Span sp;
+    TRACE_FUNCTION_F(path);
+    ::MIR::TypeResolve   state { sp, resolve, FMT_CB(ss, ss << path;), ret_type, args, fcn };
+    
+    // 1. Replace targets that point to a block that is just a goto
+    for(auto& block : fcn.blocks)
+    {
+        TU_MATCHA( (block.terminator), (e),
+        (Incomplete,
+            ),
+        (Return,
+            ),
+        (Diverge,
+            ),
+        (Goto,
+            e = get_new_target(state, e);
+            ),
+        (Panic,
+            ),
+        (If,
+            e.bb0 = get_new_target(state, e.bb0);
+            e.bb1 = get_new_target(state, e.bb1);
+            ),
+        (Switch,
+            for(auto& target : e.targets)
+                target = get_new_target(state, target);
+            ),
+        (Call,
+            e.ret_block = get_new_target(state, e.ret_block);
+            e.panic_block = get_new_target(state, e.panic_block);
+            )
+        )
+    }
+    
+    #if 0
+    // GC pass on blocks and variables
+    // - Find unused blocks, then delete and rewrite all references.
+    {
+        ::std::vector<bool> visited( fcn.blocks.size() );
+        ::std::vector< ::MIR::BasicBlockId> to_visit;
+        to_visit.push_back( 0 );
+        while( to_visit.size() > 0 )
+        {
+            auto bb = to_visit.back(); to_visit.pop_back();
+            visited[bb] = true;
+            
+            const auto& block = fcn.blocks[bb];
+            TU_MATCHA( (block.terminator), (e),
+            (Incomplete,
+                ),
+            (Return,
+                ),
+            (Diverge,
+                ),
+            (Goto,
+                if( !visited[e] )
+                    to_visit.push_back(e);
+                ),
+            (Panic,
+                ),
+            (If,
+                if( !visited[e.bb0] )
+                    to_visit.push_back(e.bb0);
+                if( !visited[e.bb1] )
+                    to_visit.push_back(e.bb1);
+                ),
+            (Switch,
+                for(auto& target : e.targets)
+                    if( !visited[target] )
+                        to_visit.push_back(target);
+                ),
+            (Call,
+                if( !visited[e.ret_block] )
+                    to_visit.push_back(e.ret_block);
+                if( !visited[e.panic_block] )
+                    to_visit.push_back(e.panic_block);
+                )
+            )
+        }
+        
+        ::std::vector<unsigned int> rewrite_table;
+        for(unsigned int i = 0, j = 0; i < fcn.blocks.size(); i ++)
+        {
+            if( visited[i] ) {
+                rewrite_table.push_back(j++);
+            }
+            else {
+                rewrite_table.push_back(~0u);
+            }
+        }
+        
+        auto it = fcn.blocks.begin();
+        for(unsigned int i = 0; i < visited.size(); i ++)
+        {
+            if( !visited[i] )
+            {
+                // Delete
+                DEBUG("GC bb" << i);
+                it = fcn.blocks.erase(it);
+            }
+            else
+            {
+                // Rewrite and advance
+                TU_MATCHA( (it->terminator), (e),
+                (Incomplete,
+                    ),
+                (Return,
+                    ),
+                (Diverge,
+                    ),
+                (Goto,
+                    e = rewrite_table[e];
+                    ),
+                (Panic,
+                    ),
+                (If,
+                    e.bb0 = rewrite_table[e.bb0];
+                    e.bb1 = rewrite_table[e.bb1];
+                    ),
+                (Switch,
+                    for(auto& target : e.targets)
+                        target = rewrite_table[target];
+                    ),
+                (Call,
+                    e.ret_block = rewrite_table[e.ret_block];
+                    e.panic_block = rewrite_table[e.panic_block];
+                    )
+                )
+                
+                ++it;
+            }
+        }
+    }
+    #endif
+}